"Современная двухключевая криптография"

СОДЕРЖАНИЕ

1 ВВЕДЕНИЕ. ПРИНЦИПЫ КРИПТОГРАФИЧЕСКОЙ ЗАЩИТЫ ИНФОРМАЦИИ
2 АСИММЕТРИЧНЫЕ КРИПТОСИСТЕМЫ
2.1 Концепция криптосистемы с открытым ключом
2.2 Однонаправленные функции
2.3 Криптосистема шифрования данных RSA
2.4 Процедуры шифрования и расшифрования в криптосистеме RSA
3 АЛГОРИТМЫ, ОСНОВАННЫЕ НА ШИФРОВАНИИ ПО МЕТОДУ RSA
3.1Схема шифрования Полига-Хеллмана
3.2 Схема шифрования Эль Гамаля
3.3 Комбинированный метод шифрования
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

"Современная двухключевая криптография"

2.3 Криптосистема шифрования данных RSA
Алгоритм RSA предложили в 1978 г. три автора: Р. Райвест (Rivest), А. Шамир (Shamir) и А. Адлеман (Adleman)2. Алгоритм по­лучил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.
Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.
В криптосистеме RSA открытый ключ Кв, секретный Ключ кв, сообщение М и криптограмма С принадлежат множеству целых чисел Zn = ={0,1,2, …, N-1},где N - модуль: N = P*Q.
Здесь Р и Q-случайные большие простые числа. Для обес­печения максимальной безопасности выбирают Р и Q равной дли­ны и хранят в секрете.
Множество ZN с операциями сложения и умножения по моду­лю N образует арифметику по модулю N.
Открытый ключ Кв выбирают случайным образом так, чтобы выполнялись условия: 1<Kв≤φ(N), НОД(Kв, φ(N))=1, φ(N)=(P-1)(Q-1) где φ(N) – функция Эйлера. Функция Эйлера φ(N) указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.
Второе из указанных выше условий означает, что открытый ключ Кв и функция Эйлера φ(N) должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ кв, такой, что kB*KB≡1(mod φ(N)) или
kB=KB -1(mod(P-1)(Q-1)) (*)
Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти φ(N). Заметим, что кв и N должны быть взаимно простыми. Открытый ключ Кв используют для шифрования данных, а секретный ключ кв - для расшифрования.
Преобразование шифрования определяет криптограмму С че­рез пару (открытый ключ Кв, сообщение М) в соответствии со сле­дующей формулой:
C = EKв(M) = EB(M) = MKe( mod N) (1)
В качестве алгоритма быстрого вычисления значения С ис­пользуют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.
Обращение функции C = MKв(mod N), т.е. определение значе­ния М по известным значениям С, Кв и N, практически не осуществимо при N≈2512.
Однако обратную задачу, т.е. задачу расшифрования крипто­граммы С, можно решить, используя пару (секретный ключ кв, криптограмма С) по следующей формуле:
М = DkB (С) = DB (С) = Ckв (mod N). (2)
Процесс расшифрования можно записать так:
DB(EB(M)) = M. (3)
Подставляя в (3) значения (1) и (2), получаем:
(МКв )kв = М (mod N) или МКв kв = М (mod N). (4)
Величина φ(N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД (х, N) = 1, то x φ(N) ≡ 1( mod N), или в несколько более общей форме
x п·φ(N)+1 ≡ х ( mod N), (5)
Сопоставляя выражения (4) и (5), получаем
KB*kB= n·φ(N)+1 или KB*kB = 1(mod φ(N)).
Именно поэтому для вычисления секретного ключа кв используют соотношение (*). Таким образом, если криптограмму C = MKe(modN) возвести в степень кв, то в результате восстанавливается исходный открытый текст М, так как
(МКв)kв = МКвkв = МП φ(N)+1 = М (mod N).
Таким образом, получатель В, который создает криптосисте­му, защищает два параметра: 1) секретный ключ kв и 2) пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ Кв.
Противнику известны лишь значения Кв и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы "потайной ход"-тройку чисел {Р, Q, Кв}, вычислил значение функции Эйлера
φ(N) = (P-1)(Q-1) и определил значение секретного ключа kв
2.4 Процедуры шифрования и расшифрования в криптосистеме RSA
Предположим, что пользователь А хочет передать пользова­телю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В-в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.
1. Пользователь В выбирает два произвольных больших про­стых числа Р и Q.
2. Пользователь В вычисляет значение модуля N = Р * Q.
3. Пользователь В вычисляет функцию Эйлера φ(N) = (P-1)(Q-1) и выбирает случайным образом значение открытого ключа Кв с учетом выполнения условий:
1<КВ< φ(N) и НОД(Кв, φ(N))=1.
4. Пользователь В вычисляет значение секретного ключа кв,используя расширенный алгоритм Евклида при решении срав-нения
kB ≡ КВ-1 (mod φ(N)).
5. Пользователь В пересылает пользователю А пару чисел
(N, Кв) по незащищенному каналу.
Если пользователь А хочет передать пользователю В сооб­щение М, он выполняет следующие шаги.
1. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа М = 0,1, ..., N-1.
2. Пользователь А шифрует текст, представленный в виде последовательности чисел Mj по формуле C = MiKв(modN) и отправляет криптограмму C1, С2, С3, ..., Сі,... пользователю В.
3. Пользователь В расшифровывает принятую криптограмму C1, С2, С3, Сі, ... используя секретный ключ кв, по формуле Mj = Сjкв (mod N).
В результате будет получена последовательность чисел Мj которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей Кв и kв.
3 АЛГОРИТМЫ, ОСНОВАННЫЕ НА ШИФРОВАНИИ ПО МЕТОДУ RSA
3.1Схема шифрования Полига-Хеллмана
Схема шифрования Полига-Хеллмана [121] сходна со схемой шифрования RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования. В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете.
Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений:
С = Pe mod n и Р = Cd mod n,
где e*d =1 (по модулю некоторого составного числа).
В отличие от алгоритма RSA в этой схеме число n не определяется через два больших простых числа; число n должно оставаться частью секретного ключа Если кто-либо узнает значения е и n. он сможет вычислить значение d.
Не зная значений е или d, противник будет вынужден вычислять значение
е = logPC (mod n).
Известно, что это является трудной задачей. Схема шифрования Полига-Хеллмана запатентована в США и Канаде.
3.2 Схема шифрования Эль Гамаля
Схема Эль Гамаля, предложенная в 1985 г., может быть использована как для шифрования, так и для цифровых подписей. Безопасность схемы Эль Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.
Для того чтобы генерировать пару ключей (открытый ключ-секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G<P. Числа Р и G могут быть распространены среди группы пользователей.
Затем выбирают случайное целое число X, причем Х<Р. Число X является секретным ключом и должно храниться в секрете.
Далее вычисляют Y=Gxmod P. Число Y является открытым ключом.
Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1<К<Р-1, такое, что числа К и (Р-1) являются взаимно простыми. Затем вычисляют числа
a = GK mod P, b=YKM mod P.
Пара чисел (a, b) является шифртекстом. Заметим, что длина шифртекста вдвое больше длины исходного открытого текста М. Для того чтобы расшифровать шифртекст (a, b), вычисляют
M = b/axmod P. (*)
Поскольку
ax≡GKXmod P,