## RSA Encryption

This is the place for queries that don't fit in any of the other categories.

### RSA Encryption

Hello, I am having trouble with RSA Encryption. If you test the code, the decryption process will not be correct.

Code: Select all
`import random, mathdef encrypt():    message = input("Enter message to encrypt: ")    myl = []    for x in message:        myl.append(ord(x))        primeNums = []    for x in range(2,100):        for y in range(2,x):            if x%y == 0:                break        else:            primeNums.append(x)    p = primeNums[random.randint(0,len(primeNums)-1)]    q = primeNums[random.randint(0,len(primeNums)-1)]    N = p*q    f = (p-1)*(q-1)    for e in range(2,f):        for h in range(2,e):            if e%h == 0:                break        else:            if f%e == 1:                break    print("Public Key 1:",N)    print("Public Key 2:",e)    for a in myl:        C = (a**e)%N        print(C,end=" ")def decrypt():    N = eval(input("Enter public key 1: "))    e = eval(input("Enter public key 2: "))    message = input("Enter message to decrypt: ")    message = message.split()        for q in range(2,int(math.floor(math.sqrt(N)))+1):        for a in range(2,q+1):            for b in range(2,a):                if a%b == 0:                    break            else:                if a == q:                    p = N//q                    if p*q == N:                        break    f = (p-1)*(q-1)    d = 0    x = 1    while True:        if (e*x)%f == 1:            d = x            break        x += 1    for g in message:        decryption = (int(g)**d)%N        print(chr(decryption),end="")`

You can refer to: http://mathcircle.berkeley.edu/BMC3/rsa/node4.html to learn more about RSA encryption, I have used pretty much the same variable names and everything.
Snaek

Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

### Re: RSA Encryption

The code you posted doesn't run "as-is" nor did you include the results of your test.

I think you are missing one of the key principals behind RSA encryption. To create an instance of the RSA algorithm, you need to create two keys: (N,e), which is the encryption key, and (N,d), which is the decryption key. (N,e) is published to the world while (N,d) is kept secret.

d and e are related by the formula ed=1 mod( (p-1)*(q-1) ) where p, q are prime and N=p*q. The security of RSA depends entirely on the difficulty of find p, q when you are given N. Your decrypt function actually factors N which is impossible for realistic values of N.

You should write a function called create_keys() that returns two tuples: (N,e) and (N,d). The first tuple should be used encrypt() and the second tuple should be used in decrypt().

For test values, assume p=101 and q=103. Pick e=7. Is e relatively prime to (p-1)(q-1)? (It is, but 5 isn't.) Now calculate d. (The answer is 8743.)

Hint: in one of my answers to your other question, I mentioned the extended GCD algorithm. GCD and then extended GCD are the first two helper functions you should implement.

casevh
casevh

Posts: 114
Joined: Sat Feb 09, 2013 7:35 am

### Re: RSA Encryption

Nevermind, I got it to work.
Snaek

Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

### Re: RSA Encryption

Btw, do you guys know of any other encryption methods that are good?
Snaek

Posts: 6
Joined: Thu Mar 14, 2013 1:15 am