Subject: Cryptography: history, methods, NSA, government, Echelon (government sattelite system).
Target: N/A
Author: BlackB
Source: EOS - December 2000.
Date: 2000-11-18
Tools used: N/A
Difficulty (scale 1-5): N/A
Published by +Tsehp November 2000

Hi!
This esssay will be a result of what I've read in an article in the scientific magazine "EOS". Subject: cryptography, how it works, how it gets broken and the role we and the governments play in it. If you're in cryptography, or interested how our privacy is threatened: this essay is for you!

A. Introduction.

Secret codes have been the exclusive property of spies and secret services for centuries. But now, since the comming of the Internet, the art of secret coding has become a true industry. Cryptographical techniques are used in the most different applications, going from identification codes for mobile phones to the protection of electronical money and the e-commerce.
What was an art has become a science based on advanced mathematical techniques.

B. Text becomes maths.

The automation of the cryptography started in the early twenties. The first automated decoder, named Colossus, has been used to decode the Lorentz-code of the Nazi's. After WW I, also the cryptographist started to use an automated computer to encode his messages, because it was faster and more flexible then any other electromechanical encoding machine. By addition, the digital computer didn't work with letters, but with binary numbers. Texts were converted to 'ones' and 'zeros' and got into the world of maths.

Converting text into binary numbers, can be done with several protocols. One of them is ASCII (American Standard Code for Information Interchange). This standard is used and known by almost everyone who works with computers nowadays.
When the text is converted, the encryption can start. Two techniques: transposition and substitution can be used and combined here. Transposition leaves the signs, but changes the signs' order.

Substitution changes the signs with other signs.

There also has to be a difference between the encryption algo and the key, that gives more precise details about the scheme.

Of all existing code systems, only the Vernam-code or 'one time pad' is absolutely uncrackable: in this code system, the key must be as long as the original text and must consist of a row random numbers. In addition, the key can be only used once.
Uncrackable means that there is no fixed algorithm to break to code. A man could occasionally find a key and break the code, but that's no algorithm, it's just coïncidence. For people not convinced that the Vernam-code can't be cracked: it is mathematically proven that you can't develop an algo to break the code.
However, the use of the system is so long-winded and so unpractical, that it's almost never applied.

C. Belgian code becomes new American standard.

A code that can be cracked theoretically, can be uncrackable in practice. Many encryption techniques are so complex, that it would take too much time and too much money to effectively crack it. If an encryption is difficult to crack depends of many factors:

- The length of the key: 4 decimal numbers deliver only 10.000 possibilities (10^4), that can be easily cracked with a computer by checking all possibilities. Long keys with letters AND numbers, deliver an astronomical big amount of keys, that way it would be almost impossible to crack it. Let us take our previous example of 4 places, but now you can choose between the 10 numbers (0123456789) and the 26 letters of the alphabet, lowercase. That would give (10+26)^4 possibilities or 1.679.616 different keys.
- Apart from the length of the key, the method of how the original text is manipulated, rotated, scrambled, etc... is very important. The original text must be transformed in such a way, that it's almost impossible for a cryptanalyst to reconstruct it. The cryptanalyst of today can rely on computers and mathematical - including statistical - techniques. Even if he should have the original text and its encrypted equivalent, a cryptanalyst should not be able to find the encryption method.
Even more feared is that the cryptanalyst would have access to the encryption computer, so he could encode texts of his choice. A coding system that encrypts 'alike' texts in 'alike' ciphertexts are easily to break. So every form of repetition or regularity needs to be avoided. The perfect encoding system, delivers a totally different encrypted text if even the slightest change in the original text has been made. Or mathematically: every bit of the encoded text is a complex non-lineair function of all bits in the original text.

After WW II, computers became more powerful, faster and cheaper. In the 60's, many companies started to use encryption. There was only one problem: there was no standard, everybody used another encoding system. In 1977, the American government decided to use an adapted version of the IBM Lucifer-encoding system. The NSA adapted the program by limiting the length of the key to 56 bits. The NSA believed that 56 bit encryption was safe enough for civil use. The NSA itself had the biggest computer processing power and was able to break the 56 bit encryption.

The new standard was called DES (Data Encryption Standard), and is still the encoding standard of America. However, nowadays computers can easily crack a 56 bit DES encryption. Last year, an encode message got decrypted by supercomputer Deep Crack and Distributed.Net, a network of 100.000 on the internet connected computers. It took only 22h and 15 minutes. The two systems together tested 245 billion keys every second!

DES' successor is finally finished and acknowledged: AES (Advanced Encryption Standard). It's developed two belgian experts: Vincent Rijmen and Joan Daemen. They call it the Flemish 'Rijndael'-system. (Flanders is a province in Belgium, where I live). This new system is very safe, performant and efficient. A simple comparison with the DES system: if we would have a machine that could crack a 56-bits DES key in one second, then that machine would need about 149.000.000.000.000 years to crack a Rijndael-key of 128 bits.

D. More privacy with public keys.

With the introduction of DES in the seventies, the problem of standarisation was solved, but there was still another problem: key distribution. This could not be done by telephone or by letter, because this could be intercepted. Therefore, people started to use couriers to exchange the keys. As this system was too long-winded, Diffie and Hellman developed a system based on modular maths.

Now you know how modular math works, it's time to explain the Diffie-Hellman protocol of distributing keys with help of an example:

Two persons, Alice and Bob, want to send eachother an encrypted message. The one-way function is: Y^x (mod P). Where Y and P are two public numbers that count for both persons. These numbers can be seen by others. In our example, Y=7 and P=11. These numbers have to apply to certain rules which I will not discuss here.

Then Alice chooses a secret private number x for himself. The same does Bob. This number x must be kept secret, otherwise the message can be decoded.
In our case:
Alice -> x = 3
Bob -> x = 6
Y = 7 and P = 11

Alice calculates with her private number 3 the one-way function: 7^3(mod 11) = 2 = A
Bob calculates with his private number 6 the one-way function: 7^6(mod 11) = 4 = A

Alice sends the result (2) to Bob, and Bob sends his result (4) to Alice.
Alice and Bob now calculate A^x(mod P):

Alice: 4^3(mod 11) = 64 (mod 11) = 9
Bob: 2^6(mod 11) = 64 (mod 11) = 9

9 is the keynumber that Alice and Bob can use for coding and decoding. A cryptanalist can't calculate this number because he hasn't got both secret numbers. The secret number x can also not be calculated of the result A, because A is a result of a one-way function.

The fact that both numbers are equal, in spite of the different calculations, can be easily explained with the mingling of colors. Imagine that Alice and Bob both use the color 'yellow'. They add each a secret other color to the yellow. Alice takes 'red' as secret color, and Bob 'purple'. When the colors are mingled, they give the mixture to eachother and add their secret color to the mixture. Result:
Alice = Yellow (basecolor) + Red (secret color)
Bob = Yellow (basecolor) + Purple (secret color)
Switch(Alice, Bob)
Alice= Yellow (base) + Purple (secret color of Bob) + Red (own secret color)
Bob= Yellow(base) + Red (secret color of Alice) + Purple (own secret color).
As you can see, the final mixture has the same color, as well for Bob as for Alice and it can be done without knowing eachothers secret color.

This system, of sending eachother numbers, is pretty long-winded for intensive commercial use. Therefore, Diffie and Hellman had the idea (only the idea) of a two key system: a private and public key. The public key is used to encrypt, the private key to decrypt. This system is know as asymmetric keycryptography.

E. The 'Pretty Good Privacy' of Zimmerman

An actual method for asymmetric keycryptography has been developed in 1977 by Ron Rivest, Adi Shamier and Leonard Adleman, respectively two computerscientists and a mathematician. They also developed the RSA - system (Rivest Shamier Adlemen), which works this way: we have two private prime numbers p and q. Multiplicated, they form the public number N. This number N can be used to encode messages. p and q are used by the receiver to decrypt. Only he can decrypt his message, because there's no mathematical method to dissolve N in his prime factors p and q. When p and q are very large, even a supercomputer can't find p and q giving N=p*q.

Philip Zimmerman, computer scientist and political activist, had the opinion that everyone should be able to use the robust RSA encryption. So he made his own RSA-related encryption method and distributed it on a Usenet-bulletinboard, so everyone could download it for free.
While Zimmerman 's fanclub was growing, he got problems with several American intitutions, among which: RSA Data Security Inc that accused Zimmerman of patent violation and the American government that accused him of exporting 'warmaterial'. He became victim of a many years long lasting FBI investigation, but went free in 1996.

The PGP program provoked a big discussion about the positive and negative effects of encryption. A debate that's still going on.... . People are argumenting that they need privacy, government is argumenting that encryption can be used by criminals, giving them a powerful weapon.

F. Echelon, the 'all-seeing' eye

Because governments worldwide saw the consequences encryption could have when criminals would start using it, they limited the strength of encryption, and forbid the export of encryption to other countries. America, England, Canada, Austria and New-Sealand developed a hypersophisticated network of sattelites that are able to intercept every form of electronical communication: phones, mobile phones, fax and e-mail. The system can't pick messages of specific persons, but can intercept masses of messages and conversations. Supercomputers then analyze the content of the intercepted info on keywords like "bomb, Bin Laden, etc...", adresses, names, telephone numbers, etc... . Only relevant messages get selected and analysed.

Initially, Echelon was used during the cold war to intercept "hostile" messages from Russia. But later on, after the cold war, Echelon was used for other purposes as there are: economical, scientific and political spying. For fysist and journalist Duncan Campbell, Echelon commits systematically infringement on the privacy of governments, companies and individuals.

Because many people, but in particular: companies, are afraid of government abuse, they are advocates of strong encryption. Governments are afraid that strong encryption will be used for criminal purposes and are adverseries of strong encryption for the regular people.
As a result of many debates about encryption, both parties agreed to use an symmetric encryption system named SSL (Secure Sockets Layer)Handshake protocol. The essence of this encryption system, is that the identity of two companies A and B get verified (to avoid criminals using it) before the encryption can be used.

However, it's the question if this measure (and many others) are really effective? Criminals could easily develop their own encryption systems. Hence the quote of computerexpert and journalist Neil Cukier:
'The people involved in the encryption debate are all intelligent, decent and pro SSL, but they _never_ own more then two of these characteristics at the same time.'