Доказательство с нулевым знанием для возможности вскрыть RSA

Алиса знает закрытый ключ Кэрол. Может быть она взломала RSA, а может она взломала дверь квартиры Кэрол и выкрала ключ. Алиса хочет убедить Боба, что ей известен ключ Кэрол. Однако она не хочет ни сообщать Бобу ключ, ни даже расшифровать для Боба одно из сообщений Кэрол. Далее приведен протокол с нулевым знанием, с помощью которого Алиса убеждает Боба, что она знает закрытый ключ Кэрол [888]. Пусть открытый ключ Кэрол - e, ее закрытый ключ - d, а модуль RSA - n.

(1) Алиса и Боб выбирают случайное kи m, для которых

kmº e(mod n)

Числа они должны выбирать случайным образом, используя для генерации kпротокол бросания монеты, а затем вычисляя m. Если и k, и mбольше 3, протокол продолжается. В противном случае числа выбираются заново.

(2) Алиса и Боб генерируют случайный шифротекст C. И снова они должны воспользоваться протоколом бросания монеты.

(3) Алиса, используя закрытый ключ Кэрол, вычисляет

M= C^dmod n

Затем она вычисляет

X= M^kmod n

и посылает X Бобу.

(4) Боб проверяет, что X^m mod n= C. Если это так, то он убеждается в правильности заявления Алисы.

Аналогичный протокол можно использовать для демонстрации возможности вскрытия проблемы дискретного логарифма [888].

Доказательство с нулевым знанием того, что n является числом Блюма

Пока неизвестно никаких действительно практичных доказательств того, что n =pq, где p и q- простые числа, конгруэнтные 3 по модулю 4. Однако если nимеет форму p^rq^s, где rи sнечетны, то у числа nсохраняются свойства, которые делают числа Блюма полезными для криптографии. И тогда существует доказательство с нулевым знанием того, что n имеет такую форму.

Предположим, что Алисе известно разложение на множители числа Блюма n, где nобладает рассмотренной выше формой. Вот как она может доказать Бобу, что n имеет такую форму [660].

(1) Алиса посылает Бобу число u, чей символ Якоби равен -1 по модулю n.

(2) Алиса и Боб совместно выбирают случайные биты: b₁, b₂, . . . b_k.

(3) Алиса и Боб совместно выбирают случайные числа: x₁, x₂, . . . x_k.

(4) Для каждого i= 1, 2, . . . k Алиса посылает Бобу квадратный корень по модулю n для одного из четырех чисел: x_i, -x_i, ux_i, - ux_i. Символ Якоби квадратного корня должен быть равен b_i.

Вероятность удачного мошенничества Алисы равна 1/2^k.

Слепые подписи

Понятие слепых подписей (см. раздел 5.3) было придумано Дэвидом Чаумом (David Chaum) [317, 323], который также предложил и первую реализацию этого понятия [318]. Она использует алгоритм RSA.

У Боба есть открытый ключ e, закрытый ключ d и открытый модуль n. Алиса хочет, чтобы Боб вслепую, не читая, подписал сообщение m.

(1) Алиса выбирает случайное число k из диапазона от 1 до n. Затем она маскирует m, вычисляя

t= mk^emod n

(2) Боб подписывает t

t^d= (mk^e)^d mod n

(3) Алиса снимает маскировку с t^d, вычисляя

s= t^d/kmod n

(4) Результатом является

s= m^dmod n

Это можно легко показать

t^d º (mk^e)^d º m^dk (mod n), поэтому t^d/k = m^dk/k º m^d (mod n).

Чаум придумал целое семейство более сложных алгоритмов слепой подписи [320, 324], называемых неожиданными слепыми подписями. Схемы этих подписей сложнее, но они дают больше возможностей.