VII Международная студенческая научная конференция Студенческий научный форум - 2015

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

В этом алгоритме каждому символу открытого текста соответствует символ шифротекста. Текст не делится на блоки (как в блочном шифровании) и не изменяется в размере. Для упрощения аппаратной реализации и, следовательно, увеличения быстродействия используются только простейшие операции: сложение по модулю 2 (XOR) и сдвиг регистра.

Формирование выходной последовательности происходит путём сложения потока исходного текста с генерируемой последовательностью (гаммой). Особенность операции XOR заключается в том, что применённая чётное число раз, она приводит к начальному значению. Отсюда, декодирование сообщения происходит путём сложения шифротекста с известной последовательностью. В реальных системах создаётся ключ заданного размера, который без труда передаётся по закрытому каналу. Последовательность генерируется на его основе и является псевдослучайной. Большой класс поточных шифров (в том числе A5) составляют шифры, генератор псевдослучайной последовательности которой основан на регистрах сдвига с линейной обратной связью.

Регистр сдвига с линейной обратной связью состоит из собственно регистра (последовательности бит заданной длины) и обратной связи. На каждом такте происходит следующие действия: крайний левый бит (старший бит) извлекается, последовательность сдвигается влево и в опустевшую правую ячейку (младший бит) записывается значение функции обратной связи. Эта функция является суммированием по модулю два определённых битов регистра и записывается в виде многочлена, где степень указывает номер бита. Извлечённые биты формируют выходную последовательность.

Для РСЛОС основным показателем является период псевдослучайной последовательности. Он будет максимален (и равен 2n−1), если многочлен функции обратной связи примитивен по модулю 2. Выходная последовательность в таком случае называется М-последовательностью.

Сам по себе РСЛОС легко поддаётся криптоанализу и не является достаточно надёжным, для использования в шифровании. Практическое применение имеют системы регистров переменного тактирования, с различными длинами и функциями обратной связи.

Структура РСЛОС в А5 выглядит следующим образом:

• три регистра (R1, R2, R3) имеют длины 19, 22 и 23 бита,

• многочлены обратных связей:

  • X¹⁹ + X¹⁸ + X¹⁷ + X¹⁴ + 1 для R1,

  • X²² + X²¹ + 1 для R2 и

  • X²³ + X²² + X²¹ + X⁸ + 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 с.

Код для цитирования: Скопировать