RSA encryption implemented in Python

Question

The past days I have been trying to implement an RSA algorithm in Python. My code worked fine for smaller prime numbers (at least up to the first million primes). However, when trying to use the 49 millionth to 50 millionth, my code broke down and gave wrong results.

For example, when using the primes 11 and 17 as starting primes, I get the following keys: public: (3,187) and private: (107,187). Using this to encrypt the number 50, the ciphertext is 84, which then decrypts back to 50.

However when using the primes 961752619 and 961752931 to encrypt the number 50 I get 781250000000, which when decrypted gives 482883073917854018.

I have tried the first 50000 numbers using the latter pair of primes and none have returned the correct value. Obviously something is going wrong here but I have no clue what. I have included a pastebin link to my code, and I have pasted the code below the post as well.

def gcd(a, b):
    if b > a:
        if b % a == 0:
            return a
        else:
            return gcd(b % a, a)
    else:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)

def find_d(phi_n,e):
    k = 1
    mod0 = False
    while not mod0:
        d = (k*phi_n+1)/e
        if(d % 1 == 0):
            return d
        k+=1

def find_e(phi_n):
    e = 3
    while True:
        if not gcd(e,phi_n) == 1:
            e+=2
        else:
            return e

def generate_keys(p1,p2):
    n = p1*p2
    phi_n = (p1-1)*(p2-1)
    e = find_e(phi_n)
    d = int(find_d(phi_n,e))
    return ((e,n),(d,n))

def endecrypt(key,m):
    return pow(m,key[0],key[1])

score 2 · Accepted Answer · answered Jun 25 '18 at 20:29

Assuming that you're using Python 3, in which division always returns a float, the problem lies in find_d(). The expression (k*phi_n+1)/e converts arbitrary-precision integers to limited-precision floats, and this is where the inaccuracy comes in. If you want to test whether k*phi_n+1 is evenly divisible by e and return the quotient if so, you should instead write:

if (k*phi_n+1) % e == 0:
    return (k*phi_n+1) // e  # Note use of integer division

or, slightly more efficiently with divmod():

d, rem = divmd(k*phi_n+1, e)
if rem == 0:
    return d

RSA encryption implemented in Python

1 Answers1