SHA
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
SHA (Secure Hash Algorithm hay Thuật toán Băm An toàn) là năm thuật toán được chấp nhận bởi FIPS dùng để chuyển một đoạn dữ liệu nhất định thành một đoạn dữ liệu có chiều dài không đổi với xác suất khác biệt cao. Những thuật giải này được gọi là "an toàn" bởi vì, theo nguyên văn của chuẩn FIPS 180-2 phát hành ngày 1 tháng 8 năm 2002:
"for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest. Any change to a message will, with a very high probability, result in a different message digest."
Tạm dịch đại ý là:
"1) Cho một giá trị băm nhất định được tạo nên bởi một trong những thuật giải SHA, việc tìm lại được đoạn dữ liệu gốc là không khả thi.
2) Việc tìm được hai đoạn dữ liệu khác nhau có cùng kết quả băm tạo ra bởi một trong những thuật giải SHA là không khả thi.
Bất cứ thay đổi nào trên đoạn dữ liệu gốc, dù nhỏ, cũng sẽ tạo nên một giá trị băm hoàn toàn khác với xác suất rất cao."
Năm thuật toán SHA là SHA-1 (trả lại kết quả dài 160 bit), SHA-224 (trả lại kết quả dài 224 bit), SHA-256 (trả lại kết quả dài 256 bit), SHA-384 (trả lại kết quả dài 384 bit), và SHA-512 (trả lại kết quả dài 512 bit). Thuật toán SHA là thuật giải băm mật được phát triển bởi Cục an ninh quốc gia Mĩ (National Security Agency hay NSA) và được xuất bản thành chuẩn của chính phủ Mĩ bởi Viện công nghệ và chuẩn quốc gia Mĩ (National Institute of Standards and Technology hay NIST). Bốn thuật toán sau thường được gọi chung là SHA-2.
SHA-1 được sử dụng rộng rãi trong nhiều ứng dụng và giao thức an ninh khác nhau, bao gồm TLS và SSL, PGP, SSH, S/MIME, và IPSec. SHA-1 được coi là thuật toán thay thế MD5, một thuật toán băm 128 bit phổ biến khác.
Hiện nay, SHA-1 không còn được coi là an toàn bởi đầu năm 2005, ba nhà mật mã học người Trung Quốc đã phát triển thành công một thuật toán dùng để tìm được hai đoạn dữ liệu nhất định có cùng kết quả băm tạo ra bởi SHA-1 [1]. Mặc dù chưa có ai làm được điều tương tự với SHA-2, nhưng vì về thuật toán, SHA-2 không khác biệt mấy so với SHA-1 nên nhiều nhà khoa học đã bắt đầu phát triển một thuật toán khác tốt hơn SHA [2][3]. NIST cũng đã khởi đầu một cuộc thi phát triển thuật toán băm mới an toàn hơn SHA, giống như quy trình phát triển chuẩn mã hóa tiên tiến (Advanced Encryption Standard hay AES)[4] Lưu trữ 2008-02-05 tại Wayback Machine.
SHA-2 sửa
SHA-2 bao gồm bốn giải thuật SHA-224, SHA-256, SHA-384 và SHA-512. Ba thuật giải SHA-256, SHA-384 và SHA-512 được xuất bản lần đầu năm 2001 trong bản phác thảo FIPS PUB 180-2. Năm 2002, FIPS PUB 180-2, bao gồm cả SHA-1 được chấp nhận thành chuẩn chính thức. Năm 2004, FIPS PUB 180-2 được bổ sung thêm một biến thể - SHA-224, với mục đích tạo ra một biến thể SHA-2 có độ dài khóa trùng với DES ba lần với 2 khóa (2TDES) - 112 bit. Những biến thể SHA-2 này được đăng ký Bằng sáng chế Hoa Kỳ số 6,829,355.
Về giải thuật, các biến thể của SHA-2 không khác nhau. Mặc dù chúng sử dụng giá trị biến và hằng số cũng như độ dài từ, v.v. khác nhau.
Mặc dù Gilbert và Handschuh (2003) đã nghiên cứu và không tìm ra điểm yếu của những biến thể này, chúng vẫn chưa được kiểm chứng kĩ như SHA-1.
Mã giả của thuật giải SHA-256:
Chú ý: Tất cả các biến đều là 32 bit không dấu quay vòng modulo 232 khi tính Khởi tạo biến (32 bit đầu tiên của phần phân số của căn bậc 2 của 8 số nguyên tố đầu tiên 2..19): h0:= 0x6a09e667 h1:= 0xbb67ae85 h2:= 0x3c6ef372 h3:= 0xa54ff53a h4:= 0x510e527f h5:= 0x9b05688c h6:= 0x1f83d9ab h7:= 0x5be0cd19 Khởi tạo hằng số (32 bit đầu tiên của phần phân số của căn bậc 3 của 64 số nguyên tố đầu tiên 2..311): kk[0..63]:= 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 7178f2 Tiền xử lý: Thêm bit '1' vào cuối đoạn dữ liệu gốc Thêm k bit '0', trong đó k là số nhỏ nhất >= 0 sao cho chiều dài của đoạn dữ liệu gốc (tính bằng ng bit) đồng dư với 448 (mod 512) Thêm độ dài của đoạn dữ liệu gốc (trước giai đoạn tiền xử lý), tính băng bits thể hiện bằng một số 64 bit big endian vào cuối đoạn dữ liệu Xử lý đoạn dữ liệu từng 512 bit một: Tách đoạn dữ liệu ra thành từng nhóm 512 bit Với mỗi nhóm Tách nhóm ra thành 16 nhóm 32 bit big endian wn w[0..15] Mở rộng 16 nhóm này thành 64 nhóm 32 bit: for i từ 16 đến 63 s0:= (ww[i-15] dịch phải 7) xor (w[i-15] dịch phải 18) xor (w[i-15] dịch phải 3) s1:= (ww[i-2] dịch phải 17) xor (w[i-2] dịch phải 19) xor (w[i-2] dịch phải 10) ww[i]:= w[i-16] + s0 + w[i-7] + s1 Khởi tạo giá trị băm cho nhóm này: a:= h0 b:= h1 c:= h2 d:= h3 e:= h4 f:= h5 g:= h6 h:= h7 = h7 Vòng lặp chính: for i từ 0 đến 63 s0:= (a dịch phải 2) xor (a dịch phải 13) xor (a dịch phải 22) maj:= (a and b) xor (a andc) xor(b andc) t2:= s0 + maj s1:= (e dịch phải 6) xor (e dịch phải 11) xor (e dịch phải 25) ch:= (e andf) xor((not e) and g) t1:= h + s1 + ch + kk[i] + w[i] h:= g g:= f f:= e e:= d + t1 d:= c c:= b b:= a a:= t1 + t2 + t2 Cộng giá trị băm vừa tính vào kết quả: h0:= h0 + a h1:= h1 + b h2:= h2 + c h3:= h3 + d h4:= h4 + e h5:= h5 + f h6:= h6 + g h7:= h7 + h h7 + h Tạo kết quả cuối cùng (big endian): digest = hash = h0 nối với h1 nối với h2 nối với h3 nối với h4 nối với h5 nối với h6 nối với h7
Mã nguồn SHA-256 bằng PHP, tương thích với UTF-8:
<?php
/*
* Copyright (C) 2006 Hieu Tran Dang (lt2hieu2004)
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the
* Free Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License along with
* this program; if not, write to the Free Software Foundation, Inc., 59 Temple
* Place, Suite 330, Boston, MA 02111-1307 USA
*/
class Hash
{
function sha256($msg)
{
$msg = Hash::utf8Encode($msg);
$msg.= chr(128);
$l = ceil(strlen($msg) / 4) + 2;
$N = ceil($l / 16);
$M = array();
for ($i = 0; $i < $N; $i++)
{
$M[] = array();
for ($j = 0; $j < 16; $j ++)
{
$M[$i][] = (ord(substr($msg, $i * 64 + $j * 4, 1)) << 24) |
(ord(substr($msg, $i * 64 + $j * 4 + 1, 1)) << 16) |
(ord(substr($msg, $i * 64 + $j * 4 + 2, 1)) << 8) |
(ord(substr($msg, $i * 64 + $j * 4 + 3, 1)));
}
}
$M[$N-1][14] = Hash::SHR((strlen($msg) - 1) * 8, 32);
$M[$N-1][15] = ((strlen($msg) - 1) * 8) & 0xffffffff;
$H = array(
0x6a09e667, 0xbb67ae85,
0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c,
0x1f83d9ab, 0x5be0cd19
);
$K = array(
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
);
$W = array();
for ($i = 0; $i < $N; $i++)
{
for ($t = 0; $t < 16; $t++) $W[$t] = $M[$i][$t];
for ($t = 16; $t < 64; $t++)
$W[$t] = Hash::sum(Hash::gamma1($W[$t - 2]), $W[$t - 7], Hash::gamma0($W[$t - 15]), $W[$t - 16]);
$a = $H[0];
$b = $H[1];
$c = $H[2];
$d = $H[3];
$e = $H[4];
$f = $H[5];
$g = $H[6];
$h = $H[7];
for ($t = 0; $t < 64; $t++)
{
$T1 = Hash::sum($h, Hash::sigma1($e), Hash::Ch($e, $f, $g), $K[$t], $W[$t]);
$T2 = Hash::sum(Hash::sigma0($a), Hash::Maj($a, $b, $c));
$h = $g;
$g = $f;
$f = $e;
$e = Hash::sum($d, $T1);
$d = $c;
$c = $b;
$b = $a;
$a = Hash::sum($T1, $T2);
}
$H[0] = Hash::sum($a, $H[0]);
$H[1] = Hash::sum($b, $H[1]);
$H[2] = Hash::sum($c, $H[2]);
$H[3] = Hash::sum($d, $H[3]);
$H[4] = Hash::sum($e, $H[4]);
$H[5] = Hash::sum($f, $H[5]);
$H[6] = Hash::sum($g, $H[6]);
$H[7] = Hash::sum($h, $H[7]);
}
$hash = "";
for ($i = 0; $i < 8; $i++)
{
$H[$i] = dechex($H[$i]);
while (strlen($H[$i]) < 8) $H[$i] = '0'.$H[$i];
$hash.= $H[$i];
}
return $hash;
}
function gamma0($x)
{
return (Hash::ROTR($x, 7) ^ Hash::ROTR($x, 18) ^ (Hash::SHR($x, 3)));
}
function gamma1($x)
{
return (Hash::ROTR($x, 17) ^ Hash::ROTR($x, 19) ^ (Hash::SHR($x, 10)));
}
function sigma0($x)
{
return (Hash::ROTR($x, 2) ^ Hash::ROTR($x, 13) ^ Hash::ROTR($x, 22));
}
function sigma1($x)
{
return (Hash::ROTR($x, 6) ^ Hash::ROTR($x, 11) ^ Hash::ROTR($x, 25));
}
function Ch($x, $y, $z)
{
return (($x & $y) ^ (~$x & $z));
}
function Maj($x, $y, $z)
{
return (($x & $y) ^ ($x & $z) ^ ($y & $z));
}
function ROTR($x, $n)
{
return (Hash::SHR($x, $n) | ($x << (32 - $n)));
}
function SHR($a, $b)
{
return ($a >> $b) & (pow(2, 32 - $b) - 1);
}
// Hàm được viết bởi Fyed
function sum()
{
$T = 0;
for($x = 0, $y = func_num_args(); $x < $y; $x++)
{
$a = func_get_arg($x);
$c = 0;
for($i = 0; $i < 32; $i++)
{
$j = (($T >> $i) & 1) + (($a >> $i) & 1) + $c;
$c = ($j >> 1) & 1;
$j &= 1;
$T &= ~(1 << $i);
$T |= $j << $i;
}
}
return $T;
}
// Dựa trên đoạn code viết bởi Angel Martin & Paul Johnston
function utf8Encode($msg)
{
$utfText = "";
for ($n = 0; $n < strlen($msg); $n++)
{
$c = ord(substr($msg, $n, 1));
if ($c < 128)
{
$utfText.= chr($c);
}
else if (($c > 127) && ($c < 2048))
{
$utfText.= chr(($c >> 6) | 192);
$utfText.= chr(($c & 63) | 128);
}
else
{
$utfText.= chr(($c >> 12) | 224);
$utfText.= chr((($c >> 6) & 63) | 128);
$utfText.= chr(($c & 63) | 128);
}
}
return $utfText;
}
}
?>
Ví dụ sửa
Dưới đây là một số ví dụ sử dụng thuật giải SHA. Đoạn dữ liệu gốc được ngầm hiểu sử dụng bảng mã ASCII.
SHA-1 sửa
SHA1("The quick brown fox jumps over the lazy dog")
= 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12
Ngay cả một thay đổi nhỏ trong đoạn dữ liệu gốc sẽ có khả năng rất lớn tạo nên một giá trị băm hoàn toàn khác do hiệu ứng tuyết lở. Ví dụ, sửa d thành c:
SHA1("The quick brown fox jumps over the lazy cog")
= de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3
Giá trị băm của một đoạn dữ liệu rỗng:
SHA1("")
= da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709
SHA-256 sửa
SHA256("The quick brown fox jumps over the lazy dog")
= d7a8fbb3 07d78094 69ca9abc b0082e4f 8d5651e4 6d3cdb76 2d02d0bf 37c9e592
Hiệu ứng tuyết lở khi sửa từ cuối cùng thành "cog":
SHA256("The quick brown fox jumps over the lazy cog")
= e4c4d8f3 bf76b692 de791a17 3e053211 50f7a345 b46484fe 427f6acc 7ecc81be
Giá trị băm của đoạn dữ liệu rỗng:
SHA256("")
= e3b0c442 98fc1c14 9afbf4c8 996fb924 27ae41e4 649b934c a495991b 7852b855
SHA-512 sửa
SHA512("The quick brown fox jumps over the lazy dog")
= 07e547d9 586f6a73 f73fbac0 435ed769 51218fb7 d0c8d788 a309d785 436bbb64
2e93a252 a954f239 12547d1e 8a3b5ed6 e1bfd709 7821233f a0538f3d b854fee6