Chapter 2.

Elementary Cryptography

Contents
Concepts of encryption
Cryptanalysis: how encryption systems are "broken"
Cryptography System:
Symmetric (secret key) encryption and the DES and AES
algorithms
Asymmetric (public key) encryption and the RSA algorithm
Cryptography secret writing is the strongest tool for controlling
against many kinds of security threats.
Well-disguised data cannot be read, modified, or fabricated easily.
Cryptography is rooted in higher mathematics: group and field
theory, computational complexity, and even real analysis,
not to mention probability and statistics
We introduce the basic principles of encryption with two simple
encryption methods: substitution and transposition.
Next, we explore how they can be expanded and improved to
create stronger, more sophisticated protection.
We analyze techniques used to break through the protective
scheme and reveal the original text. Three very popular
algorithms are in use today: DES, AES, and RSA
2.1. Terminology and Background
Consider the steps involved in sending messages from a sender,
S, to a recipient, R. If S entrusts the message to T, who then
delivers it to R, T then becomes the transmission medium.
If an outsider, O, wants to access the message (to read, change,
or even destroy it), we call O an interceptor or intruder.
Any time after S transmits it via T, the message is vulnerable to
exploitation, and O might try to access the message in any of the
following ways:
Block it, by preventing its reaching R, thereby affecting the
availability of the message.
Intercept it, by reading or listening to the message, thereby
affecting the confidentiality of the message.
Modify it, by seizing the message and changing it in some way,
affecting the message's integrity.
Fabricate an authentic-looking message, arranging for it to be
delivered as if it came from S, thereby also affecting the integrity
of the message.
Encryption is a technique that can address all these problems.
Encryption, probably the most fundamental building block of
secure computing, is a means of maintaining secure data in an
insecure environment.
We will study encryption as a security technique, and we see how
it is used in protecting programs, databases, networks, and
Electronic communications
Terminology
Cryptography: is “the science of coding and decoding
messages so as to keep these messages secure”.
 Schemes for encryption and decryption
Encryption is the process of encoding a message
Decryption is the reverse process, transforming an encrypted
message back into its normal, original form.
Alternatively, the terms encode and decode or encipher and
decipher are used instead of encrypt and decrypt.
That is, we say that we encode, encrypt, or encipher the original
message to hide its meaning.
Then, we decode, decrypt, or decipher it to reveal the original
message.
A system for encryption and decryption is called a cryptosystem.
 Secret key: Used to set some or all of the various parameters
used by the encryption algorithm.
In a classical (symmetric key) cryptography, the same secret key is
used for encryption and decryption.
The original form of a message is known as plaintext, and the
encrypted form is called cipher text.
Cryptanalysis : The study of “breaking the code”.
 is the art and science of “cracking codes, decoding secrets,
violating authentication schemes, and in general, breaking
cryptographic protocols,” all without knowing the secret key.
Systems for encrypting information are referred to as cryptosystems.
Cryptology: Cryptography and cryptanalysis together constitute
the area of cryptology.
For convenience, we denote a plaintext message P as a sequence of
individual characters P = <p1, p2, …, pn>.
Similarly, ciphertext is written as C = <c1, c2, …, cm>. For
instance, the plaintext message "I want cookies" can be denoted as
the message string <I, ,w,a,n,t, , c,o,o,k,i,e,s>.
It can be transformed into cipher text <c1, c2, …, c14>, and the
encryption algorithm tells us how the transformation is done.
Cryptography has five ingredients:
• Plaintext
• Encryption algorithm
• Secret Key
• Ciphertext
• Decryption algorithm
Security depends on the secrecy of the key, not the
secrecy of the algorithm
Description:
A sender S wanting to transmit message M to a
receiver R
To protect the message M, the sender first encrypts
it into an unintelligible message M‟
After receipt of M‟, R decrypts the message to
obtain M
M is called the plaintext
 What we want to encrypt

M‟ is called the ciphertext

 The encrypted output
Notation:

Given
P=Plaintext
C=CipherText
 k=key shared by sender and receiver
C = EK (P) Encryption
P = DK (C) Decryption
Representing Characters
We want to study ways of encrypting any computer material,
whether it is written as ASCII characters, binary data, object
code, or a control stream.
However, to simplify the explanations, we begin with the
encryption of messages written in the standard 26-letter
English[2] alphabet, A through Z.
 There are many types of encryption. In the next two sections
we look at two simple forms of encryption:
 Substitutions, in which one letter is exchanged for another, and

 Transpositions, in which the order of the letters is rearranged.

A)Substitution Ciphers
use a correspondence table with which to substitute a character
or symbol for each character of the original message.
This technique is called a monoalphabetic cipher or simple
substitution.
A substitution is an acceptable way of encrypting text and there
are several kinds of substitution ciphers.
The Caesar Cipher-early example:
The Caesar cipher has an important place in history.
The earliest known example of a substitution cipher in which
each character of a message is replaced by a character three
position down in the alphabet.
Julius Caesar is said to have been the first to use this
scheme, in which each letter is translated to the letter a
fixed number of places after it in the alphabet.
Caesar used a shift of 3, so plaintext letter pi was
enciphered as ciphertext letter ci by the rule
ci = E(pi) = pi + 3
Using this encryption, the message
IMPOSSIBLE
would be encoded as
IMPOSSIBLE
l p s r v v l eoh
Cryptanalysis of the Caesar Cipher
Let us take a closer look at the result of applying Caesar's
encryption technique to "TREATY IMPOSSIBLE.“
If we did not know the plaintext and were trying to guess it, we
would have many clues from the ciphertext.
 If we represent each letter of the alphabet by an
integer that corresponds to its position in the
alphabet:
The formula for replacing each character „p‟ of the
plaintext with a character „c‟ of the ciphertext can be
expressed as:
c = E3(p ) = (p + 3) mod 26
A more general version of this cipher that allows
for any degree of shift:
 c = Ek(p ) = (p + k) mod 26
The formula for decryption would be
 p = Dk(c ) = (c - k) mod 26
In these formulas
 „k‟ is the secret key. The symbols ‟E‟ and ‟D‟ stand for
Encryption and Decryption respectively, and p and c are
characters in the plain and cipher text respectively.
Other Substitutions
One-Time Pads
Long Random Number Sequences
The Vernam Cipher
B)Transpositions (Permutations)
A transposition is an encryption in which the letters of the
message are rearranged.
With transposition, the cryptography aims for diffusion, widely
spreading the information from the message or the key across
the cipher text.
Columnar Transpositions
The columnar transposition is a rearrangement of the characters
of the plaintext into columns.
The following set of characters is a five-column transposition.
The plaintext characters are written in rows of five and arranged
one row after another, as shown here.
 For instance, suppose you want to write the plaintext message
THIS IS A MESSAGE TO SHOW HOW A COLUMNAR
TRANSPOSITION WORKS. We arrange the letters in five columns as
T H I S I
S A M E S
T H I S I
S A G E T
O S H OW S A M E S
H O W A C
S A G E T
O L U M N
A R T R A O S H O W
N S P O S H O W A C
I T I O N
W O R K S O L U M N
A R T R A
N S P O S
I T I O N
W O R K S
The resulting ciphertext would then be read down the columns as
tssoh oaniw haaso lrsto imghw
utpir seeoa mrook istwc nasns
 Cryptography System

There are two fundamentally different

cryptographic systems
Symmetric cryptosystem/ Private key
Asymmetric cryptosystem/ Public key
 Cryptography
Symmetric Cryptosystem

Also called secret-key/private-key cryptosystem

The study of symmetric cryptosystems is referred to as
symmetric cryptography
The same key is used to encrypt and decrypt a
message
 P = DK [EK (P) ]
Have been used for centuries in a variety of forms
The key has to be kept secret
The key has to be communicated using a secure
channel
 Prior to 1970, all cryptosystems employed symmetric key
encryption.
Even today, its relevance is very high and it is being used
extensively in many cryptosystems.
The salient features of cryptosystem based on symmetric key
encryption are −
 Persons using symmetric key encryption must share a common key
prior to exchange of information.
Keys are recommended to be changed regularly to prevent any
attack on the system.
A robust mechanism needs to exist to exchange the key between
the communicating parties. As keys are required to be changed
regularly, this mechanism becomes expensive and cumbersome.
 In a group of n people, to enable two-party communication
between any two persons, the number of keys required for group is
n × n – 1/2.
Length of Key number of bits in this encryption is smaller and
hence, process of encryption- decryption is faster than asymmetric
key encryption.
Processing power of computer system required to run symmetric
algorithm is less
Challenge of Symmetric Key Cryptosystem
There are two restrictive challenges of employing symmetric key
cryptography.
Key establishment − Before any communication, both the sender and
the receiver need to agree on a secret symmetric key. It requires a secure
key establishment mechanism in place.
Trust Issue − Since the sender and the receiver use the same symmetric
key, there is an implicit requirement that the sender and the receiver
„trust’ each other.
A symmetric encryption schemes can be classified in to :
Block Ciphers
In this scheme, the plain binary text is processed in blocks
groups of bits at a time; i.e. a block of plaintext bits is selected, a
series of operations is performed on this block to generate a
block of cipher text bits.
The number of bits in a block is fixed. For example, the schemes
DES and AES have block sizes of 64 and 128, respectively.
Stream Ciphers
In this scheme, the plaintext is processed one bit at a time i.e.
one bit of plaintext is taken, and a series of operations is
performed on it to generate one bit of cipher text.
Block Cipher Schemes
There is a vast number of block ciphers schemes that are in use.
Many of them are publically known.
Most popular and prominent block ciphers are listed below.
Digital Encryption Standard
Double DES
Triple DES
Advanced Encryption Standard AES
FEISTEL BLOCK CIPHER
Feistel Cipher is not a specific scheme of block cipher.
It is a design model from which many different block ciphers are
derived. DES is just one example of a Feistel Cipher.
A cryptographic system based on Feistel cipher structure uses the
same algorithm for both encryption and decryption.
Encryption Process
The encryption process uses the Feistel structure consisting multiple
rounds of processing of the plaintext, each round consisting of a
“substitution” step followed by a permutation step.
Feistel Structure is shown in the following illustration
The input block to each round is divided into two halves that can
be denoted as L and R for the left half and the right half.
In each round, the right half of the block, R, goes through
unchanged. But the left half, L, goes through an operation that
depends on R and the encryption key. First, we apply an
encrypting function „f‟ that takes two input − the key K and R.
The function produces the output fR, K. Then, we XOR the
output of the mathematical function with L.
In real implementation of the Feistel Cipher, such as DES,
instead of using the whole encryption key during each round, a
round-dependent key a sub key is derived from the encryption
key.
This means that each round uses a different key, although all
these sub keys are related to the original key.
The permutation step at the end of each round swaps the
modified L and unmodified R. Therefore, the L for the next
round would be R of the current round. And R for the next
round be the output L of the current round.
Above substitution and permutation steps form a „round‟. The
number of rounds are specified by the algorithm design.
Once the last round is completed then the two sub blocks, „R‟
and „L‟ are concatenated in this order to form the ciphertext
block.
Decryption Process
The process of decryption in Feistel cipher is almost similar.
Instead of starting with a block of plaintext, the ciphertext block
is fed into the start of the Feistel structure and then the process
thereafter is exactly the same as described in the given
illustration.
The process is said to be almost similar and not exactly same. In
the case of decryption, the only difference is that the subkeys
used in encryption are used in the reverse order.
The final swapping of „L‟ and „R‟ in last step of the Feistel Cipher
is essential.
If these are not swapped then the resulting ciphertext could not
be decrypted using the same algorithm.
Number of Rounds
The number of rounds used in a Feistel Cipher depends on
desired security from the system.
More number of rounds provide more secure system. But at the
same time, more rounds mean the inefficient slow encryption
and decryption processes.
Number of rounds in the systems thus depend upon efficiency–
security tradeoff.
 Cryptography
DES - Popular Example of Symmetric Cryptosystem
In 1973, the NBS (National Bureau of Standards, now called NIST -
National Institute of Standards and Technology) published a request for
an encryption algorithm that would meet the following criteria:
have a high security level
be easily understood
not depend on the algorithm's confidentiality
be adaptable and economical
be efficient and exportable

In late 1974, IBM proposed "Lucifer", which was then modified by NSA
(National Security Agency) in 1976 to become the DES (Data Encryption
Standard).
DES was approved by the NBS in 1978. The DES was standardized by
the ANSI under the name of ANSI X3.92, also known as DEA (Data
Encryption Algorithm).
 Cryptography
Asymmetric/Public key/ Cryptosystem
Also called public-key cryptosystem
 keys for encryption and decryption are different but form a unique pair
 P = DKD [EKE (P) ]
 Only one of the keys need to be private while the other can be public
Invented by Diffie and Hellman in 1976

Uses Mathematical functions whose inverse is not known by

Mathematicians of the day
It is a revolutionary concept since it avoids the need of using a
secure channel to communicate the key
It has made cryptography available for the general public and made
many of today’s on-line application feasible
The salient features of this encryption scheme are as follows :
Every user in this system needs to have a pair of dissimilar
keys, private key and public key.

These keys are mathematically related − when one key is

used for encryption, the other can decrypt the ciphertext
back to the original plaintext.

It requires to put the public key in public repository and the

private key as a well-guarded secret. Hence, this scheme of
encryption is also called Public Key Encryption.
Though public and private keys of the user are related, it is
computationally not feasible to find one from another. This is
a strength of this scheme.
When Host1 needs to send data to Host2, he obtains the
public key of Host2 from repository, encrypts the data, and
transmits.
Host2 uses his private key to extract the plaintext.
Length of Keys number of bits in this encryption is large and
hence, the process of encryption-decryption is slower than
symmetric key encryption.
Processing power of computer system required to run
asymmetric algorithm is higher.
 Cryptography
Public-key Cryptosystem
Which one of the encryption or decryption key is
made public depends on the use of the key
 If Hana wants to send a confidential message to
Ahmed
 Sheencrypts the message using Ahmed’s public key
 Send the message
 Ahmed will then decode it using his own private key

 On the other hand, if Ahmed needs to make sure that

a message sent by Hana really comes from her, how
can he make that?
 Cryptography
Public-key Cryptosystem

Using digital signature

 Hana has to first encrypt a digital signature using her
private key
 Then encrypt the message (signature included) with
Ahmed’s public key
 Sends the encrypted message to Ahmed
 Ahmed decrypts the message using his private key
 Ahmed then decrypts the signature using Hana’s
public key
 If successful, he insures that it comes from Hana
 Cryptography
Public-key Cryptosystem: Example RSA
RSA is from R. Rivesh, A. Shamir and L. Aldermen
Principle: No mathematical method is yet known to efficiently
find the prime factors of large numbers
In RSA, the private and public keys are constructed from very
large prime numbers (consisting of hundred of decimal digits)
One of the keys can be made public

Breaking RSA is equivalent to finding the prime factors: this is

know to be computationally infeasible
It is only the person who has produced the keys from the prime
number who can easily decrypt the messages