Diskrétní logaritmus - Discrete logarithm

V matematiky , pro dané reálných čísel a b je logaritmus log _b je číslo x tak, že b ^x = . Analogicky v jakékoli skupině G mohou být síly b ^k definovány pro všechna celá čísla k a diskrétní logaritmický log _b a je celé k takové, že b ^k = a . V teorii čísel je více běžně používaný termín index : můžeme napsat x = ind _r a (mod  m ) (číst „index a k základně r modulo  m “) pro r ^x ≡ a (mod  m ), pokud r je primitivní kořen z m a gcd ( , m ) = 1.    

Diskrétní logaritmy jsou v několika speciálních případech rychle vyčíslitelné. Obecně však není známa žádná efektivní metoda pro jejich výpočet. Několik důležitých algoritmů v kryptografii veřejného klíče zakládá svou bezpečnost na předpokladu, že problém diskrétního logaritmu nad pečlivě vybranými skupinami nemá efektivní řešení.

Definice

Nechť G je jakákoli skupina. Označme jeho skupinové operace násobením a jeho identity prvku od 1. Nechť b být jakýkoliv prvek G . Pro jakékoli kladné celé číslo k výraz b ^k označuje součin b se sebou samým k krát:

${\ Displaystyle b^{k} = \ underbrace {b \ cdot b \ cdots b} _ {k \; {\ text {faktory}}}.}$

Podobně nechť b ^{- k} označuje součin b ⁻¹ se samotným k krát. Pro k = 0 je k -tou mocností identita : b ⁰ = 1 .

Nechť být také prvek G . Celé číslo k, které řeší rovnici b ^k = a, se nazývá diskrétní logaritmus (nebo v tomto kontextu jednoduše logaritmus ) a na základnu b . Jeden píše k  = log _b a .  

Příklady

Pravomoci 10

Mocniny 10 tvoří nekonečnou podmnožinu G = {…, 0,001, 0,01, 0,1, 1, 10, 100, 1000, ...} racionálních čísel . Tato sada G je cyklická skupina s násobením a 10 je generátor. Pro jakýkoli prvek a skupiny lze vypočítat protokol ₁₀  a . Například log ₁₀  10000 = 4 a log ₁₀  0,001 = −3. Toto jsou příklady problému s diskrétním logaritmem.

Jiné logaritmy o základně 10 ve skutečných číslech nejsou příklady problému diskrétního logaritmu, protože zahrnují neceločíselné exponenty. Například log rovnice ₁₀  53 = 1,724276… znamená, že 10 ^1,724276… = 53. Zatímco celočíselné exponenty lze definovat v jakékoli skupině pomocí ^součinů a inverzí, libovolné exponenty ve skutečných číslech vyžadují jiné pojmy, jako je exponenciální funkce .

Pravomoci pevného reálného čísla

Podobný příklad platí pro jakékoli nenulové reálné číslo b . Mocniny tvoří multiplikativní podskupinu G = {…, b ⁻³ , b ⁻² , b ⁻¹ , 1, b ¹ , b ² , b ³ , ...} nenulových reálných čísel. Pro jakýkoli prvek a z G lze vypočítat protokol _b  a .

Modulární aritmetika

Jedním z nejjednodušších nastavení pro diskrétní logaritmy je skupina ( Z _p ) ^× . To je skupina násobení modulo na primární straně . Jeho prvky jsou kongruenční třídy modulo p a skupinový součin dvou prvků lze získat obyčejným celočíselným násobením prvků následovaným redukčním modulem  p .

K th výkonu jednoho z čísel v této skupině může být vypočítán nalezením jeho k th síla jako celé číslo, a pak zjistit zbytek po dělení p . Když jsou zapojená čísla velká, je efektivnější redukovat modulo p vícekrát během výpočtu. Bez ohledu na konkrétní použitý algoritmus se tato operace nazývá modulární umocňování . Zvažte například ( Z ₁₇ ) ^× . Chcete -li vypočítat 3 ⁴ v této skupině, spočítejte 3 ⁴ = 81 a poté rozdělte 81 na 17, čímž získáte zbytek 13. Tedy 3 ⁴ = 13 ve skupině ( Z ₁₇ ) ^× .

Diskrétní logaritmus je pouze inverzní operace. Zvažte například rovnici 3 ^k ≡ 13 (mod 17) pro k . Z výše uvedeného příkladu je jedno řešení k  = 4, ale není to jediné řešení. Protože 3 ¹⁶ ≡ 1 (mod 17) - jak vyplývá z Fermatovy malé věty - také vyplývá, že pokud n je celé číslo, pak 3 ^{4+16 n} ≡ 3 ⁴ × (3 ¹⁶ ) ⁿ ≡ 13 × 1 ⁿ ≡ 13 (mod 17). Rovnice má tedy nekonečně mnoho řešení ve tvaru 4 + 16 n . Navíc, protože 16 je nejmenší kladné celé číslo m splňující 3 ^m ≡ 1 (mod 17), jsou to jediná řešení. Ekvivalentně může být množina všech možných řešení vyjádřena omezením, že k ≡ 4 (mod 16).

Pravomoci identity

Ve zvláštním případě, kdy b je identita prvek 1 ve skupině G , diskrétní logaritmus log _b  je nedefinovaná pro jiný než 1, a každé celé číslo k je diskrétní logaritmus pro a = 1.

Vlastnosti

Mocnosti dodržují obvyklou algebraickou identitu b ^{k  +  l} = b ^k  b ^l . Jinými slovy, funkce

${\ Displaystyle f \ colon \ mathbf {Z} \ to G}$

definovaný f ( K ) = b ^k je skupina homomorphism z celých čísel Z za přídavku na na podskupiny H z G vytvořeného podle b . Pro všechna a v H existuje log _b  a . Naopak, log _b  není pro neexistuje , které nejsou v H .

Pokud H je nekonečné, pak log _b  a je také jedinečný a diskrétní logaritmus se rovná skupinovému izomorfismu

${\ Displaystyle \ log _ {b} \ colon H \ to \ mathbf {Z}.}$

Na druhou stranu, pokud H je konečný řádu n , pak log _b  a je jedinečný pouze do kongruenčního modulu n a diskrétní logaritmus se rovná skupinovému izomorfismu

${\ Displaystyle \ log _ {b} \ colon H \ to \ mathbf {Z} _ {n},}$

kde Z _n označuje aditivní skupinu celých čísel modulo n .

Známý vzorec změny základů pro běžné logaritmy zůstává v platnosti: Pokud c je další generátor H , pak

${\ Displaystyle \ log _ {c} a = \ log _ {c} b \ cdot \ log _ {b} a.}$

Algoritmy

Problém diskrétního logaritmu je považován za výpočetně neřešitelný. To znamená, že pro výpočet diskrétních logaritmů obecně není znám žádný účinný klasický algoritmus.

Obecným algoritmem pro výpočet log _b  a v konečných skupinách G je zvýšit b na větší a větší mocniny k, dokud není nalezeno požadované a . Tento algoritmus se někdy nazývá zkušební násobení . Vyžaduje dobu běhu lineární ve velikosti skupiny G a tedy exponenciální v počtu číslic ve velikosti skupiny. Proto je exponenciální čase algoritmus, praktické pouze pro malé skupiny G .

Existují sofistikovanější algoritmy, obvykle inspirované podobnými algoritmy pro celočíselnou faktorizaci. Tyto algoritmy běží rychleji než naivní algoritmus, některé z nich jsou úměrné druhé odmocnině velikosti skupiny, a tedy exponenciální v polovině počtu číslic ve velikosti skupiny. Žádný z nich však neběží v polynomiálním čase (v počtu číslic ve velikosti skupiny).

• Baby-step obří krok
• Síto funkčního pole
• Algoritmus indexového počtu
• Síto číselného pole
• Algoritmus Pohlig – Hellman
• Pollardův rho algoritmus pro logaritmy
• Pollardův klokaní algoritmus (alias Pollardův lambda algoritmus)

K dispozici je efektivní kvantový algoritmus kvůli Peter Shor .

V určitých zvláštních případech existují také účinné klasické algoritmy. Například ve skupině celých celých modulů p pod přídavkem se moc b ^k stane součinem bk a rovnost znamená shodu modulo p v celých číslech. Mezi rozšířený eukleidův algoritmus nálezy K rychle.

U Diffie – Hellmana se používá modul cyklické skupiny a Prime p , což umožňuje efektivní výpočet diskrétního logaritmu pomocí Pohlig – Hellmana, pokud je pořadí skupiny (přičemž p −1) dostatečně hladké , tj. Nemá žádné velké primární faktory .

Porovnání s celočíselnou faktorizací

Zatímco výpočet diskrétních logaritmů a faktoringových celých čísel jsou odlišné problémy, sdílejí některé vlastnosti:

• oba jsou speciálními případy problému skryté podskupiny pro konečné abelianské skupiny ,
• oba problémy se zdají být obtížné ( pro nekvantové počítače nejsou známy žádné účinné algoritmy ),
• pro oba problémy jsou známy efektivní algoritmy na kvantových počítačích,
• algoritmy z jednoho problému jsou často přizpůsobeny druhému a
• obtížnost obou problémů byla použita ke konstrukci různých kryptografických systémů.

Kryptografie

Existují skupiny, pro které je výpočet diskrétních logaritmů zjevně obtížný. V některých případech (např. Velké podskupiny primárních řádů skupin ( Z _p ) ^× ) neexistuje pouze účinný algoritmus známý pro nejhorší případ, ale složitost průměrného případu může být prokázána přibližně stejně tvrdá jako nejhorší případ pomocí náhodného samoredukovatelnost .

Přitom inverzní problém diskrétního umocnění není obtížný (lze jej efektivně vypočítat například pomocí umocnění umocněním ). Tato asymetrie je analogická s tou mezi celočíselnou faktorizací a celočíselným násobením . Obě asymetrie (a další možná jednosměrné funkce ) byly využity při konstrukci kryptografických systémů.

Populární volbou pro skupinu G v diskrétní logaritmové kryptografii (DLC) jsou cyklické skupiny ( Z _p ) ^× (např. Šifrování ElGamal , výměna klíčů Diffie – Hellman a algoritmus digitálního podpisu ) a cyklické podskupiny eliptických křivek nad konečnými poli ( viz. Kryptografie eliptické křivky ).

I když obecně neexistuje žádný veřejně známý algoritmus pro řešení problému diskrétního logaritmu, první tři kroky algoritmu síta číselného pole závisí pouze na skupině G , nikoli na konkrétních prvcích G, jejichž konečný protokol je požadovaný. Tím precomputing tyto tři kroky pro určitou skupinu, jeden nemusí provádět pouze poslední krok, který je mnohem méně výpočetně náročné než první tři, aby se získal specifický logaritmus v této skupině.

Ukazuje se, že velká část internetového provozu využívá jednu z hrstky skupin, které mají řádově 1024 bitů nebo méně, např. Cyklické skupiny s řadou prvočísel Oakley uvedených v RFC 2409. Útok Logjam použil tuto chybu zabezpečení ke kompromitaci různých internetových služeb. to umožňovalo použití skupin, jejichž pořadí bylo 512bitové prvočíslo, takzvaný exportní stupeň .

Autoři útoku Logjam odhadují, že mnohem obtížnější předpočítač potřebný k vyřešení problému s diskrétním logem pro 1024bitovou prime by byl v rozpočtu velké národní zpravodajské agentury , jako je americká Národní bezpečnostní agentura (NSA). Autoři Logjam spekulují, že za tvrzeními v uniklých dokumentech NSA, že NSA je schopna prolomit velkou část současné kryptografie , stojí předpočítání proti široce opakovaně používaným 1024 DH prvočíslům .

Reference

Další čtení

• Richard Crandall ; Carl Pomerance . Kapitola 5, Prvočísla: Výpočetní perspektiva , 2. vydání, Springer.
• Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3rd ed.), London: CRC Press , ISBN 978-1-58488-508-5

Viz také

• AW Faber Model 366
• Percy Ludgate a irský logaritmus