Криптосистемы El Gamal

Криптостойкость обеспечивает задача дискретного логарифмирования

1. Определение ключей

   1. Выбирается большое простое число P и большое целое число G. G < P.

   2. Выбирается случайное число X (X<P), которое является секретным ключом.

   3. Вычисляется

Y = G^x mod P

Y - открытый ключ

2. Шифрование/Расшифрование

   1. Выбираем еще одно случайное число К

1 < K < P-1

NOD(K, P-1)=1

2. a = G^k mod P

B = Y^k mod P

3. Расшифрование

M = b/a^x mod P = b*a^-x mod P

Док-во

b/a^x = Y^k * M/a^x = G^xk M/G^kx mod P = M mod P

Пример) P = 157 G = 83 X=34

Y = G^x mod P = 83 mod 157 = 25

M = 40 (<P) K=29

a = G^k mod P = 83²⁹ mod 157 = 84

Y^k * M mod P = 25²⁹ * 40 mod 157 =110

a^x * a^-x = 1 mod P

84³⁴ * a^-x = 1 mod P

a^-x = 86

M = b*a^-x mod P = 110*86mod 157 = 40

Криптографические протоколы

1. идентификация субъектов

2. протоколы аутентификации данных и цифровой подписи

3. для управления ключевой информации

1. С любым объектов связана информация его идентифицирующая. Если при входе в систему такой идентификатор обнаруживается, то такой объект считается легальным. Такая процедура называется идентификацией. Если такой пользователь найден, то выполняется процедура аутентификация (подтверждения подлинности). Следующей выполняется процедура авторизации (разграничение полномочий). Выделяют три разновидности протоколов идентификации субъектов:

- основан на использовании известной легальным объектом секретной информации.

- основан на использовании различных спец. устройств

- использование других особенностей субъекта

Предположим, что в системе зарегистрировано N пользователей, для каждого из них есть свой идентификатор, аутентификатор. Типовая схема идентификации осуществляется следующим образов:

Номер пользователя	Идентификатор	Аутентифицирующая информация
1	ID1	E1
2	ID1	E2
3	ID1	E3
...		...

E_i=F(S_i, K_i)

S_i - случайная соль

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

Взаимная проверка подлинности пользователей

Для проверки подлинности используют такие механизмы как "запрос-ответ" и отметки времени.

В первом случае, если пользователь А хочет быть уверен в пользователе В, то он посылает ему некоторую случайную последовательность, В осуществляет заранее известные преобразования над этой последовательностью и отсылает ответ. Чтобы повысить надежность системы, осуществляется несколько таких пересылок. Рассмотрим один из таких протоколов, который называется "рукопожатие". Схема представлена т.о.

Е

g(S)

D_k

D_k

g(S)

E_k

S E_kab(s) ID_b

ГПСП

E_kab (q(S))

Решение

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

Kerberos

Используется в Windows...

На клиентской станции А пользователь вводит свой логин и пароль . Эти данные передаются в центр распределения ключей(ЦРК). ЦРК по имени пользователя находит в базе долгосрочных ключей К_к. Затем ЦРК создает общий секретный ключ и TGT. TGT включает вторую копию ключа, срок действия и т.д. ЦРК шифрует эту информацию с помощью главного ключа пользователя А, причем TGT шифруется секретным ключом ЦРК.

E_ka (E_{k црк} (TGT), K_sa срок действия)

предположим, что А пытается получить доступ к В, для этого она в начале обращается в ЦРК, куда отсылает зашифрованные ключом ЦРК TGT чтобы подтвердить действие своего сеансового ключа, запрос на доступ к В. И зашифрованный с общим сеансовым ключом К_sa аутентификатор, представляющий собой отметку о времени.

ЦРК расшифровывает TGT для получения общего сеансового ключа K_sa, после чего расшифровывает аутентификатор. Затем ЦРК создает два билета T_a T_b, но не пересылает T_a, а шифрует его секретным ключом K_b и отправляет эти данные вместе с Т_а, предварительно зашифровав сеансовым ключом.

Оба билета Т_а и Т_В содержат сгенерированный ЦРК общий сеансовый ключ для А и В. Получив эту информацию, А становится обладателем сеансового ключа К_АВ. Теперь А обращается к В и пересылает зашифрованный билет Т_В и аутентификатор , зашифрованный общим сеансовым ключом К_АВ. Расшифровав Т_В В становится обладателем общего сеансового ключа, что позволит расшифровать отметку или идентификатор А.

Аналогичным образом создаются общие сеансовые ключи для запроса к другой станции.

1) традиционные алгоритмы

2) ассиметричные