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

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

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,

01100001 01100010 01100011 1 00….00 0…011000 Now the message is multiple of 512bits

Initialization of  hash value;

H = 67452301

H = efcdab89

H =10325476

H = c3d2e1f0

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

16 sub-blocks:

W = 01100001 01100010 01100011 10000000 = 61626380

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 00000000 00000000 00000000 00000000 = 00000000

W = 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 = 67452301

b = H = efcdab89

d = H =10325476

e = H = 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

K= 5a827999

Now At i=0

a leftrotate 5 =  67452301 leftrotate 5

=011001110100010100100011000000 left rotate 5

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

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

=  1815f3d2a + 11e555b89+  61626380

= 29fb498b3 + 61626380

= 30116fc33

here most significant bit 3 is overflow

e = d = 10325476

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 = 8990536d

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 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

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

= (W XOR W XOR W XOR W ) 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

=  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); • 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

=  (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

=  b3c3afbf + 2f6a9fdf +  c82f758b + 6ed9eba1 +W

=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 • 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  = 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 • 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  = 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 Similarly at i=79 (using a,b,c,d,e updated value at i=78);

Now message-digest,

H = H + a = 67452301 + 42541b35 = a9993e36

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

H = H+c = 98badcfe + 21834873 = ba3e2571

H =H+d = 10325476 +681e6df6 = 7850c26c

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

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

Which is 160 bits.

b) Compute the decryption of c = 2.

Solution:

a)

Here, given n = 28673

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