############################################################# # Jake Voytko (C) 2008. MIT License. # # USER'S GUIDE: # # At the beginning of the file, there are helper functions to make the # main program easier to read. # # These include: # # - left_rotate(), which just performs a bitwise rotation # - combine(), which makes the final digests into a human-readable # format # # # After these helper functions, we will find the following # SHA-1 specific messages: # # - preprocess(), which performs the padding and splits # the message into blocks. # - expand(), which performs the message expansion # - md_rotate(), which is a generic version of the message # schedule # # After the SHA-1 functions, you will find the round-specific # functions, followed by the main logic of the SHA-1 function. # # At the very end of the program, you will find the "main" # section, where you can input message digests of your own. ############################################################# ############################################################# # # Left Rotate helper function # # Python doesn't include a function to automatically perform # left rotations, so we will perform it using two shifts. # # The "&0xFFFFFFFFL" part of the string keeps it within 32 # bits, since Python allows numbers to grow arbitrarily # large. ############################################################# def left_rotate(word, b): # (word left-shifted "b" bits) or (word right-shifted) "32-b" bits return ((word << b) | word >> (32-b)) & 0xFFFFFFFFL ############################################################# # combine() helper function # # This just formats the output into 5 hexidecimal blocks ############################################################# def combine(a, b, c, d, e): return hex(a)[2:10] + " " + hex(b)[2:10] + " " + hex(c)[2:10] + " " + hex(d)[2:10] + " " + hex(e)[2:10] ############################################################# # Message padding and block splitting # # Here, we are padding the message to the correct length, # and then splitting it into lists of 16 hexidecimal numbers. # ############################################################# def preprocess(message): """Converts the message to 512 bit blocks. Practically, this is done at the character level and not at the bit level.""" ret = [] # Calculate the length of the message in bits. messagelen = len(message) * 8 # Adds the bits "100000000" to the message. According to the standard, # this is always done, and official test vectors don't work out correctly # unless this is performed. message += chr(128) # Adds the necessary zeroes. while (len(message)*8) % 512 != 448: message += chr(0) # Append the length of the message message += 4*chr(0) # Keep appending the length of the message. message += chr((messagelen & 0xFF000000) >> 24) message += chr((messagelen & 0x00FF0000) >> 16) message += chr((messagelen & 0x0000FF00) >> 8) message += chr(messagelen & 0x000000FF) # Split the message into blocks of the necessary length. for i in range(0, len(message)/64): block = message[:64].encode("hex") message=message[64:] subret = [] for j in range(0, 16): subret.append(int(block[j*8 : j*8 + 8], 16)) ret.append(subret) return ret ############################################################# # Message expansion # # In ordinary implementations of SHA-1, the message exansion # is performed "on the fly". This is being done all at once # for readability's sake within the main message loop. # ############################################################# def expand(block): ret = [] for i in block: # append the 16 initial blocks ret.append(i) for i in range(16, 80): # w[i-3] xor w[i-8] xor ret.append(left_rotate((ret[i-3] ^ ret[i-8] ^ ret[i-14] ^ ret[i-16]),1)&0xFFFFFFFFL) return ret ############################################################# # # Merkle Damgard rotation # # All of the round functions use the same rotation, so we # have placed it in another function. The input parameters # are the 5 registers, the input word for this round, # f(b,c,d), and the round constant # ############################################################# def md_rotate(a, b, c, d, e, word, f_of_bcd, k): """This is the rotation inside of the compression functions.""" # leftrotate a = left_rotation(a, 5) + k + e + input word + result of function temp = (left_rotate(a, 5) + f_of_bcd + k + word + e) & 0xffffffffL # This is the round rotation. e = d d = c c = left_rotate(b, 30) b = a a = temp return a, b, c, d, e ############################################################# # # SHA-1 FUNCTIONS # # The following are the four functions used in SHA-1 # # f1() is used for the first 20 rounds # f2() is used for the second 20 rounds # f3() is used for the third 20 rounds # f4() is used for the fourth 20 rounds # # In each Python function below, you will see the constant stored, # the intermediate calculation of f(b, c, d), which will be # stored in the variable f_of_bcd # ############################################################# def f1(a, b, c, d, e, word): """The compression function for the first 20 rounds""" # store (b and c) or ((not b) and d) f_of_bcd = (b & c) | ((~b) & d) k = 0x5A827999L # call the md_rotate() function above return md_rotate(a, b, c, d, e, word, f_of_bcd, k) def f2(a, b, c, d, e, word): """The compression function for the second 20 rounds""" # b xor c xor d f_of_bcd = b ^ c ^ d k = 0x6ED9EBA1L return md_rotate(a, b, c, d, e, word, f_of_bcd, k) def f3(a, b, c, d, e, word): """The compression function for the third 20 rounds""" # (b bitwise-and c) bitwise-or (b bitwise-and d) bitwise-or (c bitwise-and d) f_of_bcd = (b & c) | (b & d) | (c & d) k = 0x8F1BBCDCL return md_rotate(a, b, c, d, e, word, f_of_bcd , k) def f4(a, b, c, d, e, word): """The compression function for the last 20 rounds""" # b xor c xor d f_of_bcd = b ^ c ^ d k = 0xCA62C1D6L return md_rotate(a, b, c, d, e, word, f_of_bcd , k) #### # End SHA-1 functions #### ############################################################# # # SHA-1 Programming Logic # # This is the main control logic of the SHA-1 hash digest. # # First, The five initial registers are initialized. # Second, We use the preprocess() function defined above # to return a list of all of the blocks in the message. # Third, We iterate through all of the blocks. For each block, # we perform the message expansion, and then iterate # through each round, calling the necessary functions # above. # Lastly, We add together the previous round constants and the # current results for each block. # ############################################################# def sha1(message): """Returns a string containing the hexidecimal digest of the message input""" # These are the start values of the main registers h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0 # Generates all of the individual message blocks. This returns a list # of all of the blocks. Each block contains 16 words. blocks = preprocess(message) # Here, we loop through each block in the list of message blocks. for block in blocks: # Perform the message expansion expansion = expand(block) # Set temporary registers equal to the main registers a = h0 b = h1 c = h2 d = h3 e = h4 word_counter = 0 # Perform the 80 rounds. for i in range(20): a, b, c, d, e = f1(a, b, c, d, e, expansion[word_counter]) word_counter+=1 for i in range(20): a, b, c, d, e = f2(a, b, c, d, e, expansion[word_counter]) word_counter+=1 for i in range(20): a, b, c, d, e = f3(a, b, c, d, e, expansion[word_counter]) word_counter+=1 for i in range(20): a, b, c, d, e = f4(a, b, c, d, e, expansion[word_counter]) word_counter+=1 # Add the previous result to the current result # The & 0xFFFFFFFFL detail keeps the message within the size of one # word, since Python doesn't perform calculations mod 2^32 h0 = (h0 + a) & 0xFFFFFFFFL h1 = (h1 + b) & 0xFFFFFFFFL h2 = (h2 + c) & 0xFFFFFFFFL h3 = (h3 + d) & 0xFFFFFFFFL h4 = (h4 + e) & 0xFFFFFFFFL # Concatenate all of the result strings and exit return combine(h0, h1, h2, h3, h4) if __name__ == "__main__": print "" print "Message digest of \"\": " + sha1("") print "" print "Message digest of \"The quick brown... \": " print " " + sha1("The quick brown fox jumps over the lazy dog") print "" print "Message digest of \"abc\": " + sha1("abc")