4.6. Криптосистемы Диффи-Хеллмана и Эль-Гамаля

Криптосистемы Диффи-Хеллмана и Эль-Гамаля основаны на вычислительной сложности задачи дисретного логарифмирования. Вычисление y=a^x {mod p} (p – простое число или степень простого числа, 1<x<p-1, 1<a<p-1, 1<b<p-1, a^c = b{mod p}) выполняется просто, но вычисление x = log_ay{mod p} выполняется достаточно сложно.

Алгоритм Диффи-Хеллмана предназначен только для генерации ключа симметричного шифрования, который затем будет использован субъектами А и В для защищенного обмена сообщениями по открытой сети.

1. А: выбирает ха и вычисляет y_a = a^xa {mod p}.

2. В: выбирает xb и вычисляет y_b = a^xb {mod p}.

3. A→B: y_a.

B→A: y_b.

A: вычисляет k_a = (y_b)^xa {mod p}.

B: вычисляет k_b = (y_a)^xb {mod p}.

7. Конец (k_a = k_b и созданный ключ может теперь использоваться для защищенного обмена сообщениями между А и В).

Значения а и р в алгоритме Диффи-Хеллмана не являются секретными, поскольку, даже зная их, нарушитель не сможет решить задачу дискретного логарифмирования и найти значения ха и хb, чтобы вычислить сгенерированный ключ симметричного шифрования.

В криптосистеме Эль-Гамаля значение а вместе с значениями р и y составляет открытый ключ, а секретным ключом является значение х (y = a^x {mod p}). Шифрование открытого текста Р в криптосистеме Эль-Гамаля выполняется по следующему алгоритму.

1. Выбор случайного целого числа k (1<k<p-1 и НОД(k, p-1) = 1).

2. C1 = a^k {mod p}.

3. C2 = Py^k {mod p}.

4. Конец (шифротекстом являются значения С₁ и С₂).

Расшифрование в криптосистеме Эль-Гамаля производится путем составления сравнения PC₁^x = C2 {mod p} и решения его относительно P. Действительно: PC₁^x {mod p} = P(a^k)^x {mod p} = P (a^x)^k {mod p} = Py^k {mod p} = C₂ {mod p}.

Если P>=p, то открытый текст должен быть разбит на блоки, длина которых равна длине числа р. В п. 3 алгоритма шифрования вместо операции умножения может использоваться операция сложения по модулю 2 (C₂ = P [+] y^k {mod p}). Тогда при расшифровании восстановление открытого текста выполняется следующим образом:

P = (C₁^x {mod p}) [+] C₂ (так как C₁^x {mod p} = y^k {mod p}).

Недостатком этого варианта является то, что открытый текст должен разбиваться на блоки заранее неизвестной длины y^k {mod p}.

4.7. Электронная цифровая подпись и ее применение

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

подготовка документа от имени другого субъекта («маскарад»);

отказ автора документа от факта его подготовки (ренегатство);

изменение получателем документа его содержания (подмена);

изменения содержания документа третьим лицом (активный перехват);

повторная передача по компьютерной сети ранее переданного документа (повтор).

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

Алгоритм получения ЭЦП под документом Р.

1. Вычисление хеш-значения Н(Р) для документа Р.

2. Шифрование Н(Р) с помощью секретного ключа автора документа ska – E_ska(H(P)) (полученный шифротекст и будет являться ЭЦП).

Алгоритм проверки ЭЦП С под документом Р.

1. Вычисление хеш-значения Н(Р) для документа Р.

2. Расшифрование ЭЦП с помощью открытого ключа автора документа pka – D_pka(C) = D_pka(E_ska(H(P)) = H(P).

3.Сравнение вычисленного и расшифрованного хеш-значения для документа Р.

Перед получением ЭЦП в подписываемый документ должны быть включены дополнительные сведения:

дата и время простановки подписи;

срок окончания действия секретного ключа данной подписи;

реквизиты (фамилия, имя, отчество подписывающего лица, его должность и название представляемой организации);

идентификатор секретного ключа (для возможности выбора лицом, проверяющим ЭЦП, нужного открытого ключа).

В системе ЭЦП подпись под электронным документом невозможно подделать без знания секретного ключа автора документа, поэтому компрометация секретного ключа недопустима.

Известны следующие системы ЭЦП:

RSA (на основе асимметричной криптосистемы RSA);

DSS (Dijital Signature Standard, стандарт США на основе асимметричной криптосистемы Эль-Гамаля);

ГОСТ Р 34.10-94 (российский стандарт ЭЦП на основе асимметричной криптосистемы Эль-Гамаля);

ГОСТ Р 34.10-2001 (российский стандарт ЭЦП, использующий асимметричную криптосистему на основе эллиптических кривых).

Алгоритмы получения и проверки ЭЦП в системе RSA не отличаются от алгоритмов шифрования и расшифрования в аналогичной криптосистеме, за исключением того, что получение ЭЦП производится с применением секретного ключа, а проверка ЭЦП – с применением открытого ключа x.

Алгоритмы получения и проверки ЭЦП в системе Эль-Гамаля отличаются от алгоритмов шифрования и расшифрования в аналогичной криптосистеме.

Алгоритм получения ЭЦП под документом Р.

1. Выбор случайного целого числа k(1<k<p-1 и НОД(k,p-1) = 1) (k – случайная составляющая ЭЦП, изменяющая подпись под вновь отправляемым по сети тем же самым документом).

2. С₁ = a^k{mod p}.

3. Определение С₂ из сравнения Р =хС₁+kC₂{mod p-1} (C1 и C2 образуют ЭЦП для Р).

Проверка ЭЦП в системе Эль-Гамаля сводится к проверке сравнения y^C1C1^C2 {mod p} = a^P {mod p}.

Действительно: y^C1C1^C2 {mod p} = a^xC1a^kC2{mod p} = a^xC1+kC2 {mod p} = a^{P {mod p-1}} {mod p} = a^P+m(p-1) {mod p} = a^P(a^m)^p-1 {mod p} = a^P {mod p}1 (из малой теоремы Ферма).

Алгоритм получения ЭЦП под документом Р в системе на базе эллиптических кривых (целое число g выбирается из условия gG = 0).

1. Выбор случайного целого числа k (1<k<g) – случайной составляющей ЭЦП, изменяющей подпись под вновь отправляемым по сети тем же самым документом).

2. Вычисление с= kG.

3. r = x_C {mod g} (x_C – xкоордината точки с).

4. s = rx + kP {mod g}.

5. Если r ≠ 0 и s ≠ 0, то эти значения образуют ЭЦП, в противном случае выбирается другое k и пп. 2…4 повторяются.

Алгоритм проверки ЭЦП в системе на основе эллиптических кривых.

1. Вычисление V = P-1 {mod g}.

2. z₁ = sV {mod g}; z₂ = -rV {mod g}.

3. Вычисление c = z₁G + z₂y; R = x_C {mod g}.

4. Проверка R=r.

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

чувствительность к любым изменениям в документе (вставкам, удалениям, перестановкам, заменам фрагментов и отдельных символов);

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

К наиболее известным функциям хеширования относятся:

MD2, MD4, MD5 (Message Digest) – получают хеш-значение длиной 128 бит и используются в системе ЭЦП RSA;

SHA (Secure Hash Algorithm) – получает хеш-значение длиной 160 бит и используется в системе ЭЦП DSS;

ГОСТ Р 34.11-94 – получает хеш-значение длиной 256 бит и используется в российских стандартах ЭЦП;

RIPEMD (Race Integrity Primitives Evaluation Message Digest) – получает хеш-значение длиной 128 или 160 бит (две модификации).