ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

ChaptER
1
LEa R NI NG OUtCOMES
Introduction to
Cryptography
What is Ethics

By the end of this chapter, you should be able to:

1. Describe the evolution history of cryptography;

2. Explain the structure of cryptography;

3. Define cryptography;

4. Discuss some historical algorithms;

5. Describe the substitution cipher; and

6. Explain the transposition cipher.

7
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

INTRODUCTION
The widespread usage of computers and the Internet today has fostered new interest in
cryptography partly due to the new emphasis on personal privacy. In our pursuits to make
it easy for computers to share stuff, little did we realise that in essence our efforts
would also make it easy for other people to see all of our personal stuff too. In most
cases we naively expose far too much personal information, making it effortless for un-
familiar persons to read our personal email messages, credit card details, love letters
and so on. Visit the link below to view the describes the importance of cryptography.

Source: http://www.youtube.com/watch?v=HwW8ZChHqAc

Furthermore as the Internet continues to grow day by day making McLuhan’s global village,
a village where everyone can see what you do and hear what you say, a reality . . ., more
information is at an attacker’s disposal. The good news is that not all hope is lost as
those concerned with privacy can use cryptography to secure their networks from eaves-
droppers within this “global village”.

Not only can cryptographic methods scramble files, but they can also be used to prove
identity (and maybe even disprove it!). Cryptography today can be used to ensure integrity
and confidentiality of the contents of a file as it is able to signify modifications,
keep online communications safe, secure and ofcourse conceal important data. There are
several inexpensive cryptographic solutions available and the best part is their imple-
mentation is not complex and there-fore you do not need to be a rocket scientist to
incorporate crypto solutions into your network.

1.1 INtRODUCtION tO CRYptOGRaphY

Before the 1970s, cryptography was a not considered as a cryptographic science, only a
few government and military personnel were privileged to understand its important role.
It is now a well-established academic discipline that is taught in many universities.
The history of cryptography has been illustrated in Figure 1.1.

8
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

Figure 1.1: Cryptography milestones

Source: http://www.sqlservercentral.com/columnists/mcoles/milestones.png

It is also widely available for use by companies and individuals. There have been many
forces that have influenced this transition. Two of the most obvious have been the move
towards automated business and the establishment of the Internet as a communications
channel. Companies now want to trade with each other and with their customers using the
Internet. Governments want to communicate with their citizens via the Internet so that,
for example, tax returns may be submitted electronically.

These three concerns addressed in traditional non-automated business environments.

9
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

Content 1
Without any doubt e-commerce is increasingly popular, but the lack of
adequate security is often quoted as being one of the main drawbacks for
its complete acceptance. Crypto-graphy initially focused on the problems
associated with confidential information, but in recent decades confiden-
tiality is frequently not the only main concern.

Content 2
Presuming that two people who are unable to see each other wish to communi-
cate using a public network, it would be a daunting task for either of them
to indisputably establish the identity to each other. Undoubtedly, for any
message being received via an open network, it is cardinal for the recipient
to be convinced that the sender’s identity is accurate.

Content 3

Not only this, but there is need for the message received to be identical to
that sent by the originator for confidence to be established between the two
parties. Furthermore, certain situations demand that the sender should not be
in a position to later deny sending the message and/or claim to have sent a
different one. Solutions to such important issues are certainly not clear-cut.

Three concerns are sufficiently addressed in traditional non-automated business environ-

ments where handwritten signatures are frequently relied on to provide assurances for
identity. However, today with widespread automation, researchers and security profes-
sionals have a significant struggle in finding ‘electronic equivalents’ which can re-
place social mechanisms, such as face-to-face recognition or use of handwritten signa-
tures that have been lost in the migration to digital transactions.

As a result cryptography has become an important tool in meeting the challenge

of keeping secret information secure. Developments on electronic equivalents to
the handwritten signa-ture were published in a 1976 paper entitled “New Directions
in Cryptography”.

We cannot overstate the impact of the paper. Before this development, cryptography was
used to assure users that no modification would occur during the transmission of their
messages. However, this assumption relied on mutual trust between the communicating
parties.

This did not prove to be a problem at that time, because environments where crypto-
graphy could be employed were undoubtedly limited and basically the main users were
financial institutions, which at that time were not probably that globalised.

However, cryptography has significantly evolved over the last three decades. Not only have

10
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

there been a lot of technological advancements in this field, but there is now a large
variety of applications available. On the other hand, everyone is likely to be a direct
user or be affected by its use. Therefore, there is a need for all people to understand
how it works and what it can achieve.

1.2 KEY CONCEptS aND DEfINItIONS

The main idea of a cipher system is to hide confidential information in a way that
it cannot be understand to an unauthorised person. There are two different uses which
are, storing data securely in a file on a computer or transmitting data across an
insecure channel such as the Internet. Figure 1.2 is illustrates the cipher taxonomy.

Ciphers

Classical Rotors Machines Modern

Substitution Transpostion Public key Private key

Stream Block

Figure 1.2: Encryption cipher taxonomy

Source: http://bluefive.pair.com/article_encryption_cipher-taxonomy.gif

In either circumstance the fact that the document is encrypted does not prevent
unauthorised people gaining access to it but, rather, ensures that they cannot
understood what they see.

The information to be concealed is often called the decryption and the

operation of disguising it is known as encryption.

11
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

A cryptogram, also known as ciphertext is a piece of encrypted plaintext. In order

to obtain ciphertext from plaintext a set of rules called the encryption algorithm is used.

Normally, the operation of this algorithm is dependent on an appropriate encryption and

decryption key, which is input to the algorithm together with the plaintext/ciphertext
to allow for the encryption and decryption respectively. Designers of cryptographic
algorithms need to be cautious, as these algorithms generally comprise of a complicated
set of rules.

The conversion of plaintext into an unreadable form achieved by the use of rules and the
assistance of keys can be regarded as a ‘magical formulae’.

Figure 1.3 provides a diagrammatic description of the use of a cipher system to protect a
transmitted message.

Figure 1.3: Cipher system diagram

During transmission, it is possible for a message to be intercepted by an interceptor.

The interceptor can also be referred to eavesdropper or bad guy. However, it must be
acknowledged that, on some occasions, the interceptors may be even good guys.

In general, what is known by the interceptor is the decryption algorithm, not the de-
cryption key. It is this lack of knowledge that is anticipated, prevents them from
knowing the plaintext.

The science of designing cipher systems is known as cryptography, whereas cryptanalysis

is inferring information from the cryptogram without knowledge of the appropriate key.
Cryptology is the collective term for both cryptography and cryptanalysis.

It is very important to note that an attacker can gain access to plaintext by various
means of attack other than just by the use of cryptanalysis.

When encrypted data is stored on a laptop the owner will obviously require having some
way of recovering the decryption key. If for instance as is practiced in most cases the
owner decides to write down the key on a piece of paper which is then stuck to the lid
of their laptop, then anyone who access to the laptop automatically has the decryption

12
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

key and hence does not need to perform any cryptanalysis.

From this simple illustration, it is clear that the use of a good encryption algorithm
can easily be comprised if the security of the keys is not critically addressed.

The success of most cryptanalytic attacks involve the attacker trying to determine the
decryption key, which enables him to gain the same knowledge as the intended recipient
and to decrypt all other communications until the keys are changed. In some instances
though, an attacker may only be interested in intercepting a particular message.

Nevertheless when an attacker comes up with a practical way of determining the decryption
key it is considered as though an algorithm has been broken. In practice if the attacker
has sufficient information to recognise the correct key or more frequently to identify the
incorrect ones, then the algorithm may be broken. It is essential for the attacker to have
access to this additional information as it can help in guessing some of the variables.

Supposing the attacker knows the language that was used to construct the plaintext
and that the decryption of some ciphertext using a guessed key does not give meaning-
ful plaintext in the given language. This extra information will definitely disqualify
the guessed key.

The knowledge of some pairs of plaintext and corresponding ciphertext enable an

attacker to carry out what is known as a plaintext attack. If the plaintext is
selected by the attacker, then it is a chosen plaintext attack. Finally, an attack
which has direct knowledge only of the ciphertext is known as a ciphertext-only
attack as shown in Figure 1.4.

Figure 1.4: The plaintext attack

13
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

When distinguishing between symmetric and asymmetric algorithms, there is a need

for trust between the sender and receiver. The publication of the famous Diffie-
Hellman paper dispelled the assumption held for centuries that encrypted messages
could only be exchanged between mutually trusted parties.

Public key algorithms are discussed in later chapters. To shed more light on this
concept a well-known example is presented in Figure 1.5. It endeavours to show that
despite the fact that a present may be transmitted through a channel with many adver-
saries, safe delivery is feasible.

Figure 1.5: The steps to ensure the safely delivery of the present

As illustrated in Figure 1.5 we presume that the sender has a present, which he
wants to securely send to someone using a briefcase with a padlock. Due to some
justifiable reason the sender is not prepared to trust the recipient with his own key.

To avoid his key falling into untrusted hands the sender instructs the intended
recipient to purchase his own padlock and key. Here we are working under the
assumption that the padlocks and briefcase are sufficiently robust that no one
can forcibly remove the contents of the briefcase. Additionally, no one else
apart from the respective owners can find a key that can unlock both padlocks.

The sender and receiver now carry out the following steps to ensure delivery

14
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

of the present as shown in Table 1.1.

Table 1.1: Steps to be Followed by Sender and Receiver to Ensure Delivery of the Present

Step 1 The sender places the present in a briefcase, which he locks with a padlock
and removes the key. He then sends the locked briefcase to the receiver.

While the briefcase is en route from sender to receiver, it is safe from

Note all adversaries, because they cannot remove the padlock from the briefcase.
However, the receiver is also unable to obtain the present.

Step 2 The receiver locks the briefcase with his padlock and removes the key.
He then returns it to the sender.

Note The briefcase is now locked with two padlocks so no one can get the
present.

Step 3 The sender removes his padlock from the briefcase using his own key
and thereafter returns the briefcase to the recipient.

Note Now the only lock on the briefcase belongs to the receiver.

Step 4 The recipient unlocks his padlock to obtain the present from the briefcase.

The result of this chain of events is that the recipient is now in possession of the
present, which has been delivered without either party needing to let their own keys
leave their possession. In this case, the necessity for trust between the two parties
is done away with. Of course in real world suppositions made about the keys and the
strength of the padlocks and briefcase are open to scrutiny.

However, when we discuss public key cryptography these assumptions are replaced by
mathematical equivalents, which are believed to be more acceptable. The concept of
secure communications without mutual trust might in theory be possible as illustrated
above.

1.3 hIStORY Of CRYptOGRaphY

When we endeavours to study the history of cryptography, there are algorithms that
we will find to be outdated and not really indicative of any modern cryptographic
techniques. However, it is very useful to study a number of early systems where en-

15
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

cryption was achieved by replacing each letter by another, called letter substitution,
and/or changing the order of the letters.

There are several motives behind this, the first one being their simplicity and ease
to understand examples which easily sheds more light on the basic concepts. Secondly,
they also help illustrate a number of potential weaknesses that exist in ciphers. Another
is that as they tend to be non-mathematical, no special scientific training is needed for
amateurs to enjoy trying them out.

1.3.1 Caesar Cipher

As illustrated in Figure 1.6. One of the earliest examples of a cipher was the Caesar
Cipher used by Julius Caesar in the Gallic Wars. In this cipher, each of the letters
A to W is encrypted by being represented by the letter that will be in three places
after it in the alphabet. With a shift of 3, the letter A would be replaced by D, B
would become E, and so on. In effect, any shift is now generally viewed as a Caesar
Cipher since a shift can be achieved by using any number from 1 to 25.

Figure 1.6: Action of caesar cipher

Once again we use a diagram to illustrate a cipher. The Figure 1.7 represents two
concentric rings of which the outer one is free to rotate. If we start with the
letter A outside A, a shift of 2 results in C being outside A and so on. Including
the shift of 0 (which of course is the same as a shift of 26), there are now 26
settings. For a Caesar Cipher the encryption key and the decryption key are both
determined by a shift.

16
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

Figure 1.7: A ‘machine’ to implement a caesar cipher

The Caesar Cipher is attained by assuming that each letter of the plaintext is on the
inner ring while the coinciding letters on the outer ring as the ciphertext which
depends on the selected shift. For decryption, we merely perform the reverse operation.

Thus, from the Figure 1.7, for a shift of 3 the ciphertext for the plaintext message
DOG is GRJ while the plaintext for a cryptogram FDW is CAT. In order to give the
reader confidence that they understand the system we list four statements to check.
If the shift is 7 then the ciphertext corresponding to VERY is CLYF while, for shift
17, the plaintext corresponding to JLE is SUN.

The encryption and decryption keys in the Caesar Cipher are both equal to the
shift however the encryption and decryption rules are different. By making minimal
adjustments in the formulation and making the two rules identical, it is possible
to obtain different encryption and decryption keys.

To see this we merely observe that a shift of 26 has an equivalent effect to a

shift of 0 and, for any shift from 0 to 25, encryption with that shift is the
same as decryption with the new shift obtained by subtracting the original shift
from 26. So, for example, encryption with shift 8 is the same as decryption with
shift 26 - 8 = 18. This enables us to use the same rule for encryption and decryption
with the decryption key 18 corres-ponding to the encryption key 8.

17
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

Due to the Caesar Cipher only having 26 keys, it is highly vulnerable to the
exhaustive key search attack. Apart from this, knowledge of a very small amount
of information like a single pair of corresponding plaintext and ciphertext
characters can enable the attacker to deduce the key.

The simplest way to illustrate an exhaustive key search is to work through a

complete example. Since there are only 26 keys, it is particularly easy for a
Caesar Cipher to be broken using an exhaustive key search. Using the Caesar Cipher,
a message created in English is transmitted, and somehow the ciphertext which is
XMZVH is intercepted.

If the originator had used a shift of 25 to create the ciphertext, then a shift
of 1 would be utilised for decryption giving YNAWI as the outcome. Since this
has no meaning in English we can safely eliminate 25 as the key value. The result
of systematically trying the keys 25 to 1, in decreasing order, is shown in the Table 1.2.
Table 1.2: An Example of an Exhaustive Key Search: Cryptogram XMZVH

Enciphering Assumed Enciphering Assumed Enciphering Assumed

key ‘message’ key ‘message’ key ‘message’0
0 XMZVH 17 GVIEQ 8 PERNZ
25 YNAWI 16 HWJFR 7 QFSOA
24 ZOBXJ 15 IXKGS 6 RGTPB
23 APCYK 14 JYLHT 5 SHUQC
22 BQDZL 13 KZMIU 4 TIVRD
21 CREAM 12 LANJV 3 UJWSE
20 DSFBN 11 MBOKW 2 VKXTF
19 ETGCO 10 NCPLX 1 WLYUG
18 FUHDP 9 ODQMY 0 XMZVH

With CREAM appearing as the most meaningful English word among the 26 probable
outcomes, we can then assume that the encryption key is 21. This enables us to
decrypt all future messages until the key is changed. As much as we have achieved
complete success in this key search, it is essential to note that when dealing with
a more complex cipher more than one key search will be required to yield the desired
result.

It is much more likely merely to limit the number of possibilities by eliminating some
obviously wrong ones. Going back to the Caesar Cipher example, you will notice that an
exhaustive key search for the ciphertext HSPPW produces two whole English words as
prob-able keys. (These shifts are 4 and 11, giving DOLLS and WHEEL respectively).

In such an instance, distinctively determining the key would require that the interceptor

18
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

be aware of the message’s context and additional variables from the cryptogram. Even
though we were not able to distinctively identify the key, we have managed to eliminate
24 keys. In the event that another cryptogram is intercepted, a full key search will not be
necessary as only the two deduced shift will be used.

From this illustration, I would like to bring to your attention that by using a shift
of 7 it is possible to find two English words with character lengths of five each.

During his reign, Caesar successfully eluded his enemies using a shift of 3 to left when
transmitting messages However with easy access to information today most people know
about encryption and thus the Caesar Cipher can effortlessly be broken.

When introducing the Caesar Cipher we noted that a shift of 26 is the same as a
shift of 0. This is because a shift of 26 is a complete revolution of the Caesar
Wheel. This reasoning can be extended to show that any shift is equivalent to a
shift between 0 and 25. For example a shift of 37 is obtained by one complete
revolution of the Caesar Wheel and then a shift of 11. Instead of saying, for
example, that a shift of 37 is equivalent to a shift of 11, we write 37 = 11 (mod 26).

This is known as using arithmetic modulo 26, and 26 is known as the modulus
as shown in Figure 1.8. Modular arithmetic, for many other module as well as
26, plays a crucial role in a number of cryptographic areas. Please refer to
the appendix for a fuller understanding of what is presented in this chapter.

Figure 1.8: The multiplication table for integers modulo 26

Source: http://thesongforce.com/caleb/Figure9.jpg

19
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

Every now and then a Caesar Cipher is referred to as an additive cipher. This is
achieved by assigning numerical values to the alphabet as shown below:

A = 0, B=1, . .. , Z = 25.

Encryption for a Caesar Cipher with shift y can now be achieved by replacing
the number x by x + y (mod 26).

Thus, for example, since N is the fourteenth letter of the alphabet, N= 13.
To encrypt N with a shift of 15, we have x = 13, y = 15, which means the
encrypted version of N is 13 + 15 = 28 = 2 (mod 26). So N is encrypted
as C.

Since additive ciphers have few keys, multiplication as an optional encryption rule
may be used as a way to extend the number of keys. Encryption being a reversible
process, this may on the other hand limits the number of ‘multiplicative keys’.

Suppose we try to encrypt messages by multiplying by 2 and use arithmetic modulo 26.
When we do this A and N are both encrypted as A, B and O are both encrypted as C, etc.
This makes decryption impracticable as only alphabetical characters represented by even
numbers can appear in cipher text.

Furthermore, the cipher text may represent one of two letters. Worse still in
attempting to encrypt multiplying by 13, fifty percent of the alphabet would be
encrypted as A with the fifty percent as N. For multiplication to work the only
integers that can be used are: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, or 25.

aCTIvITY
Can you create an application programming by C or Java to perform the
Cryptanalysis of Caesar Cipher?

1.4 SIMpLE SUBStItUtION CIphERS

It is a common misconception that a strong crypto system is synonymous with a large

number of keys. To elaborate on this we shall use the Simple Substitution Cipher (or
Mono alphabetic Cipher) that we now discuss in detail. Figure 1.9 shows a common
example for simple substitution cipher (or Mono alphabetic Cipher).

20
ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

Figure 1.9: Type of substitution cipher

Using this cipher will disprove the ‘grantee’ that a large number of keys is a sign
of strength. It also demonstrates how an interceptor can make the most of the statis-
tics of the underlying language. We illustrate this using the English alphabet as
shown below.

The order in which the letters are written dictates the encryption and decryption
keys which are equal. By replacing each letter by the one directly underneath it
the encryption rule is satisfied. When it comes to decryption the reverse applies.

For instance using the figure above as the key, the plaintext GET is will be encrypted
as ZTP and BIG as IYZ. Instead of randomly arranging the bold letters as above, a shift
can be used thus creating a Substitution cipher which in essence is a form of the Caesar
Cipher.

26 factorial, which is denoted as 26! is the number of keys for a Simple Substitution
Cipher. This is equivalent to the total number of ways in which the 26 letters of the

21
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

alphabet can be arranged i.e. 26 x 25 x 24 x ... x 3 x 2 x 1 which equals;

403, 291, 461, 126, 605, 635, 584, 000, 000.

Attempting an exhaustive key search with such a huge number could prove to be a very
daunting task not only this but it also introduces new challenges such as key manage-
ment. In the first step we understand that, unlike the Caesar Cipher, the key is long
and difficult to memorise.

Thus, in pre-computer days, when this type of system was used manually, the key was
frequently written on a piece of paper. If this paper was seen and/or stolen then the
system was compromised. In the event that the key was lost, then the legitimate recip-
ient would have to discover a practical way of breaking the algorithm when in receipt
of further encrypted messages.

To address these challenges one scheme that can be used to generate keys is to come up
with a key phrase. Repeating characters should be removed before the key phrase can be
used as the starting point, then let the rest of the alphabetical characters follow in
a chronological order. The full key phrase is obtained by adding the remaining letters
in alphabetical order.

For example when a key phrase such as “We hope you enjoy this book”
is used, it will initially be represented as “wehopyunjtisbk” and
then the full key will be as follows.

“WEHOPYUNJTISBKACDFGLMQRVXZ“

Clearly restricting keys to those that can be derived from key phrases reduces the
number of keys because a significant proportion of the 26! Possible simple substi-
tution keys cannot be derived from an English phrase in this way. However, the
number of keys is still too large for an exhaustive search to be feasible and it
is now easy to remember keys.

A second obvious observation about Simple Substitution Ciphers is that it is fairly

likely that many different keys encrypt the same message into the same cryptogram.

If MEET ME TONIGHT is the plaintext, when we encrypt using the key

given above the outcome will be FTTP FT PREYZSP. There are

18! = 6, 402, 373, 705, 728, 000.

22
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

of such keys. Since seven variables have been clearly identified, then if a further
1.5.3 Common Reasons for errors During setup
interception is made it is may not be necessary to be in possession of the entire key
to obtain the clear message.

In order to illustrate how the English language can be taken advantage of statistically,
we shall use four explicitly selected Simple Substitution cipher examples. The “bad guy”
in this case has the advantage of knowing that the plaintext is in English and it’s
encrypted using a Simple Substitution Cipher.

Example 1: G WR W RWL

The existence of only two one-letter words in English makes it easy to deduce
that either G represents A and W represents I or vice versa. It then follows
that G is unlikely to represent A and therefore the firmly results in the
message being I AM A MA. This leaves us with trying to figure out L. The way
English is structured limits the meaningful probable letters especially if we
assume that this message is a full sentence.

Based on this we can be sure that the plaintext is I AM A MAN by mere

simple reasoning without even using cryptanalytic methods. Without
even being in possession of the key, the probable keys have been
reduced to 22!. It is important here to note that this only seems feas-
ible because the message is short, if how-ever this was part of a
long paragraph it would be impractical to determine the key. By group
-ing the characters in a cryptogram into groups of say four or five,
the in-formation about the word sizes which indicate where a word
starts and ends could be eluded.

Example 2: HKC

Apart from the fact that this cipher text is written in the English language
there is not much to go on. However, when a process of elimination which is
dependent on the way that English is structured is carried out, we can firmly
disqualify keys that would simultaneously encrypt Z as H, Q as K, and K as C.

Needless to say we are still faced with a large number of probable keys making
the interception of this key almost immaterial. All in all this proves that a
three letter cryptogram which is encrypted using a Simple substitution may
securely be transmitted without fear of it being decrypted if intercepted.

Example 3: HATTPT

Assuming that this is a complete six letter word, then it definitely restricts
the probable number of plaintext that can meaningfully correspond to T because
of the way word endings are structured in English. Furthermore assuming that
T or P represents vowels, then all probable outcomes can be listed. We can
come up with words such as CHEESE, MISSES, and CANNON.

23
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

aCTIvITY
Can you create an application programming by C or Java to perform the
Cryptanalysis of simple substitution?

1.5 thE pLaYfaIR CIphER

At the commencement of the 20th Century,

the British war office used a Bigram Cipher
which was invented by Wheatstone and Play-
fair called Playfair Cipher as shown in
Figure 1.10.

This type of cipher groups the letters in

twos instead of grouping individually.
The key is a 5 by 5 square which is
made up of the 25 letter of the alphabet
excluding J. This is equivalent to 25! or

15, 511, 210, 043, 330, 985, 984, 000, 000 keys. Figure 1.10: Example of playfair cipher

The following steps have to be taken prior to encryption:

As an illustration the key below was chosen randomly.

24
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

For sake of clarity and better understanding a sixth row which the same as first row
and a sixth column which is the same as the first column is added to the 5 by 5 square.
This is shown in the diagram below.

The rule for encryption is as shown in Figure 1.11.

1 If the two letters lie in the same row of the key then each letter is replaced
by the one on its right in the extended key.

2 If two letters lie in the same column of the key then each letter is replaced by the
one below it in the extended key.

If the two letters are not in the same row or column then the first letter is
3
replaced by the letter that is in the row of the first letter and the column
of the second letter. The second letter is replaced by the fourth corner of
the rectangle formed by the three letters used so far.

Figure 1.11: Encryption rules

As an example the message; GOOD BROOMS SWEEP CLEAN shall be encrypted as

follows:

A quick look at this message shows that no Js are present so we move on to the next step
which allows to Zs appropriately. The following is what we get:

GO OD BR OZ OM SZ SW EZ EP CL EA NZ

Therefore, GO becomes FP; OD becomes UT; OM becomes PO. The complete cipher text is;

FP UT EC UW PO DV TV BV CM BG CS DY

A key phrase following the same procedure as with Simple Substitution Cipher is also
used in the construction of the Playfair Cipher. For instance using UNIVERSITY OF
LONDON as the key phrase after getting rid of repeated letters gives UNIVERSTYOFLD
and the key can be set out as shown in the next diagram.

25
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

In an effort to illustrate decryption, we use the cryptogram MBOUBTZE. We are also

fortunate to have extra information which states that the plaintext is a word which
depicts the reader’s state of mind and is seven letters long. The course of action
taken to decrypt the plaintext is to simply do the reverse of the encryption procedure
using the key provided below.

1.5.1 Homophonic Coding

The extension of the alphabet by introducing additional characters for the most
frequently used letters (A, E, N, O, R, T) of the English alphabet are represented
by more than one cipher text character is called Homophonic Coding. This cipher is
used to remove some of the weaknesses of the Simple Substitution Cipher.

In our illustration we use numerical randomising elements which are basically the
additional characters. This is shown in Figure 1.12.

Figure 1.12: Example of homophonic cryptogram

Supposing the word TEETH is our plain text, we can then represent the two Es with
different cipher text characters. The cipher text would appear as 24 27 13 08 31.
This ought to confuse anyone who is not in possession of the key.

In this case, the two numbers representing E take up approximately 6 per cent of the
cryptogram. This clearly reduces the expected incidence of the letter E and flattens
the frequency histogram. In doing this the Homophonic coding reduces the chances for
a statistical attack.

26
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

Note 1

In order to differentiate between each character from the other, for instance
‘twelve’ and ‘one followed by two’, care must be taken when writing the cipher
text in this notation. Therefore the use of spacing between each variable is
very necessary.

Note 2

Unlike Simple Substitution ciphers, breaking the homophonic coding cipher

necessitates a lot of persistence and in some case sheer luck. For those
who like a challenge, the following cryptogram might be worth trying.

A few extra details are provided to help solve this cryptogram. These are;

1 The English plaintext was encrypted using Homophonic coding.

2 The cipher text characters have been divided into groups of five characters.

3 This is to remove the chances of the attacker simply using reason to pick out
words based on their length like one letter words.

Unfortunately the key is not known making the task even more intimidating. (Those
with a “faint heart” are not obliged to try.)

27
INtRODUCtION tO CRYptOGRaphY l ChaptER 1

28
ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

1.6 pOLYaLphaBEtIC CIphERS

Given more time and resources an interceptor may be able to compile a dictionary of
corresponding plaintext and ciphertext pairs for a given key. This is possible because
as much as some of the plaintext maybe represented by more than one ciphertext characters
and a good number of plaintext will uniquely correspond to one plaintext character. In
short even if the homophonic cipher is used to flatten the frequency histogram the risk
of an interceptor decrypting the ciphertext is still prominent.

In trying to reduce this risk, a polyalphabetic cipher is used as shown in Figure 1.13.
It improves upon the Homophonic cipher by varying the ciphertext character replacing a
particular plaintext letter within a cryptogram.

Figure 1.13: Example of polyalphabetic cipher

Source: http://enchantedmind.com/images/creative_cryptography_graphic_b.gif

This variation may depend on the plaintext character’s location in the plaintext message
or the content of the plaintext that precedes it. Therefore, in this cipher identical
ciphertext characters may represent dissimilar plaintext letters which is not possible
with homophonic coding.

Once again we must point out that the simple examples of these ciphers that we describe
are no longer used. However, we discuss them in some detail so that we can then illustrate
a number of weaknesses that the modern algorithm designer has to avoid.

29
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

As with our earlier examples, we include them to illustrate a number of cryptanalytic

techniques and because they enable us to set exercises which are both informative and
enjoyable.

1.7 VIGENERE CIphERS

In the sixteenth century, a polyalphabetic substitution cipher called Vigenere Cipher was
put forward by Blaise de Vigenere. It is based on the following Table 1.3.

Table 1.3: Example of an Vigenere Cipher

Note that each row of the table corresponds to a Caesar Cipher. The first row is a
shift of 0; the second is a shift of 1; and the last is a shift of 25.

The Vigenere cipher utilises the above table together with a keyword for encryption.
For example, to encrypt the message below:

30
ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

TO BE OR NOT TO BE THAT IS THE QUESTION

Using RELATIONS as the keyword. Since the message is longer than the keyword, we have
to repeat the keyword several times in order for fit into the number of characters
contained in the message. Then derive the ciphertext using the tableau, for each letter
in the plaintext, one finds the intersection of the row given by the corresponding key-
word letter and the column given by the plaintext letter itself to pick out the cipher-
text letter.

Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL

Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION
Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY

To decrypt the message a similar procedure as encryption is followed, only in this

case the repeated keyword and the ciphertext is used to obtain the plaintext from
the on the table. This is illustrated below:

Keyword: RELAT IONSR ELATI ONSRE LATIO NSREL

Ciphertext: KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY
Plaintext: TOBEO RNOTT OBETH ATIST HEQUE STION

This time keyword letters are used to pick a column of the table and then traced down
the column to the row containing the ciphertext letter. The index of that row is the
plaintext letter.

The strength of the Vigenere cipher against frequency analysis can be seen by examining
the above ciphertext. Note that there are 7 ‘T’s in the plaintext message and that they
have been encrypted by ‘H,’ ‘L,’ ‘K,’ ‘M,’ ‘G,’ ‘X,’ and ‘L’ respectively.

This successfully masks the frequency characteristics of the English ‘T.’ One way of
looking at this is to notice that each letter of our keyword RELATIONS picks out 1 of
the 26 possible substitution alphabets given in the Vigenere tableau. Thus, any message
encrypted by a Vigenere cipher is a collection of as many simple substitution ciphers
as there are letters in the keyword.

Even though the Vigenere cipher has all the features of a useful field cipher i.e.,
easily transportable key and tableau, requires no special apparatus, easy to apply,
etc., it did not catch on its day. A variation of it, known as the Gronsfeld Cipher,
did catch on in Germany and was widely used in Central Europe.

The Gronsfeld variant used the digits of a numerical key instead of letters of keyword,
but remained unchanged in all other respects. So, in fact the Gronsfeld is a weaker

31
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

technique than Vigenere since it only uses 10 substitute alphabets (one per digit 0..9)
instead of the 26 used by Vigenere.

aCTIvITY
Can you create an application programming by C or Java to perform the
Cryptanalysis of Vigenere Ciphers?

1.8 tRaNSpOSItION CIphERS

Transposition Ciphers unlike simple substitution ciphers use the technique of

transposing the order in which the letters are written. In order to appreciate
the difference between substituting letters, or blocks of letters, with other
letters or blocks and transposition of letters we give an illustration.

Using a short key whose length is five letters for encryption, we begin by
writing the key in rows of 5 letters followed by writing the letters of the first
column, then the second column and so on. Then add Zs at the end of plaintext,
in the event that total number of characters in the plaintext is not a multiple
of 5 (as is the case with the given example). Working through an example will
clarify the procedure more.

WHAT WAS THE WEATHER LIKE ON FRIDAY is the example message given.
In order to encrypt this message we start by splitting it into rows or five
letters each as shown below:

Since the last row only has four characters we therefore add a Z to give us the following:

32
 ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

We then read down column by column to generate the following ciphertext:

WAWEEIHSERODATALNATHTIFYWEHKRZ

To obtain the decryption key we merely divide the length of the message by the key.
In this case we divide 30 by 5 to get 6. The deciphering algorithm is then identical
to encryption. So, for this example, we write the cryptogram in rows of 6 to get:

By reading down column by column we can reproduce the original plaintext.

The fact that the key must be a divisor of the ciphertext length makes this cipher
system easy to break. Just by merely counting the number of characters in the crypto-
gram and then trying each divisor one after the other the interceptor can success-
fully break the cipher.

aCTIvITY
Can you create an application programming by C or Java to perform the
Cryptanalysis of Transposition Ciphers?

1.9 SUpER-ENCRYptION

As demonstrated in the previous sections of this chapter, the illustrated ciphers are
simple and can successfully be broken by a determined attacker. In order to deter even
a determined attacker super-encryption can be used. Super-encryption is the process of
combining two or more weak ciphers to obtain one that is significantly harder to break.

For instance if we wish to use Simple Substitution Cipher and a Transposition Cipher,
we begin by encrypting our plaintext with the Simple Substitution Cipher and then use
the outcome as input to encrypt using the Transposition Cipher.

33
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

Suppose the message “ROYAL HOLLOWAY” is super-encrypted initially using a Caesar

Cipher with key 2 and then followed by using a Transposition Cipher with key 4.
Encryption using the Caesar Cipher gives the following outcome:

While the Transposition Cipher outputs the following result:

The importance of Super-encryption cannot be over emphasised as it has laid the

foundation of most modern strong encryption algorithms which have emerged out of a
combination of relatively comparatively “fragile” algorithms.

SUMMaRY

1. In this chapter, we have learned Cryptography, cryptanalysis and types of

ciphers.

2. In deed there are several aspects that influence a successful attack on an

algorithm. It is also clear that just as being in possession of the decryption
key is essential so is the underlying language. A highly structured language
makes it possible to determine a particular message without needing to discover
the whole key.

3. The examples given in this chapter clearly indicate that successful decryption
of intercepted ciphertext can be measured by how the underlying language is
structured.

4. Cryptography is the science of using mathematics to encrypt and decrypt data.

Cryptography enables to store sensitive information or transmit it across
insecure networks (like the Internet). So that it cannot be read by anyone
except the intended recipient.

5. Classical cryptanalysis involves an interesting combination of analytical

reasoning, application of mathematical tools, pattern finding, patience,
determination and luck.

34
ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

6. A cryptographic algorithm or cipher, is a mathematical function used in the

encryption and decryption process. A cryptographic algorithm works in combina-
tion with a key to encrypt the plaintext.

7. The key can be in form of a word, number or phrase. The same plaintext en-
crypts to different ciphertext with different keys.

8. A substitution cipher replaces one letter or character for another using a

rule set. It involves twirling one dial around the other so that the letters
of the alphabet do not match up.

9. One of the oldest known ciphers is called a transposition cipher. This type
of cipher changes the order of the letters of the original message. One method
is to write the message in a series of columns and rows in a grid or even
writing the message backwards.

GLOSSaRY

Cipher - Another word for algorithm.

Ciphertext - Encrypted data.

Cryptography - Cryptography is the practice and study of hiding

information.

Decryption - The process of turning ciphertext into plaintext.

Eavesdropper - One who listens in on another person’s private

conversation.

Key - A complex sequence of alpha-numeric characters,

produced by the algorithm, which allows you to
scramble and unscramble data.

Plaintext - Also known as clear text is usable data. It is data

either before encryption or after successful decryption.

35
 INtRODUCtION tO CRYptOGRaphY l ChaptER 1

REfERENCE

William, S. (1999). Cryptography and Network Security (4th ed.).

Alfred, J. Menezes, Paul, C. Van Oorschot, & Scott, A. Vanstone. (1996). Applied Cryp-
tography.

Fred Piper, & Sean Murphy. (2002). Cryptography: A Very Short Introduction. Oxford
University Press.

Douglas, R. Stinson. Cryptography: Theory and Practice.

Mihir Bellare, & Phillip Rogaway. (2005). Introduction to Modern Cryptography.

DISCUSSION QUEStIONS

1. What are the essential ingredients of a symmetric cipher?

2. What are the two basic functions used in encryption algorithms?

3. How many keys are required for two people to communicate via a cipher?

4. What is the difference between a block cipher and a stream cipher?

5. What are the two general approaches to attacking a cipher?

6. What is the difference between an unconditionally secure cipher and a computatio-

nally secure cipher?

7. Briefly define the Caesar cipher.

8. Briefly define the monoalphabetic cipher.

9. Briefly define the Playfair cipher.

10. What is the difference between a monoalphabetic cipher and a polyalphabetic cipher?

11. What are two problems with the one-time pad?

12. What is a transposition cipher?

36
ChaptER 1 l INtRODUCtION tO CRYptOGRaphY

13. What is steganography?

14. How many one-to-one affine Caesar ciphers are there?

15. A ciphertext has been generated with an affine cipher. The most frequent letter
of the ciphertext is ‘B’ and the second most frequent letter of the ciphertext
is ‘U’. Break this code.

16. Using this Playfair matrix:

M F H I/J K
U N O P Q
Z V W X Y
E L A R G
D S T B C

Encrypt this message: “Must see you over Cadogan West.”

17. How many possible keys does the Playfair cipher have? Ignore the fact that some
keys might produce identical encryption results. Express your answer as an
approximate power of 2.

18. Using the Vigenere cipher, encrypt the word “explanation” using the key log.

37