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

## Recent Comments