elliptic curve discrete logarithm problem

Angol

Főnév

elliptic curve discrete logarithm problem (tsz. elliptic curve discrete logarithm problems)

(informatika) A Elliptic Curve Discrete Logarithm Problem (ECDLP) a modern kriptográfia egyik legfontosabb és legnehezebb problémája. Ez az a matematikai probléma, amelyre az elliptikus görbéken alapuló kriptográfia (ECC) biztonsága épül. Az alábbiakban részletesen bemutatom az ECDLP lényegét, matematikai hátterét, nehézségét és szerepét a kriptográfiában.

🧠 1. Alapfogalmak

Az elliptikus görbéken definiált csoportművelet lehetővé teszi, hogy pontokat “összeadjunk”. Egy adott elliptikus görbe ${\textstyle E}$ egy test (általában véges test ${\textstyle \mathbb {F} _{p}}$ ) felett úgy néz ki, hogy:

$E:y^{2}=x^{3}+ax+b\quad {\text{mod }}p,\quad \Delta \neq 0$

Legyen ${\textstyle P}$ egy nem nulla pont a görbén, és legyen ${\textstyle k}$ egy egész szám. Definiáljuk:

$Q=kP=\underbrace {P+P+\dots +P} _{k{\text{ alkalommal}}}$

Ezt a műveletet pontszorzásnak nevezzük.

❓ 2. Mi az ECDLP?

Definíció (ECDLP):

Adott egy elliptikus görbe $E$ egy véges test felett, egy pont $P\in E$ és egy másik pont $Q\in E$ , ahol $Q=kP$ valamilyen ismeretlen egész $k$ -ra. Az ECDLP célja: megtalálni ezt a ${\textstyle k}$ -t.

Ez a diszkrét logaritmus megfelelője elliptikus görbéken:

${\text{ECDLP: }}{\text{Adott }}P{\text{ és }}Q=kP\Rightarrow {\text{keresd meg }}k{\text{-t}}$

🔐 3. Miért nehéz?

A pontszorzás egyirányú művelet:

Könnyű kiszámolni ${\textstyle kP}$ -t adott ${\textstyle k}$ és ${\textstyle P}$ esetén.
Nagyon nehéz visszafele meghatározni ${\textstyle k}$ -t adott ${\textstyle P}$ és ${\textstyle Q=kP}$ esetén, különösen, ha ${\textstyle k}$ nagy és a csoport rendje nagy prímszám.

Ez a trapdoor function jellemző: egyirányúan könnyű, de visszafelé nehéz.

A legjobb ismert algoritmusok az ECDLP-re exponenciális időbonyolultságúak:

Baby-step Giant-step: ${\textstyle O({\sqrt {n}})}$ idő és memória
Pollard’s Rho: ${\textstyle O({\sqrt {n}})}$ idő, de kevesebb memória

Nincs ismert polinomiális idejű algoritmus az ECDLP megoldására általánosan – ellentétben a hagyományos diszkrét logaritmussal, amit a subexponenciális index calculus módszer támadhat nagyobb hatékonysággal.

📊 4. ECDLP és biztonsági szintek

A kulcshossz a nehézséggel nő:

Biztonság (bit)	ECC kulcshossz	RSA kulcshossz
80-bit	160-bit	1024-bit
112-bit	224-bit	2048-bit
128-bit	256-bit	3072-bit
192-bit	384-bit	7680-bit

ECC előnye: kisebb kulcshosszal érhető el ugyanaz a biztonsági szint → gyorsabb, kevesebb memória.

💻 5. Gyakorlati alkalmazások

Az ECDLP az alábbi kriptográfiai rendszerek alapja:

ECDSA – Elliptic Curve Digital Signature Algorithm (pl. Bitcoin, TLS)
ECDH – Elliptic Curve Diffie–Hellman kulcscsere
ECIES – Elliptic Curve Integrated Encryption Scheme

🧪 6. Kód-példa Pythonban (pontszorzás)

# Egyszerű pontszorzás elliptikus görbén (mod p)
def inverse_mod(k, p):
    return pow(k, -1, p)

def point_add(P, Q, a, p):
    if P == 'O': return Q
    if Q == 'O': return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2: return 'O'
    if P != Q:
        m = ((y2 - y1) * inverse_mod(x2 - x1, p)) % p
    else:
        m = ((3 * x1**2 + a) * inverse_mod(2 * y1, p)) % p
    x3 = (m**2 - x1 - x2) % p
    y3 = (m * (x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mult(k, P, a, p):
    R = 'O'
    while k:
        if k & 1:
            R = point_add(R, P, a, p)
        P = point_add(P, P, a, p)
        k >>= 1
    return R

⚠️ 7. Támadások és védekezés

Side-channel támadások: időzítés, áramfogyasztás → védekezés: konstans idejű algoritmusok
Gyenge görbék: rosszul választott görbék lehetővé teszik az ECDLP gyors megoldását (pl. supersingular görbék)
MOV támadás: bizonyos görbéken az ECDLP áttehető a véges mezős DLP-re

Megoldás: csak biztonságos, szabványos görbéket használjunk (pl. Curve25519, secp256r1, NIST P-256)

🧮 8. ECDLP és kvantumszámítógép

A Shor-algoritmus kvantumszámítógépen polinomiális időben megoldja az ECDLP-t.

Ez azt jelenti, hogy ha a kvantumszámítógépek elég nagyok lesznek, minden ma használt ECC rendszer törhetővé válik.

Ezért folyik a kutatás poszt-kvantum kriptográfia irányába.

📌 9. Összefoglalás

Fogalom	Magyarázat
ECDLP	Kiszámítani ${\textstyle k}$ -t, ha ${\textstyle Q=kP}$ ismert
Nehézség	Nincs gyors algoritmus → biztonságos
Alkalmazások	ECDSA, ECDH, ECIES
Védelem	Biztonságos görbe, konstans idő, oldaltámadások kivédése
Kvantum fenyegetés	Shor-algoritmus veszélyt jelent az ECC-re

További információk

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