Введение

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

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

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

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

Сравнения

Сравнение двух целых чисел по модулю натурального числа m — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на m один и тот же остаток.
Величина остатка может быть получена бинарной операцией «взятия остатка» от деления, обозначаемой %%mod%%. Попробуйте:

%% \bmod{} %% %% = %%

Результат может быть также получен как %% \bmod{} %% , %% \bmod{} %% . Мы говорим, что и сравнимы по модулю :

%% \equiv %% (%% \bmod{} %% )

Операция сравнения по модулю является неотъемлемой частью многих систем шифрования. Главное свойство, которое делает сравнение по модулю настолько полезным для алгоритмов шифрования, заключается в том, что результат операции не раскрывает никакой информации о числе.

Узнайте больше про модульную арифетику на Wikipedia.

Конечные циклические группы и подгруппы

Циклическая группа — это математическая группа, порожденная одним из элементов в группе %%G%%. Так как мы будем говорить об алгоритме Эль Гамаля, то нас интересуют только два типа групп:

  • Группа целых чисел от %%1%% до %%p-1%% по операции умножения %%(mod p)%% для некоторого простого числа %%p%%, которое известно как %%\mathbb{Z}_p^*%%
  • Подгруппы %%\mathbb{Z}_p^*%% простого порядка

Узнайте больше о циклических группах на Wikipedia.

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

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

Alice

Bob

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}%%.

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

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

Алиса

    Данное число не является простым
    Нажмите на кнопку выше, чтоб увидеть спиcок примитивных корней
    Ошибка
    Число должно быть больше %%0%% и меньше %%p-1%%
    У вас нет сообщений.
    Публичный ключ
    -
    Зашифрованное сообщение
    -

    Боб

    Число должно быть больше %%0%% и меньше %%p-1%%
    Число должно быть больше %%0%% и меньше %%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

    Очередная атака, которую мы попробуем называется 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 = %% )

    1. Для всех %%m_1=1,...,2^{b_1}%%, создаем структуру словаря %%m_1^n \pmod{p} \to m_1%%
    2. Для всех %%m_2=1,...,2^{b_2}%%, вычисляем %%v^n m_2^{-n} \pmod{p}%% и ищем данное значение в словаре.
    3. Если мы найдем совпадение в словаре, мы нашли решение %%(m_1,m_2)%% для %%(v^n)(m_2^{-n}) = m_1^n \pmod{p}%% и %%m%% возможно равно %%(m_1)(m_2)%%.

    Поскольку словарь зависит только от открытого ключа %%(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)%%

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

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

    Боб

      Данное число не является простым
      Нажмите на кнопку выше, чтоб увидеть спиcок примитивных корней
      Ошибка
      Число должно быть больше %%0%% и меньше %%p-1%%
      Число должно быть больше %%0%% и меньше %%p-1%%
      Число должно быть больше %%0%% и меньше %%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')%% - значит, цифровая подпись для Эль Гамаля должна применяться вместе с Хеш-функцией.