| 0,0 → 1,397 |
|---|
| ## twofish.py - pure Python implementation of the Twofish algorithm. |
| ## Bjorn Edstrom <be@bjrn.se> 13 december 2007. |
| ## |
| ## Copyrights |
| ## ========== |
| ## |
| ## This code is a derived from an implementation by Dr Brian Gladman |
| ## (gladman@seven77.demon.co.uk) which is subject to the following license. |
| ## This Python implementation is not subject to any other license. |
| ## |
| ##/* This is an independent implementation of the encryption algorithm: */ |
| ##/* */ |
| ##/* Twofish by Bruce Schneier and colleagues */ |
| ##/* */ |
| ##/* which is a candidate algorithm in the Advanced Encryption Standard */ |
| ##/* programme of the US National Institute of Standards and Technology. */ |
| ##/* */ |
| ##/* Copyright in this implementation is held by Dr B R Gladman but I */ |
| ##/* hereby give permission for its free direct or derivative use subject */ |
| ##/* to acknowledgment of its origin and compliance with any conditions */ |
| ##/* that the originators of t he algorithm place on its exploitation. */ |
| ##/* */ |
| ##/* My thanks to Doug Whiting and Niels Ferguson for comments that led */ |
| ##/* to improvements in this implementation. */ |
| ##/* */ |
| ##/* Dr Brian Gladman (gladman@seven77.demon.co.uk) 14th January 1999 */ |
| ## |
| ## The above copyright notice must not be removed. |
| ## |
| ## Information |
| ## =========== |
| ## |
| ## Anyone thinking of using this code should reconsider. It's slow. |
| ## Try python-mcrypt instead. In case a faster library is not installed |
| ## on the target system, this code can be used as a portable fallback. |
| |
| try: |
| import psyco |
| psyco.full() |
| except ImportError: |
| pass |
| |
| block_size = 16 |
| key_size = 32 |
| |
| class Twofish: |
| |
| def __init__(self, key=None): |
| """Twofish.""" |
| |
| if key: |
| self.set_key(key) |
| |
| |
| def set_key(self, key): |
| """Init.""" |
| |
| key_len = len(key) |
| if key_len not in [16, 24, 32]: |
| # XXX: add padding? |
| raise KeyError, "key must be 16, 24 or 32 bytes" |
| if key_len % 4: |
| # XXX: add padding? |
| raise KeyError, "key not a multiple of 4" |
| if key_len > 32: |
| # XXX: prune? |
| raise KeyError, "key_len > 32" |
| |
| self.context = TWI() |
| |
| key_word32 = [0] * 32 |
| i = 0 |
| while key: |
| key_word32[i] = struct.unpack("<L", key[0:4])[0] |
| key = key[4:] |
| i += 1 |
| |
| set_key(self.context, key_word32, key_len) |
| |
| |
| def decrypt(self, block): |
| """Decrypt blocks.""" |
| |
| if len(block) % 16: |
| raise ValueError, "block size must be a multiple of 16" |
| |
| plaintext = '' |
| |
| while block: |
| a, b, c, d = struct.unpack("<4L", block[:16]) |
| temp = [a, b, c, d] |
| decrypt(self.context, temp) |
| plaintext += struct.pack("<4L", *temp) |
| block = block[16:] |
| |
| return plaintext |
| |
| |
| def encrypt(self, block): |
| """Encrypt blocks.""" |
| |
| if len(block) % 16: |
| raise ValueError, "block size must be a multiple of 16" |
| |
| ciphertext = '' |
| |
| while block: |
| a, b, c, d = struct.unpack("<4L", block[0:16]) |
| temp = [a, b, c, d] |
| encrypt(self.context, temp) |
| ciphertext += struct.pack("<4L", *temp) |
| block = block[16:] |
| |
| return ciphertext |
| |
| |
| def get_name(self): |
| """Return the name of the cipher.""" |
| |
| return "Twofish" |
| |
| |
| def get_block_size(self): |
| """Get cipher block size in bytes.""" |
| |
| return 16 |
| |
| |
| def get_key_size(self): |
| """Get cipher key size in bytes.""" |
| |
| return 32 |
| |
| |
| # |
| # Private. |
| # |
| |
| import struct |
| import sys |
| |
| WORD_BIGENDIAN = 0 |
| if sys.byteorder == 'big': |
| WORD_BIGENDIAN = 1 |
| |
| def rotr32(x, n): |
| return (x >> n) | ((x << (32 - n)) & 0xFFFFFFFF) |
| |
| def rotl32(x, n): |
| return ((x << n) & 0xFFFFFFFF) | (x >> (32 - n)) |
| |
| def byteswap32(x): |
| return ((x & 0xff) << 24) | (((x >> 8) & 0xff) << 16) | \ |
| (((x >> 16) & 0xff) << 8) | ((x >> 24) & 0xff) |
| |
| class TWI: |
| def __init__(self): |
| self.k_len = 0 # word32 |
| self.l_key = [0]*40 # word32 |
| self.s_key = [0]*4 # word32 |
| self.qt_gen = 0 # word32 |
| self.q_tab = [[0]*256, [0]*256] # byte |
| self.mt_gen = 0 # word32 |
| self.m_tab = [[0]*256, [0]*256, [0]*256, [0]*256] # word32 |
| self.mk_tab = [[0]*256, [0]*256, [0]*256, [0]*256] # word32 |
| |
| def byte(x, n): |
| return (x >> (8 * n)) & 0xff |
| |
| tab_5b = [0, 90, 180, 238] |
| tab_ef = [0, 238, 180, 90] |
| ror4 = [0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15] |
| ashx = [0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12, 5, 14, 7] |
| qt0 = [[8, 1, 7, 13, 6, 15, 3, 2, 0, 11, 5, 9, 14, 12, 10, 4], |
| [2, 8, 11, 13, 15, 7, 6, 14, 3, 1, 9, 4, 0, 10, 12, 5]] |
| qt1 = [[14, 12, 11, 8, 1, 2, 3, 5, 15, 4, 10, 6, 7, 0, 9, 13], |
| [1, 14, 2, 11, 4, 12, 3, 7, 6, 13, 10, 5, 15, 9, 0, 8]] |
| qt2 = [[11, 10, 5, 14, 6, 13, 9, 0, 12, 8, 15, 3, 2, 4, 7, 1], |
| [4, 12, 7, 5, 1, 6, 9, 10, 0, 14, 13, 8, 2, 11, 3, 15]] |
| qt3 = [[13, 7, 15, 4, 1, 2, 6, 14, 9, 11, 3, 0, 8, 5, 12, 10], |
| [11, 9, 5, 1, 12, 3, 13, 14, 6, 4, 7, 15, 2, 0, 8, 10]] |
| |
| def qp(n, x): # word32, byte |
| n %= 0x100000000 |
| x %= 0x100 |
| a0 = x >> 4; |
| b0 = x & 15; |
| a1 = a0 ^ b0; |
| b1 = ror4[b0] ^ ashx[a0]; |
| a2 = qt0[n][a1]; |
| b2 = qt1[n][b1]; |
| a3 = a2 ^ b2; |
| b3 = ror4[b2] ^ ashx[a2]; |
| a4 = qt2[n][a3]; |
| b4 = qt3[n][b3]; |
| return (b4 << 4) | a4; |
| |
| def gen_qtab(pkey): |
| for i in xrange(256): |
| pkey.q_tab[0][i] = qp(0, i) |
| pkey.q_tab[1][i] = qp(1, i) |
| |
| def gen_mtab(pkey): |
| for i in xrange(256): |
| f01 = pkey.q_tab[1][i] |
| f01 = pkey.q_tab[1][i]; |
| f5b = ((f01) ^ ((f01) >> 2) ^ tab_5b[(f01) & 3]); |
| fef = ((f01) ^ ((f01) >> 1) ^ ((f01) >> 2) ^ tab_ef[(f01) & 3]); |
| pkey.m_tab[0][i] = f01 + (f5b << 8) + (fef << 16) + (fef << 24); |
| pkey.m_tab[2][i] = f5b + (fef << 8) + (f01 << 16) + (fef << 24); |
| |
| f01 = pkey.q_tab[0][i]; |
| f5b = ((f01) ^ ((f01) >> 2) ^ tab_5b[(f01) & 3]); |
| fef = ((f01) ^ ((f01) >> 1) ^ ((f01) >> 2) ^ tab_ef[(f01) & 3]); |
| pkey.m_tab[1][i] = fef + (fef << 8) + (f5b << 16) + (f01 << 24); |
| pkey.m_tab[3][i] = f5b + (f01 << 8) + (fef << 16) + (f5b << 24); |
| |
| def gen_mk_tab(pkey, key): |
| if pkey.k_len == 2: |
| for i in xrange(256): |
| by = i % 0x100 |
| pkey.mk_tab[0][i] = pkey.m_tab[0][pkey.q_tab[0][pkey.q_tab[0][by] ^ byte(key[1],0)] ^ byte(key[0],0)]; |
| pkey.mk_tab[1][i] = pkey.m_tab[1][pkey.q_tab[0][pkey.q_tab[1][by] ^ byte(key[1],1)] ^ byte(key[0],1)]; |
| pkey.mk_tab[2][i] = pkey.m_tab[2][pkey.q_tab[1][pkey.q_tab[0][by] ^ byte(key[1],2)] ^ byte(key[0],2)]; |
| pkey.mk_tab[3][i] = pkey.m_tab[3][pkey.q_tab[1][pkey.q_tab[1][by] ^ byte(key[1],3)] ^ byte(key[0],3)]; |
| if pkey.k_len == 3: |
| for i in xrange(256): |
| by = i % 0x100 |
| pkey.mk_tab[0][i] = pkey.m_tab[0][pkey.q_tab[0][pkey.q_tab[0][pkey.q_tab[1][by] ^ byte(key[2], 0)] ^ byte(key[1], 0)] ^ byte(key[0], 0)]; |
| pkey.mk_tab[1][i] = pkey.m_tab[1][pkey.q_tab[0][pkey.q_tab[1][pkey.q_tab[1][by] ^ byte(key[2], 1)] ^ byte(key[1], 1)] ^ byte(key[0], 1)]; |
| pkey.mk_tab[2][i] = pkey.m_tab[2][pkey.q_tab[1][pkey.q_tab[0][pkey.q_tab[0][by] ^ byte(key[2], 2)] ^ byte(key[1], 2)] ^ byte(key[0], 2)]; |
| pkey.mk_tab[3][i] = pkey.m_tab[3][pkey.q_tab[1][pkey.q_tab[1][pkey.q_tab[0][by] ^ byte(key[2], 3)] ^ byte(key[1], 3)] ^ byte(key[0], 3)]; |
| if pkey.k_len == 4: |
| for i in xrange(256): |
| by = i % 0x100 |
| pkey.mk_tab[0][i] = pkey.m_tab[0][pkey.q_tab[0][pkey.q_tab[0][pkey.q_tab[1][pkey.q_tab[1][by] ^ byte(key[3], 0)] ^ byte(key[2], 0)] ^ byte(key[1], 0)] ^ byte(key[0], 0)]; |
| pkey.mk_tab[1][i] = pkey.m_tab[1][pkey.q_tab[0][pkey.q_tab[1][pkey.q_tab[1][pkey.q_tab[0][by] ^ byte(key[3], 1)] ^ byte(key[2], 1)] ^ byte(key[1], 1)] ^ byte(key[0], 1)]; |
| pkey.mk_tab[2][i] = pkey.m_tab[2][pkey.q_tab[1][pkey.q_tab[0][pkey.q_tab[0][pkey.q_tab[0][by] ^ byte(key[3], 2)] ^ byte(key[2], 2)] ^ byte(key[1], 2)] ^ byte(key[0], 2)]; |
| pkey.mk_tab[3][i] = pkey.m_tab[3][pkey.q_tab[1][pkey.q_tab[1][pkey.q_tab[0][pkey.q_tab[1][by] ^ byte(key[3], 3)] ^ byte(key[2], 3)] ^ byte(key[1], 3)] ^ byte(key[0], 3)]; |
| |
| def h_fun(pkey, x, key): |
| b0 = byte(x, 0); |
| b1 = byte(x, 1); |
| b2 = byte(x, 2); |
| b3 = byte(x, 3); |
| if pkey.k_len >= 4: |
| b0 = pkey.q_tab[1][b0] ^ byte(key[3], 0); |
| b1 = pkey.q_tab[0][b1] ^ byte(key[3], 1); |
| b2 = pkey.q_tab[0][b2] ^ byte(key[3], 2); |
| b3 = pkey.q_tab[1][b3] ^ byte(key[3], 3); |
| if pkey.k_len >= 3: |
| b0 = pkey.q_tab[1][b0] ^ byte(key[2], 0); |
| b1 = pkey.q_tab[1][b1] ^ byte(key[2], 1); |
| b2 = pkey.q_tab[0][b2] ^ byte(key[2], 2); |
| b3 = pkey.q_tab[0][b3] ^ byte(key[2], 3); |
| if pkey.k_len >= 2: |
| b0 = pkey.q_tab[0][pkey.q_tab[0][b0] ^ byte(key[1], 0)] ^ byte(key[0], 0); |
| b1 = pkey.q_tab[0][pkey.q_tab[1][b1] ^ byte(key[1], 1)] ^ byte(key[0], 1); |
| b2 = pkey.q_tab[1][pkey.q_tab[0][b2] ^ byte(key[1], 2)] ^ byte(key[0], 2); |
| b3 = pkey.q_tab[1][pkey.q_tab[1][b3] ^ byte(key[1], 3)] ^ byte(key[0], 3); |
| return pkey.m_tab[0][b0] ^ pkey.m_tab[1][b1] ^ pkey.m_tab[2][b2] ^ pkey.m_tab[3][b3]; |
| |
| def mds_rem(p0, p1): |
| i, t, u = 0, 0, 0 |
| for i in xrange(8): |
| t = p1 >> 24 |
| p1 = ((p1 << 8) & 0xffffffff) | (p0 >> 24) |
| p0 = (p0 << 8) & 0xffffffff |
| u = (t << 1) & 0xffffffff |
| if t & 0x80: |
| u ^= 0x0000014d |
| p1 ^= t ^ ((u << 16) & 0xffffffff) |
| u ^= (t >> 1) |
| if t & 0x01: |
| u ^= 0x0000014d >> 1 |
| p1 ^= ((u << 24) & 0xffffffff) | ((u << 8) & 0xffffffff) |
| return p1 |
| |
| def set_key(pkey, in_key, key_len): |
| pkey.qt_gen = 0 |
| if not pkey.qt_gen: |
| gen_qtab(pkey) |
| pkey.qt_gen = 1 |
| pkey.mt_gen = 0 |
| if not pkey.mt_gen: |
| gen_mtab(pkey) |
| pkey.mt_gen = 1 |
| pkey.k_len = (key_len * 8) / 64 |
| |
| a = 0 |
| b = 0 |
| me_key = [0,0,0,0] |
| mo_key = [0,0,0,0] |
| for i in xrange(pkey.k_len): |
| if WORD_BIGENDIAN: |
| a = byteswap32(in_key[i + 1]) |
| me_key[i] = a |
| b = byteswap32(in_key[i + i + 1]) |
| else: |
| a = in_key[i + i] |
| me_key[i] = a |
| b = in_key[i + i + 1] |
| mo_key[i] = b |
| pkey.s_key[pkey.k_len - i - 1] = mds_rem(a, b); |
| for i in xrange(0, 40, 2): |
| a = (0x01010101 * i) % 0x100000000; |
| b = (a + 0x01010101) % 0x100000000; |
| a = h_fun(pkey, a, me_key); |
| b = rotl32(h_fun(pkey, b, mo_key), 8); |
| pkey.l_key[i] = (a + b) % 0x100000000; |
| pkey.l_key[i + 1] = rotl32((a + 2 * b) % 0x100000000, 9); |
| gen_mk_tab(pkey, pkey.s_key) |
| |
| def encrypt(pkey, in_blk): |
| blk = [0, 0, 0, 0] |
| |
| if WORD_BIGENDIAN: |
| blk[0] = byteswap32(in_blk[0]) ^ pkey.l_key[0]; |
| blk[1] = byteswap32(in_blk[1]) ^ pkey.l_key[1]; |
| blk[2] = byteswap32(in_blk[2]) ^ pkey.l_key[2]; |
| blk[3] = byteswap32(in_blk[3]) ^ pkey.l_key[3]; |
| else: |
| blk[0] = in_blk[0] ^ pkey.l_key[0]; |
| blk[1] = in_blk[1] ^ pkey.l_key[1]; |
| blk[2] = in_blk[2] ^ pkey.l_key[2]; |
| blk[3] = in_blk[3] ^ pkey.l_key[3]; |
| |
| for i in xrange(8): |
| t1 = ( pkey.mk_tab[0][byte(blk[1],3)] ^ pkey.mk_tab[1][byte(blk[1],0)] ^ pkey.mk_tab[2][byte(blk[1],1)] ^ pkey.mk_tab[3][byte(blk[1],2)] ); |
| t0 = ( pkey.mk_tab[0][byte(blk[0],0)] ^ pkey.mk_tab[1][byte(blk[0],1)] ^ pkey.mk_tab[2][byte(blk[0],2)] ^ pkey.mk_tab[3][byte(blk[0],3)] ); |
| |
| blk[2] = rotr32(blk[2] ^ ((t0 + t1 + pkey.l_key[4 * (i) + 8]) % 0x100000000), 1); |
| blk[3] = rotl32(blk[3], 1) ^ ((t0 + 2 * t1 + pkey.l_key[4 * (i) + 9]) % 0x100000000); |
| |
| t1 = ( pkey.mk_tab[0][byte(blk[3],3)] ^ pkey.mk_tab[1][byte(blk[3],0)] ^ pkey.mk_tab[2][byte(blk[3],1)] ^ pkey.mk_tab[3][byte(blk[3],2)] ); |
| t0 = ( pkey.mk_tab[0][byte(blk[2],0)] ^ pkey.mk_tab[1][byte(blk[2],1)] ^ pkey.mk_tab[2][byte(blk[2],2)] ^ pkey.mk_tab[3][byte(blk[2],3)] ); |
| |
| blk[0] = rotr32(blk[0] ^ ((t0 + t1 + pkey.l_key[4 * (i) + 10]) % 0x100000000), 1); |
| blk[1] = rotl32(blk[1], 1) ^ ((t0 + 2 * t1 + pkey.l_key[4 * (i) + 11]) % 0x100000000); |
| |
| if WORD_BIGENDIAN: |
| in_blk[0] = byteswap32(blk[2] ^ pkey.l_key[4]); |
| in_blk[1] = byteswap32(blk[3] ^ pkey.l_key[5]); |
| in_blk[2] = byteswap32(blk[0] ^ pkey.l_key[6]); |
| in_blk[3] = byteswap32(blk[1] ^ pkey.l_key[7]); |
| else: |
| in_blk[0] = blk[2] ^ pkey.l_key[4]; |
| in_blk[1] = blk[3] ^ pkey.l_key[5]; |
| in_blk[2] = blk[0] ^ pkey.l_key[6]; |
| in_blk[3] = blk[1] ^ pkey.l_key[7]; |
| |
| return |
| |
| def decrypt(pkey, in_blk): |
| blk = [0, 0, 0, 0] |
| |
| if WORD_BIGENDIAN: |
| blk[0] = byteswap32(in_blk[0]) ^ pkey.l_key[4]; |
| blk[1] = byteswap32(in_blk[1]) ^ pkey.l_key[5]; |
| blk[2] = byteswap32(in_blk[2]) ^ pkey.l_key[6]; |
| blk[3] = byteswap32(in_blk[3]) ^ pkey.l_key[7]; |
| else: |
| blk[0] = in_blk[0] ^ pkey.l_key[4]; |
| blk[1] = in_blk[1] ^ pkey.l_key[5]; |
| blk[2] = in_blk[2] ^ pkey.l_key[6]; |
| blk[3] = in_blk[3] ^ pkey.l_key[7]; |
| |
| for i in xrange(7, -1, -1): |
| t1 = ( pkey.mk_tab[0][byte(blk[1],3)] ^ pkey.mk_tab[1][byte(blk[1],0)] ^ pkey.mk_tab[2][byte(blk[1],1)] ^ pkey.mk_tab[3][byte(blk[1],2)] ) |
| t0 = ( pkey.mk_tab[0][byte(blk[0],0)] ^ pkey.mk_tab[1][byte(blk[0],1)] ^ pkey.mk_tab[2][byte(blk[0],2)] ^ pkey.mk_tab[3][byte(blk[0],3)] ) |
| |
| blk[2] = rotl32(blk[2], 1) ^ ((t0 + t1 + pkey.l_key[4 * (i) + 10]) % 0x100000000) |
| blk[3] = rotr32(blk[3] ^ ((t0 + 2 * t1 + pkey.l_key[4 * (i) + 11]) % 0x100000000), 1) |
| |
| t1 = ( pkey.mk_tab[0][byte(blk[3],3)] ^ pkey.mk_tab[1][byte(blk[3],0)] ^ pkey.mk_tab[2][byte(blk[3],1)] ^ pkey.mk_tab[3][byte(blk[3],2)] ) |
| t0 = ( pkey.mk_tab[0][byte(blk[2],0)] ^ pkey.mk_tab[1][byte(blk[2],1)] ^ pkey.mk_tab[2][byte(blk[2],2)] ^ pkey.mk_tab[3][byte(blk[2],3)] ) |
| |
| blk[0] = rotl32(blk[0], 1) ^ ((t0 + t1 + pkey.l_key[4 * (i) + 8]) % 0x100000000) |
| blk[1] = rotr32(blk[1] ^ ((t0 + 2 * t1 + pkey.l_key[4 * (i) + 9]) % 0x100000000), 1) |
| |
| if WORD_BIGENDIAN: |
| in_blk[0] = byteswap32(blk[2] ^ pkey.l_key[0]); |
| in_blk[1] = byteswap32(blk[3] ^ pkey.l_key[1]); |
| in_blk[2] = byteswap32(blk[0] ^ pkey.l_key[2]); |
| in_blk[3] = byteswap32(blk[1] ^ pkey.l_key[3]); |
| else: |
| in_blk[0] = blk[2] ^ pkey.l_key[0]; |
| in_blk[1] = blk[3] ^ pkey.l_key[1]; |
| in_blk[2] = blk[0] ^ pkey.l_key[2]; |
| in_blk[3] = blk[1] ^ pkey.l_key[3]; |
| return |
| |
| __testkey = '\xD4\x3B\xB7\x55\x6E\xA3\x2E\x46\xF2\xA2\x82\xB7\xD4\x5B\x4E\x0D\x57\xFF\x73\x9D\x4D\xC9\x2C\x1B\xD7\xFC\x01\x70\x0C\xC8\x21\x6F' |
| __testdat = '\x90\xAF\xE9\x1B\xB2\x88\x54\x4F\x2C\x32\xDC\x23\x9B\x26\x35\xE6' |
| assert 'l\xb4V\x1c@\xbf\n\x97\x05\x93\x1c\xb6\xd4\x08\xe7\xfa' == Twofish(__testkey).encrypt(__testdat) |
| assert __testdat == Twofish(__testkey).decrypt('l\xb4V\x1c@\xbf\n\x97\x05\x93\x1c\xb6\xd4\x08\xe7\xfa') |
| |