SHA1

SHA1 의 동작원리 pseudo code 로 이해해보기

 

 

이 그림은 한 단계의 opertaion을 나타냄

 

 

Note 1: All variables are unsigned 32-bit quantities and wrap modulo 2³² when calculating, except for
        ml, the message length, which is a 64-bit quantity, and
        hh, the message digest, which is a 160-bit quantity.
Note 2: All constants in this pseudo code are in big endian.
        Within each word, the most significant byte is stored in the leftmost byte position

Initialize variables:
//가장 초기의 입력되는 h값들 32bit words 5개.

h0 = 0x67452301          
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0

ml = message length in bits (always a multiple of the number of bits in a character).  //참고로 메세지 SHA1은 최대 메세지 크기는 2^64 보단 작아야함

Pre-processing:
append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
   is congruent to −64 ≡ 448 (mod 512)
append ml, the original message length, as a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.

Process the message in successive 512-bit chunks:
break message into 512-bit chunks             //메세지를 블록사이즈인 512bit 단위로 쪼갬
for each chunk                       
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15  

// 512bit 블록을 32bits크기의 word 16개로 쪼갬 //이 쪼개진 메세지는 80개의 step operation 중 16(0~15)개의 단계에 연산에 key처럼 연산할 때 더해짐(위에서 Mi가 이 쪼개진 메세지임 , key값은 밑에 코드를 보면 알겠지만 상수값이 설정되서 들어감.

    Extend the sixteen 32-bit words into eighty 32-bit words:
    for i from 16 to 79                

 //총단계는 80개의 단계이므로 나머지 (80-16)단계들에서 필요한 word들도 필요함. 그래서 기존 16개 워드를  아래 식에 넣어서 16~79단계에 쓰일 워드를 생성함.
        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

    Initialize hash value for this chunk:

//위에 a,b,c,d,e 상자에 해당 값을 각각 집어넣어 초기값으로 설정!
    a = h0
    b = h1
    c = h2
    d = h3
    e = h4

    Main loop:^[3][55]
    for i from 0 to 79
        if 0 ≤ i ≤ 19 then

            f = (b and c) or ((not b) and d)  // 0-19단계 에서는 위에 그림에  에  해당 함수(ch(x,y,z)라고 불림)로 씀 // 아래 표 참조
            k = 0x5A827999
        else if 20 ≤ i ≤ 39           
            f = b xor c xor d            // 20-39단계 에서는 위에 그림에  에  해당 함수(parity(x,y,z)라고 불림)로 씀               
            k = 0x6ED9EBA1
        else if 40 ≤ i ≤ 59
            f = (b and c) or (b and d) or (c and d)  // 40-59단계에선 Maj(x,y,z) 를 f함수로 쓰고
            k = 0x8F1BBCDC
        else if 60 ≤ i ≤ 79                  //60-79단계는 다시 parity(x,y,z) 를 f함수로 씀
            f = b xor c xor d
            k = 0xCA62C1D6

//1단계 처리되면 위치를 바꿔주는데 쓰임. 위에 그림으로 보면 화살표들이  재배치하는 것에 해당하는 내용임
        temp = (a leftrotate 5) + f + e + k + w[i]         
        e = d
        d = c
        c = b leftrotate 30
        b = a
        a = temp

    Add this chunk's hash to result so far:
    h0 = h0 + a
    h1 = h1 + b
    h2 = h2 + c
    h3 = h3 + d
    h4 = h4 + e

Produce the final hash value (big-endian) as a 160-bit number:   //최종 출력 되는 해쉬값은 160bit짜리 해쉬값이 생성됨.
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4

 

 

(코드출처 : 위키피디아 _ SHA1)

 

 

* f함수에 사용되는 boolean function의 진리표

(혹시 까먹었을까 알려줌 X = "값 상관 없다(무정의 값)" , = xor , = not x )

 

 

 

a) x의 값에 의해 y 또는 z가 선택됨

x	y	z	ch(x,y,z)
0	X	0	0
0	X	1	1
1	0	X	0
1	1	X	1

 

b) x,y,z 의 값 중 과반수가 되는 값을 선택.

x	y	z	maj(x,y,z)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

 

c) x, y, z, parity(x,y,z) / 각각은 0이나 1을 가질 것인데, parity함수의 결과값을 포함해서 1의 개수가 짝수가 되게 결과값을 갖도록 만든 함수임.

x	y	z	parity(x,y,z)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1