Working RSA

2199 days ago by haynef

MATH 2500

Hayne Floyd

RSA Homework

The my_div(a,b) function from the previous homeowkr.

Returns a list [q,r] where a=bq+r.
def my_div(a,b): #check that b is nonzero if b<=0: return 'Error, b must be greater than 0' #check that a and b are integers if not(a in ZZ) or not(b in ZZ): return 'Error, a and b must both be integers' #special case when a=0 if a==0: return [0,0] if a<b: return[-1,a] #a is positive elif a>0: #copy the values of a and b k=copy(b) r=copy(a) #find 2^n *b <a while 2*k<=a: k=k*2 #r=r-2^n * b r=r-k #continuously divide (2^n * b) by 2 while k/2 in ZZ and k/2>=b: k=k/2 #if it is small enough if k<=r: #change value of r r=r-k #q=(a-r)/b r=a-bq return [(a-r)/b,r] #a is negative #similar as above except working the opposite direction else: k=-copy(b) r=copy(a) while 2*k>=a: k=k*2 r=r-k while k/2 in ZZ and k/2<=b: k=k/2 if k>=r: r=r-k return[ZZ((a-r)/b),ZZ(abs(r))] 
       

The my_gcd(a,b) function from the previous homeowkr. It returns

 [d,m,n] where d=gcd(a,b) and am+bn=d.
def my_gcd(a,b): #check that a or b is nonzero if a==0 or b==0: return 'Error, either a or b must b nonzer' i=copy(a) j=copy(b) if j>i: temp=i i=j j=temp #Starting matrix M=matrix(2,2,[1,0,0,1]) #loop until the remainder is zero while my_div(i,j)[1]>0: #set k=mod(i,j) k=my_div(i,j)[0] #set i=j and j=mod(i,j) temp=j j=my_div(i,j)[1] i=temp #use matrices to calculate m and n A= matrix(2,2,[0,1,1,-k]) M=M*A #one more matrix multiplication needed M=M*matrix(2,2,[0,1,1,-(my_div(i,j)[0])]) #return [gcd(a,b),m,n] #return j return [j,M[0][0],M[1][0]] 
       

Calculate two 100 digit primes p,q.
p=random_prime(10^100) print 'p= ',p 
        
p= 
892865435574141139887424433109814969279259831981891329430982083149285096\
754369120652734342979229193
p=  892865435574141139887424433109814969279259831981891329430982083149285096754369120652734342979229193
q=random_prime(10^100) print 'q= ',q 
        
q= 
970848498221124871309703769944431020918532114012241612565856315340880242\
5461848399836595379103448623
q=  9708484982211248713097037699444310209185321140122416125658563153408802425461848399836595379103448623

Multiply p and q together to get m.

Rm will be a function that takes an integer, x, and 

translates it into an integer in the ring of integers modulo M.
m=p*q print 'm= ',m Rm=Zmod(m) 
        
m= 
866837067240705447837928461916953019099589075418114660803908716686180587\
350932511186571525715755210017710467435466525141283604808897916154247261\
5236002721908657490098499187857382471811710124617251239
m=  8668370672407054478379284619169530190995890754181146608039087166861805873509325111865715257157552100177104674354665251412836048088979161542472615236002721908657490098499187857382471811710124617251239

Calculate phi = (p-1)(q-1)
phi=(p-1)*(q-1) print 'phi= ',phi 
        
phi= 
866837067240705447837928461916953019099589075418114660803908716686180587\
350932511186571525715755208957575425656927539842837391553485398307789164\
3131695266819112253540411665641164951322380402534573424
phi=  8668370672407054478379284619169530190995890754181146608039087166861805873509325111865715257157552089575754256569275398428373915534853983077891643131695266819112253540411665641164951322380402534573424

My CUID is C65099899.  We take the number, 65099899

and calculate its equivalence in the ring of integers modulo m.
ID=65099899 message=Rm(ID) print message 
        
65099899
65099899

Here we must find an integer, e, such that 

gcd(e,phi) = 1.  In this case 1<=e<=10000000.

This allows the later calculations to run in real time.
j=1 k=10^100 e=int(random()*(k))+j while my_gcd(e,phi)[0]>1: e=int(random()*(k))+j print 'e= ',e 
        
e= 
154290553236243076694946471381992707055497449259524227623383816536659562\
3027934305811724028444934145
e=  1542905532362430766949464713819927070554974492595242276233838165366595623027934305811724028444934145

The RSA algorithm works by taking the message and raising it to the e power.

This gives us the secure encrypted message that can only be decrypted by those

who know d, whic can be found by solving d*e + phi*m = 1 = gcd(e,phi).
encryp=message^e print 'Encrypted message: ', encryp 
        
Encrypted message: 
186703877856401638759986877690775226640561078094659057387825313002605353\
483167229778667494388237522115346921195663031662548792788529347938855232\
1889543554712669965154737924504783064902569916077055436
Encrypted message:  1867038778564016387599868776907752266405610780946590573878253130026053534831672297786674943882375221153469211956630316625487927885293479388552321889543554712669965154737924504783064902569916077055436

To decrypt the message, we take the d, found as explained above, and raise 

the decrypted message to the d power. This gives us our original message, my CUID.
d=my_gcd(e,phi)[2] decryp=encryp^d print 'Decrypted message: ',decryp 
        
Decrypted message:  65099899
Decrypted message:  65099899