АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ ШИФРОВАНИЯ
Асимметричные криптографические системы были разработаны в 1970-х го-
дах. Принципиальное отличие асимметричной криптосистемы от криптосистемы
симметричного шифрования состоит в том, что для шифрования информации и ее
последующего дешифрования используются различные ключи:
− открытый ключ K: используется для шифрования информации, вычисляется из
секретного ключа k;
− секретный ключ k: используется для дешифрования информации, зашифро-
ванной с помощью парного ему открытого ключа K.
Эти ключи различаются таким образом, что с помощью вычислений нельзя
вывести секретный ключ k из открытого ключа K. Поэтому открытый ключ K может
свободно передаваться по каналам связи.
Асимметричные системы называют еще двухключевыми криптографическими
системами или криптосистемами с открытым ключом.
Обобщенная схема асимметричной криптосистемы шифрования с открытым
ключом показана на рис. 1.19.
Для криптографического закрытия и последующего дешифрования передавае-
мой информации используются открытый и секретный ключи получателя сообще-
ния В. В качестве ключа шифрования должен использоваться открытый ключ полу-
чателя КВ, а в качестве ключа дешифрования – его секретный ключ kB.
Секретный и открытый ключи генерируются попарно. Секретный ключ дол-
жен оставаться у его владельца; он должен быть надежно защищен от несанкциони-
рованного доступа (аналогично ключу шифрования в симметричных алгоритмах).
Копия открытого ключа должна иметься у каждого абонента криптографической
сети, с которым обменивается информацией владелец секретного ключа.
Процесс передачи зашифрованной информации в асимметричной криптоси-
стеме осуществляется следующим образом:
1) Подготовительный этап. Абонент В генерирует пару ключей: секретный
ключ kB и открытый ключ Кв. Открытый ключ KB посылается абоненту А и
остальным абонентам (или делается доступным, например, на разделяемом
ресурсе).
2) Использование - обмен информацией между абонентами А и В. Абонент А
зашифровывает сообщение с помощью открытого ключа КВ абонента В и от-
Отправитель A
Получатель B
Сообщение М
Шифрование
ЕB
Секретный ключ
получателя kB
Сообщение М
’
Дешифрование
DB
Незащищенный
канал
связи / хранения
Шифротекст С
Открытый ключ получателя KB
KB
Рис. 1.19. Обобщенная схема асимметричной криптосистемы шифрованияправляет шифротекст абоненту В. Абонент В расшифровывает сообщение с
помощью своего секретного ключа kB. Никто другой (в том числе абонент А)
не может расшифровать данное сообщение, так как не имеет секретного
ключа абонента В. Защита информации в асимметричной криптосистеме ос-
нована на секретности ключа kB получателя сообщения.
Отметим характерные особенности асимметричных криптосистем:
1) Открытый ключ КВ и криптограмма С могут быть отправлены по незащи-
щенным каналам, то есть противнику известны КВ и С.
2) Алгоритмы шифрования и дешифрования
: ,
:
B
B
E M C
D C M
→
→
являются открытыми.
У. Диффи и М. Хеллман сформулировали требования, выполнение которых
обеспечивает безопасность асимметричной криптосистемы [xxx]:
1) Вычисление пары ключей (КB, kB) получателем В на основе начального усло-
вия должно быть простым.
2) Отправитель A, зная открытый ключ КB и сообщение M, может легко вычис-
лить криптограмму
( ).
KB
C E M =
3) Получатель В, используя секретный ключ kB и криптограмму С, может легко
восстановить исходное сообщение
( ).
B M D C = k
4) Противник, зная открытый ключ KB, при попытке вычислить секретный
ключ kB наталкивается на непреодолимую вычислительную проблему.
5) Противник, зная пару (KВ,С), при попытке вычислить исходное сообщение М
наталкивается на непреодолимую вычислительную проблему.
Концепция асимметричных криптографических систем с открытым ключом
основана на применении однонаправленных функций. Неформально однонаправ-
ленную функцию можно определить следующим образом [xxx]. Пусть X и Y - неко-
торые произвольные множества. Функция f : X Y → является однонаправленной,
если для всех x X ∈ можно легко вычислить функцию
y = f (x), где y ∈Y.
И в то же время для большинства y ∈Y достаточно сложно получить значение
x∈ X , такое, что f (x) = y (при этом полагают, что существует по крайней
мере одно такое значение x ).
Основным критерием отнесения функции f к классу однонаправленных
функций является отсутствие эффективных алгоритмов обратного преобразования
Y X → .
В качестве примера однонаправленной функции можно указать целочисленное
умножение. Прямая задача – вычисление произведения двух очень больших целых
чисел P и Q, то есть нахождение значения
N P Q = ×
является относительно несложной задачей для компьютера.
Обратная задача - факторизация, или разложение на множители большого це-
лого числа, то есть нахождение делителей P и Q большого целого числа N P Q = ×является практически неразрешимой задачей при достаточно больших значениях N.
По современным оценкам теории чисел, при целом
664
N = 2 и P Q≈ для разложения
числа N потребуется около 10
23
операций, то есть задача практически неразрешима
для современных компьютеров.
Другой характерный пример однонаправленной функции является модульная
экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа,
такие, что 1≤ < A N . Определим множество ZN:
{0,1, 2,... 1}. Z N N = −
Тогда модульная экспонента с основанием А по модулю N представляет собой
функцию
,
: ,
A N N N
f Z Z →
,
( ) (mod ),
x
A N
f x A N =
где X – целое число, 1 1. ≤ ≤ − x N
Существуют эффективные алгоритмы, позволяющие достаточно быстро вы-
числить значения функции ,
( ).
A N
f x
Если ,
x
y A = то естественно записать log ( ).
A
x y =
Поэтому задачу обращения функции ( )
,
f x
A N называют задачей нахождения
дискретного логарифма, или задачей дискретного логарифмирования. Задача дис-
кретного логарифмирования формулируется следующим образом. Для известных
целых A,N, y найти целое число x, такое, что
A mod N y.
x
=
Пример
Найти значение x, при котором 3 mod17 13
x
= (остаток от деления на 17).
Найдем значение 3 mod17
x
y = методом перебора: 3
1
=3, 3
2
=9, 3
3
=10, 3
4
=13,
3
5
=5, 3
6
=15, 3
7
=11, 3
8
=16, 3
9
=14, 3
10
=8, 3
11
=7, 3
12
=4, 3
13
=12, 3
14
=2, 3
15
=6, 3
16
=1, …
Таким образом, x = 4 .
Алгоритм вычисления дискретного логарифма за приемлемое время пока не
найден. Поэтому модульная экспонента считается однонаправленной функцией. По
современным оценкам теории чисел, при целых числах A =2
664
и N=2
664
, решение
задачи дискретного логарифмирования (нахождение показателя степени x для из-
вестного y) потребует около 10
26
операций, то есть эта задача имеет в 10
3
раз боль-
шую вычислительную сложность, чем задача разложения на множители. При увели-
чении длины чисел разница в оценках сложности задач возрастает.
Следует отметить, что пока не удалось доказать невозможность существова-
ния эффективного алгоритма вычисления дискретного логарифма за приемлемое
время. Исходя из этого, модульная экспонента отнесена к однонаправленным функ-
циям условно, что, однако, не мешает с успехом применять ее на практике. Вторым
важным классом функций, используемых при построении криптосистем с открытым
ключом, являются так называемые однонаправленные функции с секретом. Дадим
неформальное определение такой функции. Функция
f : X →Y
относится к классу однонаправленных функций с секретом в том случае, если она
является однонаправленной и, кроме того, возможно эффективное вычисление об-ратной функции, если известен секрет (секретное число, строка или другая инфор-
мация, ассоциируемая с данной функцией).
В качестве примера однонаправленной функции с секретом можно указать ис-
пользуемую в криптосистеме RSA модульную экспоненту с фиксированными моду-
лем и показателем степени. Переменное основание модульной экспоненты исполь-
зуется для представления числового значения сообщения М либо криптограммы С.
Как и в случае симметричных криптографических систем, с помощью асим-
метричных криптосистем обеспечивается не только конфиденциальность, но также
подлинность и целостность передаваемой информации. Подлинность и целостность
любого сообщения обеспечивается формированием цифровой подписи этого сооб-
щения и отправкой в зашифрованном виде сообщения вместе с цифровой подписью.
Проверка соответствия подписи полученному сообщению после его предвари-
тельного расшифровывания представляет собой проверку целостности и подлинно-
сти принятого сообщения.
Асимметричные криптографические системы обладают следующими важными
преимуществами перед симметричными криптосистемами:
− в асимметричных криптосистемах решена сложная проблема распределения
ключей между пользователями, так как каждый пользователь может сгенери-
ровать свою пару ключей сам, а открытые ключи пользователей могут свобод-
но публиковаться и распространяться по сетевым коммуникациям;
− исчезает квадратичная зависимость числа ключей от числа пользователей; в
асимметричной криптосистеме количество используемых ключей связано с
количеством абонентов линейной зависимостью (в системе из N пользователей
используется 2× N ключей), а не квадратичной, как в симметричных систе-
мах;
− асимметричные криптосистемы позволяют реализовать протоколы взаимодей-
ствия сторон, которые не доверяют друг другу, поскольку при использовании
асимметричных криптосистем закрытый ключ должен быть известен только
его владельцу.
Однако у асимметричных криптосистем существуют и недостатки:
− на настоящий момент нет математического доказательства необратимости ис-
пользуемых в асимметричных алгоритмах функций;
− по сравнению с симметричным шифрованием, асимметричное существенно
медленнее, поскольку при шифровании и расшифровке используются весьма
ресурсоемкие операции. По этой же причине реализовать аппаратный шифра-
тор с асимметричным алгоритмом существенно сложнее, чем аппаратно сим-
метричный алгоритм;
− необходимо защищать открытые ключи от подмены.
Последнее рассмотрим более подробно. Предположим, на компьютере абонен-
та А хранится открытый ключ KВ абонента В. Злоумышленник n имеет доступ к от-
крытым ключам, хранящимся у абонента А. Он генерирует свою пару ключей Kn и
n
k и подменяет у абонента A открытый ключ KB
абонента B на свой открытый
ключ Kn
.
Для того чтобы отправить некую информацию абоненту B, абонент A зашиф-
ровывает ее на ключе Kn, думая, что это ключ KВ. Соответственно, это сообщение
не сможет прочитать абонент B, но зато легко расшифрует и прочитает злоумыш-ленник n. От подмены открытых ключей может спасти процедура сертификации от-
крытых ключей.
4.3.1.АЛГОРИТМ ШИФРОВАНИЯ RSA
Криптоалгоритм RSA предложили в 1978 году три автора: Р. Райвест (Rivest),
А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по
первым буквам фамилий его авторов. Алгоритм RSA стал первым алгоритмом с от-
крытым ключом, который может работать в режиме как шифрования данных, так и
электронной цифровой подписи.
Надежность алгоритма RSA основывается на трудности факторизации боль-
ших чисел и сложности вычисления дискретных логарифмов в конечном поле.
В алгоритме RSA открытый ключ KB, секретный ключ kB, сообщение М и
криптограмма С принадлежат множеству целых чисел
ZN = {0, 1, 2, ..., N – 1},
где N – модуль:
N = P × Q.
Здесь P и Q – случайные большие простые числа. Для обеспечения макси-
мальной безопасности выбирают P и Q равной длины и хранят в секрете.
Множество ZN с операциями сложения и умножения по модулю N образует
арифметику по модулю N.
Открытый ключ KB выбирают случайным образом так, чтобы выполнялись
следующие условия:
1 K (N), < B ≤ϕ НОД ,1 (KB
,ϕ(N)) =
ϕ(N) = (P − )(1 Q − ),1
где ϕ(N) - функция Эйлера.
Функция Эйлера ϕ(N) указывает количество положительных целых чисел в
интервале от 1 до N, которые взаимно просты с N.
Второе из указанных выше условий означает, что открытый ключ KB и функ-
ция Эйлера ϕ(N) должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида, вычисляют секретный
ключ kB, такой, что
× =1(mod
B KB
k ϕ(N))
или
kB = KB
-1
(mod (P - 1)(Q - 1)).
Это можно осуществить, так как получатель В знает пару простых чисел (P, Q)
и может легко найти ϕ(N). Заметим, что kB и N должны быть взаимно простыми.
Открытый ключ KB используют для шифрования данных, а секретный ключ kB
– для дешифрования.
Процедура шифрования определяет криптограмму С через пару (открытый
ключ KB, сообщение М) в соответствии со следующей формулой:
( ) (mod ).
B
B
K
C E M M N = = K
В качестве алгоритма быстрого вычисления значения C используют ряд по-
следовательных возведений в квадрат целого M и умножений на M с приведением
по модулю N.
Дешифрование криптограммы С выполняют, используя пару (секретный ключ
kB, криптограмма С) по следующей формуле: ( ) (mod ).
B
B
k
M D C C N = = k
Процедуры шифрования и дешифрования в алгоритме RSA
Предположим, что пользователь А хочет передать пользователю В сообщение
в зашифрованном виде, используя алгоритм RSA. В таком случае пользователь А
выступает в роли отправителя сообщения, а пользователь В – в роли получателя.
Как отмечалось выше, криптосистему RSA должен сформировать получатель сооб-
щения, то есть пользователь В. Рассмотрим последовательность действий пользова-
телей В и А:
1) Пользователь В выбирает два произвольных больших простых числа P и Q.
2) Пользователь В вычисляет значение модуля N P Q = × .
3) Пользователь В вычисляет функцию Эйлера
ϕ( ) ( 1)( 1) N P Q = − −
и выбирает случайным образом значение открытого ключа KB с учетом вы-
полнения условий
1 ( ), ( , ( )) 1. < ≤ = K N B B ϕ ϕ НОД K N
4) Пользователь В вычисляет значение секретного ключа kB, используя расши-
ренный алгоритм Евклида при решении сравнения
1
(mod ( )).
B B
k K N ϕ
−
≡
5) Пользователь В пересылает пользователю А пару чисел (N,KB) по незащи-
щенному каналу.
Если пользователь А хочет передать пользователю В сообщение М, он выпол-
няет следующие шаги:
6) Пользователь А разбивает исходный открытый текст М на блоки, каждый из
которых может быть представлен в виде числа
Мi
= 0, 1, 2, ..., N −1.
7) Пользователь А шифрует текст, представленный в виде последовательности
чисел Мi
, по формуле
(mod )
KB C M N i i =
и отправляет криптограмму
С1, С2, С3, ..., Ci
, ...
пользователю В.
Пользователь В расшифровывает принятую криптограмму
С1, С2, С3, ..., Ci
, ...,
используя секретный ключ kB, по формуле
( ) (mod ).
B
B
k
M D C C N = = k
В результате будет получена последовательность чисел Mi
, которые пред-
ставляют собой исходное сообщение М. При практической реализации алгоритма
RSA необходимо иметь возможность без существенных затрат генерировать боль-
шие простые числа, уметь оперативно вычислять значения ключей KB и kB.
Пример:
Шифрование сообщения «САВ» и его дешифрование.
Для простоты вычислений будут использоваться небольшие числа. На практи-
ке применяются очень большие числа (длиной 250-300 десятичных разрядов).
Действия пользователя В:
1) Выбирает P = 3 и Q = 11. 2) Вычисляет модуль N P Q = × = × = 3 11 33.
3) Вычисляет значение функции Эйлера для N = 33:
ϕ ϕ ( ) (33) ( 1)( 1) 2 10 20. N P Q = = − − = × =
Выбирает в качестве открытого ключа KB произвольное число с учетом вы-
полнения условий
1 20, ( , 20) 1. < < = KB B НОД K
Пусть KB = 7.
4) Вычисляет значение секретного ключа kB, используя расширенный алгоритм
Евклида при решении сравнения
7 1(mod 20).
B
k = −
Решение дает kB = 3.
5) Пересылает пользователю А пару чисел (N = 33, KB = 7).
Действия пользователя A:
6) Представляет шифруемое сообщение как последовательность целых чисел в
диапазоне 0-32. Пусть буква А представляется как число 1, буква В - как чис-
ло 2, буква С - как число 3. Тогда сообщение САВ можно представить как
последовательность чисел 312, то есть М1 = 3, М2 = 1, М3 = 2.
7) Шифрует текст, представленный в виде последовательности чисел М1, М2 и
М3, используя ключ KB = 7 и N = 33, по формуле
7
(mod ) (mod 33).
KB C M N M i i i = =
Получает
С1 = 3
7
(mod 33) = 2187(mod 33) = 9,
С2 = 1
7
(mod 33) = 1(mod 33) = 1,
С3 = 2
7
(mod 33) = 128(mod 33) = 29.
Отправляет пользователю В криптограмму
C1, C2, C3 =9, 1, 29.
Действия пользователя В:
Расшифровывает принятую криптограмму С1, С2, С3, используя секретный
ключ kB = 3, по формуле
(mod ) (mod33).
3
i
k
Mi = Ci
B N = C
Получает
М1 = 9
3
(mod 33) = 729(mod 33) = 3,
М2 = 1
3
(mod 33) = 1(mod 33) = 1,
М3 = 29
3
(mod 33) = 24389(mod 33) = 2.
Таким образом, восстановлено исходное сообщение САВ: 312.
Криптоалгоритм RSA всесторонне исследован и признан стойким при доста-
точной длине ключей. В настоящее время длина ключа 1024 бит считается прием-
лемым вариантом. Существует мнение, что с ростом мощности процессоров крип-
тоалгоритм RSA потеряет стойкость к атаке полного перебора. Однако увеличение
мощности процессоров позволит применять более длинные ключи, что повышает
стойкость RSA. Следует отметить, что алгоритм RSA можно применять как для
шифрования сообщений, так и для электронной цифровой подписи.
Нетрудно видеть, что в асимметричной криптосистеме RSA количество ис-
пользуемых ключей связано с количеством абонентов линейной зависимостью (в
системе из N пользователей используется 2 × N ключей), а не квадратичной, как в
симметричных системах. Сравнивая наиболее популярных представителей асимметричного и симмет-
ричного шифрования, следует отметить, что быстродействие RSA существенно ни-
же быстродействия DES, а программная и аппаратная реализация криптоалгоритма
RSA гораздо сложнее, чем DES. Поэтому криптосистема RSA, как правило, исполь-
зуется при передаче сообщений небольшого объема.
4.3.2.АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ НА БАЗЕ ЭЛЕПТИЧЕСКИХ
КРИВЫХ
К криптосистемам третьего тысячелетия, несомненно, следует отнести асим-
метричные криптосистемы на базе эллиптических кривых. Криптосистемы на базе
эллиптических кривых позволяют реализовать криптоалгоритм асимметричного
шифрования, протокол выработки разделяемого секретного ключа для симметрич-
ного шифрования и криптоалгоритмы электронной цифровой подписи [xxx].
Криптосистемы на базе эллиптических кривых имеют более высокую произ-
водительность и позволяют использовать существенно меньшие размеры ключей
при сохранении требуемого уровня безопасности.
Для различных реализаций используются эллиптические кривые двух видов:
− эллиптическая кривая в конечном поле Fp
, где р – простое число, p > 3;
− эллиптическая кривая в конечном поле
2
m
F .
Эллиптическая кривая в конечном поле Fp
Пусть задано простое число р > 3. Тогда эллиптической кривой Е, определен-
ной над конечным простым полем Fp, называется множество пар чисел (x, y), x∈Fp,
y∈Fp, удовлетворяющих тождеству
2 2
y x ax b p ≡ + + (mod ), (4.1)
где a, b ∈ Fp и 4a
3
+ 27b
2
не сравнимо с нулем по модулю р.
Инвариантом эллиптической кривой называется величина J(E), удовлетво-
ряющая тождеству
3
3 2
4
( ) 1728 (mod ).
4 27
a
J E p
a b
=
+
Коэффициенты a, b эллиптической кривой Е по известному инварианту J E( )
определяются следующим образом:
3 (mod )
2 (mod ),
a k p
b k p
≡
≡
где
( )
(mod ), ( ) 0
1728 ( )
J E
k p J E
J E
= ≠
−
или 1728.
Пары (x, y), удовлетворяющие тождеству (4.1), называются точками эллипти-
ческой кривой Е; х и у – соответственно х- и у- координатами точки.
Точки эллиптической кривой будем обозначать Q(x, у) или просто Q. Две точ-
ки эллиптической кривой равны, если равны их соответствующие х- и у-
координаты.
На множестве всех точек эллиптической кривой E введем операцию сложения,
которую будем обозначать знаком +. Для двух произвольных точек Q1(x1, у1) и
Q2(х2, у2) эллиптической кривой Е рассмотрим несколько вариантов.
Пусть координаты точек Q1 и Q2 удовлетворяют условию x1≠ x2. В этом случае
их суммой будем называть точку Q3(x3, y3), координаты которой определяются
сравнениями 2
3 1 2
3 1 3
(mod )
( ) (mod )
x x x p
y x x y p
λ
λ
≡ − −
≡ − −
, где (mod ).
2 1
2 1
p
x x
y y
−
−
λ ≡
Если выполнены равенства x1 = x2 и y1 = y2 ≠0 , то определим координаты
точки Q3 следующим образом:
2
3 1
3 1 3 1
2 (mod )
,
( ) (mod )
x x p
y x x y p
λ
λ
≡ −
≡ − −
где (mod ).
2
3 2
1
2
1
p
y
x + a
λ ≡
В случае когда выполнено условие х1 = х2 и 1 2
y y p = − (mod ), сумму точек Q1 и
Q2 будем называть нулевой точкой О, не определяя ее х- и у- координаты. В этом
случае точка Q2 называется отрицанием точки Q1. Для нулевой точки О выполнены
равенства
Q + О = О + Q = Q,
где Q - произвольная точка эллиптической кривой Е.
Относительно введенной операции сложения множество всех точек эллипти-
ческой кривой Е, вместе с нулевой точкой, образуют конечную абелеву (коммута-
тивную) группу порядка m, для которого выполнено неравенство
p +1− 2 p ≤ m ≤ p +1+ 2 p.
Точка Q называется точкой кратности k, или просто кратной точкой эллипти-
ческой кривой Е, если для некоторой точки Р выполнено равенство
Q P ... P kP.
k
= 142+ 43+ =
Эллиптическая кривая в конечном поле
2
F m определяется соотношением
2 3 2
y xy x ax b + ≡ + +
при ненулевом b.
Эллиптической кривой
2
E F( ) m , является группа решений
2 2
( , ), , x y x F y F ∈ ∈ m m
приведенного выше соотношения при определенных значениях a и b, а также нуле-
вая точка О.
Аналогично группе эллиптической кривой ( ) E Fp
, множество всех точек эл-
липтической кривой
2
E F( ) m вместе с нулевой точкой образуют конечную абелеву
группу.
С помощью описанных выше правил сложения можно вычислить точку kP для
любого целого числа k и любой точки P эллиптической кривой.
Однако решение обратной задачи – нахождение числа k по известным точкам
P и kP – является слишком трудным. Данную задачу называют проблемой дискрет-
ного логарифма эллиптической кривой ECDLP (Elliptic Curve Discrete Logariphm
Problem).
Решение проблемы ECDLP является значительно более сложным, чем пробле-
мы дискретного логарифмирования (нахождение числа x по заданному числу
mod
x
y g p = при известных основании g и модуле p), на которой базируются RSA-
подобные асимметричные криптосистемы.
Сложность решения проблемы ECDLP обусловлена ресурсоемкостью опера-
ций сложения и дублирования точек, с помощью которых вычисляется kP, как вид-
но из приведенных выше формул. Отсюда следует возможность применения более
коротких ключей. Например, ключу размером 1024 бит алгоритма DSA соответст-вует по криптостойкости ключ размером 160 бит алгоритма ECDSA (DSA на эллип-
тических кривых).
Существует несколько реализаций известных криптоалгоритмов на базе эл-
липтических кривых (стандартизованы в IEEE P1363).
4.3.3.АЛОРИТМ АСИММЕТРИЧНОГО ШИФРОВАНИЯ ECES
В алгоритме ЕСЕS (Elliptic Сurve Епcryption Scheme) сначала должны быть
определены следующие параметры, являющиеся открытой информацией, общей для
всех пользователей системы:
− конечное поле Fq;
− эллиптическая кривая E(Fq);
− большой простой делитель количества точек кривой n;
− точка Р, координаты которой должны иметь тот же порядок, что и число n.
Каждый пользователь системы генерирует пару ключей следующим образом:
− выбирается случайное целое число d d n ,1 1 < < − .
− вычисляется точка Q dP = .
Секретным ключом пользователя является число d, открытым ключом – точка
Q.
Шифрование сообщения (пользователь А шифрует сообщение М для пользова-
теля В):
− сообщение разбивается на блоки Mi
, которые определенным образом допол-
няются слева (длина каждого блока равна 2L – 16 бит, где L равно ближайше-
му большему целому от
2
log q );
− полученный блок разбивается на две части равной длины: mi1 и mi2;
− выбирается случайное целое число k k n ,1 1 < < − ;
− вычисляется точка (x1, y1) = kP;
− вычисляется точка (x2, y2) = kQB;
− с помощью определенного преобразования из mi1, mi2 и x2 получают c1 и c2;
− зашифрованные данные: (x1, y1, c1, c2).
Дешифрование сообщения (пользователь В расшифровывает полученное от
пользователя А зашифрованное сообщение):
− вычисляется точка (x2, y2) = d(x1, y1);
− восстанавливается исходное сообщение mi1, mi2 из c1, c2 и x2.
Асимметричные криптографические системы были разработаны в 1970-х го-
дах. Принципиальное отличие асимметричной криптосистемы от криптосистемы
симметричного шифрования состоит в том, что для шифрования информации и ее
последующего дешифрования используются различные ключи:
− открытый ключ K: используется для шифрования информации, вычисляется из
секретного ключа k;
− секретный ключ k: используется для дешифрования информации, зашифро-
ванной с помощью парного ему открытого ключа K.
Эти ключи различаются таким образом, что с помощью вычислений нельзя
вывести секретный ключ k из открытого ключа K. Поэтому открытый ключ K может
свободно передаваться по каналам связи.
Асимметричные системы называют еще двухключевыми криптографическими
системами или криптосистемами с открытым ключом.
Обобщенная схема асимметричной криптосистемы шифрования с открытым
ключом показана на рис. 1.19.
Для криптографического закрытия и последующего дешифрования передавае-
мой информации используются открытый и секретный ключи получателя сообще-
ния В. В качестве ключа шифрования должен использоваться открытый ключ полу-
чателя КВ, а в качестве ключа дешифрования – его секретный ключ kB.
Секретный и открытый ключи генерируются попарно. Секретный ключ дол-
жен оставаться у его владельца; он должен быть надежно защищен от несанкциони-
рованного доступа (аналогично ключу шифрования в симметричных алгоритмах).
Копия открытого ключа должна иметься у каждого абонента криптографической
сети, с которым обменивается информацией владелец секретного ключа.
Процесс передачи зашифрованной информации в асимметричной криптоси-
стеме осуществляется следующим образом:
1) Подготовительный этап. Абонент В генерирует пару ключей: секретный
ключ kB и открытый ключ Кв. Открытый ключ KB посылается абоненту А и
остальным абонентам (или делается доступным, например, на разделяемом
ресурсе).
2) Использование - обмен информацией между абонентами А и В. Абонент А
зашифровывает сообщение с помощью открытого ключа КВ абонента В и от-
Отправитель A
Получатель B
Сообщение М
Шифрование
ЕB
Секретный ключ
получателя kB
Сообщение М
’
Дешифрование
DB
Незащищенный
канал
связи / хранения
Шифротекст С
Открытый ключ получателя KB
KB
Рис. 1.19. Обобщенная схема асимметричной криптосистемы шифрованияправляет шифротекст абоненту В. Абонент В расшифровывает сообщение с
помощью своего секретного ключа kB. Никто другой (в том числе абонент А)
не может расшифровать данное сообщение, так как не имеет секретного
ключа абонента В. Защита информации в асимметричной криптосистеме ос-
нована на секретности ключа kB получателя сообщения.
Отметим характерные особенности асимметричных криптосистем:
1) Открытый ключ КВ и криптограмма С могут быть отправлены по незащи-
щенным каналам, то есть противнику известны КВ и С.
2) Алгоритмы шифрования и дешифрования
: ,
:
B
B
E M C
D C M
→
→
являются открытыми.
У. Диффи и М. Хеллман сформулировали требования, выполнение которых
обеспечивает безопасность асимметричной криптосистемы [xxx]:
1) Вычисление пары ключей (КB, kB) получателем В на основе начального усло-
вия должно быть простым.
2) Отправитель A, зная открытый ключ КB и сообщение M, может легко вычис-
лить криптограмму
( ).
KB
C E M =
3) Получатель В, используя секретный ключ kB и криптограмму С, может легко
восстановить исходное сообщение
( ).
B M D C = k
4) Противник, зная открытый ключ KB, при попытке вычислить секретный
ключ kB наталкивается на непреодолимую вычислительную проблему.
5) Противник, зная пару (KВ,С), при попытке вычислить исходное сообщение М
наталкивается на непреодолимую вычислительную проблему.
Концепция асимметричных криптографических систем с открытым ключом
основана на применении однонаправленных функций. Неформально однонаправ-
ленную функцию можно определить следующим образом [xxx]. Пусть X и Y - неко-
торые произвольные множества. Функция f : X Y → является однонаправленной,
если для всех x X ∈ можно легко вычислить функцию
y = f (x), где y ∈Y.
И в то же время для большинства y ∈Y достаточно сложно получить значение
x∈ X , такое, что f (x) = y (при этом полагают, что существует по крайней
мере одно такое значение x ).
Основным критерием отнесения функции f к классу однонаправленных
функций является отсутствие эффективных алгоритмов обратного преобразования
Y X → .
В качестве примера однонаправленной функции можно указать целочисленное
умножение. Прямая задача – вычисление произведения двух очень больших целых
чисел P и Q, то есть нахождение значения
N P Q = ×
является относительно несложной задачей для компьютера.
Обратная задача - факторизация, или разложение на множители большого це-
лого числа, то есть нахождение делителей P и Q большого целого числа N P Q = ×является практически неразрешимой задачей при достаточно больших значениях N.
По современным оценкам теории чисел, при целом
664
N = 2 и P Q≈ для разложения
числа N потребуется около 10
23
операций, то есть задача практически неразрешима
для современных компьютеров.
Другой характерный пример однонаправленной функции является модульная
экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа,
такие, что 1≤ < A N . Определим множество ZN:
{0,1, 2,... 1}. Z N N = −
Тогда модульная экспонента с основанием А по модулю N представляет собой
функцию
,
: ,
A N N N
f Z Z →
,
( ) (mod ),
x
A N
f x A N =
где X – целое число, 1 1. ≤ ≤ − x N
Существуют эффективные алгоритмы, позволяющие достаточно быстро вы-
числить значения функции ,
( ).
A N
f x
Если ,
x
y A = то естественно записать log ( ).
A
x y =
Поэтому задачу обращения функции ( )
,
f x
A N называют задачей нахождения
дискретного логарифма, или задачей дискретного логарифмирования. Задача дис-
кретного логарифмирования формулируется следующим образом. Для известных
целых A,N, y найти целое число x, такое, что
A mod N y.
x
=
Пример
Найти значение x, при котором 3 mod17 13
x
= (остаток от деления на 17).
Найдем значение 3 mod17
x
y = методом перебора: 3
1
=3, 3
2
=9, 3
3
=10, 3
4
=13,
3
5
=5, 3
6
=15, 3
7
=11, 3
8
=16, 3
9
=14, 3
10
=8, 3
11
=7, 3
12
=4, 3
13
=12, 3
14
=2, 3
15
=6, 3
16
=1, …
Таким образом, x = 4 .
Алгоритм вычисления дискретного логарифма за приемлемое время пока не
найден. Поэтому модульная экспонента считается однонаправленной функцией. По
современным оценкам теории чисел, при целых числах A =2
664
и N=2
664
, решение
задачи дискретного логарифмирования (нахождение показателя степени x для из-
вестного y) потребует около 10
26
операций, то есть эта задача имеет в 10
3
раз боль-
шую вычислительную сложность, чем задача разложения на множители. При увели-
чении длины чисел разница в оценках сложности задач возрастает.
Следует отметить, что пока не удалось доказать невозможность существова-
ния эффективного алгоритма вычисления дискретного логарифма за приемлемое
время. Исходя из этого, модульная экспонента отнесена к однонаправленным функ-
циям условно, что, однако, не мешает с успехом применять ее на практике. Вторым
важным классом функций, используемых при построении криптосистем с открытым
ключом, являются так называемые однонаправленные функции с секретом. Дадим
неформальное определение такой функции. Функция
f : X →Y
относится к классу однонаправленных функций с секретом в том случае, если она
является однонаправленной и, кроме того, возможно эффективное вычисление об-ратной функции, если известен секрет (секретное число, строка или другая инфор-
мация, ассоциируемая с данной функцией).
В качестве примера однонаправленной функции с секретом можно указать ис-
пользуемую в криптосистеме RSA модульную экспоненту с фиксированными моду-
лем и показателем степени. Переменное основание модульной экспоненты исполь-
зуется для представления числового значения сообщения М либо криптограммы С.
Как и в случае симметричных криптографических систем, с помощью асим-
метричных криптосистем обеспечивается не только конфиденциальность, но также
подлинность и целостность передаваемой информации. Подлинность и целостность
любого сообщения обеспечивается формированием цифровой подписи этого сооб-
щения и отправкой в зашифрованном виде сообщения вместе с цифровой подписью.
Проверка соответствия подписи полученному сообщению после его предвари-
тельного расшифровывания представляет собой проверку целостности и подлинно-
сти принятого сообщения.
Асимметричные криптографические системы обладают следующими важными
преимуществами перед симметричными криптосистемами:
− в асимметричных криптосистемах решена сложная проблема распределения
ключей между пользователями, так как каждый пользователь может сгенери-
ровать свою пару ключей сам, а открытые ключи пользователей могут свобод-
но публиковаться и распространяться по сетевым коммуникациям;
− исчезает квадратичная зависимость числа ключей от числа пользователей; в
асимметричной криптосистеме количество используемых ключей связано с
количеством абонентов линейной зависимостью (в системе из N пользователей
используется 2× N ключей), а не квадратичной, как в симметричных систе-
мах;
− асимметричные криптосистемы позволяют реализовать протоколы взаимодей-
ствия сторон, которые не доверяют друг другу, поскольку при использовании
асимметричных криптосистем закрытый ключ должен быть известен только
его владельцу.
Однако у асимметричных криптосистем существуют и недостатки:
− на настоящий момент нет математического доказательства необратимости ис-
пользуемых в асимметричных алгоритмах функций;
− по сравнению с симметричным шифрованием, асимметричное существенно
медленнее, поскольку при шифровании и расшифровке используются весьма
ресурсоемкие операции. По этой же причине реализовать аппаратный шифра-
тор с асимметричным алгоритмом существенно сложнее, чем аппаратно сим-
метричный алгоритм;
− необходимо защищать открытые ключи от подмены.
Последнее рассмотрим более подробно. Предположим, на компьютере абонен-
та А хранится открытый ключ KВ абонента В. Злоумышленник n имеет доступ к от-
крытым ключам, хранящимся у абонента А. Он генерирует свою пару ключей Kn и
n
k и подменяет у абонента A открытый ключ KB
абонента B на свой открытый
ключ Kn
.
Для того чтобы отправить некую информацию абоненту B, абонент A зашиф-
ровывает ее на ключе Kn, думая, что это ключ KВ. Соответственно, это сообщение
не сможет прочитать абонент B, но зато легко расшифрует и прочитает злоумыш-ленник n. От подмены открытых ключей может спасти процедура сертификации от-
крытых ключей.
4.3.1.АЛГОРИТМ ШИФРОВАНИЯ RSA
Криптоалгоритм RSA предложили в 1978 году три автора: Р. Райвест (Rivest),
А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по
первым буквам фамилий его авторов. Алгоритм RSA стал первым алгоритмом с от-
крытым ключом, который может работать в режиме как шифрования данных, так и
электронной цифровой подписи.
Надежность алгоритма RSA основывается на трудности факторизации боль-
ших чисел и сложности вычисления дискретных логарифмов в конечном поле.
В алгоритме RSA открытый ключ KB, секретный ключ kB, сообщение М и
криптограмма С принадлежат множеству целых чисел
ZN = {0, 1, 2, ..., N – 1},
где N – модуль:
N = P × Q.
Здесь P и Q – случайные большие простые числа. Для обеспечения макси-
мальной безопасности выбирают P и Q равной длины и хранят в секрете.
Множество ZN с операциями сложения и умножения по модулю N образует
арифметику по модулю N.
Открытый ключ KB выбирают случайным образом так, чтобы выполнялись
следующие условия:
1 K (N), < B ≤ϕ НОД ,1 (KB
,ϕ(N)) =
ϕ(N) = (P − )(1 Q − ),1
где ϕ(N) - функция Эйлера.
Функция Эйлера ϕ(N) указывает количество положительных целых чисел в
интервале от 1 до N, которые взаимно просты с N.
Второе из указанных выше условий означает, что открытый ключ KB и функ-
ция Эйлера ϕ(N) должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида, вычисляют секретный
ключ kB, такой, что
× =1(mod
B KB
k ϕ(N))
или
kB = KB
-1
(mod (P - 1)(Q - 1)).
Это можно осуществить, так как получатель В знает пару простых чисел (P, Q)
и может легко найти ϕ(N). Заметим, что kB и N должны быть взаимно простыми.
Открытый ключ KB используют для шифрования данных, а секретный ключ kB
– для дешифрования.
Процедура шифрования определяет криптограмму С через пару (открытый
ключ KB, сообщение М) в соответствии со следующей формулой:
( ) (mod ).
B
B
K
C E M M N = = K
В качестве алгоритма быстрого вычисления значения C используют ряд по-
следовательных возведений в квадрат целого M и умножений на M с приведением
по модулю N.
Дешифрование криптограммы С выполняют, используя пару (секретный ключ
kB, криптограмма С) по следующей формуле: ( ) (mod ).
B
B
k
M D C C N = = k
Процедуры шифрования и дешифрования в алгоритме RSA
Предположим, что пользователь А хочет передать пользователю В сообщение
в зашифрованном виде, используя алгоритм RSA. В таком случае пользователь А
выступает в роли отправителя сообщения, а пользователь В – в роли получателя.
Как отмечалось выше, криптосистему RSA должен сформировать получатель сооб-
щения, то есть пользователь В. Рассмотрим последовательность действий пользова-
телей В и А:
1) Пользователь В выбирает два произвольных больших простых числа P и Q.
2) Пользователь В вычисляет значение модуля N P Q = × .
3) Пользователь В вычисляет функцию Эйлера
ϕ( ) ( 1)( 1) N P Q = − −
и выбирает случайным образом значение открытого ключа KB с учетом вы-
полнения условий
1 ( ), ( , ( )) 1. < ≤ = K N B B ϕ ϕ НОД K N
4) Пользователь В вычисляет значение секретного ключа kB, используя расши-
ренный алгоритм Евклида при решении сравнения
1
(mod ( )).
B B
k K N ϕ
−
≡
5) Пользователь В пересылает пользователю А пару чисел (N,KB) по незащи-
щенному каналу.
Если пользователь А хочет передать пользователю В сообщение М, он выпол-
няет следующие шаги:
6) Пользователь А разбивает исходный открытый текст М на блоки, каждый из
которых может быть представлен в виде числа
Мi
= 0, 1, 2, ..., N −1.
7) Пользователь А шифрует текст, представленный в виде последовательности
чисел Мi
, по формуле
(mod )
KB C M N i i =
и отправляет криптограмму
С1, С2, С3, ..., Ci
, ...
пользователю В.
Пользователь В расшифровывает принятую криптограмму С1, С2, С3, ..., Ci
, ...,
используя секретный ключ kB, по формуле
( ) (mod ).
B
B
k
M D C C N = = k
В результате будет получена последовательность чисел Mi
, которые пред-
ставляют собой исходное сообщение М. При практической реализации алгоритма
RSA необходимо иметь возможность без существенных затрат генерировать боль-
шие простые числа, уметь оперативно вычислять значения ключей KB и kB.
Пример:
Шифрование сообщения «САВ» и его дешифрование.
Для простоты вычислений будут использоваться небольшие числа. На практи-
ке применяются очень большие числа (длиной 250-300 десятичных разрядов).
Действия пользователя В:
1) Выбирает P = 3 и Q = 11. 2) Вычисляет модуль N P Q = × = × = 3 11 33.
3) Вычисляет значение функции Эйлера для N = 33:
ϕ ϕ ( ) (33) ( 1)( 1) 2 10 20. N P Q = = − − = × =
Выбирает в качестве открытого ключа KB произвольное число с учетом вы-
полнения условий
1 20, ( , 20) 1. < < = KB B НОД K
Пусть KB = 7.
4) Вычисляет значение секретного ключа kB, используя расширенный алгоритм
Евклида при решении сравнения
7 1(mod 20).
B
k = −
Решение дает kB = 3.
5) Пересылает пользователю А пару чисел (N = 33, KB = 7).
Действия пользователя A:
6) Представляет шифруемое сообщение как последовательность целых чисел в
диапазоне 0-32. Пусть буква А представляется как число 1, буква В - как чис-
ло 2, буква С - как число 3. Тогда сообщение САВ можно представить как
последовательность чисел 312, то есть М1 = 3, М2 = 1, М3 = 2.
7) Шифрует текст, представленный в виде последовательности чисел М1, М2 и
М3, используя ключ KB = 7 и N = 33, по формуле
7
(mod ) (mod 33).
KB C M N M i i i = =
Получает
С1 = 3
7
(mod 33) = 2187(mod 33) = 9,
С2 = 1
7
(mod 33) = 1(mod 33) = 1,
С3 = 2
7
(mod 33) = 128(mod 33) = 29.
Отправляет пользователю В криптограмму
C1, C2, C3 =9, 1, 29.
Действия пользователя В:
Расшифровывает принятую криптограмму С1, С2, С3, используя секретныйключ kB = 3, по формуле
(mod ) (mod33).
3
i
k
Mi = Ci
B N = C
Получает
М1 = 9
3
(mod 33) = 729(mod 33) = 3,
М2 = 1
3
(mod 33) = 1(mod 33) = 1,
М3 = 29
3
(mod 33) = 24389(mod 33) = 2.
Таким образом, восстановлено исходное сообщение САВ: 312.
Криптоалгоритм RSA всесторонне исследован и признан стойким при доста-
точной длине ключей. В настоящее время длина ключа 1024 бит считается прием-
лемым вариантом. Существует мнение, что с ростом мощности процессоров крип-
тоалгоритм RSA потеряет стойкость к атаке полного перебора. Однако увеличение
мощности процессоров позволит применять более длинные ключи, что повышает
стойкость RSA. Следует отметить, что алгоритм RSA можно применять как для
шифрования сообщений, так и для электронной цифровой подписи.
Нетрудно видеть, что в асимметричной криптосистеме RSA количество ис-
пользуемых ключей связано с количеством абонентов линейной зависимостью (в
системе из N пользователей используется 2 × N ключей), а не квадратичной, как в
симметричных системах. Сравнивая наиболее популярных представителей асимметричного и симмет-
ричного шифрования, следует отметить, что быстродействие RSA существенно ни-
же быстродействия DES, а программная и аппаратная реализация криптоалгоритма
RSA гораздо сложнее, чем DES. Поэтому криптосистема RSA, как правило, исполь-
зуется при передаче сообщений небольшого объема.
4.3.2.АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ НА БАЗЕ ЭЛЕПТИЧЕСКИХ
КРИВЫХ
К криптосистемам третьего тысячелетия, несомненно, следует отнести асим-
метричные криптосистемы на базе эллиптических кривых. Криптосистемы на базе
эллиптических кривых позволяют реализовать криптоалгоритм асимметричного
шифрования, протокол выработки разделяемого секретного ключа для симметрич-
ного шифрования и криптоалгоритмы электронной цифровой подписи [xxx].
Криптосистемы на базе эллиптических кривых имеют более высокую произ-
водительность и позволяют использовать существенно меньшие размеры ключей
при сохранении требуемого уровня безопасности.
Для различных реализаций используются эллиптические кривые двух видов:
− эллиптическая кривая в конечном поле Fp
, где р – простое число, p > 3;
− эллиптическая кривая в конечном поле
2
m
F .
Эллиптическая кривая в конечном поле Fp
Пусть задано простое число р > 3. Тогда эллиптической кривой Е, определен-
ной над конечным простым полем Fp, называется множество пар чисел (x, y), x∈Fp,
y∈Fp, удовлетворяющих тождеству
2 2
y x ax b p ≡ + + (mod ), (4.1)
где a, b ∈ Fp и 4a
3
+ 27b
2
не сравнимо с нулем по модулю р.
Инвариантом эллиптической кривой называется величина J(E), удовлетво-
ряющая тождеству
3
3 2
4
( ) 1728 (mod ).
4 27
a
J E p
a b
=
+
Коэффициенты a, b эллиптической кривой Е по известному инварианту J E( )
определяются следующим образом:
3 (mod )
2 (mod ),
a k p
b k p
≡
≡
где
( )
(mod ), ( ) 0
1728 ( )
J E
k p J E
J E
= ≠
−
или 1728.
Пары (x, y), удовлетворяющие тождеству (4.1), называются точками эллипти-
ческой кривой Е; х и у – соответственно х- и у- координатами точки.
Точки эллиптической кривой будем обозначать Q(x, у) или просто Q. Две точ-
ки эллиптической кривой равны, если равны их соответствующие х- и у-
координаты.
На множестве всех точек эллиптической кривой E введем операцию сложения,
которую будем обозначать знаком +. Для двух произвольных точек Q1(x1, у1) и
Q2(х2, у2) эллиптической кривой Е рассмотрим несколько вариантов.
Пусть координаты точек Q1 и Q2 удовлетворяют условию x1≠ x2. В этом случае
их суммой будем называть точку Q3(x3, y3), координаты которой определяются
сравнениями 2
3 1 2
3 1 3
(mod )
( ) (mod )
x x x p
y x x y p
λ
λ
≡ − −
≡ − −
, где (mod ).
2 1
2 1
p
x x
y y
−
−
λ ≡
Если выполнены равенства x1 = x2 и y1 = y2 ≠0 , то определим координаты
точки Q3 следующим образом:
2
3 1
3 1 3 1
2 (mod )
,
( ) (mod )
x x p
y x x y p
λ
λ
≡ −
≡ − −
где (mod ).
2
3 2
1
2
1
p
y
x + a
λ ≡
В случае когда выполнено условие х1 = х2 и 1 2
y y p = − (mod ), сумму точек Q1 и
Q2 будем называть нулевой точкой О, не определяя ее х- и у- координаты. В этом
случае точка Q2 называется отрицанием точки Q1. Для нулевой точки О выполнены
равенства
Q + О = О + Q = Q,
где Q - произвольная точка эллиптической кривой Е.
Относительно введенной операции сложения множество всех точек эллипти-
ческой кривой Е, вместе с нулевой точкой, образуют конечную абелеву (коммута-
тивную) группу порядка m, для которого выполнено неравенство
p +1− 2 p ≤ m ≤ p +1+ 2 p.
Точка Q называется точкой кратности k, или просто кратной точкой эллипти-
ческой кривой Е, если для некоторой точки Р выполнено равенство
Q P ... P kP.
k
= 142+ 43+ =
Эллиптическая кривая в конечном поле
2
F m определяется соотношением
2 3 2
y xy x ax b + ≡ + +
при ненулевом b.
Эллиптической кривой
2
E F( ) m , является группа решений
2 2
( , ), , x y x F y F ∈ ∈ m m
приведенного выше соотношения при определенных значениях a и b, а также нуле-
вая точка О.
Аналогично группе эллиптической кривой ( ) E Fp
, множество всех точек эл-
липтической кривой
2
E F( ) m вместе с нулевой точкой образуют конечную абелеву
группу.
С помощью описанных выше правил сложения можно вычислить точку kP для
любого целого числа k и любой точки P эллиптической кривой.
Однако решение обратной задачи – нахождение числа k по известным точкам
P и kP – является слишком трудным. Данную задачу называют проблемой дискрет-
ного логарифма эллиптической кривой ECDLP (Elliptic Curve Discrete Logariphm
Problem).
Решение проблемы ECDLP является значительно более сложным, чем пробле-
мы дискретного логарифмирования (нахождение числа x по заданному числу
mod
x
y g p = при известных основании g и модуле p), на которой базируются RSA-
подобные асимметричные криптосистемы.
Сложность решения проблемы ECDLP обусловлена ресурсоемкостью опера-
ций сложения и дублирования точек, с помощью которых вычисляется kP, как вид-
но из приведенных выше формул. Отсюда следует возможность применения более
коротких ключей. Например, ключу размером 1024 бит алгоритма DSA соответст-вует по криптостойкости ключ размером 160 бит алгоритма ECDSA (DSA на эллип-
тических кривых).
Существует несколько реализаций известных криптоалгоритмов на базе эл-
липтических кривых (стандартизованы в IEEE P1363).
4.3.3.АЛОРИТМ АСИММЕТРИЧНОГО ШИФРОВАНИЯ ECES
В алгоритме ЕСЕS (Elliptic Сurve Епcryption Scheme) сначала должны быть
определены следующие параметры, являющиеся открытой информацией, общей для
всех пользователей системы:
− конечное поле Fq;
− эллиптическая кривая E(Fq);
− большой простой делитель количества точек кривой n;
− точка Р, координаты которой должны иметь тот же порядок, что и число n.
Каждый пользователь системы генерирует пару ключей следующим образом:
− выбирается случайное целое число d d n ,1 1 < < − .
− вычисляется точка Q dP = .
Секретным ключом пользователя является число d, открытым ключом – точка
Q.
Шифрование сообщения (пользователь А шифрует сообщение М для пользова-
теля В):
− сообщение разбивается на блоки Mi
, которые определенным образом допол-
няются слева (длина каждого блока равна 2L – 16 бит, где L равно ближайше-
му большему целому от
2
log q );
− полученный блок разбивается на две части равной длины: mi1 и mi2;
− выбирается случайное целое число k k n ,1 1 < < − ;
− вычисляется точка (x1, y1) = kP;
− вычисляется точка (x2, y2) = kQB;
− с помощью определенного преобразования из mi1, mi2 и x2 получают c1 и c2;
− зашифрованные данные: (x1, y1, c1, c2).
Дешифрование сообщения (пользователь В расшифровывает полученное от
пользователя А зашифрованное сообщение):
− вычисляется точка (x2, y2) = d(x1, y1);
− восстанавливается исходное сообщение mi1, mi2 из c1, c2 и x2.
