# 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 itsGreatest common divisor)

compute `Kpr = d`

as d*e ≡ 1 mod φ(n)

(d could be computed from this formula usingExtended Euclidean algorithm,(≡) itsModular congruence)

Kpub=(n,e), Kpr = (d)

**Example:**

*p = 3, q = 11n = 3 * 11 = 33φ(33) = (3 -1)(11 -1) = 2 * 10 = 20choose *

*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

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 = 7x=4y=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*