3. Разложение на множители: Если N - произведение двух простых чисел, то лиьо

(a)разложить N на множители,

(b)для заданных целых чисел M и C найти d, для которого Md = C (mod N),

(c)для заданных целых чисел e и C найти M, для которого M = C (mod N),

(d)для заданного целого числа x определить, существует ли целое число y, для которого x = y2 (mod N).

Согласно Диффи [492, 494], проблема дискретных логарифмов была предложена Дж. Гиллом (J. Gill), проблема разложения на множители - Кнутом , а проблема рюкзака - самим Диффи.

Эта узость математических основ криптографии с открытыми ключами немного беспокоит . Прорыв в решении либо проблемы дискретных логарифмов, либо проблемы разложения на множители сделает небезопасными целые классы алгоритмов с открытыми ключами. Диффи показал [492, 494], что подобный риск смягчается двумя факторами:

1.Все операции, на которые сейчас опирается криптография с открытыми ключами - умножение, возведение в степень и разложение на множители - представляют собой фундаментальные арифметические явления . Веками они были предметом интенсивного математического изучения, и рост внимания к ним, вызванный применением в криптосистемах с открытыми ключами, увеличил, а не уменьшил н аше доверие.

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

Как мы уже видели, не все алгоритмы с открытыми ключами, основанные на этих проблемах, безопасны . Сила любого алгоритма с открытым ключом зависит не только от вычислительной сложности проблемы, леж а-щей в основе алгоритма. Трудная проблема необязательно реализуется в сильном алгоритме . Ади Шамир объясняет это тремя причинами [1415]:

1.Теория сложности обычно связана с отдельными частными случаями проблемы. Криптоаналитик же часто получает большой набор статистически связанных проблем - различные шифротексты, заши ф-рованные одним и тем же ключом.

2.Вычислительная сложность проблемы обычно измеряется для худшего или среднего случаев . Чтобы быть эффективной в качестве способа шифрования, проблема должна быть трудной для решения по чти во всех случаях.

3.Произвольную сложную проблему необязательно можно преобразовать в криптосистему, к тому же проблема должна позволить встроить в нее лазейку, знание которой и только оно делает возможным простое решение проблемы.

Глава 21

Схемы идентификации

21.1 FEIGE-FIAT-SHAMIR

Схема цифровой подписи и проверки подлинности, разработанная Амосом Фиатом (Amos Fiat) и Ади Ша-миром (Adi Shamir), рассматривается в [566, 567]. Уриель Фейге (Uriel Feige), Фиат и Шамир модифицировали алгоритм, превратив его в доказательство подлинности с нулевым знанием [544, 545]. Это лучшее доказательство подлинности с нулевым знанием.

9 июля 1986 года три автора подали заявку на получение патента США [1427]. Из-за возможного военного применения заявка была рассмотрена военными. Время от времени результатом работы Патентное бюро явл я-ется не выдача патента, а нечто, называемое секретным распоряжением . 6 января 1987 года, за три дня до истечения шестимесячного периода, по просьбе армии Патентное бюро издало такое распоряжение . Заявило, что " . . . раскрытие или публикация предмета заявки . . . может причинить ущерб национальной безопасности . . ." Авторам было приказано уведомить всех граждан США, которые по тем или иным причинам узнали о пров о-димых исследованиях, что несанкционированное раскрытие информации может закончиться двумя годами т ю-ремного заключения, штрафом $10,000 или тем и другим одновременно. Более того, авторы должны были сообщить Уполномоченному по патентам и торговым знакам обо всех иностранных гражданах, которые получили доступ к этой информации.

Это было нелепо. В течение второй половины 1986 года авторы представляли свою работу на конференциях в Израиле, Европе и Соединенных Штатах. Они даже не были американским гражданами, и вся работа была выполнена в Институте Вейцмана (Weizmann) в Израиле.

Слухи об этом стали распространяться в научном сообществе и прессе . В течение двух дней секретное распоряжение было аннулировано. Шамир и его коллеги считают, что за отменой секретного распоряжения стояло NSA, хотя никаких официальных комментариев не было. Дальнейшие подробности этой причудливой истории приведены в [936].

Упрощенная схема идентификации Feige-Fiat-Shamir

Перед выдачей любых закрытых ключей арбитр выбирает случайный модуль , n, который является произведением двух больших простых чисел. В реальной жизни длина n должна быть не меньше 512 битов и лучше как можно ближе к 1024 битам. n может общим для группы контролеров. (Использование чисел Блюма (Blum) облегчит вычисления, но не является обязательным для безопасности .)

Для генерации открытого и закрытого ключей Пегги доверенный арбитр выбирает число v, являющееся квадратичным остатком mod n. Другими словами выбирается v так, чтобы уравнение x = v (mod n) имело решение, и существовало v-1 mod n. Это v и будет открытым ключом Пегги. Затем вычисляется наименьшее s, для которого s = sqrt (v-1) (mod n). Это будет закрытый ключ Пегги. Используется следующий протокол идентификации.

(1)Пегги выбирает случайное r, меньшее n. Затем она вычисляет x =-r2 mod n и посылает x Виктору.

(2)Виктор посылает Пегги случайный бит b.

(3)Если b = 0, то Пегги посылает Виктору r. Если b = 1, то Пегги посылает Виктору y = r*s mod n.

(4)Если b = 0, Виктор проверяет, что x = -r2 mod n, убеждаясь, что Пегги знает значение sqrt(x). Если b = 1, Виктор проверяет, что x = y2*v mod n, убеждаясь, что Пегги знает значение sqrt(v-1).

Это один этап протокола, называемый аккредитацией. Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s. Это протокол "разрезать и выбрать". Если Пегги не знает s, она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 0, или она может подобрать r так, что она сможет обмануть Виктора, если он пошлет ей 1 . Она не может сделать одновременно и то, и другое. Вероятность, что ей удастся обмануть Виктора один раз, равна 50 процентам . Вероятность, что ей удастся обмануть его t раз, равна 1/2t.

Виктор может попробовать вскрыть протокол, выдавая себя за Пегги . Он может начать выполнение протокола с с другим контролером, Валерией. На шаге (1) вместо выбора случайного r ему останется просто использовать значение r, которое Пегги использовало в прошлый раз . Однако, вероятность того, что Валерия на шаге (2) выберет то же значение b, которое Виктор использовал в протоколе с Пегги, равна 1/2 . Следовательно, вероятность, что он обманет Валерию, равна 50 процентам . Вероятность, что ему удастся обмануть ее t раз, равна 1/2t.

Чтобы этот протокол работал, Пегги никогда не должна использовать r повторно. В противном случае, если Виктор на шаге (2) пошлет Пегги другой случайный бит, то он получит оба ответа Пегги . Тогда даже по одному из них он сможет вычислить s, и для Пегги все закончится.

Схема идентификации Feige-Fiat-Shamir

В своих работах [544, 545], Фейге, Фиат и Шамир показали, как параллельная схема может повысить число аккредитаций на этап и уменьшить взаимодействия Пегги и Виктора .

Сначала, как и в предыдущем примере, генерируется n, произведение двух больших простых чисел. Для генерации открытого и закрытого ключей Пегги сначала выбирается k различных чисел: vi, v2, . . . vk, где каждое vj является квадратичным остатком mod n. Иными словами, vj выбираются так, чтобы x2 = vj (mod n) имело решение, и существовало v,-1 mod n. Строка, v1, v2, . . . vk, служит открытым ключом. Затем вычисляются наименьшие для которых sj = sqrt (v,-1) (mod n). Строка s1, s2, . . . sk, служит закрытым ключом.

Выполняется следующий протокол:

(1)Пегги выбирает случайное r, меньшее n. Затем она вычисляет x =-r2 mod n и посылает x Виктору.

(2)Виктор посылает Пегги строку из k случайных битов: b1, b2, . . . bk.

(3)Пегги вычисляет y = r *(s1b1 *s2b2*...*skbk )mod n. (Она перемножает вместе значения sj, соответствующие b;=1. Если первым битом Виктора будет 1, то si войдет в произведение, а если первым битом будет 0, то нет, и т.д.) Она посылает y Виктору.

(4)Виктор проверяет, что x = y2*( v1b1 * v2b2 *. *vkbk) mod n. (Он перемножает вместе значения vb основываясь га случайной двоичной строке. Если его первым битом является 1, то v1 войдет в произведение, а если первым битом будет 0, то нет, и т.д.)

Пегги и Виктор повторяют этот протокол t раз, пока Виктор не убедится, что Пегги знает s1, s2, . . . sk.

Вероятность, что Пегги удастся обмануть Виктор t раз, равна 1/2kt. Авторы рекомендуют использовать вероятность мошенничества 1/220 и предлагают значения k = 5 и t = 4. Если у вас склонность к мании преследования, увеличьте эти значения.

Взглянем на работу этого протокола небольших числах. Если n = 35 (два простых числа - 5 и 7), то возможными квадратичными остатками являются :

1: x2 = 1 (mod 35) имеет решения: x = 1, 6, 29, 34.

4: x2 = 4 (mod 35) имеет решения: x = 2, 12, 23, 33.

9: x2 = 9 (mod 35) имеет решения: x = 3, 17, 18, 32.

11: x2 = 11 (mod 35) имеет решения: x = 9, 16, 19, 26.

14: x2 = 14 (mod 35) имеет решения: x = 7, 28.

15: x2 = 15 (mod 35) имеет решения: x = 15, 20.

16: x2 = 16 (mod 35) имеет решения: x = 4, 11, 24, 31.

21: x2 = 21 (mod 35) имеет решения: x = 14, 21.

25: x2 = 25 (mod 35) имеет решения: x = 5, 30.

29: x2 = 29 (mod 35) имеет решения: x = 8, 13, 22, 27.

30: x2 = 30 (mod 35) имеет решения: x = 10, 25.

Обратными значениями (mod 35) и их квадратными корнями являются: vv-1s=sqrt(v-1)

493 942