RSA stands for Rivest-Shamir-Adleman, who first described the algorithm in 1977. It is used in public-key cryptography. RSA is essential for modern internet protocols. Key applications are

• TLS/SSL. Whenever you visit a secure website, RSA is used to exchange symmetric session key
• Digital signatures. RSA provide a way to verify authenticity and integrity of a message. Sender uses private key to “sign” a document. Then recipient uses public key to verify the signature
• Email security. Protocols like PGP use RSA to encrypt emails
• VPN. RSA is used during the setup of secure VPN connection to authenticate parties
• Cryptocurrency and blockchain. RSA is used in key management and signing. But for most cases Elliptic Curve Cryptography is used instead of RSA

Public key cryptography

RSA is asymmetric encryption algorithm. This means it uses pair of keys

• public key: can be shared with anyone
• private key: must be kept secret

Public key is used for encryption, private key is used for decryption.

why rsa is so important

RSA solves very important problem: how to exchange encryption keys, before establishing secure connection? This was often a logistical challenge. RSA bypasses this issue, by never sharing a secret key. Instead, only an encryption key is shared.

mathematical asymmetry

The key concept that makes RSA so resilient is the asymmetry of computational difficulty between two mathematical operations: multiplication and prime factorization.

• easy direction: multiplication. It is simple, even for huge numbers. Straightforward process that takes a computer milliseconds.
• hard direction: factorization. Guessing what was prime factors of for large numbers is computationally intensive. It can take thousands of years to complete, even for supercomputers

generating Public key

Public key is a tuple (e,n).

• e – encryption exponent
• n – RSA modulus
• p – relatively big prime number
• q – relatively big prime number

n = p*q

to calculate e, we must first find euler totient (φ):

φ = (p-1)(q-1)

and e is coprime to that number:

• no common factors other than 1. In other words, greatest common divisor of e and (p-1)(q-1) is 1

Common choice for e is 2^16+1. It is a prime number, and binary representation 10000000000000001 makes it computationally efficient. It is also large enough to avoid security risks associated with small exponents.

example of public key

Lets calculate simple public key

p=5
q=11
n=p*q=55
φ = (p-1)(q-1) = 4*10 = 40
e = 3
(e,n) = (3,55)

Our public key is (3,55)

encrypting the message

To encrypt the message, sender has to calculate number c:

c ≡ m^e (mod n)

• m: original message
• e: exponent, taken from public key
• n: modulus, taken from public key

Assume, that we want to send the number 7 (for any reason). In practice, ASCII table can be used to convert letters to numbers first.

m = 7
c ≡ 7^3 (mod 55) ≡ 343 (mod 55) ≡ 13

decrypting message

To decrypt, first we need to solve this equation:

de = 1 (mod φ ) = 1 (mod((p-1)(q-1))
3d ≡ 1 (mod 40)
d ≡ 27 (mod 40)

by having d, we can decrypt the message:

• m: decrypted message
• c: encrypted message
• d: private, decryption exponent
• n: rsa modulus

m ≡ c^d (mod n)
m ≡ 13^27 (mod 55) ≡ 7