SHA-1のpure ruby版

Rubyで書くと相当短くなりますが付属のネイティブのライブラリより速度は1000倍くらい(?)遅いです。Fixnum(31ビット以下)で計算するバージョンも作ってみたのですが計算量が増えて結局Bignumと変わらない速度でした。暗号理論の道具の一つであるMessageDigest(一方向関数)がどのような物か勉強するには良かったです。

# -*- encoding: US-ASCII -*-
# SHA-1 implementation of pure ruby.

module Purerubysha1
  def self.rotate_left_shift_32bit(i, n)
    (0xffffffff & (i << n)) | (i >> (32 - n))
  end

  def self.digest(str)
    [hexdigest(str)].pack("H*")
  end

  def self.hexdigest(str)
    mask = 0xffffffff

    #H[0]..H[4]
    h_a = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0]
    # f(t;B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)
    # f(t;B,C,D) = B XOR C XOR D (20 <= t <= 39)
    # f(t;B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)
    # f(t;B,C,D) = B XOR C XOR D (60 <= t <= 79)
    f_a = []
    # K(t)
    # K(t) = 5A827999 ( 0 <= t <= 19)
    # K(t) = 6ED9EBA1 (20 <= t <= 39)
    # K(t) = 8F1BBCDC (40 <= t <= 59)
    # K(t) = CA62C1D6 (60 <= t <= 79)
    k_a = []
    80.times do |i|
      case i
        when 0 .. 19
          f_a[i] = lambda {|b, c, d| (b & c) | (~b & d)}
          k_a[i] = 0x5A827999
        when 20 .. 39
          f_a[i] = lambda {|b, c, d| b ^ c ^ d}
          k_a[i] = 0x6ED9EBA1
        when 40 .. 59
          f_a[i] = lambda {|b, c, d| (b & c) | (b & d) | (c & d)}
          k_a[i] = 0x8F1BBCDC
        when 60 .. 79
          f_a[i] = lambda {|b, c, d| b ^ c ^ d}
          k_a[i] = 0xCA62C1D6
      end
    end

    # "1" is appended.
    buf = str + ["10000000"].pack("B8")

    if (56 - buf.size % 64) < 0
      (64 + (56 - buf.size % 64)).times do
        buf += [0].pack("C")
      end
    else
      (56 - buf.size % 64).times do
        buf += [0].pack("C")
      end
    end

    # set the number of bits in the original message.
    buf += [sprintf("%016X", str.size * 8)].pack("H*")

    m_a = []
    (buf.size / 64).times do |i|
      m_a[i] = buf[i * 64, 64]
    end

    m_a.each do |m|
      w = []
      # W0 to W15
      w = m.unpack("N16")

      # W16 to W79
      (16..79).each do |t|
        # W(t) = S^1 (W(t-3) XOR W(t-8) XOR W(t-14) XOR W(t-16))
        w[t] = rotate_left_shift_32bit(w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16], 1)
      end

      a = h_a[0]
      b = h_a[1]
      c = h_a[2]
      d = h_a[3]
      e = h_a[4]

      80.times do |t|
        # TEMP = S^5(A) + f(t;B,C,D) + E + W(t) + K(t)
        temp = mask & (rotate_left_shift_32bit(a, 5) + f_a[t].call(b, c, d) + e + w[t] + k_a[t])

        # E = D; D = C; C = S^30(B); B = A; A = TEMP
        e = d; d = c; c = rotate_left_shift_32bit(b, 30); b = a; a = temp
      end

      # H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E
      h_a[0] = mask & (h_a[0] + a)
      h_a[1] = mask & (h_a[1] + b)
      h_a[2] = mask & (h_a[2] + c)
      h_a[3] = mask & (h_a[3] + d)
      h_a[4] = mask & (h_a[4] + e)
    end

    sprintf("%08X%08X%08X%08X%08X", h_a[0], h_a[1], h_a[2], h_a[3], h_a[4])
  end
end


# sample

buf = File.open('test.dat','rb').read

require 'benchmark'

Benchmark.bm do |x|
  x.report { p Purerubysha1.hexdigest("") }
  x.report { p Purerubysha1.digest("") }
end