factograf
CS

Jazyk Wikipedie

EnglishУкраїнськаDeutschFrançaisEspañolPolskiItalianoPortuguêsРусскийČeština日本語中文NederlandsSvenskaالعربيةفارسیעבריתTürkçe한국어Tiếng ViệtBahasa Indonesiaहिन्दीRomânăMagyarSuomiNorskDanskΕλληνικάБългарскиСрпскиHrvatskiSlovenčinaLietuviųLatviešuEestiქართულიՀայերենҚазақшаБеларускаяCatalàEuskaraไทย

ElGamal

ElGamal je jeden z algoritmů asymetrické kryptografie, má ovšem nevýhodu, že šifrovaná data jsou dvakrát delší než data nešifrovaná. To je možná důvodem, proč není jeho nasazení tak velké, jako nasazení algoritmu RSA, který tímto nedostatkem netrpí. Opírá se o problém výpočtu diskrétního logaritmu.

Konstrukce systému

Nechť je zvolena veřejně známá cyklická grupa {\displaystyle \mathbb {Z} _{q}^{\circ }}, tzn. celé číslo {\displaystyle q}, tzv. modul grupy, a celé číslo {\displaystyle g}, tzv. generátor dané grupy. Potom si i-tý účastník volí svůj tajný klíč {\displaystyle k_{i}}, tak, že {\displaystyle 0<k_{i}<q} a vypočte veřejný klíč {\displaystyle k_{i}^{pub}} jako {\displaystyle k_{i}^{pub}=g^{k_{i}}\mod q}, jenž zveřejní. Pokud potom chce poslat uživatel {\displaystyle A} zprávu {\displaystyle P} uživateli {\displaystyle B} (zpráva musí být menší než {\displaystyle q}), {\displaystyle A} musí znát veřejný klíč {\displaystyle B}, tzn. {\displaystyle k_{B}^{pub}}. Poté probíhá komunikace podle následujícího schématu.

  • {\displaystyle A} zvolí náhodné číslo {\displaystyle k_{A}} takové, že {\displaystyle 0<k_{A}<q}.
  • {\displaystyle A} spočte {\displaystyle k_{A}^{pub}=g^{k_{A}}\mod q}, {\displaystyle K=(k_{B}^{pub})^{k_{A}}\mod q} a {\displaystyle Q=P\circ K\mod q} a pošle pár {\displaystyle Q,k_{A}^{pub}} uživateli {\displaystyle B}.
  • Uživatel {\displaystyle B} spočte {\displaystyle K=(k_{A}^{pub})^{k_{B}}\mod q} a k tomuto číslu určí inverzní prvek {\displaystyle K^{-1}} (vzhledem k operaci {\displaystyle \circ } v grupě {\displaystyle \mathbb {Z} _{q}^{\circ }}).
  • Uživatel {\displaystyle B} spočte zprávu {\displaystyle P} jako {\displaystyle P=Q\circ K^{-1}\mod q}.

Korektnost algoritmu

S využitím vět algebry platí:

  • {\displaystyle \forall i,j\in \mathbb {N},\forall g}- generátor, {\displaystyle q} – modul {\displaystyle \in \mathbb {Z} _{q}^{\circ },} cyklická grupa v modulu q.
  • {\displaystyle k_{i}\iff 0<k_{i}<q,k_{j}\iff 0<k_{j}<q}
    • {\displaystyle k_{i}} a {\displaystyle k_{j}} jsou soukromé klíče {\displaystyle i} a {\displaystyle j}
  • {\displaystyle k_{i}^{pub}=g^{k_{i}}\mod q\land K=(k_{i}^{pub})^{k_{j}}\mod q} a ekvivalentně pro {\displaystyle k_{j}^{pub}}
    • {\displaystyle k_{i}^{pub}} je veřejný klíč a {\displaystyle K} je soukromý sdílený klíč pro šifrování komunikace mezi {\displaystyle i} a {\displaystyle j}
  • {\displaystyle K=(g^{k_{i}})^{k_{j}}\mod q=(g^{k_{j}})^{k_{i}}\mod q=g^{k_{i}\cdot k_{j}}\mod q}
  • {\displaystyle Q\circ K^{-1}\mod q=P\circ K\circ K^{-1}\mod q=P\mod q}

{\displaystyle \square }

Analýza

Na prolomení toho systému by musel útočník vyřešit problém diskrétního logaritmu, což je považováno za nepolynomiální problém, protože v současnosti neexistuje algoritmus, který by zvládl vypočítat diskrétní logaritmus v cyklické grupě s polynomiální složitostí.

Číst dál

Modulární aritmetikaobor matematiky a algebraický systém zabývající se operacemi s čísly z konečné množiny tvořené zbytky po dělení daným fixním číslem Diffieho–Hellmanova výměna klíčůvýměna šifrovacích klíčů přes nezabezpečený kanál Diskrétní logaritmusproblém inverze umocňování v konečných grupách Diffieho–Hellmanův protokol s využitím eliptických křivekvýměna šifrovacích klíčů přes nezabezpečený kanál Digital Signature Algorithmalgoritmus pro elektronický podpis Schnorrův podpiskryptografické podpisové schéma

V 24 jazycích

ČeštinaالعربيةالدارجةazərbaycancaDeutschEnglishespañolفارسیsuomifrançaisעבריתBahasa Indonesiaitaliano日本語한국어lietuviųNederlandspolskiportuguêsрусскийsvenskaTürkçeукраїнська中文

Text z Wikipedie, CC BY-SA 4.0 · Zdrojový článek