4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Depends on the algorithm, and multiplication of integers or reals doesn't make a really good one-way function. There are trivial examples of, say, RSA in a lot of places, they should get you started. But remember that there are real-world issues, which require e.g. padding. $\endgroup$ – ilkkachu Jun 14 '17 at 19:32
  • $\begingroup$ This article has a working example of RSA key generation and encryption / decryption using small numbers (<200). $\endgroup$ – Eddie Jun 15 '17 at 18:56
  • $\begingroup$ 8gwifi.org/DHFunctions.jsp use this website to debug $\endgroup$ – anish Dec 1 '17 at 6:39
10
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ RSA as shown is very unsafe, and that's not only because n is too small: problem is that a guess of the message is easily verified. $\endgroup$ – fgrieu Jun 16 '17 at 20:49
  • $\begingroup$ I am sorry to reply like this, but i dont have reputation to make comments yet.. there is some error in @galvatron message.. These values seems to be inverse numbers to 17: - 1265 - 6641 - 12017 - 17393 - 22769 - 28145 - 33521 - 38897 - 44273 - 49649 - 55025 - 60401 - 65777 - 71153 - 76529 - 81905 using any of these numbers as alternate private keys the message may be decoded.. (M^17|86609)^12448|86609 == (M^17|86609)^1265|86609 $\endgroup$ – Scholtz Oct 17 '17 at 15:38
  • 1
    $\begingroup$ That's because ed=1 mod (p-1)(q-1) is sufficient but not necessary; only mod lcm(p-1,q-1) (the Carmichael function) is necessary. lcm(256,336) = 5376 and all your alternatives differ by multiples of 5376. See crypto.stackexchange.com/questions/29591/lcm-versus-phi-in-rsa and crypto.stackexchange.com/questions/16417/… $\endgroup$ – dave_thompson_085 Oct 18 '17 at 3:13
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is not RSA: $n$ is prime! Further the values for $d$ and $c$ are wrong. See also that comment $\endgroup$ – fgrieu Jun 16 '17 at 20:45
  • $\begingroup$ @fgrieu Thanks, an extra 9 snuck into the n value. Fixed. $\endgroup$ – Skyler Jun 19 '17 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.