Schéma ElGamal

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é 10. května 2018; kontroly vyžadují 43 úprav .

Schéma Elgamal je kryptosystém s veřejným klíčem založený na obtížnosti výpočtu diskrétních logaritmů v konečném poli . Šifrovací systém zahrnuje šifrovací algoritmus a algoritmus digitálního podpisu. Schéma ElGamal je základem dřívějších standardů digitálního podpisu ve Spojených státech ( DSA ) a Rusku ( GOST R 34.10-94 ).

Schéma navrhl Taher El-Gamal v roce 1985 . [1] ElGamal vyvinul variantu Diffie-Hellmanova algoritmu . Vylepšil systém Diffie-Hellman a získal dva algoritmy, které byly použity pro šifrování a pro autentizaci. Algoritmus ElGamal nebyl na rozdíl od RSA patentován, a proto se stal levnější alternativou, protože nebyly vyžadovány žádné licenční poplatky. Předpokládá se, že algoritmus je pokryt patentem Diffie-Hellman.

Generování klíčů

Vygeneruje se náhodné prvočíslo . $p$
Je vybráno celé číslo - primitivní kořen . $G$ $p$
Náhodné celé číslo je vybráno tak, že . $X$ $(1<x<p-1)$
Vypočteno . $y=g^{x}{\bmod {p}}$
Veřejný klíč je , soukromý klíč je . $(y,g,p)$ $X$

Práce v šifrovaném režimu

Šifrovací systém ElGamal je ve skutečnosti jedním ze způsobů, jak generovat veřejné klíče Diffie-Hellman . Šifrování ElGamal by se nemělo zaměňovat s algoritmem digitálního podpisu ElGamal.

Šifrování

Zpráva musí být menší než . Zpráva je zašifrována následovně: $M$ $p$

Zvolí se klíč relace — náhodné celé číslo spojené s , takže . $(p - 1)$ $k$ $1<k<p-1$
Čísla a jsou vypočteny . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
Dvojice čísel je šifrový text . $(a,b)$

Je snadné vidět, že délka šifrovaného textu ve schématu ElGamal je dvojnásobkem délky původní zprávy . $M$

Dešifrování

Při znalosti soukromého klíče lze původní zprávu vypočítat ze šifrovaného textu pomocí vzorce: $X$ $(a,b)$

M=b(a^{x})^{-1}{\bmod {p)).

Zároveň je snadné to zkontrolovat

(a^{x})^{-1}=g^{-kx}{\bmod {p))

a proto

b(a^{x})^{-1}=(y^{k}M)g^{-xk}\equiv (g^{xk}M)g^{-xk}\equiv M {\pmod {p}}

Pro praktické výpočty je vhodnější následující vzorec:

M=b(a^{x})^{-1}=ba^{(p-1-x)}{\pmod {p))

Schéma šifrování

Příklad

Šifrování
1. Řekněme, že chceme zašifrovat zprávu . $M=5$
2. Vygenerujeme klíče:
  1. Nechte _ Zvolme náhodné celé číslo takové, že . $p=11,g=2$ $x=8$ $X$ $1<x<p$
  2. Pojďme počítat . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Veřejný klíč je tedy 3 a soukromý klíč je číslo . $(p,g,y)=(11,2,3)$ $x=8$
3. Vyberte náhodné celé číslo takové, že 1 < k < (p − 1). Nechte _ $k$ $k=9$
4. Vypočítáme číslo . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Vypočítáme číslo . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. Výsledná dvojice je šifrový text. $(a,b)=(6,9)$
Dešifrování
1. Musíte přijmout zprávu pomocí známého šifrovaného textu a soukromého klíče . $M=5$ $(a,b)=(6,9)$ $x=8$
2. M vypočítáme podle vzorce: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Mám původní zprávu . $M=5$

Protože je do schématu ElGamal zavedena náhodná proměnná , lze ElGamalovu šifru nazvat vícehodnotovou substituční šifrou. Kvůli náhodnosti výběru čísla se takové schéma také nazývá pravděpodobnostní šifrovací schéma. Pravděpodobnostní povaha šifrování je výhodou schématu ElGamal, protože pravděpodobnostní schémata šifrování vykazují větší sílu ve srovnání se schématy se specifickým šifrovacím procesem. Nevýhodou šifrovacího schématu ElGamal je, že šifrovaný text je dvakrát delší než prostý text. U pravděpodobnostního šifrovacího schématu samotná zpráva a klíč nedefinují šifrový text jednoznačně. Ve schématu ElGamal je nutné použít různé hodnoty náhodné proměnné pro šifrování různých zpráv a . Pokud použijete totéž , pak pro odpovídající šifrové texty a vztah je splněn . Z tohoto výrazu se dá snadno vypočítat , pokud někdo ví . $k$ $k$ $M$ $k$ $M$ $M'$ $k$ $(a,b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $M'$ $M$

Práce v režimu podpisu

Digitální podpis slouží k tomu, aby bylo možné identifikovat změny dat a určit identitu podepisující osoby. Příjemce podepsané zprávy může pomocí digitálního podpisu prokázat třetí straně, že podpis skutečně provedl odesílatel. Při práci v režimu podpisu se předpokládá, že existuje pevná hashovací funkce , jejíž hodnoty leží v intervalu . $h(\cdot )$ $\left(1,p-1\right)$

Podpisy zpráv

Chcete-li podepsat zprávu , provedou se následující operace: $M$

Výpis zprávy se vypočítá : (Hashovací funkce může být libovolná). $M$ $m=h(M).$
Vybere se a vypočítá se náhodné číslo , které má stejné písmeno $1<k<p-1$ $p-1$ $r=g^{k}\,{\bmod {\,}}str.$
Vypočítá se číslo , kde je multiplikativní inverzní modulo , které lze zjistit například pomocí rozšířeného Euklidova algoritmu . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
Podpis zprávy je dvojice . $M$ $\left(r,s\right)$

Ověření podpisu

Při znalosti veřejného klíče je podpis zprávy ověřen následovně: $\left(p,g,y\right)$ $\left(r,s\right)$ $M$

Kontroluje se proveditelnost podmínek: a . $0<r<p$ $0<s<p-1$
Pokud alespoň jeden z nich selže, pak je podpis považován za neplatný.
Digest se vypočítá $m=h(M).$
Podpis je považován za platný, pokud je provedeno srovnání: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Kontrola správnosti

Uvažovaný algoritmus je správný v tom smyslu, že podpis vypočítaný podle výše uvedených pravidel bude přijat při jeho ověření.

Transformace definice , máme $s$

m\,\equiv \,xr+sk{\pmod {p-1)).

Dále z Fermatovy Malé věty vyplývá, že

{\begin{aligned}g^{m}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k}) ^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}

Příklad

Podpis zprávy.
1. Řekněme, že chceme podepsat zprávu . $M=baaqab$
2. Vygenerujeme klíče:
  1. Ať jsou proměnné známé nějaké komunitě. $p=23$ $g=5$
  2. Tajný klíč je náhodné celé číslo takové, že . $x=7$ $X$ $1<x<p$
  3. Vypočítejte veřejný klíč : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Veřejný klíč je tedy 3 . $(p,g,y)=(23,5,17)$
3. Nyní vypočítáme hashovací funkci: . $h(M)=h(baaqab)=m=3$
4. Zvolme náhodné celé číslo takové, aby byla podmínka splněna . Nechte _ $k$ $1<k<p-1$ $k=5$
5. Vypočítejte r = g^k mod p = 5^5 mod 23 = 20.
6. najdeme . Takové číslo existuje, protože GCD . Lze jej nalézt pomocí rozšířeného Euklidova algoritmu. Dostat ${\displaystyle k^{-1))$ $(k,p-1)=1$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Hledání čísla . Dostáváme , protože $s\,\equiv \,(m-xr)k^{{-1}}{\pmod {p-1}}$ $s=21$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Takže jsme podepsali zprávu: . $<baaqab,20,21>$

Ověření přijaté zprávy.
1. Vypočteme hashovací funkci: . $h(M)=h(baaqab)=m=3$
2. Podívejme se na srovnání . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Vypočítejte modulo 23 na levé straně: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Vypočítejte modulo na pravé straně 23: . $5^{3}{\bmod {2}}3=10$
5. Protože pravá a levá část jsou stejné, znamená to, že podpis je správný.

Hlavní výhodou schématu digitálního podpisu ElGamal je možnost generovat digitální podpisy pro velké množství zpráv pomocí pouze jednoho tajného klíče. Aby útočník zfalšoval podpis, potřebuje vyřešit složité matematické problémy s nalezením logaritmu v poli . Je třeba uvést několik připomínek:

\mathbb {Z} _{p}

Náhodné číslo by mělo být zničeno ihned po výpočtu podpisu, protože pokud útočník zná náhodné číslo a samotný podpis, pak může snadno najít tajný klíč pomocí vzorce: a podpis zcela zfalšovat. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

Číslo musí být náhodné a nesmí být duplikováno pro různé podpisy získané se stejnou hodnotou tajného klíče. $k$

Použití skládání se vysvětluje tím, že chrání podpis před výčtem zpráv podle hodnot podpisu, které útočník zná. Příklad: pokud zvolíte náhodná čísla , která splňují podmínky , gcd(j,p-1)=1 a předpokládáme, že $m=h(M)$ $i,j$ $0<i<{p-1},0<j<{p-1}$ $r=g^{i}\cdot y^{-j}{\bmod {p))$ $s=r\cdot j^{-1}{\bmod {(}}p-1)$ $m=r\cdot i\cdot j^{-1}{\bmod {(}}p-1)$

je snadné ověřit, že se jedná o správný digitální podpis zprávy . $(r,s)$ $x=M$

Digitální podpis ElGamal se stal příkladem konstrukce dalších podpisů, které jsou svými vlastnostmi podobné. Jsou založeny na srovnání: , ve kterém trojka nabývá hodnot jedné z permutací ±r, ±s a ±m pro nějaký výběr znamének. Například původní schéma ElGamal je získáno pomocí , , , Na tomto principu vytváření podpisu jsou založeny standardy digitálního podpisu USA a Ruska. V americkém standardu DSS (Digital Signature Standard) se používají hodnoty , , , a v ruském standardu: , , . $y^{A}\cdot r^{B}=g^{C}(modp)$ $(A,B,C)$ $A=r$ $B=s$ $C=m$ $A=r$ $B=-s$ $C=m$ $A=-x$ $B=-m$ $C=s$
Další výhodou je možnost zkrátit délku podpisu nahrazením dvojice čísel dvojicí čísel ), kde je nějaký jednoduchý dělitel čísla . V tomto případě by porovnání pro ověření podpisu modulo mělo být nahrazeno novým porovnáním modulo : . To se provádí v americkém standardu DSS (Digital Signature Standard). $(s,m)$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $p$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Kryptografická síla a vlastnosti

V současné době jsou kryptosystémy s veřejným klíčem považovány za nejslibnější. Patří mezi ně schéma ElGamal, jehož kryptografická síla je založena na výpočetní složitosti problému diskrétního logaritmu , kde při daném p , g a y je nutné vypočítat x , které vyhovuje srovnání:

y\equiv g^{x}{\pmod {p)).

GOST R34.10-1994 , přijatý v roce 1994 v Ruské federaci, který upravoval postupy pro generování a ověřování elektronického digitálního podpisu, byl založen na schématu ElGamal. Od roku 2001 se používá nový GOST R 34.10-2001 využívající aritmetiku eliptických křivek definovaných nad jednoduchými Galoisovými poli . Existuje velké množství algoritmů založených na schématu ElGamal: jsou to algoritmy DSA , ECDSA , KCDSA , Schnorr schéma .

Porovnání některých algoritmů:

Algoritmus	Klíč	Účel	Kryptografická odolnost, MIPS	Poznámky
RSA	Až 4096 bitů	Šifrování a podepisování	2.7•10 28 pro 1300bitový klíč	Na základě obtížnosti problému faktorizace velkého počtu ; jeden z prvních asymetrických algoritmů. Zahrnuto v mnoha normách
ElGamal	Až 4096 bitů	Šifrování a podepisování	Při stejné délce klíče je kryptografická síla rovna RSA, tzn. 2.7•10 28 pro 1300bitový klíč	Na základě obtížného problému výpočtu diskrétních logaritmů v konečném poli; umožňuje rychle generovat klíče bez ohrožení bezpečnosti. Používá se v algoritmu digitálního podpisu DSS standardu DSA
DSA	Až 1024 bitů	Pouze podpis		Na základě obtížnosti problému diskrétního logaritmu v konečném poli ; přijat jako stát americký standard; používá se pro tajnou a neutajovanou komunikaci; Developerem je NSA.
ECDSA	Až 4096 bitů	Šifrování a podepisování	Kryptoodolnost a rychlost provozu jsou vyšší než u RSA	Moderní směr. Vyvinutý mnoha předními matematiky

Poznámky

↑ Elgamal, 1985 .

Literatura

Elgamal T. Kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech, kryptosystém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1985. - Sv. 31, Iss. 4. - S. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Alferov A.P., Zubov A.Yu., Kuzmin A.S., Cheremushkin A.V. Základy kryptografie.[ upřesnit ]
B. A. Forouzan. Schéma digitálního podpisu ElGamal // Správa šifrovacích klíčů a zabezpečení sítě / Per. A. N. Berlín. - Přednáškový kurz.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 The ElGamal signature scheme // Handbook of Applied Cryptography (English) - CRC Press , 1996. - 816 s. — ( Diskrétní matematika a její aplikace ) — ISBN 978-0-8493-8523-0

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