Hey fellas, especially you security nerds.

I've had asymmetric encryption explained to me a number of times but I can't get a handle on it because no example actually talks in human terms. They always say "two enormous prime numbers", which I understand, but I can't conceptualize.

Can someone walk me through an entire process, showing your math & work, using some very small, single- or double-digit primes? Such as if I were to encrypt the text "hello world" using prime numbers like 3, 5, and 7

This is the simplest possible explanation, the one you're looking for: https://cs.toronto.edu/~david/...

though even the simplest example is still kinda "complex", since asymmetric encryption simply isn't super intuitive to begin with. But you can run the code and debug it in python yourself

@chatgpt
Hey fellas, especially you security nerds.

I've had asymmetric encryption explained to me a number of times but I can't get a handle on it because no example actually talks in human terms. They always say "two enormous prime numbers", which I understand, but I can't conceptualize.

Can someone walk me through an entire process, showing your math & work, using some very small, single- or double-digit primes? Such as if I were to encrypt the text "hello world" using prime numbers like 3, 5, and 7

@netikras
Sure, I can walk you through the process of asymmetric encryption using small prime numbers.

First, let's choose two small prime numbers, like 3 and 5. These numbers will be used to generate the public and private keys.

To generate the keys, we'll use a formula called the RSA algorithm. Here's how it works:

1. Choose two prime numbers, p and q.
2. Calculate n = p * q.
3. Calculate phi(n) = (p - 1) * (q - 1), where phi is the Euler totient function.
4. Choose a number e that is coprime to phi(n). In our example, we can choose e = 7.
5. Calculate d such that e * d ≡ 1 (mod phi(n)). In our example, d = 23.
6. The public key is (e, n) and the private key is (d, n).

Using our small prime numbers, we can generate the keys as follows:

p = 3
q = 5
n = p * q = 15
phi(n) = (p - 1) * (q - 1) = 8
e = 7
d = 23 (since 7 * 23 ≡ 1 (mod 8))

So our public key is (7, 15) and our private key is (23, 15).

Now let's say we want to encrypt the message "hello world" using our public key.

Here's how we do it:

1. Convert each letter of the message to its ASCII code. "hello world" becomes "104 101 108 108 111 32 119 111 114 108 100".
2. Concatenate the ASCII codes into a single number. 10410110810811132119111108100.
3. Split the number into blocks that are less than or equal to n. In our case, we can use two-digit blocks:
10, 41, 01, 08, 10, 81, 13, 21, 19, 11, 08, 00
4. For each block, calculate its encrypted value as follows: ciphertext = block^e mod n. So the first block becomes 10^7 mod 15 = 4, the second block becomes 41^7 mod 15 = 11, and so on. The ciphertext becomes:
4, 11, 1, 2, 4, 11, 13, 1, 4, 11, 2, 0

Now let's say we want to decrypt the ciphertext using our private key. Here's how we do it:

1. Take each block of ciphertext and calculate its decrypted value as follows: plaintext = ciphertext^d mod n. So the first block becomes 4^23 mod 15 = 10, the second block becomes 11^23 mod 15 = 41, and so on. The plaintext becomes:
10, 41, 1, 8, 10, 108, 1

08, 101, 32, 119, 111, 114
2. Convert each number back to its ASCII code. The message is decrypted as "hello world".

And that's the process for asymmetric encryption using small prime numbers! Of course, in real-world applications, much larger prime numbers are used to generate the keys, making the encryption much more secure.

@netikras Oh please god no. If there is any topic you shouldn't ChatGPT your way into it is encryption implementation. Especially if you know that you struggle with conceptualizing it.

@PotatoCookie with this version, no, but the version that can give you references to the source material, yes.

@netikras It's already gone :c