EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 1

Evolution of Cryptography
Mohd Zaid Waqiyuddin Mohd Zulkifli

Abstract—Cryptography has undergone tremendous evolution the decryption key. Encryption and decryption keys are
since its earliest adoption by the Egyptians until now. Originally the same for symmetric crypto-system and different for
used as decorations on tombs to attract interest, cryptography has asymmetric crypto-system.
established its primary purpose in protecting secrets. Nowadays,
it is unimaginable for private or confidential data to be unen-
crypted. With the current trend of moving services to Internet, we Cryptanalysis instead is the study of defeating cryptography
now have sensitive information travelling and stored all around in the abscence of the key. This is possible, mainly with weak
world-wide network in form of data packets. They are susceptible ciphers which fail to hide the characteristic of the message,
to interception and thus fully reliant on cryptography to maintain be it the distribution of letters, the repetition or anything.
confidentiality. And the crytography system employed has to
be strong and resistant to cryptanalysis and render brute-force Cryptography and cryptanalysis are two different scientific
attack impractical as there are many who would try every means studies in direct competition with each other, the first attempts
to uncover the protected secret. to hide a secret and the latter attempts to uncover it.
Index Terms—cryptography, cryptoanalysis, war, cipher, code,
attack, evolution.
1) Shannon’s Theory of Confusion and Diffusion: Claude
E. Shannon in 1949 produced a paper titled Communication
I. I NTRODUCTION
Theory of Secrecy System which explained two components of
Julius Caesar did not use cryptography for nothing. He encryption to thwart frequency analysis, namely ”‘confusion”’
was untrusting of his messenger, yet he needed to send a and ”‘diffusion”’. Confusion is used to hide the relationship
highly confidential military instructions to his generals. He between the plaintext and the ciphertext and may be achieved
was equally afraid of the fact that the message might fall into by using complex substitution method. Whereas diffusion
his opponents’ hands and be used against him. aims at spreading the statistics over the message to avoid
exploits by cryptanalysts on any present redundancy. This is
The famously known Caesar Cipher was only one of normally achieved with repeated permutations.
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 2) Kerchoff’s Principle: In 1883, a Dutch linguist Auguste
3, so that ”‘A”’ was translated to ”‘D”’, ”‘B”’ translated to Kerchoff von Nieuwenhof stated in his book La Cryptographie
”‘E”’ and so on. This was an example of monoalphabetic Militaire that the security of a crypto-system must be totally
substitution cipher. dependent on the secrecy of the key, not the secrecy of the
algorithm. This is known as Kerchoff principle and is still
In one occasion, he sent a very critical message to Cicero, relevant even in the current modern era.
who was under siege by replacing Roman letters with Greeks.
This was another form of monoalphabetic substitution cipher. Shouldn’t a cryptosystem be more secure if the related
This particular action was actually the first documented use algorithms be kept secret? Not so. By keeping the algorithms
of cryptography for military purposes.1 secret, the benefit of having reviews from worldwide experts,
both professionals and academicians is not available. Reviews
II. F UNDAMENTALS OF C RYPTOGRAPHY are extremely important to detect any flaws in the design
The word cryptography originated from two Greek words, of the cryptosystem. This is not so different from open
kryptos which means secret and graphos which means source software methodology, exposing the source code to the
writing, hence it literally means secret writing. In particular, public to allow contribution of criticism and constructive ideas.
cryptography may be thought of as the science of secret
writing, aiming at protecting data so that only the intended Moreover, it is also very difficult to keep the inner working
recipients may decrypt and read the message. of a crypto-system secret. With the crypto-system products
being marketed to many parties, it is unreasonable to assume
A cryptography system or crypto-system is composed that the underlying algorithms can not be discovered by
of two complementing functions, encryption and decryption. reverse-engineering. Besides there is also possibility that such
Encryption operates on plaintext to transform it into secret might be revealed by irresponsible individuals who had
unintelligible form based on input key. Decryption instead been involved in the development.
operates on ciphertext to recover the original message using
Considering all these risks, it is safer to abide by Kerchoff’s
1 The Code Book, Simon Singh principle and release the crypto-system algorightms to
EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 2

the public for reviews. However, certain organizations, or one-to-many relationship between the plaintext and the
National Security Agency (NSA) notably prefer to keep ciphertext. For example, with Atbash cipher we have ”‘A”’
their algorithms secret by arguing that ”‘if less people replaced by ”‘Z”’ , ”‘B”’ replaced by ”‘Y”’ and so on, which
know about the crypto-systems, less people know how to are based on one-to-one function. The similar applied to with
attack”’. However it must be observed that these organizations Caesar Cipher, where ”‘A”’ is substituted with ”‘D”’, ”‘B”’
normally are very big and can afford to hire the best experts with ”‘E”’ and so on.
in crytography to do private reviews.
The scheme can be made more resistant to attacks and
III. P ERIODS OF C RYPTOGRAPHY analyses by replacing each plaintext alphabet with one or
Academicians have segmented cryptography history and more ciphertext alphabet. For example, ”‘A”’ may be replaced
development into 3 significant periods : by ”‘T”’ or ”‘X”’, ”‘B”’ replaced by ”‘J”’ or ”‘4”’ etc. This
has the advantage of hiding any statistical pattern which very
i Ancient ( until 1918 )
often present in normal messages.
ii Technical ( 1919-1975 )
iii Paradoxical ( from 1976 )
Frequency Analysis

A. Ancient Period During the Islamic golden age in the 9th century, an
The use of cryptography has been traced back to Arab polymath Abu Yusuf Ya’qub al-Kindi discovered a
the ancient civilisations. In 3500 B.C. , the Sumeians technique to defeat monoalphabetic substitution cipher.
developed cuneiform writing whereas the Egyptian developed The technique exploits the intrinsic properties of written
hieroglyphic writing. The Egyptians in particular is known to languages that certain letters occur more often than the others.
have used cryptography on the tombs of deceased kings and The statistical distribution of letters in the ciphertext can
rulers. However it was not used to hide any secrets, but rather be related to average distribution of letters in the particular
to tell the story of the deceased in all elegance and regality. language to find the underlying mapping function or functions.

Hebrew scholars were noted to have used Atbash The following table2 shows the average distribution of
cipher around 600 B.C. Atbash cipher is a very simple letters in English text.
monoalphabetic substitution cipher, performed by reversing
TABLE II
the alphabet. An Atbash system applied to Roman alphabet L ETTERS F REQUENCY
would be :
TABLE I Letter Frequency Letter Frequency
ATBASH C IPHER A 8.167% N 6.749%
B 1.492% O 7.507%
C 2.782% P 1.929%
Plain Cipher Plain Cipher D 4.253% Q 0.095%
A Z N M E 12.702% R 5.987%
B Y O L F 2.228% S 6.327%
C X P K G 2.015% T 9.056%
D W Q J H 6.094% U 2.758%
E V R I I 6.966% V 0.978%
F U S H J 0.153% W 2.360%
G T T G K 0.772% X 0.150%
H S U F L 4.025% Y 1.974%
I R V E M 2.406% Z 0.074%
J Q W D
K P X C
L O Y B Polyalphabetic Substitution Cipher
M N Z A

Cryptanalysis since then built on frequency analysis to

The first military cryptographic device was scytale, used form better attacks on monoalphabetic substitution cipher
by the Spartan in 500 B.C. to implement transposition cipher. and its variants. The variants included introducing null or
To send an encrypted message, the sender would wrap a dummy values in between the letters, using keyphrases etc.
strip of leather or parchment around the scytale and write However many of these variants were still unable to prevent
the message as normal. When the leather or parchment was cryptanalysis and subsequently lead to the exposure of the
then unwound, the letters of the message were automatically secrets. One tragic example was the thwart of Babington Plot,
shuffled, rendering the message in a new unintelligible form. where Sir Francis Walsingham broke the correspondence
To recover the message, the intended recepient would simply cipher between Anthony Babington and Mary Queen of Scots
take the leather and wrap it around his scytale. and proved their plan to kill Queen Elizabeth. This resulted
in the death execution of Mary Queen of Scots and other
Monoalphabetic Substitution Cipher conspirators.

Monoalphabetic substitution cipher relies on one-to-one 2 http://en.wikipedia.org/wiki/Letter frequencies

EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 3

created by a German inventor, Arthur Scherbius. The basic

The need for cipher stronger than monoalphabetic substitution design had three elements connected by wires: a keyboard for
cipher was apparent. The new cipher would have to be inputting the plaintext message, a scrambler unit that encrypts
resistant to frequency analysis, the ultimate cryptanalysis a plaintext letter into a ciphertext letter and a display board
attack at the time. consisting of various lamps for indicating the ciphertext letter.3

Near the end of 16th century, a retired French diplomat Scherbius designed it such that the scrambler revolved
Blaise de Vigenere built on previous work by Alberti, one-sixth of a revolution such that the same plaintext letter
Trithemius and Porta to introduced Vigenere cipher, which would encrypt differently that the previous. For example,
was a form of polyalphabetic substitution cipher. Unlike plaintext ’A’ would be encrypted to ’K’, and typing ’A’
monoalphabetic substitution cipher, ”‘A”’ in the plaintext may again might encrypt it to ’C’ this time and so on. However,
be translated to ”‘J”’ in one occasion and ”‘T”’ in another. after the sixth rotation, the scrambler would have made one
And ”‘B”’ also may be translated to ”‘J”’ and ”‘R”’. Notice complete revolution, hence ’A’ would be encrypted to ’K’
that a letter ”‘J”’ in the ciphertext may actually represent again. This is the one of the main weaknesses in Scherbius
”‘A”’ or ”‘B”’. This criteria renders frequency analysis a lot original design, since repetition is taboo in cryptography.
less effective.
With one scrambler, there were 6 different settings. Cascading
another scrambler, a total of 36 distinct scramble settings were
Kasiski’s Method obtained. For the Enigma machine, a third scrambler were
added, making the number of different scrambler settings to
Friedrich Wilhelm Kasiski discovered a method to break be 216. For full alphabet, this meant there were 26 x 26 x 26
Vigenere Cipher. He noticed that there are repetitions in = 17576 distinct scrambler arrangements.
Vigenere ciphertext, caused by same words being encrypted
with the same part of the key. However, 17576 was a small number, and a team of
fifteen people could try all different arrangements in a day.
By analysing the place of repeated occurences, Kasiski Realising this, Scherbius further added a new feature by
managed to guess the length of the key used for Vigenere allowing any different arrangement of the three scramblers,
Cipher. The length of the key is a critical information for increasing the number of distict arrangment by a factor of
this cipher, as the ciphertext can then be grouped into many 6. He then added a plugboard between the keyboard and the
different groups, with the number of groups equal to the first scrambler which have the effect of swapping some of
length of the key used. From there, frequency analysis can the letters before they enter the scrambler.
be conducted on individual group as usual.
With all these features, Enigma had a massive
This so called Kasiski Method is extremely powerful 10,000,000,000,000,000 number of different states or
cryptanalysis technique against Vigenere Cipher. Following arrangements. Brute-force attack a message by trying all
this discovery, cryptographers were forced to search for possible Enigma configurations was simply impossible.
stronger cryptography method, however without much
success for many years to come. The Enigma machine was accepted by German military
and many Enigma machines were built and distributed.
Codebooks were published regularly and distributed to
B. Technical Period all Enigma operators to sychronise the choice of Enigma
During World War I, mechanical machines are used to configuration for any particular day. It goes without saying
perform encryption and this marked the beginning of technical the codeboooks must be kept secret by the German military.
period in cryptography. At this time, radio transmission for
communication was already used in warfare, following its In the years to follow, German communication was
discovery by an Italian physicist by name Guglielmo Marconi unbreakable. This caused worry to Allied forces, hence they
in 1894. Encrypted messages transmitted over the air can be began to gather the best cryptanalysts to find a way to break
intercepted very easily, which means a strong cipher was of the Enigma cryptography. A young man from Poland, Marian
paramount importance. Mechanical machine for encryption Rejewski was among them, and he was credited as the person
was invented as Vigenere cipher had already been rendered who cracked Enigma.
useless by Kasiski.
Rejewski had successfully separated the problem of finding
the scrambler setting from the problem of finding the
Enigma Machine plugboard setting. Individually these problems can be solved
within reasonable time. Rejewski took advantage of German
Without doubt, the Enigma machine was the most communication requirement that the message key must be
famous cryptography device during the Technical Period of
cryptography. It was used by the German military and was 3 The Code Book, Simon Singh
EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 4

encrypted twice at the beginning of every message. The the advent of computers and digital circuits allowed for
repetition led to pattern and patterns can be exploited to find practical strong cryptosystems, there was still no easy way
the message key. Since this discovery, German communication of securing the distribution of key. The key still needed to
became transparent. be physically distributed using courier to ensure complete
confidentiality of the key, as practised by the German military
Data Encryption Standard (DES) during the World War.

Following the invention of computer and digital devices, However, in 1976, Whitfield Diffie and Martin Hellman
more and more operations were being handled electronically. presented their paper ¨’New Direction in Cryptography¨’ which
Data were kept in computers in digital form. Data packets since then changed the cryptography landscape forever. In
were also roaming via network cables and were susceptible to their paper, a method was shown to allow two parties to agree
intercept by anyone. Cryptography was needed not by military on a shared secret key, without transmitting the secret key to
and government alone anymore, but also by any institutions each other.
or organizations that used computers for managing data.
For Alice to Bob to agree on a shared secret key, they
Due to various nature of computer application and files, must first agree on g and N . Both g and N can be made
two types of symmetric key cryptography were designed, available to public. Diffie-Hellman Key Exchange protocol is
namely stream cipher and block cipher. The difference is detailed below.
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.
1) Alice and Bob agree on g and N
By early 1970’s, the need for a cryptography standard
2) Alice chooses x and compute
was apparent. Businesses and organizations who did not
X = g x mod N
have expertise in cryptography were being sold different
x must be kept secret.
cryptography devices which failed to interoperate. There was
no assurance of these cryptography products as there was no
3) Bob chooses y and compute
independent body to do certification.
Y = g y mod N
y must be kept secret.
In 1973, National Bureau of Standards (NBS), now the
National Institute of Standards and Technology (NIST) issued
4) Alice and Bob exchange X and Y openly.
a public request for proposals for a standard cryptography
standard. They eventually received a promising candidate, an
5) Independently, Alice computes shared secret key, k,
algorithm based on Lucifer cipher invented by IBM. NBS,
k = Y x mod N
with NSA aid, analysed the algorithm and made some changes
to strengthen the algorithm against any possible cryptanalysis.
and Bob computes
Also, much to others’ dismay, the NSA had reduced the key
k 0 = X y mod N
size from 128-bit to 56-bit. The resulting standard, DES was
adopted as a federal standard on 23 November 1976, despite
6) Hence, shared secret key is
criticism and complaints from many who were wary of the
k = k 0 = g xy mod N
NSA’s mysterious workings, particularly regarding the design
of S-box and the key size. While this discovery exhibited only a very little portion of
the full potential of number theory, it managed to inspire many
DES however were proven to be strong and remained as a other cryptosystem designers to start looking at application
standard for 20 years. However, in 1998, Electronic Frontier of number theory and prime number to cryptography.
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 RSA Public Key Cryptography RSA is a public key
longer sufficient, hence a variant called Triple DES or 3-DES cryptosystem that was invented by Rivest, Shamir and
was often used instead. However, after a 5 year competition, Adleman, hence the name RSA which takes the first letter
Advanced Encryption Standard (AES) designed by Rijndael of each name. With RSA, two keys are involved which are
was adopted as the new standard in 2001. public key and private key. As the names imply, public key
can be made available to others while the private key must
C. Paradoxical Period be kept in secret.
Public Key Cryptography

For centuries, one problem kept plagueing those who The relationship between the public key and private key is
wanted to use cryptography - key distribution. Eventhough such that, public key decrypts a message encrypted by private
EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 5

key, and private key decrypts a message encrypted by public The strength of RSA algorithm relies on the difficulty of
key. This type of cryptography is also known as asymmetric factoring the number N into two prime factors p and q. If
key cryptography, which is different from symmetric key the factoring is successful, p and q can be used to compute
cryptography where a single key is both used for encryption φ(N ), and finding the private key d is simply the matter of
and decryption. finding the inverse of public key e mod φ(N ).

Due to the properties of prime numbers, this problem is

RSA public key cryptography is possible because the also similar to finding all positive integers less than N that
public key and private key are inverse of each other. The are relatively prime to N . Both factoring problem and this
steps below shows how such keys are generated. problem is considered to be extremely hard for large N ,
hence providing the security to RSA algorithm.

1) Two large prime numbers, p and q are chosen.

The impact brought by the advent of RSA was tremendous.
It simplified key management. Any person can generate his
2) Compute N = p.q
or her own key pair, publish the public key and be ready to
receive encrypted message. This advantage is not shared by
3) Compute φ(N ) = (p − 1)(q − 1)
symmetric key cryptography, where sender and receiver must
first agree on the secret key.
4) Now choose e randomly. e is the public key

5) Find private key, d. d must satisfy However, RSA is much slower than DES and other
symmetric cryptosystems. General practice when transmitting
e.d = 1 mod φ(N ) a large secret file is to use symmetric cryptosystem to
transmit the file and to use RSA to communicate the secret
Now, suppose a key pair has been generated by Alice. key. This scheme takes advantage of both cryptosystems and
The public key e is put on public directory, whereas the is a general practice where speed is critical.
private key d is kept secret by her. For Bob to send a secret
message to Alice, he encrypts the message with Alice’s Quantum Cryptography
public key and sends it to her. While the encrypted message
may be intercepted by the adversaries, only Alice can read The security of quantum cryptography or quantum key
the message as she is the only one who has the private key. distribution (QKD) is based on quantum mechanics laws, in
the same manner of RSA security relying on the difficulty of
For encryption factorization.

Cipher, c = me mod φ(N )

Heisenberg Uncertainty Principle, one of the key
For decryption foundations of quantum physics states that locating a particle
in a small region of space makes the momentum of the particle
Message, m = ce mod φ(N ) uncertain; and conversely, that measuring the momentum
of a particle precisely makes the position uncertain.4 This
unique property allows the two communicating parties in
As mentioned previously, a message may also be encrypted quantum cryptography to detect any eavesdropping of any
by private key d, and needs the public key e to decrypt it. third party who tries to gain knowledge of the key. This is
This does not add confidentiality to the message, as public because any measuring action taken by the third party will
key is available to everyone. However, this shows that the introduce detectable changes to the particle states. A properly
message indeed had come from someone who knows the designed quantum cryptography scheme will be able to detect
private key. This is called digital signature, a scheme available any eavesdropping attempt by the third party, and retransmit
with asymmetric cryptography. another random key at some other time.

For signing message Quantum cryptography is associated with key distribution,

not the encryption itself. After the key distribution, secret
Sign, s = md mod φ(N ) message or files can be encrypted using mathematical based
cryptosystems such as 3-DES or AES which are more suitable
For verifying signature for digital files than quantum cryptography.

Verify v = se mod φ(N )

4 http://en.wikipedia.org/wiki/uncertainty principle
EVOLUTION OF CRYPTOGRAPHY, 17 JANUARY 2007 6

IV. C RYPTOGRAPHY I N T HE F UTURE [4] http://en.wikipedia.org/wiki/des

[5] http://en.wikipedia.org/wiki/history of cryptography
While quantum cryptography has been proven to be [6] http://en.wikipedia.org/wiki/advanced encryption standard
technically possible and a working standard, BB84, has [7] http://en.wikipedia.org/wiki/stream cipher
[8] http://en.wikipedia.org/wiki/block cipher
already been published, it is not expected to be widely [9] http://en.wikipedia.org/wiki/elliptic curve cryptography
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.

V. C ONCLUSION
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.

R EFERENCES
[1] Applied Cryptography, Bruce Scheneier
[2] The Codebook, Simon Singh
[3] FIPS 46-2, Data Encryption Standard (DES)