This article may take some terms as a given, so it is advisable that you understand the contents discussed in the article on PKC and Cryptographic Algorithms.

This method of encryption was provided by R.L. Rivest, A. Shamir, and L. Adleman (and hence the nickname “RSA” from their names) in their paper “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” in the year 1977. In addition to being a public key cryptosystem, as discussed in the PKC article, they also describe the use of RSA for digital signatures, something it is used for today as well! In fact, when you visited this page, the internet protocol of HTTPS used RSA. The security of RSA depends on the conjecture that it is extremely difficult to factor numbers.

Public Key Cryptosystem

To generate a key-pair, we follow these steps:

1. Choose two primes, \(p\) and \(q\), say 13 and 5.
2. Calculate \(n=13*5=65\)
3. Calculate the Euler totient function \(\phi(n)\). We can do this easily as \(\phi(n)=(p-1)*(q-1)=48\) since it is multiplicative in nature and since p and q are primes. (Here is Wiki for more.)
4. Choose a number \(e\) between from 2, 3, … , \(\phi(n)-1\), that is co-prime to phi, such as 11.
5. Since \(e\) is co-prime to \(\phi(n)\) it has have a multiplicative inverse in the ring of integers modulo \(\phi(n)\). Calculate \(d\), where \(de \equiv 1 \mod \phi(n)\). Here we get \(d=6\)

That’s it! Now we get our Public key as {e, n} and our Private key as {d,n}. Encryption of a message \(M\), say 23, is done as \(C=M^e \mod n = 23^{11} \mod 65 = 17\) and decryption is done in a similar manner, \(M=C^d \mod n = 17^6 \mod 65 = 23\).

Here is a link to RSA coded in C++, if you are interested in a more material implementation.

First, let us see how (and why) this works, and then we will look at its security.

Proof of correctness

Note that:

So, we want to show that

\({ (M^{e})^{d}\equiv M{\mod {pq}}}\)

for every integer \(M\) when \(p\) and \(q\) are distinct prime numbers and \(e\) and \(d\) are positive integers satisfying \(ed \equiv 1 \mod \phi(pq)\).
First we show \((M^{e})^{d}\equiv M \mod p\). Consider two cases:

1. If \(M \equiv 0 \mod p\) (i.e. \(M\) is a multiple of \(p\)), then \(M^{ed}\) is a multiple of \(p\). So \(M^{ed} \equiv 0 \equiv M \mod p\).
2. \(ed \equiv 1 \mod \phi(n) \implies ed = k*\phi(n) + 1\), for some integer \(k\)
   \(\therefore M^{ed} = M^{k*\phi(n) + 1} = M^{k(p-1)(q-1)}M\)
   Since \(M \not\equiv 0 \mod p\), we can use Fermat’s little theorem to get \(M^{k(p-1)(q-1)}M \equiv 1^{k(q-1)}M \equiv M \mod p\)

A similar approach will prove \((M^{e})^{d}\equiv M \mod q\).
Combining these, we get \({ (M^{e})^{d}\equiv M{\mod {n}}}\), thus concluding our proof of correctness.

Remarks

1. Note that you may only encrypt a message \(M \lt n\). This is because the algorithm uses modular arithmetic, and during decryption, it will return \(M=C^d \mod n\). So if you try to encrypt \(M \gt n\), you won’t get back your original message. You can, however, retrieve it by adding integer multiples of n to the answer. The easy solution to encrypt a message \(M \gt n\) is to break it into smaller-sized packets and encrypt them individually.
2. Although the original paper uses the Euler totient function \(\phi(n)\), Carmichael’s totient function, \(\lambda(n)\) is also used in modern implementations.

Security

The issues in breaking RSA arise in the following points:

1. Factoring \(n\) is extremely inefficient if the primes chosen are large enough. It would take a classical computer around over a trillion years to break an RSA-2048 bit encryption key, even with the fastest factorisation algorithm, GNFS.
2. Computing \(\phi(n)\) without factoring \(n\).
3. Determining \(d\) without factoring \(n\) or computing \(\phi(n)\).

Note that randomness in choosing primes is a massive factor in the practical strength of RSA. You can check out our other articles on breaking RSA and what it has to do with Quantum Physics!

Digital Signature

A digital signature is proof of your identity. Suppose Alice produces a key-pair as described above, and wants to send Bob a message. To do this, she can simply encrypt it with her Private key, \(S=M^d \mod n\) and then Bob may decrypt this by using her Public key as \(M=S^e \mod n\). Why this works must be clear:

1. Encryption and Decryption methods are commutative (look at Proof of correctness)
2. Alice’s Private key is unknown to anyone else, so the encrypted message can only be decrypted using her Public key, which is available to everyone. So only Bob, who receives the message, can decrypt it.