Электронная подпись в системах с открытым ключом

Система RSA

В настоящее время наиболее развитым методом криптозащиты с криптоключом является метод RSA.

Под простым числом понимают число, делящееся только на 1 и на само себя.

Взаимопростые числа – не имеют общего делителя, кроме 1.

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

1. Выберем 2 простых очень больших числа p и g.

2. Определим n как результат n = p*g

3. Выберем большое случайное число D, которое должно быть взаимопростым с результатом умножения (p-1)*(q-1)

4. Определяем число e, такое, чтоб для него было истинным соотношение

(e*d) mod (p-1)(q-1) = 1

5. Числа e и n назовем открытым ключом, d и n - секретным.

Чтобы зашифровать данные по известному ключу e,n необходимо сделать следующее:

- Разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i).

- Зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле: C(i) = (M(i)^e) mod n

Чтобы расшифровать эти данные используется секретный ключ d, n и выполняются вычисления M(i) – (C(i)^d) mod n

В результате получено число M(i), представляющее исходный текст.

Пример: САВ

1. p=3, q=11

2. n=3*11 = 33

3. (p-1)(q-1) = 20 d = 3

4. (e*3) mod 20 = 1 e = 7

5. A-1, B-2, C-3 312

C(1) = (3^7) mod 33 = 2187 mod 33 = 9

C(2) = (1^7) mod 33 = 1 mod 33 = 1

C(3) = (2^7) mod 33 = 128 mod 33 = 29

9129 – шифровалось по ключу (7, 33)

Для расшифрования ключ (3, 33)

M1 = (9^3) mod 33 = 729 mod 33 = 3

M2 = (1^3) mod 33 = 1

M3 = (29^3) mod 33 = 24389 mod 33 = 2

312 – CAB

Криптостойкость алгоритма RSA основана на предположении, что сложно определить ключ по известному, так как надо решить задачу о существовании делителей числа.

Известные алгоритмы для решения задачи имеют экспоненциальную оценку вычислительной сложности.

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

В связи с этим для чисел, состоящих из 200 цифр (рекомендуется).

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

Пусть пользователь N1 должен передать сообщение m пользователю N2, таким образом, чтобы N2 смог доказать, что сообщение прислано N1.

Для этого N1 разрабатывает систему шифрования E1(D1(X)) = X, справедливую для любых X и которую он будет использовать для аутентификации. Он рассылает ключ E1 как общий ключ его электронной подписи.

В свою очередь, получив от N2 общий ключ шифрования E2 для открытой системы, такой, что E2(D2(X)) = X

N1 вычисляет сигнатуру сообщения S=D1(m). Затем шифрует ее открытым ключом E2:

С = E2(S) и передает ее N2, который расшифровывает сообщение процедурой S= D2(c)

m* = E1(S)

При возникновении спорной ситуации N1 должен предоставить арбитру A свой личный ключ D1, удовлетворяющий условию E1(D1(X)) = X и А лишь необходимо проверить, что D1(m* ) = S ↔ S = D1(m)