CoCalc Public FilesFinite Rings and Fields / polyRSA.sagewsOpen with one click!
Authors: Jesus Jimenez, michelle freed
Views : 35
Description: RSA polynomial
R = PolynomialRing(GF(2),'x') # GF(2) is the field Z mod 2 and R is the polynomial ring F_2[x]. x = R.gen() %typeset_mode True p = x^5+x^3+1 q = x^3+x+1 e=101 n=p*q S = R.quotient(n, 'a') a = S.gen() p q expand(n)
x5+x3+1\displaystyle x^{5} + x^{3} + 1
x3+x+1\displaystyle x^{3} + x + 1
x8+x5+x4+x+1\displaystyle x^{8} + x^{5} + x^{4} + x + 1
fiOfN=(2^5-1)*(2^3-1) fiOfN
217\displaystyle 217
M=1*a^7+(0*a^6)+(0*a^5)+(0*a^4)+(1*a^3)+(1*a^2)+(0*(a^1))+(1*(a^0)) M
a7+a3+a2+1\displaystyle a^{7} + a^{3} + a^{2} + 1
eM=M^e eM
a7+a5+a2\displaystyle a^{7} + a^{5} + a^{2}
d,u,v=xgcd(fiOfN,e) v
58\displaystyle -58
dM=eM^(v+fiOfN) dM M
a7+a3+a2+1\displaystyle a^{7} + a^{3} + a^{2} + 1
a7+a3+a2+1\displaystyle a^{7} + a^{3} + a^{2} + 1
numM=16346
lM=numM.digits(2) lM
[0\displaystyle 0, 1\displaystyle 1, 0\displaystyle 0, 1\displaystyle 1, 1\displaystyle 1, 0\displaystyle 0, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1]
c=lM[0] for i in range(len(lM)): c=c+lM[i]*a^i print(c)
a^6 + a^2 + a + 1
mYES=c mYES
a6+a2+a+1\displaystyle a^{6} + a^{2} + a + 1
enc=mYES^e enc
a7+a\displaystyle a^{7} + a
enc^(v+fiOfN)
a6+a2+a+1\displaystyle a^{6} + a^{2} + a + 1
a^fiOfN
1\displaystyle 1
C = c.lift()
C
x6+x2+x+1\displaystyle x^{6} + x^{2} + x + 1
C.coefficients(sparse=False)
[1\displaystyle 1, 1\displaystyle 1, 1\displaystyle 1, 0\displaystyle 0, 0\displaystyle 0, 0\displaystyle 0, 1\displaystyle 1]