Шифрсистемы поточного шифрования (синхронные и асинхронные)

⇐ ПредыдущаяСтр 47 из 69Следующая ⇒

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

Синхронные поточные шифры (СПШ)

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

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

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

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

Плюсы:

1. Отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);

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

Минусы:

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

Асинхронные поточные шифры (АПШ) (второе название самосинхронизирующиеся)

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

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

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

Плюсы:

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

Минусы:

1. Распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);

2. Чувствительны к вскрытию повторной передачей.

Итерационные системы блочного шифрования (шифр простого блокнота)

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

Преобразование должно использовать следующие принципы:

1. Рассеивание (diffusion) — то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;

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

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

Блочные шифры бывают двух основных видов:

1. шифры перестановки (transposition, permutation, P-блоки);

2. шифры замены (подстановки, substitution, S-блоки).

Шифр простого блокнота.

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

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

Сеть Фе́ йстеля

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

Алгоритм IDEA

IDEA использует 128-битный ключ и 64-битный размер блока, открытый текст разбивается на блоки по 64 бит. Если такое разбиение невозможно, последний блок дополняется различными способами определённой последовательностью бит. Для избежания утечки информации о каждом отдельном блоке используются различные режимы шифрования. Каждый исходный незашифрованный 64-битный блок делится на четыре подблока по 16 бит каждый, так как все алгебраические операции, использующиеся в процессе шифрования, совершаются над 16-битными числами. Для шифрования и расшифрования IDEA использует один и тот же алгоритм.

Фундаментальным нововведением в алгоритме является использование операций из разных алгебраических групп, а именно:

сложение по модулю

умножение по модулю

побитовое исключающее ИЛИ (XOR).

Эти три операции несовместимы в том смысле, что:

никакие две из них не удовлетворяют дистрибутивному закону, то есть

никакие две из них не удовлетворяют ассоциативному закону, то есть

Применение этих трех операций затрудняет криптоанализ IDEA по сравнению с DES, который основан исключительно на операции исключающее ИЛИ, а также позволяет отказаться от использования S-блоков и таблиц замены. IDEA является модификацией сети Фейстеля.

Шифр Rijndael

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

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

Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции:

ByteSub – табличная подстановка 8х8 бит,

ShiftRow – сдвиг строк в двумерном массиве на различные смещения,

MixColumn – математическое преобразование, перемешивающее данные внутри столбца,

AddRoundKey – добавление материала ключа операцией XOR.

В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.

Схема Вернама.

Шифр Вернама - система симметричного шифрования, изобретённая в 1917 году сотрудниками AT& T Мейджором Джозефом Моборном и Гильбертом Вернамом. Шифр Вернама является системой шифрования, для которой доказана абсолютная криптографическая стойкость.

Для произведения шифртекста открытый текст объединяется операцией «исключающее ИЛИ» с ключом (называемым одноразовым блокнотом или шифроблокнотом).

Так, например, при применении ключа (1 1 1 0 1) на букву «А» (1 1 0 0 0) получаем зашифрованное сообщение (0 0 1 0 1): Зная, что для принимаемого сообщения имеем ключ (1 1 1 0 1), легко получить исходное сообщение той же операцией: Для абсолютной криптографической стойкости ключ должен обладать тремя критически важными свойствами

1. быть истинно случайным;

2. совпадать по размеру с заданным открытым текстом;

3. применяться только один раз.

Недостатки:

1. Для работы шифра Вернама необходима истинно случайная последовательность нулей и единиц (ключ).

2. Проблемой является тайная передача последовательности и сохранение её в тайне.

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

Тем не менее, схема шифроблокнотов достаточно надёжна при ручной шифровке.

Автоматные модели шифров:

Классические модели теории автоматов

Последовательным автоматом (или автоматом с памятью) называется система из пяти элементов

, (1)

где – множество внутренних состояний: –множество входных сигналов (или входной алфавит); – множество выходных сигналов (или выходной алфавит); — функция переходов: – функция выходов.

Если необходимо, в систему (1) добавляется шестой элемент – начальное состояние автомата.

В дальнейшем будем рассматривать только детерминированные последовательные автоматы с конечными множествами А, Xи Y.

Предполагается, что автомат функционирует в дискретные моменты времени t= 1, 2,... В каждый момент времени tавтомат, находясь в определенном состоянии a_tмножества А. воспринимает на входном канале сигнал , выдаёт на выходном канале сигнал и переходит в новое состояние .

Другими словами, автомат S, находясь в начальном состоянии a₁, индуцирует автоматное отображение S_a₁, которое ставит в соответствие входному слову выходное слово . При этом автомат проходит последовательность внутренних состояний .

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

1. Модель Мили (или автомат Мили):

2. Модель Мура (или автомат Мура):

Автоматная модель шифратора

Построим модель шифрующего автомата. Для этого необходимо дать несколько определений.

Шифром (или криптосистемой) называется система из пяти элементов

(4)

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

1. (отсюда следует, что отображение E_kинъективно).

2. , где объединение берется по всем к .

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

(5)

Функциональная модель которой представляется автоматом Мили:

(6)

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

Автомат называется обратным (слева) к автомату , если такое, что выполняется равенство . Далее, пока не оговорено противное, будем рассматривать левую обратимость.

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

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

Инъективность приводит к следующему алгоритму построения обратного автомата:

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

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

Для иллюстрации предложенных алгоритмов и моделей рассмотрим автомат Мили,. заданный таблицами 4, 5. Если произвольное значение сигнала или состояния обозначить прочерком, то автомат S^-1представляется таблицами 6, 7.

В простейшем случае ключом можно считать сам автомат. Пусть a₃ – начальное состояние. В качестве открытого текста рассмотрим последовательность . Тогда закрытый текст очевидным образом определяется по таблицам 4, 5:

Процесс расшифрования проводится по таблицам 6, 7:

Далее сформулируем ряд замечаний.

Одним из преимуществ представленного «автоматного» способа шифрования является то. что одинаковые фрагменты входной последовательности в общем случае шифруются различными блоками. Это видно даже на нашем примере: подпоследовательность x1x1 встречается во входном слове дважды, и ей соответствуют подпоследовательности y2y3 иy1y3 закрытого текста.

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

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

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

⇐ Предыдущая 42 43 44 45 464748 49 50 51 Следующая ⇒