# -*- coding: utf-8 -*- # # RIPEMD160.py : RIPEMD-160 implementation # # Written in 2008 by Dwayne C. Litzenberger # # =================================================================== # The contents of this file are dedicated to the public domain. To # the extent that dedication to the public domain is not available, # everyone is granted a worldwide, perpetual, royalty-free, # non-exclusive license to exercise all rights associated with the # contents of this file for any purpose whatsoever. # No rights are reserved. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS # BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN # ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN # CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE # SOFTWARE. # =================================================================== # This implementation was written with reference to the RIPEMD-160 # specification, which is available at: # http://homes.esat.kuleuven.be/~cosicart/pdf/AB-9601/ # It is also documented in the _Handbook of Applied Cryptography_, as # Algorithm 9.55. It's on page 30 of the following PDF file: # http://www.cacr.math.uwaterloo.ca/hac/about/chap9.pdf # The RIPEMD-160 specification doesn't really tell us how to do padding, but # since RIPEMD-160 is inspired by MD4, you can use the padding algorithm from # RFC 1320. # According to http://www.users.zetnet.co.uk/hopwood/crypto/scan/md.html: # RIPEMD-160 is big-bit-endian, little-byte-endian, and left-justified. (Note # the opposite bit and byte order.) SCAN 1.0.16 incorrectly stated # "little-bit-endian, little-byte-endian, and right-justified". """RIPEMD-160 hash module""" __all__ = ['new', 'digest_size'] __revision__ = "$Id$" import struct # Rather than writing & 0xffffffffL every time (and risking typographical # errors each time), we use this function. # Thanks to Thomas Dixon for the idea. def u32(n): return n & 0xFFFFffffL # # Ordering of the message words # # The permutation ρ rho = [7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8] # The permutation π(i) = 9i + 5 (mod 16) pi = [(9*i + 5) & 15 for i in range(16)] # Round permutation r (left line) rl = [range(16)] # id rl += [[rho[j] for j in rl[-1]]] # ρ rl += [[rho[j] for j in rl[-1]]] # ρ^2 rl += [[rho[j] for j in rl[-1]]] # ρ^3 rl += [[rho[j] for j in rl[-1]]] # ρ^4 # r' (right line) rr = [list(pi)] # π rr += [[rho[j] for j in rr[-1]]] # ρπ rr += [[rho[j] for j in rr[-1]]] # ρ^2 π rr += [[rho[j] for j in rr[-1]]] # ρ^3 π rr += [[rho[j] for j in rr[-1]]] # ρ^4 π # # Boolean functions # # f₁ (x, y, z) = x ⊕ y ⊕ z f1 = lambda x, y, z: x ^ y ^ z # f₂ (x, y, z) = (x ∧ y) ∨ (¬x ∧ z) f2 = lambda x, y, z: (x & y) | (~x & z) # f₃ (x, y, z) = (x ∨ ¬y) ⊕ z f3 = lambda x, y, z: (x | ~y) ^ z # f₄ (x, y, z) = (x ∧ z) ∨ (y ∧ ¬z) f4 = lambda x, y, z: (x & z) | (y & ~z) # f₅ (x, y, z) = x ⊕ (y ∨ ¬z) f5 = lambda x, y, z: x ^ (y | ~z) # boolean functions (left line) fl = [f1, f2, f3, f4, f5] # boolean functions (right line) fr = [f5, f4, f3, f2, f1] # # Shifts # # round X0 X1 X2 X3 ... _shift1 = [11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8] _shift2 = [12, 13, 11, 15, 6, 9, 9, 7, 12, 15, 11, 13, 7, 8, 7, 7] _shift3 = [13, 15, 14, 11, 7, 7, 6, 8, 13, 14, 13, 12, 5, 5, 6, 9] _shift4 = [14, 11, 12, 14, 8, 6, 5, 5, 15, 12, 15, 14, 9, 9, 8, 6] _shift5 = [15, 12, 13, 13, 9, 5, 8, 6, 14, 11, 12, 11, 8, 6, 5, 5] # shifts (left line) sl = [[_shift1[rl[0][i]] for i in range(16)]] sl.append([_shift2[rl[1][i]] for i in range(16)]) sl.append([_shift3[rl[2][i]] for i in range(16)]) sl.append([_shift4[rl[3][i]] for i in range(16)]) sl.append([_shift5[rl[4][i]] for i in range(16)]) # shifts (right line) sr = [[_shift1[rr[0][i]] for i in range(16)]] sr.append([_shift2[rr[1][i]] for i in range(16)]) sr.append([_shift3[rr[2][i]] for i in range(16)]) sr.append([_shift4[rr[3][i]] for i in range(16)]) sr.append([_shift5[rr[4][i]] for i in range(16)]) # # Constants # _kg = lambda x, y: int(2**30 * (y ** (1.0 / x))) # constants (left line) KL = [ 0, # Round 1: 0 _kg(2, 2), # Round 2: 2**30 * sqrt(2) _kg(2, 3), # Round 3: 2**30 * sqrt(3) _kg(2, 5), # Round 4: 2**30 * sqrt(5) _kg(2, 7), # Round 5: 2**30 * sqrt(7) ] # constants (right line) KR = [ _kg(3, 2), # Round 1: 2**30 * cubert(2) _kg(3, 3), # Round 2: 2**30 * cubert(3) _kg(3, 5), # Round 3: 2**30 * cubert(5) _kg(3, 7), # Round 4: 2**30 * cubert(7) 0, # Round 5: 0 ] # cyclic rotate def rol(s, n): assert 0 <= s <= 31 assert 0 <= n <= 0xFFFFffffL return u32((n << s) | (n >> (32-s))) # Initial value initial_h = tuple(struct.unpack("<5L", "0123456789ABCDEFFEDCBA9876543210F0E1D2C3".decode('hex'))) def box(h, f, k, x, r, s): assert len(s) == 16 assert len(x) == 16 assert len(r) == 16 (a, b, c, d, e) = h for word in range(16): T = u32(a + f(b, c, d) + x[r[word]] + k) T = u32(rol(s[word], T) + e) (b, c, d, e, a) = (T, b, rol(10, c), d, e) return (a, b, c, d, e) def _compress(h, x): # x is a list of 16 x 32-bit words hl = hr = h # Iterate through all 5 rounds of the compression function for each parallel pipeline for round in range(5): # left line hl = box(hl, fl[round], KL[round], x, rl[round], sl[round]) # right line hr = box(hr, fr[round], KR[round], x, rr[round], sr[round]) # Mix the two pipelines together h = (u32(h[1] + hl[2] + hr[3]), u32(h[2] + hl[3] + hr[4]), u32(h[3] + hl[4] + hr[0]), u32(h[4] + hl[0] + hr[1]), u32(h[0] + hl[1] + hr[2])) return h def compress(h, s): """The RIPEMD-160 compression function""" assert len(s) % 64 == 0 p = 0 while p < len(s): h = _compress(h, struct.unpack("<16L", s[p:p+64])) p += 64 assert p == len(s) return h class RIPEMD160(object): digest_size = 20 def __init__(self, data=""): self.h = initial_h self.bytes = 0 # input size (in bytes) self.buf = "" self.update(data) def update(self, data): self.buf += data self.bytes += len(data) p = len(self.buf) & ~63 # p = floor(len(self.buf) / 64) * 64 if p > 0: self.h = compress(self.h, self.buf[:p]) self.buf = self.buf[p:] assert len(self.buf) < 64 def digest(self): # Merkle-Damgård strengthening, per RFC 1320 # We pad the input with a 1, followed by zeros, followed by the 64-bit # length of the message in bits, modulo 2**64. length = (self.bytes << 3) & (2**64-1) # The total length of the message in bits, modulo 2**64 assert len(self.buf) < 64 data = self.buf + "\x80" if len(data) <= 56: # one final block assert len(data) <= 56 data = struct.pack("<56sQ", data, length) else: assert len(data) <= 120 data = struct.pack("<120sQ", data, length) h = compress(self.h, data) return struct.pack("<5L", *h) def hexdigest(self): return self.digest().encode('hex') def copy(self): obj = self.__class__() obj.h = self.h obj.bytes = self.bytes obj.buf = self.buf return obj def new(data=""): return RIPEMD160(data) digest_size = 20 # vim:set ts=4 sw=4 sts=4 expandtab: