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

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

ОГЛАВЛЕНИЕ

Следующая >>

(1) голосовать имеют право только уполномоченные избиратели;
(2) ни один из голосующих не может отдать более одного голоса;
(3) ни один из участников процесса не может узнать, как прого­
лосовал кто-то другой;
(4) никто не может продублировать голос какого-то другого участ­
ника компании;
Глава 13. Протоколы

(5) конечный результат будет корректно подсчитан;
(6) каждый из участников способен проверить, что результат под­
считан правильно;
(7) протокол будет работать и в случае, когда некоторые из его
участников нечестны.

13.4.1. Установки системы
Каждая из счетных комиссий обладает шифрующей функцией с от­
крытым ключом Ег. Будем предполагать, что фиксирована конеч­
ная абелева группа А простого порядка Q, в которой выбрана пара
элементов В иС, причем никто (включая счетные комиссии) не зна­
ет решения уравнения


Каждый из голосуюпщх имеет алгоритм подписи с открытым ключом.

13.4.2. Заполнение бюллетеня
Каждый из т избирателей выбирает голос Vj G {—1,1}, случайное
затемняюш;ее число aj G Z/QZ и публикует свое решение:
Dj=Daj{Vj),
используя схему обязательств из параграфа 13.2. Это решение ста­
новится известным всем сторонам голосования: как счетным ко­
миссиям, так и остальным избирателям. Вместе с Bj избиратель
публикует автономную версию рассмотренного ранее протокола в
подтверждение того, что его голос действительно выбран из мно­
жества {—1,1}. Голос вместе с доказательством подписывается с
помош;ью схемы подписи, принадлежап];ей избирателю.

13.4.3. Р а с п р е д е л е н и е б ю л л е т е н е й
Для подведения итогов необходимо передать отданные голоса счет­
ным комиссиям. Чтобы передать aj и Vj счетным комиссиям, ка­
ждый избиратель применяет схему Шамира разделения секрета. С
этой целью он выбирает два случайных многочлена по модулю Q
степени Т < п
Rj{X) = VJ + njX + • • • + TTjX^,
Sj{X) = aj + sijX -f • • • + ST,jX^,
и вычисляет
(uij.Wij) = (Rjii), Sj{i)) при 1 ^ г ^ n.
13.4' Система электронного голосования 349

Голосующий шифрует пары (uij^Wij)^ используя алгоритм Е{ г-ой
счетной комиссии, и отсылает ей полученный результат. После это­
го избиратель передает многочлен Rj{X)^ открыто регистрируя
Di,j = Ds„jiri,j) при 1 < / < Г,
С помощью все той же описанной ранее схемы.

13.4.4. П р о в е р к а д о с т о в е р н о с т и и н ф о р м а ц и и
Каждая из счетных комиссий должна проверить, что пара {щ^^ Щ^)
действительно получена от избирателя с номером j и согласуется с
переданным обязательством. Это достигается в результате провер­
ки следующих равенств:
т т
DiXlDi^ = D^^)XlD,,^^{n,^y =
1=1 /=1
т

1=1




13.4.5. П о д с ч е т г о л о с о в
Каждая из п счетных комиссий подсчитывает бюллетени и публи­
кует результаты:
т



Кроме того, она обнародует сумму затемняющих факторов:
т



Любой другой участник процедуры голосования, будь то счетная
комиссия или избиратель, может убедиться в корректности опубли­
кованных сумм, проверяя, что
т/ Т \ т
П ^ J U ^ C 1 = П B'^'^'G'^'^' = B^'G^K
3= 1 \ 1=1 / 3=1
Каждая из сторон процесса может определить итог, беря Т значе­
ний Ui и интерполируя по ним окончательный результат. Дело в
том, что Ui — значение многочлена, представляющего сумму голо-
Глава IS. Протоколы

сов, в точке г. Чтобы убедиться в этом, рассмотрим
т т


3= 1 j=l




Если результат — отрицательное число, то большинство избирателей
написало на бюллетене число «—1», а если положителен, то большин­
ство поставило «+1». Осталось лишь показать, что этот протокол
голосования обладает всеми семью свойствами, которые были анон­
сированы на стр. 347. Оставим это в качестве легкого упражнения.

Краткое содержание главы
- Схемы обязательств дают возможность участнику спрятать
переданное значение и открыть его позже.
- Схемы обязательств должны обладать скрываюш;им и связы-
ваюш;им свойствами. Разработаны эффективные схемы, кото­
рые обладают или теоретико-информационно связываюш;им,
или теоретико-информационно скрываюш;им свойством, но не
одновременно.
- Интерактивное доказательство знания не разглашает никакой
информации, если записи соответствующего протокола могут
имитироваться без привлечения секретной информации.
- Интерактивные доказательства знания можно трансформиро­
вать в алгоритм цифровой подписи, если заменить запрос хэш-
значением, связанным с сообщением.
- Используя основные примитивы шифрования, подписей, схем
обязательств и доказательств с нулевым разглашением, можно
создать довольно сложные протоколы. Как пример такой кон­
струкции был приведен протокол электронного голосования.

Дополнительная литература
Книга Гольдрайха содержит множество подробностей о доказатель­
ствах с нулевым разглашением. С другой стороны, книга Стинсона
дает хороший обзор этой темы. Протокол голосования, который был
у нас описан, взят из статьи Крамера и др.
R. Cramer, М. Franklin, В. Schoenmakers and М. Yung. Multi-authority
secret-ballot elections with linear work. In Advances in Cryptology —
EuroCrypt '96, Springer-Verlag LNCS 1070, 72-83, 1996.
13.4' Система электронного голосования 351

О. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudo-
randomness. Springer-Verlag, 1999.
D. Stinson. Cryptography: Theory and Practice. CRC Press, 1995.

Контрольные вопросы
13.1.1. Что такое схемы обязательств?

13.1.2. Что означают свойства связывания и сокрытия для схем обя­
зательств?

13.1.3. Как можно использовать протокол доказательства с нулевым
разглашением в целях идентификации?

13.1.4. Покажите, что если в протоколе об изоморфизме графов Пег­
ги использует один и тот же граф Н дважды, то Виктор
сможет определить скрываемый изоморфизм графов.

13.1.5. Как можно переделать интерактивную идентификационную
схему с нулевым разглашением в алгоритм цифровой подписи?

Упралснения
13.2.1. Пусть в группе А фиксированы четыре элемента Gi, G2, Bi
и ^ 2 , причем Пегги известен логарифм
b g G i Bi = logG'2 ^ 2 "" ^•
Разработайте протокол, с помощью которого Пегги может
доказать Виктору, что эти два логарифма совпадают, не рас­
крывая значения х.

13.2.2. Покажите, что доказательство с нулевым разглалхением спра­
ведливости обязательства Da{x), приведенное в тексте для
X G {—1,1}, имеет два основных свойства (см. стр. 344).

13.2.3. Покажите, что протокол голосования обладает семью свой­
ствами (см. стр.347). Определите, какое число нечестных
счетных комиссий может участвовать в протоколе, не нару­
шая его основных семи свойств.
ЧАСТЬ IV


ПРОБЛЕМЫ
СТОЙКОСТИ



Описав основные примитивы криптографии с отрытым ключом, в
которых у нас возникала потребность, покажем теперь, что их недо­
статочно. Слабые места возникают потому, что разработчики при­
емов часто не задумываются о том, как примитивы будут использо­
ваться на практике. Чтобы разобраться в этом, мы сначала выделим
некоторый список возможных атак и попытаемся сформулировать
понятие стойкости по отношению к ним. Анализ ситуации покажет
нам, что основные примитивы действительно не вполне стойки.
Осознав реальное положение дел, обратимся к двум подходам,
позволяющим строить стойкие системы. Первый, основанный на чи­
стой теории сложности, обречен на неудачу, поскольку чистая те­
ория сложности имеет дело с самым плохим случаем, а не со сред­
ними, которые и встречаются на практике. Второй подход, связан­
ный с доказуемой стойкостью, оказывается более подходящим д^ля
практических целей. Он, фактически, имеет высокое влияние на со­
временную криптографию. Последний подход тоже происходит из
теории сложности, но работает со средним, а не с наихудшим слу­
чаем.
ГЛАВА 14
АТАКИ
НА СХЕМЫ
С ОТКРЫТЫМ
КЛЮЧОМ

Цели главы
• Объяснить атаку Винера, основанную на непрерывных дробях.
• Описать алгоритм приведения базиса решетки и показать на
примерах, как его можно использовать для взлома криптогра­
фических систем.
• Рассказать о технике Копперсмита поиска малых корней по­
линомиальных уравнений над кольцами вычетов и ее крипто­
графических приложениях.
• Ввести понятие частичной дискредитации ключа и анализа де­
фектов.


14.1. Введение
Мы опишем несколько атак, направленных на наивную эксплуата­
цию таких криптосистем, как RSA и DSA. Особое внимание будет
уделено технике Копперсмита, основанной на приведении базиса ре­
шетки. Основная цель этой главы — продемонстрировать, что даже
такого криптографического примитива, как односторонняя функ­
ция RSA с секретом
X • х^ (modAT),
недостаточно для построения стойкой системы шифрования. Кри-
птостойкость системы главным образом зависит от способа исполь­
зования этой функции. В следуюп1;их главах мы объясним, как мож­
но разработать стойкую систему шифрования, опирающуюся как
на КЗА-фуякциЮу так и на другую криптографическую технику, с
которой мы уже знакомы.
Глава Ц- Атаки на схемы с открытым ключом

14.2. Атака Винера на RSA
Мы уже отмечали, что в алгоритме RSA для ускорения операций
с открытым ключом используют малые шифрующие экспоненты.
В некоторых же приложениях этой криптосистемы существеннее
ускорить процессы расшифровывания. Поэтому имеет смысл выби­
рать небольшую расшифровывающую экспоненту d. Ясно, что при
этом получается большое значение открытой экспоненты Е. Слиш­
ком маленькое число в качестве секретной экспоненты d мы брать
не можем, поскольку атакующий определит ее простым перебором.
Более того, учитывая изощренную атаку Винера, опирающуюся на
непрерывные дроби, необходимо выбирать d среди чисел, размер
которых не меньше, чем ^N^,
По вещественному числу а G R определим последовательности:
Oio = Oi, po = qo = l^ pi=aoai-\-l, qi = ai,

ai - щ
Pi = aiPi-i +Pi-2 при i ^ 2,
Qi = caqi-i + qi-2 при i ^ 2.
Целые числа ao, ai, a2, . . . называются непрерывной дробью, пред­
ставляющей а, а рациональные числа ^ — подходящими дробями.
Каждая из подходящих дробей несократима, а скорость роста их
знаменателей сравнима с показательной.
Одним из важных результатов теории непрерывных дробей явля­
ется то, что если несократимая дробь | удовлетворяет неравенству:

а ^2^2^

то ^ — одна из подходящих дробей в разложении а в непрерывную
дробь.
Винер предлагает использовать непрерывные дроби при атаке
на RSA следующим образом. Пусть у нас есть модуль N = pq^ при­
чем q < р < 2q. Допустим, что наша расшифровывающая экспонента
удовлетворяет неравенству: d < | А / ' 4 , И нападающему это извест­
но. Кроме того, ему дана шифрующая экспонента Е^ обладающая
свойством
Ed= 1 (mod(/?),
где (р = (p{N) = (р — l){q — 1). Будем также считать, что Е < ср^
поскольку это выполнено в большинстве приложений. Заметим, из

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

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

ОГЛАВЛЕНИЕ

Следующая >>