elliptic curve discrete logarithm problem

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

1. (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.

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:

$${\displaystyle 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:

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

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

Definíció (ECDLP):

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

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

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

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.

A kulcshossz a nehézséggel nő:

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

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

# 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

• 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)

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.

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

• 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)