UNIT 3

PUBLIC KEY CRYPTO

3.1 Knapsack

- Knapsack  problem is combinatorial optimization problem.

-In this problem, a  set of items are given each with weight and value to determine the  each value of number to put in collection so that weight is less than or equal to determined limit.

- The most common problem is 0 -1 knapsack problem. Every item is selected only once.

- Example – Ramesh  wants to take some fruits in his knapsack and wants to increase the profit than he does. The fruits should be picked in such a way that weight should be minimize and the value should be increased.

-Following are the weights and profits with fruits.

Items:  {Chikoo, Pear,Banan, Apple}

Weights:  { 2, 4, 1,5}

Profits: { 4, 6,3,9}

Knapsack Capacity:  6

Fruits taken are – Banana + Apple = 3+9=12.

This is the good combination of fruits , because capacity is not exceeded and  maximum profit is 12.

3.2 RSA

Ron Rivest, Adi Shamir and Len Aldeman have developed this algorithm (Rivest-Shamir-Aldeman) in 1978. It is a public-key encryption algorithm. It is a block-cipher which converts plain text into cipher text at sender side and vice versa at receiver side.

     The algorithm works as follows

     For example

1. Select two prime numbers a = 13, b = 11.

2. n = a*b = 13 * 11 = 143.

3. (n) = (13 – 1) * (11 – 1) = 12 * 10 = 120.

4. Select e such that, e is relatively prime to (n) i.e. gcd (e, (n)) = 1 and 1 < e <(n)  e is selected as  13, gcd (13, 120) = 1.

5. Finding d

e*d mod (n) = 1

13 * d mod 120 = 1

d is calculated using following method. Do the following procedure till you are not getting a integer numbers

d = 

d = 

Where,  i  = 1 to 100

= 

= 

d = 

Henced = 37

6. Hence public key = {13, 143}and
Private key = {37, 143}

7. Encryption

Plain text message (P) which is in binary format converted into integer.

Here P is selected as 13 such that P < n

∵ (13 < 143)

Now, C = Pe mod n =  1313 mod 143

Here to find out 1313 mod 143, use the following procedure

13 mod 143  = 13

132 mod 143  = 169 mod 143 = 26

134 mod 143  = 262 mod 143 = 104

138 mod 143  = 1042 mod 143 = 91

   C = [(138 mod 143) *(134 mod 143)
   *(13 mod 143)] mod 143

= [91 * 104 *13] mod 143 = 52

8. Decryption

To decrypt given plain text message we must know the Cand d.

P = Cd mod n =  5237 mod 143

Again use above mentioned procedure to find out 5237 mod 143. As

52 mod 143 = 52

522 mod 143 = 130

524 mod 143 = (130)2 mod 143 = 26

528 mod 143 = (26)2 mod 143 = 104

5216 mod 143 = (104)2 mod 143 = 91

5232 mod 143 = (91)2 mod 143 = 130 

Hence,

P = 5237 mod 143

= [(5232 mod 143) * (524 mod 143) * (52 mod 143)] mod 143

= [130 * 26 * 52] mod 143 = 13

Prime number p = 3, q = 11, e = 3, m = 00111011
(m-message) then calculate private key d and cipher text C.
Soln. :

Use RSA Algorithm [Refer Section 3.3]

Step 1 : Prime numbers   p = 3,   q = 11

Step 2 : n = p * q = 33

Step 3 : (n)  = (p – 1) * (q – 1) = (3 – 1) * (11 – 1)

= 2 * 10 = 20

Step 4 : Select e such that it is relatively prime to  (n) i.e. gcd(e,  (n)) = 1

Gcd (e, 20) = 1  

Gcd (3, 20) = 1

e = 3 is given.

Step 5 : Calculate d such that

d = e– 1 mod  (n)

Ed mod  (n) = 1

3  d mod 20 = 1

d = 

Find d such that it is divisible by e.

Where  i = 1 to 9

d =   =   =  = 7

d = 7

Step 6 :Public key = {e, n} = {3, 33}

Private key = {d, n} = {7, 33}

Step 7 : Calculate cipher text message for given plain text message.

Plain text message given in binary 00111011 which can be written as 59

Binary to decimal conversion

00111011  59 (P = 59)

c = Pe  mod n  where  P< n = 593 mod 33

= [592 mod 33] * [59 mod 33] mod 33

= 3481 mod 33 * [59 mod 33] mod 33

c = [16 * 26] mod 33

c = 20

Step 8 : Calculate plain text message.

P = cd mod n = 207 mod 33

P = [204 mod 33] * [203 mod 33] mod 33

= [202 mod 33] * [202 mod 33] * [202 mod 33] 
   [201 mod 33] mod 33

= [400 mod 33] * [400 mod 33] * [400 mod 33] 
   [20 mod 33] mod 33

= [4] * [4] * [4] * [20] mod 33  =   1280 mod 33

P = 26

Calculate cipher text using RSA algorithm given data as follows :

Prime numbers p, q as 7, 17 respectively and plain text message is to be send is 10.              

Soln. :

By using RSAAlgorithm : [Refer Section 3.3 ]

Step 1 : Prime numbers are   7 and 17   a = 7,   b = 17

Step 2 : n = a * b = 7 * 17 = 119. 

Step 3 :  (n) =(a – 1)  (b – 1)  =  (7 – 1)  (17 – 1)

=6 * 16 = 96

Step 4 : Select e such that it is relatively prime to  (n) i.e. gcd(e, (n)) = 1

If we select s then it is not relatively prime p 96 because

3 = 1 * 3

96 = 2 * 2 * 2 * 2 * 2 * 3

Gcd must be 1.

We select e as 5 (gcd must be 1)

5 = 1 * 5

Gcd (5, 96) = 1

Step 5 :Calculate d such that

d  =  e– 1 mod  (n)

Ed mod  (n) = 1

5  d mod 96 = 1

Using RSA algorithm

d = 

Where i = 1 to 9 =   = 19.4

d must be completely divisible by ‘e’.

=    = 38.6 =    = 57.8

=    = 77

d = 77

Step 6 :  Public key ={e, n} = {5, 119}

Private key={d, n} = {77, 119}

Step 7 : Calculate cipher text message for given plain text message m = 10.

Plain text denoted as p = 10 (m denoted as p)

c = pe mod n =  105 mod 119

It can be represented as

105 mod 119  = [103 mod 119] * [102 mod 119] mod 119

= [1000 mod 119] * [100 mod 119] mod 119

= 100000 mod 119

c = 40

Step 8 : Now calculate plain text P required at the time of decryption. Once sender sends 40 to the receiver then receiver can calculate plain text p.

P = cd mod n =  4077 mod 119

Now represent 4077 mod 119 as mention above it will results p as 10.

Because decryption process always yields original message / plain text

   P = 4077 mod 119 = 10

P = 10

Calculate cipher text using RSA algorithm given data is as follows :

Prime numbers P, Q as 13, 17 and the plain text to be send is 12. Assume public key e as 19.              

Soln. :

Using RSA Algorithm [Refer Section 3.3]

Step 1 :P and Q denoted as a and b in our Algorithm

a = 13,   b = 17

Step 2 : n = a  b = 13 * 17 = 221.

Step 3 :  (n)  =(a – 1)  (b – 1) = (13 – 1)  (17 – 1)

=12 * 16 = 192

Step 4 : Select e such that it is relatively prime to  (n) e is given as 19.

Step 5 : Calculate d such that,

d = e– 1 mod  (n)  ed mod  (n)  = 1

d  =     where i = 1 to 9 

=  = 10.1 =   = 20.2

=  = 30.3 =   = 40.4

=  = 50.5 =   = 60.6

=  = 70.7 =   = 80.8

=  = 91

       d = 91

Step 6 : Public key = {e, n} = {19, 221}

Private key = {d, n} = {91, 221}

Step 7 :Calculate cipher text c for given plain text message 12.

   c  = pe mod n

= 1219 mod 221

= [1210 mod 221] * [125 mod 221] * [124 mod 221]

= [125 mod 221] * [125 mod 221] *[125 mod 221] *
   [124 mod 221] mod 221

= [207] * [207] * [207] * [183] mod 221

c = 181

Step 8 :Send c = 181 to receiver as if required for decryption to obtain original plain text p.

P = cd mod n =  18191 mod 221

This yields value of original plain text message i.e. 12

P = 12

In public key cryptosystem given N = 187 and encryption key (E) as = 17. Find out corresponding private key (D).             

Soln. :

RSA Algorithm [Refer Section 3.3]

Step 1 : Select two large random prime numbers a and b. If we select a = 17 and b = 11 which results
n = 187.

n  = ab = 17 * 11 = 187.

Step 2 : Calculate (n) = (a – 1)  (b – 1)

=  (17 – 1) (11 – 1)

= 16 * 10

= 160

Step 3 : Select e such that it is relatively prime to  (n) and less than  (n). But it is given in problem statement that e = 17.

Step 4 : Calculate d such that,

d  =  e– 1 mod  (n)

ed mod  (n)  =  1

d =     where i = 1 to 20

=     = 9.4 =  = 18.8

=     = 28.2 =  = 37.70

=   = 47.11 =  = 56.52

=   = 65.94 = = 75.35

=   = 84.76 =    = 113

       d = 113

Using the RSA algorithm encrypt the following :

(i) p = 3  ,  q = 11,  e = 7,  M = 12

(ii) p = 7  ,  q = 11,  e = 17,  M = 25

(iii) Find the corresponding ds for (i) and (ii) and decrypt the ciphertexts.

Soln. :

Use RSA Algorithm

(i) Consider p as a and q as b as per our notations for prime numbers.

Step 1 : Prime numbers   a = 3,   b = 11

Step 2 : n = a * b = 33

Step 3 : (n) = (a – 1) * (b – 1)

=  (3 – 1) * (11 – 1)

=  2 * 10

=  20

Step 4 : Select e such that it is relatively prime to  (n) i.e. gcd(e,  (n)) = 1

Gcd (e, 20) = 1

Gcd (7, 20) = 1

e = 7 is given.

Step 5 : Calculate d such that

d = e– 1 mod  (n)

Ed mod  (n) = 1

7 d mod 20 = 1

d =  Where i = 1 to 100

Find d such that it is divisible by e.

Consider i = 1 you can continue till d will get integer value, Q(n) = 20 and e= 7

d = ((20 *1) +1)/7    = 21/7 = 3

d = 3

Step 6 : Public key  = {e, n} = {7, 33}

Private key = {d, n} = {3, 33}

Step 7 : Calculate cipher text message for given plain text message.

Plain text message given is M= 12 we consider M as i.e. P = 12

C = pemod n  where  p < n

= 127 mod 33

C = 12

Step 8 : Calculate plain text message.

P = cd mod n

= 123 mod 33

P = 12

P = 12

When we convert plain text message into cipher text the corresponding cipher text yields the same plain text.

(ii)   p = 7  ,  q = 11,  e = 17,  M = 25

By using RSA Algorithm : [Refer Section 4.2]

Step 1 : Prime numbers are 7 and 11   as per our notations a = 7,   b = 11

Step 2 : n = a * b = 7 * 11 = 77.

Step 3 : (n) = (a – 1)  (b – 1)

= (7 – 1)  (11 – 1) = 6 * 10 = 60

Step 4 : Select e such that it is relatively prime to  (n) i.e. gcd(e, (n)) = 1

e is given as 17

Gcd (17,60) = 1 (gcd must be 1)

Step 5 : Calculate d such that

d = e– 1 mod  (n)

Ed mod  (n) = 1

17 d mod  = 1

Using RSA algorithm

d =    where i = 1 to 100

= ((60*1) +1)/ 17)

=  3.58

d must be completely divisible by ‘e’.

= After putting value of  i = 15 into above formula we got value of d

= ((60*15) +1)/ 17) = 53

d = 53

Step 6 :Public key ={e, n} = {17, 77}

Private key =  {d, n} = {53, 77}

Step 7 : Calculate cipher text message for given plain text message M = 25.

Plain text denoted as P = 25 (m denoted as p)

C = Pe mod n

= 2517 mod 77

It can be represented as

C = 9

Step 8 :  Now calculate plain text P required at the time of decryption. Once sender sends 9 to the receiver then receiver can calculate plain text p.

P = Cd mod n

= 953 mod 77

P = 25

Decryption process always yields original plain text message

 P = 25

(iii) Find the corresponding ds for (i) and (ii) and decrypt the ciphertexts

Decryption key for question (i) is d =3 and for question (ii) is d= 53 which will decrypt the message successfully.

In an RSA system the public key (e,n) of user A is defined as (7,119). Calculate (n)and private key d. What is the cipher text when you encrypt message m =10, using the public key?

Soln. :

By using RSA Algorithm : [Refer Section 4.2]

In the problem statement Public key (e,n) = (7,119) is given, means we don’t need to select e & n. If we select following prime numbers which results n = 119 as shown below. 

Step 1 : Prime numbers are 7 and 17   a = 7,   b = 17

Step 2 : n = a * b = 7 * 17 = 119.

Step 3 : (n) = (a – 1)  (b – 1)

= (7 – 1)  (17 – 1)

= 6 * 16

= 96

Step 4 : Select e such that it is relatively prime to  (n) i.e. gcd(e, (n)) = 1

e= 7 as per problem statement.

Step 5 : Calculate d such that

d = e– 1 mod  (n)

Ed mod  (n) = 1

7  d mod 96 = 1

Using RSA algorithm

d = (((n) *i) + 1)/ 7   where i = 1 to 100

= (96*1 + 1)/7   = 13.85

d must be completely divisible by ‘e’.

= ((96*2) + 1)/7    = 21.57

= ((96*3) + 1)/7      = 48.28

= ((96*4) + 1)/7      = 55

d = 55

Step 6 : Public key ={e, n} = {7, 119}

Private key =  {d, n} = {55, 119}

Step 7 : Calculate cipher text message for given plain text message m = 10.

Plain text denoted as p = 10 (m denoted as p)

C = Pe mod n

= 107 mod 119

= 10000000 mod 119

C = 73

Step 8 :  Now calculate plain text P required at the time of decryption. Once sender sends 40 to the receiver then receiver can calculate plain text p.

P = Cd mod n

= 7355 mod 119

Now represent 4055 mod 119 as mention above it will results p as 10.

Because decryption process always yields original message / plain text

   P = 7355 mod 119 = 10

P = 10

Perform encryption using the RSA algorithm

p = 3,q = 11(two random numbers).

e(encryption key) = 7

M(plaintext message) = 5   

Soln. :

Using RSA algorithm

p = 3,   q = 11,  e = 7    and  M = 5

Step 1 : Prime number  p = 3, q = 11

Step 2 : n = p  q = 3  11 = 33

Step 3 :  (n)   =  (p – 1) (q – 1)  = (3 – 1) (11 – 1)

=  2 10

 (n) =  20

Step 4 : Select e such that it is relatively prime to (n) i.e. gcd (e,  (n)) = 1

Gcd (e, 20) = 1

Gcd (7, 20) = 1

e = 7   is given.

Step 5 :  Calculate d such that

d = e– 1 mod    (n)

e d mod  (n) = 1

7 d  mod  20 = 1

d = 

Find d such that is divisible by e.

Where, i = 1 to 100

d = where  i = 1;

= = = 3

d = 3

Step 6 : Public key = {e, n} = {7, 33}

Private key = {d, n} = {3, 33}

Step 7 :  Calculate cipher text message for given plain text message plain text M = 5.

C = Me  mod n      where  M  n

= 57  mod 33

= (55 mod 33)  (52 mod 33)  mod 33

= (53 mod 33)  (52 mod 33)  (52 mod 33)  mod 33

= (125 mod 33) (25 mod 33)  (25 mod 33)  mod 33

= (26 25 25)  mod 33

= 16250  mod 33

= 14

c = 14

The encryption algorithm to be used is RSA. Given two prime numbers 11 and 3 and public key (e) is 3. Calculate the decryption key and Calculate the ciphertext if the given plaintext is 7.

Soln. :

Using RSA algorithm

Given :  a = 11,   b = 3,   e = 3  and plain text P = 7

Step 1 :Prime number a = 11, b = 3

Step 2 :n = a  b = 11  3 = 33

Step 3 :  (n) =  (a – 1)  (b – 1) = (11 – 1)  (3 – 1)
= 10  2

=  20

Step 4 :  Select e such that it is relatively prime to  (n) i.e. gcd (e,  (n)) = 1

Gcd (e, 20) = 1

Gcd (3, 20) = 1

e = 3    is given.

Step 5 : Calculate d such that

d = e-1 mod  (n)

e d mod  (n)  = 1

3  d mod 20 = 1

d = 

Find d such that it is divisible by e

Where i = 1 to 100

d = where  i =1;

d =  = =7

d = 7

Step 6 : Public key = {e, n} = {3, 33}

Private key = {d, n} = {7, 33}

Step 7 : Calculate cipher text message for given plain text message.

Plain text message = 7

c = Pe mod n  where  P  n

= 73 mod 33  = [73 mod 33]  [7 mod 33]  mod 33

= [49   mod 33] * [7 mod 33] * mod 33

= [16  7] mod 33

c = 13

So,  cipher text=  3

3.3 Diffie-Hellman

          The Diffie Hellman algorithm was widely known as Key exchange algorithm or key agreement algorithm developed by Whitfield Diffie and Martin Hellman in 1976.Diffie Hellman algorithm is used to generate same (symmetric) private cryptographic key at sender as well as receiver end so that there is no need to transfer this key from sender to receiver.

          Remember that Diffie Hellman algorithm is used only for key agreement not for encryption or decryption of message. If sender and receiver want to communicate with each other they first agree on the same key generated by Diffie Hellman Algorithm later on they can use this key for encryption or decryption. Let us start with the algorithm.

     Steps of Diffie Hellman Algorithm

1. The first step is that if Ramesh wants to communicate with Suresh they must agree on two large prime numbers p and q.

2. Ramesh selects another secret large random integer number a, and calculate R such that

R = qa mod p

3. Ramesh sends this R to suresh.

4. Suresh independently selects another secret large random integer number b, and calculate S such that.

S = qb mod p

5. Suresh sends the number S to Ramesh.

6. Now Ramesh is calculating his secret key by using RK = Sq mod p

7. Suresh is calculating his secret key SK by using

SK = Rb mod p

8. If RK = SK then Ramesh and Suresh can agree for future communication called as key agreement algorithm.

9. We have RK = SK = K hence proved. (K is called symmetric key).

     For example

1. Ramesh and Suresh are agree on two large prime numbers say p = 17 and q = 7.

2. Ramesh selects another secret large random number 5 i.e. a = 5 and calculate R such that

R =  qa mod p =  75 mod 17 = 11

= (7  7  7 7  7) mod 17 = 11

3. Ramesh sends number R to Suresh.

4. Suresh selects another secret large random number 3. i.e. b = 3 and calculate s such that

S = qb mod p = 73 mod 17 = 3

= (7  7  7) mod 17 = 3

5. Suresh sends number S to Ramesh.

6. Ramesh now calculates its secret key RK as follows :

RK = Sa mod p = S5 mod 17

  RK = 35 mod 17 = 5

= (3  3  3  3  3) mod 17 = 5.

7. Suresh is calculating his secret key SK as follows :

SK = Rb mod p = R3 mod 17 = 113 mod 17 = 5

8. If RK = SK then Ramesh and Suresh can agree for future communication.

9. We know that if RK = SK = K = 5. Hence proved.

Solve if p = 7 and q = 17 using Diffie Hellman algorithm. Select a = 6, b = 4.

Soln. :

By using Diffie Hellman algorithm

1. Ramesh and Suresh are agree on two large prime numbers say p = 7 and q = 17.

2. Ramesh selects another secret large random number 6 i.e. a = 6 and calculate R such that

R  =  qa mod p = 176 mod 7 

= (17  17  17  17  17  17) mod 7

R = 1

3. Ramesh sends R to Suresh

4. Suresh selects another secret large number 4 i.e. b = 4 and calculate S such that

S = qb mod p=174 mod p

= (17  17  17  17) mod 7

S = 4

5. Suresh sends number S to Ramesh

6. Ramesh now calculates it’s secret key RK as follows :

RK = Sa mod p= S6 mod p=46 mod 7

= (4  4  4  4  4  4) mod 7

RK = 1

7. Suresh is calculating his secret SK as follows :

SK = Rb mod p= 14 mod 7

SK = 1

8. If RK = SK then Ramesh and Suresh can agree for future communication.

Solve p = 353 and q = 3, a = 97 and b = 233.

Soln. :

By using Diffie Hellman algorithm

1. Ramesh and Suresh are agree on two large prime numbers p = 353 and q = 3.

2. Ramesh selects another secret large random number a = 97 and calculate R such that

R = qa mod p = 397 mod 353

R = 40

3. Ramesh sends R to Suresh (value of R = 40)

4. Suresh selects another secret large random number b = 233 and calculate S such that

S = qb mod p=3233 mod 353

S = 248

5. Suresh sends value of S to Ramesh

6. Ramesh now calculates it’s secret key RK as follows :

RK = Sq mod p= 24897 mod 353

RK = 160

7. Suresh is calculating his secret key SK as follows :

SK = Rb mod p= 40233 mod 353

SK = 160

8. If RK = SK then Ramesh and Suresh can agree on same key and can communicate in future.

Ex. 

If generator g = 2 and n or p = 11 using Diffie Hellman algorithm solve the following :

(i)    Show that 2 is primitive root of 11

(ii) If A has public key 9 what is A’s private key ?

(iii) If B has public key 3 what is B’s private key ?

(iv) Calculate shared secret key. 

Soln. :

(i) To show that 2 is primitive root of 11

          In general terms, the highest possible exponent to which a number can belong (mod n) is Q(n).

          Where Q(n) is called as Euler totient function which states that how many numbers are between 1 and n – 1 that are relatively prime to n.

According Euler’s theorem

It states that for every a and n that are relatively prime.  

If a(n) = 1 mod n

For example

As mention in (i)

a = 2  and  n = 11

Calculate (n) i.e. (11)={ 1 to 10 } = 10

According to Euler’s theorem

a(n) = 1 mod n

210 = 1 mod 11

1024 = 1 mod 11

i.e. 1024 mod 11  = 1 and

1 mod 11 = 1

Hence 2 is primitive root of 11.

(ii) If ‘A’ has public key 9 then private key is

1. Say A as Ramesh and B as Suresh.

Representing g as a q (i.e. g = 2 = q)

Using Diffie Hellman algorithm

2. Suresh now calculates R such that

R = qa mod p  [Here q = 2 and p = 11]

= 29 mod 11  [a is 9 public key]

R = 6

3. Ramesh now sends R to Suresh.

(iii) Suresh has public key 3 (it’s random number) Suresh calculates S such that

S = qb mod p = [q = 2, p = 11, b = 3]

S = qb mod p = 23 mod 11

S = 8

Suresh now sending S to Ramesh.

(iv) Now Ramesh and Suresh calculating their secret keys individually.

1. Ramesh calculates it’s secret key RK as follows :

RK = Sa mod p    [S = 8, p = 11, a = 9]

= 89 mod 11 = 7

2. Suresh calculates it’s secrete key SK as follows :

SK = Rb mod p  [R = 6, b = 3, p = 11]

= 63 mod 11 = 7

Shared secret keys of Ramesh and Suresh are 7.

Hence,     RK = SK = 7

Ex.

A and B decide to use Diffie Hellman key exchange where
p = 13, g = 2, each choose his own secret no. And exchange numbers 6 and 11.

(i) What is common secret key ?

(ii) What are their secret numbers ?

(iii) Can intruder m gain any knowledge from protocol run if he sees p, 9 of and two keys 6 and 11. If yes, show how ?

Soln. : 

According to Diffie Hellman algorithm,

Let us say A as Ramesh and B as Suresh

Also p = 13 and g = 2

Here in our example we are denoting g as q,

  p = 13, 

q = 2

Secret numbers denoted as, a = 6 and b = 11 by using Diffie Hellman algorithm.

1. Ramesh and Suresh agree on two large prime numbers p = 13 and q = 2.

2. Ramesh selects another secret no. a = 6 and calculate R such that

R = qa mod p [q = 2, a = 6, p = 13]

= 26 mod 13

R = 12

3. Ramesh sends R to Suresh

4. Suresh selects another large random number b = 11 and calculate S such that

S = qb mod p   [q = 2, b = 11, p = 13]

= 211 mod 13

S = 7

5. Suresh sends S to Ramesh

6. Ramesh now calculates it’s secret key RK as follows :

RK = sa mod p  [S = 7, a = 6, p = 13]

= 76 mod 13

RK = 12

7. Suresh is calculating his secret key SK as follows :

SK = Rb mod p [R = 12, b = 11, p = 13]

= 1211 mod 13

SK = 12

(i) Shared secret key of Ramesh and Suresh is

RK = SK = 12 [A and B = 12]

(ii) Secret numbers of Ramesh and Suresh are

R = 12 and S = 7

(iii) If intruder m knows p, g and a, b then what will happen. [Here g = q]

Case I :Value of p, q, a, b are known to m represented as ,

Ramesh   m  Suresh

p = 13, q = 2  p = 13, q = 2 p = 13, q = 2

Use Diffie Hellman algorithm,

After selecting large prime numbers, it’s time to select random numbers a and b.

The secret random number selected by Ramesh and Suresh are,

Ramesh          m   Suresh

a = 6  a = 8, b = 6  b = 11

Case 2 :

Consider m as intruder selected two random numbers say a = 8 and b = 6 as his own secret key, because he wants to calculate value as R and S, as he intercepted conversion between Ramesh and Suresh

Case 3 : Following are the values available with Ramesh, Suresh and intruder m

Ramesh  intruderm  Suresh S

R = 12  R = 9, S = 12  S = 7

Case 4 :

Ramesh sending his R = 12 to suresh but intruder m sending his own R = 9 to Suresh instead of R = 12. Suresh sending his S = 7 to Ramesh, here again intruder m sending his own value of S = 12 to Ramesh. In this case Ramesh and Suresh doesn’t aware that which values they are sending and receiving [Intruder m sending his own value Because of his interception]. Following are the new values with Ramesh, Suresh and intruder m.

Ramesh   Intruder m Suresh

R = 12, S = 12 R = 12, S = 7  S = 7

R = 9

Case 5 : Based on above values Ramesh, Suresh and Intruder m calculating secret keys.

Think what is happening ? Ramesh is thinking that value of his secret key is 1 and suresh also thinking that value of his secret key is 3.

But actual communication is intercepted by intrude m.

During real communication between Ramesh and Suresh intruder m sending his own secret keys to Ramesh and Suresh. If Ramesh sending his secret key RK = 1 to Suresh because of man-in-the-middle attack. Intruder m sending his secret key RK = 3 to Suresh. In return Suresh is sending his secret key SK = 3 to Ramesh, intruder m sending his secret key SK = 1 to Ramesh.

Both Ramesh and Suresh not aware that communication intercepted by intruder m such type of attack is called as man-in-the-middle attack. 

3.4 Uses for Public Key Crypto

-  Public key cryptography is also called as asymmetric key, uses two keys i.e. pair of keys -  public key and private key.

- Public key is public but private key is known to only user.

- When the message is encrypted, it has to encrypt the users public key but decrypt message private key is required.

Applications

-         The most common application of public key is to provide confidentiality. When the sender sends a message to receiver it is encrypted using public key.

-         It is used in digital signature. It is used to authentication to the sender.

-         Digital signatures are used non repudiation system to ensure than another party can not destroy authorship of documents of another one.

-         Digital cash, time stamping service, password authentication is based on digital key.

-         Hybrid cryptosystem is done by PGP, SSH. In this keys are exchanged using key exchange algorithm.

3.5 Hash function

          The process of transforming input message m into a fixed size string (called as hash value h) is called as hash function and it is denoted by H. Here h is the output of hashing function applied on input message m.

h = H(m)

          Hash function protects the integrity of the message. If attacker tries to modify the original message then the contents of original message may changed it can be identifies by applying Hashing algorithm.The most popular hashing algorithms are MD5 and SHA. Following sections gives details on MD5 and SHA.

MD5 Message Digest Algorithm

          It was developed by Ron Rivest. This algorithm takes an input of arbitrary length and 128 - bit message digest is produced. The input message is produced in 512 - bit blocks.

          Fig. 3.8.1 shows processing of a message to produce message digest. Following steps explains the procedure of MD5.

           

Detail steps of Message Digest 5 Algorithm

1. Append padding bits

          The message is padded to make the length of message is 448 mod 512. The length of the padded message is 64 bits less than an integer multiple of 512.

          The padding message consists a single 1-bit followed by 0 bits. The length of padding bits is in between 1 to 512.

2. Append length

          64 bits of original message is appended to the result of above step 1. It is appended such that least significant bytes to most significant byte.

          The output of step 2 yields a message of integer multiple of 512 bits. As M0, M1, … Mq … ML – 1. The total length of expanded message is L * 512 bits.

3. Initialize MD Buffer

          A 128 - bit buffer is used to store the intermediate as well as final result. A buffer is represented as four 32-bit registers as P, Q, R, S.

P = 67452301

Q = EFCDA1389

R = 98BADCFE

S = 10325476.

          It used a little - endian methods. Hence initial values (IV) are represented as,

P = 01 23 45 67

Q = 89 AB CD EF

R = FE DC BA 98

S = 76 54 32 10.

4. Process Message in 512-bit (16 word of 32 bit) blocks

          It consists of four rounds of processing as shown in Fig. 3.8.2. These four rounds have similar structure but differ in primitive logical function referred as A, B, C, D.

          Each round takes input 512-bit block, processed it and produces 128 bit output. The output of fourth round is added to the first round CVq to produce CVq + 1 using addition modulo 232.

Four rounds of MD5 algorithm

5. Output

After processing all L 512-bit blocks, the 128 bit message digest is produced as a output.

The entire MD5 process can be summarized as follows :

Secure Hash Algorithm (SHA)

          The SHA was developed by NIST in 1993. It is referred as Secure Hash Algorithm-1.

          SHA - 1 takes an input message of a maximum length less than 264 bits and produced an output of 160 bit message digest. The overall processing of SHA-1 is much similar to MD5. The processing is explained as follows.

1. Append padding bits

          Padding means addition of bits to the original message. To make length of original massage to a value 64 bits less than multiple of 512. The message is padded to make the length of message 448 mod 512.

          The length of the padded message is 64 bits less than an integer multiple of 512. The padding message consists of a single 1-bit, followed by many 0 bits as required. The length of padding bits is in between 1 to 512.

2. Append length

          A block of 64-bit is appended to a message. 64 bits of original message is appended to the result of above step 1 (Original message + Padding).

          It is appended such that least significant bytes to most significant byte.

3. Initialize MD5 Buffer

          A 160-bit buffer is used to store the intermediate as well as final result. The buffer is represented as five
S32-bit registers as P, Q, R, S, T, as.

P = 67452301

Q = EFCDAB89

R = 98BADCFE

S = 10325476

T = C3D2E1FO

          It uses a big-endian method. First four registers are same as MD5. These five registers P, Q, R, S, T are represented as,

P = 67   45   23   01

Q = EF  CD  AB  89

R = 98   BA  DC FE

S = 10   32   54  76

T = C3  D2   E1   FO 

4. Process message in 512-bits (32 bit 16 word) block

          It consists of four rounds of 20-step each as shown in Fig. 3.8.3. These rounds referred as F1, F2, F3, F4 have similar structure. These rounds used different primitive logical function.

          Each round takes input 512-bit block processed it and produced 160 bit output. The output of fourth round is added to the first round CVq to produce CVq + 1.

          Each round also uses an additive constant kt,

Where 0  +  79.

K1 = 5A  82 79 99

K2 = 6 E D9 EB A1

K3 = 8F 1B BC DC

K4 = CA 62 C1 D6

Four rounds of Secure Hash Algorithm

5. Output

After processing all L 512 bit blocks, the 160 bit message digest is produced as output. The SHA compression function uses a feed forward operation where the chaining variable CVq input of the first round is added to the output obtained (last step) after execution of 80 steps to produce the next chaining variable CVq+1 as shown in Fig. 3.8.3.

     The entire SHA-1 process can be summarized  as follows:

References:

Text Book :

Information Security Principles & Practices by Mark Stamp, Wiley.

Reference Books :

Introduction to Computer Security by Bishop and Venkatramanayya, Pearson Education.

Cryptography and Network Security : Principles and Practice by Stallings, PHI.