Алгоритм А5/1. Криптографическая защита информации: симметричное шифрование

Шифр А5/1 — эго поточный шифр, используемый для шифрования связи GSM (Group Special Mobile — мобильная групповая специальная связь). Это европейский стандарт для мобильных цифровых сотовых телефонов. Он используется для шифрования канала «телефон/базовая станция».

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

Генератор А5/1 состоит из трех РСЛОС длиной 19, 22 и 23, все многочлены обратной связи у него являются неприводимыми по модулю 2 (см. подразд. 6.1). Выходом является результат операций XOR над тремя РСЛОС. В А5/1 используется изменяемое управление тактированием. Каждый регистр тактируется в зависимости от своего среднего бита, затем над регистром выполняется операция XOR с обратной пороговой функцией средних битов всех грех регистров.

Каждый кадр шифруется с помощью секретного ключа шифрования Кс и сквозного порядкового номера очередного кадра. Генератор ПСП А5/1 состоит из трех коротких РСОЛС, обозначаемых как РСОЛС 1, РСОЛС 2 и РСОЛС 3. Выходные биты снимаются с самых старших разрядов регистров, после чего с помощью операции XOR над битами с выходов всех трех регистров формируется выходной бит у шифра. Общий вид работы алгоритма шифрования А5/1 представлен на рис. 91.

Итак, согласно Б. Шнайеру [2], РСЛОС обычно производят сдвиг в сторону младших разрядов. Однако в случае с шифром А5/1 дело обстоит иначе, сдвиг происходит в сторону старших разрядов. На рис. 91 изображены три РСЛОС. Слева в них находятся старшие значащие биты, справа — младшие. Для того чтобы понять соответствие различных описаний шифра А5/1, мы представили на рис. 91 нумерацию битов как слева направо, начиная от нуля, так и справа налево, также от нуля.

Рис. 91. Алгоритм шифрования А5/1.

Из рис. 91 видно, что многочлены, лежащие в основе шифра А5/1, можно описать двумя разными способами. Если следовать логике, предложенной Б. Шнайером, то, используя нумерацию слева направо, начиная от нуля, получится следующая картина:

При этом первые два многочлена можно найти в таблице неприводимых полиномов в книге Б. Шнайера [2]. Третий регистр также является неприводимым по модулю 2. Согласно [2], полином, который в данном поле является образующим, называется примитивным, или базовым, если все его коэффициенты являются взаимно простыми. Для многочлена, описывающего РСЛОСЗ, это условие выполняется.

Регистры шифра А5/1 работают по принципу stop-and-go, что обеспечивается с помощью применения специальной функции majority, на вход которой подаются значения битов регистров: бит С1 для РСОЛС 1, бит С2 для РСОЛС 2 и СЗ для РСОЛС 3. В некоторых источниках указывается следующее соответствие битов: С1 = 8, С2 = 10, СЗ = 10. Это соответствует нумерации справа налево, начиная от нуля, при этом порядко;

вые номера битов будут соответственно 9, 11 и 11. В других же источниках можно встретить указание на Cl = 11, С2 = 12, СЗ = 13, что соответствует тем же самым битам, что и в первом случае, но при нумерации слева направо и начиная не от нуля, а от единицы.

Функция majority имеет следующий вид:

Результатом работы этой функции является один бит, который определяет, какие регистры будут тактироваться (сдвигаться), а какие нет. То есть, если бит с выхода функции совпадает со значением бита регистра на определенной позиции, то регистр сдвигается, иначе нет. Фактически эта функция является функцией большинства, она принимает то значение, которое преобладает на ее входах. В любом случае в режиме работы stop-and-go минимум два регистра будут работать на сдвиг (те, для которых определяющий бит оказался в большинстве). А в случае, когда определяющий бит совпадает у всех регистров, тактироваться будут все гри регистра. Работа регистров по правилу stop-and-go обеспечивает нелинейность работы алгоритма в целом, схема работы этого режима схематично показана на рис. 92. Функцию определения, какой из регистров необходимо тактировать, а какой нет, выполняет блок управления синхронизацией регистров (Clock Control).

На каждом шаге работы шифра два или три регистра сдвигаются. Таким образом, каждый регистр сдвигается в одном такте работы алгоритма с вероятностью % и нс сдвигается с вероятностью 'А.

Процесс формирования гаммы, необходимой для шифрования одного кадра, состоит из следующих шагов.

1. Все три регистра сбрасываются в ноль, а затем тактируются 64 раза без учета режима stop-and-go (все три регистра тактируются). Во время этого этапа каждый бит ключа Кс последовательно записывается в самый младший бит каждого регистра после операции XOR с сигналом обратной связи, как показано на рис. 93.

Рис. 92. Схема работы регистров по правилу stop-and-go в алгоритме А5/1.

• 2. Все три регистра тактируются 22 раза без учета режима stop-and-go. Во время этого этапа биты номера кадра (так же как и биты ключа шифрования Кс в предыдущем пункте) с помощью операции XOR с сигналом обратной связи последовательно записываются в самый младший разряд каждого регистра.
• 3. Осуществляется 100 тактов работы алгоритма с использованием режима stop-and-go, что обеспечивает перемешивание ключевой информации.
• 4. Осуществляется 228 тактов работы алгоритма с использованием режима stop-and-go для формирования гаммы. Затем осуществляется шифрование, когда с помощью операции XOR сформированная последовательность накладывается на информацию, содержащуюся в кадре [1].

Рис. 93. Инициализация ключа К и номера кажра F