Can someone logically explain public/private key asymmetric encryption?

abefroman · 09-01-2009, 11:45 AM

Can someone logically explain public/private key asymmetric encryption?

In other words how can a private key of AAA be used to decrypt a sentance like "The brown fox jumped over a fence." which is encrypted with the public key BBB?

TIA

win32sux · 09-01-2009, 11:59 AM

Quote:

Originally Posted by abefroman

Can someone logically explain public/private key asymmetric encryption?

In other words how can a private key of AAA be used to decrypt a sentance like "The brown fox jumped over a fence." which is encrypted with the public key BBB?

That's just the way it's designed to work. Anything encrypted with the public key is decrypted with the private key, and vice-versa. There's a good guide here. If you're interested in the math, a book like this might hold the key.

H_TeXMeX_H · 09-01-2009, 12:20 PM

Here's a nice analogy I heard on some show, actually it's here in the wiki:

Quote:

A postal analogy

An analogy which can be used to understand the advantages of an asymmetric system is to imagine two people, Alice and Bob, sending a secret message through the public mail. In this example, Alice wants to send a secret message to Bob, and expects a secret reply from Bob.

With a symmetric key system, Alice first puts the secret message in a box, and locks the box using a padlock to which she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he uses an identical copy of Alice's key (which he has somehow obtained previously, maybe by a face-to-face meeting) to open the box, and reads the message. Bob can then use the same padlock to send his secret reply.

In an asymmetric key system, Bob and Alice have separate padlocks. First, Alice asks Bob to send his open padlock to her through regular mail, keeping his key to himself. When Alice receives it she uses it to lock a box containing her message, and sends the locked box to Bob. Bob can then unlock the box with his key and read the message from Alice. To reply, Bob must similarly get Alice's open padlock to lock the box before sending it back to her.

The critical advantage in an asymmetric key system is that Bob and Alice never need to send a copy of their keys to each other. This prevents a third party (perhaps, in the example, a corrupt postal worker) from copying a key while it is in transit, allowing said third party to spy on all future messages sent between Alice and Bob. So in the public key scenario, Alice and Bob need not trust the postal service as much. In addition, if Bob were careless and allowed someone else to copy his key, Alice's messages to Bob would be compromised, but Alice's messages to other people would remain secret, since the other people would be providing different padlocks for Alice to use.

In another kind of asymmetric key system, Bob and Alice have separate padlocks. First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice. When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob. When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice. This three-pass protocol is typically used during key exchange.

http://en.wikipedia.org/wiki/Public-key_cryptography

That helped me understand it.

win32sux · 09-01-2009, 01:07 PM

I remember going through several Bob/Alice/Eve analogies for asymmetric encryption in an information security course I had to take once. Pretty much everyone in the course already had a basic understanding of how asymmetric encryption worked, so a lot of the time in that section was spent discussing how the analogies were flawed. I do understand that we all have different styles of learning, though, and I can definitely see the value in these things.

H_TeXMeX_H · 09-01-2009, 02:07 PM

Well, flaws can be found in any analogy, but it often does help to get at least the basic concept ... you can get into details later.

win32sux · 09-01-2009, 03:08 PM

Quote:

Originally Posted by H_TeXMeX_H

Well, flaws can be found in any analogy, but it often does help to get at least the basic concept ... you can get into details later.

Oh, I agree. It's just that the nature of cryptography presents a very unique challenge when it comes to analogies. Mind you, asymmetric encryption is probably not even at the top of the list. The weirdest cryptographic analogies I've ever been exposed to are the ones for hashes. There you basically trade Bob and Alice's padlock, key, and box for all sorts of things ranging from tropical fruit milkshakes to deoxyribonucleic acid - none of which actually manage to convey the cryptographically secure nature of the hash, but they do get people's mind somewhere in the same ball park (or a few blocks away from it), at least. Like you said, the actual details (technically sound ones, that is) can come later.

Wim Sturkenboom · 09-02-2009, 07:52 AM

I think the biggest problem for understanding public key encryption is the fact that there is a mathematical relationship between the encryption (public) key and the message to encrypt on the one hand and the decryption (private) key and the encrypted message on the other hand. All the explanations here bypass that point which in my opinion was the main question..

Reading http://en.wikipedia.org/wiki/RSA#Operation explains it reasonable easy; you don't have to understand the maths (my opinion; I do not understand them fully) to understand that there is the above relationship.

The important thing to understand from above link is that there are 4 numbers (encryption key e, decryption key d, the product of two prime numbers n and the clear text message m, also represented as a number). How to convert your text or picture to a number of integers is outside the scope of this explanantion but a simplification could be to think of each character in your text as being a number (see asciitable where e.g. A equals 65).

If you understand power and modulo, below the basic calculations (where c is the encrypted message and the other ones match the ones above), taken from the above article)

Code:

encrypt: c = (m^e)%n
decrypt: m = (c^d)%n

Also important to note is that if one knows e and n, one still can not get the original message back. This is because the modulo throws away part of the information that is required to decrypt using the public key.