· 5 years ago · Nov 30, 2020, 10:16 PM
1"""Simple AES cipher implementation in pure Python following PEP-272 API
2
3Homepage: https://bitbucket.org/intgr/pyaes/
4
5The goal of this module is to be as fast as reasonable in Python while still
6being Pythonic and readable/understandable. It is licensed under the permissive
7MIT license.
8
9Hopefully the code is readable and commented enough that it can serve as an
10introduction to the AES cipher for Python coders. In fact, it should go along
11well with the Stick Figure Guide to AES:
12http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html
13
14Contrary to intuition, this implementation numbers the 4x4 matrices from top to
15bottom for efficiency reasons::
16
17 0 4 8 12
18 1 5 9 13
19 2 6 10 14
20 3 7 11 15
21
22Effectively it's the transposition of what you'd expect. This actually makes
23the code simpler -- except the ShiftRows step, but hopefully the explanation
24there clears it up.
25
26"""
27
28####
29# Copyright (c) 2010 Marti Raudsepp <marti@juffo.org>
30#
31# Permission is hereby granted, free of charge, to any person obtaining a copy
32# of this software and associated documentation files (the "Software"), to deal
33# in the Software without restriction, including without limitation the rights
34# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
35# copies of the Software, and to permit persons to whom the Software is
36# furnished to do so, subject to the following conditions:
37#
38# The above copyright notice and this permission notice shall be included in
39# all copies or substantial portions of the Software.
40#
41# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
42# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
43# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
44# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
45# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
46# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
47# THE SOFTWARE.
48####
49
50
51from array import array
52
53# Globals mandated by PEP 272:
54# http://www.python.org/dev/peps/pep-0272/
55MODE_ECB = 1
56MODE_CBC = 2
57#MODE_CTR = 6
58
59block_size = 16
60key_size = None
61
62def new(key, mode, IV=None):
63 if mode == MODE_ECB:
64 return ECBMode(AES(key))
65 elif mode == MODE_CBC:
66 if IV is None:
67 raise ValueError, "CBC mode needs an IV value!"
68
69 return CBCMode(AES(key), IV)
70 else:
71 raise NotImplementedError
72
73#### AES cipher implementation
74
75class AES(object):
76 block_size = 16
77
78 def __init__(self, key):
79 self.setkey(key)
80
81 def setkey(self, key):
82 """Sets the key and performs key expansion."""
83
84 self.key = key
85 self.key_size = len(key)
86
87 if self.key_size == 16:
88 self.rounds = 10
89 elif self.key_size == 24:
90 self.rounds = 12
91 elif self.key_size == 32:
92 self.rounds = 14
93 else:
94 raise ValueError, "Key length must be 16, 24 or 32 bytes"
95
96 self.expand_key()
97
98 def expand_key(self):
99 """Performs AES key expansion on self.key and stores in self.exkey"""
100
101 # The key schedule specifies how parts of the key are fed into the
102 # cipher's round functions. "Key expansion" means performing this
103 # schedule in advance. Almost all implementations do this.
104 #
105 # Here's a description of AES key schedule:
106 # http://en.wikipedia.org/wiki/Rijndael_key_schedule
107
108 # The expanded key starts with the actual key itself
109 exkey = array('B', self.key)
110
111 # extra key expansion steps
112 if self.key_size == 16:
113 extra_cnt = 0
114 elif self.key_size == 24:
115 extra_cnt = 2
116 else:
117 extra_cnt = 3
118
119 # 4-byte temporary variable for key expansion
120 word = exkey[-4:]
121 # Each expansion cycle uses 'i' once for Rcon table lookup
122 for i in xrange(1, 11):
123
124 #### key schedule core:
125 # left-rotate by 1 byte
126 word = word[1:4] + word[0:1]
127
128 # apply S-box to all bytes
129 for j in xrange(4):
130 word[j] = aes_sbox[word[j]]
131
132 # apply the Rcon table to the leftmost byte
133 word[0] = word[0] ^ aes_Rcon[i]
134 #### end key schedule core
135
136 for z in xrange(4):
137 for j in xrange(4):
138 # mix in bytes from the last subkey
139 word[j] ^= exkey[-self.key_size + j]
140 exkey.extend(word)
141
142 # Last key expansion cycle always finishes here
143 if len(exkey) >= (self.rounds+1) * self.block_size:
144 break
145
146 # Special substitution step for 256-bit key
147 if self.key_size == 32:
148 for j in xrange(4):
149 # mix in bytes from the last subkey XORed with S-box of
150 # current word bytes
151 word[j] = aes_sbox[word[j]] ^ exkey[-self.key_size + j]
152 exkey.extend(word)
153
154 # Twice for 192-bit key, thrice for 256-bit key
155 for z in xrange(extra_cnt):
156 for j in xrange(4):
157 # mix in bytes from the last subkey
158 word[j] ^= exkey[-self.key_size + j]
159 exkey.extend(word)
160
161 self.exkey = exkey
162
163 def add_round_key(self, block, round):
164 """AddRoundKey step in AES. This is where the key is mixed into plaintext"""
165
166 offset = round * 16
167 exkey = self.exkey
168
169 for i in xrange(16):
170 block[i] ^= exkey[offset + i]
171
172 #print 'AddRoundKey:', block
173
174 def sub_bytes(self, block, sbox):
175 """SubBytes step, apply S-box to all bytes
176
177 Depending on whether encrypting or decrypting, a different sbox array
178 is passed in.
179 """
180
181 for i in xrange(16):
182 block[i] = sbox[block[i]]
183
184 #print 'SubBytes :', block
185
186 def shift_rows(self, b):
187 """ShiftRows step. Shifts 2nd row to left by 1, 3rd row by 2, 4th row by 3
188
189 Since we're performing this on a transposed matrix, cells are numbered
190 from top to bottom::
191
192 0 4 8 12 -> 0 4 8 12 -- 1st row doesn't change
193 1 5 9 13 -> 5 9 13 1 -- row shifted to left by 1 (wraps around)
194 2 6 10 14 -> 10 14 2 6 -- shifted by 2
195 3 7 11 15 -> 15 3 7 11 -- shifted by 3
196 """
197
198 b[1], b[5], b[ 9], b[13] = b[ 5], b[ 9], b[13], b[ 1]
199 b[2], b[6], b[10], b[14] = b[10], b[14], b[ 2], b[ 6]
200 b[3], b[7], b[11], b[15] = b[15], b[ 3], b[ 7], b[11]
201
202 #print 'ShiftRows :', b
203
204 def shift_rows_inv(self, b):
205 """Similar to shift_rows above, but performed in inverse for decryption."""
206
207 b[ 5], b[ 9], b[13], b[ 1] = b[1], b[5], b[ 9], b[13]
208 b[10], b[14], b[ 2], b[ 6] = b[2], b[6], b[10], b[14]
209 b[15], b[ 3], b[ 7], b[11] = b[3], b[7], b[11], b[15]
210
211 #print 'ShiftRows :', b
212
213 def mix_columns(self, block):
214 """MixColumns step. Mixes the values in each column"""
215
216 # Cache global multiplication tables (see below)
217 mul_by_2 = gf_mul_by_2
218 mul_by_3 = gf_mul_by_3
219
220 # Since we're dealing with a transposed matrix, columns are already
221 # sequential
222 for i in xrange(4):
223 col = i * 4
224
225 #v0, v1, v2, v3 = block[col : col+4]
226 v0, v1, v2, v3 = (block[col], block[col + 1], block[col + 2],
227 block[col + 3])
228
229 block[col ] = mul_by_2[v0] ^ v3 ^ v2 ^ mul_by_3[v1]
230 block[col+1] = mul_by_2[v1] ^ v0 ^ v3 ^ mul_by_3[v2]
231 block[col+2] = mul_by_2[v2] ^ v1 ^ v0 ^ mul_by_3[v3]
232 block[col+3] = mul_by_2[v3] ^ v2 ^ v1 ^ mul_by_3[v0]
233
234 #print 'MixColumns :', block
235
236 def mix_columns_inv(self, block):
237 """Similar to mix_columns above, but performed in inverse for decryption."""
238
239 # Cache global multiplication tables (see below)
240 mul_9 = gf_mul_by_9
241 mul_11 = gf_mul_by_11
242 mul_13 = gf_mul_by_13
243 mul_14 = gf_mul_by_14
244
245 # Since we're dealing with a transposed matrix, columns are already
246 # sequential
247 for i in xrange(4):
248 col = i * 4
249
250 v0, v1, v2, v3 = (block[col], block[col + 1], block[col + 2],
251 block[col + 3])
252 #v0, v1, v2, v3 = block[col:col+4]
253
254 block[col ] = mul_14[v0] ^ mul_9[v3] ^ mul_13[v2] ^ mul_11[v1]
255 block[col+1] = mul_14[v1] ^ mul_9[v0] ^ mul_13[v3] ^ mul_11[v2]
256 block[col+2] = mul_14[v2] ^ mul_9[v1] ^ mul_13[v0] ^ mul_11[v3]
257 block[col+3] = mul_14[v3] ^ mul_9[v2] ^ mul_13[v1] ^ mul_11[v0]
258
259 #print 'MixColumns :', block
260
261 def encrypt_block(self, block):
262 """Encrypts a single block. This is the main AES function"""
263
264 # For efficiency reasons, the state between steps is transmitted via a
265 # mutable array, not returned.
266 self.add_round_key(block, 0)
267
268 for round in xrange(1, self.rounds):
269 self.sub_bytes(block, aes_sbox)
270 self.shift_rows(block)
271 self.mix_columns(block)
272 self.add_round_key(block, round)
273
274 self.sub_bytes(block, aes_sbox)
275 self.shift_rows(block)
276 # no mix_columns step in the last round
277 self.add_round_key(block, self.rounds)
278
279 def decrypt_block(self, block):
280 """Decrypts a single block. This is the main AES decryption function"""
281
282 # For efficiency reasons, the state between steps is transmitted via a
283 # mutable array, not returned.
284 self.add_round_key(block, self.rounds)
285
286 # count rounds down from 15 ... 1
287 for round in xrange(self.rounds-1, 0, -1):
288 self.shift_rows_inv(block)
289 self.sub_bytes(block, aes_inv_sbox)
290 self.add_round_key(block, round)
291 self.mix_columns_inv(block)
292
293 self.shift_rows_inv(block)
294 self.sub_bytes(block, aes_inv_sbox)
295 self.add_round_key(block, 0)
296 # no mix_columns step in the last round
297
298
299#### ECB mode implementation
300
301class ECBMode(object):
302 """Electronic CodeBook (ECB) mode encryption.
303
304 Basically this mode applies the cipher function to each block individually;
305 no feedback is done. NB! This is insecure for almost all purposes
306 """
307
308 def __init__(self, cipher):
309 self.cipher = cipher
310 self.block_size = cipher.block_size
311
312 def ecb(self, data, block_func):
313 """Perform ECB mode with the given function"""
314
315 if len(data) % self.block_size != 0:
316 raise ValueError, "Plaintext length must be multiple of 16"
317
318 block_size = self.block_size
319 data = array('B', data)
320
321 for offset in xrange(0, len(data), block_size):
322 block = data[offset : offset+block_size]
323 block_func(block)
324 data[offset : offset+block_size] = block
325
326 return data.tostring()
327
328 def encrypt(self, data):
329 """Encrypt data in ECB mode"""
330
331 return self.ecb(data, self.cipher.encrypt_block)
332
333 def decrypt(self, data):
334 """Decrypt data in ECB mode"""
335
336 return self.ecb(data, self.cipher.decrypt_block)
337
338#### CBC mode
339
340class CBCMode(object):
341 """Cipher Block Chaining (CBC) mode encryption. This mode avoids content leaks.
342
343 In CBC encryption, each plaintext block is XORed with the ciphertext block
344 preceding it; decryption is simply the inverse.
345 """
346
347 # A better explanation of CBC can be found here:
348 # http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Cipher-block_chaining_.28CBC.29
349
350 def __init__(self, cipher, IV):
351 self.cipher = cipher
352 self.block_size = cipher.block_size
353 self.IV = array('B', IV)
354
355 def encrypt(self, data):
356 """Encrypt data in CBC mode"""
357
358 block_size = self.block_size
359 if len(data) % block_size != 0:
360 raise ValueError, "Plaintext length must be multiple of 16"
361
362 data = array('B', data)
363 IV = self.IV
364
365 for offset in xrange(0, len(data), block_size):
366 block = data[offset : offset+block_size]
367
368 # Perform CBC chaining
369 for i in xrange(block_size):
370 block[i] ^= IV[i]
371
372 self.cipher.encrypt_block(block)
373 data[offset : offset+block_size] = block
374 IV = block
375
376 self.IV = IV
377 return data.tostring()
378
379 def decrypt(self, data):
380 """Decrypt data in CBC mode"""
381
382 block_size = self.block_size
383 if len(data) % block_size != 0:
384 raise ValueError, "Ciphertext length must be multiple of 16"
385
386 data = array('B', data)
387 IV = self.IV
388
389 for offset in xrange(0, len(data), block_size):
390 ctext = data[offset : offset+block_size]
391 block = ctext[:]
392 self.cipher.decrypt_block(block)
393
394 # Perform CBC chaining
395 #for i in xrange(block_size):
396 # data[offset + i] ^= IV[i]
397 for i in xrange(block_size):
398 block[i] ^= IV[i]
399 data[offset : offset+block_size] = block
400
401 IV = ctext
402 #data[offset : offset+block_size] = block
403
404 self.IV = IV
405 return data.tostring()
406
407####
408
409def galois_multiply(a, b):
410 """Galois Field multiplicaiton for AES"""
411 p = 0
412 while b:
413 if b & 1:
414 p ^= a
415 a <<= 1
416 if a & 0x100:
417 a ^= 0x1b
418 b >>= 1
419
420 return p & 0xff
421
422# Precompute the multiplication tables for encryption
423gf_mul_by_2 = array('B', [galois_multiply(x, 2) for x in range(256)])
424gf_mul_by_3 = array('B', [galois_multiply(x, 3) for x in range(256)])
425# ... for decryption
426gf_mul_by_9 = array('B', [galois_multiply(x, 9) for x in range(256)])
427gf_mul_by_11 = array('B', [galois_multiply(x, 11) for x in range(256)])
428gf_mul_by_13 = array('B', [galois_multiply(x, 13) for x in range(256)])
429gf_mul_by_14 = array('B', [galois_multiply(x, 14) for x in range(256)])
430
431####
432
433# The S-box is a 256-element array, that maps a single byte value to another
434# byte value. Since it's designed to be reversible, each value occurs only once
435# in the S-box
436#
437# More information: http://en.wikipedia.org/wiki/Rijndael_S-box
438
439aes_sbox = array('B',
440 '637c777bf26b6fc53001672bfed7ab76'
441 'ca82c97dfa5947f0add4a2af9ca472c0'
442 'b7fd9326363ff7cc34a5e5f171d83115'
443 '04c723c31896059a071280e2eb27b275'
444 '09832c1a1b6e5aa0523bd6b329e32f84'
445 '53d100ed20fcb15b6acbbe394a4c58cf'
446 'd0efaafb434d338545f9027f503c9fa8'
447 '51a3408f929d38f5bcb6da2110fff3d2'
448 'cd0c13ec5f974417c4a77e3d645d1973'
449 '60814fdc222a908846eeb814de5e0bdb'
450 'e0323a0a4906245cc2d3ac629195e479'
451 'e7c8376d8dd54ea96c56f4ea657aae08'
452 'ba78252e1ca6b4c6e8dd741f4bbd8b8a'
453 '703eb5664803f60e613557b986c11d9e'
454 'e1f8981169d98e949b1e87e9ce5528df'
455 '8ca1890dbfe6426841992d0fb054bb16'.decode('hex')
456)
457
458# This is the inverse of the above. In other words:
459# aes_inv_sbox[aes_sbox[val]] == val
460
461aes_inv_sbox = array('B',
462 '52096ad53036a538bf40a39e81f3d7fb'
463 '7ce339829b2fff87348e4344c4dee9cb'
464 '547b9432a6c2233dee4c950b42fac34e'
465 '082ea16628d924b2765ba2496d8bd125'
466 '72f8f66486689816d4a45ccc5d65b692'
467 '6c704850fdedb9da5e154657a78d9d84'
468 '90d8ab008cbcd30af7e45805b8b34506'
469 'd02c1e8fca3f0f02c1afbd0301138a6b'
470 '3a9111414f67dcea97f2cfcef0b4e673'
471 '96ac7422e7ad3585e2f937e81c75df6e'
472 '47f11a711d29c5896fb7620eaa18be1b'
473 'fc563e4bc6d279209adbc0fe78cd5af4'
474 '1fdda8338807c731b11210592780ec5f'
475 '60517fa919b54a0d2de57a9f93c99cef'
476 'a0e03b4dae2af5b0c8ebbb3c83539961'
477 '172b047eba77d626e169146355210c7d'.decode('hex')
478)
479
480# The Rcon table is used in AES's key schedule (key expansion)
481# It's a pre-computed table of exponentation of 2 in AES's finite field
482#
483# More information: http://en.wikipedia.org/wiki/Rijndael_key_schedule
484
485aes_Rcon = array('B',
486 '8d01020408102040801b366cd8ab4d9a'
487 '2f5ebc63c697356ad4b37dfaefc59139'
488 '72e4d3bd61c29f254a943366cc831d3a'
489 '74e8cb8d01020408102040801b366cd8'
490 'ab4d9a2f5ebc63c697356ad4b37dfaef'
491 'c5913972e4d3bd61c29f254a943366cc'
492 '831d3a74e8cb8d01020408102040801b'
493 '366cd8ab4d9a2f5ebc63c697356ad4b3'
494 '7dfaefc5913972e4d3bd61c29f254a94'
495 '3366cc831d3a74e8cb8d010204081020'
496 '40801b366cd8ab4d9a2f5ebc63c69735'
497 '6ad4b37dfaefc5913972e4d3bd61c29f'
498 '254a943366cc831d3a74e8cb8d010204'
499 '08102040801b366cd8ab4d9a2f5ebc63'
500 'c697356ad4b37dfaefc5913972e4d3bd'
501 '61c29f254a943366cc831d3a74e8cb'.decode('hex')
502)