Question $4.$ Alice sends a reply to Bob, encrypted as e$2$ in the data file, but

Bob's public key is not as well configured as Alice's public key. We will play

the role of Eve, and break Bob's key. First, load Bob's public key into memory.

This will clear Alice's public key $-$ make sure you have the right key loaded

into the memory! Create the NTRU lattice matrix via $M=$ NTRUmatrix $(h)$

and then reduce it via LLL: $L=M.LLL().$

####################### FUNCTIONS #######################

### You can safely run this entire block at any point ###

### until you see the next block begin below. ###

def T$($d$1,$d$2,$N$)$:

$"""$

Returns a random ternary polynomial in ZZ$[$z$]$ with:

d$1$ coefficients that equal $+1$

d$2$ coefficients that equal $-1$

$"""$

if d$1+$ d$2>$ N:

raise$($ValueError$,"$d$1+$ d$2$ cannot exceed N$")$

R$.=$ PolynomialRing$($ZZ$)$

S $=$ Set$($range$($N$+1))$

pos $=$ S$.$subsets$($size$=$d$1).$random$\_$element$()$

S$2=$ S $-$ pos

neg $=$ S$2.$subsets$($size$=$d$2).$random$\_$element$()$

v $=[0$ for i in range$($N$+1)]$

for i in pos:

v$[$i$]=1$

for i in neg:

v$[$i$]=-1$

return R$($v$)$

def centerlift$($f$)$:

R$.=$ PolynomialRing$($ZZ$)$

P $=$ f$.$parent$().$base$\_$ring$().$cardinality$()$

return R$([$ mod$($t$,$ P$).$lift$\_$centered$()$ for t in f$])$

def encode$($s$)$:

$"""$

Encode the message ASCII string s as a polynomial m$($x$)$ in R$\_$p$.$

Uses environment variables p and N$.$

$"""$

s $=$ str$($s$)$

k $=$ N$*$log$($p$,128)$

if len$($s$)>=$ k:

raise$($ValueError$,$ "String too long. Max length in R$\_$p is $"+$ str$($floor$($k$)))$

t $=$ sum$($ord$($s$[$i$])*128^$i for i in range$($len$($s$)))$

return Rp$($t$.$digits$($base$=$p$))$

def decode$($m$)$:

$"""$

Decode the polynomial m$($x$)$ in R$\_$p$.$

$"""$

mc $=$ list$($m$)$

# Remember, mc$[$i$]$ belongs to GF$($p$).$ Lift to integers!

c $=$ sum$($Integer$($mc$[$i$])*$p$^$i for i in range$($len$($mc$)))$

v $=\text{'}\text{'}.$join$([$ chr$($x$)$ for x in Integer$($c$).$digits$($base$=128)])$

return v

def circulantmatrix$($a$)$:

$"""$

Returns the matrix whose ROWS are the rotations of the vector a:

$($ a$[0]$ a$[1]...$ a$[$n$-1])$

$($ a$[$n$-1]$ a$[0]...$ a$[$n$-2])$

$(......)$

$($ a$[1]$ a$[2]...$ a$[0])$

$"""$

n $=$ len$($a$)$

R $=$ range$($n$)$

return matrix$([[$ a$[($j$-$k$)\%$ n $]$ for j in R $]$ for k in R $])$

def NTRUmatrix$($h$)$:

$"""$

Returns the NTRU lattice matrix associated to the public key

$($N$,$p$,$q$,$d$)$ and h$($y$)$ in R$\_$q$,$ in row form.

This matrix is$,$ in ROW form, the $2$N x $2$N block matrix:

$($ I H $)$

$(0$ qI $)$

where H is the circulant matrix generated by the coefficients of h

as a vector.

$"""$

hv $=$ list$($centerlift$($h$))$

H $=$ circulantmatrix$($hv$)$

I $=$ identity$\_$matrix$($ZZ$,$ N$)$

O $=$ zero$\_$matrix$($ZZ$,$ N$)$

return block$\_$matrix$([[$I$,$ H$],[$O$,$ q$*$I$]])$

### End of functions block ###

###################################################

#################### PROBLEMS $2$ onwards ####################

#################### Alice's public key ####################

p $=723829$

q $=414165413$

N $=151$

d $=30$

R$.=$ PolynomialRing$($ZZ$)$

Sp$.=$ PolynomialRing$($GF$($p$))$

Rp$.=$ Sp$.$quotient$($Y$^$N $-1)$

Sq$.=$ PolynomialRing$($GF$($q$))$

Rq$.=$ Sq$.$quotient$($Z$^$N $-1)$

h $=292154189*$z$^150+301473751*$z$^149+7992279*$z$^148+256274577*$z$^147+138291792*$z$^146+213244800*$z$^145+66018664*$z$^144+216541653*$z$^143+365219395*$z$^142+82857950*$z$^141+128660538*$z$^140+293420876*$z$^139+73203043*$z$^138+260799189*$z$^137+359907246*$z$^136+349417304*$z$^135+102642608*$z$^134+118603125*$z$^133+409669254*$z$^132+94999973*$z$^131+11465625*$z$^130+228101539*$z$^129+109606852*$z$^128+83282299*$z$^127+398988836*$z$^126+42736600*$z$^125+48009769*$z$^124+188832192*$z$^123+75400492*$z$^122+238286103*$z$^121+27338506*$z$^120+21309908*$z$^119+109080944*$z$^118+75580822*$z$^117+370783439*$z$^116+64338600*$z$^115+140857785*$z$^114+197109864*$z$^113+239817418*$z$^112+384329482*$z$^111+329530957*$z$^110+77994009*$z$^109+290136702*$z$^108+167993379*$z$^107+36697370*$z$^106+97650871*$z