Ugrás a tartalomhoz

ElGamal encryption

A Wikiszótárból, a nyitott szótárból
(ElGamal szócikkből átirányítva)

Angol


Főnév

ElGamal encryption (tsz. ElGamal encryptions)

  1. (informatika) Az ElGamal titkosítási rendszer egy aszimmetrikus kriptográfiai algoritmus, amelyet Taher ElGamal publikált 1985-ben. Az algoritmus a Diffie–Hellman kulcscsere matematikai alapjain nyugszik, és egyike a legelső nyilvános kulcsú titkosítási rendszereknek, amely biztonságos titkosítást nyújt egy publikus kulcs segítségével, míg a visszafejtés csak a privát kulccsal lehetséges.

Az ElGamal rendszer egyszerű, bizonyítottan biztonságos (a diszkrét logaritmus problémára épül), és támogatja a homomorf tulajdonságokat is, ami azt jelenti, hogy a titkosított adatokon végezhetők bizonyos számítások anélkül, hogy visszafejtenénk őket. Hátránya viszont, hogy nagyobb a kimeneti mérete, mint a bemeneté, és a titkosítás/visszafejtés lassabb, mint például RSA vagy ECC esetében.


🧠 Alapfogalom: Aszimmetrikus titkosítás

  • Két külön kulcsot használ: egy nyilvános kulcsot (public key), amelyet bárki ismerhet, és egy privát kulcsot (private key), amelyet csak a tulajdonos ismer.
  • A titkosítás a nyilvános kulccsal történik.
  • A visszafejtés kizárólag a privát kulccsal végezhető el.
  • Az ElGamal ezen elven működik, és a diszkrét logaritmus problémán alapul, amely nehézsége adja a rendszer biztonságát.


🔐 ElGamal rendszer – áttekintés

Az ElGamal titkosítás a moduláris aritmetikán alapul, és a Zₚ* csoporton belül dolgozik, ahol p egy nagy prímszám.

Paraméterek:

  • p: egy nagy prímszám (pl. 2048 bit)
  • g: egy primitív gyök mod p szerint (generátor)
  • x: a privát kulcs, egy véletlenszerű egész szám 1 < x < p−1
  • y = g^x mod p: a nyilvános kulcs része

Kulcspár:

  • Privát kulcs: x
  • Nyilvános kulcs: (p, g, y)


📦 Titkosítás menete

Tegyük fel, hogy Alice szeretne Bobnak üzenetet küldeni.

  1. Bob rendelkezik egy nyilvános kulccsal: (p, g, y).
  2. Alice kiválaszt egy véletlenszerű számot k (1 < k < p−1), amely minden üzenetnél új kell legyen.
  3. Az üzenetet (m) a következőképp titkosítja:
    • c1 = g^k mod p
    • c2 = m · y^k mod p
  4. A titkosított üzenet (ciphertext): (c1, c2)


🔓 Visszafejtés

Bob a saját privát kulcsával x visszafejti a titkosítást:

  1. s = c1^x mod p (ugyanaz, mint y^k, mivel y = g^x)
  2. Számolja s⁻¹ mod p – az s multiplikatív inverzét modulo p
  3. Az eredeti üzenet: m = c2 · s⁻¹ mod p


🧮 Matematikai háttér

A biztonság alapja a diszkrét logaritmus probléma:

Adott g és y = g^x mod p, nagyon nehéz x-et kiszámolni, ha p elég nagy.

Ez a probléma jelenleg nem oldható meg hatékonyan klasszikus számítógépeken, így a rendszer kriptográfiailag biztonságos, feltéve, hogy a kulcshossz megfelelő (legalább 2048 bit).


✅ Előnyök

Előny Magyarázat
Egyszerűség Könnyen implementálható, matematikailag tiszta
Bizonyított biztonság A diszkrét logaritmus problémára épül
Homomorf titkosítás Titkosított szorzás → visszafejtés után szorzott érték
Aszimmetrikus Nem kell előzetes kulcscsere, bárki titkosíthat a publikus kulccsal


⚠️ Hátrányok

Hátrány Miért?
Lassabb, mint pl. RSA vagy ECC Műveletek sok moduláris exponenciálást igényelnek
Ciphertext bővülés A titkosított üzenet kétszer akkora, mint a bemeneti üzenet
Nem determinisztikus Azonos üzenet mindig más ciphertextet ad (ez biztonságos viszont)


🧪 Homomorf tulajdonság

Az ElGamal egy multiplikatív homomorf rendszer, vagyis:

  • E(m1) · E(m2) = E(m1 * m2)
  • Ez lehetővé teszi műveletek végrehajtását titkosított adatokon, amit például titkosított szavazásoknál, biztonságos számításoknál használnak.


🛠️ Példa Pythonban (egyszerűsítve, csak szemléltetés)

from Crypto.Util.number import getPrime, inverse
import random

# Paraméterek
p = getPrime(256)
g = 2

x = random.randint(1, p-2)        # Privát kulcs
y = pow(g, x, p)                  # Nyilvános kulcs komponens

# Üzenet
m = 123456789

# Titkosítás
k = random.randint(1, p-2)
c1 = pow(g, k, p)
s = pow(y, k, p)
c2 = (m * s) % p
ciphertext = (c1, c2)

# Visszafejtés
s_dec = pow(c1, x, p)
s_inv = inverse(s_dec, p)
m_decrypted = (c2 * s_inv) % p

print("Eredeti:", m)
print("Visszafejtve:", m_decrypted)

🔒 Biztonsági megfontolások

Probléma Megoldás
K újrahasználása k mindig véletlenszerű és egyszer használatos kell legyen!
Diszkrét logaritmus támadások Nagy p szükséges (legalább 2048 bit)
Chosen Ciphertext Attack (CCA) Ajánlott CCA-biztos verziót használni (pl. ElGamal + MAC vagy AEAD kombinációval)


📚 Alkalmazások

Terület Funkció
OpenPGP / GPG Levelek, fájlok titkosítása
e-voting rendszerek Homomorf titkosítás miatt népszerű
Digitális aláírások ElGamal aláírás (külön változat, nem azonos az encrypttel)
Tanulmányi cél Egyszerűség miatt gyakori példarendszer oktatásban


🧠 Összefoglalás

Fogalom Jelentés
ElGamal titkosítás Aszimmetrikus titkosító algoritmus
Alapja Diszkrét logaritmus probléma
Kulcspár Nyilvános: (p, g, y), Privát: x
Titkosítás (c1, c2) = (g^k mod p, m * y^k mod p)
Visszafejtés m = c2 * (c1^x)^-1 mod p
Előnyök Biztonságos, homomorf, nyílt kulcsú
Hátrányok Lassú, nagy kimenet, random k szükséges
Használat PGP, tanulmány, e-voting, biztonságos kommunikáció


Az ElGamal mára klasszikusnak számít a kriptográfiában: egyszerű, mégis nagyon hatékony matematikai struktúrára épül, és jó kiindulópont az aszimmetrikus kriptográfia megértéséhez.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=ElGamal_encryption&oldid=3494236”