Chapter 1

Introduction to Cryptography

Dalilah Abdullah
Information Systems Section
Malaysian Institute of Information Technology
Universiti Kuala Lumpur
dalilah@miit.unikl.edu.my
Owned by : Dr Shamsul Anuar Mokhtar

Introduction

Cryptography (or cryptology; derived from Greek

krypts "hidden," and the verb grfo
"write" or legein "to speak") is the study of
message secrecy.

In modern times, cryptography is considered to be a

branch of both mathematics and computer
science, and is affiliated closely with information
theory, computer security, and engineering.

Cryptography is used in applications present in

technologically advanced societies; examples include
the security of ATM cards, computer passwords, and
electronic commerce, which all depend on
cryptography.
Slide no. 2

Basic Concept

Encryption is the process of converting ordinary

information (plaintext) into unintelligible gibberish
(i.e, ciphertext).

Decryption is the reverse, moving from

unintelligible ciphertext to plaintext.

P = D(E(P))

Slide no. 3

Introduction

Before the modern era, cryptography was concerned

solely with message confidentiality.

In recent decades, the field has expanded beyond

confidentiality concerns to include techniques for
message integrity checking, sender/receiver identity
authentication, digital signatures, interactive proofs,
and secure computation, amongst others.

The earliest forms of secret writing required little

more than local pen and paper analogs, as most
people could not read.

Dr. Shamsul Anuar Mokhtar

Slide no. 4

Introduction

Cryptography has a long and fascinating history.

Cryptography can be traced from its initial and limited

use by the Egyptians some 4000 years ago, to the
twentieth century where it played a crucial role in the
outcome of both world wars.

Before the 1960s, the predominant practitioners of the

art were those associated with the military, the
diplomatic service and government in general.
Cryptography was used as a tool to protect national
secrets and strategies.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 5

Introduction

The proliferation of computers and communications

systems in the 1960s brought with it a demand from the
private sector for means to protect information in digital
form and to provide security services.

Beginning with the work of Feistel at IBM in the early

1970s and culminating in 1977 with the adoption as a
U.S. Federal Information Processing Standard for
encrypting unclassified information, DES, the Data
Encryption Standard, is the most well-known
cryptographic mechanism in history.

It remains the standard means for securing electronic

commerce for many financial institutions around the
world.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 6

Introduction

The most striking development in the history of

cryptography came in 1976 when Diffie and Hellman
published New Directions in Cryptography (exchange
key).

This paper introduced the revolutionary concept of

public-key cryptography and also provided a new and
ingenious method for key exchange, the security of
which is based on the intractability of the discrete
logarithm problem.

Although the authors had no practical realisation of a

public-key encryption scheme at the time, the idea was
clear and it generated extensive interest and activity in
the cryptographic community.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 7

Introduction

In 1978 Rivest, Shamir, and Adleman discovered the

first practical public-key encryption and signature
scheme, now referred to as RSA.

The RSA scheme is based on another hard mathematical

problem, the intractability of factoring large integers.
This application of a hard mathematical problem to
cryptography revitalised efforts to find more efficient
methods to factor.

The 1980s saw major advances in this area but none

which rendered the RSA system insecure.

Another class of powerful and practical public-key

schemes was found by El Gamal in 1985. These are also
based on the discrete logarithm problem.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 8

Introduction

One of the most significant contributions provided by

public-key cryptography is the digital signature.

In 1991 the first international standard for digital

signatures (ISO/IEC 9796) was adopted. It is based on
the RSA public-key scheme. In 1994 the U.S.
Government adopted the Digital Signature Standard, a
mechanism based on the El Gamal public key scheme.

The search for new public-key schemes, improvements

to existing cryptographic mechanisms, and proofs of
security continues at a rapid pace. Various standards
and infrastructures involving cryptography are being put
in place. Security products are being developed to
address the security needs of an information intensive
society.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 9

Classical ciphers
The main classical cipher types are:

Transposition/permutation ciphers, which

rearrange the order of letters in a message (e.g.
'help me' becomes 'ehpl em' in a trivially simple
rearrangement scheme)

Substitution ciphers, which systematically replace

letters or groups of letters with other letters or
groups of letters (e.g., 'fly at once' becomes 'gmz bu
podf' by replacing each letter with the one following
it in the alphabet).

Dr. Shamsul Anuar Mokhtar

Slide no. 10

Classical ciphers (contd.)

A scytale (rhymes with Italy) is a tool used to

perform a transposition cipher, consisting of a
cylinder with a strip of leather wound around it on
which is written a message.

The ancient Greeks, and the Spartans in particular,

are said to have used this cipher to communicate
during military campaigns.

Dr. Shamsul Anuar Mokhtar

Slide no. 11

Classical ciphers (contd.)

In a columnar transposition, the message is

written out in rows of a fixed length, and then read
out again column by column, and the columns are
chosen in some scrambled order.

Both the length of the rows and the permutation of

the columns are usually defined by a keyword.

Dr. Shamsul Anuar Mokhtar

Slide no. 12

Classical ciphers (contd.)

For example, the word ZEBRAS is of length 6 (so the

rows are of length 6), and the permutation is defined
by the alphabetical order of the letters in the
keyword. In this case, the order would be "6 3 2 4 1
5".

Suppose we use the keyword ZEBRAS and the

message WE ARE DISCOVERED. FLEE AT ONCE.
6 3 2 4 1
W E AR E
I S C O V
R E D F L
E A T O N
E Q K J E

Dr. Shamsul Anuar Mokhtar

5
D
E
E
C
U

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

Slide no. 13

Classical ciphers Caesar cipher

A Caesar cipher is a type of substitution cipher in

which each letter in the plaintext is replaced by a
letter some fixed number of positions further down
the alphabet. For example, with a shift of 3, A would
be replaced by D, B would become E, and so on. The
method is named after Julius Caesar, who used it to
communicate with his generals.

Dr. Shamsul Anuar Mokhtar

Slide no. 14

Classical ciphers Vignere cipher

The Vigenre cipher is a method of encryption that

uses a series of different Caesar ciphers based on the
letters of a keyword. It is a simple form of
polyalphabetic substitution.

The Vigenre cipher consists of several Caesar

ciphers in sequence with different shift values.

To encipher, a table of alphabets can be used,

termed a tabula recta, Vigenre square, or Vigenre
table. At different points in the encryption process,
the cipher uses a different alphabet from one of the
rows. The alphabet used at each point depends on a
repeating keyword.

Dr. Shamsul Anuar Mokhtar

Slide no. 15

Plaintext:
ATTACKATDAWN

Key:
LEMONLEMONLE
Ciphertext:
LXFOPVEFRNHR

Dr. Shamsul Anuar Mokhtar

Slide no. 16

Classical ciphers one-time pad

The one-time pad (OTP) is an encryption algorithm

where the plaintext is combined with a random key
or "pad" that is as long as the plaintext and used only
once.

If the key is truly random, never reused, and kept

secret, the one-time pad provides perfect secrecy.

The "pad" part of the name comes from early

implementations where the key material was
distributed as a pad of paper, so the top sheet could
be easily torn off and destroyed after use.

The key is used with the Vigenre table.

Dr. Shamsul Anuar Mokhtar

Slide no. 17

Classical ciphers one-time pad

Dr. Shamsul Anuar Mokhtar

Slide no. 18

Classical ciphers Vernam cipher

A Vernam cipher is a stream cipher in which the

plaintext is XORed with a random or pseudorandom
stream of data the same length to generate the
ciphertext.

If the stream of data is truly random and used only

once, this is the one-time pad.

Dr. Shamsul Anuar Mokhtar

Slide no. 19

Example: Encode VERNAM CIPHER

Plaintext

Numeric Eq.

21

17 13

12

15

17

+ Random Num. 76

48

16

82

44

03

58

11 60

05 48 88

= Sum

97

52

33

95

44

15

60

19 75

12 52 105

= mod 26

19

17

18

15

19

23 12

Ciphertext

VERNAM CIPHER TAHRSP ITXMAB

Dr. Shamsul Anuar Mokhtar

Slide no. 20

Cryptanalysis

Cryptanalysis (from the Greek krypts, "hidden",

and analein, "to loosen" or "to untie") is the study of
methods for obtaining the meaning of encrypted
information, without access to the secret information
which is normally required to do so.

Typically, this involves finding the secret key. In nontechnical language, this is the practice of
codebreaking or cracking the code, although these
phrases also have a specialised technical meaning.

Dr. Shamsul Anuar Mokhtar

Slide no. 21

Cryptanalysis (contd.)

The first known recorded

explanation of
cryptanalysis was given by
9th century Muslim
polymath Abu Yusuf Yaqub
ibn Ishaq al-Sabbah AlKindi in A Manuscript on

Deciphering Cryptographic
Messages.

This treatise includes a

description of the method
of frequency analysis.

Dr. Shamsul Anuar Mokhtar

Slide no. 22

Cryptanalysis (contd.)
A cryptanalysis can do any or all of six different things:

attempt to break a single message

attempt to recognise patterns in encrypted

messages, to be able to break subsequent ones by
applying a straightforward decryption algorithm

attempt to infer some meaning without even

breaking the encryption, such as noticing an unusual
frequency of communication or determining
something by whether the communication was short
or long

Dr. Shamsul Anuar Mokhtar

Slide no. 23

Cryptanalysis (contd.)

attempt to deduce the key, in order to break

subsequent messages easily

attempt to find weaknesses in the implementation or

environment of use of encryption

attempt to find general weaknesses in an encryption

algorithm, without necessarily having intercepted any
messages

Dr. Shamsul Anuar Mokhtar

Slide no. 24

Properties of Trustworthy Encryption Systems

It is based on sound mathematics.

It has been analysed by competent experts and

found to be sound.

It has stood the test of time.

Dr. Shamsul Anuar Mokhtar

Slide no. 25

Modern cryptographic basics

A cipher (or cypher) is a pair of algorithms which

perform this encryption and the reversing decryption.

The detailed operation of a cipher is controlled both

by the algorithm and, in each instance, by a key.

In modern cryptography, there are 3 types of

algorithms commonly used today:
Symmetric encryption algorithms
Asymmetric encryption algorithms
Hashing algorithms

Dr. Shamsul Anuar Mokhtar

Slide no. 26

Confusion and diffusion

Confusion refers to making the relationship

between the key and the ciphertext as complex and
involved as possible. Substitution (a plaintext
symbol is replaced by another) has been identified as
a mechanism for primarily confusion.

Diffusion refers to the property that redundancy in

the statistics of the plaintext is "dissipated" in the
statistics of the ciphertext. Transposition
(rearranging the order of symbols) is a technique for
diffusion, although other mechanisms are also used
in modern practice, such as linear transformations
(e.g. in Rijndael).

Dr. Shamsul Anuar Mokhtar

Slide no. 27

Confusion and diffusion (contd.)

Product ciphers use alternating substitution and

transposition phases to achieve both confusion and
diffusion respectively.

Dr. Shamsul Anuar Mokhtar

Slide no. 28

Stream and block ciphers

Stream Cipher:
Converting one symbol of plaintext immediately
into a symbol of ciphertext
The transformation depends only on the symbol,
the key and the control information of the
encipherment algorithm
Example: All substitution cipher algorithms
Block Cipher:
Encrypts a group of plaintext symbols as one block
In columnar transposition, the entire message is
translated as one block
Cryptography

Slide no. 29

Stream and block ciphers

Stream ciphers convert one symbol of plaintext

immediately into a symbol of ciphertext.
E.g.: Caesar cipher, Vernam cipher, Vigenere cipher

Dr. Shamsul Anuar Mokhtar

Slide no. 30

Stream and block ciphers (contd.)

Stream ciphers are often used in applications where

plaintext comes in quantities of unknowable length
for example, a secure wireless connection.

E.g. RC4, A5/1, A5/2, Chameleon, FISH, Helix,

ISAAC, MUGI, Panama, Phelix, Pike, SEAL, SOBER,
SOBER-128 and WAKE.

A5/1 is a stream cipher used to provide over-the-air

communication privacy in the GSM cellular telephone
standard. It was initially kept secret, but became
public knowledge through leaks and reverse
engineering. A number of serious weaknesses in the
cipher have been identified.

Dr. Shamsul Anuar Mokhtar

Slide no. 31

Stream and block ciphers (contd.)

Block ciphers encrypts a group of plaintext symbols

as one block.
E.g. Columnar transposition and other transpositions,
many commercial ciphers, such as DES, AES, RSA,
etc.

Dr. Shamsul Anuar Mokhtar

Slide no. 32

Stream and block ciphers (contd.)

Block ciphers
Dr. Shamsul Anuar Mokhtar

Slide no. 33

Comparison: Stream and Block Ciphers

Slide no. 34

Stream and block ciphers (contd.)

Advantages

Disadvantages

Stream Encryption
Algorithms
Speed of
transformation
Low error
propagation

Dr. Shamsul Anuar Mokhtar

Low diffusion
Susceptibility to
malicious insertions
and modifications

Block Encryption
Algorithms
High diffusion
Immunity to
insertion of
symbols

Slowness of
encryption
Error
propagation
Slide no. 35

Symmetric key algorithms

Symmetric encryption: uses same secret key to

encipher and decipher message.

Encryption methods can be extremely efficient,

requiring minimal processing.

The same key on both ends of the communication is

used to encrypt and decrypt messages.

Both sender and receiver must possess encryption

key.

If either copy of key is compromised, an intermediate

can decrypt and read messages.

Dr. Shamsul Anuar Mokhtar

Slide no. 36

Dr. Shamsul Anuar Mokhtar

Slide no. 37

Dr. Shamsul Anuar Mokhtar

Slide no. 38

Information Security and Cryptography

To introduce cryptography, an understanding of issues

related to information security in general is necessary.

Information security manifests itself in many ways

according to the situation and requirement.

Regardless of who is involved, to one degree or

another, all parties to a transaction must have
confidence that certain objectives associated with
information security have been met.

Some of these objectives of cryptography are listed as

follows:

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 39

Information Security and Cryptography

Privacy or confidentiality: keeping information secret

from all but those who are authorised to see it.

Data integrity: ensuring information has not been

altered by unauthorised or unknown means.

Entity authentication or identification: entity

authentication or identification (e.g., a person, a
computer terminal, a credit card, etc.).

Message authentication: corroborating the source of

information; also known as data origin authentication.

Signature: a means to bind information to an entity.

Authorisation: conveyance, to another entity, of

official sanction to do or be something.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 40

Information Security and Cryptography

Validation: a means to provide timeliness of

authorisation to use or manipulate information or
resources.

Access control: restricting access to resources to

privileged entities.

Certification: endorsement of information by a trusted

entity.

Timestamping: recording the time of creation or

existence of information.

Witnessing: verifying the creation or existence of

information by an entity other than the creator.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 41

Information Security and Cryptography

Receipt: acknowledgement that information has been

received.

Confirmation: acknowledgement that services have

been provided.

Ownership: a means to provide an entity with the

legal right to use or transfer a resource to others.

Anonymity: concealing the identity of an entity

involved in some process.

Non-repudiation: preventing the denial of previous

commitments or actions.

Revocation: retraction of certification or authorisation.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 42

Information Security and Cryptography

Cryptography is not the only means of providing

information security, but rather one set of techniques.

Over the centuries, an elaborate set of protocols and

mechanisms has been created to deal with information
security issues when the information is conveyed by
physical documents.

Often the objectives of information security cannot

solely be achieved through mathematical algorithms and
protocols alone, but require procedural techniques and
abidance of laws to achieve the desired result.

Dr. Shamsul Anuar Mokhtar

Cryptography

Slide no. 43

Next chapter
Symmetric-Key Cryptography

Dr. Shamsul Anuar Mokhtar

Information Systems Section
Malaysian Institute of Information Technology
Universiti Kuala Lumpur
shamsulanuar@miit.unikl.edu.my