RSA

RSA is a type of asymmetric encryption that uses a pair of keys: a public key for encrypting messages and a private key for decrypting them. The encryption and decryption process relies on mathematical operations involving prime numbers, modular arithmetic, and exponents.

Components

Term	Description	Example
Public Key (n, e)	Used by others to encrypt messages.	(187, 7)
Private Key (n, d)	Used to decrypt messages.	(187, 23)
n	The product of two prime numbers, used in both keys.	187
e	The public exponent used for encryption.	7
d	The private exponent used for decryption.	23
ϕ(n)	Euler’s totient function, a number derived from n.	160
x	The original message before encryption.	5
y	The encrypted message after applying the public key.	6

Steps to Generate RSA Keys

Pick Two Prime Numbers
Choose two large prime numbers, p and q.
- Example:
  p = 11
  q = 17
Calculate n
Multiply p and q to get n:
```
n = p × q
n = 11 × 17 = 187
```
Calculate ϕ(n)
Use the formula ϕ(n) = (p - 1)(q - 1) to get ϕ(n):
```
ϕ(n) = (11 - 1)(17 - 1) = 10 × 16 = 160
```
Choose e (Public Exponent)
Choose a number e that is relatively prime to ϕ(n) (e.g., e = 7). When we say two numbers are relatively prime (or coprime), we mean that they don’t have any common divisors other than 1.
Calculate d (Private Exponent)
Find d such that (e × d) ≡ 1 mod ϕ(n). This means that multiplying e and d should give a result that leaves a remainder of 1 when divided by ϕ(n).

Example of Encryption and Decryption

Public and Private Keys

Public Key: (n, e) = (187, 7)
Private Key: (n, d) = (187, 23)

Encrypting a Message (x)

To encrypt a message x, Alice uses Bob’s public key (n = 187, e = 7):

y = x^e mod n

For example, if x = 5:

y = 5^7 mod 187 = 6

So the encrypted message y = 6.

Decrypting the Message (y)

Bob receives the encrypted message y = 6 and uses his private key (n = 187, d = 23) to decrypt it:

x = y^d mod n

Decryption with y = 6:

x = 6^23 mod 187 = 5

So the decrypted message is x = 5, the original message.

Explorer