discrete logarithm problem

Angol

Főnév

discrete logarithm problem (tsz. discrete logarithm problems)

1. (informatika) A diszkrét logaritmus probléma (Discrete Logarithm Problem, DLP) egy alapvető nehézségen alapuló feladat a számelméletben és a kriptográfiában. Lényege, hogy adott legyen egy csoport ${\textstyle G}$, benne egy generátor (alap) ${\textstyle g}$ és egy elem ${\textstyle h}$; a kérdés, hogy mely egész ${\textstyle x}$ értékére teljesül

$$g^{x}=h\,?$$

Másképp: ${\textstyle x=\log _{g}h}$ mod csoportrend.

---

1. Formális leírás

• Leggyakoribb eset: ${\textstyle G=\mathbb {Z} _{p}^{*}}$, a prím ${\textstyle p}$ maradékosztályainak multiplikatív csoportja, ${\textstyle \;|G|=p-1}$.

• Adott: prím ${\textstyle p}$, generátor ${\textstyle g\in \mathbb {Z} _{p}^{*}}$, és ${\textstyle h\in \langle g\rangle }$.

• Keresett: ${\textstyle x\in \{0,1,\dots ,p-2\}}$ úgy, hogy

  $$g^{x}\;\equiv \;h{\pmod {p}}.$$

A probléma úgy is feltehető elliptikus görbe csoporton (Elliptic Curve Discrete Logarithm), ahol a művelet ponthalmaz és pontösszeadás.

---

2. Miért nehéz?

• A DLP döntési verziója (${\textstyle g^{x}=h}$ megoldható-e?) könnyen ellenőrizhető, ha valaki megad egy ${\textstyle x}$-et (polinomiális időben ellenőrizhető a hatványozás), így a probléma NP-ben van.
• Ellentétben a hagyományos logaritmussal a véges testbeli torzult hatványozás inverze nem ismert, és nincs ismert polinomiális algoritmus általános esetben (feltételezhetően nehéz).

---

3. Fő algoritmusok

1. Baby‐step Giant‐step (Shanks)
   • Idő: ${\textstyle O({\sqrt {n}})}$, memória: ${\textstyle O({\sqrt {n}})}$, ahol ${\textstyle n=|G|}$.
   • Felosztjuk ${\textstyle x=i\,m+j}$ formára, ${\textstyle m\approx \lceil {\sqrt {n}}\rceil }$, és táblázatban előre kiszámoljuk a „baby‐lépéseket” ${\textstyle g^{j}}$, majd a „óriás‐lépésekkel” keressük a találatot.
2. Pollard-féle ρ‐algoritmus
   • Idő: ${\textstyle O({\sqrt {n}})}$, memória: ${\textstyle O(1)}$.
   • Véletlen determinisztikus iterációt használ egy előre definiált partícióval; ütközés (két azonos elem) alapján visszafejtjük az exponensek különbségét.
3. Index‐calculus módszerek
   • Speciális csoportokra (például ${\textstyle \mathbb {F} _{p}^{*}}$, de nem elliptikus görbékre) ${\textstyle L_{p}[1/3]}$ alsó futásidejű eljárások.
   • Megfontolás: kis „alap‐prím” faktorizációkat gyűjtünk, lineáris egyenletrendszert oldunk meg a logaritmusokra.
4. Elliptikus görbe esetén
   • Nincs hatékony index‐calculus; legjobb általános eljárások Pollard‐ρ típusúak, ${\textstyle O({\sqrt {n}})}$.

---

4. Kriptográfiai alkalmazások

1. Diffie–Hellman kulcscsere

   $$A:K_{A}=g^{a},\quad B:K_{B}=g^{b},\quad {\text{közös kulcs: }}g^{ab}.$$

   A biztonság alapja, hogy a támadó ne tudja kiszámolni ${\textstyle a}$-t ${\textstyle g^{a}}$-ból (DLP), illetve ${\textstyle g^{ab}}$-ból ${\textstyle g^{a}}$ és ${\textstyle g^{b}}$ ismeretében (Computational Diffie–Hellman).

2. ElGamal aláírás és titkosítás

   • Eljárások, melyek biztonsága a DLP nehézségén nyugszik.

3. Elliptikus görbe kriptográfia (ECC)

   • Kisebb kulcshossz elég azonos biztonsági szinthez, mert az elliptikus DLP nehezebb.

---

5. Biztonsági paraméterek és kihívások

• Kulcsméret:
  • ${\textstyle \mathbb {Z} _{p}^{*}}$ esetén: 2048 bit (min.) a mai biztonsági szinthez.
  • ECC esetén: 256 bit körül optimális.
• Kvantumszámítógépek:
  • Shor‐algoritmus polinomiális idejű faktorizációt és DLP‐t tesz lehetővé: a klasszikus DLP‐alapú rendszerek jövője kvantumellenes (post‐quantum) eljárások felé tolódik.

---

Összefoglalás

A diszkrét logaritmus probléma az a feladat, hogy véges csoportban visszafejtsük a hatványozás exponensét. Gyakorlatilag nehéz, és e nehézségre épül a Diffie–Hellman, ElGamal és az elliptikus görbe kriptográfia. A legismertebb eljárások ${\textstyle {\sqrt {n}}}$-es futásidejűek (Shanks, Pollard‐ρ), speciális csoportokra pedig index‐calculus módszerek gyorsabbak, de elliptikus görbéknél ezek nem alkalmazhatók – így ECC ma is rendkívül hatékony és népszerű megoldás.

További információk

• discrete logarithm problem - Szótár.net (en-hu)
• discrete logarithm problem - Sztaki (en-hu)
• discrete logarithm problem - Merriam–Webster
• discrete logarithm problem - Cambridge
• discrete logarithm problem - WordNet
• discrete logarithm problem - Яндекс (en-ru)
• discrete logarithm problem - Google (en-hu)
• discrete logarithm problem - Wikidata
• discrete logarithm problem - Wikipédia (angol)