- •Министерство образования и науки Российской Федерации
- •В.И. Аверченков, м.Ю. Рытов, с.А. Шпичак
- •Брянск Издательство бгту
- •Isbn 978-5-89838-596-5
- •Редактор издательства т.И. Королева
- •Темплан 2011г., п. 57
- •1. Введение в криптографию 10
- •2. Стойкость криптографических систем 34
- •3. Принципы построения симметричных криптографических алгоритмов 61
- •4. Принципы построения асимметричных криптографических алгоритмов 98
- •5. Криптографические хэш-функции и электронно-цифровая подпись 133
- •6. Организация сетей засекреченной связи 160
- •7.Криптоанализ и перспективные направления в криптографии 183
- •Предисловие
- •1. Введение в криптографию
- •1.1. Краткая история развития криптографических методов.
- •1.2. Основные понятия криптографии
- •1.2.1. Термины и определения
- •1.2.2. Классификация шифров
- •1.2.3. Характер криптографической деятельности
- •Контрольные вопросы
- •2. Стойкость криптографических систем
- •2.1. Модели шифров и открытых текстов
- •2.1.1. Алгебраические модели шифров.
- •2.1.2. Вероятностные модели шифров.
- •2.1.3. Математические модели открытых сообщений.
- •2.2. Криптографическая стойкость шифров
- •2.2.1. Теоретико-информационный подход к оценке криптостойкости шифров
- •2.2.2. Практическая стойкость шифров.
- •2.3. Имитостойкость и помехоустойчивость шифров
- •2.3.1. Имитостойкость шифров. Имитация и подмена сообщения
- •2.3.2. Способы обеспечения имитостойкости
- •2.3.3. Помехостойкость шифров
- •2.3.4. Практические вопросы повышения надежности.
- •Контрольные вопросы
- •3. Принципы построения симметричных криптографических алгоритмов
- •3.1. Виды симметричных шифров. Особенности программной и аппаратной реализации.
- •3.2. Принципы построения блочных шифров
- •3.2.1. Базовые шифрующие преобразования
- •3.2.2. Сеть Файстеля
- •3.3. Современные блочные криптоалгоритмы
- •3.3.1. Основные параметры блочных криптоалгоритмов.
- •3.3.2. Алгоритм des
- •3.3.3. Блочный шифр tea
- •Var key:tLong2x2;
- •Var y,z,sum:longint; a:byte;
- •Inc(sum,Delta);
- •3.3.4. Международный алгоритм idea
- •3.3.5. Алгоритм aes (Rijndael)
- •InverseSubBytes(s);
- •InverseShiftRows(s);
- •InverseSubBytes(s) End;
- •3.4. Принципы построения поточных шифров
- •3.4.1. Синхронизация поточных шифрсистем
- •3.4.2. Структура поточных шифрсистем
- •3.4.3.Регистры сдвига с обратной связью
- •3.4.4. Алгоритм Берленкемпа-Месси
- •3.4.5. Усложнение линейных рекуррентных последовательностей
- •3.5. Современные поточные криптоалгоритмы
- •3.5.1. Алгоритм Гиффорда
- •3.5.2. Алгоритм a5
- •3.6. Режимы использования шифров
- •Контрольные вопросы
- •4. Принципы построения асимметричных криптографических алгоритмов
- •4.1. Математические основы асимметричной криптографии
- •4.1.1. Свойства операций
- •4.1.2. Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма
- •4.1.3. Конечные поля
- •4.1.4. Основные алгоритмы
- •Алгоритм разложения чисел на простые множители.
- •4.1.5. Алгоритмы нахождения нод и мультипликативного обратного по модулю
- •4.1.6. Китайская теорема об остатках
- •4.1.7. Символы Лежандра и Якоби. Извлечение корней
- •4.2. Примеры современных асимметричных шифров
- •4.2.1. Криптосистема rsa
- •4.2.2. Взаимосвязь компонентов rsa
- •Слабые моменты реализации rsa
- •4.2.3. Криптосистема Эль-Гамаля
- •4.2.4. Криптосистема Рабина
- •4.2.5. Рюкзачные криптосистемы
- •4.2.6. Шифрсистема Мак-Элиса
- •Контрольные вопросы
- •5. Криптографические хэш-функции и электронно-цифровая подпись
- •5.1. Криптографические хэш-функции
- •5.1.1. Блочно-итерационные и шаговые функции
- •5.1.2. Ключевые функции хэширования
- •5.1.3 Бесключевые функции хэширования
- •5.1.4. Схемы использования ключевых и бесключевых функций
- •5.2. Электронно-цифровая подпись
- •5.2.1. Задачи и особенности электронно-цифровой подписи
- •5.2.2. Асимметричные алгоритмы цифровой подписи на основе rsa
- •5.2.3. Алгоритм цифровой подписи Фиата – Фейге – Шамира
- •5.2.4. Алгоритм цифровой подписи Эль-Гамаля
- •5.2.5. Алгоритм цифровой подписи Шнорра
- •5.2.6. Алгоритм цифровой подписи Ниберга-Руппеля
- •5.2.7. Алгоритм цифровой подписи dsa
- •5.2.8. Симметричные (одноразовые) цифровые подписи
- •Контрольные вопросы
- •6. Организация сетей засекреченной связи
- •6.1. Протоколы распределения ключей
- •6.1.1. Передача ключей с использованием симметричного шифрования
- •6.1.2. Передача ключей с использованием асимметричного шифрования
- •6.1.3. Открытое распределение ключей
- •6.1.4. Предварительное распределение ключей
- •6.1.5. Схемы разделения секрета
- •6.1.6. Способы установления ключей для конференц-связи
- •6.2. Особенности использования вычислительной техники в криптографии
- •6.2.1. Методы применения шифрования данных в локальных вычислительных сетях
- •6.2.2. Обеспечение секретности данных при долгосрочном хранении.
- •6.2.4. Обеспечение секретности ключей при долгосрочном хранении
- •6.2.5. Защита от атак с использованием побочных каналов
- •7.1.2. Атаки на хэш-функции и коды аутентичности
- •7.1.3. Атаки на асимметричные криптосистемы
- •7.2. Перспективные направления в криптографии
- •7.2.1. Эллиптические кривые
- •7.2.2. Эллиптические кривые над конечными полями
- •7.2.3. Алгоритм цифровой подписи ec-dsa
- •7.2.4. Квантовая криптография
- •Контрольные вопросы
- •Приложение
- •Заключение
- •Список использованной и рекомендуемой литературы
- •Учебное издание
- •Аверченков Владимир Иванович Рытов Михаил Юрьевич Шпичак Сергей Александрович
7.2. Перспективные направления в криптографии
7.2.1. Эллиптические кривые
Проективная плоскость P2(K) над полем K определяется как множество троек (X, Y, Z) не равных одновременно нулю элементов X, Y, Z K, на котором введено отношение эквивалентности:
(X, Y, Z) ~ (X, Y, Z) для любых K*.
Так, например, две точки (4, 1, 1) и (5, 3, 3) эквивалентны в P2(F7).
Класс эквивалентности троек называется проективной точкой.
Эллиптической кривой E называется множество точек проективной плоскости, удовлетворяющих однородному уравнению Вейерштрасса
E: F(X, Y, Z) = –X3 + Y2Z + a1XYZ – a2X2Z + a3YZ2 – a4XZ2 – a6Z3 = 0,
c ai K.
Это уравнение называют также длинной формой Вейерштрасса. Кривая должна быть неособой в том смысле, что частные производные не должны обращаться в нуль одновременно ни в одной ее точке.
Множество K-рациональных точек кривой E (то есть точек, удовлетворяющих уравнению кривой) обозначается через E(K).
Кривая имеет только одну точку, чья координата Z = 0, а именно (0, 1, 0). Ее принято называть бесконечно удаленной точкой (или точкой на бесконечности) и обозначать символом O.Для удобства часто пользуются аффинной версией уравнения Вейерштрасса:
E: Y2 + a1XY + a3Y = X3 + a2X2 + a4X + a6, c ai K.
K-рациональные точки в аффинном случае – это решения уравнения в K2 и бесконечно удаленная точка O.
Переход от аффинных к проективным координатам:
- точка на бесконечности всегда переходит в бесконечно удаленную точку, как при переходе от аффинных координат к проективным, так и наоборот;
- проективная точка (X, Y, Z) кривой, отличная от бесконечно удаленной (Z 0), переходит в аффинную точку с координатами (X/Z, Y/Z);
- чтобы найти проективные координаты аффинной точки (X, Y), не лежащей на бесконечности, достаточно выбрать произвольное значение Z K* и вычислить (X·Z, Y·Z, Z).
Иногда удобнее пользоваться модифицированной формой проективной плоскости, когда проективные координаты (X, Y, Z) представляют аффинную точку (X/Z2, Y/Z3).
Для эллиптической кривой вводятся следующие константы:
Дискриминант кривой E определяется по формуле
Если char K 2, 3, то дискриминант можно вычислить и так:
Деление на 1728 = 2633 имеет смысл только в тех полях, чья характеристика отлична от 2 и от 3. Кривая E неособа тогда и только тогда, когда . Далее рассматриваются только неособые кривые.
Для неособых кривых вводится j-инвариант
он тесно связан с понятием изоморфизма эллиптических кривых.
Говорят, что кривая E с координатами X и Y изоморфна над полем K кривой E’ с координатами X’, Y’ (обе заданы уравнением Вейерштрасса), если найдутся такие константы r, s, t K и u K*, что при замене переменных
X = u2X’ + r, Y = u3Y’ + su2X’ + t
кривая E перейдет в кривую E’. Отметим, что изоморфизм кривых определен относительно поля K. Изоморфизм эллиптических кривых является отношением эквивалентности.
Лемма. Изоморфные над полем K кривые имеют один и тот же j-инвариант. С другой стороны, любые кривые с совпадающими j-инвариантами изоморфны над алгебраическим замыканием поля K. То есть j-инвариант разделяет классы эквивалентности отношения изоморфизма над алгебраическим замыканием поля K.
Групповой закон.
Рассмотрим для char K 2, 3 замену переменных
переводящую кривую заданную длинной формой Вейерштрасса в изоморфную ей кривую, определяемую короткой формой Вейерштрасса E: Y2 = X3 + aX + b при некоторых a, b K. На таких представителях классов изоморфных эллиптических кривых можно наглядно ввести групповой закон методом хорд и касательных.
Сложение точек определяется с помощью хорд. Пусть P и Q – две точки кривой. Соединим их прямой линией. Она обязательно пересечет кривую в какой-то третьей точке R, поскольку мы пересекаем кубическую кривую прямой. Точка R будет определена над тем же полем, что сама кривая и исходные точки P и Q. Отразим затем точку R относительно горизонтальной оси координат и получим точку, определяемую над основным полем. Последняя точка и будет суммой P + Q.
Рис.38. Групповой закон. Сложение точек
Касательные служат для удвоения точек (используя хорду нельзя сложить точку с собой). Пусть P – произвольная точка эллиптической кривой. Проведем касательную к кривой в точке P. Она пересечет кривую в какой-то третьей точке R (кубическая кривая пересекается по трем точкам с учетом кратности пересечения). Отразив R относительно горизонтальной оси, мы получим точку [2]P = P + P. Вертикальная касательная в точке P «пересекает» кривую в бесконечно удаленной точке. В этой ситуации P + P = O и говорят, что P – точка порядка 2.
Рис.39. Групповой закон. Удвоение точек
Метод хорд и касательных наделяет эллиптическую кривую структурой абелевой группы с бесконечно удаленной точкой в качестве нейтрального (единичного) элемента, то есть нуля. Определение операций можно легко перенести на случай общей эллиптической кривой, заданной длинной формой Вейерштрасса (в частности характеристика поля может быть любой). Необходимо только заменить отражение относительно оси абсцисс на симметрию относительно прямой
Y = a1X + a3
Алгебраические формулы, реализующие сложение точек по методу хорд и касательных.
Лемма. Пусть E – эллиптическая кривая, определяемая уравнением
E: Y2 + a1XY + a3Y = X3 + a2X2 + a4X + a6,
на которой выбраны точки P1(x1, y1) и P2(x2, y2). Точка –P1 имеет координаты
–P1(x1 – y1 – a1x1 – a3).
Введем коэффициенты
при x1 x2 и
если x1 = x2, но P2 –P1. Если P3(x3, y3) = P1 + P2 O, то x3 и y3 вычисляются по формулам:
Фиксируем натуральное число m и обозначим через [m] отображение кривой на себя, сопоставляющее каждой точке P ее кратное [m]P, то есть
Это отображение – основа криптографических систем, опирающихся на эллиптическую кривую, поскольку его можно легко вычислить, но крайне сложно обратить, то есть по данным координатам P(x, y) и [m]P(x’, y’) найти m очень трудно. (Конечно сложность обращения предполагает специальный выбор эллиптической кривой и соблюдения других условий).