From fb7feac6332db515213b7a8a95cffba23a0bcf14 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Sat, 25 Apr 2015 16:41:24 +0200 Subject: About twice as fast matrix multiplication --- pypride.py | 85 ++++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 60 insertions(+), 25 deletions(-) (limited to 'pypride.py') diff --git a/pypride.py b/pypride.py index 91ffeef..ec69060 100644 --- a/pypride.py +++ b/pypride.py @@ -126,22 +126,57 @@ Sbox_inv = [Sbox.index(x) for x in xrange(16)] PBox = [0, 16, 32, 48, 1, 17, 33, 49, 2, 18, 34, 50, 3, 19, 35, 51, 4, 20, 36, 52, 5, 21, 37, 53, 6, 22, 38, 54, 7, 23, 39, 55, 8, 24, 40, 56, 9, 25, 41, 57, 10, 26, 42, 58, 11, 27, 43, 59, 12, 28, 44, 60, 13, 29, 45, 61, 14, 30, 46, 62, 15, 31, 47, 63] PBox_inv = [PBox.index(x) for x in xrange(64)] -# Matrices for permutation in the L layer -L0_inv = L0 = [0b0000100010001000, 0b0000010001000100, 0b0000001000100010, 0b0000000100010001, 0b1000000010001000, 0b0100000001000100, 0b0010000000100010, 0b0001000000010001, 0b1000100000001000, 0b0100010000000100, 0b0010001000000010, 0b0001000100000001, 0b1000100010000000, 0b0100010001000000, 0b0010001000100000, 0b0001000100010000] -L1 = [0b1100000000010000, 0b0110000000001000, 0b0011000000000100, 0b0001100000000010, 0b0000110000000001, 0b0000011010000000, 0b0000001101000000, 0b1000000100100000, 0b1000000000011000, 0b0100000000001100, 0b0010000000000110, 0b0001000000000011, 0b0000100010000001, 0b0000010011000000, 0b0000001001100000, 0b0000000100110000] -L1_inv = [0b0000001100000010, 0b1000000100000001, 0b1100000010000000, 0b0110000001000000, 0b0011000000100000, 0b0001100000010000, 0b0000110000001000, 0b0000011000000100, 0b0001000000011000, 0b0000100000001100, 0b0000010000000110, 0b0000001000000011, 0b0000000110000001, 0b1000000011000000, 0b0100000001100000, 0b0010000000110000] -L2 = [0b0000110000000001, 0b0000011010000000, 0b0000001101000000, 0b1000000100100000, 0b1100000000010000, 0b0110000000001000, 0b0011000000000100, 0b0001100000000010, 0b0000100010000001, 0b0000010011000000, 0b0000001001100000, 0b0000000100110000, 0b1000000000011000, 0b0100000000001100, 0b0010000000000110, 0b0001000000000011] -L2_inv = [0b0011000000100000, 0b0001100000010000, 0b0000110000001000, 0b0000011000000100, 0b0000001100000010, 0b1000000100000001, 0b1100000010000000, 0b0110000001000000, 0b0000000110000001, 0b1000000011000000, 0b0100000001100000, 0b0010000000110000, 0b0001000000011000, 0b0000100000001100, 0b0000010000000110, 0b0000001000000011] -L3_inv = L3 = [0b1000100000001000, 0b0100010000000100, 0b0010001000000010, 0b0001000100000001, 0b1000100010000000, 0b0100010001000000, 0b0010001000100000, 0b0001000100010000, 0b0000100010001000, 0b0000010001000100, 0b0000001000100010, 0b0000000100010001, 0b1000000010001000, 0b0100000001000100, 0b0010000000100010, 0b0001000000010001] - -def matrixMultiply(matrix, input): - """Multiply a vector with a binary matrix - - Input: matrix as [Int], where the rows are integers; - input as Int - Output: Int""" - mult = [bin(r & input).count("1") % 2 for r in matrix] - return sum([(1 << (15 - i)) * v for i,v in enumerate(mult)]) +def swap(byte): + """Swap byte nibbles""" + return ((byte & 0xf0) >> 4) | ((byte & 0x0f) << 4) + +def rol(byte): + """Rotate left (bit 0 := bit 7)""" + return ((byte << 1) | (byte >> 7)) & 0xff + +def ror(byte): + """Rotate right (bit 7 := bit 0)""" + return (byte >> 1) | ((byte & 0x01) << 7) + +def M_L0(state): + """Apply matrix L0 using the method described in appendix H of the paper""" + temp = swap((state & 0x00ff) ^ (state >> 8)) + return (((state & 0x00ff) ^ temp) << 8) | ((state >> 8) ^ temp) + +def M_L1(state): + """Apply matrix L1 using the method described in appendix H of the paper""" + s2 = state >> 8 + s3 = swap(state & 0x00ff) + temp = s2 ^ ror(s3) + return ((rol(s2) ^ temp) << 8) | (s3 ^ temp) + +def M_L1_inv(state): + """Apply matrix L1^-1 using the method described in appendix H of the paper""" + s2 = state >> 8 + s3 = state & 0x00ff + temp = ror(s2) ^ ror(s3) + return ((ror(temp) ^ ror(s2)) << 8) | swap(temp ^ s3) + +def M_L2(state): + """Apply matrix L2 using the method described in appendix H of the paper""" + s4 = swap(state >> 8) + s5 = state & 0x00ff + temp = s4 ^ ror(s5) + return ((temp ^ rol(s4)) << 8) | (temp ^ s5) + +def M_L2_inv(state): + """Apply matrix L2^-1 using the method described in appendix H of the paper""" + s4 = state >> 8 + s5 = state & 0x00ff + temp = ror(s4) ^ ror(s5) + return (swap(ror(s4) ^ ror(temp)) << 8) | (s5 ^ temp) + +def M_L3(state): + """Apply matrix L3 using the method described in appendix H of the paper""" + s6 = state >> 8 + s7 = state & 0x00ff + temp = swap(s6 ^ s7) + return ((s6 ^ temp) << 8) | (s7 ^ temp) def roundKey(key, i): """Calculate a round key @@ -206,10 +241,10 @@ def lLayer(state): Output: the new state, as an raw string""" state = pLayer(state) - state = (matrixMultiply(L0, (state >> 48) & 0xffff) << 48) + ( - matrixMultiply(L1, (state >> 32) & 0xffff) << 32) + ( - matrixMultiply(L2, (state >> 16) & 0xffff) << 16) + ( - matrixMultiply(L3, state & 0xffff)) + state = (M_L0((state >> 48) & 0xffff) << 48) + ( + M_L1((state >> 32) & 0xffff) << 32) + ( + M_L2((state >> 16) & 0xffff) << 16) + ( + M_L3(state & 0xffff)) return pLayer_dec(state) def lLayer_dec(state): @@ -222,10 +257,10 @@ def lLayer_dec(state): Output: the new state, as raw string""" state = pLayer(state) - state = (matrixMultiply(L0_inv, (state >> 48) & 0xffff) << 48) + ( - matrixMultiply(L1_inv, (state >> 32) & 0xffff) << 32) + ( - matrixMultiply(L2_inv, (state >> 16) & 0xffff) << 16) + ( - matrixMultiply(L3_inv, state & 0xffff)) + state = (M_L0((state >> 48) & 0xffff) << 48) + ( + M_L1_inv((state >> 32) & 0xffff) << 32) + ( + M_L2_inv((state >> 16) & 0xffff) << 16) + ( + M_L3(state & 0xffff)) return pLayer_dec(state) def string2number(i): @@ -244,4 +279,4 @@ def number2string_N(i, N): Output: string (big-endian) """ s = '%0*x' % (N*2, i) - return s.decode('hex') \ No newline at end of file + return s.decode('hex') -- cgit v1.2.3