- •Глава 36. Схемы шифрования rsa, Эль Гамаля, Полига-Хеллмана
- •Часть 5. Шифры с открытым ключом шифрования
- •Глава 36.
- •36.1. Основные понятия модулярной арифметики
- •Основные способы нахождения обратных величин a–1 1 (mod n).
- •36.2. Криптосистема шифрования данных rsa
- •X((Pх)) y (modQ).
- •36.3. Схема шифрования Эль Гамаля
- •36.4. Схема шифрования Полига-Хеллмана
- •Глава 37.
- •Глава 38.
- •38.1. Основные принципы построения протоколов идентификации и аутентификации
- •Доказательство проверяемого a:
- •38.3. Типовые схемы идентификации и аутентификации пользователя информационной системы
- •38.4. Особенности применения пароля для аутентификации пользователя
- •38.5. Взаимная проверка подлинности пользователей
- •38.6. Протоколы идентификации с нулевой передачей знаний
- •38.7. Упрощенный вариант схемы идентификации с нулевой передачей знаний. Протокол Фиата-Шамира
- •38.8. Параллельная схема идентификации с нулевой передачей знаний (с нулевым раскрытием)
- •38.9. Модифицированный протокол Фиата-Шамира
- •38.10. Схема идентификации Шнорра
- •38.11. Схема идентификации Гиллоу-Куискуотера
- •38.12. Способ проверки подлинности, где не требуется предъявлять секретный пароль
- •38.13. Проверка подлинности с помощью систем шифрования с открытым ключом
- •38.14. Биометрическая идентификация и аутентификация пользователя
- •Глава 39.
- •39.1. Основные понятия
- •39.4. Однонаправленные хэш-функции
- •Схемы безопасного хэширования, у которых длина хэш-значения равна длине блока
- •39.5. Отечественный стандарт хэш-функции
- •Глава 40.
- •40.1. Электронная цифровая подпись для аутентификации данных
- •40.2. Алгоритмы электронной цифровой подписи
- •40.3. Алгоритм цифровой подписи rsa
- •Обобщенная схема цифровой подписи rsa
- •40.4. Недостатки алгоритма цифровой подписи rsa
- •40.5. Алгоритм цифровой подписи Эль – Гамаля
- •40.6. Цифровая подпись Эль-Гамаля
- •40.7. Особенности протокола Эль-Гамаля
- •40.8. Алгоритм цифровой подписи dsa
- •40.10. Цифровые подписи с дополнительными функциональными свойствами
- •40.11. Алгоритм неоспоримой цифровой подписи д.Чома
- •40.12. Протокол подписи, позволяющий отправителю сообщения не предоставлять право получателю доказывать справедливость своей подписи
- •Глава 41.
- •41.1. Генерация ключей
- •41.2. Концепция иерархии ключей
- •41.3. Распределение ключей
- •41.4. Протокол аутентификации и распределения ключей для симметричных криптосистем
- •41.5. Протокол для асимметричных криптосистем с использованием сертификатов открытых ключей
- •41.6. Использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы
- •Длины ключей для симметричных и асимметричных криптосистем при одинаковой их криптостойкости
- •41.7. Использование системы открытого распределения ключей Диффи-Хеллмана
- •41.8. Протокол skip управления криптоключами
- •Глава 42.
- •42.1. Основные понятия конечных полей
- •42.2. Криптографические протоколы. Протокол Диффи-Хеллмана
- •42.3. Протокол электронной цифровой подписи
41.8. Протокол skip управления криптоключами
Протокол SKIP (Simple Key management for Internet Protocol) может использоваться в качестве интегрирующей среды и системы управления криптоключами.
Протокол SKIP базируется на криптографии открытых ключей Диффи–Хеллмана и обладает рядом достоинств:
-
обеспечивает высокую степень защиты информации;
-
обеспечивает быструю смену ключей;
-
поддерживает групповые рассылки защищенных сообщений;
-
допускает модульную замену систем шифрования;
-
вносит минимальную избыточность.
Концепция SKIP-протокола основана на организации множества двухточечных обменов (по алгоритму Диффи–Хеллмана) в компьютерной сети.
-
Узел I имеет секретный ключ i (i = kI) и сертифицированный открытый ключ gi mod N.
-
Подпись сертификата открытого ключа производится при помощи надежного алгоритма (ГОСТ, DSA и др.). Открытые ключи свободно распространяются центром распределения ключей из общей базы данных.
-
Для каждой пары узлов I, J вычисляется совместно используемый секрет (типичная длина 1024 бита): gij mod N.
-
Разделяемый ключ Кij вычисляется из этого секрета путем уменьшения его до согласованной в рамках протокола длины 64 -128 бит.
-
Узел вычисляет ключ Кij (используемый как ключ шифрования ключей) для относительно длительного применения и размещает его в защищенной памяти.
Следует отметить, что если сеть содержит n узлов, то в каждом узле должно храниться (n –1) ключей, используемых исключительно для организации связи с соответствующими узлами. Поэтому всего в сети с n узлами должно храниться n∙(n –1)/2 различных ключей и они должны меняться время от времени (срок службы таких ключей составляет недели). Например, при n = 6 число обменов ключей составляет 6∙(6–1)/2=15; при n=1000 число обменов ключей составит 1000∙(1000–1)/2 500000. Поэтому существует практическое ограничение на значение n.
Глава 42.
Криптографические протоколы на эллиптических кривых
42.1. Основные понятия конечных полей
Кольцо называется полем, если каждый ненулевой элемент обратим и мультипликативная группа кольца абелева. Поле как множество обычно обозначают через F трактуется его как множество замкнутое относительно двух бинарных операций называемых сложением + и умножением∙. При этом пара (F,+) является абелевой группой с нейтральным элементом 0, а пара (F\0, ∙) также является абелевой группой с нейтральным элементом 1. Операция умножения дистрибутивна относительно сложения +. Если множество конечно, то поле F называют конечным и его обозначают через Fq, |F|=q. Множество F\0 (F без нуля) обозначают через F* и называют мультипликативной группой поля F. Для aF обозначим через na сумму, состоящую из n элементов a. Так как q порядок группы (Fq,+), то qa=0 для любого элемента aFq (следует из теоремы Лагранжа, в частности q1=0).
Если для некоторого натурального числа m выполняется m1=0, то наименьшее из таких чисел называют характеристикой поля F. Если же для любого натурального числа m выполняется неравенство m10, то характеристикой поля называют число 0.
Приведем некоторые основные определения и утверждения.
-
Если F – подполе поля H, то характеристики полей F и H совпадают.
-
Поле F называется простым, если оно не имеет собственных подполей.
-
Если поле не является характеристики 0, то его характеристика есть простое число p.
-
Любое конечное простое поле Fp изоморфно кольцу Z/p вычетов целых чисел по модулю p.
-
Любое конечное поле F характеристики p содержит простое подполе из p элементов и является его конечным расширением.
-
Число элементов q конечного поля Fq равно q=pn, где p характеристика поля Fq.
-
Для любого натурального числа n в поле характеристики p выполняются равенства
-
Если q=pn, где p – простое число, то поле разложения H над полем Fp многочлена xq-x есть конечное поле из q элементов.
-
Мультипликативная группа конечного поля циклична.
Группа точек эллиптической кривой. Пусть конечное поле, характеристики p2. Рассмотрим многочлен вида
,
. Обозначим через множество корней многочлена Е в поле вместе с бесконечной точкой . Таким образом,
.
Очевидно, что если , то . Мы покажем, что на (в частности, на ) можно ввести групповую операцию. Дадим ряд определений.
1. Пусть К произвольное поле и многочлен от двух переменных над К. Этот многочлен определяет аффинную алгебраическую кривую, которая также обозначается через F:
.
2. Точка называется не особенной, или гладкой на F, если значения частных производных и не равны нулю одновременно. В противном случае точка называется особой. Нетрудно доказать, что все точки , y0 не особенные тогда и только тогда, когда многочлен не имеет кратных корней. (Кратные точки вида (x,0) вполне возможны, тогда -(x,0)=(x,0). См., например, [Н.Коблиц Курс теории чисел и криптография. М.: ТВП 2001].
3. Пусть – алгебраическое замыкание поля . Пусть также
.
Кривая называется эллиптической, если многочлен не имеет кратных корней. По задаче 1 это эквивалентно тому, что все аффинные точки являются простыми.
4. Вернемся к случаю аффинной кривой F над полем К. Пусть простая точка. Касательной к F в точке Р называется прямая
.
Очевидно, что касательная определена только для неообенной точки Р. В алгебраической геометрии это определение обобщается, и касательная к кривой определяется для любой точки.
ЛЕММА. Пусть и не обязательно различные точки на . Пусть при этом , если и , если . Обозначим через , прямую, которая проходит через , если , и касательную к Е в точке в противном случае. Тогда прямая пересекает ровно в одной точке , координаты которой определяются следующим образом
,
.
ДОКАЗАТЕЛЬСТВО. Пусть и . Тогда прямая, проходящая через , задается уравнением
,
где
, .
Пусть и . Тогда касательная к Е в точке задается уравнением , где
,
так как . Таким образом, для определения надо решить систему уравнений
.
После замены имеем . Следовательно, x3 является корнем многочлена . Этот кубический многочлен имеет 3 корня с учетом кратностей.
Пусть и . Тогда – различные корни этого многочлена. Третий корень можно найти из соотношения (по теореме Виета). Значит, в данном случае лемма доказана.
Пусть теперь и . Покажем, что x1 – кратный корень r(x). Вычислим для этого . Поэтому
.
Значит, (по теореме Виета), и в данном случае лемма доказана.
Пусть теперь , но . Точки определяют вертикальную прямую . Положим по определению, что есть третья точка пересечения данной прямой и . Очевидно, что других точек пересечения прямой и нет. Аналогично, если и , то прямая есть касательная к Е в точке P1. Здесь также полагаем, что есть третья точка пересечения вертикальной касательной и . Если даны точки и , то третья точка пересечения вертикальной прямой и кривой есть точка . При имеем . Если , то полагаем, что третей точкой пересечения касательной в точке и кривой является .
Из доказанной леммы и приведенных рассуждений видно, что произвольные, не обязательно различные точки кривой однозначно определяют третью точку на . Этот замечательный факт позволяет определить операцию на . Положим . Пусть произвольные точки на . Положим , где R третья точка пересечения с прямой, проходящей через . Очевидно, что однозначно определена. Легко доказать, что множество замкнуто относительно , операция коммутативна, точка является нейтральным элементом и каждая точка имеет обратный, то есть существует со свойством . С учетом этого для доказательства того, что есть абелева группа, достаточно показать ассоциативность операции . Но этот факт сложен для доказательства (см. [Fulton W. Algebraic curves: Introduction to algebraic geometry, NY, Benjamin, 1969]).
Для удобства выпишем формулы определяющие . Имеем для всех и , если и . Во всех остальных случаях , , где
,
,
, при ,
, при , .
ПРИМЕР. Определим элементы группы для эллиптической кривой . Для этого составим таблицу
X |
0 |
1 |
2 |
3 |
4 |
5 |
-1 |
-2 |
-3 |
-4 |
-5 |
X2 |
0 |
1 |
4 |
9 |
5 |
3 |
1 |
4 |
9 |
5 |
3 |
1 |
3 |
0 |
9 |
3 |
-1 |
-1 |
-9 |
-7 |
-1 |
3 |
|
Y |
1 |
5 |
0 |
3 |
5 |
- |
- |
- |
2 |
- |
5 |
Таким образом, . В входят точки
.
Вычислим степени точки (0,1). Имеем . Действительно, и . Тогда
и .
Далее ,
,
,
,
.
Кроме того, . Значит, , и .
В общем случае имеет место следующая фундаментальная теорема (Silverman J.H. (editor) Cryptography and lattices conference. Proceedings of CALC 2001, to appear as a volume in Lecture notes in computer science, 1986).
ТЕОРЕМА. Для любой эллиптической кривой над полем существуют натуральные такие, что .