Атака Копперсмита

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Coppersmith's attack" – news · newspapers · books · scholar · JSTOR (April 2024) (Learn how and when to remove this message) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (April 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

Атака Копперсмита описывает класс криптографических атак на криптосистему с открытым ключом RSA, основанных на методе Копперсмита . Конкретные применения метода Копперсмита для атаки на RSA включают случаи, когда открытая экспонента e мала или когда доступно частичное знание простого множителя секретного ключа.

Открытый ключ в системе RSA представляет собой кортеж целых чисел , где N — произведение двух простых чисел p и q . Секретный ключ задается целым числом d, удовлетворяющим ; эквивалентно, секретный ключ может быть задан и если для повышения скорости расшифровки используется китайская теорема об остатках , см. CRT-RSA . Шифрование сообщения M создает зашифрованный текст , который может быть расшифрован с помощью вычисления .${\displaystyle (N,e)}$${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$${\displaystyle d_{p}\equiv d{\pmod {p-1}}}$${\displaystyle d_{q}\equiv d{\pmod {q-1}}}$ ${\displaystyle C\equiv M^{e}{\pmod {N}}}$${\displaystyle d}$${\displaystyle C^{d}\equiv M{\pmod {N}}}$

Чтобы сократить время шифрования или проверки подписи, полезно использовать небольшую публичную экспоненту ( ). ^[1] На практике распространенным выбором для являются 3, 17 и 65537 . Эти значения для e являются простыми числами Ферма , иногда называемыми и соответственно . Они выбраны потому, что они ускоряют операцию модульного возведения в степень . Кроме того, выбрав такие , проще проверить , и при генерации и тестировании простых чисел на шаге 1 генерации ключа . Значения или , которые не проходят этот тест, можно отклонить тут же. (Еще лучше: если e является простым числом и больше 2, то тест может заменить более дорогой тест .)${\displaystyle e}$${\displaystyle e}$ ${\displaystyle (2^{16}+1)}$${\displaystyle F_{0},F_{2}}$${\displaystyle F_{4}}$${\displaystyle (F_{x}=2^{2^{x}}+1)}$${\displaystyle e}$${\displaystyle \gcd(e,p-1)=1}$${\displaystyle \gcd(e,q-1)=1}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p{\bmod {e}}\neq 1}$${\displaystyle \gcd(p-1,e)=1}$

Если публичная экспонента мала, а открытый текст очень короток, то функцию RSA можно легко инвертировать, что делает возможными определенные атаки. Схемы заполнения гарантируют, что сообщения имеют полную длину, но дополнительно рекомендуется выбирать публичную экспоненту . При использовании этого значения проверка подписи требует 17 умножений, в отличие от примерно 25 при использовании случайной величины аналогичного размера. В отличие от низкой частной экспоненты (см. атаку Винера ), атаки, которые применяются при использовании небольшой экспоненты , далеки от полного взлома , который позволил бы восстановить секретный ключ d . Самые мощные атаки на RSA с низкой публичной экспонентой основаны на следующей теореме, которая принадлежит Дону Копперсмиту .${\displaystyle m}$${\displaystyle e=2^{16}+1}$${\displaystyle e}$${\displaystyle e}$

Для облегчения понимания представлена ​​простейшая форма атаки Хостада. ^[2] В общем случае используется метод Копперсмита.

Предположим, что один отправитель отправляет одно и то же сообщение в зашифрованном виде нескольким людям , каждый из которых использует одну и ту же малую публичную экспоненту , скажем , и разные модули . Простой аргумент показывает, что как только шифртексты известны, сообщение больше не является безопасным: Предположим, что Ева перехватывает , и , где . Мы можем предположить для всех (в противном случае можно вычислить множитель одного из чисел , вычислив .) По китайской теореме об остатках она может вычислить такое, что . Тогда ; однако, поскольку для всех , мы имеем . Таким образом , справедливо для целых чисел, и Ева может вычислить кубический корень из , чтобы получить .${\displaystyle M}$${\displaystyle P_{1};P_{2};\dots ;P_{k}}$${\displaystyle e}$${\displaystyle e=3}$${\displaystyle \left\langle N_{i},e\right\rangle }$${\displaystyle k\geq 3}$${\displaystyle M}$${\displaystyle C_{1},C_{2}}$${\displaystyle C_{3}}$${\displaystyle C_{i}\equiv M^{3}{\pmod {N_{i}}}}$${\displaystyle \gcd(N_{i},N_{j})=1}$${\displaystyle i,j}$${\displaystyle N_{i}}$${\displaystyle \gcd(N_{i},N_{j})}$${\displaystyle C\in \mathbb {Z} _{N_{1}N_{2}N_{3}}^{*}}$${\displaystyle C\equiv C_{i}{\pmod {N_{i}}}}$${\displaystyle C\equiv M^{3}{\pmod {N_{1}N_{2}N_{3}}}}$${\displaystyle M<N_{i}}$${\displaystyle i}$${\displaystyle M^{3}<N_{1}N_{2}N_{3}}$${\displaystyle C=M^{3}}$${\displaystyle C}$${\displaystyle M}$

Для больших значений требуется больше шифртекстов, в частности, достаточно шифртекстов.${\displaystyle e}$${\displaystyle e}$

Хастад также показал, что применение линейного дополнения к до шифрования не защищает от этой атаки. Предположим, что злоумышленник узнает, что для и некоторой линейной функции , т. е. Боб применяет дополнение к сообщению до его шифрования , так что получатели получают немного разные сообщения. Например, если длина бит, Боб может зашифровать и отправить это -му получателю.${\displaystyle M}$${\displaystyle C_{i}=f_{i}(M)^{e}}$${\displaystyle 1\leq i\leq k}$${\displaystyle f_{i}}$ ${\displaystyle M}$${\displaystyle M}$${\displaystyle m}$ ${\displaystyle M_{i}=i2^{m}+M}$${\displaystyle i}$

Если задействована достаточно большая группа людей, злоумышленник может восстановить открытый текст из всего шифротекста с помощью аналогичных методов. В более общем смысле, Хостад доказал, что система одномерных уравнений по модулю относительно простых составных чисел, например, применение любого фиксированного многочлена , может быть решена, если предоставлено достаточно много уравнений . Эта атака предполагает, что в шифровании RSA следует использовать рандомизированное заполнение .${\displaystyle M_{i}}$ ${\displaystyle g_{i}(M)\equiv 0{\pmod {N_{i}}}}$

Франклин и Рейтер выявили атаку против RSA , когда зашифровано несколько связанных сообщений: Если два сообщения отличаются только известным фиксированным различием между двумя сообщениями и зашифрованы RSA по одному и тому же модулю RSA , то возможно восстановить их оба. Атака изначально была описана с публичной экспонентой , но она работает более широко (с увеличением стоимости по мере роста). ${\displaystyle N}$ ${\displaystyle e=3}$${\displaystyle e}$

Пусть будет открытым ключом Алисы. Предположим, что есть два различных сообщения, удовлетворяющих некоторому публично известному полиному . Чтобы отправить и Алисе, Боб может наивно зашифровать сообщения и передать полученные шифртексты . Ева может легко восстановить , учитывая , используя следующую теорему:${\displaystyle \left\langle N;e_{i}\right\rangle }$${\displaystyle M_{1};M_{2}\in \mathbb {Z} _{N}}$${\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}}$ ${\displaystyle f\in \mathbb {Z} _{N}[x]}$${\displaystyle M_{1}}$${\displaystyle M_{2}}$ ${\displaystyle C_{1};C_{2}}$${\displaystyle M_{1};M_{2}}$${\displaystyle C_{1};C_{2}}$

Подобно атакам Хостада и Франклина-Рейтера, эта атака использует слабость RSA с публичной экспонентой . Копперсмит показал, что если рандомизированное заполнение, предложенное Хостадом, используется неправильно, то шифрование RSA не является безопасным.${\displaystyle e=3}$

Предположим, Боб отправляет сообщение Алисе, используя небольшое случайное дополнение перед его шифрованием . Злоумышленник, Ева, перехватывает шифротекст и не дает ему достичь адресата. Боб решает повторно отправить сообщение Алисе, поскольку Алиса не ответила на его сообщение. Он снова случайным образом дополняет его и передает полученный шифротекст. Теперь у Евы есть два шифротекста, соответствующих двум шифрованным сообщениям с использованием двух разных случайных дополнений.${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$

Даже если Ева не знает, какой случайный блок данных используется, она все равно может восстановить сообщение, используя следующую теорему, если случайный блок данных слишком короткий.${\displaystyle M}$

• Атака РОКА