Cryptographic Primitive III: RSA Asymmetric Keys

RSA cryptosystems involves, a private key (which is kept private) and a public key, which is kept public i.e. known to everyone. The security of RSA hinges on the mathematically difficult problem of finding prime factorization of a very large number. Let's quickly disuss how a public, private key pair can be generated,

Let, p and q be two large primes, then

$n = q \times q$

$\phi(n) = (p-1) \times (q-1)$

Here, $\phi(n)$ is called euler's totient function

Choose a random number $e$ such that,

$e \in \left\{0,1,2...\phi(n)-1\right\}$ and $gcd(e,\phi(n)) = 1$

The gcd condition will ensure that we have an inverse of $e$ in $\mathbb{Z}_{26}$.

Now, using extended euclidian algorithm one can get the inverse of e as d such that,

$d \equiv e \pmod{\phi(n)}$

So, there we have it, the private key is $e$ and the public key is $(n,d)$.

Few points to note here are,

1. $p$ and $q$ are both $\geq 2^{512}$, although the recommened size is $2^{1024}$
2. $n$ is $\geq 2^{1024}$, although the recommended size is $2^{2048}$

This will generate a key that is of the size of 1024 bit, or 2048 bit if the recommdned values are used.

The encryption and decryption of a message $m$ is done as follows,

The cipher text $c$ is generated,

$c=m^{e} \pmod{n}$

The plaintext message m can be recovered as,

$m = c^{d} \pmod{n}$

Note that, all key generation operations are done over $\phi(n)$, and all encr/decr operations are done in $n$, whcih implies that decomposing $n$ into it's prime factors would miserable break the entire crypto system, as $n$ is a publicly known parameter.