RSA kryptering med Montgomerys algoritme

[Dr_VingTor]

Holder på med et prosjekt hvor RSA kryptering skal lages. Skal lage dette i hardware (VHDL), men for å finne ut hvordan ting virker (skal virke) så holder jeg nå på å lage det i et annet språk nå (bruker Python).

 

det som skal regnes ut er: M = C^d mod n (RSA kryptering)

 

#RSA dekryptering/krypterings algoritme
def RL_Binary_method(C,d,n):
   M = 1
   P = C
   bussbredde = 8
   for i in xrange(0,bussbredde-1): #altsaa bit 0..6 (av 0..7)
       if getBitValue(d,i): 
           M = (M*P)%n    
       P = (P*P)%n
       
   if getBitValue(d,bussbredde-1): #og her tar vi bit 7 (av 0..7)
       M = (M*P)%n
   return M

#metode for å hente ut et bit fra et tall
def getBitValue(n, p):
   return (n >> p) & 1

 

Denne koden virker, men det jeg vil gjøre er å bytte ut (A*B)%n, dvs. A*B mod n, med Montgomerys algoritme, da den er egnet når en skal realisere dette i hardware, problemet mitt er at jeg ikke får det til å virke når jeg gjør det. Har funnet flere eksempler på algoritmen, men har ikke fått noen av de til å virke, så det jeg lurer på er om noen har eksempler med denne algoritmen og eventuelt kan gi noen inspill på hvilke endringer som eventuelt må gjøres i koden over.

 

for testing har jeg brukt:

d = 113

n = 143

C = 85

og en skal da få at M = 50

[Dr_VingTor]

har kommet litt lengre nå, fant at jeg hadde glemt noe som måtte leges til når en skulle bruke Montgomerys algoritme, og har fått noen av de til å virke nå (en som er omtalt som "Montgomerys multiplication" og en som er omtalt som "fast Montgomerys multiplication"), men sliter fremdeles med den jeg vil bruke som heter "faster Montgomerys multiplication" se side 20 i http://www.crypto.ruhr-uni-bochum.de/imper...manorthesis.pdf

 

noen som ser feilen?

 

def Mon_Mul_3(A,B,n): #alg3 Faster Mont. mul.
   bussbredde = 8
   #compute Mon_Mul_3(A,B,n) = A*B*r^(-1) mod n  ( r = 2**bussbredde)
   #inputs A,B,n; 0<A,B<n
   #outputs P = (A*B*(2**bussbredde)**-1) mod n
   S = 0
   C = 0
   I = 0
   R = B+n    
   for i in xrange(0,bussbredde):
       if (getBitValue(S,0)==getBitValue(C,0)) and not getBitValue(A,0):
           I = 0
       if (getBitValue(S,0)!=getBitValue(C,0)) and not getBitValue(A,0):
           I = n
       if not((getBitValue(S,0))^(getBitValue(C,0))^(getBitValue(B,0))) and getBitValue(A,0):
           I = B
       if ((getBitValue(S,0))^(getBitValue(C,0))^(getBitValue(B,0))) and getBitValue(A,0):
           I = R
       #S,C = S+C+I #with csa
       temp = S^C^I
       temp2 = ((S&C)|(S&I)|(C&I))*2
       S = temp
       C = temp2
       #end csa
       S = S/2
       C = C/2
   P = S+C
   if P >= n:
       P = P - n
   
   return P

 

og for det som er litt kryptisk ut der inne; csa = carry save adder, og den kodedelen virker (den har jeg testet og brukt i andre deler hvor den gir rett svar)

Endret 22. september 2006 av Dr_VingTor