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:

y (ciphertext) = E[Kpub](x) ≡ x^e mod n

Decryption:

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