Implementing RSA (not for practical use): Is there a limit to what numbers can be computed by Python (OR) Any other programming language?

53 views Asked by At

I was given an assignment at Uni where we were asked to implement RSA on the programming language of our choice. I chose Python to implement it and I did successfully implement it.

However, it works only with smaller numbers and starts falling apart when using bigger numbers.

Here is the code that computes the powers using the square and multiply algorithm.

def power_mod(num, power, mod):
    res = 1
    binary = bin(power)[2:]
    for digit in binary:
        if(digit == "0"):
            res = (res*res) % mod
        else:
            res = (res*res*num) % mod
    return res

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

def are_coprime(x, y):
    return gcd(x, y) == 1

def inverse(num, mod):
    if(are_coprime(num, mod) == 0):
        return -1 
    Q = 0
    R = 0
    T1 = T = 0
    T2 = 1
    A = mod
    B = num
    while(True):
        if(B!=0): 
            Q = A//B
        else: break
        R = A % B
        T = T1 - (T2*Q)
        A = B
        B = R
        T1 = T2
        T2 = T
    if(T1 > 0):
        return T1
    return T1 + mod

p = 797    # Arbitrary choice
q = 979    # Arbitrary choice
N = p*q
Phi = (p-1)*(q-1)
e = 31     # Arbitrary choice
d = inverse(e, Phi)

value = 2
x  = power_mod(value, e, N)
print("\"Encrypted\" value: " + str(x))
y = power_mod(x, d, N)
print("\"Decrypted\" value: " + str(y))

Which produces the output:

"Encrypted" value: 199872
"Decrypted" value: 235914

When it should, in theory return "2" as the Decrypted value. However, the same code works for smaller values of p and q - such as 79 and 97. This led me to search for RSA calculators online to see if it was just my code that was problematic. I stumbled upon this one and it too started falling apart when using bigger numbers.

This has me questioning if computers can really handle numbers of that size. If they can't handle numbers that size, then how do hardware implementations efficiently compute RSA keys that are thousands of bits long?

0

There are 0 answers