CODEWITHSUNDEEP
pythonencryptioncryptography
ICan'tDraw
ICan'tDraw

Reputation: 3

Testing RSA in Python

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.

Upvotes: 0

Views: 506

Answers (1)

TheGreatContini
TheGreatContini

Reputation: 6629

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.

Upvotes: 1

Related Questions