e8368dc52186f0e2c076161577e3aff81b4647fb
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
33 millSize
= 2*beltWidth
+ beltLength
34 numberOfBlankIterations
= 16
37 """construct an empty state variable
39 return {"A":[0]*millSize
,"B":[[0]*beltWidth
for x
in range(beltLength
)]}
41 def XOR_F_i(state
,inp
,wl
):
44 mapping input blocks to a state variable + XOR step of the alternating-
47 input = 1 blocklength string
48 wl = wordlength of the RadioGatun hash object
50 for i
in xrange(beltWidth
):
51 # reverse endianness of byte ordering and convert the input
53 p_i
= string2number(inp
[i
*wl
:(i
+1)*wl
][::-1])
54 state
["B"][0][i
] ^
= p_i
55 state
["A"][i
+millSize
-beltWidth
] ^
= p_i
61 state = the RadioGatun status
62 wl = wordlength of the RadioGatun hash object
65 # Belt function: simple rotation
66 out
["B"] = state
["B"][-1:]+state
["B"][:-1]
67 # Mill to belt feedforward
68 for i
in xrange(beltLength
- 1):
69 out
["B"][i
+1][i
%beltWidth
] ^
= state
["A"][i
+1]
71 out
["A"] = Mill(state
["A"],wl
)
72 # Belt to mill feedforward
73 for i
in xrange(beltWidth
):
74 out
["A"][i
+beltLength
] ^
= state
["B"][-1][i
]
80 a = Mill variable of the RadioGatun status
81 wl = wordlength of the RadioGatun hash object
84 # Gamma: Non-linearity
85 for i
in xrange(millSize
):
86 A
[i
] = a
[i
] ^ ~
((~a
[(i
+1)%millSize
]) & (a
[(i
+2)%millSize
]) )
88 # A[i] = a[i] ^ ((a[(i+1)%millSize]) | (~(a[(i+2)%millSize])&((2**(wl*8))-1)) )
89 # Pi: Intra-word and inter-word dispersion
90 for i
in xrange(millSize
):
91 a
[i
] = rotateRight(A
[(7*i
)%millSize
],i
*(i
+1)/2,wl
*8)
93 for i
in xrange(millSize
):
94 A
[i
] = a
[i
] ^ a
[(i
+1)%millSize
] ^ a
[(i
+4)%millSize
]
100 "An implementation of the RadioGatun hash function in pure Python."
102 def __init__(self
,wl
):
105 wl = wordlength (in bits) of the RadioGatun hash method
106 between 8 and 64 (default = 64)
109 if not ( 8 <= wl
<= 64) or not (wl
%8 == 0 ):
110 raise ValueError,"Wordlength should be a multiple of 8 between 8 and 64"
112 # word & block length in bytes
113 self
.wordlength
= wl
/8
114 self
.blocklength
= self
.wordlength
*beltWidth
116 # Initial message length in bits(!).
120 # Initial empty message as a sequence of bytes (8 bit characters).
123 # Call a separate init function, that can be used repeatedly
124 # to start from scratch on the same object.
129 """Initialize the message-digest and set all fields to zero.
131 Can be used to reinitialize the hash object
140 def _transform(self
, inp
):
141 """Basic RadioGatun step transforming the digest based on the input.
143 Performs the inside of the first loop of alternating input construction
144 of RadioGatun. The only thing that can be done every time new data is
145 submitted to the hash object.
146 Mangling and output mapping can only follow when all input data has
149 T
= XOR_F_i(self
.S
,inp
,self
.wordlength
)
150 self
.S
= R(T
,self
.wordlength
)
153 # Down from here all methods follow the Python Standard Library
154 # API of the md5 module.
156 def update(self
, inBuf
):
157 """Add to the current message.
159 Update the radiogatun object with the string arg. Repeated calls
160 are equivalent to a single call with the concatenation of all
161 the arguments, i.e. m.update(a); m.update(b) is equivalent
164 The hash is immediately calculated for all full blocks. The final
165 calculation is made in digest(). This allows us to keep an
166 intermediate value for the hash, so that we only need to make
167 minimal recalculation if we call update() to add moredata to
170 # Amount of bytes given at input
171 leninBuf
= long(len(inBuf
))
173 # Compute number of bytes mod 64.
174 index
= (self
.count
>> 3) % self
.blocklength
176 # Update number of bits.
177 self
.count
= self
.count
+ (leninBuf
<< 3)
179 partLen
= self
.blocklength
- index
181 # if length of input is at least the amount of bytes needed to fill a block
182 if leninBuf
>= partLen
:
183 self
.input = self
.input[:index
] + inBuf
[:partLen
]
184 self
._transform
(self
.input)
186 while i
+ self
.blocklength
- 1 < leninBuf
:
187 self
._transform
(inBuf
[i
:i
+self
.blocklength
])
188 i
= i
+ self
.blocklength
190 self
.input = inBuf
[i
:leninBuf
]
191 # if not enough bytes at input to fill a block
194 self
.input = self
.input + inBuf
197 def digest(self
, length
=256):
198 """Terminate the message-digest computation and return digest.
200 length = output length of the digest in bits
201 any multiple of 8 with a minimum of 8
204 Return the digest of the strings passed to the update()
205 method so far. This is a byte string which may contain
206 non-ASCII characters, including null bytes.
208 Calling digest() doesn't change the internal state. Adding data via
209 update() can still continu after asking for an intermediate digest
214 inp
= "" + self
.input
217 index
= (self
.count
>> 3) % self
.blocklength
219 padLen
= self
.blocklength
- index
221 padding
= ['\001'] + ['\000'] * (padLen
- 1)
222 self
.update(''.join(padding
))
224 # Mangling = blank rounds
225 for i
in xrange(numberOfBlankIterations
):
226 self
.S
= R(self
.S
,self
.wordlength
)
229 # Store state in digest.
231 for i
in xrange((length
)/self
.wordlength
/2):
232 self
.S
= R(self
.S
,self
.wordlength
)
234 digest
+= number2string_N((self
.S
["A"][1]),self
.wordlength
)[::-1] + number2string_N((self
.S
["A"][2]),self
.wordlength
)[::-1]
240 return digest
[:length
/8]
243 def hexdigest(self
,length
=256):
244 """Terminate and return digest in HEX form.
246 length = output length of the digest in bits
247 any multiple of 8 with a minimum of 8
250 Like digest() except the digest is returned as a string of
251 length 'length', containing only hexadecimal digits. This may be
252 used to exchange the value safely in email or other non-
255 Calling hexdigest() doesn't change the internal state. Adding data via
256 update() can still continu after asking for an intermediate digest
260 return ''.join(['%02x' % ord(c
) for c
in self
.digest(length
)])
263 """Return a clone object.
265 Return a copy ('clone') of the radiogatun object. This can be used
266 to efficiently compute the digests of strings that share
267 a common initial substring.
271 return copy
.deepcopy(self
)
273 # ======================================================================
274 # TOP LEVEL INTERFACE
275 # ======================================================================
277 def new(arg
=None,wl
=64,):
278 """Return a new RadioGatun hash object
280 wl = wordlength (in bits) of the RadioGatun hash method
281 between 1 and 64 (default = 64)
282 arg = if present, the method call update(arg) is made
284 EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
286 >>> import pyradiogatun
290 >>> hasher = pyradiogatun.new()
291 >>> hasher.update('1234567890123456')
292 >>> hasher.hexdigest()
293 'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
295 >>> hasher = pyradiogatun.new()
296 >>> hasher.update('Santa Barbara, California')
297 >>> hasher.hexdigest(480)
298 '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f74adb0c0a666adeb1f2d20b1f2489e3d973dae4efc1f2cc5aaa13f2b'
302 >>> hasher = pyradiogatun.new(wl=32)
303 >>> hasher.update('1234567890123456')
304 >>> hasher.hexdigest()
305 '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
307 >>> hasher = pyradiogatun.new(wl=32)
308 >>> hasher.update('Santa Barbara, California')
309 >>> hasher.hexdigest(512)
310 '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54a162949f4022531dbb6f66b64c3579df49f0f3af5951df9d68af310f2703b06d'
314 >>> hasher = pyradiogatun.new(wl=16)
315 >>> hasher.update('Santa Barbara, California')
316 >>> hasher.hexdigest()
317 'ab2203a8c3de943309b685513a29060339c001acce5900dcd6427a02c1fb8011'
321 >>> hasher = pyradiogatun.new(wl=8)
322 >>> hasher.update('Santa Barbara, California')
323 >>> hasher.hexdigest()
324 'e08f5cdbbfd8f5f3c479464a60ac186963e741d28f654e2c961d2f9bebc7de31'
327 crypto
= RadioGatunType(wl
)
333 # ======================================================================
335 # ======================================================================
337 def rotateRight(x
, amountToShift
, totalBits
):
338 """Rotate x (consisting of 'totalBits' bits) n bits to right.
340 x = integer input to be rotated
341 amountToShift = the amount of bits that should be shifted
342 totalBits = total amount bits at the input for rotation
345 n_mod
= ((amountToShift
% totalBits
) + totalBits
) % totalBits
346 return ((x
>> n_mod
) |
((x
<< (totalBits
-n_mod
)))&((2**totalBits
)-1))
348 def string2number(i
):
349 """ Convert a string to a number
351 Input: string (big-endian)
352 Output: long or integer
354 return int(i
.encode('hex'),16)
356 def number2string_N(i
, N
):
357 """Convert a number to a string of fixed size
361 Output: string (big-endian)
363 s
= '%0*x' % (N
*2, i
)
364 return s
.decode('hex')
366 # ======================================================================
368 # ======================================================================
374 if __name__
== "__main__":
375 print "DOCTEST running... no messages = all good"