Skip to content

Latest commit

 

History

History
94 lines (83 loc) · 4.35 KB

从RFC3174中理解SHA1算法.md

File metadata and controls

94 lines (83 loc) · 4.35 KB

一、前置知识点

总体上来说，SHA1算法和MD5算法很类似（因为它们都属于是针对于信息摘要的哈希算法），大体的算法流程也是基本相同，可以回忆下MD5算法的五个步骤，可以说SHA1是升级版本的MD5。不同点从直观上看，SHA1返回的信息长度是160位（20个字节），而MD5则是128位（16个字节），因此相较于MD5算法来说会更加安全一些（不过也仅仅是一些而已）

二、算法流程

算法流程就不多做介绍，和MD5算法类似，同样需要通过五个步骤来完成

1 补位

基本一样，不做额外说明

2 记录信息长度

同上

3 初始化变量

这一步开始有不同了，SHA1算法也同样有初始变量，与MD5不同的是，MD5最终是依靠初始变量组合起来的16个字节的结果，而SHA1结果为20个字节，因此也在初始变量中多了4个字节，定义如下

uint32_t H0 = 0x67452301;   // 0x01, 0x23, 0x45, 0x67
uint32_t H1 = 0xEFCDAB89;   // 0x89, 0xAB, 0xCD, 0xEF
uint32_t H2 = 0x98BADCFE;   // 0xFE, 0xDC, 0xBA, 0x98
uint32_t H3 = 0x10325476;   // 0x76, 0x54, 0x32, 0x10
uint32_t H4 = 0xC3D2E1F0;   // 0xF0, 0xE1, 0xD2, 0xC3

初始化变量的个数和结果有直接关系，因为结果是由初始化变量组合在一起的

4 处理分组数据

这一步大体结构一样，但是处理的方式有点不同

分组方式不说了，同样是将数据处理成了N*512的分组形式，下面再对每个分组进行二次分组成16份，也就是16*32=512，每个子分组是32bit的数据，着重讲讲和MD5算法的不同点

相比于MD5的四轮计算，SHA1也会涉及到四轮计算，每轮则增加到20次，一共是80次非线性函数计算，对于每轮使用的数据和MD5也是有区别的，MD5处理每次分组的数据就是把数据分成16组，每轮使用的都是这16组数据，而SHA1则不一样，只有前16组使用的是拆分的数据，从16-80则根据公式得到新的数据

/*  a. Divide M(i) into 16 words W(0), W(1), ..., W(15), where W(0) is the left - most word. */
for (t = 0; t <= 15; t++)
{
    W[t] = M[t];
}

/*  b. For t = 16 to 79 let
W(t) = S^1(W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16)). */
for (t = 16; t <= 79; t++)
{
    W[t] = MoveLeft(W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16], 1);
}

首先先看看四个非线性函数参考（二、四轮其实是一样的）

/*                  f(X, Y, Z)                      */
/* [0,  19] */
static uint32_t Ch(uint32_t X, uint32_t Y, uint32_t Z)
{
    return (X & Y) ^ ((~X) & Z);
}
/* [20, 39] */  /* [60, 79] */
static uint32_t Parity(uint32_t X, uint32_t Y, uint32_t Z)
{
    return X ^ Y ^ Z;
}
/* [40, 59] */
static uint32_t Maj(uint32_t X, uint32_t Y, uint32_t Z)
{
    return (X & Y) ^ (X & Z) ^ (Y & Z);
}

接着是每次计算所会涉及到的常量K，还记得在MD5中有个常量表T表，T表是根据公式计算得来的64个常量，而K就是直接给好的

K(t) = 5A827999         ( 0 <= t <= 19)

K(t) = 6ED9EBA1         (20 <= t <= 39)

K(t) = 8F1BBCDC         (40 <= t <= 59)

K(t) = CA62C1D6         (60 <= t <= 79)

文档也给的很干脆，每轮一个固定常量

下面该讲到具体的处理了，MD5算法每次计算改变的只是一个变量的值，但是SHA1每次计算则会改变五个变量的值

uint32_t temp = MoveLeft(A, 5) + Ch(B, C, D) + E + W[t] + K[0];
E = D;
D = C;
C = MoveLeft(B, 30);
B = A;
A = temp;

最终只需要将得到的a、b、c、d重新赋值再作为初始变量传递给下一分组计算即可

5 输出结果

在经过分组计算后能够得到A、B、C、D、E，从低位字节A开始，高位字节E结束

总结

文中每个步骤都在对比MD5和SHA1的异同，可以看出，虽然结果上SHA1只是多了4个字节，但是在细节上还是有很大的提升，算法整体上更复杂了，变化也更多了，下面总体归纳下两个算法的异同

算法 MD5 SHA1
分组数据处理 使用同一套16组数据 基于16组数据的基础上变化得到额外64组数据
初始化常量 4个 5个
非线性函数 4个 4个
常量表 T常量表分配给64次计算，各不相同 K表分配给80次计算，每20次使用同一个常量
常量变化 每次计算重新给一个常量赋值 每次计算所有常量全部发生变化