Атака Винерса - Википедия - Wieners attack

В Атака Винера, названный в честь криптолога Майкла Винера, представляет собой тип криптографическая атака против ЮАР. Атака использует непрерывная дробь метод предоставления закрытого ключа d когда d маленький.

Справочная информация о RSA

Выдуманные персонажи Алиса и Боб люди, которые хотят безопасно общаться. В частности, Алиса хочет отправить Бобу сообщение, которое может прочитать только Боб. Сначала Боб выбирает два простые числа п и q. Затем он вычисляет RSA модуль N = pq. Этот модуль RSA публикуется вместе с шифрование показатель степени е. N и е сформировать пару открытых ключей (e, N). Сделав эту информацию общедоступной, каждый может зашифровать сообщения Бобу. В расшифровка показатель степени d удовлетворяет ${ displaystyle ed = 1 { bmod { lambda}} (N)}$, куда ${ displaystyle lambda (N)}$ обозначает Функция Кармайкла хотя иногда ${ displaystyle varphi (N)}$, то Фи-функция Эйлера, используется (примечание: это порядок мультипликативная группа ${ Displaystyle mathbb {Z} _ {N} ^ {*}}$, которая не обязательно является циклической группой). Показатель шифрования е и ${ displaystyle lambda (N)}$ также должно быть относительно простой так что есть модульный обратный. В факторизация из N и закрытый ключ d держатся в секрете, так что только Боб может расшифровать сообщение. Обозначим пару закрытых ключей как (d, N). Шифрование сообщения M дан кем-то ${ Displaystyle С эквив М ^ {е} { bmod {N}}}$ и расшифровка зашифрованного текста ${ displaystyle C}$ дан кем-то ${ Displaystyle С ^ {d} эквив (М ^ {е}) ^ {d} эквив М ^ {(ред)} эквив М { bmod {N}}}$ (с помощью Маленькая теорема Ферма ).

С использованием Евклидов алгоритм, можно эффективно восстановить секретный ключ d если кто знает факторизация из Н. Имея секретный ключ d, можно эффективно разложить на множители модуль N.^[1]

Маленький закрытый ключ

В ЮАР криптосистема, Боб может использовать небольшое значение d, а не большое случайное число, чтобы улучшить ЮАР расшифровка спектакль. Однако атака Винера показывает, что выбор небольшого значения для d приведет к небезопасной системе, в которой злоумышленник сможет восстановить всю секретную информацию, т.е. ЮАР система. Этот излом основан на теореме Винера, справедливой для малых значений d. Винер доказал, что злоумышленник может эффективно найти d когда ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$.^[2]

В статье Винера также представлены некоторые контрмеры против его атаки, которые позволяют быстро расшифровать. Ниже описаны два метода.

Выбор большого открытого ключа: Заменять ${ displaystyle e}$ к ${ displaystyle e '}$, куда ${ Displaystyle е '= е + к cdot лямбда (N)}$ для некоторых больших из ${ displaystyle k}$. Когда ${ displaystyle e '}$ достаточно большой, т.е. ${ displaystyle e '> N ^ { frac {3} {2}}}$, то атака Винера не может быть применена независимо от того, насколько мала ${ displaystyle d}$ является.

С использованием Китайская теорема об остатках: Предположим, кто-то выбирает d так что оба ${ displaystyle d_ {p} = d { bmod {(}} p-1)}$ и ${ displaystyle d_ {q} = d { bmod {(}} q-1)}$ маленькие, но ${ displaystyle d}$ сам нет, то пост расшифровка из ${ displaystyle C}$ можно сделать так:

1. Первое вычисление ${ Displaystyle M_ {p} Equiv C ^ {d_ {p}} { bmod {p}}}$ и ${ Displaystyle M_ {q} Equiv C ^ {d_ {q}} { bmod {q}}}$.
2. Используйте Китайская теорема об остатках для вычисления уникального значения ${ Displaystyle M in mathbb {Z_ {N}}}$ что удовлетворяет ${ Displaystyle M Equiv M_ {p} { bmod {p}}}$ и ${ Displaystyle M Equiv M_ {q} { bmod {q}}}$. Результат ${ displaystyle M}$ удовлетворяет ${ Displaystyle M Equiv C ^ {d} { bmod {N}}}$ по мере необходимости. Дело в том, что атака Винера здесь неприменима, потому что ценность ${ displaystyle d { bmod { lambda}} (N)}$ может быть большим.^[3]

Как работает атака Винера

Обратите внимание, что

${ displaystyle lambda (N) = operatorname {lcm} (p-1, q-1) = { frac {(p-1) (q-1)} {G}} = { frac { varphi (N)} {G}}}$

куда ${ Displaystyle G = НОД (п-1, д-1)}$

С

${ Displaystyle ed Equiv 1 { pmod { lambda (N)}}}$,

существует целое число K такой, что

${ displaystyle ed = K times lambda (N) +1}$

${ displaystyle ed = { frac {K} {G}} (p-1) (q-1) +1}$

Определение ${ Displaystyle к = { гидроразрыва {K} { gcd (K, G)}}}$ и ${ displaystyle g = { frac {G} { gcd (K, G)}}}$, и замена в приведенное выше дает:

${ displaystyle ed = { frac {k} {g}} (p-1) (q-1) +1}$.

Деленное на ${ displaystyle dpq}$:

${ displaystyle { frac {e} {pq}} = { frac {k} {dg}} (1- delta)}$, куда ${ displaystyle delta = { frac {p + q-1 - { frac {g} {k}}} {pq}}}$.

Так, ${ displaystyle { frac {e} {pq}}}$ немного меньше, чем ${ displaystyle { frac {k} {dg}}}$, а первый полностью состоит из общественных Информация. Однако метод проверки и предположения все еще требуется. При условии, что ${ displaystyle ed> pq}$ (разумное предположение, если только ${ displaystyle G}$ большое) последнее уравнение можно записать как:

${ Displaystyle edg = к (п-1) (д-1) + г}$

Используя простые алгебраический манипуляции и идентичности, предположение можно проверить на точность.^[1]

Теорема Винера

Позволять ${ Displaystyle N = pq}$ с ${ Displaystyle q$

. Позволять ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$.
Данный ${ displaystyle left langle N, e right rangle}$ с ${ Displaystyle ed Equiv 1 ( mathrm {mod} lambda (N))}$, злоумышленник может эффективно восстановить ${ displaystyle d}$.^[2]

Пример

Предположим, что открытые ключи ${ displaystyle left langle N, e right rangle = left langle 90581,17993 right rangle}$
Атака должна определить ${ displaystyle d}$.
Используя теорему Винера и непрерывные дроби приблизить ${ displaystyle d}$, сначала мы пытаемся найти непрерывные дроби расширение ${ displaystyle { frac {e} {N}}}$. Обратите внимание, что этот алгоритм находит фракции в самые низкие сроки. Мы знаем, что

${ displaystyle { frac {e} {N}} = { frac {17993} {90581}} = { cfrac {1} {5 + { cfrac {1} {29+ dots + { cfrac { 1} {3}}}}}} = left [0,5,29,4,1,3,2,4,3 right]}$

Согласно непрерывные дроби расширение ${ displaystyle { frac {e} {N}}}$, все сходящиеся ${ displaystyle { frac {k} {d}}}$ находятся:

${ displaystyle { frac {k} {d}} = 0, { frac {1} {5}}, { frac {29} {146}}, { frac {117} {589}}, { frac {146} {735}}, { frac {555} {2794}}, { frac {1256} {6323}}, { frac {5579} {28086}}, { frac {17993} { 90581}}}$

Мы можем убедиться, что первый сходящийся не производит факторизацию ${ displaystyle N}$. Однако сходящийся ${ displaystyle { frac {1} {5}}}$ дает

${ displaystyle varphi (N) = { frac {ed-1} {k}} = { frac {17993 times 5-1} {1}} = 89964}$

Теперь, если мы решим уравнение

${ Displaystyle х ^ {2} - влево ( влево (N- varphi (N) вправо) +1 вправо) х + N = 0}$

${ displaystyle x ^ {2} - left ( left (90581-89964 right) +1 right) x + 90581 = 0}$

${ displaystyle x ^ {2} -618x + 90581 = 0}$

тогда мы находим корни которые ${ displaystyle x = 379; 239}$. Таким образом, мы нашли факторизацию

${ Displaystyle N = 90581 = 379 times 239 = p times q}$.

Обратите внимание, что для модуля ${ displaystyle N = 90581}$, Теорема Винера будет работать, если

${ displaystyle d <{ frac {N ^ { frac {1} {4}}} {3}} приблизительно 5,7828}$.

Доказательство теоремы Винера.

Доказательство основано на приближении с использованием цепных дробей.^[2][4]
С ${ displaystyle ed = 1 { bmod { lambda}} (N)}$, существует ${ displaystyle { mathit {k}}}$ такой, что ${ displaystyle ed-k lambda (N) = 1}$. Следовательно

${ displaystyle left | { frac {e} { lambda (N)}} - { frac {k} {d}} right vert = { frac {1} {d lambda (N)} }}$.

Позволять ${ Displaystyle G = НОД (п-1, д-1)}$обратите внимание, что если ${ displaystyle varphi (N)}$ используется вместо ${ displaystyle lambda (N)}$, то доказательство можно заменить на ${ displaystyle G = 1}$ и ${ displaystyle varphi (N)}$ заменен на ${ displaystyle lambda (N)}$.

Затем умножая на ${ displaystyle { frac {1} {G}}}$,

${ displaystyle left | { frac {e} { varphi (N)}} - { frac {k} {Gd}} right vert = { frac {1} {d varphi (N)} }}$

Следовательно, ${ displaystyle { frac {k} {Gd}}}$ является приближением ${ displaystyle { frac {e} { varphi (N)}}}$. Хотя злоумышленник не знает ${ displaystyle varphi (N)}$, он может использовать ${ displaystyle N}$ чтобы приблизить это. Действительно, поскольку

${ Displaystyle varphi (N) = N-p-q + 1}$ и ${ displaystyle p + q-1 <3 { sqrt {N}}}$, у нас есть:

${ displaystyle left vert p + q-1 right vert <3 { sqrt {N}}}$

${ displaystyle left vert N- varphi (N) right vert <3 { sqrt {N}}}$

С помощью ${ displaystyle N}$ на месте ${ displaystyle varphi (N)}$ мы получаем:

${ displaystyle left vert { frac {e} {N}} - { frac {k} {Gd}} right vert = left vert { frac {edG-kN} {NGd}} вправо верт}$

${ displaystyle qquad = left vert { frac {edG-k varphi (N) -kN + k varphi (N)} {NGd}} right vert}$

${ displaystyle = left vert { frac {1-k (N- varphi (N))} {NGd}} right vert}$

${ displaystyle leq left vert { frac {3k { sqrt {N}}} {NGd}} right vert = { frac {3k { sqrt {N}}} {{ sqrt {N} }} { sqrt {N}} Gd}} leq { frac {3k} {d { sqrt {N}}}}}$

Сейчас же, ${ Displaystyle к лямбда (N) = ed-1$, так ${ Displaystyle к лямбда (N)$. С ${ Displaystyle е < лямбда (N)}$, так ${ Displaystyle к лямбда (N)$, то получаем:

${ Displaystyle к лямбда (N) < лямбда (N) d}$

${ Displaystyle к$

С ${ Displaystyle к$ и ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$Отсюда получаем:

(1) ${ displaystyle left vert { frac {e} {N}} - { frac {k} {Gd}} right vert leq { frac {1} {dN ^ { frac {1} { 4}}}}}$

С ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}, 2d <3d,}$ тогда ${ displaystyle 2d <3d$, мы получаем:

${ displaystyle 2d$, так что (2) ${ displaystyle { frac {1} {2d}}> { frac {1} {N ^ { frac {1} {4}}}}}$

Из (1) и (2) можно заключить, что

${ displaystyle left vert { frac {e} {N}} - { frac {k} {Gd}} right vert leq { frac {3k} {d { sqrt {N}}} } <{ frac {1} {d cdot 2d}} = { frac {1} {2d ^ {2}}}}$

Если ${ displaystyle left vert x - { frac {a} {b}} right vert <{ frac {1} {2b ^ {2}}}}$, тогда ${ displaystyle { frac {a} {b}}}$ сходится ${ displaystyle x}$, таким образом ${ displaystyle { frac {k} {d}}}$ появляется среди конвергентов ${ displaystyle { frac {e} {N}}}$. Следовательно, алгоритм действительно в конечном итоге найдет ${ displaystyle { frac {k} {Gd}}}$.

Рекомендации

дальнейшее чтение

• Медник, Дон (1996). Низкоэкспонентный RSA со связанными сообщениями. Springer-Verlag Berlin Heidelberg.

• Дуйелла, Андрей (2004). Непрерывные дроби и RSA с малой секретной экспонентой.
• Реализация атаки Винера на Python.
• Р. Стинсон, Дуглас (2002). Теория и практика криптографии (2е изд.). Пресс-служба CRC. С. 200–204. ISBN  1-58488-206-9.