Cryptography

&
Network Security

Dr. (Mrs.) S. S. Chaudhari

Unit 1 : Introduction and Number Theory

(Weightage- 15%)
ACPCE Slide 2
Overview
• Services
• Mechanisms
• Attacks
• Network Security Model
• Classical Security Techniques
• Symmetric Cipher Model
• Mono-alphabetic and poly alphabetic substitution
techniques:
• Vignere cipher, playfair cipher, Hill cipher
• Transposition Techniques
• Keyed and keyless transposition ciphers
• Steganography
CNS Unit 1 S. Chaudhari
ACPCE Slide 3
Security Services

• Confidentiality: Protection from disclosure to

unauthorized party or process
• Authenticity: is the identification and assurance of the
origin of information
• Integrity: refers to the trustworthiness of data or
resources in terms of preventing improper and
unauthorized changes
• Non-Repudiation: Originator cannot deny sending the
message

CNS Unit 1 S. Chaudhari

ACPCE Slide 4
Security Services

• Availability : refers to the ability to use the information

or resource desired.

• Access control : who is allowed to access what

resources, hosts, software, network connections

• Anonymity : hides user details

CNS Unit 1 S. Chaudhari

ACPCE Slide 5
Security Goals

Confidentiality

Integrity Availability

CNS Unit 1 S. Chaudhari

ACPCE Slide 6
Interception

• Intruder(passive) intercepts in middle of the

activity and view the message
• Attack on confidentiality

A B

Intruder

CNS Unit 1 S. Chaudhari

ACPCE Slide 7
Modification

• Active intruder intercepts in middle and modifies

the message
• Attack on Integrity

A B

Intruder

CNS Unit 1 S. Chaudhari

ACPCE Slide 8
Fabrication

• Active intruder fabricates the message and

send impersonating a sender
• Attack on authenticity

A B

Intruder

CNS Unit 1 S. Chaudhari

ACPCE Slide 9
Interruption

• Active intruder intercepts in middle and stop

communication
• Attack on availability

A B

Intruder

CNS Unit 1 S. Chaudhari

ACPCE Slide 10
Non-repudiation

• It does not allow the sender of a message to

refuse the claim of not sending that message

A B
I never sent the
message which you
claim to have received

CNS Unit 1 S. Chaudhari

ACPCE Slide 11
Security Attacks
An attack is any action that compromise security of information

Passive Active

Snooping Traffic Masquerade Replay Modification Repudiation Denial of

Analysis service

Confidentiality Integrity Availability

CNS Unit 1 S. Chaudhari

ACPCE Slide 12
Security Mechanisms
“A method, protocol, tool, or procedure for enforcing a
security policy”
• Encipherment
• Data Integrity(Hashing)
• Digital Signature
• Access control
• Authentication Exchange
• Traffic Padding
• Routing Control
• Notarization
CNS Unit 1 S. Chaudhari
ACPCE Slide 13
Relation between Security Services and
Security Mechanisms
Security Services Security Mechanisms
Confidentiality Encipherment and routing control
Integrity Encipherment, digital signature, data
integrity(Hashing)

Authentication Encipherment, Digital signature,

Authenticating Exchange

Nonrepudiation Digital signature, Data integrity(Hashing),

notarization

Access control Access Control Mechanism

CNS Unit 1 S. Chaudhari

ACPCE Slide 14
Model For Network security

CNS Unit 1 S. Chaudhari

ACPCE Slide 15
Classical Security Techniques

• Cryptography

• Symmetric Key Encipherment/Secret Key

Cryptography/Private Key Cryptography

• Asymmetric Key Encipherment/ Shared Key

Cryptography/ Public Key Cryptography

• Steganography

CNS Unit 1 S. Chaudhari

ACPCE Slide 16
Cryptography

• Symmetric(Secret/ • Asymmetric(Public
Shared/Private key)
key)

C = E (M ) C =E (M )
k pu.k
M = D (C ) M =D (C )
k pr.k

CNS Unit 1 S. Chaudhari

ACPCE Slide 17
Basic Terminologies
• Plaintext - original message
• Ciphertext - coded message
• Cipher - algorithm for transforming plaintext to ciphertext
• Key - info used in cipher known only to sender/receiver
• Encipher (encrypt) - converting plaintext to ciphertext
• Decipher (decrypt) - recovering plaintext from ciphertext
• Cryptanalysis (code breaking) - study of principles/
methods of deciphering ciphertext without knowing key
• Cryptology - field of both cryptography and cryptanalysis

CNS Unit 1 S. Chaudhari

ACPCE Slide 18
Requirements for secure conventional encryption

• Strong encryption algorithm

An opponent who knows one or more ciphertexts would

not be able to find the plaintexts or the key
Ideally, even if he knows one or more pairs of plaintext-
ciphertext, he would not be able to find the key
• Sender and receiver must share the same key. Once the
key is compromised, all communications using that key are
readable
• Encryption algorithm is not a secret. It is impractical to
decrypt the message on the basis of the ciphertext plus the
knowledge of the encryption algorithm

CNS Unit 1 S. Chaudhari

ACPCE Slide 19
Classical Encryption Algorithms
• Classical (historical) algorithms are based on substitution
& permutation.
ACPCE Slide 20
Caesar Ciphers (Additive/Shift ciphers)

• The simplest monoalphabetic cipher is the

additive cipher.
• This cipher is sometimes called a shift cipher
and sometimes a Caesar cipher, but the term
additive cipher better reveals its mathematical
nature.

CNS Unit 1 S. Chaudhari

ACPCE Slide 21
Caesar Ciphers (Additive/Shift ciphers)

CNS Unit 1 S. Chaudhari

ACPCE Slide 22
Cryptanalysis
“Cryptanalysis is the science and art of breaking secret
codes created by Cryptography”
• Objective - to recover key not just message
• Approaches:
➢ Cryptanalytic attack
➢ Brute-force attack
➢ Statistical attack
➢ Pattern attack

CNS Unit 1 S. Chaudhari

ACPCE Slide 23
Cryptanalytic Attacks
• ciphertext only - algorithm & ciphertext

CNS Unit 1 S. Chaudhari

ACPCE Slide 24
Cryptanalytic Attacks

• known plaintext - ciphertext corresponding to

plaintext

CNS Unit 1 S. Chaudhari

ACPCE Slide 25
Cryptanalytic Attacks

• chosen plaintext - select plaintext

CNS Unit 1 S. Chaudhari

ACPCE Slide 26
Cryptanalytic Attacks

• chosen ciphertext - select ciphertext

CNS Unit 1 S. Chaudhari

ACPCE Slide 27
Brute Force Attack
• always possible to simply try every key
• most basic attack, proportional to key size
Key Size (bits) Number of Alternative Time required at 1 Time required at 106
Keys decryption/µs decryptions/µs
32 232 = 4.3  109 231 µs = 35.8 minutes 2.15 milliseconds
56 256 = 7.2  1016 255 µs = 1142 years 10.01 hours
128 2128 = 3.4  1038 2127 µs = 5.4  1024 years 5.4  1018 years
168 2168 = 3.7  1050 2167 µs = 5.9  1036 years 5.9  1030 years
26 characters 26! = 4  1026 2  1026 µs = 6.4  1012 years 6.4  106 years
(permutation)

Statistical Attack
Pattern Attack
CNS Unit 1 S. Chaudhari
ACPCE Slide 28
Cryptanalysis of Caesar Cipher

• only have 25 possible ciphers

– A maps to B,C,...Z
• could simply try each in turn
• a brute force search
• given ciphertext, just try all shifts of letters
• Ciphertext: SGHR HR BRR BKZRR

CNS Unit 1 S. Chaudhari

ACPCE Slide 29
K S G H R H R B R R B K Z R R
C

25 R F G Q G Q A Q Q A J Y Q Q

24 Q E F P F P Z P P Z I X P P

23 P D E O E O Y O O Y H W O O

22 O C D N D N X N N X G V N N

21 N B C M C M W M M W F U M M

20 M A B L B L V L L V E T L L

19 L Z A K A K U K K U D S K K

18 K Y Z J Z J T J J T C R J J

17 J X Y I Y I S I I S B Q I I

16 I W X H X H R H H R A P H H

15 H V W G W G Q G G Q Z O G G

14 G U V F V F P F F P Y N F F

13 F T U E U E O E E O X M E E

12 E S T D T D N D D N W L D D

11 D R S C S C M C C M V K C C

10 C Q R B R B L B B L U J B B

9 B P Q A Q A K A A K T I A A

8 A O P Z P Z J Z Z J S H Z Z

7 Z N O Y O Y I Y Y I R G Y Y

6 Y M N X N X H X X H Q F X X

5 X L M W M W G W W G P E W W

4 W K L V L V F V V F O D V V

3 V J K U K U E U U E N C U U

2 U I J T J T D T T D M B T T

1 T H I S I S C S S C L A S S

CNS Unit 1 S. Chaudhari

ACPCE Slide 30
Statistical Attack
• Compute frequency of each letter in ciphertext (KHOOR
ZRUOG):
• G = 0.1 H = 0.1 K = 0.1 O = 0.3
• R = 0.2 U = 0.1 Z = 0.1
• Apply 1-gram model of English
a 0.080 h 0.060 o 0.080 v 0.010
b 0.015 i 0.065 p 0.020 w 0.015
c 0.030 j 0.005 q 0.002 x 0.005
d 0.040 k 0.005 r 0.065 y 0.020
e 0.130 l 0.035 s 0.060 z 0.002
f 0.020 m 0.030 t 0.090

g 0.015 n 0.070 u 0.030

CNS Unit 1 S. Chaudhari

ACPCE Slide 31
Statistical Attack
• Let (i ) be a correlation function of the frequency of each letter in
ciphertext with the corresponding letter in English,


(i)=fc
()(
p −
ci)

0 c2
5
- i is the key
- f (c) is the frequency of character c in ciphertext
- p(x) is the frequency of character x in English

• For ciphertext (KHOOR ZRUOG): G H K O R U Z

ϕ(i ) = 0.1p(6 − i ) + 0.1p(7 − i ) + 0.1p(10 − i ) + 0.3p(14 − i )
+ 0.2p(17 − i ) + 0.1p(20 − i ) + 0.1p(25 − i )

CNS Unit 1 S. Chaudhari

ACPCE Slide 32

Statistical Attack
Correlation: φ(i) for 0 ≤ i ≤ 25
i φ(i) i φ(i) i φ(i) i φ(i)
0 0.0482 7 0.0442 13 0.0520 19 0.0315
1 0.0364 8 0.0202 14 0.0535 20 0.0302
2 0.0410 9 0.0267 15 0.0226 21 0.0517
3 0.0575 10 0.0635 16 0.0322 22 0.0380
4 0.0252 11 0.0262 17 0.0392 23 0.0370
5 0.0190 12 0.0325 18 0.0299 24 0.0316
6 0.0660 25 0.0430

Most probable keys, based on :

φ(6) = 0.0660 plaintext: EBIIL TLOLA
φ(10) = 0.0635 plaintext AXEEH PHKEW
φ (3) = 0.0575 plaintext HELLO WORLD
φ (14) = 0.0535 plaintext WTAAD LDGAS
The only English phrase is for i = 3 (key = 3 or ’D’)
CNS Unit 1 S. Chaudhari
ACPCE Slide 33
Caesar Cipher

• Shortcoming : Key is too short

- Can be found by exhaustive search
- Statistical frequencies not concealed well
- They look too much like regular English letters

• Solution: Make it longer

– Multiple letters in key - cryptanalysis harder

CNS Unit 1 S. Chaudhari

ACPCE Slide 34
Euler’s Phi(totient) Function
• φ(1) = 0
• φ(p)= p-1 if p is prime
• φ(m x n)= φ(m) x φ(n) if m and n are relatively
prime(co-prime)
• φ(pe) = pe – pe-1 if p is prime
• Also, if n= p1e1 x p2e2 x…..x pkek then
e1 e1−1 e2 e 2 −1 ek ek −1
 ( n ) = ( p1 − p1 )  ( p2 − p2 )  ......  ( p k − p k )

• Find φ(29), φ(32), φ(80), φ(100), φ(101), φ(240)

CNS Unit 1 S. Chaudhari

ACPCE Slide 35
Multiplicative Inverse

Euler’s Theorem:

If n and a are coprime, then

a−1 mod n = a (n)−1 mod n

• Find 7-1 mod 75 , 50-1 mod 23

CNS Unit 1 S. Chaudhari

ACPCE Slide 36
Multiplicative Ciphers

CNS Unit 1 S. Chaudhari

ACPCE Slide 37
Affine Ciphers

CNS Unit 1 S. Chaudhari

ACPCE Slide 38
Monoalphabetic Cipher

• Instead of shifting the letters with a fixed

amount, any permutation of the alphabet is
done.
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 K V Q F I B J W P E S C X HT M Y A U O L R G Z N

Plaintext: cryptography
Ciphertext: VYZXUHBYDMJZ
• Number of keys ?
CNS Unit 1 S. Chaudhari
ACPCE Slide 39

Monoalphabetic Cipher

• Keys are 26! = 4 x 1026

• Decryption without a key would need to try all the 26!

Possibilities.

• With so many keys, might think is secure

• The problem is that

– language characteristics can be used to speed up

the process of decryption

CNS Unit 1 S. Chaudhari

ACPCE Slide 40
English Letter Frequencies

CNS Unit 1 S. Chaudhari

ACPCE Slide 41
Redundancy in Language

• human languages are redundant

• letters are not equally commonly used

• in english e is by far the most common letter and

then t, r, n, i, o, a, s

• have tables of single, double & triple letter

frequencies

CNS Unit 1 S. Chaudhari

ACPCE Slide 42

Cryptanalysis of Monoalpabetic Cipher

• given ciphertext:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETS
XAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZH
SXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

• count relative letter frequencies

• Guess: P & Z are e and t
• guess ZW is TH and hence ZWP is THE
• proceeding with trial and error finally get:
it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow

CNS Unit 1 S. Chaudhari

ACPCE Slide 43
Polyalpabetic ciphers

• Idea: use different monoalphabetic substitutions

as one proceeds through the plaintext
• Makes cryptanalysis harder with more alphabets
(substitutions) to guess and flattens frequency
distribution
• A key determines which particular substitution is
used in each step

CNS Unit 1 S. Chaudhari

ACPCE Slide 44
Autokey cipher

Plaintext= HIE
K1= 3
K= DHI
Ciphertext= KPM

CNS Unit 1 S. Chaudhari

ACPCE Slide 45
Playfair Ciphers M
C
O
H
N
Y
A
B
R
D
E G F I/J K
L P Q S T
U V W X Z
• Break the plaintext into pairs of two consecutive letters
• If a pair is a repeated letter, insert a filler like 'X‘ in the
plaintext.
• If both letters fall in the same row of the key matrix, replace
each with the letter to its right (wrapping back to start from
end), eg. “AR" encrypts as "RM"
• If both letters fall in the same column, replace each with the
letter below it (again wrapping to top from bottom), eg. “MU"
encrypts to "CM"
• Otherwise each letter is replaced by the one in its row in the
column of the other letter of the pair, eg. “HS” encrypts to
“BP”, and “EA” to “IM” or “JM” (as desired)

CNS Unit 1 S. Chaudhari

ACPCE Slide 46
Security of playfair

• security much improved over monoalphabetic

• since have 26 x 26 = 676 digrams
• would need a 676 entry frequency table to analyse
(verses 26 for a monoalphabetic) and correspondingly
more ciphertext
• was widely used for many years (eg. US & British
military in WW1)
• it can be broken, given a few hundred letters
• since still has much of plaintext structure

CNS Unit 1 S. Chaudhari

ACPCE Slide 47
Vigenère Ciphers

• Proposed by Giovan Batista Belaso (1553) and

reinvented by Blaisede Vigenère (1586)
• multiple caesar ciphers
• key is multiple letters long K = k1 k2 ... kd
• ith letter specifies ith alphabet to use
• use each alphabet in turn
• repeat from start after d letters in message
• decryption simply works in reverse

CNS Unit 1 S. Chaudhari

ACPCE Slide 48
Example
keyword : deceptive
key: de cep tivedecept ived eceptive
plaintext: we are discovered save yourself
ciphertext: ZI CVT WQNGRZGVTW AVZH CQYGLMGJ
KEY
PLAINTEXT
ACPCE Slide 49
Security of Vigenère Cipher

• Its strength lays in the fact that each plaintext

letter has multiple ciphertext letters
- Letter frequencies are obscured (but not totally lost)

CNS Unit 1 S. Chaudhari

ACPCE Slide 50
Attack on Vigenère Cipher

• The Vigenère Cipher can be broken using the

following steps:
1. Find the period (key length); call it n
2. Break ciphertext into n parts
- Each part is enciphered using the same
key letter (Caesar cipher)
3. Solve each part as a Caesar cipher!

CNS Unit 1 S. Chaudhari

ACPCE Slide 51
One Time Pad

• Idea: use a (truly) random key as long as the plaintext

• It is unbreakable since the ciphertext bears no
statistical relationship to the plaintext
• Moreover, for any plaintext & any ciphertext there exists
a key mapping one to the other
• Thus, a ciphertext can be decrypted to any plaintext of
the same length
• The cryptanalyst is in an impossible situation

CNS Unit 1 S. Chaudhari

ACPCE Slide 52
Security of the One Time Pad

• The security is entirely given by the randomness of the

key
- If the key is truly random, then the ciphertext is random
- A key can only be used once if the cryptanalyst is to be kept in
the “dark”
• Problems with this “perfect” cryptosystem
- Making large quantities of truly random characters is a significant
task
- Key distribution is enormously difficult: for any message to be
sent, a key of equal length must be available to both parties

CNS Unit 1 S. Chaudhari

ACPCE Slide 53
Hill Ciphers

• By Lester Hill in 1929.

• Key is matrix

CNS Unit 1 S. Chaudhari

ACPCE Slide 54
Hill Ciphers

Plaintext = code is ready

CNS Unit 1 S. Chaudhari

ACPCE Slide 55
Hill Ciphers- Example

3 7
k =  P= HI = [ 7 8]
15 12 
37
=
c[
78
] =
[
11
15=
][LP
]

151
2

Verify?

CNS Unit 1 S. Chaudhari

ACPCE Slide 56
Transposition Ciphers
• Rearrange letters in plaintext to produce ciphertext
(also called permutation)
• Rail-Fence Cipher(Keyless) : write plaintext letters
diagonally over a number of rows, then read off
cipher row by row
– Plaintext is HELLOWORLD
– Rearrange as
H L O O L
E L W R D
– Ciphertext is HLOOLELWRD
CNS Unit 1 S. Chaudhari
ACPCE Slide 57
Columnar Transposition(Keyed)
Plaintext: THIS IS CNS CLASS

T H I S I S

C N S C L A

S S - - - -

1 2 3 4 5 6

Order : 3 6 1 4 5 2
Ciphertext: ISSATCSSCILHNS

CNS Unit 1 S. Chaudhari

ACPCE Slide 58
Example

CNS Unit 1 S. Chaudhari

ACPCE Slide 59
Double Transposition

CNS Unit 1 S. Chaudhari

ACPCE Slide 60
Confusion and Diffusion

• Confusion: No clue regarding the relationship

between ciphertext and the key

• Diffusion: Hides relationship between plaintext

and corresponding ciphertext

• Strong substitution function enhances confusion

while transposition is used to enhance diffusion

CNS Unit 1 S. Chaudhari

ACPCE Slide 61
Product Ciphers

• Ciphers using substitutions or transpositions are not

secure because of language characteristics

• Idea : using several ciphers in succession to make

harder, but:
– two substitutions make a more complex substitution
– two transpositions make more complex transposition
– but a substitution followed by a transposition makes a
new much harder cipher
• Used in modern ciphers

CNS Unit 1 S. Chaudhari

ACPCE Slide 62
Stream and Block Ciphers
Stream Ciphers : Encryption/Decryption- on one letter/symbol
at a time

CNS Unit 1 S. Chaudhari

ACPCE Slide 60
63
Block Ciphers
• Divide input bit stream into n-bit sections,
• Encrypt only that section, no dependency/history
between sections

CNS Unit 1 S. Chaudhari

ACPCE Slide 60
64
Stream Vs Block Ciphers

Stream Block

• Low Diffusion all • Slowness of encryption

information of one must wait for entire block
symbol contained in one
symbol of cipher text

• Susceptibility to • Error propagation will

insertions and affect transformation of
modifications all other characters in the
same block

CNS Unit 1 S. Chaudhari

ACPCE Slide 60
65
Stream Vs Block Ciphers

Stream Block

• Speed of • High Diffusion one

transformation – time cipher text block may
depends only on depend on several
encryption method plaintext letters

• Low error propagation • Immunity to insertion

error will affect only one of symbols not
character possible to insert a
single symbol into the
block

CNS Unit 1 S. Chaudhari

ACPCE Slide 66
Digital Steganography
• The art of hiding data in a file so that only the sender and
intended recipient suspect the presence of hidden data
• A form of security through obscurity
• Very easy to accomplish
• Harder to detect and decrypt
• BMP, JPG, TXT, HTML/XML, PDF, PNG, GIF, AU, WAV,
MP3, AVI, TIF, TGA, DLL, EXE

CNS Unit 1 S. Chaudhari

ACPCE Slide 67
Steganography & Cryptography

• Steganography and cryptography are closely related

• The difference is in their goals...

• Cryptography: although encypted and unreadable, the

existence of data is not hidden

• Steganography: no knowledge of the existence of the

data

• Steganography and cryptography can be used

together to produce better protection

CNS Unit 1 S. Chaudhari

ACPCE Slide 68
Network Security and Steganography

• Confidentiality: any unauthorized person does

not know that sensitive data exists
• Survivability: verifying that the data does not
get destroyed in the transmission
• No detection: cannot be easily found out that
the data is hidden in a given file
• Visibility: people cannot see any visible
changes to the file in which the data is hidden

CNS Unit 1 S. Chaudhari

ACPCE Slide 69
Types of Digital Steganography

• Hiding a Message inside Text

• Hiding a Message inside Images

• Hiding a Message inside Audio and Video Files

CNS Unit 1 S. Chaudhari

ACPCE Slide 70

Hiding a Message inside Text

randoM capitalosis is a rarE disEase ofTen

contrAcTed by careless inTernet users. tHis sad
illnEss causes the aFfected peRsON To randomly
capitalize letters in a bOdy oF texT. please
do not confuse this disease witH a blatant
attEmpt aT steganogRAPhy.

Reveals: MEET AT THE FRONT OF THE TRAP

CNS Unit 1 S. Chaudhari

ACPCE Slide 71
Hiding a Message inside Text

• First-letter algorithm
• Every n-th character
• Altering the amount of whitespace
• Using a publicly available cover source

CNS Unit 1 S. Chaudhari

ACPCE Slide 72
Hiding a Message inside Images

• Least-significant bit (LSB) modifications

➢ 24-bit vs. 8-bit images
➢ Tools to implement LSB: EzStego and S-Tools
• Masking and Filtering
• Algorithms and Transformations

CNS Unit 1 S. Chaudhari

ACPCE Slide 73

Hiding an Image within an Image

CNS Unit 1 S. Chaudhari