首页 > 代码库 > 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)