A5/1 implementation in Python by Piotr.

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)