02 fundamentos

02 — Fundamentos da Criptografia

Conceitos, vocabulário, modelos de adversário, princípios e definições de segurança. Pré-requisito para entender todos os outros arquivos do compendium.

1. Vocabulário básico

Termo	Definição
laintext (P, M)	Mensagem em claro.
iphertext (C)	Mensagem cifrada.
ey (k)	Segredo compartilhado (simétrico) ou par público/privado (assimétrico).
ncryption ($E_k$)	Função que transforma P em C usando k.
ecryption ($D_k$)	Função inversa.
ipher	Algoritmo de encryption/decryption (ex.: AES, ChaCha20).
ode of operation	Modo de aplicação de um block cipher a mensagens maiores que um bloco (ex.: CBC, GCM).
ryptosystem	Conjunto cipher + mode + protocolo de key management.
cheme	Mesmo que cryptosystem; mais usado em literatura acadêmica.
rimitive	Bloco básico (AES, SHA-256, RSA).
onstruction	Combinação de primitivas para alcançar um objetivo (ex.: HMAC, AES-GCM).
AC	Message Authentication Code — tag que prova autenticidade.
EAD	Authenticated Encryption with Associated Data — encryption + MAC + dados extras autenticados sem cifrar.
DF	Key Derivation Function — deriva chaves de segredossenhasmaterial chave.
RF / PRP	Pseudorandom Function / Pseudorandom Permutation.
SPRNG	Cryptographically Secure Pseudorandom Number Generator.
ntropy	Medida de imprevisibilidade. Em bits: $H(X) = -sum p_i log_2 p_i$.
once	Number used once — não precisa ser secreto, ão pode repetircom mesma chave.
V	Initialization Vector — semelhante a nonce, requisitos variam por modo.
alt	Valor público aleatório anexado para tornar mesma senha gerar hashes diferentes.
epper	Segredo fixo aplicado a todos os hashes de um sistema; não armazenado com hash.
ag (T)	Output de MAC ou AEAD.
orward secrecy	Comprometer chave atual não revela tráfego passado.
ost-compromise security (PCS)	Após compromisso de estado, segurança se recupera com nova troca de chaves.
eniability	Receptor não pode provar a terceiros que mensagem veio do remetente.

2. Princípios de Kerckhoffs (1883)

Auguste Kerckhoffs, La Cryptographie Militaire (Journal des Sciences Militaires, vol. IX, 1883):

O sistema deve ser *raticamente, senão matematicamente, indecifrável*
*ão deve exigir que seja secreto* pode cair em mãos do inimigo sem inconveniente. ⭐ — princípio canônico.
Sua chave deve ser *omunicável e memorizável*sem notas, e *udável à vontade*
Deve ser *plicável à correspondência telegráfica*
Deve ser *ortátil* e seu uso não deve requerer mais de uma pessoa.
O sistema deve ser *ácil de usar* sem demanda mental ou conhecimento de longa lista de regras.

Reformulação moderna de Bruce Schneier: "Security through obscurity is no security". Reformulação de Shannon: "The enemy knows the system".

3. Princípios de Shannon (1949)

Claude Shannon, Communication Theory of Secrecy Systems (Bell System Technical Journal 28, 1949):

Secrecy perfeita

Um cifra tem *erfect secrecy*se para todo P, P' e C: $$\Pr[E_k(P) = C] = \Pr[E_k(P') = C]$$

Ciphertext não dá nenhuma informação sobre plaintext. *eorema de Shannon* secrecy perfeita exige $|K| \geq |M|$ — chave pelo menos tão longa quanto a mensagem. *ne-Time Pad*é a única realização prática, com chave verdadeiramente aleatória, do mesmo tamanho, usada uma vez.

Confusão e difusão

*onfusão* relação entre chave e ciphertext deve ser *omplexa e não-linear* Cada bit do ciphertext depende de muitos bits da chave.
*ifusão* relação entre plaintext e ciphertext deve ser *spalhada* Um bit do plaintext afeta muitos bits do ciphertext (avalanche).

Block ciphers modernos alternam camadas de *ubstituição*(S~~boxes — confusão) e *ermutação/mixing*(P~~boxes ou multiplicação matricial — difusão). Estrutura *PN*(Substitution-Permutation Network — AES) ou *eistel*(DES).

4. Modelos de adversário

Em ordem crescente de poder:

Sigla	Nome	O que o adversário pode fazer
OA	Ciphertext-Only Attack	Vê apenas ciphertexts. Modelo mais fraco.
PA	Known-Plaintext Attack	Vê pares (P, C) coletados passivamente.
PA	Chosen-Plaintext Attack	Pode pedir encryption de plaintexts à sua escolha.
CA1	Non~~adaptive Chosen~~Ciphertext (lunchtime)	Pode pedir decryption antes de ver o desafio.
CA2	Adaptive Chosen-Ciphertext	Pode pedir decryption a qualquer momento, exceto do ciphertext-desafio.
uthenticated CCA	CCA com integridade	Modelo moderno: oracle só responde se MAC verifica.

*ierarquia* COA ⊂ KPA ⊂ CPA ⊂ CCA1 ⊂ CCA2.

Definições de segurança IND* / SUF* / EUF-*

Acrônimo	Significado	Aplicável a
ND-CPA	Indistinguishability under CPA	Cifras
ND-CCA2	Indistinguishability under adaptive CCA	Cifras (padrão moderno)
M-CCA2	Non-malleability under adaptive CCA	Equivalente a IND-CCA2
UF-CMA	Existential Unforgeability under Chosen-Message Attack	Assinaturas e MACs
UF-CMA	Strong Unforgeability (não pode forjar nova tag mesmo p/ msg já assinada)	Assinaturas modernas

*ND-CPA game*(intuição):

Adversário escolhe duas mensagens $m_0$, $m_1$ de mesmo tamanho.
Challenger sorteia $b \in \{0,1\}$ aleatório, envia $C = E_k(m_b)$.
Adversário tenta adivinhar $b$.
Cifra é IND-CPA segura se $\Pr[\text{adv adivinha}] - 1/2$ é negligível em $\lambda$.

5. Funções one-way e trapdoor

Tipo	Definição
ne-way function (OWF)	$f: X to Y$ fácil de calcular, difícil de inverter. ão se sabese existem; existência implicaria $P neq NP$.
rapdoor one-way function	OWF que tem inverso fácil dado um segredo (trapdoor). Base de RSA, ECC, lattice-based.
RP	Pseudorandom permutation indistinguível de permutação aleatória. AES é assumido PRP.
RF	Pseudorandom function. Block cipher = PRP; PRP é PRF (com gap negligível pelo PRP/PRF switching lemma).
ollision-resistant hash	Difícil achar $x neq y$ com $H(x) = H(y)$.

6. Modelos teóricos

Random Oracle Model (ROM)

Bellare + Rogaway (CCS '93). Tratamos hash como função aleatória ideal: cada query nova retorna valor uniformemente aleatório. Provas em ROM dão garantia heurística — esquema seguro em ROM *ode*ser seguro com hash real, mas não é garantido (Canetti~~Goldreich~~Halevi 1998 mostraram contraexemplos artificiais).

Standard Model

Sem oracles idealizados. Provas mais difíceis mas mais convincentes. Esquemas como RSA~~OAEP, Cramer~~Shoup, Boneh-Boyen têm versões standard model.

Generic Group Model

Adversário só pode usar operações de grupo (multiplicação, exponenciação) sem explorar representação. Usado para provar lower bounds (Shoup 1997, Maurer 2005).

Universal Composability (UC)

Canetti 2001. Framework para provar segurança composicional: se F é UC~~seguro, é seguro em qualquer protocolo maior. Ideal para protocolos multi~~party.

7. Hierarquia de criptografia

Simétrica vs assimétrica

Aspecto	Simétrica	Assimétrica
Chave	Mesma para encrypt e decrypt	Par público/privado
Velocidade	~1000× mais rápida	Mais lenta
Distribuição	Problema (precisa canal seguro)	Resolvido (publica chave pública)
Uso prático	Bulk encryption	Key exchange + assinatura
Hybrid	TLS faz: assimétrica troca chave simétrica, simétrica cifra dados

Por finalidade

*onfidencialidade* encryption (AES, ChaCha20, RSA-OAEP, ECIES).
*ntegridade* hash, MAC (HMAC, KMAC, Poly1305, CMAC).
*utenticidade* MAC, assinatura digital.
*ão-repúdio* assinatura digital (não MAC — qualquer um com a chave MAC pode forjar).
*rescor* nonces, timestamps, sequence numbers.
*nonimato* ring signatures, group signatures, mix-nets.
*rivacidade computacional* FHE, MPC, ZKP.

8. Níveis de segurança

Convencionalmente medidos em *its*— significam: melhor ataque conhecido leva $2^n$ operações.

Algoritmo	Nível de segurança	Notas
3DES (chave 168 bit)	112 bit	Deprecated NIST após 2023
AES-128	128 bit	Padrão; resistência clássica forte
AES-256	256 bit (clássico) / 128 bit (Grover)	Pós-quântico viável
RSA-2048	~112 bit	Mínimo aceitável; recomenda 3072+
RSA-3072	128 bit	Equivalente AES-128 clássico
RSA-15360	256 bit	Inviável na prática; use ECC
ECC P-256	128 bit	Padrão TLS atual
ECC P-384	192 bit	CNSA suite
ECC P-521	256 bit
Curve25519	128 bit	Bernstein 2006
Curve448	224 bit
Ed25519	128 bit	EdDSA
SHA-256	128 bit collision / 256 bit preimage
SHA-512	256 bit collision / 512 bit preimage
SHA3256	idem SHA-256

Regra de equivalência (clássica, NIST SP 800-57):

Symmetric	RSA	DH	ECC
80	1024	1024	160
112	2048	2048	224
128	3072	3072	256
192	7680	7680	384
256	15360	15360	521

9. Geração de aleatoriedade

Entropy sources

*ardware* ring oscillators, thermal noise, shot noise, Intel RDRAND, ARM TRNG.
*S pooling* Linux getrandom(2), /dev/urandom, /dev/random; macOS SecRandomCopyBytes; Windows BCryptGenRandom.
*ser input* timing de teclado, mouse — relevante em boot inicial e VMs.

CSPRNGs

*ES~~CTR DRBG*(NIST SP 800~~90A) — saída de AES em CTR mode.
*MAC~~DRBG*(NIST SP 800~~90A) — popular.
*ash~~DRBG*(NIST SP 800~~90A).
*ortuna*(Schneier, 2003) — usado em FreeBSD.
*haCha20-based*— Linux desde 4.8 (2016).
*ualECDRBG*❌ — NIST SP 800-90A original incluía. *ackdoor NSA suspeitada e depois confirmada*(Snowden); removido 2014.

Regras

*unca*use Math.random(), rand(), random(), srand(time()).
*empre*use API criptográfica do OS (getrandom, BCryptGenRandom).
*eed cuidadosamente*após boot — VMs clonadas, embedded, IoT são vulneráveis (Mining Your Ps and Qs, Heninger et al. 2012; ROCA).

10. Princípios de design moderno

"Don't roll your own crypto"

Implementar primitivas é fácil; implementar *om segurança*(sem side-channel, sem bugs sutis) é extremamente difícil. Use bibliotecas auditadas:

*ibsodium*(alta-nível, design seguro por default).
*aCl*(predecessor de libsodium, DJB).
*oringSSL*(Google fork de OpenSSL).
*penSSL 3.x*(com FIPS provider quando exigido).
*ink*(Google, high-level).
*ing*(Rust, fork de BoringSSL).
*ge*(file encryption, Filippo Valsorda).

Constant-time

Todo código que toca segredo deve executar em tempo independente do segredo: sem *ranches*sobre segredo, sem *able lookups indexados por segredo* sem *ultiplicações variáveis em CPUs antigas* Bernstein é o evangelista. AES-NI ajuda (instruções dedicadas).

Misuse-resistance

APIs devem dificultar uso errado:

*aCl/libsodium*— apenas crypto_secretbox (autenticada), sem ECB cru.
*ES~~GCM~~SIV*(Gueron-Lindell) — degrada gracilmente em nonce reuse.
*ink*— keysets versionados, rotação built-in.

Defense in depth

Camadas redundantes. Ex.: TLS + HSTS + HPKP (legacy) / CT (Certificate Transparency); LUKS + dm-verity; signed binaries + boot guard.

Hybrid (clássico + PQC)

Combine algoritmo clássico estabelecido + PQC novo. Ataque precisa quebrar *mbos* Padrão em transição (X25519MLKEM768 = X25519 ⊕ ML~~KEM~~768).

11. Métodos de prova

Método	Como funciona
eduction proof	Mostra que quebrar esquema implica quebrar problema duro (factoring, DLP, LWE). Padrão moderno.
ybrid argument	Sequência de games quase-indistinguíveis; diferença total ≤ soma.
ame-based proof	Define security game; prova vantagem do adversário negligível.
imulation-based proof	Simulator gera distribuição indistinguível sem segredo. Usado em ZKP, MPC, UC.

12. Quem confia em quê (chain of trust)

Camada	Confia em
Aplicação	TLS library
TLS library	CA root store
CA	Procedimentos de validação + HSM + auditoria
HSM	Hardware vendor + certificação FIPS 140-3 / CC EAL
Certificação	NIST, CSE-CST, BSI, ANSSI
OS RNG	Kernel + hardware (IntelAMDARM)
Kernel	Boot chain (UEFI Secure Boot → shim → grub → kernel)
UEFI	OEM signing keys + Boot Guard fuses
Fuses	Fabricante de chip

Cada elo é um possível ponto de comprometimento. Confidential Computing tenta encurtar a chain isolando workload do host.

13. Diferenças culturais: criptografia "americana" vs "europeia"

Tradição	Características
IST/NSA (US)	Padrões formais (FIPS), competições abertas (AES, SHA~~3, PQC), DSA, P~~256384521 (curvas Brainpool/NIST), influência state-actor histórica (Dual_EC).
CRYPT/ENISA (EU)	eSTREAM, NESSIE, recomendações ENISA; Brainpool curves; preferência por algoritmos europeus (Serpent, Twofish, Camellia em algumas suites).
OST (RU)	GOST 28147~~89 (block cipher 64~~bit), Kuznyechik (GOST R 34.12-2015), Streebog (hash).
M (CN)	SM2 (curva chinesa), SM3 (hash), SM4 (block cipher). Obrigatório em algumas aplicações governamentais chinesas.
ernstein school	Curve25519, Ed25519, ChaCha20, Poly1305, SipHash, BLAKE; design constant-time, sem patentes, simples de implementar.

14. Padronizações relevantes

Órgão	Padrão	Escopo
NIST	FIPS 140-3	Requisitos de módulos criptográficos
NIST	FIPS 186-5	Digital signatures (DSA, RSA, ECDSA, EdDSA)
NIST	FIPS 197	AES
NIST	FIPS 198-1	HMAC
NIST	FIPS 202	SHA-3
NIST	FIPS 203	ML-KEM
NIST	FIPS 204	ML-DSA
NIST	FIPS 205	SLH-DSA
NIST	SP 800-38A–G	Modes (ECB, CBC, CFB, OFB, CTR, CCM, GCM, KW, XTS)
NIST	SP 800-56ABC	Key establishment
NIST	SP 800-90ABC	RNG
NIST	SP 800-131A	Algorithm transitions
NIST	SP 800-208	Stateful hash signatures (XMSS, LMS)
IETF	RFC 8446	TLS 1.3
IETF	RFC 7748	X25519/X448
IETF	RFC 8032	EdDSA
IETF	RFC 9180	HPKE
IETF	RFC 9420	MLS
IETF	RFC 7539 → 8439	ChaCha20-Poly1305
IETF	RFC 2104	HMAC
IETF	RFC 5869	HKDF
IETF	RFC 9106	Argon2
ISO/IEC	18033-3	Block ciphers
ISO/IEC	9797-1/2	MACs
ISO/IEC	10118	Hash functions
ISO/IEC	11770	Key management

15. Bibliografia essencial

*atz + Lindell* Introduction to Modern Cryptography, CRC Press, 3ª ed. 2020 — texto-padrão de graduação/mestrado.
*oneh + Shoup* A Graduate Course in Applied Cryptography — gratuito em toc.cryptobook.us.
*enezes, van Oorschot, Vanstone* Handbook of Applied Cryptography (CRC) — clássico técnico, gratuito em cacr.uwaterloo.ca/hac/.
*chneier* Applied Cryptography, 1996 (datado mas referência cultural).
*umasson* Serious Cryptography, No Starch Press 2017 — referência prática moderna.
*erguson + Schneier + Kohno* Cryptography Engineering, Wiley 2010.
*ernstein, Lange, et al.* Post-Quantum Cryptography, Springer 2009 (handbook).
*oldreich* Foundations of Cryptography, 2 volumes Cambridge — teórico, denso.

Online

IACR ePrint Archive: eprint.iacr.org
Real World Crypto Symposium proceedings
CFRG (Crypto Forum Research Group) IETF
Cryptography Stack Exchange (community Q&A)
David Wong, Real-World Cryptography (Manning 2021)
Filippo Valsorda blog filippo.io
Trail of Bits blog, NCC Group Cryptography Services

Termo	Definição
laintext (P, M)	Mensagem em claro.
iphertext (C)	Mensagem cifrada.
ey (k)	Segredo compartilhado (simétrico) ou par público/privado (assimétrico).
ncryption (\(E_k\))	Função que transforma P em C usando k.
ecryption (\(D_k\))	Função inversa.
ipher	Algoritmo de encryption/decryption (ex.: AES, ChaCha20).
ode of operation	Modo de aplicação de um block cipher a mensagens maiores que um bloco (ex.: CBC, GCM).
ryptosystem	Conjunto cipher + mode + protocolo de key management.
cheme	Mesmo que cryptosystem; mais usado em literatura acadêmica.
rimitive	Bloco básico (AES, SHA-256, RSA).
onstruction	Combinação de primitivas para alcançar um objetivo (ex.: HMAC, AES-GCM).
AC	Message Authentication Code — tag que prova autenticidade.
EAD	Authenticated Encryption with Associated Data — encryption + MAC + dados extras autenticados sem cifrar.
DF	Key Derivation Function — deriva chaves de segredossenhasmaterial chave.
RF / PRP	Pseudorandom Function / Pseudorandom Permutation.
SPRNG	Cryptographically Secure Pseudorandom Number Generator.
ntropy	Medida de imprevisibilidade. Em bits: \(H(X) = -sum p_i log_2 p_i\).
once	Number used once — não precisa ser secreto, ão pode repetircom mesma chave.
V	Initialization Vector — semelhante a nonce, requisitos variam por modo.
alt	Valor público aleatório anexado para tornar mesma senha gerar hashes diferentes.
epper	Segredo fixo aplicado a todos os hashes de um sistema; não armazenado com hash.
ag (T)	Output de MAC ou AEAD.
orward secrecy	Comprometer chave atual não revela tráfego passado.
ost-compromise security (PCS)	Após compromisso de estado, segurança se recupera com nova troca de chaves.
eniability	Receptor não pode provar a terceiros que mensagem veio do remetente.

Tipo	Definição
ne-way function (OWF)	\(f: X to Y\) fácil de calcular, difícil de inverter. ão se sabese existem; existência implicaria \(P neq NP\).
rapdoor one-way function	OWF que tem inverso fácil dado um segredo (trapdoor). Base de RSA, ECC, lattice-based.
RP	Pseudorandom permutation indistinguível de permutação aleatória. AES é assumido PRP.
RF	Pseudorandom function. Block cipher = PRP; PRP é PRF (com gap negligível pelo PRP/PRF switching lemma).
ollision-resistant hash	Difícil achar \(x neq y\) com \(H(x) = H(y)\).