0
$\begingroup$

This question already has an answer here:

How does asymmetric crypto work?

For example, if you use PGP in emails, you generate a private key that is known only to you and a public key, which is available to everyone.

Is there a simple way to explain, why you need a private key and why no one can decrypt the message with just the public key?

I think of an explanation like for example with prime numbers:

  • If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
  • Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. (See one-way functions for more information.)
  • The product of the two prime numbers can be used as a public key
  • The primes themselves as a private key. So the private key is the knowledge of two very large prime numbers

for easy understanding lets take the simple example (very large) prime numbers: 3 and 5:

  • private key: the knowlege of 3 and 5
  • the public key is just those numbers multiplied: 15
  • you cannot find out 3 and 5, so the message encrypted with 15 is ...

Here is a quite good explanation already, but it is not clear enough:
Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

Can you please add an example with those numbers?

$\endgroup$

marked as duplicate by otus, Gilles, DrLecter, e-sushi, poncho Aug 19 '14 at 2:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from security.stackexchange.com Aug 16 '14 at 10:25

This question came from our site for information security professionals.

  • $\begingroup$ I don't quite understand your question. Do you need a non technical explanation of PKI and the key exchange process? $\endgroup$ – ilikebeets Aug 14 '14 at 8:20
  • 2
    $\begingroup$ Are you sure that the wikipedia article doesn't explain everything? $\endgroup$ – Artjom B. Aug 14 '14 at 8:44
  • 3
    $\begingroup$ Because that is the whole POINT of asymmetric crypto. $\endgroup$ – Aron Aug 14 '14 at 9:19
  • 1
    $\begingroup$ @rubo77 because this is how PKI works. If you want to study how PKI works, I can recommend a book or two on PKI. The "simple" explanation takes chapters there and is not suitable for StackExchange format. $\endgroup$ – Eugene Mayevski 'Allied Bits Aug 14 '14 at 9:51
  • 1
    $\begingroup$ @rubo77 what is it you want? You have all the information you need. If you don't understand RSA its because you don't understand maths. For example...do you understand Fermat's Little Theorem? If you do, would the derivation of it be required for you "understanding" of RSA? $\endgroup$ – Aron Aug 14 '14 at 9:51
3
$\begingroup$

I stumbled onto this great write up by Cloudflare a while ago as I was trying to understand Elliptic Curve Crypto better. It however starts of with some background on Public Key Cryptography followed by a detailed explanation and example of RSA key pair genaration AND how those keys (smallish primes) are used to encrypt a basic message. I suspect you will find that example answers some of your questions.

Specifically refer to the sections titled "The dawn of public key cryptography" and "A toy RSA algorithm".

All subsequent sections deal with ECC and go into a fair amount of detail (a great article on the whole).

Edit: If you tinker with the values in the example it should illustrate why the mathematics would not allow you to decrypt a message using the public key.

$\endgroup$
2
$\begingroup$

Symmetric encryption works with a single key because the function that is used to encrypt/decrypt is symmetric: f(f(x)) = x. In asymmetric encryption, you have two functions that inverse each other (called inverse functions). You get security only from the fact that only one of these functions is public, and the other one is hidden.

To make it more practical, we set functions (crypto algorithms) that are always known but are instantiated with a parameter (the key) in a large input space. So, there is a space of possible functions once the key is set, and they have only one inverse function in the other set of inverse functions.

You set a public key parameter for the encryption function and then there is only one possible private key parameter that would make the decryption function an inverse of the encryption function. Alternatively when you want to sign a message, you use the private key parameter for the encryption function (applied on a hash of your message) and only the public key parameter will make the decryption function the correct inverse.

Since the functions are known to everyone, we must protect the secret parameter. It must be very hard to guess the private parameter from the public one, which is why functions that are computationally expensive are used to build pairs of keys that maintain the inversion of crypto functions. Any arithmetic operations that are easy to perform in one way and hard to perform the other way around allow you to build such a pair, and you can then build inverse functions that can be instantiated with this pair of keys.

$\endgroup$
2
$\begingroup$

Here is a very basic analogy. Modular exponentiation is far more complex, but say we have two numbers.

If I have one number (Say, 1537) and I divide it by another number (say, 3) and I said "find the remainder", that would be very easy. You would simply divide 1537/3 with the remainder of 1.

However,, if I said "the remainder is 4 and the divisor is 6. Find the number." that would be nearly impossible without trial and error. It could be 4, 10, 16, 22, 28, etc...

$\endgroup$
2
$\begingroup$

In the case of RSA, the key element is modular exponentiation.

Modular means that you are doing all computations modulo a given integer n: whenever you add, subtract, or multiply integers together, you then do a division of the result by n, and you keep only the remainder.

For instance, if you multiply 8 with 11 modulo 15, you first get 8×11 = 88, and 88 is equal to 5×15+13. The remainder of the division of 88 by 15 is then 13. Therefore, we say that the product of 8 by 11 modulo 15 is 13.

A lot of properties of addition and multiplication on integers also work on modular integers. E.g. you still have distributivity: a(b+c) = ab+ac for all integers a, b and c. Some properties are not maintained, in particular modular integers have no order: none can be said to be greater or lower than any other.

Exponentiation is about doing many multiplications. To make things simple: with RSA, there is a modulus n. Given an integer x modulo n, everybody can compute x3_ modulo n: just multiply x with itself, then again, and do the divide by n to keep the remainder. Thus, computing the cube of an integer is feasible with knowledge of n alone. The reverse operation, i.e. computing a cube root, appears to be much harder: we have no idea how it could be done, except if we know the prime factors of n, in which case it becomes easy again.

So there you have it: you encrypt by computing the cube, you decrypt by computing the cube root. The encryption requires knowledge of the public part (n) only, decryption needs knowledge of the private part (the factors p and q).

For instance, with n = 15, the encryption of x = 7 is 13 (because 7×7×7 = 343 = 22×15+13).

An important point to notice is that modulo 15, every value is a cube of some other value:
  03 = 0 mod 15
  13 = 1 mod 15
  23 = 8 mod 15
  33 = 12 mod 15
  43 = 4 mod 15
  53 = 5 mod 15
  63 = 6 mod 15
  73 = 13 mod 15
  83 = 2 mod 15
  93 = 9 mod 15
  103 = 10 mod 15
  113 = 11 mod 15
  123 = 3 mod 15
  133 = 7 mod 15
  143 = 14 mod 15

Of course, n = 15 is a very small modulus which allows for trying out all values. With a 300-digit integer, such enumeration would be... more difficult.

(Note: I am describing things with cubes and cube roots, but in all generality, RSA uses a public exponent denoted e, which is not necessarily equal to 3. e = 3 is a valid and efficient choice, which works as long as neither p-1 or q-1 is a multiple of 3, where p and q are the prime factors of n.)

See also this answer.

$\endgroup$
1
$\begingroup$

One way to look at public / private key-pairs is to view it as yin and yang.

The yin can encrypt things that only the yang can decrypt.

At the same time

The yang can encrypt things that only the yin can decrypt.

This is used by public key cryptography

  • We publish our public keys.
  • We keep our private keys private.
  • We can send messages that only the designated receiver can decrypt.
  • We can verify signatures of senders that only the authorised sender can create.

Note 1: The PGP algorithm documented at Wikipedia makes it clear that both symmetric and asymmetric keys are used in tandem to actually implement the encryption / decryption.

Note 2: The definitions above such as authorised sender, designated receiver etc are backed by processes to try to ensure the parties involved are correct but on the internet anyone may be a dog and any communication, private key or endpoint may also be compromised.

$\endgroup$
  • 1
    $\begingroup$ I think the OP understands the concept, he wants a demonstration of how it's done in the real world. $\endgroup$ – Chris Murray Aug 14 '14 at 10:28

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