Cheie publică RSA cu cunoștințe zero

Să presupunem că Bob are $k>1$ chei publice RSA $(e_i, n_i)$ fără nicio cunoaștere a cheilor private corespunzătoare. Alice are, de asemenea, toate cheile publice, dar are și o cheie privată doar pentru una dintre ele, să zicem, $(d_j, n_j)$. Este posibil ca ea să-i demonstreze lui Bob că are cel puțin una dintre cheile private, fără să dezvăluie $j$

EDITARE: notația schimbată conform sugestiilor fgrieu

Iată o propunere (din capul meu). Imagine de ansamblu

• Bob trage o aleatorie $X$, și îl trimite criptat determinist sub fiecare cheie publică
• Alice descifrează $X$ cu cheia publică pe care o deține
• Alice verifică că Bob a făcut cum era de așteptat, având în vedere asta $X$
• dezvăluie Alice $X$ lui Bob

Mai precis:

• Definiți a 8 miliarde de dolari-bit hash (să zicem SHA-512) astfel încât $\min(n_i)>2^{16b}$
• Definiți o funcție de generare a măștilor (cum ar fi MGF1 cu acel hash) astfel încât pentru bytestring $X$, $\operatorname{MGF}(X,\ell)$ este o $\ell$-byte hash de $X$
• Definiți lungimile octeților $\ell_i=\left\lfloor\log_2(n_i)/8\right\rfloor$, care sunt astfel încât $2^{8\ell_i}<n_i<2^{8\ell_i+8}$ (pentru a evita atacurile de sincronizare, este de dorit ca $n_i$ au aceeași dimensiune a biților, deci $l_i$ egal)
• Bob trage o aleatorie $X\în\{0,1\}^{8b}$ (A $b$-byte șir de octeți)
• Pentru fiecare $i$, Bob
  • calculează $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$
  • calculează $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (un $l_i$-byte șir de octeți)
  • calculează și ieșire $C_i={X_i}^{e_i}\bmod n_i$
• Alice primește $C_i$, inclusiv $C_j$
• Alice calculează $f={C_j}^{d_j}\bmod n_j$
• exprimă Alice $f$ ca șir de octeți $M\mathbin\|G$ cu $M$ de $l_i-b$ octeți și $G$ de $b$ octeți.
• Alice își revine $X$ prin calcul $X=G\oplus H(M\mathbin\|J)$
• Pentru fiecare $i$, Alice
  • calculează $M_i=\operatorname{MGF}\bigl(X\mathbin\|H(n_i),l_i-b\bigr)$, Unde $I$ este index $i$ ca șir de octeți.
  • calculează $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|H(n_i)))$ (un $l_i$-byte șir de octeți)
  • verificări ${X_i}^{e_i}\bmod n_i=C_i$ (când $i=j$, acest lucru verifică $M=\operatorname{MGF}\bigl(X\mathbin\|H(n_j),l_j-b\bigr)$ ca efect secundar)
• Doar dacă toate verificările au trecut și fără a dezvălui (de exemplu, prin sincronizare) unde a apărut o eroare, dacă este cazul, sau care $X_i$ a fost folosit pentru a se recupera $X$
  • dezvăluie Alice $X$
• Bob verifică că Alice a dezvăluit dreptul $X$

Motivație:

• Alice demonstrează că poate descifra una dintre criptograme $C_i$, astfel încât ea deține o cheie privată
• Ea nu dezvăluie care, deoarece a verificat că toate criptogramele se potrivesc la fel $X$. Nu există niciun risc ca biții de ordin înalt într-o anumită cantitate în $[0,n_j)$ poate oferi un avantaj în ghicire $j$ (cum ar putea fi cazul într-o implementare naivă a celălalt răspuns).
• Reprezentanți $X_i$ de $X$ sunt răspândite $[0,n_i)$ ca în RSASSA-OAEP, cu funcții de umplutură independente. Observați că criptarea directă $X_i=X$, sau $X_i=F(X)$ pentru ceva injecție fixă $F$, ar lăsa sistemul vulnerabil la Atacul transmis de HÃ¥stad; în plus, ar putea fi imposibil să se definească o lățime comună sigură pentru $X_i$, de exemplu. dacă $n_0$ este de 2048 de biți, $n_1$ 8192 de biți, $e_1=3$; căptușeala rezolvă asta.
• De cand $X$ este o provocare trasă de Bob, protocolul este imun la reluare: Alice nu poate scăpa de datele pe care le-a precalculat înainte de a pierde accesul la cheia ei privată sau de datele calculate anterior de Amanda, care deține și o cheie privată.

Posibile îmbunătățiri pentru a-l proteja pe Alice să nu devină un oracol de decriptare, Bob să-și modifice $X$, și poate face o dovadă mai ușoară:

• Alice desenează mai întâi $b$-octet $Y$ și trimite un angajament $H(Y\mathbin\|S_0)$
• Bob îl desenează $b$-octet $X$ și trimite un angajament $H(X\mathbin\|S_1)$
• dezvăluie Alice $Y$, Bob îl verifică $H(Y\mathbin\|0)$
• protocolul de mai sus este modificat
  • este folosit $M_i=\nume operator{MGF}\bigl(X\mathbin\|Y\mathbin\|H(n_i),l_i-b\bigr)$
  • este folosit $X_i=M_i\mathbin\|(X\oplus H(M_i\mathbin\|Y\mathbin\|H(n_i)))$
  • Alice verifică în continuare $H(X\mathbin\|1)$ chibrituri
  • dezvăluie Alice $H(X\mathbin\|S_2)$ Decat $X$
  • Bob verifică asta. (unde $S_i$ sunt șiruri de octeți scurte, nevide, arbitrare distincte)

Actualizare: O altă metodă, prezentată în acest alt răspuns, este de a folosi un Semnătură de inel bazată pe RSA, și fă-o pe Alice să-i demonstreze lui Bob capacitatea ei de a semna un mesaj de provocare.