CIPHER MACHINES AND CRYPTOLOGY What is Cryptography

#### What is Cryptography

Cryptography (from the Greek Krypto 'hidden' and Grafo 'written') is the study and implementation of techniques to hide information, or to protect it from being read. The information that is protected can be written text, electronic signals such as Morse, Telex or speech, or all kinds of digital information like computer files, e-mail messages or data transmissions.

The unprocessed readable information is called plaintext or plain data. The process of making the information unreadable is called encryption or enciphering. The result of encryption is a ciphertext or cryptogram. Reversing this process and retrieving the original readable information is called decryption or deciphering. An algorithm or so-called cipher is used to encrypt or decrypt information, .

How a cryptographic algorithm works, is controlled by a secret key, sometimes called password or passphrase (on crypto machines, the key is the setting of the machine). The key is known only to those who are authorized to read the information. Without knowing the key, it should be impossible to reverse the encryption process, or the time required to reverse the process should take so much time that the information has become useless.

Cryptanalysis or crypto-analysis is the study and analysis of existing ciphers or encryption algorithms, in order to assess their quality, to find weaknesses or to find a way to reverse the encryption process without having the key. Decryption without a key (often also without authorization) is a cryptanalytic attack, referred to as breaking or cracking a cipher.

A cryptanalytic attack can exploit weaknesses in the algorithm or crypto device itself, exploit its implementation procedures, or try out all possible keys (a brute-force attack). In general, there are two types of attack: The ciphertext-only attack, where the cryptanalyst or attacker has access only to the ciphertext, and the known-plaintext attack, where the cryptanalyst has access to both ciphertext and its corresponding plaintext or assumed plaintext, to retrieve the corresponding key.

Cryptology comprises both cryptography (making) and cryptanalysis (breaking). The expressions 'code', 'encoding' and 'decoding' are frequently used in cryptography. A code, however, is a simple replacement of information with other information, and doesn't use an algorithm. Generally, these are code books or tables that convert one value (letters, words or phrases) into another value (letter sequence, numerical value or special symbols). Cryptography, on the other hand, uses an algorithm (often a combination of fractioning, transposition and substitution) to manipulate the information. Although technically wrong, the expression 'encoding' is often used to indicate encryption or enciphering and one should therefore look at the context in which such expressions are used.

#### A Brief History

Ever since mankind has existed, people have had secrets, and other people have wanted to know these secrets. The earliest forms of cryptography were performed by pencil and paper, and of course were available only to those who had access to proper education. These classical ciphers were mainly transposition ciphers, which rearrange the letters in a message, and substitution ciphers, which replaced letters, groups of letters or words with other letters, groups or words. One of the earliest reported substitution ciphers was the Caesar cipher or Caesar's shift, in which the letters of the alphabet were replaced by the letters of a second alphabet that was shifted a fixed number of positions again the normal alphabet. It was named after Julius Caesar who used it to communicate with his generals during his military campaigns.

Cryptography was used to secure secret communications from military leaders, diplomats, spies and religious groups. Unfortunately, most of the early ciphers revealed statistical information which could be used to break them. As early as the 9th century, Arab mathematicians discovered frequency analysis and developed methods to break ciphers. This started the race between codemakers and codebreakers. Frequency analysis proved to solve many of the known ciphers, and it was only with the invention of the poly-alphabetic cipher by Leon Battista Alberti in the 15th century that codemakers were one step ahead of the codebreakers again. Poly-alphabetic ciphers like Vigenère use different sets of alphabets during the encryption process. For ages, these ciphers were considered to be unbreakable until Charles Babage in the 19th century developed the multiple frequency analysis techniques.

Cryptography was extensively used by governments to protect their diplomatic post. In the 18th century, all major countries in Europe started recruiting cryptologists to either protect their communication, mostly letters through postal services, or break the encrypted messages of other countries. These bureaus became known as the Black Chambers. Some of the most notorious Black Chambers were the Austrain Geheime Kabinets-Kanzlei in Vienna, the French Cabinet Noir and later the British Room 40, notorious for their great skill in intercepting and decrypting all kinds of military and diplomatic post. Cryptography soon became an important weapon in politics and in the many wars in Europe. By the end of the 19th century important steps were made in the development of cryptography. Auguste Kerckhoffs was one of the most important men to change cryptography from a dark art into a science, based on mathematics. It was Kerckhoffs who stated the fundamental principle that encryption should not depend on the secrecy of the system - which sooner or later would be compromised - but should solely depend on the secrecy of the key.

Many new pencil-and-paper ciphers or hand ciphers were developed and used during the First World War. Among them were ADFGVX, Playfair and Double Transposition. All of them were based on transposition, substitution and fractioning of letters. One important invention was the one-time pad encryption for Telex traffic by Gilbert Vernam in 1917. He realized that when a Telex signal is mixed with a truly random key with the same length as the message, the message would be unbreakable. Pencil-and-paper versions of his invention soon followed. With the rise of wireless communication, the need for secure communications for both military as civilian use grew exponential. The impractical and time-consuming hand ciphers could not keep up with the growing demand and this lead to the development of cipher machines.

After the First World War, two types of machines dominated the market. The electromechanical rotor machines such as the German Enigma and Siemens & HalskeT-52, and the British Typex, and the fully mechanical pin-and lug machines like the Hagelin series. Although machines took over most of the work, pencil-and-paper based hand ciphers still remained in use for short-time tactical purposes, where the time to cryptanalyse them would render the tactical information useless. For example, the secure Double Transposition hand cipher was used until the end of the Second World War by both Allied an Axis forces. Some pencil-and-paper ciphers such as one-time pads were even used during the Cold War for clandestine operations by intelligence services.

All major countries realized the importance of intelligence gathering and new organizations saw the light. In Britain, Room 40 was reorganized into the Government Communications & Cipher School (GC&CS), which played a decisive role during the Second World War. Amongst their most famous cryptologist were Alan Turing, Alastair Denniston, Dilly Knox and John Tiltman. In the United States, the Signal Intelligence Service (SIS) and the Communications Security section of the Office of Naval communications (OP-20-G) were the most important code breaking organizations with legendary cryptologists such as William Friedman and Meredith Gardner.

The Second World War lead to improved cipher machines like the American SIGABA and SIGCUM, and the German Lorenz SZ-40 and Schlusselgeraet 41. To break the enormous amount of encrypted message traffic the codebreaker had to build new, automated machines, which lead directly to the development of the first digital computers. In Bletchley Park, Max Newton and Tommy Flowers developed the Colossus, a digital programmable computer to break the Lorenz SZ-40/42 messages. This was the first step in the evolution of cryptography towards the new computer age. However, new improved electro-mechanical cipher machines such as the KL-7, Fialka M-127 and Hagelin CX-52 were designed and remained in service until the 1980s, when the digitalization really broke through.

It was Claude Elwood Shannon who laid the foundations for modern cryptography in 1948 with his famous Information Theory. The development of electronics and digital computers after the Second World War made it possible to create encryption algorithms, far more complex than before. The new computer algorithms were no longer based on the simple substitution, transposition and fractioning of letters and words, but on a large number of complex operations on data bits. One of the first block ciphers - encryption performed on blocks of data bits - was the Lucifer cipher, designed by Feistel and Coppersmith for IBM, and based on what is known as a Feistel network. It was the predecessor of DES, the first ever cryptographic standard. However, the computer revolution did not only lead to better encryption systems, but also to faster and better codebreaking techniques. The race between codemakers and codebreakers continued as before. Absolute security was one of the reasons that one-time pad systems remained in use until the 1980s for Telex traffic and such, although the expensive and complex key distribution, a typical downside of one-time pad, made it only affordable to the military and diplomatic services.

The cryptologic community remained very closed and mainly controlled by government agencies until the 1970s. The public release of DES (Data Encryption Standard) and the RSA public-key algorithm were a turning point in the spreading of cryptography. Following Kerckhoffs principle, newly designed crypto algorithms were released into the public domain, to subject them to extensive academic research. The advantage was obvious. A very large open crypto community could assess new algorithms, discover weaknesses and propose improvements or disapprove the use of a weak algorithm. This lead to a 'survival of the fittest' situation, resulting in quality encryption standards.

The most widely used symmetric algorithms today are the Advanced Encryptions Standard (AES), International Data Encryption Algorithm (IDEA), Blowfish and Triple DES. Nevertheless, secret algorithms are still developed and used, mainly by government agencies. Another type of computer algorithms are stream ciphers. They were developed as an answer to the key distribution problem of long keys, as used in systems like one-time pad. Where a block cipher performs a cryptographic function on a fixed number of plain bits, the stream cipher produces a continuous stream of random values that is mixed with the plain bits. Some well known stream ciphers are RC4, SEAL and SOBER.

Another field of cryptography is message integrity and authentication. How can we be sure that the message that we receive is authentic and has not been tampered or modified? The solution is a Hash function, a special one-way function. Hash functions use a crypto algorithm, controlled by a secret key, to take an input and return a unique fixed-size string, which is called the hash value. This value is used to 'sign' the message. This unique value cannot be reproduced without the secret key. Therefore it is impossible to change the message content, since this would require the calculation of a new signature value, which is impossible without knowing the key. Meanwhile many different cryptographic hash functions are developed. MD5, SHA-2 and RIPEMD are some of the modern secure hash functions.

The most important development for modern cryptography was public-key cryptography. Until 1970, all encryption was based on symmetric-key algorithms. Both encryption and decryption are performed with the same key. Both sender and receiver of an encrypted message have to use the same key. The disadvantage of this system was a complex key distribution system with several security issues. The invention of the asymmetric-key algorithm by James Ellis was a revolution in the world of cryptography. With asymmetric-key cryptography, two keys are used. A public key for encryption only, and a secret private key for decryption. The public key cannot be used to decrypt the information. This solved the expensive and risky problem of secret key distribution.

From now on, you could make your public key available to everyone. Everyone can encrypt his message, destined to you, with your public key, but only you, with your private secret key, can decrypt the message. There is no longer a need to share a secret key! James Ellis' invention at the Government Communications Headquarters (GCHQ), the successor of the GC&CS, remained top secret. However, Whitfield Diffie and Martin Hellman proposed an asymmetric-key algorithm in 1976 and Ronald Rivest, Adi Shamir, and Len Adleman invented RSA, another public-key system in 1978. Because of their solution to the secret key distribution problem, the Diffie-Hellman and RSA algorithms are among the most widely used crypto algorithms in the world.

Public-key algorithms are based on the computational complexity problem. The Diffie-Hellman algorithm is based on the discrete logarithm problem and RSA is based on the problem of factorization of large primes. Asymmetric-key algorithms require large keys and heavy computation, which makes them suitable only for encryption of small amounts of data. Therefore, strong traditional symmetric algorithms are often used to encrypt the actual information and the asymmetric-key algorithm is then used to encrypt the secret key for the symmetric algorithm. One of the most popular implementations of this principle is Philip Zimmermann's PGP, which is a combination of powerful symmetric block ciphers, the practical public-key asymmetric cryptography and the message integrity of digital signatures by hash functions.