Cryptography and Network Security

I Module

Introduction to Cryptography

Define Cryptology -This is the study of techniques for ensuring the secrecy and/or
authenticity of information. The two main branches of cryptology are cryptography, which is
the study of the design of such techniques; and cryptanalysis, which deals with the defeating
such techniques, to recover information, or f orging information that will be accepted as
authentic.

Computer Security – Generic name for the collection of tools designed to protect data and to
thwart hackers
Network Security – Measures to protect data during their transmission
Internet Security – easures to protect data during their transmission over a collection of
interconnected networks

2 Differnet Secuirty Attacks are

1. Passive Attacks
Two types of passive attacks are release of message contents and traffic analysis.
The release of message contents is easily understood (Figure a). A telephone conversation, an
electronic mail message, and a transferred file may contain sensitive or confidential information
A second type of passive attack, traffic analysis, is subtler (Figure b). Suppose that we had a
way of masking the contents of messages or other information traffic so that opponents, even if
they captured the message, could not extract the information from the message. The common
technique for masking contents is encryption

2. Active Attacks

It can be subdivided into four categories: masquerade, replay, modification of messages, and
denial of service.

A masquerade takes place when one entity pretends to be a different entity (Figure a). A
masquerade attack usually includes one of the other forms of active attack. For example,
authentication sequences can be captured and replayed after a valid authentication sequence
has taken place

Replay involves the passive capture of a data unit and its subsequent retransmission to
produce an unauthorized effect (Figure b)

Modification of messages simply means that some portion of a legitimate message is altered,
or that messages are delayed or reordered, to produce an unauthorized effect ( Figure c). For
example, a message meaning "Allow John Smith to read confidential file accounts" is modified to
mean "Allow Fred Brown to read confidential file accounts."

The denial of service prevents or inhibits the normal use or management of communications
facilities (Figure d). This attack may have a specific target; for example, an entity may suppress
all messages directed to a particular destination (e.g., the security audit service)
Model f or Network Security

Symmetric Cipher Model

A symmetric encryption scheme has five ingredients
Plaintext: This is the original intelligible message or data that is fed into the algorithm
as input.
Encryption algorithm: The encryption algorithm performs various substitutions and
transformations on the plaintext.
Secret key: The secret key is also input to the encryption algorithm. The key is a value
independent of the plaintext and of the algorithm. The algorithm will produce a different
output depending on the specific key being used at the time. The exact substitutions and
transformations performed by the algorithm depend on the key.
Ciphertext: This is the scrambled message produced as output. It depends on the
plaintext and the secret key. For a given message, two different keys will produce two
different ciphertexts. The ciphertext is an apparently random stream of data and, as it
stands, is unintelligible.
Decryption algorithm: This is essentially the encryption algorithm run in reverse. It
takes the ciphertext and the secret key and produces the original plaintext.
Model of Conventional Cryptosystem

A source produces a message in plaintext, X = [X1, X2, ..., XM]. The M elements of X are letters in
some finite alphabet. Traditionally, the alphabet usually consisted of the 26 capital letters.
Nowadays, the binary alphabet {0, 1} is typically used. For encryption, a key of the form K =
[K1, K2, ..., KJ] is generated

With the message X and the encryption key K as input, the encryption algorithm forms the
ciphertext Y = [Y1, Y2, ..., YN]. We can write this as
Y = E(K, X)
Substitution Techniques

i. Caesar Cipher
The earliest known use of a substitution cipher, and the simplest, was by Julius Caesar.
The Caesar cipher involves replacing each letter of the alphabet with the letter standing three
places further down the alphabet. For example,

For instance, here is a Caesar cipher using a left rotation of three places, equivalent to a right
shift of 23 (the shift parameter is used as thekey):
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW

When encrypting, a person looks up each letter of the message in the "plain" line and writes
down the corresponding letter in the "cipher" line. Deciphering is done in reverse, with a right
shift of 3.
Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD
Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

The encryption can also be represented using modular arithmetic by first transforming the
letters into numbers, according to the scheme, A = 0, B = 1,..., Z = 25.[1] Encryption of a letter
by a shift n can be described mathematically as
Decryption is performed similarly,
ii. Monoalphabetic Ciphers

With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase in the key
space can be achieved by allowing an arbitrary substitution. Recall the assignment for the
Caesar cipher:
plain: a b c d e f g h i j k l m n o p q r s t u v w x y z
cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

P 13.33
H 5.83
F 3.33
B 1.67
C 0.00
Z 11.67
D 5.00
W 3.33
G 1.67
K 0.00
S 8.33
E 5.00
Q 2.50
Y 1.67
L 0.00
U 8.33
V 4.17
T 2.50
I 0.83
N 0.00
O 7.50
X 4.17
A 1.67
J 0.83
R 0.00
M 6.67

iii. Playf air Cipher

The Playfair algorithm is based on the use of a 5 x 5 matrix of letters constructed using a
keyword

To start, pick a that does not contain any letter more than once. For example, I’ll pick the word .
Now write the letters of that word in the first squares of a five by five matrix
Then finish filling up the remaining squares of the matrix with the remaining letters of the
alphabet, in alphabetical order. Since there are 26 letters and only 25 squares, we assign I and J
to the same square.

To encipher a message, divide it into pairs of letters. Pay no attention to punctuation

or to spaces between words. For example, the sentence “Why, don’t you?” becomes

Now, find each pair of letters in the matrix you made earlier. Most pairs of letters will
form two corners of a smaller square or rectangle within the matrix. For example, in my matrix,
the first pair of letters ( WH) are at two corners of a two-by-three rectangle also containing Y, A,
B, and IJ. The enciphering of the pair WH is the pair at the two other corners of this rectangle,
namely YI . (I could also have chosen , in this case.) It’s
important to be consistent about the order of the new pair: the one that comes first is
the one on the same as the first of the original pair. In this case, Y is on the same row
as W . We can continue to translate the remaining pairs of letters in the same way, ending up
with

iii. Hill Cipher

The Hill Cipher uses an area of mathematics called Linear Algebra, and in particular requires
the user to have an elementary understanding of matrices. It also make use of Modulo
Arithmetic (like the Affine Cipher). Because of this, the cipher has a significantly more
mathematical nature than some of the others. However, it is this nature that allows it to act
(relatively) easily on larger blocks of letters.

In the examples given, we shall walk through all the steps to use this cipher to act on digraphs
and trigraphs. It can be extended further, but this then requires a much deeper knowledge of
the background mathematics. Some important concepts are used throughout: Matrix
Multiplication; Modular Inverses; Determinants of Matrices; Matrix Adjugates (for finding
inverses).
Encryption

To encrypt a message using the Hill Cipher we must first turn our keyword into a key matrix (a
2 x 2 matrix for working with digraphs, a 3 x 3 matrix for working with trigraphs, etc). We also
turn the plaintext into digraphs (or trigraphs) and each of these into a column vector. We then
perform matrix multiplication modulo the length of the alphabet (i.e. 26) on each vector. These
vectors are then converted back into letters to produce the ciphertext.

Example (Refer Note book)

This example will rely on some linear algebra and some number theory. The key for a hill
cipher is a matrix e.g.

In the above case, we have taken the size to be 3×3, however it can be any size (as long as it is
square). Assume we want to encipher the message ATTACK AT DAWN. To encipher this, we
need to break the message into chunks of 3. We now take the first 3 characters from our
plaintext, ATT and create a vector that corresponds to the letters
(replace A with 0, B with 1 ... Z with 25 etc.) to get: [0 19 19] (this is ['A' 'T' 'T']).
To get our ciphertext we perform a matrix multiplication (you may need to revise matrix
multiplication if this doesn't make sense):

Now for the tricky part, the decryption. We need to find an inverse matrix modulo 26 to use as
our 'decryption key'. i.e. we want something that will take 'PFO' back to 'ATT'. If our 3 by 3 key
matrix is called K, our decryption key will be the 3 by 3 matrix K-1, which is the inverse of K.

Let K be the key matrix. Let d be the determinant of K. We wish to find K-1 (the inverse of K),
such thatK × K-1 = I (mod 26), where I is the identity matrix. The following formula tells us how
to find K-1given K:

Once K-1 is found, decryption can be performed.

Rotor Machines
In cryptography, a rotor machine is an electro-mechanical stream cipher device used
for encrypting and decrypting secret messages .
The basic principle of the rotor machine is illustrated in Figure. The machine consists of a set of
independently rotating cylinders through which electrical pulses can flow. Each cylinder has 26
input pins and 26 output pins, with internal wiring that connects each input pin to a unique
output pin. For simplicity, only three of the internal connections in each cylinder are shown.
Steganography is the practice of concealing a file, message, image, or video within
another file, message, image, or video

Character marking: Selected letters of printed or typewritten text are overwritten in pencil.
The marks are ordinarily not visible unless the paper is held at an angle to bright light.
Invisible ink: A number of substances can be used for writing but leave no visible trace until
heat or some chemical is applied to the paper.
Pin punctures: Small pin punctures on selected letters are ordinarily not visible unless the
paper is held up in front of a light.
Typewriter correction ribbon: Used between lines typed with a black ribbon, the results of
typing with the correction tape are visible only under a strong light.

Data Encryption Standard(DES)

The most widely used encryption scheme is based on the Data Encryption Standard (DES)
adopted in 1977 by the National Bureau of Standards. The algorithm itself is referred to as the
Data Encryption Algorithm (DEA). For DES, data are encrypted in 64-bit blocks using a 56-bit
key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same
steps, with the same key, are used to reverse the encryption.

DES Encryption
The overall scheme for DES encryption is illustrated in Figure. As with any encryption scheme,
there are two inputs to the encryption function: the plaintext to be encrypted and the key. In
this case, the plaintext must be 64 bits in length and the key is 56 bits in length.
 First, the
64-bit
plaintext
passes
through an
initial permutation (IP) that rearranges the bits to produce the permuted input. This is followed
by a phase consisting of 16 rounds of the same function, which involves both permutation and
substitution functions. The output of the last (sixteenth) round consists of 64 bits that are a
function of the input plaintext and the key. The left and right halves of the output are swapped
to produce the preoutput. Finally, the preoutput is passed through a permutation (IP-1) that is
the inverse of the initial permutation function, to produce the 64-bit ciphertext.

Single Round of DES Algorithm

The round key Ki is 48 bits. The R input is 32 bits. This R input is first expanded to 48 bits by
using a table that defines a permutation plus an expansion that involves duplication of 16 of
the R bits. The resulting 48 bits are XORed with Ki. This 48-bit result passes through a
substitution function that produces a 32-bit output, which is permuted as defined by Table.

The role of the S-boxes in the function F is illustrated in the below Figure. The substitution
consists of a set of eight S-boxes, each of which accepts 6 bits as input and produces 4 bits as
output.
The Strength of DES

The Use of 56-Bit Keys

With a key length of 56 bits, there are 2 56 possible keys, which is approximately 7.2 x 10 16.
Thus, on the face of it, a brute-force attack appears impractical. Assuming that, on average, half
the key space has to be searched, a single machine performing one DES encryption per
microsecond would take more than a thousand years to break the cipher.

The Feistel Cipher

Below figure shows the structure proposed by Feistel. The inputs to the encryption algorithm
are a plaintext block of length 2w bits and a key K. The plaintext block is divided into two
halves, L0 and R0. The two halves of the data pass through n rounds of processing and then
combine to produce the ciphertext block. Each round i has as inputs Li-1 and Ri-1, derived from
the previous round, as well as a subkey Ki
Feistel Encryption and Decryption
Confusion and Diffusion
Every block cipher involves a transformation of a block of plaintext into a block of ciphertext,
where the transformation depends on the key. The mechanism of diffusion seeks to make
the statistical relationship between the plaintext and ciphertext as complex as possible in
order to thwart attempts to deduce the key. On the other hand, confusion seeks to make
the relationship between the statistics of the ciphertext and the value of the encryption
key as complex as possible, again to thwart attempts to discover the key. Thus, even if the
attacker can get some handle on the statistics of the ciphertext, the way in which the key was
used to produce that ciphertext is so complex as to make it difficult to find the key

Multiple Encryption and Triple DES

Double DES

Decryption requires that the keys be applied in reverse order:

P = D(K1, D(K2, C))
For DES, this scheme apparently involves a key length of 56 x 2 = 112 bits, of resulting in a
dramatic increase in cryptographic strength.

Triple DES with Two Keys

The function follows an encrypt-decrypt-encrypt (EDE) sequence
C = E(K1, D(K2, E(K1, P)))

There is no cryptographic significance to the use of decryption for the second stage. Its only
advantage is that it allows users of 3DES to decrypt data encrypted by users of the older single
DES:
C = E(K1, D(K1, E(K1, P))) = E(K1, P)
3DES with two keys is a relatively popular alternative to DES and has been adopted for use in
the key management standards ANS X9.17 and ISO 8732.

IDEA(International Data Encryption Algorithm)

IDEA is a block cipher which uses a 128-bit length key to encrypt successive 64-bit blocks of
plaintext.
The encryption scheme uses a total of fifty-two 16-bit subkeys. These are generated from the
128-bit subkey as follows: The 128-bit key is split into eight 16-bit keys which are the first
eight subkeys.
The digits of the 128-bit key are shifted 25 bits to the left to make a new key which is split into
the next eight 16-bit subkeys
The encryption involves modular multiplication with a modulus of ((2^16)+1) and addition
with a modulus of (2^16). The 64-bit plaintext block is split into four 16-bit segment which
we'll call p1, p2, p3 and p4. The subkeys are s1, s2, s3, s4 ....s52.
The encryption consists of eight rounds with each round involving the following steps:
p1 x s1 --> d1
p2 + s2 --> d2
p3 + s3 --> d3
p4 x s4 --> d4
d1 XOR d3 --> d5
d2 XOR d4 --> d6
d5 x s5 --> d7
d6 + d7 --> d8
d8 x s6 --> d9
d7 + d9 --> d10
d1 XOR d9 --> d11
d3 XOR d9 --> d12
d2 XOR d10 --> d13
d4 XOR d10 --> d14

After this process the output blocks d12, d13 are exchanged so that d11, d13, d12 and d14 are
used as input to the next round (in that order) along with the next 6 subkeys, s7 to s12.
This procedure is followed for eight rounds in total giving four output blocks which we'll call e1,
e2, e3 and e4.
Four more steps using the last four subkeys complete the encryption:
e1 x s49 --> c1
e2 + s50 --> c2
e3 + s51 --> c3
e4 x s52 --> c4
Design – Mixing operations from different algebraic groups
- XOR
- Addition modulo 216
- Multiplication modulo 216 + 1
Description of IDEA
64 bit sub blocks: p1, p2, p3, p4. 4 sub-block become the I/P to the first round of the algorithm.
There are 8 rounds total.
Each round the four 4 sub blocks are XORed, added, and multiplied with one another and
with six 16 bit sub-keys
Between rounds the II and III subblocks are swapped
Speed – Twice as fast as DES. iDEA on a 33 MHz 386 machine encrypts data at 880 KB / Sec
Sub-Key Generation(IDEA)
The 128-bit key of IDEA is taken as the first eight subkeys, K(1) through K(8).
The next eight subkeys are obtained the same way, after a 25-bit circular left shift, and this is
repeated until all encryption subkeys are derived.
One Time Pad
one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if
used correctly. Each bit or character from the plaintext is encrypted by a modular addition
with a bit or character from a secret random key (or pad) of the same length as the plaintext,
resulting in a ciphertext. If the key is truly random, as large as or greater than the plaintext,
never reused in whole or part, and kept secret, the ciphertext will be impossible to decrypt or
break without knowing the key.