GMR

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. prosince 2019; kontroly vyžadují 13 úprav .

GMR je kryptografický algoritmus používaný k vytváření digitálního podpisu. Pojmenováno podle prvních písmen tvůrců - Ronalda Rivesta , Silvia Micaliho a Shafiho Goldwassera .

GMR je založeno na vysoké výpočetní složitosti faktorizace velkých celých čísel, jako je kryptosystém RSA . Na rozdíl od něj je však GMR odolný vůči útokům založeným na zvoleném otevřeném textu [1] .

Co to znamená prolomit digitální podpis?

Dá se říci, že kryptoanalytik „prolomil“ digitální podpis , pokud mu dokonalý útok umožňuje s nenulovou pravděpodobností provést následující [2] : $A$

Total break: výpočet soukromého klíče $A$
Univerzální padělání: najděte účinný algoritmus, který je ekvivalentní algoritmu digitálního podpisu (obecně se používá jiný, ale ekvivalentní tajný klíč) $A$
Selektivní padělání: padělání podpisu nějaké zprávy zvolené a priori kryptoanalytikem
Existenciální padělek: Padělek podpisu alespoň jedné zprávy. Kryptanalytik si zároveň nevybírá zprávu k padělání podpisu, padělání může být náhodné a nesmyslné. Padělek tohoto typu může způsobit minimální poškození . Autoři schématu GMR prokázali jeho odolnost vůči tomuto typu útoku [3] . $A$

Popis algoritmu

Předpokládejme, že Alice potřebuje poslat Bobovi sekvenci zpráv, které jsou digitálně podepsané . Nechte Alici, aby podepisovala zprávy, parametr náhodného šifrování je . Veřejný klíč se skládá z následujících komponent: $2^{b}$ $k$

Maximální počet zpráv, které mají být zašifrovány $B=2^{b},b\in \mathbb {N} \cup \left\lbrace 0\right\rbrace$
Dvě náhodně vybraná Bloomova čísla a , tedy dvě čísla, která jsou součinem prvočísel , srovnatelná s číslem modulo [4] $n_{1}=p_{1}q_{1}$ $n_{2}=p_{2}q_{2}$ $3$ $čtyři$
Dvě nekonečné rodiny jednosměrných funkcí s tajným vchodem $f_{i,n}\left(x\right)$
Náhodné číslo vybrané z rozsahu $r$ $f_{i,n_{1}}\left(\cdot \right)$

Soukromý klíč se skládá z prvočísel , která umožňují efektivní výpočet inverzních funkcí a . $p_{1},q_{1},p_{2},q_{2}$ $f_{i,n_{1}}^{-1}\left(y\right)$ $f_{i,n_{2}}^{-1}\left(y\right)$

Zvažte případ generování podpisu pro jednu zprávu , tedy a . Alice vybere náhodné číslo z rozsahu a vypočítá podpis zprávy : $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)

a .

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

Po obdržení podepsané zprávy to Bob postupně zkontroluje

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

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

K podepisování zpráv Alice sestaví hash tree s listy z kořenového prvku . Všechny vnitřní vrcholy stromu jsou vybírány náhodně a stejně pravděpodobně z množiny hodnot , podobně jako v případě jedné zprávy. Každý vnitřní uzel je bezpečně spojen s oběma svými podřízenými uzly výpočtem hodnoty , umístěné ve vrcholu, stejným způsobem, jak je vypočítáno výše . Nakonec je zpráva bezpečně spojena s i-tým listem autentizačního stromu vyhodnocením hodnoty stejným způsobem, jak je vypočítáno výše . Podpis zprávy se skládá z $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}\paralelní 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}$

Posloupnosti vrcholů stromů od kořene po list $b$ $r$ $r_j$
$b$ hodnoty umístěné ve vrcholech (podobně jako výše) $t$
$s_{j}$ (podobně jako výše) [5] . $s$

Jednosměrné funkce s tajným vchodem

Jako jednosměrné funkce lze použít pro a , kde funkce bere jako vstup bitový řetězec a vrací celé číslo reprezentované bity v obráceném pořadí [6] . Funkce také přijímá bitový řetězec a vrací jeho délku. Znaménko plus nebo mínus se volí tak, aby hodnota byla kladná a nepřesahovala . V tomto případě se výpočet inverzní funkce provádí v čase úměrném , kde je délka řetězce , za předpokladu, že podepsané zprávy mají stejnou délku. Signaturu -bitové zprávy lze tedy vypočítat v čase [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 ^{+}$ $i$ ${\text{len}}\left(\cdot \right)$ $i\in \left\lbrace 0,1\right\rbrace ^{+},$ ${\displaystyle f_{i,n))$ $n/2$ ${\displaystyle k^{3))$ $k$ $i$ $k$ $O\left(bk^{3}\right)$

Kryptografická síla algoritmu

Goldwasser, Micali a Rivest prokázali [3] , že algoritmus GMR neumožňuje kryptoanalytikovi úspěšně provést adaptivní útok na základě zvolené zprávy, konkrétně provést existenciální padělek podpisu generovaného schématem GMR. Kryptanalytik, který získal podpisy pro více zpráv, nemůže zfalšovat podpis pro žádnou další zprávu.

Zobecnění schémat

Zobecnění schématu GMR pro použití jako určené schéma potvrzovacího podpisu je možné [7] .

Poznámky

↑ 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 , str. padesáti.
↑ HCA Van Tilborg, S. Jajodia, 2014 , str. 240.
↑ 1 2 S. Goldwasser, S. Micali, R. L. Rivest, 1988 , s. 305.
↑ S. Goldwasser, E. Waisbard, 2004 , str. 95.

Literatura

Goldwasser S., Micali S., Rivest RL Schéma digitálního podpisu zabezpečené proti útokům adaptivních vybraných zpráv // SIAM Journal on Computing. - 1988. - T. 61 , č. 3 . - S. 281-308 .
Van Tilborg HCA, Jajodia S. Encyklopedie kryptografie a bezpečnosti. — Springer Science & Business Media, 2014.
Goldwasser S., Waisbard E. Transformace schémat digitálního podpisu na určená schémata potvrzovacích podpisů // Konference Theory of Cryptography. - Springer, Berlín, Heidelberg, 2004. - S. 77-100 .

Odkazy

Schémata digitálního podpisu

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta