src/CryptoPlus/Hash/pymd5.py

   1 #!/usr/bin/env python
   2 # -*- coding: iso-8859-1 -*-
   3
   4 # Note that PyPy contains also a built-in module 'md5' which will hide
   5 # this one if compiled in.
   6
   7 """A sample implementation of MD5 in pure Python.
   8
   9 This is an implementation of the MD5 hash function, as specified by
  10 RFC 1321, in pure Python. It was implemented using Bruce Schneier's
  11 excellent book "Applied Cryptography", 2nd ed., 1996.
  12
  13 Surely this is not meant to compete with the existing implementation
  14 of the Python standard library (written in C). Rather, it should be
  15 seen as a Python complement that is more readable than C and can be
  16 used more conveniently for learning and experimenting purposes in
  17 the field of cryptography.
  18
  19 This module tries very hard to follow the API of the existing Python
  20 standard library's "md5" module, but although it seems to work fine,
  21 it has not been extensively tested! (But note that there is a test
  22 module, test_md5py.py, that compares this Python implementation with
  23 the C one of the Python standard library.
  24
  25 BEWARE: this comes with no guarantee whatsoever about fitness and/or
  26 other properties! Specifically, do not use this in any production
  27 code! License is Python License!
  28
  29 Special thanks to Aurelian Coman who fixed some nasty bugs!
  30
  31 Dinu C. Gherman
  32 """
  33
  34
  35 __date__    = '2004-11-17'
  36 __version__ = 0.91 # Modernised by J. Hallén and L. Creighton for Pypy
  37
  38 __metaclass__ = type # or genrpy won't work
  39
  40 import struct, copy
  41
  42
  43 # ======================================================================
  44 # Bit-Manipulation helpers
  45 # ======================================================================
  46
  47 def _bytelist2long(list):
  48     "Transform a list of characters into a list of longs."
  49
  50     imax = len(list)/4
  51     hl = [0L] * imax
  52
  53     j = 0
  54     i = 0
  55     while i < imax:
  56         b0 = long(ord(list[j]))
  57         b1 = (long(ord(list[j+1]))) << 8
  58         b2 = (long(ord(list[j+2]))) << 16
  59         b3 = (long(ord(list[j+3]))) << 24
  60         hl[i] = b0 | b1 |b2 | b3
  61         i = i+1
  62         j = j+4
  63
  64     return hl
  65
  66
  67 def _rotateLeft(x, n):
  68     "Rotate x (32 bit) left n bits circularly."
  69
  70     return (x << n) | (x >> (32-n))
  71
  72
  73 # ======================================================================
  74 # The real MD5 meat...
  75 #
  76 #   Implemented after "Applied Cryptography", 2nd ed., 1996,
  77 #   pp. 436-441 by Bruce Schneier.
  78 # ======================================================================
  79
  80 # F, G, H and I are basic MD5 functions.
  81
  82 def F(x, y, z):
  83     return (x & y) | ((~x) & z)
  84
  85 def G(x, y, z):
  86     return (x & z) | (y & (~z))
  87
  88 def H(x, y, z):
  89     return x ^ y ^ z
  90
  91 def I(x, y, z):
  92     return y ^ (x | (~z))
  93
  94
  95 def XX(func, a, b, c, d, x, s, ac):
  96     """Wrapper for call distribution to functions F, G, H and I.
  97
  98     This replaces functions FF, GG, HH and II from "Appl. Crypto."
  99     Rotation is separate from addition to prevent recomputation
 100     (now summed-up in one function).
 101     """
 102
 103     res = 0L
 104     res = res + a + func(b, c, d)
 105     res = res + x
 106     res = res + ac
 107     res = res & 0xffffffffL
 108     res = _rotateLeft(res, s)
 109     res = res & 0xffffffffL
 110     res = res + b
 111
 112     return res & 0xffffffffL
 113
 114
 115 class MD5Type:
 116     "An implementation of the MD5 hash function in pure Python."
 117
 118     def __init__(self):
 119         "Initialisation."
 120
 121         # Initial message length in bits(!).
 122         self.length = 0L
 123         self.count = [0, 0]
 124
 125         # Initial empty message as a sequence of bytes (8 bit characters).
 126         self.input = []
 127
 128         # Call a separate init function, that can be used repeatedly
 129         # to start from scratch on the same object.
 130         self.init()
 131
 132
 133     def init(self):
 134         "Initialize the message-digest and set all fields to zero."
 135
 136         self.length = 0L
 137         self.count = [0, 0]
 138         self.input = []
 139
 140         # Load magic initialization constants.
 141         self.A = 0x67452301L
 142         self.B = 0xefcdab89L
 143         self.C = 0x98badcfeL
 144         self.D = 0x10325476L
 145
 146
 147     def _transform(self, inp):
 148         """Basic MD5 step transforming the digest based on the input.
 149
 150         Note that if the Mysterious Constants are arranged backwards
 151         in little-endian order and decrypted with the DES they produce
 152         OCCULT MESSAGES!
 153         """
 154
 155         a, b, c, d = A, B, C, D = self.A, self.B, self.C, self.D
 156
 157         # Round 1.
 158
 159         S11, S12, S13, S14 = 7, 12, 17, 22
 160
 161         a = XX(F, a, b, c, d, inp[ 0], S11, 0xD76AA478L) # 1
 162         d = XX(F, d, a, b, c, inp[ 1], S12, 0xE8C7B756L) # 2
 163         c = XX(F, c, d, a, b, inp[ 2], S13, 0x242070DBL) # 3
 164         b = XX(F, b, c, d, a, inp[ 3], S14, 0xC1BDCEEEL) # 4
 165         a = XX(F, a, b, c, d, inp[ 4], S11, 0xF57C0FAFL) # 5
 166         d = XX(F, d, a, b, c, inp[ 5], S12, 0x4787C62AL) # 6
 167         c = XX(F, c, d, a, b, inp[ 6], S13, 0xA8304613L) # 7
 168         b = XX(F, b, c, d, a, inp[ 7], S14, 0xFD469501L) # 8
 169         a = XX(F, a, b, c, d, inp[ 8], S11, 0x698098D8L) # 9
 170         d = XX(F, d, a, b, c, inp[ 9], S12, 0x8B44F7AFL) # 10
 171         c = XX(F, c, d, a, b, inp[10], S13, 0xFFFF5BB1L) # 11
 172         b = XX(F, b, c, d, a, inp[11], S14, 0x895CD7BEL) # 12
 173         a = XX(F, a, b, c, d, inp[12], S11, 0x6B901122L) # 13
 174         d = XX(F, d, a, b, c, inp[13], S12, 0xFD987193L) # 14
 175         c = XX(F, c, d, a, b, inp[14], S13, 0xA679438EL) # 15
 176         b = XX(F, b, c, d, a, inp[15], S14, 0x49B40821L) # 16
 177
 178         # Round 2.
 179
 180         S21, S22, S23, S24 = 5, 9, 14, 20
 181
 182         a = XX(G, a, b, c, d, inp[ 1], S21, 0xF61E2562L) # 17
 183         d = XX(G, d, a, b, c, inp[ 6], S22, 0xC040B340L) # 18
 184         c = XX(G, c, d, a, b, inp[11], S23, 0x265E5A51L) # 19
 185         b = XX(G, b, c, d, a, inp[ 0], S24, 0xE9B6C7AAL) # 20
 186         a = XX(G, a, b, c, d, inp[ 5], S21, 0xD62F105DL) # 21
 187         d = XX(G, d, a, b, c, inp[10], S22, 0x02441453L) # 22
 188         c = XX(G, c, d, a, b, inp[15], S23, 0xD8A1E681L) # 23
 189         b = XX(G, b, c, d, a, inp[ 4], S24, 0xE7D3FBC8L) # 24
 190         a = XX(G, a, b, c, d, inp[ 9], S21, 0x21E1CDE6L) # 25
 191         d = XX(G, d, a, b, c, inp[14], S22, 0xC33707D6L) # 26
 192         c = XX(G, c, d, a, b, inp[ 3], S23, 0xF4D50D87L) # 27
 193         b = XX(G, b, c, d, a, inp[ 8], S24, 0x455A14EDL) # 28
 194         a = XX(G, a, b, c, d, inp[13], S21, 0xA9E3E905L) # 29
 195         d = XX(G, d, a, b, c, inp[ 2], S22, 0xFCEFA3F8L) # 30
 196         c = XX(G, c, d, a, b, inp[ 7], S23, 0x676F02D9L) # 31
 197         b = XX(G, b, c, d, a, inp[12], S24, 0x8D2A4C8AL) # 32
 198
 199         # Round 3.
 200
 201         S31, S32, S33, S34 = 4, 11, 16, 23
 202
 203         a = XX(H, a, b, c, d, inp[ 5], S31, 0xFFFA3942L) # 33
 204         d = XX(H, d, a, b, c, inp[ 8], S32, 0x8771F681L) # 34
 205         c = XX(H, c, d, a, b, inp[11], S33, 0x6D9D6122L) # 35
 206         b = XX(H, b, c, d, a, inp[14], S34, 0xFDE5380CL) # 36
 207         a = XX(H, a, b, c, d, inp[ 1], S31, 0xA4BEEA44L) # 37
 208         d = XX(H, d, a, b, c, inp[ 4], S32, 0x4BDECFA9L) # 38
 209         c = XX(H, c, d, a, b, inp[ 7], S33, 0xF6BB4B60L) # 39
 210         b = XX(H, b, c, d, a, inp[10], S34, 0xBEBFBC70L) # 40
 211         a = XX(H, a, b, c, d, inp[13], S31, 0x289B7EC6L) # 41
 212         d = XX(H, d, a, b, c, inp[ 0], S32, 0xEAA127FAL) # 42
 213         c = XX(H, c, d, a, b, inp[ 3], S33, 0xD4EF3085L) # 43
 214         b = XX(H, b, c, d, a, inp[ 6], S34, 0x04881D05L) # 44
 215         a = XX(H, a, b, c, d, inp[ 9], S31, 0xD9D4D039L) # 45
 216         d = XX(H, d, a, b, c, inp[12], S32, 0xE6DB99E5L) # 46
 217         c = XX(H, c, d, a, b, inp[15], S33, 0x1FA27CF8L) # 47
 218         b = XX(H, b, c, d, a, inp[ 2], S34, 0xC4AC5665L) # 48
 219
 220         # Round 4.
 221
 222         S41, S42, S43, S44 = 6, 10, 15, 21
 223
 224         a = XX(I, a, b, c, d, inp[ 0], S41, 0xF4292244L) # 49
 225         d = XX(I, d, a, b, c, inp[ 7], S42, 0x432AFF97L) # 50
 226         c = XX(I, c, d, a, b, inp[14], S43, 0xAB9423A7L) # 51
 227         b = XX(I, b, c, d, a, inp[ 5], S44, 0xFC93A039L) # 52
 228         a = XX(I, a, b, c, d, inp[12], S41, 0x655B59C3L) # 53
 229         d = XX(I, d, a, b, c, inp[ 3], S42, 0x8F0CCC92L) # 54
 230         c = XX(I, c, d, a, b, inp[10], S43, 0xFFEFF47DL) # 55
 231         b = XX(I, b, c, d, a, inp[ 1], S44, 0x85845DD1L) # 56
 232         a = XX(I, a, b, c, d, inp[ 8], S41, 0x6FA87E4FL) # 57
 233         d = XX(I, d, a, b, c, inp[15], S42, 0xFE2CE6E0L) # 58
 234         c = XX(I, c, d, a, b, inp[ 6], S43, 0xA3014314L) # 59
 235         b = XX(I, b, c, d, a, inp[13], S44, 0x4E0811A1L) # 60
 236         a = XX(I, a, b, c, d, inp[ 4], S41, 0xF7537E82L) # 61
 237         d = XX(I, d, a, b, c, inp[11], S42, 0xBD3AF235L) # 62
 238         c = XX(I, c, d, a, b, inp[ 2], S43, 0x2AD7D2BBL) # 63
 239         b = XX(I, b, c, d, a, inp[ 9], S44, 0xEB86D391L) # 64
 240
 241         A = (A + a) & 0xffffffffL
 242         B = (B + b) & 0xffffffffL
 243         C = (C + c) & 0xffffffffL
 244         D = (D + d) & 0xffffffffL
 245
 246         self.A, self.B, self.C, self.D = A, B, C, D
 247
 248
 249     # Down from here all methods follow the Python Standard Library
 250     # API of the md5 module.
 251
 252     def update(self, inBuf):
 253         """Add to the current message.
 254
 255         Update the md5 object with the string arg. Repeated calls
 256         are equivalent to a single call with the concatenation of all
 257         the arguments, i.e. m.update(a); m.update(b) is equivalent
 258         to m.update(a+b).
 259
 260         The hash is immediately calculated for all full blocks. The final
 261         calculation is made in digest(). This allows us to keep an
 262         intermediate value for the hash, so that we only need to make
 263         minimal recalculation if we call update() to add moredata to
 264         the hashed string.
 265         """
 266
 267         leninBuf = long(len(inBuf))
 268
 269         # Compute number of bytes mod 64.
 270         index = (self.count[0] >> 3) & 0x3FL
 271
 272         # Update number of bits.
 273         self.count[0] = self.count[0] + (leninBuf << 3)
 274         if self.count[0] < (leninBuf << 3):
 275             self.count[1] = self.count[1] + 1
 276         self.count[1] = self.count[1] + (leninBuf >> 29)
 277
 278         partLen = 64 - index
 279
 280         if leninBuf >= partLen:
 281             self.input[index:] = list(inBuf[:partLen])
 282             self._transform(_bytelist2long(self.input))
 283             i = partLen
 284             while i + 63 < leninBuf:
 285                 self._transform(_bytelist2long(list(inBuf[i:i+64])))
 286                 i = i + 64
 287             else:
 288                 self.input = list(inBuf[i:leninBuf])
 289         else:
 290             i = 0
 291             self.input = self.input + list(inBuf)
 292
 293
 294     def digest(self):
 295         """Terminate the message-digest computation and return digest.
 296
 297         Return the digest of the strings passed to the update()
 298         method so far. This is a 16-byte string which may contain
 299         non-ASCII characters, including null bytes.
 300         """
 301
 302         A = self.A
 303         B = self.B
 304         C = self.C
 305         D = self.D
 306         input = [] + self.input
 307         count = [] + self.count
 308
 309         index = (self.count[0] >> 3) & 0x3fL
 310
 311         if index < 56:
 312             padLen = 56 - index
 313         else:
 314             padLen = 120 - index
 315
 316         padding = ['\200'] + ['\000'] * 63
 317         self.update(padding[:padLen])
 318
 319         # Append length (before padding).
 320         bits = _bytelist2long(self.input[:56]) + count
 321
 322         self._transform(bits)
 323
 324         # Store state in digest.
 325         digest = struct.pack("<IIII", self.A, self.B, self.C, self.D)
 326
 327         self.A = A
 328         self.B = B
 329         self.C = C
 330         self.D = D
 331         self.input = input
 332         self.count = count
 333
 334         return digest
 335
 336
 337     def hexdigest(self):
 338         """Terminate and return digest in HEX form.
 339
 340         Like digest() except the digest is returned as a string of
 341         length 32, containing only hexadecimal digits. This may be
 342         used to exchange the value safely in email or other non-
 343         binary environments.
 344         """
 345
 346         return ''.join(['%02x' % ord(c) for c in self.digest()])
 347
 348     def copy(self):
 349         """Return a clone object.
 350
 351         Return a copy ('clone') of the md5 object. This can be used
 352         to efficiently compute the digests of strings that share
 353         a common initial substring.
 354         """
 355         if 0: # set this to 1 to make the flow space crash
 356             return copy.deepcopy(self)
 357         clone = self.__class__()
 358         clone.length = self.length
 359         clone.count  = [] + self.count[:]
 360         clone.input  = [] + self.input
 361         clone.A = self.A
 362         clone.B = self.B
 363         clone.C = self.C
 364         clone.D = self.D
 365         return clone
 366
 367
 368 # ======================================================================
 369 # Mimic Python top-level functions from standard library API
 370 # for consistency with the md5 module of the standard library.
 371 # ======================================================================
 372
 373 digest_size = 16
 374
 375 def new(arg=None):
 376     """Return a new md5 crypto object.
 377
 378     If arg is present, the method call update(arg) is made.
 379     """
 380
 381     crypto = MD5Type()
 382     if arg:
 383         crypto.update(arg)
 384
 385     return crypto
 386
 387
 388 def md5(arg=None):
 389     """Same as new().
 390
 391     For backward compatibility reasons, this is an alternative
 392     name for the new() function.
 393     """
 394
 395     return new(arg)