5G
Advertisement

Ques1. Compute the message Digest using SHA-1 Algorithm for the following message:

abc

showing all intermediate steps with mathematical expressions. Refer the internet for initial values and other setups.

Solution:

Compute the message Digest using SHA-1 Algorithm (showing all intermediate steps)

Given,

Message(m) = abc

 

First, we convert into decimal value =  97 98 99

Now, binary value = 01100001 01100010 01100011

 

Which is 24bits (11000) but we know that in SHA-1 

l+1+k  = 448 mod 512

Where l = length of the message in bits

  k = no of zero bits

 

Now we can calculate k = 448 – (1+24) = 423

 

Therefore 423 number of zero bits

 

Padding the messages:

We know that padded messages in SHA-1 should be multiple of 512bits.

Here format of a padded message be like

m_appending bits_zero bits_length of the message in bits 

Here we append ‘1’ bit to the end of the message(m) 

Therefore,

The padded message will be

01100001 01100010 01100011 1 00….00 0…011000

Compute the message Digest using SHA-1 Algorithm showing all intermediate steps

Now the message is multiple of 512bits

 

 

Initialization of  hash value;

H[0] = 67452301

H[1] = efcdab89

H[2] = 98badcfe

H[3] =10325476

H[4] = c3d2e1f0

 

Now the 512bits block is divided into sixteen 32 bits subblocks.

16 sub-blocks:

W[0] = 01100001 01100010 01100011 10000000 = 61626380

W[1] = 00000000 00000000 00000000 00000000 = 00000000

W[2] = 00000000 00000000 00000000 00000000 = 00000000

W[3] = 00000000 00000000 00000000 00000000 = 00000000

W[4] = 00000000 00000000 00000000 00000000 = 00000000

W[5] = 00000000 00000000 00000000 00000000 = 00000000

W[6] = 00000000 00000000 00000000 00000000 = 00000000

W[7] = 00000000 00000000 00000000 00000000 = 00000000

W[8] = 00000000 00000000 00000000 00000000 = 00000000

W[9] = 00000000 00000000 00000000 00000000 = 00000000

W[10] = 00000000 00000000 00000000 00000000 = 00000000

W[11] = 00000000 00000000 00000000 00000000 = 00000000

W[12] = 00000000 00000000 00000000 00000000 = 00000000

W[13] = 00000000 00000000 00000000 00000000 = 00000000

W[14] = 00000000 00000000 00000000 00000000 = 00000000

W[15] = 00000000 00000000 00000000 00011000 = 00000018

 

Now SHA-1 has 4 rounds, each consisting 20 steps.

 

Rounds Steps Function (f) value of k(additive constants)
1 1 to 19 (b AND c) OR ((NOT b) AND d) 5a827999
2 20 to 39 b XOR c XOR d 6ed9eba1
3 40 to 59 (b AND c) OR (b AND d) OR (c AND d)  8f1bbcdc
4 60 to 79 b XOR c XOR d ca62c1d6

 

For (16 to 79)

 

    W[i]  = (W[i-3] XOR W[i-8] XOR W[i-14] XOR W[i-16]) leftrotate 1  ( i from 16 to 79)

 

  • FOR the 1st round(1 to 19):

 

Initialize a,b,c,d,e registers

a = H[0] = 67452301

b = H[1] = efcdab89

c = H[2] = 98badcfe

d = H[3] =10325476

e = H[4] = c3d2e1f0

 

Calculating the function,

 

f = (b AND c) OR ((NOT b) AND d)

= (efcdab89 AND 98badcfe) OR (NOT( efcdab89) AND 10325476)

= 88888888  OR  (10325476 AND 10325476)

= 88888888 OR 10325476

= 98badcfe

 

K= 5a827999

 

Now At i=0

 

a leftrotate 5 =  67452301 leftrotate 5

              =011001110100010100100011000000 left rotate 5

Advertisement

            11001110100010100100011000000010 (1 rotation)

     10011101000101001000110000000101 (2 rotation)

     00111010001010010001100000001011 (3 rotation)

     01110100010100100011000000010110 (4 rotation)

     11101000101001000110000000101100 (5 rotaion)

Hex = e8a4602c

 

temp = (a leftrotate 5) + f + e + k + W[i]

   = e8a4602c + 98badcfe+ c3d2e1f0 + 5A827999 + w[0]

   = e8a4602c + 98badcfe+ c3d2e1f0 + 5A827999 + 61626380

   =  1815f3d2a + 11e555b89+  61626380

   = 29fb498b3 + 61626380

   = 30116fc33

here most significant bit 3 is overflow

 

e = d = 10325476 

d = c = 98badcfe 

c = b left roate 30 = efcdab89  leftrotate 30

Efcdab89 = 11101111110011011010101110001001

11011111100110110101011100010011 (1 rotation)

10111111001101101010111000100111 (2 rotation)

01111110011011010101110001001111 (3 rotation)

11111100110110101011100010011110 ( 4 rotation)

11111001101101010111000100111101 (5 rotation)

11110011011010101110001001111011 ( 6 rotation)

11100110110101011100010011110111 ( 7 rotation)

11001101101010111000100111101111 ( 8 rotation)

10011011010101110001001111011111 (9 rotation)

00110110101011100010011110111111 ( 10 rotation)

01101101010111000100111101111110 ( 11rotation)

11011010101110001001111011111100 ( 12 rotation)

10110101011100010011110111111001 (13 rotation)

01101010111000100111101111110011 ( 14rotation )

11010101110001001111011111100110 (15 rotation)

10101011100010011110111111001101 ( 16 rotation)

01010111000100111101111110011011 ( 17 rotation)

10101110001001111011111100110110 ( 18 rotation)

01011100010011110111111001101101 (19 rotation)

10111000100111101111110011011010 (20 rotation)

01110001001111011111100110110101 ( 21 rotation)

11100010011110111111001101101010 ( 22 rotation)

11000100111101111110011011010101 (23 rotation)

10001001111011111100110110101011 (24 rotation)

00010011110111111001101101010111 (25 rotation)

00100111101111110011011010101110 ( 26 rotation)

01001111011111100110110101011100 (27 rotation)

10011110111111001101101010111000 (28 rotation)

00111101111110011011010101110001 (29 rotation)

01111011111100110110101011100010 (30 rotation)

 

Hex value = 7bf36ae2

c= 7bf36ae2

b = a = 67452301

a = temp

 

Therefore at i=0

a= 0116fc33 , b= 67452301, c= 7bf36ae2, d =  98badcfe , e =  10325476

 

Similarly (by using the updated value of a,b,c,d,e)

 

At i=1   (using a,b,c,d,e updated value at i=0);

f = (b AND c) OR ((NOT b) AND d)  

temp = (a leftrotate 5) + f + e + k + w[1] = 8990536d

e = d = 98badcfe

d = c =  7bf36ae2 

c = b left roate 30 = 59d148c0

b =a =  0116fc33

a =temp

 

a = 8990536d,  b= 0116fc33, c= 59d148c0, d= 7bf36ae2, e =98badcf

 

Similarly 

At i = 2

a =a1390f08,  b= 8990536d, c= c045bf0c, d=59d148c0, e =7bf36ae2

 

Similarly i=3 to i =15

SHA-1 Algorithm showing all intermediate step

At i=16; (using a,b,c,d,e updated value at i=15);

f = (b AND c) OR ((NOT b) AND d)  

   = (196bee77 AND 644a3da5) OR (NOT(196bee77) AND 1181ed99)

   =  004a2c25 OR (e6941188 AND 1181ed99)

    =    004a2c25  OR 00800188

      = 00ca2dad

 

W[16] = W[16-3] XOR W[16-8] XOR W[16-14] XOR W[16-16]) leftrotate 1

 

             = (W[13] XOR W[8] XOR W[2] XOR W[0] ) leftrotate 1

             =(00000000 XOR 00000000 XOR 00000000 XOR 61626380) left rotate 1

=  (61626380) left rotate 1

             =  c2c4c700

 

temp = (a leftrotate 5) + f + e + k + W[16] 

          =  17bac5e4 + 00ca2dad + 18c623f9 + 5a827999 + c2c4c700

           = 1884f391 + 73489d92 + c2c4c700

           = 1884f391 + 1360d6492

           = 14e925823

Here 1 is the overflow

 

e = d = 1181ed99 

d = c =  644a3da5

c = b left roate 30 = c65afb9d

b =a =  20bdd62f

a =temp

Therefore at i=16 to 19 (using a,b,c,d,e updated value at i=15);

showing all intermediate steps

 

    • FOR 2nd round(20 to 39):

    a = fd9e1d7d, 

    b = dc64901d, 

    c = 20aa99ca, 

    d = d3a49608, 

    e = c82f758b

    Calculating the function,

     

    f = b XOR c XOR d

    Advertisement

    =  (dc64901d XOR 20aa99ca XOR d3a49608)

    = 2f6a9fdf

     

    K= 6ed9eba1

     

    Now,

    AT i=20  (using a,b,c,d,e updated value at i=19);

    temp = (a leftrotate 5) + f + e + k + W[20] 

             =  b3c3afbf + 2f6a9fdf +  c82f758b + 6ed9eba1 +W[20]

              =1a37b0ca

     

    e = d = d3a49608

    d = c = 20aa99ca

    c = b left roate 30 =77192407

    b = a = fd9e1d7d 

    a =temp

    a= 1a37b0ca, b = fd9e1d7d, c = 77192407, d = 20aa99ca, e = d3a49608

    Similarly i=21 to i = 39

SHA-1 Algorithm showing all intermediate steps

    • For the 3rd round(40 to 59): 

    a =32de1cba

    b=4c986405

    c=f718e5cf 

    d=03d447f6  

    e=f72eec32

    Calculating the function,

     

    f = (b AND c) OR (b AND d) OR (c AND d) 

      = (4c986405 AND f718e5cf ) OR (4c986405 AND 03d447f6) OR (f718e5cf  AND 03d447f6)

      = 44186405 OR 00904404 OR 031045c6

      = 479865c7

    K=8f1bbcdc

     

    Now,

    AT i=40  (using a,b,c,d,e updated value at i=39);

    temp = (a leftrotate 5) + f + e + k + W[40]  = fc87dedf 

    e = d = 03d447f6

    d = c = f718e5cf 

    c = b left roate 30 =53261901

    b = a = 32de1cba 

    a =temp

       

    a=fc87dedf , b = 32de1cba, c = 53261901, d =  f718e5cf, e = f72eec32

    Similarly i=41 to i = 59

Compute the message Digest using SHA-1 Algorithm showing all intermediate steps

 

    • For the 4th round(60 to 79):

    a =3f52de5a

    b=09d785fd

    c=3498bfd4 

    d=f211824f  

    e=d79915ab

    Calculating the function,

    f = b XOR c XOR d

       = 09d785fd XOR 3498bfd4 XOR f211824f  

       = cf5eb866

    K=ca62c1d6

    Now,

    AT i=60 (using a,b,c,d,e updated value at i=59);

    temp = (a leftrotate 5) + f + e + k + W[60]  = d756c147,

    e = d = f211824f 

    d = c = 3498bfd4

    c = b left roate 30 =4275e17f

    b = a = 32de1cba 

    a =temp

       

    a=d756c147, b = 3f52de5a, c = 4275e17f, d =  3498bfd4, e = f211824f 

     

    Similarly i=61 to i = 78

CRytography assignment solution

Similarly at i=79 (using a,b,c,d,e updated value at i=78);

 

a=42541b35, b=5738d5e1, c=21834873, d=681e6df6, e=d8fdf6ad 

 

Now message-digest,

H[0] = H[0] + a = 67452301 + 42541b35 = a9993e36

H[1] = H[1]+b = efcdab89 + 5738d5e1 = 14706816a (1 is overflow here)

H[2] = H[2]+c = 98badcfe + 21834873 = ba3e2571

H[3] =H[3]+d = 10325476 +681e6df6 = 7850c26c

H[4] = H[4] +e =c3d2e1f0 + d8fdf6ad = 19cd0d89d (1 is overflow here)

 

Therefore message digest = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

 

Which is 160 bits.

 

Ques 2. Consider RSA encryption with public encryption key (n, e) = (28673, 7).

a) Use Pollard’s rho – method to factor n (show steps). Start with the number 14 and use the iteration function f (x) = x^2 + 1.

b) Compute the decryption of c = 2.

Solution:

a)

Here, given n = 28673

start with the number 14,

And  iteration function f (x) = x2 + 1.

Now using pollard’s rho-method

Now we compute for k=1, Xk and Yk

 X1 =   142 + 1 (mod 28673 )   

      =  197 mod 28673

      =  197

And

 Y1 =   (1972 + 1)2 +1  (mod 28673 )   

      =  1506216101 mod 28673

      =  23411

Now here we need to check,  GCD of (| Y1 – X1 |, n) > 1 or not

GCD(| Y1 – X1 |, n) = GCD((|23411 – 197|), 28673)

                                = GCD(23214, 28673)

Using the Euclidean algorithm  we get,

q r1 r2 r
1 28673 23214 5459
4 23214 5459 1378
3 5459 1378 1325
1 1378 1325 53
25 1325 53 0
53 0

By using the Euclidean algorithm  we get,

GCD(23214, 28673) = 53> 1

So one factor will be (P) = 53

Now the other factor will be (Q)= 28673/ 53 = 541

Therefore Factor of n = 53 and 541

                                   

b)

Given,

 public encryption key (n, e) = (28673, 7)

And c =2

We have already calculated using Pollard’s rho method factor of 28673 which is  53 and 541.

Therefore P=53 and Q=541;

Now we can calculate

 Φ(n) =  (P-1)x(Q-1) 

  = 52 x 540 

  = 28080

We can also calculate private key d, by using the formula,

ed  = 1 mod Φ(n)

7d = 1 mod 28080

Here we get, private key (d) = 8023

Now  we can decrypt the ciphertext,

M  = Cd mod n

     = (2)8023 mod 28673

Since factor of 28673 = 53 x 541

Therefore we can write,

x= (2)8023  mod 53                                   And

  = 14 mod 53    

  x = (2)8023  mod 541

     = 346 mod 541

 

Now applying Chinese Remainder theorem we get

x = 10084

Therefore M = 10084

 

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here