How does RSA work?

RSA is a cryptosystem for public-key encryption and is widely used for securing sensitive data, particularly when being sent over an insecure network such as the Internet. One of the 3 seminal events in cryptography of the 20th century, RSA opens the world to a host of various cryptographic protocols like digital signatures, cryptographic voting etc. So, let's dive into the deep of RSA; to understand what is it and how does it work?

What is RSA?

RSA stands for Rivest–Shamir–Adleman. It's one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the "factoring problem". The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978. RSA is a relatively slow algorithm, and because of this, it is less commonly used to directly encrypt user data. More often, RSA passes encrypted shared keys for symmetric key cryptography which in turn can perform bulk encryption-decryption operations at much higher speed.

How does RSA work?

RSA encryption system has mainly three phases -

• First one is Key Generation - Whoever wants to receive secret messages creates a public key (which is published) and a private key (kept secret). The keys are generated in a way that conceals their construction and makes it 'difficult' to find the private key by only knowing the public key.

• The second one is Encryption - A secret message to any person can be encrypted by his/her public key (that could be officially listed as phone numbers).

• The third one is Decryption - Only the person being addressed can easily decrypt the secret message using the private key.

It required you to first share your key. Since you’re sharing the key precisely to establish an encrypted communication over an insecure channel, you have to share them in advance, which opens up the possibility of eavesdropping by intercepting the keys during the transfer.

You now need two keys, a public key (encryption) and a private key (decryption). You share the public key with others, and keep the private key with you. The public key encrypts the message, and the private key decrypts the message. Encryption is almost a one-way function, unless you apply the decryption algorithm, or use the private key, to decrypt it. This is known as a trapdoor mechanism. For eg., your body has a mixture of blood and plasma. You can't separate it unless you use a centrifuge. The centrifuge is then your trapdoor. You can also think of it as a padlock, which was sent open and you receive it locked. You then unlock it with the key.

So, you only need one private key. And share your public key with others. RSA is mathematically robust. It's a trap door mechanism.

For example -

You first select two random prime numbers such as p and q.

Obtain the modulus n, such that   n=p×q.

Than apply totient function  ϕ(n)=(p−1)×(q−1)

After that choose a prime number e, such that  1

e should be coprime with ϕ(n).

e is essentially your encryption key.

Compute d. d is the essentially your decryption key.

Such that   e×d=1modϕ(n)

Now you have the keys -

Public key = (e,n)

Private key = (d,n)

Only the public key (e,n) is published; all the other numbers involved (p,q,φ,d) must be kept private! The main property of this construction is that it is 'difficult' to compute d just from the numbers e and n.

Both encryption and decryption need a power reduced modulo a module m. If the whole power is computed before starting the modulo computation, this may be very inefficient and involve large numbers. Therefore, a more efficient method of reducing already the intermediate powers modulo m is used.

What is the real-time use of it?

Many protocols like SSH, OpenPGP, S/MIME, and SSL/TLS rely on RSA for encryption and digital signature functions. RSA is built into many common software products, including Microsoft's Internet Explorer. It is also used in software programs - browsers are an obvious example, which needs to establish a secure connection over an insecure network like the Internet or validate a digital signature. RSA signature verification is one of the most commonly performed operations in IT.