SHA-1 を実装してみた

某所の例の問題を考えてるときにハッシュ関数アルゴリズムの SHA-1 の中をいじりたくなって、英語版 Wikipedia の SHA-1 の頁を参考にして Ruby で実装してみた。
ほぼ擬似コードのとおりに実装しただけで、効率は考えていない。

class Integer
  def rotate(r)
    self << r & 0xffffffff | self >> 32 - r
  end
end

class SHA1
  def main_loop(h, w)
    a, b, c, d, e = h
    80.times do |i|
      f = case i
        when  0..19 then b & c | ~b & d
        when 40..59 then b & c | b & d | c & d
        else             b ^ c ^ d
      end
      a, b, c, d, e =
      a.rotate(5) + e + f + @k[i / 20] + w[i] & 0xffffffff, a, b.rotate(30), c, d
    end
    [a, b, c, d, e].each_with_index {|x, j| h[j] = h[j] + x & 0xffffffff}
  end

  def hash(m)
    h = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0]
    until m == '' do
      w = []
      16.times do
        w << m[0, 8].hex
        m = m[8..-1]
      end
      16.upto(79) {|i| w[i] = (w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]).rotate(1)}
      main_loop(h, w)
    end
    h.map {|x| '%08x' % x} .join
  end

  def digest(message)
    @k = [2, 3, 5, 10].map {|x| (Math.sqrt(x) * 2 ** 30).to_i}
    length = message.size
    m = ''
    message.each_byte {|b| m += '%02x' % b}
    m += '80' + '00' * (-(length + 9) % 64) + '%016x' % (8 * length)
    hash(m)
  end
end

# 使用例
puts SHA1.new.digest('The quick brown fox jumps over the lazy dog')

# 同じことをライブラリにある Digest::SHA1 クラスでやるとこうなる
require 'digest/sha1'
puts Digest::SHA1.hexdigest('The quick brown fox jumps over the lazy dog')