It took me a lot of time to find a neat explanation of asymmetric encryption. Many sides say “a message is encrypted using a public key and it can only be decrypted with a corresponding private key.” Okay, fine, but how does it work in detail? Finally I found the RSA-entry in wikipedia. It’s almost what I was looking, but there are still lots of links to mathematical definitions and calculations you can’t do with your pocket calculator. So I decided to write a little compilation of the presented algorithm and to apply it using numbers you can handle. Also small number help to clarify things – but keep in mind that all the numbers are much much much greater in serious encryption.

### How do we get our private-and-public-key-pair?

- Choose two distinct (large) random prime numbers
*p*and q

p = 7, q = 3. - Compute n = p*q. This n is used as the modulus for both the public and private keys

n = 7*3 = 21. - Compute the totient: phi(n) = (p-1)(q-1)

phi(21) = (7-1) * (3-1) = 12. - Choose an integer
*e*such that 1<e<phi(n) and that e and phi(n) share no factors other than 1 (i.e.*e*and phi(n) are coprime.).*e*is released as the public key exponent.

In order to chose an e I will factorize my phi(12) first: 12 = 2*2*3.

I chose e=5. e does not necessarily have to be prime but it makes it easier to avoid sharing a factor. - Compute an integer
*d*to satisfy the congruence relation**d*e mod phi(n) = 1**;*d*is kept as the private key exponent.

“congruence relation” sounds more complicated than it actually is: Take two different numbers and apply the same modulo-operation to them (like mod 3). If the result is the same for both you may call your integers**congruent****modulo***5.*Like 11 and 16 are congruent modulo 5, since**11 mod 5 = 1**and**16 mod 5 = 1**.

So we are looking for a integer d that fits into

d * 5 mod 12 = 1.

I needed some tries here and wrote some lines to find the lowest d = 5. With one d found you can find all but just adding 12 :-). I didn’t want to take 5 as the private key exponent, since having the same exponent for encryption and decryption is… well… stupid. So I’ll choose 17.

17 * 5 mod 12 = 1.

85 mod 12 = 1. Correct!

Do we have our private and our public key now? Yes, we have. Note that a key is not one single number but a pair of two numbers. Both are needed in the processes of encryption und decryption. One is the exponent and the other the modulus. Just a second and you’ll see why.

public key: e =5 (exponent) / n = 21 (modulus).

private key: d = 17 (exponent) / n = 21 (modulus).

### Let’s encrypt something

We have given our public key to anyone we know. And we kept our private key hidden somewhere under the bed. Now a beautiful and clever girl named Alice wants to send me a message. Fortunately the letters of her message can be represented as a stream of bits and we interpret this stream as a number. So her message is 10. It is important that her message is lower than our modulus, we’ll later see why. Let’s call her original message **m** and the encrypted message **c**.

m=10

The encryption it a simple formula: **c = m^e mod n**.

c = 10^5 mod 21

c = 100000 mod 21

c = 19.

So Alice hands me a little note saying “19”. 19? What the hack is that supposed to mean?

### Now the magic happens

I rush back home to find my private key and apply it to “19”

The formula for the decryption look very similar: **m = c^d mod n**.

m = 19^17 mod 21.

m = 5480386857784802185939 mod 21. (Try it using calc.exe)

m = 10!

Wow! Alice says “10” to us. Isn’t 10 the international code for “I would like to date you?” I think so.

### Signing

To encrypt with the public key means you can decrypt only with the private key. The converse is also true – to encrypt with the private key means you can decrypt only with the public key. Try it!

How can utilize this? We can use it to guarantee that a message is from a specific sender.

I have been dating Alice for some time now and we are used to leave messages to each other at a hidden place. Unfortunately another girl – Eve – is very jealous and has spied our secret mailbox. One week ago she found a message from Alice to me. She couldn’t read it, but she threw it away and replaced it by a mean offense against me. She encrypted it using my public key (which is public 🙂 ) and I thought it was written by Alice. The message started a little fight but luckily we found about Eve’s intention and started signing our messages. Now we transfer messages like this:

- Alice writes me a message
**m**. - She encrypts
**m**using my public key, the result is**c**. - Now she encrypts
**c**using her own private key, the result is**cs**(**c**signed) - She leaves me the message
- I decrypt
**cs**using her public key, getting**c**. (Eve can do this as well – but that’s it. She can’t read**c**and she can’t leave me a fake**cs**because she doesn’t have Alice’s private key. - I decrypt
**c**using my private key and get back**m**– bingo!

### Padding

Breaking this code (meaning “decrypt without having the private key”) is always a lot of work and hard trying. But is becomes much easier, when you know that **m** is short. That’s because you only have check that little fraction of configurations where **m = c^d mod n **leads to small **m**s. To avoid this small messages are artificially made longer until they are close to **n**. That process is called padding and even padding can be a tricky task.

### Last question

We know what happens to short messages. But what happens to long messages? It is obvious that messages – seen as a number – can’t be greater than **n-1,** since the **mod n** – part of the decryption formula will never return values >**n-1**. I guess the message is split up in parts, but couldn’t find a satisfying answer. If I do, I’ll let you know.

Take care,

Bob

July 8th, 2009 at 11:36 am

Hi Bob,

based on how you approach the math problem, I find it amazing taking to consider that I am not a math whiz. Anyway, I have a math problem and hoping if you could shed light on it. Just try. Actually this concerns hexadecimal values.

Consider this,

I have a string of hex values, I receive from a particular device as stated below:

#1 Data:

20 02 1e 00 01 3f 01 1d 01 00 02 3f 52 00 01 00 02 3f 52 6d 20 33 00 00 42 61 74 68 00 00 00 00 01 03 03 03 29 3f 09 3f 02 00 08

#2 Data:

20 02 1e 00 01 3f 01 11 01 00 02 3f 52 00 01 00 02 3f 52 6d 20 33 00 00 42 61 74 68 00 00 00 00 01 03 03 03 29 3f 09 3f 02 00 08

#3 Data:

20 02 1e 00 01 3f 01 15 01 00 02 3f 52 00 01 00 02 3f 52 6d 20 33 00 00 42 61 74 68 00 00 00 00 01 03 03 03 29 3f 09 3f 02 00 08

Now using this hex value below, would I conclude that the #1 Data: is identical to my last hex value below:

last hex value:

20 02 1e 00 01 3f 01 18 01 00 02 3f 52 00 01 00 02 3f 52 6d 20 33 00 00 42 61 74 68 00 00 00 00 01 03 03 03 29 3f 09 3f 02 00 08

You may or may not reply to me but I was hoping if you found something you could reply me back by any chance..

Thanks

August 13th, 2009 at 10:30 pm

Nice article. A description of a method that allows both hashing and decryption of asymmetric passwords you can find here http://www.developers-blog.org/blog/default/2009/07/05/Public-Key-based-asymmetic-password-hashing.