How exactly are public and private keys used to encrypt and the decrypt data?

Question

In asymmetric encryption schemes, a public key is used by an outside source to encrypt data to be sent to the holder of the private key.

It's my understanding that public keys are generated from the private key using a one-way, or trapdoor function, rendering it computationally infeasible to reverse-engineer the private key from the public key or its encrypted message.

My question is not why private keys can't be reverse-engineered, or how public/private keys are generated.

My question is exactly HOW the public key is used to encrypt the data, and the process by which the private key can decrypt it. Can anyone give an example of a very simple public and private key, and how exactly they're used to encrypt, and then decrypt some data?

For the sake of simplicity and ease of understanding, perhaps an example could utilize multiplication as the one-way function to frame the keys, and a small string of ones and zeroes could be used as the data to be encrypted and then decrypted.

Answer 1

Here is a numerical example with RSA.

(Edit and warning: as fgrieu notes in the comment, these values are strictly for illustrating the math involved; all of the parameters are unsuitable for actual use. See the answers here for discussion about how to properly choose the primes $p$ and $q$, and here about secure RSA key sizes.)

Quoting the relevant parts:

The first step of RSA encryption is to generate two primes, $p$ and $q$.

$$p = 257$$

$$q = 337$$

The product of $p$ and $q$ is $n$, in our case:

$$n = 257\cdot 337 = 86609$$

The euler totient, $\phi(n)$ is calculated below:

$$\phi(n) = (p-1)(q-1) = 256\cdot 336 = 86016$$

Now we have to chose an exponent, $e$ that is relatively prime to $\phi(n) = (p-1)(q-1)$. The pair $(e, n)$ is our public key that is used to encrypt messages.

$$e = 17$$

$17$ is relatively prime to $86016$ because they share no factors. We know this because $17$ itself is a prime number, so its only factors are $1$ and $17$. $9113$ is not divisible by $17$, so the numbers are relatively prime.

Our next step is to calculate a value for $d$. If you recall from the RSA algorithm, $d$ must be chosen so that it is the inverse of $e$, modulo $n$. So for our example, we must find a number such that:

$$e\cdot d \equiv 1 \mod \phi(n)$$

$$17 \cdot d \equiv 1 \mod 86016$$

To solve for d we use the Extended Euclidean Algorithm which can be used to find multiplicative inverses.

Using the Extended Euclidean Algorithm, we can calculate one possible value for $d$ is $65777$. We can check the algorithm by computing $e*d \mod \phi(n)$ and ensuring it equals $1$.

$$e\cdot d \mod \phi(n) = 17\cdot 65777 \mod 86016 = 1118209 \mod 86016 = 1$$

$d$ is our private key and is used to decrypt our messages. Now that we have both a public key and a private key, we can encrypt and decrypt messages.

$$\hbox{Pub } = (e,n) = (17, 86609)$$

$$\hbox{Priv } = (d,n) = (65777, 86609)$$

To encrypt a message m, we first convert it into a large integer. Then we calculate m^e \mod n. The result is the encrypted message, or ciphertext, $c$. Let’s send the text “Hi”. In order to do this, we must convert the message into an integer. We’ll use the integer $18537$ to represent our text.

$$c = m^e \mod n$$

$$c = 18537^{17} \mod 86609 $$

$$c = 12448$$

Now, can we decrypt $12448$ back into the original message, $18537$? To decrypt a message we use the private key, $(65777, 88609)$

$$m = c^d \mod n$$

$$m = 12448^{65777} \mod 86609$$

Here we use the Chinese Remainder theorem, an easy way to solve $a^b \mod n$

$$m = 18537 \mod 86609$$

Indeed, when we perform decryption on our ciphertext, we are left with the original message.

---

One more thing:

It's my understanding that public keys are generated from the private key using a one-way, or trapdoor function

Not always. In Diffie-Hellman key exchange, you start with a private value $x$ and generate $g^x \mod p$ as a public key, given suitable $g$ and $p$ (and are known to the public). However, for RSA, you pick secret primes $p$ and $q$ and from that generate the public key $(N=pq, e)$, such that $\gcd(e, (p-1)(q-1)) = 1$. And from that you can derive the decryption exponent (private key) $d$, such that $ed \equiv 1 \bmod (p-1)(q-1)$.

Answer 2

Thank you to ilkkachu and galvatron for pointing me in the right direction with this answer, I'll go into more descriptive detail on the exact encoding and decoding process.

For this example I'll be using RSA encryption keys.

public key  : (n=32652967, e=8749163)
private key : (n=32652967, d=16193959)

So, let's say we want to encrypt and send the message "Hey" to another computer. We'll do that in a few steps.

1. Convert the string into a number. We can use hexadecimal values to do this, as hexadecimal values can simultaneously represent characters or numbers depending on their interpretation. So, converting from String -> Hex -> Integer:

   "Hey" -> 0x486579 -> 4744569
   

2. Now, we use the public key of the computer we're sending the message to, and use it to encrypt the data. (m : message, c : encrypted message)

   m^e % n = c
   4744569^8749163 % 32652967 = 24978475
   

   This integer is then sent to the receiving computer, and if intercepted, it is encrypted and doesn't translate into usable hex (0x17d242b).

3. Now, the receiving computer will use its own private key on the integer data that it received to turn it back into a number that con be converted to usable hex.

   c^d % n = m
   24978475^16193959 % 32652967 = 4744569
   4744569 -> 0x486579 -> "Hey"
   

   And just like that, some data has been encrypted using a computer's public key, sent, and then decrypted by it's private key.