diff options
| -rw-r--r-- | A5.1/python/A51_Tables/a51.py | 167 | ||||
| -rw-r--r-- | A5.1/python/A51_Tables/table_gen.py | 62 |
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) |