encryption : RSA algorithm

Question

I am implementing the RSA algorithm for encryption and decryption as given here:

http://www.di-mgt.com.au/rsa_alg.html

But could not understand the random prime number generation part in key generation. So I am taking two prime numbers as inputs from user. I had difficulties with generating the e also. so I made it constant (e= 17)

Some prime number inputs working properly ( i.e encoding and decoding properly) in gcc under linux but not in devcpp under windows. (e.g 53,61)

Here is the key generation code:

/* Generates private and public keys and saves into two separate files */
void keygen()
{
    int p,q,phi,d,e,n,s;

    printf("\n Enter two prime numbers: ");
    scanf("%d%d",&p,&q);

    n = p*q;
    phi=(p-1)*(q-1);

    e=17;

    // selec d such that d*e = 1+ k*phi for some integer k.
    d = 0;
    do
    {
        d++;
        s = (d*e)%phi;
    }while(s!=1);

    printf("\n public key: { e=%d n=%d }",e,n);
    printf("\n private key: { d=%d n=%d }\n",d,n);

}

Need help and suggestions in the prime number and e generation.

Answer 1

so you already know that e * d needs to be congruent to 1 mod phi(n)

since you know phi(n) a tuple (e,d) can be calculated by using the extended euclidean algorithm (EEA):

choose an integer for e (usually a small integer; this will be the public exponent, encryption will be faster with smaller exponents) that is less than phi(n) and greater than 2 (?... i think)

when you have a candidate for e, calculate the greatest common divisor (gcd) of e and phi(n) ... should be 1 ... if not, choose a new candidate for e and repeat (since there would be no modular inverse, in other words no private exponent d exists for this e and phi(n))

after you know that gcd(e,phi(n))==1 you can calculate d using the EEA (or as a shortcut, calculate EEA directly since it will also provide the GCD ... if that's not 1, choose a new value for e)

EEA (quick and dirty for calculating modular inverse):

imagine a table with 3 columns:

lets say those columns are named: b, q and t

so the lines of that table will look like:

b0, q0, t0
b1, q1, t1
...
(and so on)

the first 2 rows will be initially filled. for all other rows there is an itterative rule that can be applied to the previous two rows that will result in the values for the next row

the first 2 rows are:

phi(n), NO_VALUE, 0
e, floor(phi(n)/e), 1

the itterative rule to create the next row is: (where [] is an index operator for selecting the row)

b[i] = b[i-2] mod b[i-1]
q[i] = b[i-1] / b[i] (integer division, no fractions ... )
t[i] = t[i-2] - ( q[i-1] * t[i-1] )

you can abort the scheme when b[i] becomes 0 or 1 ... you don't really need q for the last row ...

so if b[i] is 0, b[i-1] can not be 1 since you should have aborted when you calculated b[i-1] if that were 1 ...

if you reach b[i]==0, b[i-1] is your gcd ... since it is not 1 you need a new value for e

if b[i]==1 your gcd is 1, and there is an inverse ... and that is t[i] (if t is negative, add phi(n))

example with real values:

let's say phi(n) is 120 let's say we choose 23 as a candidate for e

our table will look like:

b     q     t
120   –     0
23    5     1
5     4     -5
3     1     21
2     1     -26
1     2     47

the last calculated b is 1 so => gcd(23,120) == 1 (proof: the inverse exists)
the last calculated t is 47 => 23*47 mod 120 == 1 (t is the inverse)