Public Key Encryption process

Factual Questions
1

Basically I would like to know how Public Key Encryption works.
From What I could research on the Internet, a message is encrypted using a key that is available to anyone - a public key.
In order to decrypt the message, you need a private key - availbale only to those people that are allowed to read the decoded message.

The public key (from what I understand), can be a very large number (128 digits) that has only 2 prime factors - let’s say a 63 digit and a 64 digit number. So, how exactly does this work?

I have found NO sites that explain how this could work on a very simplistic level. Could anyone give a simple example of how a message could be encoded with a public key of 3589 and then decoded by its private key the 2 prime factors of the public key which are 37 and 97 ?

2

Your numbers are a bit large to work with spontaniously, do you mind if I use 3 and 17 instead? And I’m only going to discuss the RSA public key algorithm here, which is the most popular.

Okay, to quickly summarize http://www.faqs.org/faqs/cryptography-faq/part06/ …

A public key cryptosystem is defined by four major components:

A public key. (aka the encryption key)

A private key. (aka the decryption key)

An encryption function, which takes the public key and a plaintext message and gives back an encrypted message.

A decryption function, which takes the private key and an encrypted message, and gives back a plaintext.

The encryption function has a special property - it’s something that’s fairly easy to compute, but very hard to guess what the inputs were if you only know the answer. The modulo (remainder) operation explained below is an example of one such function.

But back to RSA. RSA’s two keys are based on two (very large!) prime numbers. These two numbers are known as P and Q. These numbers are not the keys, but the keys are made from them.

There are also two other numbers involved, called e and d. These are essentially arbitrary and are picked because we need them to do the math in the encryption and decryption functions. They have certain mathematical qualities relative to p and q - see the link if you care. Basically, (de - 1) must be divisible by (p-1)(q-1). I believe this is so that the modulo math in the encryption and decryption functions will work correctly, though my understanding is sketchy.

Speaking of modulo math, let’s cover that quickly. Modulo math is when you divide one number by another and then find the remainder. Remember this from 5th grade? Like, 7 divided by 3 is 2, with a remainder of 1? Because 3 * 2 = 6, plus 1 = 7.

Another way to think of modulo math is adding times together. If it’s been 14 hours since 11 o’clock, what time is it? Well, the clock wraps around at 12 hours, so 14 - 12 = 2. 11+2 = 13, but it wraps around at 12 again so 13 - 12 = 1. So 14 hours past 11 o’clock is 1 o’clock.

Notice that if you only know the answer, 1, it’s very hard to know what the two input numbers were. It could be 2 and 3, 6 and 13, or possibly even something like 25 and 76.

Now maybe you can see the beginnings of the encryption already. If you and some friends wanted to share secret messages. You could assign A=1, b=2, c=3, etc and write each other long strings of numbers, but that might be figured out pretty fast. A slightly (only slightly, it’s still easy to break) more clever method might be to pick a random number, and then tell your friends the random number. Then when they want to encrypt a message, they take the number of each letter, and modulo the random number with it. Now A=17 or something crazy like that.
Okay, here’s the encrypter and decrypter functions for RSA. Remember, p and q and prime numbers, e and d are more or less arbitrary numbers picked so they have the above mentioned properties with regard to p and q. We will turn our message to be sent into a number as well, perhaps by changing the letters into numbers ala A=1, B=2, C=3, etc, and then lumping them together. So “ABC” becomes “123”. (In RSA, the number representing the plaintext of a message can be any number up to 2^512, which is roughly 4.2 billion ^ 16, so you have plenty of message size to play with…

The encrypter function is:

Encrypted = (Decrypted ^ e) modulo (p*q)

The decrypter function is:

Decrypted = (Encrypted ^ d) modulo (p*q)

The information you need to encrypt a message is p * q and e. So the public key in RSA systems is the pair of numbers: (e, p*q).

Similiarly, the information you need to decrypt a message is (d, p*q). This is the private key.

Besides the modulo problem, the security of the system rests on the fact that it’s hard to deduce p and q from p times q. Especially when p is 256 bits long, and q is 258 bits long, as they are in RSA. You can safely publish (pq, e) in every newspaper in the world and it’s going to be very, very, VERY difficult for someone to deduce the individual p and q from that. And since e was chosen more or less at random, you’re not giving away much there either. As the link I gave earlier says, nobody has figured out any good way to get p and q from (pq, e). The only ways we know are brute-force methods that are very slow - they take the fastest computers we can make right now several days to break even a really short message.
Now, a quick runthrough of the math. Before we encrypt or decrypt we need to generate p and q. We’ll just pick 3 and 17 since they make the math easy.

Now we need to find e and d. (ed - 1) has to be divisible by (p-1)(q-1). So (ed - 1) has to be divisible by (2 * 16) or 32. Now, we have a fair bit of lattitude here, because e and d can be very large if we want them to be, and they don’t have to be prime either. They can be just about anything as long as they satisfy the equation. To keep the math decently simple, I will choose 63 (32 * 2 - 1) as what ed - 1 will equal. Now, since ed - 1 = 63, ed = 64. Again, I will more or less randomly choose e as 4 and d as 16, since 4 * 16 = 64.

Okay, so we have p and q and e and d. Next, we choose our message. How about “A” = 1? (Yeah, yeah, I know - if we use only a single digit for each letter, we can only do up to J before we run out of numbers. I’m trying to keep the math easy, alright?)

Now we do the math:

Encrypted = (Decrypted ^ e) mod (p*q)

Encrypted = (1 ^ 4) mod (51)

This is easy enough I can do it in my head: 1 to the anything = 1, and 1 mod anything = 1. So:

1^ 4 mod 51 = 1

This is not so good - our cyphertext really ought to be different than our plaintext. This happened because I chose “1” as the plaintext. In reality I think RSA pads any message that’s too short (too small a number) so this kind of thing doesn’t happen.

Well, let’s work the decryption:

Decrypted = (Encrypted ^ d) mod (p*q)

Decrypted = (1 ^ 16) mod (51)

Again, we’ve lucked out - 1 to the or mod anything is 1, so:

1^ 16 = 1, and 1 mod 51 = 1

Thus we have our “A” again. Actually, this example is a cheat. As mentioned before, the math doesn’t work out right unless short messages are padded to be longer than (pq) or (ed - 1) or something. But hopefully this will give you an idea how things work.
-Ben

3

Very good and concise explanation MikeRochenelle. Thanks.

4

Here’s another good source of info on all things crypto from the boffins at RSA Labs

5

Pretty good explanation MR for someone who claims his understanding is sketchy. Let me just add some explanation of the mathematics behind it all.

First let me write x = y (mod z) to mean that z divides x - y (or that x and y leave the same remainder when divided by z). Then this “modular” equality has all the properties of ordinary equality. In particular, if x = y (mod z) and x’ = y’ (mod z), then xx’ = yy’ (mod z) and x + x’ = y + y’ (mod z). Also subtraction and also division provided what you divide by has no factors in common with z.

Then Fermat showed (“Fermat’s little theorem”) that if P is a prime, then any number a (all numbers are positive integers here) satisfies a^P = a (mod P). In fact, if e = 1 (mod P - 1) implies that a^e = a (mod P). Euler generalized this as follows: Let N be a square free number (not divisible by an square > 1). Then there is number, denoted phi(N), which I will explain later, with the property that for any e such that e = 1 (mod phi(N)) and any number a, a^e = a (mod N). This is actually very easy to prove from Fermat’s little theorem.

Now what is phi(N)? It is the number of numbers that are less than (or equal to) N and have no divisors in common with N. So phi(12) = 4, since only 1, 5, 7, and 11 are less than 12 and have no divisors in common with 12. (The “or equal to” clause is there only to make phi(1) = 1). phi is called Euler’s function, BTW. When N is a prime, phi(N) = N - 1. When N = PQ is a product of two primes, then phi(N) = (P-1)(Q-1). And this is the basis for RSA cryptography.

6
      • I will toss in a 2-cent explanation that involves no math: the encryption/decryption function requires two particular numbers. It can be encoded with either, and then decoded with the other. Messages can also be encrypted more than once with different numbers, and are still recoverable as long as they are unencrypted with the correct paired numbers. So one of those numbers becomes your “public” number key you give out to anybody, and the other you keep secret as the private key.
  • So, let’s say you want to send secret message to George. Your public key is listed on your own website, and George’s public key is listed on his website. So you write your message, and then first you encrypt it with your private key, and then you encrypt it with George’s public key. Then you send the whole thing to George.
  • When George receives it, the email address says it’s from you, so he first unencrypts it with your public key, and then unencrypts it with his private key, and there’s the message. George knows that the message is really from you, because if it hadn’t been encrypted with your private key, it wouldn’t have unencrypted properly with your public key. And he knows the message was meant for him, because if it wouldn’t have been encrypted with his public key, it wouldn’t have unencrypted with his private key. And since nobody else should have more than one of either two sets of two numbers, they can’t read it at all (…unless they have a really really fast computer setup).
    ~
7

Thanks MikeRochenelle, kferr, Hari Seldon, and Doug C.
That was very helpful.

And Mike that was quite a posting. (Roughly speaking 9 screens). Must have taken a lot of work. Thanks.

8

If you’re interested in this stuff, go to your library and grab a copy of Simon Singh’s The Code Book. It has a chapter or two on this, and it’s very readable.

If you’re really interested in this stuff, go to your local college library and grab a copy of Bruce Schneier’s Applied Cryptography. Somewhat less readable, but a classic.

9

MikeRochenelle and the others have given a great explanation of how the algorithm works. In order to turn this into a cryptosystem however, there are a few more things you should know.

In reality, nobody ever encrypts a plaintext message with RSA directly. For one thing, it would be too slow: all currently known public-key algorithms are many orders of magnitude slower than conventional symmetric ciphers, and not practical for large amounts of data. For another, it would be insecure: an attacker could try to guess the message, encrypt it with your public key and check if their guess is correct!

So how it works in practice is: when I want to send you a message, I generate a random number and use that as the key to encrypt the plaintext using a conventional symmetric cipher. I then use your public key to encrypt the random number with RSA, and send you both the conventionally encrypted message and the RSA-encrypted random number. You then use your private key to get at the random number, with which you can decrypt the message.

Likewise, if I want to use my own private key to sign the message, as DougC mentioned, I would not actually sign the entire message. What actually happens is that I use a ‘secure hash’ algorithm to create a ‘summary’ of the message, and sign that. If the algorithm is strong enough, it should be infeasible to create another message with the same hash, so signing the summary is as good as signing the message.

10

Well, what can I say - I’m a big geek, I love this stuff. The post actually flowed out pretty fast. That can sometimes happen when your muse is upon you.

Ask me about mailing around padlocks… ;]
-Ben

11

Although Martin Wold is correct that use of the RSA method is too slow, the idea of guessing the message and encrypting it is ludicrous. Even one misplaced comma will result in an entirely different ciphertext and give no clue whatever. If you are that good at guessing the message, why bother decrypting it? But it is too slow and the way it is used is to encrypt a key for an ordinary cipher.

12

If you want to get involved in cryptography, you have to read this book. It’s that good.

13

When encrypting a message larger than the modulus, you can’t do the entire message in a single operation, so you’d have to divide the plaintext into blocks and encrypt them individually. Guessing a message 512 bits at a time (64 bytes), with each correctly guessed block giving you some hints to the contents of the next block, would be doable in many circumstances – not easy, but a whole lot easier than brute-forcing RSA directly.

Also, not all messages are plain text. A message may be part of an automated system such as a banking application. If the format is known, there may be situations where you could bring down, with some educated guesses, the number of possible messages to a brute-forceable level – say, a few trillion or so. Again, it’s not trivial but it beats having to factor a 2048-bit RSA key.

There are some more subtle attacks on RSA as well; for example, if I could trick you into encrypting with your private key (i.e. signing) a plaintext supplied by me, I may be able to trick you into decrypting a message that was sent to me earlier. I don’t remember the details and I don’t have my copy of Applied Cryptography handy, but see here for a related (and very cool) example.

Sure, there are other defenses against all that, but encrypting non-random data with RSA is definitely a Bad Idea, irrespective of the performance issue.

By the way, another advantage of the hybrid method is that you can send a single message to multiple recipients, simply by including several copies of the randomly-generated number, each encrypted with another RSA key.

14

Sorry, I meant “a message that was sent to you earlier”.

15

>> the idea of guessing the message and encrypting it is ludicrous

Martin Wolf is correct. This technique is very effective and widely used. It was used during WWII to break Enigma. The plaintext which we suspect is part of the cyphertext is called a “crib”. You can have the plain text or a part of it or some idea of it for many reasons and trying it out may give you the break you need. If a message is transmitted encoded in two different cyphers and one is already compromised, then you have a crib. Many messages have standard formats

Cribs were an essential part in breaking the Enigma codes. German weather boats transmiited every day the weather report which was standard and almost as good as plaintext for the allies. The American Segaba cypher was not broken mainly because Americans were much more scrupulous in abiding by safe practices, one of them being that no message could be transmitted on Segaba and other, less secure, cyphers.

16

Snork, splutter.

Hahahahaha.

Sorry, that “German” text was just too funny.
The allies into Enigma coded messages in part by first getting a copy of the “weather code.” This was a book(let) that described the abbreviations to be used in describing the weather and the format of the weather report (time, date, position, temperature, humidity, etc., length of each and positon in mesage, yada, yada yada) to be used.

For some stations, the Allies knew the weather and could put together the weather report in the weatehr code themselves and try to recover it from the Enigma coded message. Some places, the Germans sent the weather reports in Enigma and in clear.

Since the Germans did periodically change codes, the Allies had to break Enigma rather often. Also, different parts of the military used different codes so that knowing the code for, say, submarine stuff wouldn’t help decode Army stuff.

To keep your codes secret, never ever send a message both in clear and encrypted.

17

I believe the Japanese Purple Code was broken because of the formality of all the messages. I may be wrong here, but didn’t all messages start out with the Emperor’s Name and Title no matter what the content?