16
$\begingroup$

I have just learned about using PGP/GPG for email encryption and one thing bugs me:

How is it possible that a message encrypted with somebody's public key can be decrypted only with that person's private key?

This concept of asymmetric encryption is not easy for me to understand. Simply said, I would expect that the process to encrypt with the public key should be unique and therefore be able to be reverted with the same key.

What's the key operation that ensures this is not possible?

$\endgroup$
2
  • $\begingroup$ Yes, You are wright Johnatan. As you know this is one-way function. It it is almost impossible to find her invert function in normal time. For true Rsa, you use numbers that has 100 digits. So their product will have about 200 digits. By that Brute force is useless. I would reccomend You to read a bit from math side to understand it. $\endgroup$
    – Nermin Huskić
    Jul 28, 2013 at 19:20
  • 1
    $\begingroup$ Actually, for each modulus-public exponent pair there are multiple private exponents which all can decrypt the messages encrypted with the public key. Some of them take a bit longer than the other ones. $\endgroup$ Jul 29, 2013 at 7:15

5 Answers 5

10
$\begingroup$

The basic explanation is that you need both keys to make a complete encryption/decryption cycle.

Basically the encryption works with modulo arithmetic so that

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

and

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

where $a$ and $b$ are the public and private key of the algorithm. $m$ is the plain text message and $c$ s the ciphertext.

The most important thing about the formulas is

$$m=(m^a)^b \mod n = (m^b)^a \mod n$$

For this to work $a$, $b$ and $n$ must follow certain restrictions.

This is the basic idea behind RSA and other asymmetric encyption systems whereas you can make the operations more complex/different but the basic idea that using two different keys to complete the encryption/decryption cycle.

$\endgroup$
6
  • $\begingroup$ Thanks Uwe this is very helpful! (I think the p in your formulas is acutally the n of n=pq.) So, if we were to decrypt the ciphertext but only had the public key, we would need to calculate the private key as I can see in the second formula. To calculate the private key we would need to determine the primes in n=pq. Then we get d using: d=(1 mod ((p-1)(q-1))/e which is computally very expensive to brute force in order to find primes p and q. That's it, right? :) $\endgroup$ Jul 29, 2013 at 7:00
  • 1
    $\begingroup$ @king_julien That's it. The difficulty to brute force the parts is the basic security of such algorithms. Also there is no inverse for $m^a \mod p$ which makes it difficult to brute force the algorithms. $\endgroup$
    – Uwe Plonus
    Jul 29, 2013 at 7:06
  • $\begingroup$ You say "where $a$ and $b$ are the public and private key of the algorithm. m is the plain text message and $$c is the ciphertext." and what is $n$? $\endgroup$
    – rubo77
    Aug 14, 2014 at 9:27
  • $\begingroup$ @rubo77 n is an arbitary chosen value. The concrete constraints for this value depends on the algorithm used. $\endgroup$
    – Uwe Plonus
    Sep 8, 2014 at 8:48
  • $\begingroup$ "Where $a$ and $b$ are the public and the private key" implies that $a$ is the public key and $b$ is the private key. But I believe it's the other way, so that it should read "Where $a$ and $b$ are the private and the public key". $\endgroup$ Jan 22, 2016 at 6:13
10
$\begingroup$

Since your problem seems to be with the principle of public key crypto rather than with the math itself, here is an analogy with a physical object that may help.

Take a key lock padlock as below:

Standard Key lock Padlock

To close the padlock, you don't need the key, just the padlock itself. To open you use the key.

Now, if Bob has a copy of Alice's padlock, he can send her a message secretly by putting it in a box and applying the padlock. Alice recovers the message by using the key.

To convert this analogy to public key crypto, just consider that the public key of the system is (a copy of) the open padlock and that the private key is the padlock's key.

This analogy is, of course, not perfect but it may help you to go beyond the apparent paradox of public-key crypto.

$\endgroup$
1
  • $\begingroup$ Thank you, this is a nice analogy which I should use in the future! Just for myself I required a mathematical explanation. $\endgroup$ Jul 29, 2013 at 8:52
4
$\begingroup$

Magic!

enter image description here

Have a look at the wikipedia image from the PGP article. The magic behind how the whole thing works is through the RSA algorithm.

Let's say Alice wants to send an encrypted message to Bob. Bob generates a public and private key pair. How the key generation process works is through a whole bunch of mathematics.

Essentially, this is how RSA works.

  1. Chose two large and distinct primes, $p$ and $q$.
  2. Compute $n = pq$
  3. Chose the public exponent, $e$. This is $65537$ by tradition.
  4. Compute $\varphi(n) = \varphi(p)\varphi(q) = (p − 1)(q − 1)$, where $\varphi$ is Euler's totient function.
  5. Compute $d$ such that $d$ is that multiplicative inverse of $e$ (modulo $\varphi(n)$).

The public key consists of $n$ and $e$ while the private key consists of $n$ and $d$. It is very difficult to derive the private key from the public key because prime factorization is a difficult problem.

The actual encryption of the data is done using a symmetric cipher and a completely random key. Alice then encrypts the random key with the RSA public key belonging to Bob and the encrypted key as well as the encrypted data is sent to Bob.

Bob decrypts the encrypted key using his private key and then decrypts the encrypted message with the decrypted key.

How Alice can be confident that she is using the public key belonging to Bob is a completely different problem involving complicated stuff like a web of trust.

$\endgroup$
4
  • 1
    $\begingroup$ Thank you for the answer! While the illustration is nice, it still leaves the question how using RSA on the encrypted key can only be decrpyted using the private key. The first tip is that RSA uses a one-way function which is the essential characteristic for its asymmetric encryption. Specifically, mathematical integer factorisation is the one-way function used here. $\endgroup$ Jul 28, 2013 at 19:05
  • $\begingroup$ Decryption is only possible with the private key (i.e. with both keys) because RSA requires you to know the two primes used in the calculation. You can calculate the primes used in the RSA encryption only if you have both keys. However, the same should apply to the encryption, right? Of course not apparently, but I don't see it... Hence I'm asking the question: Where in the illustration do we have the private key in the RSA encryption process? $\endgroup$ Jul 28, 2013 at 19:05
  • 2
    $\begingroup$ The point is exactly that it doesn't. $\:$ Nowhere. $\;\;\;$ $\endgroup$
    – user991
    Jul 28, 2013 at 22:01
  • 1
    $\begingroup$ @RickyDemer Well sorry, it's not that obvious to me from this answer. Most of this answer focuses on explaining PGP but the key to my question is how RSA encryption works. I wish that part were explained a bit more elaborated so I could understand it as well. $\endgroup$ Jul 29, 2013 at 6:08
1
$\begingroup$

I guess the canonical of public key crypto is RSA.

RSA is the consequence of a piece of number theory called Euler's Theorem, which says:

$a^{\varphi(n)} \equiv 1 \mod n$

where $\phi(n)$ is Euler's totient function. You can check the Wikipedia article for more information on it, but the important piece regarding RSA is that if $n = pq$, then $\varphi(n) = (p-1)(q-1)$.

The RSA cryptosystem consists of 3 values:

  1. Public exponent $e$
  2. Private exponent $d$
  3. Public modulus $n = pq$ where $p$ and $q$ are primes

To encrypt with RSA, we compute:

$C = M^e \mod n$

To decrypt we compute:

$M = C^d \mod n$

That is, $M = C^d = (M^e)^d \mod n$

To see why this works, we need to look at the relationship between $e$, $d$, and $n$

We choose $e$ and $d$ such that:

$ed \equiv 1 \mod \varphi(n)$

$e$ and $d$ are multiplicative inverses $\mod \varphi(n)$.

That is, $ed$ is some multiple of $\varphi(n)$, plus $1$.

All we're really doing is taking advantage of Euler's theorem:

if

$a^{\varphi(n)} = 1 \mod n$

then

$a^{k\varphi(n)} = 1 \mod n$

$a^{k\varphi(n)+1} \equiv a \mod n$

$ed = k\varphi(n) + 1 \mod \varphi(n)$

$ed \equiv 1 \mod \varphi(n)$

Given $M^e \mod n$ it is difficult to compute $M$. This is known as the RSA problem and there is no known efficient solution.

Given $n$ and $e$, it is difficult to compute $d$. This is because to compute $d$, we need to know $\varphi(n)$. We cannot compute $\varphi(n)$ without knowing the factors of $n$.

The most efficient solution to these problem is integer factorization. This is where RSA gets its security.

$\endgroup$
1
  • $\begingroup$ what is k in your formula ? $\endgroup$
    – Vadym B.
    Apr 28, 2021 at 19:25
0
$\begingroup$

Understand that RSA, simply, is a substitution algorithm. Instead of an alphabet of 26 letters, it becomes an alphabet of $N$ letters. The nature of the public exponent $e$ create a bijective mapping of $M$ to $C$, while the private exponent $d$ creates an inverse bijective mapping of $C$ to $M$, due to the $e$, $d$ pair creating a RSA Identity for each $N$.

If a random $d$ is not the modular multiplicative inverse of $e$, it will not create a RSA Identity. Further, it may, or may not, create a bijective mapping, but will not create the inverse bijective mapping needed to decrypt the message.

Note, there are multiple private exponents $d'$ that pair with $e$ which also create a RSA Identity, and will therefore decrypt the message, though these are equally as hard to find as $d$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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