0

I'm a newbie in programming. I have to write an RSA algorithm in python (it's my project I am doing on my studies). I supose I've got a problem with modular inverse algorithm? I have tested my app and it seems to work not exactly as I wanted to. I tested it for small primes like 11 and 13 and it seems that the app have a problem with modular inverse algorithm. I also tried an algorithm from wikibooks, but it doesn't work for large primes (ex. 1028-bit numbers) - there's too much calculations. Maybe some of you have idea how to fic it and why it doesn't work properly? Thank you for your time.

Oh and I also noticed that my algorithm mixes up private and publickey.

ex1. p 11 q 13 d 1 e 29 n 143 euler f 120

ex2. p 11 q 13 d 49 e 73 n 143 euler f 120

Here you are, p and q are primes. Here's the code:

 import random
 import sys
 import fractions


 def FermatTest(a,p):
    probablyprime=pow(a,p-1,p)
     if probablyprime==1:
         return True
     else:
         return False

 def MillerRabinTest(n, k):
     r, s = 0, n - 1
     while s % 2 == 0:
         r += 1
         s //= 2
     for _ in range(k):
         a = random.randrange(2, n - 1)
         x = pow(a, s, n)
         if x == 1 or x == n - 1:
             continue
         for _ in range(r - 1):
             x = pow(x, 2, n)
             if x == n - 1:
                 break
         else:
             return False
     return True

 def EuclidForRelativePrime(p,keylength):   
     while True:    
         k=random.randrange(3,p-1)
         if fractions.gcd(p,k)==1:
                 break
     return k

 def ModInv(e,euler_function):
     d=pow(e,euler_function-2,euler_function)
     return d


 def GenPrime(key_length):
     while True:
         p=random.getrandbits(key_length)
         if FermatTest(2,p)==True and MillerRabinTest(p,10)==True:
                 break
     return p


 key_length=int(input('Podaj dlugosc klucza RSA [w bitach]:'))
 private_key_file=input('Podaj nazwę dla nowej pary kluczy: ')
 public_key_file=str((private_key_file+'.pub'))
 q=GenPrime(key_length)
 r=GenPrime(key_length)
 euler_function=(q-1)*(r-1)
 n=q*r
 q=0
 r=0
 e=EuclidForRelativePrime(euler_function,key_length)
 d=ModInv(e,euler_function)

 #public_key=(e,n)
 #private_key=(d,n)

 target1=open(private_key_file,'w')
 target1.write(str(d))
 target1.write('\n')
 target1.write(str(n))

 target=open(public_key_file,'w')
 target.write(str(e))
 target.write('\n')
 target.write(str(n))
Aniadka
  • 17
  • 2
  • Hmmm... no. Fisrt of all I am testing my numbers with Fermat test and Miller-Rabin test. I also tried for 11 and 13 and the result was the same. Makes no sense. – Aniadka Jan 25 '16 at 23:05
  • As the [first answer](http://stackoverflow.com/a/12519619/1816580) to the question I linked to says, the modulus must be a prime to use that trick. `euler_function` is not a prime, so you can't use that formula and must use the extended euclidean algorithm to calculate the inverse, which is provided in the [second answer](http://stackoverflow.com/a/12538744/1816580). This is a very good duplicate. You should be able to see a button above your question to confirm the duplicate. – Artjom B. Jan 25 '16 at 23:07

0 Answers0