A Primer On RSA Public Key Cryptography

About

RSA, also known as Rivest–Shamir–Adleman, is a public key cryptography system and one of the most widely used. It is one of the first public key cryptography systems found that allowed a party to encrypt/decrypt messages using its algorithm. It is based on the hardness of factoring large primes.

The most fundamental component of RSA is that it comes with two keys, a public key, and a secret key. The public key can be shared to the rest of the world while the private key remains a secret. The private key is then used to decrypt messages encrypted to the public key.

History

RSA is one of the most basic and first found public key systems that allowed asymetric encryption as opposed to symmetric encryption. It was developed in 1973 at GCHQ by Ron Rivest, Adi Shamir and Leonard Adleman.

Design

Variables

Public Key And Secret Key

PublicKey: (e,n)
SecretKey: (d)

Encryption and Decryption

Encryption: message^e mod n
Decryption: ciphertext^d mod n

Internals

p : A Randomally Generated Large Prime Number
q : A Randomally Generated Large Prime Number
n = p * q (the modulus and public key)

r = (p-1)(q-1) (Carmichael's totient function on n)
e: A statically chosen coprime number that is released in the public key. The usual value is 65537.

d = e^-1 mod r (modular multiplicative inverse)

Others

Message: the number or message to encrypt by the public key Ciphertext: the ciphertext to decrypt by the private key

Key Generation

Lets say we would like to generate a new RSA Keypair.

To generate a keypair, we need to generate two random primes, known as p and q to find the modulus, stored as the public key, also known as n.

These primes are generally generated in the sizes of 2048, 3072, 4096 bits to be secure. That is quite a large number and hard to factor for most computers, excluding quantum computers which may be able to break RSA.

Step 1: Generate The Prime Numbers

For this purpose, we will generate small primes of p=17 and q=3.

Step 2: Construct the Modulus From The Primes To Generate The Modulus `n`

Equation: n = (p * q)

We will then multiply them together to get n = (17 * 3) = 51. This n is kept in the public key.

Step 3: Calculate `r`

Equation: r = (p-1)(q-1)

We will then compute r with the following equation: r=(p-1)(q-1).

That would be r = (17-1)(3-1) = (16)(2) = 32

This can be done using Euclids Algorithms. You then need to find the least common multiple of that number.

Step 4: Calculate `e` as a Coprime

e: {3,5,17,65537}

e is released as part of the public key. For this example, we will choose the coprime 5. Most RSA systems use 65537 or 2¹⁶-1.

Step 5: Calculate the Secret Key (`d`)

Equation: d = e^-1 mod r

We then get d = (5 mod 32) = 5 so d=5 or the secret key

Step 6: Conclude with the Public Key and Private Key

PublicKey: (e,n) = (5,51)

SecretKey: (d) = 5

Encryption

To encrypt a message, lets say 8 we take the message as a number and calculate the following:

Equation: CipherText = message^e mod n

CipherText = 8⁵ mod 51

CipherText = 32768 mod 51

CipherText = 26

Decryption

To decrypt a message, we take the CipherText and use the private key, also known as d.

Equation: DecryptedMessage = CipherText^d mod n

CipherText = 26 (as per this example)

26⁵ mod 51

11881376 mod 51

DecryptedMessage = 8

Conclusion

RSA is an important part of Public-Key Cryptography and still plays a fundamental role in security. It is often used for WebPKI, GNUpg, and SSH. It is used to encrypt traffic in TLS/SSL and widely deployed around the world. The simplicity of it makes it a valuable solution as it only remains on integer factorization problems. In today's society, RSA keys are often generated for daily purposes and serve a fundamanetal role to keeping things secure.