Skip to content

Instantly share code, notes, and snippets.

@tstevens
Created April 18, 2011 14:08
Show Gist options
  • Save tstevens/925415 to your computer and use it in GitHub Desktop.
Save tstevens/925415 to your computer and use it in GitHub Desktop.
Implementation of SHA-1 Hash in pure ruby
#http://stackoverflow.com/questions/5940316/left-rotate-through-carry-in-ruby
class Integer
def lotate(n=1)
self << n | self >> (32 - n)
end
end
# FIPS 180-2 -- relevant section #'s below
# Pulls parts from Wiki pseudocode and http://ruby.janlelis.de/17-sha-256
class SHA1
def self.digest(input)
# 5.3.1 - Initial hash value
z = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0
# 5.1.1
length = input.length*8
input << 0x80
input << 0 while input.size%64 != 56
input += [length].pack('Q').reverse
#6.1.2
input.unpack('C*').each_slice(64){|chunk|
#6.1.2 - 1. Prepare the message schedule
w = []
chunk.each_slice(4){|a,b,c,d| w << (((a<<8|b)<<8|c)<<8|d) }
#Expand from sixteen to eighty -- 6.1.2 - 1. Prepare the message schedule
(16..79).map{|i|
w[i] = (w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]).lotate & 0xffffffff
}
#6.1.2 - 2. Initialize the five working variables.
a,b,c,d,e = z
(0..79).each{|i| # 6.1.2 - 3. & 4.1.1 - SHA-1 Functions
case i
when 0..19
f = ((b & c) | (~b & d))
k = 0x5A827999
when 20..39
f = (b ^ c ^ d)
k = 0x6ED9EBA1
when 40..59
f = ((b & c) | (b & d) | (c & d))
k = 0x8F1BBCDC
when 60..79
f = (b ^ c ^ d)
k = 0xCA62C1D6
end
temp = (a.lotate(5) & 0xffffffff) + f + e + k + w[i] & 0xffffffff
e = d
d = c
c = b.lotate(30) & 0xffffffff
b = a
a = temp
}
# 6.1.2 - 4. Compute the ith intermediate hash value
z[0] = z[0] + a & 0xffffffff
z[1] = z[1] + b & 0xffffffff
z[2] = z[2] + c & 0xffffffff
z[3] = z[3] + d & 0xffffffff
z[4] = z[4] + e & 0xffffffff
}
# Produce the final hash value (big-endian)
return '%.8x'*5 % z
end
end
if $0 == __FILE__
input = gets(nil) || ''
if RUBY_VERSION >= '1.9'
input = input.force_encoding('US-ASCII')
end
puts SHA1.digest(input)
end
@JoshCheek
Copy link

Thanks for posting this, it was totally useful today, I was tearing my hair out trying to interpret / modify this code.

A few things that would make it better:

  • if you change each_with_object to each_slice, you can get rid of the dependency on active_support (which will make it dramatically faster to load)
  • the variables shouldn't be instance variables, they should be local variables, so just remove all the asperands.
  • functions shouldn't print their values, better to return the value and let the code invoking the function decide to print it (e.g. we wanted to use the return value, not print it out, so had to edit the function)
  • the ARGF should probably not invoke automatically, you could put it in an if statement that checks to see if you're running the file directly or loading it as a lib to decide how to behave: if $0 == __FILE__

@strags
Copy link

strags commented Apr 28, 2013

This implementation isn't quite right... take the sha1 of any 56-byte message, and you'll see that it differs from that returned by Digest::SHA1. (This is true for any message where byte_length % 64 is between 56 and 63).

The reason is that your padding algorithm doesn't work correctly in these cases.

@tstevens
Copy link
Author

Github doesn't notify you about gist comments apparently... I wrote this for a college network security/crypto class so I didn't expect it to be perfect. @strags did you correct the padding issue you described? If you could share the fix that would be awesome! I would like to keep this implementation as accurate as possible for anyone else who stumbles across it.

@reprah
Copy link

reprah commented Jul 25, 2013

@tstevens I wrote a fix for your padding algorithm; check out my fork of this gist. I verified that it gives the same output as the Ruby library's SHA-1 for messages whose length % 64 bytes (or 512 bits) fall into that weird range (56..63) where the padding has to be adjusted.

There's still a bug, though! When I try to hash a message that's >= 64 bytes, I get a NoMethodError in your leftrotate() function. Can you verify this?

Thanks for making your implementation free for all to use!

@tstevens
Copy link
Author

tstevens commented Nov 2, 2014

Over a year behind but I finally fixed this up. Both the NoMethodError and padding issues have been resolved with this update!

@xxxperimental
Copy link

Hey, can you please explain this expression?
'%.8x'*5 % z
Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment