[irc/quakenet/qwebirc.git] / qwebirc / util / rijndael.py

"""
A pure python (slow) implementation of rijndael with a decent interface

To include -

from rijndael import rijndael

To do a key setup -

r = rijndael(key, block_size = 16)

key must be a string of length 16, 24, or 32
blocksize must be 16, 24, or 32. Default is 16

To use -

ciphertext = r.encrypt(plaintext)
plaintext = r.decrypt(ciphertext)

If any strings are of the wrong length a ValueError is thrown
"""

# ported from the Java reference code by Bram Cohen, April 2001
# this code is public domain, unless someone makes 
# an intellectual property claim against the reference 
# code, in which case it can be made public domain by 
# deleting all the comments and renaming all the variables

import copy
import string

shifts = [[[0, 0], [1, 3], [2, 2], [3, 1]],
          [[0, 0], [1, 5], [2, 4], [3, 3]],
          [[0, 0], [1, 7], [3, 5], [4, 4]]]

# [keysize][block_size]
num_rounds = {16: {16: 10, 24: 12, 32: 14}, 24: {16: 12, 24: 12, 32: 14}, 32: {16: 14, 24: 14, 32: 14}}

A = [[1, 1, 1, 1, 1, 0, 0, 0],
     [0, 1, 1, 1, 1, 1, 0, 0],
     [0, 0, 1, 1, 1, 1, 1, 0],
     [0, 0, 0, 1, 1, 1, 1, 1],
     [1, 0, 0, 0, 1, 1, 1, 1],
     [1, 1, 0, 0, 0, 1, 1, 1],
     [1, 1, 1, 0, 0, 0, 1, 1],
     [1, 1, 1, 1, 0, 0, 0, 1]]

# produce log and alog tables, needed for multiplying in the
# field GF(2^m) (generator = 3)
alog = [1]
for i in xrange(255):
    j = (alog[-1] << 1) ^ alog[-1]
    if j & 0x100 != 0:
        j ^= 0x11B
    alog.append(j)

log = [0] * 256
for i in xrange(1, 255):
    log[alog[i]] = i

# multiply two elements of GF(2^m)
def mul(a, b):
    if a == 0 or b == 0:
        return 0
    return alog[(log[a & 0xFF] + log[b & 0xFF]) % 255]

# substitution box based on F^{-1}(x)
box = [[0] * 8 for i in xrange(256)]
box[1][7] = 1
for i in xrange(2, 256):
    j = alog[255 - log[i]]
    for t in xrange(8):
        box[i][t] = (j >> (7 - t)) & 0x01

B = [0, 1, 1, 0, 0, 0, 1, 1]

# affine transform:  box[i] <- B + A*box[i]
cox = [[0] * 8 for i in xrange(256)]
for i in xrange(256):
    for t in xrange(8):
        cox[i][t] = B[t]
        for j in xrange(8):
            cox[i][t] ^= A[t][j] * box[i][j]

# S-boxes and inverse S-boxes
S =  [0] * 256
Si = [0] * 256
for i in xrange(256):
    S[i] = cox[i][0] << 7
    for t in xrange(1, 8):
        S[i] ^= cox[i][t] << (7-t)
    Si[S[i] & 0xFF] = i

# T-boxes
G = [[2, 1, 1, 3],
    [3, 2, 1, 1],
    [1, 3, 2, 1],
    [1, 1, 3, 2]]

AA = [[0] * 8 for i in xrange(4)]

for i in xrange(4):
    for j in xrange(4):
        AA[i][j] = G[i][j]
        AA[i][i+4] = 1

for i in xrange(4):
    pivot = AA[i][i]
    if pivot == 0:
        t = i + 1
        while AA[t][i] == 0 and t < 4:
            t += 1
            assert t != 4, 'G matrix must be invertible'
            for j in xrange(8):
                AA[i][j], AA[t][j] = AA[t][j], AA[i][j]
            pivot = AA[i][i]
    for j in xrange(8):
        if AA[i][j] != 0:
            AA[i][j] = alog[(255 + log[AA[i][j] & 0xFF] - log[pivot & 0xFF]) % 255]
    for t in xrange(4):
        if i != t:
            for j in xrange(i+1, 8):
                AA[t][j] ^= mul(AA[i][j], AA[t][i])
            AA[t][i] = 0

iG = [[0] * 4 for i in xrange(4)]

for i in xrange(4):
    for j in xrange(4):
        iG[i][j] = AA[i][j + 4]

def mul4(a, bs):
    if a == 0:
        return 0
    r = 0
    for b in bs:
        r <<= 8
        if b != 0:
            r = r | mul(a, b)
    return r

T1 = []
T2 = []
T3 = []
T4 = []
T5 = []
T6 = []
T7 = []
T8 = []
U1 = []
U2 = []
U3 = []
U4 = []

for t in xrange(256):
    s = S[t]
    T1.append(mul4(s, G[0]))
    T2.append(mul4(s, G[1]))
    T3.append(mul4(s, G[2]))
    T4.append(mul4(s, G[3]))

    s = Si[t]
    T5.append(mul4(s, iG[0]))
    T6.append(mul4(s, iG[1]))
    T7.append(mul4(s, iG[2]))
    T8.append(mul4(s, iG[3]))

    U1.append(mul4(t, iG[0]))
    U2.append(mul4(t, iG[1]))
    U3.append(mul4(t, iG[2]))
    U4.append(mul4(t, iG[3]))

# round constants
rcon = [1]
r = 1
for t in xrange(1, 30):
    r = mul(2, r)
    rcon.append(r)

del A
del AA
del pivot
del B
del G
del box
del log
del alog
del i
del j
del r
del s
del t
del mul
del mul4
del cox
del iG

class rijndael:
    def __init__(self, key, block_size = 16):
        if block_size != 16 and block_size != 24 and block_size != 32:
            raise ValueError('Invalid block size: ' + str(block_size))
        if len(key) != 16 and len(key) != 24 and len(key) != 32:
            raise ValueError('Invalid key size: ' + str(len(key)))
        self.block_size = block_size

        ROUNDS = num_rounds[len(key)][block_size]
        BC = block_size / 4
        # encryption round keys
        Ke = [[0] * BC for i in xrange(ROUNDS + 1)]
        # decryption round keys
        Kd = [[0] * BC for i in xrange(ROUNDS + 1)]
        ROUND_KEY_COUNT = (ROUNDS + 1) * BC
        KC = len(key) / 4

        # copy user material bytes into temporary ints
        tk = []
        for i in xrange(0, KC):
            tk.append((ord(key[i * 4]) << 24) | (ord(key[i * 4 + 1]) << 16) |
                (ord(key[i * 4 + 2]) << 8) | ord(key[i * 4 + 3]))

        # copy values into round key arrays
        t = 0
        j = 0
        while j < KC and t < ROUND_KEY_COUNT:
            Ke[t / BC][t % BC] = tk[j]
            Kd[ROUNDS - (t / BC)][t % BC] = tk[j]
            j += 1
            t += 1
        tt = 0
        rconpointer = 0
        while t < ROUND_KEY_COUNT:
            # extrapolate using phi (the round key evolution function)
            tt = tk[KC - 1]
            tk[0] ^= (S[(tt >> 16) & 0xFF] & 0xFF) << 24 ^  \
                     (S[(tt >>  8) & 0xFF] & 0xFF) << 16 ^  \
                     (S[ tt        & 0xFF] & 0xFF) <<  8 ^  \
                     (S[(tt >> 24) & 0xFF] & 0xFF)       ^  \
                     (rcon[rconpointer]    & 0xFF) << 24
            rconpointer += 1
            if KC != 8:
                for i in xrange(1, KC):
                    tk[i] ^= tk[i-1]
            else:
                for i in xrange(1, KC / 2):
                    tk[i] ^= tk[i-1]
                tt = tk[KC / 2 - 1]
                tk[KC / 2] ^= (S[ tt        & 0xFF] & 0xFF)       ^ \
                              (S[(tt >>  8) & 0xFF] & 0xFF) <<  8 ^ \
                              (S[(tt >> 16) & 0xFF] & 0xFF) << 16 ^ \
                              (S[(tt >> 24) & 0xFF] & 0xFF) << 24
                for i in xrange(KC / 2 + 1, KC):
                    tk[i] ^= tk[i-1]
            # copy values into round key arrays
            j = 0
            while j < KC and t < ROUND_KEY_COUNT:
                Ke[t / BC][t % BC] = tk[j]
                Kd[ROUNDS - (t / BC)][t % BC] = tk[j]
                j += 1
                t += 1
        # inverse MixColumn where needed
        for r in xrange(1, ROUNDS):
            for j in xrange(BC):
                tt = Kd[r][j]
                Kd[r][j] = U1[(tt >> 24) & 0xFF] ^ \
                           U2[(tt >> 16) & 0xFF] ^ \
                           U3[(tt >>  8) & 0xFF] ^ \
                           U4[ tt        & 0xFF]
        self.Ke = Ke
        self.Kd = Kd

    def encrypt(self, plaintext):
        if len(plaintext) != self.block_size:
            raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(plaintext)))
        Ke = self.Ke

        BC = self.block_size / 4
        ROUNDS = len(Ke) - 1
        if BC == 4:
            SC = 0
        elif BC == 6:
            SC = 1
        else:
            SC = 2
        s1 = shifts[SC][1][0]
        s2 = shifts[SC][2][0]
        s3 = shifts[SC][3][0]
        a = [0] * BC
        # temporary work array
        t = []
        # plaintext to ints + key
        for i in xrange(BC):
            t.append((ord(plaintext[i * 4    ]) << 24 |
                      ord(plaintext[i * 4 + 1]) << 16 |
                      ord(plaintext[i * 4 + 2]) <<  8 |
                      ord(plaintext[i * 4 + 3])        ) ^ Ke[0][i])
        # apply round transforms
        for r in xrange(1, ROUNDS):
            for i in xrange(BC):
                a[i] = (T1[(t[ i           ] >> 24) & 0xFF] ^
                        T2[(t[(i + s1) % BC] >> 16) & 0xFF] ^
                        T3[(t[(i + s2) % BC] >>  8) & 0xFF] ^
                        T4[ t[(i + s3) % BC]        & 0xFF]  ) ^ Ke[r][i]
            t = copy.copy(a)
        # last round is special
        result = []
        for i in xrange(BC):
            tt = Ke[ROUNDS][i]
            result.append((S[(t[ i           ] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF)
            result.append((S[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF)
            result.append((S[(t[(i + s2) % BC] >>  8) & 0xFF] ^ (tt >>  8)) & 0xFF)
            result.append((S[ t[(i + s3) % BC]        & 0xFF] ^  tt       ) & 0xFF)
        return string.join(map(chr, result), '')

    def decrypt(self, ciphertext):
        if len(ciphertext) != self.block_size:
            raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(ciphertext)))
        Kd = self.Kd

        BC = self.block_size / 4
        ROUNDS = len(Kd) - 1
        if BC == 4:
            SC = 0
        elif BC == 6:
            SC = 1
        else:
            SC = 2
        s1 = shifts[SC][1][1]
        s2 = shifts[SC][2][1]
        s3 = shifts[SC][3][1]
        a = [0] * BC
        # temporary work array
        t = [0] * BC
        # ciphertext to ints + key
        for i in xrange(BC):
            t[i] = (ord(ciphertext[i * 4    ]) << 24 |
                    ord(ciphertext[i * 4 + 1]) << 16 |
                    ord(ciphertext[i * 4 + 2]) <<  8 |
                    ord(ciphertext[i * 4 + 3])        ) ^ Kd[0][i]
        # apply round transforms
        for r in xrange(1, ROUNDS):
            for i in xrange(BC):
                a[i] = (T5[(t[ i           ] >> 24) & 0xFF] ^
                        T6[(t[(i + s1) % BC] >> 16) & 0xFF] ^
                        T7[(t[(i + s2) % BC] >>  8) & 0xFF] ^
                        T8[ t[(i + s3) % BC]        & 0xFF]  ) ^ Kd[r][i]
            t = copy.copy(a)
        # last round is special
        result = []
        for i in xrange(BC):
            tt = Kd[ROUNDS][i]
            result.append((Si[(t[ i           ] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF)
            result.append((Si[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF)
            result.append((Si[(t[(i + s2) % BC] >>  8) & 0xFF] ^ (tt >>  8)) & 0xFF)
            result.append((Si[ t[(i + s3) % BC]        & 0xFF] ^  tt       ) & 0xFF)
        return string.join(map(chr, result), '')

def encrypt(key, block):
    return rijndael(key, len(block)).encrypt(block)

def decrypt(key, block):
    return rijndael(key, len(block)).decrypt(block)

def test():
    def t(kl, bl):
        b = 'b' * bl
        r = rijndael('a' * kl, bl)
        assert r.decrypt(r.encrypt(b)) == b
    t(16, 16)
    t(16, 24)
    t(16, 32)
    t(24, 16)
    t(24, 24)
    t(24, 32)
    t(32, 16)
    t(32, 24)
    t(32, 32)
Commit	Line	Data
ace37679 CP	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
314	def decrypt(self, ciphertext):
315	if len(ciphertext) != self.block_size:
316	raise ValueError('wrong block length, expected ' + str(self.block_size) + ' got ' + str(len(ciphertext)))
317	Kd = self.Kd
318
319	BC = self.block_size / 4
320	ROUNDS = len(Kd) - 1
321	if BC == 4:
322	SC = 0
323	elif BC == 6:
324	SC = 1
325	else:
326	SC = 2
327	s1 = shifts[SC][1][1]
328	s2 = shifts[SC][2][1]
329	s3 = shifts[SC][3][1]
330	a = [0] * BC
331	# temporary work array
332	t = [0] * BC
333	# ciphertext to ints + key
334	for i in xrange(BC):
335	t[i] = (ord(ciphertext[i * 4 ]) << 24 \|
336	ord(ciphertext[i * 4 + 1]) << 16 \|
337	ord(ciphertext[i * 4 + 2]) << 8 \|
338	ord(ciphertext[i * 4 + 3]) ) ^ Kd[0][i]
339	# apply round transforms
340	for r in xrange(1, ROUNDS):
341	for i in xrange(BC):
342	a[i] = (T5[(t[ i ] >> 24) & 0xFF] ^
343	T6[(t[(i + s1) % BC] >> 16) & 0xFF] ^
344	T7[(t[(i + s2) % BC] >> 8) & 0xFF] ^
345	T8[ t[(i + s3) % BC] & 0xFF] ) ^ Kd[r][i]
346	t = copy.copy(a)
347	# last round is special
348	result = []
349	for i in xrange(BC):
350	tt = Kd[ROUNDS][i]
351	result.append((Si[(t[ i ] >> 24) & 0xFF] ^ (tt >> 24)) & 0xFF)
352	result.append((Si[(t[(i + s1) % BC] >> 16) & 0xFF] ^ (tt >> 16)) & 0xFF)
353	result.append((Si[(t[(i + s2) % BC] >> 8) & 0xFF] ^ (tt >> 8)) & 0xFF)
354	result.append((Si[ t[(i + s3) % BC] & 0xFF] ^ tt ) & 0xFF)
355	return string.join(map(chr, result), '')
356
357	def encrypt(key, block):
358	return rijndael(key, len(block)).encrypt(block)
359
360	def decrypt(key, block):
361	return rijndael(key, len(block)).decrypt(block)
362
363	def test():
364	def t(kl, bl):
365	b = 'b' * bl
366	r = rijndael('a' * kl, bl)
367	assert r.decrypt(r.encrypt(b)) == b
368	t(16, 16)
369	t(16, 24)
370	t(16, 32)
371	t(24, 16)
372	t(24, 24)
373	t(24, 32)
374	t(32, 16)
375	t(32, 24)
376	t(32, 32)