Expert Cryptography

Encryption, a short tutorial

2010-03-23T00:26:00.000-07:00

Encryption, a short tutorial
How to reverse engineer encrypted files
by Jon
(12 October 1997)

Courtesy of Fravia's page of reverse engineering

Well, soon or later we'll have to collect all encryption essays under a single project. This NEW EDITION of the "encryption" essay by Jon (our encryption specialist, you may want to have a look at his other essays about kremlin and about Blowfish) is VERY interesting for all encryption enthusiasts among us, and I know that many reverse engineers analyze and study encryption methods with real passion (crackers are also pretty interested in this stuff, for obvious reasons :-)
I would like to thank personally Joe Peschel for having helped Jon with this, hope to see some essays by him, on these matters, soon.

Encryption. Copyright by Jon.

With additions and corrections by Joe Peschel.

[September 28th, 1997.]

INDEX:

1. Introduction (the purpose of encryption)

2. How encryption works

3. About decryption

4. How to reverse engineer an encrypted file

(brute force attack and figuring out the key)

5. Algorithms (most known)

6. Encryption programs & Info

[1. Introduction (the purpose of encryption).]

The general purpose of encryption is to scramble computer-information with a password, which

only you should know. You could say that encryption is like a digital key. But why should I use

"digital keys" on my confident computer-information?, you might ask. Well, you lock your door to

your home don't you? An why do you do that? So nobody can steal your things. Encryption is the

same thing. You scramble your data, so it will be useless to people that don't have the right

key.

There's probably a lot of information on your computer that you would like to keep secret.

This could be company information, your financial status, the source codes of your applications,

love-letters, or just XXX-images from the internet (example: what would you say, if your

little brother found the file c:\download\xxx\pamela.jpg on your computer?).

Whatever the purpose is, encryption is the answer. The encrypted file will be ABSOLUTELY

useless to the curious guy/girl.

Encryption could also be used in shareware-program, as a part of the protection scheme. That

won't be described here, but if you want to know more about it, there's a lot of great examples

in the cracking essays from the +HCU'ers and +ORC.

[2. How encryption works.]

The encryption process is when the encryption-program takes the file you have

selected and modifies it with a algorithm (see section 5, for more info about

that). Some encryption programs have multiple algorithms, so the user can select

the one they trust most.

The encryption process works like this: after you've selected the file you wish

to have encrypted, it will ask you for a password. In many cases the password is

hashed. If the encryption program doesn't support a hash function, your encrypted file may

not be so safe, and you will have to enter a password of an required length.

See section 6, which describes the some of the better encryption programs. Many encryption

programs work in CBC mode (Cipher Block Chaining), which adds additional

security. In some implementations of Blowfish, for instance, the CBC Initialization

Vector makes a random 64 bit value.

This makes every encrypted file unique (even if you encrypt the same file, using the same

algorithm, with the same password, it will be different). When using CBC the data

will be encrypted in blocks which are all linked together and that will make the

encrypted data even harder to break. Other encryption programs use ECB

(Electronic Code Book), which is not as secure since it is vulnerable to a known

plaintext attack.

When the encryption process is done, the encrypted data will be written to a file.

Some encryption programs rename the file to something random (that way, nobody can

know what the contents of the file is).

Others just overwrites the source file, with the encrypted one.Some programs also

uses archives. This allows multiple files in one encrypted file. If the program

supports archives, it's likely that it also includes the option to compress the file(s).

This is very handy if you are emailing the file. But public key encryption, such as PGP,

is better suited for e-mail.

[3. About decryption.]

There's not much to say about decryption. It's the reverse of encryption. Before the

decryption process, the program often check the file for some kind of signature (most

encryptors make a signature to the output file, so the decryptor can identify it). This

is handy, because if you try to decrypt a file with a different algorithm/program the

output will be trash.

[4. How to reverse engineer an encrypted file (brute force attack and figuring out the key).]

Many encryption algorithms can be reverse engineered and cracked. Here are a few that have

been: MS Word versions 2-7, Excel, Word Perfect up to version 7, Windows 3.x and 95 screen

savers (see the essay by Lonely Hawk on Fravia's pages), PKzip (Peter Conrad's implementation

of the Biham/Kocher known-plaintext attack), CrypEdit, and Crypt-o-Text.

There is also an essay by Casimir (Fravia's pages) on the reversal of Crypt-o-text. After

the algorithm is reversed (in the most of above programs) it takes only a matter of seconds

to recover a password. The Pkzip known-plaintext attack can take a while, but it is not a

brute-force or wordlist-based cracker.

In strong, properly implemented encryption algorithm the password isn't stored anywhere in

the cryptfile.

Therefore you must take other means:

1. Use a brute force attack program. You can make your own, or fetch one from the

Internet. But this option is very hard; the keysizes in the modern encryption algorithms

are so large that it can take years on a single personal computer. A combined effort of

several hundreds or thousands of machines connected to the Internet, however, can and has

cracked 48-bit RC5 and 56-bit DES.

(See the RSA Data Security Secret Key Challenge at:

http://fravia.anticrack.de/tppmsgs/msgs2.htm#214)

You may also want to build a wordlist from all of the ASCII data on a victim's machine.

2.Another option is to collect all the info you can get

on the person that has encrypted the file. Often people encrypt files with their birthdays

(it can be reversed, or in another format), social security number, dogs name, etc.

3.Often people uses the same codes from a computer-game they like, or a screen-saver or MS-Word

password, Excel, or other snake-oil to encrypt their secret files.

4.Social engineering ala Mitnick.

5. Keyboard loggers, handy little programs that copy keystrokes to a file.

Personally, I've made a program, that puts my 56-bytes password (not only letters,

also special characters) into the clipboard, and then starts my favorite encryption program.

Then I can just press CTRL+V to paste the password.

This is very useful, since nobody else has access to my computer (DO NOT use this method if

someone else has access to your computer, an attacker will discover this fast).

[5. Algorithms (most known).]

Blowfish

Blowfish is one of the most known algorithms today. It's very fast, about 5,2 mb/s in

Window$ 95 on my P200 (it should be even faster on pure 32-bits OS's like WinNT. It's

also one of the most secure (if not THE most secure). It's key-size is up to 448-bits

(56 bytes), and if you use the full key-size, a brute-force attack is senseless.

In standard mode it encrypts in 16 rounds, but it can be expanded (or reduced) to, for

example 32 rounds (which takes twice the time, but gives twice the encryption). Blowfish

was invented by Bruce Schneier, and was published in Doctor Dobb's Journal, issue 4/94.

There hasn't been found any weaknesses so far.

Cobra

Cobra is new algorithm. It wasn't designed from scratch, but is similar to Blowfish.

Cobra was originally designed to be a 128-bit, 24 rounds encryption algorithm, but like

Blowfish it can be changed. It was invented by Christian Schneider, and in April, 1996 it

was posted to the newsgroup sci.crypt.research

DES

This is THE most know algorithm (that doesn't mean that it's the best). The life of DES

(Data encryption Standard, BTW) started in 1974 when a group of IBM scientists collaborated

with the NSA, to develop a secure encryption algorithm. At the start people didn't trust

the algorithm, because it was developed in cooperation with the NSA, but it was soon the

most used. From 1976 to 1997 (it's still being used) it has been used to encrypt federal

non-classified documents. Because it was designed to work in hardware, it's VERY slow when

implemented in software. But that's not the only problem; it's key-size is only 7 bytes (56

bits). Therefore all possible keys can be tried in a few hours on a FAST computer. (Actually

cracking one 56-bit DES key took several months on hundreds of computers, but there have

always been rumors that the US government can crack DES in minutes.

There exist mutations of the DES algorithm, TDES (triple DES), which TRIPLES the key-size

to 21 bytes and NewDES which is much more fast, but not as secure.

GOST

This algorithm is the Russian counterpart to the American DES algorithm. It's has been

used for a long time, but there are no known weaknesses. The keysize is 32 bytes, and it

encrypts in 32 rounds. However the encryption function is more simple than Blowfish.

IDEA

This algorithm is the most used today. It uses a 128-bits key (16 bytes), and is regarded

to be one of the best and most secure algorithm available today. IDEA was developed in

Zurich, Switzerland by Xuejia Lai and James Massey.

RC4

At first, not much was known about this algorithm, because it's implemented in a commercial

product by RSA, and the source-code was not available to the public. But a group named

Cypherpunks made it available to the public by posting the source-code to the sci.crypt

newsgroup. Now, it's also available in RSADSI's BSAFE Toolkit (with the source-code).

There's more info about this algorithm in Bruce Schneier's Applied Cryptography 2nd. Ed.

It's implemented in some programs under other names like psuedo-RC4 (because it's a

trademark of RSA). It was designed by Ronald Rivest.

SAFER

SAFER was invented by James Massey (one of the IDEA designers), and stands for Secure and

Fast Encryption Routine. There are different version, with different key-lengths. The most

used is SAFER SK-128, which uses a 128-bits key-size, but there are also versions with

smaller key-sizes.

SAFER was designed at the request of CYLINK, which is in the words of Bruce Schneier

(designer of Blowfish) "tainted by the NSA". Although SAFER is criticized by Bruce

Schneier, it resists any known form of cryptanalytic attack.

[6. Encryption programs & Info.]

In this section I'll describe some great encryption programs and info (links).

Programs:

My two favorite encryption programs are Blowfish Advanced 95 8.2f and Kremlin 1.21.

Blowfish Advanced is a very powerful program. It has 5 algorithms: Blowfish, Blowfish32

(the same as Blowfish but with 32 rounds; twice the encryption), GOST, Triple-DES and

Cobra.

It uses the full 448 bits of the Blowfish algorithm.

Download it at http://www-hze.fht-esslingen.de/~tis5maha/software.html, and find a reg-code

at http://www.chez.com/jon101514/pc_bfa2f.zip

Kremlin 1.21 is a very handy tool. It's completely drag-n-drop based, and is very easy to

use.

It has 8 algorithms, ASCII, Blowfish, DES, IDEA, NewDES, Safer, Psuedo-RC4 (the same as

RC4) and Vigenere. It's not as safe as Blowfish Advanced 95, as it's maximum key-size is

160 bits, and it only works in EBC-mode (the less secure).

Download it at http://www.mach5.com/ If you have read my essay about it, and was annoyed

that you couldn't select all the algorithms within the program, register it with:

9797708151 (works for both version 1.1, 1.2 and 1.21).

There's a lot of other nice shareware/freeware encryptors on the web.

Try http://www.tucows.com/, http://www.shareware.com/ or http://www.mysharewarepage.com/.

You can also search for a program using Yahoo, etc. But remember because of the stupid and

useless US laws against exporting strong encryption software, you'll at times end up with

cripplewarez, so check that the encryption programs you download are COMPLETE (best areas

for complete downloads, as usual: Russia, Poland, Holland, Scandinavia, Yugoslavija).

Info:

Here are some nice links (including the ones mentioned above in this essay):

http://www.counterpane.com/blowfish.html - The Blowfish Page. Here you'll find info

and the source code of Blowfish.

http://www-hze.fht-esslingen.de/~tis5maha/software.html - Download Blowfish Advanced 95

http://www.mach5.com/ - Download Kremlin (there's also a new section with crypto-info).

http://www.chez.com/jon101514/pc_bfa2f.zip - Blowfish Advanced '95 reg-code.

http://www.tucows.com/, http://www.shareware.com/, http://www.mysharewarepage.com/ -

Lots of shareware/freeware encryptors, but beware of some of the snake-oil programs

(mostly the crippled US encryptors).

http://hack.box.sk/ - Some brute-force attack utils (also has cracks, serials and hack utils)

http://ourworld.compuserve.com/homepages/c_schneider/ - Author of Cobra.

http://www.cs.auckland.ac.nz/~pgut001/links.html - Peter Gutmann's site. Has the biggest

list of crypto-links I've seen!

http://www.sni.net/~mpj/crypto.htm - Nice crypto-page with a LOT of links.

http://fravia.anticrack.de/tppmsgs/msgs2.htm#215 - Joe Peschel's homepage. Lots of brute-force

crackers, encryption info, etc.

Here are some nice Newsgroups

sci.crypt - Great newsgroup, with lots of info.

sci.crypt.research - newsgroup

This essay is only an introduction to encryption from a reverse engineering standpoint.

Visit the sites above for more info and source-codes, etc. I want to thank Joe Peschel.

He helped me make this essay better by correcting errors in and adding new info to it.

Now it's much better :-)

Concise Object Relational Architecture (Cobra)

2010-03-23T00:17:00.000-07:00

Concise Object Relational Architecture

COBRA is an object persistence layer written in the Java programming language. It is uses relational database technology to provided the persistent storage mechanism; however the store is fully encapsulated shielding programmers from the details of relational database access.

A whitepaper fully describes COBRA with examples.

COBRA source code and classes can be down loaded from this site.

Javadocs can be browsed on this site.

History

The original version of COBRA was inspired by the Javaworld article: Reflections on Java, Beans, and relational databases published in September 1997. The current implementation embodies ideas from Scott Ambler's paper on: Mapping Objects To Relational Databases and the sister paper: The Design of a Robust Persistence Layer for Relational Databases.

COBRA has been used as the access mechanism for a large customer services database. This was backed by Postgresql then Oracle 8. However only the features required to solve immediate problems have been implemented. Much further work is necessary.

Developments

COBRA is an open source project. It is provided 'as is'. Anyone can download the source if they find a feature is missing or wish to change the functionality they can do this themselves and even contribute the updates to the master source.

The Solitaire Encryption Algorithm

2010-03-22T22:33:00.000-07:00

The Solitaire Encryption Algorithm

In Neal Stephenson's novel Cryptonomicon, the character Enoch Root describes a cryptosystem code-named "Pontifex" to another character named Randy Waterhouse, and later reveals that the steps of the algorithm are intended to be carried out using a deck of playing cards. These two characters go on to exchange several encrypted messages using this system. The system is called "Solitaire" (in the novel, "Pontifex" is a code name intended to temporarily conceal the fact that it employs a deck of cards) and I designed it to allow field agents to communicate securely without having to rely on electronics or having to carry incriminating tools. An agent might be in a situation where he just does not have access to a computer, or may be prosecuted if he has tools for secret communication. But a deck of cards...what harm is that?

Solitaire gets its security from the inherent randomness in a shuffled deck of cards. By manipulating this deck, a communicant can create a string of "random" letters that he then combines with his message. Of course Solitaire can be simulated on a computer, but it is designed to be implemented by hand.

Solitaire may be low-tech, but its security is intended to be high-tech. I designed Solitaire to be secure even against the most well-funded military adversaries with the biggest computers and the smartest cryptanalysts. Of course, there is no guarantee that someone won't find a clever attack against Solitaire (watch this space for updates), but the algorithm is certainly better than any other pencil-and-paper cipher I've ever seen.

It's not fast, though. It can take an evening to encrypt or decrypt a reasonably long message. In David Kahn's book ``Kahn on Codes,'' he describes a real pencil-and-paper cipher used by a Soviet spy. Both the Soviet algorithm and Solitaire take about the same amount of time to encrypt a message: most of an evening.

Encrypting with Solitaire
Solitaire is an output-feedback mode stream cipher. Sometimes this is called key-generator (KG in U.S. military speak). The basic idea is that Solitaire generates a stream, often called a ``keystream,'' of numbers between 1 and 26. To encrypt, generate the same number of keystream letters as plaintext letters. Then add them modulo 26 to plaintext letters, one at a time, to create the ciphertext. To decrypt, generate the same keystream and subtract, modulo 26 from the ciphertext to recover the plaintext. (Don't worry, I'll explain "modulo" in a minute.)

For example, to encrypt the first Solitaire message mentioned in Stephenson's novel, "DO NOT USE PC":

1. Split the plaintext message into five-character groups. (There is nothing magical about five-character groups; it's just tradition.) Use X's to fill in the last group. So if the message is "DO NOT USE PC" then the plaintext is:

DONOT USEPC

2. Use Solitaire to generate ten keystream letters. (Details are below.) Assume they are:

KDWUP ONOWT

3. Convert the plaintext message from letters into numbers, A=1, B=2, etc:

4 15 14 15 20 21 19 5 16 3

4. Convert the keystream letters similarly:

11 4 23 21 16 15 14 15 23 20

5. Add the plaintext number stream to the keystream numbers, modulo 26. (All this means is, if the sum is more than 26, subtract 26 from the result.) For example, 1+1=2, 26+1=27, and 27-26=1, so 26+1=1.

15 19 11 10 10 10 7 20 13 23

6. Convert the numbers back to letters.

OSKJJ JGTMW

If you're really good at this, you can learn to add letters in your head, and just add the letters from steps (1) and (2). It just takes practice. It's easy to remember that A+A=B; remembering that T+Q=K is harder.

Decrypting with Solitaire

The basic idea is that the receiver generates the same keystream, and then subtracts the keystream letters from the ciphertext letters.

1. Take the ciphertext message and put it in five-character groups. (It should already be in this form.)

OSKJJ JGTMW

2. Use Solitaire to generate ten keystream letters. If the receiver uses the same key as the sender, the keystream letters will be the same:

KDWUP ONOWT

3. Convert the ciphertext message from letters into numbers:

15 19 11 10 10 10 7 20 13 23

4. Convert the keystream letters similarly:

11 4 23 21 16 15 14 15 23 20

5. Subtract the keystream numbers from the ciphertext numbers, modulo 26. For example, 22-1=21, 1-22=5. (It's easy. If the first number is less than or equal to the second number, add 26 to the first number before subtracting. So 1-22=? becomes 27-22=5.)

4 15 14 15 20 21 19 5 16 3

6. Convert the numbers back to letters.

DONOT USEPC

As you can see, decryption is the same as encryption, except that you subtract the keystream from the ciphertext message.

Generating the Keystream Letters
This is the heart of Solitaire. The above descriptions of encryption and decryption work for any output-feedback mode stream cipher. It's the way RC4 works. It's the way OFB mode for DES works. This section is specific to Solitaire, and explains how Solitaire generates those keystream letters.

Solitaire generates its keystream using a deck of cards. You can think of a 54-card deck (remember the two jokers) as a 54-element permutation. There are 54!, or about 2.31 * 10^71, possible different orderings of a deck. Even better, there are 52 cards in a deck (without the jokers), and 26 letters in the alphabet. That kind of coincidence is just too good to pass up.

To be used for Solitaire, a deck needs a full set of 52 cards and two jokers. The jokers must be different in some way. (This is common. The deck I'm looking at as I write this has stars on its jokers: one has a little star and the other has a big star.) Call one joker A and the other B. Generally, there is a graphical element on the jokers that is the same, but different size. Make the "B" joker the one that is "bigger." If it's easier, you can write a big "A" and "B" on the two jokers, but remember that you will have to explain that to the secret police if you ever get caught.

To initialize the deck, take the deck in your hand, face up. Then arrange the cards in the initial configuration that is the key. (I'll talk about the key later, but it's different than the keystream.) Now you're ready to produce a string of keystream letters.

Here's how to produce a single output character. This is Solitaire:

1. Find the A joker. Move it one card down. (That is, swap it with the card beneath it.) If the joker is the bottom card of the deck, move it just below the top card.

2. Find the B joker. Move it two cards down. If the joker is the bottom card of the deck, move it just below the second card. If the joker is one up from the bottom card, move it just below the top card. (Basically, assume the deck is a loop...you get the idea.)

It's important to do these two steps in order. It's tempting to get lazy and just move the jokers as you find them. This is okay, unless they are very close to each other.

So if the deck looks like this before step 1:

A 7 2 B 9 4 1

at the end of step 2 it should look like:

7 A 2 9 4 B 1

And if the deck looks like this before step 1:

3 A B 8 9 6

at the end of step 2 it should look like:

3 A 8 B 9 6

If you have any doubt, remember to move the A joker before the B joker. And be careful when the jokers are at the bottom of the deck. If the joker is the last card, think of it as the first card before you start counting.

3. Perform a triple cut. That is, swap the cards above the first joker with the cards below the second joker. If the deck used to look like:

2 4 6 B 5 8 7 1 A 3 9

then after the triple cut operation it will look like:

3 9 B 5 8 7 1 A 2 4 6

"First" and "second" jokers refer to whatever joker is nearest to, and furthest from, the top of the deck. Ignore the "A" and "B" designations for this step.

Remember that the jokers and the cards between them don't move; the other cards move around them. This is easy to do in your hands. If there are no cards in one of the three sections (either the jokers are adjacent, or one is on top or the bottom), just treat that section as empty and move it anyway. If the deck used to look like:

B 5 8 7 1 A 3 9

then after the triple cut operation it will look like:

3 9 B 5 8 7 1 A

A deck that looks like:

B 5 8 7 1 A

will remain unchanged by this step.

4. Perform a count cut. Look at the bottom card. Convert it into a number from 1 through 53. (Use the bridge order of suits: clubs, diamonds, hearts, and spades. If the card is a club, it is the value shown. If the card is a diamond, it is the value plus 13. If it is a heart, it is the value plus 26. If it is a spade, it is the value plus 39. Either joker is a 53.) Count down from the top card that number. (I generally count 1 through 13 again and again if I have to; it's easier than counting to high numbers sequentially.) Cut after the card that you counted down to, leaving the bottom card on the bottom. If the deck used to look like:

7 ... cards .. 4 5
... cards ... 8 9

and the ninth card was the 4, the cut would result in:

5 ... cards ... 8 7
... cards ... 4 9

The reason the last card is left in place is to make the step reversible. This is important for mathematical analysis of its security.

A deck with a joker as the bottom card will remain unchanged by this step.

Be sure not to reverse the order when counting cards off the top. The correct way to count is to pass the cards, one at a time, from one hand to another. Don't make piles on the table.

5. Find the output card. To do this, look at the top card. Convert it into a number from 1 through 53 in the same manner as step 4. Count down that many cards. (Count the top card as number one.) Write the card after the one you counted to on a piece of paper; don't remove it from the deck. (If you hit a joker, don't write anything down and start over again with step 1.) This is the first output card. Note that this step does not modify the state of the deck.

6. Convert the output card to a number. As before, use the bridge suits to order them. From lowest to highest, we have clubs, diamonds, hearts, and spades. Hence, A-clubs through K-clubs is 1 through 13, A-diamonds through K-diamonds is 14 though 26, A-hearts through K-hearts is 1 through 13, and A-spades through K-spades is 14 through 26. (We need 1 through 26, and not 1 through 52, so we can get to letters.)

That's how to use Solitaire to encrypt a single character. You can use it to create as many keystream numbers as you need; just go through the same six steps once for each output character. (Don't rekey the deck). And remember, you'll need one per message character.

I know that there are regional differences in decks of cards, depending on the country. In general, it does not matter what suit ordering you use, or how you convert cards to numbers. What matters is that the sender and the receiver agree on the rules. If you're not consistent you won't be able to communicate.

Keying the Deck
Before you start producing output cards, you have to key the deck. This is probably the most important part of the whole operation, and the one that the entire security of the system hinges upon. Solitaire is only as secure as the key. That is, the easiest way to break Solitaire is to figure out what key the communicants are using. If you don't have a good key, none of the rest of this matters. Here are some suggestions for exchanging a key.

1. Use identically shuffled decks. A random key is the best. One of the communicants can shuffle up a random deck and then create another, identical deck. One goes to the sender and the other to the receiver. Most people are not good shufflers, so shuffle the deck at least six times. And both parties should keep an additional spare deck in the same keyed order, otherwise if you make a mistake you'll never be able to decrypt the message. Also remember that the key is at risk as long as it exists; the secret police could find the deck and copy down its order.

2. Use a bridge ordering. A description of a set of bridge hands that you might see in a newspaper or a bridge book is about a 95-bit key. Agree on a way to take the bridge-hand diagram and convert it into an ordering of the deck. Then agree on a way to put the two jokers into the deck. (One obvious one is to put the A joker after the first card mentioned in the text, and the B joker after the second card mentioned in the text.)

Be warned, though: the secret police can find your bridge column and copy down the order. You can try setting up some repeatable convention for which bridge column to use; for example, "use the bridge column in your hometown newspaper for the day on which you encrypt the message," or something like that. Or use a list of keywords to the New York Times website, and use the bridge column for the day of the article that comes up when you search on those words. If the keywords are found or intercepted, they look like a passphrase. And pick your own convention for converting bridge columns into deck orderings; remember that the secret police read Neal Stephenson's books, too.

3. Use a passphrase to order the deck. This method uses the Solitaire algorithm to create an initial deck ordering. Both the sender and receiver share a passphrase. (For example, "SECRET KEY.") Start with the deck in a fixed order; lowest card to highest card, in bridge suits, followed by the A and then the B joker. Perform the Solitaire operation, but instead of Step 5, do another count cut based on the first character of the passphrase (19, in this example). In other words, do step 4 a second time, using 19 as the cut number instead of the last card. Remember to put the top cards just above the bottom card in the deck, as before.

Repeat the five steps of the Solitaire algorithm once for each character of the key. That is, the second time through the Solitaire steps use the second character of the key, the third time through use the third character, etc.

Optional step: (This is NOT used in the examples below.) Use the final two characters to set the positions of the jokers. If the second to last character is a G (a 7), put the A joker after the seventh card. If the last character is a T (a 20), put the B joker after the twentieth card.

Remember, though, that there are only about 1.4 bits of randomness per character in standard English. You're going to want at least an 64-character passphrase to make this secure; I recommend at least 80 characters, just in case. Sorry; you just can't get good security with a shorter key.
Sample Output
Here's some sample data to practice your Solitaire skills with:

Sample 1: Start with an unkeyed deck: A-clubs to K-clubs, A-diamonds to K-diamonds, A-hearts to K-hearts, A-spades to K-spades, A joker, B joker. (You can think of this as 1 ... 52, A, B.)

Here's how to generate the first two outputs. The initial deck is:

1 2 3 4 ... 52 A B

After the first step (moving the A joker):

1 2 3 4 ... 52 B A

After the second step (moving the B joker):

1 B 2 3 4 ... 52 A

After the third step (the triple cut):

B 2 3 4 ... 52 A 1

After the fourth step (the count cut):

2 3 4 ... 52 A B 1

The last card is a 1, which means cut one card. Remember that the 1 stays where it is, so the one card (the B, moves to the bottom of the deck just above the 1.

The fifth step does not change the deck, but produces an output card. The top card is a 2, so count down two cards to the 4. The first Solitaire output is 4. (Of course, you're not supposed to remove this card from the deck. Keep the 4 where it is; just write it down somewhere.)

To produce the second Solitaire output, go through the five steps again.

Step 1:

2 3 4 ... 49 50 51 52 B A 1

Step 2:

2 3 4 ... 49 50 51 52 A 1 B

Step 3:

A 1 B 2 3 4 ... 49 50 51 52

Step 4:

51 A 1 B 2 3 4 ... 49 50 52

The last card is a 52, so count 52 cards down to the 51. Cut the single card, the 51 with the rest of the deck. Remember that the 52 remains unmoved.

Step 5 produces the output card. The first card is a 51. Counting down fifty-one cards gets to the 49, which is the second output card. (Again, don't remove the 49 from the deck.)

The first ten outputs are:

4 49 10 (53) 24 8 51 44 6 4 33

The 53 is skipped, of course. I just put it there for demonstration.

If the plaintext is

AAAAA AAAAA

then the ciphertext is:

EXKYI ZSGEH

Sample 2: Using keying method 3 and the key "FOO," (remember that the optional keying step is not used in these examples) the first fifteen outputs are:

8 19 7 25 20 (53) 9 8 22
32 43 5 26 17 (53) 38 48

If the plaintext is all As, then the ciphertext is:

ITHZU JIWGR FARMW

Sample 3: Using keying method 3 and the key "CRYPTONOMICON," the message "SOLITAIRE" encrypts to:

KIRAK SFJAN

Remember that Xs are used to fill out the last five-character group.

Of course you should use a longer key. These samples are for test purposes only. There are more samples on the website, and you can use the PERL script to create your own.
Real Security, Not Security Through Obscurity
Solitaire is designed to be secure even if the enemy knows how the algorithm works. I have assumed that "Cryptonomicon" will be a best seller, and that copies will be available everywhere. I assume that the NSA and everyone else will study the algorithm and will watch for it. I assume that the only secret is the key.

That's why keeping the key secret is so important. If you have a deck of cards in a safe place, you should assume the enemy will at least entertain the thought that you are using Solitaire. If you have a bridge column in your safe deposit box, you should expect to raise a few eyebrows. If any group is known to be using the algorithm, expect the secret police to maintain a database of bridge columns to use in cracking attempts. Solitaire is strong even if the enemy knows you are using it, and a simple deck of playing cards is still much less incriminating than a software encryption program running on your laptop, but the algorithm is no substitute for street smarts.
Operational Notes
1. The first rule of an output-feedback mode stream cipher, any of them, is that you should never use the same key to encrypt two different messages. Repeat after me: NEVER USE THE SAME KEY TO ENCRYPT TWO DIFFERENT MESSAGES. If you do, you completely break the security of the system. Here's why: if you have two ciphertext streams, A+K and B+K, and you subtract one from the other, you get (A+K)-(B+K) = A+K-B-K = A-B. That's two plaintext streams combined with each other with no key involved, and is very easy to break. Trust me on this one: you might not be able to recover A and B from A-B, but a professional cryptanalyst can. This is vitally important: never use the same key to encrypt two different messages.

2. Keep your messages short. This algorithm is designed to be used with small messages: a couple of thousand characters at most. Use shorthand, abbreviations, and slang in your messages. Don't be chatty. If you have to encrypt a 100,000-word novel, use a computer algorithm.

3. Like all output-feedback stream ciphers, this system has the unfortunate feature of never recovering from a mistake. If you're encrypting a message, and you make a mistake in one of the operations, every letter afterwards will be encrypted wrong. You won't be able to decrypt it, even with the key. And you'll never know. So if you're encrypting a message, go through the encryption process twice to make sure they agree. If you're decrypting, check to make sure the message makes sense as you decrypt it. And if you're keying from a random deck, keep a spare copy of the ordered deck for this reason.

4. Solitaire is reversible. This means that if you leave the deck lying around after you've encrypted your message, the secret police can find it and work the algorithm backwards using the deck. This process can recover all of the output cards and decrypt a message. It is important that you shuffle the deck completely, six times, after you finish encrypting a message.

5. For maximum security, try to do everything in your hands and head. If the secret police starts breaking down your door, just calmly shuffle the deck. (Don't throw it up in the air; you'd be surprised how much of the deck ordering is maintained during a game of 52-Pickup.) Remember to shuffle the backup deck, if you have one.

6. Be careful about worksheets, if you have to write things down. They will have sensitive information on them.

Burning is probably the best method of data destruction available, but think about the paper. Ungummed, rice cigarette papers seem ideally suited to this role. A colleague did some tests with Club Cabaret Width papers, and they burn completely.

It's not as difficult to write on cigarette papers as you might think. Using a No. 2 pencil with a fine but blunt tip works well. A No. 3 pencil works better, but it is a bit weirder to be carrying. Pens have a number of problems. First the extremely hard tip of the pen is more likely to leave impressions in the surface below the paper. Also, anything with ink has the possibility to bleed through to the surface below.

And good cigarette papers are made to burn cleanly and completely. The Club papers burned best when allowed to burn in the free air. That is, lit and released at about chest level. These papers also have the advantage of having very low volume and could be easily eaten if required.

They are also extremely thin. These three-inch square papers can be folded six times into a 1 cm square which is about 1 mm thick. One paper can comfortably hold 80 characters in 8 rows of two five letter blocks each. It seems quite possible a reasonably careful writer could fit 120 characters.

7. Solitaire can work on computers. Often only one end of the communications has to use the deck of cards; the other is safe enough to use a computer. Use a computer when you can: it's faster and the computer never makes mistakes.

8. Most card games do not include jokers, so carrying a deck around with them may be suspicious. Be prepared with a story.

9. The security of Solitaire does not depend on the secrecy of the method. I assume that the secret police know that you're using it.
Security Analysis
There's quite a lot of it; watch this space for details.

Learning More
I recommend my own book, Applied Cryptography (John Wiley & Sons, 1996), as a good place to start. Then read The Codebreakers, by David Kahn (Scribner, 1996). After that, there are several books on computer cryptography, and a few others on manual cryptography. It's a fun field; good luck.

test vectors - Perl - Ada - C (#1) - C (#2) - C++ - Delphi - Forth (#1) - Forth (#2) - Java - Javascript - K - Palm OS - Pascal - Perl CGI - Python (#1) - Python (#2) - TCL
Note: only the Perl implementation has been tested by Counterpane.

64-Bit Block Cipher (Blowfish)

2010-03-22T22:01:00.000-07:00

64-Bit Block Cipher (Blowfish)
Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish)

B. Schneier

Fast Software Encryption, Cambridge Security Workshop Proceedings (December 1993), Springer-Verlag, 1994, pp. 191-204.

ABSTRACT:

Blowfish, a new secret-key block cipher, is proposed. It is a Feistel network, iterating a simple encryption function 16 times. The block size is 64 bits, and the key can be any length up to 448 bits. Although there is a complex initialization phase required before any encryption can take place, the actual encryption of data is very efficient on large microprocessors.

The cryptographic community needs to provide the world with a new encryption standard. DES [16], the workhorse encryption algorithm for the past fifteen years, is nearing the end of its useful life. Its 56-bit key size is vulnerable to a brute-force attack [22], and recent advances in differential cryptanalysis [1] and linear cryptanalysis [10] indicate that DES is vulnerable to other attacks as well.

Many of the other unbroken algorithms in the literature--Khufu [11,12], REDOC II [2,23, 20], and IDEA [7,8,9]--are protected by patents. RC2 and RC4, approved for export with a small key size, are proprietary [18]. GOST [6], a Soviet government algorithm, is specified without the S-boxes. The U.S. government is moving towards secret algorithms, such as the Skipjack algorithm in the Clipper and Capstone chips [17].

If the world is to have a secure, unpatented, and freely- available encryption algorithm by the turn of the century, we need to develop several candidate encryption algorithms now. These algorithms can then be subjected to years of public scrutiny and cryptanalysis. Then, the hope is that one or more candidate algorithms will survive this process, and can eventually become a new standard.

This paper discusses the requirements for a standard encryption algorithm. While it may not be possible to satisfy all requirements with a single algorithm, it may be possible to satisfy them with a family of algorithms based on the same cryptographic principles.

AREAS OF APPLICATION

A standard encryption algorithm must be suitable for many different applications:

Bulk encryption. The algorithm should be efficient in encrypting data files or a continuous data stream.

Random bit generation. The algorithm should be efficient in producing single random bits.

Packet encryption. The algorithm should be efficient in encrypting packet-sized data. (An ATM packet has a 48- byte data field.) It should implementable in an application where successive packets may be encrypted or decrypted with different keys.

Hashing. The algorithm should be efficient in being converted to a one-way hash function.

PLATFORMS

A standard encryption algorithm must be implementable on a variety of different platforms, each with their own requirements. These include:

Special hardware. The algorithm should be efficiently implementable in custom VLSI hardware.

Large processors. While dedicated hardware will always be used for the fastest applications, software implementations are more common. The algorithm should be efficient on 32-bit microprocessors with 4 kbyte program and data caches.

Medium-size processors. The algorithm should run on microcontrollers and other medium-size processors, such as the 68HC11.

Small processors. It should be possible to implement the algorithm on smart cards, even inefficiently.

The requirements for small processors are the most difficult. RAM and ROM limitations are severe for this platform. Also, efficiency is more important on these small machines. Workstations double their capacity almost annually. Small embedded systems are the same year after year, and there is little capacity to spare. If there is a choice, the extra computation burden should be on large processors rather than small processors.

ADDITIONAL REQUIREMENTS

These additional requirements should, if possible, be levied on a standard encryption algorithm.

The algorithm should be simple to code. Experiences with DES [19] show that programmers will often make implementation mistakes if the algorithm is complicated. If possible, the algorithm should be robust against these mistakes.

The algorithm should have a flat keyspace, allowing any random bit string of the required length to be a possible key. There should be no weak keys.

The algorithm should facilitate easy key-management for software implementations. Software implementations of DES generally use poor key management techniques. In particular, the password that the user types in becomes the key. This means that although DES has a theoretical keyspace of 256, the actual keyspace is limited to keys constructed with the 95 characters of printable ASCII. Additionally, keys corresponding to words and near words are much more likely.

The algorithm should be easily modifiable for different levels of security, both minimum and maximum requirements.

All operations should manipulate data in byte-sized blocks. Where possible, operations should manipulate data in 32-bit blocks.

DESIGN DECISIONS

Based on the above parameters, we have made these design decisions. The algorithm should:

Manipulate data in large blocks, preferably 32 bits in size (and not in single bits, such as DES).

Have either a 64-bit or a 128-bit block size.

Have a scalable key, from 32 bits to at least 256 bits.

Use simple operations that are efficient on microprocessors: e.g., exclusive-or, addition, table lookup, modular- multiplication. It should not use variable-length shifts or bit-wise permutations, or conditional jumps.

Be implementable on an 8-bit processor with a minimum of 24 bytes of RAM (in addition to the RAM required to store the key) and 1 kilobyte of ROM.

Employ precomputable subkeys. On large-memory systems, these subkeys can be precomputed for faster operation. Not precomputing the subkeys will result in slower operation, but it should still be possible to encrypt data without any precomputations.

Consist of a variable number of iterations. For applications with a small key size, the trade-off between the complexity of a brute-force attack and a differential attack make a large number of iterations superfluous. Hence, it should be possible to reduce the number of iterations with no loss of security (beyond that of the reduced key size).

If possible, have no weak keys. If not possible, the proportion of weak keys should be small enough to make it unlikely to choose one at random. Also, any weak keys should be explicitly known so they can be weeded out during the key generation process.

Use subkeys that are a one-way hash of the key. This would allow the use of long passphrases for the key without compromising security.

Have no linear structures (e.g., the complementation property of DES) that reduce the complexity of exhaustive search [4].

Use a design that is simple to understand. This will facilitate analysis and increase the confidence in the algorithm. In practice, this means that the algorithm will be a Feistel iterated block cipher [21].

Most of these design decisions are not new. Almost all block ciphers since Lucifer [5,21] are Feistel ciphers, and all have a flat keyspace (with the possible exception of a few weak keys). FEAL [13,14,15] and Khufu [11] use a variable number of iterations. Khufu [11] has a large number of subkeys that are a one-way function of the key. RC2 [18] has a variable-length key. GOST [6] uses a 32-bit word length and a 64-bit block size. MMB [2] uses a 32-bit word length and a 128-bit block size.

BUILDING BLOCKS

There are a number of building blocks that have been demonstrated to produce strong ciphers. Many of these can be efficiently implemented on 32-bit microprocessors.

Large S-boxes. Larger S-boxes are more resistant to differential cryptanalysis. An algorithm with a 32-bit word length can use 32-bit S-boxes. Khufu and REDOC III both use a 256-entry, 32-bit wide S-box [11,20].

Key-dependent S-boxes. While fixed S-boxes must be designed to be resistant to differential and linear cryptanalysis, key-dependent S-boxes are much more resistant to these attacks. They are used in the Khufu algorithm [11]. Variable S-boxes, which could possibly be key dependent, are used in GOST [6].

Combining operations from different algebraic groups. The IDEA cipher introduced this concept, combining XOR mod 216, addition mod 216, and multiplication mod 216+1 [7]. The MMB cipher uses a 32-bit word, and combines XOR mod 232 with multiplication mod 232-1 [2].

Key-dependent permutations. The fixed initial and final permutations of DES have been long regarded as cryptographically worthless. Khufu XORs the text block with key material at the beginning and the end of the algorithm [11].

BLOWFISH

Blowfish is a variable-length key block cipher. It does not meet all the requirements for a new cryptographic standard discussed above: it is only suitable for applications where the key does not change often, like a communications link or an automatic file encryptor. It is significantly faster than DES when implemented on 32-bit microprocessors with large data caches, such as the Pentium and the PowerPC.

DESCRIPTION OF THE ALGORITHM

Blowfish is a variable-length key, 64-bit block cipher. The algorithm consists of two parts: a key-expansion part and a data- encryption part. Key expansion converts a key of at most 448 bits into several subkey arrays totaling 4168 bytes.

Data encryption occurs via a 16-round Feistel network. Each round consists of a key-dependent permutation, and a key- and data-dependent substitution. All operations are XORs and additions on 32-bit words. The only additional operations are four indexed array data lookups per round.

Subkeys:

Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption.

1. The P-array consists of 18 32-bit subkeys:
P1, P2,..., P18.

2. There are four 32-bit S-boxes with 256 entries each:
S1,0, S1,1,..., S1,255;
S2,0, S2,1,..,, S2,255;
S3,0, S3,1,..., S3,255;
S4,0, S4,1,..,, S4,255.

The exact method used to calculate these subkeys will be described later.

Encryption:

Blowfish is a Feistel network consisting of 16 rounds (see Figure 1). The input is a 64-bit data element, x.

Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
Next i
Swap xL and xR (Undo the last swap.)
xR = xR XOR P17
xL = xL XOR P18
Recombine xL and xR

Function F (see Figure 2):
Divide xL into four eight-bit quarters: a, b, c, and d
F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232

Decryption is exactly the same as encryption, except that P1, P2,..., P18 are used in the reverse order.

Implementations of Blowfish that require the fastest speeds should unroll the loop and ensure that all subkeys are stored in cache.

Generating the Subkeys:

The subkeys are calculated using the Blowfish algorithm. The exact method is as follows:

1. Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of pi (less the initial 3). For example:

P1 = 0x243f6a88
P2 = 0x85a308d3
P3 = 0x13198a2e
P4 = 0x03707344

2. XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

3. Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2).

4. Replace P1 and P2 with the output of step (3).

5. Encrypt the output of step (3) using the Blowfish algorithm with the modified subkeys.

6. Replace P3 and P4 with the output of step (5).

7. Continue the process, replacing all entries of the P- array, and then all four S-boxes in order, with the output of the continuously-changing Blowfish algorithm.

In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys rather than execute this derivation process multiple times.

MINI-BLOWFISH

The following mini versions of Blowfish are defined solely for cryptanalysis. They are not suggested for actual implementation. Blowfish-32 has a 32-bit block size and subkey arrays of 16-bit entries (each S-box has 16 entries). Blowfish-16 has a 16-bit block size and subkey arrays of 8-bit entries (each S-box has 4 entries).

DESIGN DECISIONS

The underlying philosophy behind Blowfish is that simplicity of design yields an algorithm that is both easier to understand and easier to implement. Through the use of a streamlined Feistel network--a simple S-box substitution and a simple P-box substitution--I hope that the design will not contain any flaws.

A 64-bit block size yields a 32-bit word size, and maintains block-size compatibility with existing algorithms. Blowfish is easy to scale up to a 128-bit block, and down to smaller block sizes. Cryptanalysis of the mini-Blowfish variants may be significantly easier than cryptanalysis of the full version.

The fundamental operations were chosen with speed in mind. XOR, ADD, and MOV from a cache are efficient on both Intel and Motorola architectures. All subkeys fit in the cache of a 80486, 68040, Pentium, and PowerPC.

The Feistel network that makes up the body of Blowfish is designed to be as simple as possible, while still retaining the desirable cryptographic properties of the structure. Figure 3 is round i of a general Feistel network: Rn,i are reversible functions of text and key, and Ni is a non-reversible function of text and key. For speed and simplicity, I chose XOR as my reversible function. This let me collapse the four XORs into a single XOR, since:

R--1,i+1 = R1,i+1 XOR R2,i-1 XOR R3,i XOR R4,i

This is the P-array substitution in Blowfish. The XOR can also be considered to be part of the non-reversible function, Ni, occurring at the end of the function. (Although equivalent, I chose not to illustrate them in this way because it simplifies description of the subkey-generation process.) There are two XORs that remain after this reduction: R1 in the first round and R2 in the last round. I chose not to eliminate these in order to hide the input to the first non-reversible function.

I considered a more complicated reversible function, one with modular multiplications and rotations. However, these operations would greatly increase the algorithm's execution time. Since function F is the primary source of the algorithm's security, I decided to save time-consuming complications for that function.

Function F, the non-reversible function, gives Blowfish the best possible avalanche effect for a Feistel network: every text bit on the left half of the round affects every text bit on the right half. Additionally, since every subkey bit is affected by every key bit, the function also has a perfect avalanche effect between the key and the right half of the text after every round. Hence, the algorithm exhibits a perfect avalanche effect after three rounds and again every two rounds after that.

I considered adding a reversible mixing function, more complicated than XOR, before the first and after the last round. This would further confuse the entry values into the Feistel network and ensure a complete avalanche effect after the first two rounds. I eventually discarded the addition as a time- consuming complication with no clear cryptographic benefits.

The non-reversible function is designed for strength, speed, and simplicity. Ideally, I wanted a single S-box with 232 32-bit words, but that was impractical. My eventual choice of 256-entry S-boxes was a compromise between my three design goals. The small-number of bits to large-number of bits may have weaknesses with respect to linear cryptanalysis, but these weaknesses are hidden both by combining the output of four S-boxes and making them dependent on the key.

I used four different S-boxes instead of one S-box primarily to avoid symmetries when different bytes of the input are equal, or when the 32-bit input to function F is a bytewise permutation of another 32-bit input. I could have used one S-box and made each of the four different outputs a non-trivial permutation of the single output, but the four S-box design is faster, easier to program, and seems more secure.

The function that combines the four S-box outputs is as fast as possible. A simpler function would be to XOR the four values, but mixing addition mod 232 and XOR combines two different algebraic groups with no additional instructions. The alternation of addition and XOR ends with an addition operation because an XOR combines the final result with xR.

If the four indexes chose values out of the same S-box, a more complex combining function would be required to eliminate symmetries. I considered using a more complex combining function in Blowfish (using modular multiplications, rotations, etc.), but chose not to because the added complication seemed unnecessary.

The key-dependent S-boxes protect against differential and linear cryptanalysis. Since the structure of the S-boxes is completely hidden from the cryptanalyst, these attacks have a more difficult time exploiting that structure. While it would be possible to replace these variable S-boxes with four fixed S-boxes that were designed to be resistant to these attacks, key-dependent S-boxes are easier to implement and less susceptible to arguments of "hidden" properties. Additionally, these S-boxes can be created on demand, reducing the need for large data structures stored with the algorithm.

Each bit of xL is only used as the input to one S-box. In DES many bits are used as inputs to two S-boxes, which strengthens the algorithm considerably against differential attacks. I feel that this added complication is not as necessary with key- dependent S-boxes. Additionally, larger S-boxes would take up considerably more memory space.

Function F does not depend on the iteration. I considered adding this dependency, but did not feel that it had any cryptographic merit. The P-array substitution can be considered to be part of this function, and that is already iteration-dependent.

The number of rounds is set at 16 primarily out of desire to be conservative. However, this number affects the size of the P- array and therefore the subkey-generation process; 16 iterations permits key lengths up to 448 bits. I expect to be able to reduce this number, and greatly speed up the algorithm in the process, as I accumulate more cryptanalysis data.

In algorithm design, there are two basic ways to ensure that the key is long enough to ensure a particular security level. One is to carefully design the algorithm so that the entire entropy of the key is preserved, so there is no better way to cryptanalyze the algorithm other than brute force. The other is to design the algorithm with so many key bits that attacks that reduce the effective key length by several bits are irrelevant. Since Blowfish is designed for large microprocessors with large amounts of memory, I chose the latter.

The subkey generation process is designed to preserve the entire entropy of the key and to distribute that entropy uniformly throughout the subkeys. It is also designed to distribute the set of allowed subkeys randomly throughout the domain of possible subkeys. I chose the digits of pi as the initial subkey table for two reasons: because it is a random sequence not related to the algorithm, and because it could either be stored as part of the algorithm or derived when needed. There is nothing sacred about pi; any string of random bits--digits of e, RAND tables, output of a random number generator--will suffice. However, if the initial string is non-random in any way (for example, ASCII text with the high bit of every byte a 0), this non-randomness will propagate throughout the algorithm.

In the subkey generation process, the subkeys change slightly with every pair of subkeys generated. This is primarily to protect against any attacked of the subkey generation process that exploit the fixed and known subkeys. It also reduces storage requirements. The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of P15, P16, P17, and P18 does not affect every bit of the ciphertext, and that any S-box entry only has a .06 probability of affecting any single ciphertext block.)

The key bits are repeatedly XORed with the digits of pi in the initial P-array to prevent the following potential attack: Assume that the key bits are not repeated, but instead padded with zeros to extend it to the length of the P-array. An attacker might find two keys that differ only in the 64-bit value XORed with P1 and P2 that, using the initial known subkeys, produce the same encrypted value. If so, he can find two keys that produce all the same subkeys. This is a highly tempting attack for a malicious key generator.

To prevent this same type of attack, I fixed the initial plaintext value in the subkey-generation process. There is nothing special about the all-zeros string, but it is important that this value be fixed.

The subkey-generation algorithm does not assume that the key bits are random. Even highly correlated key bits, such as an alphanumeric ASCII string with the bit of every byte set to 0, will produce random subkeys. However, to produce subkeys with the same entropy, a longer alphanumeric key is required.

The time-consuming subkey-generation process adds considerable complexity for a brute-force attack. The subkeys are too long to be stored on a massive tape, so they would have to be generated by a brute-force cracking machine as required. A total of 522 iterations of the encryption algorithm are required to test a single key, effectively adding 29 steps to any brute-force attack.

POSSIBLE SIMPLIFICATIONS

I am exploring several possible simplifications, aimed at decreasing memory requirements and execution time. These are outlined below:

Fewer and smaller S-boxes. It may be possible to reduce the number of S-boxes from four to one. Additionally, it may be possible to overlap entries in a single S-box: entry 0 would consist of bytes 0 through 3, entry 1 would consist of bytes 1 through 4, etc. The former simplification would reduce the memory requirements for the four S-boxes from 4096 bytes to 1024 bytes, the latter would reduce the requirements for a single S-box from 1024 bytes to 259 bytes. Additional steps may be required to eliminate the symmetries that these simplifications would introduce. Additionally, four different 10- or 12-bit indexes into a single large S-box could be used instead of the current series of S-boxes.

Fewer iterations. It is probably safe to reduce the number of iterations from 16 to 8 without compromising security. The number of iterations required for security may be dependent on the length of the key. Note that with the current subkey generation procedure, an 8-iteration algorithm cannot accept a key longer than 192 bits.

On-the-fly subkey calculation. The current method of subkey calculation requires all subkeys to be calculated advance of any data encryption. In fact, it is impossible to calculate the last subkey of the last S-box without calculating every subkey that comes before. An alternate method of subkey calculation would be preferable: one where every subkey can be calculated independently of any other. High-end implementations could still precompute the subkeys for increased speed, but low-end applications could only compute the required subkeys when needed.

CONCLUSIONS

I conjecture that the most efficient way to break Blowfish is through exhaustive search of the keyspace. I encourage all cryptanalytic attacks, modifications, and improvements to the algorithm. Attacks on mini versions of Blowfish, those with a 32- or even a 16-bit block size, are also encouraged. Source code in C and test data can be provided to anyone wishing to implement the algorithm, in accordance with U.S. export laws.

The software magazine Dr. Dobb's Journal is sponsoring $1000 contest for the best cryptanalysis of Blowfish received before April 1995. Please contact me for details.

Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in the public domain, and can be freely used by anyone.

ACKNOWLEDGEMENTS

Much of the motivation for this algorithm, as well as the design criteria, was developed with Niels Fergusen. I would also like to thank Eli Biham, Agnes Chan, Peter Gutmann, Angel Johnston, Lars Kundsen, and Matt Robshaw for their helpful suggestions.

REFERENCES

1. E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.

2. T.W. Cusick and M.C. Wood, "The REDOC-II Cryptosystem," Advances in Cryptology--CRYPTO '90 Proceedings, Springer- Verlag, 1991, pp. 545-563.

3. J. Deamen, R. Govaerts, and J. Vandewalle, "Block Ciphers Based on Modular Arithmetic," Proceedings of the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, 15-16 Feb 1993, pp. 80-89.

4. J.-H. Evertse, "Linear Structures in Blockciphers," Advances in Cryptology--EUROCRPYT '87, Springer-Verlag, 1988, pp. 249- 266.

5. H. Feistel, "Cryptography and Computer Privacy," Scientific American, v. 228, n. 5, May 73, pp. 15-23.

6. GOST 28147-89, "Cryptographic Protection for Data Processing Systems," "Cryptographic Transformation Algorithm," Government Standard of the U.S.S.R., Inv. No. 3583, UDC 681.325.6:006.354. (in Russian)

7. X. Lai, J. Massey, and S. Murphy, "Markov Ciphers and Differential Cryptanalysis," Advances in Cryptology--EUROCRYPT '91 Proceedings, Springer-Verlag, 1991, pp. 17-38.

8. J.L. Massey and X. Lai, "Device for Converting a Digital Block and the Use Thereof," International Patent PCT/CH91/00117, 16 May 1991.

9. J.L. Massey and X. Lai, "Device for the Conversion of a Digital Block and Use of Same," U.S. Patent 5,214,703, 25 May 1993.

10. M. Matsui, "Linear Cryptanalysis Method for DES Cipher," Advances in Cryptology--CRYPTO '93 Proceedings, Springer- Verlag, 1994, in preparation.

11. R.C. Merkle, "Fast Software Encryption Functions," Advances in Cryptology--CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 476-501.

12. R.C. Merkle, "Method and Apparatus for Data Encryption," U.S. Patent 5,003,597, 26 Mar 1991.

13. S. Miyaguchi, "The FEAL-8 Cryptosystem and Call for Attack," Advances in Cryptology--CRYPTO '89 Proceedings, Springer- Verlag, 1990, pp. 624-627.

14. S. Miyaguchi, "Expansion of the FEAL Cipher," NTT Review, v. 2, n. 6, Nov 1990.

15. S. Miyaguchi, "The FEAL Cipher Family," Advances in Cryptology--CRYPTO '90 Proceedings, Springer-Verlag, 1991, pp. 627-638.

16. National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS Publication 46, Jan 1977.

17. National Institute of Standards and Technology, "Clipper Chip Technology," 30 Apr 1993.

18. RSA Laboratories, Answers to Frequently Asked Questions About Today's Cryptography, Revision 2.0, RSA Data Security Inc., 5 Oct 1993.

19. B. Schneier, "Data Guardians," MacWorld, Feb 1993, 145-151.

20. B. Schneier, Applied Cryptography, John Wiley & Sons, New York, 1994.

21. J.L Smith, The Design of Lucifer, A Cryptographic Device for Data Communication, RC 3326, White Plains: IBM Research.

22. M.J. Weiner, "Efficient DES Key Search," Advances in Cryptology--CRYPTO '93 Proceedings, Springer-Verlag, in preparation.

23. M.C. Wood, "Method of Cryptographically Transforming Electronic Digital Data from One Form to Another," U.S. Patent 5,003,596, 26 Mar 1991.

The DES Algorithm Illustrated

2010-03-22T21:18:00.000-07:00

The DES Algorithm Illustrated
by J. Orlin Grabbe

The DES (Data Encryption Standard) algorithm is the most widely used encryption algorithm in the world. For many years, and among many people, "secret code making" and DES have been synonymous. And despite the recent coup by the Electronic Frontier Foundation in creating a $220,000 machine to crack DES-encrypted messages, DES will live on in government and banking for years to come through a life- extending version called "triple-DES."

How does DES work? This article explains the various steps involved in DES-encryption, illustrating each step by means of a simple example. Since the creation of DES, many other algorithms (recipes for changing data) have emerged which are based on design principles similar to DES. Once you understand the basic transformations that take place in DES, you will find it easy to follow the steps involved in these more recent algorithms.

But first a bit of history of how DES came about is appropriate, as well as a look toward the future.

The National Bureau of Standards Coaxes the Genie from the Bottle

On May 15, 1973, during the reign of Richard Nixon, the National Bureau of Standards (NBS) published a notice in the Federal Register soliciting proposals for cryptographic algorithms to protect data during transmission and storage. The notice explained why encryption was an important issue.

Over the last decade, there has been an accelerating increase in the accumulations and communication of digital data by government, industry and by other organizations in the private sector. The contents of these communicated and stored data often have very significant value and/or sensitivity. It is now common to find data transmissions which constitute funds transfers of several million dollars, purchase or sale of securities, warrants for arrests or arrest and conviction records being communicated between law enforcement agencies, airline reservations and ticketing representing investment and value both to the airline and passengers, and health and patient care records transmitted among physicians and treatment centers.

The increasing volume, value and confidentiality of these records regularly transmitted and stored by commercial and government agencies has led to heightened recognition and concern over their exposures to unauthorized access and use. This misuse can be in the form of theft or defalcations of data records representing money, malicious modification of business inventories or the interception and misuse of confidential information about people. The need for protection is then apparent and urgent.

It is recognized that encryption (otherwise known as scrambling, enciphering or privacy transformation) represents the only means of protecting such data during transmission and a useful means of protecting the content of data stored on various media, providing encryption of adequate strength can be devised and validated and is inherently integrable into system architecture. The National Bureau of Standards solicits proposed techniques and algorithms for computer data encryption. The Bureau also solicits recommended techniques for implementing the cryptographic function: for generating, evaluating, and protecting cryptographic keys; for maintaining files encoded under expiring keys; for making partial updates to encrypted files; and mixed clear and encrypted data to permit labelling, polling, routing, etc. The Bureau in its role for establishing standards and aiding government and industry in assessing technology, will arrange for the evaluation of protection methods in order to prepare guidelines.

NBS waited for the responses to come in. It received none until August 6, 1974, three days before Nixon's resignation, when IBM submitted a candidate that it had developed internally under the name LUCIFER. After evaluating the algorithm with the help of the National Security Agency (NSA), the NBS adopted a modification of the LUCIFER algorithm as the new Data Encryption Standard (DES) on July 15, 1977.

DES was quickly adopted for non-digital media, such as voice-grade public telephone lines. Within a couple of years, for example, International Flavors and Fragrances was using DES to protect its valuable formulas transmitted over the phone ("With Data Encryption, Scents Are Safe at IFF," Computerworld 14, No. 21, 95 (1980).)

Meanwhile, the banking industry, which is the largest user of encryption outside government, adopted DES as a wholesale banking standard. Standards for the wholesale banking industry are set by the American National Standards Institute (ANSI). ANSI X3.92, adopted in 1980, specified the use of the DES algorithm.

Some Preliminary Examples of DES

DES works on bits, or binary numbers--the 0s and 1s common to digital computers. Each group of four bits makes up a hexadecimal, or base 16, number. Binary "0001" is equal to the hexadecimal number "1", binary "1000" is equal to the hexadecimal number "8", "1001" is equal to the hexadecimal number "9", "1010" is equal to the hexadecimal number "A", and "1111" is equal to the hexadecimal number "F".

DES works by encrypting groups of 64 message bits, which is the same as 16 hexadecimal numbers. To do the encryption, DES uses "keys" where are also apparently 16 hexadecimal numbers long, or apparently 64 bits long. However, every 8th key bit is ignored in the DES algorithm, so that the effective key size is 56 bits. But, in any case, 64 bits (16 hexadecimal digits) is the round number upon which DES is organized.

For example, if we take the plaintext message "8787878787878787", and encrypt it with the DES key "0E329232EA6D0D73", we end up with the ciphertext "0000000000000000". If the ciphertext is decrypted with the same secret DES key "0E329232EA6D0D73", the result is the original plaintext "8787878787878787".

This example is neat and orderly because our plaintext was exactly 64 bits long. The same would be true if the plaintext happened to be a multiple of 64 bits. But most messages will not fall into this category. They will not be an exact multiple of 64 bits (that is, an exact multiple of 16 hexadecimal numbers).

For example, take the message "Your lips are smoother than vaseline". This plaintext message is 38 bytes (76 hexadecimal digits) long. So this message must be padded with some extra bytes at the tail end for the encryption. Once the encrypted message has been decrypted, these extra bytes are thrown away. There are, of course, different padding schemes--different ways to add extra bytes. Here we will just add 0s at the end, so that the total message is a multiple of 8 bytes (or 16 hexadecimal digits, or 64 bits).

The plaintext message "Your lips are smoother than vaseline" is, in hexadecimal,

"596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A".

(Note here that the first 72 hexadecimal digits represent the English message, while "0D" is hexadecimal for Carriage Return, and "0A" is hexadecimal for Line Feed, showing that the message file has terminated.) We then pad this message with some 0s on the end, to get a total of 80 hexadecimal digits:

"596F7572206C6970 732061726520736D 6F6F746865722074 68616E2076617365 6C696E650D0A0000".

If we then encrypt this plaintext message 64 bits (16 hexadecimal digits) at a time, using the same DES key "0E329232EA6D0D73" as before, we get the ciphertext:

"C0999FDDE378D7ED 727DA00BCA5A84EE 47F269A4D6438190 9DD52F78F5358499 828AC9B453E0E653".

This is the secret code that can be transmitted or stored. Decrypting the ciphertext restores the original message "Your lips are smoother than vaseline". (Think how much better off Bill Clinton would be today, if Monica Lewinsky had used encryption on her Pentagon computer!)

How DES Works in Detail

DES is a block cipher--meaning it operates on plaintext blocks of a given size (64-bits) and returns ciphertext blocks of the same size. Thus DES results in a permutation among the 2^64 (read this as: "2 to the 64th power") possible arrangements of 64 bits, each of which may be either 0 or 1. Each block of 64 bits is divided into two blocks of 32 bits each, a left half block L and a right half R. (This division is only used in certain operations.)

Example: Let M be the plain text message M = 0123456789ABCDEF, where M is in hexadecimal (base 16) format. Rewriting M in binary format, we get the 64-bit block of text:

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
L = 0000 0001 0010 0011 0100 0101 0110 0111
R = 1000 1001 1010 1011 1100 1101 1110 1111

The first bit of M is "0". The last bit is "1". We read from left to right.

DES operates on the 64-bit blocks using key sizes of 56- bits. The keys are actually stored as being 64 bits long, but every 8th bit in the key is not used (i.e. bits numbered 8, 16, 24, 32, 40, 48, 56, and 64). However, we will nevertheless number the bits from 1 to 64, going left to right, in the following calculations. But, as you will see, the eight bits just mentioned get eliminated when we create subkeys.

Example: Let K be the hexadecimal key K = 133457799BBCDFF1. This gives us as the binary key (setting 1 = 0001, 3 = 0011, etc., and grouping together every eight bits, of which the last one in each group will be unused):

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

The DES algorithm uses the following steps:

Step 1: Create 16 subkeys, each of which is 48-bits long.

The 64-bit key is permuted according to the following table, PC-1. Since the first entry in the table is "57", this means that the 57th bit of the original key K becomes the first bit of the permuted key K+. The 49th bit of the original key becomes the second bit of the permuted key. The 4th bit of the original key is the last bit of the permuted key. Note only 56 bits of the original key appear in the permuted key.

PC-1

57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4

Example: From the original 64-bit key

K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

we get the 56-bit permutation

K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111

Next, split this key into left and right halves, C0 and D0, where each half has 28 bits.

Example: From the permuted key K+, we get

C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111

With C0 and D0 defined, we now create sixteen blocks Cn and Dn, 1<=n<=16. Each pair of blocks Cn and Dn is formed from the previous pair Cn-1 and Dn-1, respectively, for n = 1, 2, ..., 16, using the following schedule of "left shifts" of the previous block. To do a left shift, move each bit one place to the left, except for the first bit, which is cycled to the end of the block. Iteration Number of Number Left Shifts 1 1 2 1 3 2 4 2 5 2 6 2 7 2 8 2 9 1 10 2 11 2 12 2 13 2 14 2 15 2 16 1 This means, for example, C3 and D3 are obtained from C2 and D2, respectively, by two left shifts, and C16 and D16 are obtained from C15 and D15, respectively, by one left shift. In all cases, by a single left shift is meant a rotation of the bits one place to the left, so that after one left shift the bits in the 28 positions are the bits that were previously in positions 2, 3,..., 28, 1. Example: From original pair pair C0 and D0 we obtain: C0 = 1111000011001100101010101111 D0 = 0101010101100110011110001111 C1 = 1110000110011001010101011111 D1 = 1010101011001100111100011110 C2 = 1100001100110010101010111111 D2 = 0101010110011001111000111101 C3 = 0000110011001010101011111111 D3 = 0101011001100111100011110101 C4 = 0011001100101010101111111100 D4 = 0101100110011110001111010101 C5 = 1100110010101010111111110000 D5 = 0110011001111000111101010101 C6 = 0011001010101011111111000011 D6 = 1001100111100011110101010101 C7 = 1100101010101111111100001100 D7 = 0110011110001111010101010110 C8 = 0010101010111111110000110011 D8 = 1001111000111101010101011001 C9 = 0101010101111111100001100110 D9 = 0011110001111010101010110011 C10 = 0101010111111110000110011001 D10 = 1111000111101010101011001100 C11 = 0101011111111000011001100101 D11 = 1100011110101010101100110011 C12 = 0101111111100001100110010101 D12 = 0001111010101010110011001111 C13 = 0111111110000110011001010101 D13 = 0111101010101011001100111100 C14 = 1111111000011001100101010101 D14 = 1110101010101100110011110001 C15 = 1111100001100110010101010111 D15 = 1010101010110011001111000111 C16 = 1111000011001100101010101111 D16 = 0101010101100110011110001111 We now form the keys Kn, for 1<=n<=16, by applying the following permutation table to each of the concatenated pairs CnDn. Each pair has 56 bits, but PC-2 only uses 48 of these. PC-2 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Therefore, the first bit of Kn is the 14th bit of CnDn, the second bit the 17th, and so on, ending with the 48th bit of Kn being the 32th bit of CnDn. Example: For the first key we have C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110 which, after we apply the permutation PC-2, becomes K1 = 000110 110000 001011 101111 111111 000111 000001 110010 For the other keys we have K2 = 011110 011010 111011 011001 110110 111100 100111 100101 K3 = 010101 011111 110010 001010 010000 101100 111110 011001 K4 = 011100 101010 110111 010110 110110 110011 010100 011101 K5 = 011111 001110 110000 000111 111010 110101 001110 101000 K6 = 011000 111010 010100 111110 010100 000111 101100 101111 K7 = 111011 001000 010010 110111 111101 100001 100010 111100 K8 = 111101 111000 101000 111010 110000 010011 101111 111011 K9 = 111000 001101 101111 101011 111011 011110 011110 000001 K10 = 101100 011111 001101 000111 101110 100100 011001 001111 K11 = 001000 010101 111111 010011 110111 101101 001110 000110 K12 = 011101 010111 000111 110101 100101 000110 011111 101001 K13 = 100101 111100 010111 010001 111110 101011 101001 000001 K14 = 010111 110100 001110 110111 111100 101110 011100 111010 K15 = 101111 111001 000110 001101 001111 010011 111100 001010 K16 = 110010 110011 110110 001011 000011 100001 011111 110101 So much for the subkeys. Now we look at the message itself. Step 2: Encode each 64-bit block of data.

There is an initial permutation IP of the 64 bits of the message data M. This rearranges the bits according to the following table, where the entries in the table show the new arrangement of the bits from their initial order. The 58th bit of M becomes the first bit of IP. The 50th bit of M becomes the second bit of IP. The 7th bit of M is the last bit of IP.

IP

58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

Example: Applying the initial permutation to the block of text M, given previously, we get

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

Here the 58th bit of M is "1", which becomes the first bit of IP. The 50th bit of M is "1", which becomes the second bit of IP. The 7th bit of M is "0", which becomes the last bit of IP.

Next divide the permuted block IP into a left half L0 of 32 bits, and a right half R0 of 32 bits.

Example: From IP, we get L0 and R0

L0 = 1100 1100 0000 0000 1100 1100 1111 1111
R0 = 1111 0000 1010 1010 1111 0000 1010 1010

We now proceed through 16 iterations, for 1<=n<=16, using a function f which operates on two blocks--a data block of 32 bits and a key Kn of 48 bits--to produce a block of 32 bits. Let + denote XOR addition, (bit-by-bit addition modulo 2). Then for n going from 1 to 16 we calculate Ln = Rn-1 Rn = Ln-1 + f(Rn-1,Kn) This results in a final block, for n = 16, of L16R16. That is, in each iteration, we take the right 32 bits of the previous result and make them the left 32 bits of the current step. For the right 32 bits in the current step, we XOR the left 32 bits of the previous step with the calculation f . Example: For n = 1, we have K1 = 000110 110000 001011 101111 111111 000111 000001 110010 L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010 R1 = L0 + f(R0,K1) It remains to explain how the function f works. To calculate f, we first expand each block Rn-1 from 32 bits to 48 bits. This is done by using a selection table that repeats some of the bits in Rn-1 . We'll call the use of this selection table the function E. Thus E(Rn-1) has a 32 bit input block, and a 48 bit output block. Let E be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are obtained by selecting the bits in its inputs in order according to the following table: E BIT-SELECTION TABLE 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 Thus the first three bits of E(Rn-1) are the bits in positions 32, 1 and 2 of Rn-1 while the last 2 bits of E(Rn-1) are the bits in positions 32 and 1. Example: We calculate E(R0) from R0 as follows: R0 = 1111 0000 1010 1010 1111 0000 1010 1010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 (Note that each block of 4 original bits has been expanded to a block of 6 output bits.) Next in the f calculation, we XOR the output E(Rn-1) with the key Kn: Kn + E(Rn-1). Example: For K1 , E(R0), we have K1 = 000110 110000 001011 101111 111111 000111 000001 110010 E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101 K1+E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111. We have not yet finished calculating the function f . To this point we have expanded Rn-1 from 32 bits to 48 bits, using the selection table, and XORed the result with the key Kn . We now have 48 bits, or eight groups of six bits. We now do something strange with each group of six bits: we use them as addresses in tables called "S boxes". Each group of six bits will give us an address in a different S box. Located at that address will be a 4 bit number. This 4 bit number will replace the original 6 bits. The net result is that the eight groups of 6 bits are transformed into eight groups of 4 bits (the 4-bit outputs from the S boxes) for 32 bits total. Write the previous result, which is 48 bits, in the form: Kn + E(Rn-1) =B1B2B3B4B5B6B7B8, where each Bi is a group of six bits. We now calculate S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) where Si(Bi) referres to the output of the i-th S box. To repeat, each of the functions S1, S2,..., S8, takes a 6-bit block as input and yields a 4-bit block as output. The table to determine S1 is shown and explained below: S1 Column Number Row No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 If S1 is the function defined in this table and B is a block of 6 bits, then S1(B) is determined as follows: The first and last bits of B represent in base 2 a number in the decimal range 0 to 3 (or binary 00 to 11). Let that number be i. The middle 4 bits of B represent in base 2 a number in the decimal range 0 to 15 (binary 0000 to 1111). Let that number be j. Look up in the table the number in the i-th row and j-th column. It is a number in the range 0 to 15 and is uniquely represented by a 4 bit block. That block is the output S1(B) of S1 for the input B. For example, for input block B = 011011 the first bit is "0" and the last bit "1" giving 01 as the row. This is row 1. The middle four bits are "1101". This is the binary equivalent of decimal 13, so the column is column number 13. In row 1, column 13 appears 5. This determines the output; 5 is binary 0101, so that the output is 0101. Hence S1(011011) = 0101. The tables defining the functions S1,...,S8 are the following: S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 S2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 S3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 S4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 S5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 S6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 S7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 S8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 Example: For the first round, we obtain as the output of the eight S boxes: K1 + E(R0) = 011000 010001 011110 111010 100001 100110 010100 100111. S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111 The final stage in the calculation of f is to do a permutation P of the S-box output to obtain the final value of f: f = P(S1(B1)S2(B2)...S8(B8)) The permutation P is defined in the following table. P yields a 32-bit output from a 32-bit input by permuting the bits of the input block. P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Example: From the output of the eight S boxes: S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) = 0101 1100 1000 0010 1011 0101 1001 0111 we get f = 0010 0011 0100 1010 1010 1001 1011 1011 R1 = L0 + f(R0 , K1 ) = 1100 1100 0000 0000 1100 1100 1111 1111 + 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100 In the next round, we will have L2 = R1, which is the block we just calculated, and then we must calculate R2 =L1 + f(R1, K2), and so on for 16 rounds. At the end of the sixteenth round we have the blocks L16 and R16. We then reverse the order of the two blocks into the 64-bit block R16L16 and apply a final permutation IP-1 as defined by the following table: IP-1 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 That is, the output of the algorithm has bit 40 of the preoutput block as its first bit, bit 8 as its second bit, and so on, until bit 25 of the preoutput block is the last bit of the output. Example: If we process all 16 blocks using the method defined previously, we get, on the 16th round, L16 = 0100 0011 0100 0010 0011 0010 0011 0100 R16 = 0000 1010 0100 1100 1101 1001 1001 0101 We reverse the order of these two blocks and apply the final permutation to R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100 IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101 which in hexadecimal format is 85E813540F0AB405. This is the encrypted form of M = 0123456789ABCDEF: namely, C = 85E813540F0AB405. Decryption is simply the inverse of encryption, follwing the same steps as above, but reversing the order in which the subkeys are applied. DES Modes of Operation

The DES algorithm turns a 64-bit message block M into a 64-bit cipher block C. If each 64-bit block is encrypted individually, then the mode of encryption is called Electronic Code Book (ECB) mode. There are two other modes of DES encryption, namely Chain Block Coding (CBC) and Cipher Feedback (CFB), which make each cipher block dependent on all the previous messages blocks through an initial XOR operation.

Cracking DES

Before DES was adopted as a national standard, during the period NBS was soliciting comments on the proposed algorithm, the creators of public key cryptography, Martin Hellman and Whitfield Diffie, registered some objections to the use of DES as an encryption algorithm. Hellman wrote: "Whit Diffie and I have become concerned that the proposed data encryption standard, while probably secure against commercial assault, may be extremely vulnerable to attack by an intelligence organization" (letter to NBS, October 22, 1975).

Diffie and Hellman then outlined a "brute force" attack on DES. (By "brute force" is meant that you try as many of the 2^56 possible keys as you have to before decrypting the ciphertext into a sensible plaintext message.) They proposed a special purpose "parallel computer using one million chips to try one million keys each" per second, and estimated the cost of such a machine at $20 million.

Fast forward to 1998. Under the direction of John Gilmore of the EFF, a team spent $220,000 and built a machine that can go through the entire 56-bit DES key space in an average of 4.5 days. On July 17, 1998, they announced they had cracked a 56-bit key in 56 hours. The computer, called Deep Crack, uses 27 boards each containing 64 chips, and is capable of testing 90 billion keys a second.

Despite this, as recently as June 8, 1998, Robert Litt, principal associate deputy attorney general at the Department of Justice, denied it was possible for the FBI to crack DES: "Let me put the technical problem in context: It took 14,000 Pentium computers working for four months to decrypt a single message . . . . We are not just talking FBI and NSA [needing massive computing power], we are talking about every police department."

Responded cryptograpy expert Bruce Schneier: " . . . the FBI is either incompetent or lying, or both." Schneier went on to say: "The only solution here is to pick an algorithm with a longer key; there isn't enough silicon in the galaxy or enough time before the sun burns out to brute- force triple-DES" (Crypto-Gram, Counterpane Systems, August 15, 1998).

Triple-DES

Triple-DES is just DES with two 56-bit keys applied. Given a plaintext message, the first key is used to DES- encrypt the message. The second key is used to DES-decrypt the encrypted message. (Since the second key is not the right key, this decryption just scrambles the data further.) The twice-scrambled message is then encrypted again with the first key to yield the final ciphertext. This three-step procedure is called triple-DES.

Triple-DES is just DES done three times with two keys used in a particular order. (Triple-DES can also be done with three separate keys instead of only two. In either case the resultant key space is about 2^112.)

General References

"Cryptographic Algorithms for Protection of Computer Data During Transmission and Dormant Storage," Federal Register 38, No. 93 (May 15, 1973).

Data Encryption Standard, Federal Information Processing Standard (FIPS) Publication 46, National Bureau of Standards, U.S. Department of Commerce, Washington D.C. (January 1977).

Carl H. Meyer and Stephen M. Matyas, Cryptography: A New Dimension in Computer Data Security, John Wiley & Sons, New York, 1982.

Dorthy Elizabeth Robling Denning, Cryptography and Data Security, Addison-Wesley Publishing Company, Reading, Massachusetts, 1982.

D.W. Davies and W.L. Price, Security for Computer Networks: An Introduction to Data Security in Teleprocessing and Electronics Funds Transfer, Second Edition, John Wiley & Sons, New York, 1984, 1989.

Miles E. Smid and Dennis K. Branstad, "The Data Encryption Standard: Past and Future," in Gustavus J. Simmons, ed., Contemporary Cryptography: The Science of Information Integrity, IEEE Press, 1992.

Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Boca Raton, 1995.

Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, New York, 1996.

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.

-30-

This article appeared in Laissez Faire City Times, Vol 2, No. 28.

Homepage: http://orlingrabbe.com/
Laissez Faire City Times: http://zolatimes.com/

Prime Number Hide-and-Seek: How the RSA Cipher Works

2010-03-22T20:55:00.000-07:00

Prime Number Hide-and-Seek: How the RSA Cipher Works

Preface: What is This?

The RSA cipher is a fascinating example of how some of the most abstract mathematical subjects find applications in the real world. Few are the mathematicians who study creatures like the prime numbers with the hope or even desire for their discoveries to be useful outside of their own domain. But every now and then that is exactly what happens.

This text explains the mathematics behind RSA -- how and why it works. The intended audience is just about anyone who is interested in the topic and who can remember a few basic facts from algebra: what a variable is, the difference between a prime number and a composite number, and the like.

The most important mathematical facts necessary for understanding RSA's foundations are reviewed near the beginning. Even if you are familiar with everything covered in these sections, I would recommend that you at least skim through them.

In one or two places, I have specifically targeted an explanation to what I consider to be the average computer programmer, leveraging analogous concepts in programming and general mathematics.

Before getting started, I should make some observations on the mathematical notation used here.

For the most part, where notations for the same idea differ between standard mathematics and the common practices among computer programmers, I have stuck with the mathematicians. This is, after all, a mathematical subject. However, I have deviated in a few places where there was too much opportunity for confusion. I have used * to denote multiplication, and have completely avoided "implied" multiplication (i.e., using PQ as shorthand for P * Q). Since not all web browsers can display superscripts, I have used ^ to denote exponentiation. (This necessitates more parenthesizing than would normally be used.) The mathematician's three-bar congruency symbol is not available, so I have made do with = instead. Variables are always named with a single capital letter.

Finally, please note that throughout the text I use the word number to refer specifically to a positive integer -- what are sometimes referred to as the natural numbers, or counting numbers.

Introduction: The Idea of a Trapdoor Function

What a mathematician refers to as a function is very similar to a function in computer programming. It is, in essence, an abbreviation. For example:

F(X) = 7 * X + 43.

If X happens to be 3, then F(X) will be 64. So, "F(3)" is shorthand for "7 * 3 + 43".

The same function in a C program might look like:

int F(int x)
{
return 7 * x + 43;
}

Of course, in a computer program, functions are used to encapsulate all kinds of algorithms, and frequently make use of external variables and the like. In mathematics, however, a function is used solely for the number it returns. And, given a certain number as input, they will always return the same output. (Thus, rand() would not qualify as a mathematical function, unless it were written so that the seed value was passed in as an input parameter.)

Mathematicians often consider how to construct a function's inverse -- taking a function and making a new one that "goes in the other direction", so to speak:

G(X) = (X - 43) / 7.

G(64) is equal to 3, and in general, G(F(X)) is equal to X. Therefore, G is F's inverse. Not all functions are invertible, of course. Clearly, the function:

F(X) = X * 0

cannot be inverted. (Because how could G(F(X)) return X when F(X) is always zero?)

Usually, when you have a mathematical function for which an inverse does exist, constructing it is not too difficult. In fact, it is often transparent. Typically, you can just run through the steps backwards, subtracting where the original function adds, and so on. But can it be done for every invertible function?

To put the question in terms of programming, imagine that there are two functions:

int foo(int x);
int bar(int x);

foo() and bar() work like mathematical functions -- they do nothing but compute a return value, and given the same number for input, they will always produce the same output. (And pretend for the moment that this is on a machine where integers can be arbitrarily large.) Suppose you are told that bar() is the inverse of foo(). The statement:

x == bar(foo(x))

is always true, as long as x meets foo()'s requirements for a valid argument.

Now, imagine that you have the source code for foo(), but not for bar(). Can you write your own replacement for bar(), just by examining foo()?

It seems that you ought to be able to. There are no secrets as to what foo() does, after all. You can run foo() with different inputs as many times as you like. You already know that bar() exists, somewhere, so you know that it is possible to write. Is it guaranteed that you can reconstruct it?

Theoretically speaking, the answer is yes. Given such an function, it is always possible to construct its inverse. However, if we also throw in the tiny constraint that you have to finish before the heat-death of the universe, the answer subtly changes.

There are some special functions that, though what they do is simple enough, and how they do what they do is utterly transparent, figuring out how to undo what they do is a diabolical task. Such a creature is a trapdoor function. Anyone can fall through a trapdoor, but only those who know where the hidden lever is can climb back out again.

In 1975, Whitfield Diffie, Martin E. Hellman, and Ralph Merkle realized that a trapdoor function could be the basis for an entirely new kind of cipher -- one in which the decoding method could remain secret even when the encoding method was public knowledge. Diffie and Hellman published a paper in 1976 that described this idea, and offered some examples of weak trapdoor functions. And in 1977, Ronald L. Rivest, Adi Shamir, and Leonard Adleman outlined, in an MIT technical memo, an excellent candidate that became the basis for the RSA cipher.

What follows is a description of that function.

Background, Part I: How to Calculate with Exponents

Here's a quick refresher on how to combine exponents. Recall that:

N^2 = N * N,
N^3 = N * N * N,
N^4 = N * N * N * N,

and so on. For example:

2^7 = 2 * 2 * 2 * 2 * 2 * 2 * 2 = 128.

If we fiddle with exponents for a bit, we will quickly realize that:

N^E * N = N^(E + 1).

So, for example:

2^7 * 2 = 128 * 2 = 256 = 2^8.

Building upon this, we can also see that:

N^E * N * N = N^(E + 2).

But N * N can also be written as N^2:

N^E * N^2 = N^(E + 2).

We can extrapolate from this, and derive a more general rule -- namely:

N^A * N^B = N^(A + B).

And, if we repeated this process on the next level up, we would find that:

(N^A)^B = N^(A * B).

These two simple facts are very useful when handling exponent-laden formulas.

Background, Part II: Modulus Arithmetic

Most computer programmers are familiar with modulus as a "remainder" operator, usually denoted by "%", which gives the remainder of an integer division instead of the quotient. For example:

27 % 12 = 3.

Though the idea is the same, the mechanics here are slightly different from what mathematicians refer to as modulus arithmetic. In essence, modulus arithmetic consists of taking the infinitely long number-line and coiling it around a finite circle. All the numbers that land on the same point along the circle's edge are considered interchangeable, or congruent. Thus, the analogue to the above example in modulus arithmetic would be expressed as:

27 = 3 (mod 12),

or, in words:

27 is congruent to 3, modulo 12.

(Though note that mathematicians actually use a three-barred version of the equal sign to indicate congruency.) In this case, 12 is the modulus that we are working under, and the equation simply tells us that, under a modulus of 12, 27 and 3 are considered to be the same number. Likewise:

11 + 16 = 3 (mod 12)

reads as:

11 plus 16 is congruent to 3, modulo 12.

Modulus arithmetic is sometimes called clockface arithmetic -- if it's currently 11 o'clock, then 16 hours later it will be 3 o'clock. (Of course, the analogy is less perfect when the modulus is something other than 12.)

An important feature of modulus arithmetic is that you can replace the terms of an addition operation with congruent values, and still get the right answer:

16 = 4 (mod 12), therefore
11 + 16 = 11 + 4 = 3 (mod 12).

Another example:

9835 = 7 (mod 12), and
1176 = 0 (mod 12), therefore
9835 + 1176 = 7 + 0 = 7 (mod 12).

Even better, this trick also works with multiplication:

9835 * 1176 = 7 * 0 = 0 (mod 12)

(and, if we check, we will see that, yes, 9835 * 1176 is 11565960, and 11565960 = 0 (mod 12)).

If our modulus was 10, then modulus arithmetic would be equivalent to ignoring all but the last digit in our numbers:

37 = 7 (mod 10),
287 + 482 = 9 (mod 10), and
895 * 9836 = 0 (mod 10).

And, in a sense, a C program does all of its calculations in modulus arithmetic. Since integer calculations in C are permitted to overflow, the high bits silently falling off into the bit bucket, a C program using 32-bit integers is really doing all of its arithmetic modulo 2^32.

As you might imagine, some calculations that are time-consuming and produce huge numbers become trivial in modulus arithmetic. The ability to reduce values to their remainders before doing the actual calculation keeps the calculations from getting out of hand.

Background, Part III: The Fundamental Theorem of Algebra

The Fundamental Theorem of Algebra states that for every number, there is exactly one way to factor that number into primes -- and vice versa: every selection of primes multiplies into a different number. For example:

1176 = 2 * 2 * 2 * 3 * 7 * 7, or
1176 = 2^3 * 3^1 * 7^2.

It is guaranteed that there is no other way to break 1176 into prime factors. And, certainly, any time you take three 2s, two 7s, and a three, you're always going to get 1176 when you multiply them together. The Fundamental Theorem of Algebra assures us that both these things are true for every number.

(By the way, this is one of the reasons that 1 is not considered to be a prime number: if it were, then each number would have an infinite number of prime factorizations, all differing by how many 1s were included. Instead, 1 is considered to have no prime factors at all, and we say that a number is prime if it has exactly one prime factor -- namely itself.)

Put another way, the Fundamental Theorem of Algebra states that the set of all numbers and the set of all selections of prime numbers are "isomorphic" -- there is a perfect one-to-one mapping between the two. A number is therefore defined by its prime factorization.

Background, Part IV: Relatively Prime Numbers

The greatest common divisor (abbreviated GCD) of two numbers is the largest number that evenly divides into both of them. For example:

GCD(15, 10) = 5,
GCD(18, 10) = 2,
GCD(21, 10) = 1, and
GCD(170, 102) = 34.

Or, another way to look at it is to say that the GCD is the intersection of the two numbers' set of prime factors:

GCD((2^3 * 3^1 * 7^2), (2^2 * 5^1 * 7^3)) = 2^2 * 7^2, so
GCD(1176, 6860) = 196.

When two numbers have no common factors, their GCD will be 1, and the two numbers are said to be relatively prime (or coprime). For example, we can see in our list up above that 21 and 10 are relatively prime.

Since a prime number has no factors besides itself, clearly a prime number is relatively prime to every other number (except for multiples of itself). And the same can be said of the number 1.

Okay. Enough background material. Let's get to the good stuff.

Euler's Totient Function

Euler's Totient Function is denoted by the Greek letter phi, and is defined as follows:

phi(N) = how many numbers between 1 and N - 1 which are relatively prime to N.

Thus:

phi(4) = 2 (1 and 3 are relatively prime to 4),
phi(5) = 4 (1, 2, 3, and 4 are relatively prime to 5),
phi(6) = 2 (1 and 5 are relatively prime to 6),
phi(7) = 6 (1, 2, 3, 4, 5, and 6 are relatively prime to 7),
phi(8) = 4 (1, 3, 5, and 7 are relatively prime to 8), and
phi(9) = 6 (1, 2, 4, 5, 7, and 8 are relatively prime to 9).

Here is the same definition expressed as C code:

phi = 1;
for (i = 2 ; i < N ; ++i)
if (gcd(i, N) == 1)
++phi;

(By the way, notice that phi(1) is specially defined to be 1.)

It should be easy to see that phi(N) will be N - 1 whenever N is prime. Somewhat less obvious is the useful fact that phi(N) is also easy to calculate when N has exactly two different prime factors:

phi(P * Q) = (P - 1) * (Q - 1), if P and Q are prime.

(The proof of this fact is left as an exercise for the reader. It's actually not too hard.) Thus, for example:

phi(15) = 2 * 4 = 8 (1, 2, 4, 7, 8, 11, 13, and 14).

The two prime factors cannot be the same number for this to work, and in fact you can see above that phi(9) does not equal 4.

Euler's Totient Theorem

This theorem is one of the important keys to the RSA algorithm:

If GCD(T, R) = 1 and T < R, then T^(phi(R)) = 1 (mod R).

Or, in words:

If T and R are relatively prime, with T being the smaller number, then when we multiply T with itself phi(R) times and divide the result by R, the remainder will always be 1.

We can test this theorem on some smaller numbers for which we have already calculated the totient. Using 5 for T and 6 for R, we get:

phi(6) = (2 - 1) * (3 - 1) = 1 * 2 = 2, so
5^(phi(6)) = 5^2 = 25, and
25 = 24 + 1 = 6 * 4 + 1, therefore
25 = 1 (mod 6).

Using 2 for T and 15 for R, we have:

phi(15) = (3 - 1) * (5 - 1) = 2 * 4 = 8, so
2^(phi(15)) = 2^8 = 256, and
256 = 255 + 1 = 17 * 15 + 1, therefore
256 = 1 (mod 15).

Variations on a Theme

Here again is the equation of Euler's Totient Theorem:

T^(phi(R)) = 1 (mod R)

(remembering that T < R, and T and R are relatively prime). Thanks to the way that modulus arithmetic works on multiplication, we can easily see that:

T^(phi(R)) * T^(phi(R)) = 1 * 1 (mod R),

which can be rewritten, using the laws of exponents, as:

T^(phi(R) + phi(R)) = 1 * 1 (mod R),

or:

T^(2 * phi(R)) = 1 (mod R).

If we ran through this sequence again, we would get:

T^(3 * phi(R)) = 1 (mod R).

Clearly, we could keep doing this as many times as we like. So, we can expand on Euler's Totient Theorem, and state a more general corollary:

If GCD(T, R) = 1 and T < R, then T^(K * phi(R)) = 1 (mod R), where K can be any number.

However, we can state this corrollary another way. Notice that if K can be any number, then K * phi(R) is just the set of numbers that are evenly divisible by phi(R). Or, in other words, the numbers that are congruent to zero, modulo phi(R). So:

If GCD(T, R) = 1 and T < R, then T^S = 1 (mod R) whenever S = 0 (mod phi(R)).

Now, let's tweak our equation further by multiplying both sides by T:

T^S * T = 1 * T (mod R).

Simplifying leaves us with:

T^(S + 1) = T (mod R).

If we repeat this, we will get:

T^(S + 1) * T = T * T (mod R),

or:

T^(S + 2) = T^2 (mod R).

Doing this yet again will give us:

T^(S + 3) = T^3 (mod R),

and so on. This pattern looks familiar, doesn't it?

What makes it interesting this time is that S is not a multiple of R, but of phi(R). In other words, we have the rather surprising rule:

T^E = T^F (mod R) whenever E = F (mod phi(R)).

(once again, only as long as T < R, and T and R are relatively prime).

The Plot Thickens

We are on the edge of something very important. Let's back up a bit and look at this equation more closely:

T^(S + 1) = T (mod R).

Notice what we have here. We take a number, T, and raise it to a power, and when we do the calculation in modulus arithmetic, we wind up with T again. In short, we have a recipe for a function that returns its own input (presuming that R has been chosen ahead of time, and that T is verified to be relatively prime to R).

If you're thinking to yourself, "What's so interesting about that?", then consider what we would have if we broke this function up into two separate steps. Specifically, let's imagine that we can find two new numbers P and Q such that:

P * Q = S + 1, for one of the possible values of S.

Or, more to the point:

P * Q = 1 (mod phi(R))

Then we could write:

T^(P * Q) = T (mod R),

which is equivalent to:

(T^P)^Q = T (mod R),

and this is something that can be broken up into two steps:

T^P = X (mod R), and then
X^Q = T (mod R).

Now, if you don't see the value in doing this, imagine now that the two steps are performed on separate computers. And that X is sent from the first computer to the second over an insecure phone line....

Does This Really Work?

T stands for the plaintext, the message that is to be sent. P, Q, and R together form the cipher's keys -- P and R make up the public key, and Q and R make up the private key. And X becomes the encrypted message.

Here, again, is the central equation that makes it work:

P * Q = 1 (mod phi(R))

Note here that P and Q will both automatically be relatively prime to phi(R). (Why? Because if either P or Q had a factor in common with phi(R), then P * Q would also have that as a factor. But we know that P * Q divided by phi(R) leaves a remainder of one.) This is important.

Imagine a clockface, with just an hour hand, and imagine yourself placing the hour hand on midnight and then moving it forward by jumps, over and over, each jump covering N hours. If you pick a value for N that is divisible by 2 or 3 (the prime factors of 12), then you will find that you will only hit certain numbers before you return to midnight, and the sequence will then repeat. If N is 2, then the hour hand will visit 12, 2, 4, 6, 8, 10, 12, 2, 4, 6, 8, 10, 12 ...

If, however, your N is relatively prime with 12, then you will wind up hitting every number exactly once before finally returning to midnight 12 jumps later. For example, using 7 for your N, the itinerary would be: 12, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5, 12, ... In addition, the order in which you visit the numbers is entirely dependent on what value you pick for N.

In a similar vein, it is important that both P and Q be relatively prime to phi(R). Because of this, we know that every possible value for T, when raised to the power P modulo R, will land on a different number. (Remember that when doing exponents in modulus arithmetic, it is actually phi(R), and not R itself, that determines the length of the cycles.) If this weren't true -- if P, for example, shared a factor in common with phi(R) -- then some values for T could get mapped to the same value for X, and it would clearly be impossible to tell which was originally which. There could not be one value for Q that would correctly map X back to T every time.

The question of which T-values will wind up going to which X-values depends entirely on the value used for P -- and here's the rub for the would-be codebreaker: Just about every possible mapping of T-values to X-values does in fact exist. Somewhere out there is a P that will make that mapping.

If this:

T^P = X
X^Q = T

was the cipher's scheme, there'd be no cipher. With P already being public knowledge, it would be trivial to take an X and compute backwards to T. But, instead, we have this:

T^P = X (mod R)
X^Q = T (mod R)

as the cipher's scheme, and that changes everything. The modulus arithmetic erases too much information. There's no way to deduce how many times the hour hand needs to spin around the clockface when Q turns X back into T. Without knowing what Q is, a given X could wind up going to any of the possible values for T.

But what is really maddening to our would-be codebreaker is that even when T and P and X are all known, Q still can't be deduced! (Of course, it actually can -- but not necessarily within anyone's lifetime. But we're getting ahead of ourselves.)

So, let's see how to make this recipe work.

Making a Pair of Keys

To construct our own personal cipher keys, we need an appropriate value for R. So, we start by randomly picking two prime numbers, U and V, and multiplying them together:

R = U * V.

There are two good reasons for selecting a value for R that has exactly two prime factors. First of all, we have an easy formula for calculating phi(R):

phi(R) = (U - 1) * (V - 1).

Secondly, we want R to be hard to factor. The fewer factors a number has, the longer it takes to find them.

We then need to find values for P and Q such that:

P * Q = 1 (mod phi(R)).

When the numbers have been chosen, P and R together become the public key, and Q and R make up the private key. U and V are no longer needed, and can be forgotten.

An Example

In order to see all this in action, we want to stick with numbers that we can actually work with. So, for our example, we will select the primes 5 and 11 to be our U and V. This gives R a value of 55, and:

phi(55) = (5 - 1) * (11 - 1) = 4 * 10 = 40.

Now, we need to find numbers to fit the equation:

P * Q = 1 (mod 40).

There are, of course, an infinite number of pairs that will fit this equation. So, let's find one of them.

Our only initial constraint is that P and Q are both relatively prime to 40. So, we can't use numbers that are multiples of 2 and/or 5. We also don't want P and Q to be congruent mod 40, since that would turn our trapdoor cipher into a garden-variety symmetric cipher. Ideally, in fact, we'd prefer that P and Q be relatively prime to each other. Let's start with 7, which we'll assign to P:

7 * Q = 1 (mod 40).

What would that make Q? If we rewrite this equation to get rid of the unfamiliar modulus arithmetic, we have:

7 * Q = K * 40 + 1, where K can be any number.

The first value for Q that works is 23:

7 * 23 = 161 = 4 * 40 + 1.

So we have 7 for P, our public key, and 23 for Q, our private key.

To make our cipher work, you may recall that the values we use for T must be less than R, and also relatively prime to R. We also don't want to use 1 for T, because 1 raised to any power whatsoever is going to remain 1. Finally, the same holds true for R - 1, because R - 1 is congruent to -1, modulo R.

So, we'll take what's left and create the following character set:

2 3 4 6 7 8 9 12 13 14 16 17 18
A B C D E F G H I J K L M
19 21 23 24 26 27 28 29 31 32 34 36 37
N O P Q R S T U V W X Y Z
38 39 41 42 43 46 47 48 49 51 52 53
sp 0 1 2 3 4 5 6 7 8 9 *

The message we will encrypt is "VENIO" (Latin for "I come"):

V E N I O
31 7 19 13 21

To encode it, we simply need to raise each number to the power of P modulo R.

V: 31^7 (mod 55) = 27512614111 (mod 55) = 26
E: 7^7 (mod 55) = 823543 (mod 55) = 28
N: 19^7 (mod 55) = 893871739 (mod 55) = 24
I: 13^7 (mod 55) = 62748517 (mod 55) = 7
O: 21^7 (mod 55) = 1801088541 (mod 55) = 21

So, our encrypted message is 26, 28, 24, 7, 21 -- or "RTQEO" in our personalized character set.

When the message "RTQEO" arrives on the other end of our insecure phone line, we can decrypt it simply by repeating the process -- this time using Q, our private key, in place of P.

R: 26^23 (mod 55) = 350257144982200575261531309080576 (mod 55) = 31
T: 28^23 (mod 55) = 1925904380037276068854119113162752 (mod 55) = 7
Q: 24^23 (mod 55) = 55572324035428505185378394701824 (mod 55) = 19
E: 7^23 (mod 55) = 27368747340080916343 (mod 55) = 13
O: 21^23 (mod 55) = 2576580875108218291929075869661 (mod 55) = 21

The result is 31, 7, 19, 13, 21 -- or "VENIO", our original message.

How to Crack RSA

Now, let's switch hats. Imagine that we've just managed to pluck the message "RTQEO" off of our wiretap. By looking up the message's destination in the public-key directory, we find that our message was encrypted with a value of 55 for R and 7 for P. How do we go about decrypting it when we don't know the value for Q?

Well, we know that that:

P * Q = 1 (mod phi(R)),

or, without the modulus arithmetic:

P * Q = K * phi(R) + 1.

We can divide both sides of the equation by P, which gives us a formula for Q:

Q = (K * phi(R) + 1) / P.

K is also unknown, though, so we will try plugging in different numbers for K, and look for values for Q that meet all the necessary constraints.

(1 * 40 + 1) / 7 = 41 / 7 (doesn't divide evenly)
(2 * 40 + 1) / 7 = 81 / 7 (ditto)
(3 * 40 + 1) / 7 = 121 / 7 (ditto)
(4 * 40 + 1) / 7 = 161 / 7 = 23 (this could be it!)

Each time we find a candidate for Q, we can test it out on the message. We might get gibberish, in which case we can continue searching. If 23 hadn't worked and we needed to continue the search, it would be pretty obvious that we only needed to test every seventh number, since those are the only numbers which will give us a result that is evenly divisible by 7. Furthermore, we only need to test values up 39, thanks to the modulus arithmetic. So, even though this process involves a brute-force search, it is very simple and very fast.

Well then, so what's the catch? Simply that, in order to do any of this, we first need to know the value of phi(R). Of course, we already know that R has exactly two prime factors, so calculating phi(R) is a snap once we know what those factors are.

Famous last words.

How to Make RSA Uncrackable

Of course, in our case the factors of R can be found by consulting a times table. So it's not much of a challenge. (For that matter, since we're encrypting one character at a time, our coded messages would also be vulnerable to good old-fashioned cryptanalysis).

To make it less easy to find R's factors, we need to pick larger prime numbers for U and V to begin with. If, instead of 5 and 11, we had chosen 673 and 24971, we would have a value of 16805483 for R, and phi(R) would be 16779840. (This would also give us enough room to encrypt more than one byte at a time, which seriously reduces the vulnerability to cryptanalysis.) Looking for a P and Q pair is no longer something you want to do with pencil and paper, of course, but it took me less than three minutes to find the usable pair 397 and 211333 -- including the time it took to write and debug a Perl script.

On the other hand, it also took me less than three seconds to run "factor" on 16805483 to obtain 673 and 24971. Armed with those numbers, it wouldn't take much longer to derive 211333 from 397. So even these numbers aren't close to being large enough. We need really big numbers.

Well, we can certainly find huge values for R that are difficult to factor. But how far can we go before it becomes too difficult for us to use the number in the first place?

Huge Exponents in Modulus Arithmetic

The problem is this: The bigger R gets, the bigger P and Q will be, and P and Q are to be used as exponents! Even the relatively tame-looking

9^(9^9)

produces a number over 350 million decimal digits long. How are we going to be able to encrypt anything without needing terabytes of storage?

The trick is that we only need to calculate these exponential values modulo R. As always, modulus arithmetic simplifies things a great deal.

Let's revisit our example, and look at how we could decrypt the number 28, remembering that R = 55 and Q = 23:

28^23 (mod 55) = ?

To start with, we look at Q's binary representation. 23 in binary is 10111, which means that:

23 = 16 + 4 + 2 + 1, or
23 = 2^4 + 2^2 + 2^1 + 2^0.

We can now break the exponential calculation apart into several smaller ones:

28^23 = 28^(2^4 + 2^2 + 2^1 + 2^0)
= 28^(2^4) * 28^(2^2) * 28^(2^1) * 28^(2^0)
= 28^(2 * 2 * 2 * 2) * 28^(2 * 2) * 28^2 * 28
= (((28^2)^2)^2)^2 * (28^2)^2 * 28^2 * 28.

This may look like anything but an improvement, at first. But on a closer examination, you'll see that we actually have many repeated subterms. This simplifies matters, particularly when we take advantage of the fact that we are calculating in modulo 55.

We compute the first square in modulus arithmetic:

28^2 = 784 = 14 (mod 55).

By substituting this value into our equation:

28^23 = (((28^2)^2)^2)^2 * (28^2)^2 * 28^2 * 28 (mod 55),

we get:

28^23 = ((14^2)^2)^2 * 14^2 * 14 * 28 (mod 55).

Now by computing that square:

14^2 = 196 = 31 (mod 55),

we will have:

28^23 = (31^2)^2 * 31 * 14 * 28 (mod 55).

And, finally:

31^2 = 961 = 26 (mod 55), and
26^2 = 676 = 16 (mod 55);

and so:

28^23 = 16 * 31 * 14 * 28 (mod 55).

We can continue to take advantage of the modulus when we do the final multiplications:

28^23 = 16 * 31 * 14 * 28 (mod 55)
= 16 * 31 * 392 (mod 55)
= 16 * 31 * 7 (mod 55)
= 16 * 217 (mod 55)
= 16 * 52 (mod 55)
= 832 (mod 55)
= 7 (mod 55)

Lo and behold: 7, the same result as when we did it the hard way.

This binary technique is really no different than how computers normally compute integer powers. However, the fact that we can break the process down to successive multiplications allows us to apply the modulus at every step of the way. This assures us that at no point will our algorithm have to handle a number larger than (R - 1)^2.

Huge Factors in Modulus Arithmetic

The magic of modulus arithmetic will also ensure that it's possible to find our P and Q pair. Remember that, after we've selected some humongous value for R, we need to find values to fit:

P * Q = 1 (mod phi(R)),

or, without the modulus arithmetic:

P * Q = K * phi(R) + 1, where K is any number.

After picking a likely value for P -- which probably will not be a conveniently small number like 7 -- we will need to find a matching Q. By rewriting the above as:

P * Q - phi(R) * K = 1,

with known values for P and phi(R), we have what is called a Diophantine equation. This really just means that we have more unknowns than equations. However, it also means that algorithms exist for solving it, the most well-known one being Euler's. (One thing you quickly discover when you dabble in number theory is that a lot of things are named after Euler.) While it's still not something you'd want to do with pencil and paper, it doesn't involve anything more advanced than a whole lot of long division. In short, it's something that a computer can do in a relatively brief amount of time.

Safety in Numbers

Okay. So we know that the whole process is still practical, even if R is immense. But all of this is still moot unless we can select an R in the first place. R has to be the product of two prime numbers, don't forget. If we want R to be so big that it can't be factored easily, how are we going to find those factors to begin with?

It turns out that there is an interesting little asymmetry here. Determining whether or not a number is prime happens to be a relatively cheap process.

One of the most famous methods for testing a number for primality uses Fermat's Little Theorem. Here is the version of this Theorem that we're interested in:

If P is prime, then N^(P - 1) = 1 (mod P) is true for every number N < P.

Does this seems suspiciously reminiscent of Euler's Totient Theorem? It should. Euler was the first person to publish a proof of Fermat's Little Theorem, and his Totient Theorem is a generalization of Fermat's. You can see this for yourself by remembering that phi(P) = P - 1 when P is prime.

Of course, as far as proofs go, this theorem is only useful for proving that a given number is composite. For example, it just so happens that:

4^14 (mod 15) = 268435456 (mod 15) = 1,

even though 15 is no prime. Nonetheless, it is also true that:

3^14 (mod 15) = 4782969 (mod 15) = 9, and
5^14 (mod 15) = 6103515625 (mod 15) = 10.

On the other hand, 17, which is prime, results in 1 every time:

3^16 (mod 17) = 43046721 (mod 17) = 1,
4^16 (mod 17) = 4294967296 (mod 17) = 1,
5^16 (mod 17) = 152587890625 (mod 17) = 1, and so on.

So, if we want to know if a number is prime, we can run it through this test, using (say) 2 as the base. If anything besides 1 results, we know with certainty that the number is composite. If the answer is 1, however, we try the test again with 3, and then 4, and so on. If we keep getting back 1 as the result, it soon becomes rather unlikely that the number is anything but prime.

Unlikely, mind you, but not impossible. There are a handful of numbers which pass this test for every base, but which are not prime. Called Carmichael numbers, they are far more rare than the prime numbers -- but, like the primes numbers, there are still an infinite number of them. So we wouldn't want to rely on this test alone.

Fortunately, there are other tests for primality which are more reliable. But they all have at least one thing in common with this test: When they reject a number, they tell us only that the number can be factored. The test results give us no information at all as to what the factors might be. How unfortunate!

Unfortunate for the mathematicians, that is. Very fortunate for us.

Summing Up

The basic truth is that, in order to find the factors of a composite number, we're pretty much stuck with using brute force: Divide the number by all the primes you can get your hands on until one of them goes in evenly. There are plenty of ways to improve on this approach (the Number Field Sieve currently being the best), but they are complicated, and all they do is allow you to narrow the scope of the search. They don't reduce the search enough to make this problem tractable in general.

Nor is it likely that new approaches will, either! The real issue is that the encrypting and decrypting algorithms have a running time that is linear with respect to the length of R. That is to say, doubling the number of digits in R doubles the amount of time (roughly) needed to encrypt, decrypt, and to select the two primes to make a key with. But the algorithms for factoring R have a running time that is exponential with respect to the length of R. That is to say, the time (roughly) doubles with every few digits! (Because every digit added to R makes it ten times larger, and thus multiplies the number of potential candidates for its measly two factors.)

So if a new technique is suddenly found that makes it a trillion times faster to factor a number, all we have to do is increase the size of R we use by enough digits, and the situation will be right back where it started -- and all it means to us is that it takes a little bit longer to send and receive our messages. Already some people are using keys that, in order to factor with the Number Field Sieve, would require more energy than exists in the known universe.

An illustration: At the time of my writing, one of the largest general numbers that has been independently factored was the number used as the modulus for the RSA-140 challenge. (By "general numbers", I'm excluding creatures like Mersenne numbers and Fermat numbers, which have specialized factoring techniques that are inapplicable elsewhere.) It was completed on February 2, 1999. Now, the record previous to this was the RSA-130 number, and the process of factoring it was estimated as taking a total of 1000 MIPS-years of computer time. RSA-140, a number only 10 decimal digits longer, required twice that amount.

This, finally, is the heart of what makes RSA a trapdoor function: the gap between obtaining a number with two prime factors, and rediscovering the factors from the number itself. And the gap just keeps expanding as the numbers get larger.

The breakthrough that would completely destroy RSA's security would be an algorithm that actually produced a number's factors directly, instead of merely narrowing the search's scope. Such a thing has not been proven impossible, and it may well be that such a proof will never be found. But considering that prime numbers have been studied for thousands of years, and given the renewed attention that has been focused on this problem in the last few decades, the likelihood of the existence of such an algorithm appears very remote. Discovering one would change the face of number theory as much as RSA has changed the face of cryptography.

However -- if this were to happen, there are other trapdoor functions out there, waiting to be found. Whatever the future of RSA may be, the trapdoor cipher has certainly changed the face of cryptography forever.

References

1. Clawson, Calvin C.: "Mathematical Mysteries", 1996, Plenum Press. (Clawson devotes an entire chapter to the mathematics behind RSA, and it is this that gave me the inspiration to create this text.)

2. Benson, Donald C.: "The Moment of Proof", 1999, Oxford University Press. (Like the previous one, this fine book discusses the mathematics of RSA alongside of many other topics.)

3. Gardner, Martin: "Penrose Tiles to Trapdoor Ciphers", 1989, W.H. Freeman & Co. (This is another anthology of Gardner's wonderful columns for "Scientific American", and includes the column which was the first widely published description of the RSA cipher -- the one which set the NSA to frantically running around in circles.)

4. Ribenboim, Paulo: "The Little Book of Big Primes", 1991, Springer-Verlag. (The title should actually be "The Little Book of Big Number Theory" -- the book is chock full of theorems and conjectures that relate to prime numbers.)

5. Devlin, Keith: "All the Math that's Fit to Print", 1994, The Mathematical Association of America. (A collection of short columns from The Manchester Guardian, in which I learned that the set of Carmichael numbers has been proven to be infinite.)

6. Wells, David: "The Penguin Dictionary of Curious and Interesting Numbers", 1986, Penguin Books. (I had to pull this out at the last minute to find out how many digits were in 9^(9^9). For the curious whose libraries lack this little gem, the exact number of digits is 369693100.)

Thanks to readers Joel Sturman and Lee Sloan for pointing out errors and ommisions in previous drafts.

RSA Public-Key Cryptosystem

2010-03-22T20:53:00.000-07:00

RSA Public-Key Cryptosystem
Overview. Write a program to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adleman) cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating large integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate large integers (hundreds of digits). The built-in C type int is only capable of dealing with 16 or 32 bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers. You will use this data type to write a client program that encrypts and decrypts messages using RSA.

Note: the training wheels are off on this assignment - you're starting with a blank screen, not our code. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in. Remember to thoroughly test and debug each function as you write it.

The RSA cryptosystem. As discussed in Lecture S1, the RSA public key cryptosystem involves three integers d, e, and n that satisfy certain mathematical properties. The private key (d, n) is known only by Bob, while the public key (e, n) is published on the Internet. If Alice wants to send Bob a message (e.g., her credit card number) she encodes her message as an integer M that is between 0 and n-1. Then she computes:

E(M) = Me mod n

and sends the integer E(M) to Bob. As an example, if M = 2003, e = 7, d = 2563, n = 3713, then Alice computes

E(M) = 20037 mod 3713 = 129,350,063,142,700,422,208,187 mod 3713 = 746.

When Bob receives the encrypted communication E(M), he decrypts it by computing:

M = E(M)d mod n.

Continuing with the example above, Bob recovers the original message by computing:

M = 7462563 mod 3713 = 2003.

To check your arithmetic, you may use bc, maple, or xmaple.

Part 1 (extended precision arithmetic). The RSA cryptosystem is easily broken if the private key d or the modulus n are too small (e.g., 32 bit integers). The built-in C types int and long int can typically handle only 16 or 32 bit integers. Your main challenge is to design, implement, and analyze an extended precision arithmetic data type that can manipulate large (nonnegative) integers. To make it easier to check your work, we recommend working with integers represented using familiar decimal (base 10) notation. (We note that you could achieve superior performance by using a base that is a power of 2, e.g., 256 or 32,768.) Your data type will support the following operations: addition, subtraction, multiplication, division, modular exponentiation, and comparison. You may use the header file XP.h.

# Data structure. The first and most critical step is to choose an appropriate data structure to represent N-digit extended precision integers. A natural approach is to store each digit as an element in an array. To avoid pointers and memory allocation and deallocation headaches, consider packaging the array up in a struct as follows:

#define N 100 // maximum number of digits supported
#define NN (2*N + 1) // number of digits allocated

typedef struct {
unsigned char digit[NN];
} XP;

We declare our array to have slightly more than N elements to give ourselves a bit of extra scratch space to store intermediate results - the exact reason for using 2N + 1 will become clear later. Advanced students (who like pointers) may wish to make it a true first class ADT as in Sedgewick, p. 181.

# Initialization. Implement a function XPinitDecimal() that takes a string of decimal digits as input, and returns the extended precision integer corresponding to this string. If you represent integers using decimal notation, this will be straightforward; if you use base 2 or 256, consider using Horner's method to do the conversion.

# Display. Implement a function XPshowDecimal() that takes an extended precision integer as input and prints out a (decimal) representation of that integer.

# Addition. Implement the function XPadd(). It should take two extended precision integers as input and return a third extended precision integer that is the sum of the two. Implement the method you learned in grade school. Observe that if a and b are 2N-digit integers, the sum will have at most 2N + 1 digits.

Once you've written the above three function, you should be able to write code like:

XP a, b, c; // declare extended precision variables
a = XPinitDecimal("123456789"); // a = 123456789
b = XPinitDecimal("54545454"); // b = 54545454
c = XPadd(a, b); // c = a + b
XPshowDecimal(c); // print 178002243

# Random number generation. Implement a function XPrand() that takes as input an integer n and returns a pseudo-random n-digit extended precision integer by choosing each digit at random. This will be useful in debugging the subsequent code, and also in analyzing its complexity.

# Parity. Implement the function XPisOdd() that takes an extended precision integer as input and return 1 if and only if it is odd. You may assume that the base is even, so that this amount to checking the parity of the least significant bit.

# Comparisons. Implement the following functions: XPgreater(), XPless(), and XPeq(). They should take two (2N+1)-digit extended precision integers as input and return 1 if and only if the first integer is greater than (less than, equal to) the second.

# Subtraction. Implement the functions XPsub(). It should take two (2N+1)-digit extended precision integers as input and return a third extended precision integer that is the difference of the two. You should check that the first integer is greater than or equal to the second before subtracting; otherwise output an error message.

# Multiplication. Implement the function XPmul(). It should take two extended precision integers as input and return a third extended precision integer that is the product of the two. Observe that if a and b are N-digit integers, the product will have at most 2N digits.

# Division. Integer division is the most complicated of the arithmetic functions. Here is one of the simplest algorithms to compute q = a / b and r = a mod b, where a and b are extended precision integers, with b not equal to 0. This algorithm requires the least amount of code, but its correctness may not be immediately apparent.

div(a, b) {
if (a < b) return (0, a) (q, r) = div(a, 2b) q = 2q if (r < b) return (q, r) else return (q + 1, r - b) } Note that you should use extended precision arithmetic to perform each of the intermediate computations. The natural way to implement this algorithm is using recursion. Observe that if a and b are 2N-digit numbers, then the intermediate results will never have more than 2N+1 digits. Part 2 (encryption and decryption). Now it's time to put all your hard work to use. The encryption and decryption processes are identical, except that they involve different encryption/decryption keys. Write a program rsa.c that takes in one command line arguments (the name of the encryption key), reads in a decimal string from standard input, and applies the RSA function to the message. It should work as follows. In real applications, you might want to send an ASCII text message instead of a decimal integer; however, you are only responsible for handling decimal inputs. % gcc126 rsa.c xp.c # compile % a.out bob.pub < message.txt > message.encrypted # Alice encrypts
% mail bob@princeton.edu < message.encrypted # Alice emails Bob
% a.out bob.pri < message.encrypted # Bob decrypts

# RSA function. The key step is to implement the RSA function: given three extended precision integers a (the base), b (the exponent), and n (the modulus), compute c = ab mod n. You will implement this as the function XPrsa() in xp.c.

A natural way to compute c is to set x = 1; then multiply it by a, b times; then set c = x mod n. This method has two serious flaws.

# First, observe that if the inputs a, b, and n are N-digit decimal integers, then the intermediate result x could contain as many as 10N digits. To see the great importance of this, observe that if N is 30, the intermediate result could consume a terrabyte of memory!

# The second problem is that repeating anything b times will be slow. If b is even moderately large (say 30 decimal digits), it will take centuries to execute, even on the fastest supercomputer.

We use two ideas to overcome the above obstacles. First, the following mathematical identity is useful to keep the intermediate numbers small.

xy mod n = ((x mod n) * (y mod n)) mod n

Second, we use the technique of divide-and-conquer or repeated squaring. We incorporate both ideas into the following pseudocode. This allows us to perform modular exponentiation in a reasonable amount of time (when an appropriate base case is added).

t = a ^ (b / 2) mod n
c = (t * t) mod n
if (b is odd)
c = (c * a) mod n
return c

Note here that the division is integer division, and each of the intermediate computations is performed using extended precision arithmetic. The exponentiation computation is naturally implemented using recursion. As above, if a, b, and n are N-digit numbers, then the intermediate results in this function will never have more than 2N digits. However, since t * t could be 2N digits long, the intermediate results in the mod (division) function might be as many as 2N + 1 digits. This explains why we allocate 2N + 1 digit.

Part 3 (analysis). Perform a complexity analysis of the following operations for N-digit extended precision arithmetic: addition, multiplication, division, RSA encryption (RSA exponent is small, say 7), and RSA decryption (RSA exponent has roughly N digits) algorithms. For each operation, give the exponent and coefficient of the leading term in its asymptotic running time, e.g., 1.3 × 10-5 N2 seconds. Justify your answers with empirical and/or theoretical evidence. Using this analysis, estimate the largest input (measured in number of digits) that each of your functions could handle in 1 day (86,400 seconds). Depending on your conclusions, you may wish to modify your design and implementation to improve performance. You may find it helpful to use the program timing.c to estimate the running times of your functions.

Legal notice. It is a violation of US law to export your solution for this assignment to foreign governments or embargoed destinations (Cuba, Iran, Iraq, Libya, North Korea, Serbia, Sudan, Syria, and Taliban-controlled areas of Afghanistan as of January 2000). It is also illegal to import your solution into several countries, including France, Iran, Iraq, and Russia.

Extra credit. Write a program that compute two large pseudo-random prime numbers p and q of a specified number of digits. Compute φ = (p - 1) (q - 1), and select a small integer e that is relatively prime with φ. Use these to generate a public key (e, n) and its companion secret key (d, n).

This assignment was created by Bob Sedgewick and Kevin Wayne.
Copyright © 2000 Robert Sedgewick