On the reduction of key space for A5/1.pdf Рассмотрим генератор псевдослучайной последовательности (гаммы), состоящийиз k регистров с обратной связью. Состоянием генератора будем называть булев век-тор X = (x1, . ..,x „ ) , составленный из состояний регистров, где п = Е lj, lj - дли-i=1на i-го регистра. Функцией управления сдвигом назовем векторную булеву функциюc : Zn ^ Z 2, c(x) = (y1,...,yk), такую, что при следующем такте i-й регистр сдвигаетсятогда и только тогда, когда yj = 1. Функцией следующего состояния называетсявекторная булева функция ^ x t : Zn ^ Zn, которая в соответствии с функцией управлениясдвигом и функциями обратной связи регистров определяет следующее состояние:пех^х) = х'. Вырожденным состоянием назовем такое состояние, у которого какминимум в одном регистре все значения одинаковы. Будем говорить, что функцияуправления сдвигом обратима, если по любому невырожденному состоянию пех^х)можно восстановить вектор с(х) однозначно. Доказан следующий факт.Теорема 1. Пусть функции обратной связи всех регистров генератора обратимыпо последней переменной. Тогда функция следующего состояния обратима тогда итолько тогда, когда обратима функция управления сдвигом.А5/1 [1] - это поточный алгоритм шифрования, используемый для обеспеченияконфиденциальности передаваемых данных между телефоном и базовой станцией в европейскойсистеме мобильной цифровой связи GSM (Group Special Mobile).Утверждение 1. Функция управления сдвигом в генераторе A5/1 необратима.Из утверждения 1 и теоремы 1 следует, что функция ^ x t в А5/1 необратима,а значит, существуют состояния, в которые нельзя перейти. t -Простым состояниемназовем такое состояние, которое получено совершением t тактов, начиная с состояниябез предшественника, причем такое t минимально. Количество t-простых состоянийобозначим Nt.Теорема 2. Количества t-простых состояний в А5/1 для t = 0,1, 2, 3 равны 3 261,13 258, 334 253 и 2792 249 соответственно.Заметим, что сумма чисел N0, N1, N2, N3 составляет довольно большую долю в количествевсех состояний ключевого пространства шифра А5/1 - больше девяти десятых.Наглядней этот результат можно увидеть в таблице ниже (первая строка - числосделанных тактов, вторая - доля оставшегося числа состояний в ключевом пространстве).Число тактов 0 1 2 3 4Ключевое пространство, % 100 62,5 42,2 25,9 15Полученные результаты можно использовать следующим образом. Пусть естьнекое состояние, с которого мы начинаем перехват генерируемой гаммы. Можно пропуститьT битов гаммы для того, чтобы отсечь большую долю состояний, которые немогли получиться в процессе тактирования. Таким образом, при совершении T тактовможно отбросить все 0, 1, . . . , (T - 1)-простые состояния. Нахождение такого T , прикотором откинутое число знаков гаммы будет как можно меньше, а отброшенная доляключевого пространства достаточно большой, уменьшит трудоемкость криптоанализа.Стоит отметить, что наблюдается экспоненциальное сокращение ключевого пространствас каждым пропущенным битом гаммы, т. е. при каждом отбрасывании битагаммы ключевое пространство сокращается почти в 2 раза.К сожалению, с каждым следующим тактом значительно увеличивается сложностьподсчета числа t-простых состояний, и уже для 3-простых состояний подсчет их долизанял около 100 мин работы суперкомпьютера SMP16x256 (использовалось 4 ядра).

Скачать электронную версию публикации