介绍

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字 “指纹” 的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或 hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法 1）是一种密码散列函数。SHA-1 可以生成一个被称为消息摘要的 160 位（20 字节）散列值，散列值通常的呈现形式为 40 个十六进制数。2005 年，密码分析人员发现了对 SHA-1 的有效攻击方法，这表明该算法可能不够安全，不能继续使用。2020 年，针对 SHA-1 的选择前缀冲突攻击已经实际可行。

通过散列算法可实现数字签名实现，数字签名的原理是将要传送的明文通过一种函数运算（Hash）转换成报文摘要（不同的明文对应不同的报文摘要），报文摘要加密后与明文一起传送给接受方，接受方将接受的明文产生新的报文摘要与发送方的发来报文摘要解密比较，比较结果一致表示明文未被改动，如果不一致表示明文已被篡改。

密码散列函数

密码散列函数（英语：Cryptographic hash function），又译为加密散列函数、密码散列函数、加密散列函数，是散列函数的一种。它被认为是一种单向函数，也就是说极其难以由散列函数输出的结果，回推输入的资料是什么。

伪代码

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

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Initial 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)

演示

• 【SHA1 算法】| 哈希算法 | Hash 算法 | 密码学 | 信息安全 | 消息摘要：

• 硬核讲解哈希算法加密原理（ sha-1 哈希算法)：

• Christof Paar 教授在德国波鸿大学的教学视频：

实现

JavaScript

//= ===============================================================
// SHA1.js
//
// Module that replicates the SHA-1 Cryptographic Hash
// function in Javascript.
//= ===============================================================

// main variables
const CHAR_SIZE = 8

/**
 * Adds padding to binary/hex string representation
 *
 * @param {string} str - string representation (binary/hex)
 * @param {int} bits - total number of bits wanted
 * @return {string} - string representation padding with empty (0) bits
 *
 * @example
 *      pad("10011", 8); // "00010011"
 */
function pad (str, bits) {
  let res = str
  while (res.length % bits !== 0) {
    res = '0' + res
  }
  return res
}

/**
 * Separates string into chunks of the same size
 *
 * @param {string} str - string to separate into chunks
 * @param {int} size - number of characters wanted in each chunk
 * @return {array} - array of original string split into chunks
 *
 * @example
 *      chunkify("this is a test", 2)
 */
function chunkify (str, size) {
  const chunks = []
  for (let i = 0; i < str.length; i += size) {
    chunks.push(str.slice(i, i + size))
  }
  return chunks
}

/**
 * Rotates string representation of bits to the left
 *
 * @param {string} bits - string representation of bits
 * @param {int} turns - number of rotations to make
 * @return {string} - string representation of bits after rotation
 *
 * @example
 *      rotateLeft("1011", 3); // "1101"
 */
function rotateLeft (bits, turns) {
  return bits.substr(turns) + bits.substr(0, turns)
}

/**
 * Pre-processes message to feed the algorithm loop
 *
 * @param {string} message - message to pre-process
 * @return {string} - processed message
 */
function preProcess (message) {
  // convert message to binary representation padded to
  // 8 bits, and add 1
  let m = message.split('')
    .map(e => e.charCodeAt(0))
    .map(e => e.toString(2))
    .map(e => pad(e, 8))
    .join('') + '1'

  // extend message by adding empty bits (0)
  while (m.length % 512 !== 448) {
    m += '0'
  }

  // length of message in binary, padded, and extended
  // to a 64 bit representation
  let ml = (message.length * CHAR_SIZE).toString(2)
  ml = pad(ml, 8)
  ml = '0'.repeat(64 - ml.length) + ml

  return m + ml
}

/**
 * Hashes message using SHA-1 Cryptographic Hash Function
 *
 * @param {string} message - message to hash
 * @return {string} - message digest (hash value)
 */
function SHA1 (message) {
  // main variables
  let H0 = 0x67452301
  let H1 = 0xEFCDAB89
  let H2 = 0x98BADCFE
  let H3 = 0x10325476
  let H4 = 0xC3D2E1F0

  // pre-process message and split into 512 bit chunks
  const bits = preProcess(message)
  const chunks = chunkify(bits, 512)

  chunks.forEach(function (chunk, i) {
    // break each chunk into 16 32-bit words
    const words = chunkify(chunk, 32)

    // extend 16 32-bit words to 80 32-bit words
    for (let i = 16; i < 80; i++) {
      const val = [words[i - 3], words[i - 8], words[i - 14], words[i - 16]]
        .map(e => parseInt(e, 2))
        .reduce((acc, curr) => curr ^ acc, 0)
      const bin = (val >>> 0).toString(2)
      const paddedBin = pad(bin, 32)
      const word = rotateLeft(paddedBin, 1)
      words.push(word)
    }

    // initialize variables for this chunk
    let [a, b, c, d, e] = [H0, H1, H2, H3, H4]

    for (let i = 0; i < 80; i++) {
      let f, k
      if (i < 20) {
        f = (b & c) | (~b & d)
        k = 0x5A827999
      } else if (i < 40) {
        f = b ^ c ^ d
        k = 0x6ED9EBA1
      } else if (i < 60) {
        f = (b & c) | (b & d) | (c & d)
        k = 0x8F1BBCDC
      } else {
        f = b ^ c ^ d
        k = 0xCA62C1D6
      }
      // make sure f is unsigned
      f >>>= 0

      const aRot = rotateLeft(pad(a.toString(2), 32), 5)
      const aInt = parseInt(aRot, 2) >>> 0
      const wordInt = parseInt(words[i], 2) >>> 0
      const t = aInt + f + e + k + wordInt
      e = d >>> 0
      d = c >>> 0
      const bRot = rotateLeft(pad(b.toString(2), 32), 30)
      c = parseInt(bRot, 2) >>> 0
      b = a >>> 0
      a = t >>> 0
    }

    // add values for this chunk to main hash variables (unsigned)
    H0 = (H0 + a) >>> 0
    H1 = (H1 + b) >>> 0
    H2 = (H2 + c) >>> 0
    H3 = (H3 + d) >>> 0
    H4 = (H4 + e) >>> 0
  })

  // combine hash values of main hash variables and return
  const HH = [H0, H1, H2, H3, H4]
    .map(e => e.toString(16))
    .map(e => pad(e, 8))
    .join('')

  return HH
}

资源

• guyongqiangx/cryptography: 密码编码学算法学习 (opens new window)
• RFC 3174: US Secure Hash Algorithm 1 (SHA1) (opens new window)
• brix/crypto-js: JavaScript library of crypto standards. (opens new window)
• SECURE HASH STANDARD (opens new window)

参考

• SHA-1 - Wikiwand (opens new window)
• 散列函数 - Wikiwand (opens new window)