RSA keys on fingers

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

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

#266: PREMINT Test Operation! 30 Winners will Receive Chipper Momo-chan NFT!

CTF CyberTalents — Admin Gate First

Everydaysdrugs.com

Good insight into Russian hacking techniques

v1ew_s0urce.html

Malware’s Attack

MDT Updates: 2020 June — Week 4

What is wrong with Service of Legal Notice and Encryption Using WhatsApp?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Denys Popov

Denys Popov

More from Medium

Asbury dreaming

Natural wine in Alsace, an afternoon with Lissner and Beck-Hartweg

A Bluffer’s Guide to Doctor Who: The Smugglers