Parametrii domeniului în schema de identificare Schnorr

Am studiat recent schema de identificare Schnorr. Cartea Cryptography: Theory and Practice de Stinson și Paterson afirmă următoarele despre parametrii de domeniu din schema de identificare Schnorr:

Schema necesită o autoritate de încredere, sau AT, care alege unii parametri comuni ai sistemului (parametri de domeniu) pentru schemă, după cum urmează:

1. $p$ este un prim mare (adică $p\aproximativ 2^{2048}$).

2. $q$ este un mare divizor prim al $p-1$ (adică $q\aproximativ 2^{224}$).

3. $\alpha \in \mathbb{Z}_p^*$ are ordine $q$

4. $t$ este un parametru de securitate astfel încât $q>2^t$. (Un parametru de securitate este un parametru a cărui valoare poate fi aleasă pentru a oferi un nivel dorit de securitate într-o schemă dată. Aici, probabilitatea adversarului de a-l înșela pe Alice sau Bob este $2^{-t}$, asa de $t=80$ va oferi securitate adecvată pentru majoritatea aplicațiilor practice.)

Întrebarea mea este cum putem găsi așa ceva $p$, $q$, $\alpha$ și $t$? Și de ce trebuie să fie $p\aproximativ 2^{2048}$, $q\aproximativ 2^{224}$ și $t=80$?

Vom avea nevoie de un test de primalitate eficient pentru a produce $p$ și $q$. Dacă sunteți mulțumit de numerele prime probabile, atunci Miller-Rabin testul va fi suficient pentru majoritatea scopurilor practice.Scrieți IsPrime() pentru test.

În primul rând alege $t$ conform cerințelor de securitate ale schemei dumneavoastră. Există o șansă de $2^{-t}$ că un înșelător poate submina schema la întâmplare, deci o alegere $t=80$ înseamnă că, chiar dacă atacatorul dvs. a încercat să vă falsifice sistemul la întâmplare $2^{80}$ ori ar reuși în medie o singură dată. Permiterea unui adversar $2^{80}$ Este puțin probabil ca încercările de a vă falsifica sistemul să fie o propunere realistă, deci $t=80$ este considerat bine în acest sens.

Acum găsim $q$, ar trebui să fie suficient de mare încât un adversar să nu poată rezolva logaritmi discreti într-un grup arbitrar de $q$ elemente (de exemplu, folosind pas de bebeluș pas de gigant metoda) și, de asemenea, mai mare $2^t$. Dacă $q\aproximativ 2^{224}$ apoi aproximativ $2^{112}$ operaţiile de grup ar fi cerute de metodă şi cel puţin aşa $2^{112}$ operațiunile de calcul ar fi necesare pentru BS-GS. Pentru a găsi 224 de biți $q$ generați un număr aleatoriu de 223 de biți $n$ si lasa $q_0=2^{223}+n$. Calculează IsPrime($q_0$) iar dacă are succes lasă $q=q_0$ în caz contrar se incrementează $q_0$ cu 1 si repetam pana avem succes.

Acum găsim $p$, ar trebui să fie suficient de mare încât un adversar să nu poată rezolva logaritmi discreti modulo $p$ (de exemplu, folosind sita câmp numeric). Dacă $p\aproximativ 2^{2048}$ Ghidurile NIST sugerează cel puțin asta $2^{112}$ ar fi necesare operații de calcul. Pentru a găsi 2048 de biți $p$, generați un număr aleatoriu de 1824 de biți $m$ si lasa $p_0=q(2^{1824}+m)$. Calculează IsPrime($p_0$) iar dacă are succes lasă $p=p_0$ în caz contrar se incrementează $p_0$ de $q$ si repetam pana avem succes.

Acum găsim $\alpha$. Lăsa $r=(p-1)/q$ Rețineți că $r$ este un număr întreg. Începe cu $g=2$. Calcula $\alpha_0\equiv g^r\pmod p$, dacă $\alpha_0\not\equiv 1\pmod p$ lua $\alpha=\alpha_0$, în caz contrar, crește $g$ cu 1 și repetați până la succes.

Parametrii sunt aleși pentru a oferi 112 biți de securitate computațională clasică, alți parametri ar oferi niveluri diferite de securitate, de ex. $q\aproximativ 2^{160}$ și $p\aproximativ 2^{1024}$ ar oferi aproximativ 80 de biți de securitate computațională clasică și $q\aproximativ 2^{256}$ și $p\aproximativ 2^{3072}$ ar oferi aproximativ 128 de biți de securitate computațională clasică.