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...