Потоковые шифры


Потоковые и блочные шифры. Симметричные и асимметричные алгоритмы.

Потоковые шифры — это шифры, при которых каждый бит информации шифруется с помощью гаммирования.

Гаммирование — это наложение на открытые данные гаммы шифра по определенному правилу. Для расшифрования та же гамма накладывается на зашифрованный текст.

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

Надежность этого метода зависит от гаммы, полученной генератором (избегайте нулей, соблюдайте последовательность).

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

Существует 2 основных вида блочных шифров — шифры перестановки Р-блоки и шифры замены S-блоки.

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

В полиалфавитном шифре для замены символа исходного текста применяют другие символы из другого набора, например шифр Видженера.

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

  1. Объект А передает объекту Б ключ
  2. Объект А, используя ключ, зашифровывает текст, которое пересылает объекту Б
  3. Объект Б получает текст и расшифровывает его.

Если для каждого этапа передачи информации будет использован уникальный ключ, то надежность системы будет высокой.

А в асимметричном алгоритме шифрования для зашифрования текста используется 2 ключа — один открытый для шифрования, а второй секретный для расшифровки. Они различные и не могут быть получены один из другого. Обмен информацией тоже происходит в 3 этапа:

  1. объект Б узнает открытый и секретный ключи, секретный остается у себя, а открытый становится доступный, сообщает это объекту А
  2. объект А, используя открытый ключ объекта Б, зашифровывает текст, которое отправляет объекту Б
  3. объект Б получает текст и расшифровывает его, используя секретный ключ.

Пример симметричного алгоритма шифрования — код Цезаря, пример асимметричного алгоритма шифрования — сеть Фейсталя.

Потоковые шифры

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

Режим гаммирования для поточных шифров

Простейшая реализация поточного шифра изображена на рисунке. Генератор гаммы выдаёт ключевой поток (гамму):

Поток битов открытого текста:

Гамма шифра и поток битов открытого текста подвергаются операции XOR. Так получается поток битов шифротекста: , где

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом:

Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

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

Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

Заметим, что выполняться синхронизация должна так, чтобы ни одна часть потока ключей не была повторена. Поэтому переводить генератор в более раннее состояние не имеет смысла.

  • отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);
  • предохраняют от любых вставок и удалений шифротекста, так как они приведут к потере синхронизации и будут обнаружены.
  • уязвимы к изменению отдельных бит шифрованного текста. Если злоумышленнику известен открытый текст, он может изменить эти биты так, чтобы они расшифровывались, как ему надо.
  • Самосинхронизирующиеся поточные шифры

    Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста.

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

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

    • Размешивание статистики открытого текста. Так как каждый знак открытого текста влияет на следующий шифротекст, статистические свойства открытого текста распространяются на весь шифротекст. Следовательно, АПШ может быть более устойчивым к атакам на основе избыточности открытого текста, чем СПШ.
    • распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);
    • чувствительны к вскрытию повторной передачей.
  • Большинство существующих шифров с секретным ключом однозначно могут быть отнесены либо к поточным, либо к блочным шифрам. Но теоретическая граница между ними является довольно размытой. Например, используются алгоритмы блочного шифрования в режиме поточного шифрования (пример: для алгоритма DES режимы CFB и OFB). Рассмотрим основные различия между поточными и блочными шифрами не только в аспектах их безопасности и удобства, но и с точки зрения их изучения в мире:

    • важнейшим достоинством поточных шифров перед блочными является высокая скорость шифрования, соизмеримая со скоростью поступления входной информации; поэтому, обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных.
    • в синхронных поточных шифрах (в отличие от блочных) отсутствует эффект размножения ошибок, то есть число искаженных элементов в расшифрованной последовательности равно числу искаженных элементов зашифрованной последовательности, пришедшей из канала связи.
    • структура поточного ключа может иметь уязвимые места, которые дают возможность криптоаналитику получить дополнительную информацию о ключе (например, при малом периоде ключа криптоаналитик может использовать найденные части поточного ключа для дешифрования последующего закрытого текста).
    • ПШ в отличие от БШ часто могут быть атакованы при помощи линейной алгебры (так как выходы отдельных регистров сдвига с обратной линейной связью могут иметь корреляцию с гаммой). Также для взлома поточных шифров весьма успешно применяется линейный и дифференциальный анализ.


    Теперь о положении в мире:

    • в большинстве работ по анализу и взлому блочных шифров рассматриваются алгоритмы шифрования, основанные на стандарте DES; для поточных же шифров нет выделенного направления изучения; методы взлома ПШ весьма разнообразны.
    • для поточных шифров установлен набор требований, являющихся критериями надёжности (большие периоды выходных последовательностей, постулаты Голомба, нелинейность); для БШ таких чётких критериев нет.
    • исследованием и разработкой поточных шифров в основном занимаются европейские криптографические центры, блочных – американские.
    • исследование поточных шифров происходит более динамично, чем блочных; в последнее время не было сделано никаких заметных открытий в сфере DES-алгоритмов, в то время как в области поточных шифров случилось множество успехов и неудач (некоторые схемы, казавшиеся стойкими, при дальнейшем исследовании не оправдали надежд изобретателей).

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

    1. Cистемно-теоретический подход основан на создании для криптоаналитика сложной, ранее неисследованной проблемы.
    2. Cложно-теоретический подход основан на сложной, но известной проблеме (например, факторизация чисел или дискретное логарифмирование).
    3. Информационно-технический подход основан на попытке утаить открытый текст от криптоаналитика – вне зависимости от того сколько времени потрачено на дешифрование, криптоаналитик не найдёт однозначного решения.
    4. Рандомизированный подход основан на создании объёмной задачи; криптограф тем самым пытается сделать решение задачи расшифрования физически невозможной. Например: криптограф может зашифровать некоторую статью, а ключом будут указания на то, какие части статьи были использованы при шифровании. Криптоаналитику придётся перебирать все случайные комбинации частей статьи, прежде чем ему повезёт, и он определит ключ.

    Теперь приведём теоретические критерии Райнера Рюппеля для проектирования поточных систем:

    • длинные периоды выходных последовательностей
    • большая линейная сложность
    • диффузия – рассеивание избыточности в подструктурах, “размазывание” статистики по всему тексту
    • каждый бит потока ключей должен быть сложным преобразованием большинства битов ключа
    • критерий нелинейности для логических функций.

    До сих пор не было доказано, что эти критерии необходимы или достаточны для безопасности поточной системы шифрования.

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

    Все методы криптоанализа поточных шифров обычно подразделяют на 3 класса:

    Атаки путём полного перебора(перебор всех возможных вариантов). Сложность полного перебора зависит от количества всех возможных решений задачи (размера пространства ключей или пространства открытого текста). Этот вид атаки применим ко всем видам систем поточного шифрования. При разработке систем шифрования разработчики стремятся сделать так, чтобы этот вид атак был наиболее эффективным по сравнению с другими существующими методами взлома.

    Делятся на два подкласса:

    1. Метод криптоанализа статистических свойств шифрующей гаммы: направлен на изучение выходной последовательности криптосистемы; криптоаналитик пытается установить значение следующего бита последовательности с вероятностью выше вероятности случайного выбора с помощью различных статистических тестов.
    2. Метод криптоанализа сложности последовательности: криптоаналитик пытается найти способ генерировать последовательность, аналогичную гамме, но более просто реализуемым способом.

    Оба метода используют принцип линейной сложности.

    Этот вид атак рассматривается в предположении, что криптоаналитику известны описание генератора, открытый и соответствующий закрытый тексты. Задача криптоаналитика определить использованный ключ (начальное заполнение регистров).

    Виды аналитических атак, применяемые к синхронным поточным шифрам:

    Потоковые шифры

    Потоковые шифры преобразуют открытый текст в шифротекст по одному биту за операцию. Простейшая реализация потокового шифра показана на Рис. -6. Генератор потока ключей (иногда называемый генератором с бегущим ключом) выдает поток битов: k1, k2, k3, . ki. Этот поток ключей (иногда называемый бегущим ключом) и поток битов открытого текста, p1, p2, p3, . pi, подвергаются операции «исключающее или», и в результате получаетсяы поток битов шифротекста.

    При дешифрировании операция XOR выполняется над битами шифротекста и тем же самым потоком ключей для восстановления битов открытого текста.

    это работает правильно.

    Безопасность системы полностью зависит от свойств генератора потока ключей. Если генератор потока ключей выдает бесконечную строку нулей, шифротекст будет совпадать с открытым текстом, и все операция будет бессмысленна. Если генератор потока ключей выплевывает повторяющийся 16-битовый шаблон, алгоритм будет являться простым XOR с пренебрежимо малой безопасностью (см. раздел 1.4). Если генератор потока ключей выплевывает бесконечный поток случайных (по настоящему, а не псевдослучайных — см. раздел 2.8) битов, вы получаете одноразовый блокнот и идеальную безопасность.

    На деле безопасность потокового шифра находится где-то между простым XOR и одноразовым блокнотом. Генератор потока ключей создает битовый поток, который похож на случайный, но в действительности детерминирован и может быть безошибочно воспроизведен при дешифрировании. Чем ближе выход генератора потока ключей к случайному, тем больше времени потребуется криптоаналитику, чтобы взломать шифр.

    Рис. -6. Потоковый шифр

    Однако, если генератор потока ключей при каждом включении создает один и тот же битовый поток, то использующую его криптосистему взломать нетрудно. Покажем на примере, почему это так.

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

    Теперь, перехватив любое другое шифрованное сообщение, она сможет расшифровать его, используя полученный поток ключей. Кроме того, она может расшифровать и прочитать любое из ранее перехваченных сообщений. Когда Ева получит пару открытый текст/шифротекст, она сможет читать все.

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

    Генератор потока ключей состоит из трех основных частей (см. Рис. -7). Внутреннее состояние описывает текущее состояние генератора потока ключей. Два генератора потока ключей, с одинаковым ключом и одинаковым внутренним состоянием, выдают одинаковые потоки ключей. Функция выхода по внутреннему состоянию генерирует бит потока ключей. Функция следующего состояния по внутреннему состоянию генерирует новое внутреннее состояние.

    Рис. -7. Устройство генератора потока ключей.

    Потоковые шифры

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

    Гаммирование — наложение на открытые данные гаммы шифра (случайной или псевдослучайной последовательности единиц и нулей) по определенному правилу. Обычно используется «исключающее ИЛИ», называемое также сложением по модулю 2 и реализуемое в ассемблерных программах командой XOR. Для расшифровывания та же гамма накладывается на зашифрованные данные.

    При однократном использовании случайной гаммы одинакового размера с зашифровываемыми данными взлом кода невозможен (так называемые криптосистемы с одноразовым или бесконечным ключом). В данном случае «бесконечный» означает, что гамма не повторяется.

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

    Понятно, что обмен ключами размером с шифруемую информацию не всегда уместен. Поэтому чаще используют гамму, получаемую с помощью генератора псевдослучайных чисел (ПСЧ). В этом случае ключ — порождающее число (начальное значение, вектор инициализации, initializing value, IV) для запуска генератора ПСЧ. Каждый генератор ПСЧ имеет период, после которого генерируемая последовательность повторяется. Очевидно, что период псевдослучайной гаммы должен превышать длину шифруемой информации.

    Генератор ПСЧ считается корректным, если наблюдение фрагментов его выхода не позволяет восстановить пропущенные части или всю последовательность при известном алгоритме, но неизвестном начальном значении [4, c. 63].

    При использовании генератора ПСЧ возможны несколько вариантов [4, c. 126 — 128]:

    1. Побитовое шифрование потока данных. Цифровой ключ используется в качестве начального значения генератора ПСЧ, а выходной поток битов суммируется по модулю 2 с исходной информацией. В таких системах отсутствует свойство распространения ошибок.

    2. Побитовое шифрование потока данных с обратной связью (ОС) по шифртексту. Такая система аналогична предыдущей, за исключением того, что шифртекст возвращается в качестве параметра в генератор ПСЧ. Характерно свойство распространения ошибок. Область распространения ошибки зависит от структуры генератора ПСЧ.

    3. Побитовое шифрование потока данных с ОС по исходному тексту. Базой генератора ПСЧ является исходная информация. Характерно свойство неограниченного распространения ошибки.

    4. Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

    «Облегчённые» поточные шифры

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

    Ниже приведен список рассматриваемых в данной статье «легковесных» криптографических алгоритмов, основанных на поточном шифровании и основные механизмы реализации. Но прежде чем мы перейдем к их описанию, необходимо ознакомиться с основными реализациями, которые используются в аппаратной части таких алгоритмов: LFSR и FCSR.


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

    Contents

    Регистр сдвига с линейной обратной связью — регистр сдвига битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

    Рисунок 1. Регистр сдвига с линейной обратной связью

    В течение каждого такта регистр сдвига с линейной обратной связью выполняет следующие операции:

    • читается бит, расположенный в ячейке L — 1; этот бит является очередным битом выходной последовательности;
    • функции обратной связи вычисляет новое значение для ячейки 0, используя текущие значения ячеек;
    • содержимое каждой i-й ячейки перемещается в следующую ячейку i+1, где i = 0;1;. ;L-2;
    • в ячейку 0 записывается бит, ранее вычисленный функцией обратной связи.
    Илон Маск рекомендует:  Смена серийного номера тома

    Если функция обратной связи выполняет логическую операцию «XOR» (исключающее ИЛИ), значения бит (ячеек) могут быть вычислены по следующим формулам:

    Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году. Позднее ими был разработан алгоритм такого шифра. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется. В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSR. Позднее он был подвергнут атаке с выбором шифротекста. В 2005 году Арно и Бергер предложили идею совместного использования FCSR и линейного фильтра для создания поточного шифра, который получил название F-FCSR (Filtered FCSR). Позже ими были предложены 4 алгоритма, реализующих эту идею: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 и F-FCSR-DF8. Первые два использовали статические фильтры, последние — фильтры, зависящие от ключа. Позже была выявлена слабость всех этих алгоритмов перед различными видами атак. В 2005 Терри Бергер, Франсуа Арноль и Седрик Лараду предложили два шифра на основе F-FCSR для участия в конкурсе eSTREAM: F-FCSR-H для аппаратной реализации и F-FCSR-8 для программной. В результате последующих испытаний у первоначальных версий F-FCSR-H и F-FCSR-8 были найдены уязвимости, которые позже были исправлены в версиях F-FCSR-H v.2 и F-FCSR-16. Улучшенный вариант F-FCSR-H v.2 стал финалистом eSTREAM. Но после обнаружения уязвимости был исключен из eSTREAM Portfolio (rev.1).

    Рисунок 2. Конфигурация Галуа для FCSR

    FCSR реализуется в двух конфигурациях: Галуа и Фиббоначи. В F-FCSR используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения:

    1. q — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
      • T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q
      • Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2
    2. p — параметр, зависящий от ключа, такое, что 0 n n+1
    3. d: d = (1 − q)/2, в двоичной записи , di = <0, 1>, dn-1 = 1
    4. M — n-разрядный главный регистр, значения его i-го разряда, .
    5. C — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, .
    6. (m, c) — состояние FCSR

    Если (m, c) — состояние FCSR в момент времени t, , то — двоичное представление p/q, где p = m + 2c.

    Семейство поточных шифров Grain

    В этом разделе описывается семейство поточных шифров Grain. Главным его отличием от остальных алгоритмов, представленных на проекте eSTREAM, является чрезвычайно малая аппаратная реализация. В течение этого проекта (eSTREAM) начальная версия v0 была доработана после некоторых наблюдений Berbain. Окончательный вариант Grain известен как Grain v1.

    Как и другие шифры, Grain v1 достаточно современен для того чтобы использовать публичные, т.е. общедоступные векторы инициализации (IV), хотя и 80-битные. Признавая необходимость в 128-битных ключах, Hell предложил 128-битные ключи для Grain, в котором используются 96-битные векторы инициализации. Принцип тот же, что и у 80-битной версии, но особенностью является нелинейная часть шифра, а именно меньшая степень чем в v0.

    Общая идея Grain состоит в использовании ключа размера |k|; NFSR и LFSR аналогично c размером |k| и выходной функции, которая использует состояние обоих регистров. LFSR обеспечивает функционирование NFSR путем передачи данных. В NFSR поступает ключ, а LFSR — вектор инициализации, дополняемый константой. После этого ключ и вектор инициализации загружаются, но перед генерацией гаммы состояние определяется путем 2 · |k| обновлений, где происходит обратная связь выходной последовательности в LSRF. После инициализации начинается генерирование гаммы.

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

    Grain v1

    Поточный шифр Grain был разработан Мартином Хеллом, Томасом Йоханссоном и Вилли Мейером. Их основной целью было разработать алгоритм, который очень легко реализовать в аппаратной части и который достаточно мал по площади. Это бит-ориентированный синхронный поточный шифр, который означает, что ключ генерируется независимо от входного текста. В общем, поточный шифр состоит из двух этапов.

    Первый этап — это этап инициализации внутреннего состояния с помощью секретного ключа и вектора инициализации. После этого состояние повторно обновляется и используется для генерации гаммы. Основные элементы поточного шифра Grain, как было упомянуто выше, — это два 80-битных регистров сдвига, где один имеет линейную обратную связь (LFSR), а другой нелинейную обратную связь (NFSR). Размер ключа составляет 80-бит, в образовании которого используется 64-бита вектора инициализации. К сожалению, первоначальная версия Grain v0 имела уязвимость в функции вывода, которую обнаружили во время первого этапа оценки. В Grain v1 проблема с ветором инициализации была решена.

    Основную структуру алгоритма можно увидеть на рисунке 3. Два многочлена степени 80 f(x) и g(х) используются в качестве функции обратной связи для регистров сдвига с обратной связью LFSR и NFSR. Функция выхода h(х) использует в качестве входной последовательности биты из обоих регистров сдвига с обратной связью. Кроме того, семь бит из NFSR XOR-ятся и результат прибавляется к функции h(x). Этот результат используется в фазе инициализации в качестве дополнительной обратной связи LFSR и NFSR (серые линий на рисунке обозначают эту обратную связь). Во время нормальной работы это значение используется в качестве гаммы.

    Рисунок 3. Схема поточного шифра Grain v1

    Аппаратный модуль Grain v1 был реализован с 16-битным AMBA APB интерфейсом и технологическим процессом в 0,35 мкм на CMOS. Этот интерфейс подходит к 16-битной архитектуре. Причиной для этой реализации на 16-битах слова является подход с низким энергопотреблением. Подробности итераций прохода данных представлены на рисунке 4. Видно, что регистры сдвига обратной связи NFSR и LFSR обрабатывают 16 бит за такт. Только один регистр действует в тот же момент времени, что облегчает ввод ключа и вектор инициализации, потому что те же самые 16 проводов подключены ко всем регистрам. Кроме того, значительно уменьшается среднее потребление энергии. Это происходит за счет наличия временного регистра, который хранит промежуточные результаты. Кроме того все комбинационные схемы, как функции обратной связи g, f и h должны быть реализованы в шестнадцатеричной системе счисления. Входы этих функции — это выбранные биты из регистров, которые не показаны подробно на этом рисунке. h функция также включает в себя XOR операции выходной функции. Выход модуля уже зарегистрирован и вместо гаммы и зашифрованного результата входных данных хранится в регистре. Вместо того, чтобы мультиплексор сам выбирал корректную обратную функцию для временного регистра, команда AND используются для включения и отключения соответствующих входов. Производство 16-битного результата шифрования требует 13 тактов после инициализации.

    Рисунок 4. Схема обработки данных поточного шифра Grain v1

    Ниже представлена таблица со значениями GE для основных элементов реализации Grain v1.

    Таблица 1. Компоненты реализации Grain v1

    Компонент реализации Минимальная площадь (radix — 1), GE Минимальная прощадь (radix — 16), GE
    NFSR + LFSR (160 бит) 1,275 1,130
    Временный регистр 85
    Регистр выхода 50 150
    Комбинация логики с misc 315 1,835
    Контроллер (FSM) 120 160
    Суммарно 1,760 3,360

    Trivium

    Разработчиками поточного шифра Trivium являются Кристоф де Каниэр и Барт Пренель. Это аппаратно-ориентированный синхронный поточный шифр, который был разработан для исследования того, насколько простым должен быть шифр, чтобы не жертвовать его безопасностью. Можно генерировать до 2^64 битов гаммы из 80-битного ключа и 80 битов вектора инициализации. Состояние состоит из 288 бит которые обозначены как S0, S2, . s287. В течение инициализации, которая не показана на схеме, ключ и вектор не загружаются в состояние и в то же время обновление фнкции происходит 1152 раз без использования выхода для гаммы. В описании алгоритма, N используется для определения количества выходных битов поточного шифра.

    Реализация модуля Trivium имеет тот же 16-битный AMBA APB интерфейс, как и Grain v1. Использование 16-битного процессора также мотивировано энергосбережением, которое является необходимым критерием для «облегчённых» шифров. Рисунок 5 показывает подробную информацию об архитектуре Trivium. «Коробки» с входящем полем comb являются комбинационными логическими элементами алгоритма, которые используются для обновления состояния в соответствии со спецификацией. 288 бит для определения состояния разделяются в 16-разрядные регистры. Кроме того необходимо два временных регистра для хранения промежуточных результатов. Выходной регистр снова используется для непосредственного применения операции XOR гаммы с входным значением. Во время инициализации ключ, вектор инициализации и константы загружаются в регистры. Затем комбинационные схемы используются для обновления регистров, где также используются временные регистры для предотвращения перезаписи необходимых значений. Генерация 16-битной гаммы требует 22 такта после фазы инициализации.

    Рисунок 5. Схема обработки данных поточного шифра Trivium

    Ниже представлена таблица со значениями GE для основных элементов реализации Trivium.

    Таблица 2. Компоненты реализации Trivium

    Компонент реализации Минимальная площадь (radix — 1), GE Минимальная прощадь (radix — 16), GE
    Регистры состояния (288 бит) 1,840 2,040
    Временный регистр 200
    Регистр выхода 50 150
    Комбинация логики с misc 290 410
    Контроллер (FSM) 210 290
    Суммарно 2,390 3,090

    Bean является поточным шифром, который имеет некоторые сходства с Grain: The NFSR и LFSR у второго заменяются на два FCSR. Существует определенный смысл этой замены, так как LFSR в Grain используется для обеспечения большего периода последовательности и случайности, в то время как NFSR используется для обеспечения нелинейности. A FCSR комбинируют обеспечение обоих свойств LFSR и NFSR, плюс остаются такими же компактными на аппаратном уровне. Помимо этого Bean использует реализацию на архитектуре Фибоначчи, в отличие от Grain, который реализован на архитектуре Галуа.

    На рисунке 6 представлена архитектура реализации поточного шифра Bean.

    Рисунок 6. Архитектура Фибоначчи в поточном шифре Bean

    У обоих регистров сдвига размер составляет 80 бит, как и размер ключа. Состояние первого FCSR 1 обозначается , а состояние FCSR 2 , которые определяются следующим образом:

    Обновление состояния FCSR 1:

    Обновление состояния FCSR 2:

    Функция используется для создания самой гаммы. Используется S-box, на вход которого подается 6 бит, а на выходе 4. Биты гаммы получаются из :

    А функция имеет вид:

    Hummingbird

    В отличие от существующих легких криптографических примитивов, в которых присутствует либо блочный шифр, либо поточный шифр, Hummingbird является сочетанием двух вышеупомянутых шифров с 16-битным размером блока, 256-битным размером ключа, и 80-битным внутренним состоянием. Размер ключа и внутреннего состояния Hummingbird обеспечивает уровень безопасности, адекватный для многих приложений RFID. Для ясности, мы используем обозначения, перечисленные в таблице 1 описания алгоритма. На рисунке 7 показана структура верхнего уровня шифрования Hummingbird в процессе зашифрования.

    Рисунок 7. Структура верхнего уровня шифрования Hummingbird

    Общая структура алгоритма шифрования Hummingbird состоит из четырех 16-битных блочных шифров — четырех 16-битных регистров внутреннего состояния RS1,RS2,RS3 и RS4, и 16-ступенчатого LFSR. 256-битный секретный ключ K делится на четыре 64-битных подключа k1,k2,k3 и k4, которые используются в четырех блочных шифров. 16-битный блок открытого текста шифруется взятием по модулю добавлением и содержащий первый регистр RS1 внутреннего состояния. Результат сложения затем шифруется с первым блочным шифром . Эта процедура повторяется таким же образом, еще три раза, и выход является зашифрованным текстом . Кроме того, состояние четырех регистров внутреннего состояния также будут обновлены непредсказуемым способом, основанным на их текущих состояниях, выходах первых трех блочных шифров, и состоянии LFSR. Процесс расшифровки происходит по схеме аналогичной шифрованию.

    На практике в Hummingbird используют четыре 16-битных случайные которые в первую очередь выбираются для инициализации четырех внутренних состояний регистров (i = 1, 2, 3, 4),далее следуют четыре последовательных шифрования сообщения (RS1+ RS3)mod2 с Hummingbird, работающим в режиме инициализации. Последний 16-битный зашифрованный текст используется для инициализации LFSR. Кроме того, 13тый бит LFSR всегда имеет значение, чтобы предотвратить нулевой регистр. LFSR также «шагнул» с целью обновлениярегистра внутреннего состояния RS2.


    Четыре одинаковых 16-битных блочных шифра используются в последовательном порядке в схеме шифрования Hummingbird.16-битный блочный шифр является типичной SP-сетью с 16-битным размером блока и 64-битным ключом.Он состоит из 4 итераций, и на последней итерации включает в себя только функцию смешения содержимого ключа и шаги замещения S-бокса. Как и в любой другой SP-сети, одна очередная итерация состоит из трех этапов: шаг смешения ключа, слой замены и слой перестановки. В этом 16-битном блочном шифре для смешения ключа используются простое исключение или операция, с целью эффективной реализации в программной и аппаратной части.

    Глоссарий

    Библиографический указатель

    Перейти к списку литературы по разделу «Облегчённые» поточные шифры.

    Симметричные и потоковые шифры

    Симметричные криптосистемы (также симметричное шифрование, симметричные шифры) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями.

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

    Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже:

    • 1. Простая перестановка
    • 2. Одиночная перестановка по ключу
    • 3. Двойная перестановка
    • 4. Перестановка «Магический квадрат»

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

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

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

    Магическими квадратами называются квадратные таблицы со вписанными в их клетки последовательными натуральными числами от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число. Подобные квадраты широко применялись для вписывания шифруемого текста по приведенной в них нумерации. Если потом выписать содержимое таблицы по строкам, то получалась шифровка перестановкой букв. На первый взгляд кажется, будто магических квадратов очень мало. Тем не менее, их число очень быстро возрастает с увеличением размера квадрата. Так, существует лишь один магический квадрат размером 3 х 3, если не принимать во внимание его повороты. Магических квадратов 4 х 4 насчитывается уже 880, а число магических квадратов размером 5 х 5 около 250000. Поэтому магические квадраты больших размеров могли быть хорошей основой для надежной системы шифрования того времени, потому что ручной перебор всех вариантов ключа для этого шифра был немыслим.

    В квадрат размером 4 на 4 вписывались числа от 1 до 16. Его магия состояла в том, что сумма чисел по строкам, столбцам и полным диагоналям равнялась одному и тому же числу — 34. Впервые эти квадраты появились в Китае, где им и была приписана некоторая «магическая сила».

    Шифрование по магическому квадрату производилось следующим образом. Например, требуется зашифровать фразу: «ПриезжаюCегодня.». Буквы этой фразы вписываются последовательно в квадрат согласно записанным в них числам: позиция буквы в предложении соответствует порядковому числу. В пустые клетки ставится точка.

    После этого шифрованный текст записывается в строку (считывание производится слева направо, построчно): .ирдзегюСжаоеянП При расшифровывании текст вписывается в квадрат, и открытый текст читается в последовательности чисел «магического квадрата» Программа должна генерировать «магические квадраты» и по ключу выбирать необходимый. Размер квадрата больше чем 3х3.

    В настоящее время симметричные шифры — это:

    • 1. блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.
    • 2. поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования. Поточный шифр может быть легко создан на основе блочного (например, ГОСТ 28147-89 в режиме гаммирования), запущенного в специальном режиме.

    Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей» (key schedule). Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.

    Типичным способом построения алгоритмов симметричного шифрования является сеть Фейстеля. Алгоритм строит схему шифрования на основе функции F(D, K), где D — порция данных, размером вдвое меньше блока шифрования, а K — «ключ прохода» для данного прохода. От функции не требуется обратимость — обратная ей функция может быть неизвестна. Достоинства сети Фейстеля — почти полное совпадение дешифровки с шифрованием (единственное отличие — обратный порядок «ключей прохода» в расписании), что сильно облегчает аппаратную реализацию.

    Операция перестановки перемешивает биты сообщения по некоему закону. В аппаратных реализациях она тривиально реализуется как перепутывание проводников. Именно операции перестановки дают возможность достижения «эффекта лавины». Операция перестановки линейна — f(a) xor f(b) == f(a xor b)

    Операции подстановки выполняются как замена значения некоей части сообщения (часто в 4, 6 или 8 бит) на стандартное, жестко встроенное в алгоритм иное число путем обращения к константному массиву. Операция подстановки привносит в алгоритм нелинейность.

    Зачастую стойкость алгоритма, особенно к дифференциальному криптоанализу, зависит от выбора значений в таблицах подстановки (S-блоках). Как минимум считается нежелательным наличие неподвижных элементов S(x) = x, а также отсутствие влияния какого-то бита входного байта на какой-то бит результата — то есть случаи, когда бит результата одинаков для всех пар входных слов, отличающихся только в данном бите.

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

    Большую популярность потоковым шифрам принесла работа Клода Шеннона, опубликованная в 1949 году, в которой Шеннон доказал абсолютную стойкость шифра Вернама(также известного, как одноразовый блокнот). В шифре Вернама ключ имеет длину, равную длине самого передаваемого сообщения. Ключ используется в качестве гаммы, и если каждый бит ключа выбирается случайно, то вскрыть шифр невозможно (т.к. все возможные открытые тексты будут равновероятны). До настоящего времени было придумано немало алгоритмов потокового шифрования. Такие как: A3, A5, A8, RC4,PIKE, SEAL, eSTREAM.

    Простейшая реализация поточного шифра изображена на рисунке. Генератор гаммы выдаёт ключевой поток (гамму): k1, k2, k3,…, kL . Обозначим поток битов открытого текста m1, m2, m3,…, mL . Тогда поток битов шифротекста получается с помощью применения операции XOR: c1, c2, c3,…, cL , где ci=mi (M2) ki. M2 — сложение по модулю 2.

    Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: mi=ci (M2) ki .

    Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

    Методология сравнения потоковых шифров

    Рубрика: Технические науки

    Дата публикации: 05.10.2020 2020-10-05

    Статья просмотрена: 821 раз

    Библиографическое описание:

    Кубрак К. Г., Шалашова А. Ю. Методология сравнения потоковых шифров // Молодой ученый. — 2020. — №20. — С. 163-167. — URL https://moluch.ru/archive/124/34133/ (дата обращения: 12.11.2020).

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

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

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

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

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

    Одним из известнейших первых шифров является, так называемый, шифр Цезаря. Основной идея шифра заключается в том, что каждая буква в сообщении заменяется другой буквой того же алфавита, которая отстоит на заданное число позиций от заменяемой буквы. В частности, если взять значение цикличного сдвига позиции равным 3, то в латинском алфавите буква A будет заменена на D, B на E, …, Z на C. Своей цели такое преобразование достигает — полученный шифр невозможно прочесть. Однако, если сообщение достаточно длинное, то можно сопоставить буквы по частоте появления букв в незашифрованном тексте, к примеру, в русском языке наиболее распространённая буква — о, и для того, чтобы понять величину сдвига, необходимо лишь посчитать частоту появления букв, встречающуюся в зашифрованном тексте.

    Существует три [1] способа устранения данной уязвимости в шифре: омофонический, полиалфавитный и полиграммный шифр.

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

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

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

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


    Обычно, потоковые шифры быстрее и проще в реализации, чем блочные, но всё зависит от конкретных алгоритмов реализации.

    Рассмотрим подробнее способ превращения открытого текста, состоящего из n битов вида m1, m2, …, mn, в шифрованный текст, состоящий, соответственно, из битов с1, c2, …, cn. Генератор гаммы создаёт ключевой поток k1, k2, …, kn, который затем при помощи операции XOR (исключающее ИЛИ) побитово складывается с открытым текстом m1, m2, …, mn. Полученная последовательность и будет являться зашифрованным текстом с1, c2, …, cn, ci = miki, где i = 1..n. Операция расшифрования производится аналогичным образом: зашифрованный текст побитово складывается при помощи операции XOR с ключевым потоком, mi = ciki, где i = 1..n.

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

    Последовательные биты ключевой последовательности генерируются на основе внутреннего состояния генератора. Это состояние может быть изменено двумя способами:

    ‒ независимо от открытого или зашифрованного текста, в таком случае шифр называется синхронным;

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

    Рис. 1. Принцип работы синхронных потоковых шифров

    Рис. 2. Принцип работы самосинхронизирующихся потоковых шифров

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

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

    Вектор инициализации — случайная величина, изменяющаяся при каждой новой сессии работы шифра. [4] Вектор инициализации смешивается с ключом для формирования эффективного ключа в предстоящей сессии работы шифра, называемого сессионным ключом. Различные сессионные ключи генерируют различные ключевые последовательности, даже если используется один и тот же ключ в различных сессиях.

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

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

    ‒ Длина эффективного ключа. Данная характеристика важна тем, что в зависимости от области применения, на используемый шифр накладываются ограничения, связанные с ГОСТ. Измеряется в битах.

    ‒ Длина вектора инициализации в битах.

    ‒ Скорость обработки 1 байта открытого текста, измеряется в количестве тактовых сигналов микропроцессора, обрабатывающего данные в соответствие с алгоритмом. На разных микропроцессорах может отличаться, поэтому для разных шифров следует проводить измерения для одного и того же микропроцессора.

    Последняя величина может быть не указана явно, но, имея в распоряжении алгоритм, её можно довольно просто вычислить.

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

    Сравнение некоторых шифров

    В таблице, представленной ниже, приводится пример сравнения потоковых шифров по предложенным характеристикам. Сравниваемые шифры — RC4, Salsa20, HC-256 и SOSEMANUK.

    Cравнение шифров

    Наименование

    Дата создания

    Длина ключа, бит

    Вектор инициа­лизации, бит

    Скорость обработки 1 байта текста, число тактовых сигналов

    Наиболее значимые атаки

    Вычисли­тельная сложность атаки

    Потоковые шифры

    Общие сведений о потоковых шифрах.

    Потоковые шифры представляют собой разновидность гаммирова- ния и преобразуют открытый текст в шифрованный последовательно по 1 биту. Генератор ключевой последовательности, иногда называемый генератором бегущего ключа, выдает последовательность бит kj, k2 . kiy . Эта ключевая последовательность складывается по модулю 2 с последовательностью бит исходного текста р, р2 ••., Pi . для получения шифрованного текста:

    На приемной стороне шифрованный текст складывается по модулю 2 с идентичной ключевой последовательностью для получения исходного текста:

    Стойкость системы целиком зависит от внутренней структуры генератора ключевой последовательности. Если генератор выдает последовательность с небольшим периодом, то стойкость системы будет невелика. Напротив, если генератор будет выдавать бесконечную последовательность истинно случайных (не псевдослучайных!) бит, то мы получим одноразовый блокнот с идеальной стойкостью.

    Реальная стойкость потоковых шифров лежит где-то посредине между стойкостью простой моноалфавитной подстановки и одноразового блокнота. Генератор ключевой последовательности выдает поток битов, который выглядит случайным, но в действительности является детерминированным и может быть в точности воспроизведен на приемной стороне. Чем больше генерируемый поток похож на случайный, тем больше усилий потребуется от криптоаналитика для взлома шифра.

    Однако, если каждый раз при включении генератор будет выдавать одну и ту же последовательность, то взлом криптосистемы будет тривиальной задачей. Перехватив два шифрованных текста, злоумышленник может сложить их по модулю 2 и получить два исходных текста, сложенных также по модулю 2. Такую систему раскрыть очень просто. Если же в руках противника окажется пара исходный текст-шифрованный текст, задача вообще становится тривиальной.

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

    Потоковые шифры наиболее пригодны для шифрования непрерывных потоков данных, например, в сетях передачи данных.

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

    Потоковые шифры

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

    Режим гаммирования для поточных шифров

    Простейшая реализация поточного шифра изображена на рисунке. Генератор гаммы выдаёт ключевой поток (гамму):

    Поток битов открытого текста:

    Гамма шифра и поток битов открытого текста подвергаются операции XOR. Так получается поток битов шифротекста: , где

    Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом:

    Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

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


    Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

    Заметим, что выполняться синхронизация должна так, чтобы ни одна часть потока ключей не была повторена. Поэтому переводить генератор в более раннее состояние не имеет смысла.

    • отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);
    • предохраняют от любых вставок и удалений шифротекста, так как они приведут к потере синхронизации и будут обнаружены.
    • уязвимы к изменению отдельных бит шифрованного текста. Если злоумышленнику известен открытый текст, он может изменить эти биты так, чтобы они расшифровывались, как ему надо.
  • Самосинхронизирующиеся поточные шифры

    Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста.

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

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

    • Размешивание статистики открытого текста. Так как каждый знак открытого текста влияет на следующий шифротекст, статистические свойства открытого текста распространяются на весь шифротекст. Следовательно, АПШ может быть более устойчивым к атакам на основе избыточности открытого текста, чем СПШ.
    • распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);
    • чувствительны к вскрытию повторной передачей.
  • Большинство существующих шифров с секретным ключом однозначно могут быть отнесены либо к поточным, либо к блочным шифрам. Но теоретическая граница между ними является довольно размытой. Например, используются алгоритмы блочного шифрования в режиме поточного шифрования (пример: для алгоритма DES режимы CFB и OFB). Рассмотрим основные различия между поточными и блочными шифрами не только в аспектах их безопасности и удобства, но и с точки зрения их изучения в мире:

    • важнейшим достоинством поточных шифров перед блочными является высокая скорость шифрования, соизмеримая со скоростью поступления входной информации; поэтому, обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных.
    • в синхронных поточных шифрах (в отличие от блочных) отсутствует эффект размножения ошибок, то есть число искаженных элементов в расшифрованной последовательности равно числу искаженных элементов зашифрованной последовательности, пришедшей из канала связи.
    • структура поточного ключа может иметь уязвимые места, которые дают возможность криптоаналитику получить дополнительную информацию о ключе (например, при малом периоде ключа криптоаналитик может использовать найденные части поточного ключа для дешифрования последующего закрытого текста).
    • ПШ в отличие от БШ часто могут быть атакованы при помощи линейной алгебры (так как выходы отдельных регистров сдвига с обратной линейной связью могут иметь корреляцию с гаммой). Также для взлома поточных шифров весьма успешно применяется линейный и дифференциальный анализ.

    Теперь о положении в мире:

    • в большинстве работ по анализу и взлому блочных шифров рассматриваются алгоритмы шифрования, основанные на стандарте DES; для поточных же шифров нет выделенного направления изучения; методы взлома ПШ весьма разнообразны.
    • для поточных шифров установлен набор требований, являющихся критериями надёжности (большие периоды выходных последовательностей, постулаты Голомба, нелинейность); для БШ таких чётких критериев нет.
    • исследованием и разработкой поточных шифров в основном занимаются европейские криптографические центры, блочных – американские.
    • исследование поточных шифров происходит более динамично, чем блочных; в последнее время не было сделано никаких заметных открытий в сфере DES-алгоритмов, в то время как в области поточных шифров случилось множество успехов и неудач (некоторые схемы, казавшиеся стойкими, при дальнейшем исследовании не оправдали надежд изобретателей).

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

    1. Cистемно-теоретический подход основан на создании для криптоаналитика сложной, ранее неисследованной проблемы.
    2. Cложно-теоретический подход основан на сложной, но известной проблеме (например, факторизация чисел или дискретное логарифмирование).
    3. Информационно-технический подход основан на попытке утаить открытый текст от криптоаналитика – вне зависимости от того сколько времени потрачено на дешифрование, криптоаналитик не найдёт однозначного решения.
    4. Рандомизированный подход основан на создании объёмной задачи; криптограф тем самым пытается сделать решение задачи расшифрования физически невозможной. Например: криптограф может зашифровать некоторую статью, а ключом будут указания на то, какие части статьи были использованы при шифровании. Криптоаналитику придётся перебирать все случайные комбинации частей статьи, прежде чем ему повезёт, и он определит ключ.

    Теперь приведём теоретические критерии Райнера Рюппеля для проектирования поточных систем:

    • длинные периоды выходных последовательностей
    • большая линейная сложность
    • диффузия – рассеивание избыточности в подструктурах, “размазывание” статистики по всему тексту
    • каждый бит потока ключей должен быть сложным преобразованием большинства битов ключа
    • критерий нелинейности для логических функций.

    До сих пор не было доказано, что эти критерии необходимы или достаточны для безопасности поточной системы шифрования.

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

    Все методы криптоанализа поточных шифров обычно подразделяют на 3 класса:

    Атаки путём полного перебора(перебор всех возможных вариантов). Сложность полного перебора зависит от количества всех возможных решений задачи (размера пространства ключей или пространства открытого текста). Этот вид атаки применим ко всем видам систем поточного шифрования. При разработке систем шифрования разработчики стремятся сделать так, чтобы этот вид атак был наиболее эффективным по сравнению с другими существующими методами взлома.

    Делятся на два подкласса:

    1. Метод криптоанализа статистических свойств шифрующей гаммы: направлен на изучение выходной последовательности криптосистемы; криптоаналитик пытается установить значение следующего бита последовательности с вероятностью выше вероятности случайного выбора с помощью различных статистических тестов.
    2. Метод криптоанализа сложности последовательности: криптоаналитик пытается найти способ генерировать последовательность, аналогичную гамме, но более просто реализуемым способом.

    Оба метода используют принцип линейной сложности.

    Этот вид атак рассматривается в предположении, что криптоаналитику известны описание генератора, открытый и соответствующий закрытый тексты. Задача криптоаналитика определить использованный ключ (начальное заполнение регистров).

    Виды аналитических атак, применяемые к синхронным поточным шифрам:

    «Облегчённые» поточные шифры

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

    Ниже приведен список рассматриваемых в данной статье «легковесных» криптографических алгоритмов, основанных на поточном шифровании и основные механизмы реализации. Но прежде чем мы перейдем к их описанию, необходимо ознакомиться с основными реализациями, которые используются в аппаратной части таких алгоритмов: LFSR и FCSR.

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

    Contents

    Регистр сдвига с линейной обратной связью — регистр сдвига битовых слов, у которого значение входного (вдвигаемого) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами. Применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

    Рисунок 1. Регистр сдвига с линейной обратной связью


    В течение каждого такта регистр сдвига с линейной обратной связью выполняет следующие операции:

    • читается бит, расположенный в ячейке L — 1; этот бит является очередным битом выходной последовательности;
    • функции обратной связи вычисляет новое значение для ячейки 0, используя текущие значения ячеек;
    • содержимое каждой i-й ячейки перемещается в следующую ячейку i+1, где i = 0;1;. ;L-2;
    • в ячейку 0 записывается бит, ранее вычисленный функцией обратной связи.

    Если функция обратной связи выполняет логическую операцию «XOR» (исключающее ИЛИ), значения бит (ячеек) могут быть вычислены по следующим формулам:

    Впервые идея использования регистра сдвига с обратной связью по переносу (FCSR) для создания поточного фильтра была предложена Клаппером и Горески в 1994 году. Позднее ими был разработан алгоритм такого шифра. Один FCSR без подключения линейного компонента не может быть использован в качестве поточного шифра, так как легко дешифруется. В 2002 году был предложен самосинхронизующийся поточный шифр, основанный на совместном использовании FCSR и LFSR. Позднее он был подвергнут атаке с выбором шифротекста. В 2005 году Арно и Бергер предложили идею совместного использования FCSR и линейного фильтра для создания поточного шифра, который получил название F-FCSR (Filtered FCSR). Позже ими были предложены 4 алгоритма, реализующих эту идею: F-FCSR-SF1, F-FCSR-SF, F-FCSR-DF1 и F-FCSR-DF8. Первые два использовали статические фильтры, последние — фильтры, зависящие от ключа. Позже была выявлена слабость всех этих алгоритмов перед различными видами атак. В 2005 Терри Бергер, Франсуа Арноль и Седрик Лараду предложили два шифра на основе F-FCSR для участия в конкурсе eSTREAM: F-FCSR-H для аппаратной реализации и F-FCSR-8 для программной. В результате последующих испытаний у первоначальных версий F-FCSR-H и F-FCSR-8 были найдены уязвимости, которые позже были исправлены в версиях F-FCSR-H v.2 и F-FCSR-16. Улучшенный вариант F-FCSR-H v.2 стал финалистом eSTREAM. Но после обнаружения уязвимости был исключен из eSTREAM Portfolio (rev.1).

    Рисунок 2. Конфигурация Галуа для FCSR

    FCSR реализуется в двух конфигурациях: Галуа и Фиббоначи. В F-FCSR используется конфигурация Галуа, так как она эффективней. Вводятся следующие обозначения:

    1. q — целостность соединения (connection integer) — отрицательное нечетное целое число, удовлетворяющее следующим условиям:
      • T = (|q| − 1)/2 — простое, 2T — период битовой последовательности p/q
      • Число единиц в двоичном представлении числа (1 − q)/2 порядка n/2
    2. p — параметр, зависящий от ключа, такое, что 0 n n+1
    3. d: d = (1 − q)/2, в двоичной записи , di = <0, 1>, dn-1 = 1
    4. M — n-разрядный главный регистр, значения его i-го разряда, .
    5. C — l-разрядный регистр сдвига, l + 1 — число единиц в двоичной записи d, .
    6. (m, c) — состояние FCSR

    Если (m, c) — состояние FCSR в момент времени t, , то — двоичное представление p/q, где p = m + 2c.

    Семейство поточных шифров Grain

    В этом разделе описывается семейство поточных шифров Grain. Главным его отличием от остальных алгоритмов, представленных на проекте eSTREAM, является чрезвычайно малая аппаратная реализация. В течение этого проекта (eSTREAM) начальная версия v0 была доработана после некоторых наблюдений Berbain. Окончательный вариант Grain известен как Grain v1.

    Как и другие шифры, Grain v1 достаточно современен для того чтобы использовать публичные, т.е. общедоступные векторы инициализации (IV), хотя и 80-битные. Признавая необходимость в 128-битных ключах, Hell предложил 128-битные ключи для Grain, в котором используются 96-битные векторы инициализации. Принцип тот же, что и у 80-битной версии, но особенностью является нелинейная часть шифра, а именно меньшая степень чем в v0.

    Общая идея Grain состоит в использовании ключа размера |k|; NFSR и LFSR аналогично c размером |k| и выходной функции, которая использует состояние обоих регистров. LFSR обеспечивает функционирование NFSR путем передачи данных. В NFSR поступает ключ, а LFSR — вектор инициализации, дополняемый константой. После этого ключ и вектор инициализации загружаются, но перед генерацией гаммы состояние определяется путем 2 · |k| обновлений, где происходит обратная связь выходной последовательности в LSRF. После инициализации начинается генерирование гаммы.

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

    Grain v1

    Поточный шифр Grain был разработан Мартином Хеллом, Томасом Йоханссоном и Вилли Мейером. Их основной целью было разработать алгоритм, который очень легко реализовать в аппаратной части и который достаточно мал по площади. Это бит-ориентированный синхронный поточный шифр, который означает, что ключ генерируется независимо от входного текста. В общем, поточный шифр состоит из двух этапов.

    Первый этап — это этап инициализации внутреннего состояния с помощью секретного ключа и вектора инициализации. После этого состояние повторно обновляется и используется для генерации гаммы. Основные элементы поточного шифра Grain, как было упомянуто выше, — это два 80-битных регистров сдвига, где один имеет линейную обратную связь (LFSR), а другой нелинейную обратную связь (NFSR). Размер ключа составляет 80-бит, в образовании которого используется 64-бита вектора инициализации. К сожалению, первоначальная версия Grain v0 имела уязвимость в функции вывода, которую обнаружили во время первого этапа оценки. В Grain v1 проблема с ветором инициализации была решена.

    Основную структуру алгоритма можно увидеть на рисунке 3. Два многочлена степени 80 f(x) и g(х) используются в качестве функции обратной связи для регистров сдвига с обратной связью LFSR и NFSR. Функция выхода h(х) использует в качестве входной последовательности биты из обоих регистров сдвига с обратной связью. Кроме того, семь бит из NFSR XOR-ятся и результат прибавляется к функции h(x). Этот результат используется в фазе инициализации в качестве дополнительной обратной связи LFSR и NFSR (серые линий на рисунке обозначают эту обратную связь). Во время нормальной работы это значение используется в качестве гаммы.

    Рисунок 3. Схема поточного шифра Grain v1

    Аппаратный модуль Grain v1 был реализован с 16-битным AMBA APB интерфейсом и технологическим процессом в 0,35 мкм на CMOS. Этот интерфейс подходит к 16-битной архитектуре. Причиной для этой реализации на 16-битах слова является подход с низким энергопотреблением. Подробности итераций прохода данных представлены на рисунке 4. Видно, что регистры сдвига обратной связи NFSR и LFSR обрабатывают 16 бит за такт. Только один регистр действует в тот же момент времени, что облегчает ввод ключа и вектор инициализации, потому что те же самые 16 проводов подключены ко всем регистрам. Кроме того, значительно уменьшается среднее потребление энергии. Это происходит за счет наличия временного регистра, который хранит промежуточные результаты. Кроме того все комбинационные схемы, как функции обратной связи g, f и h должны быть реализованы в шестнадцатеричной системе счисления. Входы этих функции — это выбранные биты из регистров, которые не показаны подробно на этом рисунке. h функция также включает в себя XOR операции выходной функции. Выход модуля уже зарегистрирован и вместо гаммы и зашифрованного результата входных данных хранится в регистре. Вместо того, чтобы мультиплексор сам выбирал корректную обратную функцию для временного регистра, команда AND используются для включения и отключения соответствующих входов. Производство 16-битного результата шифрования требует 13 тактов после инициализации.

    Рисунок 4. Схема обработки данных поточного шифра Grain v1

    Ниже представлена таблица со значениями GE для основных элементов реализации Grain v1.

    Таблица 1. Компоненты реализации Grain v1

    Компонент реализации Минимальная площадь (radix — 1), GE Минимальная прощадь (radix — 16), GE
    NFSR + LFSR (160 бит) 1,275 1,130
    Временный регистр 85
    Регистр выхода 50 150
    Комбинация логики с misc 315 1,835
    Контроллер (FSM) 120 160
    Суммарно 1,760 3,360

    Trivium

    Разработчиками поточного шифра Trivium являются Кристоф де Каниэр и Барт Пренель. Это аппаратно-ориентированный синхронный поточный шифр, который был разработан для исследования того, насколько простым должен быть шифр, чтобы не жертвовать его безопасностью. Можно генерировать до 2^64 битов гаммы из 80-битного ключа и 80 битов вектора инициализации. Состояние состоит из 288 бит которые обозначены как S0, S2, . s287. В течение инициализации, которая не показана на схеме, ключ и вектор не загружаются в состояние и в то же время обновление фнкции происходит 1152 раз без использования выхода для гаммы. В описании алгоритма, N используется для определения количества выходных битов поточного шифра.

    Реализация модуля Trivium имеет тот же 16-битный AMBA APB интерфейс, как и Grain v1. Использование 16-битного процессора также мотивировано энергосбережением, которое является необходимым критерием для «облегчённых» шифров. Рисунок 5 показывает подробную информацию об архитектуре Trivium. «Коробки» с входящем полем comb являются комбинационными логическими элементами алгоритма, которые используются для обновления состояния в соответствии со спецификацией. 288 бит для определения состояния разделяются в 16-разрядные регистры. Кроме того необходимо два временных регистра для хранения промежуточных результатов. Выходной регистр снова используется для непосредственного применения операции XOR гаммы с входным значением. Во время инициализации ключ, вектор инициализации и константы загружаются в регистры. Затем комбинационные схемы используются для обновления регистров, где также используются временные регистры для предотвращения перезаписи необходимых значений. Генерация 16-битной гаммы требует 22 такта после фазы инициализации.

    Рисунок 5. Схема обработки данных поточного шифра Trivium

    Ниже представлена таблица со значениями GE для основных элементов реализации Trivium.

    Таблица 2. Компоненты реализации Trivium

    Компонент реализации Минимальная площадь (radix — 1), GE Минимальная прощадь (radix — 16), GE
    Регистры состояния (288 бит) 1,840 2,040
    Временный регистр 200
    Регистр выхода 50 150
    Комбинация логики с misc 290 410
    Контроллер (FSM) 210 290
    Суммарно 2,390 3,090

    Bean является поточным шифром, который имеет некоторые сходства с Grain: The NFSR и LFSR у второго заменяются на два FCSR. Существует определенный смысл этой замены, так как LFSR в Grain используется для обеспечения большего периода последовательности и случайности, в то время как NFSR используется для обеспечения нелинейности. A FCSR комбинируют обеспечение обоих свойств LFSR и NFSR, плюс остаются такими же компактными на аппаратном уровне. Помимо этого Bean использует реализацию на архитектуре Фибоначчи, в отличие от Grain, который реализован на архитектуре Галуа.

    На рисунке 6 представлена архитектура реализации поточного шифра Bean.

    Рисунок 6. Архитектура Фибоначчи в поточном шифре Bean

    У обоих регистров сдвига размер составляет 80 бит, как и размер ключа. Состояние первого FCSR 1 обозначается , а состояние FCSR 2 , которые определяются следующим образом:

    Обновление состояния FCSR 1:

    Обновление состояния FCSR 2:

    Функция используется для создания самой гаммы. Используется S-box, на вход которого подается 6 бит, а на выходе 4. Биты гаммы получаются из :

    А функция имеет вид:

    Hummingbird

    В отличие от существующих легких криптографических примитивов, в которых присутствует либо блочный шифр, либо поточный шифр, Hummingbird является сочетанием двух вышеупомянутых шифров с 16-битным размером блока, 256-битным размером ключа, и 80-битным внутренним состоянием. Размер ключа и внутреннего состояния Hummingbird обеспечивает уровень безопасности, адекватный для многих приложений RFID. Для ясности, мы используем обозначения, перечисленные в таблице 1 описания алгоритма. На рисунке 7 показана структура верхнего уровня шифрования Hummingbird в процессе зашифрования.

    Рисунок 7. Структура верхнего уровня шифрования Hummingbird

    Общая структура алгоритма шифрования Hummingbird состоит из четырех 16-битных блочных шифров — четырех 16-битных регистров внутреннего состояния RS1,RS2,RS3 и RS4, и 16-ступенчатого LFSR. 256-битный секретный ключ K делится на четыре 64-битных подключа k1,k2,k3 и k4, которые используются в четырех блочных шифров. 16-битный блок открытого текста шифруется взятием по модулю добавлением и содержащий первый регистр RS1 внутреннего состояния. Результат сложения затем шифруется с первым блочным шифром . Эта процедура повторяется таким же образом, еще три раза, и выход является зашифрованным текстом . Кроме того, состояние четырех регистров внутреннего состояния также будут обновлены непредсказуемым способом, основанным на их текущих состояниях, выходах первых трех блочных шифров, и состоянии LFSR. Процесс расшифровки происходит по схеме аналогичной шифрованию.

    На практике в Hummingbird используют четыре 16-битных случайные которые в первую очередь выбираются для инициализации четырех внутренних состояний регистров (i = 1, 2, 3, 4),далее следуют четыре последовательных шифрования сообщения (RS1+ RS3)mod2 с Hummingbird, работающим в режиме инициализации. Последний 16-битный зашифрованный текст используется для инициализации LFSR. Кроме того, 13тый бит LFSR всегда имеет значение, чтобы предотвратить нулевой регистр. LFSR также «шагнул» с целью обновлениярегистра внутреннего состояния RS2.

    Четыре одинаковых 16-битных блочных шифра используются в последовательном порядке в схеме шифрования Hummingbird.16-битный блочный шифр является типичной SP-сетью с 16-битным размером блока и 64-битным ключом.Он состоит из 4 итераций, и на последней итерации включает в себя только функцию смешения содержимого ключа и шаги замещения S-бокса. Как и в любой другой SP-сети, одна очередная итерация состоит из трех этапов: шаг смешения ключа, слой замены и слой перестановки. В этом 16-битном блочном шифре для смешения ключа используются простое исключение или операция, с целью эффективной реализации в программной и аппаратной части.

    Глоссарий

    Библиографический указатель

    Перейти к списку литературы по разделу «Облегчённые» поточные шифры.

    Илон Маск рекомендует:  Атрибут minlength в HTML
    Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL