Public-key cryptosystems and RSA

tags: cryptography

Public key crypto-system is a security systems that does ciphering by two keys, a public key that is known by every one, and a private key that is only known for the one that will decrypt. Public-key cryptosystems were created to defeat the idea of key distribution centers, because if KDC gets compromised, other cryptosystems render useless. There is no need ti distribute the private key, it gets generated at the decrypting end.

RSA Algorithm

RSA algorithm builds upon all the theorems we learned about in Introduction to Number Theory. To use RSA first calculate two prime numbers $p$ and $q$, then calculate $n$ that $p\ast q$. We also calculate $\varphi (n)$ that we know is $(p-1)(q-1)$.

RSA is built on two exponentiation operations.\begin{eqnarray} C = M^{e}\space mod\space n \\ M = C^{d}\space mod \space n = (M^e)^d\space mod \ n \\ \end{eqnarray} where $d$ is the inverse of $e$ in $mod\varphi (n)$, all of our work in exponentiation is in $\varphi (n)$ to ensure the cyclic property number theory and comply to Fermat. $M$ must be less than for proper recovery of data, because if it was not less than that you would not be able to recover it after the last modulus.

RSA is not widely used in encryption or confidentiality but is used for signing and authentication.

The strength of RSA lies in the part that n is usually a really large number, so factoring it to two large primes, p and n, is infeasible, and also trying to get all the numbers relatively prime to n to calculate $\varphi (n)$ is also infeasible.

Key generation

We first have to select values for p and q, and since $n=p\ast q$ is known to anyone, p and q must be very large numbers to prevent finding them by exhaustive methods. To create a very large prime numbers, we choose a random large odd number and apply primarity to test to them (^42eb15). Since the length between to successive primes is $ln(n)$ and we discard even numbers, the worst case is that we will retry the generation $0.5ln(n)$ times.

After the prime number generation, if we found that e (65537) is not relatively prime to $\varphi (n)$ we redo the prime generation.

Efficient operations of Public Key with Montgomery Algorithm

Instead of doing multiplication of self the value $e$ times, exponentiation can be sped-up by the following formula:

Get the binary representation of this number and exponentiate by the powers of two and multiply the results together, this is equivalent to total exponentiation.

The code implementation for this is called Montgomery algorithm and is as follows: The f x f part is a left shift of the exponent and f x a adds a 1 to be shifted later.

Also exponentiation is also sped up by using a preselected value $65537$ and generating p and q for it. The number has two 1 bits so speed up exponentiation.

Efficient operations of private key

We can use the CRT to make the cipher text smaller by considering p and q as $m_1$ and $m_2$.

TODO: see what is meant by the operations here

We can also use the cyclic property and discrete exponent theorem to make the d smaller.