19CSPC701

CRYPTOGRAPHY AND NETWORK SECURITY

7th Sem CSE

Dr. M. Umaselvi,
ASP/CSE,
P. A. College of Engineering and Technology,
Pollachi
1
 Unit I INTRODUCTION

Security trends – Security attacks, services and

mechanisms – OSI security architecture – Classical
encryption techniques: Substitution techniques,
Transposition techniques, steganography – Number
theory: Introduction to Number theory Euclid’s
algorithm (extended), Totient function, Testing for
Primality, Fermat’s and Euler’s theorem – The Chinese
remainder theorem – Exponentiation and logarithm.

2
 OSI (Open Systems
Interconnection) Security Architecture

• a. Attack
• b. Mechanism
• C. Service

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Classical encryption techniques:

1. Substitution techniques
2. Transposition techniques
3. Steganography

21
22
23
24
25
26
27
28
29
30
31
33
 CLASSICAL ENCRYPTION TECHNIQUES

1. Substitution Techniques
1. Caesar Cipher
2. Monoalphabetic Ciphers
3. Playfair Cipher
4. Hill Cipher
5. Polyalphabetic Ciphers
6. One-Time Pad
2.Transposition (Permutation) Techniques
1. Rail Fence Transposition Cipher
2. Block (Single Columnar) Transposition Cipher
3. Double Columnar Transposition Cipher

3. Steganography
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
To find (−n)%k just find k−(n%k).

Ex: (−144)%5=5−(144%5)=5−(4)=1.

50
51
To find (−n)%k just find k−(n%k).

Ex: (−144)%5=5−(144%5)=5−(4)=1.
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
Introduction to Number theory

1. Euclid’s algorithm (extended)

2. Totient function
3. Testing for Primality
4. Fermat’s and Euler’s theorem
5. The Chinese remainder theorem
6. Exponentiation and logarithm

68
 Modular Arithmetic
• Several important cryptosystems make use
of modular arithmetic. This is when the
answer to a calculation is always in the
range 0 – m where m is the modulus.
• To calculate the value of n mod m, you take
away as many multiples of m as possible
until you are left with an answer between 0
and m.
69
If n is a negative number then you add as many
multiples of m as necessary to get an answer in
the range 0 – m.

Examples (−n)%k = k−(n%k).

Ex:
17 mod 5 = 2 7 mod 11 (−144)%5
=7 =5−(144%5)
=5−(4)
20 mod 3 = 2 11 mod 11 =1.
=0
-3 mod 11 = 8 -1 mod 11
= 10
70

25 mod 5 = 0 -11 mod

• Two numbers a and b are said to be “congruent modulo n” if
(a mod n) = (b mod n) 🡪 a ≡ b(mod n)
(73 mod 23) = ( 4 mod 23) 🡪 73 ≡ 4(mod 23)
• The difference between a and b will be a multiple of n
So a-b = kn for some value of k
73-4 = 3.23

E.g: 4 ≡9 ≡ 14≡19 ≡ -1 ≡ -6 mod 5

73 ≡ 4(mod 23); 21 ≡ -9(mod 10)
(−n)%k = k−(n%k).
Ex: 73 mod 23 = 4
(−144)%5 4 mod 23 = 4
=5−(144%5) 73 ≡ 4(mod 23)
=5−(4)
=1. 71
 Properties of Congruences
1. a ≡ b (mod n) if n|(a-b)
2. a ≡ b (mod n) implies b ≡ a (mod n) 21 ≡ -9(mod 10)
3. a ≡ b (mod n) and b ≡ c (mod n) imply a ≡ c (mod n)
4 ≡9 ≡ 14≡19 ≡ -1 ≡ -6 mod 5

Proof of 1.
If n|(a-b), then (a-b) = kn for some k. Thus, we can write
a = b + kn. Therefore,
(a mod n) = (remainder when b + kn is divided by n) =
(remainder when b is divided by n) = (b mod n).

Example:
23 ≡ 8 (mod 5) because 23 -8 =15 = 5x3
-11 ≡ 5 (mod 8) because -11-5 =-16 = 8x(-2)
81 ≡ 0 (mod 27) because 81-0=81 = 27x3 72
 Modular Arithmetic Operations
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) - (b mod n)] mod n = (a - b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n

Proof of 1.
Let (a mod n) = Ra and (b mod n) = Rb. Then, we can write
a = Ra + jn for some integer j and b = Rb + kn for some integer k.
(a + b) mod n = (Ra + jn + Rb + kn) mod n
= [Ra + Rb + (k + j) n] mod n
= (Ra + Rb) mod n
= [(a mod n) + (b mod n)] mod n
73
 Examples
[(a mod n) + (b mod n)] mod n = (a + b) mod n

11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8 ) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(a mod n) - (b mod n)] mod n = (a - b) mod n
[(11 mod 8 ) - (15 mod 8)] mod 8 = -4 mod 8 = 4
(11 - 15) mod 8 = -4 mod 8 = 4
[(a mod n) x (b mod n)] mod n = (a x b) mod n
[(11 mod 8 ) x (15 mod 8)] mod 8= 21 mod 8 = 5
(11 x 15) mod 8 = 165 mod 8 = 5

74
75
7
6
 Exponentiation
• Exponentiation is done by repeated
multiplication, as in ordinary arithmetic.

77
78
 1. Prime Numbers
• prime numbers only have divisors of 1 and self
– they cannot be written as a product of other numbers
– note: 1 is prime, but is generally not of interest

• eg. 2,3,5,7 are prime, 4,6,8,9,10 are not

• prime numbers are central to number theory

• list of prime number less than 200 is:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
71 73 79 83 89 97 101 103 107 109 113 127 131 137 139
149 151 157 163 167 173 179 181 191 193 197 199

79
 4. Fermat's Theorem
• ap-1 ≡ 1 (mod p)
– where p is prime and gcd(a,p)=1

• Fermat’s Little Theorem (alternative form of Fermat’s Theorem)

ap ≡ p (mod p)

• useful in public key and primality testing

80
 Fermat’s Theorem : ap-1 ≡ 1 (mod p)

Fermat’s Little Theorem : ap ≡ p (mod p)

81
Fermat’s Theorem : ap-1 ≡ 1 (mod p)

82
Fermat’s Theorem : ap-1 ≡ 1 (mod p)

83
84
 3. Relatively Prime Numbers & GCD

• two numbers a,b are relatively prime if have no

common divisors apart from 1
– eg. 8 & 15 are relatively prime since factors of 8 are
1,2,4,8 and of 15 are 1,3,5,15 and 1 is the only
common factor

85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
The Chinese remainder theorem

100
101
102
CRT – Method 2

103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118