RSA Encryption

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

RSA Encryption

Postby Snaek » Fri Mar 15, 2013 1:22 am

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, math
def 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.
Image
Snaek
 
Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

Re: RSA Encryption

Postby casevh » Fri Mar 15, 2013 4:38 am

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: 70
Joined: Sat Feb 09, 2013 7:35 am

Re: RSA Encryption

Postby Snaek » Fri Mar 15, 2013 3:57 pm

Nevermind, I got it to work.
Image
Snaek
 
Posts: 6
Joined: Thu Mar 14, 2013 1:15 am

Re: RSA Encryption

Postby Snaek » Sun Mar 17, 2013 6:55 pm

Btw, do you guys know of any other encryption methods that are good?
Image
Snaek
 
Posts: 6
Joined: Thu Mar 14, 2013 1:15 am


Return to General Coding Help

Who is online

Users browsing this forum: micseydel, Yoriz and 4 guests