Criptosistemul Nakasha-Stern

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 octombrie 2019; verificările necesită 4 modificări .

Criptosistemul Nakasha - Stern este un algoritm criptografic cu cheie publică bazat pe complexitatea computațională a problemei logaritmului discret . Spre deosebire de RSA , este omomorfă în ceea ce privește adunarea și scăderea, nu înmulțirea .

Dezvoltat de David Nakache și Jacques Stern în 1998 [1] în două versiuni: deterministă și probabilistică. Este o îmbunătățire a schemei Benalo [2] - autorii au reușit să construiască un criptosistem homomorf probabilist cu securitate semantică și să reducă semnificativ raportul dintre dimensiunea textului cifrat și dimensiunea textului simplu .

Există o implementare (python3) a algoritmilor de generare a cheilor, criptare și decriptare [3] .

Comparație cu RSA

Asemănări

Utilizarea numerelor RSA [1]

Diferențele

Utilizarea diferitelor funcții unidirecționale cu o intrare secretă . După cum subliniază autorii lui [1] , acest punct este de mare interes teoretic, deoarece, în opinia lor, în prezent există doar o mică varietate de funcții unidirecționale cu o intrare secretă, iar acest lucru afectează direct viteza de creare. noi criptosisteme cu cheie publică [1] .
Puterea acestui algoritm nu este direct legată de puterea algoritmului de criptare al criptosistemului RSA . Și anume, securitatea RSA este legată de complexitatea problemei factorizării întregi , iar securitatea criptosistemului Nakas-Stern este legată de complexitatea problemei logaritmului discret [4] .
Criptosistemul RSA este homomorf în ceea ce privește înmulțirea, în timp ce criptosistemul Nakas-Stern este homomorf în ceea ce privește adunarea [1] .

Descrierea variantei deterministe a criptosistemului

În general, o versiune deterministă a criptosistemului Nakasha-Stern poate fi descrisă după cum urmează: să fie un B-neted (B este mic - de obicei un număr de 10 biți), un număr impar, fără pătrat și să fie un RSA număr (de obicei considerat a fi un număr de cel puțin 768 de biți) astfel încât împarte și este coprim cu , unde este funcția Euler . În continuare, lăsați comanda . Apoi triplul numerelor formează o cheie privată. Un mesaj mai mic decât este criptat ca . Decriptarea se bazează pe utilizarea divizorilor primi ai numărului [1] . $\sigma$ $n=pq$ $n$ $\sigma$ $\phi(n)$ $\phi (n)/\sigma$ $\phi(n)$ $g\in \mathbb {Z} /n\mathbb {Z}$ $\phi(n)/4$ $p,\q,\\sigma$ $m$ $\sigma$ $g^{m}mod\n$ $\sigma$

Generare cheie

Alegeți „ prime mici ” unde este par. Aici expresia „primuri mici” înseamnă că fie primul dintre numerele prime (1, 3, 5, ...) este luată, fie generată în alt mod decât folosind algoritmi pentru generarea de numere prime mari. $k$ $p_{1},...,p_{k)$ $k$
Lasă , și $u=\prod _{i=1}^{k/2}p_{i)$ $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ $\sigma =uv=\prod _{i=1}^{k}p_{i)$
Alegeți 2 „primuri mari” astfel încât , sunt prime. Aici expresia „primuri mari” este folosită în sensul în care este folosită în algoritmii de generare a numerelor prime mari. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Lasă . În literatură, numărul - produsul „primelor mari” - se numește număr RSA. $n=pq$ $n$
Alegeți un număr aleatoriu astfel încât y să fie ordinea $g\mod\n$ $g$ $\phi(n)/4$

Apoi cheia publică este formată dintr-un triplu de numere . Și închis - [1] $\sigma ,\n,\g$ $p,\q$

Pe măsură ce numărul crește, generarea cheilor devine o operațiune care necesită foarte mult timp, deoarece numărul a trebuie să fie într-un interval adecvat și, în plus, să satisfacă testele de primalitate împreună cu numărul . Pentru a evita această dificultate, autorii propun să se genereze mai întâi numere prime și apoi, prin selectarea numerelor prime auxiliare , să se obțină egalitatea și , unde sunt prime [1] . $n$ $p=2au+1$ $a,\b,\u,\upsilon$ $p',q'$ $p=2aup'+1$ $q=2b\upsilon q'+1$ $p,\q$

Criptare

Criptarea constă într-o singură operație de exponențiere modulo : un mesaj mai mic decât , este criptat ca . Și aici nu sunt folosite în niciun fel . [unu] $n$ $m$ $\sigma$ $E(m)=g^{m}mod\n$ $\sigma$

Decriptare

Decriptarea se bazează pe teorema chineză a restului . Fie divizori primi . Algoritmul calculează și apoi decriptează mesajul m folosind teorema chineză a restului [1] . $p_{i},\ 1\leq i\leq k$ $\sigma$ $m_{i}=m\mod\p_{i)$

Pentru a găsi m i dat textul cifrat , algoritmul calculează , care este exact . Aceasta rezultă din următoarele calcule - aici : . Comparând acest rezultat cu toate puterile posibile ale , se poate găsi valoarea lui . Mai formal, funcția de decriptare este reprezentată de pseudocod [1] : $c=g^{m}mod\n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\n$ $g^{m_{i}\phi (n)/p_{i))\mod\n$ $y_{i}=(m-m_{i})/p_{i)$ ${\textstyle c_{i}\ =\ c^{\phi (n)/p_{i))\ =\ g^{m\phi (n)/p_{i))\ =\ g^{(m_ {i}+y_{i}p_{i})\phi (n)/p_{i}}\ =\ g^{m_{i}\phi (n)/p_{i}}g^{y_{ i}\phi (n)}\ =\ g^{m_{i}\phi (n)/p_{i}}\ mod\ n}$ $g^{j\phi (n)/p_{i)}$ $m_{{i}}$

pentru = 1 la : $i$ $k$
$c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\n$

pentru = 0 la - 1: $j$ $p_{i}$

daca : $c_{i}==g^{j\phi (n)/p_{i))\ mod\n$

$m_{i}=j$

$X$ =Memento chinezesc( , ) $m_i$ $p_{i}$

Exemplu

Generare cheie pentru $k = 6$

[cm. „Descrierea unei variante deterministe a unui criptosistem”]

$p=21211=2*101*3*5*7+1$

$q=928643=2*191*11*13*17+1$

$n=21211*928643=19697446673$

$g=131$

$\sigma =3*5*7*11*13*17$

$p_{1}=3,...,p_{6}=17$

\{i,j\)

conţine

g^{j\phi (n)/p_{i}}\mod\n\mod\10000

	i=1	i=2	i=3	i=4	i=5	i=6
j = 0	unu	unu	unu	unu	unu	unu
j = 1	1966	6544	1967	6273	6043	372
j = 2	9560	3339	4968	7876	4792	7757
j = 3		9400	1765	8720	262	3397
j = 4			6488	8651	6291	702
j = 5			2782	4691	677	4586
j = 6				9489	1890	8135
j = 7				8537	6878	3902
j = 8				2312	2571	5930
j = 9				7701	7180	6399
j = 10					8291	9771
j = 11					678	9771
j = 12						609
j = 13						7337
j = 14						6892
j = 15						3370
j = 16						3489

Criptare $m=202$

$c=g^{m}mod\n=131202\mod\19697446673$

Decriptare

$c^{\phi (n)/p_{1}}\mod\nmod\10000=1996$

$c^{\phi (n)/p_{2}}\mod\n\mod\10000=3339$

$c^{\phi (n)/p_{3}}\mod\n\mod\10000=2782$

$c^{\phi (n)/p_{4}}\mod\n\mod\10000=7994$

$c^{\phi (n)/p_{5}}\mod\n\mod\10000=1890$

$c^{\phi (n)/\ p_{6))\mod\n\mod\10000=3370$

Apoi, folosind tabelul de mai sus:

$m_{1}=m\ mod\ 3=tabel(1996)=1$

$m_{2}=m\ mod\ 5=tabel(3339)=2$

$m_{3}=m\ mod\ 7=tabel(2782)=1996$

$m_{4}=m\mod\ 11=tabel(7994)=4$

$m_{5}=m\ mod\ 13=tabel(1890)=7$

$m_{6}=m\mod\17=tabel(3370)=15$

iar prin teorema chineză a restului obținem: [1] $m=202$

Descrierea variantei probabilistice a criptosistemului

O variantă probabilistică a unui criptosistem este o îmbunătățire față de criptosistemele probabilistice anterioare (de exemplu, criptosistemul Benalo).

Criptosistemele anterioare aveau un dezavantaj foarte semnificativ: pentru a cripta un set mic de date (de exemplu, voturi 0, 1 în votul electronic), criptosistemele deterministe, precum RSA, nu sunt potrivite [1] , deoarece pentru decriptare va fi suficient să compara textul cifrat cu elementele criptate ale setului . Această proprietate a criptosistemelor - incapacitatea de a distinge textele cifrate ale diferitelor elemente ale mulțimii S, se numește securitate semantică [5] . Dar cu o combinație de homomorfism și putere semantică, criptosistemele anterioare au început să genereze aproximativ un kilobyte de text cifrat pentru a cripta textul simplu în câțiva biți [1] . În criptosistemul Nakasha-Stern, pe lângă faptul că are proprietățile homomorfismului, puterea semantică, raportul dintre dimensiunea textului cifrat și dimensiunea textului simplu este exact egal cu . Autorii afirmă că este sigur să luați [1] . $S$ $S$ $n/\sigma$ $\sigma /n<{\frac {1}{4)}$

Generare cheie

Alegeți „prime mici” unde este par. Aici expresia „primuri mici” înseamnă că fie primul dintre numerele prime (1, 3, 5, ...) este luată, fie generată în alt mod decât folosind algoritmi pentru generarea de numere prime mari. $k$ $p_{1},...,p_{k)$ $k$
Lasă , și $u=\prod _{i=1}^{k/2}p_{i)$ $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ $\sigma =uv=\prod _{i=1}^{k}p_{i)$
Alegeți 2 „primuri mari” astfel încât , sunt prime. Aici expresia „primuri mari” este folosită în sensul în care este folosită în algoritmii de generare a numerelor prime mari. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Să fie un număr RSA. $n=pq$
Alegeți un număr aleatoriu astfel încât y să fie ordinea $g\mod\n$ $g$ $\phi(n)/4$

Apoi cheia publică este formată dintr-un triplu de numere . Și închis - [1] $\sigma ,\n,\g$ $p,\q$

Criptare

Criptarea probabilistică este foarte asemănătoare cu criptarea deterministă . „Descrierea unei variante deterministe a unui criptosistem”] . Și anume, să fie un număr pozitiv ales aleatoriu din inelul de resturi modulo : . Atunci algoritmul este scris ca [1] $X$ $n$ $x\in \mathbb {Z} /n\mathbb {Z}$ $E(m)=x^{\sigma}g^{m}mod\n$

Decriptare

Decriptarea în varianta probabilistică a algoritmului de către D. Nakache și J. Stern rămâne neschimbată în comparație cu versiunea deterministă [vezi. „Descrierea unei variante deterministe a unui criptosistem”] . Efectul înmulțirii prin criptare este luat în considerare atunci când ridicăm textul cifrat la puterea . Să facem câteva calcule pentru a verifica acest lucru. $x^{\sigma }$ $\phi (n)/p_{i)$

Fie divizori primi . Algoritmul calculează și apoi decriptează mesajul folosind teorema chineză a restului. $p_{i},1\leq i\leq k$ $\sigma$ $m_{i}=m\mod\p_{i)$ $m$

Pentru a găsi , având în vedere textul cifrat , algoritmul calculează , care este exact . Aceasta rezultă din următoarele calcule: $m_i$ $c=x^{\sigma}g^{m}mod\n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\n$ $g^{m_{i}\phi (n)/p_{i))\mod\n$

{\begin{matrix}c^{\phi (n)/p_{i))&\equiv &x^{\sigma \phi (n)/p_{i))g^{m\phi (n) )/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\& \equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrice}}

Comparând acest rezultat cu toate puterile posibile ale , se poate găsi valoarea [1] $g^{j\phi (n)/p_{i)}$ $m_{{i}}$

Aplicație

În majoritatea domeniilor de aplicare ale criptosistemului Nakasha-Stern, se utilizează proprietatea de homomorfism a acestui criptosistem în ceea ce privește adunarea și scăderea [6] [2] :

Să presupunem că un client are un cont bancar și dorește să retragă o sumă mică . De asemenea, presupunem că soldul este stocat în formă criptată , iar reprezentantul băncii, efectuând operațiunea de retragere a sumei din contul clientului , nu are acces la decriptarea datelor contului. Cu ajutorul criptosistemului Nakasha-Stern se propune o soluție simplă la această problemă prin operațiune - aceasta este valoarea soldului noului cont în formă criptată: . Mai formal: să fie algoritmii de criptare a contului , apoi contul egal cu suma și se calculează prin următoarea formulă: [1] . $m$ $u$ $m$ $E(m)$ $u$ $E(m)/E(u)\mod\n$ $mu$ $E(m_{1})=g^{m_{1}}mod\n,\E(m_{2})=g^{m_{2}}mod\n$ $m_{1},\ m_{2}$ $m_1$ $m_2$ $E(m_{1})E(m_{2})=g^{m_{1}}g^{m_{2}}mod\n=g^{m_{1}+m_{2} }mod\n$
Securitate cloud computing . Să presupunem că cloud-ul conține mulți utilizatori (clienți) . Utilizatorul are date sensibile stocate în cloud. Acest serviciu cloud se numește Storage aaS (stocare ca serviciu). Utilizatorul poate aplica în cloud cu o solicitare pentru a calcula valoarea unei anumite funcții în funcție de datele confidențiale. Solicitarea trebuie să conțină o descriere a funcției , ID-ul utilizatorului și cheia publică a utilizatorului . Cloud-ul trebuie să verifice autoritatea de calcul a utilizatorului . O astfel de verificare poate fi implementată utilizând procedura standard de semnătură digitală electronică . Dacă utilizatorul și-a validat drepturile de a calcula funcția , atunci cloud-ul trebuie să calculeze valoarea și să o trimită utilizatorului. După cum se poate lua funcția de criptare a oricărui sistem criptografic homomorf cu cheie publică, cum ar fi, de exemplu, criptosistemul Nakache-Stern. Un utilizator care își depozitează datele sensibile și trimite o solicitare de evaluare a funcției nu are încredere în cloud și trebuie să ia măsuri și cerințe adecvate pentru a le asigura securitatea. Evident, ar fi mult mai sigur să transferați datele în așa fel încât în timpul operațiunilor care se efectuează asupra acestora, informațiile despre aceste date să nu fie difuzate în niciun fel. Prin urmare, în primul rând, datele trebuie să fie criptate și trebuie să ajungă la server deja în formă criptată. Aceasta înseamnă că criptarea trebuie făcută în continuare de către utilizator. În al doilea rând, este necesar să se prelucreze aceste date fără decriptare, deoarece trebuie urmate anumite proceduri pentru transmiterea și stocarea cheii secrete , mai ales complexe dacă informațiile sunt procesate într-un mediu neîncrezat. Criptosistemele cu criptare homomorfă ajută doar la rezolvarea acestor probleme [7] [2] . $S$ $p_{1},...,p_{i},...,p_{l)$ $p_{i}$ $x_{i}$ $p_{i}$ $F$ $F$ $pk_{i)$ $p_{i}$ $F(x_{i})$ $F$ $E(pk_{i},\F(x_{i}))$ $E$ $F$

Ofucare pentru a proteja produsele software. Pentru prima dată, utilizarea ofuscării în criptografie a fost menționată în lucrarea lui Diffie și Hellman [8] . În acesta, pentru a construi un criptosistem asimetric, se propune utilizarea complexității sarcinii, care constă în analiza programelor într-un limbaj de programare de nivel scăzut (asamblator, bytecode). Scopul principal al ofuscarii este de a face dificilă înțelegerea funcționării programului. Deoarece toate arhitecturile computerizate tradiționale folosesc șiruri binare, prin aplicarea criptării complet homomorfe pe biți, orice funcție poate fi calculată. Prin urmare, este posibilă criptarea homomorfă a întregului program astfel încât să-și păstreze funcționalitatea [9] .
Votul electronic. Și anume, Să fie candidați și direcția, care are acest criptosistem, distribuie între participanți un buletin-vector , unde este numele de familie al celui de-al treilea candidat. Și fiecare participant are o cheie publică . Ca rezultat, obținem - fiecare alegător revine în direcția unui vector , unde este vectorul preferințelor. Câștigătorul alegerii este candidatul care a primit cele mai multe voturi în total - acest număr - suma voturilor - se calculează pe vectori criptați ai alegătorilor. Acest lucru este posibil prin homomorfism. Și avantajul acestei abordări este că nu este nevoie să decriptăm datele alegătorilor pentru numărarea voturilor - securitatea alegerilor pentru alegători este crescută [10] . $n$ $(p_{1},...,\p_{n})$ $p_{i}$ $i$ $pk$ $(\nu _{1},...,\nu _{n})$ $\nu _{i}\in \{0,1\)$
Zona de filigran [11] . Omomorfismul criptosistemului vă permite să aplicați un filigran datelor criptate [12] .
Dovada de cunoștințe zero . Sistemele omomorfe sunt utilizate atunci când devine necesară confirmarea deținerii oricăror informații care pot fi verificate fără a dezvălui informațiile în sine [13] [14] .

Atacurile

Atacurile larg cunoscute asupra acestui criptosistem nu sunt documentate. Autorii înșiși încurajează munca de distrugere a criptosistemului. Articolul original a oferit [1] 768 USD cuiva care ar putea descifra textul cifrat și să publice metoda criptoanalizei . Mai jos sunt datele pentru această sarcină. $c$

$c$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a 16

$g$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743 16

$n$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d 16

Aici ( — se formează din primele prime, cu excepția lui 2) [1] . $k=30$ $p_{i}$ $i$

Link -uri

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Jacques, Stern. Un nou criptosistem cu cheie publică bazat pe reziduuri mai mari // ACM . - 1998. - P. 59–66 . Arhivat din original pe 6 decembrie 2006.
↑ 1 2 3 A.I. Troubey. Criptare homomorfă: securitate cloud computing și alte aplicații (recenzie) (rusă) // Informatică. - 2015. - ianuarie. Arhivat din original pe 26 noiembrie 2018.
↑ Implementarea algoritmilor de criptare, decriptare, generare de chei în criptosistemul Nakashe-Stern . Preluat la 16 decembrie 2018. Arhivat din original la 28 decembrie 2020. (nedefinit)
↑ Thomas W. Cusick. O comparație între RSA și criptosistemul cu cheie publică Naccache-Stern // Protocoale de securitate. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. — P. 111–116 . — ISBN 9783540624943 , 9783540680475 . - doi : 10.1007/3-540-62494-5_10 . Arhivat din original pe 2 decembrie 2018.
↑ S. Goldwasser, S. Micali. Criptare probabilistică (engleză) // JCSS. - 1984. - Aprilie. - P. 270-299 .
↑ O scurtă prezentare a criptosistemului homomorf și a aplicațiilor lor // International Journal of Computer Applications. — 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. Despre băncile de date și homomorfismele de confidențialitate // Bazele calculului securizat.
↑ W. Diffie, M. Hellman. Noi direcții în criptografie // IEEE Trans. inf. teorie.
↑ J. Alwen [et al.] Despre relația dintre criptarea funcțională, ofuscarea și criptarea complet homomorfă // Cryptography and Coding – 14th IMA Intern. Conf., IMACC-2013..
↑ JD Cohen Benaloh. Alegeri cu vot secret verificabile (engleză) // Universitatea Yale: teză de doctorat. — 1988.
↑ B. Pfitzmann, M. Schunter. Amprentare asimetrică (engleză) // Spinger-Verlag. - 1996. - P. 84-95 .
↑ Construirea unei scheme securizate de filigranare dependentă de conținut folosind criptarea homomorfă.
↑ O. Goldreich, S. Micali, A. Wigderson. Dovezi care nu dau nimic altceva decât validitatea lor și o metodologie de proiectare a protocolului criptografic . - 1986. - P. 174-187 .
↑ G. Brassard, D. Chaum, C. Crepeau. Discuții minime de dovezi de cunoștințe // JCSS. - 1988. Arhivat la 27 septembrie 2011.

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP