Hi Guest

More contents, please log on!

Bitmere.com 区块链技术 Content
1.SHA简介
关于SHA的定义直接参考wiki介绍:
安全散列算法(英语:Secure Hash Algorithm,缩写为SHA)是一个密码散列函数家族,是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的,长度固定的字符串(又称消息摘要)的算法。且若输入的消息不同,它们对应到不同字符串的机率很高。
SHA可看作是是一种单向函数,几乎不可逆,给一段信息,它会给你生成固定长度的摘要,当然,不同的信息是的确有可能生成相同的摘要的,这被称作碰撞,简单来说,摘要的长度越长,碰撞几率越低。
既然有碰撞这种可能性,那碰撞肯定会被拿来用作攻击手段的,SHA-1已经在17年被Google和荷兰的小组攻破了,目前使用的标准是SHA-2,其实在算法上SHA-2和SHA-1区别不大,但是至今SHA-2还没被攻破,所以暂且当它没什么弱点。
从SHA的特点来看,用来作文件验证和数字签名是非常合适的。比特币使用的就是SHA-2中的SHA256算法。
2.SHA256的算法实现
首先,SHA算法在数学原理上是相当复杂的(那些移位与或非对于算法的作用看着就头大),对于不以密码学研究为目的,同时也是初学者的我来说,去分析它的数学细节对我没有什么意义,因此我暂且忽略那一部分直接看它的算法实现。
实现可以分为三个部分:常量初始化,信息预处理,生成摘要。
2.1常量初始化
首先是初始化8个值,分别是最开始的连续8个素数(从2到19)的平方根的二进制表示的小数部分的前32位,有点绕,不过就是这样啦,这些后面会作为迭代的初值使用。
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
然后还要初始化64个值,分别是最开始的连续64个素数(从2到311)的立方根的二进制表示的小数部分的前32位,可以看到这64个数也成了数组的形式,因为是要在后面每次迭代中拿来进行循环运算的。
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
2.2信息预处理
预处理分为三步,首先是在原信息后加一个‘1’;然后再添加k个0,直到信息长度 mod 512 = 448,如果原信息是447这种长度,那其实就不用加0了;最后就是再添加原信息的长度到末尾,是64位的大端模式的格式。
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
2.3生成摘要
到了最麻烦的一步了,生成摘要。
首先,经过第二步,现在信息已经是512bit的倍数这种格式了,所以这里首先是把信息分成块,每一块是512bit,然后每一块都是一次迭代,每一次迭代都会更新摘要,最后一次迭代结果就是最终生成的摘要。
所以,关键就是每一步迭代过程中发生了什么。
对于SHA256算法,最终的摘要是256bit的,结合前面的8个32bit的初值,这里就不难理解了,总的摘要是分成8个值进行更新的。块大小是512bit的,将其也以32bit为单位分成16个,然后通过对16个数进行运算,生成另外48个数,总之,得到了64个值,这和前面的64个常量相对应,剩下的就直接看下图吧:

每次迭代摘要的更新流程
中间各种运算符什么的,就是一些运算而已,没什么好说的, W是从块中得到的64个数的集合,K是之前初始化的64个数的集合,可以看到一次迭代内部有64次循环,每次循环都会更新一次摘要。
最后,来看看伪代码把:
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 := 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 + w
        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
一目了然,对吧。
BitMere.com is Information release platform,just provides information storage space services.
The opinions expressed are solely those of the author,Does not constitute advice, please treat with caution.
You have to log in before you can reply Login | 立即注册

Points Rules

Write the first review

李悔之2015 初中生
  • Follow

    1

  • Following

    0

  • Articles

    13

Promoted