Introdução

A criptografia é a arte da transformação de um texto (ou qualquer outro arquivo) compreensível em um texto incompreensível tal que só uma informação adicional secreta, a chave, permita desfazê-la; útil desde a antiguidade, por exemplo, para ocultar do inimigo a comunicação militar.

Resumo

O livro primeiro estabelece a diferença entre

• a antiga criptografia simétrica usada entre correspondentes conhecidos para, por exemplo,
  • cifrar a comunicação em uma rede sem fio, e
  • proteger um arquivo no disco rígido, …

e

• a recente criptografia assimétrica usada entre correspondentes desconhecidos para, por exemplo,
  • cifrar a comunicação na internet, e
  • autenticar documentos ou transações (financeiras).

Um sobrevoo da História da criptografia apresenta os algoritmos simétricos da antiguidade que servirão como pedras angulares dos algoritmos criptográficos simétricos modernos, as redes de permutação e substituição, como o atual padrão AES.

Este é percorrido passo a passo para compreender a sua invulnerabilidade contra os ataques mais sofisticados para decifrar o texto cifrado por ele sem conhecimento da chave.

Entra nos anos 70 a criptografia assimétrica, indispensável na idade da internet e ubíqua no nosso dia-a-dia, por exemplo, para cifrar os mensageiros do celular, sites seguros no navegador e transações financeiras à distância. Sofre, porém, do ataque pelo homem no meio que assume as identidades dos correspondentes, o que leva à infraestrutura de teias de confiança, autoridades e certificados, visualizados por cadeados na barra de endereço no navegador.

Por trás de toda a criptografia assimétrica figura a Aritmética Modular que permite criar uma aplicação invertível (chamada de arapuca) cujo inverso é praticamente incomputável. Exemplos são a potenciação respectivamente a exponenciação modular que são usadas pelos dois algoritmos fundamentais da criptografia assimétrica:

• O mais antigo (dos anos 70, contudo até hoje seguro) é a Troca de Chaves por Diffie-Hellman, e
• o mais usado até hoje, o RSA

que são ambos estudados passo a passo e cujas bases teóricas são motivadas e explicadas.

Ultimamente a criptografia por curvas elípticas finitas, um grupo finito de pontos num reticulado no plano, tornou-se o novo padrão da criptografia assimétrica. A sua aplicação arapuca é análoga à do Diffie-Hellman, assim como os passos da cifração e assinatura, mas pela sua maior complexidade mais segura.

Elas são usadas, por exemplo, para assinar as transações na criptomoeda Bitcoin cujo conceito e funcionamento é desenvolvido na parte final do livro: Ao contrário de uma moeda comum na qual os negociantes confiam em um banco, uma criptomoeda mantém um livro-razão público de todas as transações. Para garantir a sua imutabilidade, ele precisa de funções de embaralhamento (ou hashes) que têm vários usos na computação, os quais são todos apresentados e comparados no penúltimo capítulo. O último capítulo examina a anatomia do livro-razão, a Blockchain ou, literalmente, cadeia de blocos: os seus blocos e os laços entre eles (os hashes). Em seguida responde às questões como ela

• começou,
• cresce por mineração, e
• é mantida consistente pela rede dos participantes.

História

Historicamente, a chave para codificar e descodificar é a mesma: a cifração simétrica. Nos anos 70, surgiu a cifração assimétrica, na qual as chaves para cifrar (a chave pública) e decifrar (a chave secreta) são diferentes. Matematicamente, ela baseia-se em uma função alçapão, uma função invertível que é facilmente computável, mas cujo inverso é computacionalmente inviável.

Hoje em dia os algoritmos de cifração assimétrica têm altíssimo valor comercial: Toda hora, seguram e certificam milhões de transações financeiras na internet; quanto mais seguros os algoritmos, tanto mais as transações.

Criptografia Simétrica

Distinguimos entre

• a criptografia histórica (necessariamente simétrica antes dos anos $1970$) e
• criptografia simétrica moderna.

A criptografia (simétrica) histórica trata textos e dispõe de duas operações:

• permutação (das letras do alfabeto), e
• transposição (das letras do texto claro)

Por exemplo, a Enigma usada pela Alemanha na Segunda Guerra Mundial usava apenas o primeiro recurso, a substituição das letras do texto claro pelas letras permutadas do alfabeto.

A criptografia simétrica moderna trata dados, isto é, bites, baites ou números em geral em blocos (Cifras de Feistel como o AES) e itera estas duas operações,

• permutação (das letras do alfabeto), e
• transposição (das letras do texto claro)

além de aplicar uma operação matemática como a multiplicação de matrizes, para obter ótima difusão (isto é, filosoficamente, cada letra do texto cifrado depende de todas as letras da chave e do texto claro).

Criptografia Assimétrica

A primeira parte trata a questão ubíqua da confiança. Como a criptografia assimétrica permite obter a chave por uma fonte anônima, como garantir que seja confiável? Quer dizer, como evitar o perigo do ataque do man-in-the-middle em que o atacante se interpõe entre os correspondentes, assumindo a identidade de cada um, assim observando e interceptando suas mensagens?

Na segunda parte, tratamos das ideias matemáticas por trás da implantação dos algoritmos de criptografia assimétrica:

• quanto à teoria matemática, orientamo-nos ao livro Hoffstein, Pipher, e Silverman (2008) que se contenta com os conhecimentos algébricos do ensino médio;
• quanto às implementações dos algoritmos apresentados, usamos o livro de Sweigart (2013).

Introduzimos as ferramentas básicas para tratar a criptográfica assimétrica, que é matematicamente mais rica: Por trás de todos os algoritmos criptográficos é o problema da insolubilidade computacional do logaritmo discreto, o que muda a figura é o grupo sobre o qual ele opera. Os exemplos principais são

• o grupo multiplicativo de um corpo finito, o caso clássico, e
• o grupo aditivo de uma curva elíptica, o mais recente.

O Grupo Multiplicativo de um Corpo Finito

Estudamos primeiro o caso clássico, o grupo multiplicativo de um corpo finito: Revisaremos as bases matemáticas, números primos, aritmética modular e corpos finitos, para então tratar os algoritmos mais antigos (dos anos 80) baseados nelas: os algoritmos

• ElGamal, que é a implementação a mais próxima do primeiro esboço de um sistema assimétrico delineado por Diffie e Hellman (1976),
• RSA por Rivest, Shamir, e Adleman (1978), a sua implementação predominante.

O Grupo Aditivo de uma Curva Elíptica

Concluímos com o caso mais recente, o grupo aditivo de uma curva elíptica: As suas bases matemáticas são mais envolvidas, com efeito, baseiam-se na teoria dos corpos finitos.

Criptomoedas

Os meios criptográficos para implementar uma criptomoeda como o Bitcoin são

• a criptografia assimétrica para assinar as transações (mais especificamente, a criptografia assimétrica por curvas elípticas finitas), e
• as funções de hash criptográficas para
  • endereçar as transações, e
  • dificultar a extensão da blockchain (em particular, a sua modificação maléfica), o livro de registro público das transações mantido pelos computadores.

Roteiro

0. O primeiro capítulo não-numerado, Introdução,

   • define a criptografia,
   • resume a sua História, dos tempos antigos aos tempos modernos, e
   • orienta o leitor sobre a divisão dos capítulos.

   O segundo capítulo não-numerado, Notações, é um glossário das noções e notações usadas.

1. Este capítulo estabelece a diferença entre a criptografia simétrica, usada desde a antiguidade, e a criptografia assimétrica, inventada nos anos 70. Em particular, destaca a importância da assinatura digital, possibilitada pela última. Mostra como quaisquer dados, sejam textos ou imagens, se codificam em arquivos digitais, isto é,

   • sequências de bits (o ponto de vista útil para a criptografia simétrica) ou, equivalentemente,
   • números (o ponto de vista útil para a criptografia assimétrica).

2. Este capítulo dá os exemplos históricos da criptografia (simétrica) dos romanos e espartanos que servirão como protótipos para algoritmos modernos.

   Discute a segurança destes algoritmos e mostra como podem ser quebrados por regularidades estatísticas apesar de um grande número de chaves.

   Desmantela a Enigma, máquina criptográfica usada pelos eixos de potências, em particular, pelos alemães durante a Segunda Guerra Mundial. Delineia como ela foi quebrada pelos aliados apesar de ser teoricamente segura.

3. Este capítulo apresenta AES, o atual algoritmo padrão da criptografia simétrica, e mostra como os algoritmos antigos servem como suas pedras angulares. Motiva porque ele é considerado imune contra os ataques mais valentes conhecidos. Explica em particular o ataque da Criptoanálise Diferencial e mostra a imunidade do AES contra ela.

4. Este capítulo sobre a criptografia assimétrica discute

   • o seu funcionamento,
   • as vantagens e limitações,
   • as suas manifestações no nosso dia-a-dia, como a cifração de sites seguros no navegador.

   Salienta a indispensabilidade da assinatura digital para assegurar toda negociação (financeira) online.

   Orienta sobre as melhores práticas para o gerenciamento das chaves públicas e privadas; em particular, como guardar as chaves privadas da forma mais segura possível.

   Introduz ao uso do o atual padrão GPG para criptografia assimétrica, e apresenta uns aplicativos, tais como mensageiros, que a usam (entre eles WhatsApp).

5. Este capítulo estimula o leitor a estudar a base de toda a teoria por trás da criptografia assimétrica, a Aritmética Modular, pela sua utilidade na criptografia assimétrica.

6. Este capítulo dá os passos do protocolo criptográfico assimétrico mais antigo, dos anos 70, a troca de chaves por Diffie-Hellman, e explica porque é considerado seguro até hoje.

7. Este capítulo prepara a estrada para o algoritmo assimétrico mais usado até hoje, o RSA, pela apresentação do Algoritmo de Euclides, uma iterada divisão com resto, em que ele se baseia.

8. Este capítulo dá

   • os passos do primeiro algoritmo assimétrico, o RSA, e explica porque é considerado seguro até hoje, e
   • os do algoritmo ElGamal que se baseia no Diffie-Hellman e serve como protótipo para muitos protocolos de assinatura como o DSA e EC-DSA.

9. Este capítulo introduz a criptografia pelas curvas elípticas finitas, o novo padrão da criptografia assimétrica e atualmente considerado mais eficiente. Compara as suas vantagens e inconveniências com o Diffie-Hellman ou RSA.

10. Este capítulo prepara as ferramentas principais para as criptomoedas baseadas na Prova de Trabalho (tal como o Bitcoin) pela introdução das funções de embaralhamento ou funções hash. Os seus valores servem como (carteiras de) identidade de arquivos. Existem vários usos delas na computação; logo, existem diferentes tipos delas com diferentes finalidades os quais apresenta todas.

11. Este capítulo explica

    • o conceito de uma criptomoeda e
    • o funcionamento da criptomoeda pioneira Bitcoin:
      • O que é uma cadeia de blocos,
      • de que consiste um bloco, e
      • como os Bitcoins são (seguramente) guardados e transferidos?

Livros de Referência

Excelentes livros de referências para acompanhar o curso são

• o clássico Menezes, Oorschot, e Vanstone (1997), gratuitamente disponível no endereço http://www.cacr.math.uwaterloo.ca/hac/, e
• o compêndio mais recente Joux (2009).

Links

Lembremo-nos de que, mesmo se o link URL expirou, o conteúdo é ainda disponível pelo archive.org no endereço https://web.archive.org/web/URL/ . Por exemplo, o plotter de funções sobre um corpo finito http://graui.de/code/ffplot/ ficará disponível sob https://web.archive.org/web/http://graui.de/code/ffplot/ . Neste caso, a página foi arquivada no dia 5 de maio 2018; o seu estado nesta data continua a estar disponível em https://web.archive.org/web/20180505102200/http://graui.de/code/ffplot/ .

Notações

Esta secção explica a linguagem matemática básica, conjuntos e funções. Como as notações usada na matemática acadêmica diferem em uns pontos das do ensino escolar, repitamos as mais comuns:

Conjuntos

A noção fundamental da matemática é a de um conjunto; segundo os dicionários Aurélio, Houaiss ou Michaelis:

• qualquer coleção de seres matemáticos,
• qualquer reunião de objetos, determinados e diferenciáveis, quer esses objetos pertençam à realidade exterior, quer sejam objetos do pensamento, ou
• qualquer reunião das partes que constituem um todo.

Esta coleção de seres matemáticos é denotada por $\{ \text{ seres matemáticos } \}$. Se um ser matemático $a$ pertence ao conjunto $A$, dizemos que $a$ é em $X$ e escrevemos $a \in A$ ou $A \ni a$.

Por exemplo, o conjunto

• dos números naturais $\mathbb{N} = \{ 1, 2, 3, \ldots \}$ é denotado por $\mathbb{N}$ .
• dos números inteiros $\mathbb{Z} = \{ -2, -1, 0, 1, 2, \ldots \}$ é denotado por $\mathbb{Z}$,
• dos números racionais $\{ x/y \text{ para } x,y \text{ em } \mathbb{Z} \}$ é denotado por $\mathbb{Q}$; por exemplo, $2/3$ é nele , e
• dos números reais $\{ a_N 10^N + \cdots + a_1 10 + a_0 + a_{-1} 10^{-1} + \cdots \}$ para $a_N$, , $a_1$, $a_0$, $a_{-1}$ em $\{$ $0$, $1$, , $9$ $\}$ é denotado por $\mathbb{R}$; por exemplo, $\pi = 3,14159 \ldots$ é nele.

Podemos comparar dois conjuntos $A$ e $B$:

• denote $A \supseteq B$ que $A$ contém (ou inclui) $B$, e
• denote $A \subseteq B$ que $A$ é contido (ou incluso) $B$.

Podemos formar um novo conjunto a partir de dois conjuntos $A$ e $B$:

• denote $A \cup B$ a união de $A$ e $B$, o conjunto dos elementos que pertencem a $A$ ou $B$,
• denote $A \cap B$ a intersecção de $A$ e $B$, o conjunto dos elementos que pertencem a $A$ e $B$;
• se $A \supseteq B$, então denote $A - B$ a diferença entre $A$ e $B$, o conjunto dos elementos que pertencem a $A$ mas não a $B$.

Por exemplo, os números irracionais são todos os números reais que não são racionais, isto é, que pertencem ao $\mathbb{R} - \mathbb{Q}$.

Denote $A \times B$ o seu produto cujos elementos são $(a,b)$ para $a$ em $A$ e $b$ em $B$, isto é, $$A \times B = \{ (a, b) \text{ para } a \text{ em } A \text{ e } b \text{ em } B \}.$$ Se $B = A$, escrevemos $A^2$ em vez de $A \times A$, e $A^3$ em vez de $A \times A \times A$, e assim por diante. Por exemplo, $\mathbb{R}^2$ é o plano (euclidiano), e $\mathbb{R}^3$ é o espaço.

Funções

Fórmula

Uma função descreve a dependência entre duas quantidades. No ensino escolar, é usualmente denotada por uma equação $$f(x) = \text{ expressão em $x$}$$ onde na expressão figuram

• operações aritméticas $+$, $-$, $\cdot$, $/$ …
• sobre números reais, constantes, funções algébricas como $x^2$ e funções especiais como $\exp(x)$, $\log(x)$, $\mathrm{sen}(x)$, …

Por exemplo:

1. A distância $s$ percorrida por um objeto na queda livre depende do tempo da queda $t$: vale $s = g \cdot t^2$ onde $g = 9,8 \mathrm{m}/\mathrm{s}^2$ é a constante da aceleração gravitacional da terra.
2. A forca de atração $K$ entre duas massas $m'$ e $m''$ depende de $m'$, $m''$ e a distância $r$ entre elas: Pela lei gravitacional de Newton $K = G (m' m'')/r^2$ onde $G = 6,67 \cdot 10^{-11} \mathrm{N} \mathrm{m}^2 \mathrm{kg}^{-2}$ é a constante de gravidade universal de Newton.

Porém, existem outras dependências, por exemplo:

3. O preço de uma entrada ao teatro de fantoches depende do número da fila do assento: Esta dependência descreve-se por uma tabela de preços, dando o número da fila $1$, $2$, $3$, … e o preço correspondente de $100$ Centavos, $20$ Centavos, $5$ Centavos, …

Definição. Uma função $f$ é uma regra que associa a cada elemento $x$ de um conjunto $X$ exatamente um elemento $y$ de um conjunto $Y$.

Esta associação é simbolicamente expressa por $y = f(x)$. Refiramo-nos

• a $x$ como variável (independente) ou argumento,
• a $y$ como variável dependente ou valor (da função),
• a $X$ como domínio da função, e
• a $Y$ como contra-domínio da função.

A $\mathrm{im} f$ de $f$ é o conjunto de todos os valores de $f$, $$\mathrm{im} f = \{ \text{ todos os } f(x) \text{ para } x \text{ em } X \}.$$ Por exemplo, $\mathrm{im} \mathrm{sen} = [-1,1]$ e $\mathrm{im} f = \{c\}$ para a função constante $f \equiv c$. O contra-domínio contém a imagem, mas não necessariamente coincide com ela, $$\mathrm{im} f \subseteq Y.$$

Usualmente, vemos funções com $X$ e $Y \subseteq \mathbb{R}$, isto é, funções reais; chamamo-nas muitas vezes simplesmente de funções. Usualmente as letras $a,b,c,\ldots, r, s, t, u ,x,y,z$ denotem números reais; as letras $i,j,k, l, n,m$ denotem números naturais (usados para enumerações). Nos nossos exemplos:

1. Aqui (a magnitude) de $t$ em $\mathbb{R}_{\geq 0}$ e $f(t) = s \in \mathbb{R}_{\geq 0}$. Tem-se $X = \mathbb{R}_{\geq 0}$ e $\mathrm{im} f = \mathbb{R}_{\geq 0}$.
2. Aqui (a magnitude) de $m',m''$ em $\mathbb{R}_{\geq 0}$ e $K$ em $\mathbb{R}_{\geq 0}$. Tem-se $X = (\mathbb{R}_{\geq 0} \times \mathbb{R}_{\geq 0}) \times \mathbb{R}_{\geq 0}$ e $\mathrm{im} f = \mathbb{R}_{\geq 0}$.
3. Aqui $X = \mathbb{N} = \{ 1, 2, 3 \}$ e $\mathrm{im} f = \{ 100, 20, 5 \}$.

Funções reais aparecem em diversas formas: além de

• uma equação,

obtemos pela substituição da variável por um número real como $0,5$, $1$, $2$, $1000$, …

• uma tabela de valores $x$ e $y$ dado pela avaliação do lado direito da igualdade $f(x) = ...$, e

• um gráfico

  1. pela marcação dos pontos $(x,y)$ no plano que são dados pelos valores da tabela, e
  2. pela conexão destes pontos.

Em mais detalhes:

• Na forma de uma equação como nos exemplos acima: $y = f(x)$, por exemplo, $y = x^2,\mathrm{sen} x \ldots$ Para facilitar, fazemos o convênio seguinte: Se escrevemos apenas a regra de associação, por exemplo, $f(x) = 1/(x(x-3))$ ou $\sqrt x$, então o domínio é o subconjunto máximo de $\mathbb{R}$ para que esta regra seja definida (quer dizer, faça sentido). Por exemplo, nestes exemplos, $X = \mathbb{R} - \{0,3\}$ e $X = \mathbb{R}_{\geq 0}$.

• Na forma de uma tabela de valores, por exemplo: Um experimento mede a tensão $U$ de um resistor em dependência da corrente $Y$. A tabela tem as entradas $Y = 50;100;150, \ldots (mA)$ e $U = 2;4,6; \ldots (V)$. Aqui $X = \{50,100, \ldots\}$ (e $Y = \mathbb{R}_{\geq 0}$). (Gostaríamos de extrapolar esta função, isto é, estender o seu domínio a $\mathbb{R}_{\geq 0}$; a este fim, parece provável que $U = RI$ com $R = 0,04 \Omega$.)

• A equação funcional $y = f(x)$ associa a cada valor $x$ um único valor $y$, em símbolos, $x \mapsto y = f(x)$. Um tal par de valores $(x_0, y_0)$ pode ser interpretado como ponto $P$ no plano cartesiano. Para cada par de valores $(x_0,y_0)$ obtemos exatamente um ponto. Dado um ponto $P$, os números reais $x_0$ e $y_0$ são chamados das coordenadas (cartesianas). O conjunto de todos os pontos $(x, y = f(x))$ forma a curva da função (ou gráfico), que ilustra o percurso da função $y = f (x)$. (Por exemplo, a parábola $y = x^2$ ou uma função afim $y = ax + b$.)

  Para desenhar a curva:

  1. Enche uma tabela de valores para uns argumentos $x'$, $x''$, …

  2. Desenha os pontos dados nela, e

  3. Conecta-os para obter o percurso da curva da função.

De vez em quando, para destacar que um objeto, por exemplo, uma função $h \colon X \to Y$, depende de outro objeto, por exemplo, de um conjunto $D$ ou uma ênupla $w$, escrevemos $h(D)$ ou $h_D$ respetivamente $h(w)$ ou $h_w$ em vez de $h$.

Aplicação

No ensino acadêmico, uma função ou aplicação é denotada por $$f \colon X \to Y$$ para os dois conjuntos,

• o domínio $X$, e
• o contra-domínio $Y$ de $f$

dizemos que manda ou envia cada argumento $x$ em $X$ a um único valor $y$ em $Y$.

Lê-se que $f$ é uma função de $X$ a $Y$, ou tem argumentos em $X$ e valores em $Y$. No contexto informático, pensamos de $f$ como um algoritmo, e referimo-nos a $X$ e $Y$ como entrada e saída.

Uma função manda ou envia cada argumento $x$ em $X$ a um único valor $y$ em $Y$ (ou associa a cada $x$ um único $y$). Escrevemos $$x \mapsto y$$ e denotemos este valor $y$ por $f(x)$. Frequentemente, $X = \mathbb{R}$ ou $X = \mathbb{R} \times \cdots \times \mathbb{R}$ e $Y = \mathbb{R}$ ou $Y = \{ \pm 1 \}$. Por exemplo, a função $f \colon \mathbb{R} \to \mathbb{R}$ dada por $x \mapsto x^2$ manda $2$ em $\mathbb{R}$ a $2^2 = 4$ em $\mathbb{R}$.

Função e aplicação são sinónimos. Contudo, a conotação é outra: Se os objetas do domínio são, por exeplo, números inteiros, conjuntos, então aplicação é mais comum, enquanto função é principalmente usada quando o domínio consiste de (ênuplas de) números reais.

Formar Novas Funções

Composição

A partir de duas funções $f$ e $g$ (sobre quaisquer domínios e imagens) pode ser obtida outra por concatenação; a função composta ou a composição $g \circ f$, dado que a imagem de $f$ é contida no domínio de $g$, isto é, $Y(f) \subseteq X(g)$. É definida por $$g \circ f \colon x \mapsto g(x) \mapsto f(g(x)),$$ simbolicamente, para obter $g \circ f(x) = g(f(x))$, substituímos $x$ em $g(x)$ por $f(x)$.

Se temos duas funções, $$f \colon X \to Y, \quad \text{ e } \quad g \colon Y \to Z$$ isto é, tais que os valores de $f$ são argumentos de $g$, a sua composição é definida por $$x \mapsto f(x) \mapsto g(f(x)),$$ isto é, a saída de $f$ é a entrada de $g$, e denotada por $$g \circ f \colon X \to Z.$$

Inversão de funções

Por definição, uma função $f \colon X \to Y$ associa a cada argumento $x \in X$ exatamente um valor $y \in Y$. Frequentemente surge o problema inverso: Dado um valor $y$, determina o seu argumento $x$ sob $f$, isto é, tal que $y = f(x)$. Se uma função $f$ é injetora, isto é, $x' \neq x''$ implica $f(x') \neq f(x'')$, isto é, a argumentos diferentes são associados valores diferentes, então a cada valor $y \in \mathrm{im} f$ é associado um único argumento $x \in X$. A função $g \colon \mathrm{im} f \to X$ obtida pela associação inequívoca inversa $y \mapsto x$, ou $g(y) = x$ é a ou o de $f$ e denotada por $g = f^{-1}$. Ora, $y$ é a variável e $x$ a variável . Em fórmulas, a função inversa $g$ é obtida pela permutação das duas variáveis $x$ e $y$ na equação $y = f(x)$.

Matematicamente, a função $f$ tem o inverso $g = f^{-1}$, se $g(f(x)) = x$ e $f(g(x)) = x$. Por exemplo, sobre $\mathbb{R}_{\geq 0}$ vale $\sqrt (x^2) = x = (\sqrt{x})^2$ para $f(x) = x^2, g(x) = \sqrt x$, e $(2x + 1)/2-1/2 = x=2(x/2-1/2) + 1$ para $f(x) = 2x + 1$ e $g(x) = x/2 - 1/2$.

Para desenhar a função inversa, poderíamos permutar as designações dos dois eixos. Porém, isto comumente não se faz. Porém, se o domínio e a imagem coincidem, o gráfico da função inversa $g = f^{-1}$ é o espelhamento do gráfico da função invertida $f$ na diagonal dos pontos cuja coordenada $x$ é igual à coordenada $y$.

Exemplos. Olhemos uns exemplos de funções invertíveis. Observamos em particular que a invertibilidade depende do domínio: Quanto menor o domínio, tanto mais provável que a função seja invertível.

• A parábola $y = x^2$ não é invertível sobre $\mathbb{R}$, mas só sobre $\mathbb{R}_{\geq 0}$ e $\mathbb{R}_{\leq 0}$ (pela radiciação quadrática).
• A função $y = 2x + 1$ cresce de modo estritamente monótono, em particular, é invertível.
• O seno (que mede o comprimento do cateto oposto no círculo unitário) cresce de modo estritamente monótono no intervalo $[-\pi/2,\pi/2]$; logo tem um inverso, o neste intervalo.
• a exponencial $\exp$ é invertível pelo logaritmo $\log$.

Resumimos:

• Toda função estritamente monótona (crescente ou decrescente) é invertível.
• Na inversão o domínio e imagem trocam os papéis.
• Se o domínio e imagem coincidem, obtemos o gráfico da função inversa pelo espelhamento do gráfico da função na diagonal $y = x$.

Algarismos

Um número real no dia-a-dia é escrito em notação decimal $$a_N \ldots a_1 a_0, a_{-1} \ldots$$ com $a_N$, , $a_1$, $a_0$, $a_{-1}$ , em $\{ 0, 1, \ldots, 9 \}$. Isto é, é como soma em potências de $10$ e com algarismos $0$, …, $9$. Por exemplo, $$321,34 = 3 \cdot 10^2 + 2 \cdot 10 + 1 + 3 \cdot 10^{-1} + 4 \cdot 10^{-2}.$$ Em vez da base decimal $b = 10$, existem outras. As mais comuns na informática são

• a base binária $b = 2$ com os algarismos $0$ e $1$, e
• a base hexadecimal $b = 16$ com os algarismos $0, ..., 9$ e $A$, $B$, $C$, $D$, $E$ e $F$ (que correspondem a $10$, $11$, $12$, $13$, $14$ e $15$).

Isto é,

• no conta-quilómetro binário, o último algarismo retorna à posição inicial após dois quilómetros, o penúltimo após $2^2 = 4$ quilómetros, e assim por diante,
• no conta-quilómetro hexadecimal, o último algarismo retorna à posição inicial após $16$ quilómetros, o penúltimo após $16^2 = 256$ quilómetros, e assim por diante.

Por exemplo, $$1101 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0$$ e $$A02F = 10 \cdot 16^3 + 0 \cdot 16^2 + 2 \cdot 16^1 + 15 \cdot 16^0.$$

1 Criptografia

A criptografia serve a proteger dados, e consegue isto por um embaralhamento (cifração) que praticamente pode unicamente ser invertido (decifração) com uma informação adicional secreta, a chave.

Outrora, a criptografia estudou a transformação de um $$\text{texto inteligível }$$ $$\Downarrow$$ $$\text{texto ininteligível }$$

tal que só uma informação adicional secreta, a chave, permita desfazê-la.

Hoje em dia, a criptografia estuda a transformação de

$$\text{dados inteligíveis}$$ $$\Downarrow$$ $$\text{dados ininteligíveis}$$

tal que só uma informação adicional secreta, a chave, permita desfazê-la.

Isto é, toda sequência de bites $1011...$ é uma número $n$ pela sua expansão binária $n = 1 + 0 \cdot 2 + 1 2^2 + 1 2^3 + \cdots$ e vice-versa.

• O ponto de vista de uma sequência de bites (ou, mais exatamente, de dígitos hexadecimais cujos dezasseis símbolos $0$ – $9$ e A – F correspondem a um grupo de quatro bites) é preferida na criptografia simétrica cujos algoritmos transformam-nas, por exemplo, por permutação e substituição dos seus dígitos.
• O ponto de vista de um número é preferida na criptografia assimétrica (com duas chaves) cujos algoritmos operam nele por funções matemáticas como a potenciação e exponenciação.

1.1 Dados

Dados referem-se classicamente, antes da época digital, a textos, hoje em dia a qualquer arquivo digital, sejam textos, imagens, sons, e assim por diante. Nos nossos exemplos, sempre suponhamos que os dados sejam um texto. Quando assumirmos o ponto de vista matemática, os dados referem-se a um número natural, isto é, um elemento em $0$, $1$, $2$, $3$, …

Mostramos pelos exemplos de textos e imagens como esta codificação, dos dados em (sequências de) números se faz: Recordemo-nos de que

• um bite é um dígito binário, isto é, uma das $2$ possibilidades $0$ ou $1$, e
• um baite a sequência de $8$ bites, isto é, uma das $2^8 = 256$ possibilidades entre $0 = 0000 0000$ e $255 = 1111 1111$.

Codificação de Textos

Um texto é uma sequência de símbolos. Há várias codificações que associam a cada símbolo um número; as duas mais conhecidas são

• a ASCII, que cobre todos os caracteres ingleses (e os símbolos de pontuação) e que envia um símbolo a um baite,
• a UTF-8, que inclui a ASCII e cobre todos os caracteres de todos os idiomas (por exemplo, do chinês, coreano, … e além disso, por exemplo, todos os símbolos matemáticos) e que envia um símbolo a $1$, $2$, $3$ ou até $4$ baites.

Por exemplo, $$0 \mapsto 48, ..., 9 \mapsto 57; A \mapsto 65, ..., Z \mapsto 90; a \mapsto 97, ..., z \mapsto 122.$$ Com efeito, o ASCII somente predetermina a codificação dos números $0 - 127$, isto é, todas as sequências de bites que começam com 0. Depois do ASCII,para internacionalizá-la, surgiram inúmeras codificações (por exemplo,

• ISO-8859-1 ou ISO-Latin-1 para os alfabetos latins na Europa ocidental e
• ISO-8859-5 para os alfabetos cirílicos usados na Europa oriental (por exemplo, na Bulgária ou Sérbia) e na Rússia.

Todas elas ocuparam o espaço dos números $128 - 255$ para acrescentar os símbolos do próprio alfabeto, isto é, todas as sequências de bites que começam com 1.

A codificação UTF-8 teve uma abordagem mais engenhosa: O número dos dígitos binários consecutivos iniciais iguais a $1$ nos primeiros $3$ bites, acrescentado por $1$, iguale o número de baites, de $1$ a $4$, do símbolo codificado. Isto é, ela envia um símbolo a $1$, $2$, $3$ ou até $4$ baites, onde $$\# \{ \text{baites} \} = \# \{ \text{dígitos binários consecutivos iniciais iguais a $1$} \} + 1$$

Por exemplo, o símbolo ç, a letra c com uma cedilha, tem $2$ baites e $$\text{ç} \mapsto 1011 0011 1100 0111.$$ Vemos que, com efeito, o número dos primeiros coeficientes consecutivos iguais a $1$ é $1$ (como já o segundo coeficiente é igual a $0$), o que, acrescentado por $1$, resulta em $2$, o número de baites de ç.

Codificação de Imagens (por um bitmap = mapa de graus das cores primárias)

Para imagens, o formato mais simples é o de um bitmap, um mapa de bites. Uma imagem

• é um conjunto de pixeis (por exemplo, $1024 \times 768$),

• cada pixel é uma cor, e

• cada cor é os seus graus de intensidade da luz das três cores primárias

  • Vermelho (= Red),
  • Verde (= Green) e
  • Azul (= Blue).

  O homem não consegue distinguir mais de 256 graus de cada cor primária,

  $\implies$ basta codificar cada pixel por três baites.

1.2 Chaves: A criptografia simétrica e assimétrica

Recordemo-nos de que a chave é a informação adicional secreta que pode ter várias formas a qual é sobretudo uma questão da conveniência. As mais usais são a

• de um número,
• de uma sequência de letras, por exemplo,
  • uma senha, ou
  • uma frase secreta (com espaços).

Por exemplo, no algoritmo antigo da Cítala ou bastão de Licurgo, a chave consiste da circunferência (em letras) do bastão usado, um número. Hoje em dia, um código PIN (= Número de Identificação Pessoal) ou senha são omnipresentes no nosso dia-a-dia; para facilitar a decoração, para datas muito sensíveis, é encorajada a decoração de completas frases (= múltiplas palavras) secretas.

A criptografia assimétrica depende de chaves maiores e por isso as armazena em arquivos (de textos com $64$ letras, chamados de ASCII-armor) de alguns quilobaites.

Historicamente, a chave para inverter a transformação (de dados inteligíveis em dados ininteligíveis) era tanto necessária para decifrar quanto para cifrar, a criptografia simétrica. Já foi usada pelo egípcios quase 2000 anos antes de Cristo.

Nos anos 70, surgiu a criptografia assimétrica, na qual as chaves para cifrar (a chave pública) e decifrar (a chave privada) são diferentes.

Com efeito, só a chave para decifrar é privada, guardada secreta, enquanto a para cifrar é pública, conhecida a todo mundo. (Porém, é possível, e muitíssimo útil, que as chaves trocam os seus papéis, a chave privada cifra e a pública decifra, a assinatura digital, explicada mais em baixo.)

Em comparação a criptografia simétrica, a criptografia assimétrica evita o risco de comprometimento da chave para decifrar envolvido

• na troca da chave com o cifrador, e
• na posse da chave do cifrador (além do decifrador).

Em particular o primeiro ponto, que permite comunicar seguramente com qualquer pessoa através de um canal inseguro, é uma grande vantagem em comparação à criptografia simétrica! Tão grande que, enquanto antes da era da internet a criptografia assimétrica era impensável, depois a internet ficou impensável sem a criptografia assimétrica.

Tamanho da Chave

A um nível de segurança comparável, os algoritmos da criptografia simétrica são mais econômicos que os da criptografia assimétrica.

Aqui mais econômicos quer dizer que os algoritmos simétricos

• são mais rápidos, e
• usam chaves menores. Por exemplo, o algoritmo assimétrico RSA usa chaves de pelo menos $2048$ bites, enquanto o algoritmo simétrico AES usa chaves de $128$ bites. (Esta diferença será explicada em Seção 9.5.)

Esta diferença se reflete pelo gerenciamento entre uma chave assimétrica ou simétrica:

• Uma chave assimétrica é armazenada em um arquivo (por exemplo, como arquivo de texto em um disco rígido, ou como arquivo em um cartão inteligente), e este arquivo é comumente assegurada por uma frase secreta (passphrase) que o usuário decora.
• Uma chave simétrica é decorada como senha, isto é, guardada na memória do usuário. (Na prática, esta senha é transformado por um hash criptográfico, como o MD5 ou SHA-256 a uma sequência de byes de um comprimento determinado, por exemplo, de $32$ baites. Padroniza o comprimento da chave e cifra para evitar uma leitura por outra pessoa.)

Exemplo de uma chave pública codificada em ASCII:

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: SKS 1.1.6
Comment: Hostname: pgp.mit.edu

mQENBFcFAs8BCACrW3TP/ZiMRQJqWP0SEzXqm2cBZ+fyBUrvcu1fGU890pd43J diW
IreHx/sbJdW1wjABeW8xS1bM67nLW9VVHUPLi9QP3VGfmqmXqbWIB7OxizZ PTDCWm
oymm/+TlTTAZWU6Wwvmjk88QlmU941tUvBsQ1cw1cAxw+2jLCgkz8XvW npMPKKj1f
sNZ/FcPVMC6dkwHAFc7Rm4DNibJzLvD8woL0vAdUR4HhOQli9+Fpv UO0KVVhOwF0f
14EURddA4qZVyPM8e3FvxiWF0JWJuxCuiBHh5ghT/Q+OQMMOJW VTwME5nQ87vohfX
gjRbYjW8gyLRqIjt2Gc7dNgIoKE5r/PABEBAAG0I0Vubm8g TmFnZWwgPGVubm8ubm
FnZWxAdC1vbmxpbmUuZGU+iQE5BBMBAgAjBQJXBQLPAh sDBwsJCAcDAgEGFQgCCQo
LBBYCAwECHgECF4AACgkQVJDsz4ujnoR03gf9HIIc pOSI1yokf6JZjH/Oon+FDoJd
7i7B1wfMyOKmSDsTbrJqimi7s8R9hsSljYuf/s TzMbGGCoHkOfnZyGuv3HovTO90x
g5JSsCTU/DhojHqANODJ23lTZFgW0vOmxkL KpRKOPiZ+xX3z9PjDNULFCBLV4s2+m
UABKbkKJLecytE8g4WWDkV7ePHrkTZyS sAoaNvLW6f0BxGmO0L4Igf35UG2ZbzMah
m8eFu6ADr3gQKO1DaiOhQsF5oInGq ymyaZyNCMR0CohWZuGT1DLVFUOzGos1p42Tl
BqylUJGw8ll9xeQJevAMf2xdrl DyRNxyy6ojOjXMzmf32CPQpI7JN7kBDQRXBQLPA
QgAwL9sFKBf2h8KLjHkfSXD EMMVgKdifO9J6F0ubS8l4vXj+DlnJusjxa7oLMIrxp
BT35y06pohtqwKMsxGEZ Uvx9MKk1NdU5OksPyvoSSVcIm4APzC/1pSFaHUjlWp3HI
4PC5yFBo3IMqIajtu PyYOB3A8O5iIIm8ip1BvEVHTruAOz/1wIFr+xgFmglqU2XvO
coDHz442h71CD0 2iDVjQyO8Cmb87AmSc+dV4iXUalK5+GQRe21lAhIB2jVprdFvx6
VJvsF7Xf+RB 2GsZ61v4glGgYFaXLDeRYwyearjGuE2thLo9RdGu2/gfyJFwij43Lc
7kGX1/rI YHOTPJTmv5QQARAQABiQEfBBgBAgAJBQJXBQLPAhsMAAoJEFSQ7M+Lo56
EoLMH /3AMzxXON2m0rXwFVnBStaYGAC7bQilAJdgoiYASAxS2KHphpvHQ8Y6BUOHv
xG Wp4v350kZkiMGDblOe63/6mFHizFg/PTxeRDJLS7hWp1RUASd47hmBbrjFDRHu
4i1mYHrHvQy6QXSO6z88fStgYFWcer+JALtlnJCs8cQ67wMRxjZPEjUj1uGrm6 skK
Y5LBJvTCj4GN3vPVExvmLvRXPgS0pgiCYPdqbxUY97VT9jzsHXeCmmNJO8t oUnlH0
HpIcNfP76d3vdBwnAkCarnxqcCPBMZ+0lJWYUeqmlRTIBsIMRTOpTi3x fdbVBxlb+
wJ/p8VnJSURox3xoxHaJCHeU==jKED

-----END PGP PUBLIC KEY BLOCK-----

Para comparar, o hash md5 (de 16 baites) da palavra “chave” em codificação hexadecimal (isto é, o alfabeto 0, …, 9, A, B, C, D, E, F) é

3fc75801d131d80c89186ce5d064dc2ba3.

Considerações Práticas

• Para aproveitar ambas as vantagens da criptografia simétrica e assimétrica, comunica-se frequentemente (por exemplo, ao navegar a um site seguro [pelo protocolo TSL])
  • primeiro com chaves assimétricas (para trocar uma chave simétrica), e
  • depois com uma chave simétrica.
• Na criptografia assimétrica, a comunicação pessoal da chave pública, pelo grande tamanho da chave pública, é inviável para o ser humano, Por isso, comumente
  • obtém-se a chave pública eletronicamente (e-mail, site, …), e
  • verifica-se por uma soma de verificação criptográfica (por exemplo, soletrando-a no telefone).
• Mesmo se uma chave assimétrica é desnecessária para um usuário cifrar por exemplo o seu disco rígido, as vezes revela-se na prática vantajosa: Atualmente só chaves assimétricas podem ser armazenadas em um cartão inteligente. Para decifrar o disco rígido cada vez que se liga o notebook,
  • em vez do usuário entrar a sua frase secreta (comprida),
  • é mais prático entrar o seu cartão inteligente no leitor.
  Assim, o usuário é mais inclinado a desligar (e assim cifrar) o seu notebook quando não o usa (quer dizer, quando está em maior risco).

Assinatura Digital

A chave pública e privada podem inverter os seus papéis: Assim só o dono da chave privada pode cifrar o texto, e todo mundo (que conhece a chave pública) pode decifrá-lo.

O que parece fútil é com efeito um uso (economicamente) importantíssimo da criptografia assimétrica. Ele chama-se assinatura digital, e serve para identificar a fonte de dados na internet: Com efeito, como só o dono da chave privada pode cifrar o texto tal que a chave pública o decifre, todo mundo que conhece a chave pública pode verificar que o texto cifrado provém do dono da chave privada.

1.3 Segurança

A criptografia assimétrica usa métodos matemáticos, mais exatamente aritmética modular, para cifrar. A segurança (= a dificuldade da decifração) da criptografia assimétrica é baseada em problemas matemáticos reconhecidos dificílimos há séculos.

A criptografia simétrica (como as funções de hash) usa métodos de cifrarão mais artesanais, que, de aparência, visam maximizar a difusão e confusão, principalmente por substituição e permutação (vide Seção 1.3.1). A segurança da criptografia simétrica é simplesmente baseada na renitência de falhar diante ataques de criptógrafos durante anos. Isto é, não é satisfatório de um ponto de vista transcendente, mais pelo menos prático. (A grande maioria das ciências, por exemplo, a medicina, confia quase exclusivamente nas estatísticas como fonte de conhecimento.)

Critérios para Segurança de um Algoritmo Criptográfico

O princípio de Kerckhoff postula que o

• algoritmo seja público.

Enquanto o conhecimento da chave compromete uma única cifração, o conhecimento do algoritmo compromete todas as cifrações. Um algoritmo público garante a dificuldade da decifração depender só do conhecimento da chave, mas não do do algoritmo. Quanto mais usado, tanto mais provável que o algoritmo será conhecido. Para ele ser útil, necessita ser seguro mesmo sendo público.

As metas de Shannon da

• Confusão respectivamente
• Difusão

desejam ofuscar a relação entre o texto cifrado e

• a chave respectivamente
• o texto claro

Idealmente, quando uma letra da chave respectivamente do texto claro muda, a metade do texto cifrado mude, isto é, cada letra do texto cifrado mude com uma probabilidade de 50%. Enquanto a saída da cifração, o texto cifrado, depende deterministicamente da entrada, do texto claro, e da chave, o algoritmo visa ofuscar esta relação no sentido de torná-la tão complicada, entrelaçada, embaralhada quanto possível: cada letra da saída, do texto cifrado, depende de cada letra da entrada, do texto claro, e da chave.

Uma boa confusão ou difusão dificulta ataques estatísticos sobre

• ou muitas chaves cifrando o mesmo texto claro,
• ou muitos textos claros cifrados pela mesma chave.

Segurança Perfeita

Textos claros geralmente não ocorrem com a mesma probabilidade. Ela depende, por exemplo, do idioma, do jargão ou do protocolo usado.

Moralmente, um método de criptografia é perfeitamente seguro se um texto cifrado gerado com ele não permite tirar conclusões sobre o texto claro correspondente. Isto é, a probabilidade que um texto claro e uma chave resultaram no texto cifrado é a mesma para todos os textos claros e todas as chaves.

Denote $p$ um texto claro e $\mathcal{P}(p)$ a sua probabilidade.

Um método de criptografia é chamado perfeitamente seguro se, para todo texto claro, a sua probabilidade é (estocasticamente) independente de qualquer texto cifrado. Em fórmulas, para todo texto claro $p$ e todo texto cifrado $c$, temos $\mathcal{P}(p | c) = \mathcal{P}(p)$.

Se um atacante interceptar um texto cifrado $c$, então ele terá nenhuma vantagem, isto é, a sua probabilidade de obter o texto claro é a mesma como se ele não conhecesse $c$.

Teorema de Shannon

Em 1949, Shannon provou o seguinte teorema, que explica sob quais condições um método de criptografia é perfeitamente seguro:

Seja finita o número de chaves e de texto claros e $\mathcal{P}(p)> 0$ para todo texto claro $p$. O método de criptografia é perfeitamente seguro, se

• a distribuição de probabilidade no espaço das chaves é a distribuição uniforme e
• para cada texto claro $p \in \mathcal{p}$ e todo texto cifrado $c$ existe uma única chave $k$ para obter $c$ a partir de $p$.

Isto é, desvios estatísticos tendem a enfraquecer o criptossistema. Em particular, é importante usar um gerador de números totalmente aleatório para as chaves.

One-time pad

Um criptossistema perfeitamente seguro é o one-time pad em que uma chave (do mesmo tamanho que o do texto claro) é adicionada (bite a bite) ao texto claro (vide ). Vide Seção 3.1.

Usar um tal criptossistema perfeitamente seguro é geralmente complicado na prática. Para aplicações em tempo real, como na Internet, eles são pouco usados.

Segurança Provada

Como segurança perfeita é inviável, a segurança é demonstrada

• ou por demonstração da resistência contra os ataques conhecidos,
• ou por redução à dificuldade computacional de um problema matemático (chamada de segurança comprovada).

Embora existam criptossistemas simétricos comprovadamente seguros (tal como o gerador pseudo-aleatório de Blum-Blum-Shub cuja segurança é redutível ao problema da computação do Resíduo Quadrático), os algoritmos mais eficientes e mais usados, tal como o AES, comprovam a sua resistência apenas contra ataques conhecidos, tais como as da criptoanálise diferencial ou linear.

Segurança Formalmente Provada

Os problemas usados pela criptografia assimétrica são todos NP: Todo algoritmo criptográfico cifra ou decifra uma mensagem com a chave em tempo polinomial no tamanho da chave em bites. Por outro lado, todos os algoritmos conhecidos para cifrar ou decifrar sem a chave levam tempo exponencial no tamanho da chave em bites.

Por enquanto, a conjectura sendo irresolvida, existem teoricamente algoritmos polinomiais para cifrar ou decifrar sem a chave em tempo polinomial; contudo, praticamente, após décadas de esforços contínuas da comunidade de criptógrafos em vão, parece improvável.

Exemplo. O exemplo inicial de um tal criptossistema comprovadamente seguro foi em 1982 o de Goldwasser e Micali para a segurança semântica pela redução ao problema do Resíduo Quadrático.

Dados $x$ e $N$ um produto de dois primos, é difícil determinar se $x$ é quadrático módulo $N$ (isto é, se existe $y$ tal que $x = y^2 \mod N$ ou não) se, e tão-somente se, o assim-chamado símbolo de Jacobi para $x$ é $+1$ e se os fatores primos de $N$ são desconhecidos.

O criptossistema de Goldwasser-Micali consiste em:

• um algoritmo de geração de chaves que produz
  • a chave privada como dois primos $p$ e $q$, e
  • a chave pública $N = pq$ e um número $x$ que é quadrático nem módulo $p$, nem módulo $q$ (tal que o símbolo de Jacobi de $x$ para $N$ é $1$, e para ambos os seus fatores $p$ e $q$ é $-1$). Por exemplo, se $p, q \equiv 3 \mod 4$, então $x = N-1$ serve.
• um algoritmo de cifração probabilístico: Se $m = (m_1, m_2, ...)$ são as bites da mensagem clara, então são gerados números $y_1, y_2, ...$ indivisíveis por $p$ e $q$ e a mensagem cifrada é $M = (M_1, M_2, ...)$ com $M_1 = y_1^2 x^{m_1}$, $M_1 = y_1^2 x^{m_1}$, …
• um algoritmo de decifração determinístico: Se $M = (M_1, M_2, ...)$ é a mensagem cifrada, então $m_1 = 0$ se, e tão-somente se, $M_1$ é quadrático módulo $N$, … o que é rapidamente determinado pelo conhecimento de ambos os fatores $p$ e $q$ de $N$.

Logo em seguida, em 1985, surgiu criptossistema o algoritmo ElGamal, que foi provado semanticamente seguro pela redução ao problema de Diffie-Hellman Decisório. Isto é, a segurança semântica (IND-CPA) do criptossistema ElGamal é provada sob a hipótese da dificuldade do problema de Diffie-Hellman Decisório que é uma variação do (dificílimo) problema da computação do logaritmo discreto (na aritmética modular); vide Seção 6.2 para mais detalhes. Isto é, prova-se que ganhar o jogo do IND-CPA é pelo menos tão difícil quanto o problema de Diffie-Hellman suposições de segurança com um fator polinomial.

Paradoxo

Cautela: A segurança teórica permanece uma idealização insuficiente para a realidade: Por exemplo, Ajtai e Dwork apresentaram em 1997 um criptossistema e o provaram teoricamente seguro pela redução a um problema difícil. Um ano depois, em 1998, este foi quebrado por Phong Nguyen e Jacques Stern.

O paradoxo é que comprovado não significa verdadeiro: um sistema comprovadamente seguro não é necessariamente verdadeiramente seguro, porque a prova se faz em um modelo formal que supõe

• certo funcionamento, atacante e objetivo de segurança e
• dificuldade do problema ao qual a prova é reduzido.

Por exemplo,

• O criptossistema implementado difere do criptossistemas formal.
• Um atacante pode ser mais forte do que aquele assumido.
• Um objetivo parcial já é suficiente para o atacante: Se, por exemplo, o objetivo de segurança é que o atacante não derive o inteiro texto claro do texto cifrado, então possivelmente já lhe baste derivar um trecho do texto claro.
• Improvável, mas teoricamente possível, é que o problema matemático subjacente é mais fácil do que suposto.

Além disto, a prova pode estar errada! Apesar desta incerteza, as provas de segurança são um critério (teoricamente necessário, mas praticamente insuficiente) útil para a segurança de um criptossistema.

Cenários de Ataques

O que exatamente significa segurança? A ideia que o atacante não pode derivar o texto original do texto cifrado é insuficiente, porque não significa que um atacante consiga outras informações relevantes sobre o conteúdo do texto claro (tais como trechos dele).

Mas até esta condição que não consiga informações sobre o texto claro é insuficiente nalgumas circunstâncias: Se

• o método de criptografia de chave pública for determinístico (ou seja, se a mesma entrada sempre retornar a mesma saída, como é o caso da criptografia RSA de livro didático, por exemplo) e
• o atacante pode limitar o número de possíveis textos claros (ele sabe, por exemplo que a mensagem cifrada é “sim” ou “não”),

então ele pode cifrar todos esses possíveis textos claros com a chave pública e comparar o texto cifrado com os seus textos cifrados obtidos.

Portanto, num método de criptografia assimétrica, sempre deve ser assumido que o atacante conheça a chave pública. Assim, ele pode cifrar qualquer texto claro de sua escolha e compará-lo com o texto cifrado para aprender algo sobre o texto claro desconhecido. Esse ataque é chamado de ataque de texto claro selecionado (Chosen Plaintext Attack = CPA).

Demarquemos a noção da segurança pela resistência contra vários cenários de ataques que ordenamos pelos recursos dos quais o atacante dispõe:

(Apenas) Texto Cifrado (ou CPO = ciphertext-only attack)

O atacante tem o texto cifrado de várias mensagens, todas cifradas pelo mesmo algoritmo. A tarefa do atacante é encontrar tantas mensagens claras quanto possíveis, ou melhor ainda, encontrar a chave ou chaves que foram usadas, o que permitiria decifrar outras mensagens cifradas com essas mesmas chaves.

Texto Claro Provável

O atacante tem o texto cifrado e supõe que o texto claro contenha certas palavras ou até frases inteiras (o crib). Por exemplo, a Enigma, máquina criptográfica usada pelos eixos de potências na Segunda Guerra Mundial, foi quebrada pela repetitividade das palavras nas mensagens; muitas comunicaram, por exemplo, diariamente o boletim meteorológico e o anunciaram por tais palavras (Wetterbericht em alemão) no início de cada tal mensagem.

Texto Claro Conhecido (ou KPO = known plaintext attack)

O atacante tem o texto cifrado e o texto claro correspondente. A tarefa é encontrar as chaves usadas ou um algoritmo que decifra outros textos cifrados pelas mesmas chaves. (A criptoanálise linear situa-se neste cenário.) Um exemplo recente é um ataque de 2006 ao protocolo Wired Equivalent Privacy (WEP) para cifrar uma rede local sem fio que explora a previsibilidade de partes das mensagens cifradas, os cabeçalhos do protocolo 802.11.

Texto Claro Joeirado ou Adaptativo (CPA = chosen plaintext attack)

O atacante tem o texto cifrado e o texto claro correspondente, e pode escolher os textos claros; assim que o atacante possa deliberadamente variar, ou adaptar, o texto claro e analisar as alterações resultantes no texto cifrado. (A criptoanálise diferencial situa-se neste cenário.)

Este é o cenário mínimo para criptografia assimétrica! Como a chave de criptografia é pública, o atacante pode cifrar mensagens à vontade. Logo, se o atacante pode reduzir o número de textos claros possíveis, por exemplo, ele sabe que são ou “Sim” ou “Não”, então ele pode cifrar todos os textos claros possíveis pela chave pública e compará-los com o texto cifrado interceptado. Por exemplo, o algoritmo modelar RSA (em Seção 8.1) sofre deste ataque, e nas suas implementações é preciso de preencher o texto claro por dados aleatórios para robustecê-lo contra este ataque CPA.

Texto Cifrado Seletivo (CCA = chosen ciphertext attack)

No ataque de texto cifrado selecionado o atacante seleciona diferentes textos cifrados (exceto o texto cifrado a ser decifrado) que serão decifrados para ele derivar a chave. Por exemplo, o atacante dispõe de um dispositivo que não é desmontável e cifra automaticamente.

No ataque de texto cifrado adaptativo os textos cifrados (exceto o texto cifrado a ser decifrado) são adaptados dependendo do texto obtido após cada decifração. Poucos ataques práticos se situam neste cenário, mas ele é importante para provas de segurança: Se a resistência contra os ataques neste cenário é comprovada, então a resistência contra todo ataque realístico de texto cifrado selecionado pode ser admitida.

Segurança Semântica

O termo “segurança polinomial” apareceu em 1984 em Goldwasser e Micali (1984).

Segurança Semântica IND-CPA

Os autores, Goldwasser e Micali, demonstraram subsequentemente que a segurança semântica é equivalente a IND-CPA, indistinguibilidade (IND) do texto cifrado sob texto claro selecionado (= Chosen Plain-text Attack):

Em um método de criptografia assimétrica, o atacante conhece a chave pública. Assim, ele pode cifrar qualquer texto claro de sua escolha e compará-lo com o texto cifrado para aprender algo sobre o texto claro desconhecido. Esse ataque é chamado de ataque de texto claro selecionado (CPA = Chosen Plain-text Attack). Um método de criptografia é seguro contra IND-CPA (indistinguibilidade do texto cifrado para textos claros selecionados), se nenhum atacante consegue distinguir o qual entre dois textos claros, que ele selecionou antes, corresponde ao texto cifrado, que recebeu depois.

Passos

O criptossistema é indistinguível sob ataque de texto claro selecionado se todo adversário de tempo polinomial probabilístico tiver apenas uma “vantagem” insignificante sobre adivinhação aleatória:

O jogo IND-CPA em quatro passos com restrição de tempo de execução polinomial (no comprimento [em bites] da chave $k$) para os cálculos de atacante (ao criar os dois textos claros, no segundo passo, e ao escolher o texto claro que corresponde ao texto cifrado, no quarto passo).

1. É criada um par de chaves, uma secreta e outra pública, ambas com $k$ bites. O atacante recebe a chave pública.

2. O atacante cria dois textos claros de tamanho igual $M_0$ e $M_1$.

3. A máquina criptográfica

   1. escolhe aleatoriamente um bit $b$ em $\{ 0, 1 \}$
   2. cifra $M_b$, e
   3. passa o texto cifrado ao atacante.

4. O atacante escolhe um bite $b'$ em $\{ 0, 1 \}$.

Um atacante que escolhe o bite $b'$ na quarta etapa aleatoriamente está com probabilidade $1/2$ correto. Um método de criptografia é chamado seguro contra IND-CPA se nenhum atacante tiver uma probabilidade de sucesso significantemente maior que $1/2$. Isto é, se $\mathcal{P}( b = b' ) - 1/2$ é insignificante. O adversário tem uma “vantagem” insignificante, se vence com probabilidade $\geq 1 / 2 + \epsilon (k)$, onde $\epsilon$ é uma função insignificante em $k$, isto é, para toda função polinomial (diferente de zero) $p$ existe $k_0$ tal que $\epsilon(k) < \frac{1}{p(k)}$ para todo $k > k_0$.

Uma diferença insignificante deve ser permitida porque é o atacante facilmente aumenta a sua probabilidade de sucesso acima de $1/2$ por adivinhar uma chave secreta e tentar decifrar o texto cifrado com ela.

Observação. Embora o jogo acima é formulado para um criptossistema assimétrico, pode ser adaptado ao caso simétrico, substituindo a cifração com a chave pública por um oráculo criptográfico (= uma função cujo funcionamento é totalmente desconhecido) que retém a chave secreta e cifra textos claros arbitrários a pedido do adversário.

Algoritmos Semanticamente Seguros

Algoritmos de criptografia semântica segura incluem El Gamal e Goldwasser-Micali porque a sua segurança semântica pode ser reduzida à solução dalgum problema matemático difícil, isto é, irresolúvel em tempo polinomial; nestes exemplos, o problema Diffie-Hellman decisório e o Problema do Resíduo Quadrático. Outros algoritmos semanticamente inseguros, como RSA, podem ser tornados semanticamente seguros por preenchimentos criptográficos aleatórios como o OAEP (= Optimal Asymmetric Encryption Padding).

Exemplo. O método de criptografia Elgamal é IND-CPA-seguro sob a hipótese de que o problema de Diffie Hellman Decisório seja difícil. Para provar a segurança, construamos a partir de um

• vencedor $A$ do jogo IND-CPA para El Gamal (isto é, se lhe é dada a cifração de uma de duas mensagens claras sob a chave pública, então ele identifica com probabilidade $1/2 + \epsilon$ à qual (das duas mensagens claras) ela corresponde),
• um decididor $S$ para DDH, isto é, dada uma base $g$ e expoentes $x$, $y$ e $z$ em $\{ 0, ..., p-1 \}$, decide em tempo polinomial se $g^z = g^{xy} \mod p$ ou não,

como se segue:

1. $S$ simula a geração das chaves e dá $g^x$ como chave pública a $A$. Porém, $S$ não sabe a chave secreta correspondente, sem $A$ o saber.
2. $A$ produz duas mensagens $m_0$ e $m_1$.
3. $S$ simula a cifração: Ele escolhe aleatoriamente um bite $b$ e define a cifração por $g^y, g^z m_b$.
4. $A$ decide se esta cifração corresponde a $m_0$ ou a $m_1$.

• Se $g^z = g^{xy}$, então a cifração é indistinguível de uma cifração normal e $A$ ganha com probabilidade $1/2 + \epsilon$.
• Se $g^z$ é aleatório, então $A$ só adivinha e ganha com probabilidade $1/2$.

A estratégia de $S$ é, portanto, optar por $g^z = g^{xy}$ se, e tão-somente se, $A$ está correto. Logo, a probabilidade que $S$ esteja correto é $1/2 + \epsilon/2$.

Segurança Semântica IND-CCA

Recordemo-nos de

• que um método de criptografia é seguro contra IND-CPA (indistinguibilidade de texto cifrado para textos claros selecionados), se nenhum atacante consegue distinguir o qual entre dois textos claros, que ele selecionou antes, corresponde ao texto cifrado, que recebeu depois, e
• que no ataque de texto cifrado selecionado (ou, mais exatamente, adaptativo) o atacante seleciona textos cifrados (exceto o texto cifrado a ser decifrado) que serão decifrados para ele derivar a chave.

Um método de criptografia é seguro contra IND-CCA (indistinguibilidade de texto cifrado para textos cifrados selecionados), se o atacante, no segundo e quarto passo do jogo de IND-CPA, pode mandar decifrar qualquer texto cifrado (exceto aquele a ser decifrado), e, mesmo assim, não consegue distinguir o qual entre dois textos claros corresponde ao texto cifrado:

1. O oráculo cria uma chave secreta.
2. O atacante manda decifrar quaisquer textos cifrados (exceto aquele a ser decifrado), calcula e produz dois textos claros de tamanho igual $M_0$ e $M_1$.
3. O oráculo
   • extrai um bit aleatório $b$ em $\{ 0, 1 \}$
   • cifra $M_b$, e
   • passa o cifrado ao atacante.
4. O atacante manda decifrar quaisquer textos cifrados, calcula e escolhe um bite $b'$ em $\{ 0, 1 \}$.

Exemplo. O ataque de Bleichenbacher de PKCS#1 de 1998 contra a variante de RSA seguro contra IND-CPA (mas, justamente, não contra IND-CCA).

Bellare e Namprempre mostraram em 2000 para uma cifra simétrica que se

• a cifra resiste contra IND-CPA, e
• a função unidirecional resiste (não é forjável) contra um ataque de mensagens selecionadas,

então a cifra com Encrypt-then-MAC resiste contra um ataque IND-CCA.

Maleabilidade

Um sistema criptográfico é maleável se é possível transformar toda mensagem cifrada $M$ de uma mensagem $m$, sem nenhum conhecimento sobre $m$, em uma mensagem cifrada $N = f(M)$ de alguma mensagem $n$ por uma função conhecida $f$ tal que a relação entre $m$ e $n$ seja conhecida.

Exemplo. Todos os criptossistemas comuns são maleáveis; veremos, entre outros, que o criptossistema ElGamal é maleável.

Como consequência prática, uma cifra maleável não permita verificar a autenticidade de uma mensagem, isto é, se foi alterada entre envio e receção. Logo, é mais suscetível a um ataque de Man-in-the-middle, um homem (no meio) entre dois correspondentes que interceta e forja as suas mensagens trocadas.

Se a maleabilidade é indesejada (para garantir a autenticidade da mensagem cifrada), então se anexa à mensagem um valor de uma função unidirecional, tal como um hash criptográfico, chamado de Código de Autenticação de Mensagem (MAC) da mensagem cifrada. (Chamado de Encrypt-then-MAC e usado, por exemplo, em VPNs, redes privadas virtuais. O hash não cifrado da mensagem clara, MAC-and-Encrypt é usado no protocolo SSH e o hash cifrado da mensagem clara no protocolo TLS que segura o protocolo HTTPS.) Embora um atacante possa alterar a mensagem cifrada $M$, não consegue alterar o seu MAC.

Observação. Existem cifras assimétricas não-maleáveis; a primeira tal cifra foi a de Cramer-Shoup.

Algoritmos Maleáveis

• O one-time pad que

  • cifra o texto claro por uma adição XOR com a chave, e
  • decifra o texto cifrado da mesma maneira.

  é maleável porque um bite no texto cifrado é invertido se, e tão-somente se, o bit correspondente no texto claro é invertido.

  Se o atacante sabe decifrar um trecho do texto cifrado, então ele pode alterá-lo para corresponder a qualquer outro texto do mesmo comprimento. Isto é: Se $m$ seja o texto claro, $k$ a chave secreta e $E(m) = m \oplus k$ o texto cifrado, então o texto cifrado de $m \oplus t$ para qualquer $t$ é $E(m) \oplus t = (m \oplus t) \oplus k = E(m \oplus t)$.

• No sistema criptográfico RSA, um texto claro $m$ é cifrado por $E(m) = m^e \mod n$ onde $e$ é a chave pública módulo $n$. Se $M = E(m)$ é um texto cifrado de um texto claro $m$, então o texto cifrado de $mt$ para qualquer $t$ é $$M \cdot t^e = E(m) \cdot t^e \mod n = (mt)^e \mod n = E(mt).$$ Por isso, quando implementado, o texto claro é primeiro preenchido aleatoriamente por um protocolo como OAEP ou o PKCS1.

• No sistema criptográfico ElGamal, um texto claro $m$ é cifrado pelo par $E(m) = (g^b, m A^b)$, onde $A = g^a$ é a chave pública para a base $g$. Logo, se o par $(g^b, c)$ é o texto cifrado de $m$, então, para qualquer $t$, o par $(g^b, t \cdot c)$, é o texto cifrado de $tm$.

CrypTool

É recomendado experimentar com o aplicativo CrypTool que

• apresenta mais de $300$ algoritmos criptográficos tais como os históricos (simétricos)

  • de César
  • da cítala, e
  • da Enigma,

  mas também os modernos simétricos e assimétricos, como

  • AES, e
  • RSA

e

• dá ao usuário as ferramentas estatísticas para tentar decifrar textos exemplares.

Além disto, explica a matemática por trás destes algoritmos, por exemplo, o Algoritmo de Euclides, por animações.

Tem duas versões diferentes, CrypTool 1 e CrypTool 2. Trabalhamos de preferência com o CrypTool 1.

2 Criptografia Simétrica Antiga

Apresentamos uns exemplos antigos de algoritmos criptográficos sobre textos: Historicamente, a criptografia estuda a transformação de um $$\text{texto inteligível }$$ $$\Downarrow$$ $$\text{texto ininteligível }$$

tal que só uma informação adicional secreta, a chave, permita desfazê-la.

Os algoritmos protótipos históricos são

• a substituição por César, que avança toda letra no texto claro pela mesma distância no alfabeto (a de Agosto era $1$ enquanto a de Caesar $3$), e
• a permutação do texto claro pelo bastão de Licurgo onde a fita é enrolada verticalmente mas o texto escrito sobre ela horizontalmente.

Veremos que mesmo com a presença de muitas chaves um algoritmo, como o dado pela permutação arbitraria do alfabeto que tem quase $2^{80}$ chaves, pode ser facilmente quebrado porque preserva regularidades como a da frequência das letras.

Como critério suficiente para uma boa segurança existe o da boa difusão por Shannon: Idealmente, se uma letra do texto claro muda, então a metade das letras do texto cifrado muda.

Veremos em Seção 3 como os algoritmos modernos, as redes da substituição e permutação, juntam e iteram os dois algoritmos protótipos complementares para atingir a meta da boa difusão por Shannon.

2.1 Substituição (= permutação das letras do Alfabeto)

Por traslado das letras do alfabeto

Este método foi usado por (Júlio) César (100 – 44 B.C.) e por Augusto (César) (63 – 14 B.C.): Fixa-se uma distancia $d$ entre letras em ordem alfabética, isto é, um número entre 0 e 25, e traslada-se (para frente) cada letra do alfabeto (latino) por esta distância $d$. Suponhamos que as letras sejam arranjadas em um anel; assim que o traslado de uma letra no fim do alfabeto resulte em uma letra no início do alfabeto.

Por exemplo, se $d = 3$, então $$A \mapsto D, B \mapsto E, ..., W \mapsto Z, X \mapsto A, ..., Z \mapsto C.$$

Existem $26$ chaves (incluindo a chave trivial $d = 0$).

Para decifrar, traslada-se cada letra pela distância $-d$, isto é, $d$ posições para trás. Se as letras do alfabeto forma uma roda, então as letras estão trasladadas

• na cifração no sentido horário, e
• na decifração no sentido anti-horário.

Pela ciclicidade (ou circularidade) da formação das letras, observamos que um traslado de $d$ posições no sentido anti-horário iguala a um de $26-d$ posições no sentido horário.

Questão: Para qual $d$ a cifração é auto-inversa, isto é, a cifração iguala a decifração?

Por permutação das letras do alfabeto

Em vez de substituirmos cada letra por outra trasladada pela mesma distância fixada $d$, substituamos cada letra por outra letra arbitrária, por exemplo:

Para podermos desfazer a cifração, é necessária que nunca duas letras sejam enviada a mesma letra! Isto é, permutamos as letras. Assim obtemos $26 \cdot 25 \cdots 1 = 26! > 10^{26}$ chaves ($\approx$ o número de senhas que podem ser formados com $80$ bites).

2.2 Permutação (= permutação das letras do texto claro)

A cítala ou o bastão de Licurgo (= legislador de Esparta cerca de 800 AC) é um bastão com o qual os espartanos cifravam como segue:

1. enrolar o bastão com um pano estreito,
2. escrever neste pano horizontalmente, isto é, no sentido da borda maior, e
3. desenrolar o pano do bastão.

As letras assim transpostas no pano podiam unicamente ser decifradas por um bastão com a mesma circunferência (e suficientemente comprido) pela mesma maneira como o texto foi cifrado:

1. enrolar o bastão com o pano,
2. ler este pano horizontalmente, isto é, no sentido da borda maior.

Aqui, a chave é o número dado pelo número das letras que cabem nesta circunferência.

Por exemplo, se o bastão tem uma circunferência de $2$ letras (e um comprimento de $3$ letras), as duas linhas

tornam-se as três linhas

que são concatenadas (para não revelarem nem a circunferência, nem o comprimento) à linha

2.3 Segurança dos Exemplos Históricos

Aplicamos os critérios para segurança em Seção 1.3.1 aos exemplos históricos.

Cifração de César

A Substituição (das letras do alfabeto por traslado) usada por César $$A \mapsto D, B \mapsto E, C \mapsto F, ..., W \mapsto Z, X \mapsto A, ..., Z \mapsto C.$$

viola todas as qualidades desejáveis, principalmente o princípio de Kerckhoff, que o algoritmo seja público:

Uma vez o método for conhecido, considerando a pequena quantidade de 25 chaves, o texto cifrado cede em pouco tempo a um ataque de força bruta, uma busca exaustiva que prova cada chave.

Substituição por permutação arbitrária das letras do Alfabeto

A Substituição (das letras do alfabeto por permutação arbitrária)

tem $26 \cdot 25 \cdots 1 = 26! > 10^{26}$ chaves, por isso um ataque de força bruta é computacionalmente inviável.

Mas ele viola as metas da difusão e confusão. Se a chave (= permutação do alfabeto) troca a letra $\alpha$ pela letra $\beta$, então há

• má confusão porque a substituição de $\beta$ na chave implica unicamente a substituição de cada letra $\beta$ no texto cifrado,
• má difusão porque a substituição de uma letra $\alpha$ no texto claro implica unicamente a substituição da letra correspondente $\beta$ no texto cifrado.

Com efeito, o algoritmo permite ataques estatísticos sobre a frequência de

• letras,
• bigramas (= pares de letras) e
• trigramas (= triplos de letras).

em português. Por exemplo,

• a letra mais frequente em português é ‘a’
• o bigrama mais frequente em português é ‘de’
• o trigrama mais frequente em português é ‘que’

$\implies$ Substituindo

• a letra mais frequente do texto cifrado à letra mais frequente em português (= ‘a’),
• o bigrama mais frequente do texto cifrado ao bigrama mais frequente em português (= ‘de’), …
• o trigrama mais frequente do texto cifrado ao bigrama mais frequente em português (= ‘que’), …

é um ponto de partida propício para decifrar o texto: Quanto mais texto cifrado, tanto mais provável que esta substituição coincide com a dada pela da chave para estas letras.

Por exemplo, o texto $$\text{GWQP VQX Q CQPQ XU GWQP G NQX VQX}$$ considerando que as três letras mais comuns do português são, nesta ordem, AEO e que $Q$, $G$ e $X$ aparecem respectivamente $6$, $4$ e $4$ vezes, obtemos $$\text{E*E* *AO A *A*A OU E*E* *AO *AO}.$$ Suponhamos que $*AO$ = $VAO$ e que $E*E*$ = $ELES$. Em particular, $V$ corresponde a $V$ e $P$ a $S$. Logo $$\text{ELES VAO A *ASA O* ELES *AO VAO}$$ para estarmos levados ao chute $$\text{ELES VAO A CASA OU ELES NAO VAO}.$$ Este exemplo é muito artificial pela sua brevidade que dificilmente permita formar uma frase que tenha no mesmo tempo um conteúdo típico e frequências de letras típicas. Como exercício, caro leitor, construa uma tal frase!

A cítala

A cítala viola

• o princípio de Kerckhoff, que o algoritmo seja público.

Com efeito, o valor máximo da circunferência é $< n/2$ onde $n$ = o número das letras do texto cifrado. Por isso, um ataque de força bruta, é viável.

Ela tem

• má difusão porque a substituição de uma letra $\alpha$ no texto claro implica unicamente a substituição da mesma letra $\alpha$ no texto cifrado.

Com efeito, o algoritmo permite ataques estatísticos sobre a frequência de

• bigramas (= pares de letras)
• trigramas (= triplos de letras), e
• assim por diante.

Por exemplo, propício seria a escolha da circunferência como o número $n$ que maximiza a frequência do bigrama ‘de’ entre as cadeias de letras nas posições $1, 1 + n, 1 + 2n, ...$, $2, 2 + n, 2 + 2n, ...$.

Por exemplo, se olhamos $$\text{ADABESACA}.$$ observamos que $d$ e $e$ são distanciados por três letras, o que nos leva ao chute que $$\text{ circunferência } = 3 \text{ letras},$$ e à decifração $$\text{ABA DE CASA}.$$

2.4 A Enigma

A enigma substitui o alfabeto, isto é, permuta as letras do alfabeta latim, mas cada letra por outro alfabeto; é uma substituição poli-alfabética.

Construção

O esquema elétrico, constituído por:

• Bateria (1),
• Teclado (2),
• O painel de ligações (3, 7) com cabo (8),
• o jogo dos cilindros (5) com o de entrada (4) e o de retorno (6), e
• o painel das lampadas (9)

Ao teclar uma letra, a corrente entra

1. pelo painel de ligações,
2. no cilindro de entrada,
3. no jogo dos cilindros,
4. no cilindro de retorno, e
5. percorre todo o caminho outra vez, no sentido inverso,
6. para finalmente ascender a lampada da letra cifrada.

Cada cilindro consiste em

• um cabeamento interno,
• um anel
• um rotor.

Ao teclar uma letra, o rotor à direita (o rotor rápido) avança uma posição (antes da corrente entrar nos cilindros). Figura 2.1 mostra a substituição da letra A

• ao primeiro, e
• ao segundo teclar.

Em posições inicialmente determinadas pela posição do anel do rotor rápido e do rotor no meio, avançam também, uma posição,

• primeiro o rotor no meio (o rotor médio) e
• depois o à esquerda (o rotor lento)

Após este primeiro avanço (ou do rotor médio, ou do rotor lento),

• o rotor médio avança (uma posição) após uma rotação completa do rotor rápido, isto é, 26 avanços, e
• o rotor lento avança (uma posição) após uma rotação completa do rotor médio, isto é, 26 avanços.

Isto é, os rotores comportam-se como os de um taxímetro ou conta-quilômetros, com a diferença que

• os da Enigma têm $26$ “algarismos” (correspondentes às letras do alfabeto) e
• os do velocímetro $10$ algarismos

(além do detalhe que o rotor médio avança mais uma vez após o avanço do rotor lento). Esta simulação da Enigma online mostra a cifração da Engima em ação.

Cada cilindro permuta o alfabeto inteiro por um cabeamento interno. Este cabeamento é fixo, e não pode ser mudado pelo usuário. Por dentro, há uma verdadeira salada de cabos:

O anel tem o entalhe que desencadeia o avanço do rotor seguinte. Por isso, a posição do anel determina o ponto em que o vai-um, o avanço do rotor seguinte, tem lugar. Como o rotor lento não tem sucessor, de fato só as posições do rotor médio e rápido têm efeito criptográfico.

O cilindro de retorno garante que a substituição seja auto-inversa, isto é, a cifração iguale à decifração. Também, um defeito criptográfico, implicou que uma letra nunca foi cifrada a si mesma para evitar um curto-circuito!

O cilindro de entrada igualmente permuta o alfabeto, mas só existia na versão comercial da Enigma.

Na versão militar, não fazia nada, isto é, a substituição é a identidade. Isto foi intuído por Marian Rejweski, criptógrafo polonês (pelo vício dos alemães na ordem) antes da Segunda Guerra Mundial. Assim conseguiu inferir o cabeamento dos cilindros da Enigma à distância, enquanto os franceses e britânicos estavam perdidos.

O painel de ligações troca uns pares de letras, na prática, dez. Por exemplo, na foto, A e J, e S e O.

Expresso por uma fórmula, a substituição $M$ (= Maquina) da Enigma descreve-se pela concatenação das substituições $$M = P \circ E \circ C_R(c_R) \circ C_M(c_M) \circ C_L(c_L) \circ R \circ C_L(c_L)^{-1} \circ C_M(c_M)^{-1} \circ C_R(c_R)^{-1} \circ E^{-1} \circ P^{-1}$$ onde

• $P$ é a substituição pelo Painel de ligações
• $E$ é a substituição pelo cilindro de Entrada
• $R$ é a substituição pelo cilindro de Retorno.
• $C_R(c_R)$, $C_M(c_M)$ e $C_L(c_L)$ são as substituições pelo Cilindro Rápido, Médio e Lento na posição $c_R$, $c_M$ e $c_L$, onde $$C_{R/M/L}(c_{R/M/L}) = T^{c_{R/M/L}} C_{R/M/L} T^{-c_{R/M/L}}$$ com
  • $c_{R/M/L} = r_{R/M/L} - a_{R/M/L}$ com
    • $r_{R/M/L}$ = posição do Rotor, e
    • $a_{R/M/L}$ = posição do Anel;
  • $T$ = a Traslação = a substituição que traslada cada letra do alfabeto à sua vizinha, isto é $A \mapsto B$, $B \mapsto C$, …, $Y \mapsto Z$, $Z \mapsto A$, e
  • $C_{R/M/L}$ = a substituição do cilindro.

O CrypTool 2 inclui uma animação do funcionamento criptográfico da Enigma. (Mencionamos que o funcionamento do anel é errôneo, porque não afeta o momento do vai-um.)

Ataque Estatístico pelas Frequências das Letras

Em particular, como a cada letra teclada (ao menos) o rotor rápido avança uma posição, isto é $r_R$ é aumentado por $1$, toda a substituição $M$ muda. (E a cada rotação completa do rotor rápido, após 26 avanços, o rotor médio avança, e igualmente, a cada rotação completa do rotor médio, após 26 avanços, o rotor lento avança.)

Como a cada letra teclada o rotor rápido avança uma posição,

• isto é $r_R \leadsto r_R + 1$, e
• logo $c_R = r_R - a_R \leadsto c_R + 1$,
• segue que $C_R(c_R+1) = T^{c_R} C_R(c_R) T^{-c_R}$ muda, e
• por isso toda a substituição $M$ muda!

Por isso, as mesmas substituições só reaparecem após uma rotação completa de todos os cilindros, em particular, do cilindro lento; isto é, após cerca de $17.000$ tecladas (a periodicidade). A Enigma é uma cifração por uma substituição poli-alfabética.

Recordemo-nos de que o ataque estatístico pelas frequências das letras

1. conta o número de cada letra no texto cifrado, e
2. associa a letra mais frequente no texto cifrado à letra mais frequente do idioma do texto claro, por exemplo, aqui, do alemão; em seguida, a segunda letra mais frequente no texto cifrado à segunda letra mais frequente do idioma do texto claro, e assim por diante.

Esta correspondência entre a frequência da letra cifrada e a da letra clara necessita que cada letra seja substituída pela mesma substituição!

Logo, o ataque estatístico pela frequência das letras (por exemplo, da língua alemã) para decifrar o texto,

• na teoria, aplica-se em textos cujo número de letras é um grande múltiplo desta periodicidade de $17.000$ (porque, por exemplo, todas as letras nas posições 1, 17.001, 34.001 e assim por diante são substituídas pela mesma substituição); por exemplo, em um texto com $850.000$ letras, um livro espessíssimo;
• na prática, não se aplica, porque, por ordem, as mensagens alemãs tinham no máximo $250$ letras.

Chaves

Para a Engima I, há quatro fatores:

• Ordem e Escolha dos Cilindros: Foram escolhidos $3$ (o lento, no meio e o rápido) entre $5$ cilindros e em qualquer ordem, resultando em $5 \cdot 4 \cdot 3 = 60$ possibilidades.

• Posição do Anel: Determina a qual ponto o cilindro seguinte inicialmente avança uma posição, isto é, quando a rodada inicial se completa. Depois, uma rodada se completa a cada $26$ letras. Há $26$ posições ($1$ – $26$) do anel para o rotor rápido e no meio (enquanto a posição do anel do rotor lento não importa, porque não implica um avanço de um cilindro em seguida), resultando em $26 \cdot 26 = 676$ possibilidades.

• Posição do Rotor: Determina em qual ponto a corrente inicialmente entra. Para cada um dos $3$ rotores, há $26$ possíveis posições ($A$ – $Z$), resultando em $26 \cdot 26 \cdot 26 = 17.576$ posições. Por causa do mecanismo do escalonamento, $26 \cdot 26 = 676$ posições entre elas são criptograficamente redundantes, sobrando $17.576 - 676 = 16.900$ possibilidades.

• Conexões do Painel: Há até $13$ cabos com dois conectores para conectar as $26$ letras do alfabeto.

  1. Para o primeiro cabo, há $26$ possibilidades para a letra do conector entrante e $25$ possibilidades para a letra do conector sainte. Como não importa a ordem dos $2$ conectores, sobram $[26 \cdot 25] / 2$ possibilidades.
  2. Semelhantemente, para o segundo cabo, há $24$ possibilidades para a letra do conector entrante e $23$ possibilidades para a letra do conector sainte. Como não importa a ordem dos $2$ conectores, sobram $[24 \cdot 23] / 2$ possibilidades.
  3. …

  Em geral, para o cabo $n$, há $n(n-1)/2$ possibilidades.

  Como a ordem em que os $13$ pares de letras foram conectadas pelos cabos não importa, divide-se por $13 \cdot 12 \cdots 2 \cdot 1 = 13!$.

  Ao total, obtemos $$26 \, 25 \cdot 24 \, 23 \cdots 2 1 / (2 \cdots 2) \cdot (13 \cdot 12 \cdots 1)$$ possibilidades. Durante a guerra, a partir de Agosto 1939, foram conectados $10$ pares de letras, dando $$26 \, 25 \cdot 24 \, 23 \cdots 8 \, 7 / (2 \cdots 2) \cdot (10 \cdot 9 \cdots 1) = 150.738.274.937.250$$ possibilidades.

Resumimos que há

• $60$ possibilidades para os cilindros,
• $676$ possibilidades para as posições dos anéis,
• $16.900$ possibilidades para as posições dos cilindros, e
• $150.738.274.937.250$ possibilidades para os pares de letras conectados pelos cabos,

o que dá ao total $$60 \cdot 676 \cdot 16.900 \cdot 150.738.274.937.250 = 103.325.660.891.587.134.000.000 \sim 10^{23}$$ possibilidades, mais o menos o número de sequências de $80$ bites. (Por exemplo, o DES (= Data Encryption Standard) utiliza uma chave de $56$ bites.)

Na Segunda Guerra Mundial as mensagens enviadas pelos alemães tiveram, por ordem, no máximo $250$ letras. Por isso:

• A posição do anel médio importava pouquíssimo, porque o anel médio só avança a um múltiplo (o qual em média valia $13$) de $26$. Isto é, este avanço raramente ocorre.
• A posição do anel no início importava mais, mas não tanto, porque em média o avanço ocorre após $13$ tecladas, um número maior do que o número de letras da maioria das palavras alemães.

Logo, importam criptograficamente

• as $60$ possibilidades para os cilindros (rápido, médio e lento),
• as $16.900$ possibilidades para as posições do rotor rápido, médio e lento, e
• as $150.738.274.937.250$ possibilidades para os pares de letras trocadas.

A bomba de Turing ajudou a reduzir estas possibilidades, sobretudo as do maior fator, as ligações do painel. Sobraram ainda $$60 \cdot 16.900 = 1.014.000$$ possibilidades. Considerando a força de trabalho de $4200$ pessoas (entre elas $80\%$ mulheres) em Bletchley Park, o centro criptográfico inglês, neste ponto, um ataque de força bruta é viável, isto é, provando exaustivamente todas as possibilidades sobrantes.

A Bomba de Turing

Presumindo uma configuração do painel de ligações e um crib, uma palavra (alemã típica) que provavelmente ocorre no texto cifrado, a bomba de Turing (o nome deriva-se do som de uma bomba-relógio que a primeira tal máquina, a bomba criptográfica polonesa, emitia) elimina muitas posições de cilindros inválidas, da seguinte maneira:

1. Intui um crib, uma palavra provável, por exemplo,

   • OBERKOMMANODERWEHRMACHT, (= comando supremo do exercito alemão)
   • WETTERBERICHT (= previsão do tempo)
   • EINS (= o número um)

   e compara com um trecho do texto cifrado. Para encontrar o trecho certo, toma em conta que a Enigma nunca cifrava uma letra a si mesma!

   1	2	3	4	5	6	7	8	9	10	11	12	13
   W	E	T	T	E	R	B	E	R	I	C	H	T
   A	R	E	S	T	U	W	L	S	K	H	I	O

2. Cria o menu, um diagrama do percurso de uma letra dado pelas substituições entre o texto claro e o texto cifrado; aqui obtemos o circuíto

   R	—	2	—	E
   $\mid$				$\mid$
   9				3
   $\mid$				$\mid$
   S	—	4	—	T

   Isto é, são trocadas as letras

   • $R$ e $E$ na segunda posição,
   • $E$ e $T$ na terceira posição,
   • $T$ e $S$ na quarta posição, e
   • $S$ e $R$ na nona posição.

3. Intui um conector do painel de ligações que troca uma das letras do circuito, por exemplo a troca entre $R$ e $Z$.

Então, a Bomba de Turing, fixados

• uma palavra provável, aqui WETTERBERICHT,
• o texto cifrado, aqui ARESTUWLSKHIO, e
• um conector no painel de ligações, aqui entre $R$ e $Z$

provou cada posição de cilindros para a sua compatibilidade com os circuitos do menu, da seguinte maneira:

Recordemo-nos de que a substituição da uma letra pela Enigma se descreve pela concatenação $M$ das substituições seguintes $$M = P \circ E \circ C_R \circ C_M \circ C_L \circ R \circ C_L^{-1} \circ C_M^{-1} \circ C_R^{-1} \circ E^{-1} \circ P$$ onde

• $P$ é a substituição pelo painel de ligações
• $E$ é a substituição pelo cilindro de entrada
• $R$ é a substituição pelo cilindro de retorno, e
• $C_R$, $C_M$ e $C_L$ são as substituições pelo cilindro rápido, médio e lento.

Para facilitar,

• tomamos em conta que $E = \mathrm{id}$ é a identidade, e
• abreviamos $$C := C_R \circ C_M \circ C_L \circ R \circ C_L^{-1} \circ C_M^{-1} \circ C_R^{-1}$$

Isto é, $$M = P \circ C \circ P$$

Para destacar a dependência da substituição $C$ da posição $p$ da letra no texto a ser cifrado (pelo avanço do cilindro rápido a cada letra teclada), denote $$C(p) = \text{ a substituição pelos cilindros na posição $p$ do texto. }$$ (Conforme à notação anterior e supondo que o cilindro no meio não avance, ela deveria ser $C(\mathbf{c} + (0, 0, p))$ onde $\mathbf{c} = (c_L, c_M, c_R)$ é a configuração inicial do cilindro lento, médio e rápido.) Aqui para $p = 2$, obtemos $$\mathbf{E} = P (C(2) (P(\mathbf{R}))).$$ Como o painel de ligação troca as letras em pares, a substituição pelo painel de ligação é auto-inversa, isto é, $P \circ P = \mathrm{identidade}$. Por isso, ao aplicarmos $P$ a ambos lados desta equação, $$P(\mathbf{E}) = C(2) (P(\mathbf{R}));$$ Em seguida, da mesma maneira, $$P(\mathbf{T}) = C(3) (P(\mathbf{E})) = C(3) C(2) (P(\mathbf{R}));$$ e assim por diante para as outras letras no circuito, até $$P(\mathbf{R}) = C(9) \circ C(4) \circ C(3) \circ C(2) (P(\mathbf{R})),$$ fechando o circuito.

Isto é, sob esta configuração dos cilindros, obtemos que a substituição $C = C(9) C(4) C(3) C(2)$ deixa a letra $P(\mathbf{R})$ invariante, $$C(P(\mathbf{R})) = P(\mathbf{R}).$$

Concluímos que cada tal circuito (obtido pelo texto claro e cifrado) exclui muitas configurações. A Bomba calculou quais.

Alan Turing calculou quantas configurações de posições de cilindros são em média compatíveis para um Crib com dado número de circuitos e letras :

As equações acima implicam também, a partir de

• uma configuração válida e
• a troca de uma letra do circuito por um conector do painel de ligações,

todas as outras trocas das letras no circuito pelo painel de ligações:

Por exemplo, dado $P(\mathbf{R})$, o valor $P(\mathbf{E})$ define-se por $$P(\mathbf{E}) = C(2) (P(\mathbf{R}));$$ em seguida, $$P(\mathbf{T}) = C(9) (P(\mathbf{E})) = C(9) C(2) (P(\mathbf{R}));$$ e assim por diante, obtendo as trocas de todas as letras do circuito: $\mathbf{R}$, $\mathbf{E}$, $\textbf{T}$ e $\textbf{S}$.

Como a validade da chave era um dia, e a mesma entre todas as naves (e entre todas as aeronaves e entre todos os trens), logo que uma chave foi obtida, todas as mensagens entre todas as naves durante este dia podiam ser decifradas com ela. Mudavam as posições dos rotores e conectores do painel cada dia, e a escolha e ordem dos cilindros cada mês.

Destacamos a importância do crib, da palavra alemã típica, neste método. Os aliados até provocaram pelas suas manobras certas mensagens para aplicar este método. Caso contrário, não conseguiram por exemplo decifrar a comunicação entre os condutores de trem por desconhecimento do jargão (= gírias profissionais) entre eles.

3 Criptografia Simétrica Moderna ou Cifras de Feistel

Hoje em dia, a criptografia estuda a transformação de

$$\text{dados inteligíveis}$$ $$\Downarrow$$ $$\text{dados ininteligíveis}$$

tal que só uma informação adicional secreta, a chave, permite desfazê-la.

3.1 One-time Pad

O One-time pad (= Bloco de Uso Único) adiciona (pela operação XOR, isto é, ou exclusivo, a disjunção exclusiva) cada baite do texto claro $t$ com o baite (na posição) correspondente de uma chave $c$ que

• é do mesmo comprimento, e
• é descartada após uso, isto é, não será usada para cifra outros textos claros.

Isto é, o texto cifrado $T = (T_1, T_2, ...)$ é $$T = t \oplus c = (t_1 \oplus c_1, t_2 \oplus c_2, ...).$$ Este método de cifração é tão seguro quanto teoricamente possível!

Se o texto claro tem um único bloco $t$, então a simples adição (XOR) de uma chave, o one-time pad, é um algoritmo seguro. Porém, é frequentemente inconveniente ou até praticamente impossível ter uma chave tão grande quanto o texto claro: Por exemplo,

• para cifrar um disco rígido, precisa outro do mesmo tamanho para guardar a chave, e
• para cifrar a comunicação em uma rede (por exemplo, sem fio), precisaria saber já antes quanto texto será transferido.

Na prática, imagine-se um agente duplicar gigabaites de ruído em dois meios de armazenamento, por exemplo, um disco rígido e pendrive, e levar um destes meios para cifrar a sua comunicação pelo one-time pad.

Infelizmente, é uma péssima ideia (apesar de ser tão natural) de usar a mesma chave para dois blocos diferentes: se, por exemplo, o texto claro tem dois blocos $b'$ e $b''$, então, com este algoritmo, a soma (XOR) $$(b' \oplus c) \oplus (b' \oplus c) = b' \oplus b''$$ dos dois blocos cifrados $b' \oplus c$ e $b'' \oplus c$ iguala a soma $b' \oplus b''$ dos dois blocos claros (porque a adição XOR é por definição auto-inversa, isto é $x \oplus x = 0$ independente do dígito binário ser $x = 0$ ou $x = 1$)!

Pode ser visto como a cifração do primeiro bloco por one-time pad cuja chave é o segundo bloco. Infelizmente, o segundo bloco não é uma boa chave, porque longe de ser aleatório; ao contrário, normalmente o seu conteúdo semelha ao do primeiro bloco, isto é, a chave é previsível.

3.2 Cifras de Feistel

Por isso, é mais seguro aplicar uma substituição do bloco por outro segunda a escolha da chave.

Porém, o alfabeto desta substituição seria gigantesco, e, por isso, este ideal é praticamente inatingível, sobretudo sobre um hardware tão limitado quanto o de um cartão inteligente com o seu processador de $8$ bites.

Para um bloco de por exemplo, $16$ baites, esta tabela de substituição teria horrendos $2^{256} \cdot 16$ baites. Por isso, por exemplo, o AES adiciona a chave; depois substitui só cada baite, cada casa do bloco, uma tabela de substituição de $2^8 = 256$ entradas de $1$ baite; em seguida, permuta as casas. Veremos que estas operações se complementam tão bem que são quase tão seguros como uma substituição do bloco inteiro. Isto é, em compensa da ausência de uma substituição do bloco inteiro por outro, a permutação imita esta substituição gigantesca da melhor maneira.

Uma Cifra de Feistel ou uma rede de substituição e permutação (abreviada SPN para Substitution Permutation Network) agrupa o texto (= sequência de baites) em blocos de $n$ baites (por exemplo, $n = 16$ para AES e $n = 2$ no nosso modelo prototípico) e cifra cada bloco pela iteração (por exemplo, $10$ vezes no AES, e $5$ vezes no nosso modelo prototípico) dos três seguintes passos, em dada ordem:

1. adição (XOR) da chave,
2. substituição do alfabeto (que opera em cada sub-bloco do bloco), e
3. permutação (entre todos os sub-blocos do bloco).

Isto é, após

1. a adição (por Ou Exclusivo) da chave como no One-time pad,

são aplicadas

2. a substituição do alfabeto (por exemplo,
   • no algoritmo de Heys, cada letra hexadecimal por outra, ou
   • no algoritmo AES cada baite, par de letras hexadecimais, por outro), e
3. a permutação do texto (do passo atual, chamado de estado), por exemplo, por exemplo, no AES, que agrupa o texto em um quadrado de baites (= pares de letras hexadecimais), são permutas as casas nas linhas (e colunas).

Estas duas simples operações,

• a substituição do alfabeto, e
• a permutação do texto

complementam-se muito bem, isto é, geram alta confusão e difusão após de poucas iterações.

Na primeira e última rodada, os passos antes respetivamente depois da adição da chave são omitidos porque não aumentam a segurança criptográfica: Como o algoritmo é público (segundo o critério de Kerckhoff), qualquer atacante pode desfazer os passos que não necessitam o conhecimento da chave.

3.3 Modelo Prototípico por Heys

Usamos o algoritmo de Heys (2002) como modelo simples de uma cifra de Feistel que

• divide o texto claro em blocos de $16$ bites, e
• subdivide cada bloco em $4$ blocos de $4$ bites

e em cada uma das primeiras rodadas $1$, $2$ e $3$,

1. Adiciona a chave da rodada (para cada rodada, tem uma chave correspondente independente) ao bloco, $B \mapsto B \oplus C$.

2. Substitui cada um dos $4$ sub-blocos de $4$ bites pela tabela

   0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
   E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

3. Troca o bite $i$ do sub-bloco $j$ com o bite $j$ do sub-bloco $i$;

Na penúltima $4^{\mathrm{a}}$ rodada

1. Adiciona a chave da rodada ao bloco, $B \mapsto B \oplus C$.
2. Substitui cada um dos $4$ sub-blocos de $4$ bites pela tabela.

Na última $5^{\mathrm{a}}$ rodada

1. Adiciona a chave da rodada ao bloco, $B \mapsto B \oplus C$.

Isto é:

• Na $5^{\mathrm{a}}$ rodada, os passos seguintes, a substituição e a permutação, são omitidos, pois o algoritmo sendo público (pelo princípio de Kerckhoff) podem ser desfeitos por qualquer decifrador, sem ele conhecer a chave. Isto é, de um ponto de vista criptográfico, são supérfluos.
• Na $4^{\mathrm{a}}$ rodada, o último passo, a permutação, é omitido, pois ele só permutaria a última $5^{\mathrm{a}}$ chave. Isto é, de um ponto de vista criptográfico, é supérfluo.

A tabela origina do algoritmo DES e e comumente chamada de S-box, caixa de substituição.

3.4 Criptoanálise Diferencial

Para compreender as razões por trás das escolhas de cada passo de um algoritmo criptográfico simétrico moderno que cifra em blocos, tal como o AES, precisa-se de entender contra quais ataques se robustece. Um dos mais conhecidos ataques é o da criptoanálise diferencial que vamos explicar agora pelo exemplo da cifra de bloco prototípica de Heys:

O sonho de todo decifrador é poder aprender se uma parte da chave escolhida é correta, isto é, se coincide com a parte correspondente da chave usada para cifrar o texto: Por exemplo, no algoritmo de Heys a chave consiste de $16$ bites: Se for possível saber, para $8$ bites da chave provada, se eles coincidem com os bites correspondentes da chave correta, então o decifrador

• ao invés de provar, por um ataque de força bruta, todas as combinações possíveis, de que existem $2^{16} = 65536$,
• apenas, todas as combinações possíveis destes $8$ bites (de que existem $2^8 = 256$) e dos $8$ restantes 16 (de que existem $2^8 = 256$).

Isto é, o número de combinações que precisam ser provadas foi reduzido de $2^{16} = 65536$ a $2 \cdot 256 = 512$.

Mais exatamente, a chave consiste de $4$ blocos de $4$ bites. Daremos um exemplo da criptoanálise abaixo em que o decifrador terá um critério probabilista para decidir se $2$ dos blocos, isto é, $8$ bites, da chave provada são corretos.

Critério de Decifração

No ataque de força bruta, o decifrador, para cada chave possível, decifra o texto cifrado com ela. Para saber se a chave é correta, isto é, se coincide com a chave usada para cifrar o texto, o decifrador verifica se o conteúdo seja inteligível; por exemplo, pelo critério de

1. contar as frequências das letras, pares e triples do texto decifrado, e
2. compará-las às frequências do idioma provável em que o texto claro foi escrito: Se elas se aproximam, então, provavelmente, o texto claro é inteligível e a chave usada pelo decifrador é a usada pelo cifrador.

Se a cifra tem uma única rodada, então este critério se aplica. Porém, se a cifra tem duas ou mais rodadas, e o decifrador executa a última rodada do algoritmo da decifração com certa chave, então este critério não presta mais porque o texto obtido é a saída do algoritmo da cifração (com a mesma chave) da penúltima rodada (logo, de qualquer forma, ininteligível). Ao invés dele, o critério da criptoanálise diferencial para ter encontrado a chave correta é probabilista: a chave provada é provavelmente correta se, para uma determinada diferença “entrante” $\Delta X$ e uma determinada diferença “sainte” $\Delta Y$, pares de textos claros com diferença $\Delta X$ resultam na penúltima rodada com determinada probabilidade em pares de textos cifrados com diferença $\Delta Y$.

Para a criptoanálise diferencial ser aplicável, o decifrador precisa de poder cifrar pelo cifrador (pela mesma chave)

• um número arbitrário de textos claros
• com conteúdos arbitrários, e

em seguida,

• examina os textos cifrados.

A criptoanálise diferencial explora a alta probabilidade da propagação de uma diferença $\Delta X = X' \oplus X''$ entre dois textos claros $X'$ e $X''$ a uma diferença $\Delta Y = Y' \oplus Y''$ entre os dois textos cifrados $Y'$ e $Y''$ de $X'$ e $X''$ na penúltima rodada. (Recordemo-nos de que $X' \oplus X''$ é a adição XOR bite a bite, em que a saída é $1$ se, e tão-somente se, as duas entradas são diferentes. Isto é, $\Delta X$, indica todos os bites em que $X'$ e $X''$ diferem.)

Chamemos este par $D = (\Delta X, \Delta Y)$ o diferencial. Para a criptoanálise diferencial ser eficiente, é preciso existir um diferencial $D$ com alta probabilidade $p_D$ (onde alto é quantificado em Equação 3.1); isto é, entre todos os pares entrantes com a diferença $\Delta X$, a probabilidade de um par sainte ter diferença $\Delta Y$ (na penúltima rodada) é $p_D$. Mais exatamente, o cifrador cifrará um número estatisticamente significante de pares ($> 1/p_D$) de textos claros com diferença $\Delta X$ para contar o número de pares dos textos cifrados com diferença $\Delta Y$.

Frequência das Diferenças para uma Tabela de Substituição

Observemos que para uma aplicação $A$ afim (isto é, dada por um polinômio de grau $1$, ou, equivalentemente, a composição

• de uma aplicação linear, isto é, $A(x \oplus y) = A(x) \oplus A(y)$ para todo $x$ e $y$, e
• de uma traslação, isto é, $A(x) = x \oplus x_0$ para algum $x_0$ fixo),

o diferencial $(\Delta X, \Delta Y)$ independe do par $X'$ e $X''$ entrante: Se a aplicação $A$

• é linear, então sempre, isto é, para quaisquer par com diferença $\Delta X$ o resultado é $\Delta Y = A(\Delta X)$, e se
• é uma traslação, isto é, $A = \cdot \oplus a_0$ para algum $a_0$ fixo, então sempre $\Delta Y = \Delta X$.

Aplicada esta observação à uma cifre de Feistel, vemos que

• a permutação é uma aplicação linear,
• a adição da chave é uma traslação,

isto é, a diferencial independe do par $X'$ e $X''$ entrante. Porém, a diferença sainte $\Delta Y$ da substituição não é determinada apenas pela diferença $\Delta X$, mas ela depende de $X'$ e $X''$!

Logo, para encontrar tal diferencial $D$ com uma alta probabilidade $p_D$, precisamos de investigar apenas a tabela de substituição. Estamos interessados na frequência de uma diferença sainte $\Delta Y$ dada uma diferença entrante $\Delta X$: Dada $\Delta X$, há $2^4 = 16$ possibilidades para $X'$ (e o qual determina $X'' = X' \oplus \Delta X$), e contamos as frequências das $2^4 = 16$ possíveis saídas $\Delta Y = 0,1, ..., F$.