Library
Mathematics

The Magic of RSA Encryption

RSA is a public-key encryption system that relies on the extreme difficulty of factoring very large numbers. This guide covers how keys are generated, how messages are securely locked, and the mathematical intuition behind why it works.

Public:(n,e)Private:dPublic: (n,e) \quad Private: d
Imagine having a mailbox where anyone can drop a letter in through a slot, but only you have the key to open the back and read what is inside. RSA is the digital version of this: a public key for locking messages that anyone can use, and a private key only you possess to unlock them.
Step-by-step solver
1

(a) Key Generation

Select two primes, p=5 and q=11, then calculate n and the totient.

n=5×11=55;φ(55)=(5−1)(11−1)=40n = 5 \times 11 = 55; \varphi(55) = (5-1)(11-1) = 40
2

(b) Find Keys

Choose e=7, then find d such that 7d leaves a remainder of 1 when divided by 40.

7×23=161=4(40)+1⇒d=237 \times 23 = 161 = 4(40) + 1 \Rightarrow d = 23
3

(c) Encrypt

To encrypt message m=9, raise it to the power of 7 modulo 55.

c=97 mod 55=4782969 mod 55=4c = 9^7 \bmod 55 = 4782969 \bmod 55 = 4
4

(d) Decrypt

Raise the ciphertext 4 to the power of the private key 23 modulo 55 to recover the message.

423 mod 55=94^{23} \bmod 55 = 9

Original question

Can you please explain RSA encryption for me

Follow-up chat

Ask me anything about this lesson. I'll answer using what we just covered.