gozerbot.contrib.rijndael

Source Code for Module gozerbot.contrib.rijndael

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 xrange(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 xrange(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 xrange(256)] 69 box[1][7] = 1 70 for i in xrange(2, 256): 71 j = alog[255 - log[i]] 72 for t in xrange(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 xrange(256)] 79 for i in xrange(256): 80 for t in xrange(8): 81 cox[i][t] = B[t] 82 for j in xrange(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 xrange(256): 89 S[i] = cox[i][0] << 7 90 for t in xrange(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 xrange(4)] 101 102 for i in xrange(4): 103 for j in xrange(4): 104 AA[i][j] = G[i][j] 105 AA[i][i+4] = 1 106 107 for i in xrange(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 xrange(8): 115 AA[i][j], AA[t][j] = AA[t][j], AA[i][j] 116 pivot = AA[i][i] 117 for j in xrange(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 xrange(4): 121 if i != t: 122 for j in xrange(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 xrange(4)] 127 128 for i in xrange(4): 129 for j in xrange(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 xrange(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 xrange(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 - def __init__(self, key, block_size = 16):

200 if block_size != 16 and block_size != 24 and block_size != 32: 201 raise ValueError('Invalid block size: ' + str(block_size)) 202 if len(key) != 16 and len(key) != 24 and len(key) != 32: 203 raise ValueError('Invalid key size: ' + str(len(key))) 204 self.block_size = block_size 205 206 ROUNDS = num_rounds[len(key)][block_size] 207 BC = block_size / 4 208 # encryption round keys 209 Ke = [[0] * BC for i in xrange(ROUNDS + 1)] 210 # decryption round keys 211 Kd = [[0] * BC for i in xrange(ROUNDS + 1)] 212 ROUND_KEY_COUNT = (ROUNDS + 1) * BC 213 KC = len(key) / 4 214 215 # copy user material bytes into temporary ints 216 tk = [] 217 for i in xrange(0, KC): 218 tk.append((ord(key[i * 4]) << 24) | (ord(key[i * 4 + 1]) << 16) | 219 (ord(key[i * 4 + 2]) << 8) | ord(key[i * 4 + 3])) 220 221 # copy values into round key arrays 222 t = 0 223 j = 0 224 while j < KC and t < ROUND_KEY_COUNT: 225 Ke[t / BC][t % BC] = tk[j] 226 Kd[ROUNDS - (t / BC)][t % BC] = tk[j] 227 j += 1 228 t += 1 229 tt = 0 230 rconpointer = 0 231 while t < ROUND_KEY_COUNT: 232 # extrapolate using phi (the round key evolution function) 233 tt = tk[KC - 1] 234 tk[0] ^= (S[(tt >> 16) & 0xFF] & 0xFF) << 24 ^ \ 235 (S[(tt >> 8) & 0xFF] & 0xFF) << 16 ^ \ 236 (S[ tt & 0xFF] & 0xFF) << 8 ^ \ 237 (S[(tt >> 24) & 0xFF] & 0xFF) ^ \ 238 (rcon[rconpointer] & 0xFF) << 24 239 rconpointer += 1 240 if KC != 8: 241 for i in xrange(1, KC): 242 tk[i] ^= tk[i-1] 243 else: 244 for i in xrange(1, KC / 2): 245 tk[i] ^= tk[i-1] 246 tt = tk[KC / 2 - 1] 247 tk[KC / 2] ^= (S[ tt & 0xFF] & 0xFF) ^ \ 248 (S[(tt >> 8) & 0xFF] & 0xFF) << 8 ^ \ 249 (S[(tt >> 16) & 0xFF] & 0xFF) << 16 ^ \ 250 (S[(tt >> 24) & 0xFF] & 0xFF) << 24 251 for i in xrange(KC / 2 + 1, KC): 252 tk[i] ^= tk[i-1] 253 # copy values into round key arrays 254 j = 0 255 while j < KC and t < ROUND_KEY_COUNT: 256 Ke[t / BC][t % BC] = tk[j] 257 Kd[ROUNDS - (t / BC)][t % BC] = tk[j] 258 j += 1 259 t += 1 260 # inverse MixColumn where needed 261 for r in xrange(1, ROUNDS): 262 for j in xrange(BC): 263 tt = Kd[r][j] 264 Kd[r][j] = U1[(tt >> 24) & 0xFF] ^ \ 265 U2[(tt >> 16) & 0xFF] ^ \ 266 U3[(tt >> 8) & 0xFF] ^ \ 267 U4[ tt & 0xFF] 268 self.Ke = Ke 269 self.Kd = Kd

270

271 - def encrypt(self, plaintext):

272 if len(plaintext) != self.block_size: 273 raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(plaintext))) 274 Ke = self.Ke 275 276 BC = self.block_size / 4 277 ROUNDS = len(Ke) - 1 278 if BC == 4: 279 SC = 0 280 elif BC == 6: 281 SC = 1 282 else: 283 SC = 2 284 s1 = shifts[SC][1][0] 285 s2 = shifts[SC][2][0] 286 s3 = shifts[SC][3][0] 287 a = [0] * BC 288 # temporary work array 289 t = [] 290 # plaintext to ints + key 291 for i in xrange(BC): 292 t.append((ord(plaintext[i * 4 ]) << 24 | 293 ord(plaintext[i * 4 + 1]) << 16 | 294 ord(plaintext[i * 4 + 2]) << 8 | 295 ord(plaintext[i * 4 + 3]) ) ^ Ke[0][i]) 296 # apply round transforms 297 for r in xrange(1, ROUNDS): 298 for i in xrange(BC): 299 a[i] = (T1[(t[ i ] >> 24) & 0xFF] ^ 300 T2[(t[(i + s1) % BC] >> 16) & 0xFF] ^ 301 T3[(t[(i + s2) % BC] >> 8) & 0xFF] ^ 302 T4[ t[(i + s3) % BC] & 0xFF] ) ^ Ke[r][i] 303 t = copy.copy(a) 304 # last round is special 305 result = [] 306 for i in xrange(BC): 307 tt = Ke[ROUNDS][i] 308 result.append((S[(t[ i ] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF) 309 result.append((S[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF) 310 result.append((S[(t[(i + s2) % BC] >> 8) & 0xFF] ^ (tt >> 8)) & 0xFF) 311 result.append((S[ t[(i + s3) % BC] & 0xFF] ^ tt ) & 0xFF) 312 return string.join(map(chr, result), '')

313