Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
На первый взгляд, эти требования производят странное впечатление. Однако такой канал оказывается одним из фундаментальных понятий криптографии. Скоро мы увидим, как с его помощью строится неинтерактивное (т.е. без взаимодействия сторон) доказательство с нулевым разглашением. Но сначала мы опишем способ построения такого канала, использующий сложность решения задачи дискретного логарифмирования.
Точнее, пусть имеются такие большое конечное поле F9 и фиксированный элемент b мультипликативной группы F9, что не существует практически реализуемого способа вычисления Ьху по значениям Ьх и Ьу. Это — условие Диффи-Хеллмана, и считают, что оно выполняется, если задача дискретного логарифмирования в F9 трудноразрешима
Пусть, далее, существует легко вычислимое (и легко обратимое) отображение ф нашего конечного поля в n-мерное векторное пространство F2 над полем F2. Пусть образ F9 при этом отображении содержит все элементы F2 1 (т.е. все векторы, заканчивающиеся нулем). Например, если q взаимно просто с р, то можно определить п условием 2" < р < 2™ ихотображать элемент F9 (например, неотрицательное
целое, меньшее р) в отвечающую ему последовательность двоичных знаков. —У
Пусть элементами сообщения являются наборы по п бит, т. е.элементы т Є F2. Наконец, зафиксируем раз и навсегда некоторый эле-
(см. § 3).
§ 5. ПРОТОКОЛЫ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ
135
мент CeF*, выбранный так, чтобы никто не знал его дискретного логарифма. (Напомним, что по предположению задача дискретного логарифмирования трудноразрешима в F*.) Элемент С может быть предложен «Центром доверия» (т.е. специальным посредником, которому доверяют обе стороны) или выбран с помощью случайной или интерактивной процедуры с участием Пикары и Вивалеса.
Скрытая передача происходит следующим образом. Вивалес выбирает случайно целое число х,0 < х < q — 1,и элемент і Є {1,2}. Далее символы х и г будут обозначать фиксированные целые числа из множеств {l,...,q— 2} и {1,2} соответственно. Вивалес полагает ?i = Ьх и /Зз_^ = С/Ьх. Он объявляет своим открытым ключом пару {.?ii?i) и сохраняет секретными величины х и г. Заметим, что Вивалес не может знать дискретный логарифм /?-,-, который мы обозначим через X : если бы он его знал, то он мог бы вычислить дискретный логарифм С = ?i?z-i, что противоречит нашим предположениям.
Пусть у Пикары имеется два элемента текста: Tn1 Є F2 из первого пакета и т2 Є F2 из второго пакета. Она выбирает случайно два целых числа 0 < у%,у2 < q — 1и посылает Вивалесу две пары элементов: bVl, ЬУ2 Є F* и q1 = Tn1 + ^(?l1), а2 = т2 + V(^22) Є (сложение производится в п-мерном векторном пространстве F2; такая операция известна как «исключающее или»). Пикара оставляет у і и у2 секретными.
Поскольку ?\' = (by')x и Вивалес знает числа Ьу' их, он может легко найти ip(?y'), а следовательно, и тп; = а і + ф^у'). Однако, если бы он захотел найти т^-і, то ему пришлось бы найти величину
/Зд!"' = Ьх Уз~', зная лишь ЬУз~' и Ьх и не зная ни уз-і, ни х . Поэтому (в силу условия Диффи-Хеллмана) найти тп3_; он не может.
Заметим, что Пикара может легко проверить, что ?\?% = С и, следовательно, убедиться, что Вивалес не знает дискретных логарифмов сразу обоих элементов своего открытого ключа (?\,?2). Так как в интересах Вивалеса иметь всю возможную информацию, Пикара может быть уверена в том, что дискретный логарифм одного из элементов этой пары он знает. Но у Пикары нет возможности различить /J1 и ?2, чтобы узнать, какое из них Вивалес получил как Ьх, а какое — как C/bx. Значит, как для Вивалеса, так и для Пикары условия 1 и 2 выполнены.
Если один ключ ?i и ?2 (т. е. одни и те же а; и г) используется для последовательности пар (m1?m2), то Пикара знает, что дешифрованные Вивалесом элементы ті занимают в парах Tn15Tn2 одинаковые места. Если требуется, чтобы новая последовательность элементов была послана независимым (от предыдущей) образом, то Вивалес должен
136
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
выбрать случайно новые величины жиги послать новый открытый
КЛЮЧ ?i и ?2 ¦
Использование скрытой передачи для неинтерактивного доказательства того, что разложение на множители известно.
Смысл слова «неинтерактивное» можно представить диаграммой
Центр
/ \
Пикара —> Вивалес
Здесь «Центр доверия» можно понимать как источник случайных битов, посылаемых одновременно Пикаре и Вивалесу (Центр может перед рассылкой производить над битами какие-нибудь арифметические операции). Комбинация этих битов и реакция на них Пикары (сообщение, посланное ею Вивалесу) должны быть достаточны для того, чтобы Вивалес поверил, что она на самом деле сделала то, о чем сообщает (т. е. чтобы вероятность того, что Вивалеса обманули, была экспоненциально мала).
Под «неинтерактивностью» понимается то, что в процессе проверки Вивалес не переписывается с Пикарой. Однако допускается, чтобы в самом начале процедуры Пикара получила длинную последовательность открытых ключей скрытой передачи (?\,?2) для Вивалеса, описанных выше. Это не рассматривается как переписка Вивалеса с Пикарой. Фактически, теми же самыми открытыми ключами (в соответствии со смыслом термина «открытый») может пользоваться каждый, кто захочет играть роль Пикары. И Пикара может использовать одну и ту же последовательность открытых ключей во многих различных доказательствах с нулевым разглашением, которые она направляет Вивалесу.
