Ассиметричные алгоритмы шифрования

План
Концепция криптосистемы с открытым ключом
Элементы теории чисел
Односторонние функции
Алгоритм Диффи-Хелмана
RSA
Криптоалгоритмы на основе эллиптических кривых
Алгоритм Эль-Гамаля (El Gamal)

1 Концепция криптосистемы с открытым ключом
Ключевой обмен,
Электронно-цифровая подпись
Аутентификация

Обобщенная схема асимметричной криптосистемы с открытым ключом
*
Алгоритм
шифрования
Алгоритм
расшифрования
Генерация
ключей
Отправитель Р1
Получатель Р2
Криптограмма, С
М
М
Кр2 - секретный
Кр1 - открытый
Незащищенный
канал
Противник

2 Элементы теории чисел

3 Односторонние (однонаправленные) функции
Односторонние (однонаправленные) функции
обладают следующим свойством:
Если известно x , то вычислить f(x) относительно просто
Если известно y=f(x) , то для вычисления x нет простого (эффективного) пути.

4 Алгоритм Диффи-Хелмана

Алгоритм Диффи – Хеллмана
(Diffie - Hellman)
*

5 RSA

АСИММЕТРИЧНЫЕ КРИПТОАЛГОРИТМЫ
Алгоритм RSA

АСИММЕТРИЧНЫЕ КРИПТОАЛГОРИТМЫ

Алгоритм RSA (Rivest-Shamir-Adleman)
*
Генерация ключей
Получатель 1. P, Q - простые, N = P · Q
2. φ(N) = (P-1) · (Q-1), φ(N) - функция Эйлера
Выбор открытого ключа Y:
1
Вычисление секретного ключа X:
X · Y ≡ 1 (mod φ(N)) (N,Y) → отправителю
Отправитель шифрование М (Мi = 0, 1, 2, …, N-1)
3. Ci = MiY (mod N)
Получатель расшифрование С(С1, С2, …, Сi, …)
4. Мi = СiX (mod N)
Пример
Генерация ключей
1. P = 3, Q = 11, N = P · Q = 33
2. φ(N) = (P-1) · (Q-1) = 2 · 10 = 20
Y = 7, НОД(Y, φ(N)) = 1
X · Y = 1 (mod 20), 7 · 3 = 1 (mod 20), Х = 3
Сообщение: М1М2 → 32; М1 = 3<33, М2 = 2<33
Шифрование Ci = MiY (mod N)
3. C1 = 37 mod 33 = 2187 mod 33 = 9
C2 = 27 mod 33 = 128 mod 33 = 29 Шифротекст 9,29
Расшифрование Мi = СiX (mod N)
4. М1 = 93 mod 33 = 729 mod 33 = 3
М2 = 293 mod 33 = 24389 mod 33 = 2 Восстановленный текст 3,2

6 КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения
Что такое Эллиптическая кривая?
В общем случае эллиптическая кривая описывается математическим уравнением вида:
y2+axy+by=x3+cx2+dx+e ,
где a, b, c, d и e являются действительными числами, удовлетворяющими некоторым простым условиям.

В случае криптографии с использованием эллиптических кривых приходится иметь дело с редуцированной формой эллиптической кривой, которая определяется над конечным полем.
Особый интерес для криптографии представляет объект, называемый эллиптической группой по модулю p, где p является простым числом.
Эллиптическая кривая над конечным полем задаётся уравнением
y2=x3+ax+b (mod p).
КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения

КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения
Пространственный график эллиптической кривой y2=x3-5x+1

Криптоалгоритм основан на “Проблеме Дискретного Логарифма Эллиптической Кривой”
(Elliptic Curve Discrete Logarithm Problem – ECDLP):
“Даны “базовая точка” P и расположенная на кривой точка kP; найти значение k”.
Для эллиптических кривых и базовых точек решение таких уравнений представляет весьма и весьма большую трудность!
С точки же зрения криптографии имеется возможность определить новую криптографическую систему на основе эллиптических кривых.
Любая стандартная система, основанная на проблеме дискретного логарифма, аналогична системе основанной на ECDLP. Например, Эллиптическая Кривая DSA (ECDSA) уже стандартизирована (ANSI X9.62 – Ref. 4) и на ее основе может быть реализован протокол открытого обмена ключами Diffie-Hellman.
КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения

КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения
Из-за трудности взлома алгоритм ECDLP можно применять для высоко защищенных систем; обеспечивая сопоставимый уровень безопасности, алгоритм имеет значительно меньшие размеры ключа, чем, например, алгоритмы RSA или DSA. В приведенной ниже таблице сравниваются приблизительные
размеры параметров эллиптических систем и RSA, обеспечивающих одинаковую стойкость шифра,
которая рассчитывается на основе современных методов решения ECDLP и факторинга (поиска делителей) для больших целых чисел.

Использование эллиптических кривых позволяет строить высоко защищенные системы с ключами явно меньших размеров по сравнению с аналогичными “традиционными” системами типа RSA или DSA.
В частности такие системы менее требовательны к вычислительной мощности и объему памяти оборудования и потому хорошо подходят, например, для смарт-карт или портативных телефонов.
Разумеется существуют и проблемы, которые ограничивают повсеместное распространение криптографических систем на основе эллиптических кривых.
КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Общие положения

КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Некоторые проблемы и трудности в использовании систем на основе Эллиптической Кривой
1. Истинная сложность ECDLP ещё не осознана полностью. Исследования показывают, что некоторые использовавшиеся для отработки алгоритмов шифрования эллиптические кривые, фактически не подходят для таких операций. Такие кривые называются «аномальными».
2. Чрезвычайно трудно создать подходящую кривую и точку Р. Координаты базовой точки P должны иметь достаточно большое значение, чтобы гарантировать трудность взлома ECDLP.
3. Относительно медленная проверка цифровой подписи.
4. Проблема лицензирования и патентования криптосистем на основе эллиптической кривой еще не решена. В этой области существует множество патентов, но главным образом для применения в частных случаях.

КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Скорость обработки
Сравнительные характеристики алгоритмов RSA и ECDSA при создании и проверки подписей.
Алгоритмы выполнялись на параллельных процессорах Motorola 56303 DSP (66 МГЦ).

КРИПТОАЛГОРИТМЫ НА ОСНОВЕ
ЭЛЛИПТИЧЕСКИХ КРИВЫХ
Заключительные замечания
Криптосистемы на основе эллиптической кривой получают все большее распространение скорее
как альтернатива, а не замена
системам на основе RSA, поскольку системы на основе ECDLP имеют некоторые преимущества, особенно при использовании в устройствах с маломощными процессорами и/или маленькой памятью.

7 Алгоритм Эль-Гамаля (El Gamal)
*
Генерация ключей
1. P, G - простые (P>G) 2. Х - секретный ключ, (случайное целое Х
3. Y - открытый ключ Y = GX mod P
Шифрование М
4. К - случайное целое, 1<К<(P-1), НОД(К, P-1) = 1
a = GK mod P b = YKM mod P (a, b) - шифротекст
Расшифрование (a, b)
5. M = (b / aX ) mod P
Пример p=19 G=2 x=3 k=5 M=10
Шифрование М = 5
1. Р = 11, G = 2 (P>G)
2. X
3. Y = GX mod P = 28 mod 11= 256 mod 11 = 3
Y = 3 - открытый ключ
4. К = 9, НОД(К, Р-1) = 1, НОД(9, 10) = 1
a = GK mod P = 29 mod 11 = 512 mod 11 = 6
b = YKM mod P = 39 ·5 mod 11 = 19683 · 5 mod 11 = 9
(a, b) = (6, 9) - шифротекст
Расшифрование
5. М = (b / aX ) mod P = 9 / 68 mod 11
6 8 M = 9 mod 11
1679619 · M = 9 mod 11
M = 5

ЭЦП RSA
*
Генерация ключей
1. P, Q - большие простые числа.
2. Модуль N = P · Q; φ(N) = (P-1) · (Q-1), φ(N) - функция Эйлера
3. Открытый ключ E ≤ φ(N); НОД(E, φ(N)) = 1
4. Секретный ключ D < N; E · D = 1 (mod φ(N))
Постановка подписи
5. Вычисление хэш-функции Н = h(M), М - сообщение
6. Подпись (M,S) → S = H D (mod N)
Проверка подписи
7. Вычисление хэш-функции Н' = h(M)
8. Вычисление Н" = S E (mod N)
9. Н ' = Н" ?
Пример
Генерация ключей
1. P = 3, Q = 11
2. N = 33; φ(N) = 20
3. E = 7, НОД(7, 20) = 1
4. D = 3, 7 · 3 = 1 (mod 20)
Постановка подписи
5. Н = 4
6. S = 4 3 (mod 33) = 31
Проверка подписи
7. Н ' = 4
8. Н " = 317 (mod 33) = 27512614111 (mod 33) = 4
9. Н ' = Н" = 4 – подпись верна

Обобщенная схема формирования ЭЦП
*
Отправитель
(постановка ЭЦП)
Получатель
(проверка ЭЦП)
Сообщение
М
Блок
сжатия
HD
Генерация
ключей
SE
Блок
сжатия
канал
H ' = H "
S = HD mod N
H = h (M)
E, N
N, D
M
H " = S E (mod N)
H ' = h(M)
да
нет
ЭЦП
подлинная
ЭЦП
ошибочная