Why is my RSA Implementation in Python not working?

Question

For learning purposes I am trying to implement RSA Public-Key Cryptography in Python. I already took some looks at sample code and searched trough whole stackoverflow trying to find an answer.

My implementation is not working correctly and i have no clue why.

I can easily generate a Public- and Private key. When i use the public key for encryption i get something like

16102208556492

Which, i think, looks correct. When i now try to decrypt the ciphertext it gives me random ASCII symbols. So i thought decryption must be wrong but it also looks quite good.

Since days i am trying to find the miscalculation!

All I started with are the mathematical algorithms from the book "Guide to Elliptic Curve Cryptography" by Darrel Hankerson, Alfred Menezes and Scott Vanstone.

Algorithm 1.1: RSA key pair Generation

INPUT: Security parameter l
OUTPUT: RSA public key e, private key d and n
1. Randomly select two primes p and q with same bitlength l/2
2. Compute n = pq and phi = (p-1)(q-1)
3. Select an arbitrary integer e with 1 < e < phi and gcd(e, phi)==1
4. Compute the integer d satisfying 1 < d < phi and ed == 1 mod phi
5. Return(n, e, d)

Algorithm 1.2: Basic RSA encryption

INPUT: RSA public key e, n, plaintext m
OUTPUT: Ciphertext c
1. Compute c = m**e mod n
2. Return(c)

Algorithm 1.3: Basic RSA decryption

INPUT: RSA private d, n, ciphertext c
OUTPUT: Plaintext m
1. Compute m = c**d mod n
2. Return(m)

I understand how it works mathematically so I implemented it like this:

Algorithm 1.1 in Python

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, n)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

Algorithm 1.2 in Python

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

Algorithm 1.3 in Python

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

It does not seem to be very wrong what i am coding here, but anyway either here or in the other functions must be something wrong.

Here is my full python code

# RSA

# Imports
import random

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d satisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, n)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

def mrt(odd_int):
    odd_int = int(odd_int)
    rng = odd_int - 2
    n1 = odd_int - 1
    _a = [i for i in range(2,rng)]
    a = random.choice(_a)
    d = n1 >> 1
    j = 1
    while((d&1)==0):
        d = d >> 1
        j += 1
    t = a
    p = a
    while(d>0):
        d = d>>1
        p = p*p % odd_int
        if(d&1):
            t = t*p % odd_int
    if(t == 1 or t == n1):
        return True
    for i in range(1,j):
        t = t*t % odd_int
        if(t==n1):
            return True
        if(t<=1):
            break
    return False

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def Randomly_Select_Prime_w_Bitlength(l):
    prime = random.getrandbits(int(l))
    if (prime % 2 == 1):
        if (mrt(prime)):
            return prime
    return Randomly_Select_Prime_w_Bitlength(l)

def Arbitrary_Int_e(phi):
    _e = [i for i in range(1, phi)]
    e = random.choice(_e)
    if(gcd(e, phi) == 1 % phi):
        return e
    return Arbitrary_Int_e(phi)

def inverse(e, phi):
    a, b, u = 0, phi, 1
    while(e > 0):
        q = b // e
        e, a, b, u = b % e, u, e, a-q*u
    if (b == 1):
        return a % phi
    else:
        print("Must be coprime!")    

Answer 1

As Marek Klein stated out in his comment I called the "inverse()" function with wrong parameters. It was d = inverse(e, n) instead of d = inverse(e, phi).

But also from logical point of view, n is public, e is public, thus if that worked anyone can compute d that is supposed to be private.

Also squeamish ossifrage pointed out that

The function Randomly_Select_Prime_w_Bitlength() often produces numbers with fewer bits than required, and sometimes produces a runtime error (because odd_int is too small in mrt()). If p and q are too small, you won't be able to encrypt as many bits of data as expected.

Randomly_Select_Prime_w_Bitlength() is now covering a check if the random prime is larger then 3 so it cannot return a Runtime-Error by going smaller then possible.

Here is the corrected code:

# RSA 

# Imports
import random

# INPUT: Secure parameter l
def Generation(l):
    # Randomly select 2 primes with same Bitlength l/2
    p = Randomly_Select_Prime_w_Bitlength(l/2)
    q = Randomly_Select_Prime_w_Bitlength(l/2)
    # Compute
    n = p * q
    phi = (p - 1) * (q - 1)
    # Select an arbitrary integer e with 1 < e < phi and gcd(e,phi) == 1
    e = int(Arbitrary_Int_e(phi))
    # Compute the integer d statisfying 1 < d < phi and e*d == 1 % phi
    d = inverse(e, phi)
    # Return n e d
    print("Public Key: " + str(e))
    print("Private Key: " + str(d))
    print("n = " + str(n))

# INPUT: RSA public key e, n, message m
def Encryption(e, n, m):
    c = [pow(ord(char),e,n) for char in m]
    print(''.join(map(lambda x: str(x), c)))
    return c

# INPUT: RSA private key d, n, ciphertext c
def Decryption(d, n, c):
    m =  [chr(pow(char, d, n)) for char in c]
    print(''.join(m))
    return ''.join(m)

def mrt(odd_int):
    odd_int = int(odd_int)
    rng = odd_int - 2
    n1 = odd_int - 1
    _a = [i for i in range(2,rng)]
    a = random.choice(_a)
    d = n1 >> 1
    j = 1
    while((d&1)==0):
        d = d >> 1
        j += 1
    t = a
    p = a
    while(d>0):
        d = d>>1
        p = p*p % odd_int
        if(d&1):
            t = t*p % odd_int
    if(t == 1 or t == n1):
        return True
    for i in range(1,j):
        t = t*t % odd_int
        if(t==n1):
            return True
        if(t<=1):
            break
    return False

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def Randomly_Select_Prime_w_Bitlength(l):
    prime = random.getrandbits(int(l))
    if (prime % 2 == 1 and prime > 3):
        if (mrt(prime)):
            return prime
    return Randomly_Select_Prime_w_Bitlength(l)

def Arbitrary_Int_e(phi):
    _e = [i for i in range(1, phi)]
    e = random.choice(_e)
    if(gcd(e, phi) == 1 % phi):
        return e
    return Arbitrary_Int_e(phi)

def inverse(e, phi):
    a, b, u = 0, phi, 1
    while(e > 0):
        q = b // e
        e, a, b, u = b % e, u, e, a-q*u
    if (b == 1):
        return a % phi
    else:
        print("Must be coprime!")    

Answer 2

There is an easier method to implement RSA in python:

bits = 2048 # the bit length of the rsa key, must be multiple of 256 and >= 1024
E = 65537 # (default) the encryption exponent to be used [int]
from Crypto.PublicKey import RSA
key = RSA.generate(bits,E)
with open('my_key.pem','w') as file:
    file.write(key.exportKey())
    file.write(key.publickey().exportKey())

Use of Crypto.PublicKey requires (in windows CMD or mac TERMINAL):

pip install pycrypto

for some systems running python 3 (like mine):

pip3 install pycrypto

Both public key (modulus + encryption exponent) and private key (decryption exponent) are in base64 format, to convert to hexadecimal for other use:

from base64 import b64decode
base64_string = 'AAAAbbbb123456=='
hex_string = b64decode(base64string).hex()

Two keys generated within a short time between each other may have their most significant digits equal:

MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCpLVejQvo2xJwx04Oo2qotAge9 wWQDsk62hb0ua8r9+VM837+cArMStt9BoSTOCmNz7cYUXzGjQUsUi7tnHXM+Ddec EG7J3q/w12ox2QN3wTndsW+GO9BD2EHY674t8A3JLSJP/bcD/FGBtjzytyd5hmQJ Fife8rr4sAMkTXwoIwIDAQAB and (~10 seconds between each other) MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCz9un7Xq248zlmkwVuXze2tUMy a30BaodLJXYuAktGuiMAFwpprql0N9T06HdiphZmr+hT45gG57ZOlJn/yzN4U30Q DXevDVapq6aYJ/Q21CO2bkLkMjEMy5D4IdwMeBgK+5pJFYETB6TzLfDkEcTQMr++ f7EHosWd0iBGm01cKQIDAQAB