howforge.com

Choosing e is very easy but finding d is not that simple. According to above formula, de = 1 + k(phi) is actually derived to below formula.

d = e^-1 mod phi

It is possible to compute d in straight forward approach; however, it might lead to incorrect value. For example, let p be 11 and q be 3. Consequently, n is 11*3 or 33 and phi is (11-1)(3-1) or 20. To make it more simple, we choose 3 as e because 3 is the smallest number which satisfygcd(3,20) = 1.

d = 3^-1 mod 20 = 0.33333333333333331

Oops! We are talking about integer. Otherwise, we may try to test each number e from 2 to n-1 such that de = 1 + k(phi). Wait a moment, we have another approach using GCD. This algorithm is called extended euclidean algorithm. Instead of giving only a GCD of given 2 numbers, EEA also gives x and y which satisfy below equation.

ax + by = gcd(a,b)

Actually, d = e^-1 mod phi is also known as modular inversion. Let's go to the detail.

• a = e
• b = phi
• (e)x + (phi)y = gcd(e,phi)
• (e)x + (phi)y = 1 where gcd(e,phi) = 1
• (e)x = 1 + (phi)(-y)

According to de = 1 + k(phi), d = x. Hooray! Now we have n = 33, e = 3 and d = 7 Let's go to encrypt a message m = 7.

c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13

In case of decryption, we use d and n.

m = c^d mod n = 13^7 mod 33 = 62748517 mod 33 = 7

It seems to be very easy because p, q, e and d are so small. Let's try p = 137 and q = 131. Using the same approach, we will have n = 17947, e = 681 and d = 3401. To encrypt a message m = 513, see below.

c = 513^681 mod 17947

I don't know how about other languages but Python can't handle this number.

>>> math.pow(513,681)
Traceback (most recent call last):
  File "", line 1, in 
OverflowError: math range error

Fortunately, we have the right-to-left binary algorithm.

def mod_exp(b,e,m):
    y = 1
    while e > 0:
        if e&1 == 1:
            y = (y*b)%m
        e = e>>1
        b = (b*b)%m
    return y

It works great. As a result, c = 513^681 mod 17947 = 650. However, e must be a positive integer. In case of p = 3037 and q = 131, we will have n = 4321651, e = 193 and d = -1207919. So encryption is still easy, e.g., m = 43.

c = m^e mod n = 43^193 mod 4321651 = 2511821

However, decryption is impossible because d is a negative integer.

m = c^d mod n = 2511821^-1207919 mod 4321651

Fortunately, we have GCD again. According to modular exponentiation, it is defined as follow.

c = b^e = d^|e| (mod m) where e<0 and bd = 1 (mod m)

So the trick is to find new d using GCD. Below is the modified version of mod_exp(b,e,m) to support negative e.

def mod_exp(b,e,m):
    if e < 0:
        c,x,y = extended_gcd(b,m)
        b,e = x,-e
    y = 1
    while e > 0:
        if e&1 == 1:
            y = (y*b)%m
        e = e>>1
        b = (b*b)%m
    return y

Tags: mathematics, rsa, python, euclidean, modular arithmetics