Curso de Criptografia

UFAL, Maceió — Inverno 2019

Inverno 2019

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

e

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:

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

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 (simétrica) histórica trata textos e dispõe de duas operações:

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,

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:

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

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

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

Roteiro

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

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

  2. 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 é,

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

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

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

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

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

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

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

  9. Este capítulo dá

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

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

  12. Este capítulo explica

Livros de Referência

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

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:

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

Por exemplo, o conjunto

Podemos comparar dois conjuntos AA e BB:

Podemos formar um novo conjunto a partir de dois conjuntos AA e BB:

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×BA \times B o seu produto cujos elementos são (a,b)(a,b) para aa em AA e bb em BB, isto é, A×B={(a,b) para a em A e b em B}. A \times B = \{ (a, b) \text{ para } a \text{ em } A \text{ e } b \text{ em } B \}. Se B=AB = A, escrevemos A2A^2 em vez de A×AA \times A, e A3A^3 em vez de A×A×AA \times A \times A, e assim por diante. Por exemplo, 2\mathbb{R}^2 é o plano (euclidiano), e 3\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)= expressão em x f(x) = \text{ expressão em $x$} onde na expressão figuram

Por exemplo:

  1. A distância ss percorrida por um objeto na queda livre depende do tempo da queda tt: vale s=gt2s = g \cdot t^2 onde g=9,8m/s2g = 9,8 \mathrm{m}/\mathrm{s}^2 é a constante da aceleração gravitacional da terra.
  2. A forca de atração KK entre duas massas mm' e mm'' depende de mm', mm'' e a distância rr entre elas: Pela lei gravitacional de Newton K=G(mm)/r2K = G (m' m'')/r^2 onde G=6,671011Nm2kg2G = 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:

  1. 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 11, 22, 33, … e o preço correspondente de 100100 Centavos, 2020 Centavos, 55 Centavos, …

Definição. Uma função ff é uma regra que associa a cada elemento xx de um conjunto XX exatamente um elemento yy de um conjunto YY.

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

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

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

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

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

obtemos pela substituição da variável por um número real como 0,50,5, 11, 22, 10001000, …

Em mais detalhes:

Coordenadas Cartesianas de um ponto nos eixos xx e yy

De vez em quando, para destacar que um objeto, por exemplo, uma função h:XYh \colon X \to Y, depende de outro objeto, por exemplo, de um conjunto DD ou uma ênupla ww, escrevemos h(D)h(D) ou hDh_D respetivamente h(w)h(w) ou hwh_w em vez de hh.

Aplicação

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

dizemos que manda ou envia cada argumento xx em XX a um único valor yy em YY.

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

Uma função manda ou envia cada argumento xx em XX a um único valor yy em YY (ou associa a cada xx um único yy). Escrevemos xy x \mapsto y e denotemos este valor yy por f(x)f(x). Frequentemente, X=X = \mathbb{R} ou X=××X = \mathbb{R} \times \cdots \times \mathbb{R} e Y=Y = \mathbb{R} ou Y={±1}Y = \{ \pm 1 \}. Por exemplo, a função f:f \colon \mathbb{R} \to \mathbb{R} dada por xx2x \mapsto x^2 manda 22 em \mathbb{R} a 22=42^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 ff e gg (sobre quaisquer domínios e imagens) pode ser obtida outra por concatenação; a função composta ou a composição gfg \circ f, dado que a imagem de ff é contida no domínio de gg, isto é, Y(f)X(g)Y(f) \subseteq X(g). É definida por gf:xg(x)f(g(x)),g \circ f \colon x \mapsto g(x) \mapsto f(g(x)), simbolicamente, para obter gf(x)=g(f(x))g \circ f(x) = g(f(x)), substituímos xx em g(x)g(x) por f(x)f(x).

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

Inversão de funções

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

Matematicamente, a função ff tem o inverso g=f1g = f^{-1}, se g(f(x))=xg(f(x)) = x e f(g(x))=xf(g(x)) = x. Por exemplo, sobre 0\mathbb{R}_{\geq 0} vale (x2)=x=(x)2\sqrt (x^2) = x = (\sqrt{x})^2 para f(x)=x2,g(x)=xf(x) = x^2, g(x) = \sqrt x, e (2x+1)/21/2=x=2(x/21/2)+1(2x + 1)/2-1/2 = x=2(x/2-1/2) + 1 para f(x)=2x+1f(x) = 2x + 1 e g(x)=x/21/2g(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=f1g = f^{-1} é o espelhamento do gráfico da função invertida ff na diagonal dos pontos cuja coordenada xx é igual à coordenada yy.

A função inversa

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.

Resumimos:

Algarismos

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

Isto é,

Por exemplo, 1101=123+122+021+120 1101 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 e A02F=10163+0162+2161+15160. 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 texto inteligível \text{texto inteligível } \Downarrow texto ininteligível \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

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

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

dados = arquivo digital (de texto, imagem, som, vídeo, …)
= sequência de bites (= 0, 1)
= sequência de baites (= 00, 01, …, FE, FF)
= número (= 0, 1, 2, 3 …)

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

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 00, 11, 22, 33, …

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

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

Por exemplo, 048,...,957;A65,...,Z90;a97,...,z122. 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 01270 - 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,

Todas elas ocuparam o espaço dos números 128255128 - 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 11 nos primeiros 33 bites, acrescentado por 11, iguale o número de baites, de 11 a 44, do símbolo codificado. Isto é, ela envia um símbolo a 11, 22, 33 ou até 44 baites, onde #{baites}=#{dígitos binários consecutivos iniciais iguais a 1}+1 \# \{ \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 22 baites e ç1011001111000111. \text{ç} \mapsto 1011 0011 1100 0111. Vemos que, com efeito, o número dos primeiros coeficientes consecutivos iguais a 11 é 11 (como já o segundo coeficiente é igual a 00), o que, acrescentado por 11, resulta em 22, 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

Mapa de graus das cores primárias (RGB = Vermelho, Verde e Azul)

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

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

criptografia simétrica

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.

criptografia assimétrica

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

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

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

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

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

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

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

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

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 pp um texto claro e 𝒫(p)\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 pp e todo texto cifrado cc, temos 𝒫(p|c)=𝒫(p)\mathcal{P}(p | c) = \mathcal{P}(p).

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

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 𝒫(p)>0\mathcal{P}(p)> 0 para todo texto claro pp. O método de criptografia é perfeitamente seguro, se

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

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

O criptossistema de Goldwasser-Micali consiste em:

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

Por exemplo,

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

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 kk) 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 kk bites. O atacante recebe a chave pública.

  2. O atacante cria dois textos claros de tamanho igual M0M_0 e M1M_1.

  3. A máquina criptográfica

    1. escolhe aleatoriamente um bit bb em {0,1}\{ 0, 1 \}
    2. cifra MbM_b, e
    3. passa o texto cifrado ao atacante.
  4. O atacante escolhe um bite bb' em {0,1}\{ 0, 1 \}.

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

Uma diferença insignificante deve ser permitida porque é o atacante facilmente aumenta a sua probabilidade de sucesso acima de 1/21/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

como se segue:

  1. SS simula a geração das chaves e dá gxg^x como chave pública a AA. Porém, SS não sabe a chave secreta correspondente, sem AA o saber.
  2. AA produz duas mensagens m0m_0 e m1m_1.
  3. SS simula a cifração: Ele escolhe aleatoriamente um bite bb e define a cifração por gy,gzmbg^y, g^z m_b.
  4. AA decide se esta cifração corresponde a m0m_0 ou a m1m_1.

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

Segurança Semântica IND-CCA

Recordemo-nos de

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 M0M_0 e M1M_1.
  3. O oráculo
  4. O atacante manda decifrar quaisquer textos cifrados, calcula e escolhe um bite bb' em {0,1}\{ 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

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 MM de uma mensagem mm, sem nenhum conhecimento sobre mm, em uma mensagem cifrada N=f(M)N = f(M) de alguma mensagem nn por uma função conhecida ff tal que a relação entre mm e nn 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 MM, 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

CrypTool

É recomendado experimentar com o aplicativo CrypTool que

e

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.

Cifrar com a Enigma no CrypTool 2

2 Criptografia Simétrica Antiga

Apresentamos uns exemplos antigos de algoritmos criptográficos sobre textos: Historicamente, a criptografia estuda a transformação de um texto inteligível \text{texto inteligível } \Downarrow texto ininteligível \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

Veremos que mesmo com a presença de muitas chaves um algoritmo, como o dado pela permutação arbitraria do alfabeto que tem quase 2802^{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 dd 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 dd. 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.

Imaginemos que as letras do alfabeto formem uma roda

Por exemplo, se d=3d = 3, então AD,BE,...,WZ,XA,...,ZC. A \mapsto D, B \mapsto E, ..., W \mapsto Z, X \mapsto A, ..., Z \mapsto C.

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

O César desloca cada letra do alfabeto pela a mesma distância

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

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

Questão: Para qual dd 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 dd, substituamos cada letra por outra letra arbitrária, por exemplo:

A B Y Z
\downarrow \downarrow \downarrow \downarrow
E Z G A

Para podermos desfazer a cifração, é necessária que nunca duas letras sejam enviada a mesma letra! Isto é, permutamos as letras. Assim obtemos 26251=26!>102626 \cdot 25 \cdots 1 = 26! > 10^{26} chaves (\approx o número de senhas que podem ser formados com 8080 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.
A cítala enrolada com um cinto de couro

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 22 letras (e um comprimento de 33 letras), as duas linhas

l u a
m e l

tornam-se as três linhas

l m
u e
a l

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

L M U E A L
A cítala cifrando uma ordem militar em inglês.

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 AD,BE,CF,...,WZ,XA,...,ZC. 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)

A B Y Z
\downarrow \downarrow \downarrow \downarrow
E Z G A

tem 26251=26!>102626 \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á

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

em português. Por exemplo,

\implies Substituindo

é 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 GWQP VQX Q CQPQ XU GWQP G NQX VQX \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 QQ, GG e XX aparecem respectivamente 66, 44 e 44 vezes, obtemos E*E* *AO A *A*A OU E*E* *AO *AO. \text{E*E* *AO A *A*A OU E*E* *AO *AO}. Suponhamos que *AO*AO = VAOVAO e que E*E*E*E* = ELESELES. Em particular, VV corresponde a VV e PP a SS. Logo ELES VAO A *ASA O* ELES *AO VAO \text{ELES VAO A *ASA O* ELES *AO VAO} para estarmos levados ao chute ELES VAO A CASA OU ELES NAO VAO. \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

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

Ela tem

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

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

Por exemplo, se olhamos ADABESACA. \text{ADABESACA}. observamos que dd e ee são distanciados por três letras, o que nos leva ao chute que circunferência =3 letras, \text{ circunferência } = 3 \text{ letras}, e à decifração ABA DE CASA. \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.

O esquema elétrico

Construção

O esquema elétrico, constituído por:

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.
O percurso da corrente nos cabos da Enigma ao teclar uma letra

Cada cilindro consiste em

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

Figura 2.1: A Enigma em ação

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,

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

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

(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:

Os cilindros

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.

Marian Rejweski

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.

O painel de ligações

Expresso por uma fórmula, a substituição MM (= Maquina) da Enigma descreve-se pela concatenação das substituições M=PECR(cR)CM(cM)CL(cL)RCL(cL)1CM(cM)1CR(cR)1E1P1 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

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

Cifrar com a Enigma no CrypTool 2

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 é rRr_R é aumentado por 11, toda a substituição MM 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,

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.00017.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,

Chaves

Para a Engima I, há quatro fatores:

Resumimos que há

o que dá ao total 6067616.900150.738.274.937.250=103.325.660.891.587.134.000.0001023 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 8080 bites. (Por exemplo, o DES (= Data Encryption Standard) utiliza uma chave de 5656 bites.)

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

Logo, importam criptograficamente

A bomba de Turing ajudou a reduzir estas possibilidades, sobretudo as do maior fator, as ligações do painel. Sobraram ainda 6016.900=1.014.000 60 \cdot 16.900 = 1.014.000 possibilidades. Considerando a força de trabalho de 42004200 pessoas (entre elas 80%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.

O interior da bomba de Turing

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,

    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

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

Então, a Bomba de Turing, fixados

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 MM das substituições seguintes M=PECRCMCLRCL1CM1CR1E1P 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

Para facilitar,

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

Para destacar a dependência da substituição CC da posição pp da letra no texto a ser cifrado (pelo avanço do cilindro rápido a cada letra teclada), denote C(p)= a substituição pelos cilindros na posição p do texto. 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(𝐜+(0,0,p))C(\mathbf{c} + (0, 0, p)) onde 𝐜=(cL,cM,cR)\mathbf{c} = (c_L, c_M, c_R) é a configuração inicial do cilindro lento, médio e rápido.) Aqui para p=2p = 2, obtemos 𝐄=P(C(2)(P(𝐑))). \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 é, PP=identidadeP \circ P = \mathrm{identidade}. Por isso, ao aplicarmos PP a ambos lados desta equação, P(𝐄)=C(2)(P(𝐑)); P(\mathbf{E}) = C(2) (P(\mathbf{R})); Em seguida, da mesma maneira, P(𝐓)=C(3)(P(𝐄))=C(3)C(2)(P(𝐑)); 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(𝐑)=C(9)C(4)C(3)C(2)(P(𝐑)), 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)C = C(9) C(4) C(3) C(2) deixa a letra P(𝐑)P(\mathbf{R}) invariante, C(P(𝐑))=P(𝐑). 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 :

# circuitos \ # letras 8 9 10 11 12 13 14 15
3 2.2 1.1 0.42 0.14 0.04 <0.01 <0.01 < 0.01
2 58 28 11 3.8 1.2 0.30 0.06 < 0.01
1 1500 720 280 100 31 7.7 1.6 0.28

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

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

Por exemplo, dado P(𝐑)P(\mathbf{R}), o valor P(𝐄)P(\mathbf{E}) define-se por P(𝐄)=C(2)(P(𝐑)); P(\mathbf{E}) = C(2) (P(\mathbf{R})); em seguida, P(𝐓)=C(9)(P(𝐄))=C(9)C(2)(P(𝐑)); 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

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

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

dados = arquivo digital (de texto, imagem, som, vídeo, …)
= sequência de bites (= 0, 1)
= sequência de baites (= 00, 01, …, FE, FF)
= número (= 0, 1, 2, 3 …)

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 tt com o baite (na posição) correspondente de uma chave cc que

Isto é, o texto cifrado T=(T1,T2,...)T = (T_1, T_2, ...) é T=tc=(t1c1,t2c2,...). 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 tt, 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,

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 bb' e bb'', então, com este algoritmo, a soma (XOR) (bc)(bc)=bb (b' \oplus c) \oplus (b' \oplus c) = b' \oplus b'' dos dois blocos cifrados bcb' \oplus c e bcb'' \oplus c iguala a soma bbb' \oplus b'' dos dois blocos claros (porque a adição XOR é por definição auto-inversa, isto é xx=0x \oplus x = 0 independente do dígito binário ser x=0x = 0 ou x=1x = 1)!

A soma de dois textos claros revela regularidades!

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 88 bites.

Para um bloco de por exemplo, 1616 baites, esta tabela de substituição teria horrendos 2256162^{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 28=2562^8 = 256 entradas de 11 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 nn baites (por exemplo, n=16n = 16 para AES e n=2n = 2 no nosso modelo prototípico) e cifra cada bloco pela iteração (por exemplo, 1010 vezes no AES, e 55 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

  1. a substituição do alfabeto (por exemplo,
  2. 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,

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

e em cada uma das primeiras rodadas 11, 22 e 33,

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

  2. Substitui cada um dos 44 sub-blocos de 44 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 ii do sub-bloco jj com o bite jj do sub-bloco ii;

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

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

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

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

Isto é:

Diagrama das rodadas da cifra de Feistel dada em Heys (2002)

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 1616 bites: Se for possível saber, para 88 bites da chave provada, se eles coincidem com os bites correspondentes da chave correta, então o decifrador

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

Mais exatamente, a chave consiste de 44 blocos de 44 bites. Daremos um exemplo da criptoanálise abaixo em que o decifrador terá um critério probabilista para decidir se 22 dos blocos, isto é, 88 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” ΔX\Delta X e uma determinada diferença “sainte” ΔY\Delta Y, pares de textos claros com diferença ΔX\Delta X resultam na penúltima rodada com determinada probabilidade em pares de textos cifrados com diferença ΔY\Delta Y.

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

em seguida,

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

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

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

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

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

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

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

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

Esta tabela alista, para umas diferenças entrantes e todos os pares entrantes com estas diferenças, as suas diferenças saintes.

as diferenças saintes ΔY\Delta Y para três diferenças entrantes ΔX\Delta X (alistadas horizontalmente) e todas as entradas XX (alistadas verticalmente).
XX \backslash ΔX\Delta X 10111011 10001000 01000100
00000000 00100010 11011101 11001100
00010001 00100010 11101110 10111011
00100010 01110111 01010101 01100110
00110011 00100010 10111011 10011001
01000100 01010101 01110111 11001100
01010101 11111111 01100110 10111011
01100110 00100010 10111011 01100110
01110111 11011101 11111111 10011001
10001000 00100010 11011101 01100110
10011001 01110111 11101110 00110011
10101010 00100010 01010101 01100110
10111011 00100010 10111011 10111011
11001100 11011101 01110111 01100110
11011101 00100010 01100110 00110011
11101110 11111111 10111011 01100110
11111111 01010101 11111111 10111011

Contemos, para toda diferença entrante ΔX\Delta X, quantas vezes cada diferença sainte ΔY\Delta Y resulta entre todos os possíveis pares entrantes XX' e XX'' com XX=ΔXX' \oplus X'' = \Delta X.

A frequência das diferenças saintes ΔY\Delta Y (alistadas horizontalmente) para toda as diferenças entrantes ΔX\Delta X (alistadas verticalmente).
ΔX\Delta X $backslash ΔY\Delta Y 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 0 0 0 2 0 2 4 0 4 2 0 0
2 0 0 0 2 0 6 2 2 0 2 0 0 0 0 2 0
3 0 0 2 0 2 0 0 0 0 4 2 0 2 0 0 4
4 0 0 0 2 0 0 6 0 0 2 0 4 2 0 0 0
5 0 4 0 0 0 2 2 0 0 0 4 0 2 0 0 2
6 0 0 0 4 0 4 0 0 0 0 0 0 2 2 2 2
7 0 0 2 2 2 0 2 0 0 2 2 0 0 0 0 4
8 0 0 0 0 0 0 2 2 0 0 0 4 0 4 2 2
9 0 2 0 0 2 0 0 4 2 0 2 2 2 0 0 0
A 0 2 2 0 0 0 0 0 6 0 0 2 0 0 4 0
B 0 0 8 0 0 2 0 2 0 0 0 0 0 2 0 2
C 0 2 0 0 2 2 2 0 0 0 0 2 0 6 0 0
D 0 4 0 0 0 0 0 4 2 0 2 0 2 0 2 0
E 0 0 2 4 2 0 0 0 6 0 0 0 0 0 2 0
F 0 2 0 0 6 0 0 0 0 4 0 2 0 0 2 0

As entradas de cada linha somam-se a 1616, o número dos possíveis pares para uma dada diferença entre eles. A primeira linha constata que duas entradas iguais resultam em duas saídas iguais. O número maior é 88 e atingido para ΔX=B\Delta X = B e ΔY=2\Delta Y = 2. Além dele, surge cinco vezes o número 66.

Exemplo. A tabela de frequência

Escolheremos os nossos diferenciais entre os com estas altas frequências:

Trilhas Diferenciais

Para uma cifra de Feistel, uma trilha diferencial é uma sequência finita de diferenças (ΔU1,ΔU2,...) (\Delta U_1, \Delta U_2, ...) tal que toda diferença ΔUi\Delta U_i é a entrada da S-box da rodada ii da cifra. Dada a saída ΔVi\Delta V_i da S-box da rodada ii, a entrada ΔUi+1\Delta U_{i + 1} da rodada seguinte é o resultado da aplicação da permutação a ΔVi\Delta V_i.

Queremos encontrar o mais provável trilha diferencial D=(ΔU1,ΔU2,ΔU3,ΔU4)D = (\Delta U_1, \Delta U_2, \Delta U_3, \Delta U_4) da cifra de Heys, ou, pelo menos, tal que cada diferencial (ΔUi,ΔVi)(\Delta U_i, \Delta V_i) seja entre os mais prováveis.

Todo diferencial consiste de 44 sub-diferenciais, correspondente aos 44 sub-blocos de 44 bites que constituem o bloco de 1616 bites. Para encontrar uma tal trilha diferencial provável, queremos, em cada rodada,

Um exemplo de uma tal trilha DD é a seguinte: Seja a diferença entrante na primeira rodada ΔU1=[0000101100000000], \Delta U_1 = [ 0000 \; 1011 \; 0000 \; 0000 ], que é pela S-box 22 substituída por ΔV1=[0000001000000000]. \Delta V_1 = [ 0000 \; 0010 \; 0000 \; 0000 ]. Pela permutação subsequente, obtemos a diferença entrante na segunda rodada ΔU2=[0000000001000000] \Delta U_2 = [ 0000 \; 0000 \; 0100 \; 0000 ] que é pela S-box 33 substituída por ΔV2=[0000000001100000]. \Delta V_2 = [ 0000 \; 0000 \; 0110 \; 0000 ]. Pelos bites número 22 e 33 diferentes de zero, obtemos na terceira rodada pela permutação a diferença entrante com dois sub-diferenciais ativos ΔU3=[0000001000100000] \Delta U_3 = [ 0000 \; 0010 \; 0010 \; 0000 ] que é pelas S-boxes 22 e 33 substituída por ΔV3=[0000010101010000]. \Delta V_3 = [ 0000 \; 0101 \; 0101 \; 0000 ]. Finalmente, obtemos pela permutação como entrada da quarta rodada ΔU4=[0000011000000110]. \Delta U_4 = [ 0000 \; 0110 \; 0000 \; 0110 ].

Trilha Diferencial

Denote Si,jS_{i,j} a substituição do sub-bloco jj pela S-box na rodada ii. Na nossa trilha diferencial, alistamos

a probabilidade que, se a diferença ΔX\Delta X entre na substituição Si,jS_{i,j}, então a diferença ΔY\Delta Y saia:

Substituição Entrada Saída Probabilidade
S12S_{12} BB 22 8/168/16
S23S_{23} 44 66 6/166/16
S32S_{32} 22 55 6/166/16
S33S_{33} 22 55 6/166/16

Se suponhamos que os diferenciais de uma rodada sejam independentes dos diferenciais da rodada anterior, então a probabilidade pDp_D da substituição ΔU1=[0000101100000000] \Delta U_1 = [ 0000 \; 1011 \; 0000 \; 0000 ] por ΔU4=[0000011000000110]. \Delta U_4 = [ 0000 \; 0110 \; 0000 \; 0110 ]. é o produto das probabilidades de cada substituição, pD=8/166/16(6/166/16)=27/1024. p_D = 8/16 \cdot 6/16 \cdot (6/16 \cdot 6/16) = 27/1024.

A fim de encontrar a chave, para

o decifrador

  1. cifra o par U1U'_1 e U1U''_1,
  2. inverte a cifração até a entrada da S-box na quarta rodada pela chave K5=[0000K5,5,...,K5,80000K5,13,...,K5,16] K_5 = [ 0000 \; K_{5,5}, ..., K_{5,8} \; 0000 \; K_{5,13}, ..., K_{5,16} ] para obter o par Υ4\Upsilon'_4 e Υ4\Upsilon''_4 e assim a diferença ΔΥ4\Delta \Upsilon_4, e
  3. compara a diferença ΔΥ4\Delta \Upsilon_4 com ΔU4\Delta U_4 e, se coincidem, então aumenta a contagem nn por 11.

Se para uma combinação de sub-blocos K5,5,...,K5,8K_{5,5}, ..., K_{5,8} e K5,13,...,K5,16K_{5,13}, ..., K_{5,16} vale n/mpDn/m \approx p_D, isto é, a proporção entre

é próxima da probabilidade pDp_D, então estes sub-blocos são provavelmente os sub-blocos 22 e 44 da chave 55 usada pelo cifrador.

Observação. Para concluir ter encontrado os sub-blocos corretos, usamos as hipóteses

  1. que os diferenciais de uma rodada sejam independentes dos diferenciais da rodada anterior, e
  2. que uma probabilidade de pares coincidentes próxima da calculada indica a chave correta.

Os dois não tem fundamento matemático rígido, mas são apenas plausíveis, porque, respetivamente:

  1. Cada rodada visa difundir o máximo, isto é, tornar o valor de cada bite da saída praticamente independente de todos os bites da entrada.
  2. É improvável existir uma chave que seja diferente mas reproduza a mesma probabilidade.

Notemos que para este ataque ser mais rápido, isto é, ser mais eficaz do que o ataque de força bruta (que simplesmente prova todas as chaves possíveis), é preciso #{ bites ativos }log2pD<#{ bites da chave }(3.1) \# \{ \text{ bites ativos } \} - \log_2 p_D < \# \{ \text{ bites da chave } \} \qquad(3.1) onde

Logo, é necessário que a trilha seja estreita, isto é, tenha poucos blocos ativos, para poder aprender se a chave provada é correta, isto é, coincide com a chave usada, apenas nestes blocos ativos (o que reduz o número de combinações logaritmicamente). No exemplo dado, apenas 22 dos 44 sub-diferenciais são ativos, o que permitiu ao decifrador aprender nestes 22 blocos se a chave é correta: o número de combinações que precisam ser provadas foi reduzido de 216=655362^{16} = 65536 a 2256=5122 \cdot 256 = 512.

3.5 AES

Os algoritmos criptográficos simétricos modernos, tais como DES e AES, cifram dados em vez de textos, isto é, sequências de baites ou bites. Ambos, o DES e o AES, são cifras de bloco, isto é, agrupam o texto claro em blocos de um tamanho de baites determinado (no caso do AES, de 1616, 2424 ou 3232 baites).

Lembremo-nos de que, idealmente, a rodada consistiria só

Porém, o alfabeto desta substituição seria tão gigantesco que este ideal é praticamente inatingível; sobretudo sobre um hardware tão limitado quanto o de um cartão inteligente.

Para um bloco de por exemplo, 1616 baites, esta tabela de substituição teria horrendos 2256162^256 \cdot 16 baites. Por isso o AES substitui só cada baite, cada casa do bloco, uma tabela de substituição de 28=2562^8 = 256 entradas de 11 baite; em seguida, considera o bloco como quadrado de 4×44 \times 4 casas, e

  1. permuta as casas de cada linha, e
  2. adiciona as colunas entre elas.

Os criadores do AES conseguiram demonstrar em Daemen e Rijmen (1999) que estas duas operações se complementam tão bem que, após várias iterações, quase compensam da ausência de uma substituição do bloco inteiro por outro. Isto é, conseguiram demonstrar que é imune contra um ataque de criptoanálise diferencial em Seção 3.4 pela sua ótima difusão. Para uma fonte mais detalhada, vide Daemen e Rijmen (2002).

Em vez disto, para conseguirem uma boa confusão e difusão (como definidas por Shannon), iteram ambas as operações (conhecidas pelos algoritmos antigos que operam sobre textos),

além da operação (nova sobre dados = sequências de bites),

O algoritmo AES é o vencedor de uma competição anunciada pelo National Institute of Standards and Technology of the United States (NIST) de 1997 a 2000 para substituir o então padrão de criptografia simétrico, o Data Encryption Standard (DES).

Antes de tornar-se o AES, este algoritmo foi denominado pelos seus criadores Vincent Rijmen e Joan Daemen Rijndael, pelas letras iniciais dos seus sobrenomes.

No final da competição, restaram estes cinco algoritmos com as seguintes votações:

Entre eles, nenhum deles se destacou pela sua maior segurança, mas o Rijndael, sim, pela sua simplicidade, ou clareza, e em particular economia computacional, na implementação. Como este algoritmo será a rodar por toda parte, por exemplo, nos processadores minúsculos de 8 bites nos cartões inteligentes (smartcards), a decisão foi tomada em favor do Rijndael.

Até hoje, este algoritmo continua firme e forte e é considerado o mais seguro; não há necessidade para outro padrão de algoritmo criptográfico simétrico.

E com efeito roda em todo lugar. Por exemplo, para cifrar uma rede sem fio, usa-se uma chave só, então a criptografia é simétrica. A opção mais segura, e logo mais recomendada, é a cifração por AES.

Cifração de uma rede sem fio pelo AES

Vamos conhecer este algoritmo tão simples!

Cifração em Blocos

O algoritmo AES agrupa o texto claro (e as chaves) em retângulos de 4×B4 \times B baites onde B:= número das colunas do bloco =4,6 ou 8. B := \text{ número das colunas do bloco } = 4, 6 \text{ ou } 8. Comumente, e para nós de agora para diante, B=4B = 4, isto é, os retângulos são quadrados. Em base hexadecimal (= cujos algarismos são 0099, A=10A = 10, B=11B = 11, C=12C = 12, D=13D = 13, E=14E = 14 e F=15F = 15), um tal quadrado tem por exemplo a forma

A1 13 B1 4A
A3 AF 04 1E
3D 13 C1 55
B1 92 83 72

O corpo binário Rijndael

Não para implementá-lo, mas para entendermos as funções do AES, principalmente SubBytes e MixColumn, precisamos de uma digressão matemática: Um baite b7...b1b0b_7 ... b_1 b_0 em {0,1}××{0,1}\{ 0, 1 \} \times \cdots \times \{ 0, 1 \} é considerado como polinômio com coeficientes binários por b7...b1b0b7X7++b1X+b0 b_7 ... b_1 b_0 \mapsto b_7 X^7 + \cdots + b_1 X + b_0 Por exemplo, o número hexadecimal 0x570x57, ou baite 010101111010101111, corresponde a x6+x5+x2+x+1. x^6 + x^5 + x^2 + x + 1.

Todas as adições e multiplicações têm lugar no corpo binário 𝔽28\mathbb{F}_{2^8} com 28=2562^8 = 256 elementos, o qual é um conjunto de números com uma adição e multiplicação (que satisfaz a leis comutativa, associativa e distributiva; como, por exemplo, \mathbb{Q}) construído como segue: Seja 𝔽2={0,1} \mathbb{F}_2 = \{ 0, 1 \} o corpo de dois elementos com

Seja 𝔽2[X]=/2= os polinômios sobre 𝔽2 , \mathbb{F}_2[X] = \mathbb{Z} / 2 \mathbb{Z} = \text{ os polinômios sobre $\mathbb{F}_2$ }, isto é, as somas finitas a0+a1X+a2X2++anXna_0 + a_1 X + a_2 X^2 + \cdots + a_n X^n para a0a_0, a1a_1, …, ana_n em 𝔽2\mathbb{F}_2 e seja 𝔽28:=𝔽2[X]/(X8+X4+X3+X+1)𝐅2[X]. \mathbb{F}_{2^8} := \mathbb{F}_2[X] / (X^8 + X^4 + X^3 + X+1) \mathbf{F}_2[X]. Isto é, o resultado de ambas as operações ++ e \cdot em 𝔽2[X]\mathbb{F}_2[X] é o resto da divisão por X8+X4+X3+X+1X^8 + X^4 + X^3 + X+1.

Adição

A adição ++ de dois polinômios é a adição em 𝔽2\mathbb{F}_2 coeficiente a coeficiente. Isto é, como baites, a adição ++ é dada pela adição XOR.

Multiplicação

A multiplicação \cdot é dada pela multiplicação natural seguida pela divisão com resto pelo polinômio m(x)=x8+x4+x3+x+1. m(x) = x^8 + x^4 + x^3 + x + 1. Por exemplo, em notação hexadecimal, 5783=C157 \cdot 83 = C1, pois (x6+x4+x2+x+1)(x7+x+1)=x13+x11+x9+x8+x6+x5+x4+x3+1 (x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) = x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 e x13+x11+x9+x8+x6+x5+x4+x3+1=(x5+x3+1)(x8+x4+x3+x+1)+x7+x6+1 x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1 = (x^5 + x^3 + 1) (x^8 + x^4 + x^3 + x + 1) + x^7 + x^6 + 1

A multiplicação pelo polinômio 11 não muda nada, é o elemento neutro. Para qualquer polinômio b(x)b(x), o algoritmo estendido de Euclides, calcula polinômios a(x)a(x) e c(x)c(x) tais que b(x)a(x)+m(x)c(x)=1. b(x)a(x) + m(x)c(x) = 1. Isto é, na divisão com resto de a(x)b(x)a(x) \cdot b(x) por m(x)m(x) sobra o resto 11. Quer dizer, aa é o inverso multiplicativo em 𝔽28\mathbb{F}_{2^8}, b1(x)=a(x) em 𝔽28 b^{-1}(x) = a(x) \text{ em } \mathbb{F}_{2^8} Quando invertermos um baite bb em 𝔽28\mathbb{F}_{2^8}, referimo-nos ao baite a=b1a = b^{-1}.

Com efeito, a

é o análogo da

Rodadas

O AES cifra cada bloco iterativamente, em rodadas. Seja R:= o número de rodadas R := \text{ o número de rodadas } que depende de BB, há

Então, para nós, R=10R = 10. Nestas rodadas, são geradas chaves, o texto claro substituído e transposto pelas seguintes operações:

  1. Rodada r=0r = 0:

  2. Rodadas r=1,...,R1r = 1, ..., R-1 para cifrar, aplicando as seguintes funções:

    1. SubBytes para substituir cada casa do quadrado (isto é, byte, sequencia de oito bites) por uma sequência de bites melhor distribuída,
    2. ShiftRows para transpôr as casas das linhas do quadrado,
    3. MixColumn para adicionar as casas das colunas do quadrado entre elas,
    4. AddRoundKey para gerar uma chave a partir da chave da rodada anterior e adicioná-la (por XOR) ao quadrado.
  3. Rodada r=Rr = R para cifrar, aplicando as seguintes funções:

    1. SubBytes
    2. ShiftRows
    3. AddRoundKey

    Isto é, em comparação às rodadas anteriores, a função MixColumn é omitida: Revela-se que MixColumn e AddRoundKey, após uma leve modificação de AddRoundkey, podem trocar a ordem sem modificar o resultado final de ambas operações. Nesta equivalente ordem, a operação MixColumn não aumenta a segurança criptográfica, sendo a última operação invertível sem chave. Então, pode ser omitida.

O CrypTool 1 oferece no Menu Individual Procedures -> Visualization of Algorithms -> AES

Figura 3.1: As rodadas do AES no CrypTool 1

Vamos descrever estas funções em mais detalhes:

SubBytes

SubBytes substitui cada baite do bloco por outro baite pela tabela de substituição S-box dada abaixo.

substituição no algoritmo AES

Para calcular o valor da casa pelo qual o S-box substitui o dado baite:

  1. Calcula o seu inverso multiplicativo BB em 𝔽28\mathbb{F}_{2^8},

  2. Calcula ai=bi+bi+4+bi+5+bi+6+bi+7+ci a_i = b_i + b_{i + 4} + b_{i + 5} + b_{i + 6} + b_{i + 7} + c_i onde i=0i = 0, 11, …, 77 é o índice de cada bite de um baite, e

Em forma matricial, (a0a1a2a3a4a5a6a7)=(1000111111000111111000111111000111111000011111000011111000011111)(b0b1b2b3b4b5b6b7)+(11000110) \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{pmatrix} + \begin{pmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{pmatrix} e como tabela calculada de antemão em notação hexadecimal (onde o número da linha corresponde ao primeiro e o número da coluna ao segundo digito do baite a ser substituído):

63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

ShiftRows

ShiftRows traslada a linha ll do quadrado ll posições para a esquerda (onde as linhas são enumeradas a partir de zero, isto é, ll percorre 0,1,20, 1, 2 e 33 e a traslação é cíclica). (Em particular, primeira linha não é trasladada.) Visualmente, o quadrado com entradas

B00B_00 B01B_{01} B02B_{02} B03B_{03}
B10B_10 B11B_{11} B12B_{12} B13B_{13}
B20B_20 B21B_{21} B22B_{22} B23B_{23}
B30B_30 B31B_{31} B32B_{32} B33B_{33}

é transformada em um com entradas

B00B_00 B01B_{01} B02B_{02} B03B_{03}
B11B_11 B12B_{12} B13B_{13} B10B_{10}
B22B_22 B23B_{23} B20B_{20} B21B_{21}
B33B_33 B30B_{30} B31B_{31} B32B_{32}
transposição no algoritmo AES

MixColumn

MixColumn multiplica cada coluna do bloco por uma matriz fixa. Mais exatamente,

então (a0,ja1,ja2,ja3,j)=(02030101010203010101020303010102)(b0,jb1,jb2,jb3,j) \begin{pmatrix} a_{0,j} \\ a_{1,j} \\ a_{2,j} \\ a_{3,j} \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} b_{0,j} \\ b_{1,j} \\ b_{2,j} \\ b_{3,j} \end{pmatrix} Por exemplo, o baite a0,ja_{0,j} é calculado por a0,j=2b0,j+3b1,j+b2,j+b3,j a_{0,j} = 2 \cdot b_{0,j} + 3 \cdot b_{1,j} + b_{2,j} + b_{3,j}

AddRoundKey

AddRoundKey adiciona, pela operação XOR, a chave W(r)W(r) da rodada atual rr ao quadrado BB do texto cifrado, isto é, BW(r). B \oplus W(r). A chave é gerada coluna a coluna. Denotemo-las por W(r)0W(r)_0, W(r)1W(r)_1, W(r)2W(r)_2 e W(r)3W(r)_3; isto é, W(r)=W(r)0W(r)1W(r)2W(r)3. W(r) = W(r)_0 \mid W(r)_1 \mid W(r)_2 \mid W(r)_3. Como a chave tem 1616 baites, cada coluna tem 44.

  1. A primeira chave W(0)W(0), isto é, da primeira rodada, é dada pela chave inicial WW.

  2. Para r=1,...,Rr =1, ..., R (onde RR é o número total de rodadas, R=10R = 10 para nós), as quatro colunas W(r)0W(r)_0, W(r)1W(r)_1, W(r)2W(r)_2 e W(r)3W(r)_3 da nova chave são geradas a partir das colunas da antiga chave W(r1)W(r-1) como segue:

    1. A primeira coluna W(r)0W(r)_0 é dada por W(r)0=W(r1)0ScheduleCore(W(r1)3); W(r)_0 = W(r-1)_0 \oplus \mathrm{ScheduleCore}(W(r-1)_3); isto é, a última coluna da chave da rodada precedente mais o resultado de ScheduleCore aplicada à primeira coluna da chave da rodada precedente (que denotemos por TT); aqui ScheduleChore é a composição das transformações:
      1. SubWord: Substitui cada um dos 44 baites de TT segundo a S-box em SubBytes.
      2. RotWord: Traslada TT um baite à esquerda.
      3. Rcon(rr): Adiciona (por XOR) a TT o valor constante, em notação hexadecimal, [(02)r1000000(02)^{r-1} \; 00 \; 00 \; 00] onde a potencia (= produto iterado) é calculada no corpo de Rijndael 𝔽28\mathbb{F}_{2^8}. Isto é, o único baite que muda é o primeiro, pela adição, ou do o valor 2r12^{r-1} (para r8r \leq 8 ), ou do valor 2r12^{r-1} em 𝔽28\mathbb{F}_{2^8} para r=9,10r = 9, 10.
    2. As colunas seguintes W(r)1W(r)_1, W(r)2W(r)_2 e W(r)3W(r)_3 são dadas, para i=1,2i = 1, 2 e 33, por W(r)i=W(r)i1W(r1)i; W(r)_i = W(r)_{i-1} \oplus W(r-1)_i; isto é, a coluna precedente da chave da rodada atual mais a coluna atual da chave da rodada precedente.
Algoritmo Completo

Observamos que a única transformação que não é afim (isto é, dada por um polinômio de grau 11, ou, equivalentemente, a composição de uma aplicação linear e um traslação) é a inversão no corpo 𝔽28\mathbb{F}_{2^8} na operação SubBytes. Com efeito

  1. Na operação SubBytes são aplicadas, nesta ordem,
    1. a inversão em 𝔽28\mathbb{F}_{2^8},
    2. uma aplicação linear, e
    3. a traslação por um vetor constante.
  2. ShiftRows é uma permutação, em particular,linear.
  3. MixColumn é uma adição, em particular, linear.
  4. AddRoundKey é a traslação pela chave da rodada.

Quanto às metas da difusão e confusão, podemos ressaltar que a cada etapa são substituídos e transpostos cerca da metade dos bites (no SubBytes) ou baites (no MixColumn e ShiftRows). Para convencer-se da complementaridade das simples operações para segurança criptográfica, isto é, que geram em conjunção alta confusão e difusão após de poucas iterações,

vale a pena experimentar em Individual Procedures -> Visualization of Algorithms -> AES -> Inspector com uns valores patológicos, por exemplo:

Figura 3.2: Os valores dos bloques ao longo das rodadas no AES no CrypTool 1

Vemos como se espalha esta pequena diferença inicial, gerando já resultados totalmente diferente após, digamos, quatro rodadas! Isto torna plausível a imunidade do AES contra a criptoanálise diferencial como será mostrado em Seção 3.6.

No caso que todas as entradas da chave e do texto claro sejam iguais a 00, compreendemos também o impacto da adição da constante Rcon(r)(r) à chave em cada rodada: é dela que provém toda a confusão!

3.6 Imunidade do AES contra a Criptoanálise Diferencial

O principio principal é o de Shannon, da boa difusão e confusão. Idealmente, cada bite cifrado depende de cada bite da chave e do texto claro; se um bite da chave ou do texto claro muda, então todo bite do texto cifrado muda com uma probabilidade de 50%50 \%.

Contra a criptoanálise diferencial, isto é, para evitar trilhas diferenciais altamente prováveis, o AES usa

Trilhas e Pesos

O quociente de propagação p(ΔXΔY)p(\Delta X \to \Delta Y) para um diferencial DD , uma diferença entrante ΔX\Delta X e diferença sainte ΔY\Delta Y para uma aplicação hh é p(ΔXΔY)=2n#{X tal que a diferença das imagens de X e X=XΔ seja ΔY} p(\Delta X \to \Delta Y) = 2^{-n} \# \{ X' \text{ tal que a diferença das imagens de } X' \text{ e } X'' = X' \oplus \Delta \text{ seja } \Delta Y \}

O peso de restrição w(ΔXΔY)w(\Delta X \to \Delta Y) de um diferencial é w(ΔXΔY)=log2p(ΔXΔY) w(\Delta X \to \Delta Y) = - \log_2 p(\Delta X \to \Delta Y)

Se a aplicação h:ΔXΔYh \colon \Delta X \mapsto \Delta Y é afim (isto é, h=A+kh = A \cdot + k, um polinômio de grau 11, ou, equivalentemente, a composição de uma aplicação linear AA e um traslação +k\cdot + k), o quociente de propagação é 11 para ΔY=AΔX\Delta Y = A \Delta X e 00 senão.

Se h=h1hnh = h_1 \oplus \cdots \oplus h_n, então h:ΔXΔYh \colon \Delta X \mapsto \Delta Y para ΔX=ΔX1ΔXn\Delta X = \Delta X_1 \oplus \cdots \oplus \Delta X_n e ΔY=ΔY1ΔYn\Delta Y = \Delta Y_1 \oplus \cdots \oplus \Delta Y_n tem quociente de propagação p(h)=p(h1)p(hn) p(h) = p(h_1) \cdots p(h_n) e peso de restrição w(h)=w(h1)++w(hn). w(h) = w(h_1) + \cdots + w(h_n).

Uma trilha diferencial é uma sequência finita de diferenças ΔU1ΔU2...\Delta U_1 \to \Delta U_2 \to ... tal que o resultado do diferencial ΔUi1ΔUi\Delta U_{i-1} \to \Delta U_i seja a entrada do diferencial seguinte ΔUiΔUi+1\Delta U_i \to \Delta U_{i + 1}.

O peso de restrição w(D)w(D) de uma trilha diferencial é w(D)=w(ΔU1)+w(ΔU2)+ w(D) = w(\Delta U_1) + w(\Delta U_2) + \cdots

É inviável calcular o quociente de propagação de uma trilha diferencial, mas fácil calcular o seu peso de restrição. Se os diferenciais da trilha diferencial são pouco correlacionados, então p(D)2w(D)(*) p(D) \approxeq 2^{-w(D)} \qquad (*) Esta aproximação, por exemplo, para DES, é muito boa se w(D)<nw(D) < n. Se w(D)>nw(D) > n, então (*)(*) não pode valer mais. Neste caso, em média apenas uma fração 2nw(D)2^{n - w(D)} das trilhas diferenciais DD com peso w(D)w(D) com uma diferença inicial ΔU1\Delta U_1 ocorrem.

Observamos que o peso de restrição de uma trilha independe das chaves das rodadas, porque cada peso de restrição é. Contudo, o quociente de propagação da trilha depende das chaves. Porém, pela aproximação (*)(*), uma trilha diferencial com peso de restrição significantemente <n< n tem um quociente de propagação que pode ser considerado independente das chaves das rodadas.

Trilhas largas

O passo da permutação é subdividido em dois sub-passos

e os quais, em combinação, conseguem uma excelente confusão e difusão porque garantem trilhas largas, diferenciais com muitos baites ativos, após poucas rodadas. Mais exatamente, Teorema 2 mostrará que após quatro rodadas, qualquer trilha diferencial tem 2525 baites ativos, isto é, o dos baites diferentes de 00 em todos os diferenciais na trilha diferenciais é 25\geq 25.

Daqui por diante, um vetor é uma sequência finita. Um vetor de bites (por exemplo, um bite, um baite, um vetor de baites) é ativo se é diferente de 00. Para um vetor de baites aa, seja W(a):=#{ baites ativos }, W(a) := \# \{ \text{ baites ativos } \}, o peso de aa. Recordemo-nos de que uma aplicação FF entre vetores de baites é linear se F(x+y)=F(x)+F(y)F(x + y) = F(x) + F(y).

Definição. Para uma aplicação linear FF entre espaços de vetores de baites, seja W(F):=min{W(v)+W(F(v)) para todos os vetores de baites v} W(F) := \min \{ W(v) + W(F(v)) \text{ para todos os vetores de baites } v \} o seu número de ramificação.

Isto é, para W(F)W(F) ser grande, quanto menos baites diferentes de 00 em vv, tanto mais em F(v)F(v). Como F = MixColumn opera sobre vetores de 44 baites, W(F)5W(F) \leq 5. Com efeito, vale igualdade:

Lema 1. O número de ramificação da aplicação linear MixColumn é 55.

Em particular, para qualquer vetor vv que tem um único baite diferente de 00, a sua imagem F(v)F(v) tem quatro baites diferentes de 00.

Para i=1i = 1, 22, …,

Em particular, é aplicado MixColumn ai1a_{i-1} para obter bib_i.

Uma trilha (diferencial) é uma sequência finita de diferenciais (de pares de 1616 baites); em particular, é uma sequência finita, ou vetor, de baites e podemos contar o seu peso, isto é, contar ao início de cada rodada o número de baites diferentes de 00 e somá-los. Isto é, o peso W(D)W(D) de uma trilha DD é W(a0)+W(a1)+W(a_0) + W(a_1) + \cdots.

Como SubBytes opera baite a baite, e AddRoundKey não muda o diferencial, observamos que as únicas operações que mudam os baites ativos em uma trilha diferencial são ShiftRows e MixColumn. Além disso,

Em particular, W(ai)=W(bi)W(a_i) = W(b_i) e WC(bi)=WC(ai+1)W_C(b_i) = W_C(a_{i + 1}).

Teorema 1. Para uma trilha diferencial DD sobre duas rodadas, W(D)5WC(a1) W(D) \geq 5 W_C(a_1) onde W(D)W(D) é o número de baites ativos da trilha e WC(a1)W_C(a_1) é o número de colunas ativas na entrada da segunda rodada.

Demonstração: Como pelo Lema 1 o número de ramificação de MixColumn é 5\geq 5, em cada coluna, a soma do número de baites ativos em a0a_0 e a1a_1 é 5\geq 5. Logo, peso da trilha =#{ baites ativos em a0 e a1 }5WC(a1) \text{ peso da trilha } = \# \{ \text{ baites ativos em $a_0$ e $a_1$ } \} \geq 5 W_C(a_1)

Teorema 1 com WC(a1)=2W_C(a_1) = 2

Em particular, toda trilha sobre duas rodadas tem 5\geq 5 baites ativos.

Lema 2. Em uma trilha diferencial sobre duas rodadas, WC(a0)+WC(a2)5 W_C(a_0) + W_C(a_2) \geq 5 onde WC(a0)W_C(a_0) e WC(a2)W_C(a_2) são os números de colunas ativas na entrada e saída da trilha.

Demonstração: Como ShiftRows move cada baite diferente a uma coluna diferente, observamos #{ colunas ativas depois }max{#{ baites ativos } em cada coluna antes }, \# \{ \text{ colunas ativas depois } \} \geq \max \{ \# \{ \text{ baites ativos } \} \text{ em cada coluna antes } \}, e #{ colunas ativas antes }max{#{ baites ativos } em cada coluna depois }, \# \{ \text{ colunas ativas antes } \} \geq \max \{ \# \{ \text{ baites ativos } \} \text{ em cada coluna depois } \}, quer dizer, antes e depois de ShiftRows.

Seja gg uma coluna (isto é, os baites do bloco nas posições dadas por esta coluna, independente da rodada) que é ativa em a1a_1, na entrada da segunda rodada (ou, equivalentemente, em b0b_0, após ShiftRows na primeira rodada). Temos #{ colunas ativas em a0 }#{ baites ativos na coluna g em b0 }, \# \{ \text{ colunas ativas em $a_0$ } \} \geq \# \{ \text{ baites ativos na coluna $g$ em $b_0$ } \}, e, da mesma maneira, #{ colunas ativas em b1 }#{ baites ativos na coluna g em a1 }. \# \{ \text{ colunas ativas em $b_1$ } \} \geq \# \{ \text{ baites ativos na coluna $g$ em $a_1$ } \}. Como MixColumn tem número de ramificação 55, #{ baites ativos em g em b0}+#{ baites ativos em g em a1}5 \# \{ \text{ baites ativos em $g$ em $b_0$} \} + \# \{ \text{ baites ativos em $g$ em $a_1$} \} \geq 5 e pois #{ colunas ativas em b1 }=#{ colunas ativas em a2 }, \# \{ \text{ colunas ativas em $b_1$ } \} = \# \{ \text{ colunas ativas em $a_2$ } \}, segue #{ colunas ativas em a0 }+#{ colunas ativas em a2 }5. \# \{ \text{ colunas ativas em $a_0$ } \} + \# \{ \text{ colunas ativas em $a_2$ } \} \geq 5.

Lema 2 com uma coluna ativa em a1a_1

Teorema 2. Toda trilha diferencial sobre quatro rodadas tem 25\geq 25 baites ativos.

Demonstração: Tem-se #{ baites ativos }5[WC(a1)+WC(a3)]25, \# \{ \text{ baites ativos } \} \geq 5[W_C(a_1) + W_C(a_3)] \geq 25, onde

Teorema 2

Corolário: Não há trilhas com uma probabilidade maior que 21502^{-150} para 44 rodadas de AES.

Demonstração: Como a S-box tem um quociente de propagação de 262^{-6} e uma trilha com 44 rodadas pelo menos 2525 S-boxes ativas. Por Capítulo 5 em Daemen (1995), a probabilidade da trilha é aproximadamente o produto da probabilidade de cada S-box.

4 Criptografia Assimétrica

A criptografia assimétrica foi sugerida pela primeira vez, publicamente, em Diffie e Hellman (1976).

Diffie e Hellman, os inventores da ideia da criptografia assimétrica

Por trás dela figura uma função alçapão (mais especificamente, nesse artigo, a exponencial modular), uma função invertível que é facilmente computável, mas cujo inverso é dificilimamente computável em ausência de uma informação adicional, a chave secreta.

função alçapão

Para cifrar, aplica-se a função, para decifrar, seu inverso com a chave secreta. Por exemplo, na abordagem segundo Diffie e Hellman, esta função é a exponencial, porém, sobre outro domínio que os números reais a que estamos acostumados, explicado em Seção 5.1.

Com efeito, Diffie e Hellman (1976) introduziu apenas um esquema para trocar uma chave secreta através de um canal inseguro. Foi foi realizado pela primeira vez

Os inventores do algoritmo RSA, Rivest, Shamir e Adleman

4.1 Chave pública e privada

Recordemo-nos de que há duas chaves, uma chave pública e outra privada, Comumente:

Assim, um texto pode ser transferido do cifrador (Alice) a uma pessoa só, o decifrador (Bob).

Os papéis das chaves públicas e privada podem ser invertidos:

Assim, o cifrador pode provar a todos os decifradores (os que têm a chave pública) a sua posse da chave privada; a assinatura digital.

A teoria (quer dizer a matemática) por trás da cifração pela chave pública (mensagens digitais) ou privada (assinatura digital) é quase a mesma; unicamente os papéis dos argumentos da função alçapão são invertidos. (Por exemplo, no algoritmo RSA, esta troca de variáveis é verdadeiramente tudo o que acontece.) Porém, na prática, geralmente são cifrados:

assinatura digital

Isto é, enquanto

Subchaves Efêmeras

Uma subchave de uma chave principal é uma chave (cuja soma de verificação criptográfica é) assinada pela chave principal.

O dono frequentemente cria subchaves a fim de usar a chave (pública e privada) principal unicamente

e as subchaves para os outros fins quotidianos (assinar e decifrar) com um maior risco de comprometimento.

Desta maneira o eventual comprometimento de uma subchave (o que é mais provável pelo seu uso quotidiano!) não comprometerá a chave principal. Neste caso,

subchaves

Estudamos como as subchaves funcionam em prática no aplicativo criptográfico principal, o programa de linha-de-comando GPG discutido em Seção 4.6. Uma boa referência é https://wiki.debian.org/Subkeys.

Subchaves para o Dia-a-Dia

Para mais segurança, o usuário cria (por exemplo, em GPG)

Impressões digitais de subchaves no GPG para Subscrever e Encriptar

Quanto ao uso de chaves diferentes para assinar e cifrar,

Melhores Práticas para a Gerência das Chaves

Unicamente a chave principal é imutavelmente ligada a identidade do dono, e todas as outras substituíveis: Enquanto a

leitor de cartão inteligente

(Perfect) Forward Secrecy

Na (Perfect) Forward Secrecy (sigilo futuro perfeito), depois que os correspondentes trocaram as suas chaves públicas (permanentes) e estabeleceram confiança mútua,

Desta maneira, mesmo se a correspondência foi espreitada e gravada, não pode ser decifrada posteriormente; em particular, não pode ser decifrada pela obtenção da chave privada de um correspondente.

Por exemplo, o protocolo TLS que cifra a comunicação em grande parte da internet, tem em versão 1.2 suporte para Perfect Forward Secrecy:

Perfect Forward Secrecy

Assinatura

Deve ser pensado com solenidade antes de assinar qualquer documento. O mesmo vale para assinaturas digitais.

Vantagem

Uma assinatura tem como vantagem a garantia que o dono da chave privada escrevesse o conteúdo. Na comunicação por e-mails, evita o risco que um atacante

Inconveniência

Porém, como inconveniência, caro leitor, se a comunicação contém algo que não desejas ser visto por terceiros (por exemplo, ser lido em voz alta pelo promotor público no tribunal), melhor não comproves a tua origem pela tua assinatura! Como esta mensagem pode ser espreitada, o teu correspondente mudar de ideia sobre a tua privacidade ou a sua conta ser hackeada, …

Para dar uma analogia à realidade nossa, uma assinatura automática compara-se a gravação de toda conversa privada; esperemos que ninguém tenha acesso a ela!

Assinatura de Grupo

Observamos que Alice quer provar ao Bob que ela é a remetente, mas não a terceiros! Por isso surgiu a ideia da assinatura de grupo: uma chave efêmera para assinar é criada e compartilhada (isto é, a chave pública e privada) entre Alice e Bob. Desta maneira, Alice e Bob têm certeza sobre o originário, mas terceiros apenas que ele pertença ao grupo.

Assinatura de Grupo

4.2 O dono desconhecido da chave privada ou o Ataque MITM

A criptografia assimétrica permite a Alice, que conhece uma chave pública,

Com este conforte que a criptografia assimétrica (em contraste com a criptografia simétrica) permite à Alice, obter a chave pública impessoalmente sem encontrar o Bob, surge o problema da identidade do dono da chave pública: Considerando que a Alice

como garantir à Alice a identidade da chave privada, isto é, que o dono da chave privada seja verdadeiramente o Bob?

Quer dizer, como evitar um ataque “man-in-the middle” — MIM (talvez “Maria-Bonita-no-Meio” em português nordestino) ? No MIM, o atacante se interpõe entre os correspondentes, assumindo a identidade de cada um, assim observando e interceptando suas mensagens:

MITM

Suponhamos que Maria Bonita intercepte a correspondência entre Alice e Bob.

  1. Bob envia a sua chave pública à Alice. Maria Bonita intercepta-a, e envia à Alice a sua chave pública própria que alega Bob como o seu dono.
  2. Se Alice enviar uma mensagem ao Bob, ela usa, sem ter noção, a chave pública da Maria Bonita!
  3. Alice cifra então uma mensagem com a chave pública de Maria Bonita e envia-a ao Bob.
  4. Maria Bonita intercepta a mensagem, decifra-a com a sua chave privada; ela pode ler a mensagem e, se quiser, modificá-la.
  5. Cifra a mensagem com a chave pública do Bob.
  6. Bob decifra a sua mensagem com a sua chave privada e não suspeita de nada.

Assim, Alice como Bob são persuadidos que usem a chave pública do outro, mas, na verdade, é a da Maria Bonita!

Em termos práticos, este problema ocorre por exemplo no protocolo ARP, o Protocolo de Resolução de Endereços (do inglês Address Resolution Protocol) de 1982 (na RFC 826) que padroniza a resolução de endereços (conversão) da camada de internet em endereços da camada de enlace. Isto é, o ARP mapeia um endereço de rede (por exemplo, um endereço IPv4) em um endereço físico como um endereço Ethernet (ou endereço MAC). (Em redes Internet Protocol Version 6 (IPv6), o ARP foi substituído pelo NDP, o Protocolo de Descoberta de Vizinhos (do inglês Neighbor Discovery Protocol).)

O ataque de ARP poisoning (= poluição de cache ARP) procede como segue:

Maria Bonita quer interceptar as mensagens da Alice ao Bob, todos os três fazendo parte na mesma rede física.

  1. Maria Bonita envia um pacote arp who-has à Alice que contem como endereço de IP fonte o do Bob cuja identidade queremos usurpar (ARP spoofing) e o endereço físico MAC da placa de rede de Maria Bonita.
  2. A Alice criará uma entrada que associa o endereço MAC de Maria Bonita ao endereço IP do Bob.
  3. Assim quando Alice comunicar com o Bob no nível IP, será Maria Bonita que receberá os pacotes da Alice!

Filosofia das Soluções

Esta garantia da integridade da identidade é estabelecida por terceiros, isto é, identidades com chaves privadas que confirmam pelas suas assinaturas digitais que o Bob é o dono da chave privada.

O problema da identidade das chaves públicas surge outra vez: Como garantir que as identidades dos donos das chaves privadas sejam verdadeiras?

Há duas soluções:

autoridades hierárquicas
teia de confiança

Autoridades Hierárquicas

Nas autoridades hierárquicas, os donos de chaves privadas distinguem-se por níveis hierárquicos. No nível o mais alto jazem as autoridades radicais nas quais se confia incondicionalmente. Por exemplo,

Teia de Confiança

Na teia de confiança, os donos de chaves privadas não se distinguem de um ao outro.

A ausência de autoridades radicais, entidades incondicionalmente confiáveis, é compensada pela

Padronização das Filosofias na Internet

Na internet,

Comparamos as vantagens e inconveniências entre as duas abordagens:

4.3 X.509

Estrutura de um certificado X.509

A assinatura de um certificado X.509 é a cifração pela chave privada do hash da concatenação [V,SN,AI,CA,TA,A,KA] [ V, SN, AI, CA, TA , A, KA ] de

O sistema de autoridades hierárquicas foi criado para estabelecer a confiança através de máquinas e tem como grande vantagem

Porém, confiança é uma questão humana, e tem como calcanhar-de-aquiles a confiança (absoluta) na autoridade (radical):

4.4 O aperto de mão pelo X.509

Relatamos o maior uso do padrão X.509 na internet, o TLS Handshake:

Aperto de Mão no TLS

A referência definitiva é a especificação RFC 5246. Uma ótima visão global é dada pela Conexão Ilustrada de TLS 1.3 com cada baite explicado.

São os primeiros passos entre um cliente e o servidor, por exemplo, um site de comércio eletrônico, para estabelecer uma conexão cifrada (por exemplo, para receber os dados do cartão de crédito do cliente).

Opcionalmente,

  1. O “Alô” entre o cliente e o servidor, em que o cliente propõe, e o servidor escolhe, um pacote criptográfico; isto é, o conjunto dos algoritmos criptográficos,

    Por exemplo, o pacote criptográfico TLS_RSA_WITH_3DES_EDE_CBC_SHA (codificado 0x00 0x0a) usa

    Além disto, cada um,

    criam um nonce, isto é, um número de uso único, que contém

    que evita um ataque de repetição (replay attack); isto é, a reutilização das autentificações em outras sessões.

  2. O servidor identifica e autentifica-se pelo

    certificado X.509

    Este contém (principalmente):

    Na imagem, temos o servidor www.detran.al.gov

    O cliente procura a chave pública da autoridade (radical) indicada no certificado (que é usualmente inclusa no navegador), e usa-a para decifrar esta assinatura digital. Se o resultado é a soma de verificação esperada (isto é, do endereço do servidor e da sua chave pública), então

    Como o cliente (ou, mais exatamente, o seu navegador) confia incondicionalmente nas autoridades radicais, a este ponto ele tem certeza que a chave pública pertença verdadeiramente ao servidor visado.

    (Opcionalmente, neste ponto também o cliente se autentifica por um certificado.)

  3. O cliente

    O servidor

  4. O cliente e o servidor calculam o segredo (master secret), um número de 4848 baites, por uma função PRF, master_secret = PRF(pre_master_secret, ClientHello.random + ServerHello.random) que usa como variáveis

    O cliente e o servidor calculam quatro chaves simétricas (para o algoritmo combinado inicialmente, por exemplo, se é AES, cada uma de 1616 baites) a partir do segredo; nomeadamente:

    Entre elas,

    Que cada lado tem uma chave diferente se deve à melhor prática (best practice) de usar uma chave diferente para cada uso diferente.

4.5 OpenPGP

Vamos discutir:

  1. as vantagens e inconveniências da teia de confiança:
  2. as vantagens e inconveniências (das implementações) de OpenPGP:

Teia de Confiança

O sistema da teia de confiança modela o estabelecimento da confiança humana e tem como grande vantagem que

e como grande inconveniência que

Além disso,

Na prática, em vez da teia de confiança, é mais viável estabelecer a confiança por outro canal impessoal (pela troca das impressões digitais das chaves públicas), por exemplo,

OpenPGP

Apesar da absurdidade (visto que confiança é uma questão humana e pessoal) da confiança automática do usuário prestada às certificadoras radicais (sobretudo empresas),

Avaliam principalmente o esforço para a instalação do programa e a manutenção das chaves (a qual inerentemente necessita da estimativa do usuário para a confiança nas chaves usadas) desproporcionalmente grande para o benefício (da maior privacidade e segurança) obtido. Infelizmente, justamente porque tão poucas pessoas usam OpenPGP, a usabilidade dos programas dedicados melhorou pouco nos últimos anos.

Por isso:

Recentemente, surgiu o programa opmsg (como alternativa a GPG que será apresentado em Seção 4.6) que implementa (muitos métodos d’) o protocolo Off the RecordOTR (como alternativa a OpenPGP) que oferece:

Além disso

4.6 Exemplos de Programas OpenPGP

Apresentamos uns programas que usam a teia de confiança (o protocolo OpenPGP), como

GPG

O programa GnuPG é um programa de linha-de-comando e pouco acolhedor para principiantes. Serve para a funcionalidade criptográfica de muitos programas criptográficos com interface gráfica.

Objetivo do GPG

Oferecer ao grande público aberta e gratuitamente métodos criptográficos para cifrar dados eletrônicos confidenciais.

Funções Principais

Um programa de linha-de-comando para

Aceitação

História

  1. O desenvolvimento do programa Gnu Privacy Guard (= GPG) pelo alemão Werner Koch começou (e até hoje não cessou) para ter uma alternativa livre ao programa de criptografia de e-mail comercial Pretty Good Privacy (= PGP) por Phil Zimmermann. Até hoje, é o desenvolvedor principal e depende de doações como única fonte de renda. No ínico de 2015, os seus recuros estavam acabando e pediu ajuda financeira, a qual recebeu amplamente.
O criador e desenvolvedor principal Werner Koch
  1. A versão 1.0.0 foi anunciada.
  1. O Ministério Federal Alemão de Economia e Tecnologia patrocinou a portabilidade para o Microsoft Windows.
  1. A versão 2.0 foi anunciada e trouxe mudanças significativas na arquitetura do programa.

Funcionamento

Criação de um par de chaves no GPG na linha-de-comando

Cria um par de chaves, uma pública e a outra privada, escolhendo

A chave pública é destinada à divulgação. Ela serve

A chave privada é guardada e protegida por uma senha. Ela serve

Enigmail

Enigmail

Mailvelope

O Mailvelope é uma extensão para os navegadores Firefox e Chrome, desenvolvido por uma empresa alemã, que adiciona recursos de criptografia e descriptografia à interface de provedores comuns de webmail como:

Por exemplo, cifra e decifra mensagens (usando o padrão OpenPGP), arquivos em seu disco rígido e envie anexos de e-mail cifrados.

Mailvelope é de código aberto e com base em OpenPGP.js (https://openpgpjs.org), uma biblioteca OpenPGP para JavaScript.

Uma introdução é dada em https://casalribeiro.com/pt/email-encryption-mailvelope/ .

Criar uma chave pública pelo Mailvelope
Uma chave pública criada pelo Mailvelope

É muito confortável, porém, este conforto vem ao detrimento da segurança; consta-se que

Por isso, é mais seguro usar um cliente de e-mail, como Thunderbird com Enigmail. Em seguida, para proteger as chaves da melhor forma, um cartão inteligente, como sera apresentado no fim deste capítulo.

Automatizar a Troca de Chaves

Todo programa que será apresentado (Autocrypt ou prettyeasyprivacy ou Delta-Chat) não é uma solução perfeita, mas conforme a RFC 7435 (Request for Comments, padrão livremente criado pelos usuários na internet) oferece apenas “Opportunistic Security: Some Protecion Most of the Time”: Opportunistic Security significa uma proteção contra atacantes passivos, mas não contra atacantes ativos; isto é, a cifração da comunicação funciona só enquanto ninguém se interesse nela! Justamente pela falta da verificação do dono da chave privada que corresponde à chave pública, é vulnerável ao ataque “man-in-the middle” (MITM) em que o atacante se interpõe entre as duas partes que se comunicam; Por exemplo, é perfeitamente possível

A cifração da comunicação apenas impede que é lida por terceiros, mas não garante que a conta pertença à pessoa alegada. Para evitar este ataque, tem que verificar pessoalmente (ou por outro canal, por exemplo, por telefone) com o dono o “fingerprint” (= impressão digital = uma soma de verificação criptográfica) da sua chave pública.

Autocrypt

Na versão 2.0 a extensão Enigmail tem suporte para o programa Autocrypt que automatiza a troca de chaves públicas: Ele insere uma linha adicional no cabeçalho do e-mail (que é normalmente invisível para o usuário) que contém o certificado (nome, endereço de e-mail e referência à chave pública do usuário). Autocrypt foi iniciado por um projeto da União Europeia em resposta às revelações por Edward Snowden.

Funcionamente de Autocrypt

Em vez disto, o envio automático da chave pública de Alice, um melhor funcionamento seria:

  1. O cliente de e-mail de Alice pede ao receptor Bob a cifração.
  2. O cliente de e-mail de Bob põe-se automatizadamente com o cliente de Alice de acordo sobre as chaves públicas usadas.
  3. Se Alice e Bob quiserem, podem verificar a impressão digital das chaves públicas por outro canal (por exemplo, por telefone).

prettyeasyprivacy

Outro projeto para mandar e-mails cifrados automaticamente como Autocrypt, fundado por uma iniciativa privada, que dá suporte a programas comerciais como o cliente de e-mail (e agendador, entre outros) Microsoft Outlook é prettyeasyprivacy.

Instala e lança mão de GPG(4Win), isto é, é uma interface gráfica no cliente de e-mail para este programa.

Uma ideia interessante é usar Safewords (palavras seguras) em vez da codificação hexadecimal para verificar a impressão digital de uma chave pública, isto é,

Delta-Chat

Mais um projeto semelhante, para mandar mensagens instantâneas automaticamente cifradas para outros usuários, é o aplicativo Delta-Chat que usa a conta de e-mail do usuário.

Delta-Chat

Como usa o mesmo protocolo aberto como o e-mail, em comparação a muitos outros aplicativos para mandar mensagens instantâneas automaticamente cifradas (como WhatsApp), não depende dos servidores de uma empresa específica. (Dizem que tem suporte a federação, por exemplo, um usuário de hotmail.com pode comunicar com outro de gmail.com.) Esta dependência traz os seguintes problemas:

Além disso, é compatível a destinatários que não usam o Delta Chat porque podem ser contatados por e-mail.

Isto dito, os meta-dados entre os servidores de e-mail não são cifrados. (O protocolo de e-mail IMAP é antigo e tem muitas deficiências; porém, é o estabelecido padrão, testado pelo tempo, com um grande ecossistema de programas.)

O mensageiro Conversations propõe um protocolo moderno XMPP que usa menos meta-dados que o protocolo IMAP. (Aparenta que o mensageiro Signal use menos meta-dados que Conversations, mas infelizmente quase todos os servidores são mantidos pela própria fornecedora Open Whisper Systems, em contraste ao Conversations. No fim das contas, a única solução segura é rodar o seu próprio servidor!)

É uma solução bastante completa quanto à segurança; infelizmente pouco estabelecida; por exemplo, há muitos servidores de e-mail (isto é, que comunicam pelo protocolo IMAP); porém, pouquíssimos que comunicam por XMPP.

5 Teoria dos Números Elementar

Explicamos a utilidade da aritmética modular na criptografia: Lembremo-nos que a função alçapão é facilmente computável, porém o seu inverso (por exemplo, a radiciação no RSA) é quase incomputável!

É esta dificuldade de calcular o inverso que corresponde à dificuldade da decifração, de inverter a cifração.

Os algoritmos criptográficos assimétricos como o RSA usam

Os algoritmos criptográficos, como o RSA, usam a aritmética modular para dificultar a computação da função inversa da potenciação, a radiciação. Já conhecemos a aritmética modular ou circular! Pela aritmético do relógio, onde um número fixo mm, por exemplo m=12m = 12 no caso do relógio, é considerado igual a 00. Como o indicador recomeça a contar a partir de 00 após cada volta, por exemplo, 33 horas após 1111 horas são 22 horas: 11+3=14=12+2=2. 11 + 3 = 14 = 12 + 2 = 2. Sobre este domínios, chamados de anéis finitos, (os gráficos d’) estas funções tornam-se irregulares e praticamente incomputáveis, pelo menos sem conhecimento de um atalho, a chave.

A seguir,

  1. convencemo-nos da plausibilidade desta dificuldade (em comparação ao caso do domínio dos números reais),
  2. construimos este domínio, e
  3. explicamos como calcular o inverso sobre ele.

5.1 Aritmética Modular como Randomização

A dificuldade de calcular o inverso corresponde à dificuldade da decifração, de inverter a cifração. Na criptografia assimétrica,

baseiam-se em uma função invertível tal que

Por exemplo, os inversos das funções alçapão

são dados pela

Observação. Observamos que as funções usadas são ambas algébricas, isto é, exprimem-se por uma fórmula (de somas, produtos e potências) finita. Funções analíticas, isto é, somas infinitas convergentes, por exemplo, o seno, cosseno, …, parecem impraticáveis pelos erros que surgem do necessário arredondamento.

Eles são

Introduzamos estes domínios:

Funções sobre Conjuntos Discretos

O seu domínio não é o dos números inteiros \mathbb{Z} (ou o dos números reais \mathbb{R} que os contém), porque ambas as funções, exponenciação e potenciação, são contínuas sobre \mathbb{R}:

Exponencial xexx \mapsto e^x
A parábola da função cúbica xx3x \mapsto x^3

Se o domínio destas funções fosse \mathbb{R}, os seus inversos poderiam ser aproximados sobre \mathbb{R}, por exemplo, pelo Método da Bisseção: Dado y0y_0, encontrar um x0x_0 tal que f(x)=y0f(x) = y_0 equivalha encontrar um zero x0x_0 da função xf(x)y0. x \mapsto f(x) - y_0.

Bisseção de uma função contínua
  1. (Inicialização) Escolha um intervalo [a,b][a, b] tal que f(a)<0 e f(b)>0. f(a) < 0 \quad \text{ e } \quad f(b) > 0.
  2. (Recalibração) Calcule o seu meio m:=a+b2m := \frac{a + b}{2}. Temos e itere com o intervalo dado pelas novas bordas.

Pelo Teorema do Valor Intermediário, o zero é garantido de estar no intervalo, que a cada passo diminui e converge à interseção.

Teorema do Valor Intermédiario

Bisseção do polinômio F(x)=x3+3x2+12x+8F(x) = x^3 + 3x^2 + 12x + 8 com pontos iniciais x1=5x_1 = -5 e x2=0x_2 = 0

Step x F(x) x(i)x(i1)\|x(i) - x(i-1)\|
x2x_{2} 0 8 5
x3x_{3} 2.5-2.5 18.875-18.875 2.52.5
x4x_{4} 1.25-1.25 4.26563-4.26563 1.251.25
x5x_{5} 0.625-0.625 1.427731.42773 0.6250.625
x6x_{6} 0.9375-0.9375 1.43726-1.43726 0.31250.3125
x7x_{7} 0.7813-0.7813 0.02078-0.02078 0.156250.15625
x8x_{8} 0.7031-0.7031 0.698040.69804 0.078130.07813
x9x_{9} 0.7422-0.7422 0.337450.33745 0.039060.03906
x10x_{10} 0.7617-0.7617 0.158060.15806 0.019530.01953
x11x_{11} 0.7715-0.7715 0.068570.06857 0.009770.00977
x12x_{12} 0.7764-0.7764 0.023880.02388 0.004880.00488
x13x_{13} 0.7783-0.7783 0.001540.00154 0.002440.00244
x14x_{14} 0.7800-0.7800 0.00962-0.00962 0.001220.00122

Anéis Finitos

Para evitar a iterada aproximação ao zero e assim dificultar a computação da função inversa (além de facilitar a computação da função mesma), o domínio de uma função alçapão é um anel finito (= principalmente um conjunto finito que contém 00 e 11 e sobre que uma soma ++ é definida) /m={0,1,...,m1} \mathbb{Z} / m \mathbb{Z} = \{ 0, 1, ..., m-1 \} para um número natural mm. Neles, vale m=1++1=0m = 1 + \cdots + 1 = 0 e toda adição (e logo toda multiplicação e toda potenciação) tem resultado <m< m. Assim /m\mathbb{Z} / m \mathbb{Z} é como anel não incluso em \mathbb{R}. Por exemplo, para m=7m = 7, 22=22=4 e 32=33=7+2=0+2=2. 2^2 = 2 \cdot 2 = 4 \quad \text{ e } \quad 3^2 = 3 \cdot 3 = 7 + 2 = 0 + 2 = 2. Introduziremos estes anéis finitos primeiro pelos exemplos /12\mathbb{Z} / 12 \mathbb{Z} e /7\mathbb{Z} / 7 \mathbb{Z} (= os anéis dos números das horas do relógio e dos dias da semana), depois para mm qualquer.

Quando olhamos as funções, cujos gráficos são tão regulares em \mathbb{R}, no anel finito /101\mathbb{Z} /101 \mathbb{Z},

Figura 5.1: A exponencial com base 22 em /101\mathbb{Z} / 101 \mathbb{Z}
Figura 5.2: Os pontos da função cúbica Y=X3Y = X^3 em /101\mathbb{Z} / 101 \mathbb{Z}

observamos que

é inicialmente tão regular sobre /101\mathbb{Z} / 101 \mathbb{Z} quanto sobre \mathbb{Z}, mas

começa a comportar-se erraticamente (exceto a formosa simetria da parábola no eixo central x=50,5x = 50,5 pela igualdade (x)2=x2(-x)^2 = x^2).

Invitamos o caro leitor a experimentar com este plotter em linha de gráficos de funções discretos (de que origina a imagem acima), uma cortesia de Sascha Grau.

Observação: Observamos que dependente da base gg da exponenciação xgxx \mapsto g^x e do expoente EE da potência xEx^E, a função pode só ser invertível sobre subconjuntos do seu domínio e contra-domínio, isto é, dos seus argumentos e valores.

Para invertê-la, na sua imagem (= o conjunto dado por todos os seus valores), ela precisa de ser injetora (isto é, manda argumentos diferentes a valores diferentes).

A imagem da exponenciação nunca contém 00 e é possivelmente menor ainda do que /101*:=/101{0}\mathbb{Z} / 101 \mathbb{Z}^* := \mathbb{Z} / 101 \mathbb{Z} - \{ 0 \}. Para g=2g = 2 sobre /101\mathbb{Z} / 101 \mathbb{Z}, a sua imagem é máximo, quer dizer, é /101*\mathbb{Z} / 101 \mathbb{Z}^*; em outras palavras, todos os números (diferentes de zero) são potências de gg. (Diz-se que gg gera /101*\mathbb{Z} / 101 \mathbb{Z}^*.) Porém, por exemplo g=4=22g = 4 = 2^2 gera sobre o mesmo domínio só a metade de /101*\mathbb{Z} / 101 \mathbb{Z}^*, isto é, um conjunto de 5050 elementos. Seção 7.2 mostrará que existe um gerador de /m*\mathbb{Z} / m \mathbb{Z}^* se, e tão-somente se,

Se o expoente EE é par, E=2eE = 2 e para um inteiro ee, então a potenciação xxEx \mapsto x^E satisfaz (x)E=(x)2e=(x)2e=x2e=x2e=xE(-x)^E = (-x)^{2 e} = {(-x)^2}^e = {x^2}^e = x^{2e} = x^E, isto é, manda x-x e xx ao mesmo valor. Em particular, não é injetora. Observamos esta simetria para xx2x \mapsto x^2 sobre /101\mathbb{Z} / 101 \mathbb{Z} em Figura 5.3 ao longo do eixo central x=50,5x = 50, 5 (e também que a sua restrição a {0,...,50}\{0, ..., 50\} é injetora).

Figura 5.3: Os pontos da função quadrática Y=X2Y = X^2 em /101\mathbb{Z} / 101 \mathbb{Z}

Dado um módulo mm, Seção 7.2 mostrará para quais expoentes EE a potenciação xxEx \mapsto x^E é injetora sobre /m\mathbb{Z} / m \mathbb{Z}:

Vale a pena verificá-lo pelo plotter.

5.2 Aritmética Modular

Introduzamos esses domínios finitos /m\mathbb{Z} /m \mathbb{Z} (o anel dos inteiros módulo mm, para um número natural (comumente primo) mm) das funções alçapão na criptografia assimétrica; são eles que dificultam tanto a nossa vida quando tentamos invertê-la (em comparação a \mathbb{R} ou \mathbb{Z}).

Veremos que já os conhecemos e usamos no dia-a-dia para m=12m = 12, na aritmética do relógio, e para m=7m = 7, nos dias da semana.

Recordemo-nos breve da Divisão com Resto:

Definição. Sejam aa e bb números inteiros positivos. Que aa dividido por bb tem resto rr significa que existe um inteiro qq tal que a=bq+r com 0r<b. a = b \cdot q + r \quad \text{ com } 0 \leq r < b. Exemplo. Para a=230a = 230 e b=17b = 17, obtemos 230=1713+9230 = 17 \cdot 13 + 9. Isto é, o resto de 230230 dividido por 1717 é 99.

Para mm um número inteiro qualquer, definiremos o anel finito /m\mathbb{Z} /m \mathbb{Z} (= para nós sobretudo um conjunto finito em que podemos somar) como segue:

Aritmética Modular no dia-a-dia

Damos exemplos da aritmética modular do nosso dia-a-dia (como o relógio, os dias da semana, ou até o alfabeto). A propriedade comum entre estes exemplos é a sua circularidade (de onde a nomenclatura “anel”).

Relógio

O exemplo protótipo de aritmética modular é a aritmética do relógio em que o ponteiro volta após 1212 horas no início; isto é, vale a equação 12=0, 12 = 0, que implica, entre outros, as equações 9+4=1 e 12=11;(*) 9 + 4 = 1 \quad \text{ e } \quad 1-2 = 11; \quad (*) Quer dizer, 44 horas depois das 99 horas é 11 hora, e 22 horas antes da 11 hora são 1111 horas. Podemos ir mais longe: 9+24=9,(**) 9 + 24 = 9, \quad (**) quer dizer se agora são 99 horas, então 2424 horas (= um dia) mais tarde também.

Relógio como Anel dos números 1,2,...,11,12=01, 2, ..., 11, 12 = 0

Dias da Semana

Além das horas, outro exemplo do aritmética modular no dia-a-dia são os dias da semana: tendo passado 77 dias, os dias da semana recomeçam. Se numeramos sábado, domingo, segunda, terça, quarta, quinta e sexta-feira por 00, 11, 22, 33, 44, 55, 66 então vale a equação 7=0, 7 = 0, e que implica, entre outros, as equações 4+4=1 e 12=5; 4 + 4 = 1 \quad \text{ e } \quad 1-2 = 5; Quer dizer, 44 dias depois da quarta-feira é domingo, e 22 dias antes do domingo é sexta-feira. Podemos ir mais longe: 5+14=55 + 14 = 5, quer dizer se agora é quinta-feira, então daqui em 1414 dias (= duas semanas) também.

A circularidade semanal de tomar comprimidos

Meses

Além das semanas, outro exemplo do aritmética modular no dia-a-dia são os meses do ano: tendo passado 1212 meses, os meses do ano recomeçam. Se numeramos janeiro, fevereiro, … por 11, 22, … então vale, como no relógio, a equação 12=0, 12 = 0, e que implica, entre outros, as equações 10+4=1 e 12=11; 10 + 4 = 1 \quad \text{ e } \quad 1-2 = 11; Quer dizer, um trimestre depois outubro recomeça o ano, e 22 meses antes de janeiro é novembro. Podemos ir mais longe: 5+24=55 + 24 = 5, quer dizer se agora é maio, então daqui em 22 anos também.

O ciclo do ano

A cifração de César

Na cifração de César, trasladamos cada letra do alfabeto por uma distancia tt fixa; por exemplo, para t=3t = 3, obtemos AD,BE,...,WZ A \mapsto D, B \mapsto E, ..., W \mapsto Z Para trasladarmos as últimas t=3t = 3 letras XX, YY e ZZ do alfabeto, consideramos o alfabeto como anel, isto é:

Roda das Letras do Alfabeto Latino

Assim, XA,...,ZC. X \mapsto A, ..., Z \mapsto C. Se identificamos cada letra do alfabeto romano com a sua posição, A0,B1,...,X23,Y24,Z25. A \mapsto 0, B \mapsto 1, ..., X \mapsto 23, Y \mapsto 24, Z \mapsto 25. então vale 23+3023 + 3 \mapsto 0, 24+3=124 + 3 = 1 e 25+3=225 + 3 = 2; isto é, 26=026 = 0.

Formalização

Formalmente, derivamos as equações em (*)(*) e (**)(**) das igualdades 9+4=13=12+1=0+1=1 e 12=1=1+0=1+12=11. 9 + 4 = 13 = 12 + 1 = 0 + 1 = 1 \quad \text{ e } \quad 1-2 = -1 = -1 + 0 = -1 + 12 = 11. e 9+24=9+212=9+20=9. 9 + 24 = 9 + 2 \cdot 12 = 9 + 2 \cdot 0 = 9.

Em geral, para quaisquer aa e xx em \mathbb{Z}, a+12x=a a + 12 \cdot x = a ou, equivalentemente, para quaisquer aa e bb em \mathbb{Z}, a=b se 12ab. a = b \quad \text{ se } 12 \mid a - b. Em palavras, aa e bb deixam o mesmo resto divido por 1212.

As mesmas observações valem para os dias da semana.

Não há nada de especial sobre o número m=12m = 12 (horas até meio-dia), m=7m = 7 (dias da semana) ou m=26m = 26 (letras do alfabeto latino). Por exemplo, as mesmas observações valeriam se o relógio indicasse m=15m = 15 horas (como no planeta Netuno em que o dia, a rotação completa em torno do próprio eixo, dura 1616 horas):

O relógio com 1515 horas

Definição. Seja m1m \geq 1 um inteiro. Os números inteiros aa e bb são congruentes módulo mm ou, em fórmulas, abmodm. a \equiv b \mod m. se mabm \mid a - b, isto é se a sua diferença aba-b é divisível por mm. Em outras palavras, se aa e bb deixam o mesmo resto divido por mm. O número mm é o módulo.

Exemplo: Para a cifração de César, sejam

A cifração e decifração se descrevem pelo aritmética modular por ci+tmod26 e ictmod26 c \equiv i + t \mod 26 \quad \text{ e } \quad i \equiv c - t \mod 26

O anel finito das classes de resíduos

Dado um inteiro m1m \geq 1, queremos construir um conjunto /m\mathbb{Z} /m \mathbb{Z} com 00 e 11 e sobre que podemos somar (isto é, existe uma operação ++) tal que nele valha m=1++1=0. m = 1 + \cdots + 1 = 0. (Já observamos que, para esta igualdade valer, ++ sobre /m\mathbb{Z} /m \mathbb{Z} tem de ser definida diferente de ++ sobre \mathbb{Z}.) Além do conjunto, queremos construir uma aplicação (ou talvez melhor identificação) :/m\bar \cdot \colon \mathbb{Z} \to \mathbb{Z} /m \mathbb{Z} tal que x=y\bar x = \bar y se, e tão-somente se, xymodmx \equiv y \mod m. Isto é, \bar \cdot identifica xx e yy se têm o mesmo resto divido por mm.

Um tal conjunto chama-se anel (comutativo com 11). Mais exatamente, é

Queremos construir de duas formas, prática e teórica,

Para o matematicamente interessado, a propriedade definidora do anel /m\mathbb{Z} / m \mathbb{Z} é que ele seja

Observamos que, por exemplo,

Matematicamente, a propriedade definidora da minimidade do anel /m\mathbb{Z} / m \mathbb{Z} é uma propriedade universal: Qualquer aplicação A\mathbb{Z} \to A que satisfaz m0m \mapsto 0 passa pela aplicação /m\mathbb{Z} \to \mathbb{Z} / m \mathbb{Z}; isto é, sempre há uma aplicação /mA\mathbb{Z} / m \mathbb{Z} \to A tal que /mA=A. \mathbb{Z} \to \mathbb{Z} / m \mathbb{Z} \to A \quad = \quad \mathbb{Z} \to A.

Construção Teórica

Esta é a construção encontrada em livros de matemática (universitária).

Equação ()(\dagger) diz que exatamente m0m \mathbb{Z} \mapsto 0, e consequentemente, para xx em \mathbb{Z} qualquer, exatamente x+mx. x + m \mathbb{Z} \mapsto \bar x. O que nos leva a pôr

Construção Prática

Esta é a construção encontrada em livros de ciências que aplicam a matemática (por exemplo, a ciência da computação).

Pomos

Isto é, para adicionar e multiplicar em /m\mathbb{Z} /m \mathbb{Z},

  1. calculamos a soma ou produto como em \mathbb{Z}, e
  2. calculamos o seu resto divido por mm.

Pela definição da identificação =r\bar \cdot = \mathrm{r} como resto divido por mm, a igualdade x+y=x+y\bar{x + y} = \bar{x} + \bar y requer que a soma dos restos seja definida pelo resto da soma.

Por exemplo, para m=4m = 4 obtemos as tabelas de adição e multiplicação

+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

e

* 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

Exercício. Mostra que um número inteiro é divisível por 33 (respectivamente 99) se, e tão-somente se, a soma dos seus algarismos decimais é divisível por 33 (respectivamente 99).

Exemplos em Python

Em Python, o operador modular é denotado pelo símbolo percentual %. Por exemplo, na shell interativa, obtemos:

>>> 15 % 12
3
>>> 210 % 12
6
>>> 20 % 10
0

Potenciação Rápida

A função alçapão

em /m\mathbb{Z} / m \mathbb{Z} para um número natural mm. Vemos como calculá-la eficazmente:

Algoritmo

Dados uma base bb e um expoente ee em \mathbb{Z}, para calcular be em /M, b^e \text{ em } \mathbb{Z} / M \mathbb{Z},

  1. Expande o expoente binariamente, isto é e=e0+e12+e222++es2s com e0,e1,...,es em {0,1}, e = e_0 + e_1 2 + e_2 2^2 + \cdots + e_s 2^s \, \text{ com } e_0, e_1, ..., e_s \text{ em } \{ 0, 1 \},
  2. Calcula b1,b2,b22,...,b2smodM. b^1, b^2, b^{2^2}, ..., b^{2^s} \mod M.

Como b2n+1=b2n2=(b2n)2b^{2^{n + 1}} = b^{2^n \cdot 2} = (b^{2^n})^2, isto é, cada potência é o quadrado da anterior (e no máximo MM), cada uma, sucessivamente, é facilmente computável. Obtemos be=be0+e12+e222++es2s=be0(b2)e1(b22)e2(b2s)es b^e = b^{e_0 + e_1 2 + e_2 2^2 + \cdots+ e_s 2^s} = b^{e_0} (b^2)^{e_1} (b^{2^2})^{e_2} \cdots (b^{2^s})^{e_s} Isto é, apenas as potências com expoentes e0,e1,...,ese_0, e_1, ..., e_s iguais a 11 importam, as outras podem ser omitidas.

Este algoritmo leva 2log2(e)2 \log_2(e) multiplicações módulo MM.

Exemplos

Para calcular 353^5 módulo 77, expandimos 5=1+021+122 5 = 1 + 0 \cdot 2^1 + 1 \cdot 2^2 e calculamos 31=3,32=92,322=(32)222=4mod7, 3^1 = 3, 3^2 = 9 \equiv 2, 3^{2^2} = (3^2)^2 \equiv 2^2 = 4 \mod 7, obtendo 35=31+22=31322=345mod7. 3^5 = 3^{1 + 2^2} = 3^1 \cdot 3^{2^2} = 3 \cdot 4 \equiv 5 \mod 7.

Para calcular 3113^{11} módulo 55, expandimos 11=1+121+022+123 11 = 1 + 1 \cdot 2^1 + 0 \cdot 2^2 + 1 \cdot 2^3 e calculamos 31=3,32=94,322=(32)242=1 e 323=3222=(322)212=1mod5, 3^1 = 3, 3^2 = 9 \equiv 4, 3^{2^2} = (3^2)^2 \equiv 4^2 = 1 \text{ e } 3^{2^3} = 3^{2^2 \cdot 2} = (3^{2^2})^2 \equiv 1^2 = 1 \mod 5, obtendo 311=31+21+23=31321323=341=122mod5. 3^{11} = 3^{1 + 2^1 + 2^3} = 3^1 \cdot 3^{2^1} \cdot 3^{2^3} = 3 \cdot 4 \cdot 1 = 12 \equiv 2 \mod 5.

6 Troca de Chaves segundo Diffie-Hellman

Para já nos convencermos da utilidade da aritmética modular, olhamos o protocolo para construir uma chave secreta mútua através de um canal inseguro, apresentado pela primeira vez em Diffie e Hellman (1976).

Isto não é exatamente criptografia assimétrica, ou criptografia de chave pública, porque a chave secreta é conhecida a ambos os correspondentes. Os alogritmos assimétricos que se baseiam neste protocolo (por exemplo, ElGamal e ECC) geram uma chave de uso único para cada mensagem. Esta geração tem de ser suficientemente aleatória para ser imprevisível.

6.1 Troca de Chaves

Observação. Denote daqui por diante, num algoritmo de criptografia assimétrica,

Para Alice e Bob construírem uma chave secreta através de um canal inseguro, combinam primeiro

e depois

  1. Alice, para gerar uma metade da chave, escolhe um número aa,
  2. Bob, para gerar outra metade da chave, escolhe um número bb,
  3. A chave secreta mútua entre Alice e Bob é c:=Ab=(ga)b=gab=gba=(gb)a=Bamodp. c := A^b = (g^a)^b = g^{ab} = g^{ba} = (g^b)^a = B^a \mod p.

O CrypTool 1 oferece no Menu Individual Procedures -> Protocols uma entrada para experimentar com os valores das chaves no Diffie-Hellman.

Os passos do Diffie-Hellman no CrypTool 1

Em Seção 8, o algoritmo ElGamal mostra como cifrar uma mensagem pela chave mútua (que constrói uma chave mútua efêmera por cada mensagem cifrada).

6.2 Segurança

A segurança da troca de chaves de Diffie-Hellman reside na dificuldade de computar o logaritmo módulo pp.

Um olheiro obteria a chave secreta Ab=BaA^b = B^a a partir de AA e BB, se pudesse computar a=loggA ou b=loggBmodp; a = \log_g A \quad \text{ ou } \quad b = \log_g B \mod p; isto é, o logaritmo logg\log_g inverte a exponenciação xgx=yx \mapsto g^x = y, loggy=x com x tal que gx=y. \log_g y = x \quad \text{ com } x \text{ tal que } g^x = y.

Enquanto a exponenciação é facilmente computável, o logaritmo é dificilimamente computável para escolhas de pp e gg apropriadas, isto é:

Concluímos que, como AA e BB são públicos, a segurança computacional de Diffie-Hellman baseia-se unicamente na dificuldade da computação do logaritmo módulo pp.

Mais exatamente, a segurança da Troca de Diffie-Hellman baseia-se no problema de Diffie-Hellman Computacional. Os três problemas da computação do logaritmo modular são, em ordem descendente da sua dificuldade:

O primeiro problema é mais difícil do que o segundo, e o segundo e mais difícil que o terceiro; isto é: A solução do primeiro problema implica a do segundo, e a do segundo implica a do terceiro. Ou, equivalentemente, a hipótese da solução do terceiro problema implica a do segundo, e a do segundo implica a do primeiro.

Se o grupo que contém gg é genérico (isto é, satisfaz apenas os axiomas de um grupo, mas nada além) e de cardinalidade prima ou desconhecida, então se demonstra que não existe solução do problema de Diffie-Hellman Decisório, logo, tampouco para os problemas de Diffie-Hellman Computacional e o Logaritmo Discreto. Porém, isto não exclui que exista solução em grupos específicos tal como /p\mathbb{Z} / p \mathbb{Z} das unidades multiplicativas módulo um primo pp; o que de fato ocorre!

Vice-versa: Toda solução conhecida do segundo problema se baseie na solução do primeiro; logo, supõe-se que, de fato, estes dois problemas sejam equivalentes, isto é, a solução do primeiro problema implique a do segundo, e reciprocamente. Existem evidências: Joux e Nguyen (2003) constrói uma família de grupos onde eles são equivalentes e, supostamente, irresolúveis (como definido acima). Antes, em 2001, Maurer e Wolf (1999) já demonstrou esta equivalência para grupos genéricos (baseado em observações para curvas elípticas finitas no início dos anos 90) com certas restrições nos divisores primos da cardinalidade do grupo.

Ao contrário, o terceiro problema é para muitos grupos mais fácil do que o segundo, isto é, existem grupos conhecidos em que o problema Diffie-Hellman Decisório é resolúvel, mas não o problema de Diffie-Hellman Computacional. (Este é um fenómeno não tão desconhecido: Por exemplo, enquanto leva tempo exponencial (no número de bites) para calcular os fatores primos de um número composto nn, existem algoritmos que levam tempo polinomial para decidir se nn é composto sem revelar os seus fatores. De fato, conjetura-se que todo algoritmo BPP, cuja saída pode ser verifica em tempo polinomial com probabilidade de erro <1/2< 1 / 2, é um algoritmo em P, os cuja saída pode ser verifica em tempo polinomial. Foi demonstrado em 2002 por Agrawal, Kayal e Saxena, um algoritmo polinomial existir para a verificação se um número é primo ou não, isto é, ser em P; antes, por exemplo, o Teste de Rabin-Miller, já mostrou que o problema é em BPP. [Na prática, o Teste de Rabin-Miller permanece o algoritmo preferido porque é muito mais rápido e a probabilidade de erro arbitrariamente pequena.])

O exemplo clássico e importante, de um grupo em que o problema de Diffie-Hellman Decisório é resolúvel: se gg gera todo o grupo /p*\mathbb{Z} / p \mathbb{Z}^* (isto é, ge1modpg^e \equiv 1 \mod p para e=p1e = p-1 pela primeira vez) então o valor de gamodpg^a \mod p em {±1}\{ \pm 1 \} revela se aa é par ou ímpar. Isto é, dados gag^a, gbg^b e gabg^{ab}, calculam-se em tempo polinomial (no número de bits) os bits menos significativos de aa, bb e abab; logo, consegue-se pela sua comparação distinguir gabg^{ab} de um número qualquer em tempo polinomial com probabilidade de erro <1/2< 1 / 2. Isto é, o problema é resolúvel segundo a definição dada acima.

O exemplo clássico, de um grupo em que o problema de Diffie-Hellman Decisório é supostamente irresolúvel segundo muitos criptologistas, é um subgrupo de cardinalidade prima de Zp×Z_p^\times para pp primo. Por exemplo, se (p1)/2(p - 1) / 2 é primo, (isto é, pp é um primo seguro), então o grupo de quadrados módulo pp é um tal grupo.

Observação. A criptografia baseada em emparelhamentos (pairing-based cryptography) usa (os grupos de) curvas elípticas finitas especialmente criadas em que o problema de Diffie-Hellman Computacional seja considerado difícil, mas o de Diffie-Hellman Decisório seja fácil. Isto é, outra indicação da suposta inequivalência entre eles.

Ele foi popularizada por Antoine Joux em 2002, e usa certo emparelhamento de Weil ee na curva elíptica para, por exemplo, estabelecer um segredo comum entre três participantes (enquanto a Troca de Chave segundo Diffie-Hellman é restrita a dois): O emparelhamento é bilinear, isto é, e(ga,hb)=e(g,h)abe(g^a, h^b) = e(g, h)^{ab}. Se a Alice partilha A=gaA = g^a, o Bob partilha B=gbB = g^b e o Charles partilha C=gcC = g^c para um inteiro aleatório e secreto cc, então

Pela bilinearidade, todos os valores são iguais. (Nota que gg denota um ponto na curva, um par de números e a potenciação é a iterada adição deste ponto no grupo como explicado em Seção 9.3.)

Números Apropriados

Teorema de Euclides. #{ números primos }= \# \{ \text{ números primos } \} = \infty Demonstração: Suponhamos o contrário, que haja só um número finito p1,...,pnp_1, ..., p_n de números primos. Considere q=p1...pn+1q = p_1 ... p_n + 1. Como qq é maior que p1p_1, …, pnp_n, não é primo. Seja então pp um número primo que divida qq. Pela hipótese, pp em {p1,...,pn}\{p_1, ..., p_n\}. Porém, pela sua definição, qq tem o resto 11 divido por qualquer primo p1p_1, …, pnp_n. Contradição!

O Teorema de Euclides garante que haja números primos arbitrariamente grandes (>1024> 1024 bites). Em Seção 7.3, veremos como encontrá-los. Graças a Deus, quase todo número primo pp satisfaz que

O Teorema da Raiz Primitiva (que será demonstrado em Seção 7.2) garante que sempre haja um número gg em 𝐅p*\mathbf{F}_p^* tal que {g,g2,g3,...,gp1},=𝐅p*(={1,2,3,...,p1}) \{ g, g^2, g^3, ..., g^{p-1} \}, = \mathbf{F}_p^* (= \{ 1, 2, 3, ..., p-1 \}) Em particular, a cardinalidade de {g,g2,g3,...,gp1}\{ g, g^2, g^3, ..., g^{p-1} \} é um múltiplo de qualquer divisor primo qq de p1p-1.

Na prática, os números pp e gg são adotados duma fonte confiável.

Computação do Logaritmo

Como inicialmente os valores gxg^x sobre /p\mathbb{Z} / p \mathbb{Z} igualam os valores de gxg^x sobre \mathbb{Z}, mais exatamente para x<loggpx < \log_g p (por exemplo, em Figura 5.1 com g=2g = 2 e p=101p = 101 para x<7x < 7), os números secretos aa e bb devem ser suficientemente grande, mais exatamente, maior do que loggp\log_g p. Para garantir isto na prática, estes números são artificialmente aumentados (por exemplo, se obtidos a partir de uma mensagem demasiada curta, ela é artificialmente enchida).

Presentemente, o algoritmo mais rápido para calcular o logaritmo xx a partir de gxg^x, é uma modificação do campo de número de peneira geral de Gordon (1993). A grosso modo, o número de operações para calcular o logaritmo de um número inteiro de nn bites é exp(logn1/3). \exp(\log n^{1/3}).

Módulos Arbitrários

Observemos para módulos que não são primos, isto é, um produto de fatores primos, que a dificuldade aumenta linearmente no número dos fatores, ao contrário dela aumentar exponencialmente no número dos bites de cada fator:

Produto de Primos Diferentes

Se o módulo m=pqm = pq é produto de dois fatores pp e qq sem fator comum, então o logaritmo modular loggmodm \log_g \mod m pode ser computado, pelo Teorema Chinês dos Restos, pelos logaritmos loggmodp e loggmodq \log_g \mod p \quad \text{ e } \quad \log_g \mod q Mais exatamente, existem inteiros aa e bb, computados (em tempo linear no número dos bites de pp e qq) pelo Algoritmo de Euclides (estendido), tais que ap+bq=1ap + bq = 1 e loggmodm=a(loggmodp)+b(loggmodq). \log_g \mod m = a (\log_g \mod p) + b (\log_g \mod q).

Potência de um Primo

Se o módulo m=pem = p^e é uma potência de um primo pp, então Bach (1984) mostra como o logaritmo modular módulo mm para uma base gg logg:/m*/ϕ(m) \log_g \colon \mathbb{Z} / m \mathbb{Z}^* \to \mathbb{Z} / \phi(m) \mathbb{Z} pode ser computado em tempo polinomial a partir do logaritmo módulo pp. Exponhamos os passos para um número primo p>2p > 2:

  1. Recordemo-nos da subsecção sobre a existência da raiz primitiva para qualquer módulo de Seção 7.2 que /pe*\mathbb{Z} / p^e \mathbb{Z}^* é cíclico de ordem (p1)pe1(p-1)p^{e-1}. Logo, existe uma aplicação multiplicativa /pe*μp1×U1 \mathbb{Z} / p^e \mathbb{Z}^* \to \mu_{p-1} \times U_1 dada por xxpe1,x/xpe1(*) x \mapsto x^{p^{e-1}}, x / x^{p^{e-1}} \quad (*) onde μp1={ζ/pe*:ζp1=1} \mu_{p-1} = \{ \zeta \in \mathbb{Z} / p^e \mathbb{Z}^* : \zeta^{p-1} = 1 \} denote o grupo das (p1)(p-1)-ésimas raízes da unidade e U1=1+p/pe U_1 = 1 + p \mathbb{Z} / p^e \mathbb{Z} o das unidades unitárias.

  2. Temos o isomorfismo μp1𝔽p* \mu_{p-1} \to \mathbb{F}_p^* dado por xxmodpx \mapsto x \mod p e o seu inverso por XXpe1X \mapsto X^{p^{e-1}} para qualquer XX em /pe\mathbb{Z} / p^e \mathbb{Z} tal que XxmodpX \equiv x \mod p. (Observa que a restrição do homomorfismo /pe*U1 \mathbb{Z} / p^e \mathbb{Z}^* \to U_1 dado por x1pe1x^{1 - p^{e-1}} a U1U_1 é a identidade porque a ordem de U1U_1 é pe1p^{e-1}.)

  3. Temos o logaritmo para a base gg logg:𝔽p*/(p1) \log_g \colon \mathbb{F}_p^* \to \mathbb{Z} / (p-1) \mathbb{Z} e temos o logaritmo natural log:U1p(/pe) \log \colon U_1 \to p (\mathbb{Z} / p^e \mathbb{Z}) que é calculado em tempo polinomial pela fórmula u[xpe1]/pe;(6.1) u \mapsto [x^{p^e} - 1]/p^e; \qquad(6.1) e o qual fornece o logaritmo logg:U1p(/pe)\log_g \colon U_1 \to p (\mathbb{Z} / p^e \mathbb{Z}) para a base gg pelo escalamento logg=log/logg. \log_g = \log \cdot / \log g.

  4. Pelo Teorema Chinês dos Restos, temos o isomorfismo /(p1)×/pe1/(p1)pe1 \mathbb{Z} / (p-1) \mathbb{Z} \times \mathbb{Z} / p^{e-1} \mathbb{Z} \to \mathbb{Z} / (p-1) p^{e-1} \mathbb{Z} dada pelo produto e o seu inverso dado por y(aymodp,bymodpe1)y \mapsto (a y \mod p, b y \mod p^{e-1}) onde aa e bb satisfazem a(p1)+b(pe1)=1a (p-1) + b (p^{e-1}) = 1 e foram obtidos pelo Algoritmo de Euclides (estendido).

Concluímos que, dado

o valor logg(y)\log_g(y) de logg:(/pe)*/(p1)pe1\log_g \colon (\mathbb{Z} / p^e \mathbb{Z})^* \to \mathbb{Z} / (p-1)p^{e-1} \mathbb{Z} é computado em tempo polinomial.

Observação. Para facilitar a computação, ao invés da projeção /pe*U1 \mathbb{Z} / p^e \mathbb{Z}^* \to U_1 dada em (*)(*) por xx1pe1x \mapsto x^{1 - p^{e-1}}, é mais rápido usar a dada por π:xxp1\pi \colon x \mapsto x^{p-1}. Porém, a sua restrição a U1U_1 não é a identidade. Logo, é preciso usar ao invés de logg:U1p/pe \log g \colon U_1 \to p \mathbb{Z} / p^e \mathbb{Z} o logaritmo escalado (p1)1logg (p-1)^{-1} \log_g para obter logg=(p1)1loggπ=(log(g)p1)1logπ:U1p/pe. \log_g = (p-1)^{-1} \log_g \circ \pi = (\log(g) p-1)^{-1} \log \circ \pi \colon U_1 \to p \mathbb{Z} / p^e \mathbb{Z}.

Logaritmo Discreto Para uma Potência de um Primo

Fundamentemos a Equação 6.1 que define o logaritmo log:U1p(/pe)\log \colon U_1 \to p (\mathbb{Z} / p^e \mathbb{Z}): recordemos a definição da exponencial sobre \mathbb{R} pelos juros compostos exp(x)=lim(1+1n)n, \exp(x) = \lim \left(1+\frac{1}{n}\right)^n, a qual leva à definição da função inversa log(x)=limn(x1n1)=lim1ϵ(xϵ1) \log(x) = \lim n (x^{\frac{1}{n}} - 1) = \lim \frac{1}{\epsilon}(x^{\epsilon} - 1) onde ϵ=1n0\epsilon = \frac{1}{n} \to 0.

Ora, em /pe\mathbb{Z} / p^e \mathbb{Z}, temos 11, pp, p2p^2, …, pe=0p^e = 0, isto é, pn0p^n \to 0, o que talvez motive a ideia de considerar pp como pequeno. Logo, o bom análogo sobre U1U_1 é log(x)=lim1pe1(xpe11). \log(x) = \lim \frac{1}{p^{e-1}}(x^{p^{e-1}} - 1). Com efeito, sobre U1U_1 log(1+x)=xx22+x33... \log(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - ... é um valor bem-definido em p/pep \mathbb{Z} / p^e \mathbb{Z}, porque se pp divide xx, então nenhum denominador da fração cortada é divisível por pp e todos os números indivisíveis por pp são invertíveis em /pe\mathbb{Z} / p^e \mathbb{Z}. Da mesma maneira, sobre p/pep \mathbb{Z} / p^e \mathbb{Z}, exp(x)=n0xnn! \exp(x) = \sum_{n \geq 0} \frac{x^n}{n!} é um valor bem definido em 1+p/pe1 + p \mathbb{Z} / p^e \mathbb{Z}, porque se pp divide xx, então nenhum denominador cortado é divisível por pp e todos os números indivisíveis por pp são invertíveis em /pe\mathbb{Z} / p^e \mathbb{Z}.

De interesse particular é a base epe^p do logaritmo natural em 1+p/pe1 + p \mathbb{Z} / p^e \mathbb{Z}, isto é, o argumento yy tal que logy=1\log y = 1. Por exemplo, para p=7p = 7 e e=4e = 4, calculamos exp(p)=n0pnn!=1+p+p22+p33!=1+7127=1+17+472+273. \exp(p) = \sum_{n \geq 0} \frac{p^n}{n!} = 1 + p + \frac{p^2}{2} + \frac{p^3}{3!} = 1 + 7 \cdot 127 = 1 + 1 \cdot 7 + 4 \cdot 7^2 + 2 \cdot 7^3.

7 Multiplicação e Divisão Modular

Estudamos a multiplicação nos anéis finitos /n\mathbb{Z} /n \mathbb{Z}. Interessamo-nos em particular por quais números podemos dividir neles. Será o Algoritmo de Euclides que nos computa a reposta.

7.1 O Algoritmo de Euclides

A chave privada

define uma função que é o inverso da função definida pela chave pública. Este inverso é computado via o maior divisor comum entre os dois números. Este, por sua vez, é computado pelo Algoritmo de Euclides, uma iterada divisão com resto.

Introduzimos então

Sejam aa e bb números inteiros. Denotamos por aba \mid b que aa divide bb, isto é, que bb é um múltiplo de aa (existe um inteiro qq tal que b=qab = q a). Recordemo-nos de umas implicações básicas sobre a divisibilidade entre números inteiros:

Proposição 1. Sejam a,b,ca,b,c números inteiros.

  1. Se a|ba | b e b|cb | c, então a|ca | c.
  2. Se a|ba | b e b|ab | a, então a=±ba = \pm b.
  3. Se a|ba | b e a|ca | c, então a|b±ca | b \pm c.

Definição. Um divisor comum de dois números inteiros aa e bb é um número natural que divide os dois. O maior divisor comum de dois números inteiros aa e bb é o maior número natural que divide os dois. Denote mdc(a,b)\mathrm{mdc}(a,b) o maior divisor comum de aa e bb, mdc(a,b)=o maior número natural que divide a e b \mathrm{mdc}(a,b) = \text{o maior número natural que divide } a \text{ e } b

Exemplo. O maior divisor comum de 1212 e 1818 é 66.

Definição. Os números inteiros aa e bb são relativamente primos se mdc(a,b)=1\mathrm{mdc}(a,b) = 1, isto é, se nenhum número inteiro >1> 1 divide aa e bb.

Para quaisquer números inteiros aa e bb, os números inteiros a/ga/g e b/gb/g para g=mdc(a,b)g = \mathrm{mdc}(a,b) são relativamente primos.

A divisão com resto ajuda-nos a construir um algoritmo eficiente para calcular o maior divisor comum. Recordemos-nos, mais uma vez Divisão com Resto:

Definição. Sejam aa e bb números inteiros positivos. Que aa dividido por bb tem quociente qq e resto rr significa a=bq+r com 0r<b.(7.1) a = b \cdot q + r \quad \text{ com } 0 \leq r < b. \qquad(7.1)

Exemplo. Para a=19a = 19 e b=5b = 5, obtemos 19=53+419 = 5 \cdot 3 + 4. Isto é, o resto de 1919 dividido por 55 é 44.

Uma combinação linear (ou soma de múltiplos) de dois números inteiros aa e bb é uma soma s=λa+μb s = \lambda a + \mu b para números inteiros λ\lambda e μ\mu.

Exemplo. Para a=15a = 15 e b=9b = 9, uma soma de múltiplos deles é s=2a+(3)b=21539=3. s = 2 \cdot a + (-3) \cdot b = 2 \cdot 15 - 3 \cdot 9 = 3.

É importante observar pela Proposição 1.C a seguinte implicação: se um número inteiro dd divide aa e bb, então dd divide toda combinação linear ss de aa e bb.

Algoritmo de Euclides

Em particular, olhando à divisão com resto em Equação 7.1, para um número inteiro dd, observamos:

Isto é, dd divide aa e bb se, e tão-somente se, dd divide bb e rr. Quer dizer, os divisores comuns de aa e bb são os mesmos que os de bb e rr. Em particular, mdc(a,b)=mdc(b,r). \mathrm{mdc}(a,b) = \mathrm{mdc}(b,r). Dividindo com resto os números bb e rr (que é <b< b), obtemos b=rq+r com 0r<r b = r \cdot q' + r' \quad \text{ com } 0 \leq r' < r e mdc(b,r)=mdc(r,r). \mathrm{mdc}(b,r) = \mathrm{mdc}(r,r'). Iterando, e assim diminuindo o resto, chegamos a s=r...s = r^{'...'} e r...r^{'...''} com r...=0r^{'...''} = 0, isto é mdc(a,b)=...=mdc(s,0)=s. \mathrm{mdc}(a,b) = ... = \mathrm{mdc}(s,0) = s. Em palavras, o maior divisor comum é o penúltimo resto (ou o último diferente de 00).

Exemplo. Para calcular mdc(748,528)\mathrm{mdc}(748, 528), obtemos

748=5281+220748 = 528 \cdot 1 + 220

528=2202+88528 = 220 \cdot 2 + 88

220=882+44220 = 88 \cdot 2 + 44

88=442+088 = 44 \cdot 2 + 0

logo mdc(528,220)=44\mathrm{mdc}(528, 220) = 44.

O CrypTool 1, na entrada do menu Indiv. Procedures -> Number Theory Interactive -> Learning Tool for Number Theory, Seção 1.3, página 15, mostra uma animação deste algoritmo:

O algoritmo de Euclides no CrypTool 1

Formalizemos o que acabamos de observar:

Teorema. (Algoritmo de Euclides) Sejam aa e bb números inteiros positivos com aba \geq b. O seguinte algoritmo calcula mdc(a,d)\mathrm{mdc}(a,d) em um número finito de passos:

(início) Ponha r0=ar_0 = a e r1=br_1 = b, e i=1i = 1.

(divisão) Divida ri1r_{i-1} por rir_i com resto para obter ri1=riqi+ri+1 com 0ri+1<ri. r_{i-1} = r_i q_i + r_{i + 1} \quad \text{ com } 0 \leq r_{i + 1} < r_i. (distinção) Distinga entre:

Demonstração: Precisamos de demonstrar que o algoritmo termina com o maior divisor comum de aa e bb:

Observação: Bastam 2log2b+12 \cdot \log_2 b + 1 divisões com resto para o algoritmo terminar.

Demonstração: Demonstramos ri+2<1/2ri.() r_{i + 2} < 1/2 \cdot r_i. \quad (\dagger) Temos

Neste último caso, segue ri=ri+11+ri+2 r_i = r_{i + 1} \cdot 1 + r_{i + 2} e então ri+2=riri+1<ri1/2ri=1/2ri. r_{i + 2} = r_i - r_{i + 1} < r_i - 1/2 \cdot r_i = 1/2 \cdot r_i. Por (\dagger) obtemos iterativamente que bastam 2log2b+12 \cdot \log_2 b + 1 divisões com resto para o algoritmo terminar.

Com efeito, revela-se que já bastam no máximo 1.45log2(b)+1.681.45 \log_2(b) + 1.68 divisões com resto, e em média já 0.85log2(b)+0.140.85 \log_2(b) + 0.14.

Algoritmo de Euclides Estendido

Para a computação do inverso modular, precisamos de mais informações do que o maior divisor comum (calculado pelo Algoritmo de Euclides).

Com efeito, observa-se que em cada passo do Algoritmo de Euclides o maior divisor comum mdc(x,m)\mathrm{mdc}(x, m) de xx e mm é uma combinação linear (ou soma de múltiplos) de xx e mm, isto é, mdc(x,m)=λx+μm para inteiros x e m. \mathrm{mdc}(x, m) = \lambda x + \mu m \quad \text{ para inteiros } x \text{ e } m. O inverso de xx módulo mm é um destes múltiplos. Vamos apresentar o Algoritmo de Euclides Estendido que preserva esta informação.

Teorema. (Algoritmo de Euclides Estendido) Para quaisquer números inteiros positivos aa e bb, o seu maior divisor comum mdc(a,b)\mathrm{mdc}(a,b) é uma combinação linear de aa e bb; isto é, há números inteiros uu e vv tais que au+bv=mdc(a,b). au + bv = \mathrm{mdc}(a,b). Demonstração: Como r0=ar_0 = a, r1=br_1 = b, e r2=r0q1r1r_2 = r_0 - q_1 r_1, segue que r2r_2 é uma combinação linear de aa e bb. Em geral, como ri1r_{i-1} e rir_i são combinações lineares de aa e bb, primeiro qiriq_i r_i é uma combinação linear de aa e bb, e assim ri+1=ri1qiri r_{i + 1} = r_{i-1} - q_i r_i é uma combinação linear de aa e bb. Em particular, se rI+1=0r_{I + 1} = 0 então rI=mdc(rI,rI+1)=mdc(a,b)r_I = \mathrm{mdc}(r_I, r_{I + 1}) = \mathrm{mdc}(a,b) é uma combinação linear de aa e bb.

O CrypTool 1, na entrada do menu Indiv. Procedures -> Number Theory Interactive -> Learning Tool for Number Theory, Seção 1.3, página 17, mostra uma animação deste algoritmo:

O algoritmo de Euclides estendido no CrypTool 1

Exemplo. Revenhamos à calculação do maior divisor comum de a=748a = 748 e b=528b = 528. O algoritmo de Euclides deu:

748=5281+220748 = 528 \cdot 1 + 220

528=2202+88528 = 220 \cdot 2 + 88

220=882+44220 = 88 \cdot 2 + \mathbf{44}

88=442+088 = 44 \cdot 2 + 0,

o que fornece as combinações lineares

220=7485281=ab220 = 748 - 528 \cdot 1 = a - b

88=5282202=b(ab)2=3b2a88 = 528 - 220 \cdot 2 = b - (a-b) \cdot 2 = 3b - 2a

44=220882=(ab)(3b2a)2=5a7b\mathbf{44} = 220 - 88 \cdot 2 = (a-b) - (3b - 2a) \cdot 2 = 5a - 7b.

Com efeito, 44=57487528. 44 = 5 \cdot 748 - 7 \cdot 528.

Implementação em Python

Para implementar o algoritmo de Euclides, vamos usar atribuição múltipla em Python:

>>> spam, eggs = 42, 'Hello'
>>> spam
42
>>> eggs
'Hello'
>>> a, b, c, d = ['Alice', 'Bob', 'Carol', 'David']
>>> a
'Alice'
>>> b
'Bob'
>>> c
'Carol'
>>> d
'David'

Os nomes das variáveis e os seus valores são alistados à esquerda respectivamente à direita de ==.

Algoritmo de Euclides

Aqui é uma função que implementa o algoritmo de Euclides em Python; ela devolve o maior divisor comum mdc(a,b)\mathrm{mdc}(a,b) de dois inteiros aa e bb.

def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

Por exemplo, no shell interativo:

>>> gcd(24, 30)
6
>>> gcd(409119243, 87780243)
6837

Algoritmo de Euclides Estendido

O operador // vai figurar na implementação do algoritmo de Euclides estendido; ele divide dois números e arredonda para baixo. Isto é, devolve o maior inteiro igual ou menor que o resultado da divisão. Por exemplo, no shell interativo:

>>> 41 // 7
5
>>> 41 / 7
5.857142857142857
>>> 10 // 5
2
>>> 10 / 5
2.0

Optamos pela seguinte implementação do algoritmo de Euclides estendido:

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

Por exemplo,

print egcd(1432,123211)

7.2 Divisibilidade Modular

A chave privada é calculada pelo inverso multiplicativo na aritmética modular a partir da chave pública, tanto no algoritmo RSA quanto no algoritmo ElGamal.

Acabamos de apreender como calcular o maior divisor comum pelo Algoritmo de Euclides Estendido; agora apreendamos como ele é usado para calcular este inverso multiplicativo.

Unidades

Enquanto em \mathbb{Q} podemos dividir por qualquer número (exceto 00), em \mathbb{Z} unicamente por ±1\pm 1! Os números pelos quais pode se dividir são chamadas invertíveis ou unidades. A quantidade de números invertíveis em /m\mathbb{Z} / m \mathbb{Z} depende do módulo mm. De modo grosso, quanto menos fatores primos em mm, tanto mais unidades em /m\mathbb{Z} / m \mathbb{Z}.

Caracterização

Definição. O elemento x\bar x em /m\mathbb{Z} / m \mathbb{Z} é uma unidade (ou invertível) se existe y\bar y em /m\mathbb{Z} / m \mathbb{Z} tal que yx=1\bar y \bar x = 1. O elemento y\bar y é o inverso de x\bar x e denotado por x1\bar x^{-1}. O conjunto das unidades (em que podemos multiplicar e dividir) é denotado por (/m)*:={ as unidades em /m}. (\mathbb{Z} / m \mathbb{Z})^* := \{ \text{ as unidades em } \mathbb{Z} / m \mathbb{Z} \}. A função totiente de Euler Φ\Phi é m#(/m)*; m \mapsto \# (\mathbb{Z} / m \mathbb{Z})^*; isto é, dado mm, conta quantas unidades /m)\mathbb{Z} / m \mathbb{Z}) tem.

Observações:

Exemplos:

Proposição. Seja mm em \mathbb{N} e x\bar x em /m\mathbb{Z} / m \mathbb{Z}, isto é, x\bar x em {0,1,...,m1}\{ 0, 1, ..., m-1 \}. O número x\bar x é uma unidade em /m\mathbb{Z} / m \mathbb{Z} se, e tão-somente se, mdc(x,m)=1\mathrm{mdc}(x,m) = 1.

Demonstração: Observamos que cada divisor comum de x\bar x e mm divide cada soma de múltiplos s=ux+vms = u \bar x + v m de x\bar x e mm; em particular, se s=1s = 1, então o maior divisor comum de x\bar x e mm é 11.

Pelo Algoritmo de Euclides Estendido, há uu e vv em \mathbb{Z} tais que ux+vm=mdc(x,m). u \bar x + v m = \mathrm{mdc}(\bar x,m). Logo, pela observação acima, mdc(x,m)=1\mathrm{mdc}(\bar x,m) = 1 se, e tão-somente se, há uu em \mathbb{Z} tal que ux1modm. u \bar x \equiv 1 \mod m. Equivalentemente, ux=1 em /m. \bar u \bar x = 1 \quad \text{ em } \mathbb{Z} / m \mathbb{Z}. para u\bar u em /m\mathbb{Z} / m \mathbb{Z} o resto de uu dividido por mm. Isto é, x\bar x é uma unidade em /m\mathbb{Z} / m \mathbb{Z} cujo inverso é x1=u\bar x^{-1} = \bar u.

Observação. Concluímos que para xx em {0,...,m1}\{ 0, ..., m-1 \} com mdc(x,m)=1\mathrm{mdc}(x,m) = 1, obtemos pelo Algoritmo de Euclides Estendido uu e vv em \mathbb{Z} tais que ux+vm=1 u x + v m = 1 O inverso x1x^{-1} de xx em /m\mathbb{Z} /m \mathbb{Z} é dado pelo resto de uu dividido por mm.

Em Python, podemos então calcular o inverso de aa em /m\mathbb{Z} / m \mathbb{Z} por

def ModInverse(a, m):
    if gcd(a, m) != 1:
        return None # no mod. inverse exists if a and m not rel. prime
    else
        gcd, x, y = egcd(a,m)
        return x % m

Corpos Finitos

Corolário 7.1. Se pp é um número primo, então (/p)*={1,...,p1}. (\mathbb{Z} / p \mathbb{Z})^* = \{ 1, ..., p-1 \}.

Isto é, todos os elementos, exceto 00, são unidades. Em particular, Φ(p)=p1\Phi(p) = p-1.

Demonstração: Se pp é primo, então mdc(x,p)=1\mathrm{mdc}(x, p) = 1 para qualquer xx em {1,...,p1}=/p\{1, ..., p-1\} = \mathbb{Z} / p \mathbb{Z}.

Um anel cujos elementos, exceto 00, são todos unidades é um corpo. Isto é, em um corpo, dado um elemento aa, além de a-a, o inverso de aa sob adição, sempre há a1a^{-1}, o inverso de aa sob multiplicação. Em vez de ba1b a^{-1}, se escreve também b/ab / a. Em outras palavras, além de podermos subtrair, podermos dividir. Os exemplos mais comuns são \mathbb{Q}, \mathbb{R} e \mathbb{C}, todos sendo infinitos.

O corpo com pp elementos (isto é, /p\mathbb{Z} / p \mathbb{Z}) é denotado por 𝔽p\mathbb{F}_p.

Observação. Para um módulo do tipo m=pqm = pq para pp e qq primo, vale pelo Teorema Chinês dos Restos /m=/p×/q\mathbb{Z} /m \mathbb{Z} = \mathbb{Z} /p \mathbb{Z} \times \mathbb{Z} /q \mathbb{Z}, e conforme /m*=/p*×/q*. \mathbb{Z} /m \mathbb{Z}^* = \mathbb{Z} /p \mathbb{Z}^* \times \mathbb{Z} /q \mathbb{Z}^*. Em particular, como os dois fatores são corpos, ϕ(m)=(p1)(q1)\phi(m) = (p-1)(q-1). Esta observação é (implicitamente, neste curso) usada no algoritmo RSA.

Existência da raiz primitiva para um módulo primo

Teorema. (Existência da raiz primitiva em um corpo finito) Se pp é um número primo, então existe α\alpha em 𝔽p*={1,2,...,p1}\mathbb{F}_p^* = \{ 1, 2, ..., p-1 \} tal que 𝔽p*={α,α2,...}. \mathbb{F}_p^* = \{ \alpha, \alpha^2, ... \}.

Demonstração: Como (pela iterada divisão com resto) um polinômio de grau mm tem m\leq m raízes, e xm=1x^m = 1 se, e tão-somente se, P(x)=0P(x) = 0 para P(X)=Xm1P(X) = X^m - 1, vale #{x em 𝔽p* tal que xm=1}m() \# \{ x \text{ em } \mathbb{F}_p^* \text{ tal que } x^m = 1 \} \leq m \quad (\dagger)

Mostramos que qualquer tal grupo GG é cíclico, isto é, gerado por um elemento: Seja xx um elemento em GG de ordem (= o menor número m>0m> 0 tal que xm=1x^m = 1) máxima. Se m<#Gm < \# G, então há por ()(\dagger) um yy em GG cuja ordem não divide mm. Então a ordem de z=xyz = xy é >m> m, em contradição à escolha de mm.

Existência da Raiz Primitiva para um módulo qualquer

Para explicarmos porque usualmente só módulos primos são usados para Diffie-Hellman, estabeleçamos para quais módulos mm as unidades de /m\mathbb{Z} / m \mathbb{Z} têm um único gerador:

Proposição. Se pp é um número primo e ee um inteiro positivo, então α\alpha em /pe\mathbb{Z} / p^e \mathbb{Z} é uma unidade se, e tão-somente se, pp não divide α\alpha.

Demonstração: O número α\alpha em A=/peA = \mathbb{Z} / p^e \mathbb{Z} é uma unidade se, e tão-somente se, a multiplicação α\alpha \cdot sobre AA é sobrejetora, isto é, todo elemento em AA é produto de α\alpha. Como AA é finito, pelo princípio do pombal, uma aplicação sobre AA é sobrejetora se, e tão-somente se, é injetora, isto é, manda dois argumentos diferentes a dois valores diferentes.

Como a multiplicação ϕ=α\phi = \alpha \cdot sobre AA satisfaz ϕ(ab)=ϕ(a)ϕ(b)\phi(a \cdot b) = \phi(a) \cdot \phi(b), ela é injetora se, e tão-somente se, para todo xx em AA, se ϕ(x)=0\phi(x) = 0, então x=0x = 0.

Por contraposição, existe xx em AA não-nulo com ϕ(x)=αx=0\phi(x) = \alpha x = 0, isto é, pep^e não divide xx, mas divide αx\alpha x se, e tão-somente se, pp divide α\alpha. \quad q.e.d.

Em particular, notemos o valor da Função Totiente de Euler Φ(pe)=#/pe*=(p1)pe1. \Phi(p^e) = \# \mathbb{Z} / p^e \mathbb{Z}^* = (p-1)p^{e - 1}.

Recordemo-nos de que a ordem ee de um elemento gg do grupo /m*\mathbb{Z} / m \mathbb{Z}^* é o mínimo expoente ee tal que ge=1g^e = 1.

Teorema (Existência da raiz primitiva para um módulo que é a potência de 22) Seja ee um inteiro positivo. Existe α\alpha em /2e\mathbb{Z} / 2^e \mathbb{Z} tal que /2e*={α,α2,...}. \mathbb{Z} / 2^e \mathbb{Z}^* = \{ \alpha, \alpha^2, ... \}. se, e tão-somente se, e=0,1e = 0, 1 ou 22.

Demonstração: Se e=0,1e = 0, 1 ou 22, então 00, 11 e 33 geram /2e*\mathbb{Z} / 2^e \mathbb{Z}^*. Se e=3e = 3, então, nenhum dos dois números x=3x = 3 ou 77 tais que x3mod22x \equiv 3 \mod 2^2 geram /23\mathbb{Z} / 2^3 \mathbb{Z}; logo, não existe gerador. Se e>3e > 3 e gxamod2eg^x \equiv a \mod 2^e, então gxamod23g^x \equiv a \mod 2^3. Logo, tampouco existe gerador. \quad q.e.d.

Teorema (Existência da raiz primitiva para um módulo que é a potência de um número primo ímpar) Se pp é um número primo >2> 2 e ee um inteiro positivo, então existe α\alpha em /pe\mathbb{Z} / p^e \mathbb{Z} tal que /pe*={α,α2,...}. \mathbb{Z} / p^e \mathbb{Z}^* = \{ \alpha, \alpha^2, ... \}.

Demonstração: O caso e=1e = 1 já foi demonstrado. Mostremos primeiro o caso e=2e = 2: Seja g=g1g = g_1 um gerador de /p\mathbb{Z} / p \mathbb{Z} e g2=g+kpg_2 = g + k p em /p2\mathbb{Z} / p^2 \mathbb{Z}. Temos g2p1gp11modp, g_2^{p-1} \equiv g^{p-1} \equiv 1 \mod p, isto é, g2p11+rpmodp2g_2^{p-1} \equiv 1 + r p \mod p^2 para algum rr inteiro.

Se r0r \neq 0, então a ordem de g2>p1g_2 > p-1. Como #/p2*=(p1)p\# \mathbb{Z} / p^2 \mathbb{Z}^* = (p-1)p, pelo Teorema de Lagrange, a ordem de g2g_2 é (p1)p(p-1)p; isto é, g2g_2 gera /p2*\mathbb{Z} / p^2 \mathbb{Z}^*.

Temos g2p1=(g+kp)p11modp2 g_2^{p-1} = (g+kp)^{p-1} \equiv 1 \mod p^2 se, e tão-somente se, (g+kp)pg+kpmodp2. (g + kp)^p \equiv g + kp \mod p^2. Como (g+kp)p=gpmodp2(g + kp)^p = g^p \mod p^2, se, e tão-somente se, gpgkpmodp2. g^p - g \equiv kp \mod p^2. Isto é, se k[gpg]/pmodp2k \nequiv [g^p - g]/p \mod p^2, então g2g_2 gera /p2\mathbb{Z} / p^2 \mathbb{Z}.

Observemos que se gt1+kpsmodps+1, g^t \equiv 1 + k p^s \mod p^{s+1}, então gpt1+kps+1modp(s+1)+1. g^{p t} \equiv 1 + k p^{s+1} \mod p^{(s+1)+1}. Logo, se a ordem de gg módulo ps+1p^{s+1} é >t> t, então a ordem de gg módulo módulo p(s+1)+1p^{(s+1)+1} é >tp> tp. Em particular, se gg gera /ps+1\mathbb{Z} / p^{s+1} \mathbb{Z}, isto é, a sua ordem é (p1)ps(p-1)p^s em /ps+1\mathbb{Z} / p^{s+1} \mathbb{Z}, então a ordem de gg é (p1)ps+1(p-1)p^{s+1} em /p(s+1)+1\mathbb{Z} / p^{(s+1)+1} \mathbb{Z}, isto é, gg gera /p(s+1)+1\mathbb{Z} / p^{(s+1)+1} \mathbb{Z}.

Por indução, o primeiro passo o caso s=1s = 1 já demonstrado acima, obtemos que se gg gera /p2*\mathbb{Z} / p^2 \mathbb{Z}^*, então gera /ps*\mathbb{Z} / p^s \mathbb{Z}^* para todo ss. \quad q.e.d.

Teorema Chinês dos Restos Sejam nn e mm inteiros. Se nn e mm tem nenhum divisor comum, então a aplicação natural /nm/n×/m \mathbb{Z} / nm \mathbb{Z} \to \mathbb{Z} / n \mathbb{Z} \times \mathbb{Z} / m \mathbb{Z} dada por x(xmodn,xmodm)x \mapsto (x \mod n, x \mod m) é bijetora.

Demonstração:

Se x0modnx \equiv 0 \mod n e x0modmx \equiv 0 \mod m, então, como mm e nn têm nenhum divisor comum, x0modmnx \equiv 0 \mod m n; logo, a aplicação é injetora.

Seja (y,z)(y, z) em /n×/m\mathbb{Z} / n \mathbb{Z} \times \mathbb{Z} / m \mathbb{Z}. Como mm e nn têm nenhum divisor comum, existem, pelo Algoritmo de Euclides Estendido, inteiros aa e bb tais que am+bn=1a m + b n = 1. Logo, x=ay+bzx = a y + b z satisfaz xymodmx \equiv y \mod m e xzmodnx \equiv z \mod n. \quad q.e.d.

Corolário. O grupo /m\mathbb{Z} / m \mathbb{Z} é cíclico, isto é, gerado por um único elemento, se, e tão-somente se,

Demonstração: Pelo Teorema Chinês dos Restos, se m=p1e1p2enm = p_1^{e_1} \cdots p_2^{e_n} para primos p1p_1, …, pnp_n, então ϕ:/m/p1e1××/pnen \phi \colon \mathbb{Z} / m \mathbb{Z} \to \mathbb{Z} / p_1^{e_1} \mathbb{Z} \times \cdots \times \mathbb{Z} / p_n^{e_n} \mathbb{Z} é bijetora e respeita ++, isto é, f(x+y)=f(x)+f(y)f(x + y) = f(x) + f(y); logo respeita \cdot, isto é, f(xy)=f(x)f(y)f(x \cdot y) = f(x) \cdot f(y). Em particular, ϕ(1)=1\phi(1) = 1, e para todo aa em /m*\mathbb{Z} / m \mathbb{Z}^* existe bb com ab1modmab \equiv 1 \mod m se, e tão-somente se, existem b1b_1, …, bnb_n tais que ab11modp1e1a b_1 \equiv 1 \mod p_1^{e_1}, …, abn1modpnena b_n \equiv 1 \mod p_n^{e_n}. Consequentemente /m*/p1e1*××/pnen* \mathbb{Z} / m \mathbb{Z}^* \to \mathbb{Z} / p_1^{e_1} \mathbb{Z}^* \times \cdots \times \mathbb{Z} / p_n^{e_n} \mathbb{Z}^* é bijetora. Logo, como /pn\mathbb{Z} / p^n \mathbb{Z} é ciclico para um primo p>2p > 2, o produto é cíclico se, e tão-somente se, existe um único fator não-trivial.

Pequeno Teorema de Fermat

O Pequeno Teorema de Fermat é uma observação útil quanto à ciclicidade da multiplicação nos anéis finitos /p\mathbb{Z} /p \mathbb{Z} para pp um número primo:

Como (/p)*={1,...,p1}(\mathbb{Z} /p \mathbb{Z})^* = \{ 1, ..., p-1 \} é finito (de cardinalidade p1p-1), para qualquer número xx diferente de 00, necessariamente x0,x1,x2,...,xpx^0, x^1, x^2, ..., x^p terá uma repetição, xn=xn+mx^n = x^{n + m} para algum expoente nn e algum mp1m \leq p-1. Como em /p\mathbb{Z} /p \mathbb{Z} todo número exceto 00 é invertível, podemos dividir por xn1x^{n-1}; isto é, há mp1m \leq p-1 tal que 1=xm1 = x^m. Pelo Teorema de Lagrange, veremos que não somente mp1m \leq p-1, mas mais exatamente mp1m \mid p-1.

Este teorema nos servirá, por exemplo,

Observação. No entanto, não quer dizer que possivelmente já xm=1x^m = 1 para m<p1m < p-1. Com efeito, há muitos XX em /p\mathbb{Z} /p \mathbb{Z} para que isto vale: Para qualquer xx em /p\mathbb{Z} /p \mathbb{Z} e divisor dd de p1p-1, a potência X:=xdX := x^d satisfaz xm=1x^m = 1 já para m=(p1)/d<p1m = (p-1)/d < p-1. No mesmo tempo, acabamos de demonstrar que sempre há uma raiz primitiva, um gerador x0x_0 de /m*\mathbb{Z} /m \mathbb{Z}^*; isto é, necessariamente x0m1x_0^m \neq 1 para todo m<p1m < p-1.

Quanto à segurança criptográfica, o que pesa é o maior fator primo qq em p1p-1; por isso, os números primos queridos são da forma p=2q+1p = 2q + 1 com qq primo, os primos seguros. Para facilitar os cálculos (sem perda de segurança),

Juiz e Matemático leigo francês Pierre de Fermat (1655{}^\dagger 1655)

Teorema. (Pequeno Teorema de Fermat) Se pp é um número primo, então, para qualquer número inteiro aa,

Demonstração: Suponhamos que pap \mid a. Vale pap \mid a se, e tão-somente se, a=0\bar a = 0, e então ap1=ap1=0p1=0\bar{a^{p-1}} = {\bar a}^{p-1} = 0^{p-1} = 0 em /m\mathbb{Z} / m \mathbb{Z}.

Suponhamos que pap \nmid a. Como o grupo (/p)*(\mathbb{Z} / p \mathbb{Z})^* é finito, há nn e n+mn + m tais que an=an+m\bar a^n = \bar a^{n + m}. Como pp é primo, #(/p)*=p1\# (\mathbb{Z} / p \mathbb{Z})^* = p-1 pelo Corolário 7.1. Em particular, podemos dividir por todo número exceto 00, em particular, por aa, e obtemos am=1\bar a^m = 1 com mp1m \leq p-1. Pelo Teorema de Lagrange, mp1m \mid p-1, isto é, p1=mdp-1 = m d para um divisor dd. Logo ap1=amd=(am)d=1d=1\bar a^{p-1} = \bar a^{m d} = (\bar a^m)^d = 1^d = 1.

Corolário. Se pp é um número primo, então, para qualquer número inteiro aa vale apamodpa^p \equiv a \mod p.

Com efeito, o Corolário equivale ao Pequeno Teorema de Fermat, porque se pp é primo, então pode se dividir por qualquer número aa (diferente de zero) em /p\mathbb{Z} / p \mathbb{Z} (diz-se que /p\mathbb{Z} / p \mathbb{Z} é um corpo).

Para demonstrar o Teorema de Lagrange, precisamos da noção de um grupo:

Definição. Um grupo GG é um conjunto com uma operação binária :G×GG\cdot \colon G \times G \to G tal que

Teorema. (Lagrange) Seja GG um grupo. Se HH é um subgrupo de GG, então #H#G\# H \mid \# G.

Demonstração: Define a relação \sim sobre GG por ggg' \sim g'' se há hh em HH tal que g=hgg'' = h g'. Como HH é um grupo, ela é transitiva e uma relação de equivalência. Logo GG é a união disjunta de classes de equivalência.

Seja gg em uma tal classe de equivalência CC. Por definição de \sim, a aplicação g:HCg \colon H \to C é sobrejetora. Como gg é invertível (por g1g^{-1}), ela é injetora, então uma bijeção.

Concluímos que todas as classes de equivalência têm cardinalidade #H\# H e, pela união disjunta, que #H#G\# H \mid \# G.

7.3 Detectar Primos

Recordemo-nos do Teorema de Euclides que asserta que haja números primos arbitrariamente grandes (por exemplo, com 2048\geq 2048 dígitos binários para o RSA):

Teorema de Euclides. Existe uma infinitude de números primos.

Demonstração: Suponhamos o contrário, que haja só um número finito p1,...,pnp_1, ..., p_n de números primos. Considere q=p1...pn+1. q = p_1 ... p_n + 1. Como qq é maior que p1p_1, …, pnp_n, não é primo. Seja então pp um número primo que divida qq. Pela hipótese, pp em {p1,...,pn}\{p_1, ..., p_n\}. Mas por definição qq tem resto 11 divido por qualquer p1p_1, …, pnp_n.

Contradição! Logo, não existe um maior número primo. \quad q.e.d.

Exemplos de Grandes Números Primos

Marin Mersenne (Oizé, 1588 — Paris, 1648) foi um padre mínimo francês que tentou encontrar, sem êxito, uma fórmula para todos os números primos. Motivada por uma carta de Fermat em que lhe sugeriu que todos os números 22p+12^{2^p}+1, os Números de Fermat fossem primos, Mersenne estudou os números 2p1 para p primo . 2^p-1 \quad \text{ para $p$ primo }. Em 1644 publicou o trabalho Cogita physico-mathematica que afirma que estes são primos para p=2,3,5,7,13,17,19,31 e 127. p = 2,3,5,7,13,17,19,31 \text{ e } 127. (e erroneamente incluiu p=63p = 63 e p=257p = 257). Só um computador conseguiu mostrar em 19321932 que 225712^{257} - 1 é composto.

Os números primos de Mersenne, da forma 2p12^p-1 para pp primo, conhecidos são

22, 33, 55, 77, 1313, 1717, 1919, 3131, 6161, 8989, 107107, 127127, 521521, 607607, 12791279, 22032203, 22812281, 32173217, 42534253, 44234423, 96899689, 99419941, 1121311213, 1993719937, 2170121701, 2320923209, 4449744497, 8624386243, 110503110503, 132049132049, 216091216091, 756839756839, 859433859433, 12577871257787, 13982691398269, 29762212976221, 30213773021377, 69725936972593, 1346691713466917, 2099601120996011, 2403658324036583, 2596495125964951, 3040245730402457, 3258265732582657, 3715666737156667, 4264380142643801, 4311260943112609, 5788516157885161, 7420728174207281, 7723291777232917 e 8258993382589933

O número primo 2825899331 2^{82\,589\,933} - 1 tem 2486204824\,862\,048 algarismos. Foi encontrado no dia 8 de dezembro 2018 e é até hoje o maior número primo conhecido.

O CrypTool 1, na entrada do menu Indiv. Procedures -> Number Theory Interactive -> Compute Mersenne Numbers permite calcular uns números primos de Mersenne.

Testes

Um teste rápido se o número natural nn é composto é o Pequeno Teorema de Fermat (formulado pela sua contra-posição): Se há um número natural aa tal que anamodn a^n \nequiv a \mod n então nn é composto.

Mas a implicação inversa, isto é, se nn é primo, então há um número natural aa tal que anamodna^n \nequiv a \mod n, não vale: Há números nn (que se chamam Números de Carmichael) que são compostos mas, para todo número natural aa, anamodn. a^n \equiv a \mod n. O menor tal número nn é 561561 (que é divisível por 33).

O crivo de Eratóstenes

O algoritmo mais simples para verificar se um número é primo ou não é o crivo de Eratóstenes (285 – 194 a.C.).

Eratóstenes, o terceiro bibliotecário-chefe da Biblioteca de Alexandria

Para exemplificá-lo, vamos determinar os números primos entre 11 e 3030.

Inicialmente, determina-se o maior número pelo que dividiremos para verificar se o número é composto; é a raiz quadrada da cota superior arredondada para baixo. No caso, a raiz de 3030, arredondada para baixo, é 55.

  1. Crie uma lista de todos os números inteiros de 2 até o valor da cota: 22, 33, 44, 55, 66, 77, 88, 99, 1010, 1111, 1212, 1313, 1414, 1515, 1616, 1717, 1818, 1919, 2020, 2121, 2222, 2323, 2424, 2525, 2626, 2727, 2828, 2929 e 3030.
  2. Encontre o primeiro número da lista. Ele é um número primo, 22.
  3. Remova da lista todos os múltiplos de 22 até 3030: 22, 33, 55, 77, 99, 1111, 1313, 1515, 1717, 1919, 2121, 2323, 2525, 2727 e 2929.

O próximo número da lista é primo. Repita o procedimento:

Conforme determinado inicialmente, 55 é o último número pelo qual dividimos. A lista final 2,3,5,7,11,13,17,19,23,292,3,5,7,11,13,17,19,23,29 contém só números primos.

Segue uma implementação em Python:

def primeSieve(sieveSize):
    # Returns a list of prime numbers calculated using
    # the Sieve of Eratosthenes algorithm.

    sieve = [True] * sieveSize
    sieve[0] = False # zero and one are not prime numbers
    sieve[1] = False
    # create the sieve
    for i in range(2, int(math.sqrt(sieveSize)) + 1):
        pointer = i * 2
        while pointer < sieveSize:
            sieve[pointer] = False
            pointer += i
    # compile the list of primes
    primes = []
    for i in range(sieveSize):
        if sieve[i] == True:
            primes.append(i)
    return primes

O Teste Determinista AKS

O teste de AKS determina em tempo polinomial se nn é composto ou primo (mais exatamente, em tempo 𝑂(d)6\textit{O}(d)^6 onde dd = o número de dígitos dd [binários] de nn). Na prática, basta normalmente o Teste de Miller-Rabin probabilista que garante muito mais testemunhas (= números aa que provam se nn é composto ou não) do que o Pequeno Teorema de Fermat.

Com efeito, quando comparamos a duração entre os dois algoritmos para verificar se um número é primo num computador com um processador Intel Pentium-4 de 2 GHz, obtemos

número primo Miller-Rabin AKS
73097309 0.010.01 12.3412.34
90040979004097 0.010.01 23:22.5523:22.55
23112^31-1 0.010.01 6:03:14.366:03:14.36

O CrypTool 1 oferece no Menu Individual Procedures -> RSA uma entrada para experimentar com diferentes algoritmos para detectar números primos.

Os algoritmos para verificar se um número é primo no CrypTool 1

O Teste Probabilista Miller-Rabin

Os testes simplistas, para saber se um número nn é primo ou não, são ineficientes porque calculam os fatores de nn. Em vez deles, para saber apenas se é primo ou não, há o Teste de Miller-Rabin. Após a sua demonstração, damos a sua contraposição; é nesta formulação que é aplicado.

O Teste de Miller-Rabin. Seja p>2p > 2 um número primo, seja n1=2kqn-1 = 2^k q para números kk e qq (com qq ímpar). Então, para qualquer número inteiro aa indivisível por pp vale

Demonstração: Pelo Pequeno Teorema de Fermat ap1=(ad)2k1modp a^{p-1} = (a^d)^{2^k} \equiv 1 \mod p Extraindo iterativamente a raiz quadrada, obtemos

Se para um número ímpar, um número possivelmente primo, escrevemos n1=2kqn-1 = 2^k q, então pelo Teste de Fermat nn não é primo se existe um inteiro aa tal que a2kq1modna^{2^k q} \nequiv 1 \mod n. O Teste de Miller-Rabin explicita a condição aq2k=(aq)2k=((aq)2))21a^{q 2^k} = (a^q)^{2^k} = ((a^q)^2) \cdots)^2 \nequiv 1:

O Teste de Miller-Rabin. (Contraposição) Seja nn ímpar e n1=2kqn-1 = 2^k q para números kk e qq (com qq ímpar). Um inteiro aa relativamente primo a nn é uma Testemunha de Miller-Rabin (para a divisibilidade) de nn, se

Questão: Quais as chances que declaramos pelo Teste de Miller-Rabin acidentalmente um número primo, isto é, um número que é na verdade composto?

Teorema. (Sobre a frequência das testemunhas) Seja nn ímpar e composto. Então pelo menos 75%75 \% dos números em {1,...,n1}\{ 1, ..., n-1 \} são Testemunhas de Miller-Rabin para nn.

Logo, já depois de 55 tentativas a1a_1, a2a_2, …, a5a_5 sem testemunha sabemos com uma chance 1/45=1/1024<0,1%1/4^5 = 1/1024 < 0,1 \%, que o número é primo!

Implementação em Python

Vamos implementar

  1. o algoritmo de Miller-Rabin,
  2. um teste para um número primo, e
  3. uma função para gerar números primos (grandes).
# Primality Testing with the Rabin-Miller Algorithm
# http://inventwithpython.com/hacking (BSD Licensed)

import random


def rabinMiller(num):
    # Returns True if num is a prime number.

    s = num - 1
    t = 0
    while s % 2 == 0:
        # keep halving s while it is even (and use t
        # to count how many times we halve s)
        s = s // 2
        t += 1

    for trials in range(5): # try to falsify num's primality 5 times
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1: # this test does not apply if v is 1.
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True
def isPrime(num):
    # Return True if num is a prime number. This function does a
    # quicker prime number check before calling rabinMiller().

    if (num < 2):
        return False # 0, 1, and negative numbers are not prime

    # About 1/3 of the time we can quickly determine if num is not
    # prime  by dividing by the first few dozen prime numbers.
    # This is quicker # than rabinMiller(), but unlike rabinMiller()
    # is not guaranteed to prove that a number is prime.
    lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
    47, 59,  61,  67,  71,  73,  79,  83,  89,  97,  101, 103, 107,
    109, 113, 127, 131, 137, 149, 151, 157, 163, 167, 173, 179, 181,
    191, 193, 197, 199, 211, 223, 227, 233, 239, 241, 251, 257, 263,
    269, 271, 277, 281, 283, 293, 307, 311, 313, 331, 337, 347, 349,
    353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 431, 433,
    439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
    523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
    613, 617, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
    701, 709, 719, 727, 739, 743, 751, 757, 761, 769, 773, 787, 797,
    809, 811, 821, 823, 827, 829, 853, 857, 859, 863, 877, 881, 883,
    887, 907, 911, 919, 929, 937, 941, 947, 967, 971, 977, 983, 991,
    997]

    if num in lowPrimes:
        return True

    # See if any of the low prime numbers can divide num
    for prime in lowPrimes:
        if (num % prime == 0):
            return False

    # If all else fails, call rabinMiller() to check if num is a prime.
    return rabinMiller(num)
def generateLargePrime(keysize = 1024):
    # Return a random prime number of keysize bits in size.
    while True:
        num = random.randrange(2**(keysize-1), 2**(keysize))
        if isPrime(num):
            return num

8 Algoritmos Assimétricos Clássicos

Apresentamos

  1. o algoritmo RSA que se baseia na dificuldade de computar a fatoração em números primos, e
  2. dois algoritmos que se baseiam nãoo protocolo de Diffie-Hellman (para construir uma chave secreta mútua através de um canal inseguro),
    1. ElGamal e
    2. ECC, criptografia com curvas elípticas

Ambos os algoritmos do tipo Diffie-Hellman, os algoritmosElGamal e ECC criam (em contraste ao RSA) uma chave efêmera para cada cifração e assinatura. É importante que esta chave seja imprevisível; caso contrário, esta informação permite a deduzir a chave privada. (Por exemplo, um aplicativo Bit Coin sob Android teve esta falha.)

Isto é, é preciso garantir que haja suficientemente entropia (isto é, desordem no sistema) na criação desta chave efêmera, usando como parâmetros particulares

8.1 O Algoritmo RSA

Apresentamos o algoritmo RSA de Rivest, Shamir, e Adleman (1978) que cria

Em comparação ao protocolo de Diffie-Hellman, ele tem a vantagem que é completamente assimétrico:

As chaves para cifrar e decifrar serão construídas via a Fórmula de Euler que por seu turno se baseia no Pequeno Teorema de Fermat.

Fórmula de Euler

Pequeno Teorema de Fermat. Se pp é um número primo, então, para qualquer número inteiro aa,

Em particular, ap=a(p1)+1=ap1a=aa^p = a^{(p-1)+1} = a^{p-1} a = a para todo inteiro aa. Se pap \nmid a, então

Isto é, se o expoente m1modp1m \equiv 1 \mod p-1, então amamodpa^m \equiv a \mod p.

Em particular, se m=Edm = Ed, isto é, EE e dd são tais que Ed1modp1Ed \equiv 1 \mod p-1, em outras palavras, d1/Emodp1d \equiv 1/E \mod p-1 então aEd=(aE)damodp, a^{Ed} = (a^E)^d \equiv a \mod p, isto é, ad=a1/E=aE! a^{d} = a^{1/E} = \sqrt[E]{a}! Isto é, a computação da EE-ésima raiz E\sqrt[E]{\cdot} iguala à da dd-ésima potência d\cdot^d, um grande atalho computacional!

Exemplo. Por exemplo, para p=5p = 5, E=3E = 3 e d=3d=3 temos p1=4p-1 = 4 e Ed=91mod5Ed = 9 \equiv 1 \mod 5. Por exemplo, para a=2a=2 vale 23=83mod5 e 33=272mod5 2^3 = 8 \equiv 3 \mod 5 \quad \text{ e } \quad 3^3 = 27 \equiv 2 \mod 5

O Matemático suíço Leonhard Euler (1707170717831783)

Esta computação de E\sqrt[E]{\cdot} por d\cdot^d é o atalho do RSA. Porém, para ser secreto, precisamos dificultar a computação de dd a partir de EE. Dado pp e EE, o número dd tal que Ed1modp1Ed \equiv 1 \mod p-1 é diretamente calculado pelo algoritmo de Euclides.

No RSA, ao invés de um singelo primo pp, usamos um produto N=pqN = pq de dois números primos diferentes pp e qq que serão desconhecidos, cujo conhecimento é porém necessário (e dificílimo) para calcular dd! Veremos primeiro como adaptar o Pequeno Teorema de Fermat, para um módulo pp ao módulo N=pqN = pq, a Fórmula de Euler:

Teorema. (Fórmula de Euler) Sejam pp e qq números primos diferentes. Se aa é divisível nem por pp, nem por qq, então a(p1)(q1)1modpq. a^{(p-1)(q-1)} \equiv 1 \mod pq.

Demonstração: Pelo pequeno teorema de Fermat, a(p1)(q1)=(ap1)q11q1=1modp a^{(p-1)(q-1)} = (a^{p-1})^{q-1} \equiv 1^{q-1} = 1 \mod p e a(q1)(p1)=(aq1)p11p1=1modq a^{(q-1)(p-1)} = (a^{q-1})^{p-1} \equiv 1^{p-1} = 1 \mod q isto é, pp e qq dividem a(p1)(q1)1a^{(p-1)(q-1)} - 1. Como pp e qq são primos diferentes, pqpq divide a(p1)(q1)1a^{(p-1)(q-1)} - 1, isto é, a(p1)(q1)1modpqa^{(p-1)(q-1)} \equiv 1 \mod pq.

Para números primos diferentes pp e qq, denote N:=pq e ϕ(N):=(p1)(q1). N := pq \quad \text{ e } \quad \phi(N) := (p-1)(q-1).

Observação. Recordemo-nos de que a função totem de Euler ϕ\phi de Seção 7.2 que conta o número de unidades em /N\mathbb{Z} /N \mathbb{Z}. Verifica-se que Φ(N)=(p1)(q1)\Phi(N) = (p-1)(q-1).

Pela Fórmula de Euler aϕ(N)1modNa^{\phi(N)} \equiv 1 \mod N. Logo, como para o módulo p1p-1 em vez de ϕ(N)\phi(N),

e geralmente:

Corolário. (Radiciação modN\mod N) Sejam pp e qq números primos diferentes. Para qualquer expoente nn tal que n1modϕ(N) n \equiv 1 \mod \phi(N) vale anamodN para todo inteiro a. a^n \equiv a \mod N \quad \text{ para todo inteiro } a.

Demonstração: Como n1mod(p1)(q1)n \equiv 1 \mod (p-1)(q-1), isto é, há ν\nu tal que n1=ν(p1)(q1)n-1 = \nu (p-1)(q-1), vale pela Fórmula de Euler, an=aν(p1)(q1)+1=(a(p1)(q1))νa1νa=amodN. a^n = a^{\nu (p-1)(q-1) + 1} = (a^{(p-1)(q-1)})^\nu \cdot a \equiv 1^\nu \cdot a = a \mod N.

Observação (crucial para o algoritmo RSA). Se m1modϕ(N)m \equiv 1 \mod \phi(N), então pela Fórmula de Euler amamodNa^m \equiv a \mod N, isto é, a potenciação é a identidade, midmodN \cdot^m \equiv \textrm{id} \mod N Em particular, se m=Edm = Ed é o produto de dois números inteiros EE e dd, isto é, Ed1modϕ(N), Ed \equiv 1 \mod \phi(N), então a=am=aEd=(aE)d. a = a^m = a^{Ed} = (a^E)^d. Isto é, a potenciação d=1/E\cdot^d = \cdot^{1/E} inverte E\cdot^E módulo NN, a extração da EE-ésima radiciação é a dd-ésima potência, E=1/Ed