asymmetric encryption

uses public key to encrypt and private to decrypt. anyone can encrypt but only someone with the private key can decrypt

basically, anyone can send me a message securely

very expensive

used in https handshake (not transport though, switches to symmetric encryption)

Bob secretly chooses two primes:

Compute:

n = pq = 55

Compute Euler’s totient:

φ (n) = (p - 1) (q - 1) = 4 \cdot 10 = 40

Choose a public exponent:

e = 3

Find a private exponent $d$ such that:

e d \equiv 1 (mod 40)

One solution is:

d = 27 since 3 \cdot 27 = 81 \equiv 1 (mod 40)

Keys:

Bob publishes $(3, 55)$ and keeps $27$ secret.

Alice wants to send the message:

m = 7

She encrypts using Bob’s public key:

c = m^{e} mod n = 7^{3} mod 55

Compute:

7^{3} = 343, 343 mod 55 = 13

So the ciphertext is:

c = 13

Alice sends 13 to Bob.

Bob decrypts using his private key:

m = c^{d} mod n = 1 3^{27} mod 55

Evaluating this (via modular exponentiation) yields:

m = 7

The original message is recovered.

Why This Works (Short Theory Note)

The exponents $e$ and $d$ are chosen so that:

e d \equiv 1 (mod φ (n))

This means there exists an integer $k$ such that:

e d = 1 + k φ (n)

Because of this structure, exponentiating by $e$ and then by $d$ returns the original message:

(m^{e})^{d} \equiv m (mod n)

The critical point is:

So:

This is the core asymmetry behind RSA.