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 г.

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