Nakasha-Stern kryptosystem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. oktober 2019; checks kræver 4 redigeringer .

Nakasha- Stern kryptosystem er en offentlig nøgle kryptografisk algoritme baseret på beregningskompleksiteten af det diskrete logaritmeproblem . I modsætning til RSA er den homomorf med hensyn til addition og subtraktion, ikke multiplikation .

Udviklet af David Nakache og Jacques Stern i 1998 [1] i to versioner: deterministisk og probabilistisk. Det er en forbedring af Benalo-skemaet [2] - forfatterne var i stand til at bygge et probabilistisk homomorfisk kryptosystem med semantisk sikkerhed og signifikant reducere forholdet mellem størrelsen af chifferteksten og størrelsen af klarteksten .

Der er en implementering (python3) af nøglegenererings-, krypterings- og dekrypteringsalgoritmer [3] .

Sammenligning med RSA

Ligheder

Brug af RSA-numre [1]

Forskelle

Brug af forskellige envejsfunktioner med hemmelig indgang . Som forfatterne af [1] understreger , er dette punkt af stor teoretisk interesse, fordi der efter deres mening i øjeblikket kun er et lille udvalg af envejsfunktioner med en hemmelig indgang, og dette påvirker direkte hastigheden af at skabe nye offentlige nøglekryptosystemer [1] .
Styrken af denne algoritme er ikke direkte relateret til styrken af krypteringsalgoritmen i RSA -kryptosystemet . Sikkerheden i RSA er nemlig relateret til kompleksiteten af heltalsfaktoriseringsproblemet , og sikkerheden i Nakas-Stern-kryptosystemet er relateret til kompleksiteten af det diskrete logaritmeproblem [4] .
RSA-kryptosystemet er homomorft med hensyn til multiplikation, mens Nakas-Stern-kryptosystemet er homomorft med hensyn til addition [1] .

Beskrivelse af den deterministiske variant af kryptosystemet

Generelt kan en deterministisk version af Nakasha-Stern-kryptosystemet beskrives som følger: lad være en B-glat (B er lille - normalt et 10-bit tal), et ulige, kvadratfrit tal, og lad være et RSA tal (normalt menes at være mindst 768-bit tal) sådan at dividere og er coprime med , hvor er Euler-funktionen . Lad derefter bestille . Så danner det tredobbelte af tal en privat nøgle. En besked mindre end er krypteret som . Dekryptering er baseret på brugen af prime divisorer af tallet [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$

Nøglegenerering

Vælg "små primtal " , hvor er lige. Her betyder udtrykket "små primtal", at enten de første af primtal (1, 3, 5, ...) tages eller genereres på en anden måde end at bruge algoritmer til at generere store primtal. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Lad , og ${\displaystyle u=\prod _{i=1}^{k/2}p_{i))$ $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Vælg 2 "store primtal" , sådan at , er primtal. Her bruges udtrykket "store primtal" i den betydning, som det bruges i algoritmer til at generere store primtal. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Lad . I litteraturen kaldes tallet - produktet af "store primtal" - RSA-tallet. $n=pq$ $n$
Vælg et tilfældigt tal , så y er rækkefølgen $g\ mod\ n$ $g$ $\phi(n)/4$

Derefter dannes den offentlige nøgle af en tripel af tal . Og lukket - [1] $\sigma ,\ n,\ g$ $p,\ q$

Efterhånden som antallet vokser, bliver nøglegenerering en meget tidskrævende operation, fordi tallet a skal være i et passende interval og derudover opfylde primalitetstestene sammen med tallet . For at omgå denne vanskelighed foreslår forfatterne først at generere primtal og derefter ved at vælge hjælpeprimtal opnå lighed og , hvor er primtal [1] . $n$ $p=2au+1$ $a,\ b,\ u,\upsilon$ $p',q'$ $p=2aup'+1$ $q=2b\upsilon q'+1$ $p,\ q$

Kryptering

Kryptering består af en enkelt eksponentieringsoperation modulo : en besked mindre end , krypteres som . Og her bliver de ikke brugt på nogen måde . [en] $n$ $m$ $\sigma$ $E(m)=g^{m}mod\ n$ $\sigma$

Dekryptering

Dekrypteringen er baseret på den kinesiske restsætning . Lad være prime divisorer . Algoritmen beregner og dekrypterer derefter meddelelsen m ved hjælp af den kinesiske restsætning [1] . $p_{i},\ 1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$

For at finde m i givet chifferteksten , beregner algoritmen , hvilket er nøjagtigt . Dette følger af følgende beregninger - her : . Ved at sammenligne dette resultat med alle mulige potenser af , kan man finde værdien af . Mere formelt er dekrypteringsfunktionen repræsenteret af pseudokode [1] : $c=g^{m}mod\ n$ $c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$ $g^{m_{i}\phi (n)/p_{i))\ mod\ n$ ${\displaystyle y_{i}=(m-m_{i})/p_{i))$ ${\tekststil 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}}$

for = 1 til : $jeg$ $k$
$c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$

for = 0 til - 1: $j$ $p_{i}$

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

$m_{i}=j$

$x$ = KinesiskPåmindelse( , ) $m_i$ $p_{i}$

Eksempel

Nøglegenerering til $k = 6$

[cm. "Beskrivelse af en deterministisk variant af et kryptosystem"]

$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$

{\displaystyle \{i,j\))

indeholder

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

	i=1	i=2	i=3	i=4	i=5	i=6
j = 0	en	en	en	en	en	en
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

Kryptering $m=202$

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

Dekryptering

$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$

Brug derefter tabellen ovenfor:

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

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

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

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

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

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

og ved den kinesiske restsætning får vi: [1] $m=202$

Beskrivelse af den probabilistiske variant af kryptosystemet

En probabilistisk variant af et kryptosystem er en forbedring af tidligere sandsynlige kryptosystemer (for eksempel Benalo-kryptosystemet).

Tidligere kryptosystemer havde en meget væsentlig ulempe: at kryptere et lille sæt data (for eksempel stemmer 0, 1 ved elektronisk afstemning), er deterministiske kryptosystemer, såsom RSA, ikke egnede [1] , fordi det til dekryptering vil være nok til at sammenligne chifferteksten med de krypterede elementer i sættet . Denne egenskab ved kryptosystemer - manglende evne til at skelne chiffertekster af forskellige elementer i sættet S, kaldes semantisk sikkerhed [5] . Men med en kombination af homomorfi og semantisk styrke begyndte tidligere kryptosystemer at generere omkring en kilobyte chiffertekst for at kryptere klarteksten i nogle få bits [1] . I Nakasha-Stern-kryptosystemet er forholdet mellem størrelsen af chifferteksten og størrelsen af klarteksten, ud over at have egenskaberne homomorfi, semantisk styrke, nøjagtigt lig med . Forfatterne oplyser, at det er sikkert at tage [1] . $S$ $S$ $n/\sigma$ $\sigma /n<{\frac {1}{4))$

Nøglegenerering

Vælg "små primtal" , hvor er lige. Her betyder udtrykket "små primtal", at enten de første af primtal (1, 3, 5, ...) tages eller genereres på en anden måde end at bruge algoritmer til at generere store primtal. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Lad , og ${\displaystyle u=\prod _{i=1}^{k/2}p_{i))$ $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Vælg 2 "store primtal" , sådan at , er primtal. Her bruges udtrykket "store primtal" i den betydning, som det bruges i algoritmer til at generere store primtal. $a, \ b$ $p=2au+1$ $q=2b\upsilon +1$
Lad være et RSA-nummer. $n=pq$
Vælg et tilfældigt tal , så y er rækkefølgen $g\ mod\ n$ $g$ $\phi(n)/4$

Derefter dannes den offentlige nøgle af en tripel af tal . Og lukket - [1] $\sigma ,\ n,\ g$ $p,\ q$

Kryptering

Probabilistisk kryptering minder meget om deterministisk kryptering . "Beskrivelse af en deterministisk variant af et kryptosystem"] . Nemlig, lad være et tilfældigt valgt positivt tal fra ringen af rester modulo : . Derefter skrives algoritmen som [1] $x$ $n$ $x\in \mathbb {Z} /n\mathbb {Z}$ $E(m)=x^{\sigma }g^{m}mod\ n$

Dekryptering

Dekryptering i den probabilistiske version af algoritmen af D. Nakache og J. Stern forbliver uændret i sammenligning med den deterministiske version [se. "Beskrivelse af en deterministisk variant af et kryptosystem"] . Effekten af at gange med i kryptering tages i betragtning, når vi hæver chifferteksten til magten . Lad os lave nogle beregninger for at bekræfte dette. ${\displaystyle x^{\sigma ))$ ${\displaystyle \phi (n)/p_{i))$

Lad være prime divisorer . Algoritmen beregner og dekrypterer derefter meddelelsen ved hjælp af den kinesiske restsætning. $p_{i},1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$ $m$

For at finde , givet chifferteksten , beregner algoritmen , hvilket er nøjagtigt . Dette følger af følgende beregninger: $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{matrix}}

Ved at sammenligne dette resultat med alle mulige potenser af , kan man finde værdien [1] $g^{j\phi (n)/p_{i))$ $m_{{i}}$

Ansøgning

I det fremherskende flertal af anvendelsesområder for Nakasha-Stern-kryptosystemet bruges egenskaben for homomorfi af dette kryptosystem med hensyn til addition og subtraktion [6] [2] :

Antag, at en klient har en bankkonto og ønsker at hæve et mindre beløb . Vi antager også, at saldoen er gemt i krypteret form , og bankrepræsentanten, der udfører operationen med at hæve beløbet fra kundens konto , har ikke adgang til at dekryptere kontodataene. Ved hjælp af Nakasha-Stern-kryptosystemet foreslås en simpel løsning på dette problem gennem operationen - dette er værdien af den nye kontosaldo i krypteret form: . Mere formelt: lad være kontoen krypteringsalgoritmer , så kontoen lig med summen og beregnes ved følgende formel: [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$
Cloud Computing Sikkerhed . Antag, at skyen indeholder mange brugere (klienter) . Brugeren har følsomme data gemt i skyen. Denne cloud-tjeneste kaldes Storage aaS (storage as a service). Brugeren kan henvende sig til skyen med en anmodning om at beregne værdien af en funktion afhængigt af fortrolige data. Anmodningen skal bestå af en beskrivelse af funktionen , bruger-id og brugerens offentlige nøgle . Skyen skal kontrollere brugerens computerautoritet . En sådan verifikation kan implementeres ved hjælp af standardproceduren for elektronisk digital signatur . Hvis brugeren har valideret deres rettigheder til at beregne funktionen , skal skyen beregne værdien og sende den til brugeren. Som man kan tage krypteringsfunktionen af ethvert homomorfisk offentlig nøgle kryptosystem, såsom for eksempel Nakache-Stern kryptosystem. En bruger, der lægger deres følsomme data på lager og indsender en anmodning om at evaluere funktionen , har ikke tillid til skyen og skal træffe passende foranstaltninger og krav for at sikre deres sikkerhed. Det er klart, at det ville være meget sikrere at overføre data på en sådan måde, at information om disse data under de operationer, der udføres på dem, ikke ville blive spredt på nogen måde. Derfor skal dataene for det første være krypteret, og de skal ankomme til serveren allerede i krypteret form. Det betyder, at kryptering stadig skal udføres af brugeren. For det andet er det nødvendigt at behandle disse data uden dekryptering, da visse procedurer skal følges for at transmittere og opbevare den hemmelige nøgle , især kompleks, hvis informationen behandles i et miljø, der ikke er tillid til. Kryptosystemer med homomorf kryptering er blot med til at løse disse problemer [7] [2] . $S$ ${\displaystyle p_{1},...,p_{i},...,p_{l))$ $p_{i}$ $x_{i}$ $p_{i}$ $F$ $F$ ${\displaystyle pk_{i))$ $p_{i}$ $F(x_{i})$ $F$ $E(pk_{i},\ F(x_{i}))$ $E$ $F$

Uklarhed for at beskytte softwareprodukter. For første gang blev brugen af obfuskation i kryptografi nævnt i Diffies og Hellmans arbejde [8] . I det, for at bygge et asymmetrisk kryptosystem, foreslås det at bruge kompleksiteten af opgaven, som består i at analysere programmer i et lavniveau programmeringssprog (assembler, bytecode). Hovedformålet med sløring er at gøre det vanskeligt at forstå programmets funktion. Da alle traditionelle computerarkitekturer bruger binære strenge, kan enhver funktion beregnes ved at anvende fuldstændig homomorf kryptering over bits. Derfor er det muligt at homomorf kryptere hele programmet, så det bevarer sin funktionalitet [9] .
Elektronisk afstemning. Nemlig Lad der være kandidater og direktoratet, som har dette kryptosystem, fordeler blandt deltagerne en stemmeseddel-vektor , hvor er efternavnet på den th kandidat. Og hver deltager har en offentlig nøgle . Som et resultat får vi - hver vælger vender tilbage til retningen en vektor , hvor er vektoren af præferencer. Vinderen af valget er den kandidat, der fik flest stemmer i alt - dette antal - summen af stemmer - er beregnet over krypterede vektorer af vælgere. Dette er muliggjort af homomorfi. Og fordelen ved denne tilgang er, at der ikke er behov for at dekryptere vælgerdata for at tælle stemmer - sikkerheden ved valg for vælgere er øget [10] . $n$ $(p_{1},...,\ p_{n})$ $p_{i}$ $jeg$ $pk$ $(\nu _{1},...,\nu _{n})$ $\nu _{i}\i \{0,1\}$
Vandmærkeområde [ 11] . Homomorfien af kryptosystemet giver dig mulighed for at anvende et vandmærke på krypterede data [12] .
Nul vidensbevis . Homomorfe systemer bruges, når det bliver nødvendigt at bekræfte besiddelsen af enhver information, der kan verificeres uden at afsløre selve informationen [13] [14] .

Angreb

Alment kendte angreb på dette kryptosystem er ikke dokumenteret. Forfatterne opfordrer selv til at arbejde med at bryde kryptosystemet. Den originale artikel tilbød [1] $768 til en person, der kunne dechifrere chifferteksten og udgive kryptoanalysemetoden . Nedenfor er dataene for denne opgave. $c$

$c$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a 16

$g$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743 16

$n$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d 16

Her ( — er dannet af de første primtal, bortset fra 2) [1] . $k=30$ $p_{i}$ $jeg$

Links

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Jacques, Stern. Et nyt offentlig nøglekryptosystem baseret på højere rester // ACM . - 1998. - S. 59–66 . Arkiveret fra originalen den 6. december 2006.
↑ 1 2 3 A.I. Troubey. Homomorf kryptering: Cloud Computing Security og andre applikationer (gennemgang) (russisk) // Informatik. - 2015. - Januar. Arkiveret fra originalen den 26. november 2018.
↑ Implementering af kryptering, dekryptering, nøglegenereringsalgoritmer i Nakashe-Stern-kryptosystemet . Hentet 16. december 2018. Arkiveret fra originalen 28. december 2020. (ubestemt)
↑ Thomas W. Cusick. En sammenligning af RSA og Naccache-Stern public-key kryptosystem // Security Protocols. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. — S. 111–116 . — ISBN 9783540624943 , 9783540680475 . - doi : 10.1007/3-540-62494-5_10 . Arkiveret fra originalen den 2. december 2018.
↑ S. Goldwasser, S. Micali. Probabilistisk kryptering (engelsk) // JCSS. - 1984. - April. - S. 270-299 .
↑ En kort oversigt over homomorfe kryptosystem og deres applikationer // International Journal of Computer Applications. – 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. Om databanker og privatlivshomomorfier // Fundamenter for sikker beregning.
↑ W. Diffie, M. Hellman. Nye retninger i kryptografi // IEEE Trans. inf. teori.
↑ J. Alwen [et al.] Om forholdet mellem funktionel kryptering, sløring og fuldt homomorf kryptering // Cryptography and Coding – 14th IMA Intern. Conf., IMACC-2013..
↑ JD Cohen Benaloh. Verificable Secret-Ballot Elections (engelsk) // Yale University: Ph-D afhandling. - 1988.
↑ B. Pfitzmann, M. Schunter. Asymmetrisk fingeraftryk (engelsk) // Spinger-Verlag. - 1996. - S. 84-95 .
↑ Konstruktion af et sikkert indholdsafhængigt vandmærkeskema ved hjælp af homomorfisk kryptering.
↑ O. Goldreich, S. Micali, A. Wigderson. Beviser, der ikke giver andet end deres gyldighed og en metode til kryptografisk protokoldesign . - 1986. - S. 174-187 .
↑ G. Brassard, D. Chaum, C. Crepeau. Minimum diskussionsbevis for viden // JCSS. - 1988. Arkiveret den 27. september 2011.

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort