Python RSA Brute Force Check

Question

I have an exercise to brute force a piece of text that has been encrypted with a very small key. The public key I have is (e = 5, n = 203). The text has been converted to ASCII, shifted a fixed number and then encrypted with the RSA public key. I have to decrypt this text using brute force only. To decrypt I'm using the simple formula of:

decrypt = (value**d)%n

Where value is the thing I want to decrypt, d being the value I am unsure of and n being the modulus.

So far I have put the numbers in a tuple called en and I loop through it like this:

for i in range(1,10):   
    for a in range(0,41):
       ans = (en[a]**i)%203
       print (chr(ans))

The first for loop is "d" the private key value I am not sure of and the second for loop is for going through the 41 length tuple. I don't have the block shift part implemented yet but I want to check if this is the correct way of brute forcing a simple RSA key.

Answer 1

I took the liberty to improve on L3viathan's answer and provide a full working source ready to copy paste and run:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def factor(n):
    for i in range(3, n):
        if n%i == 0:
            return i

e = 5
n = 203

p = factor(n)
q = n//p
phi_n = (p-1) * (q-1)

# Only for python >= 3.8
# From https://docs.python.org/3/library/functions.html#pow
# If mod is present and exp is negative, base must be relatively prime to mod.
# In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.
# d_crack = pow(e, -1, phi_n)

# python < 3.8
d_crack = modinv(e, phi_n)

print('cracked d:', d_crack) # prints "cracked d: 101"

Answer 2

You should try to factor n by brute force:

for i in range(n):
    if n%i == 0:
        print i

, from which you will find p=7 and q=29.

d = e^-1 mod phi(n) = e^-1 mod (p-1)*(q-1)

therefore d = e^-1 mod 168, ergo d=162.