SHA1算法原理及示例.md

Posted by lizhao on 07-09,2019

SHA1算法原理及示例

输入任意的一个字符串,将会获得一个160位的二进制信息摘要(我们看到的,一般是已经转换成十六进制消息,共40位) 这篇文章将会以 Zab 为消息,然后进行转换

处理的步骤

声明常量及运算符:

  1. 运算符和符号

    X^Y    = X, Y逻辑与
    
    X // Y   = X, Y逻辑或
    
    X XOR Y= X, Y逻辑异或
    
    ~X     =   X逻辑取反
    
    X+Y定义如下:
    
    字 X 和 Y 代表两个整数 x 和y, 其中 0 <= x < 2^32 且 0 <= y < 2^32. 令整数z = (x + y) mod 2^32. 这时候 0 <= z < 2^32. 将z转换成字Z, 那么就是 Z = X + Y.
    
    循环左移位操作符Sn(X)。X是一个字,n是一个整数,0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)
    
    X<<n定义如下:抛弃最左边的n位数字,将各个位依次向左移动n位,然后用0填补右边的n位(最后结果还是32位)。X>>n是抛弃右边的n位,将各个位依次向右移动n位,然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算
    
  2. 常量K

    这个东西下面运算的时候用到,t是循环变量,是传入的参数,类似于分段函数,用到再往这里翻

    Kt = 0x5A827999 (0 <= t <= 19)

    Kt = 0x6ED9EBA1 (20 <= t <= 39)

    Kt = 0x8F1BBCDC (40 <= t <= 59)

    Kt = 0xCA62C1D6 (60 <= t <= 79).

  3. 定义函数

在SHA1中我们需要一系列的函数。
每个函数ft (0 <= t <= 79)都操作32位字B,C,D并且产生32位字作为输出。
ft(B,C,D)可以如下定义

ft(B,C,D) = (B AND C) or ((NOT B) AND D) ( 0 <= t <= 19)

ft(B,C,D) = B XOR C XOR D             (20 <= t <= 39)

ft(B,C,D) = (B AND C) or (B AND D) or (C AND D) (40 <= t <= 59)

ft(B,C,D) = B XOR C XOR D                    (60 <= t <= 79).

预处理

转成位

具体过程:按照该字符的ASCII码进行转换

补位

可以这么推算,最后输出的是一个定长的数据,那么输入的内容应该也是要保证长度,所以和md5一样,都有一个补位的机制。 具体过程:先补一个1,然后再补0,直到长度满足对512取模后余数是448

填入原数据长度

具体过程:原来的数据的长度,放到补位完消息的末尾,前面补0,共计64位

示例

原数据是Zab

转成位 
    Zab = 0x5A6162 = 0101 1010 0110 0001 0110 0010
    'Z' = 0x5A = 0101 1010
    'a' = 0x61 = 0110 0001
    'b' = 0x62 = 0110 0010
补位      
    先补一个1--》0101 1010 0110 0001 0110 0010 1 
    再补n个0 --》0101 1010 0110 0001 0110 0010 10...0
    十六进制写法:
        61626380 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000
    现在,数据的长度是448,对512取膜余数就是448
填入原数据长度
    原消息(0101 1010 0110 0001 0110 0010)长度是24,
    二进制消息后面补上:
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00011000
    十六进制补上 00000000 00000018
    结果就是
        61626380 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000018
        
下面就是按照这个十六进制角度来运算,二进制的可以自行转换

运算

求Mn

n的取值范围是0~15,根据我们之前预处理之后的数据获取

求Wn

n的范围是0~79,根据0.2标签的常量,0.3的函数,Mn,H0 ~ H4进行计算
> W t = M t , 当0≤t≤15   
> Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16) ,当16≤t≤79,这里的t-3,t-8是下标

求H0~H4

声明变量TEMP 
H0~H4 初始值
> H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0. 

声明变量A = H0, B = H1, C = H2, D = H3, E = H4.(4) 对于 t = 0 到 79,执行下面的循环
TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;
E = D; D = C; C = S30(B); B = A; A = TEMP;

按顺序拼接H0 H1 H2 H3 H4,即可得到结果

示例

第一步结束之后的数据为

> 61626380 00000000 00000000 00000000
> 00000000 00000000 00000000 00000000
> 00000000 00000000 00000000 00000000
> 00000000 00000000 00000000 00000018
求Mn
       M0 = 0x61626380
       M1 = 0x00000000
       M2 = 0x00000000
       M3 = 0x00000000
       ...
       M15 = 0x00000018
求Wn
    Wt = Mt , 当0≤t≤15   
    Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).当16≤t≤79
    W0 = M0 = 0x61626380
    W15 = M15 = 0x00000018
    ...
    W79 = 
求H0~H4

令 A = H0, B = H1, C = H2, D = H3, E = H4.
对于 t = 0 到 79,执行下面的循环
    TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;
    E = D; D = C; C = S30(B); B = A; A = TEMP;

令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. 

按顺序拼接H0 H1 H2 H3 H4,

参考链接:

SHA1算法实现及详解

SHA1算法原理