RSA keys on fingers
Keys generation:
Choose large primes p,q
n = p * q
n will be the length of the key (for RSA keys should be at least 2¹⁰²⁴)
φ(n) = (p -1)(q -1)
choose Kpub
= e ∈ { 1, 2, 3, …, φ(n)-1 }
gcd(e, φ(n)-1) = 1
(gcd its Greatest common divisor)
compute Kpr = d
as d*e ≡ 1 mod φ(n)
(d could be computed from this formula using Extended Euclidean algorithm, (≡) its Modular congruence)
Kpub=(n,e), Kpr = (d)
Example:
p = 3, q = 11
n = 3 * 11 = 33
φ(33) = (3 -1)(11 -1) = 2 * 10 = 20
choose e
∈ { 1, 2, 3, …, 19}, in our example let it be 3
e = 3
d*3 ≡ 1 mod 20, (7*3 ≡ 1 mod 20)
d = 7
Encryption:
given: Kpub=(n,e), x (plaintext)
y (ciphertext) = E[Kpub](x) ≡ x^e mod n
Decryption:
given: Kpr=d, y (ciphertext)
x (plaintext)= D[Kpr](y) ≡ y^d mod n
Example:
given: n = 33, e = 3, d = 7
x=4
y=4³ mod 33 = 31
y=31
x=31⁷ mod 33 = 4
verification:
31⁷ ≡ (-2)⁷ mod 33 =
-128 mod 33 = (-4*33 + 4 ) mod 33 = 4