In this post we will see in detail the RSA cryptosystem which was one the first Assymetric Cryptosystem constructions also known as Public-Key Cryptosystem.
RSA is named after its three inventors: Ronald Rivest, Adi Shamir and Leonard Adleman who published in 1978 their paper titled: “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” (paper link).
I think its really amazing reading this paper in particular and old papers in general as it gives you some perspective about how life looked like tens of years ago! Just as an example, the paper begins with the following:
The era of “electronic mail” [10] may soon be upon us; we must ensure that two important properties of the current “paper mail” system are preserved: (a) messages are private, and (b) messages can be signed. We demonstrate in this paper how to build these capabilities into an electronic mail system.
It is sometimes hard to believe that all this progress was done back in the 1970s without the internet, or perhaps these inventions is what made the internet possible. Just imagine, they had no emails!
Anyway, back to our original topic.
Assymetric Cryptography
Before jumping into RSA, let’s see what was so innovative about it.
Say we have Alice and Bob who wish to secretly communicate, how can they do this?
Up until the invention Assymetric Cryptography both Alice and Bob have had to agree on some secret key which will later be used to encrypt and decrypt the information they exchange.
Since only the two communicating parties knew the key the channel was assumed to be secret.
In the old days (and by old I mean up until the 1970’s) this key had to be exchanged over a secure channel.
These “secure channels” were typically just armed convoys carrying a printed key material.
But today none of this happen, when you connect to the internet you don’t have to send a secure envelope to the server with guards sailing across the ocean 
.
The cornerstone of the technology that lets us connect to websites without any convoys is the seminal work of Whitfield Diffie and Martin Hellman who published in 1976 their legendary paper titled “New Directions in Cryptography” (paper link), which led to a Key-Exchange protocol popularized under the name “Diffie-Hellman Key-Exchange”.
Notice: While we won’t get into the Diffie-Hellman protocol here, we do have to understand it allows two parties to exchange information on publicly from which a secret key can be derived, known only to these two parties.
The Diffie-Hellman protocol ends with two parties having a Symmetric Key. By “Symmetric” we mean that both parties hold the same key and this key is used for both encryption and decryption.
The major innovation in the RSA cryptosystem is that keys don’t have to be symmetric anymore! Instead, each party $P_i$ generates a secret key $sk_i$ and a public key $pk_i$. The secret key is kept secret and the public key is publicly published. Whenever someone wants to send $P_i$ a message $m$ it encrypt $m$ with the public key $pk_i$. The RSA cryptosystem is built such that ciphertexts created this way can be efficiently decrypted using the secret key $sk_i$ but since only $P_i$ holds this secret key it will be the only party being able to read these messages!
So, if two parties $P_1,P_2$ wish to communicate, $P_1$ will sends $P_2$ messages using $P_2$’s public key $pk_2$ and $P_2$ will sends messages to $P_1$ using $P_1$’s public key $pk_1$. Each party will decrypt its incoming messages using its secret key $sk_1$ or $sk_2$.
Let’s see how RSA make this magic happen.
RSA Groups
Given two distinct primes $p,q$ we call $N=pq$ an RSA-modulus. We denote by $\mathbb{Z}^\ast_N$ the set of numbers between $1$ and $N-1$ that are coprime to $N$. Notice that each number dividing $N$ has to divide at least one of its prime factors which are $p$ and $q$ so $\mathbb{Z}^\ast_N$ is the set of all numbers between $1$ and $N-1$ that are neither a multiple of $p$ nor $q$.
An RSA group is a group whose elements are $\mathbb{Z}^\ast_N$ for some RSA-modulus $N$ and the group operation is the modular multiplcation modulo $N$.
Let’s have an example. Let $p=3$ and $q=5$ we have $N=p\cdot q = 15$ so $\mathbb{Z}^\ast_N=\lbrace 1,2,4,7,8,11,13,14\rbrace$. Our RSA group operation will take two numbers from $\mathbb{Z}^\ast_N$ and multiply them modulo $15$, for example $4*7=28 \equiv 13 \mod 15$. So if we apply the group operation on $4$ and $7$ we get $13$.
One characteristic of groups is that each element should have an inverse. We say that $a,b$ are inverse if $a*b=1$ according to the group operations. For example $2\ast8=16 \equiv 1 \mod 15$ so $2$ and $8$ are the inverse of each other!
One question you can ask is: “Given a number $a$ in $\mathbb{Z}^\ast_N$, how fast can we find its inverse?”. According to a popular theorem called the Chinese Remainder Theorem finding the inverse of $a$ in the RSA group can be done very efficiently if we know $p,q$, the factors of $N$. But what if we don’t know them and instead we are just given $N$? Well, we don’t really know but we assume that it is very hard and for sufficiently large $p,q$ it can take very long time.
Notice: If anyone invalidates this assumption it means that the RSA cryptosystem will be immediately broken.
Square Roots in RSA Groups
To be continued…