<< Предыдущая

стр. 57
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

где г — зависящее от т случайное число длины п — к, Копперсмит
показал, что такое пополнение сообщения нестойко.
Предположим, что Боб дважды посылает одно сообщение Алисе,
т. е. возникает два шифротекста Ci и С2, соответствующих сообще­
ниям
Ш1 = 2^˜^т + п , т 2 = 2^˜^т + Г2,
где Г1 и Г2 — два разных случайных числа, состоящие из п —/с битов.
Атакующий вводит обозначение уо = ^2 — ^1 и пытается решить
систему уравнений:
Г gi{x,y) =х^ -Си
\ д2{х,у) = {х + у)^-С2.
Глава Ц' Атаки на схемы с открытым ключом

Он вычисляет результант h{y) многочленов gi{x^y) и д2{х^у) отно­
сительно переменной х. Теперь уо — маленький корень многочлена
h{y) степени Е^, Опираясь на теорему Копперсмита 14.3, нападаю­
щий находит разность Г2 — ri и узнает т 2 , используя метод атаки
Франклина-Рейтера.
Поскольку тривиальная схема пополнения сообщений дискреди­
тирована, нужно найти стойкий метод пополнения сообщений А^ЛЯ
криптосистемы RSA. К этому вопросу мы вернемся в главе 17.

14.4.3. О б о б щ е н и е а т а к и В и н е р а
Напомним, что атака Винера на RSA возможна в том случае, если
атакующему известно о неравенстве



где d — секретная экспонента, а. N — модуль RSA. Бонех и Дерфи,
используя двумерный аналог теоремы Копперсмита (т. 14.3), с по­
мощью эвристического алгоритма смогли обобщить атаку Винера
на случай, когда
d ^ iV^'^^2.
Мы не будем рассказывать о нем подробно, но покажем, как ав­
торы подходят к проблеме, известной под именем задачи о малом
обратном.
Пусть у нас есть Д^Л-модуль 7V, шифрующая экспонента Е и
расшифровывающая экспонента d. По определению, существует та­
кое целое число А;, что


где ср = ^{N) — порядок группы обратимых элементов в кольце
Z/NZ, Подставляя в эту формулу значение (^, получим


--4^-^)='-
Положим

2 ' 2
Теперь при малом d, т. е. d < 7V^, его вычисление равносильно поиску
двух малых решений к и s уравнения:
/(А;, s) = k{A + s) = l (modE),
Чтобы увидеть, что к и s действительно малы по сравнению с мо-
14-5. Частичное раскрытие ключа

дулем Е этого уравнения, обратите внимание на то, что Е ^ N.,
поскольку d мало, и поэтому

\s\ < 2N'''^ Е''^ и \к\<^^^^Е'.
ip N
Поиск целых чисел к и s можно интерпретировать как поиск целого
числа, близкого к Л, обратный к которому по модулю Е мал. Это
и называется задачей о малом обратном. Бонех и Дерфи показали,
что задача имеет решение при J ^ 0,292. Следовательно, они уси­
лили атаку Винера. Способ, с помощью которого авторы добились
успеха, основывается на многомерном аналоге методе Копперсмита,
применяемом к многочлену /(А:, 5).


14.5. Частичное раскрытие ключа

Частичное раскрытие 1слюча относится к следующему вопросу. Пред­
положим, что в некоторой криптографической схеме нападающий
узнал какое-то множество битов секретного ключа. Может ли он,
опираясь на эту информацию, полностью восстановить секретный
ключ? Иначе говоря, приводит ли частичное раскрытие секретного
ключа к полному взлому криптосистемы? Приведем несколько при­
меров, связанных с RSA., хотя стоит отдавать себе отчет, что они
не исчерпывают всех возможных ситуаций. Существует несколько
теоретических результатов, посвященных частичному раскрытию
ключа и в других схемах, например, DSA и криптосистемах с сим­
метричным ключом.

14.5.1. Частичное раскрытие секретной
экспоненты в RSA
Удивительно, но в наиболее общем случае эксплуатирования систе­
мы RSA с малой шифрующей экспонентои Е можно тривиальным
образом раскрыть половину высших значащих битов секретной экс­
поненты. Напомним, что существует такое натуральное число А;, что
О <к <Е и
Ed-k{N-{p + q) + l) = l.
Теперь предположим, что для каждого возможного значения г (О <
г ^ Е) нападающий вычисляет


\ Е \
370 Глава 14- Атаки на схемы с открытым ключом

Тогда


Следовательно, D^ — хорошее приближение к истинному значению
расшифровывающей экспоненты d.
Очевидно, число к должно быть четным. Поэтому при Е = 3 мы
должны получить А = 2. Значит, D2 содержит половину значащих
:
битов экспоненты d. К сожалению для нападающего и к счастью для
пользователя криптосистемы, нет никакого способа узнать оставшие­
ся биты экспоненты, имея лишь половину главных значащих цифр.

14.5.2. Частичное раскрытие простых
множителей модуля RSA
Предположим, что п-битовый модуль N алгоритма RSA имеет раз­
ложение на простые множители N = pqcp^qm атакующий узнал
J наименьших значащих битов числа р. Напомним, что общее коли­
чество знаков в р должно быть около | . Так что атакующий знает
младшую половину всех значащих битов множителя р. Запишем
р = жо2^ + Ро, q = 1/о2^ + до,
где Ро — известный набор знаков. Тогда
N = Poqo (mod2t)
и мы можем определить величину^ qo = Qo- Далее выпишем много­
член
р{х,у) = (Ро + 2Ta:)(Qo + 2?у) = PoQo + 2?(Роу + Qox) + 2^ху,
Многочлен р{х^ у) второй степени зависит от двух переменных и
имеет «известный» малый корень по модулю N^ а именно (жо, уо), где
0<гго, 2/0^24 ^ N"^, Следовательно, применяя обобщение теоремы
Копперсмита 14.3, можно найти XQ И уо? после чего разложить N на
множители.
Аналогичная атака имеет успех, когда нападающему известна
старшая половина значащих цифр числа р.

14.5.3. Частичное раскрытие младп1их значащих
цифр секретной экспоненты RSA
Предположим, что при малой шифрующей экспоненте Е в RSA из­
вестна четверть младших значащих бит расшифровывающей экспо-
^И поэтому будем обозначать ее как Qo. — Прим. перев.
14'6. Анализ дефектов 371

ненты d, т. е.
d = Do + 2^а:о,
Зп

где DQ — известно и О ^ гго ^ 2 4 . Напомним, что существует
четное число к {О < к < Е), при котором
Ed-k{N-{p + q) + l) = h
Поскольку N = pq^ получаем:
Edp - kp{N - р -\-1) + kN = p.
Если положить ро = р (mod 2^), то возникает уравнение
EDoPo - kpo{N-po + l) + kN-po = 0 (mod2?), (14.3)
которое дает нам алгоритм полного восстановления экспоненты d.
Для каждого четного числа А;, не превосходящего Е, решаем относи­
тельно Ро уравнение (14.3) по модулю 2^. При этом получится О(^)
возможных значений для ро- Беря поочередно каждое из них, будем
пытаться разложить N на множители, опираясь на технику преды­
дущего подпараграфа. Одно из таких ро совпадает с р (mod 2^). В
этом случае мы сможем разложить N на множители и тем самым
восстановить d.


14.6. Анализ дефектов

Интересный класс атак сводится к попыткам внести сбой в работу
криптосистемы. Ограничимся описанием такого сорта нападений
на алгоритм подписи RSA^ хотя подобные атаки возможны и на
другие алгоритмы, как с открытым, так и с секретным ключом.
Вообразите, что у нас есть аппаратная реализация RSA^ напри­
мер, смарт-карта. Микропроцессор карты подписывает сообщения
для нас, используя встроенный секретный ключ RSA^ а нападаю­
щий, естественно, стремится его раскрыть. С этой целью он ста­
рается вынудить микропроцессор карты допустить ошибки в вы­
числениях, например нагрев ее или охладив, или как-то несильно
повредив карту любым доступным способом.
Любопытный случай возникает, когда микропроцессор карты
использует китайскую теорему об остатках в целях ускорения про­
цедуры подписи, как это описано в главе 11 на стр.293. При этом
сначала вычисляется хэш-значение от сообщения:
Я = /i(M),
Глава 14- Атаки на схемы с открытым ключом

а затем
Sp = Н^р (modp), Sq = h^4 (modg),
где dp = d (modp — 1) li dq = d (mod^ — 1). Окончательная подпись
получается из 5^ и Sq благодаря китайской теореме об остатках:
и == {sq — Sp)t (modg), S = Sp-i- up^
где t = p˜^ (modg).
Допустим теперь, что атакующий смог ввести дефекты в вычи­
сления таким образом, что Sp оказалось вычислено неверно. Тогда
он получит значение подписи 5, удовлетворяющее соотношениям:
S^ ^Н (modp), S^ = Н {modq).
Следовательно, вычисляя
9 = НОД(5^-Я,ЛГ),
МОЖНО разложить N на множители.

К р а т к о е с о д е р ж а н и е главы

- Использование малой шифрующей экспоненты в RSA — не­
удачная идея ввиду атаки Винера.
- Решетки — дискретный аналог векторных пространств. В них
есть наименьший ненулевой вектор.
- Приведение базиса часто дает наименьший ненулевой вектор
в данной решетке.
- Теорема Копперсмита позволяет найти решение полиномиаль­
ного уравнения в кольце вычетов, если известно, что решение
мало. Метод поиска решения основан на построении решетки,
зависящей от уравнения, и приведения ее базиса д,ля отыска­
ния наименьшего вектора.
- Атаки Хастада и Франклина-Рейтера показывают, что необ­
ходимо соблюдать осторожность при разработке схем попол­
нения сообщений в криптосистеме RSA.
- Опираясь на теорему Копперсмита, можно доказать, что ча­
стичное раскрытие знаков или р и q^ или d в RSA может спо­
собствовать полному взлому криптосистемы.

Дополнительная литература
Основная работа об атаке Копперсмита на RSA^ использующей ре­
шетки, принадлежит самому Копперсмиту. Этот подход к атакам
Ц^б. Анализ дефектов

был упрощен в статье Хоугрэйв-Грэхема. Рассказ об атаках на RSA
в этой главе близко следует обзору Бонеха. Полный обзор крипто­
графических методов, основанных на решетках, дан в работе Нгу-
ена и Стерна.
D. Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of
the American Mathematical Society (AMS), 46, 203-213, 1999.
D. Coppersmith. Small solutions to polynomial equations, and low expo-
nent RSA vulnerabilities, J. Cryptology, 10, 233-260, 1997.
N. Howgrave-Graham. Finding small solutions of univariate modular
equations revisited. In Cryptography and Coding, Springer-Verlag LNCS
1355, 131-142, 1997.
P. Nguyen and J. Stern. The two faces of lattices in cryptology. In CALC
'01, Springer-Verlag LNCS 2146, 146-180, 2001.

Контрольные вопросы
14.1.1. Как разложить вещественное число а в непрерывную дробь?

14.1.2. Какое число нужно разлагать в непрерывную дробь при ата­
ке Винера на RSA с малой секретной экспонентой?

14.1.3. Что такое решетка?

14.1.4. Как Вы думаете, какое из свойств LLL-приведенных базисов
решетки наиболее важно с точки зрения криптографии?

14.1.5. Предположим, что у нас есть уравнение f{xo) = О (тоёЛГ),
где / — многочлен степени D. Насколько маленьким должен
быть корень XQJ чтобы его можно было найти за полиноми­
альное время, используя метод Копперсмита?

14.1.6. Объясните, что подразумевают, говоря об атаке Хастада на
криптосистему RSA1

Лабораторные работы
14.2.1. Реализуйте на программном уровне различные атаки из этой
главы, такие как атака Винера и атаки на основе LLL-алго-
ритма. Исследуйте с их помощью следующие вопросы:
(а) существуют ли ситуации, когда эвристические аргу­
менты в этой главе не работают?
(б) существуют ли ситуации, при которых атаки более
успешны, чем позволяет теоретический анализ?
374 Глава 14- Атаки на схемы с открытым ключом

Упражнения
14.3.1. Покажите, что р^ля LLL-приведенного базиса п-мерной ре­
шетки L выполняется условие: если х — ненулевой вектор
решетки, то
||6ilK2^IN|.
14.3.2. Покажите на формальном уровне, что LLL-алгоритм, опи­
санный в тексте, действительно завершается в течение поли­
номиального времени, если базис решетки имеет целые коор­
динаты.

<< Предыдущая

стр. 57
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>