Введение
Среди способов защиты информации наиболее важным считается криптографический. Он предусматривает такое преобразование информации, при котором она становится доступной для прочтения лишь обладателю некоторого секретного параметра (ключа). В последние годы область применения криптографии значительно расширилась. Ее стали повседневно использовать многие организации, коммерческие фирмы, частные лица. При этом законного пользователя того или иного криптографического средства, прежде всего беспокоит его надежность. Одним из способов оценки надежности является попытка «взлома», т.е. получение доступа к информации без знания ключа. Подобные задачи призвано решать смежное научное направление, называемое криптоанализом. Криптоанализ и криптография объединены общим названием – криптология.
Вводная лекция.
Защита информации
– это всевозможные средства и функции, обеспечивающие доступность, конфиденциальность или целостность информации или связи, исключая средства и функции, предохраняющие от неисправностей. Защита информации включает в себя криптографию, криптоанализ, защиту от собственного излучения и защиту (компьютера) от несанкционированного доступа.
Криптография
– это раздел прикладной математики, изучающий модели, методы, алгоритмы, программные и аппаратные средства преобразования информации (шифрования) в целях сокрытия ее содержания, предотвращения видоизменения или несанкционированного использования.
Криптосистема
– это система, реализованная программно, аппаратно или программно-аппаратно и осуществляющая криптографическое преобразование информации.
Криптоанализ
– это раздел прикладной математики, изучающей модели, методы, алгоритмы, программные и аппаратные средства анализа криптосистемы или ее входных и выходных сигналов с целью извлечения конфиденциальных параметров, включая открытый текст.
Из данных определений видно, что криптоанализ занимается задачами, которые в математическом смысле обратные задачи криптографии. Система криптографии и криптоанализа образует новую науку – криптологию.
В развитии криптологии принято выделять три этапа.
Первый этап
. (С древних времен до 1949г). Этот этап характеризуется частными, узкоспециальными и вычислительно простыми алгоритмами криптографии и криптоанализа без использования компьютеров. Его часто называют этапом до компьютерной криптографии.
Второй этап.
(1949-1976гг.) Этот этап принято отсчитывать с момента публикации американского математика-прикладника К. Шеннона «Теория связи в секретных системах». В этот период принято активно проводились систематические исследования по криптологии с использованием компьютера. Криптология становится математической наукой.
Третий этап.
(1976г. – настоящее время). Этот этап можно назвать и «эрой открытой криптологии». Этот этап принято отсчитывать с момента публикации работы американских математиков У.Дифори, М.Хеллмана «Новые направления в криптографии».В этой работе было показано, что «секретная» передача информации возможна (вотличие от результатов Шеннона) без предварительной передачи «секретного ключа».
Главной особенностью этого этапа становится массовое применение криптографии в банковском деле, электронной торговле, компьютерных сетях и других сферах жизнедеятельности.
Современная криптология широко использует теорию вероятностей, математическую статистику, алгебру, теорию чисел и теорию алгоритмов.
Некоторые определения и формулы.
В криптологии общеприняты следующие понятия:
· Пространство сообщений
· Пространство ключей
· Пространство зашифрованных сообщений
Остается уточнить понятие текста. При этом обычно фиксируют некоторую сумму символов, называемую алфавита. Это может быть английский, русский или какой-нибудь другой алфавит. Часто в качестве алфавита используются натуральные числа или символы 0 и 1. Словом называется упорядоченный набор букв данного алфавита. Множество слов обозначают через
1.
Арифметические основы
Основные обозначения.
Простые числа.
Натуральное число
, если оно не имеет других натуральных делителей, кроме 1 и
числом будет наименьший, отличный от единицы делитель целого числа
Взаимно простые числа.
Два целых числа
Наибольший общий делитель.
Всякое целое, делящее числа
(НОД) и обозначается
Алгоритм Евклида.
Способ нахождения наибольшего общего делителя двух целых Для случая положительных чисел
(где все
Последний положительный остаток
/Пример/
Найдем НОД (175,77).
175=77*2+21;
77=21*3+14;
21=14*1+7;
14-7*2.
Последний положительный остаток равен 7. Следовательно (175,77)=7.
Наименьшее общее кратное.
Всякое целое, кратное всех данных чисел, называется их общим кратным. Наименьшее положительное общее кратное называется наименьшим общим кратным
(НОК) и обозначается
Классы вычетов.
Числа, сравнимые по модулю
вычетов
по модулю
Функция Эйлера.
Арифметическая функция
Сравнения.
Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное число
по модулю
по модулю
это читается следующим образом:
*Доказательство*
Из
(
откуда
Обратно, из
выводим
т.е.
Сравнимость чисел
Свойства сравнений.
1. Два числа, сравнимые с третьим, сравнимы между собой.
2. Сравнения можно почленно складывать.
3. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив знак на обратный.
4. Сравнения можно почленно перемножать.
5. Обе части сравнения можно возвести в одну и ту же степень.
6. Обе части сравнения можно умножить на одно и то же целое число.
7. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
8. Обе части сравнения и модуль можно умножить на одно и то же целое.
9. Обе части сравнения и модуль можно разделить любой их общий делитель.
10. Если сравнение
11. Если сравнение имеет место по модулю
12. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.
Первообразные корни.
При
, которому
Если
Если
Пусть
по модулю
Символ Лежандра.
Функция чисел
и обозначается
Символ Якоби.
Символ Якоби
является обобщением символа Лежандра и служит для упрощения вычисления последнего. Пусть
его разложение на простые множители. Для всякого целого
Цепные дроби.
Цепная дробь – один из важнейших способов представления чисел и функций. Цепная дробь есть выражение вида
где
2.
Алгебраические основы
Понятие группы.
Группой
называется непустое множество
1). Операция * ассоциативна, т.е. для любых
2). В G имеется единичный элемент (или единица) e такой, что для любого
3). Для каждого a Î G существует обратный элемент
4). Для любых
Если дополнительно группа удовлетворяет четвертой аксиоме, то группа называется абелевой
или коммутативной
.
Множество
Через
Если взять все классы вычетов, взаимно простые с модулем m, и определить их умножение по модулю m, то получится группа, обозначаемая через
и обозначается через
Группа
, если она порождена одним элементом, т.е. в ней имеется такой элемент a, что любой другой элемент представим в виде
Циклическими являются группы
Циклическая группа всегда коммутативна.
Подгруппы групп.
Подмножество
этой группы, если H образует группу относительно операции группы
Подгруппы группы
подгруппами.
Гамоморфизмы групп.
Отображение
, если оно согласовано с операциями на группах
Кольца и поля.
Кольцом
называется множество
1).
2). Операция умножения ассоциативна, т.е. для всех
3). Выполняются законы дистрибутивности, т.е. для всех
Подкольца.
Подмножество
этого кольца, если оно замкнуто относительно имеющихся операций сложения и умножения и само образует кольцо относительно этих операций.
Гомоморфизмы колец.
Пусть
3. Генераторы случайных последовательностей
3.1 Равномерно распределённая случайная последовательность и её свойства
Случайные числа и их генераторы являются неотъемлемыми современных криптосистем. Приведём конкретные примеры использования случайных чисел в криптологии:
1). Сеансовые и другие ключи для симметрических криптосистем, таких как DES, ГОСТ 28 147-89, Blowfish;
2). Стартовые значения для программ генерации ряда математических величин в асимметрических криптосистемах, например, “больших простых чисел” в криптосистемах RSA, ElGamal;
3). Случайные слова, комбинируемые с парольными для нарушения “атаки угадывания” пароля криптоаналитика;
4). Вектор инициализации для блочных криптосистем, работающих в режиме обратной связи;
5). Случайные значения параметров для многих систем электронной цифровой, например DSA;
6). Случайные выборы в протоколах аутенфинации, например в протоколе Цербер (Kerberos);
7). Случайные параметры протоколов для обеспечения уникальности различных реализаций одного и того же протокола, например в протоколах SET и SSL.
Отметим, что для некоторых из этих криптографических применений необходимы огромные массивы случайных чисел, которые по своему назначению требуют конфиденциального использования. Например, в протоколе Цербер сетевой сервер генерирует тысячи сессионных ключей ежечасно. К сожалению, компьютеры по своей конструкции предназначены быть детерминированными системами, поэтому на современных компьютерах генерация случайных чисел весьма затруднительна.
Известно, что проблема генерации случайной последовательности с произвольным законом распределения вероятностей сводится к проблеме генерации так называемой равномерно распределённой случайной последовательности (РРСП), или, как её часто называют в криптографических приложениях, “число случайной” последовательности.
РРСП – случайная последовательность
Свойство
Свойство
Из базовых свойств
Свойство
Свойство
Где
Свойство
Свойство
которая тоже является РРСП.
Свойство
Свойство
поэтому для любого алгоритма прогнозирования
Свойство
Свойство
С учетом свойств
Генератор РРСП – устройство, позволяющее по запросу получить реализацию равномерно распределенной случайной последовательности
1. Табличный.
2. Физический.
3. Программный.
В следующем разделе мы рассмотрим программный генератор.
Программный генератор РРСП – программа имитации на компьютере реализации РРСП. Имитируемая последовательность
В разделе “Алгоритмы генерации псевдослучайных последовательностей” мы познакомимся с основными методами генерации псевдослучайных последовательностей, а в разделе “Методы генерации истинно случайных последовательностей” мы рассмотрим различные методы повышения “случайности” генераторов РРСП.
3.2 Алгоритмы генерации псевдослучайных последовательностей.
Классификация существующих алгоритмов генерации псевдослучайных последовательностей представлена на рис. Выделяются три основных подхода к построению алгоритмов генерации:
1). Прямые методы построения элементарных рекуррентных последовательностей:
2). Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.
3). Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.
Линейные и мультипликативные конгруэнтные генераторы.
Линейным конгруэнтным генератором (ЛКГ) с параметрами (
Параметры этого генератора (3.2.1) имеют следующий смысл:
Если приращение
«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы
Квадратичный конгруэнтный генератор.
Этот алгоритм генерации псевдослучайной последовательности
где
Свойство
Квадратичная конгруэнтная последовательность (
1).
2).
3).
4). Если
Свойство
Если
Генератор Эйхенауэра-Лена с обращением.
Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра-Лена с обращением определяется следующим нелинейным рекуррентным соотношением
где
Конгруэнтный генератор, использующий умножение с переносом.
В этом случае нелинейная псевдослучайная последовательность определяется рекуррентным соотношением:
Где в отличие от (
Параметрами нелинейного конгруэнтного генератора (
Рекуррентны в конечном поле.
Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка
где
Параметры генератора (
являлся примитивным многочленом по модулю
Генераторы
Фибоначчи
. Общий вид рекуррентного соотношения, определяющего генератор Фибоначчи задаётся уравнением
где
4. Первый этап развития криптографии
Защита информации может быть двух видов: шифрование и передача по закрытому каналу.
Предполагается, что сообщения передаются по так называемому “открытому” каналу связи, в принципе доступного для прослушивания некоторым другим лицам, отличным от получателя и отправителя.
Будем считать, что A (Алиса) – отправитель сообщения, а В (Боб) – корреспондент (получатель) сообщения, Е (Елена) – некий враг.
Классическая система секретной связи показана на рис. 1.
Классическим примером шифра подстановки (замены) является шифр Цезаря. При шифровании с его помощью каждая буква латинского алфавита циклически вправо на
Шифрование осуществляется в соответствии с этой подстановкой. Величина
Криптоанализ этого шифра очень прост. Для любого современно языка вычислены частотные характеристики букв, т.е. относительные частоты их появления в “нормальных” текстах.
Модулярный шифр.
Выберем число
Гомофоническое шифрование.
Один из способов защиты от частотной криптоатаки. Каждая буква текста шифруется несколькими символами этого или другого алфавита. Число этих символов пропорционально частотной характеристики шифруемой буквы.
Полиграммное шифрование.
При полиграммном шифровании заменяются не буквы текста, а их комбинации. Если заменяются пары букв, то мы имеем биграмное шифрование. Примером такого шифрования является шифр Плейфера. Образуем из алфавита квадрат
Замена биграмм производится по правилам:
1) если
2) если
3) если
4) при нечетном количестве букв в незашифрованном тексте к нему дописывается незначащая буква.
5) в наиболее вероятном количестве, когда
Код Энигма.
Одним из ярких примеров докомпьютерных шифров является код Энигма. По своей сути он является кодом замены. Код Энигма был реализован на базе машины инженера Кирха. Эта машина представляла собой ряд вращающихся на одной оси барабанов с электрическими контактами, обеспечивающих множество вариантов простой замены, определяемой текущим положением барабанов. В ранних моделях было пять барабанов, которые перед началом работы устанавливались по кодовому слову, а в ходе кодирования поворачивались при кодировании очередного символа. Слабым местом системы было ограниченное число барабанов и их редкая замена, что вызвало охоту англичан за экземплярами машины Кирха в подводных лодках Германии.
Код Энигма в своем первоначальном виде потерял свою привлекательность при появлении ЭВМ, т.к. пять барабанов могли обеспечить лишь около ста миллионов ключей, что возможно перебрать за один день.
5. Второй этап развития криптографии
5.1 Шенноновское понятие секретных систем
По Шеннону существует три общих типа секретных систем:
1. Системы маскировки, которые включают в себя применение таких методов, как невидимые чернила, представление сообщения в форме безобидного текста или маскировки криптограммы, и другие методы, с помощью которых факт наличия сообщения скрывается от противника;
2. Тайные системы (например, инвертирование речи), в которых для раскрытия сообщения требуется специальное оборудование;
3. «Собственно» секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., но само существование сообщения не скрывается и предполагается. Что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов.
Математически криптограмма
сообщение,
ключ, т.е.
Оценка секретных систем.
Имеется несколько различных критериев, которые можно использовать для оценки качества секретной системы. Рассмотрим их подробнее.
1) Количество секретности.
Некоторые секретные системы являются совершенными в том смысле, что положение противника не облегчается в результате перехвата любого количества сообщений. Другие системы, хотя и дают противнику некоторую информацию при перехвате очередной криптограммы, но не допускают единственного «решения». Системы, допускающие единственное решение, очень разнообразны как по затрате сил и времени, необходимых для получения этого решения, так и по количеству материала, который необходимо перехватить для получения единственного решения.
2) Объем ключа.
Ключ должен быть передан из передающего пункта в приемный пункт таким способом, чтобы его нельзя было перехватить. Иногда его нужно запомнить. Поэтому желательно иметь ключ настолько малый, насколько это возможно.
3) Сложность операции шифрования и дешифрования.
Операции шифрования и дешифрования должны быть, конечно по возможности, простыми. Если эти операции производятся вручную, то их сложность приводит к потере времени, появлению ошибок и т.д. Если они производятся механически, то сложность приводит к использованию больших и дорогих устройств.
4) Разрастание числа ошибок.
В некоторых типах шифров ошибка в одной букве, допущенная при шифровании или передаче, приводит к большому числу ошибок в расшифрованном тексте. Такие ошибки разрастаются в результате операции дешифрования, вызывая значительную потерю информации и часто требуя повторной передачи криптограммы.
5) Увеличение объема сообщения.
В некоторых типах секретных систем сообщения увеличиваются в результате операции шифрования. Этот нежелательный эффект можно наблюдать в системах, в которых делается попытка потопить статистику сообщения в массе добавляемых нулевых символов, или где используются многократные замены.
Совершенная секретность.
Предположим, что имеется конечное число возможных сообщений.
так что
После того, как шифровальщик противника перехватил некоторую криптограмму
он может вычислить апосториорные вероятности различных сообщений
Необходимое и достаточное условие для того, чтобы система была совершенно секретной, можно записать в следующем виде
где
априорная вероятность сообщения
условная вероятность криптограммы
вероятность получения криптограммы
апостериорная вероятность сообщения
Для совершенной секретности системы величины
Следовательно, должно быть выполнено одно из равенств:
или же
Если
Теорема.
Необходимое и достаточное условие для совершенной секретности состоит в том, что
для всех
Ненадежность.
Имеется два основных типа ненадежности: ненадежность ключа и ненадежность сообщения.
ненадежность ключа;
ненадежность сообщения.
,
,
где
криптограмма, сообщение, ключ.
вероятность ключа
апостериорная вероятность ключа
если перехвачена криптограмма
вероятность сообщения
апостериорная вероятность сообщения
если перехвачена криптограмма
Для кода подстановки.
6. Третий этап развития криптографии
Идею, лежащую в основе криптосистем с открытым ключом, высказали в 1975 году Диффи и Хелмен. Они ввели понятие односторонней функции с секретом. Это дало принципиальную возможность разрабатывать криптосистемы с открытым ключом, в которых алгоритм шифрования является общедоступным, и поэтому нет необходимости в секретных каналах связи для предварительного обмена ключами.
При шифровании с открытым ключом для шифрования и расшифрования используются разные ключи, и знание одного их них не дает практической возможности определить второй.
6.1 Шифр Ривеста – Шамира – Алдемана
Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году система RSA (Массачусетский технологический институт). Она основана на трудности разложения больших целых чисел на простые сомножители.
Исходный текст должен быть переведен в цифровую форму. В результате текст представляется в виде одного большого числа. Затем полученное число разбивается на части так, чтобы каждая из них была числом в промежутке от
Пользователь
Чтобы восстановить исходный текст,
1. Находит число
Для решения сравнения
Любой другой пользователь, который знает только
Алгоритм применения RSA.
1. Отправитель выбирает два больших простых числа
2. Затем он выбирает случайное число
3. После этого он публикует
4. Если
5. Получатель сообщения расшифровывает его. Возводя в степень
Пояснение.
Таким образом, открытым ключом служит пара чисел
Электронная подпись (цифровая подпись).
Если
Пусть
Практически невозможно изменить основной текст
Далее
Теперь каждый, кто знает открытые параметры
Для этого необходимо вычислить значение хеш-функции
/*Пример*/ Электронная подпись RSA.
Пусть
Вычисляем значение хеш-функции, получим
Подпись верна.
Определение Хеш-функции.
Хеш-функцией называется любая функция
9. Криптографические алгоритмы
9.1 Шифр Эль-Гамаля
Пусть имеются абоненты
Для всей группы абонентов выбирается некоторое большое простое число
Затем каждый абонент выбирает своё секретное число
В результате получаем следующую таблицу ().
Абонент | Открытый ключ | Секретный ключ |
Табл(). Ключи пользователей в системе Эль=Гамаля.
Алгоритм передачи сообщения
Шаг 1. Алиса формирует случайное число
и передаёт пару чисел
Шаг 2. Боб, получив
/*Пример*/
Алиса хочет передать Бобу сообщение
Алиса выбирает случайное число
Теперь Алиса посылает Бобу шифрограмму (17,12). Боб вычисляет по формуле (9.1.4):
Боб расшифровал сообщение
Электронная подпись на базе Эль-Гамаля.
Алиса выбирает большое простое число
Затем она вычисляет число
Это число
Теперь Алиса может подписывать сообщения. Допустим, она хочет подписать сообщение
Вначале Алиса вычисляет значение хеш-функции для сообщения
Далее Алиса вычисляет числа:
Под
Такое
Получив сообщение Боб заново вычисляет значение хеш-функции
/*Пример*/
Пусть общие параметры для некоторого сообщества пользователей
Пусть Алиса создала документ
9.2 Криптосистемы на эллиптических кривых
Использование эллиптических кривых в криптографических целях было Нило Коблицом и Виктором Миллером в 1985 году. С 1998 года использование эллиптических кривых для решения криптографических задач, таких, как цифровая подпись, было закреплено в стандартах США ANSI X9.62 и FIPS 186-2, а в 2001 году аналогичный стандарт, ГОСТ Р34.10-2001, был принят и в России.
Особое достоинство криптосистем на эллиптических кривых состоит в том, что по сравнению с “обычными” RSA системами, они обеспечивают существенно более высокую стойкость при равной трудоемкости или, наоборот, существенно меньшую трудоемкость при равной стойкости.
В результате тот уровень стойкости, который достигается в RSA при использовании 1024-битовых модулей, в системах на эллиптических кривых реализуется при размере модуля 160 бит, что обеспечивает более простую как программную, так и аппаратную реализацию.
Эллиптические кривые.
Кривая третьего порядка
называется эллиптической кривой.
Дискриминант этого уравнения равен
Если
Графический вид шифрования.
Алгоритм шифрования.
Для пользователей некоторой сети выбираются общая эллиптическая кривая
Каждый пользователь
Допустим, пользователь
1. Выбирает случайное число
2. Вычисляет
3. Шифрует
4. Посылает
Пользователь
1. Вычисляет
2. Дешифрует
{
Цифровая подпись.
Для сообщества пользователей выбирается общая эллиптическая кривая
Каждый пользователь
Чтобы подписать сообщение, Алиса делает следующее:
1. Вычисляет значение хеш-функции сообщения
2. Выбирает случайно число
3. Вычисляет
4. Вычисляет
5. Вычисляет
6. Подписывает сообщение парой чисел
Для проверки подписанного сообщения
1. Вычисляет
2. Убеждается, что
3. Вычисляет
4. Вычисляет композицию точек на кривой
5. Если
9.5 Общие принципы стохастической защиты информации
Метод стохастической защиты информации был разработан как помехоустойчивый код, содержащий признаки и операции введения избыточности при кодировании и принятия решения о наличии ошибок (и исправлении ошибок) при декодировании, объединенные с операциями прямого и обратного стохастического преобразования.
Сформулируем сущность и основные особенности метода защиты информации, использующего сигнальную конструкцию стохастического кодирования, содержащего операции стохастического преобразования двоичной последовательности длиной
1) Применение двупараметрических преобразований
2) Сочетание преобразования на большой длине блока (блочное шифрование) с использованием последовательности гаммы.
3) Использование последовательности гаммы с очень большим периодом, удовлетворяющей тестам на случайность и требованиям на непредсказуемость.
4) Использование случайных таблиц замены для двупараметрической операции, не имеющей другого формального описания, кроме таблицы.
5) Использование при генерации гаммы регистров с обратной связью при большой длине регистра и нелинейных операций
6) Принцип преобразования сообщения в квази случайную последовательность с распределением, не зависящим от статистики исходного сообщения.
7) Возможность совмещения задач криптографической защиты и помехоустойчивого кодирования с обнаружением и исправлением ошибок
Стохастическое шифрование представляет собой преобразование
имеет место:
при
,
при
для всех
где
–канальный (исходный) и преобразованный векторы ошибки, т.е. сумма по модулю 2между искажаемым и искаженным вектором.
Особенности стохастического шифрования.
1) Использование двупараметрической операции замены.
2) Развитие двух идей Шеннона:
- равновероятность обеспечивает нулевое количество в криптограмме о сообщении (проверяется с помощью тестов Кнута или NIST
);
- если длина ключа не менее длины сообщения, то процедура перебора ключа в принципе не может обеспечить получение исходного сообщения. Если длина сообщения
Напротив. Если длина начальной установки датчика гаммы менее длины сообщения, то при переборе всех возможных ключей в качестве варианта сообщения не будут появляться все возможные сообщения и на основе анализа симонтики сообщения можно выделить высоковероятное сообщение; этот критерий является критерием отбора исходного сообщения.
10. Криптоанализ
10.1 Существующие методики криптографических атак
Все предназначение криптографии заключается в сохранении открытого текста (или ключа, или того и другого) в тайне от оппонентов. Предполагается, что оппоненты располагают неограниченным доступом к линиям связи между отправителем и получателем.
Криптоанализом называют науку восстановления (дешифрования) открытого текста без доступа к ключу. Успешный криптоанализ позволяет восстановить открытый текст или ключ. Кроме того, криптоанализ позволяет обнаружить слабые места в криптоносителях, что в конце концов приведет к тем же результатам. Раскрытие ключа без привлечения методов криптологии называют компрометацией.
Попытка криптоанализа называется атакой. Фундаментальное допущение криптоанализа состоит в том. Что секретность сообщения всецело зависит от ключа.
Известны четыре основных типа криптоаналитических атак:
1. Атака на основе только шифротекста.
Криптоаналитик располагает шифротекстами (криптограммами) нескольких сообщений, зашифрованных. Его задача состоит в дешифровании как можно большего числа сообщении
Дано:
Определить: либо
2. Атака на основе открытого текста.
Криптоаналитик располагает доступом не только к шифротекстам нескольких сообщений, но и к открытому тексту одного из этих сообщений. Его задача в определении ключа (или ключей), примененного для шифрования сообщений, с целью дешифрования других сообщений, зашифрованных тем же ключом (ключами).
Дано:
Определить: либо
3. Атака на основе подобранного открытого текста.
У криптоаналитика есть доступ не только к шифротекстам и открытым текстам нескольких сообщений, но и возможность выбирать открытый текст для шифрования. Это предоставляет больше возможностей, чем вскрытие с использованием открытого текста, так как криптоаналитик может выбирать для шифрования блоки открытого текста, что может предоставить дополнительную информацию о ключе. Его задача состоит в раскрытии ключа (или ключей), применительно для шифрования сообщений, или алгоритма, позволяющего дешифровать все новые сообщения, зашифрованные тем же ключом (или ключами).
Дано:
где криптоаналитик может выбирать
Определить: либо
4. Атака на основе адаптивно подобранного открытого текста.
Криптоаналитик может не только выбирать шифруемый текст, но также уточнять свой последующий выбор на основе полученных ранее результатов шифрования. Так при вскрытии с использованием подобранного открытого текста криптоаналитик может выбирать для шифрования только один крупный блок открытого текста. При адаптивном же вскрытии с использованием подобранного открытого текста он может выбирать следующий блок, используя результаты первого выбора и т.д.
Кроме перечисленных типов известны так же, по крайней мере, еще три типа криптоаналитических атак.
1) Атака на основе подобранного шифротекста.
Криптоаналитик может выбирать различные шифротексты для расшифрования. А так же имеет доступ к расшифрованным открытым текстам. Например, у криптоаналитика есть доступ к «черному ящику», выполняющему автоматическое расшифровывание. Его задача состоит в раскрытии ключа.
Дано:
Получить:
Такой тип вскрытия применим, главным образом, к алгоритмам с открытым ключом. Кроме того, вскрытие с использованием подобранного шифротекста в некоторых случаях эффективно против симметрических алгоритмов.
2) Атака на основе подобранного ключа.
Такой тип вскрытия не означает, что криптоаналитик может выбирать ключ – просто он кое-что знает о связях между различными ключами.
3) Бандитский криптоанализ.
До получения ключа «криптоаналитик» прибегает к угрозам, шантажу или пыткам. Возможно также взяточничество, которое иногда называют «вскрытием с покупкой ключа». Это очень мощные и, зачастую, самые эффективные методы взлома алгоритма.
Подробнее мы рассмотрим атаку на основе подобранного шифротекста, т.к. в настоящее время во всем мире используется кодирование с открытым ключом.
10.2 Взлом шифров с открытым ключом на основе подобранного шифротекста
СЦЕНАРИЙ №1.
Еве, подслушивающей линии связи Алисы, удалось перехватить сообщение
(11.1)
Для вскрытия
меньшее n
и достает открытый ключ Алисы
Затем она вычисляет:
(11.2)
Если
то
Далее Ева просит подписать Алису y
её закрытым ключом, тем самым расшифровав y.
(Алиса должна подписать сообщение, а не его хесл-значение). Алиса никогда раньше не видела y.
Алиса посылает Еве:
(11.3)
После этого Ева вычисляет:
(11.4)
Ева получает
СЦЕНАРИЙ №2.
Трент – компьютер-нотариус. Если Алиса хочет заверить документ, она посылает Тренту. Трент подписывает его цифровой подписью RSAи отправляет обратно. (Однонаправленные хеш-функции не используются, Трент шифрует своим закрытым ключом все сообщение). Ева хочет, чтобы Трент подписал такое сообщение, которое в обычном случае он никогда не подпишет. Это сообщение может содержать фальшивую временную метку, или же автором этого сообщения может являться другое лицо. Какой бы не была причина, Трент никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение
и вычисляет:
(11.5)
Значение
это открытый ключ Трента, который должен быть опубликован. Далее Ева вычисляет
(11.6)
и посылает Тренту на подпись. Трент возвращает
(11.7)
которое и является подписью
СЦЕНАРИЙ №3.
Ева хочет, чтобы Алиса подписала сообщение
Если Ева сможет заставить Алису подписать
Вывод
: Никогда не используйте алгоритм RSAдля подписи случайных документов, подсунутых вас посторонними. Вначале всегда следует воспользоваться однонаправленной хеш-функцией. Формат блоков, предлагаемый ISO 9796, предотвращает описанное вскрытие.
10.3 Взлом шифров с открытым ключом при использовании общего модуля
Возможна реализация RSA, в которой всем пользователям раздается одинаковый модуль
Пусть одно и то же сообщение когда-нибудь шифровалось разными показателями (с одним и тем же модулем), и эти два показателя – взаимно простые числа. Пусть
Криптоаналитик знает
Так как
Считая
Из всего выше сказанного следует вывод, что нельзя делать
10.4 Методы повышения стойкости RSA
12. Квантовая криптография
Впервые идея шифрования с использованием квантового канала сформулирована в 1970 г. С.Уиснером и развита в 80-е г.г. Ч.Беннетом, Ж.Брассаром и С.Брейдбардом.
Для пересылки последовательности двоичных битов в квантовом канале связи используются специальным образом поляризованные фотоны. Фотон - элементарная квантовая система, которая характеризуется определенным направлением поляризации
Рис.12.1. Поляризация фотона.
Здесь r – единичный вектор, указывающий поляризацию фотона и направленный под углом
то
Принято говорить, что имеет место диагональная поляризация фотона, если вектор его поляризации:
то говорят о диагоналях поляризации и обозначают её символом “x”.
Проиллюстрируем применение квантовых сигналов в криптографии на примере передачи секретного ключа по открытому квантовому каналу. Рассмотрим классическую схему криптографической передачи информации. Алиса, желающая передать Бобу секретный ключ, который в дальнейшем будет использоваться, например, для обмена информацией с помощью некоторой криптосистемы. Ева – криптоаналитик, которая хотела бы скрытно завладеть копией передаваемого ключа.
Алиса гарантирует случайную секретную двоичную ключевую последовательность длиной N:
и случайную секретную индексную последовательность той же длины:
Затем Алиса генерирует в квантовый канал связи последовательность N фотонов: i – му фотону Fi
, несущему сигнал Ki
, дается поляризация “+” (если Ji
=0) и поляризация “x” (если Ji
=1).
Боб, имея два приемника фотонов (с поляризациями “+” и “x”), принимает поток фотонов. Если бы он знал индексную последовательность J, то, переключая приемники, добился бы того, что
. Очевидно, что в среднем совпадает N/2 символов у J и J’. Следовательно, лишь половина (в среднем) фотонов будет зарегистрирована безошибочно, а остальные фотоны не несут никакой информации о K:
Если Ева извлечет некоторые фотоны из последовательности измерения своими приемниками, то Боб сразу же обнаружит потерю фотонов.
Следующие шаги протокола выполняются в обычном канале связи. Прежде всего, через этот канал Алиса определяет посредством открытого обмена сообщениями, какие фотоны зарегистрированы и какие из них соответствуют истинной поляризации
Из-за возможных действий Евы (в том числе связанных со “вставкой ” фотонов) Алиса и Боб должны убедиться, что их получившиеся битовые строки идентичны. Простое решение состоит в том, чтобы Алиса и Боб открыто сравнили некоторые
1. Передача по квантовому каналу:
а) случайная бытовая строка
б) последовательность поляризаций, задаваемая
в) посланная Алисой последовательность фотонов;
г) последовательность поляризаций
д) битовая строка, зарегистрированная Бобом;
2. Обсуждение по открытому каналу:
а) Боб сообщает поляризацию зарегистрированных фотонов;
б) Алиса отмечает, какие поляризации были угаданы правильно;
в) последовательность
г) Боб указывает номера
3. Результат: оставшиеся
Шаг | Информация | ||||||||||||||
1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
2 | х | + | х | + | + | + | + | + | х | х | + | + | + | + | + |
3 | |||||||||||||||
4 | + | х | х | + | + | х | х | + | х | + | х | х | х | х | + |
5 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | ||||
6 | + | х | + | х | х | + | + | х | х | х | + | ||||
7 | V | V | V | V | V | V | |||||||||
8 | 1 | 1 | 0 | 1 | 0 | 1 | |||||||||
9 | 1 | 0 | |||||||||||||
10 | V | V | |||||||||||||
11 | 1 | 0 | 1 | 1 |
Табл. 13.1 Протокол выработки секретного ключа с помощью квантового канала связи.
То говорят о прямоугольной поляризации и обозначают ее символом “+”.
! |
Как писать рефераты Практические рекомендации по написанию студенческих рефератов. |
! | План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом. |
! | Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач. |
! | Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты. |
! | Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ. |
→ | Виды рефератов Какими бывают рефераты по своему назначению и структуре. |