О сокращении ключевого пространства шифра A5/1 и обратимости функции следующего состояния в поточном генераторе

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