SHA1算法原理.doc

1、SHA1 算法原理1 SHA1 算法简介安全哈希算法（Secure HashAlgorithm）主要适用于数字签名标准（Digital Signature StandardDSS）里面定义的数字签名算法（Digital Signature AlgorithmDSA） 。对于长度小于 264 位的消息，SHA1 会产生一个 160 位的消息摘要。当接收到消息的时候，这个消息摘要可以用来验证数据的完整性。在传输的过程中，数据很可能会发生变化，那么这时候就会产生不同的消息摘要。 SHA1 有如下特性：不可以从消息摘要中复原信息；两个不同的消息不会产生同样的消息摘要。2 术语和概念2.1 位(Bit)

2、，字节（ Byte）和字（Word ）SHA1 始终把消息当成一个位（bit ）字符串来处理。本文中，一个“字” （Word）是 32 位，而一个“字节” （Byte ）是 8 位。比如，字符串“abc”可以被转换成一个位字符串：01100001 0110001001100011。它也可以被表示成 16 进制字符串: 0x616263.2.2 运算符和符号下面的逻辑运算符都被运用于“字” （Word） XY = X， Y 逻辑与 X / Y = X， Y 逻辑或 X XOR Y= X， Y 逻辑异或 X = X 逻辑取反 X+Y 定义如下： 字 X 和 Y 代表两个整数 x 和 y, 其中 0

3、 32-n) Xn 是抛弃右边的 n 位，将各个位依次向右移动 n 位，然后在左边的 n 位填 0。因此可以叫 Sn(X)位循环移位运算3 SHA1 算法描述在 SHA1 算法中，我们必须把原始消息（字符串，文件等）转换成位字符串。SHA1 算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先，我们将它转换成位字符串如下： 01100001 01100010 01100011 a=97 b=98 c=99 这个位字符串的长度为 24。下面我们需要 5 个步骤来计算MD5。3.1 补位消息必须进行补位，以使其长度在对 512 取模以后的余数是448。也就是说， （补位后的消息长度）

4、%512 = 448。即使长度已经满足对 512 取模后余数是 448，补位也必须要进行。 补位是这样进行的：先补一个 1，然后再补 0，直到长度满足对512 取模后余数是 448。总而言之，补位是至少补一位，最多补 512位。还是以前面的“abc ”为例显示补位的过程。 原始信息： 01100001 01100010 01100011 补位第一步：01100001 01100010 01100011 1 首先补一个“1” 补位第二步：01100001 01100010 01100011 10.0 然后补 423 个“0” 我们可以把最后补位完成后的数据用 16 进制写成下面的样子 61626

5、380 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 现在，数据的长度是 448 了，我们可以进行下一步操作。3.2 补长度所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个 64 位的数据来表示原始消息的长度。如果消息长度不大于 264，那么第一个字就是 0。在进行了补长度的操作以后，整个消息就变成下面这样了（16 进制格式） 61626380 00000000 00000000 0

6、0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000018 如果原始的消息长度超过了 512，我们需要将它补成 512 的倍数。然后我们把整个消息分成一个一个 512 位的数据块，分别处理每一个数据块，从而得到消息摘要。3.3 使用的常量一系列的常量字 K(0), K(1), . , K(79)，如果以 16 进制给出。它们如下： Kt = 0x5A827999 (0 = t = 19) Kt = 0x6ED9EBA1 (2

7、0 = t = 39) Kt = 0x8F1BBCDC (40 = t = 59) Kt = 0xCA62C1D6 (60 = t = 79).3.4 需要使用的函数在 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) o

8、r (C AND D) (40 = t = 59) ft(B,C,D) = B XOR C XOR D (60 = t = 79).3.5 计算消息摘要必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区，每个都由 5 个 32 位的字组成，还需要一个 80 个 32位字的缓冲区。第一个 5 个字的缓冲区被标识为 A，B，C，D，E。第一个 5 个字的缓冲区被标识为 H0, H1, H2, H3, H4 。80 个字的缓冲区被标识为 W0, W1,., W79 另外还需要一个一个字的 TEMP 缓冲区。 为了产生消息摘要，在第 4 部分中定义的 16 个字的数据块 M1, M2

9、,., Mn 会依次进行处理，处理每个数据块 Mi 包含 80 个步骤。 在处理每个数据块之前，缓冲区Hi 被初始化为下面的值（16进制） H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2E1F0. 现在开始处理 M1, M2, . , Mn。为了处理 Mi,需要进行下面的步骤 (1). 将 Mi 分成 16 个字 W0, W1, . , W15, W0 是最左边的字 (2). 对于 t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-1

10、6). (3). 令 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; (5). 令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. 在处理完所有的 Mn, 后，消息摘要是一个 160 位的字符串，以下面的顺序标识 H0 H1 H2 H3 H4.对于 SHA256,SHA384,SHA512。你也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。sha1 是一种比 md5 的安全性强的算法，当然 sha256 和 sha512 更好，但计算开销更大一些,理论上，凡是采取“消息摘要”方式的数字验证算法都是有“碰撞”的也就是两个不同的东西算出的消息摘要相同，互通作弊图就是如此。但是安全性高的算法要找到指定数据的“碰撞”很困难（困难到用暴力法寻找要花去几百年甚至几千年） ，而利用公式来计算“碰撞”就更困难目前为止通用安全算法中仅有 md5 被破解.