Симметричное шифрование Поточные шифры

Абсолютно стойкий шифр. Гаммирование

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

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

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

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

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

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

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

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

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

В самосинхронизирующихся поточных шифрах элементы входной последовательности зашифровываются с учетом N предшествующих элементов, которые принимают участие в формировании ключевой последовательности. Самосинхронизирующиеся поточные шифры имеют ограниченную память на свои предыдущие состояния. При потере одного или нескольких знаков шифр сам «восстановит» верное состояние через несколько символов. Это зависит от того, сколько предыдущих состояний шифра используется для зашифрования текущего элемента открытого текста.

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

Шифры с гаммой, зависящей только от ключа и номера такта шифрования (см. табл. 1 правый столбец верхняя строка – СИНХРОННЫЕ), получили наибольшее распространение в современной практике.

Генераторы псевдослучайных чисел на основе сдвиговых регистров с обратной связью Сдвиговый регистр с обратной связью состоит из двух частей: собственно n-битного сдвигового регистра и устройства обратной связи

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

Линейный сдвиговый регистр с обратной связью Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register – LFSR). Обратная связь в этом устройстве реализуется просто как сумма по модулю 2 всех (или некоторых) битов регистра. Биты, которые участвуют в обратной связи, образуют отводную последовательность.

4-битовый LFSR с отводом от первого и четвертого разрядов

Нелинейные поточные шифры Фильтрующие - строятся на базе одного ЛРС созданием от его ячеек дополнительных отводов, никак не связанных с отводами обратной связи. Значения, получаемые по этим отводам, смешиваются на основе какой-либо нелинейной функции фильтра. Бит-результат данной функции и подается на выход схемы как очередной бит гаммы.

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

Комбинирующий поточный шифр с элементами памяти

Динамические шифры строятся также на базе нескольких ЛРС, но объединяют их не на равноправных условиях, а по схеме "начальник- подчиненный".

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

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

Потенциально любой шифр замены можно описать полной таблицей соответствий между входными и выходными данными. Но для того чтобы описать только одно отображение над 64-битным блоком (то есть алфавитом из 2 64 элементов) требуется 64×2 64 = 2 70 бит запоминающего устройства, а ведь это отображение будет применено только при каком-то одном конкретном значении ключа. Поэтому современный блочный шифр это закон, описывающий данное отображение алгоритмически.

Количество бит в обрабатываемом блоке называется разрядностью блока, количество бит в ключе размером ключа алгоритма. Наиболее популярная на сегодняшний день разрядность блока 64 и 128 бит, а количество бит в ключе 128, 192 или 256 бит.

Обратимые операции в блочном шифровании

Необратимые операции в блочном шифровании

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

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

Количество бит в исходном операнде называется разрядностью входа табличной подстановки, количество бит в результате разрядностью выхода. Наиболее часто по такой схеме применяются подстановки 4x4 (читается "четыре на четыре") бита и 8x8 бит. Обратное преобразование (S-Box -1 ), задается на дешифрующей стороне также таблицей и, соответственно, такой же размерности. В тех случаях, когда от подстановки не требуется обратимость, наряду с традиционными применяются подстановки 4x8, 8x32 бита и некоторые другие.

P-блоки Permutation (перестановка) P-блок (блок перестановки) подобен традиционному шифру транспозиции символов. Он перемещает биты. В современных блочных шифрах мы можем найти три типа P-блоков: прямые P-блоки, P-блоки расширения и P- блоки сжатия. Прямой P-блок является обратимым, а P-блоки сжатия и расширения нет.

Структура блочного алгоритма симметричного шифрования. Раунд Одной из наиболее распространенных схем блочных шифров являются сети (англ. network). Блочный шифр, построенный по такой схеме, состоит из многократных повторений, называемых циклами, или раундами (англ. round), нескольких видов операций, называемых слоями. Разбиение всего процесса шифрования на несколько однотипных слоев позволяет: сократить размер программного кода использованием цикла; унифицировать "алгоритмическую формулу" шифрования и, как следствие, упростить проверку стойкости шифра к известным видам криптоатак; сделать шифр легко усложняемым при необходимости (путем увеличения числа раундов); ввести понятие ключей раунда, на которые разбивается весь материал ключа.

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

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

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

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

Предыдущий рисунок показывает простой составной шифр с двумя раундами. На практике составные шифры имеют больше чем два раунда. В каждом раунде проводятся три преобразования: 1.8-битовый текст смешивается с ключом, чтобы сделать символы текста равновероятными (скрыть биты, используя ключ) "отбелить" текст (whiting). Это обычно делается с помощью операции ИСКЛЮЧАЮЩЕЕ ИЛИ слова на 8 битов с ключом на 8 битов. 2. Выходы "отбеливателя" разбиты на четыре группы по 2 бита и подаются в четыре S-блока. Значения битов изменяются в соответствии с построением S-блоков в этом преобразовании. 3. Выходы S-блоков поступают в P-блок, при этом биты переставлены так, чтобы в следующем раунде результат каждого блока поступил на различные входы.

Рассеивание (предыдущий рисунок) а) В первом раунде бит 8, после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующими битами ключа K 1, изменяет два бита (биты 7 и 8) через S-блок 4. Бит 7 переставлен и становится битом 2; бит 8 переставлен и становится битом 4. После первого раунда бит 8 изменяет биты 2 и 4. Во втором раунде бит 2 после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующими битами ключа K 2 изменяет два бита (биты 1 и 2) через S-блок 1. Бит 1 – переставлен и становится битом 6; бит 2 переставлен и становится битом 1. Бит 4 после проведения операции ИСКЛЮЧАЮЩЕЕ ИЛИ с соответствующим битом в K 2 изменяет биты 3 и 4. Бит 3 остается, бит 4 переставлен и становится битом 7. После второго раунда из 8 бит изменены биты 1, 3, 6 и 7. b) Прохождение этих шагов в другом направлении (от зашифрованного текста до исходного текста) показывает, что каждый бит в зашифрованном тексте изменяет исходный текст на несколько битов.

Перемешивание На рисунке показано, как изменение единственного бита в исходном тексте вызывает изменение многих битов в зашифрованном тексте. Рисунок также доказывает нам, что свойство перемешивания может быть получено с помощью составного шифра. Четыре бита зашифрованного текста, биты 1, 3, 6 и 7 преобразованы с помощью трех битов в ключах (бит 8 в K 1 и битах 2 и 4 в K 2 ). Прохождение в обратном направлении показывает, что каждый бит ключа в каждом раунде затрагивает несколько битов в зашифрованном тексте. Отношения между битами зашифрованного текста и ключевыми битами показаны в затененных прямоугольниках.

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

1. Выбирается размер блока данных, который будет зашифрован, за одну итерацию алгоритма шифрования. 2. Затем его делят пополам и работают с каждой из половинок. 3. Если размер левой половинки равен размеру правой, то такую архитектуру, называют классической или сбалансированной сетью Фейстеля. 4. Если же деление блока данных происходит не на равные части, то такой алгоритм называют разбалансированной сетью Фейстеля.

На изображенной схеме буквами L i и R i обозначены левая и правая половинки исходных данных на i-м шаге последовательного преобразования. Каждый такой целый шаг называют раундом шифрования. Функция гаммирования, обозначена через F i, поскольку на каждом раунде может быть использована своя собственная функция. Ключ также имеет индекс i, но уже в силу того, что исходный ключ k может быть преобразован некоторым образом (говорят развернут) в последовательность итерационных ключей, либо подключей, которые используются непосредственно функцией гаммирования.

1. Сначала с помощью функции гаммирования вырабатывают гамма-последовательность, которая зависит от итерационного ключа k i и правой половины данных. 2. После этого левая половинка просто суммируется с полученной гаммой по модулю, например, Затем левая и правая половинки меняются местами. На этом один цикл шифрования заканчивается. 4. Поскольку за один раз обрабатывается только одна половина данных, желательно, чтобы число раундов было кратно двум. В таком случае есть уверенность, что каждая из половинок будет обработана одинаковое число раз. На схеме отображена сеть Фейстеля с четным числом раундов.

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