Volume 18, No 2, 2011, P. 51-63
UDC 519.7
S. A. Kiselev, N. N. Tokareva
On reduction of key space of the cipher A5/1 and on reversibility of the next-state function for a stream generator
Abstract:
We study stream ciphers based on feedback shift registers. For a stream generator (in general form) we prove that reversibility of its next-state function is closely connected to the recurrency of the shift control function. Then we study generator for the stream cipher À5/1 used in GSM cellular telephone standard. For this generator we count the number of states that can be obtained after t cycles from an initial state without predecessors and cannot be obtained in this way after the smaller number of cycles. We show how to exponentially reduce the key space of A5/1 while clocking. The results can be directly used in cryptanalysis of A5/1.
Ill. 5, tab. 2, bibliogr. 8.
Keywords: stream cipher, feedback shift register, A5/1.
Kiselev Semyon Alexandrovich 2
Tokareva Natalia Nikolaevna 1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: kiselev.senya@gmail.com, tokareva@math.nsc.ru
