Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Теперь опишем процедуру, с помощью которой Пикара может убедить Вивалеса в том, что она знает разложение на множители целого числа п = pq, не сообщая ему никакой информации о значениях сомножителей. Мы будем использовать эквивалентность знания р и q возможности извлечения из произвольного числа квадратного корня в арифметике по модулю п = pq (см. упражнение 5 ниже). Процедура имеет следующий вид.
1. Центр вырабатывает случайно целое число х и посылает Пикаре и Вивалесу наименьший неотрицательный вычет из Xі по модулю п; полагаем у = Xі (mod п).
2. Пикара находит четыре квадратных корня из у по модулю п, а именно, ±х, ±г'. Она произвольным образом выбирает из них один;
§ 5. ПРОТОКОЛЫ С НУЛЕВЫМ РАЗГЛАШЕНИЕМ
137
обозначаем его через х0.
3. Пикара выбирает случайно целое число г и посылает Вивалесу число s — г2 (mod п). Она также вычисляет mi = г (mod п) и 77I2 = х0г (mod ті) и посылает эти два сообщения Вивалесу с помощью скрытой передачи.
4. Вивалес может прочитать только одно из этих сообщений. Он проверяет, что квадрат этого числа по модулю п равен s (если его случайное г равно 1) или равен уа (если і = 2).
5. Шаги 1-4 повторяются (с различными открытыми ключами (?i,32)). Если Пикара выдержит T проверок, то Вивалес убедится (с вероятностью ошибки 1-2 ) в том, что Пикара действительно знает это разложение.
УПРАЖНЕНИЯ
1. Рассмотрим процедуру доказательства с нулевым разглашением знания одного дискретного логарифма. Пусть Пикара в действительности не знает значение дискретного логарифма. Какова вероятность того, что она сможет успешно обманывать Вивалеса при Т-кратном повторении шагов 1-3 этой процедуры?
2. Опять рассмотрим процедуру доказательства с нулевым разглашением знания одного дискретного логарифма. Пусть Вивалес не знает величину N.
а) Объяснить, почему описанный в тексте протокол не обладает свойством нулевого разглашения.
б) Как Пикара может уменьшить количество информации о N, поступающей к Вивалесу?
3. Пусть Пикара не знает N и поэтому на шаге 1 выбирает случайное число е. < В, где В — граница для возможного значения N. На шаге 3 она посылает просто число X -f є вместо наименьшего положительного вычета из х + е по модулю N. Объяснить, почему это не будет доказательством с нулевым разглашением? Почему эта процедура, проделанная Клайдом, не будет правильно имитировать поведение Пикары?
4. Объяснить, как можно использовать приведенную в тексте процедуру доказательства с нулевым разглашением знания одного дискретного логарифма в системе электронной идентификации с открытым ключом. (Это означает, что Пикара убеждает Вивалеса в том, что она действительно Пикара.)
5. Объяснить, почему умение извлекать квадратные корни по модулю п = рд по существу эквивалентно знанию разложения числа га на простые множители.
6. Может ли один и тот же открытый ключ (?i,?2) для скрытой передачи использоваться несколькими лицами для представления Вивалесу доказательств с нулевым разглашением того, что они все, независимо друг от друга, знают разложение на простые множители одного и того же числа? Считается, что все они имеют доступ ко всем передаваемым сообщениям.
7. Используя скрытую передачу, построить неинтерактивное доказательство с нулевым разглашением знания дискретного логарифма. (Предполагается, что порядок N группы известен всем.)
8. Недавно была предложена следующая схема протокола с нулевым разглашением, позволяющего Пикаре показать Вивалесу, что она знает делители р и д
138
ГЛ. IV. ОТКРЫТЫЙ ключ
целого числа п, о котором известно, что оно является произведением двух простых чисел, сравнимых с 3 по модулю 4. Найти основной изъян этой схемы.
Шаг 1. Вивалес, который знает п, но не знает р и q, выбирает случайно целое число х. Он вычисляет наименьший неотрицательный вычет числа г4 по модулю п и посылает результат (который мы обозначим через у) Пикаре.
Шаг 2. Получив у, Пикара вычисляет квадратный корень в кольце вычетов по модулю п (что ей нетрудно сделать, так как она знает разложение п, см. упражнение 5 выше). Из четырех возможных квадратных корней она (единственным образом) выбирает тот, который является квадратичным вычетом как по модулю р, так и по модулю q. Это число должно быть наименьшим положительным вычетом из X2 по модулю п. Она посылает его Вивалесу.
Шаг 3. Вивалес проверяет, что полученное число на самом деле является вычетом числа X2 по модулю п. Тем самым он убеждается, что Пикара действительно извлекла квадратный корень по модулю п, что возможно лишь при знании разложения числа п.
9. Найти недостаток следующей процедуры доказательства с нулевым разглашением знания разложения. Пусть п является произведением двух простых р и q. Предположим, что «Центр доверия» вырабатывает бесконечную последовательность г/1,1/2,-¦¦ квадратов случайных чисел (приведенных по модулю га), как это описано в тексте. Поочередно для каждого г/< Пикара находит один из его квадратных корней Xi и посылает его Вивалесу, который проверяет, что х2 = у,- (mod п).
