3.1. Алгоритм rsa

В 1978г. был сделан следующий выдающийся шаг в области криптосистем с открытым ключом: Рональд Ривест (Ronald Rivest), Ади Шамир (Adi Shamir) и Леонард Аделман (Leonard Adelman) опубликовали алгоритм электронной цифровой подписи, написанный годом ранее. С тех пор алгоритм Rivest - Shamir – Adelman (RSA) широко используется практически во всех приложениях, использующих криптографию с открытым ключом.

Требования к электронной цифровой подписи во многом аналогичны требованиям к обычной подписи на документе:

• задача подписи – надежно подтвердить подлинность документа и его автора;

• подпись должна быть неотъемлема от документа;

• подпись должна быть уникальна и (в идеале) ее невозможно подделать.

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

Последовательность действий RSA следующая:

1. Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое);

2. Вычисляется их произведение n=pq, которое называется модулем.

3. Вычисляется значение функции Эйлера от числа n: ϕ(n)=(p-1)(q-1);

4. Выбирается целое число e (1 < e < ϕ(n)), взаимно простое со значением функции ϕ(n). Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537;

• Число e называется открытой экспонентой;

• Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в e.

• Слишком малые значения e, например 3, потенциально могут ослабить безопасность схемы RSA;

1. Вычисляется число d, мультипликативно обратное к числу e по модулю ϕ(n) , то есть число, удовлетворяющее условию:

2. de ≡ 1 mod ϕ(n);

Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

3. Пара {e, n} публикуется в качестве открытого ключа RSA;

4. Пара {d, n} играет роль закрытого ключа RSA и держится в секрете.

Алгоритм позволяет зашифровать целое число X, которое должно быть меньше n, с помощью следующего выражения:

3.2. Шифр Эль-Гамаля

Еще одним распространенным асимметрическим криптографическим шифром, как уже было упомянуто, является алгоритм Эль-Гамаля (Taher Elgamal). Это алгоритм шифрования с открытым ключом, основанный на трудности вычислений дискретных логарифмов. Алгоритм Эль-Гамаля может быть использован для шифрования данных, для формирования цифровой подписи и для согласования общего ключа.

Факттически здесь используется схема Диффи — Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих дуг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Общими открытыми параметрами в криптосистеме системе Эль-Гамаля являются числа Р (большое простое число) и А (А< P). Закрытыми ключами абонентов являются числа Хi, 1 < Х i < Р-1, открытыми ключами – значения Y_i:Y_i=A^XimodP. Пользователь, передающий сообщение, выбирает случайное число k, взаимно простое с Р-1, и вычисляет числа r = A^k mod P, e=m*. Пара чисел (r, е), являющаяся шифротекстом, передается другому пользователю. Для расшифровывания сообщения необходимо вычислить m = e*modP. В результате получается исходное сообщение m.