Интернет магазин китайских планшетных компьютеров

Компьютеры - A5 - Структура А5

Алгоритм A5 в настоящее время — это целое семейство шифров. Для описания возьмем А5/1, как родоначальника этого семейства. Изменения в производных алгоритмах опишем отдельно.

Потоковое шифрование

Схема поточного шифра: сложение открытого текста и последовательности бит даёт шифротекст

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

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

Таким образом, Безопасность системы полностью зависит от свойств последовательности. В идеальном случае каждый бит гаммы — это независимая случайная величина, и сама последовательность является случайной. Такая схема была изобретена Вернамом в 1917 году и названа в его честь. Как доказал Клод Шеннон в 1949 году, это обеспечивает абсолютную криптостойкость. Но использование случайной последовательности означает передачу по защищённому каналу сообщения равного по объёму открытому тексту, что значительно усложняет задачу и практически нигде не используется.

В реальных системах создаётся ключ заданного размера, который без труда передаётся по закрытому каналу. Последовательность генерируется на его основе и является псевдослучайной. Большой класс поточных шифров составляют шифры, генератор псевдослучайной последовательности которой основан на регистрах сдвига с линейной обратной связью.

РСЛОС

Регистр сдвига с линейной обратной связью,
многочлен обратной связи х+х+х+х+1

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

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

Система РСЛОС в А5

Система регистров в алгоритме А5/1

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

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

• три регистра имеют длины 19, 22 и 23 бита,
• многочлены обратных связей:
  • X + X + X + X + 1 для R1,
  • X + X + 1 для R2 и
  • X + X + X + X + 1 для R3,
• управление тактированием осуществляется специальным механизмом:
  • в каждом регистре есть биты синхронизации: 8, 10, 10,
  • вычисляется функция F = x&y|x&z|y&z, где & — булево AND, | - булево OR, а x, y и z — биты синхронизации R1, R2 и R3 соответственно,
  • сдвигаются только те регистры, у которых бит синхронизации равен F,
  • фактически, сдвигаются регистры, синхробит которых принадлежит большинству,
• выходной бит системы — результат операции XOR над выходными битами регистров.

Функционирование алгоритма А5

Рассмотрим особенности функционирования алгоритма, на основе известной схемы. Передача данных осуществляется в структурированном виде — с разбивкой на кадры. При инициализации алгоритма, на его вход поступают сессионный ключ, сформированный А8, и номер кадра. Далее последовательно выполняются следующие действия:

• инициализация:
  • 64 такта без управления сдвигами регистров, при которых младшие биты складываются с соответствующим битом сессионного ключа,
  • аналогичные 22 такта, только суммирование производится с номером кадра,
  • 100 тактов с управлением сдвигами регистров, но без генерации последовательности,
• 228 тактов рабочие, происходит шифрование передаваемого кадра и дешифрование принимаемого,
• далее инициализация производится заново, используется новый номер кадра.

Отличия производных алгоритмов A5/x

Система регистров в алгоритме А5/2

В алгоритм А5/2 добавлен ещё один регистр на 17 бит, управляющий движением остальных. Изменения структуры следующие:

• добавлен регистр R4 длиной 17 бит,
• многочлен обратной связи для R4 X17 + X10 + 1,
• управление тактированием осуществляет R4:
  • в R4 биты 3, 7, 10 есть биты синхронизации,
  • вычисляется мажоритарная функция F = x&y|x&z|y&z, где & — булево AND, | - булево OR, а x, y и z — биты синхронизации R4, R4 и R4 соответственно,
  • R1 сдвигается если R4 = F,
  • R2 сдвигается если R4 = F,
  • R3 сдвигается если R4 = F,
• выходной бит системы — результат операции XOR над старшими битами регистров и мажоритарных функций от определённых битов регистров:
  • R1 — 12, 14, 15,
  • R2 — 9, 13, 16,
  • R3 — 13, 16, 18.

Изменения в функционировании не такие существенные и касаются только инициализации:

• 64+22 такта заполняется сессионным ключом и номером кадра также R4,
• 1 такт R4, R4 и R4 заполняются 1,
• 99 тактов с управлением сдвигами регистров, но без генерации последовательности.

Видно, что инициализация занимает такое же время.

Алгоритм А5/3 разработан в 2001 году и должен сменить A5/1 в третьем поколении мобильных систем. Также он называется алгоритм Касуми. При его создании за основы взят шифр MISTY, корпорации Mitsubishi. В настоящее время считается, что A5/3 обеспечивает требуемую стойкость.

Алгоритм A5/0 не содержит шифрования.