Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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

This concept of asymetric encryption is not very intuitive for me. Simply said I would except 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?

share|improve this question

migrated from security.stackexchange.com Jul 28 '13 at 21:49

This question came from our site for Information security professionals.

    
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. –  Nermin Huskić Jul 28 '13 at 19:20
1  
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. –  Paŭlo Ebermann Jul 29 '13 at 7:15

4 Answers 4

up vote 5 down vote accepted

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.

share|improve this answer
    
Thanks Uwe this is very helpful! (I think the p in your formulas is acutally the n of n=p*q.) 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=p*q. 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? :) –  king_julien Jul 29 '13 at 7:00
1  
@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. –  Uwe Plonus Jul 29 '13 at 7:06
    
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$? –  rubo77 Aug 14 at 9:27
    
@rubo77 n is an arbitary chosen value. The concrete constraints for this value depends on the algorithm used. –  Uwe Plonus Sep 8 at 8:48

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.

share|improve this answer
    
Thank you, this is a nice analogy which I should use in the future! Just for myself I required a mathematical explanation. –  king_julien Jul 29 '13 at 8:52

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.

share|improve this answer
    
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. –  king_julien Jul 28 '13 at 19:05
    
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? –  king_julien Jul 28 '13 at 19:05
2  
The point is exactly that it doesn't. $\:$ Nowhere. $\;\;\;$ –  Ricky Demer Jul 28 '13 at 22:01
1  
@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. –  king_julien Jul 29 '13 at 6:08

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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