Skip to main content

Encryption and Decryption - Note of Fundamental Number Theory II

The first thing we need to do in the main function is to prepare two groups of keys.

The function setRSAKeys() helps to generate a public/private key pairs:

int setRSAKeys( key* publickey, key* privatekey)
{
    //generate two 512bit primes p and q
    int p, q;
    srand((unsigned)time(0));
    getPrime(&p);
    getPrime(&q);
    //printf("p = %d, q = %d\n", p, q);

    //calculate n and phi(n)
    int n, phi_n;
    n = p * q;
    phi_n = (p - 1) * (q - 1);
    //printf("n = %d, phi(n) = %d\n", n, phi_n);

    //calculate e, a small odd relatively prime to phi_n
    int e = 1;
    do
    {
        e += 2;
    } while (1 != gcd(e, phi_n));
    //printf("e = %d\n", e);

    //calculate d, the multiplicative inverse of e, modulo phi_n
    euclid_coefficients ec ;
    int d;
    ec = Extended_Euclid(e, phi_n);
    d = ec.x;
    if (0 > d)
    {
        d += phi_n;
    }
    //printf("d = %d\n", d);

    //return (n, e) and (n, d)
    publickey->n = n;
    publickey->_key = e;
    privatekey->n = n;
    privatekey->_key = d;

    return 0;
}

In the function above, two primes are picked to compute \(n\), which in reality is a gigantic number because \(p\) and \(q\) are big primes, say 1024 bits each. (again in this note we simplified the case by using small integers)

Then \(e\) and \(d\ =\ \phi(n)\) are obtained to form the primes: \(e\) is a small odd integer and falls into the public key set. \(d\), another big number calculated based on \(n\), is not very easy to guess (or reversed-engineering), and is therefore put as part of the private key set.

Euler's phi function:

\(\phi(n)=n\ \displaystyle\prod_{p|n} \left(1- \frac{1}{p}\right)\)

where \(\phi(n)\) is the size of \(\mathbb{Z}_{n}^*\), \(p\) runs over all the primes dividing \(n\) (including \(n\) itself, if \(n\) is prime, too)

\(\mathbb{Z}_{n}^*\) is the multiplicative group modulo n, or defined as

\(\mathbb{Z}_{n}^* = {[a]_n}\) in \(\mathbb{Z}_{n} : gcd(a,n) = 1\)

where \([a]_{n}\) = \(a'\) mod \(n\), \(a'\) in \({Z}\)

e.g. \(\mathbb{Z}_{15}^*\ =\ \{1, 2, 4, 7, 8, 11, 13, 14\}\), \(\phi( 15 ) = 15 ( 1 - \frac{1}{3} ) ( 1 - \frac{1}{5} ) = 8\)

When we select \(p\) and \(q\), which are primes and \(n\ =\ pq\), The phi function becomes \(\phi(n)\ =\ (p-1)(q-1)\), much easier now =)

At the end of the above function we have set two groups of keys: the public key \(\{e,\ n\}\) and the private key \(\{d,\ n\}\)

With the public and private keys, encrypting and decrypting a message becomes easy. Given a message \(M\), to encrypt \(M\) we do:

\(M^e\ mod\ n\)

the outcome of which, \(S\), is the encrypted message. To decrypt the secret,

\(S^d\ mod\ n\)

will give you the original message.

\(d = e^{-1}\ mod\ \phi(n) = e^{-1}\ mod\ ((p-1)(q-1))\) guarantees for the given \(p\), \(q\) and \(e\) there will be a unique \(d\). Therefore for a given public key \(\{ e,\ n \}\), there will be one and only one private key \(\{ d,\ n \}\). This is exactly what we want!

On the other hand,

\((M^e\ mod\ n)^d\ mod\ n\ =\ M^{ed}\ mod\ n\ =\ M\)

promises the encryption and decryption are irreversible operations.

To be continued...