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

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

ОГЛАВЛЕНИЕ

Следующая >>


14.3.3. Докажите лемму 14.2.

14.3.4. Покажите, что если в атаке Франклина-Рейтера / = Ах Л- В
и ?" = 3, то наибольший общий делитель, появляющийся в
алгоритме, всегда линеен (при условии его существования).

14.3.5. Покажите, как разложить на множители модуль RSA^ если
известна половина старших значащих битов одного из его
делителей.
ГЛАВА 15
ОПРЕДЕЛЕНИЯ
СТОЙКОСТИ

Ц е л и главы
• Объяснить различные понятия стойкости схем шифрования, в
первую очередь семантическую стойкость и неразличимость
шифрования.
• Описать различные модели атак, в частности, рассказать об
адаптивной атаке с выбором шифротекста.
• Показать, как связаны концепции жесткости и адаптивной
атаки с выбором шифротекста.
• Исследовать криптосистемы RSA и Эль-Гамаль с точки зрения
этих определений стойкости и атак.
• Ввести понятия, имеюпще отношение к стойкости схем подписи.
• Показать, что наивная (не хэшированная) схема подписи RSA
нестойка из-за свойства гомоморфности.


15.1. Стойкость шифрования
До сих пор мы не исследовали детально вопроса о внедрении кри­
птографических примитивов в реальные протоколы и системы. При
проектировании криптографических систем нам нужно иметь абсо­
лютно точное представление о том, какие именно свойства стойко­
сти обеспечивает тот или иной примитив и как защитить разраба­
тываемые схемы от всех возможных атак.
По суш;еству, криптографические примитивы напоминают собой
или функцию RSA^ или потенцирование в кольце вычетов. Обе эти
функции являются односторонними, причем функция RSA — функ­
ция с секретом. При использовании примитивов в реальной схеме
необходимо быть очень внимательным. Например, функция RSA
полностью детерминирована, и при ее наивном использовании бу­
дут получаться тождественные шифротексты при шифровании тем
же ключом одного сообп];ения дважды. Как мы убедились в главах 7
Глава 15. Определения стойкости

и 14, это плохое свойство. Но есть и более веские причины избегать
шифрующих алгоритмов с детерминированным открытым ключом.
Чтобы понять, почему, нам следует разобраться сначала в том, что
означает стойкость криптосистемы. Начать надо с определения
- цели нападающего,
- соответствующих типов атак,
- вычислительной модели.
Мы будем обсуждать эти понятия в контексте криптосистем с от­
крытым ключом, но аналогичные концепции есть и в симметричном
шифровании.

15.1.1. П о н я т и я с т о й к о с т и
Нам надо разобраться, по существу, с тремя видами стойкости:
- теоретико-информационная или абсолютная стойкость;
- семантическая стойкость;
- полиномиальная стойкость.
Обсудим каждый из них поочередно. Эти понятия существенно бо­
лее сильные, чем раскрытие секретного ключа или дешифрование
криптограммы, о которых мы говорили раньше.

15.1.1.1. Теоретико-информационная стойкость. Напомним,
что схема называется абсолютно стойкой (обладает теоретико-ин­
формационной стойкостью), если нападающий с неограниченными
вычислительными возможностями не сможет извлечь никакой ин­
формации об открытом тексте, используя данный шифротекст. Те­
орема Шеннона (см. стр. 103) фактически утверждает, что ключ та­
кой системы равен по длине самому сообщению, причем никакой
ключ нельзя использовать дважды.
Очевидно, абсолютно стойкую систему невозможно создать в
рамках модели шифрования с открытым ключом, поскольку ши­
фрующий (открытый) ключ в такой модели должен использоваться
долго, причем его длина мала по сравнению со средним сообщением.
15.1.1.2. Семантическая стойкость. Семантическая стой­
кость похожа на теоретико-информационную, но здесь предполага­
ется, что атакующий обладает полиномиальными вычислительными
возможностями. Говоря формально, при любом распределении веро­
ятностей на пространстве сообщений все, что нападающий может
вычислить за полиномиальное время о данном открытом тексте по
15.1, Стойкость шифрования

данному шифротексту, он может узнать и без шифротекста. Дру­
гими словами, обладание шифротекстом никак не помогает извлечь
информацию о сообш;ении.
Приведем упрощенное формальное определение. Предположим,
что мы хотим извлечь однобитовую информацию из пространства
сообщений, т. е. значение фиксированной функции
^:М^{0,1}.
Допустим, что для любого т из пространства сообщений

Р{д{т) = 1) = Р{9{т) = 0) = ^,

где Р{д(гп) = а) — вероятность события ^(ш) = а. Кроме того,
будем считать, что открытые тексты и шифротексты имеют по­
стоянную длину (в частности, количество знаков в шифротексте не
даст никакой информации о подлежащем открытом тексте).
Под противником мы будем понимать алгоритм S, который по
открытому ключу Y и шифротексту С, полученному с помощью се­
кретного ключа х^ соответствующего У, пытается определить зна­
чение функции д от открытого текста т , ассоциированного с ши­
фротекстом С Таким образом, выходные данные алгоритма S со­
стоят из единственного бита, равного значению д{т).
Будем считать нападение успешным, если вероятность коррект­
ного определения значения д{т) больше половины. Ясно, что про­
тивник может угадать ответ с вероятностью ^ и не глядя на ши-
фротекст. Поэтому успешным атакующим можно назвать лишь тот
алгоритм, вероятность правильного ответа у которого увеличивает­
ся после изучения шифротекста. В связи с этим определим выигрыш
противника по формуле:

Advs = P{S{C,Y)=g{d:,{C)))-\

где dx обозначает расшифровывающую функцию с секретным клю­
чом д;, ассоциированным с открытым ключом У. В этих терминах
схема называется семантически стойкой, если
1
^ ^ ^ ^ ^ "71л'
J\^ля всех противников 5, всех функций д и всех многочленов р{к) с
достаточно большим параметром стойкости к.
15.1.1.3. Полиномиальная стойкость. Неприятность, связан­
ная с семантической стойкостью, заключается в том, что очень
Глава 15. Определения стойкости

трудно проверить, обладает ли конкретная схема этим свойством.
Полиномиальная стойкость, иногда называемая неразличимостью
шифрования., является несравненно более просто проверяемым свой­
ством. К счастью, мы покажем, что система, обладающая полино­
миальной стойкостью, семантически стойка. Следовательно, чтобы
проверить криптосистему на семантическую стойкость, достаточно
продемонстрировать ее полиномиальную криптостойкость.
Будем говорить, что система обладает свойством неразличи­
мости шифрования, или полиномиальной стойкостью, если ника­
кой атакующий не сможет победить в следующей игре с вероятно­
стью, превышающей 50%. Нападающий А, которому дана шифрую­
щая функция / у , соответствующая открытому ключу У, совершает
два шага:
- Поиск. На этой стадии нападающий генерирует два открытых
текста MQ И M I .
- Гипотеза. Нападающему дают шифротекст С^, соответству­
ющий одному из выбранных сообщений М^, причем скрывают
от него, какому именно. Цель нападающего — угадать значе­
ние Ь с вероятностью, большей 50%.
Заметим, что отсюда следует вероятностная природа полиномиаль­
но стойкой шифрующей функции, поскольку в противном случае
атакующий может вычислить
Ci = / K ( M I )

И сравнить полученное значение с Сь- Следовательно, выигрыш на­
падающего равен

AdvA = Р{А{гипотеза, Сь, Y, M Q , M I ) = Ь) - -

т. к. гипотеза нападающего состоит в выборе одного из возможных
значений Ь\ О или 1. Схема называется полиномиально стойкой, если
1
Adv^ ^
v{k)
при любом противнике А, произвольном многочлене р и достаточно
большом к.

15.1.2. Виды атак
Теперь нам следует ввести различные модели атак. Существует три
основных модели:
15.L Стойкость шифрования

- пассивная атака^ или атака с выбором открытого текста, СРА
(от англ. chosen plaintext attack);
- атака с выбором шифротекста^ ССА1 (от англ. chosen cipher-
text attack);
- адаптивная атака с выбором шифротекста^ ССА2 (от англ.
adaptive chosen ciphertext attack).

15.1.2.1. Пассивная атака. Пассивная атака — очень слабая
форма атаки. Нападаюш;ей Еве разрешается просматривать раз­
личные шифрованные сообп1;ения. Кроме того, ей открыт доступ к
«черному ящику», осуществляющему шифрование, но не расшифро­
вывание. Таким образом, пассивная атака — простейшая модель
нападения на криптосистему с открытым ключом, поскольку она
предусматривает открытый доступ к функции шифрования.
15.1.2.2. Атака с выбором шифротекста. Атака с выбором
шифротекста {CCAl)^ которую часто называют атакой обеденно­
го перерыва, представляет собой несколько более сильную модель
нападения. Здесь Еве предоставлен доступ к расшифровывающе­
му «черному ящику». Она может предлагать ящику расшифровать
полиномиальное число шифротекстов по ее выбору во время обе­
денного перерыва, пока законный пользователь аппарата подкреп­
ляет свои силы. После этого, спустя некоторое время, Еве дают те­
стовый шифротекст и предлагают дешифровать его или восстано­
вить какую-нибудь информацию о подлежащем открытом тексте
собственными силами, не прибегая к помощи «черного ящика».
В контексте нашей игры в полиномиальную стойкость, описан­
ной выше, эта атака означает, что нападающий может задавать
вопросы расшифровывающему прибору на первой стадии, т.е. на
стадии поиска^ но не во время стадии гипотезы.
15.1.2.3. Адаптивная атака с выбором шифротекста. Ада­
птивная атака с выбором шифротекста {ССА2) — наиболее сильная
форма атаки. В этом случае Еве можно пользоваться расшифро­
вывающим прибором А^ля расшифровывания любого шифротекста
по ее выбору, кроме тестового. Принято считать, что любая вновь
предлагаемая криптосистема с открытым ключом должна обладать
полиномиальной стойкостью по отношению к адаптивной атаке с
выбором шифротекста.
Следовательно, в нашей игре с полиномиальной стойкостью на­
падающий имеет право обращаться к расшифровывающему прибору
на любой стадии игры. При этом ему запрещается лишь подавать
Глава 15. Определения стойкости

на вход прибора тестовый шифротекст С^, иначе игра станет бес­
смысленной.
Сформулируем стандартное определение стойкости схемы ши­
фрования с открытым ключом. Аналогичное определение применя­
ется к симметричным системам шифрования.

Определение 15.1. Алгоритм шифрования с открытым ключом
называют стойким^ если он семантически стоек в отношении ада­
птивной атаки с выбором шифротекста.
Однако легче проверить, что данная криптосистема удовлетво­
ряет следуюш;ему определению.

Определение 15.2. Алгоритм шифрования с открытым ключом
называют стойким^ если он полиномиально стоек в отношении ада­
птивной атаки с выбором шифротекста.
На самом деле эти определения связаны между собой. Докажем,
например, следуюш;ий важный результат.

Теорема 15.3. При пассивном нападении полиномиально стойкая
система обязана быть семантически стойкой.
Доказательство. Применим метод «от противного». Предполо­
жим, что существует алгоритм шифрования, не являюш;ийся семан­
тически стойким, т. е. найдется такой алгоритм 5, что

Adv5 > -ттт
р{к)
А^ля некоторого многочлена р и достаточно большого числа к. По­
кажем, что этот алгоритм не будет и полиномиально стойким. Для
этого мы построим атаку А на полиномиальную стойкость схемы
шифрования, используюш;ую алгоритм S^ нападаюш;ий на семанти­
ческую стойкость, как оракул.
На стадии поиска в атаке А генерируются два сообш;ения MQ И
Ml, для которых
p(Mo)/5(Mi),
ЧТО можно легко сделать, опираясь на упрощенное формальное опре­
деление семантической стойкости, поскольку значения функции д от
сообщений распределены равномерно.
Противнику А выдается шифротекст С^, соответствующий од­
ному из выбранных сообщений, и предлагается определить Ь. На
этапе гипотеза нападающий передает шифротекст Сь оракулу 5,
который находит наилучшую гипотезу для значения д{ть). Алго-
15Л. Стойкость шифрования

ритм А сравнивает эту гипотезу с д{Мо) и g{Mi) и определяет зна­
чение 6.
Ясно, что если S достигает успеха при взломе семантической
стойкости схемы, то А удается взломать ее полиномиальную стой­
кость. Поскольку
Р{А{гипотеза, Сь, Y, MQ, M I ) = b) = P{S{C, Y) = g{d^{C))),
имеет место неравенство

AdvA - Adv5 > -TTT-
p{k)
Следовательно, полиномиальная стойкость влечет семантическую. •
Заметим, что если брать более сложное определение семантиче­
ской стойкости, то можно показать, что при пассивной атаке поня­
тия семантической и полиномиальной стойкости эквивалентны.

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

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

ОГЛАВЛЕНИЕ

Следующая >>