[Shinoa]

What is RSA?

RSA is the most common public-key based cryptosystem, which as this convenient image shows, just means that you use one key to encrypt data and another to decrypt it. This works because of some math voodoo wizardry, not allowing you to decrypt the encrypted message with the first key. Because of this, RSA is very useful when dealing with two parties that never actually met in any way. You publish the first key, but keep the second key a secret, and when someone is sending you the data they encrypt it with the first key which only you can decrypt.
RSA was named after some San Franciscin, New Yorker, and Israeli. Some British guy working for the government developed practically the same system 5 years before them, but that's all kinda irrelevant so I'm just gonna skip over all that.

How does it work?

Start by picking 2 prime numbers (p & q). For the sake of this tutorial I'll go with 17 and 23, but if you wanna use this for anything practical you wanna generate really big numbers and run them through a primality test, the Miller-Rabin test for example. Next multiply p and q, 17*23=391, and call it n.

Next you're gonna find the totient of n (or φ(n)).
If your search up Euler's totient function, you're gonna fine a whole bunch of math mumbo jumo such as

and so on. All we need to know for our purposes though is that t = φ(n) = (p-1) * (q-1), (17-1) * (23 - 1) = 352.

Now that that's done you're gonna need to choose a number for e. e has to be greater than 1 and less than n and be coprime to n. For simplicity's sake choose a prime number that's less than n and doesn't go into n. That number is going to be you're public key. I'll go with 19, but if you're using this for anything useful, the public key should be at least 2048 bit.

Next you have to find d, the private key, which is the trickiest part of this whole thing. You need to do some modular multiplicative inverse and Extended Euclidean algorithm stuff, which can be dumbed down to "What's the solution to ((e * x - 1) % t = 0) and/or (d * x = 1 % t)" and still be almost impossible to do by hand when you have very large numbers so um... have some code.

Spoiler: Python

Code:

def gcd(e, y):                while e != 0:        e, y = y%e, e    return y def findPriv(e, t):    if gcd(e, t) != 1:        return None    u1, u2, u3 = 1, 0, e    v1, v2, v3 = 0, 1, t    while v3 != 0:        h = u3 // v3        v1, v2, v3, u1, u2, u3 = (u1 - h * v1), (u2 - h * v2), (u3 - h * v3), v1, v2, v3    return u1 % t

                                                                                                                                                                                                            plz don't hurt me @phyrrus9

In my case it outputs 315.

Now that that's done let's do a quick recap.
p = 17          ; prime 1
q = 23          ; prime 2
n = 391        ; p*q
t = 352        ; (p-1)*(q-1)
e = 19          ; random prime that is greater than 1, less than n, and does not go into n (public key)
d = 315        ; modular multiplicative inverse stuff (private key)

Now to the actual encryption part.
m = plaintext
c = ciphertext
(m^e) % n = c
(c^d) % n = m

So let's have m be 6.
(6^19) % 391 = 386
(386^315) % 391 = 6

Ta-Da! Simple as that.
If you're planning on actually using this for anything you're probably going to want to know two other things. 1) How to convert strings to decimal. ASCII is the standard way to encode characters into integers, click here. 2) Padding stuff, click here.

Edit: Btw "%" = mod

---

I'm pretty bad at explaining things in general, and am still a beginner when it comes to cryptography and the such, so hope I did a decent job explaining it

[phyrrus9]

What is RSA?

RSA is the most common public-key based cryptosystem, which as this convenient image shows, just means that you use one key to encrypt data and another to decrypt it. This works because of some math voodoo wizardry, not allowing you to decrypt the encrypted message with the first key. Because of this, RSA is very useful when dealing with two parties that never actually met in any way. You publish the first key, but keep the second key a secret, and when someone is sending you the data they encrypt it with the first key which only you can decrypt.
RSA was named after some San Franciscin, New Yorker, and Israeli. Some British guy working for the government developed practically the same system 5 years before them, but that's all kinda irrelevant so I'm just gonna skip over all that.

How does it work?

Start by picking 2 prime numbers (p & q). For the sake of this tutorial I'll go with 17 and 23, but if you wanna use this for anything practical you wanna generate really big numbers and run them through a primality test, the Miller-Rabin test for example. Next multiply p and q, 17*23=391, and call it n.

Next you're gonna find the totient of n (or φ(n)).
If your search up Euler's totient function, you're gonna fine a whole bunch of math mumbo jumo such as

and so on. All we need to know for our purposes though is that t = φ(n) = (p-1) * (q-1), (17-1) * (23 - 1) = 352.

Now that that's done you're gonna need to choose a number for e. e has to be greater than 1 and less than n and be coprime to n. For simplicity's sake choose a prime number that's less than n and doesn't go into n. That number is going to be you're public key. I'll go with 19, but if you're using this for anything useful, the public key should be at least 2048 bit.

Next you have to find d, the private key, which is the trickiest part of this whole thing. You need to do some modular multiplicative inverse and Extended Euclidean algorithm stuff, which can be dumbed down to "What's the solution to ((e * x - 1) % t = 0) and/or (d * x = 1 % t)" and still be almost impossible to do by hand when you have very large numbers so um... have some code.

Spoiler: Python

Code:

def gcd(e, y):                while e != 0:        e, y = y%e, e    return y def findPriv(e, t):    if gcd(e, t) != 1:        return None    u1, u2, u3 = 1, 0, e    v1, v2, v3 = 0, 1, t    while v3 != 0:        h = u3 // v3        v1, v2, v3, u1, u2, u3 = (u1 - h * v1), (u2 - h * v2), (u3 - h * v3), v1, v2, v3    return u1 % t

                                                                                                                                                                                                            plz don't hurt me @phyrrus9

In my case it outputs 315.

Now that that's done let's do a quick recap.
p = 17          ; prime 1
q = 23          ; prime 2
n = 391        ; p*q
t = 352        ; (p-1)*(q-1)
e = 19          ; random prime that is greater than 1, less than n, and does not go into n (public key)
d = 315        ; modular multiplicative inverse stuff (private key)

Now to the actual encryption part.
m = plaintext
c = ciphertext
(m^e) % n = c
(c^d) % n = m

So let's have m be 6.
(6^19) % 391 = 386
(386^315) % 391 = 6

Ta-Da! Simple as that.
If you're planning on actually using this for anything you're probably going to want to know two other things. 1) How to convert strings to decimal. ASCII is the standard way to encode characters into integers, click here. 2) Padding stuff, click here.

---

I'm pretty bad at explaining things in general, and am still a beginner when it comes to cryptography and the such, so hope I did a decent job explaining it

In part 2 are you gonna talk about encodings and handshakes?

[reGEN]

Nice beginner-friendly guide! It's amazing how mathematics can make solutions so elegantly simple (for now). I think including the basics behind it ((modular) exponentiation) to explain how it works and why it's so incredibly impractical to reverse would complete your tutorial.

[phyrrus9]

Nice beginner-friendly guide! It's amazing how mathematics can make solutions so elegantly simple (for now). I think including the basics behind it ((modular) exponentiation) to explain how it works and why it's so incredibly impractical to reverse would complete your tutorial.

Computer science is just applied mathematics. That's real elegance

[Shinoa]

In part 2 are you gonna talk about encodings and handshakes?

Maybe. If I ever get around to it I want to do key exchanges (handshakes) or elliptic-curve cryptography.

[phyrrus9]

In part 2 are you gonna talk about encodings and handshakes?

or elliptic-curve cryptography.

oh god not the hipster stuff again

[Shinoa]

oh god not the hipster stuff again

Lol. It's primarily used in cryptocurrency stuff, which is admittedly pretty hipster

[phyrrus9]

oh god not the hipster stuff again

Lol. It's primarily used in cryptocurrency stuff, which is admittedly pretty hipster

Congrats, you've got a like from me (a rare thing)...... admitting you have a problem is the first step. was a good read either way

[Blink]

Nice beginner-friendly guide! It's amazing how mathematics can make solutions so elegantly simple (for now). I think including the basics behind it ((modular) exponentiation) to explain how it works and why it's so incredibly impractical to reverse would complete your tutorial.

Computer science is just applied mathematics. That's real elegance

And logic, lotsa logic.

[Shinoa]

Congrats, you've got a like from me (a rare thing)...... admitting you have a problem is the first step. was a good read either way

I'm honored

And logic, lotsa logic.

Wouldn't CS logic fall under mathematical logic?