ElGamal encryption

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.

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

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.

• 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

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

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)

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

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

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.

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)

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.

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