GMR

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 15. december 2019; checks kræver 13 redigeringer .

GMR er en kryptografisk algoritme , der bruges til at skabe en digital signatur. Opkaldt efter de første bogstaver fra skaberne - Ronald Rivest , Silvio Micali og Shafi Goldwasser .

GMR er baseret på den høje beregningsmæssige kompleksitet af faktorisering af store heltal, som RSA -kryptosystemet . Men i modsætning til det er GMR modstandsdygtig over for angreb baseret på valgt klartekst [1] .

Hvad vil det sige at knække en digital signatur?

Det kan siges, at en kryptoanalytiker har "knækket" en digital signatur , hvis det perfekte angreb tillader ham at gøre følgende med en sandsynlighed, der ikke er nul [2] : $EN$

Total pause: beregn den private nøgle $EN$
Universal forfalskning: find en effektiv algoritme, der svarer til den digitale signaturalgoritme (generelt bruges en anden, men tilsvarende hemmelig nøgle) $EN$
Selektiv forfalskning: at forfalske signaturen på en meddelelse valgt på forhånd af kryptoanalytikeren
Eksistentiel forfalskning: Forfalsk signaturen på mindst én besked. Samtidig vælger kryptanalytikeren ikke en besked til at forfalske en signatur, forfalskning kan være tilfældigt og meningsløst. En falsk af denne type kan medføre minimal skade på . Forfatterne af GMR-skemaet beviste sin modstand mod denne type angreb [3] . $EN$

Beskrivelse af algoritmen

Antag, at Alice skal sende en sekvens af beskeder til Bob, der er digitalt signeret . Lad Alice antage at signere beskeder, den tilfældige krypteringsparameter er . Den offentlige nøgle består af følgende komponenter: $2^{b}$ $k$

Maksimalt antal meddelelser, der skal krypteres $B=2^{b},b\in \mathbb {N} \cup \left\lbrace 0\right\rbrace$
To tilfældigt udvalgte Bloom-tal og , det vil sige to tal, der er produktet af primtal , der kan sammenlignes med et tal modulo [4] $n_{1}=p_{1}q_{1}$ ${\displaystyle n_{2}=p_{2}q_{2))$ $3$ $fire$
To uendelige familier af envejsfunktioner med hemmelig indgang $f_{i,n}\left(x\right)$
Tilfældigt tal valgt fra området $r$ $f_{i,n_{1}}\left(\cdot \right)$

Den private nøgle består af primtal, der muliggør effektiv beregning af de inverse funktioner og . $p_{1},q_{1},p_{2},q_{2}$ $f_{i,n_{1}}^{-1}\left(y\right)$ $f_{i,n_{2}}^{-1}\left(y\right)$

Overvej tilfældet med at generere en signatur for én besked , det vil sige og . Alice vælger et tilfældigt tal fra området og beregner beskedsignaturen : $m$ $B=1$ $b=0$ $r_{0}$ $f_{i,n_{1}}\left(\cdot \right)$ $\left(t,r_{0},s\right)$

t=f_{r_{0},n_{1}}^{-1}\left(r\right)

og .

s=f_{m,n_{2}}^{-1}\left(r_{0}\right)

Efter at have modtaget den underskrevne besked, tjekker Bob det sekventielt

$f_{m,n_{2}}\left(s\right)=r_{0}$

$f_{r_{0},n_{1}}\left(t\right)=r$ .

For at signere beskeder bygger Alice et hash-træ med blade fra rodelementet . Alle interne træspidser vælges tilfældigt og lige sandsynligt fra værdisættet , på samme måde i tilfælde af en enkelt besked. Hver intern node er sikkert forbundet med begge dens underordnede noder ved at beregne værdien af , placeret i toppunktet, på samme måde som beregnet ovenfor . Endelig er meddelelsen sikkert forbundet med det i -te blad i godkendelsestræet ved at evaluere en værdi på samme måde som beregnet ovenfor . Meddelelsessignaturen består af $B=2^{b}>1$ $r$ $B$ ${\displaystyle r_{0},r_{1},\dots ,r_{B-1))$ $f_{i,n_{1}}\left(\cdot \right)$ $r_{0}$ $R$ $f_{R_{0}\parallel R_{1},n_{1}}\left(R\right)$ $t$ $m_{j}\left(0\leqslant j\leqslant B-1\right)$ $j$ $r_j$ $s_{j}=f_{m_{j},n_{2}}^{-1}\left(r_{j}\right)$ $s$ $m_{j}$

Sekvenser af træspidser fra rod til blad $b$ $r$ $r_j$
$b$ værdier placeret ved toppunkter (svarende til ovenfor) $t$
$s_{j}$ (svarende til ovenfor) [5] . $s$

Envejsfunktioner med hemmelig indgang

Som envejsfunktioner kan bruges til og , hvor funktionen tager en bitstreng som input og returnerer et heltal repræsenteret af bits i omvendt rækkefølge [6] . Funktionen accepterer også en bitstreng og returnerer dens længde. Plus- eller minustegnet vælges således, at værdien er positiv og ikke overstiger . I dette tilfælde udføres beregningen af den inverse funktion i en tid proportional med , hvor er længden af strengen , forudsat at de signerede meddelelser har samme længde. Således kan signaturen af en -bit-meddelelse beregnes i tid [6] . $f_{i,n}\left(x\right)=\pm 4^({\text{rev))\left(i\right)}x^{2^({\text{len)) \left(i\right)}}\mod{n}$ $n=n_{1}$ $n=n_{2}$ ${\text{rev}}\left(\cdot \right)$ $i\in \left\lbrace 0,1\right\rbrace ^{+}$ $jeg$ ${\text{len}}\left(\cdot \right)$ $i\in \left\lbrace 0,1\right\rbrace ^{+},$ ${\displaystyle f_{i,n))$ $n/2$ ${\displaystyle k^{3))$ $k$ $jeg$ $k$ $O\left(bk^{3}\right)$

Algoritmens kryptografiske styrke

Goldwasser, Micali og Rivest beviste [3] at GMR-algoritmen ikke tillader en kryptoanalytiker at udføre et adaptivt angreb baseret på en valgt besked, nemlig at udføre en eksistentiel forfalskning af en signatur genereret af GMR-skemaet. En kryptanalytiker, der har fået signaturer for et antal meddelelser, kan ikke forfalske en signatur for nogen yderligere meddelelse.

Scheme generaliseringer

Generaliseringer af GMR-skemaet til brug som et udpeget bekræftersignaturskema er mulige [7] .

Noter

↑ S. Goldwasser, S. Micali, R. L. Rivest, 1988 .
↑ S. Goldwasser, S. Micali, R. L. Rivest, 1988 , s. 284.
↑ 1 2 S. Goldwasser, S. Micali, R. L. Rivest, 1988 , s. 298-304.
↑ HCA Van Tilborg, S. Jajodia, 2014 , s. halvtreds.
↑ HCA Van Tilborg, S. Jajodia, 2014 , s. 240.
↑ 1 2 S. Goldwasser, S. Micali, R. L. Rivest, 1988 , s. 305.
↑ S. Goldwasser, E. Waisbard, 2004 , s. 95.

Litteratur

Goldwasser S., Micali S., Rivest RL En digital signaturordning, der er sikret mod adaptive valgte beskedangreb // SIAM Journal on Computing. - 1988. - T. 61 , nr. 3 . - S. 281-308 .
Van Tilborg HCA, Jajodia S. Encyclopedia of cryptography and security. — Springer Science & Business Media, 2014.
Goldwasser S., Waisbard E. Transformation af digitale signaturskemaer til udpegede bekræftersignaturskemaer // Theory of Cryptography Conference. - Springer, Berlin, Heidelberg, 2004. - S. 77-100 .

Links

Digitale signaturordninger

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