首页 > 代码库 > SHA1 安全哈希算法(Secure Hash Algorithm)
SHA1 安全哈希算法(Secure Hash Algorithm)
安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准 (Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64位的消息,SHA1会产生一个160位的消息摘要。当接收到消息的时候,这个消息摘要可以用来验证数据的完整性。在传输的过程中,数据很可能会发生变化,那么这时候就会产生不同的消息摘要。 SHA1有如下特性:不可以从消息摘要中复原信息;两个不同的消息不会产生同样的消息摘要,(但会有1x10 ^ 48分之一的机率出现相同的消息摘要,一般使用时忽略)。
术语和概念
位,字节和字
SHA1始终把消息当成一个位(bit)字符串来处理。本文中,一个字(Word)是32位,而一个字节(Byte)是8位。比如,字符串“abc”可以被转换成一个位字符串:01100001 01100010 01100011。它也可以被表示成16进制字符串: 0x616263.
运算符和符号
下面的逻辑运算符都被运用于“字”(Word)
X & Y = X, Y逻辑与
X | Y = X, Y逻辑或
X ^ 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)
SHA1算法描述
在SHA1算法中,我们必须把原始消息(字符串,文件等)转换成位字符串。SHA1算法只接受位作为输入。假设我们对字符串“abc”产生消息摘要。首先,我们将它转换成位字符串如下:
01100001 01100010 01100011
―――――――――――――
‘a’=97 ‘b’=98 ‘c’=99
这个位字符串的长度为24。下面我们需要5个步骤来计算消息摘要MAC。
补位
消息必须进行补位,以使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)%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进制写成下面的样子
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
经过以上的处理之后,数据的长度是448了,我们可以进行下一步操作。
补长度
所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式)
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018
如果原始的消息长度超过了512,我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块,分别处理每一个数据块,从而得到消息摘要。
使用的常量
一系列的常量字K(0), K(1), ... , K(79),如果以16进制给出。它们如下:
Kt = 0x5A827999 (0 <= t <= 19)
Kt = 0x6ED9EBA1 (20 <= t <= 39)
Kt = 0x8F1BBCDC (40 <= t <= 59)
Kt = 0xCA62C1D6 (60 <= t <= 79).
使用的函数
在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).
计算消息摘要
必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。第二个5个字的缓冲区被标识为H0, H1, H2, H3, H4
。80个字的缓冲区被标识为W0, W1,..., W79
另外还需要一个一个字的TEMP缓冲区。
为了产生消息摘要,在第3.2部分中定义的512位(16个字)的数据块M1, M2,..., 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 令
W[t] = S1(W[t-3] XOR W[t-8] XOR W[t-14] XOR W[t-16]).
(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在许多安全协议中广为使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被视为是MD5(更早之前被广为使用的散列函数)的后继者。
附录案例代码:
1 public class SHA1 { 2 private final int[] abcde = { 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0 }; 3 // 摘要数据存储数组 4 private int[] digestInt = new int[5]; 5 // 计算过程中的临时数据存储数组 6 private int[] tmpData = http://www.mamicode.com/new int[80]; 7 8 // 计算sha-1摘要 9 private int process_input_bytes(byte[] bytedata) { 10 // 初试化常量 11 System.arraycopy(abcde, 0, digestInt, 0, abcde.length); 12 // 格式化输入字节数组,补10及长度数据 13 byte[] newbyte = byteArrayFormatData(bytedata); 14 // 获取数据摘要计算的数据单元个数 15 int MCount = newbyte.length / 64; 16 // 循环对每个数据单元进行摘要计算 17 for (int pos = 0; pos < MCount; pos++) { 18 // 将每个单元的数据转换成16个整型数据,并保存到tmpData的前16个数组元素中 19 for (int j = 0; j < 16; j++) { 20 tmpData[j] = byteArrayToInt(newbyte, (pos * 64) + (j * 4)); 21 } 22 // 摘要计算函数 23 encrypt(); 24 } 25 return 20; 26 } 27 28 // 格式化输入字节数组格式 29 private byte[] byteArrayFormatData(byte[] bytedata) { 30 // 补0数量 31 int zeros = 0; 32 // 补位后总位数 33 int size = 0; 34 // 原始数据长度 35 int n = bytedata.length; 36 // 模64后的剩余位数 37 int m = n % 64; 38 // 计算添加0的个数以及添加10后的总长度 39 if (m < 56) { 40 zeros = 55 - m; 41 size = n - m + 64; 42 } else if (m == 56) { 43 zeros = 63; 44 size = n + 8 + 64; 45 } else { 46 zeros = 63 - m + 56; 47 size = (n + 64) - m + 64; 48 } 49 // 补位后生成的新数组内容 50 byte[] newbyte = new byte[size]; 51 // 复制数组的前面部分 52 System.arraycopy(bytedata, 0, newbyte, 0, n); 53 // 获得数组Append数据元素的位置 54 int l = n; 55 // 补1操作 56 newbyte[l++] = (byte) 0x80; 57 // 补0操作 58 for (int i = 0; i < zeros; i++) { 59 newbyte[l++] = (byte) 0x00; 60 } 61 // 计算数据长度,补数据长度位共8字节,长整型 62 long N = (long) n * 8; 63 byte h8 = (byte) (N & 0xFF); 64 byte h7 = (byte) ((N >> 8) & 0xFF); 65 byte h6 = (byte) ((N >> 16) & 0xFF); 66 byte h5 = (byte) ((N >> 24) & 0xFF); 67 byte h4 = (byte) ((N >> 32) & 0xFF); 68 byte h3 = (byte) ((N >> 40) & 0xFF); 69 byte h2 = (byte) ((N >> 48) & 0xFF); 70 byte h1 = (byte) (N >> 56); 71 newbyte[l++] = h1; 72 newbyte[l++] = h2; 73 newbyte[l++] = h3; 74 newbyte[l++] = h4; 75 newbyte[l++] = h5; 76 newbyte[l++] = h6; 77 newbyte[l++] = h7; 78 newbyte[l++] = h8; 79 return newbyte; 80 } 81 82 private int f1(int x, int y, int z) { 83 return (x & y) | (~x & z); 84 } 85 86 private int f2(int x, int y, int z) { 87 return x ^ y ^ z; 88 } 89 90 private int f3(int x, int y, int z) { 91 return (x & y) | (x & z) | (y & z); 92 } 93 94 private int f4(int x, int y) { 95 return (x << y) | x >>> (32 - y); 96 } 97 98 // 单元摘要计算函数 99 private void encrypt() { 100 for (int i = 16; i <= 79; i++) { 101 tmpData[i] = f4(tmpData[i - 3] ^ tmpData[i - 8] ^ tmpData[i - 14] ^ tmpData[i - 16], 1); 102 } 103 int[] tmpabcde = new int[5]; 104 for (int i1 = 0; i1 < tmpabcde.length; i1++) { 105 tmpabcde[i1] = digestInt[i1]; 106 } 107 for (int j = 0; j <= 19; j++) { 108 int tmp = f4(tmpabcde[0], 5) + f1(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] + tmpData[j] 109 + 0x5a827999; 110 tmpabcde[4] = tmpabcde[3]; 111 tmpabcde[3] = tmpabcde[2]; 112 tmpabcde[2] = f4(tmpabcde[1], 30); 113 tmpabcde[1] = tmpabcde[0]; 114 tmpabcde[0] = tmp; 115 } 116 for (int k = 20; k <= 39; k++) { 117 int tmp = f4(tmpabcde[0], 5) + f2(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] + tmpData[k] 118 + 0x6ed9eba1; 119 tmpabcde[4] = tmpabcde[3]; 120 tmpabcde[3] = tmpabcde[2]; 121 tmpabcde[2] = f4(tmpabcde[1], 30); 122 tmpabcde[1] = tmpabcde[0]; 123 tmpabcde[0] = tmp; 124 } 125 for (int l = 40; l <= 59; l++) { 126 int tmp = f4(tmpabcde[0], 5) + f3(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] + tmpData[l] 127 + 0x8f1bbcdc; 128 tmpabcde[4] = tmpabcde[3]; 129 tmpabcde[3] = tmpabcde[2]; 130 tmpabcde[2] = f4(tmpabcde[1], 30); 131 tmpabcde[1] = tmpabcde[0]; 132 tmpabcde[0] = tmp; 133 } 134 for (int m = 60; m <= 79; m++) { 135 int tmp = f4(tmpabcde[0], 5) + f2(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] + tmpData[m] 136 + 0xca62c1d6; 137 tmpabcde[4] = tmpabcde[3]; 138 tmpabcde[3] = tmpabcde[2]; 139 tmpabcde[2] = f4(tmpabcde[1], 30); 140 tmpabcde[1] = tmpabcde[0]; 141 tmpabcde[0] = tmp; 142 } 143 for (int i2 = 0; i2 < tmpabcde.length; i2++) { 144 digestInt[i2] = digestInt[i2] + tmpabcde[i2]; 145 } 146 for (int n = 0; n < tmpData.length; n++) { 147 tmpData[n] = 0; 148 } 149 } 150 151 // 4字节数组转换为整数 152 private int byteArrayToInt(byte[] bytedata, int i) { 153 return ((bytedata[i] & 0xff) << 24) | ((bytedata[i + 1] & 0xff) << 16) | ((bytedata[i + 2] & 0xff) << 8) 154 | (bytedata[i + 3] & 0xff); 155 } 156 157 // 整数转换为4字节数组 158 private void intToByteArray(int intValue, byte[] byteData, int i) { 159 byteData[i] = (byte) (intValue >>> 24); 160 byteData[i + 1] = (byte) (intValue >>> 16); 161 byteData[i + 2] = (byte) (intValue >>> 8); 162 byteData[i + 3] = (byte) intValue; 163 } 164 165 // 将字节转换为十六进制字符串 166 private static String byteToHexString(byte ib) { 167 char[] Digit = { ‘0‘, ‘1‘, ‘2‘, ‘3‘, ‘4‘, ‘5‘, ‘6‘, ‘7‘, ‘8‘, ‘9‘, ‘A‘, ‘B‘, ‘C‘, ‘D‘, ‘E‘, ‘F‘ }; 168 char[] ob = new char[2]; 169 ob[0] = Digit[(ib >>> 4) & 0X0F]; 170 ob[1] = Digit[ib & 0X0F]; 171 String s = new String(ob); 172 return s; 173 } 174 175 // 将字节数组转换为十六进制字符串 176 private static String byteArrayToHexString(byte[] bytearray) { 177 String strDigest = ""; 178 for (int i = 0; i < bytearray.length; i++) { 179 strDigest += byteToHexString(bytearray[i]); 180 } 181 return strDigest; 182 } 183 184 // 计算sha-1摘要,返回相应的字节数组 185 public byte[] getDigestOfBytes(byte[] byteData) { 186 process_input_bytes(byteData); 187 byte[] digest = new byte[20]; 188 for (int i = 0; i < digestInt.length; i++) { 189 intToByteArray(digestInt[i], digest, i * 4); 190 } 191 return digest; 192 } 193 194 // 计算sha-1摘要,返回相应的十六进制字符串 195 public String getDigestOfString(byte[] byteData) { 196 return byteArrayToHexString(getDigestOfBytes(byteData)); 197 } 198 199 public static void main(String[] args) { 200 String data = "http://www.mamicode.com/123456"; 201 String digest = new SHA1().getDigestOfString(data.getBytes()); 202 } 203 }
SHA1 安全哈希算法(Secure Hash Algorithm)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。