summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndreas Bogk <andreas@pt141.(none)>2009-01-15 17:21:19 +0100
committerAndreas Bogk <andreas@pt141.(none)>2009-01-15 17:21:19 +0100
commit9b2768d943a452ce6b30c41906ec1aeed495f4b1 (patch)
tree08e4ef1e805e34e5b82fb427f9bbdbb696c43c5b
parent239963273242004426adcaf902459a9e1531ab1a (diff)
A5/1 implementation in Python by Piotr.
-rw-r--r--A5.1/python/A51_Tables/a51.py167
-rw-r--r--A5.1/python/A51_Tables/table_gen.py62
2 files changed, 229 insertions, 0 deletions
diff --git a/A5.1/python/A51_Tables/a51.py b/A5.1/python/A51_Tables/a51.py
new file mode 100644
index 0000000..b118287
--- /dev/null
+++ b/A5.1/python/A51_Tables/a51.py
@@ -0,0 +1,167 @@
+from BitVector import BitVector
+"""
+Module with implementations of:
+lsfr - Linear Feedback Shift Register
+a51 - algorithm A5/1
+"""
+
+class lsfr:
+ def __init__(self, length, taps, middle_bit, name=""):
+ """
+ length - length of the register in bits
+ taps - feedback taps, for clocking the shift register.
+ These correspond to the primitive polynomial
+ Example polynomials from A5/1:
+ x**19 + x**5 + x**2 + x + 1, x**22 + x + 1,
+ or x**23 + x**15 + x**2 + x + 1
+ middle_bit - middle bit of each of the three shift registers, for clock control
+ name - name of LSFR - for print()
+ """
+ self.taps = taps
+ self.length = length
+ self.name = name
+ self.value = BitVector(size = length);
+ self.clk_bit_nr = length-middle_bit-1
+
+ def mix(self, liczba):
+ """Read value from LSB to MSB and add each bit to LSFR's feedback"""
+ for key_bit in reversed(liczba):
+ bit = key_bit
+ self.clock(bit)
+
+ def clock(self, bit=False):
+ """Clock LSFR. Can add value of bit to feedback."""
+ for tap in self.taps:
+ bit_nr = self.length - tap - 1
+ bit = bit ^ self.value[bit_nr]
+ self.value << 1
+ self.value[self.length-1] = bit
+
+ def out(self):
+ """Clock LSFR. Can add value of bit to loopback."""
+ return self.value[0]
+
+ def clk_bit(self):
+ """Return clocking bit."""
+ return self.value[self.clk_bit_nr]
+
+ def set_value(self, value):
+ """Set internal state of LSFR."""
+ self.value = BitVector(size=self.length, intVal=value)
+
+ def __str__(self):
+ return "%s:%X" % (self.name, self.value.intValue())
+
+
+class a51:
+ def __init__(self):
+ self.key_size = 64
+ self.fn_size = 22
+ self.r1 = lsfr(19, [13, 16, 17, 18], 8, "R1")
+ self.r2 = lsfr(22, [20, 21], 10, "R2")
+ self.r3 = lsfr(23, [7, 20, 21, 22], 10, "R3")
+ self.r1_state_mask = ((1 << self.r1.length) -1 )
+ self.r2_state_mask = ((1 << self.r2.length) -1 )
+ self.r3_state_mask = ((1 << self.r3.length) -1 )
+
+ def initialize(self, key, fn):
+ """
+ Initialize algorithm with:
+
+ key - value of Kc - integer value of 64 bits
+ fn - fame number - integer value of 22 bits
+ """
+ key_vect = BitVector(size=self.key_size, intVal=key)
+ fn_vect = BitVector(size=self.fn_size, intVal=fn)
+
+ self.r1.mix(key_vect)
+ self.r2.mix(key_vect)
+ self.r3.mix(key_vect)
+
+ self.r1.mix(fn_vect)
+ self.r2.mix(fn_vect)
+ self.r3.mix(fn_vect)
+
+ for i in xrange(0, 100):
+ self._clock_regs()
+
+ def _clock_regs(self):
+ """Clock all LSFR's according to majority rule."""
+ maj = self._majority()
+ if self.r1.clk_bit() == maj:
+ self.r1.clock()
+ if self.r2.clk_bit() == maj:
+ self.r2.clock()
+ if self.r3.clk_bit() == maj:
+ self.r3.clock()
+
+ def get_output(self):
+ """
+ Generate 228 keystream bits:
+
+ AtoB - 114 bits of keystream for the A->B direction. Store it, MSB first
+ BtoA - 114 bits of keystream for the B->A direction. Store it, MSB first
+ """
+ AtoB = self.gen_block(114)
+ BtoA = self.gen_block(114)
+ return (AtoB, BtoA)
+
+ def _out_bit(self):
+ out_bit = self.r1.out() ^ self.r2.out() ^ self.r3.out()
+ return out_bit
+
+ def gen_block(self,size):
+ out = BitVector(size=0)
+ for i in xrange(0, size):
+ self._clock_regs()
+ out = out + BitVector(intVal = int(self._out_bit()))
+ return out.intValue()
+
+ def _majority(self):
+ sum = self.r1.clk_bit()+self.r2.clk_bit()+self.r3.clk_bit()
+ if sum >= 2:
+ return True
+ else:
+ return False
+
+ def get_state(self):
+ state = self.r3.value + self.r2.value + self.r1.value
+ return state.intValue()
+
+ def set_state(self,state):
+ r1_value = state & self.r1_state_mask
+ state = state >> self.r1.length
+ r2_value = state & self.r2_state_mask
+ state = state >> self.r2.length
+ r3_value = state & self.r3_state_mask
+ state = state >> self.r3.length
+ self.r1.set_value(r1_value)
+ self.r2.set_value(r2_value)
+ self.r3.set_value(r3_value)
+
+def test():
+ key = 0xEFCDAB8967452312 #== 0x48C4A2E691D5B3F7 from A5/1 pedagogical implementation in C
+ fn = 0x000134
+ known_good_AtoB = 0x14D3AA960BFA0546ADB861569CA30# == 0x534EAA582FE8151AB6E1855A728C00 from A5/1 pedagogical implementation in C
+ known_good_BtoA = 0x093F4D68D757ED949B4CBE41B7C6B#== 0x24FD35A35D5FB6526D32F906DF1AC0 from A5/1 pedagogical implementation in C
+ alg = a51()
+ alg.initialize(key, fn)
+ alg.set_state(alg.get_state())
+ (AtoB, BtoA) = alg.get_output()
+ failed = False
+ if (AtoB != known_good_AtoB) or (BtoA != known_good_BtoA):
+ failed = True
+
+ print "Key: %x" % key
+ print "Fame number: %x" % fn
+ print "Known good keystream from A to B: 0x%029x" % known_good_AtoB
+ print "Observed keystream from A to B : 0x%029x" % AtoB
+ print "Known good keystream from B to A: 0x%029x" % known_good_BtoA
+ print "Observed keystream from B to A : 0x%029x" % BtoA
+ if failed != True:
+ print "\nResult: everything looks ok."
+ else:
+ print "\nResult: test failed!"
+
+if __name__ == '__main__':
+ test() \ No newline at end of file
diff --git a/A5.1/python/A51_Tables/table_gen.py b/A5.1/python/A51_Tables/table_gen.py
new file mode 100644
index 0000000..0e22db3
--- /dev/null
+++ b/A5.1/python/A51_Tables/table_gen.py
@@ -0,0 +1,62 @@
+from a51 import *
+
+class table_gen:
+ def __init__(self, end_point_bit, max_chain_len, max_number_chains):
+ self.end_point_mask = (1 << end_point_bit) - 1
+ self.max_number_chains = max_number_chains
+ self.max_chain_len = max_chain_len
+ self.reduction_function = 0
+
+ def gen(self, reduction_function):
+ self.reduction_function = reduction_function
+ for chain_number in xrange(0,self.max_number_chains):
+ start_point = self._gen_start_point(chain_number)
+ (max_chain_len_exceed, end_point, chain_length) = self._gen_chain(start_point)
+
+ if max_chain_len_exceed == False: #max_chain_len_exceed is looping
+ print (start_point, end_point, chain_length)
+
+ def _gen_start_point(self, chain_number):
+ start_point = ((chain_number+1) << (18+22))+((chain_number+1) << (18))+(chain_number+1)
+ return start_point #TODO: find better method to generate start_points of chains
+
+ def _gen_chain(self, start_point): #a5_until_endpoint
+ alg = a51()
+ state = start_point
+ alg.set_state(state)
+
+ print "Generating a chain"
+
+ for chain_links in xrange(0, max_chain_len):
+ output = alg.gen_block(64)
+ print "State:%x -> Output:%x" % (state, output)
+ if self._is_endpoint(output):
+ return (False, output, chain_links)
+
+ state = self._reduction(output)
+ alg.set_state(state)
+
+ return (True, None, None)
+
+ def _is_endpoint(self, output):
+ if (output & self.end_point_mask) == 0:
+ return True
+ else:
+ return False
+
+ def _reduction(self, output):
+ return output ^ self.reduction_function
+
+def gen_tables(max_tables, end_point_bit, max_chain_len, max_number_chains):
+ generator = table_gen(end_point_bit, max_chain_len, max_number_chains)
+ for table_nr in xrange(1,max_tables):
+ reduction_function = table_nr
+ generator.gen(reduction_function)
+
+if __name__ == '__main__':
+ max_tables = 156
+ max_number_chains = 2000
+ end_point_bit = 27
+ max_chain_len = 2000
+
+ gen_tables(max_tables, end_point_bit, max_chain_len, max_number_chains)
personal git repositories of Harald Welte. Your mileage may vary