Криптография. 1 История криптографии

• Название: 1 История криптографии
• Анкор: Криптография
• Дата: 17.12.2019
• Размер: 251.1 Kb.
• Имя файла: Криптография .docx
• Тип: Документы; #100728
• страница: 5 из 6

Дополнение до целого блока

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

Поэтому на практике применимо решение, стандартизованное как «Метод дополнения 2» в ISO/IEC 9797-1, добавляющее единичный бит в конец сообщения и заполняющее оставшееся место нулями.В этом случае была доказана стойкость к подобным атакам.

№12 Построение симметричных алгоритмов(DES,3DES,thofish)

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

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

Алгоритм DES

Алгоритм DES (Data Encryption Sdandard) разработан IBM под именем Lucifer, в 1977 году после некоторых модификаций принят как стандарт

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

Существенным недостатком алгоритма DES является короткий ключ (56 значащих битов), что при современном уровне развития компьютерных средств означает высокую вероятность его взлома путем прямого перебора значений ключа

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

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

Алгоритм TripleDES

3DES – TripleDES – алгоритм, использующий ключ длиной 168 бит, состоящий из трёх блоков по 56 бит. Этот алгоритм тоже поточный и тоже блоковый. Блок составляет, как и у DES, 64 бита. Для зашифровывания 64 бит текста три раза применяется алгоритм DES каждый раз с новой третью ключа. Конечно, такой шифр сломать труднее, но есть предположение, что криптостойкость его не сильно выше, чем у DES. При этом очевидно, что производительность шифрующего оборудования сильно падает, по сравнению с DES (примерно в три раза)

№13 Российский стандарт шифрования ГОСТ 28147-89
ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название — «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).

Принцип работы алгоритма

Алгоритм принципиально не отличается от DES. В нем также происходят циклы шифрования (их 32) по схеме Фейстеля (Рис. 2.9.).



Рис. 2.9. Раунды шифрования алгоритма ГОСТ 28147-89.

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k₁…k₈. Ключи k₉…k₂₄ являются циклическим повторением ключей k₁…k₈ (нумеруются от младших битов к старшим). Ключи k₂₅…k₃₂ являются ключами k₁…k₈, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A₃₃ и B₃₃ склеиваются (следует обратить внимание на то, что старшим битом становится A₃₃, а младшим - B₃₃) – результат есть результат работы алгоритма.

Функция f(A_i,K_i) вычисляется следующим образом: A_i и K_i складываются по модулю 2³², затем результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, т. е. столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, т.е. разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовала используемые в Интернет узлы замены.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей k_i.

Режимы работы алгоритма ГОСТ 28147-89

Алгоритм ГОСТ 28147-89 имеет четыре режима работы.

1.Режим простой замены принимает на вход данные, размер которых кратен 64-м битам. Результатом шифрования является входной текст, преобразованный блоками по 64 бита в случае зашифрования циклом «32-З», а в случае расшифрования — циклом «32-Р».

2.Режим гаммирования принимает на вход данные любого размера, а также дополнительный 64-битовый параметр — синхропосылку. В ходе работы синхропосылка преобразуется в цикле «32-З», результат делится на две части. Первая часть складывается по модулю 2³² с постоянным значением 1010101₁₆. Если вторая часть равна 2³²-1, то её значение не меняется, иначе она складывается по модулю 2³²-1 с постоянным значением 1010104₁₆. Полученное объединением обеих преобразованных частей значение, называемое гаммой шифра, поступает в цикл «32-З», его результат порязрядно складывается по модулю 2 с 64-разрядным блоком входных данных. Если последний меньше 64-х разрядов, то лишние разряды полученного значения отбрасываются. Полученное значение подаётся на выход. Если ещё имеются входящие данные, то действие повторяется: составленный из 32-разрядных частей блок преобразуется по частям и так далее.

3.Режим гаммирования с обратной связью также принимает на вход данные любого размера и синхропосылку. Блок входных данных поразрядно складывается по модулю 2 с результатом преобразования в цикле «32-З» синхропосылки. Полученное значение подаётся на выход. Значение синхропосылки заменяется в случае зашифрования выходным блоком, а в случае расшифрования — входным, то есть зашифрованным. Если последний блок входящих данных меньше 64 разрядов, то лишние разряды гаммы (выхода цикла «32-З») отбрасываются. Если ещё имеются входящие данные, то действие повторяется: из результата зашифрования заменённого значения образуется гамма шифра и т.д.

4.Режим выработки имитовставки принимает на вход данные, размер которых составляет не меньше двух полных 64-разрядных блоков, а возвращает 64-разрядный блок данных, называемый имитовставкой. Временное 64-битовое значение устанавливается в 0, далее, пока имеются входные данные, оно поразрядно складывается по модулю 2 с результатом выполнения цикла «16-З», на вход которого подаётся блок входных данных. После окончания входных данных временное значение возвращается как результат.

Криптоанализ шифра

В шифре ГОСТ 28147-89 используется 256-битовый ключ и объем ключевого пространства составляет 2²⁵⁶. Ни на одном из существующих в настоящее время компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28147-89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2⁵⁶.

Существуют атаки и на полнораундовый ГОСТ 28147—89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма, использует слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147—89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако, сильные таблицы замен делают такую атаку абсолютно непрактичной.

Отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147—89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифротекстов с достаточно низкой сложностью.

В 2004 году группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7% 12 бит секретного ключа. Для атаки требуется 2³⁵ выбранных открытых текстов и 2³⁶ операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма.

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. От качества этой таблицы зависит качество шифра. При "сильной" таблице замен стойкость шифра не опускается ниже некоторого допустимого предела даже в случае ее разглашения. И наоборот, использование "слабой" таблицы может уменьшить стойкость шифра до недопустимо низкого предела. Никакой информации по качеству таблицы замен в открытой печати России не публиковалось, однако существование "слабых" таблиц не вызывает сомнения - примером может служить "тривиальная" таблица замен, по которой каждое значение заменяется на него самого. В ряде работ ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом).

№14 Стандарт шифрования США AES

Понимание того, что стандарт DES больше не соответствует всем требованиям заставило правительство Соединенных Штатов искать ему замену. После открытого конкурса, продолжающегося несколько лет, в 2001-м году, AES был принят в качестве стандарта Соединенных Штатов. AES использует комбинацию симметрических шифров и 128, 192, или 256-битный ключ, обеспечивающий более усиленную защиту чем DES. Хотя в AES были обнаружены некоторые потенциальные уязвимости, большей частью теоретические, когда шифры стало легче взломать в ситуации, когда они не были правильно применены, нежели в случае грубой силовой атаки, когда необходимо проверять каждую возможную ключевую комбинацию.

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

№15 Принцип построения и свойства хэш-функций.

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

Простейшим примером хеш-функции, преобразующей любую последовательность байтов в один байт, является следующая:
y=(a AND NOT e AND NOT u) OR (NOT a AND NOT e AND u) OR (NOT a AND e AND NOT u),
где:
a, e, u- аргументы,
OR - дизъюнкции,
AND - конъюнкции.
Эта функция равна единице только тогда, когда один из ее аргументов равен единице. Пусть задана битовая последовательность. которая состоит из трех байтов. Она для удобства использования записана в три строки:
10 100 100
01 100 011
01 010 110
Определяя поразрядно функцию "y", получаем байт:
10 010 001.
Хеш-функция позволяет преобразовывать код ключа базы данных в ее адрес. Это дает возможность так размещать элементы данных в памяти, что их затем несложно будет найти. Хеш-функции также широко используются при шифровании.


Алгоритм применения хэш-функции:

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

• полученный дайджест шифруется закрытым ключом отправителя (подписывается ЭЦП) и пересылается получателю вместе с сообщением;

• получатель расшифровывает дайджест сообщения открытым ключом отправителя;

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

Обобщенная схема хэш – функции



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

Дополнения до блока требуемой длины возможно: нулями, пробелами, иными символами, вычисленными по определенным правилам значениями.

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

System.Security.Cryptography. PaddingMode (режимы дополнения).

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

 

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

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

Таким образом, происходит последовательная обработка входных блоков данных.

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



Пример получения хэш-свертки для текста произвольной длины:



№16 Криптографическая стойкость. Теоретико-информационный подход к оценке криптостойкости шифров