# DSA (Digital Signature Algorithm)

### 📌 Classificação

* **Categoria:** Criptografia Assimétrica / Assinaturas Digitais
* **Padrão:** FIPS 186-5 (NIST)
* **Criado por:** NIST (National Institute of Standards and Technology) - 1991
* **Base Matemática:** Problema do Logaritmo Discreto (DLP)
* **Status:** ⚠️ Permitido, mas sendo substituído por ECDSA/EdDSA

***

### 🎯 Descrição Geral

**DSA (Digital Signature Algorithm)** é um algoritmo de **assinatura digital** padronizado pelo governo dos EUA. Diferente do RSA (que pode fazer cifragem e assinatura), o DSA foi projetado **exclusivamente para assinaturas** — não pode ser usado para cifragem de mensagens.

```
┌─────────────────────────────────────────────────────────────┐
│                         DSA                                  │
│                                                              │
│   Mensagem + Chave Privada ──► DSA ──► Assinatura (r, s)    │
│                                                              │
│   Mensagem + Chave Pública + Assinatura ──► Válido/Inválido │
└─────────────────────────────────────────────────────────────┘
```

#### Analogia

> *"DSA é como um carimbo digital que só pode ser usado para autenticar documentos — não para trancar cofres. É especialista em uma única tarefa: provar que foi você quem assinou."*

***

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

#### Parâmetros do DSA

O DSA requer parâmetros públicos compartilhados:

```python
# 1. Escolher um primo grande p (1024-3072 bits)
p = primo_grande

# 2. Escolher um primo q que divide p-1 (160-256 bits)
q = primo_divisor_de_p-1  # q tem 160-256 bits

# 3. Escolher gerador g
#    g = h^{(p-1)/q} mod p, onde 1 < h < p-1
h = random.randint(2, p-2)
g = pow(h, (p-1)//q, p)

# Parâmetros públicos: (p, q, g)
```

#### Geração de Chaves

```python
def dsa_keygen(p, q, g):
    # 1. Escolher chave privada x (1 < x < q)
    x = random.randint(2, q-1)
    
    # 2. Calcular chave pública y = g^x mod p
    y = pow(g, x, p)
    
    return (x), (y)  # privada, pública
```

#### Geração de Assinatura

```python
def dsa_sign(message, private_key_x, p, q, g):
    # 1. Calcular hash da mensagem
    h = hashlib.sha256(message).digest()
    z = int.from_bytes(h, 'big') % q
    
    # 2. Escolher k aleatório (1 < k < q)
    #    NUNCA reutilizar k!
    k = random.randint(2, q-1)
    
    # 3. Calcular r = (g^k mod p) mod q
    r = pow(g, k, p) % q
    if r == 0:
        return dsa_sign(message, private_key_x, p, q, g)
    
    # 4. Calcular s = k^{-1} * (z + x*r) mod q
    k_inv = mod_inverse(k, q)
    s = (k_inv * (z + private_key_x * r)) % q
    if s == 0:
        return dsa_sign(message, private_key_x, p, q, g)
    
    return (r, s)
```

#### Verificação de Assinatura

```python
def dsa_verify(message, signature, public_key_y, p, q, g):
    r, s = signature
    
    # 1. Validar 0 < r < q e 0 < s < q
    if not (0 < r < q and 0 < s < q):
        return False
    
    # 2. Calcular hash da mensagem
    h = hashlib.sha256(message).digest()
    z = int.from_bytes(h, 'big') % q
    
    # 3. Calcular w = s^{-1} mod q
    w = mod_inverse(s, q)
    
    # 4. Calcular u1 = (z * w) mod q
    u1 = (z * w) % q
    
    # 5. Calcular u2 = (r * w) mod q
    u2 = (r * w) % q
    
    # 6. Calcular v = ((g^{u1} * y^{u2}) mod p) mod q
    v = (pow(g, u1, p) * pow(public_key_y, u2, p)) % p % q
    
    # 7. Verificar se v == r
    return v == r
```

***

### 🔢 Exemplo Numérico (Pequeno)

```python
# Parâmetros (pequenos para exemplo)
p = 23
q = 11  # 11 divide 22 (p-1)
g = 4   # 4^(22/11)=4^2=16 mod 23 = 16 (gerador do subgrupo de ordem q)

# Geração de chaves
x = 6  # chave privada
y = pow(4, 6, 23)  # 4^6 mod 23 = 4096 mod 23 = 2

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

# Assinatura (mensagem hash z = 7)
z = 7
k = 3

r = pow(4, 3, 23) % 11  # 4^3=64 mod 23=18, 18 mod 11=7
print(f"r={r}")

k_inv = pow(3, -1, 11)  # 3^{-1} mod 11 = 4
s = (4 * (7 + 6*7)) % 11  # (7 + 42) = 49, 49*4=196 mod 11=9
print(f"s={s}")

print(f"Assinatura: ({r}, {s})")

# Verificação
w = pow(9, -1, 11)  # 9^{-1} mod 11 = 5
u1 = (7 * 5) % 11  # 35 mod 11 = 2
u2 = (7 * 5) % 11  # 2
v = (pow(4, 2, 23) * pow(2, 2, 23)) % 23 % 11
# 4^2=16, 2^2=4, 16*4=64 mod 23=18, 18 mod 11=7
print(f"v={v}")

print(f"Assinatura válida: {v == r}")  # True
```

***

### 📏 Tamanhos de Chave DSA (NIST)

| Nível de Segurança | Tamanho p (bits) | Tamanho q (bits) | Status                       |
| ------------------ | ---------------- | ---------------- | ---------------------------- |
| 80 bits            | 1024 bits        | 160 bits         | ❌ Obsoleto (quebrado)        |
| 112 bits           | 2048 bits        | 224 bits         | ⚠️ Permitido (desencorajado) |
| 128 bits           | 3072 bits        | 256 bits         | ✅ Recomendado                |
| 192 bits           | 7680 bits        | 384 bits         | ✅ Alto nível                 |
| 256 bits           | 15360 bits       | 512 bits         | ✅ Máximo                     |

#### Evolução dos Tamanhos

```
Ano  | Tamanho Mínimo | Status
-----|----------------|--------
1991 | 512 bits p     | ❌ Quebrado
2000 | 1024 bits p    | ❌ Quebrado (2016)
2010 | 2048 bits p    | ⚠️ Em uso (enfraquecendo)
2020 | 3072 bits p    | ✅ Recomendado
2030+| 3072+ bits p   | ✅ Futuro
```

***

### 💻 Exemplos Práticos

#### Exemplo 1 – Gerar Chaves DSA (OpenSSL)

```bash
# Gerar parâmetros DSA (2048 bits)
openssl dsaparam -out dsa_params.pem 2048

# Gerar chave privada
openssl gendsa -out dsa_private.pem dsa_params.pem

# Extrair chave pública
openssl dsa -in dsa_private.pem -pubout -out dsa_public.pem

# Verificar chaves
openssl dsa -in dsa_private.pem -text -noout
openssl dsa -pubin -in dsa_public.pem -text -noout

# Output exemplo:
# Private-Key: (2048 bit)
# priv: 00:aa:bb:cc:...
# pub: 00:11:22:33:...
# P: (primo grande)
# Q: (primo menor)
# G: (gerador)
```

#### Exemplo 2 – Assinar e Verificar (OpenSSL)

```bash
# Criar arquivo
echo "Documento importante assinado com DSA" > documento.txt

# Assinar com DSA
openssl dgst -sha256 -sign dsa_private.pem -out signature.bin documento.txt

# Verificar assinatura
openssl dgst -sha256 -verify dsa_public.pem -signature signature.bin documento.txt

# Output: Verified OK
```

#### Exemplo 3 – DSA em Python (cryptography)

```python
from cryptography.hazmat.primitives.asymmetric import dsa
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.serialization import Encoding, PrivateFormat, PublicFormat

# Gerar chaves DSA (3072 bits)
private_key = dsa.generate_private_key(key_size=3072)
public_key = private_key.public_key()

print(f"Tamanho da chave: {private_key.key_size} bits")

# Assinar mensagem
message = b"Mensagem secreta para assinar com DSA"
signature = private_key.sign(
    message,
    hashes.SHA256()
)

print(f"Assinatura (tamanho): {len(signature)} bytes")

# Verificar assinatura
try:
    public_key.verify(signature, message, hashes.SHA256())
    print("✅ Assinatura DSA VÁLIDA!")
except:
    print("❌ Assinatura INVÁLIDA!")

# Modificar mensagem (teste)
message_tampered = b"Mensagem secreta MODIFICADA"
try:
    public_key.verify(signature, message_tampered, hashes.SHA256())
    print("❌ ERRO: Assinatura deveria ser inválida!")
except:
    print("✅ Corretamente rejeitou mensagem alterada")
```

#### Exemplo 4 – DSA com Parâmetros Personalizados

```python
from cryptography.hazmat.primitives.asymmetric import dsa
from cryptography.hazmat.primitives import hashes

# Gerar com tamanho específico
key_sizes = [1024, 2048, 3072]

for size in key_sizes:
    try:
        private_key = dsa.generate_private_key(key_size=size)
        print(f"DSA-{size}: OK")
        
        # Assinar mensagem pequena
        message = b"Test"
        sig = private_key.sign(message, hashes.SHA256())
        print(f"  Assinatura tamanho: {len(sig)} bytes")
        
    except ValueError as e:
        print(f"DSA-{size}: Erro - {e}")

# Nota: 1024 bits pode não ser suportado em versões modernas
```

#### Exemplo 5 – Comparação DSA vs RSA vs ECDSA

```python
import time
from cryptography.hazmat.primitives.asymmetric import dsa, rsa, ec
from cryptography.hazmat.primitives import hashes

def benchmark_dsa():
    start = time.time()
    private_key = dsa.generate_private_key(key_size=3072)
    gen_time = time.time() - start
    
    message = b"X" * 1000
    
    start = time.time()
    signature = private_key.sign(message, hashes.SHA256())
    sign_time = time.time() - start
    
    start = time.time()
    private_key.public_key().verify(signature, message, hashes.SHA256())
    verify_time = time.time() - start
    
    return gen_time, sign_time, verify_time, len(signature)

def benchmark_rsa():
    start = time.time()
    private_key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
    gen_time = time.time() - start
    
    message = b"X" * 1000
    
    start = time.time()
    signature = private_key.sign(message, hashes.SHA256())
    sign_time = time.time() - start
    
    start = time.time()
    private_key.public_key().verify(signature, message, hashes.SHA256())
    verify_time = time.time() - start
    
    return gen_time, sign_time, verify_time, len(signature)

def benchmark_ecdsa():
    start = time.time()
    private_key = ec.generate_private_key(ec.SECP256R1())
    gen_time = time.time() - start
    
    message = b"X" * 1000
    
    start = time.time()
    signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))
    sign_time = time.time() - start
    
    start = time.time()
    private_key.public_key().verify(signature, message, ec.ECDSA(hashes.SHA256()))
    verify_time = time.time() - start
    
    return gen_time, sign_time, verify_time, len(signature)

print("Benchmark (3072 bits equivalente):")
print("-" * 50)

d_gen, d_sign, d_verify, d_size = benchmark_dsa()
print(f"DSA:    gen={d_gen:.3f}s sign={d_sign:.3f}s verify={d_verify:.3f}s size={d_size}B")

r_gen, r_sign, r_verify, r_size = benchmark_rsa()
print(f"RSA:    gen={r_gen:.3f}s sign={r_sign:.3f}s verify={r_verify:.3f}s size={r_size}B")

e_gen, e_sign, e_verify, e_size = benchmark_ecdsa()
print(f"ECDSA:  gen={e_gen:.3f}s sign={e_sign:.3f}s verify={e_verify:.3f}s size={e_size}B")
```

***

### ⚠️ Vulnerabilidades e Ataques

#### 1. Reutilização de k (O ERRO MAIS GRAVE)

**Mesmo problema fatal do ECDSA!**

```python
# Se o mesmo k for usado para duas assinaturas diferentes:
# Assinatura1: (r, s1) com k
# Assinatura2: (r, s2) com mesmo k

# O atacante pode recuperar a chave privada:
# s1 - s2 = k^{-1} * (z1 - z2) mod q
# k = (z1 - z2) / (s1 - s2) mod q
# x = (s1*k - z1) / r mod q

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

**Caso real:** PlayStation 3 (2010) usava mesmo k → chave privada extraída.

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

```python
# ❌ NUNCA fazer:
k = 1  # muito pequeno
k = 12345  # fixo
k = random.randint(1, 1000)  # espaço muito pequeno

# ✅ Correto:
import secrets
k = secrets.randbelow(q-2) + 1  # criptograficamente seguro
```

#### 3. Lattice Attacks

Se `k` vazar poucos bits, a chave pode ser recuperada.

**Mitigação:** Usar RFC 6979 (k determinístico baseado na chave + mensagem).

#### 4. Timing Attacks

Implementações não constant-time podem vazar `k`.

**Mitigação:** Usar implementações constant-time.

#### 5. Ataque de Subgrupo (Se g não for bem escolhido)

**Mitigação:** Validar que `g^q mod p == 1`.

***

### 🛡️ Melhores Práticas

#### 1. Tamanhos Recomendados

```bash
# ❌ Obsoleto - NÃO USE
openssl dsaparam -out dsa_params.pem 1024

# ⚠️ Permitido (mas evitado)
openssl dsaparam -out dsa_params.pem 2048

# ✅ Recomendado
openssl dsaparam -out dsa_params.pem 3072

# ✅ Alto nível
openssl dsaparam -out dsa_params.pem 7680
```

#### 2. Use RFC 6979 (k Determinístico)

```python
# Em vez de k aleatório, use k = HMAC(key, message)
# Remove a necessidade de RNG (elimina ataques de RNG fraco)

# OpenSSL suporta via flag
# Mas é mais fácil usar EdDSA que tem isso por padrão!
```

#### 3. Hash Seguro

```python
# ❌ SHA-1 (quebrado)
# ⚠️ SHA-224 (fraco)
# ✅ SHA-256 (mínimo)
# ✅ SHA-384/512 (recomendado)

# OpenSSL
openssl dgst -sha256 -sign dsa_private.pem ...  # OK
openssl dgst -sha1 -sign dsa_private.pem ...    # ❌
```

#### 4. Validação de Assinaturas

```python
def validate_dsa_signature(r, s, q):
    # Sempre validar antes de processar!
    if not (0 < r < q and 0 < s < q):
        raise ValueError("Assinatura inválida")
```

***

### 📊 DSA vs ECDSA vs EdDSA

| Característica                  | DSA                 | ECDSA               | EdDSA (Ed25519)     |
| ------------------------------- | ------------------- | ------------------- | ------------------- |
| **Base**                        | Logaritmo discreto  | Curvas elípticas    | Curvas de Edwards   |
| **Tamanho chave (128 bits)**    | 3072 bits           | 256 bits            | 256 bits            |
| **Tamanho assinatura**          | 512 bits (64 bytes) | 512 bits (64 bytes) | 512 bits (64 bytes) |
| **Aleatoriedade necessária**    | ✅ Sim (k)           | ✅ Sim (k)           | ❌ Não               |
| **Determinístico (RFC 6979)**   | Opcional            | Opcional            | ✅ Sim (nativo)      |
| **Velocidade (assinar)**        | Lenta               | Rápida              | Muito rápida        |
| **Velocidade (verificar)**      | Média               | Média               | Rápida              |
| **Resistência a timing attack** | Difícil             | Difícil             | ✅ Fácil             |
| **Status**                      | ⚠️ Legado           | ✅ Moderno           | ✅ Moderno           |

***

### 🔄 Por que DSA está sendo substituído?

| Razão                  | Explicação                                           |
| ---------------------- | ---------------------------------------------------- |
| **Tamanho da chave**   | ECC oferece mesma segurança com chaves muito menores |
| **Velocidade**         | ECDSA e EdDSA são mais rápidos                       |
| **Aleatoriedade**      | DSA precisa de RNG (risco de repetir k)              |
| **Complexidade**       | Implementação segura é difícil                       |
| **Apenas assinaturas** | RSA pode fazer assinatura E cifragem                 |
| **EdDSA**              | Remove todos os problemas do DSA/ECDSA               |

***

### 📜 História do DSA

| Ano       | Evento                                             |
| --------- | -------------------------------------------------- |
| **1991**  | NIST propõe DSA (FIPS 186)                         |
| **1994**  | Padrão finalizado                                  |
| **2000**  | FIPS 186-2 (aumenta tamanhos)                      |
| **2005**  | Vulnerabilidades de timing descobertas             |
| **2009**  | FIPS 186-3 (adiciona curvas maiores)               |
| **2013**  | FIPS 186-4                                         |
| **2015**  | Logjam attack enfraquece DSA-1024                  |
| **2022**  | NIST recomenda ECDSA/EdDSA sobre DSA               |
| **2023+** | DSA em desuso, mantido apenas para compatibilidade |

***

### 🎯 Resumo Rápido

| Ponto               | Resumo                                        |
| ------------------- | --------------------------------------------- |
| **Função**          | Apenas assinatura digital (NÃO cifragem)      |
| **Base**            | Logaritmo discreto                            |
| **Tamanho mínimo**  | 3072 bits (p) / 256 bits (q)                  |
| **ERRO CRÍTICO**    | Reutilizar k → chave privada exposta          |
| **Vantagem**        | Padrão NIST (aceito em governos)              |
| **Desvantagem**     | Lento, tamanho grande, implementação complexa |
| **Recomendação**    | ✅ Use **Ed25519** (moderno) ou **ECDSA**      |
| **Quando usar DSA** | Apenas compatibilidade com sistemas legados   |

***

### 🔗 Links Úteis

* [FIPS 186-5 (NIST) - Digital Signature Standard](https://csrc.nist.gov/publications/detail/fips/186/5/final)
* [RFC 6979 - Deterministic DSA/ECDSA](https://tools.ietf.org/html/rfc6979)
* [OpenSSL DSA Documentation](https://www.openssl.org/docs/man1.1.1/man3/DSA_sign.html)
* [PlayStation 3 Hack - k Reuse Attack](https://events.ccc.de/congress/2010/Fahrplan/events/4087.en.html)


---

# 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/dsa-digital-signature-algorithm.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.