EN|RU

Том 18, номер 2, 2011 г., Стр. 51-63

УДК 519.7
Киселёв С. А., Токарева Н. Н.
О сокращении ключевого пространства шифра A5/1 и обратимости функции следующего состояния в поточном генераторе

Аннотация:
Исследуются поточные шифры на регистрах сдвига с обратной связью. Для общего вида поточного генератора доказана теорема, позволяющая отождествить понятия обратимости функции следующего состояния и возвратности функции управления сдвигом. Отдельно рассматривается генератор для А5/1 — поточного шифра, используемого в стандарте GSM и обеспечивающего конфиденциальность переговоров. Для него подсчитано число состояний, которые могут быть получены за t тактов, начиная из состояний без предшественников, причём за меньшее число тактов в такие состояния перейти нельзя. Предложен способ экспоненциального сокращения ключевого пространства А5/1 при тактировании, который может быть использован в криптоанализе.
Ил. 5, табл. 1, библиогр. 8.

Ключевые слова: поточный шифр, регистр сдвига, А5/1.

Киселёв Семён Александрович 2
Токарева Наталья Николаевна 1,2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: kiselev.senya@gmail.com, tokareva@math.nsc.ru

Статья поступила 24 июня 2010 г.
Исправленный вариант — 19 февраля 2011 г.

Литература

[1] Киселёв С. А. О сокращении ключевого пространства поточного шифра А5/1 при тактировании // Прикл. дискрет. математика. Прил. № 3. — 2010. — С. 21–23.

[2] Anderson R. Subject: A5 // posting to Newsgroups: sci.crypt, alt.security, uk.telecom; 17 June 1994.

[3] Biryukov A., Shamir A., Wagner D. Real time cryptanalysis of A5/1 on a PC // Fast Software Encryption Workshop — FSE’2000. (New York, April 10–12, 2000): Proc. — Berlin: Springer–Verl., 2001. — P. 1–18. (Lect. Notes Comput. Sci.; Vol. 1978).

[4] Chambers W. G. On random mappings and random permutations // Fast Software Encryption Workshop — FSE’1994. (Leuven, December 14–16, 1994): Proc. — Berlin: Springer-Verl., 1995. — P. 22–28. (Lect. Notes Comput. Sci.; Vol. 1008).

[5] Golic J. Cryptanalysis of alleged A5 stream cipher // Adv. Cryptology. Workshop on the theory and application of cryptographic techniques — EUROCRYPT’97 (Konstanz, May 11–15, 1997): Proc. — Berlin: Springer-Verl., 1997. — P. 239–255. (Lect. Notes Comput. Sci.; Vol. 1233).

[6] Semenov A., Zaikin O., Bespalov D., Posypkin M. Parallel algorithms for SAT in applocation to discrete functions inversion problems // arXiv.org, Preprint 1102.3563v1.

[7] Shepherd S. J. Cryptanalysis of the GSM A5 cipher algorithm // IEEE Colloquium on Security and Cryptography Applications to Radio Systems, Digest No. 1994/141 (Savoy Place, London, June 3, 1994).

[8] Wagner D. et al. The real-time cryptanalysis of A5/2 // Crypto’99 (Santa Barbara, August 15–19, 1999): Proc. — Berlin: Springer–Verl., 1999 — P. 12–21.

 © Институт математики им. С. Л. Соболева, 2015