Файл: Программа работы.doc

Затем случайным образом выбирается элемент , такой, что и являются взаимно простыми числами, т.е.

.

(2.2)

Замечание 1: Здесь и далее - есть функция Эйлера, определяемая из выражения

Замечание 2: Для вычисления в условиях схемы RSA можно использовать следующее соотношение, справедливость которого очевидна из определения функции Эйлера

.

(2.3)

Несложно убедиться, что данный метод вычисления имеет сложность порядка двоичных операций[7].
Замечание 3: Скорость работы алгоритма шифрования RSA существенным образом зависит от выбора . На практике наиболее используемыми вариантами являются значения , , . Каждое из этих чисел содержит в двоичном представлении только две единицы, поэтому алгоритм повторного возведения в квадрат позволяет выполнить шифрование достаточно быстро[1].
Пара чисел

---

будет, таким образом являться открытым ключом алгоритма.

Далее с помощью расширенного алгоритма Евклида [1,3] определяется закрытый ключ , такой что:

.

(2.4)

Другими словами

.

(2.5)

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

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

.

(2.6)

При расшифровке сообщения для каждого зашифрованного блока вычисляется

.

(2.7)

Для доказательства применимости данного алгоритма достаточно подробно рассмотреть свойства функции Эйлера [4,8].

Стойкость RSA существенным образом зависит от выбора

---

и . Как правило, практическую ценность имеет шифрование с ключами длины порядка сотен бит. Другим важным условием стойкости является требование, чтобы значение было по возможности наименьшим [1,7].

В литературе описаны многочисленные модификации схемы RSA, отличающиеся повышенным быстродействием, большей стойкостью и т.д.[1,7,8].

---

2.3. Цифровая подпись в схеме Эль-Гамаль

В отличие от криптосистемы RSA, построенной на сложности задачи факторизации больших чисел, профессор Стэнфордского университета (США) Тахер Эль-Гамаль (Taher ElGamal) разработал в 1985 г. асимметричную криптосистему, основанную на сложности задачи дискретного логарифмирования [9].

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

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

	,	(3.1)
	.	(3.2)

Затем вычисляется значение из выражения

.

(3.3)

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

Для подписания сообщения , сначала выбирается случайное число

---

, такое что

.

(3.4)

Значение в дальнейшем сохраняется в секрете. Затем вычисляется значение из выражения

(3.5)

Далее с помощью расширенного метода Евклида для нахождения решается следующее уравнение

.

(3.6)

Подписью является пара чисел . Для проверки подписи необходимо проверить справедливость равенства:

.

(3.7)

Несложно убедиться, что для каждой процедуры подписания необходимо новое значение , выбранное случайным образом. Компрометация значения дает возможность по перехваченным значениям , и восстановить за полиномиальное время значение секретного ключа [1].

Известны модификации данного алгоритма для доказательства идентичности, аутентификации и обмена ключами [1].

---