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