安全哈希算法Secure Hash Algorithm

mysql password算法是由两轮sha1算法形成的mysql独有的密码加密函数。

安 全散列算法（英语：Secure Hash Algorithm）是一种能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。且若输入的消息不同，它们对应到不同字符串的机率 很高；而SHA是FIPS所认证的五种安全散列算法。这些算法之所以称作“安全”是基于以下两点（根据官方标准的描述）：

SHA家族的五 个算法，分别是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美国国家安全局（NSA）所设计，并由美国国家标准与 技术研究院（NIST）发布；是美国的政府标准。后四者有时并称为SHA-2。SHA-1在许多安全协议中广为使用，包括TLS和SSL、PGP、 SSH、S/MIME和IPsec，曾被视为是MD5（更早之前被广为使用的散列函数）的后继者。但SHA-1的安全性如今被密码学家严重质疑；虽然至今 尚未出现对SHA-2有效的攻击，它的算法跟SHA-1基本上仍然相似；因此有些人开始发展其他替代的散列算法。缘于最近[何时？]对SHA-1的种种攻 击发表，“美国国家标准与技术研究院（NIST）开始设法经由公开竞争管道（类似高级加密标准AES的发展经过），发展一个或多个新的散列算法。”

2012 年10月2日，Keccak被选为NIST散列函数竞赛的胜利者,[1]成为SHA-3。 SHA-3并不是要取代SHA-2，因为SHA-2目前并没有出现明显的弱点。由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解 的方法，NIST感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的SHA-3。设计者宣称在Intel Core 2的CPU上面，此算法的性能是12.5cpb（每字节周期数，cycles per byte）。不过，在硬件实做上面，这个算法比起其他算法明显的快上很多。

SHA所定义的长度

下表中的中继散列值（internal state）表示对每个数据区块压缩散列过后的中继值（internal hash sum）。

算法	输出散列值长度（bits）	中继散列值长度（bits）	数据区块长度（bits）	最大输入消息长度（bits）	一个Word长度（bits）	循环次数	使用到的运算符	碰撞攻击
SHA-0	160	160	512	264 − 1	32	80	+,and,or,xor,rotl	是
SHA-1	160	160	512	264 − 1	32	80	+,and,or,xor,rotl	存在263的攻击
SHA-256/224	256/224	256	512	264 − 1	32	64	+,and,or,xor,shr,rotr	尚未出现
SHA-512/384	512/384	512	1024	2128 − 1	64	80	+,and,or,xor,shr,rotr	尚未出现

SHA-0和SHA-1
SHA-1压缩算法中的一个循环。A, B, C, D和E是这个state中的32位文字；F是会变化的非线性函数；<<<n代表bit向左循环移动n个位置。n因操作而异。田代表modulo 232之下的加法，Kt是一个常数。

最 初载明的算法于1993年发布，称做安全散列标准（Secure Hash Standard），FIPS PUB 180。这个版本现在常被称为SHA-0。它在发布之后很快就被NSA撤回，并且由1995年发布的修订版本FIPS PUB 180-1（通常称为SHA-1）取代。SHA-1和SHA-0的算法只在压缩函数的消息转换部份差了一个比特的循环位移。根据NSA的说法，它修正了一 个在原始算法中会降低散列安全性的弱点。然而NSA并没有提供任何进一步的解释或证明该弱点已被修正。而后SHA-0和SHA-1的弱点相继被攻 破，SHA-1似乎是显得比SHA-0有抵抗性，这多少证实了NSA当初修正算法以增进安全性的声明。

SHA-0和SHA-1可将一个最大264比特的消息，转换成一串160位的消息摘要；其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学散列算法MD4和MD5。
SHA-0的破解

在CRYPTO 98上，两位法国研究者提出一种对SHA-0的攻击方式[3]：在261的计算复杂度之内，就可以发现一次碰撞（即两个不同的消息对应到相同的消息摘 要）；这个数字小于生日攻击法所需的280，也就是说，存在一种算法，使其安全性不到一个理想的散列函数抵抗攻击所应具备的计算复杂度。

2004年时，Biham和Chen也发现了SHA-0的近似碰撞，也就是两个消息可以散列出几乎相同的数值；其中162比特中有142比特相同。他们也发现了SHA-0的完整碰撞（相对于近似碰撞），将本来需要80次方的复杂度降低到62次方。

2004 年8月12日，Joux, Carribault, Lemuet和Jalby宣布找到SHA-0算法的完整碰撞的方法，这是归纳Chabaud和Joux的攻击所完成的结果。发现一个完整碰撞只需要251 的计算复杂度。他们使用的是一台有256颗Itanium2处理器的超级电脑，约耗80,000 CPU工时。

2004年8月17日，在 CRYPTO 2004的Rump会议上，王小云，冯登国（Feng）、来学嘉（Lai），和于红波（Yu）宣布了攻击MD5、SHA-0和其他散列函数的初步结果。他 们攻击SHA-0的计算复杂度是240，这意谓的他们的攻击成果比Joux还有其他人所做的更好。请参见MD5安全性。2005年二月，王小云和殷益群、 于红波再度发表了对SHA-0破密的算法，可在239的计算复杂度内就找到碰撞。
SHA-1的破解

鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实现密码系统的人们也应重新考虑。在2004年CRYPTO会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以SHA-2取而代之。

2005年，Rijmen和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击：在280的计算复杂度之内找到碰撞。

2005年二月，王小云、殷益群及于红波发表了对完整版SHA-1的攻击，只需少于269的计算复杂度，就能找到一组碰撞。（利用生日攻击法找到碰撞需要280的计算复杂度。）

这 篇论文的作者们写道；“我们的破密分析是以对付SHA-0的差分攻击、近似碰撞、多区块碰撞技术、以及从MD5算法中查找碰撞的消息更改技术为基础。没有 这些强力的分析工具，SHA-1就无法破解。”此外，作者还展示了一次对58次加密循环SHA-1的破密，在233个单位操作内就找到一组碰撞。完整攻击 方法的论文发表在2005年八月的CRYPTO会议中。

殷益群在一次面谈中如此陈述：“大致上来说，我们找到了两个弱点：其一是前置处理不够复杂；其二是前20个循环中的某些数学运算会造成不可预期的安全性问题。”

2005年8月17日的CRYPTO会议尾声中王小云、姚期智、姚储枫再度发表更有效率的SHA-1攻击法，能在263个计算复杂度内找到碰撞。

2006年的CRYPTO会议上，Christian Rechberger和Christophe De Cannière宣布他们能在容许攻击者决定部分原消息的条件之下，找到SHA-1的一个碰撞。

在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜索法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；但这并不表示该破密法已经可以进入实际应用的阶段。

就 应用层面的考量而言，一种新的破密法出现，暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生，但确有必要发展更 强的散列算法来取代旧的算法。在“碰撞”攻击法之外，另有一种反译攻击法（Pre-image attack），就是由散列出的字符串反推原本的消息；反译攻击的严重性更在碰撞攻击之上，但也更困难。在许多会应用到密码散列的情境（如用户密码的存 放、文件的数字签章等）中，碰撞攻击的影响并不是很大。举例来说，一个攻击者可能不会只想要伪造一份一模一样的文件，而会想改造原来的文件，再附上合法的 签章，来愚弄持有私密密钥的验证者。另一方面，如果可以从密文中反推未加密前的用户密码，攻击者就能利用得到的密码登录其他用户的账户，而这种事在密码系 统中是不能被允许的。但若存在反译攻击，只要能得到指定用户密码散列过后的字符串（通常存在影文件中，而且可能不会透露原密码信息），就有可能得到该用户 的密码。
SHA-2
SHA-2的第t个加密循环。图中的深蓝色方块是事先定义好的非线性函数。ABCDEFGH一开始分别是八个初始 值，Kt是第t个密钥，Wt是本区块产生第t个word。原消息被切成固定长度的区块，对每一个区块，产生n个word（n视算法而定），通过重复运作循 环n次对ABCDEFGH这八个工作区段循环加密。最后一次循环所产生的八段字符串合起来即是此区块对应到的散列字符串。若原消息包含数个区块，则最后还 要将这些区块产生的散列字符串加以混合才能产生最后的散列字符串。

NIST发布了三个额外的SHA变体，这三个函数都将消息对应到更长的 消息摘要。以它们的摘要长度（以比特计算）加在原名后面来命名：SHA-256，SHA-384和SHA-512。它们发布于2001年的FIPS PUB 180-2草稿中，随即通过审查和评论。包含SHA-1的FIPS PUB 180-2，于2002年以官方标准发布。2004年2月，发布了一次FIPS PUB 180-2的变更通知，加入了一个额外的变种SHA-224″，这是为了符合双密钥3DES所需的密钥长度而定义。

SHA-256和 SHA-512是很新的散列函数，前者以定义一个word为32位，后者则定义一个word为64位。它们分别使用了不同的偏移量，或用不同的常数，然 而，实际上二者结构是相同的，只在循环运行的次数上有所差异。SHA-224以及SHA-384则是前述二种散列函数的截短版，利用不同的初始值做计算。

这些新的散列函数并没有接受像SHA-1一样的公众密码社区做详细的检验，所以它们的密码安全性还不被大家广泛的信任。Gilbert和Handschuh在2003年曾对这些新变种作过一些研究，声称他们没有找到弱点。

SHAd

SHAd函数是一个简单的相同SHA函数的重述：

SHAd-256(m)=SHA-256(SHA-256(m))。它会克服有关延伸长度攻击的问题。
应用

SHA-1, SHA-224, SHA-256, SHA-384和SHA-512都被需要安全散列算法的美国联邦政府所应用，他们也使用其他的密码算法和协议来保护敏感的未保密数据。FIPS PUB 180-1也鼓励私人或商业组织使用SHA-1加密。Fritz-chip将很可能使用SHA-1散列函数来实现个人电脑上的数字版权管理。

首先推动安全散列算法出版的是已合并的数字签章标准。

SHA散列函数已被做为SHACAL 分组密码算法的基础。
SHA-1算法

以下是SHA-1算法的伪代码：

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

Initialize variables:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

Pre-processing:
append the bit ‘1’ to the message
append k bits ‘0’, where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1

Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4

Main loop:
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f := (b and c) or ((not b) and d)
k := 0x5A827999
else if 20 ≤ i ≤ 39
f := b xor c xor d
k := 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f := (b and c) or (b and d) or(c and d)
k := 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f := b xor c xor d
k := 0xCA62C1D6

temp := (a leftrotate 5) + f + e + k + w[i]
e := d
d := c
c := b leftrotate 30
b := a
a := temp

Add this chunk’s hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e

Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4

上述关于f表达式列于FIPS PUB 180-1中，以下替代表达式也许也能在主要循环里计算f：

(0  ≤ i ≤ 19): f := d xor (b and (c xor d))         (alternative)

(40 ≤ i ≤ 59): f := (b and c) or (d and (b or c))   (alternative 1)
(40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c))  (alternative 2)
(40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c))   (alternative 3)

SHA-2算法

以下是SHA-256算法的伪代码。注意，64个word w[16..63]中的比特比起SHA-1算法，混合的程度大幅提升。

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

Initialize variables
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize table of round constants
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[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

Pre-processing:
append the bit ‘1’ to the message
append k bits ‘0’, where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[0..15]

Extend the sixteen 32-bit words into sixty-four 32-bit words:
for i from 16 to 63
s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3)
s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10)
w[i] := w[i-16] + s0 + w[i-7] + s1

Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7

Main loop:
for i from 0 to 63
s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22)
maj := (a and b) xor (a and c) xor(b and c)
t2 := s0 + maj
s1 := (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25)
ch := (e and f) xor ((not e) and g)
t1 := h + s1 + ch + k[i] + w[i]

h := g
g := f
f := e
e := d + t1
d := c
c := b
b := a
a := t1 + t2

Add this chunk’s hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h

Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

其中ch函数及maj函数可利用前述SHA-1的优化方式改写。

SHA-224和SHA-256基本上是相同的，除了：

h0到h7的初始值不同，以及
SHA-224输出时截掉h7的函数值。

SHA-512和SHA-256的结构相同，但：

SHA-512所有的数字都是64位，
SHA-512运行80次加密循环而非64次，
SHA-512初始值和常数拉长成64位，以及
二者比特的偏移量和循环位移量不同。

SHA-384和SHA-512基本上是相同的，除了：

h0到h7的初始值不同，以及
SHA-384输出时截掉h6和h7的函数值。