Understanding RSA with simple, easy numbers
Asymmetric encryption uses two different keys: a public key (shared with everyone) and a private key (kept secret). Anyone can encrypt a message with your public key, but only you can decrypt it with your private key.
First, we need to generate our keys. RSA uses prime numbers for this.
n = p × q =
This n is part of both public and private keys
Meer over modulair rekenen op Wikipedia →φ(n) = (p-1) × (q-1) =
This counts numbers less than n that don't share factors with n
Meer over de indicator op Wikipedia →e must be: 1 < e < φ(n) and gcd(e, φ(n)) = 1
We choose: e =
e and φ(n) must be coprime (share no factors except 1)
Meer info over ggd op Wikipedia →d × e ≡ 1 (mod φ(n))
d =
d is the modular multiplicative inverse of e
Meer over de modulaire inverse op Wikipedia →(, )
(e, n)
Share this with everyone!
(, )
(d, n)
Keep this secret!
Alice wants to send a secret number to Bob. She uses Bob's public key to encrypt it.
c = me mod n
c = mod
c = mod
c =
Bob receives the encrypted number and uses his private key to decrypt it.
Bob received: c =
m = cd mod n
m = mod
m = mod
m =
The original message is recovered!
Has message:
Uses Bob's public key
mod =
Receives:
Uses his private key
mod =
The magic is in the mathematical relationship:
me×d mod n = m
Because we chose d such that: e × d ≡ 1 (mod φ(n))
This is Euler's theorem in action: mφ(n) ≡ 1 (mod n)
An attacker knows n and e (public key), but to find d they need φ(n).
To calculate φ(n) = (p-1)(q-1), they need to factor n into p × q.
With small numbers like ours, this is easy. But with 2048-bit numbers, factoring is computationally infeasible!
Experiment with different messages and see the encryption/decryption in real-time.