1 # =============================================================================
2 # Copyright (c) 2008 Christophe Oosterlynck (christophe.oosterlynck_AT_gmail.com)
3 # Philippe Teuwen (philippe.teuwen_AT_nxp.com)
5 # Permission is hereby granted, free of charge, to any person obtaining a copy
6 # of this software and associated documentation files (the "Software"), to deal
7 # in the Software without restriction, including without limitation the rights
8 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 # copies of the Software, and to permit persons to whom the Software is
10 # furnished to do so, subject to the following conditions:
12 # The above copyright notice and this permission notice shall be included in
13 # all copies or substantial portions of the Software.
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 # =============================================================================
24 """RadioGatun pure python implementation
26 Code based on the standard found here: http://radiogatun.noekeon.org/
27 Api and code interface is based on the MD5 implementation of pypy
28 http://codespeak.net/pypy/dist/pypy/doc/home.html
34 numberOfBlankIterations
= 16
37 """construct an empty state variable
39 return {"A":[0]*millSize
,"B":[[0]*beltWidth
for x
in range(beltLength
)]}
41 def XORstate(state1
,state2
):
42 """XOR the vectors of the status of a RadioGatun object
45 for i
in xrange(millSize
):
46 out
["A"][i
] = state1
["A"][i
] ^ state2
["A"][i
]
47 for i
in xrange(beltLength
):
48 for j
in xrange(beltWidth
):
49 out
["B"][i
][j
] = state1
["B"][i
][j
] ^ state2
["B"][i
][j
]
55 input = 1 blocklength string
56 wl = wordlength of the RadioGatun hash object
59 for i
in xrange(beltWidth
):
60 # reverse endianness of byte ordering and convert the input
62 p_i
= string2number(inp
[i
*wl
:(i
+1)*wl
][::-1])
63 mapped
["B"][0][i
] = p_i
64 mapped
["A"][i
+16] = p_i
70 state = the RadioGatun status
71 wl = wordlength of the RadioGatun hash object
74 # Belt function: simple rotation
75 for i
in xrange(beltLength
):
76 out
["B"][i
] = state
["B"][(i
- 1)%beltLength
]
77 # Mill to belt feedforward
79 out
["B"][i
+1][i
%beltWidth
] ^
= state
["A"][i
+1]
81 out
["A"] = Mill(state
["A"],wl
)
82 # Belt to mill feedforward
83 for i
in xrange(beltWidth
):
84 out
["A"][i
+13] ^
= state
["B"][12][i
]
90 a = Mill variable of the RadioGatun status
91 wl = wordlength of the RadioGatun hash object
94 # Gamma: Non-linearity
95 for i
in xrange(millSize
):
96 #A[i] = a[i] ^ ~((~a[(i+1)%millSize]) & (a[(i+2)%millSize]) )
97 A
[i
] = a
[i
] ^
((a
[(i
+1)%millSize
]) |
(~
(a
[(i
+2)%millSize
])&((2**(wl
*8))-1)) )
98 # Pi: Intra-word and inter-word dispersion
99 for i
in xrange(millSize
):
100 #TODO: don't hardcode wordlength in ror64
101 a
[i
] = _rotateRight(A
[(7*i
)%millSize
],i
*(i
+1)/2,wl
*8)
103 for i
in xrange(millSize
):
104 A
[i
] = a
[i
] ^ a
[(i
+1)%millSize
] ^ a
[(i
+4)%millSize
]
109 class RadioGatunType
:
110 "An implementation of the MD5 hash function in pure Python."
112 def __init__(self
,wl
):
115 wl = wordlength (in bits) of the RadioGatun hash method
116 between 1 and 64 (default = 64)
119 if not ( 1 <= wl
<= 64) or not (wl
%8 == 0 ):
120 raise ValueError,"Wordlength should be a multiple of 8 between 1 and 64"
122 # word & block length in bytes
123 self
.wordlength
= wl
/8
124 self
.blocklength
= self
.wordlength
*3
126 # Initial message length in bits(!).
130 # Initial empty message as a sequence of bytes (8 bit characters).
133 # Call a separate init function, that can be used repeatedly
134 # to start from scratch on the same object.
139 """Initialize the message-digest and set all fields to zero.
148 def _transform(self
, inp
):
149 """Basic RadioGatun step transforming the digest based on the input.
151 Performs the inside of the first loop of alternating input construction
152 of RadioGatun. The only thing that can be done every time new data is
153 submitted to the hash object.
154 Mangling and output mapping can only follow when all input data has
157 T
= XORstate(self
.S
,F_i(inp
,self
.wordlength
))
158 self
.S
= R(T
,self
.wordlength
)
161 # Down from here all methods follow the Python Standard Library
162 # API of the md5 module.
164 def update(self
, inBuf
):
165 """Add to the current message.
167 Update the radiogatun object with the string arg. Repeated calls
168 are equivalent to a single call with the concatenation of all
169 the arguments, i.e. m.update(a); m.update(b) is equivalent
172 The hash is immediately calculated for all full blocks. The final
173 calculation is made in digest(). This allows us to keep an
174 intermediate value for the hash, so that we only need to make
175 minimal recalculation if we call update() to add moredata to
178 # Amount of bytes given at input
179 leninBuf
= long(len(inBuf
))
181 # Compute number of bytes mod 64.
182 index
= (self
.count
[0] >> 3) % self
.blocklength
184 # Update number of bits.
185 self
.count
[0] = self
.count
[0] + (leninBuf
<< 3)
187 partLen
= self
.blocklength
- index
189 # if length of input is at least the amount of bytes needed to fill a block
190 if leninBuf
>= partLen
:
191 self
.input = self
.input[:index
] + inBuf
[:partLen
]
192 self
._transform
(self
.input)
194 while i
+ self
.blocklength
- 1 < leninBuf
:
195 self
._transform
(inBuf
[i
:i
+self
.blocklength
])
196 i
= i
+ self
.blocklength
198 self
.input = inBuf
[i
:leninBuf
]
199 # if not enough bytes at input to fill a block
202 self
.input = self
.input + inBuf
205 def digest(self
, length
=256):
206 """Terminate the message-digest computation and return digest.
208 length = output length of the digest in bits
209 any multiple of 8 with a minimum of 8
212 Return the digest of the strings passed to the update()
213 method so far. This is a byte string which may contain
214 non-ASCII characters, including null bytes.
216 Calling digest() doesn't change the internal state. Adding data via
217 update() can still continu after asking for an intermediate digest
222 inp
= "" + self
.input
223 count
= [] + self
.count
225 index
= (self
.count
[0] >> 3) % self
.blocklength
227 if index
< self
.blocklength
:
228 padLen
= self
.blocklength
- index
230 padLen
= 2*self
.blocklength
- index
232 #provide padding chars encoded as little endian
233 padding
= ['\001'] + ['\000'] * (padLen
- 1)
234 self
.update(''.join(padding
))
236 # Mangling = blank rounds
237 for i
in xrange(numberOfBlankIterations
):
238 self
.S
= R(self
.S
,self
.wordlength
)
241 # Store state in digest.
243 for i
in xrange((length
)/self
.wordlength
/2):
244 self
.S
= R(self
.S
,self
.wordlength
)
246 digest
+= number2string_N((self
.S
["A"][1]),self
.wordlength
)[::-1] + number2string_N((self
.S
["A"][2]),self
.wordlength
)[::-1]
252 return digest
[:length
/8]
255 def hexdigest(self
,length
=256):
256 """Terminate and return digest in HEX form.
258 length = output length of the digest in bits
259 any multiple of 8 with a minimum of 8
262 Like digest() except the digest is returned as a string of
263 length 'length', containing only hexadecimal digits. This may be
264 used to exchange the value safely in email or other non-
267 Calling hexdigest() doesn't change the internal state. Adding data via
268 update() can still continu after asking for an intermediate digest
272 return ''.join(['%02x' % ord(c
) for c
in self
.digest(length
)])
275 """Return a clone object.
277 Return a copy ('clone') of the radiogatun object. This can be used
278 to efficiently compute the digests of strings that share
279 a common initial substring.
281 if 0: # set this to 1 to make the flow space crash
282 return copy
.deepcopy(self
)
283 clone
= self
.__class
__()
284 clone
.length
= self
.length
285 clone
.count
= [] + self
.count
[:]
286 clone
.input = "" + self
.input
290 # ======================================================================
291 # TOP LEVEL INTERFACE
292 # ======================================================================
294 def new(wl
=64,arg
=None):
295 """Return a new RadioGatun hash object
297 wl = wordlength (in bits) of the RadioGatun hash method
298 between 1 and 64 (default = 64)
299 arg = if present, the method call update(arg) is made
301 EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
303 >>> import pyradiogatun
307 >>> hasher = pyradiogatun.new()
308 >>> hasher.update('1234567890123456')
309 >>> hasher.hexdigest()
310 'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
312 >>> hasher = pyradiogatun.new()
313 >>> hasher.update('Santa Barbara, California')
314 >>> hasher.hexdigest()
315 '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f'
319 >>> hasher = pyradiogatun.new(32)
320 >>> hasher.update('1234567890123456')
321 >>> hasher.hexdigest()
322 '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
324 >>> hasher = pyradiogatun.new(32)
325 >>> hasher.update('Santa Barbara, California')
326 >>> hasher.hexdigest()
327 '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54'
330 crypto
= RadioGatunType(wl
)
336 # ======================================================================
338 # ======================================================================
340 def rotateRight(x
, amountToShift
, totalBits
):
341 """Rotate x (consisting of 'totalBits' bits) n bits to right.
343 x = integer input to be rotated
344 amountToShift = the amount of bits that should be shifted
345 totalBits = total amount bits at the input for rotation
348 n_mod
= ((amountToShift
% totalBits
) + totalBits
) % totalBits
349 return ((x
>> n_mod
) |
((x
<< (totalBits
-n_mod
)))&((2**totalBits
)-1))
351 def string2number(i
):
352 """ Convert a string to a number
354 Input: string (big-endian)
355 Output: long or integer
357 return int(i
.encode('hex'),16)
359 def number2string_N(i
, N
):
360 """Convert a number to a string of fixed size
364 Output: string (big-endian)
366 s
= '%0*x' % (N
*2, i
)
367 return s
.decode('hex')
369 # ======================================================================
371 # ======================================================================
377 if __name__
== "__main__":
378 print "DOCTEST running... no messages = all good"