Цель алгоритмов шифрования - помочь людям обмениваться секретной или конфиденциальной информацией друг с другом, используя информационный эквивалент физических ключей. Чтобы облегчить обсуждение, мы скажем, что Боб хочет послать Алисе сообщение, чтобы Ева не смогла его увидеть. С симметричным алгоритмом шифрования ключ, используемый для шифрования сообщения, совпадает с ключом, используемым для его расшифровки. Это аналогично тому, как Боб помещает свое сообщение в ящик, закрывает его и отправляет Алисе для открытия. Большая проблема с таким подходом состоит в том, что Алиса нуждается в копии ключа, который использовал Боб. Это проблема курицы и яйца: для безопасного обмена информацией друг с другом Алиса и Боб уже должны были обмениваться секретной информацией. Если Боб когда-нибудь отправит ключ Алисе, Ева может легко перехватить его и использовать для чтения своих сообщений. Теоретически, Боб может дать Алисе ключ лично, но на практике это не очень хорошо работает. Представьте, что вам нужно ехать в офис какой-либо компании, чтобы дать им номер вашей кредитной карты, прежде чем вы сможете что-то купить онлайн. Это ужасно неудобно!
Решением проблемы являются алгоритмы асимметричного шифрования,
которые не используют один и тот же ключ для шифрования и дешифрования.
Продолжая нашу аналогию с ящиками и физическими ключами, Алиса отправляет
разблокированный замок всем, кто хочет отправлять ей сообщения.
Боб кладет свое сообщение в ящик, запирает его замком Алисы и отправляет обратно Алисе.
Поскольку Алиса - единственная, у кого есть ключ от замка,
только она может прочитать сообщение, как только оно окажется в запертом ящике.
Алгоритм Эль Гамаля является примером информационного алгоритма,
который работает по этому принципу.
В основу криптографической системы Эль Гамаля
положена сложность задачи вычисления дискретных логарифмов в конечном поле.
Существуют эффективные алгоритмы возведения числа в степень в конечном поле,
однако восстановление показателя (дискретного логарифма) по известному
основанию и его степени является сложной математической задачей.
На сегодняшний день не известно ни одного эффективного алгоритма
вычисления дискретных логарифмов больших чисел
Перед тем, как мы познакомимся с алгоритмом Эль Гамаля, мы должны понять несколько базовых вещей.
Сравнение двух целых чисел по модулю натурального числа m — математическая операция,
позволяющая ответить на вопрос о том, дают ли два выбранных целых числа
при делении на m один и тот же остаток.
Величина остатка может быть получена бинарной операцией «взятия остатка»
от деления, обозначаемой %%mod%%. Попробуйте:
%% \bmod{} %% %% = %%
Результат может быть также получен как %% \bmod{} %% , %% \bmod{} %% . Мы говорим, что и сравнимы по модулю :
%% \equiv %% (%% \bmod{} %% )
Операция сравнения по модулю является неотъемлемой частью многих систем шифрования. Главное свойство, которое делает сравнение по модулю настолько полезным для алгоритмов шифрования, заключается в том, что результат операции не раскрывает никакой информации о числе.
Узнайте больше про модульную арифетику на Wikipedia.
Циклическая группа — это математическая группа, порожденная одним из элементов в группе %%G%%. Так как мы будем говорить об алгоритме Эль Гамаля, то нас интересуют только два типа групп:
Узнайте больше о циклических группах на Wikipedia.
Алиса хочет, чтобы люди могли отправлять ей секретные сообщения, поэтому она создает открытый ключ %%(p,g,y)%%,
которым она делится с миром и личный ключом %%x%%, который она никогда никому не рассказывает.
Боб хочет отправить Алисе секретное сообщение, поэтому он использует открытый ключ Алисы и одноразовый сессионный ключ %%k%%, создает зашифрованный текст %%(u, v)%%.
Вот как это работает:
1.Алиса выбирает простое число %%p%%
2.Выбирает целое число %%g%%, такое, что %%g%% - первообразный корень %%p%%, который генерирует циклическую подгруппу %%\mathbb{Z}_p^*%% порядка %%n%%
3.Выбирает случайный секретный ключ, такой что %%1 \leq x \leq n-1%%.
3.Вычисляет %%y = g^x \pmod{p}%%
5.Публикует открытый ключ %%(p,g,y)%%.
1.Смотрит на ключ Алисы %%(p,g,y)%%.
2.Боб выбирает случайное %%k%%, такое что %%1 \leq k \leq n-1%%
3.Создает сообщение %%m%%, такое что %%1 \leq m \leq p-1%%. Если сообщение слишком большое, то Боб делит сообщение на части и шифрует их отдельно.
4.Вычисляет числа %%u = g^k \pmod{p}%%, %%v = m y^k \pmod{p}%%.
5.Боб публикует шифр текст %%(u,v)%%.
6.Алиса видит шифртекст %%(u,v)%%.
7.Расшифровывает сообщение %%m = u^{-x} v \pmod{p}%%.
Это небольшое приложение, которое вы можете использовать,
чтобы попробовать шифрование Эль Гамаля.
Это игрушечная реализация, поэтому, пожалуйста, даже не пытайтесь
использовать большие числа))
Пока Алиса и Боб обменивались секретиками, Ева чувствовала себя брошенной. Она решила научиться читать сообщения друзей. Давайте поможем ей в этом интересном занятии!
Пока Боб ненадолго отлучился, хитрая Ева смогла подсмотреть в переписку. Она увидела то, что все сообщения шифруются при помощи одного и того же сессионного ключа. Кроме того, она смогла запомнить одно из сообщений.
Такого набора данных хватит, чтоб Ева спокойно могла прочитать любое сообщение, которое будет отправлено с данными параметрами.
Предположим, что при отправке двух разных сообщений %%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 (встреча в середине).
Не стоит путать эту атаку с Man in the Middle (человек по середине), о которой [спойлер]
мы поговорим чуть позже.
Если соблюдается ряд условий и сообщение m, которое Боб посылает Алисе, достаточно короткое,
то Ева может восстановить %%m%%, если она сможет узнать %%v%% (а она сможет, т.к это открытая информация),
когда Боб посылает свой шифротекст Алисе.
В частности, Meet in the Middle работает только в том случае, если:
Если все магическим образом будут выполнены все условия,то Ева может действовать следующем образом:
Она знает, что $$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)$$
С теорией закончили, перейдем к реализации атаки:
Простое число %%p%% имеет бит,
Открытый ключ:
( %%p = %% ,
%%g = %% ,
%%y = g^x \pmod{p} = %% )
где порядок подгруппы сгенерированной %%g%% это %%n=%% ,
и секретный ключ: %%x = %%
Предполагая, %%b = %% бит, положим, что %%b_1 = %% бит, значит %%b_2=%% бит,
%%m = %%
Если публичный ключ %%k%%, то, шифртекст:
( %%u = %% ,
%%v = %% )
Поскольку словарь зависит только от открытого ключа %%(p,g,y)%% и длины сообщения %%b%%, мы можем использовать его снова. Примечательно, что от сеансового ключа %%k%% словарь никак не зависит.
Используя атаку Meet in the Middle, мы помогли вычислить Еве сообщение %%m = %% .
Теперь рассмотрим работу алгоритма в режиме подписи.
Для подписи сообщения %%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. Там вы найдете много полезной информации, а также реализацию данного алгоритма в приложении обмена сообщениями.
Источники, которые мы использовали: