Cryptography is the science of encoding a message into a form that is unreadable and making sure only the proper people are capable of decoding the message back into its original form.
This is usually done by using an encryption algorithm and a decryption algorithm (these two are often the same) and very often a secret key. Some of the early cryptographic systems did not use a key but instead kept the algorithm itself secret. The message sender uses the encryption algorithm and the key to encode the message, and then sends it to the receiver. The receiver then uses the decryption algorithm and the key to turn back the encrypted message into its original form and read it.
If the message is intercepted on the way by a third party, they will only have unreadable data and will have gained nothing, unless they can figure out the decryption algorithm and obtain the key. This is why the key is never to be sent with the message, and has to be kept secret at all cost. If the key is compromised, the sender and the encrypted data is no longer safe. The sender and the receiver then usually agree on a new key to prevent any further damage.
In ancient Greece, around 550 Bc, messages were sent encoded to generals and could only be decoded using special staff keys. The key actually consisted of a physical object, which was applied on the message to get the decrypted version of it. In 50 Bc. , one of the most simple cryptographic algorithms ever used was the one called the Caesar cipher, that was used by Julius Caesar to send messages to his generals. It consisted simply of switching each letter with the letter that was 3 letters further down the alphabet.
For example “Stephen” would become “Vwhskhq”. To decrypt the message, the receivers would simply subtract 3 letters from each letter. This algorithm was later improved and called ROT13, where the letters could be shifted to any number between 1 and 25, and the number of letters shifted was the secret key. This very simple algorithm has been used on Usenet successfully to prevent people from inadvertently reading materials they might find offensive. Monoalphabetic substitution is another simple step away from the ROT13 algorithm. In this algorithm, each letter correspond to another letter but in no particular order.
For example a = d, d = x, f = e, etc for all 26 letters. This made it much harder to break but also made fairly big keys that couldn’t be memorized, since they consisted of 26 pairs of letters. In France during 1585, members of the king’s court liked to send romantic or gossip messages to each other and encrypt them for safety, which becomes almost a necessity. Blaise de Vigenere came up with a poly-alphabetic substitution known as the Vigenere cipher. Basically, the algorithm would encrypt messages several letters at a time instead of letter by letter.
For example ab = fh, th = sq. To simplify the huge keys it would require, the key was broken into a table and a key, the table was fairly big but the key was small enough to be memorized, and the table was useless without the key. This cipher wasn’t totally safe but no totally sure method to break it was developed before early in the 20th century. During World War I, American troops used native Indians to send messages over the radio, which could only be understood by other native Indians, and absolutely nobody in Germany could understand it.
Also in World War I (most cryptographic algorithms are developed for wars), the Playfair algorithm is developed by the Allies, the key, like in the Vigenere cipher, is based on a little table and a short keyword, which were both changed periodically. The rules used with the table were much more complex and made it fairly safe. In World War II, however, the Germans gave up on abstract algorithms and came up with a physical encrypting/decrypting machine called the Enigma. It had different wheels of different sizes which were to be tuned differently depending on the date, the different turnings were listed in a little booklet that came with the machine. It wasn’t broken before the Allies finally managed to capture enough pieces of the machine and collect enough data from operating errors by the Germans. Whitfield Diffie and Martin Helbman (1976) come up with the notion of Public Key Cryptography.
In 1977, RSA (Ronald L. Rivest, Adi Shamir and Leonard M. Adleman) develops a Public Key algorithm based on large prime numbers that is theoretically impossible to break in a reasonable amount of time. Digital signatures were also made possible. 1991, PGP (Pretty Good Privacy) reuses an algorithm very similar to RSA’s and gets posted on the web. Phil Zimmerman gets sued for both exporting cryptographic data and violating copyright laws.
A new version of PGP is quickly developed which is different enough from RSA’s to be marketed. Because of its broadcasting on the web and the fact that it is freeware, PGP becomes one of the most widespread crypto systems. Now, we will quickly go over the concepts of public key cryptography and the global idea of how the RSA algorithm works (or PGP, they are almost the same), as well as digital signatures and “digicash”. I will also explain the general methods used to break most ciphers. I cannot however explain in detail because I cannot broadcast that kind of information without breaking the law which I will explain later.
Public Key Cryptography The main problem with most cryptographic algorithms is that they are vulnerable to having the key exposed, and the key has to be agreed on by the sender and the receiver ahead of time. This means that when the sender and receiver exchange keys the first time, there is an opportunity for a third party to capture the key (or whenever keys are changed, in many cases keys were changed periodically for additional safety). This is exactly what public key cryptography avoids. The receiver of the message sends his public key to the sender. It is a public key, so it doesn’t matter if the whole world knows the key or not. The key can only be used to encrypt data, not decrypt it.
Then the sender will encrypt the message with the public key and send it to the receiver. Once the receiver received the data, he takes his private key and uses it to decipher the data. Note that the private key was never transmitted by the receiver to anyone, so it is almost invulnerable to exposure. Also note that the public and private keys work in pairs.
There is only one private key associated with each public key and vice versa, and ideally it is impossible to find one key from the other one. If someone intercepts the message he gets only an unreadable encrypted version of it, and using the public key or any other incorrect key used with the decryption algorithm will simply generate another series of numbers. If the receiver wants to reply to the sender, the sender has to have his own set of private and public key as well, and then the whole story goes on again the other way around. Ideally, there is even a phonebook of all public keys so that anybody could send an encrypted message safely to anybody else by simply looking up that person’s public key.
The RSA Algorithm The RSA algorithm is based on large prime numbers. One very interesting property of large prime numbers is that it is very hard to find out wether a very large number is a prime, and if it is not, finding out what numbers it is a product of can be very hard too. So if we take two (very) large primes and multiply them together, we get a number that is almost prime, and it will be very hard to find what two numbers were originally multiplied to obtain it. These numbers are used as the public and private keys, since it is very hard to find them. Theoretically, if the keys are chosen large enough, breaking the RSA algorithm would take several hundred years using all the biggest computers on the planet put together.
RSA has offered a large amount of money to whoever comes up with a reliable and fast algorithm that can break their code. They still have all their money. Digital Signatures There remains one problem with passing all these messages: messages can be passed from sender to receiver safely, but the receiver has no means of determining who the message was actually from. For example, Bob could take Joe’s public key and send the following message to Joe: “You’re a wuss. signed: Jack”.
Now, when Joe receives this message, he has absolutely no way of telling that Bob sent the message, and not Jack. This is where digital signatures come in handy. They allow a person to sign a message in a way that certifies that the message was actually sent by them. This is done by using one other interesting property of the private and public keys in RSA: they can be reversed in the algorithm and it will still work.
For example, if you encode something using the private key, it can be decoded with and only with the public key. So when Jack sends something to Bob, he takes “signed Jack” and encrypts it with his private key (note that this in no way reveals what his private key is) and adds that at the end of his message as a signature. When Bob receives the message from Jack and decrypts it, he will obtain a small encrypted piece of data at the end of the message, which is the encrypted signature Jack put there. Bob can decrypt it with Jack’s public key, and if a real message comes out of it, (i. e: not a series of apparently random numbers) then he knows that Jack was indeed the person that sent him the message. Usually, people add the exact time and date inside their signature to make sure each signature can be used only once.
That is, once Bob has Jack’s signature at the end of the message, he can’t send a message to Tom that says: “You’re a BIG wuss, signed Jack” and then paste the signature he just got from Jack at the end, because Tom will be able to see that there is a time difference in the signature’s data and will therefore know that the message isn’t really coming from Jack. Digital Money Digital Money is a form of money that can be used online (or anywhere else for what that matters), with both safety and anonymity. Most digital money systems out there are closer to prototypes than actual widely used systems. Different digital money schemes probably exist, but this one works and is simple and safe.
It is a simple application of digital signatures. The costumer sends a digital signature to whoever he wants to send money to by encrypting the data using his private key. (See the section above for details on digital signatures). In the signature, he/she includes the amount, the time, who the money goes to, a transaction number and whatever data is convenient to include.
Very much like a check, really. When the person being paid receives the data, he/she can check it by decrypting it with the payer’s public key. He/she cannot modify it since it is encrypted, he/she cannot duplicate it since there is a transaction number, and finally the payment cannot be intercepted by a third party because it contains the public key of who the money goes to, which means it will be worthless to anyone else. To guarantee confidentiality the digital signature is encrypted again before being sent with the receiver’s public key so that no third party can even find out who is being paid how much for what. There are even a little more complicated schemes that will allow total confidentiality. That is, even the person receiving the money will not know who is paying him because the transaction is handled directly through the “digicash” servers instead of between the buyer and the seller, although usually he will have to know in order to send the purchased product or information to his customer.
Once the receiver has received the payment and checked it, he/she forwards the digital signature (encrypted with the “digicash” servers public key to guarantee confidentiality) to the “digicash” server, which checks it and transfers the corresponding amount between the two “digicash” accounts. The payment has been successfully made without ever revealing anyone’s private key or identity. Breaking Encoded Data Breaking encoded data is not easy, especially when dealing with complex encryption schemes. Here are some of the ways that are used to do it: 1. Stealing the key! (and don’t let them know you have it). This is the simplest and most radical way of breaking into someone’s secret transmissions.
2. Guessing the key. Some people do tend to use their dog’s name as a key and things like that, but this method is still much more efficient in movies than in real life. Usually this is more widely used by having the brute force methods test for common words first and then uncommon words. 3. Figuring out what algorithm is used.
Knowing this will help a lot to break the cipher. 4. Brute force. This method is basically to try out all the possible keys until a correct result appears. It can be time consuming but even a slow computer can break all of the simpler ciphers instantly.
There are smarter versions of this which search first through more likely values, or manage to cut out large chunks of the search space by elimination before actually trying everything. 5. Letter frequency analysis. Some letters appear more often than others in a normal text conversation.
(“e” is the most frequent). So knowing this, if the cipher is a mono-alphabetic substitution, the letters can be found by matching their frequencies. For poly-alphabetic substitution, there are also letter frequency charts for short multiple letter strings. Look for human errors in the encoded transmissions. Often over a long series of messages, the user will make a mistake at least once, and the messed up data usually says a lot about what the key might be (especially people who tend to forget to encrypt a message when sending it, and then correct their error by encrypting it and sending it again, this gives the listening third party an encrypted and a decrypted version of the same text, which is usually very useful for finding the key. ) Note that RSA is very resistant to all of these methods since the keys are always safe and brute force will take several hundred years to work.
The only human error that could actually endanger the cipher would be to broadcast the private key by mistake. Being able to encrypt our messages so that no one else can read them is great, but is this something we really need? Most of us do not need to have our transmissions encrypted, for the very simple reason that simply nobody is interested in intercepting and reading our electronic mail. Privacy of this type would be nice, but it definitely would not be worth going through the trouble of setting up everything that needs to be set up unless you have an important secret to keep. However if it came all set up with most operating systems then it would be convenient enough to use on a regular basis.
Remember that because of the way the Internet is built, anyone connected to the Ethernet cable can read every single transmission made on the net. That’s not exactly private. But there are people out there that need to keep important secrets and aren’t terrorists or criminals or the army. Most businesses will not be able to use the Internet as a means of communication as long as all their online communications are vulnerable to industrial spying.
For businesses, the only safe way to communicate through a medium where each single bit they send can be listened to is to encrypt all of their communications with a cipher strong enough to resist breaking attempts from the other businesses. Another use of cryptography applied to business is the one used by the french television channel Canal+, which is broadcasted, but only the customers paying every month for the new keycode that corresponds to their decoder box will be able to decode the broadcasted programs. Without the use of encryption, the whole scheme of having a premium channel broadcasted through airwaves would be totally impossible. Finally, one of the most useful uses of cryptography that we might all find use for is “Digicash”. Without cryptography it is very close to impossible to implement a successful and convenient scheme for online money. And online money is something most online businesses and shoppers would love to have.
Cryptography has its origins in wars and is therefore considered very much like a weapon because of the advantage it can give to one side or the other. Legally, any information about any kind of strong encryption is considered “munitions” (remember Michael Grubb’s T shirt?). What this means is basically that it is illegal to export it to another country in any way. The FBI takes this matter extremely seriously.
There are more or less equivalent laws in most other countries in the world as well. Illegal immigrants in France tattooed cryptographic data on their forearms so that it would be illegal to send them back to their country. Since the Internet is worldwide, posting any strong encryption information on the web is the same as exporting it, and is therefore illegal. Which means that right now encrypted Internet communications are more or less illegal as well. Also, the government is now trying to impose the Clipper chip as a standard on all computers, and banning all other forms of cryptography, in order to have a unique crypto system which it has the ability to break.
The problem is, is that it is already too late to prevent these crypto systems from being exported. Most foreign countries already have knowledge of them, and there are many foreign business companies which use strong cryptography (including the RSA algorithm). So prohibiting exportation of these materials is purely and simply useless. Furthermore, prohibiting US companies from being able to export strong cryptography results in loss of marketing opportunities for them.
It also means that they won’t be able to conduct safe, private conversations when dealing with foreign companies because they cannot use encrypted communications.
