Testing RSA in Python

Question

I created a small code for testing RSA, but when I try to decrypt a message with keys that are 6-7 digit long, it takes a while and gives me the wrong result.

from math import sqrt


def isPrime(n):
    x = int(sqrt(n)) + 1

    if n < 2:
        return False`

    for i in range(2, x):
        if (n / i).is_integer():
            return (i, False

    return True


def factor(num):
    hold = list()
    inum = int(sqrt(num) + 1)

    hold.append((1, num))
    if num % 2 == 0: hold.append((2, int(num / 2)))

    for i in range(3, inum, 2):
        x = num / i

        if x.is_integer():
            hold.append((i, int(x)))

    return hold


def egcd(a, b):
    #Extended Euclidean Algorithm
    x,y, u,v = 0,1, 1,0

    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b

    return y


def fastMod(n, e):
    if e == 0:
        return 1

    if e % 2 == 1:
        return n * fastMod(n, e - 1)

    p = fastMod(n, e / 2)
    return p * p


def decrypt(p, q, em):
    #Uses CRT for decrypting
    mp = em % p; mq = em % q;
    dp = d % (p-1); dq = d % (q-1);
    xp = fastMod(mp, dp) % p; xq = fastMod(mq, dq) % q

    log = egcd(p, q)
    cp = (p-log) if log > 0 else (p+log)
    cq = cp

    m = (((q*cp)*xp) + ((p*cq)*xq)) % n

    return m


def encrypt(pm):
    return fastMod(pm, e) % n

Is there any way to improve speed or fix any errors? I try to decrypt a few messages I made with a key 9-10 digits long, but it takes too long.

You can replace fastMod(x, y) % z with Python's built-in function pow(x,y,z). — r3mainer
– r3mainer, Commented Aug 2, 2017 at 7:53

TheGreatContini · Accepted Answer · 2017-08-02 03:19:27Z

A lot of things need improvement, but most notably:

For RSA encryption/decryption: fastMod( ) should take the modulus as an input parameter, and reduce by the modulus each iteration. I found this code which illustrates the right way to do it.
For parameter generation: In practice, one could never use a function like your isPrime( ) to determine primality because it runs in exponential time. Instead, you should be doing Miller-Rabin / Strong pseudo prime tests, which can use fastMod( ) as a sub-routine.

By the way, you are implementing textbook RSA here, which is hugely insecure. You would need to use padding such as OAEP to have security, but you need to be very careful on how you implement that to prevent various forms of attacks (such as side channel attacks).

As for why you are getting the wrong result, it is hard to tell without seeing all of your code. Maybe you want to include a main function that generates params and tries to use them for encryption and decryption.

EDIT: I did notice this which looks suspicious: log = egcd(p, q). Not sure what you are doing here. I suggest you first compute d as the inverse of e mod (p-1)*(q-1) and verify that you are getting that correct (ie multiply d*e mod (p-1)*(q-1) and make sure the result is 1). If so, then do a fastMod( ) with d to see if it decrypts (it should). Once you get that working, then move on to making CRT work.

Collectives™ on Stack Overflow

Testing RSA in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related