Введение

Цель алгоритмов шифрования - помочь людям обмениваться секретной или конфиденциальной информацией друг с другом, используя информационный эквивалент физических ключей. Чтобы облегчить обсуждение, мы скажем, что Боб хочет послать Алисе сообщение, чтобы Ева не смогла его увидеть. С симметричным алгоритмом шифрования ключ, используемый для шифрования сообщения, совпадает с ключом, используемым для его расшифровки. Это аналогично тому, как Боб помещает свое сообщение в ящик, закрывает его и отправляет Алисе для открытия. Большая проблема с таким подходом состоит в том, что Алиса нуждается в копии ключа, который использовал Боб. Это проблема курицы и яйца: для безопасного обмена информацией друг с другом Алиса и Боб уже должны были обмениваться секретной информацией. Если Боб когда-нибудь отправит ключ Алисе, Ева может легко перехватить его и использовать для чтения своих сообщений. Теоретически, Боб может дать Алисе ключ лично, но на практике это не очень хорошо работает. Представьте, что вам нужно ехать в офис какой-либо компании, чтобы дать им номер вашей кредитной карты, прежде чем вы сможете что-то купить онлайн. Это ужасно неудобно!

Решением проблемы являются алгоритмы асимметричного шифрования, которые не используют один и тот же ключ для шифрования и дешифрования. Продолжая нашу аналогию с ящиками и физическими ключами, Алиса отправляет разблокированный замок всем, кто хочет отправлять ей сообщения. Боб кладет свое сообщение в ящик, запирает его замком Алисы и отправляет обратно Алисе. Поскольку Алиса - единственная, у кого есть ключ от замка, только она может прочитать сообщение, как только оно окажется в запертом ящике. Алгоритм Эль Гамаля является примером информационного алгоритма, который работает по этому принципу. В основу криптографической системы Эль Гамаля положена сложность задачи вычисления дискретных логарифмов в конечном поле. Существуют эффективные алгоритмы возведения числа в степень в конечном поле, однако восстановление показателя (дискретного логарифма) по известному основанию и его степени является сложной математической задачей. На сегодняшний день не известно ни одного эффективного алгоритма вычисления дискретных логарифмов больших чисел

Немного вводной теории

Перед тем, как мы познакомимся с алгоритмом Эль Гамаля, мы должны понять несколько базовых вещей.

Работа в режиме шифрования

Алиса хочет, чтобы люди могли отправлять ей секретные сообщения, поэтому она создает открытый ключ %%(p,g,y)%%, которым она делится с миром и личный ключом %%x%%, который она никогда никому не рассказывает. Боб хочет отправить Алисе секретное сообщение, поэтому он использует открытый ключ Алисы и одноразовый сессионный ключ %%k%%, создает зашифрованный текст %%(u, v)%%.
Вот как это работает:

Интерактивная схема шифрования

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

Атаки на алгоритм шифрования

Пока Алиса и Боб обменивались секретиками, Ева чувствовала себя брошенной. Она решила научиться читать сообщения друзей. Давайте поможем ей в этом интересном занятии!

Атака одинаковых сессионных ключей

Пока Боб ненадолго отлучился, хитрая Ева смогла подсмотреть в переписку. Она увидела то, что все сообщения шифруются при помощи одного и того же сессионного ключа. Кроме того, она смогла запомнить одно из сообщений.

Такого набора данных хватит, чтоб Ева спокойно могла прочитать любое сообщение, которое будет отправлено с данными параметрами.

Предположим, что при отправке двух разных сообщений %%m%% и %%m'%% был использован один и тот же секретный ключ %%k%%. (Параметры %%p,g,y,x%% тоже одинаковые). Тогда рассмотрим шифртекст, который получается в таком случае:
$$m: u = g^k \pmod{p}, v = m \cdot (y^k) \pmod{p} $$ $$m': u' = g^k \pmod{p}, v' = m'\cdot(y^k) \pmod{p} $$ $$ \frac{v'}{v}= \frac{m'}{m} \Rightarrow m' = \frac{v' \cdot m}{v} $$ Ура! При помощи такой формулы мы спокойно можем получить информацию о другом сообщении, которое было передано с таким же %%k%%.

Когда мы рассказали Еве о данной атаке, она была на седьмом небе от счастья. Но недолго она оставалась такой: Алиса и Боб догадались о том, что их сообщения были прочитаны, поэтому они устранили уязвимость: решили каждый раз генерировать случайный сессионный ключ. Но при этом они продолжили использовать относительно маленькие числа для ключей. Этим мы и воспользуемся!

Атака малого модуля

Атака состоит в том, что мы будем искать решение %%y = g^x \pmod{p}%%, зная %%y%%, %%g%% и %%p%% (помним, что параметры имеют относительно малое значение), алгоритмом baby step giant step.

Пусть есть уравнение %%y = g^x%% в цикличекой группе. Положим, что %%x = i \cdot m - j%%, где %%m%% - заранее выбранная константа (обычно используют округленное вверх значение квадратного корня из %%p%%). Очевидно, что любое %%x%% из промежутка %%[0,p)%% можно представить в такой форме. Тогда уравение принимает вид: %%y = g^{m \cdot i - j} \Rightarrow y \cdot (g^{-m})^{i} = g^j%% Алгоритм предварительно вычисляет %%g^i%% для некоторых %%i%%. Потом корректируется значение %%m%% и пробуются различные значения %%i%%.

Давайте рассмотрим пример:
$$20 = 5^x \pmod{53}$$
В данном случае %%g = 5%%, %%y = 20%% и %%p = 53%%, и мы хотим узнать %%x%%. Для начала определим квадратный корень из %%p-1%%, и округлим до ближайшего целого:
$$m = \lfloor\sqrt{p-1}\rfloor = \lfloor\sqrt{52}\rfloor = 7$$
Затем мы вычислим %%g^i \pmod{p} %% от %%1%% до %%m%% и занесем информацию в виде словаря %%\{g^i \pmod{p}, i\}%%
$$\{1: 0, 5: 1, 25: 2, 11: 3, 42: 4, 51: 5, 43: 6, 3: 7\}$$
Например: Если %%i = 6%%, мы получаем %%5^6 \pmod{53} \equiv 43 \Rightarrow \{43:6\}%%
Теперь у нас есть список пар от %%0%% до квадратного корня из %%p-1%%. Вычислим %%g^{-m}%%. Согласно одному из следствий малой теоремы Ферма %%g^{-m} = g^{m(p-2)} = 18%% Затем мы проходимся по значениям %%y \cdot (g^{-m})^j \pmod{p} = 20 \cdot 18^j \pmod{53}%% пока мы не найдем совпадения в таблице. Тогда мы умножаем число на %%m%% и добавляем число, которое сопоставлено в таблице.
$$j = 0: 20 \pmod{53} = 20$$ $$j = 1: 20 \cdot 18 \pmod{53} = 42$$ Число %%42%% есть в нашем словаре, значит %%x = 1*7 + 4 = 11%%
Действительно, если выполнить проверку, то получится верное равенство! Таким образом, мы знаем более эффективный алгоритм нахождения решения уравнения %%y = g^x \pmod{p}%%, чем полный перебор.

Атака Meet in the Middle

Очередная атака, которую мы попробуем называется Meet in the Middle (встреча в середине). Не стоит путать эту атаку с Man in the Middle (человек по середине), о которой [спойлер] мы поговорим чуть позже.
Если соблюдается ряд условий и сообщение m, которое Боб посылает Алисе, достаточно короткое, то Ева может восстановить %%m%%, если она сможет узнать %%v%% (а она сможет, т.к это открытая информация), когда Боб посылает свой шифротекст Алисе. В частности, Meet in the Middle работает только в том случае, если:

• %%m%% состоит из %%B%% бит, причем Ева знает %%B%%, и %%B%% является небольшим числом.
• %%m%% можно разделить на две части таким образом, что %%m=(m1)(m2)%%. Пусть %%m1%% состоит из битов %%b1%%, а %%m2%% - из битов %%b2%%.
• Ева знает %%n%%. Поскольку сессионный ключ Боба %%k%% обладает свойством %%1 \leq k \leq n-1%%, ему также необходимо каким-то образом определить %%n%%. Если он может, то Ева может тоже.
• %%m%% не является элементом подгруппы, порожденной %%g%%. Это кажется совершенно маловероятным. Однако, порядок %%n%% подгруппы, генерируемой %%g%%, часто выбирается небольшим по соображениям эффективности.
• Порядок %%n%% подгруппы, порожденной %%g%%, имеет свойство, что %%n ≤ (p-1) \cdot 2^{−b}%%. Опять же, возможно, что %%n%% мало по соображениям эффективности.

Если все магическим образом будут выполнены все условия,то Ева может действовать следующем образом:
Она знает, что $$y = g^x (mod p)$$
и что $$v = m \cdot (y^k) (mod p)$$
Возведем обе части в степень n: $$v^n = (m^n) \cdot (y^{nr}) (mod p)$$
Это бесполезно как часть атаки, если %%m%% является элементом подгруппы, порожденной %%g%%, потому что тогда %%m^n=1%% (поскольку все элементы подгруппы генерируют эту подгруппу, хотя и в другом порядке)
Однако если это не так, вспомним, что %%g_n=g_0=1%%, поскольку подгруппа, порожденная %%g%%, циклична, так что
$$y^{kn}=g^{xkn}=(g^n)^{xk}=1^{xk}=1$$
Получаем, что $$v^n = m^n (modp)$$
Используя предположение, что %%m = (m1)(m2)%%: $$v^n=(m^n_1)(m^n_2) (modp)$$ $$(v^n)(m^{−n}_2)=m^n_1(modp)$$

С теорией закончили, перейдем к реализации атаки:

Работа в режиме подписи

Теперь рассмотрим работу алгоритма в режиме подписи.

Подпись сообщений

Для подписи сообщения %%m%% выполняются следующие операции:
1) Выбирается случайное число %%1 < k < p-1%% взаимнопростое с %%p-1%% - разовый ключ
2) Вычисляется %%r = g^k \pmod{p}%%
3) Вычисляется %%s = (m - xr)k^{-1} \pmod{p-1}%%
4) Подписью сообщения %%m%% является пара %%(r,s)%%

Проверка подписи

Зная открытый ключ %%(p,g,y)%%, подпись %%(r,s)%% сообщения %%m%% проверяется следующим образом:
1) Проверяется выполнимость условий: %%0 < r < p%% и %%0 < s < p-1%%
2) Подпись считается верной, если выполняется сравнение: %%y^r \cdot r^s \equiv g^m (mod p)%%

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

Это небольшое приложение, которое вы можете использовать, чтобы попробовать алгоритм Эль Гамаля в режиме подписи.
Это игрушечная реализация, поэтому, пожалуйста, даже не пытайтесь использовать большие числа))

Атаки на алгоритм цифровой подписи

Атака на плохо выбранные разовые ключи

При рассмотрении стойкости необходимо соотношение %%m \equiv xr + ks \pmod{p-1}%%. Тот, кто наблюдает за подписывающим, видит серию подписанных документов:
$$ [m_1, r_1, s_1] \longrightarrow m_1 \equiv xr_1 + k_1s_1 \pmod{p-1}$$ $$ [m_2, r_2, s_2] \longrightarrow m_2 \equiv xr_2 + k_2s_2 \pmod{p-1}$$ $$ \dots $$ $$ [m_n, r_n, s_n] \longrightarrow m_n \equiv xr_n + k_1s_n \pmod{p-1}$$ Неизвестные тут: %%x, k_1 \dots k_n%%. Получили систему уравнений от %%n+1%% неизвестных, т.е. неопределенная система уравнений. Если знаем хоть один разовый ключ, то система становится определенной и решается - значит, все ключи должны быть случайными, секретными и разными.

Атака "по корректной тройке"

Атака связана с построением цифровой подписи по известной корректной тройке %%[m, r, s]%% Если взять параметры %%A,B,C%% такие, что %%\exists (Ar - Cs)^{-1} \pmod{p-1} %% то можно построить целую серию документов, удовлетворяющих соотношению проверки. $$r' = r^Ag^By^c \pmod{p}$$ $$s' = s \cdot r'/(Ar - Cs)^{-1} \pmod{p-1}$$ $$m' = r'(Am-Bs)/(Ar-Cs) \pmod{p-1}$$ Покажем это: $$y^{r'}r'^{s'} \equiv y^{r'}(r^{A}g^{B}y^{C})^{{sr'}/(Ar-Cs)} \equiv (y^{r'(Ar-Cs)} \cdot r^{Asr'} \cdot g^{Bsr'} \cdot y^{Csy'})^{(Ar-Cs)^{-1}} = (y^{r'Ar-r'Cs+r'Cs} \cdot r^{Asr'} \cdot g^{Bsr'})^{1 \over Ar-Cs} = ((y^{r} \cdot r^{s})^{Ar'} \cdot g^{Bsr'})^{1 \over Ar-Cs} \equiv g^{(mAr'+Bsr')/(Ar-Cs)}\equiv g^{m'} $$ Создав таким образом множество документов, можно организовать DDOS-атаку на проверяющего. Защита: %%m'%% - случайное число, %%m = Hash(m')%% - значит, цифровая подпись для Эль Гамаля должна применяться вместе с Хеш-функцией.

Материалы

Если вам понравился алгоритм Эль Гамаля и вы хотите более подробно изучить его работу, то исследуйте проект на github. Там вы найдете много полезной информации, а также реализацию данного алгоритма в приложении обмена сообщениями.

Источники, которые мы использовали:

• El Gamal T. - A public key cryptosystem and a signature scheme based on discrete logarithms
• Рябко, Фионов - Криптографические методы защиты информации
• Menezes A. J., Oorschot P. v., Vanstone S. A - Handbook of Applied Cryptography