Din capul meu, propun această variație EC-ElGamal pe o curbă eliptică standard de 256 de biți, folosind hash și XOR pentru partea de criptare (aproape înjumătățind dimensiunea textului cifrat față de manualul EC-ElGamal) și un schimb simplu de lucru/spațiu -off pentru a stoarce în continuare un mesaj într-un text cifrat de 32 de octeți $m$ de $b$ biți, cu mici fixe $b$ (de exemplu. $b=8$).
- Utilizați o curbă eliptică standard peste câmp $\mathbb F_p$ cu generator $G$ de ordine $n$, cu $p$ și $n$ Prime de 256 de biți și (conjecturat) securitate de 128 de biți. secp256r1 (alias NIST P-256) și secp256k1 califica. ma refer la Sec1v2 pentru matematică și notație ECC.
- Generare cheie:
- Alegeți cheia privată $d$ aleatoriu în interval $[1,n)$
- Calculați cheia publică $Q\obține d\,G$
- Criptarea $b$-bit text simplu $m$
- Alege $e$ aleatoriu în interval $[1,2^{32})$
- Calcula $F\obține e\,G$
- Alege $k$ aleatoriu în interval $[1,n)$
- Calcula $R\obține k\,G$
- In timp ce $R_x\not\equiv0\pmod{2^b}$
- Calcula $R\obține R+F$ și $k\obține k+e$, care mentine $R=k\,G$
- Dacă $k\ge n$ RNG-ul care a ales $k$ este cel mai probabil rupt; anulați sau reporniți criptarea
- Dacă $R_y$ este ciudat, stabilit $R_y\obține p-R_y$ și $k\ obține n-k$, care mentine $R=k\,G$
- Calcula $S\obține k\,Q$ (punctul secret comun)
- Calcula $u\obține \operatorname{SHA-256}(S_x)\bmod2^b$, Unde $S_x$ este exprimat ca un șir de octeți de 32 de octeți
- Calcula $v\gets u\oplus m$
- Text cifrat de ieșire de 256 de biți, constând din 256 $-b$ biţi pentru $R_x$ cu ordinul inferior $b$ biți eliminați (sunt zero prin construcție) și $b$ biţi pentru $v$
- Decriptare:
- Din extrasul de text cifrat $R_x$ (inserând $b$ biţi de ordin inferior la zero) şi $v$
- Calculați an $R_y$ potrivire $R_x$ (aceasta este o tehnică standard pentru a anula compresia punctului, vezi Sec1v2 §2.3.4, pasul 2.4.1); dacă nu reușește, anulați decriptarea.
- Dacă $R_y$ este ciudat, stabilit $R_y\obține p-R_y$
- Calcula $S\obține d\,R$ (punctul secret comun)
- Calcula $u\obține \operatorname{SHA-256}(S_x)\bmod2^b$, Unde $S_x$ este exprimat ca un șir de octeți de 32 de octeți
- Calculați și scoateți textul simplu descifrat $m\gets u\oplus v$
presupun IND-CCA1 (prin urmare IND-CPA) securitate la nivel de 128 de biți, în ipoteze plauzibile (duritatea unei variante a problemei decizionale Diffie-Hellman pentru curba eliptică și SHA-256 modelat ca un oracol aleatoriu). Există un atac banal împotriva IND-CCA2 (deci accesul la un oracol de decriptare compromite confidențialitatea mesajelor trecute chiar dacă oracolul de decriptare a trecut pe lista neagră textele cifrate originale; aceasta nu este o problemă în practică).
Atenție că cifrul este trivial maleabil. Acest lucru permite unui adversar să răstoarne biții doriti în textul simplu, modificând acești biți în textul cifrat. Aceasta poate fi o problemă practică. Un anumit nivel de atenuare a acestuia este posibil prin înlocuire $u\oplus\ldots$ de Format Păstrarea criptării cu o mai lată $u$ ca cheie; sau/și mai multă muncă sau/și spațiu.
Bucla while la criptare este un compromis timp/spațiu, căutare $k$ prin enumerare astfel încât să fie $x$ coordona $R_x$ are $b$ biți de ordin inferior la zero care nu trebuie transmisi. Căutarea este optimizată pentru a solicita $\aproximativ2^b$ adaosuri de puncte, dar pentru $b$ începând cu aproximativ $8$ asta va deveni o durere. Utilizarea incrementului secret $e$ si potrivire $F=e\,G$ este o finală plăcută $k$ mai uniform (vezi nota), dar nu cunosc nici un atac dacă luăm $e=1$ și, astfel $F=G$. Creșterea secretă în continuare ar putea ajuta la atenuarea atacurilor pe canale laterale.
Dacă vrem să evităm o parte sau tot acest compromis timp/spațiu, putem
- trivial, măriți dimensiunea textului cifrat.
- sau/și aventurează-te în a genera o curbă personalizată, cu dimensiunea biților de $n$ și $p$ redus cu câțiva biți de la 256. Pentru fiecare 1 bit de securitate la care renunțăm, câștigăm aproximativ 2 pt. $n$ și $p$, deci pe biți de text cifrat, sau de 4 ori mai puține presupuneri în bucla while. Și pentru secp256r1 cele mai cunoscute atacuri necesită, fără îndoială $>2^{140}$ operații pe biți (bazate pe o extrapolare conservatoare a unui fișier similar Revendicare de $>2^{140}$ pentru Ed25519).
Notă: În manualul Diffie-Hellman sau ElGamal, alegem $k$ uniform în $[0,n)$. Varianta noastră se limitează la $k$ cu $k\,G$ având o $x$ coordonează cu ea de ordin inferior $b$ biți la zero. Printr-un argument statistic, există aproximativ $n/2^b$ astfel de $k$. Am vrea să alegem $k$ uniform în acest subset de $[0,n)$. Cel mai simplu ar fi repetarea la întâmplare $k$, dar asta are un cost de calcul prohibitiv pentru multiplicarea punctelor $R\obține k\,G$. Economisim la asta trecând de la un singur candidat $k$ la următorul cu un increment fix $e$, permițând actualizarea $R$ printr-un singur punct $R\obține R+F$.
Dacă am folosit fix $e=1$, apoi $k$ selectat de bucla while ar avea o proprietate distinsă (pentru a ști $k$): probabilitatea ca a $k$ este selectat este proporțional cu $j$ calculabil din $k$ ca cel mai mic $j>0$ astfel încât $k-j$ este în submult (sau $k+1$ daca nu exista asa ceva $j$, care apare pentru un singe $k$ în submult). Problema este similară cu alegerea neuniformă a primului obținut prin alegerea unui punct de plecare aleatoriu și căutarea următorului prim.
Alegerea oricărui fix public $e$ nu rezolvă problema, deoarece definiția de $j$ poate fi adaptat la $k-e\,j$ în submult. Cu toate acestea, alegerea unui secret aleatoriu $e$ pentru fiecare alegere de $k$ face. O tehnică similară este utilizată în generatoarele prime aleatorii pentru RSA. Nu am nicio referință, dar un argument este că un adversar nu știe $e$ nu stiu ce $e$ a folosi pentru un test; pot testa pentru toți $e$ și combină rezultatele, dar apoi testul lor este copleșit de zgomot.
Am ales limita superioară a intervalului $[1,2^{32})$ pentru $e$ astfel încât calculul $F\obține e\,G$ are un cost marginal așteptat în comparație cu $R\obține k\,G$. Sunt încrezător (fără dovezi sau referințe) că acest lucru este mai mult decât suficient pentru a face părtinire în selecția $k$ practic nedetectabil chiar și pentru ipoteticii adversari care știu $k$; iar adversarii efectivi nu puteau decât să obțină $k$ printr-un canal lateral.
Gând final: am putea atenua orice teamă că criteriile $R_x\equiv0\pmod{2^b}$ creează o slăbiciune prin ajustarea acesteia la: scăzut $b$ un pic de $R_x$ sunt o funcție (având aproximativ o distribuție uniformă) a celorlalți biți ai $R_x$. A $b$-bit CRC ar face. Receptorul poate reconstrui biții de ordin inferioară necesari $R_x$ prin aplicarea acestei funcţii.
