Introduction
Julius Caesar did not use cryptography for nothing. He was untrusting of his messenger, yet he needed to send a highly confidential military instructions to his generals. He was equally afraid of the fact that the message might fall into his opponents’ hands and be used against him.
The famously known Caesar Cipher was only one of his methods. This method was very simple and very fast, at least during the time when automation by machines was not available. The cipher implemented an alphabet shift by 3, so that ”‘A”’ was translated to ”‘D”’, ”‘B”’ translated to ”‘E”’ and so on. This was an example of monoalphabetic substitution cipher.
In one occasion, he sent a very critical message to Cicero, who was under siege by replacing Roman letters with Greeks. This was another form of monoalphabetic substitution cipher. This particular action was actually the first documented use of cryptography for military purposes.
Fundamentals of Cryptography
The word cryptography originated from two Greek words, kryptos which means secret and graphos which means writing, hence it literally means secret writing. In particular, cryptography may be thought of as the science of secret writing, aiming at protecting data so that only the intended recipients may decrypt and read the message. A cryptography system or crypto-system is composed of two complementing functions, encryption and decryption.
Encryption operates on plaintext to transform it into unintelligible form based on input key. Decryption instead operates on ciphertext to recover the original message using the decryption key. Encryption and decryption keys are the same for symmetric crypto-system and different for asymmetric crypto-system.
Cryptanalysis instead is the study of defeating cryptography in the abscence of the key. This is possible, mainly with weak ciphers which fail to hide the characteristic of the message, be it the distribution of letters, the repetition or anything. Cryptography and cryptanalysis are two different scientific studies in direct competition with each other, the first attempts to hide a secret and the latter attempts to uncover it.
Shannon’s Theory of Confusion and Diffusion
Claude E. Shannon in 1949 produced a paper titled Communication Theory of Secrecy System which explained two components of encryption to thwart frequency analysis, namely ”‘confusion”’ and ”‘diffusion”’. Confusion is used to hide the relationship between the plaintext and the ciphertext and may be achieved by using complex substitution method. Whereas diffusion aims at spreading the statistics over the message to avoid exploits by cryptanalysts on any present redundancy. This is normally achieved with repeated permutations.
Kerchoff’s Principle
In 1883, a Dutch linguist Auguste Kerchoff von Nieuwenhof stated in his book La Cryptographie Militaire that the security of a crypto-system must be totally dependent on the secrecy of the key, not the secrecy of the algorithm. This is known as Kerchoff principle and is still relevant even in the current modern era.
Shouldn’t a cryptosystem be more secure if the related algorithms be kept secret? Not so. By keeping the algorithms secret, the benefit of having reviews from worldwide experts, both professionals and academicians is not available. Reviews are extremely important to detect any flaws in the design of the cryptosystem. This is not so different from open source software methodology, exposing the source code to the public to allow contribution of criticism and constructive ideas.
Moreover, it is also very difficult to keep the inner working of a crypto-system secret. With the crypto-system products being marketed to many parties, it is unreasonable to assume that the underlying algorithms can not be discovered by reverse-engineering. Besides there is also possibility that such secret might be revealed by irresponsible individuals who had been involved in the development.
Considering all these risks, it is safer to abide by Kerchoff’s principle and release the crypto-system algorithms to the public for reviews. However, certain organizations, National Security Agency (NSA) notably prefer to keep their algorithms secret by arguing that ”‘if less people know about the crypto-systems, less people know how to attack”’. However it must be observed that these organizations normally are very big and can afford to hire the best experts in crytography to do private reviews.
Periods of Cryptography
Academicians have segmented cryptography history and development into 3 significant periods :
- Ancient ( until 1918 )
- Technical ( 1919-1975 )
- Paradoxical ( from 1976 )
Ancient Period
The use of cryptography has been traced back to the ancient civilisations. In 3500 B.C. , the Sumeians developed cuneiform writing whereas the Egyptian developed hieroglyphic writing. The Egyptians in particular is known to have used cryptography on the tombs of deceased kings and rulers. However it was not used to hide any secrets, but rather to tell the story of the deceased in all elegance and regality.
Hebrew scholars were noted to have used Atbash cipher around 600 B.C. Atbash cipher is a very simple monoalphabetic substitution cipher, performed by reversing the alphabet. An Atbash system applied to Roman alphabet would be :

The first military cryptographic device was scytale, used by the Spartan in 500 B.C. to implement transposition cipher. To send an encrypted message, the sender would wrap a strip of leather or parchment around the scytale and write the message as normal. When the leather or parchment was then unwound, the letters of the message were automatically shuffled, rendering the message in a new unintelligible form. To recover the message, the intended recepient would simply take the leather and wrap it around his scytale.
Monoalphabetic Substitution Cipher
Monoalphabetic substitution cipher relies on one-to-one or one-to-many relationship between the plaintext and the ciphertext. For example, with Atbash cipher we have ”‘A”’ replaced by ”‘Z”’ , ”‘B”’ replaced by ”‘Y”’ and so on, which are based on one-to-one function. The similar applied to with Caesar Cipher, where ”‘A”’ is substituted with ”‘D”’, ”‘B”’ with ”‘E”’ and so on.
The scheme can be made more resistant to attacks and analyses by replacing each plaintext alphabet with one or more ciphertext alphabet. For example, ”‘A”’ may be replaced by ”‘T”’ or ”‘X”’, ”‘B”’ replaced by ”‘J”’ or ”‘4”’ etc. This has the advantage of hiding any statistical pattern which very often present in normal messages.
Frequency Analysis
During the Islamic golden age in the 9th century, an Arab polymath Abu Yusuf Ya’qub al-Kindi discovered a technique to defeat monoalphabetic substitution cipher. The technique exploits the intrinsic properties of written languages that certain letters occur more often than the others. The statistical distribution of letters in the ciphertext can be related to average distribution of letters in the particular language to find the underlying mapping function or functions.
The following table shows the average distribution of letters in English text.

Polyalphabetic Substitution Cipher
Cryptanalysis since then built on frequency analysis to form better attacks on monoalphabetic substitution cipher and its variants. The variants included introducing null or dummy values in between the letters, using keyphrases etc. However many of these variants were still unable to prevent cryptanalysis and subsequently lead to the exposure of the secrets. One tragic example was the thwart of Babington Plot, where Sir Francis Walsingham broke the correspondence cipher between Anthony Babington and Mary Queen of Scots and proved their plan to kill Queen Elizabeth. This resulted in the death execution of Mary Queen of Scots and other conspirators.
The need for cipher stronger than monoalphabetic substitution cipher was apparent. The new cipher would have to be resistant to frequency analysis, the ultimate cryptanalysis attack at the time.
Near the end of 16th century, a retired French diplomat Blaise de Vigenere built on previous work by Alberti, Trithemius and Porta to introduced Vigenere cipher, which was a form of polyalphabetic substitution cipher. Unlike monoalphabetic substitution cipher, ”‘A”’ in the plaintext may be translated to ”‘J”’ in one occasion and ”‘T”’ in another. And ”‘B”’ also may be translated to ”‘J”’ and ”‘R”’. Notice that a letter ”‘J”’ in the ciphertext may actually represent ”‘A”’ or ”‘B”’. This criteria renders frequency analysis a lot less effective.
Kasiski’s Method
Friedrich Wilhelm Kasiski discovered a method to break Vigenere Cipher. He noticed that there are repetitions in Vigenere ciphertext, caused by same words being encrypted with the same part of the key.
By analysing the place of repeated occurences, Kasiski managed to guess the length of the key used for Vigenere Cipher. The length of the key is a critical information for this cipher, as the ciphertext can then be grouped into many different groups, with the number of groups equal to the length of the key used. From there, frequency analysis can be conducted on individual group as usual.
This so called Kasiski Method is extremely powerful cryptanalysis technique against Vigenere Cipher. Following this discovery, cryptographers were forced to search for stronger cryptography method, however without much success for many years to come.
Technical Period
During World War I, mechanical machines are used to perform encryption and this marked the beginning of technical period in cryptography. At this time, radio transmission for communication was already used in warfare, following its discovery by an Italian physicist by name Guglielmo Marconi in 1894. Encrypted messages transmitted over the air can be intercepted very easily, which means a strong cipher was of paramount importance. Mechanical machine for encryption was invented as Vigenere cipher had already been rendered useless by Kasiski.
Enigma Machine
Without doubt, the Enigma machine was the most famous cryptography device during the Technical Period of cryptography. It was used by the German military and was created by a German inventor, Arthur Scherbius. The basic design had three elements connected by wires: a keyboard for inputting the plaintext message, a scrambler unit that encrypts a plaintext letter into a ciphertext letter and a display board consisting of various lamps for indicating the ciphertext letter.
Scherbius designed it such that the scrambler revolved one-sixth of a revolution such that the same plaintext letter would encrypt differently that the previous. For example, plaintext ’A’ would be encrypted to ’K’, and typing ’A’ again might encrypt it to ’C’ this time and so on. However, after the sixth rotation, the scrambler would have made one complete revolution, hence ’A’ would be encrypted to ’K’ again. This is the one of the main weaknesses in Scherbius
original design, since repetition is taboo in cryptography.
With one scrambler, there were 6 different settings. Cascading another scrambler, a total of 36 distinct scramble settings were obtained. For the Enigma machine, a third scrambler were added, making the number of different scrambler settings to be 216. For full alphabet, this meant there were 26 x 26 x 26 = 17576 distinct scrambler arrangements.
However, 17576 was a small number, a team of fifteen people could try all different arrangements in a day. Realising this, Scherbius further added a new feature by allowing any different arrangement of the three scramblers, increasing the number of distict arrangment by a factor of 6. He then added a plugboard between the keyboard and the first scrambler which have the effect of swapping some of the letters before they enter the scrambler.
With all these features, Enigma had a massive 10,000,000,000,000,000 number of different states or arrangements. Brute-force attack a message by trying all possible Enigma configurations was simply impossible.
The Enigma machine was accepted by German military and many Enigma machines were built and distributed. Codebooks were published regularly and distributed to all Enigma operators to sychronise the choice of Enigma configuration for any particular day. It goes without saying the codeboooks must be kept secret by the German military.
In the years to follow, German communication was unbreakable. This caused worry to Allied forces, hence they began to gather the best cryptanalysts to find a way to break the Enigma cryptography. A young man from Poland, Marian Rejewski was among them, and he was credited as the person who cracked Enigma.
Rejewski had successfully separated the problem of finding the scrambler setting from the problem of finding the plugboard setting. Individually these problems can be solved within reasonable time. Rejewski took advantage of German communication requirement that the message key must be encrypted twice at the beginning of every message. The repetition led to pattern and patterns can be exploited to find the message key. Since this discovery, German communication became transparent.
Data Encryption Standard
Following the invention of computer and digital devices, more and more operations were being handled electronically. Data were kept in computers in digital form. Data packets were also roaming via network cables and were susceptible to intercept by anyone. Cryptography was needed not by military and government alone anymore, but also by any institutions or organizations that used computers for managing data.
Due to various nature of computer application and files, two types of symmetric key cryptography were designed, namely stream cipher and block cipher. The difference is in the size of input; stream cipher operates on bit-by-bit or byte-by-byte whereas block cipher operates block-by-block. A block size is typically 64-bit, as used in DES, 3-DES and RC2.
By early 1970’s, the need for a cryptography standard was apparent. Businesses and organizations who did not have expertise in cryptography were being sold different cryptography devices which failed to interoperate. There was no assurance of these cryptography products as there was no independent body to do certification.
In 1973, National Bureau of Standards (NBS), now the National Institute of Standards and Technology (NIST) issued a public request for proposals for a standard cryptography standard. They eventually received a promising candidate, an algorithm based on Lucifer cipher invented by IBM. NBS, with NSA aid, analysed the algorithm and made some changes to strengthen the algorithm against any possible cryptanalysis. Also, much to others’ dismay, the NSA had reduced the key size from 128-bit to 56-bit. The resulting standard, DES was adopted as a federal standard on 23 November 1976, despite criticism and complaints from many who were wary of the NSA’s mysterious workings, particularly regarding the design of S-box and the key size.
DES however were proven to be strong and remained as a standard for 20 years. However, in 1998, Electronic Frontier Foundations (EFF) managed a successful brute-force attack on DES using a $1 million machine, confirming the wary of many who thought 56-bit key size was too short. DES is no longer sufficient, hence a variant called Triple DES or 3-DES was often used instead. However, after a 5 year competition, Advanced Encryption Standard (AES) designed by Rijndael was adopted as the new standard in 2001.
Paradoxical Period
Public Key Cryptography
For centuries, one problem kept plagueing those who wanted to use cryptography – key distribution. Eventhough the advent of computers and digital circuits allowed for practical strong cryptosystems, there was still no easy way of securing the distribution of key. The key still needed to be physically distributed using courier to ensure complete confidentiality of the key, as practised by the German military during the World War.
However, in 1976, Whitfield Diffie and Martin Hellman presented their paper ¨’New Direction in Cryptography¨’ which since then changed the cryptography landscape forever. In their paper, a method was shown to allow two parties to agree on a shared secret key, without transmitting the secret key to each other.
For Alice to Bob to agree on a shared secret key, they must first agree on g and N. Both g and N can be made available to public. Diffie-Hellman Key Exchange protocol is detailed below.

While this discovery exhibited only a very little portion of the full potential of number theory, it managed to inspire many other cryptosystem designers to start looking at application of number theory and prime number to cryptography.
RSA Public Key Cryptography
RSA is a public key cryptosystem that was invented by Rivest, Shamir and Adleman, hence the name RSA which takes the first letter of each name. With RSA, two keys are involved which are public key and private key. As the names imply, public key can be made available to others while the private key must be kept in secret.
The relationship between the public key and private key is such that, public key decrypts a message encrypted by private key, and private key decrypts a message encrypted by public key. This type of cryptography is also known as asymmetric key cryptography, which is different from symmetric key cryptography where a single key is both used for encryption and decryption.
RSA public key cryptography is possible because the public key and private key are inverse of each other. The steps below shows how such keys are generated.

Now, suppose a key pair has been generated by Alice. The public key e is put on public directory, whereas the private key d is kept secret by her. For Bob to send a secret message to Alice, he encrypts the message with Alice’s public key and sends it to her. While the encrypted message may be intercepted by the adversaries, only Alice can read the message as she is the only one who has the private key.

As mentioned previously, a message may also be encrypted by private key d, and needs the public key e to decrypt it. This does not add confidentiality to the message, as public key is available to everyone. However, this shows that the message indeed had come from someone who knows the private key. This is called digital signature, a scheme available with asymmetric cryptography.

The strength of RSA algorithm relies on the difficulty of factoring the number N into two prime factors p and q. If the factoring is successful, p and q can be used to compute ϕ(N), and finding the private key d is simply the matter of finding the inverse of public key e mod ϕ(N).
Due to the properties of prime numbers, this problem is also similar to finding all positive integers less than N that are relatively prime to N. Both factoring problem and this problem is considered to be extremely hard for large N, hence providing the security to RSA algorithm.
The impact brought by the advent of RSA was tremendous. It simplified key management. Any person can generate his or her own key pair, publish the public key and be ready to receive encrypted message. This advantage is not shared by symmetric key cryptography, where sender and receiver must first agree on the secret key.
However, RSA is much slower than DES and other symmetric cryptosystems. General practice when transmitting a large secret file is to use symmetric cryptosystem to transmit the file and to use RSA to communicate the secret key. This scheme takes advantage of both cryptosystems and is a general practice where speed is critical.
Quantum Cryptography
The security of quantum cryptography or quantum key distribution (QKD) is based on quantum mechanics laws, in the same manner of RSA security relying on the difficulty of factorization.
Heisenberg Uncertainty Principle, one of the key foundations of quantum physics states that locating a particle in a small region of space makes the momentum of the particle uncertain; and conversely, that measuring the momentum of a particle precisely makes the position uncertain.This unique property allows the two communicating parties in quantum cryptography to detect any eavesdropping of any third party who tries to gain knowledge of the key. This is because any measuring action taken by the third party will introduce detectable changes to the particle states. A properly designed quantum cryptography scheme will be able to detect any eavesdropping attempt by the third party, and retransmit another random key at some other time.
Quantum cryptography is often associated with key distribution, not the encryption itself. After the key distribution, secret message or files can be encrypted using mathematical based cryptosystems such as 3-DES or AES which are more suitable for digital files than quantum cryptography.
Cryptography in the Future
While quantum cryptography has been proven to be technically possible and a working standard, BB84, has already been published, it is not expected to be widely adopted in the near future. Many businesses and organizations are already comfortable with electronic based encryption using mathematically strong algorithms such as Advanced Encryption Standard(AES) and Triple-DES. Unlike the time when classical cryptography were totally defenseless against cryptanalysis, electronic cryptography are now still sufficient to protect data.
However, as computing power increases, and hardware becoming cheaper, stronger cryptanalysis attacks become possible. Increasing the key size is one of the easiest defence. AES currently operates with 128, 192 or 256-bits key size. Whereals for RSA, 512-bit is no longer secure, and the current recommended key size by FIPS 186-3 is 1024-bit. There are also calls for 2048-bit and 4096-bit RSA to ensure an ultra-high security.
Besides, increasing the key size, another defence is to base the cryptography algorithm on a more difficult mathematical problem. For instance, elliptical curve cryptography (ECC) uses shorter key to provide the same level of security as RSA. ECC is based on the algebraic structure of elliptic curves over finite fields and poses more difficult problem than factorization as used in RSA. Shorter key size of ECC is an advantage as it will simplify key management. ECC is fast growing as an alternative to RSA for public key cryptography.
Conclusion
The evolution of cryptography has shown that its development must follow the pace of technology closely. From the ancient time where communication is via written letter to the time where communication is in a form of complicated network of radio equipment and computers, crytography has managed to adapt itself to continue being the method of protecting confidentiality of secret data.
While not in line with its main objective of protecting data, public key cryptography has also found its other function, as the technology to allow digital signature. This also raised other new concerns such key management and certificate management.
Certainly, the development of cryptography is indicative of human ability to adapt to changes and to improve. As technology, economy and politics change, so will cryptography to adapt itself. As such, cryptography will only keep evolving – for unbreakable security, time and cost efficiency and catering for widest range of applications and environment.
References
- Applied Cryptography, Bruce Schneier
- The Codebook, Simon Singh
- FIPS 46-2, Data Encryption Standard (DES)
Filed under: Information Security