Шифр Хилла.

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

A=0,B=1,C=2,D=3,E=4,F=5,G=6,H=7,I=8,J=9,K=10,L=11,M=12,N=13,O=14,P=15,Q=16,R=17,S=18,T=19,U=20,V=21,W=22,X=23,Y=24,Z=25Ex: M=3

C1=(K11P1+K12P2+K13P3)mod26

C2=(K21P1+K22P2+K23P3)mod26

C3=(K31P1+K32P2+K33P3)mod26

C- символ шифрованного текста.

P- символ открытого текста.

C=KP

K- матрица; K^-1- обратная матрица; K*K^-1=1.

Криптосистема Хилла в общем виде записывается так:

C=E_k(P)=KP; P=D_k(C)=K^-1C=KK^-1P=P.

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

7. Типы криптоанализа шифрованных сообщений. Понятие защищенности шифрованных сообщений.

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

Криптоанализ:

• анализ только шифрованного текста- известен алгоритм и шифрованный текст;

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

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

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

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

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

Критерии защищённости:

• стоимость взлома шифра превышает стоимость зашифрованной информации;

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

8. Классификация шифров по ключевой информации.

Классификация по ключевой информации.

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

В конце ХIХ века голландец А.Кергофф в своей книге, посвященной применению шифров, упомянул, как одну из настоятельных рекомендаций, идею о том, что при раскрытии самого алгоритма преобразований третья сторона не должна ни на шаг приблизиться к сокрытому тексту. Это должно было достигаться базированием всего алгоритма шифрования на небольшом объеме секретной информации, данная идея легла в основу всей современной криптографии и получила название принцип Кергоффа, В противовес тайнописи криптографией с ключом называют сегодня алгоритмы шифрования, в которых сам алгоритм преобразований широко известен и доступен для исследований каждому желающему, но шифрование производится на основе небольшого объема информации- ключа, известного только отправителю и получателю сообщения. В современной криптографии в зависимости от методик размер ключа составляет от 56 до 4096 бит. Естественно, любой криптоалгоритм с ключом можно превратить в тайнопись, просто “зашив” в исходном коде программы некоторый фиксированный ключ и считая закрытым весь алгоритм. А вот обратное преобразование- попытка выделить из тайнописи некий небольшой аргумент-параметр- удастся далеко не всегда.

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

9. Нелинейные поточные шифры. Фильтрующие шифры. Линейный регистр сдвига.

Нелинейные поточные шифры

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

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

Линейные регистры сдвига.

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

Алгоритм такта:

• первый бит из последовательности поступает на выход РЛС- очередная гамма;

• содержимое всех промежуточных ячеек памяти сдвигается на одну позицию вправо;

• в пустую ячейку памяти, которая появилась в результате сдвига у левого края помещается бит, который вычисляется как операция XOR над значением из ячеек ЛРС с определенным номером.

Число бит, охваченных операцией сдвига- разрядность.

Перед использованием ЛРС в ячейках побитно помещают ключ.

10. Комбинирующие поточные шифры. Корреляционно-стойкий комбинирующий шифр.

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

Одной из основных проблем комбинирую шифров является возможность просачивания информации из одного или нескольких ЛРС в выходную гамму. Так, в простейшем примере итоговая шифрующая последовательность порождается по формуле g=аb(bc) Несмотря на то что подобная гамма является сбалансированной, т.е. вероятности появления нулей и единиц в ней совпадают, в нее с неприемлемо большой вероятностью проходит поток бит, порождаемый первым ЛРС. Действительно, вероятность P(g=b)=4/8=1/2, P(g=c)=4/8=1/2, но Р(g=a)=6/8. Это позволяет при несколько большем объеме перехваченной информации, чем это требовалось ранее, проводит на первый ЛРС все те же атаки, что и на одиночный ЛРС. А получив всю необходимую информацию по первому ЛРС, можно либо непосредственно воспользоваться ею для чтения с «домысливанием» открытого текста, либо попытаться узнать больше информации о втором и третьем ЛРС.

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

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

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

12. Динамический поточный шифр.

Динамические шифры строятся также на базе нескольких ЛРС, но объединяют их не на равноправных условиях, а по схеме «начальник-подчиненный». Так, например, бит, порождаемый управляющим регистром, определяет бит, какого из подчиненных ЛРС (первого или второго) будет подан на выход всего алгоритма. Бит от противоположного выбранному регистра просто отбрасывается.

По другой схеме, если на очередном своем шаге управляющий ЛРС генерирует “1”, то бит подчиненного ЛРС, полученный на этом же шаге, поступает на выход системы, а если же управляющий ЛРС выдал “0”, то бит подчиненного регистра просто отбрасывается. Разумеется, возможны и сложные схемы взаимодействия ЛРС и их комбинации с уже описанными методами.

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

13. Определение блочного шифрования. Блок информации. Ключ алгоритма. Абсолютно симметричный блочный шифр.

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

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

КЕУ = 10F5DА54

В принципе блочный шифр как закон отображения.

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

Количество бит в обрабатывающем блоке называется разрядностью блока, количество бит в ключе- размером ключа алгоритма. Наиболее популярная на сегодняшний день разрядность блока- 64 и 128 бит, а размер ключа (128 или 256). В общем виде процесс блочного шифрования описывается формулой:

Z=EnCrypt(X,Key),

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

X =DeCrypt(Z, Key).

В тех случаях, когда и для шифрования и для дешифрования используется одна и та же последовательность действий, т.е. EnCryptDeCryptCrypt и, соответственно Crypt(Crypt (X,Key), Key)=X блочный шифр называется абсолютно симметричным. Подобные шифры обладают преимуществами и недостатками, а их построение на самом деле не такая сложная задача, как может показаться на первый взгляд.

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

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

Основные обратимые криптопримитивы

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

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

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

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

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

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

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

Основные необратимые криптопримитивы:

Параметра V в обратимых и необратимых: Во-первых, конечно же, фиксированные числовые констант. Единственным ограничением, которым всегда пользуются создатели блочных шифров, является логическое обоснование ее выбора. В тех случаях, когда шифр полон фиксированных числовых констант, выбор которых трудно объясним, вполне может появиться подозрение, что создатели планомерно конструировали их для получения каких-либо недокументированных возможностей по взлому шифра. Поэтому, когда применение фиксированных числовых констант выполняет только роль “перемешивания” данных, их обычно выбирают из двоичной записи общеизвестных, не связанных ни с чем величин, например, чисел  (отношение диаметра к длине окружности), е (основание натурального логарифма) или  (золотое сечение или как контрольную сумму какого-либо распространенного текста.

Вторым возможным значением параметра Vявляется материал ключа. Материалом ключа называется блок данных, вычисляемый как основание ключа шифрования и зависящий только от него. В простейшем случае материалом ключа может выступать сам ключ, (если его разрядность совпадает с разрядностью операции) либо произвольная его часть без какой-либо обработки. Однако прямое применение ключа в преобразованиях может привести к раскрытию некоторой информации о нем. Конечно вероятность подобной атаки крайне мала и зависит только от общей структуры шифра, но криптография оперирует и гораздо меньшими рисками, поэтому общепринятым подходом является “перестраховаться и в этом случае”. Для этого в качестве материала ключа обычно используют значения, вычисленные из него по необратимой схеме. При этом лучше всего чтобы любой элемент материала зависел от всех бит ключа- даже при малейшем изменении ключа (например, только в одном бите) должен меняться и весьма значительно каждый блок материала ключа.

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

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

16. Сети блочных шифров, ветви сети, раунд сети, образующая функция. Sp-сеть, kaslt-сеть.

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

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

• сократить размер программного кода использованием цикла;

• унифицировать “формулу” шифрования и, как следствие, упростить проверку стойкости шифра к известным видам криптоатак;

• сделать шифр легко усложняемым при необходимости (путем увеличения числа раундов);

• ввести понятие ключей раунда, на которые разбивается весь материал ключа.

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

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

Более современной модификацией технологии сетей является KASLT-сеть с тремя слоями в каждом раунде. Первый слой- добавление ключа (Key Addition- KA)- производит смешивание данных с ключом раунда. Смешивание производится обычно какой-либо простой операцией- сложением либо ХОR. Второй слой- подстановка (Substitution- S)- производит алгоритмическую или чаще табличную подстановку для обеспечения нелинейных свойств шифра. Третий слой- линейное преобразование (Linear Transformation, LT)- производит активное обратимое перемешивание данных внутри блока. Как видим, по сравнению с SP-сетью здесь добавление ключа вынесено в отдельный слой, разделены линейная и нелинейная часть преобразования, а перемешивание данных производится с помощью быстро реализуемых в программной реализации линейных преобразований.

17. Классическая структура сети Файштеля. Ветви сети, материал ключа, раунд сети, образующая функция.

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

Независимые потоки информации, порожденные из исходного блока, называются ветвями сети. В классической схеме их две. Величины Vi именуются параметрами сети, обычно их роль играет материал ключа. Функция F называется образующей. Оптимальное число раундов для сети Файштеля К- от 8 до 32. Сеть Файштеля обладает тем свойством, что даже если в качестве образующей функции F будет использовано необратимое преобразование, то и в этом случае вся цепочка будет восстановима. Это происходит вследствие того, что для обратного преобразования сети Файштеля не нужно вычислять функцию F-1- и при дешифровании вычисляется только прямое значение F. Обратимость требуется только две операции наложения F на шифруемую в данном раунде ветвь, поэтому здесь чаще всего применяется ХОR, реже- арифметическое сложение.

Более того, как нетрудно заметить, сеть Файштеля, в которой для наложения значения F используется операция ХОR, симметрична. Исключающее ИЛИ обратимо своим же повтором и потому инверсия последнего обмена ветвей делает возможным раскодирование блока той же сетью Файштеля, но только в обратном порядке параметров Vi. Заметим, что для обратимости сети Файштеля не имеет значение, является ли число раундов четным или нечетным числом. В большинстве реализаций сети Файштеля прямое и обратное преобразования производятся одним и тем же фрагментом программного кода, оформленного в виде процедуры, которому в качестве параметра передается вектор величин Vi либо в исходном (для шифрования), либо в инверсном (для дешифрования) порядке.

18. Абсолютно симметричная сеть Файштеля. Модификация сети Файштеля для большего числа ветвей: тип 1- размер блока, ветви сети, материал ключа, раунд сети, образующая функция.

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

Абсолютно симметричная сеть Файштеля

А вот модификацию сети Файштеля для большего числа ветвей применяют гораздо чаще. Это в первую очередь связано с тем, что при больших размерах шифруемых блоков (128 и более бит) становится неудобно работать с математическими функциями по модулю 64 и выше. Как известно основные единицы информации, обрабатываемые процессорами, на сегодняшний день- это байт и двойное машинное слово (32 бита). Поэтому все чаще в блочных криптоалгоритмах встречается сеть Файштеля с 4 ветвями.

19. Модификация сети Файштеля для большего числа ветвей: тип 2 и тип 3- размер блока, ветви сети, материал ключа, раунд сети, образующая функция.

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

Основная часть современных криптоисследований, посвященных сети Файштеля, относится конечно же, к структуре образуюшей функции F и правилу вычисления материала ключа Vi. Из других решений интерес представляют только дополнительные начальные и оконечные преобразования данных («забеливание»)над шифруемым блоком. Подобные обратимые преобразования выполняются либо операцией ХОR, либо сложением. Начальное “забеливание” имеет целью произвести перемешивание данных блока с частью материала ключа на самой ранней стадии и, тем самым, повысить рандомизацию входного текста- и, как следствие, еще сильнее снизить вероятность успешной атаки по известному открытому тексту. Выходное преобразование усложняет обратную трассировку при частично известном злоумышленнику ключе, а кроме того, делает сеть Файштеля с “забеливанием” снова симметричной.

20. Свойства и назначение хэш-функций.

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

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

Бесключевые хэш-функции – имеют один вход (сообщение).

Ключевые хэш-функции – имеют два входа (сообщение и секретный ключ).

По функциональному назначению хэш-функции можно разделить на следующие классы:

Коды обнаружения изменений (modification detection codes, manipulation detection codes, MDCs).

Коды аутентификации сообщений (message authentication codes, MACs).

Другие приложения.

Классификация хэш-функций.

Хэш-функция- необратимое преобразование данных со следующими свойствами:

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

• на выходе получаем двоичный блок данных фиксированной длины;

• значения на выходе алгоритма распределяются по равномерному закону по всему диапазону возможных результатов;

• при изменении хотя бы одного бита на входе алгоритма его выход значительно меняется, в идеальном случае инвертируется произвольная половина бит.

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

21. Понятие криптографически стойкой Хэш-функции.

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

• зная результат невозможно подобрать, только кроме полного перебора, какой-либо входной блок данных, даёт такой же блок;

• невозможно подобрать, кроме как полным перебором, пару различных входных блоков, дающих на выходе произвольный, но одинаковый результат.

Хэш-функция реализуется, как правило, в виде некоторой итеративной процедуры, которая позволяет вычислить для сообщения М произвольной длины так называемый хэш-код Н(М) фиксированного размера m (обычно m составляет 128 - 256 бит). Этот код и является эталонной характеристикой сообщения М.

К хэш-функциям предъявляют следующие основные требования:

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

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

Хэш-функция должна обладать устойчивостью к коллизиям, т.е. должно быть трудно найти два случайных сообщения, M и M', для которых H(M)=H(M').

22. Основы построения хэш-функций. Итеративная последовательная схема.

Типовая хэш-функция вычисляется путем последовательного шифрования двоичных блоков Мi сообщения М в соответствии со следующим итеративным выражением: Нi = Е (Нi-1, Мi), где Е – базовая функция шифрования (см. рис. 2.).

Типовая схема вычисления блочной хэш-функции:

Н0 – специфицированное начальное значение хэш-функции;

Нn – значение хэш-функции, принимается за эталонную характеристику.

Основы построения хэш функций- принцип итеративной последовательной схемы.

Ядро: преобразование k бит в n бит, где n (разрядность результата хэш), k (разрядность исходного документа):

• если k>mn, где m- остаток:

1. добиваем нулями;

2. многократно повторяем сообщение до кратности;

3. добивается случайным набором 1 и 0.

   • если k<n:

1. многократное повторение;

2. добивание констант.

Итеративные х.ф.:

Х.ф. хэширующая документ целиком- однопроходная. Остальные случаи- многопроходные.

23. Хэш-функции на основе блочных шифров.

24. Алгоритм TandemDm.

25. Алгоритм md5.

26. Аппаратное шифрование des: структура, перестановки, сеть Файштеля, расширение ключа.

Традиционно первой знаменательной вехой в истории блочного шифрования считается опубликование в 1977 году и принятие в 1980 году в США национального стандарта шифрования данных DES (Data Encryption Standart). Параметры алгоритма таковы: разрядность блока- 64 бита, размер ключа- 56 бит. Алгоритм представляет собой классическую сеть Файштеля из 16 раундов с добавлением входной и выходной перестановок бит.

Входные данные (64 бита); входная перестановка бит (цель: распределить равномерно по блоку рядом стоящие биты); сеть Файштеля из 16 раундов; выходная перестановка бит; порядок перестановки обратен ко входной; выходные данные (64 бита).

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

Разрядность ключей раундов, применяемых в DES равна 48 битам. Для симметричности алгоритма шифрования дешифрования в DES, как и в классической сети Файштеля, производится дополнительно размен последнего обмена ветвей. Это позволяет производить шифрование и дешифрование одним и тем же программным кодом, передавая ему в первом случае ключи раундов в прямом порядке (k0, k1,…, k15), а во втором случае- в обратном (k15, k14,…, k0). Общий вид сети Файштеля алгоритма DES:

Образующая функция сети в алгоритме DES состоит из 4 операций:

1. перестановка бит/расширение блока с помощью повторов по определенной схеме;

2. наложение ключа раунда операций ХОR;

3. табличные подстановки;

4. перестановка бит.

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

Наложение ключа раунда производится операцией ХОR, разрядность операции- 48 бит.

DES: расширение ключа.

Расширение ключа (создание ключей раунда) производится в DES по следующей схеме. На основе 56 значащих бит из ключа на начальном этапе создаются два 28-битных вектора С0 и D0 путем выбора бит из ключа в определенной последовательности.

Для выбора 48 бит ключа i–го раунда, получившиеся после циклических сдвигов вектора СiDi объединяются, и из 56 бит получившегося массива отбираются 48 по закону.

По-настоящему заставили DES уйти с рынка конкурентно-способных блочных шифров две причины: ориентация на аппаратную реализацию и слишком малый размер ключа.

27. Tea: структура, алгоритм, образующая функция, ключ.

Пожалуй, самым простым представителем семейства программно ориентированных надежных блочных шифров является ТЕА (Тiny Еncryption Algorithm). Дословно его название переводится на русский как “крошечный криптоалгоритм». Представляет собой классическую сеть Файштеля из 64 раундов.

Размер блока- 64 бита.

Результат образующей функции накладывается на независимую ветвь‚ операцией «сложение», поэтому восстановить исходный текст простым обращением порядка ключей раунда не удастся. Алгоритм ТЕА является примером несимметричной 1 сети Файштеля- для дешифрования приходится реализовывать отдельную процедуру, хотя, как и шифрование, очень простую.

ТЕА: расширение ключа

Алгоритм использует 128 битный ключ, который превращается в ключи раунда по очень простой схеме. Ключ разбивается на четыре 32-разрядных машинных слова К0, К1, К2, К3. Во всех четных (считая с 0) раундах в качестве 64-битного ключа раунда используется пара (К0, К1) в нечетных- пара (К2, К3). В общепринятой схеме номер раунда обозначается переменной i; раундов- r, компоненты ключа раунда- как массив k[i] (он использует сквозную нумерацию по машинным словам- в нулевом раунде используются k[0] и k[1], в первом- k[2] и k[3] и т.д.). В таких обозначениях общая формула создания 128 компонент материала ключа для ТЕА выглядит следующим образом: k[i] =К(i mod 4)

28. Idea: структура, алгоритм, расширение ключа.

Алгоритм IDEA (International Data Еncryption algirithm).

IDEA построена по схеме, очень напоминающей сеть Файштеля. Подобный пинцип проектирования блочных шифров в классификации получил название обобщенной сети Файштеля. Исходный блок данных длиной в 64 бита разбивается на 4 ветви- все операции в IDEA выполняются в 16-битной арифметике. Затем в каждом из 8 раундов над ветвями и материалом ключа выполняются в специально подобранной очередности три операции: сложение, исключающее ИЛИ и модифицированное умножение. Модифицированное умножение изображено на схеме символом *. Длина ключа алгоритма составляет 128 бит.

Модифицированное умножение представляет собой обычное умножение по модулю 65537(216+1) с двумя условностями. Во-первых, если какой-либо из сомножителей равен 0, то перед умножением он заменяется на 216. Во-вторых, если получившееся после взятия модуля число равно 216, то оно заменяется на 0. Определенная подобным образом операция обладает следующими свойствами:

• отображает пару 16-разрядных чисел на 16-разрядное число;

• обратима (по известному результату и одному из сомножителей возможно однозначно определить второй сомножитель).

Раунд алгоритма IDEA

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

Алгоритм IDEA

Idea: расширение ключа

Получение из 128-битного ключа материала ключа в IDEA предельно просто. Первые 8 16-битных компонент k[0]...k[7] материала ключа получаются непосредственно разбиением 128 бит ключа на блоки без каких-либо преобразований. Затем 6 раз повторяется следуюшая операция: ключ сдвигается циклически влево на 25 бит и очередные 8 компонент получаются таким же разбиением уже сдвйнутого ключа на 16-битные блоки.

В псевдокоде:

k[0]...k[7]=key

key=key ROL 25

k[8]...k[15]=key

key=key ROL 25

. . .

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

29. Структура гост 28147-89: образующая функция, расширение ключа.

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

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

Общий вид ГОСТ 28147-89

Образующа функция ГОСТ 28147-89

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

ГОСТ 281 47-89: расширение ключа

Расширение ключа производится по очень простой схеме: 256-битный ключ разбивается на восемь З2-битных машинных слов. Они нумеруются с К0 по К7.

32 компоненты материала ключа получаются их применением в следующем порядке:

k[0]...k[32]=К0 К1...К6 К7 К0 К1...К6 К7 К0 К1...К6 К7 К7 К6...К1 К0

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

К0 К1...К6 К7 К7 К6...К1 К0 К7 К6...К1 К0 К7 К6...К1 К0

30. Конкурс aes: цели и условия конкурса, алгоритмы шифрования конкурса.

Цели и суловия конкурса

Конкурс АЕS (Advanced Encrypton Standart)- “улучшенный стандарт шифрования” и был проведен под эгидой Национального Институга Стандартизации и Техники (National Institute of Standart- NIST) в 1997-2000 годах.

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

• шифр должен быть блочным;

• шифр должен иметь длину блока, равную 128 битам;

• шифр должен поддерживать ключи длинной 128, 192, 256 бит.

NIST представил общественности документ, в котором сравнивались все 15 претендентов и были объявлены 5 финалистов, прошедших во второй этап конкурса. Все критерии, по которым производилось сравнение алгоритмов, были разбиты сотрудниками Института на категории: криптографические и практические характеристики.

Среди наиболее важных криптографических характеристик специалисты NIST указывали:

• стойкость к известным на момент проведения конкурса криптографическим атакам;

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

• отсугствие слабых ключей;

• стойкость к криптоатакам, специфичным для применяемых в шифе схем и криптоопераций;

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

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

• отсутствие необоснованно сложных преобразований и “необъяснимых” констант (что дает некоторый шанс исключить недокументированные свойства шифра, известные только разработчикам);

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

К наиболее важным практическим аспектам жюри отнесло:

• оптимизацию по скорости выполнения кода (в первую очередь, на 32-, 8- и 16-разрядных архитектурах ЭВМ);

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

• возможность оптимизации по размеру кода (для хранения в ПЗУ «слабых» микросхем и в других запоминающих устройствах с ограниченными ресурсами);

• возможность распараллеливания кода (естественно без потерь в криптостойкости);

• идентичность кода и времени исполнения процедур шифрования и дешифрования;

• сложность и затраты времени на процедуру создания материала ключа;

• характер зависимости скорости работы алгоритма от размера используемого ключа (128, 192 и 256 бит).

31. Mars структура: образующая функция, схемы входного и выходного перемешивания.

МАRS: структура

Он представляет собой блочный шифр с размером блока, равным 128 битам, и переменной длиной ключа. Схема расширения материала ключа такова, что в качестве него может использоваться последовательность бит произвольной длины от 128 до 1248 бит. Сами авторы отмечают, что такая большая возможная длина ключа выбрана ими не с точки зрения стойкости шифра (очевидно, что барьер в 256 бит будет еще очень долго оставаться недосягаемой величиной), а ради удобства использования шифра совместно с другими криптографическими примитивами. Так, например, во многих системах распространения ключей уникальная ключевая информация, получаемая в результате выполнения всех положенных действий, имеет длину в 512, 768 или 1024 бита.

Алгоритм МАRS можно классифицировать как среднего уровня сложности и реализации. Он представляет собой традиционную сеть Файштеля 3-го типа с 4-мя ветвями. Однако для повышения стойкости шифра к известным и, возможно, новым схемам криптоанализа разработчики значительно усложнили дополнительные входное и выходное преобразования сети Файштеля. В результате весь процесс шифрования удобно представить в виде 6 последовательных i преобразований.

1. Входное сложение с материалом ключа (первичное “забеливание”).

2. Входное перемешивание данных (8 раундов преобразования Е_ТRANS).

3. Первые 8 раундов сети Файштеля (первая схема наложения).

4. Завершающие 8 раундов сети Файштеля (вторая схема наложения).

5. Выходное перемешивание данных (8 раундов преобразования D_TRANS).

6. Выходное сложение с материалом ключа (выходное забеливание).

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

Схемы входного сложения с материалом ключа выходного “забеливания”:

Входное сложение алгоритма МАRS

Выходное «забеливание» алгоритма МАRS

Схемы входного и выходного перемешивания. Обе процедуры состоят из 8-кратного повторения типовых схем Е_ТRANS и D_ТRANS. “Разнообразят” данное восьмикратное повторение только операции арифметического сложения (в обратном проходе- вычитания), выполняемые после 1, 2, 5 и 6 применения схем перемешивания. Подобная «нестройность» алгоритма лежит в полном соответствии с общей концепцией авторов сделать шифр легко анализируемым и понятным, но не при димым к простому аналитическому виду.

Входное перемешивание МАRS

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

Выходное перемешивание МАRS

Табличные подстановки S0 и S1 на этапе перемешивания имеют разрядноcть 8х32 бита (то есть в качестве индекса в табличной выборке используются только младшие 8 бит из каждой ветви). Эти же две таблицы, но объединенные вместе, образуют табличную подстановку S разрядностью 9х32 бита, используемую в основных раундах сети Файштеля.

О бразующая функция F, используемая в алгоритме во всех 16 раундах сети Файштеля. Как видим, в ней разработчики использовали проактически все применяемые на сегодняшний день криптопримитивы: арифметическое сложение, исключающее ИЛИ, 32-разрядное умножение, сдвиги на фиксированное и переменное число бит, табличные подстановки. Подобный “винегрет” авторы снова объясняют повышением потенциальной стойкости алгоритма к еще неизвестным методам криптоатак. Вероятность того, что какая-либо закономерность потока данных, используемая в подобной атаке, пройдет через все виды криптопреобразований, очень мала- уверяют они.

Образующая функция МАRS

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

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

32. Основные принципы ассиметричной криптографии.

33. Ассиметричная криптография и электронная цифровая подпись. Понятия.

34. Алгоритм RSA (асимметричная криптография).

35. Алгоритм Эль Гамаль (асимметричная криптография).