Схема Эль-Гамаля

Безопасность схемы Эль-Гамаля основана на трудоемкости вычисления дискретных логарифмов в конечном поле.

Для генерации пары ключей сначала выбирается простое число р и два случайных числа, g и x; оба эти числа должны быть меньше р. Затем вычисляется:

Открытым ключом являются y, g и р. И g, и р можно сделать общими для группы пользователей. Закрытым ключом является х.

Чтобы зашифровать сообщения М, сначала выбирается случайное число k, взаимно простое с р-1. Затем вычисляются такие величины:

Пара чисел a и b являются шифртекстом. Заметьте, что шифртекст в два раза длиннее открытого текста. Для расшифрования a и b вычисляется величина:

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

Первый из опубликованных алгоритмов на основе открытых ключей опубликован в работе Диффи и Хелман, в которой было определено само понятие криптографии с открытым ключом [Diff76b]. Обычно этот алгоритм называют протоколом обмена ключами по схеме Диффи-Хеллмана. Эффективность алгоритма Диффи-Хеллмана опирается на трудность вычисления дискретных логарифмов.

Протокол обмена ключами между двумя пользователями:

1. Открытыми параметрами протокола Диффи-Хеллмана являются большое простое число p и число g, являющееся первообразный корень числа p. Число g является первообразным корнем простого числа p, если все числа

g ¹ mod p, g ² mod p,..., g ^p-1 mod p

различны и представляют все целые числа от 1 до p -1 в некоторой перестановке.

2. Пользователь A выбиpает случайное число a, pавновеpоятное из целых 1... p -1. Это число он деpжит в секpете, а пользователю B посылает по открытому каналу число

y ₁ = g ^a mod p.

3. Аналогично поступает и пользователь B, генеpиpуя случайное число b, вычислив

y ₂ = g ^b mod p,

и отпpавляя его пользователю А.

4. После этого пользователь А вычисляет значение

k_ab = (y ₂) ^a mod p = (g ^b mod p) ^a mod p.

5. То же делает и пользователь B:

k_ba = (y ₁) ^b mod p = (g ^a mod p) ^b mod p.

6. По правилам модулярной арифметики

(x ^a mod p) ^b mod p= (x ^a mod p) ^b mod p. = x ^ba mod p.

Таким образом, у обоих пользователей оказывается общий секретный ключ

k= k_ab = k_ba =g ^ba mod p,

котоpый можно использовать для шифpования инфоpмации другими алгоpитмами. Данный алгоpитм нельзя использовать собственно для шифpования и дешифрования сообщений.

АЛГОРИТМЫ ЦИФРОВОЙ ПОДПИСИ С ОТКРЫТЫМ КЛЮЧОМ.

Идея цифровой подписи, как законного средства подтверждения подлинности и авторства документа в электронной форме, впервые была сформулирована явно в 1976 году в статье двух молодых американских специалистов по вычислительным наукам из Стэндфордского университета Уитфилда Диффи и Мартина Хеллмана.

Суть ее состоит в том, что для

гарантированного подтверждения подлинности информации, содержащейся в электронном документе,

для возможности неопровержимо доказать третьей стороне (партнеру, арбитру, суду и т.п.), что электронный документ был составлен именно конкретным лицом, или по его поручению, и именно в том виде, в котором он предъявлен,

автору документа предлагается выбрать свое индивидуальное число (называемое обычно индивидуальным ключом, паролем, кодом, и т.д.). И каждый раз для "цифрового подписывания" сворачивать (замешивать) этот свой индивидуальный ключ, хранимый в секрете от всех, с содержимым конкретного электронного документа. Результат такого "сворачивания" - другое число, и может быть назван цифровой подписью данного автора под данным конкретным документом.

Использование алгоритма RSA для цифровой подписи.

Система RSA широко используется в системе цифровой подписи, так как ее преобразования обладают всеми необходимыми свойствами.

Использование цифровой подписи предполагает существование двух процедур; подписывания и проверки.

Процедура подписывания сообщения М - это возведение числа М в степень d пo модулю n:

S = M^d mod n.

Число S есть цифровая подпись, которую может выработать только владелец секретного ключа.

Процедура проверки подписи S, соответствующей сообщению М ­­- это возведение числа S в целую степень числа е по модулю n:

M'=S^e mod n.

Если М'= М, то сообщение М признается подписанным пользователем, который предоставил ранее открытый ключ е.