Пока неизвестно никаких действительно практичных доказательств того, что п =pq, где р и q - простые числа, конгруэнтные 3 по модулю 4. Однако если п имеет форму/?1,где г и s нечетны, то у числа п сохраняются свойства, которые делают числа Блюма полезными для криптографии . И тогда существует доказательство с нулевым знанием того, что п имеет такую форму.
Предположим, что Алисе известно разложение на множители числа Блюма и, где п обладает рассмотренной выше формой. Вот как она может доказать Бобу, что п имеет такую форму [660].
(1) Алиса посылает Бобу число и, чей символ Якоби равен -1 по модулю п.
(2) Алиса и Боб совместно выбирают случайные биты: Ьи Ъ2, . . . Ък.
(3) Алиса и Боб совместно выбирают случайные числа: хь х2, . . . Ху
(4) Для каждого i = 1, 2, . . . к Алиса посылает Бобу квадратный корень по модулю п для одного из четырех чисел: х„ -х„ их,, - их,. Символ Якоби квадратного корня должен быть равен &,.
Вероятность удачного мошенничества Алисы равна 1/2*
23.12 Слепые подписи
Понятие слепых подписей (см. раздел 5.3) было придумано Дэвидом Чаумом (David Chaum) [317, 323], который также предложил и первую реализацию этого понятия [318]. Она использует алгоритм RSA.
У Боба есть открытый ключ е, закрытый ключ d и открытый модуль п. Алиса хочет, чтобы Боб вслепую, не читая, подписал сообщение от.
(1) Алиса выбирает случайное число к из диапазона от 1 до п. Затем она маскирует от, вычисляя t = mke mod n
(2) Боб подписывает t td = (mke)d mod n
(3) Алиса снимает маскировку с t , вычисляя
s = td/k mod n (4) Результатом является s = md mod n Это можно легко показать