13.3Атака 1. Расшифровка ранее полученного сообщения при помощи специально подобранного текста.

Тип атаки - «Атака с заданным текстом».

Злоумышленник перехватывает сообщение, адресованное А, зашифрованное открытым ключом А. Для того чтобы расшифровать его, злоумышленник составляет другое сообщение, зависящее от перехваченного, и передает составленное сообщение на подпись А (то есть А применяет свой закрытый ключ для этого сообщения!). Затем, произведя несложные вычисления, получает расшифрованный текст.

Рассмотрим следующий пример. Все расчеты будем вести с небольшими числами для наглядности. А открытым способом распространяет криптографическую пару: открытый ключ и модуль – (e=7, n=33). Пусть В передает А число, например 2, зашифрованное открытым ключом А, то есть передает ss = 2^7 mod 33 = 29. С перехватывает это число (29), кроме того, С, как и всем остальным известна криптографическая пара (7, 33). Цель C – расшифровать перехваченное сообщение 29.

С сначала подбирает два числа t и r, меньшие n, такие что t = (1/r) mod n. В нашем примере n = 33, поэтому возьмем r = 17, t = 2 (17*2 Mod 33 =1).

А затем вычисляет x = r^e mod n = 17^7 mod 33 = 8. Теперь берет перехваченное число ss и вычисляет y = ss*x mod n = 29*8 mod 33 = 1.

Настал важный момент. Если С имеет возможность попросить А зашифровать произвольный текст своим закрытым ключом, то есть фактически подписать какой-то документ, то полученный y передается А на подпись. А подписывает y и передает С, то есть С получает u = y ^ d mod n. В нашем примере А вычисляет u = 1 ^ 3 mod 33 = 1 (d=3 – закрытый ключ А) и отдает C.

Теперь С, наконец, расшифровывает ранее перехваченное сообщение следующим образом: s = t*u mod n = 2*1 mod 33 = 2. Как видите, это и отправлял В.

t*u mod n = u/r mod n = y^d/r mod n = (x^d * ss^d)/r mod n =

= ss^d mod n = s

Преобразуем t*u mod n, заменив t на 1/r, получим u/r mod n. Подставим выражение для y, получим (x^d * ss^d)/r mod n. А так как x = r^e mod n, то r = x^d mod n по основному соотношению между открытым и закрытым ключом. Сокращаем одинаковые выражения в числителе и знаменателе, получаем ss^d mod n. А это по основному соотношению между открытым и закрытым ключом равно исходному сообщению.

Замечание 1. В нашем примере можно было А и не передавать y на подпись, так как 1 в любой степени останется 1. Но это – счастливая случайность, практически невероятная.

Замечание 2. Важно, что передается сообщение, а не его хэш. Так как расшифровка хэш ничего не дает узнать о сообщении (если оно закрыто) и не дает возможности подделать документ, даже если он открыт, в случае если нет возможности полностью модифицировать трафик.

13.4Атака 2. Подпись нотариуса на неверном документе.

Пусть А – нотариус. Если В хочет заверить документ, он отправляет его А, тот подписывает весь документ своим закрытым ключом. Но нотариус может отказаться подписать некоторый документ, так как он с его точки зрения не является законным. С хочет заставить нотариуса подписать этот документ.

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

Для того чтобы сократить вычисления, возьмем те же n=33, закрытый ключ d=3, открытый ключ e=7. Нам также понадобится некоторое t, такое что, существует t^-1 mod n, то есть возьмем t =2, обратное по модулю 33 к которому равно 17.

Итак, С хочет подписать сообщение s = 5, но нотариус этого делать не будет. Тогда С вычисляет y = t^e mod n = 2^7 mod 33 = 29. Затем С рассчитывает m = y*s mod n = 29*5 mod 33 = 13 и посылает это m на подпись нотариусу. Понятно, что нотариусу число 13 нравится гораздо больше, чем число 5, и он с радостью подписывает его, то есть возвращает p = m^d mod n = 13^3 mod 33 = 19.

Теперь С вычисляет значение p*t^-1 mod n = 19*17 mod 33 = 26. Интересно то, что это – нужный нам подписанный документ.

p*t^-1 mod n = (m^d * t^-1) mod n = (y^d *s^d * t^-1) mod n. А так как y = t^e mod n, то y^d mod n = t^-1, сокращаем эти два выражения и получаем s^d mod n, то есть подписанное интересующее нас s.

Проверим результат в числах s^d mod n = 5^3 mod 33 = 26.