Nakasha-Stern kryptosystem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 oktober 2019; kontroller kräver 4 redigeringar .

Nakasha- Stern - kryptosystemet är en kryptografisk algoritm med offentlig nyckel baserad på beräkningskomplexiteten hos det diskreta logaritmproblemet . Till skillnad från RSA är den homomorf med avseende på addition och subtraktion, inte multiplikation .

Utvecklad av David Nakache och Jacques Stern 1998 [1] i två versioner: deterministisk och probabilistisk. Det är en förbättring av Benalo-schemat [2] - författarna kunde bygga ett probabilistiskt homomorft kryptosystem med semantisk säkerhet och avsevärt minska förhållandet mellan storleken på chiffertexten och storleken på klartexten .

Det finns en implementering (python3) av nyckelgenererings-, krypterings- och dekrypteringsalgoritmer [3] .

Jämförelse med RSA

Likheter

Använda RSA-nummer [1]

Skillnader

Användning av olika enkelriktade funktioner med hemlig ingång . Som författarna till [1] betonar , är denna punkt av stort teoretiskt intresse, eftersom det enligt deras åsikt för närvarande bara finns ett litet utbud av enkelriktade funktioner med en hemlig ingång, och detta påverkar direkt hastigheten att skapa nya offentliga nyckelkryptosystem [1] .
Styrkan hos denna algoritm är inte direkt relaterad till styrkan hos krypteringsalgoritmen för RSA -krypteringssystemet . Säkerheten för RSA är nämligen relaterad till komplexiteten i heltalsfaktoriseringsproblemet , och säkerheten för Nakas-Stern-kryptosystemet är relaterad till komplexiteten i det diskreta logaritmproblemet [4] .
RSA-kryptosystemet är homomorft med avseende på multiplikation, medan Nakas-Stern-kryptosystemet är homomorft med avseende på addition [1] .

Beskrivning av den deterministiska varianten av kryptosystemet

I allmänhet kan en deterministisk version av Nakasha-Stern-kryptosystemet beskrivas på följande sätt: låt vara ett B-slät (B är litet - vanligtvis ett 10-bitars tal), ett udda, kvadratfritt tal, och låt vara ett RSA nummer (Tänks vanligen vara minst 768-bitars tal) så att delar och är coprime med , där är Euler-funktionen . Låt sedan beställa . Sedan bildar trippeln av siffror en privat nyckel. Ett meddelande mindre än är krypterat som . Dekryptering är baserad på användningen av primtalsdelare för talet [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$

Nyckelgenerering

Välj "små primtal " där är jämnt. Här betyder frasen "små primtal" att antingen de första av primtalen (1, 3, 5, ...) tas eller genereras på något annat sätt än att använda algoritmer för att generera stora primtal. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Låt , och $u=\prod _{i=1}^{k/2}p_{i}$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Välj 2 "stora primtal" så att , är primtal. Här används frasen "stora primtal" i den mening som den används i algoritmer för att generera stora primtal. $a, \b$ $p=2au+1$ $q=2b\upsilon +1$
Låt . I litteraturen kallas talet - produkten av "stora primtal" - för RSA-talet. $n=pq$ $n$
Välj ett slumpmässigt tal så att y är ordningen $g\ mod\ n$ $g$ $\phi(n)/4$

Sedan bildas den publika nyckeln av en trippel av siffror . Och stängd - [1] $\sigma ,\ n,\ g$ $p,\ q$

När antalet växer blir nyckelgenerering en mycket tidskrävande operation, eftersom siffran a måste ligga inom ett lämpligt intervall och dessutom uppfylla primalitetstesten tillsammans med numret . För att kringgå denna svårighet, föreslår författarna att först generera primtal och sedan, genom att välja hjälpprimtal , uppnå jämlikhet och , där är 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 av en enda exponentieringsoperation modulo : ett meddelande som är mindre än , krypteras som . Och här används de inte på något sätt . [ett] $n$ $m$ $\sigma$ $E(m)=g^{m}mod\ n$ $\sigma$

Dekryptering

Dekrypteringen är baserad på den kinesiska restsatsen . Låt vara primtalare . Algoritmen beräknar och dekrypterar sedan meddelandet m med hjälp av den kinesiska restsatsen [1] . $p_{i},\ 1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$

För att hitta m i givet chiffertexten , beräknar algoritmen , vilket är exakt . Detta följer av följande beräkningar - här : . Genom att jämföra detta resultat med alla möjliga krafter av , kan man hitta värdet av . Mer formellt representeras dekrypteringsfunktionen av pseudokod [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))$ ${\textstil 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))$ $mi}}$

för = 1 till : $i$ $k$
$c_{i}\ =\ c^{\phi (n)/p_{i))\ mod\ n$

för = 0 till - 1: $j$ $pi}$

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

$m_{i}=j$

$x$ = ChineseReminder( , ) $mi$ $pi}$

Exempel

Nyckelgenerering för $k = 6$

[centimeter. "Beskrivning av en deterministisk variant av ett 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\))

innehåller

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

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

Använd sedan tabellen ovan:

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

och av den kinesiska restsatsen får vi: [1] $m=202$

Beskrivning av den probabilistiska varianten av kryptosystemet

En probabilistisk variant av ett kryptosystem är en förbättring av tidigare probabilistiska kryptosystem (till exempel Benalo-kryptosystemet).

Tidigare kryptosystem hade en mycket betydande nackdel: för att kryptera en liten uppsättning data (till exempel rösterna 0, 1 vid elektronisk röstning) är deterministiska kryptosystem, såsom RSA, inte lämpliga [1] , eftersom det för dekryptering kommer att räcka för att jämför chiffertexten med de krypterade elementen i uppsättningen . Denna egenskap hos kryptosystem - oförmågan att särskilja chiffertexter av olika element i mängden S, kallas semantisk säkerhet [5] . Men med en kombination av homomorfism och semantisk styrka började tidigare kryptosystem generera ungefär en kilobyte chiffertext för att kryptera klartexten i några bitar [1] . I Nakasha-Stern-kryptosystemet, förutom att ha egenskaperna homomorfism, semantisk styrka, är förhållandet mellan storleken på chiffertexten och storleken på klartexten exakt lika med . Författarna uppger att det är säkert att ta [1] . $S$ $S$ $n/\sigma$ $\sigma /n<{\frac {1}{4))$

Nyckelgenerering

Välj "små primtal" där är jämnt. Här betyder frasen "små primtal" att antingen de första av primtalen (1, 3, 5, ...) tas eller genereras på något annat sätt än att använda algoritmer för att generera stora primtal. $k$ ${\displaystyle p_{1},...,p_{k))$ $k$
Låt , och $u=\prod _{i=1}^{k/2}p_{i}$ ${\displaystyle \upsilon =\prod _{i=k/2+1}^{k}p_{i))$ ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i))$
Välj 2 "stora primtal" så att , är primtal. Här används frasen "stora primtal" i den mening som den används i algoritmer för att generera stora primtal. $a, \b$ $p=2au+1$ $q=2b\upsilon +1$
Låt vara ett RSA-nummer. $n=pq$
Välj ett slumpmässigt tal så att y är ordningen $g\ mod\ n$ $g$ $\phi(n)/4$

Sedan bildas den publika nyckeln av en trippel av siffror . Och stängd - [1] $\sigma ,\ n,\ g$ $p,\ q$

Kryptering

Probabilistisk kryptering är mycket lik deterministisk kryptering . "Beskrivning av en deterministisk variant av ett kryptosystem"] . Låt oss nämligen vara ett slumpmässigt valt positivt tal från ringen av rester modulo : . Då skrivs algoritmen som [1] $x$ $n$ $x\in \mathbb {Z} /n\mathbb {Z}$ $E(m)=x^{\sigma }g^{m}mod\ n$

Dekryptering

Dekryptering i den probabilistiska versionen av algoritmen av D. Nakache och J. Stern förblir oförändrad i jämförelse med den deterministiska versionen [se. "Beskrivning av en deterministisk variant av ett kryptosystem"] . Effekten av att multiplicera med kryptering tas med i beräkningen när vi höjer chiffertexten till makten . Låt oss göra några beräkningar för att verifiera detta. $x^{\sigma }$ ${\displaystyle \phi (n)/p_{i))$

Låt vara primtalare . Algoritmen beräknar och dekrypterar sedan meddelandet med den kinesiska restsatsen. $p_{i},1\leq i\leq k$ $\sigma$ ${\displaystyle m_{i}=m\ mod\ p_{i))$ $m$

För att hitta , med tanke på chiffertexten , beräknar algoritmen , vilket är exakt . Detta följer av följande beräkningar: $mi$ $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{matris}}

Genom att jämföra detta resultat med alla möjliga potenser av , kan man hitta värdet [1] $g^{j\phi (n)/p_{i))$ $mi}}$

Applikation

I den rådande majoriteten av tillämpningsområden för Nakasha-Stern-kryptosystemet används egenskapen homomorfism för detta kryptosystem med avseende på addition och subtraktion [6] [2] :

Anta att en kund har ett bankkonto och vill ta ut ett mindre belopp . Vi antar också att saldot lagras i krypterad form och att bankrepresentanten, som utför operationen att ta ut beloppet från kundens konto , inte har tillgång till att dekryptera kontodata. Med hjälp av Nakasha-Stern-kryptosystemet föreslås en enkel lösning på detta problem genom operationen - detta är värdet på det nya kontosaldot i krypterad form: . Mer formellt: låt vara kontot krypteringsalgoritmer , då kontot lika med summan och beräknas med följande 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 Security . Antag att molnet innehåller många användare (klienter) . Användaren har känslig data lagrad i molnet. Denna molntjänst kallas Storage aaS (storage as a service). Användaren kan ansöka till molnet med en begäran om att beräkna värdet av någon funktion beroende på konfidentiell data. Begäran ska bestå av en beskrivning av funktionen , användar-ID och användarens publika nyckel . Molnet måste kontrollera användarens beräkningsauktoritet . Sådan verifiering kan implementeras med hjälp av standardproceduren för elektroniska digitala signaturer . Om användaren har validerat sina rättigheter att beräkna funktionen måste molnet beräkna värdet och skicka det till användaren. Som man kan ta krypteringsfunktionen för vilket homomorft kryptosystem som helst med offentlig nyckel, såsom till exempel Nakache-Stern-kryptosystemet. En användare som lagrar sina känsliga uppgifter och skickar en begäran om att utvärdera funktionen litar inte på molnet och måste vidta lämpliga åtgärder och krav för att säkerställa sin säkerhet. Uppenbarligen skulle det vara mycket säkrare att överföra uppgifter på ett sådant sätt att information om dessa uppgifter under de operationer som utförs på dem inte skulle spridas på något sätt. Därför måste data för det första krypteras och de måste anlända till servern redan i krypterad form. Detta innebär att kryptering fortfarande måste göras av användaren. För det andra är det nödvändigt att behandla dessa data utan dekryptering, eftersom vissa procedurer måste följas för att överföra och lagra den hemliga nyckeln , särskilt komplex om informationen behandlas i en opålitlig miljö. Kryptosystem med homomorf kryptering hjälper bara till att lösa dessa problem [7] [2] . $S$ ${\displaystyle p_{1},...,p_{i},...,p_{l))$ $pi}$ $x_{i}$ $pi}$ $F$ $F$ ${\displaystyle pk_{i))$ $pi}$ $F(x_{i})$ $F$ $E(pk_{i},\ F(x_{i}))$ $E$ $F$

Obfuskation för att skydda mjukvaruprodukter. För första gången nämndes användningen av obfuskation i kryptografi i arbetet av Diffie och Hellman [8] . I det, för att bygga ett asymmetriskt kryptosystem, föreslås det att man använder komplexiteten i uppgiften, som består i att analysera program i ett programmeringsspråk på låg nivå (assembler, bytecode). Huvudsyftet med obfuskering är att göra det svårt att förstå hur programmet fungerar. Eftersom alla traditionella datorarkitekturer använder binära strängar, genom att tillämpa helt homomorf kryptering över bitar, kan vilken funktion som helst beräknas. Därför är det möjligt att homomorfiskt kryptera hela programmet så att det behåller sin funktionalitet [9] .
Elektronisk röstning. Nämligen, Låt det finnas kandidater och direktoratet, som har detta kryptosystem, fördelar bland deltagarna en valsedel-vektor , där är efternamnet på den e kandidaten. Och varje deltagare har en offentlig nyckel . Som ett resultat får vi - varje väljare återgår till riktningen en vektor , där är vektorn för preferenser. Vinnaren av valet är den kandidat som fick flest röster totalt - detta antal - summan av röster - beräknas över krypterade vektorer av väljare. Detta möjliggörs av homomorfism. Och fördelen med detta tillvägagångssätt är att det inte finns något behov av att dekryptera väljardata för att räkna röster - säkerheten vid val för väljare ökar [10] . $n$ $(p_{1},...,\ p_{n})$ $pi}$ $i$ $pk$ $(\nu _{1},...,\nu _{n})$ ${\displaystyle \nu _{i}\in \{0,1\))$
Vattenstämpelområde [ 11] . Homomorfismen hos kryptosystemet låter dig applicera en vattenstämpel på krypterad data [12] .
Noll kunskapsbevis . Homomorfa system används när det blir nödvändigt att bekräfta innehavet av all information som kan verifieras utan att avslöja själva informationen [13] [14] .

Attacker

Allmänt kända attacker på detta kryptosystem är inte dokumenterade. Författarna själva uppmuntrar arbetet med att bryta kryptosystemet. Den ursprungliga artikeln erbjöd [1] $768 till någon som kunde dechiffrera chiffertexten och publicera kryptoanalysmetoden . Nedan finns uppgifterna för denna uppgift. $c$

$c$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a 16

$g$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743 16

$n$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d 16

Här ( — bildas från de första primtal, förutom 2) [1] . $k=30$ $pi}$ $i$

Länkar

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Jacques, Stern. Ett nytt kryptosystem med offentlig nyckel baserat på högre rester // ACM . - 1998. - S. 59–66 . Arkiverad från originalet den 6 december 2006.
↑ 1 2 3 A.I. Troubey. Homomorphic Encryption: Cloud Computing Security and Other Applications (Review) (ryska) // Informatik. - 2015. - Januari. Arkiverad från originalet den 26 november 2018.
↑ Implementering av kryptering, dekryptering, nyckelgenereringsalgoritmer i Nakashe-Stern-kryptosystemet . Hämtad 16 december 2018. Arkiverad från originalet 28 december 2020. (obestämd)
↑ Thomas W. Cusick. En jämförelse mellan RSA och 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 . Arkiverad från originalet den 2 december 2018.
↑ S. Goldwasser, S. Micali. Probabilistisk kryptering (engelska) // JCSS. - 1984. - April. - S. 270-299 .
↑ En kort översikt av homomorfiska kryptosystem och deras tillämpningar // International Journal of Computer Applications. — 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. Om databanker och integritetshomomorfismer // Grunderna för säker beräkning.
↑ W. Diffie, M. Hellman. Nya riktningar inom kryptografi // IEEE Trans. inf. teori.
↑ J. Alwen [et al.] Om förhållandet mellan funktionell kryptering, obfuskation och fullständigt homomorf kryptering // Kryptografi och kodning – 14:e IMA Intern. Conf., IMACC-2013..
↑ JD Cohen Benaloh. Verifierbara hemliga val (engelska) // Yale University: Ph-D avhandling. — 1988.
↑ B. Pfitzmann, M. Schunter. Asymmetrisk fingeravtryck (engelska) // Spinger-Verlag. - 1996. - S. 84-95 .
↑ Konstruera säkert innehållsberoende vattenmärkningsschema med hjälp av homomorfisk kryptering.
↑ O. Goldreich, S. Micali, A. Wigderson. Bevis som inte ger något annat än deras giltighet och en metod för kryptografisk protokolldesign . - 1986. - S. 174-187 .
↑ G. Brassard, D. Chaum, C. Crepeau. Minsta diskussionsbevis för kunskap // JCSS. - 1988. Arkiverad 27 september 2011.

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort