În lucrarea Zero-Knowledge Proofs of Identity (de Feige, Fiat și Shamir) este descris un protocol ZK care folosește reziduurile pătratice. Secțiunea 3 descrie o „schemă de identificare eficientă”, dar (după înțelegerea mea) algoritmul PK pare a fi stricat (în sensul „nu funcționează”, nu în termeni de „securitate slabă”).
Protocolul de generare a cheilor este (pașii 1-3 sunt citați din lucrare, folosind aceeași notație ca și lucrarea):
Configurare: Lasă $n$ să fie un întreg Blum (produsul a două numere prime, $p$ și $q$, unde ambele $p$ și $q$ sunt congruente cu 3 mod 4). Lăsa $Z_n$ denotă inelul de reziduuri sub operațiunea mod.
- Alege $k$ numere aleatorii $S_1, ..., S_k$ în $Z_n$.
- Alegeți fiecare $I_j$ (aleatoriu și independent) ca $\pm 1 / S_j^2$ (mod n).
- Publica $I = I_1, ..., I_k$ și păstrează $S = S_1, ..., S_k$ secret.
Fără notație, pentru a obține cheia publică trebuie să calculăm pătratul fiecărui secret $S_j$ și apoi găsiți fie inversul modular al acestui pătrat, fie $(n-1)$ ori acest invers. (I.E. $S_j^2 \cdot I_j = 1 (\text{mod}n)$ sau $S_j^2 \cdot I_j = -1 (\text{mod}n)$).
Problema este că la pasul 2, $Z_n$ nu este un domeniu ceea ce înseamnă că $I_j$ nu este garantat existența. Și anume orice $g \în Z_n$ nu va avea invers dacă nici unul $p | g$ sau $q | g$. Pentru un foarte mare $n$ Este puțin probabil să se întâmple acest lucru, dar este ușor de demonstrat că se întâmplă întotdeauna.
Dovada existenței: fără pierderea generalității, lit $p < q$. Atunci $p^2 \în Z_n$. pentru că $\text{gcd}(p^2, n) = p > 1$, noi vedem asta $p^2$ nu are invers în $Z_n$.
Mic exemplu: când $n = 21$, niciunul dintre membrii acestui set nu are invers în $Z_n$ $\{0, 3, 6, 7, 9, 12, 14, 15, 18\}$. Unii dintre ei sunt candidați validi pentru a avea ca rezultat un imposibil $I_j$ (ca mai sus, este $S_j = 3$ atunci $S^2_j = 9$).
Ce ar trebui să faci dacă primești unul dintre aceste numere „spărțite”? Să desenezi din nou? Pentru mari $n$ probabilitatea este mică (este ușor să calculezi numărul de numere „despărțite” în $Z_n$ la fel de $1 + (p-1) + (q-1) = p+q-1$, care dispare în $pq$ pentru mari $p$ și $q$) dar cel puțin în implementările de testare cu mici $n$ (ca $n = 21$) rupe orice cod încercând să obțină acel invers.
