А5 — это поточный алгоритм шифрования, используемый для обеспечения конфиденциальности передаваемых данных между телефоном и базовой станцией в европейской системе мобильной цифровой связи GSM (Group Special Mobile).
В этом алгоритме каждому символу открытого текста соответствует символ шифротекста. Текст не делится на блоки (как в блочном шифровании) и не изменяется в размере. Для упрощения аппаратной реализации и, следовательно, увеличения быстродействия используются только простейшие операции: сложение по модулю 2 (XOR) и сдвиг регистра.
Формирование выходной последовательности происходит путём сложения потока исходного текста с генерируемой последовательностью (гаммой). Особенность операции XOR заключается в том, что применённая чётное число раз, она приводит к начальному значению. Отсюда, декодирование сообщения происходит путём сложения шифротекста с известной последовательностью. В реальных системах создаётся ключ заданного размера, который без труда передаётся по закрытому каналу. Последовательность генерируется на его основе и является псевдослучайной. Большой класс поточных шифров (в том числе A5) составляют шифры, генератор псевдослучайной последовательности которой основан на регистрах сдвига с линейной обратной связью.
Регистр сдвига с линейной обратной связью состоит из собственно регистра (последовательности бит заданной длины) и обратной связи. На каждом такте происходит следующие действия: крайний левый бит (старший бит) извлекается, последовательность сдвигается влево и в опустевшую правую ячейку (младший бит) записывается значение функции обратной связи. Эта функция является суммированием по модулю два определённых битов регистра и записывается в виде многочлена, где степень указывает номер бита. Извлечённые биты формируют выходную последовательность.
Для РСЛОС основным показателем является период псевдослучайной последовательности. Он будет максимален (и равен 2n−1), если многочлен функции обратной связи примитивен по модулю 2. Выходная последовательность в таком случае называется М-последовательностью.
Сам по себе РСЛОС легко поддаётся криптоанализу и не является достаточно надёжным, для использования в шифровании. Практическое применение имеют системы регистров переменного тактирования, с различными длинами и функциями обратной связи.
Структура РСЛОС в А5 выглядит следующим образом:
три регистра (R1, R2, R3) имеют длины 19, 22 и 23 бита,
многочлены обратных связей:
X19 + X18 + X17 + X14 + 1 для R1,
X22 + X21 + 1 для R2 и
X23 + X22 + X21 + X8 + 1 для R3,
управление тактированием осуществляется специальным механизмом:
в каждом регистре есть биты синхронизации: 8 (R1), 10 (R2), 10 (R3),
вычисляется функция F = x&y|x&z|y&z, где & — булево AND, | - булево OR, а x, y и z — биты синхронизации R1, R2 и R3 соответственно,
сдвигаются только те регистры, у которых бит синхронизации равен F,
фактически, сдвигаются регистры, синхробит которых принадлежит большинству,
выходной бит системы — результат операции XOR над выходными битами регистров. [1]
В данной реализации на выходе каждого регистра берется младший бит, а при сдвиге новый бит попадает в старшие разряды. Начальное заполнение регистров отлично от принятого: функция создает заполненный регистр нужной длины, используя различные сдвиги начального 8-ми байтного ключа.
При изучении материалов на «Википедии» [1] и в книге Б.Шнайера [2] может возникнуть путаница относительно выходных битов регистров. Исходя из описания и иллюстраций «Википедии» [1], выходной бит системы РСЛОС является результатом операции XOR над старшими битами регистров, а новые биты поступают в младшие разряды. Для исправления этой ошибки в программной реализации необходимо инвертировать биты регистров на этапе заполнения.
Полиномы обратных связей взяты из таблицы, приведенной в книге Б.Шнайера [2]. Как отмечалось ранее, в [1] неправильно указан порядок бит регистров, поэтому необходимо руководствоваться [2].
На Рис.1 приведена иллюстрация системы РСЛОС в А5/1, где голубым цветом выделены полиномы обратных связей для каждого регистра, на Рис.2 [2] все представлено иначе, именно этот вариант используется в реализации.
Рисунок – система РСЛОС в А5/1 [1]
Рисунок – порядок бит регистра и полиномы обратных связей [2]
Для шифра А5/1 были разработаны и реализованы программно-ориентированные алгоритмы в рамках изучения курса "Программно-аппаратная защита информации". На рис.3 показан пример работы программы, отражающий работу алгоритма на примере текстового файла.
Рисунок – текст до/после шифрования
Заключение
Реализация А5/1 не составляет сложностей, затруднения вызывают различные описания. Это связано с тем, что информация о алгоритме держалась в секрете, дабы обеспечить его стойкость, но потом случилась утечка и каждый источник сейчас трактует полученные данные по-своему.
Алгоритм не разрабатывался для обычного поточного шифрования любых данных, для этих целей существуют более продвинутые и продуктивные шифры. А5/1 эффективен, удовлетворяет известным статистическим тестам, существенной слабостью является то, что его регистры слишком коротки, чтобы предотвратить поиск ключа перебором. Варианты A5 с более длинными сдвиговыми регистрами и более плотными многочленами обратной связи должны снизить вероятность взлома алгоритма через данную уязвимость.
Библиографический список
[1] «A5». [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/A5 (дата обращения: 21.12.14).
[2] Шнайер, Б. Прикладная криптография – Москва: Триумф, 2002. – 816 с.