В статье Zero-Knowledge Proofs of Identity (авторами Feige, Fiat и Shamir) описан протокол ZK, который использует квадратичные остатки. В разделе 3 описывается «Эффективная схема идентификации», но (насколько я понимаю) алгоритм ПК кажется сломанным (в смысле «не работает», а не в терминах «плохой безопасности»).
Протокол генерации ключа (шаги 1-3 цитируются из документа с использованием тех же обозначений, что и в документе):
Настройка: Пусть $n$ — целое число Блюма (произведение двух простых чисел, $р$ и $q$, где оба $р$ и $q$ конгруэнтны 3 по модулю 4). Позволять $Z_n$ обозначим кольцо вычетов при операции mod.
- выберите $к$ случайные числа $S_1, ..., S_k$ в $Z_n$.
- Выберите каждый $I_j$ (случайно и независимо) как $\pm 1 / S_j^2$ (мод. н).
- Публиковать $I = I_1, ..., I_k$ и хранить $S = S_1, ..., S_k$ секрет.
Без обозначения, чтобы получить открытый ключ, нам нужно вычислить квадрат каждого секрета. $S_j$ а затем найти либо модулярную инверсию этого квадрата, либо $(n-1)$ раз это обратное. (т.е. $S_j^2 \cdot I_j = 1 (\text{mod}n)$ или же $S_j^2 \cdot I_j = -1 (\text{mod}n)$).
Проблема в том, что на шаге 2 $Z_n$ не является полем, что означает, что $I_j$ не гарантируется существование. А именно, любой $г \in Z_n$ не будет иметь обратного, если либо $р | г$ или же $q | г$. Для очень большого $n$ это маловероятно, но легко доказать, что это происходит всегда.
Доказательство существования: без ограничения общности пусть $р < д$. затем $p^2 \в Z_n$. Так как $\text{gcd}(p^2, n) = p > 1$, Мы видим, что $р^2$ не имеет обратного в $Z_n$.
Маленький пример: когда $n = 21$, ни один из членов этого множества не имеет обратного в $Z_n$ $\{0, 3, 6, 7, 9, 12, 14, 15, 18\}$. Некоторые из них являются действительными кандидатами на то, чтобы привести к невозможному $I_j$ (как указано выше, $S_j = 3$ тогда $S^2_j = 9$).
Что вы должны делать, если вы получите один из этих «сломанных» номеров? Рисовать снова? Для больших $n$ вероятность мала (легко подсчитать количество "битых" чисел в $Z_n$ как $1 + (p-1) + (q-1) = p+q-1$, который исчезает в $pq$ для больших $р$ и $q$), но, по крайней мере, в тестовых реализациях с небольшим $n$ (нравиться $n = 21$) он ломает любой код, пытающийся получить это обратное.
