1 | """ |
---|
2 | A pure python (slow) implementation of rijndael with a decent interface |
---|
3 | |
---|
4 | To include - |
---|
5 | |
---|
6 | from rijndael import rijndael |
---|
7 | |
---|
8 | To do a key setup - |
---|
9 | |
---|
10 | r = rijndael(key, block_size = 16) |
---|
11 | |
---|
12 | key must be a string of length 16, 24, or 32 |
---|
13 | blocksize must be 16, 24, or 32. Default is 16 |
---|
14 | |
---|
15 | To use - |
---|
16 | |
---|
17 | ciphertext = r.encrypt(plaintext) |
---|
18 | plaintext = r.decrypt(ciphertext) |
---|
19 | |
---|
20 | If any strings are of the wrong length a ValueError is thrown |
---|
21 | """ |
---|
22 | |
---|
23 | # ported from the Java reference code by Bram Cohen, April 2001 |
---|
24 | # this code is public domain, unless someone makes |
---|
25 | # an intellectual property claim against the reference |
---|
26 | # code, in which case it can be made public domain by |
---|
27 | # deleting all the comments and renaming all the variables |
---|
28 | |
---|
29 | import copy |
---|
30 | import string |
---|
31 | |
---|
32 | shifts = [[[0, 0], [1, 3], [2, 2], [3, 1]], |
---|
33 | [[0, 0], [1, 5], [2, 4], [3, 3]], |
---|
34 | [[0, 0], [1, 7], [3, 5], [4, 4]]] |
---|
35 | |
---|
36 | # [keysize][block_size] |
---|
37 | num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32: {16: 14, 24: 14, 32: 14}} |
---|
38 | |
---|
39 | A = [[1, 1, 1, 1, 1, 0, 0, 0], |
---|
40 | [0, 1, 1, 1, 1, 1, 0, 0], |
---|
41 | [0, 0, 1, 1, 1, 1, 1, 0], |
---|
42 | [0, 0, 0, 1, 1, 1, 1, 1], |
---|
43 | [1, 0, 0, 0, 1, 1, 1, 1], |
---|
44 | [1, 1, 0, 0, 0, 1, 1, 1], |
---|
45 | [1, 1, 1, 0, 0, 0, 1, 1], |
---|
46 | [1, 1, 1, 1, 0, 0, 0, 1]] |
---|
47 | |
---|
48 | # produce log and alog tables, needed for multiplying in the |
---|
49 | # field GF(2^m) (generator = 3) |
---|
50 | alog = [1] |
---|
51 | for i in range(255): |
---|
52 | j = (alog[-1] << 1) ^ alog[-1] |
---|
53 | if j & 0x100 != 0: |
---|
54 | j ^= 0x11B |
---|
55 | alog.append(j) |
---|
56 | |
---|
57 | log = [0] * 256 |
---|
58 | for i in range(1, 255): |
---|
59 | log[alog[i]] = i |
---|
60 | |
---|
61 | # multiply two elements of GF(2^m) |
---|
62 | def mul(a, b): |
---|
63 | if a == 0 or b == 0: |
---|
64 | return 0 |
---|
65 | return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255] |
---|
66 | |
---|
67 | # substitution box based on F^{-1}(x) |
---|
68 | box = [[0] * 8 for i in range(256)] |
---|
69 | box[1][7] = 1 |
---|
70 | for i in range(2, 256): |
---|
71 | j = alog[255 - log[i]] |
---|
72 | for t in range(8): |
---|
73 | box[i][t] = (j >> (7 - t)) & 0x01 |
---|
74 | |
---|
75 | B = [0, 1, 1, 0, 0, 0, 1, 1] |
---|
76 | |
---|
77 | # affine transform: box[i] <- B + A*box[i] |
---|
78 | cox = [[0] * 8 for i in range(256)] |
---|
79 | for i in range(256): |
---|
80 | for t in range(8): |
---|
81 | cox[i][t] = B[t] |
---|
82 | for j in range(8): |
---|
83 | cox[i][t] ^= A[t][j] * box[i][j] |
---|
84 | |
---|
85 | # S-boxes and inverse S-boxes |
---|
86 | S = [0] * 256 |
---|
87 | Si = [0] * 256 |
---|
88 | for i in range(256): |
---|
89 | S[i] = cox[i][0] << 7 |
---|
90 | for t in range(1, 8): |
---|
91 | S[i] ^= cox[i][t] << (7 - t) |
---|
92 | Si[S[i] & 0xFF] = i |
---|
93 | |
---|
94 | # T-boxes |
---|
95 | G = [[2, 1, 1, 3], |
---|
96 | [3, 2, 1, 1], |
---|
97 | [1, 3, 2, 1], |
---|
98 | [1, 1, 3, 2]] |
---|
99 | |
---|
100 | AA = [[0] * 8 for i in range(4)] |
---|
101 | |
---|
102 | for i in range(4): |
---|
103 | for j in range(4): |
---|
104 | AA[i][j] = G[i][j] |
---|
105 | AA[i][i + 4] = 1 |
---|
106 | |
---|
107 | for i in range(4): |
---|
108 | pivot = AA[i][i] |
---|
109 | if pivot == 0: |
---|
110 | t = i + 1 |
---|
111 | while AA[t][i] == 0 and t < 4: |
---|
112 | t += 1 |
---|
113 | assert t != 4, 'G matrix must be invertible' |
---|
114 | for j in range(8): |
---|
115 | AA[i][j], AA[t][j] = AA[t][j], AA[i][j] |
---|
116 | pivot = AA[i][i] |
---|
117 | for j in range(8): |
---|
118 | if AA[i][j] != 0: |
---|
119 | AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255] |
---|
120 | for t in range(4): |
---|
121 | if i != t: |
---|
122 | for j in range(i + 1, 8): |
---|
123 | AA[t][j] ^= mul(AA[i][j], AA[t][i]) |
---|
124 | AA[t][i] = 0 |
---|
125 | |
---|
126 | iG = [[0] * 4 for i in range(4)] |
---|
127 | |
---|
128 | for i in range(4): |
---|
129 | for j in range(4): |
---|
130 | iG[i][j] = AA[i][j + 4] |
---|
131 | |
---|
132 | def mul4(a, bs): |
---|
133 | if a == 0: |
---|
134 | return 0 |
---|
135 | r = 0 |
---|
136 | for b in bs: |
---|
137 | r <<= 8 |
---|
138 | if b != 0: |
---|
139 | r = r | mul(a, b) |
---|
140 | return r |
---|
141 | |
---|
142 | T1 = [] |
---|
143 | T2 = [] |
---|
144 | T3 = [] |
---|
145 | T4 = [] |
---|
146 | T5 = [] |
---|
147 | T6 = [] |
---|
148 | T7 = [] |
---|
149 | T8 = [] |
---|
150 | U1 = [] |
---|
151 | U2 = [] |
---|
152 | U3 = [] |
---|
153 | U4 = [] |
---|
154 | |
---|
155 | for t in range(256): |
---|
156 | s = S[t] |
---|
157 | T1.append(mul4(s, G[0])) |
---|
158 | T2.append(mul4(s, G[1])) |
---|
159 | T3.append(mul4(s, G[2])) |
---|
160 | T4.append(mul4(s, G[3])) |
---|
161 | |
---|
162 | s = Si[t] |
---|
163 | T5.append(mul4(s, iG[0])) |
---|
164 | T6.append(mul4(s, iG[1])) |
---|
165 | T7.append(mul4(s, iG[2])) |
---|
166 | T8.append(mul4(s, iG[3])) |
---|
167 | |
---|
168 | U1.append(mul4(t, iG[0])) |
---|
169 | U2.append(mul4(t, iG[1])) |
---|
170 | U3.append(mul4(t, iG[2])) |
---|
171 | U4.append(mul4(t, iG[3])) |
---|
172 | |
---|
173 | # round constants |
---|
174 | rcon = [1] |
---|
175 | r = 1 |
---|
176 | for t in range(1, 30): |
---|
177 | r = mul(2, r) |
---|
178 | rcon.append(r) |
---|
179 | |
---|
180 | del A |
---|
181 | del AA |
---|
182 | del pivot |
---|
183 | del B |
---|
184 | del G |
---|
185 | del box |
---|
186 | del log |
---|
187 | del alog |
---|
188 | del i |
---|
189 | del j |
---|
190 | del r |
---|
191 | del s |
---|
192 | del t |
---|
193 | del mul |
---|
194 | del mul4 |
---|
195 | del cox |
---|
196 | del iG |
---|
197 | |
---|
198 | class rijndael: |
---|
199 | |
---|
200 | def __init__(self, key, block_size=16): |
---|
201 | if block_size != 16 and block_size != 24 and block_size != 32: |
---|
202 | raise ValueError('Invalid block size: ' + str(block_size)) |
---|
203 | if len(key) != 16 and len(key) != 24 and len(key) != 32: |
---|
204 | raise ValueError('Invalid key size: ' + str(len(key))) |
---|
205 | self.block_size = block_size |
---|
206 | |
---|
207 | ROUNDS = num_rounds[len(key)][block_size] |
---|
208 | BC = block_size // 4 |
---|
209 | # encryption round keys |
---|
210 | Ke = [[0] * BC for i in range(ROUNDS + 1)] |
---|
211 | # decryption round keys |
---|
212 | Kd = [[0] * BC for i in range(ROUNDS + 1)] |
---|
213 | ROUND_KEY_COUNT = (ROUNDS + 1) * BC |
---|
214 | KC = len(key) // 4 |
---|
215 | |
---|
216 | # copy user material bytes into temporary ints |
---|
217 | tk = [] |
---|
218 | for i in range(0, KC): |
---|
219 | tk.append((key[i * 4] << 24) | (key[i * 4 + 1] << 16) | |
---|
220 | (key[i * 4 + 2] << 8) | key[i * 4 + 3]) |
---|
221 | |
---|
222 | # copy values into round key arrays |
---|
223 | t = 0 |
---|
224 | j = 0 |
---|
225 | while j < KC and t < ROUND_KEY_COUNT: |
---|
226 | Ke[t // BC][t % BC] = tk[j] |
---|
227 | Kd[ROUNDS - (t // BC)][t % BC] = tk[j] |
---|
228 | j += 1 |
---|
229 | t += 1 |
---|
230 | tt = 0 |
---|
231 | rconpointer = 0 |
---|
232 | while t < ROUND_KEY_COUNT: |
---|
233 | # extrapolate using phi (the round key evolution function) |
---|
234 | tt = tk[KC - 1] |
---|
235 | tk[0] ^= (S[(tt >> 16) & 0xFF] & 0xFF) << 24 ^ \ |
---|
236 | (S[(tt >> 8) & 0xFF] & 0xFF) << 16 ^ \ |
---|
237 | (S[ tt & 0xFF] & 0xFF) << 8 ^ \ |
---|
238 | (S[(tt >> 24) & 0xFF] & 0xFF) ^ \ |
---|
239 | (rcon[rconpointer] & 0xFF) << 24 |
---|
240 | rconpointer += 1 |
---|
241 | if KC != 8: |
---|
242 | for i in range(1, KC): |
---|
243 | tk[i] ^= tk[i - 1] |
---|
244 | else: |
---|
245 | for i in range(1, KC // 2): |
---|
246 | tk[i] ^= tk[i - 1] |
---|
247 | tt = tk[KC // 2 - 1] |
---|
248 | tk[KC // 2] ^= (S[ tt & 0xFF] & 0xFF) ^ \ |
---|
249 | (S[(tt >> 8) & 0xFF] & 0xFF) << 8 ^ \ |
---|
250 | (S[(tt >> 16) & 0xFF] & 0xFF) << 16 ^ \ |
---|
251 | (S[(tt >> 24) & 0xFF] & 0xFF) << 24 |
---|
252 | for i in range(KC // 2 + 1, KC): |
---|
253 | tk[i] ^= tk[i - 1] |
---|
254 | # copy values into round key arrays |
---|
255 | j = 0 |
---|
256 | while j < KC and t < ROUND_KEY_COUNT: |
---|
257 | Ke[t // BC][t % BC] = tk[j] |
---|
258 | Kd[ROUNDS - (t // BC)][t % BC] = tk[j] |
---|
259 | j += 1 |
---|
260 | t += 1 |
---|
261 | # inverse MixColumn where needed |
---|
262 | for r in range(1, ROUNDS): |
---|
263 | for j in range(BC): |
---|
264 | tt = Kd[r][j] |
---|
265 | Kd[r][j] = U1[(tt >> 24) & 0xFF] ^ \ |
---|
266 | U2[(tt >> 16) & 0xFF] ^ \ |
---|
267 | U3[(tt >> 8) & 0xFF] ^ \ |
---|
268 | U4[tt & 0xFF] |
---|
269 | self.Ke = Ke |
---|
270 | self.Kd = Kd |
---|
271 | |
---|
272 | def encrypt(self, plaintext): |
---|
273 | if len(plaintext) != self.block_size: |
---|
274 | raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(plaintext))) |
---|
275 | Ke = self.Ke |
---|
276 | |
---|
277 | BC = self.block_size // 4 |
---|
278 | ROUNDS = len(Ke) - 1 |
---|
279 | if BC == 4: |
---|
280 | SC = 0 |
---|
281 | elif BC == 6: |
---|
282 | SC = 1 |
---|
283 | else: |
---|
284 | SC = 2 |
---|
285 | s1 = shifts[SC][1][0] |
---|
286 | s2 = shifts[SC][2][0] |
---|
287 | s3 = shifts[SC][3][0] |
---|
288 | a = [0] * BC |
---|
289 | # temporary work array |
---|
290 | t = [] |
---|
291 | # plaintext to ints + key |
---|
292 | for i in range(BC): |
---|
293 | t.append((ord(plaintext[i * 4]) << 24 | |
---|
294 | ord(plaintext[i * 4 + 1]) << 16 | |
---|
295 | ord(plaintext[i * 4 + 2]) << 8 | |
---|
296 | ord(plaintext[i * 4 + 3])) ^ Ke[0][i]) |
---|
297 | # apply round transforms |
---|
298 | for r in range(1, ROUNDS): |
---|
299 | for i in range(BC): |
---|
300 | a[i] = (T1[(t[i] >> 24) & 0xFF] ^ |
---|
301 | T2[(t[(i + s1) % BC] >> 16) & 0xFF] ^ |
---|
302 | T3[(t[(i + s2) % BC] >> 8) & 0xFF] ^ |
---|
303 | T4[t[(i + s3) % BC] & 0xFF]) ^ Ke[r][i] |
---|
304 | t = copy.copy(a) |
---|
305 | # last round is special |
---|
306 | result = [] |
---|
307 | for i in range(BC): |
---|
308 | tt = Ke[ROUNDS][i] |
---|
309 | result.append((S[(t[i] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF) |
---|
310 | result.append((S[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF) |
---|
311 | result.append((S[(t[(i + s2) % BC] >> 8) & 0xFF] ^ (tt >> 8)) & 0xFF) |
---|
312 | result.append((S[t[(i + s3) % BC] & 0xFF] ^ tt) & 0xFF) |
---|
313 | return ''.join(map(chr, result)) |
---|
314 | |
---|
315 | def decrypt(self, ciphertext): |
---|
316 | if len(ciphertext) != self.block_size: |
---|
317 | raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(ciphertext))) |
---|
318 | Kd = self.Kd |
---|
319 | |
---|
320 | BC = self.block_size // 4 |
---|
321 | ROUNDS = len(Kd) - 1 |
---|
322 | if BC == 4: |
---|
323 | SC = 0 |
---|
324 | elif BC == 6: |
---|
325 | SC = 1 |
---|
326 | else: |
---|
327 | SC = 2 |
---|
328 | s1 = shifts[SC][1][1] |
---|
329 | s2 = shifts[SC][2][1] |
---|
330 | s3 = shifts[SC][3][1] |
---|
331 | a = [0] * BC |
---|
332 | # temporary work array |
---|
333 | t = [0] * BC |
---|
334 | # ciphertext to ints + key |
---|
335 | for i in range(BC): |
---|
336 | t[i] = (ciphertext[i * 4] << 24 | |
---|
337 | ciphertext[i * 4 + 1] << 16 | |
---|
338 | ciphertext[i * 4 + 2] << 8 | |
---|
339 | ciphertext[i * 4 + 3]) ^ Kd[0][i] |
---|
340 | # apply round transforms |
---|
341 | for r in range(1, ROUNDS): |
---|
342 | for i in range(BC): |
---|
343 | a[i] = (T5[(t[i] >> 24) & 0xFF] ^ |
---|
344 | T6[(t[(i + s1) % BC] >> 16) & 0xFF] ^ |
---|
345 | T7[(t[(i + s2) % BC] >> 8) & 0xFF] ^ |
---|
346 | T8[t[(i + s3) % BC] & 0xFF]) ^ Kd[r][i] |
---|
347 | t = copy.copy(a) |
---|
348 | # last round is special |
---|
349 | result = [] |
---|
350 | for i in range(BC): |
---|
351 | tt = Kd[ROUNDS][i] |
---|
352 | result.append((Si[(t[i] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF) |
---|
353 | result.append((Si[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF) |
---|
354 | result.append((Si[(t[(i + s2) % BC] >> 8) & 0xFF] ^ (tt >> 8)) & 0xFF) |
---|
355 | result.append((Si[t[(i + s3) % BC] & 0xFF] ^ tt) & 0xFF) |
---|
356 | return ''.join(map(chr, result)) |
---|
357 | |
---|
358 | def encrypt(key, block): |
---|
359 | return rijndael(key, len(block)).encrypt(block) |
---|
360 | |
---|
361 | def decrypt(key, block): |
---|
362 | return rijndael(key, len(block)).decrypt(block) |
---|