Symmetric-Key Cryptography

Cryptography converts readable data into gibberish, with the ability to recover the original data from that gibberish. The first flavor of crypto is called symmetric key. In this approach, an algorithm uses a key to convert information to what looks like random bits. Then the same key is used to recover the original data.

Bob is a sales rep for a company that makes printing machinery. He sells to a newspapers, magazines, independent printing houses large and small, and even universities. His product line includes presses, tools, replacement parts, repair services, and training. The end of the quarter is coming up in a couple of weeks, and he’s just received a memo from Alice, the vice president of sales. The company is having difficulty “making its number” the memo says. Then it outlines a new, complex pricing policy.

This new policy list the asking prices for all their products and also indicates the lowest prices sales reps are allowed to negotiate. In the past, they have based the amount of the discounts they give on the size of the order, expectations of futuresales with a given client, and other factors. But now, the memo states, sales reps have the authority to give even bigger discounts.

Bob wants to closely limit who has access to this information. If potential costumers knew how far he was willing to go in discounting, they would have edge in negotiations. Existing costumers might demand rebates, and competitors would gain knowledge that could aid them in winning contract. In addition, stock analyst or business reporters could report the company‘s slow sales this quarter, affecting its reputation.

How can Bob and Alice keep this memo secret? They could choose not to let it leave the office, or may be Bob could simply memorize it.But its more than 20 pages long and too complex to memorize it, and he will need to consult it while trying to make a sale.

So Bob keeps an electronic copy of the memo on his laptop, and takes steps to protect the file. But Bob can lose his laptop, or someone might steal it or simply look through the files while he’s at lunch. To protect the file he decides to encrypt it.

Let say Bob buys a computer program to encrypt sensitives files. When running the program, he simply flips the switch to encrypt and feeds the file to the program. When file comes out of the program, it looks like gibberish. If intruders get their hands on it, they will have no idea what it means.

The problem is that as long as the file is gibberish Bob won’t be able to read it either. To read it he must somehow convert it back to its original form. The program has just a feature; he flips the switch to decrypt, feeds in the gibberish, and out comes the file in its former conditions.

But there is one problem with ths scenario. If intruders are able to operates the program, and can obtain the encrypted file, thus, the intruders can convert the encrypted file back. Even if they can’t, where can Bob safely store the program? If he can keep the program out of the hands of attackers, why not store his file there as well?

No, he does not have a place where he can keep the encrypting and decrypting program safe. And Bob has access to it, he must assume that attackers can gain access. That is why he uses encryption in the first place. By itself, an encryption machine cannot protect secrets. Bob needs additional protection.

That additional protection is a secret number. If he feeds the file and a secret number to the program, the program will encrypt the file. Until the program has a secret number, it will not run. To decrypt the file, Bob must present the gibberish and the same secret number.

If an attacker somehow obtains a copy of the gibberish and feeds it to the program for recovery, it on’t work. The program ask fo the number, which the attacker does not know. It’s possible to try numbers at random ( or to try all possible numbers systematically), but every time a wrong number is inserted, the application simply spits out different gibberish.

Event hough someone can use the same program Bob used, It never re-creates the original file without the secret number. Even if the attacker guesses a number close to the original number, even if it is off by only 1, the program will not produce anything close to the correct encrypted file.

Crypto Terminology

When we want to convert sensitive information to gibberish, we encrypt the data. To convert it back, we decrypt it.To do this, w use an algorithm. The word “algorithm” is a scientific term for a recipe or step-by-step procedure. It is a list of instructions or things to do in a particular order. An algorithm might have a rigid list of commands to follow, or it might contains a series of questions and depending on the answers, describe the appropriate steps to follow. A mathematical algorithm might list the operation to perform in a particular order to “find x”. For example, an automobile diagnostic algorithmmay ask questions about oil pressure, torque, fluid levels, temperature, and so on, to determine what’s wrong. A computer program can also implement an algorithm, meaning the program converts the algorithm’s list of commands, questions, and operations into the computer’s language, enabling it to perform the steps in appropriate order. In computer cryptography, algorithms are sometimes complex mathematical operations or simply bit manipulations.Many encryptions algorithm exist, and each one has its own particular list of commands or steps. Just as you can have a program that plays solitaire or one that computes the trajectory of satellites, you can have a program that implements an encryption algorithm that takes your data and converts it to gibberish.

The data that you want to keep secret is called plaintext ( some call it cleartext). Your plaintext could be a human-readable text file, such as the memo. Or it could be a binary file, which looks like nonsense for human eyes but makes perfect sense for computer program. For example, if you open a PowerPoint file using windows text editor, the file looks like gibberish because the program cannot convert the PowerPoint formatting informations; but if you open the same file in PowerPoint, it appears as intended. Whether or not your information is readable by a human or a given program, it’s called plaintext.

After data is encrypted, it’s known as ciphertext.

The algorithm encrypts our plaintext into ciphertext, but it need one more thing-a key.

We have also met attacker, someone trying to steal information. Actually, an attacker may try to do more than simply uncover someone else’s secrets. Some attackers try to pose as people they are not, disable website, delete someone’s information, prevent customers from buyingat a particular onine merchant, slow down systems, and on and on and on.The term attacker is simply a catchall for the individual from whom we must protect our digital assets.

The study of breaking cryprographic systems is known as cryptanalysis. Similar to the attacker, the cryrptanalyst looks for weaknesses in algorithm. All algorithm can be “broken”; the good ones are simply the algorithms strong enough to withstand an attack for so long the break comes ‘too late”. So a cryptanalyst ‘s job is to find weaknesses that may help someone break the algorithm faster. Attacker may use cryptanalitical techniques to damage the cryptography algorithm, but yhey also use other tools.

The cryptographer develops crypto systems: the cryptanalyst looks for weaknesses. It’s important for the crypto communityto know about the weaknesses, because the attackers are looking for them as well.Attackers are almost certainlynot going to announcetheir discoveries to the world, so cryptanalysts perform a service, letting us all know what attackers probably know but won’t tell us.

Why Cryptography??

If someone tell you, “ I don’t need security. I have no secret, nothing to hide,” respond by saying, “OK, let me see your medical files. How abaout your paycheck, bank statement, investment portofolio, and credit card bills?Will you let me write down your Social Security Number, credit dard number and bank account number? What is the PIN for your ATM, credit card or phone card? What is your password to log on to the network at work? Where do you spare house key?”

The point is that we all have information we want kept private. Sometimes the reason is simply our natural desire for privacy, we would feel uncomportable if the whole world knew our medical history or financial details. Another good reason is self protection-thieves could use some kinds of information to rob us. In other words, the motives for keeping secret are not automatically nefarious.

Corporations also have secrets-strategy report, sales forecast, technical product details, rsearch result, personnel files,and so on. Although dishonest companies might try to hide villainous activities from thr public, most firms simply want to hide valuable information from dishonest people. This people may be working for competitors, they might be larcenous employees, or they could be hacker or crackers : people whobreak into computer networks to steal information, commit vandalism, disrupt services, or simply to show what they can do.

For your secrets to be secure, it may be necessary to add protections not provided by your computer systems OS.The built in protections may be adequate in some cases.If no one ever tries to break into or steal data from particular computer, its data will be safe.Or if the intruder has not learned how to get around the simple default mechanism, they are sufficient. But manu attackers do have the skills and resources to break various security system. If you decide to do nothing and hope that no silled crackers targets your informations, you may get lucky, and nothing bad will happen. But most people aren’t willing to take that risk.

One of the most important tools for protecting data is cryptography, any various method that are used to turn readable files into gibberish. For example, suppose your sensitive material look like this:

“do not believ that the competition can match the new feature set, yet their support, services,and consulting offering pose a serious threat to our salability. We must invest more money in our”

Here is what the data look when it encrypted:

“1214!@#$%^&^&**+???ASHJHKBYT{K:LNKLJ:L#$%^&**())TTUI BJKBM CVJNMK?L":PBFTYCDKMO:P!@#$%^&*(+_

Even if attacker obtains the contentof the file, it is gibberish. It does not matter whether or not the OS protections worked. The secret is still secret.

In addition to keeping secrets, cryptography can add security to the process of authentication people ‘s identity. Because the password method used in almost all commercial operating systems is probably not very strong against a sophisticated ( or even an unsophisticated) attackers want to pose as someone else, it’s not a matter simply of guessing a password. Attackers must also solve an intractable mathematical problem.

In the physical world, security is a fairly simple concept. If the lock on your haouse’s doors and windows are so strong that a thief cannot break into steal your belongings, the house id secure. For further protection against intruders breaking through the locks, you migh have security your bank account but the teller asks for identification and does not trust the thief’s story, your money is secure. When you sign a contract with another person, the signatures are the legal driving force that implies both parties to honor their word.

In the digital world, security works in a similar way. One concept is pripacy, meaning that no one can break into files to read your sensitive data (such as medical record) or steal money (by, for example,obtaining credit card numbers or online brokerage account information). Privacy is the lock on the door. Another concept, data integrity, refers to a mechanism that tell us when something has been altered. That’s the alarm. By Applying the practice of authentication, we can verify identities. That is comparable to the ID required to withdraw money from a bank account (or conduct a transaction with online broker). And finally, non repudiation is a legal driving force that impels people to honor their word.

Cryptography is by no means the only tool needed to ensure data security, nor will it solve all security problems. It is one instrument among many. Moreover, cryptography is not foolproof. All cryto can be broken, and more importantly, if it is implemented incorrectly, it adds no real security.

Quantum Cryptography : Secure Key Exchange??

How can we communicate secret messages and be sure that they are not read by an undesirable third person? Cryptography is the discipline that tries to answer this question.

In traditional cryptography, only the Vernam cipher permits the establishment of an unconditionally secure channel between a sender (Alice) and a receiver (Bob). This method requires Alice and Bob both to agree on a secret key, which is determined beforehand. Alice encodes the message using this key, and the encoded message cannot then be decoded, except by using the same key, i.e., by Bob. The rule for encoding is simple. Suppose that Alice wants to transmit one bit of information. For this she uses one bit of the key, performing an ”exclusive-or” operation with the bit to be transmitted. Bob, on his part, can redo the same operation, which cancels out the first ”exclusive-or”, to decode the transmitted bit.

Unfortunately, the Vernam cipher suffers from a major inconvenience. For the method to remain unbreakable, the key must consist of as many secret bits as the message to be transmitted, since the key can only be used once. Using a key more than once causes the Vernam cipher to lose its property of being unbreakable and allows a fairly easy cryptanalysis after successive transmissions.

Strictly speaking, the secret key must originally be exchanged from hand to hand by Alice and Bob. This means that if one wants to transmit a gigabit of secret information, Alice and Bob must meet to exchange, forexample, a CD-ROM containing a billion random bits. This procedure is not practical because it imposes that Alice and Bob must meet, even if they then want to communicate at a distance of 10.000 km.

Mathematicians have therefore developed other cryp-tographic methods, looking to rectify these difficulties.The first difference between the Vernam cipher and current methods of encoding consists in replacing the simple ”exclusive-or” operation by a much more com-plicated operation between the key and the plaintext message.Using these methods,it is practically infeasible to recover the plaintext from the encoded message, or even to recover the key from the plaintext together with corresponding encoded message,even if the key is much smaller than the message to be sent. This is the case, for example, with the DES block cipher, or the more recent Belgian Rijndael algorithm, chosen to be the new AES standard.

Thanks to these algorithms, Alice and Bob can now exchange a small key, which is useful for encoding big messages. The price to be paid for this advantage is that absolute security is lost, and an assumption must be adopted. In theory, it is now possible to recover the plaintext message from the encoded message, but doing this is sufficiently difficult that we can suppose that the enemy does not have the computational resources to do it.

In practice, this assumption is realistic. A hacker will find it much easier, in general, to exploit the weaknesses of an information processing system itself than to perform the necessary calculations to break the algorithm, even if in possession of todays most powerful computers. Nevertheless, nothing says that in the long term, developments in mathematics or information theory willnot make feasible the extraction of the plaintext message from the encoded message.

The second improvement of modern cryptography is the introduction of public key cryptography, allowing Alice and Bob to exchange secret messages without meeting beforehand to exchange a key.

In public key cryptosystems, widely used these days, each correspondant possesses two keys. One key is pub-lic and known to all (for example, it may be published in a directory) and only permits the encoding of a message, not the decoding. The second key, on the other hand, is private, and only permits decoding. To send a message from Alice to Bob, the procedure is as follows. If she hasnt alreadydonethis, Alice procures Bob ‘s public key (from a public database, or perhaps she simply asks Bob for it). Then, Alice uses Bobs public key to encode her confidential message and sends the encoded information to Bob. Bob is the only person in possession of the corresponding private key, and thus the only person able to decode the message which Alice has just sent him.

In this scheme, the essential idea is that encoding is public, in the sense that anyone can send an encrypted message to Bob, but that decoding requires knowledge of the private key.

Again, the practical advantages of public key cryptography should be weighed against the loss of security that is introduced (compared with the Vernam cipher). A connection exists between the public key and the corresponding private key, and it is therefore possible in theory to recover the one from the other. Nevertheless, it is fortunately very difficult to carry out this operation within the limits of current mathematical knowledge and the power of contemporary computers.

In order to demonstrate these ideas, let us take the example of the Rivest-Shamir-Adleman (RSA) algorithm, which can be used as the basis of a public key cryptosystem. In this system, the private key can be deduced from the public key if one is able to factorise numbers larger than a certain number of digits, which is currently very difficult. In fact, while it is easy to multiply two large prime numbers together, recovering them from the product is much more difficult. Unfortunately, advances in factorisation always raise the bar for cryptographers, who must use keys, and thus numbers to factorise, that are larger and larger. In addition, if a mathematician one day discovers an algorithm enabling the rapid factorisation of large numbers, he will be able to decode all messages encoded with RSA without anyone knowing it, since he has access to all the public keys.

This danger is all the greater since physicists have devised a new method of doing calculations, using a quantum computer. This new generation of computers, still at an essentially theoretical stage, has the property of being able to solve rapidly certain problems that are believed to be difficult with traditional information theoretic techniques. Thus Peter Shor has discovered a quantum algorithm (that is an algorithm that runs on a quantum computer) allowing the factorisation of large numbers in a reasonable time. It seems, therefore, that many dangers are present for the long term security of current cryptographic techniques. Classical cryptography, while popular and currently offering a level of security that is largely sufficient, gives no long term guarantee of the messages it is used to protect. This is why we want to present here an alternative manner of securing the confidentiality of a message, without relying on technological assumptions, or complexity assumptions (i.e., assumptions about the speed with which a certain mathematical operation can be carried out using the computers of today).

Are we then condemned to exchange, by hand and in advance, megabits of secret keys in order to guarantee absolute security? From the point of view of the most fundamental laws of physics known today, there is another possibility. Quantum physics, describing the individual dynamics of each elementary particle (photons, electrons,...) that makes up our universe can offset this difficulty and allows the construction of communication protocols with no security weaknesses. This is the aim of quantum cryptography.

Quantum cryptography was born around 20 years ago when two researchers, Charles Bennett and Gilles Brassard, had the idea of using quantum physics or transmitting confidential messages. The transmission s achieved using individual photons (”quanta” of light) sent from a sender (Alice) to a receiver (Bob) via an optic fibre.

A theorem known as the ”no-cloning theorem” prevents a third party (Eve) from being able to decode the information transmitted. Indeed it can be shown that if one does not have in advance a precise characterization of the quantum state describing the light, and in particular of the state of the photon, then it is impossible to reproduce the state, that is to make a clone. In fact, the simple act of observing a photon, in order to determine its state, disturbs it in such a way that afterwards, one cannot return it to itsinitial state,or produce a clone. The no-cloning theorem is bad news for anyone wanting to determine completely the quantum state of a photon. On the other hand, it can be seen as positive from the point of view of cryptography. Eve, who wants to read the secret information without being detected, needs to copy the quantum state of the photon. Since this is impossible, she must at least determine the quantum state of the photon. But by attempting to do this, she introduces disturbances, and can therefore be detected by Alice and Bob.

The essential goal, then, is for Alice and Bob to exchange a secret key with the assurance that any attempt at eavesdropping by a third party will be detected. If this secret key is correctly transmitted, then Alice and Bob can use it with the Vernam cipher method described above, thus obtaining a cryptosystem that is unconditionally secure even at a distance.

Beginning with the idea of no-cloning, researchers have described a communication protocol that uses the polarisation of photons to encode the bits that will be the secret key. Photons possess two states of polarization that can be distinguished using a polarising filter (such as a calcite crystal, for example). Like this, vertically polarised light will pass through a filter oriented in the same sense, while horizontally polarised light will not pass, but will be abosorbed by the filter. If now the light is diagonally polarised at 45 , only half of the light intensity will pass. What happens if we only allow a single photon at a time, diagonally polarised, to impinge upon the filter? Clearly the photon cannot be divided into two, since it is the indivisible building block of light.

Experiment shows that, as predicted by quantum theory, half of the time the photon will pass through the filter, and half of the time it will be absorbed.

Did you know: CryptoBytes

Egyptians used alternate hieroglyphs while inscribing tablets, the first documented use of written cryptography. The place was Menet Khufu, which borders the Nile River. The writer of these tablets did not use a completely different set of hieroglyphs, though. Instead, his was a system of partial substitution, with some unusual hieroglyphs here and there.

To hide messages, generals in ancient Greece used the shaved head of a servant, tattooed the message on his bald scalp, waited a week, and then sent the servant on his way. The secret message was concealed under a fresh growth of hair.

The Arabs were the first to make significant advances in cryptanalysis (the practice of changing ciphertext into plaintext without complete knowledge of the cipher).

Abu Yahmadi, creator of the first Arab dictionary, wrote a book in 725 on how he solved a Byzantine cryptographic puzzle written in Greek. His method of attack started on an assumption that the puzzle began with "In the name of god," and so he worked out the rest from that assumption. This method of attack is the same one that was employed in World War II to break German communications.

Subhalasha, an Arabic Encyclopedia (1412), contained a section on Cryptography. Ciphers cited are substitution and transposition. Also, it mentioned running a text through multiple substitution ciphers.

In the famous Greek drama the Iliad, cryptography was used when Bellerophon was sent to the king with a secret tablet which told the king to have him put to death. The king tried to kill him by having him fight several mythical creatures, but he won every battle.

The first major advances in cryptography were made in Italy. Venice created an elaborate organization in 1452 with the sole purpose of dealing with cryptography. They had three cipher secretaries who solved and created ciphers that were used by the government.

But during the Spanish Inquisition epoch the cryptography was doomed and persecuted being considered black magic and Satanic deed.

But during the Spanish Inquisition epoch the cryptography was doomed and persecuted being considered black magic and Satanic deed. In the period of Renaissance the creativity in many spheres also gave impulse to cryptography as a science and as an art of secret communications between the monarchs and emperors, like Leonardo da Vinci, Cardinal Richelieu and the Kings of France Louis XII-XIV. The «coding of messages», the substitution of words and figures by symbols and numerals of previously agreed character became wisely used in government correspondence. And the services of specialists in coding and decoding of secret letters became available as a result of this practice.

The Kama Sutra of Vatsayana lists cryptography as the 44th and 45th of 64 arts (yogas) men and women should know and practice. The date of this work is unclear but is believed to be between the first and fourth centuries, AD. In this list of arts, the 44th and 45th read: The art of understanding writing in cipher, and the writing of words in a peculiar way; The art of speaking by changing the forms of words. It is of various kinds. Some speak by changing the beginning and end of words, others by adding unnecessary letters between every syllable of a word, and so on.

The Equatorie of the Planetis (1392), possibly written by Geoffrey Chaucer, contains passages in cipher. The cipher is a simple substitution with a cipher alphabet consisting of letters, digits and symbols. Breaking codes can make or break historical figures. A good example of how codes can change history, is the story of Mary Queen of Scots, a Catholic who was chased out of an th Century. Mary fled to England looking for increasingly Protestant Scotland in the 16protection from her cousin Elizabeth, the queen of England, but instead she received 19 years in prison. Sir Francis Walsingham, Elizabeth's principal secretary suspected that Mary was actively involved with a man called Anthony Babington to overthrow Elizabeth. Walsingham intercepted messages that Mary had written to Babington in a secret cipher. Little did they know that the person helping them smuggle messages was a double agent working for Queen Elizabeth. Walsingham handed the messages over to a man called Thomas Phelippes to decode. This he eventually did, and Mary effectively signed her own death warrant. Just because we can't understand a text does not mean that it was necessarily meant to be kept secret. Sometimes it is just that we have lost the art of decoding them. The ancient Egyptians used hieroglyphs, as their means of written communication and for thousands of years this script was a mystery to scholars. In 1799, a French team discovered a slab of stone, now known as the Rosetta Stone, which is permanently housed in the British Museum. The Rosetta Stone contained three scripts, hieroglyphics at the top, demotic (the simplified form of ancient Egyptian writing) in the middle and Greek at the bottom. Over the course of many years, using the Rosetta Stone as a reference point, scholars gradually unraveled the mysteries of hieroglyphics.

The writer Edgar Allan Poe had a great fascination with cryptography. Besides numerous references to it in his stories, he conducted his own cryptographic challenge in December 1839. This challenge was published in Alexander's Weekly Messenger, and in it he asked the readers to submit their cryptographs to him, asserting that he would solve them all. He was true to his word and for the next six months, Poe managed to decipher all the codes submitted by his readers. A year later he was sent two cryptographs by one of his readers, Mr. W.B.Tyler. Poe published these cryptographs in the magazine for his readers to solve, but never published the solutions himself. Many believe that W.B.Tyler was a pseudonym for Poe himself, and that he was the author of the cryptographs, which remained unsolved for decades. The first US Patent on a cryptographic device was filed in 1861. About 1,800 patents on the field have been issued since.

In 1895, radio was invented. The importance of this to cryptology is immense. During times of War, it allowed for enemy communications to be intercepted in mass. Thus, the profession of cryptanalysis, or the breaking of encrypted messages, was born.

Gilbert S Vernam created a machine in 1917 that makes a non-repeating, virtually random sequence of characters (often called a one-time pad). Using an encryption key the same length as the message, and never using that key again is the only proven method of securely communicating. However, it is impractical under most circumstances because all parties must have a long and identical key, which presents a logistical nightmare for everyday use.

In 1918, the United States employed eight American Indians from the Choctaw tribe to relay important messages across insecure communication channels in their native tongue. Since Native American languages are extremely complex and difficult to learn, this allowed for simple and effective encryption. During World War II they repeated this trick with the Navaho code talkers.

The greatest era of international smuggling - Prohibition (in the 1920s) - created the greatest era of criminal cryptology. (To this day, the FBI runs a cryptanalytic office to deal with criminal cryptography.) During Prohibition, alcohol was transported into the country by illegal smugglers who used coded radio communication to control illegal traffic and help avoid Coast Guard patrols. In order to keep the Coast Guard in the dark, the smugglers used an intricate system of codes and ciphers. The Coast Guard hired Mrs. Elizebeth Smith Friedman to decipher these codes, and thus forced the smugglers to use more complex codes, and to change their keys more often. She succeeded in sending many of them to jail.

In 1924, Alexander von Kryha produced his «coding machine» which was used, even by the German Diplomatic Corps, into the 1950s. However, it was cryptographically weak - having a small period. A test cryptogram of 1135 characters was solved by the US cryptanalysts Friedman, Kullback, Rowlett and Sinkov in 2 hours and 41 minutes.

Nevertheless, the machine continued to be sold and used - a triumph of salesmanship and a lesson to consumers of cryptographic devices. In the 1930s, the British developed the TYPEX encryption machine, based on the commercial Enigma from the 1920s. This machine contained five rotors, each of which changed letters of the alphabet to other letters. After each character of the message being encrypted was typed, the rotors changed positions, creating an entirely new encryption scheme for the next letter. Reversing the process decrypted the message.

In 1937, the Japanese invented the PURPLE machine to encrypt messages. This machine was a totally new concept to cryptography. All machines prior to it used rotors to change the position of letters in the alphabet. Instead, the Purple Machine used telephone stepping switches, and thus standard cryptanalytic techniques were useless against it. US cryptographer William Friedman eventually broke the code generated by this machine.

The Bombe, a machine that decodes Enigma messages, was invented in 1940. The workload of (Russian) code machine operators was enormous: between 1941 and 1945 they coded and decoded more than 1,6 million messages (or 1500 telegrams in cipher per day). By the end of the war, the cryptographic service of the General Staff of the Army comprised some 5000 specialists and the amount of coding machines involved in the providing of security of telecommunications reached some 396 units.

The Lucifer cipher was developed at IBM in 1970. This eventually evolved into DES, which was accepted as the official US standard, only recently replaced by AES. DES was strengthened in the form of triple-DES, an algorithm accepted worldwide as relatively secure.

"New Directions in Cryptography" was published in 1976, introducing the concept of public-key cryptography, which forms the basis of Internet encryption. The book also focuses on the powers of authentication via a one-way function, where the authenticator does not need to know the actual password.

In 1990, mathematicians from Switzerland invented the International Data Encryption Algorithm (IDEA) to replace the aging DES. IDEA has 128 bits, meaning there are 340,282,366,920,938,463,463,374,607,431,768,211,456 possible keys. This algorithm also has the advantage of being able to be carried out quickly, because it uses math that comes naturally to computers.

In English, "e" is the most common letter, typically showing up 13 percent of the time. Code breakers look for such patterns, deducing that if a certain letter or symbol shows up more than any other, it probably stands for the letter "e."

During WW2, the neutral country Sweden had one of the most effective cryptanalysis departments in the world. It was formed in 1936, and by the time the war started, employed 22 people. The department was divided into groups, each concerned with a specific language. The Swedes were very effective in interpreting the messages of all the warring nations. They were helped, however, by bungling cryptographers. Often the messages that were received were haphazardly enciphered, or even not enciphered at all.

The Swedes even solved a German cipher that was implemented on a Siemens machine similar to a Baudot machine used to encipher wired messages. In a short story by Sir Arthur Conan Doyle, The Adventure of the Dancing Men, Sherlock Holmes is confronted by a simple substitution cipher. He solves the crime by deciphering a code in which the cipher text elements are hieroglyphics of little dancing men. Holmes figures these symbols are some kind of secret code. Using the method of frequency analysis, he substitutes the letter 'e' for the most commonly occurring figure. He also notices repetitions of certain poses, yet these dancers hold flags in their hands. Instead of counting these as different letters, he deduces that they mark word divisions. Following along these lines, and with the aid of some background knowledge of the squire's wife, he manages to crack the code and solve the case.

The Politics of Cryptography

Ciphering has always been considered vital for military and diplomatic secrecy. Empires and nations have frequently owed their existence to the security of their communications, as information that falls into the wrong hands can give an enemy a crucial advantage.

Historians believe that the deciphering of the German Enigma codes by British intelligence at Bletchley Park in World War II played a key role in the allied victory. Indeed, the Allies went to great lengths to prevent the Germans from discovering that the Enigma had been broken. For instance, when the British discovered the locations of five German tankers refueling submarines in the Atlantic, they sank only three. If the British had taken out all five tankers, the Germans might have become suspicious.

Is cryptography a weapon? Its relation to military operations seems to be rather that of a support function. An army needs jeeps, radios, food and clothes, just as it needs a way to report observations, and receive orders, that cannot be overheard by its rivals.

Here are a few historical events where cryptography had played an important role. The Spartans of Greece created the first military form of cryptography. They used a system which consisted of a thin sheet of papyrus wrapped around a staff (known as a skytale). This was used in the 5th century B.C. to send secret messages between Greek warriors. The secret key of the text is the circumference of the wood. With the wrong circumference, the message is unusable. If the wood matches, you are able to read the message.

In the latter part of the Middle Ages the use of secret writing increased. European cryptology dates from the Middle Ages, during which it was developed by the Papal States and the Italian city-states. The first brief code vocabularies, called nomenclators, were gradually expanded and became the mainstay for several centuries for diplomatic communications of nearly all European governments. In 1628, a Frenchman named Antoine Rossignol helped his army defeat the Huguenots by decoding a captured message. After this victory, he was called upon many times to solve ciphers for the French government. When Rossignol died in 1682, his son, and later his grandson, continued his work. By this time, there were many cryptographers employed by the French government. Together, they formed the "Cabinet Noir" (the "Black Chamber").

By the 1700's, "Black Chambers" were common in Europe, one of the most renown being that in Vienna. It was called 'The Geheime Kabinets-Kanzlei' and was directed by Baron Ignaz de Koch between 1749 and 1763. This organisation read through all the mail coming to foreign embassies, copied the letters, resealed them, and returned them to the post-office the same morning. The same office also handled all other political or military interceptions, and would sometimes read as many as 100 letters a day.

The English Black Chamber was formed by John Wallis in 1701. Until that time, he had been solving ciphers for the government in a variety of unofficial positions. After his death in 1703, his grandson, William Blencowe, who was taught by his grandfather, took over his position and was granted the title of Decypherer. The English Black Chamber had a long history of victories in the cryptographic world.

In the early history of the United States, codes were widely used, as were book ciphers. During the American Civil War (1861-1865) ciphers were not very complex. Many techniques consisted merely of writing words in a different order and substituting code words for proper names and locations. The Confederate Army primarily used the Vigenère cipher and on occasion monoalphabetic substitution.

In the beginning of the 20th century, war was becoming likely in Europe. During World War One, England spent a substantial effort improving its cryptanalytic capabilities so that when the war started, they were able to solve most enemy ciphers. The cryptanalysis group was called 'Room 40' because of its initial location in a building in London. Their greatest achievements were in solving German naval ciphers. These solutions were greatly simplified because the Germans often used political or nationalistic words as keys, changed keys at regular intervals and gave away intelligence indicators when keys were changed.

The United States had initially chosen to remain neutral during World War One (1914-1918). However, when Germany broke its pledge not to engage in submarine warfare, the United States decided to break all diplomatic relations with Germany. British cryptographers broke the Zimmerman Telegram (1917), a secret German communication to Mexico in which the Germans offered Mexico United States territory in return for joining the German cause. When the American public realised this, their opinion changed in favour of joining the war with the allies. It is believed that no other single cryptanalysis has had such enormous consequences as the deciphering of the Zimmerman Telegram.

The ADFGVX system was put into service by the Germans near the end of World War One. This was a cipher which performed a substitution (through a keyed array), fractionation and then transposition of the letter fractions. It was broken by the French cryptanalyst, Lieutenant Georges Painvin.

In 1939, Japan had started using their PURPLE code, one of the most complex codes of World War II. However the Americans (under the direction of Chief Cryptanalyst William Friedman) had great success at breaking Japanese codes. (The US Navy, having broken Japans' ORANGE and RED codes in the 1920's, had experience in the formal language used by the Japanese in their communications.) While the Japanese, unable to break US codes, assumed that their codes were also unbreakable.

The cracking of the Enigma machine used by the Germans during World War II is believed to be one of the greatest achievements in the field of cryptanalysis. The Enigma was an electrical enciphering machine (and looked like a typing machine), which provided better encryption of messages t han other machines at the time because of the concept of rotating rotors. Originally built for commercial use, it was soon put to use by the Germans for securing their radio communications during the War. They believed the machine to be invincible as the likelihood of breaking a message enciphered by the Enigma was too remote a possibility to consider.

The initial work on cryptanalysing Enigma began during peacetime by the Polish Cipher Bureau. They had managed to acquire a commercial Enigma, and three young mathematicians led by Marian Rejewski began to work on it. By early 1933, they had figured out the complex ciphers using a combination of math, statistics, computational ability and guesswork.

When the Second World War began, the Poles, realizing that a German invasion was imminent, handed over all the information to the British. The British cipher department later came to be known as the famous Bletchley Park. It was here that the young English mathematician, Alan Turing, started work on the Enigma. Turing, collaborating with another British mathematician Gordon Welchman, further enhanced this machine which came to be known as the Turing Bombe. This Bombe was in effect a collection of Enigma machines and this played a key role in the cracking of the Enigma cipher. This was the first recorded instance of an electro-mechanical device being used in cryptanalysis.

Fish was used by the German army in WWII to encipher high-command communications. It was produced by a stream cipher called the Lorentz machine. Fish was the name given to it by British cryptanalysts. It was important because it caused difficulties for British analysts, who finally developed a machine called Colossus, which was arguably the first, or one of the first, digital computers. The Colossus machine may have been an important factor in the planning and success of the Allied attack on Normandy. Given the intelligence produced by cryptanalysis of Fish, Allied forces knew the positions of pretty much every German division.

Great minds in Cryptography

There are many notable personalities who participated in the evolution of Cryptography. The Greek philosopher and writer Polybius arranged the alphabet into a squared grid or matrix. By numbering the rows and columns, letters could be transformed into other paired characters. The Polybius square's features of splitting a character into two parts, reducing the number of characters needed and ability to convert letters into numbers is still used in modern algorithms.

Julius Caesar used his famous substitution cipher (the 'Caesar Cipher'), which shifted each letter four places further through the alphabet. The first European manual on cryptography (c. 1379) was a compilation of ciphers by Gabriele de Lavinde of Parma, who served Pope Clement VII. This manual, now in the Vatican archives, contains a set of keys for 24 correspondents and embraces symbols for letters, nulls, and several two-character code equivalents for words and names.

The Italian architect and writer Leon Battista Alberti is known as "The Father of Western Cryptology" in part because of his development of polyalphabetic substitution. Polyalphabetic substitution is any technique which allows different ciphertext symbols to represent the same plaintext symbol. This makes it more difficult to interpret ciphertext using frequency analysis. He did this by designing a cipher disk to simplify the process (c. 1466-7). This class of cipher was apparently not broken until the 1800's. The next major step was taken in 1518, by Trithemius, a German monk. He wrote Polygraphia, the first printed work on cryptology. He devised a table that repeated the alphabet with each row a duplicate of the one above it, shifted over one letter.

The resulting series of words would be a legitimate prayer. He also described polyalphabetic ciphers in the now-standard form of rectangular substitution tables. He introduced the notion of changing alphabets with each letter. In 1553, Giovan Batista Belaso came up with the idea of the password. He chose a keyword that is written above the plaintext, in a letter-to-letter correspondence. The keyword is restarted at the beginning of each new plaintext word. The letter of the keyword above the letter of the plaintext is the first letter of the cipher line to be used. In other words, if the plaintext letter is 'c', and it's keyword letter is 's', then the line of the Trithemius cipher beginning with 's' is used to encipher the letter 'c'.

Giovanni Battista Porta wrote in 1563 a text on ciphers, introducing the digraphic cipher. He said that the three types of ciphers were transposition, substitution, and symbol-substitution (use of a strange alphabet).

The most famous cryptographer of the 16th century was Blaise de Vigènere (1523-1596). In 1585, he wrote Tracte des Chiffres in which he used a Trithemius table, but changed the way the key system worked. One of his techniques used the plaintext, as it's own key. Another used the ciphertext. Sir Francis Bacon celebrated bilateral cipher (1623) was an arrangement of the letters «a» and «b» in five-letter combinations, each representing a letter of the alphabet. This code illustrates the important principle that a code employing only two different signs can be used to transmit information.

The 'wheel cipher' was invented by Thomas Jefferson around 1795, and although he never did very much with it, a very similar system was re-invented for use in World War II by the US Navy, which then called it the Strip Cipher. Jefferson's wheel cipher consisted of twenty-six cylindrical wooden pieces, each threaded onto an iron spindle. The letters of the alphabet were inscribed on the edge of each wheel in a random order. Turning these wheels, words could be scrambled and unscrambled.

In 1859, Pliny Earle Chase, developed what is known as the fractionating or tomographic cipher. A two-digit number was assigned to each character of plaintext by means of a table. These numbers were written so that the first numbers formed a row on top of the second numbers. The bottom row was multiplied by nine, and the corresponding pairs are put back in the table to form the ciphertext.

The British scientist Sir Charles Wheatstone (1802-1875) developed the Playfair Code, a table system that was easy to use. Although not difficult to analyse, it did muddle character frequency techniques by the use of digraphs (coding two letters at a time).

Friedrich W. Kasiski developed a cryptanalysis method in 1863 which broke almost every existing cipher of that time. The method was to find repetitions of strings of characters in the ciphertext. The distance between these repetitions is then used to find the length of the key. This technique makes cryptanalysis of polyalphabetic substitution ciphers quite straight forward.

In 1883, the French teacher and writer Auguste Kerckhoffs wrote 'La Cryptographie Militaire' in which he set forth six basic requirements of cryptography. He formulated procedures for long-term diplomatic codes as well as inventing the superpositioning technique for code breaking.

In 1917, the Americans formed the cryptographic organization MI-8, with Herbert Osborne Yardley as the director. They analyzed all types of secret messages, including codes, secret inks and encryptions. They continued with much success during and after WW1. Yardley wrote a best seller, The American Black Chamber, describing the workings of MI-8. Another American, William Frederick Friedman, worked with his wife, Elizebeth Smith, and they became an important husband-and-wife team in the history of cryptology.

In 1929, Lester S. Hill published an article Cryptography in an Algebraic Alphabet in which a block of plaintext is enciphered by a matrix operation. Hill's major contribution was the use of mathematics to design and analyze cryptosystems.

Arthur Scherbius, inventor of the Enigma Machine, tried to sell it commercially, but he had no success with that. It was eventually taken over and improved by the German government who used it to encrypt military communications in World War II. It was broken by the Polish mathematician, Marian Rejewski, based only on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Continued breaks were based on developments during the war by Alan Turing, Gordon Welchman and others at Bletchley Park in England (1933 - 1945). The British engineer Tommy Flowers built Colossus (the world's first programmable electronic computer) to also help Bletchley Park crack German codes.

The Japanese Purple machine was invented in response to revelations by Herbert O. Yardley and broken by a team headed by William Frederick Friedman. The Purple machine used telephone stepping relays instead of rotors and thus had a totally different permutation at each step rather than the related permutations of one rotor in different positions.

In 1948, Shannon published A Communications Theory of Secrecy Systems. Shannon was one of the first modern cryptographers to attribute advanced mathematical techniques to the science of ciphers. Although the use of frequency analysis for solving substitution ciphers was begun many years earlier, Shannon's analysis demonstrates several important features of the statistical nature of language that make the solution to nearly all previous ciphers very straight forward.

Dr. Horst Feistel led a research project at the IBM Watson Research Lab in the 1960's which developed the Lucifer cipher. In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography", introducing the idea of public key cryptography. They also put forth the idea of authentication by powers of a one-way function. Inspired by the Diffie-Hellman paper and acting as complete novices in cryptography, Ronald L. Rivest, Adi Shamir and Leonard M. Adleman had been discussing how to make a practical public key system. They invented the RSA computer-encryption algorithm. RSA is a public key algorithm based on the difficulty of factoring large numbers.

The algorithm was published in the September 1977 issue of Scientific American. Even today, it is used to keep text secret. Pretty Good Privacy (PGP) was released in 1991 by American Phil Zimmerman. To this day, it is considered a very secure way of communication across the Internet. PGP employs a public key system so that the sender cannot determine the key used to decrypt the message, even if he knows the key for encrypting the message. PGP is designed so that it can be integrated into email packages, thus allowing it to be used by the average citizen.