# ElGamal

## ElGamal

### 📌 Classificação

* **Categoria:** Criptografia Assimétrica / Cifragem e Assinaturas
* **Criado por:** Taher ElGamal (1985)
* **Base Matemática:** Problema do Logaritmo Discreto (DLP)
* **Status:** ✅ Funcional (mas menos comum que RSA/ECC)

***

### 🎯 Descrição Geral

**ElGamal** é um sistema de criptografia assimétrica baseado no **problema do logaritmo discreto**, similar ao Diffie-Hellman. Diferente do RSA (que usa fatoração), ElGamal utiliza a mesma base matemática do Diffie-Hellman para oferecer **cifragem de mensagens** (não apenas troca de chaves).

```
┌─────────────────────────────────────────────────────────────┐
│                         ELGAMAL                              │
│                                                              │
│   Cifragem:   Mensagem + Chave Pública → Cifrado (c1, c2)   │
│   Decifragem: Cifrado + Chave Privada → Mensagem Original   │
│                                                              │
│   Assinatura: Mensagem + Chave Privada → Assinatura (r, s)  │
│   Verificação: Mensagem + Assinatura + Chave Pública → Válido│
└─────────────────────────────────────────────────────────────┘
```

#### Analogia

> *"ElGamal é como enviar um cadeado em uma caixa: o remetente coloca a mensagem em uma caixa, tranca com o cadeado público, mas só o dono da chave privada pode abrir. O diferencial é que cada mensagem usa um cadeado descartável diferente."*

***

### ⚙️ Como Funciona (Matemática)

#### Geração de Chaves

```python
def elgamal_keygen():
    # 1. Escolher um primo grande p
    p = gerar_primo_grande()
    
    # 2. Escolher um gerador g (raiz primitiva módulo p)
    g = encontrar_gerador(p)
    
    # 3. Escolher chave privada x (1 < x < p-1)
    x = random.randint(2, p-2)
    
    # 4. Calcular chave pública y = g^x mod p
    y = pow(g, x, p)
    
    # Chave pública: (p, g, y)
    # Chave privada: x
    
    return (p, g, y), x
```

#### Cifragem

```python
def elgamal_encrypt(message, public_key):
    p, g, y = public_key
    
    # 1. Escolher número aleatório k (1 < k < p-1)
    k = random.randint(2, p-2)
    
    # 2. Calcular a = g^k mod p
    a = pow(g, k, p)
    
    # 3. Calcular b = (y^k * M) mod p
    #    onde M é a mensagem convertida para número
    M = string_to_int(message)
    b = (pow(y, k, p) * M) % p
    
    # 4. Cifrado é o par (a, b)
    return (a, b)
```

#### Decifragem

```python
def elgamal_decrypt(ciphertext, private_key, public_key):
    a, b = ciphertext
    p, g, y = public_key
    x = private_key
    
    # Calcular a^{-x} mod p (inverso multiplicativo)
    a_inv = pow(a, -x, p)  # Python 3.8+ com inverso modular
    
    # Recuperar mensagem: M = b * a^{-x} mod p
    M = (b * a_inv) % p
    
    return int_to_string(M)
```

#### Demonstração Matemática

```
Cifragem:
a = g^k mod p
b = M * y^k mod p

Decifragem:
b * a^{-x} = M * y^k * (g^k)^{-x} = M * (g^x)^k * g^{-kx} = M * g^{xk} * g^{-kx} = M

Resultado: A mensagem original é recuperada!
```

***

### 🔢 Exemplo Numérico (Pequeno)

```python
# Parâmetros (pequenos para exemplo)
p = 23
g = 5

# Geração de chaves
x = 6  # chave privada
y = pow(5, 6, 23)  # 5^6 mod 23 = 15625 mod 23 = 8

print(f"Chave pública: p={p}, g={g}, y={y}")
print(f"Chave privada: x={x}")

# Cifragem (mensagem M = 10)
M = 10
k = 3  # número aleatório

a = pow(5, 3, 23)  # 5^3 = 125 mod 23 = 10
b = (pow(8, 3, 23) * 10) % 23  # 8^3 = 512 mod 23 = 6, 6*10=60 mod 23=14

print(f"Cifrado: a={a}, b={b}")

# Decifragem
a_inv = pow(10, -6, 23)  # 10^{-6} mod 23
M_rec = (14 * a_inv) % 23

print(f"Mensagem recuperada: {M_rec}")  # 10 ✅
```

***

### ✍️ Assinatura ElGamal

ElGamal também pode ser usado para **assinaturas digitais** (base do DSA).

#### Geração de Assinatura

```python
def elgamal_sign(message, private_key, public_key):
    p, g, y = public_key
    x = private_key
    
    # 1. Escolher k aleatório (1 < k < p-1, coprimo com p-1)
    k = random.randint(2, p-2)
    while math.gcd(k, p-1) != 1:
        k = random.randint(2, p-2)
    
    # 2. Calcular r = g^k mod p
    r = pow(g, k, p)
    
    # 3. Calcular hash da mensagem
    h = hash(message) % (p-1)
    
    # 4. Calcular s = k^{-1} * (h - x*r) mod (p-1)
    k_inv = mod_inverse(k, p-1)
    s = (k_inv * (h - x * r)) % (p-1)
    
    return (r, s)
```

#### Verificação de Assinatura

```python
def elgamal_verify(message, signature, public_key):
    r, s = signature
    p, g, y = public_key
    
    # 1. Calcular hash da mensagem
    h = hash(message) % (p-1)
    
    # 2. Verificar: y^r * r^s ≡ g^h (mod p)
    left = (pow(y, r, p) * pow(r, s, p)) % p
    right = pow(g, h, p)
    
    return left == right
```

***

### 💻 Exemplos Práticos

#### Exemplo 1 – ElGamal Básico em Python

```python
import random

def generate_keys(bits=512):
    """Gerar chaves ElGamal"""
    # Gerar primo p (simplificado - use biblioteca em produção)
    p = 23  # primo pequeno para exemplo
    g = 5   # gerador
    
    # Chave privada
    x = random.randint(2, p-2)
    
    # Chave pública
    y = pow(g, x, p)
    
    return (p, g, y), x

def encrypt(message, public_key):
    p, g, y = public_key
    m = int.from_bytes(message.encode(), 'big')
    
    # k aleatório
    k = random.randint(2, p-2)
    
    a = pow(g, k, p)
    b = (pow(y, k, p) * m) % p
    
    return (a, b)

def decrypt(ciphertext, private_key, public_key):
    a, b = ciphertext
    p, g, y = public_key
    x = private_key
    
    # Calcular inverso
    a_inv = pow(a, -x, p)
    m = (b * a_inv) % p
    
    # Converter de volta para string
    return m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()

# Exemplo de uso
pub_key, priv_key = generate_keys()
print(f"Chave pública: {pub_key}")
print(f"Chave privada: {priv_key}")

message = "Mensagem Secreta!"
print(f"Original: {message}")

cipher = encrypt(message, pub_key)
print(f"Cifrado: a={cipher[0]}, b={cipher[1]}")

decrypted = decrypt(cipher, priv_key, pub_key)
print(f"Decifrado: {decrypted}")
```

#### Exemplo 2 – ElGamal com Python (Biblioteca)

```python
# pip install pycryptodome
from Crypto.PublicKey import ElGamal
from Crypto.Math.Primality import generate_probable_prime
from Crypto.Random import random
import Crypto.Random

def elgamal_demo():
    # Gerar parâmetros (p, g)
    p = generate_probable_prime(512)  # primo de 512 bits
    g = 2
    
    # Gerar chaves
    key = ElGamal.generate(p, g)
    private_key = key
    public_key = key.publickey()
    
    print(f"Parâmetros: p={p}, g={g}")
    print(f"Chave pública: y={public_key.y}")
    
    # Mensagem (como número)
    message = 123456789
    
    # Cifrar
    k = random.StrongRandom().randint(1, p-2)
    ciphertext = public_key.encrypt(message, k)
    print(f"Cifrado: {ciphertext}")
    
    # Decifrar
    decrypted = private_key.decrypt(ciphertext)
    print(f"Decifrado: {decrypted}")
    
    assert message == decrypted

if __name__ == "__main__":
    elgamal_demo()
```

#### Exemplo 3 – ElGamal para Cifragem de Strings

```python
import random

class ElGamalCipher:
    def __init__(self, p, g, x):
        self.p = p
        self.g = g
        self.x = x
        self.y = pow(g, x, p)
    
    def encrypt_char(self, m):
        """Cifrar um caractere"""
        k = random.randint(2, self.p-2)
        a = pow(self.g, k, self.p)
        b = (pow(self.y, k, self.p) * m) % self.p
        return (a, b)
    
    def decrypt_char(self, cipher):
        a, b = cipher
        a_inv = pow(a, -self.x, self.p)
        return (b * a_inv) % self.p
    
    def encrypt_string(self, message):
        """Cifrar string completa"""
        return [self.encrypt_char(ord(c)) for c in message]
    
    def decrypt_string(self, ciphertext):
        """Decifrar string completa"""
        return ''.join(chr(self.decrypt_char(c)) for c in ciphertext)

# Exemplo
p = 23
g = 5
x = 6

cipher = ElGamalCipher(p, g, x)
message = "HELLO"
print(f"Mensagem original: {message}")

encrypted = cipher.encrypt_string(message)
print(f"Cifrado: {encrypted}")

decrypted = cipher.decrypt_string(encrypted)
print(f"Decifrado: {decrypted}")
```

#### Exemplo 4 – Comparação: ElGamal vs RSA

```python
import time
import random

def compare_elgamal_rsa():
    """Comparar desempenho ElGamal vs RSA"""
    
    # ElGamal (512 bits)
    p_elgamal = 23  # simplificado
    g = 5
    x_elgamal = 6
    
    # RSA (simplificado)
    # p=61, q=53, n=3233, e=17, d=2753
    
    # Teste de cifragem
    messages = [random.randint(1, 100) for _ in range(100)]
    
    start = time.time()
    # Cifragem ElGamal
    # ...
    elgamal_time = time.time() - start
    
    start = time.time()
    # Cifragem RSA
    # ...
    rsa_time = time.time() - start
    
    print(f"ElGamal: {elgamal_time:.4f}s")
    print(f"RSA: {rsa_time:.4f}s")
    print("Nota: ElGamal produz cifrados 2x maiores que RSA")

# Nota: ElGamal produz ciphertext de tamanho dobrado (a, b)
# enquanto RSA produz ciphertext de tamanho único
```

#### Exemplo 5 – Assinatura ElGamal

```python
import random
import hashlib

def mod_inverse(a, m):
    """Inverso modular usando Euclides estendido"""
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise ValueError("Inverso não existe")
    return x % m

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y

def elgamal_sign(message, private_key, public_key):
    p, g, y = public_key
    x = private_key
    
    # Hash da mensagem
    h = int(hashlib.sha256(message.encode()).hexdigest(), 16) % (p-1)
    
    # Escolher k aleatório (coprimo com p-1)
    k = random.randint(2, p-2)
    while math.gcd(k, p-1) != 1:
        k = random.randint(2, p-2)
    
    # Calcular r = g^k mod p
    r = pow(g, k, p)
    
    # Calcular s = k^{-1} * (h - x*r) mod (p-1)
    k_inv = mod_inverse(k, p-1)
    s = (k_inv * (h - x * r)) % (p-1)
    
    return (r, s)

def elgamal_verify(message, signature, public_key):
    r, s = signature
    p, g, y = public_key
    
    # Hash da mensagem
    h = int(hashlib.sha256(message.encode()).hexdigest(), 16) % (p-1)
    
    # Verificar: y^r * r^s ≡ g^h (mod p)
    left = (pow(y, r, p) * pow(r, s, p)) % p
    right = pow(g, h, p)
    
    return left == right

# Exemplo
p = 23
g = 5
x = 6
y = pow(g, x, p)
public_key = (p, g, y)

message = "Documento importante"
signature = elgamal_sign(message, x, public_key)
print(f"Assinatura: r={signature[0]}, s={signature[1]}")

is_valid = elgamal_verify(message, signature, public_key)
print(f"Assinatura válida: {is_valid}")

# Tentar modificar mensagem
message_tampered = "Documento importante (modificado)"
is_valid = elgamal_verify(message_tampered, signature, public_key)
print(f"Mensagem alterada - válida: {is_valid}")
```

***

### ⚠️ Vulnerabilidades e Ataques

#### 1. Reutilização de k (Mesmo erro fatal do ECDSA)

```python
# Se o mesmo k for usado para duas mensagens diferentes:
# (a1, b1) e (a2, b2) com mesmo k

# Então: b1/b2 = M1/M2 (mod p)
# O atacante pode recuperar M1 se conhecer M2

# Mitigação: nunca reutilizar k!
```

#### 2. k Fraco ou Previsível

Se `k` for pequeno ou previsível, o sistema é vulnerável a ataques de força bruta.

**Mitigação:** Usar gerador criptograficamente seguro.

#### 3. Logjam Attack (mesmo do DH)

Grupos fracos (p pequeno) são vulneráveis.

**Mitigação:** Usar primos grandes (≥2048 bits).

#### 4. Ataque de Homem no Meio (MITM)

ElGamal puro não autentica as partes.

**Mitigação:** Assinar as chaves públicas.

#### 5. Ataque de Subgrupo

Se `g` não for gerador de um grupo grande, o atacante pode reduzir o espaço de busca.

**Mitigação:** Usar geradores de ordem prima.

***

### 📊 ElGamal vs RSA vs ECC

| Característica                  | ElGamal            | RSA              | ECC                   |
| ------------------------------- | ------------------ | ---------------- | --------------------- |
| **Base matemática**             | Logaritmo discreto | Fatoração        | Curvas elípticas      |
| **Tamanho da chave (128 bits)** | 3072 bits          | 3072 bits        | 256 bits              |
| **Tamanho do ciphertext**       | 2× tamanho chave   | 1× tamanho chave | 2× tamanho chave      |
| **Aleatoriedade necessária**    | ✅ Sim (k)          | ❌ Não            | ✅ Sim (ECDSA)         |
| **Cifragem**                    | ✅ Sim              | ✅ Sim            | ❌ Não (só assinatura) |
| **Assinatura**                  | ✅ Sim              | ✅ Sim            | ✅ Sim                 |
| **Velocidade (cifragem)**       | Média              | Rápida           | N/A                   |
| **Velocidade (assinatura)**     | Média              | Lenta            | Rápida                |

***

### 📈 Tamanhos Recomendados

| Nível de Segurança | Tamanho p (bits) | Tamanho ciphertext (bits) |
| ------------------ | ---------------- | ------------------------- |
| 80 bits            | 1024 bits        | 2048 bits                 |
| 112 bits           | 2048 bits        | 4096 bits                 |
| 128 bits           | 3072 bits        | 6144 bits                 |
| 192 bits           | 7680 bits        | 15360 bits                |
| 256 bits           | 15360 bits       | 30720 bits                |

***

### 🎯 Aplicações do ElGamal

| Aplicação                    | Uso                                    |
| ---------------------------- | -------------------------------------- |
| **GnuPG (OpenPGP)**          | Cifragem de chave de sessão (opcional) |
| **Cryptlib**                 | Implementação de cifragem assimétrica  |
| **Sistemas acadêmicos**      | Ensino e pesquisa                      |
| **Criptomoedas (variantes)** | Esquemas de compromisso                |
| **Votação eletrônica**       | Cifragem homomórfica                   |

***

### 🔗 Links Úteis

* [Original Paper - Taher ElGamal (1985)](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.476.9482)
* [RFC 4880 - OpenPGP (ElGamal support)](https://tools.ietf.org/html/rfc4880)
* [Crypto++ ElGamal](https://www.cryptopp.com/wiki/ElGamal)

***

### ⚠️ Aviso

> ElGamal é um algoritmo criptográfico. Este documento é para **fins educacionais**. Em aplicações reais, prefira **RSA (para compatibilidade)** ou **ECC (para eficiência)** . O ElGamal moderno é mais comum em sua variante **ElGamal sobre curvas elípticas (ECC)**.

***

### 🎯 Resumo Rápido

| Ponto              | Resumo                                                            |
| ------------------ | ----------------------------------------------------------------- |
| **Função**         | Cifragem e assinatura digital                                     |
| **Base**           | Logaritmo discreto                                                |
| **Tamanho mínimo** | 2048 bits (p)                                                     |
| **Vantagem**       | Aleatoriedade (semana, mas pode ser vantagem em alguns contextos) |
| **Desvantagem**    | Ciphertext dobra de tamanho                                       |
| **Uso moderno**    | Principalmente em sua variante ECC (ElGamal sobre curvas)         |
| **Recomendação**   | Prefira RSA ou ECC para novos projetos                            |


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xmorte.gitbook.io/bibliadopentestbr/conceitos/criptografia/assimetrica/elgamal.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.