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

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.