Criptografia e Seguranca

Paulo J. Almeida

Departamento de Matematica da Universidade de Aveiro

18 de Julho de 2012

Conteudo

1 Preliminares 41.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Vocabulario . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Complexidade 122.1 Estimativas de tempo . . . . . . . . . . . . . . . . . . . . . . . 122.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Criptografia Simetrica 183.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Cifra de Substituicao . . . . . . . . . . . . . . . . . . . . . . . 193.3 Criptoanalise classica . . . . . . . . . . . . . . . . . . . . . . . 203.4 Criptoanalise da Cifra de Substituicao . . . . . . . . . . . . . 223.5 Cifra de Deslocamento . . . . . . . . . . . . . . . . . . . . . . 253.6 Algoritmo de Euclides e inversos mod n . . . . . . . . . . . . 263.7 Cifra Afim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.8 Funcao φ de Euler . . . . . . . . . . . . . . . . . . . . . . . . 333.9 Criptoanalise da Cifra Afim . . . . . . . . . . . . . . . . . . . 343.10 Cifra de Vigenere . . . . . . . . . . . . . . . . . . . . . . . . . 363.11 Criptoanalise da cifra de Vigenere . . . . . . . . . . . . . . . . 373.12 Cifra de Hill . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.13 Ataque a cifra de Hill . . . . . . . . . . . . . . . . . . . . . . . 433.14 Cifra de Permutacao . . . . . . . . . . . . . . . . . . . . . . . 433.15 Cifras de Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . 443.16 Cifra de Fluxo baseada no LFSR . . . . . . . . . . . . . . . . 453.17 Criptoanalise da cifra de fluxo baseada no LFSR . . . . . . . . 46

1

4 Criptografia de chave publica 494.1 Teorema Chines dos Restos . . . . . . . . . . . . . . . . . . . 494.2 Lagrange, Euler e Fermat . . . . . . . . . . . . . . . . . . . . 534.3 Raızes primitivas . . . . . . . . . . . . . . . . . . . . . . . . . 534.4 Exponenciacao modular rapida . . . . . . . . . . . . . . . . . 544.5 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.5.1 Ataque do expoente publico pequeno . . . . . . . . . . 564.6 Resıduos quadraticos . . . . . . . . . . . . . . . . . . . . . . . 574.7 Algoritmo de Tonelli-Shanks . . . . . . . . . . . . . . . . . . . 654.8 Cifra de Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . 664.9 Protocolo Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . 69

4.9.1 Ataque do homem no meio . . . . . . . . . . . . . . . . 704.10 Sistema ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.10.1 Ataque da repeticao da chave efemera . . . . . . . . . . 724.11 Sistema Merkle-Hellman . . . . . . . . . . . . . . . . . . . . . 72

5 Primalidade 755.1 Teste de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 765.2 Teste de Miller-Rabin . . . . . . . . . . . . . . . . . . . . . . . 775.3 Teste de Solovay-Strassen . . . . . . . . . . . . . . . . . . . . 795.4 Teste n− 1 de Lucas . . . . . . . . . . . . . . . . . . . . . . . 80

6 Factorizacao 826.1 Metodo p− 1 de Pollard . . . . . . . . . . . . . . . . . . . . . 826.2 Metodo ro de Pollard . . . . . . . . . . . . . . . . . . . . . . . 836.3 Factorizacao de Fermat . . . . . . . . . . . . . . . . . . . . . . 856.4 Crivo quadratico . . . . . . . . . . . . . . . . . . . . . . . . . 90

7 Logaritmo Discreto 947.1 Enumeracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947.2 Algoritmo passos de bebe passos de gigante . . . . . . . . . . . 957.3 Calculo de ındices . . . . . . . . . . . . . . . . . . . . . . . . . 96

8 Assinaturas digitais 998.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 998.2 Assinatura RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 1008.3 Assinatura ElGamal . . . . . . . . . . . . . . . . . . . . . . . 101

8.3.1 Forjar assinaturas ElGamal . . . . . . . . . . . . . . . 102

2

8.3.2 Falhas de protocolo . . . . . . . . . . . . . . . . . . . . 1048.4 DSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

9 Funcoes de sıntese 1099.1 Ataque do Aniversario . . . . . . . . . . . . . . . . . . . . . . 1109.2 Funcoes de sıntese comprovadamente seguras . . . . . . . . . . 111

9.2.1 Funcao de sıntese Chaum-van Heijst-Pfitzmann . . . . 1139.2.2 VSH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

3

Capıtulo 1

Preliminares

1.1 Introducao

Alice deseja enviar uma mensagem a Bob sem que Olga a perceba, no casodesta interceptar a mensagem. Com este objectivo, Alice pode cifrar amensagem antes de a enviar a Bob. Bob recebe a mensagem e decifra-a.Critografia e a ciencia que estuda estas duas accoes. Se Carla interceptaa mensagem cifrada, pode tentar quebrar a cifra e ler a mensagem. Crip-toanalise e a ciencia em que se estuda metodos ou processos para quebrarcifras. Criptologia engloba tanto a Criptografia como a Criptoanalise.

Durante este curso iremos aprender varios sistemas criptograficos, al-guns dos quais sao correntemente usados nas diversas comunicacoes de men-sagens (militares, espionagem, numeros de PIN, conversacoes telefonicas,transaccoes bancarias, Internet, e-mail, etc.). Ao mesmo tempo, Estudare-mos metodos para quebrar certos cifras e a razao pela qual alguns dos sis-temas criptograficos sao considerados inquebraveis. Iremos tambem estudarfuncoes de sıntese (que sao uma especie de impressao digital), assinaturase identificacao digital e diversos protocolos de seguranca. As ferramentasessenciais deste curso serao Teoria dos Numeros e algumas nocoes de Algebra.

1.2 Vocabulario

Mensagem original (ou texto plano) - Mensagem que se pretende tornar se-creta, por exemplo OLA;

Mensagem cifrada - A mensagem secreta que se obtem apos ter sido

4

cifrada, por exemplo ROD (usando o sistema criptografico utilizado por JulioCesar);

Emissor - Quem envia a mensagem;Receptor - Quem recebe a mensagem;Cifrar - Transformar a mensagem original numa mensagem cifrada;Decifrar - Transformar a mensagem cifrada na mensagem original;Cifra - Conjunto de procedimentos e conjunto de sımbolos (letras, nomes,

sinais, etc) usados para cifrar uma mensagem;Codificacao simples - Transformar a mensagem original em numeros ou

bits1. Por exemplo, se fizermos a transformacao 2 → 0, A→ 1, ..., Z→ 26entao a palavra OLA passava a 15 12 1. Usualmente utiliza-se o codigoASCII, que representa cada sımbolo por 8 bits (byte): A→ 01000001, B→01000010, a→ 01100001, 0 → 00110000, ? → 00111111, etc;

Descodificar - Transformar numeros ou bits em mensagens;Monogramica (ou monografica) - Uma cifra que traduz um a um os

sımbolos do texto original em texto cifrado;Poligramica (ou poligrafica - Uma cifra que traduz varios sımbolos do

texto original, em grupo e ao mesmo tempo, em texto cifrado;Cifra de transposicao ou permutacao - Uma cifra que re-arranja e/ou

permuta as letras, sımbolos ou bits do texto plano;Cifra de substituicao - Uma cifra que substitui letras, sımbolos ou bits

por outros sem lhes alterar a ordem;Sistema criptografico - Conjunto de procedimentos para cifrar e decifrar

uma mensagem;Chave - Num sistema criptografico, corresponde a um nome, uma palavra,

uma frase, etc, que permite cifrar ou decifrar uma mensagem.Sistema criptografico de chave simetrica - Necessita de uma chave secreta

partilhada pelo emissor e pelo receptor. O emissor e o receptor tem queconcordar com uma chave antes do inıcio da transmissao da mensagem;

Sistema criptografico de chave publica - Cada utilizador tem uma chavepara cifrar que e publica e foi publicada e uma chave para decifrar que esecreta (normalmente so utilizadores autorizados tem a chave secreta);

Assinatura - Processo pelo qual o emissor pode certificar o receptor da suaidentidade. Nos sistemas de chave publica este processo evita que utilizadoresinimigos enviem mensagens enganosas;

1bits e o plural de bit - binary digit

5

Criptoanalise - E o processo pelo qual o inimigo (quem nao esta autorizadoa decifrar a mensagem) tenta transformar a mensagem cifrada na mensagemoriginal.

Os processos para cifrar e decifrar devem ser faceis de aplicar para osutilizadores autorizados mas deve ser difıcil um inimigo ou utilizador naoautorizado decifrar as mensagens. Teoria dos numeros e uma excelente fontede problemas com alguns mecanismos faceis e alguns mecanismos difıceis,portanto aparenta ser uma optima area para ser usada em criptologia.

1.3 Historia

A historia da criptografia aparenta ter sido iniciada no antigo Egipto, cercade 1900 a.C. pelo arquitecto Khnumhotep II, na tempo do farao AmenemhetII. O escriba de Khnumhotep II substituiu alguns trechos e palavras de docu-mentos importantes por sımbolos estranhos de modo a dificultar que ladroeschegassem a tesouros reportados nesses documentos.

Alguns seculos mais tarde aparecem outros metodos de transmitir men-sagens de modo secreto, por exemplo na Mesopotamia, Assıria, China, Indiae Egipto. Exemplos desses metodos sao:

Tatuagens com mensagens na cabeca de escravos. Infelizmenteera preciso esperar o cabelo crescer antes de ”enviar”a mensagem.A decifracao era feita no barbeiro;

Marcas na madeira de placas de cera. As marcas eram escondidascom cera nova. Para decifrar, bastava derreter a cera;

Mensagens dentro do estomago de animais de caca.

Este tipo de ocultacao de mensagens toma o nome de esteganografia edistingue-se da criptografia porque neste caso a mensagem nao e alterada ebaseia-se no facto de um interceptor nao saber da existencia da mensagem.Quando se utiliza criptografia, sabe-se que esta a ser enviada uma mensagem,mas o seu sentido e obscuro. Como exemplos modernos de esteganografia,temos a ocultacao de mensagens em imagens digitais, atraves da alteracao dealguns bits em cada componente da cor e marcas ocultas nas notas bancarias

6

para evitar a sua falsificacao. Apesar da sua aparente semelhanca com crip-tografia, os metodos de esteganografia sao muito distintos dos utilizados emcriptografia e nao serao estudados durante este curso.

Cerca de 600 a.C., os hebreus criaram alguns sistemas criptograficosaquando da escrita do livro de Jeremias, nomeadamente o Atbash, que con-siste de uma troca simples entre as letras do hebraico, por ordem inversa.

O primeiro sistema criptografico de uso militar tera sido o Scytale ouBastiao de Licurgo, utilizado pelo general espartano Pasanius, em 475 a.C..O scytale consiste em escrever a mensagem numa tira estreita de couro oupergaminho quando esta esta enrolada em torno de um bastiao de madeira.A mensagem original e escrita no sentido do comprimento do bastiao e, por-tanto, quando a tira e desenrolada obtem-se a mensagem cifrada. Para voltara obter a mensagem original, deve-se enrolar outra vez a tira num bastiaocom o mesmo perımetro e forma. Este e um exemplo de uma cifra de trans-posicao. Esta e ainda a ideia de muitas tecnicas populares actuais.

Na India, por volta de 300 a. C., apareceu um livro intitulado Artha-sastra, atribuıdo a Kautilya, onde sao referidos os primeiros metodos decriptoanalise. Estes processos sao recomendados para diplomatas. O famosoKama Sutra de Vatsayana, menciona a criptografia nas artes (yogas) 44 e45, de entre a sua lista de 64 artes e ciencias que todos devem saber (Part I,capıtulo 3, http://www.sacred-texts.com/sex/kama/index.htm).

Julio Cesar utilizou uma cifra que consistia em substituir cada letra pelaletra que se encontra tres posicoes depois no alfabeto. Este e um exemplo deuma cifra de deslocamento.

No seculo VIII, al-Khalil, escreveu o livro Kitab al Mu’amma (que signi-fica ”O livro das mensagens criptograficas”). Infelizmente este livro desa-pareceu. al-Khalil decifrou um criptograma bizantino antigo quando supos,correctamente, que o inıcio do criptograma era ”Em nome de Deus”. Estemetodo, conhecido como o metodo da palavra provavel, foi usado para aju-dar a decifrar mensagens cifradas pelo Enigma, durante a Segunda GuerraMundial. Cerca de 100 anos depois, al-Kindi, escreveu um outro livro sobrecriptografia, ainda existente, intitulado Risalah fi Istikhraj al Mu’amma (Es-critos sobre a decifracao de mensagens criptograficas). al-Kindi considerouanalises estatısticas para quebrar cifras, processo ainda usado na actualidade.

Em 1466, Leon Battista Alberti, escreveu um ensaio, no qual mencionauma cifra em disco, criando a nocao de cifra poli-alfabetica.

Giovan Batista Belaso inventou, em 1553, um sistema criptografico poli-alfabetico a que actualmente se chama cifra de Vigenere, por ter sido fal-

7

samente atribuıdo a Blaise de Vigenere durante o seculo XIX. Este sistematem uma chave e uma serie de diferentes cifras de Cesar e foi consideradoindecifravel durante muito tempo, porem e facilmente quebrado utilizandoanalise estatıstica. Em 1585, Vigenere criou a nocao de auto-chave, processoainda hoje utilizado, por exemplo no sistema DES.

Durante os seculos XVIII e XIX, assistiu-se a proliferacao de CamerasEscuras, gabinetes de espionagem, onde se utilizava a criptologia para finsmilitares e fins civis, nomeadamente para decifrar mensagens diplomaticas.Em Viena, e criada uma das mais eficientes cameras escuras, onde se de-cifrava cerca de 100 mensagens diplomaticas internacionais, por dia. Franca,Inglaterra e Alemanha tambem criam os seus centros de criptoanalise, tendoempregado diversos matematicos famosos.

Durante a Primeira Guerra Mundial assiste-se a uma proliferacao de sis-temas criptograficos para usos militares. Como exemplos, temos o Playfair eo ADFGVX.

A cifra inglesa Playfair (guerra dos Boers e Primeira Guerra Mundial)consiste em escrever a palavra chave (que nao pode ter letras repetidas)seguida das restantes letras num quadrado cinco por cinco. Se considerarmosa palavra chave Palmerston, obtemos

P A L M ER S T O NB C D F GH IJ K Q UV W X Y Z

Para cifrar um par de letras, forma-se um rectangulo do qual as letras saovertices. A mensagem cifrada consiste dos outros dois vertices. Por exemplo,PI e cifrado em AH. Se duas letras estao na mesma linha (resp. mesmacoluna), toma-se as letras seguintes, e. g. EU e cifrado em NZ e ME fica EP.Se a mensagem original tiver duas letras iguais consecutivas, coloca-se um Xa separa-las, e. g. a mensagem ASSIM passa a ser AS XS IM.

A cifra alema ADFGVX (Primeira Guerra Mundial), utiliza uma tabelafixa para efectuar uma substituicao da mensagem original. Cada letra etransformada no par de letras correspondente a linha e coluna onde a letraoriginal esta.

8

A D F G V XA K Z W R 1 FD 9 B 6 C L 5F K 7 J P G XG E V Y 3 A NV 8 O D H 0 2X U 4 I S T M

Assim, ACHTUNG e primeiro cifrado em GV DG VG XV XA GX FV.Esta e a parte da substituicao da cifra.

Em seguida, efectua-se um deslocamento, utilizando uma chave sem le-tras repetidas, neste caso a chave e DEUTSCH. Constroi-se uma tabela emque, na primeira linha esta a palavra chave, na segunda linha o numeral cor-respondente a ordem alfabetica de cada letra da primeira linha e, nas linhasseguintes e escrita a mensagem que resultou do processo de substituicao efec-tuado anteriormente. A mensagem cifrada e obtida, escrevendo as letras dascolunas seguindo a ordem indicada na segunda linha.

D E U T S C H2 3 7 6 5 1 4G V D G V G XV X A G X F V

No nosso exemplo, a mensagem cifrada correspondente a mensagem ori-ginal ACHTUNG e GF GV VX XV VX GG DA.

A grande fraqueza da cifra ADFGVX e usar uma tabela fixa para a parteda substituicao. A alternancia entre substituicoes e deslocacoes permite obtercifras bastante seguras, sendo este processo a base do DES (Data EncryptionStandard) e do AES (Advanced Encryption Standard).

Apos esta guerra comecam a aparecer as primeiras maquinas cifrantes queusam rotores mecanicos. Em 1923, Arthur Scherbius, desenvolve o ENIGMA,talvez a mais famosa maquina cifrante. O ENIGMA e utilizado pelos alemaesdurante a Segunda Guerra Mundial para comunicacoes com os submarinose para deslocar as suas tropas. O ataque criptoanalıtico ao ENIGMA foiiniciado pelo matematico polaco Marian Rejewski (juntamente com JerzyRozycki e Henryk Zygalski), que apos a Polonia ter sido invadida conseguiupassar a sua informacao para Franca. Esta informacao acabou por chegara Inglaterra, onde Turing e o seu grupo de criptoanalıticos trabalhavam.Estes conseguiram decifrar o ENIGMA o que permitiu descobrir planos mil-

9

itares dos alemaes e o envio mensagens enganosas para os alemaes localizadosem Franca, conseguindo assim facilitar a invasao por Dunquerque. Japaotinha a Maquina Purpura, cujo sistema foi quebrado por equipa lideradapor William Frederick Friedman (criador da palavra criptoanalise). O sis-tema criptografico utilizado pelos EUA durante Segunda Guerra Mundial,encontra-se ainda classificado.

Nos anos 60, o Dr. Horst Feistel, liderando um projecto de pesquisa noIBMWatson Research Lab, desenvolve a cifra Lucifer. Em 1974, a IBM apre-senta Lucifer ao NBS (National Bureau of Standards), o qual, apos algumasalteracoes, adopta esta cifra como cifra padrao nos EUA, criando assim oDES (Data Encryption Standard). Este sistema foi criticado desde o inıciopor varios investigadores e acabou por ser quebrado, usando forca bruta, em1997.

Whitfield Diffie e Martin Hellman publicam, em 1976, o artigo ”New Di-rections in Cryptography”, onde introduzem a ideia de criptografia de chavepublica, neste caso baseada no problema do logaritmo discreto, e avancamcom a ideia de autenticacao utilizando funcoes de um so sentido (one wayfunctions). Inspirados por aquele artigo, Ronald L. Rivest, Adi Shamir eLeonard M. Adleman, desenvolvem uma cifra de chave publica, que tambempode ser usada para assinaturas digitais, baseada no contraste entre a difi-culdade de factorizar numeros grandes e a relativa facilidade de identificarnumeros primos grandes. Este sistema passou a ser conhecido como RSAe foi patenteado. Em 1984, Taher Elgamal desenvolve o sistema ElGamaltambem utilizando o problema do logaritmo discreto.

Nos anos 90 aparecem diversos sistemas criptograficos em particular oIDEA (International Data Encryption Algorithm) de Xuejia Lai e JamesMassey, que pretende ser um substituto do DES. A criptografia quantica eintroduzida em 1990. O PGP (Pretty Good Privacy) de Phil Zimmermann,desenvolvido em 1991, ainda e um dos programas mais utilizados para pro-teger a privacidade do e-mail e dos arquivos guardados no computador doutilizador. Nas versoes mais recentes do PGP, e utilizado o sistema ElGamal.Em 1997, o NIST solicitou propostas para a substituicao do DES. Em 2000, oNIST escolheu o Rijndael (de entre os finalistas estava MARS da IBM, RC6de RSA Laboratories, Rijndael de Joan Daemen e Vincent Rijmen, Serpentde Anderson, Biham e Knudsen, e o twofish de Bruce Schneier e sua equipa),para ser o novo AES (Advanced Encryption Standard). So em 2005 e queo NIST (National Institute of Standards and Technology), que substituiu oNBS, publica um plano de transicao com a duracao de dois anos, para que as

10

agencias governamentais deixassem de utilizar o DES e passassem a utilizaro AES.

11

Capıtulo 2

Complexidade

Tudo indica que seja praticamente impossıvel criar cifras absolutamente in-quebraveis. E mais razoavel e suficiente para o uso concreto, requerer queum sistema seja praticamente inquebravel por um inimigo, isto e, requererque um sistema demore demasiado tempo (usando milhoes de computadoressuper-potentes) a ser quebrado. Durante este curso, iremos ver o que istosignifica em casos concretos.

2.1 Estimativas de tempo

Um topico que e central em complexidade e a estimacao do numero deoperacoes bit necessarias para efectuar operacoes aritmeticas ou calculosmatematicos num computador. Vamos comecar com algumas nocoes basicas.

Um inteiro n pode ser escrito em qualquer base b com b > 0 inteiro.Usamos a notacao (dk−1dk−2 · · · d1d0)b para significar que

n = dk−1bk−1 + dk−2b

k−2 + · · · d1b+ d0,

onde os algarismos di sao sımbolos que podem tomar valores entre 0 e b −1 e dk−1 e nao nulo. Esta representacao e unica dependendo apenas dabase escolhida. Quando a base e 10 escreve-se apenas dk−1dk−2 · · · d1d0, semindicacao da base, para representar n. Por exemplo,

5476 = 5 · 103 + 4 · 102 + 7 · 10 + 6,

12

(10110)2 = 1 · 24 + 0 · 23 + 1 · 22 + 1 · 2 + 0 = 22.

As fraccoes podem tambem ser representadas em qualquer base, usando-se neste caso o ponto flutuante para distinguir a parte inteira da parte frac-cionaria, i. e.

n = (dk−1dk−2 · · · d1d0.d−1d−2 · · · d−m)b,

se

n =k−1∑

j=−m

djbj.

Diz-se que um inteiro n tem k algarismos, quando escrito na base b, sen = (dk−1dk−2 · · · d1d0)b. Note-se que

numero de algarismos = [logb n] + 1 =

[log n

log b

].

Estamos em condicoes de calcular o tempo necessario para fazer certasoperacoes aritmeticas. Comecaremos com a adicao. Os computadores tra-balham no sistema binario, portanto iremos fazer as nossas operacoes nestesistema, daı o nome de operacoes bit (binary digit). Consideremos a seguinteadicao:

1111

1111000

+0011110

10010110

Suponhamos que ambos os numeros tem k bits, adicionando-se zeros aesquerda caso necessario. Vejamos em detalhe em que consiste esta adicao.Basicamente, temos que repetir k vezes os seguintes passos:

1. Se ambos os bits numa coluna sao zero e nao ha transporte. Neste caso,mete-se um zero e se estivermos na coluna k + 1 o processo termina.Se nao estivermos na coluna k + 1 passa-se a coluna seguinte;

2. Se ou (a) ambos os bits sao zero e ha transporte, ou (b) um dos bits ezero e o outro e um e nao ha transporte, entao mete-se um 1 e passa-sea coluna seguinte; se estivermos na coluna k + 1 o processo termina.

13

3. Se ou (a) ambos os bits sao um e nao ha transporte, ou (b) um dos bitse zero e o outro e um e ha transporte, entao mete-se um 0, mete-se umtransporte na coluna seguinte e passa-se a frente;

4. Se ambos os bits sao um e ha transporte, mete-se um 1, mete-se umtransporte na coluna seguinte e passa-se a frente.

Chamamos operacao bit a uma implementacao deste processo. Portanto,adicionar dois numeros com k bits demora k + 1 operacoes bit. Iremos vercomo descobrir o numero de operacoes bit de varias outras operacoes ar-itmeticas. O tempo que um computador demora a efectuar uma certa tarefae, essencialmente, proporcional ao numero de operacoes bit. No entanto, aconstante de proporcionalidade (o numero de nano-segundos que um com-putador demora a fazer uma operacao bit) depende do computador em par-ticular. Quando falarmos de estimar o tempo que se demora a efectuar certatarefa estaremos a falar do numero de operacoes bit requeridas.

Vejamos agora o processo de multiplicar um numero n com k bits por umnumero m com l bits. Por exemplo,

11101

×1101

00011101

01110100

11101000

101111001

Obtemos, no maximo l linhas, onde cada linha consiste de uma copia den deslocada para a direita uma certa distancia. Portanto, cada linha temno maximo k + l − 1 bits. Temos assim que fazer, no maximo l − 1 adicoes,de inteiros com k + l − 1 bits. Portanto, temos (l − 1)(k + l) operacoes bit.Note-se que neste calculo, negligenciamos o tempo necessario para ”deslocarpara a direita”e o tempo de acesso a memoria. No entanto, este tempo econsiderado irrisorio, quando comparado a um grande numero de operacoesbit. Assim, so nos interessa majorar o numero de operacoes bit. Convemtambem simplificar ao maximo as nossas estimativas. Por exemplo, se k ≥ l,podemos estimar

tempo(k-bit× l-bit) ≤ 2kl ≤ 2k2

14

Definicao. Sejam f, g, duas funcoes aritmeticas, i. e. funcoes cujo conjuntode partida consiste dos inteiros positivos e o conjunto de chegada consistedos numeros reais (por vezes, o conjunto de chegada sera o conjunto doscomplexos). Se g ≥ 0, escrevemos

f(n) = O(g(n))

se existir C > 0 e um inteiro n0 tal que

f(n) ≤ Cg(n)

para qualquer n ≥ n0. Mais geralmente, se existe C > 0, tal que

f(n1, . . . , nk) ≤ Cg(n1, . . . , nk)

para ni’s suficientemente grandes, escrevemos

f = O(g).

Exemplo. Se f = a0 + a1d + · · · + adnd e um polinomio de grau d, com

ad > 0 entao f = O(nd).

Exemplo. log n = O(nϵ), para qualquer ϵ > 0.

Exemplo. O numero de algarismos de n na base b e O(

lognlog b

)= O(log n).

Exemplo. Tempo para efectuar a adicao de n com m, com m ≤ n, eO(log n).

Exemplo. Tempo para efectuar o produto de n por m, com m ≤ n, eO(log2 n).

Note-se que os dois exemplos anteriores referem-se aos processos descritospara efectuar estas operacoes. Claramente, existem outros processos paraefectuar as operacoes mencionadas, podendo estes demorar mais, ou menostempo. Por exemplo, poderıamos ter multiplicado m por n, fazendo a adicaode n com ele proprio, m− 1 vezes. Ha processos de multiplicacao rapida quepermitem multiplicar dois numeros m ≤ n em

O(log n(log log n)(log log log n))

operacoes bit. A cada procedimento que nos permite efectuar certa operacao(ou resolver certa questao), chamamos algoritmo.

O algoritmo da divisao ensinado no ensino basico tambem tem O(kl)operacoes bit, quando se divide um numero com k bits por um com l bits.

15

Exemplo. Converter o inteiro n com k bits para a sua representacao na base10. Dividir n por 1010 demora O(4k) e temos que efectuar[

log n

log 10

]+ 1

divisoes (tantas quantos os dıgitos na base 10 de n). Obtemos assim

tempo(converter n para decimal) = O(k2) = O(log2 n).

Exemplo. Converter o inteiro n com k bits para a sua representacao na baseb. Suponhamos que b tem l bits. Dividir n por b demora O(lk) e temos queefectuar [

log n

log b

]+ 1

divisoes (tantas quantos os algarismos na base b de n). Obtemos assim

tempo(converter n para a base b) = O(lk)O(k/l) = O(k2) = O(log2 n).

Exemplo. Tempo requerido para obter n!. Temos que efectuar O(n) (maisexactamente n − 2) multiplicacoes, cada uma entre um numero com, nomaximo, nk bits e outro, com, no maximo, k bits. Portanto, cada multi-plicacao demora O(nk2) operacoes bit. Assim,

tempo(calcular n!) = O(n2k2) = O(n2 log2 n).

2.2 P versus NP

Definicao. Um algoritmo para efectuar uma computacao (ou responder auma questao), envolvendo inteiros n1, . . . , nr de k1, . . . , kr bits, respectiva-mente, e um algoritmo de tempo polinomial se existirem inteiros d1, . . . , drtais que

numero de operacoes bit = O(kd11 · · · kdr

r )

Definicao. Uma operacao (questao, computacao, tarefa) e de tempo polino-mial se existir um algoritmo de tempo polinomial para a efectuar (resolver).Dizemos que estas operacoes estao na classe P.

Definicao. Se a prova de uma resposta, dada a uma questao, pode ser efec-tuada em tempo polinomial, dizemos que esta questao esta na classe NP.

16

Claramente, temos que P⊂NP.

Exemplo. Questao: factorizar o numero n. Se alguem conseguir resolver aquestao, basta publicar essa factorizacao n = m1 · · ·mt. Para verificarmosse a resposta esta correcta, basta multiplicarmos os inteiros m1, . . . ,mt. Estaverificacao pode ser efectuada em tempo polinomial (t − 1 multiplicacoes,onde t e muito pequeno). Portanto, a factorizacao esta na classe NP. Noentanto, ainda nao foram descobertos algoritmos para efectuar factorizacoesem tempo polinomial. Assim, a factorizacao pode nao estar na classe P.

Um dos problemas do milenio consiste em provar ou provar que e falsa,a afirmacao P = NP .

17

Capıtulo 3

Criptografia Simetrica

Criptografia e a arte e ciencia de enviar mensagens secretas. O emissor usauma chave para cifrar a mensagem, esta e enviada ate ao receptor que usaoutra chave para a decifrar. Escrevendo letras e sinais de pontuacao comonumeros, podemos assumir que a mensagem a enviar e um inteiro P quee codificado num outro inteiro C. O problema consiste em inventar chavesque tornem impossıvel ou computacionalmente irrealizavel que o inimigo (ouqualquer pessoa que nao queiramos que leia a mensagem) decifre a men-sagem interceptada. Muitas vezes a criptografia usa chaves secretas que sosao conhecidas pelo emissor e pelo receptor. Se o inimigo descobre a chavede cifrar e intercepta a mensagem cifrada, ele pode conseguir descobrir achave de decifrar e recuperar a mensagem original. Este foi o metodo que osmatematicos ingleses usaram para decifrar o Enigma, usado pelos alemaespara comunicar entre si e, em particular, com os submarinos, na segundaguerra mundial.

Neste capıtulo iremos estudar alguns exemplos classicos de criptosistemas.

3.1 Introducao

Normalmente, o primeiro passo para inventar um criptosistema consiste emcodificar a mensagem, i. e. transformar a mensagem original em numerosou bits. Este processo pode ser efectuado letra a letra, e. g. A→ 0, ...,Z→ 25, ou em pares de letras, e. g. dadas duas letras correspondentes ax, y ∈ {0, 1, . . . , 25}, o par de letras ira corresponder ao inteiro

26x+ y ∈ {0, 1, . . . , 675}.

18

Por exemplo, o par ”EU”corresponde ao numero 125. A codificacao podetambem ser feita a n-uplos de letras, n ≥ 3, fazendo-se a correspondencia:se a letra αi corresponde ao numero xi entao o n-uplo α1 · · ·αn correspondea inteiro

26n−1x1 + · · · 26xn−1 + xn.

Durante este curso, usaremos essencialmente as codificacoes

1. A→ 0, ..., Z→ 25;

2. 2 → 0, A→ 1, . . . , Z→ 26;

3. 2 → 0, A→ 1, . . . , Z→ 26, 0 → 27, . . . 9 → 36;

4. O codigo ASCII.

Definicao. Um criptosistema e um quıntuplo (P, C,K, E ,D) que satisfaz asseguintes condicoes:

1. P e o conjunto finito dos textos planos possıveis;

2. C e o conjunto finito dos textos cifrados possıveis;

3. K e o conjunto finito das chaves;

4. Para cada K ∈ K existe uma regra para cifrar eK ∈ E e uma regra paradecifrar correspondente dK ∈ D, tais que eK : P −→ C, dK : C −→ Pe dK(eK(x)) = x, para qualquer x ∈ P .

3.2 Cifra de Substituicao

As cifras de Substituicao sao utilizadas a centenas de anos. Actualmenteainda aparecem em Criptogramas nas revistas recreativas. Como o proprionome indica, estas cifras consistem em substituir cada letra por uma outraletra. Nestas cifras nao e necessario codificar a mensagem primeiro.

Cifra (Substituicao). Seja m um inteiro positivo. Sejam P = C = Zm.O conjunto das chaves K consiste de todas as permutacoes dos numeros0, 1, . . . ,m − 1. Sejam x ∈ P e y ∈ C. Para cada permutacao π ∈ K,definimos

eπ(x) = π(x)

19

edπ(y) = π−1(y),

onde π−1 e a permutacao inversa de π.

Estas cifras tem m! chaves possıveis. No caso de m = 26, obtemos maisde 4.0× 1026 chaves, o que torna impraticavel a busca exaustiva da chave deum sistema criptografico deste tipo. Mais tarde veremos como quebrar estessistemas.

Exercıcio. Considere m = 26. Sabendo que foi utilizada uma cifra de sub-stituicao, decifre a seguinte mensagem na lıngua inglesa.

MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA

3.3 Criptoanalise classica

Suponhamos que se deseja decifrar uma mensagem, mas nao se sabe a chave.Para isso usa-se criptoanalise. Diz-se quebrar o codigo ao processo de de-scobrir como decifrar mensagens num dado criptosistema sem se saber aschaves. Para quebrar um codigo necessitamos de dois tipos de informacao:que tipo de criposistema temos, e quais sao as chaves desse criptosistema.Iremos assumir que o tipo de criptosistema a quebrar e conhecido (princıpiode Kerckhoff) e iremos so estudar como descobrir as chaves.

Ha varios nıveis de ataques a um criptosistema, os mais comuns sao

So mensagem cifrada(ciphertext-only): O oponente possui uma men-sagem cifrada;

Texto plano conhecido (known plaintext): O oponente possui um textoplano e a mensagem cifrada correspondente;

Texto plano escolhido (chosen plaintext): o oponente obteve acesso tem-porario a maquina de cifrar. Portanto pode escolher um texto plano ecifra-lo.

Mensagem cifrada escolhida (chosen ciphertext): O oponente obteveacesso temporario a maquina de decifrar. Portanto pode escolher umamensagem cifrada e decifra-la.

20

Letra E T A O I N SProbabilidade 0.127 0.091 0.082 0.075 0.070 0.067 0.063

Letra H R D L C U MProbabilidade 0.061 0.060 0.043 0.040 0.028 0.028 0.024

Letra W F G Y P B VProbabilidade 0.023 0.022 0.020 0.020 0.019 0.015 0.010

Letra K J X Q ZProbabilidade 0.008 0.002 0.001 0.001 0.001

Figura 3.1: Distribuicao de Frequencias na Lıngua Inglesa

Letra A E O S R I NProbabilidade 0.146 0.126 0.107 0.078 0.065 0.062 0.051

Letra D M T U C L PProbabilidade 0.050 0.047 0.047 0.046 0.039 0.028 0.025

Letra H G Q B F V JProbabilidade 0.013 0.013 0.012 0.010 0.010 0.009 0.004

Letra J X K W YProbabilidade 0.004 0.002 0.001 0.001 0.001

Figura 3.2: Distribuicao de Frequencias na Lıngua Portuguesa

Normalmente, e preferıvel usar textos planos sem espacos nem pontuacao,tornando o criptosistema mais seguro.

Muitas tecnicas de criptoanalise utilizam as propriedades estatısticas deuma lıngua. Nas figuras 3.1 e 3.2 estao representadas as frequencias relativasdas lınguas Ingles e Portugues, respectivamente. Por vezes temos tambem deusar as frequencias relativas de duas ou tres letras consecutivas (digramas etrigramas). Os digramas mais frequentes na lıngua inglesa sao: TH, HE, IN,ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS,OR, TI, IS, ET, IT, AR, TE, SE, HI e OF. Os trigramas mais frequentes nalıngua inglesa sao: THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS,ETH, FOR e DTH.

21

3.4 Criptoanalise da Cifra de Substituicao

Vamos complicar um pouco e analisar como se pode quebrar a cifra de sub-stituicao. Considere a mensagem cifrada

YIFQFM ZRWQFY VECFMD ZPCVMR ZWNMDZ VEJBTX

CDDUMJ NDIFEF MDZCDM QZKCEY FCJMYR NCWJCS

ZREXCH ZUNMXZ NZUCDR JXYYSM RTMEYI FZWDYV

ZVYFZU MRZCRW NZDZJJ XZWGCH SMRNMD

HNCMFQ CHZJMX JZWIEJ YUCFWD JNZDIR

A seguinte tabela apresenta a analise de frequencia desta mensagemcifrada

Letra A B C D E F G H IFrequencia 0 1 15 13 7 11 1 4 5

Letra J K L M N O P Q RFrequencia 11 1 0 16 9 0 1 4 10

Letra S T U V W X Y ZFrequencia 3 2 5 5 8 6 10 20

Como o Z aparece significativamente mais vezes que qualquer outra letra,podemos conjecturar que dK(Z) = e. As outras letras que aparecem pelomenos de 9 vezes sao M, C, D, F, J, R, Y, N e sera de esperar que estasletras sejam obtidas a partir de t, a, o, i, n, s, h, r, mas por termos um textotao pequeno, as frequencias nao variam de modo suficiente para nos dar acorrespondencia correcta.

Nesta altura, e aconselhavel considerar digramas, especialmente aquelesque contem a letra Z. Verifica-se que os digramas DZ e ZW aparecem quatrovezes cada, que os digramas NZ e ZU aparecem tres vezes cada e que os digra-mas RZ, HZ, XZ, FZ, ZR, ZV, ZC, ZD, ZJ aparecem duas vezes cada. ComoZW aparece quatro vezes, WZ nunca aparece e W nao e das letras que maisaparecem, podemos conjecturar que dK(W ) = d. Como DZ aparece quatrovezes e ZD aparece duas vezes, podemos esperar que dK(D) ∈ {r, s, t}, masnao conseguimos, de uma maneira clara, prever qual das tres possibilidadese a correcta.

22

Assumindo dK(W ) = d, verifica-se que os unicos digramas com W nofim, que aparecem mais que uma vez sao ZW e RW. Entre os digramas maisfrequentes na lıngua inglesa, os unicos que terminam em d sao ed e nd, dondesomos levados a conjecturar que dK(R) = n.

Antes de continuarmos a nossa analise, vejamos quais sao os digramas quemais aparecem na mensagem cifrada. Alem dos digramas DZ e ZW tambemMD eMR aparecem quatro vezes cada, e, alem de NZ e ZU, tambem CD, CH,FM, IF e NM aparecem tres vezes. Atendendo aos digramas mais frequentesna lıngua inglesa podemos inferir que dK(M) ∈ {a, i, n, o, s} e dK(R) ∈{n, r, s, t}. Mais, como NM e NZ sao frequentes, entao provavelmente temosdK(NM) ∈ {ha, hi}.

A ultima afirmacao permite-nos conjecturar que dK(N) = h e dK(M) ∈{a, i}.

Vejamos como fica a frase se efectuarmos as substituicoes conjecturadas:

- - - - - - end - - - - - - - - - e - - - - n edh - - e - - - - - -YIFQFM ZRWQFY VECFMD ZPCVMR ZWNMDZ VEJBTX- - - - - - h - - - - - - - e - - - - e - - - - - - - - - n h - d - - -CDDUMJ NDIFEF MDZCDM QZKCEY FCJMYR NCWJCSen - - - - e - h - - e he - - - n - - - - - - n - - - - - - ed - - -ZREXCH ZUNMXZ NZUCDR JXYYSM RTMEYI FZWDYVe - - - e - - ne - nd he - e - - - ed - - - - - nh - -ZVYFZU MRZCRW NZDZJJ XZWGCH SMRNMD- h - - - - - - e - - - - ed - - - - - - - d - - he - - nHNCMFQ CHZJMX JZWIEJ YUCFWD JNZDIR

A sequencia ne - nd sugere que devemos substituir C por a o que implicaque dK(M) = i. Donde

23

- - - - - i end - - - - - a - i - e - a - in edhi - e - - - - - -YIFQFM ZRWQFY VECFMD ZPCVMR ZWNMDZ VEJBTXa - - - i - h - - - - - i - ea - i - e - a - - - a - i - n had - a -CDDUMJ NDIFEF MDZCDM QZKCEY FCJMYR NCWJCSen - - a - e - hi - e he - a - n - - - - - i n - i - - - - ed - - -ZREXCH ZUNMXZ NZUCDR JXYYSM RTMEYI FZWDYVe - - - e - ineand he - e - - - ed - a - - inhi -ZVYFZU MRZCRW NZDZJJ XZWGCH SMRNMD- hai - - a - e - i - - ed - - - - - a - d - - he - - n

HNCMFQ CHZJMX JZWIEJ YUCFWD JNZDIR

Das vogais mais frequentes so nos falta determinar a letra que corre-sponde a o. Sabemos que esta letra e muito comum, portanto sera aceitavelsupor que e uma das letras D, F, J, Y. Mas D, F, J sao facilmente elimi-nadas senao provocavam sequencias de muitas vogais no texto plano. Con-jecturamos entao que dK(Y ) = o. Quando se faz esta substituicao, obtem-seas sequencias a-ion o que sugere a terminacao ation muito comum em ingles.Assim, dK(J) = t.

o - - - - i end - - o - - a - i - e - a - in edhi - e - - t - - -YIFQFM ZRWQFY VECFMD ZPCVMR ZWNMDZ VEJBTXa - - - it h - - - - - i - ea - i - e - a - o - ation hadta -CDDUMJ NDIFEF MDZCDM QZKCEY FCJMYR NCWJCSen - - a - e - hi - e he - a - n t - oo - i n - i - o - - ed - o -ZREXCH ZUNMXZ NZUCDR JXYYSM RTMEYI FZWDYVe - o - e - ineand he - ett - ed - a - - inhi -ZVYFZU MRZCRW NZDZJJ XZWGCH SMRNMD- hai - - a - eti - ted - - t o - a - d - the - - n

HNCMFQ CHZJMX JZWIEJ YUCFWD JNZDIR

Ja tınhamos reparado que dK(D) ∈ {r, s, t}. Atendendo a sequencia d-the, faz sentido considerar que dK(D) = s. Das letras mais frequentes so nossobram F e r. Donde dK(F ) = r.

24

o - r - ri end - ro - - aris e - a - in edhise - - t - - -YIFQFM ZRWQFY VECFMD ZPCVMR ZWNMDZ VEJBTXass - it hs - r - r iseasi - e - a - o ration hadta -

CDDUMJ NDIFEF MDZCDM QZKCEY FCJMYR NCWJCSen - - a - e - hi - e he - asn t - oo - i n - i - o - redso -ZREXCH ZUNMXZ NZUCDR JXYYSM RTMEYI FZWDYVe - ore - ineand hesett - ed - a - - inhisZVYFZU MRZCRW NZDZJJ XZWGCH SMRNMD- hair - a - eti - ted - - t o - a - ds thes - n

HNCMFQ CHZJMX JZWIEJ YUCFWD JNZDIR

Agora, facilmente se obtem

Our friend from Paris examined his empty glass with surprise, asif evaporation had taken place while he wasn’t looking. I pouredsome more wine and he settled back in his chair, face tilted uptowards the sun

3.5 Cifra de Deslocamento

Nesta subseccao, apresentamos as cifras de deslocamento, da qual o sistemacriptografico utilizado por Julio Cesar e um exemplo. A base desta cifra,assim como de outras cifras que estudaremos posteriormente, e a aritmeticamodular.

Definicao. Sejam a e b inteiros e n um inteiro positivo. Se n | (a − b),dizemos que a e congruente com b e escrevemos

a ≡ b mod n

Cifra (Deslocamento). Seja m um inteiro positivo. Sejam P = C = K = Zm.Para 0 ≤ K ≤ m− 1, x ∈ P e y ∈ C definimos

eK(x) ≡ x+K mod m

edK(y) ≡ y −K mod m

25

A cifra de Cesar e uma cifra de deslocamento, com K = 3 e m = 23. OROT-13, actualmente utilizado online, em newsgroups e usenet, para ocultarmensagens ofensivas, respostas a puzzles, etc., e outro exemplo de uma cifrade deslocamento, neste caso com K = 13 e m = 26. Note-se que, neste casoeK(eK(x)) = x.

As cifras de deslocamento sao exemplos de cifras de substituicao.As cifras de deslocamento sao muito inseguras, porque ha somente m

chaves possıveis, e m e normalmente muito pequeno. Uma busca exaustivada chave quebra rapidamente um destes sistemas criptograficos.

Exercıcio. A seguinte mensagem foi cifrada com uma cifra de deslocacaocom m = 27. Decifre-a.

OCUAE SCMRUMLQLDQSFCMZOM

3.6 Algoritmo de Euclides e inversos mod n

Antes de vermos mais sistemas criptograficos, necessitamos de alguns resul-tados elementares da Teoria dos Numeros.

Definicao. Sejam a e b dois inteiros tais que pelo menos um deles e naonulo. Chamamos maximo divisor comum ao maior elemento do conjunto dosdivisores comuns de a e b e denotamos este elemento por (a, b).

Sejam a e b dois inteiros positivos. Pelo algoritmo da divisao, existemdois inteiros q0 e r0, tais que

a = q0b+ r0, com 0 ≤ r0 < b

Se r0 = 0 podemos utilizar o algoritmo da divisao para os inteiros b por r0.Entao existem q1 e r1 tais que

b = q1r0 + r1, com 0 ≤ r1 < r0

Procedendo desta forma obtemos uma sequencia de inteiros nao negativosr0, r1, . . . , rn, tais que r0 > r1 > · · · > rn ≥ 0. Note que este processo temde terminar ao fim de um numero finito de passos e que o ultimo resto, quedenotamos por rk+1, e nulo.

26

Teorema 3.1. Se a e b sao dois inteiros positivos e rk e o ultimo resto naonulo obtido pelo algoritmo de Euclides, entao rk = (a, b). Mais, o algoritmode Euclides permite encontrar inteiros u e v tais que

au+ bv = (a, b)

Demonstracao: O algoritmo de Euclides pode ser esquematizado peloseguinte sistema de equacoes:

a = bq0 + r0b = r0q1 + r1r0 = r1q2 + r2...rk−2 = rk−1qk + rkrk−1 = rkqk+1

(3.1)

Seja d = (a, b). Vamos provar por inducao que d|ri e d|ri+1, para todoo 0 ≤ i ≤ k − 1. Como d|a e d|b, temos d|(a − bq0), i.e., d|r0. Comod|b e d|r0 entao d|(b − r0q1) = r1. Agora, suponhamos que d|ri e d|ri+1,queremos provar que d|ri+1 e d|ri+2. Usando a hipotese de inducao, obtemosque d|(ri − ri+1qi+2). Mas ri − ri+1qi+2 = ri+2. Portanto d|ri+2.

Acabamos de provar que d|ri para todo 0 ≤ i ≤ k. Em particular, d|rk.Como d, rk > 0, temos d ≤ rk.

Reciprocamente, a ultima equacao em (3.1) e o facto de rk = 0, diz-nosque rk|rk−1. Usando a penultima equacao, obtemos rk|rk−2. Por inducao,concluımos que rk|ri, para qualquer 0 ≤ i ≤ k. Usando a segunda equacao,temos rk|b e usando a primeira, rk|a. Logo, rk|d. Portanto, rk = d.

Agora, provamos a segunda parte do teorema. Seja r−2 = a e r−1 = b.Sabemos que

ri = ri−2 − ri−1qi, (3.2)

para qualquer 0 ≤ i ≤ k. Vamos provar por inducao que, para qualquer0 ≤ i ≤ k, existem inteiros ui e vi tais que ri = uia+ vib. Como r0 = a− bq0,o resultado e valido para i = 0. Suponhamos, por hipotese de inducao que oresultado e verdadeiro para i e para i− 1. Entao

ri+1 = ri−1 − riqi+1

= ui−1a+ vi−1b− (uia+ vib)qi+1

= (ui−1 − uiqi+1)a+ (vi−1 − viqi+1)b

= ui+1a+ vi+1b

27

Portanto, para qualquer 0 ≤ i ≤ k, ri = uia + vib. Em particular, existeminteiros u e v, tais que rk = ua+ vb. 2

Exemplo. Seja a = 543 e b = 431. A seguinte tabela esquematiza o al-goritmo de Euclides para calcular d = (a, b) e descobrir u e v tais queau+ bv = 1.

i −2 −1 0 1 2 3 4 5 6

qi 1 3 1 5 1 1 2ri 543 431 112 95 17 10 7 3 1ui 1 0 1 −3 4 −23 27 −50 127vi 0 1 −1 4 −5 29 −34 63 −160

Entao (a, b) = 1 e 127a − 160b = 1. Mais, para cada −2 ≤ i ≤ kri = aui + bvi.

Teorema 3.2. Suponhamos que a > b. Entao

tempo(determinar (a, b) usando o algoritmo de Euclides) = O(log3 a).

Demonstracao: O algoritmo de Euclides consiste em efectuar sucessi-vas divisoes, onde os sucessivos restos formam uma sequencia estritamentedecrescente. Portanto, para estimar o numero de operacoes bit, precisamosde saber quantas divisoes e necessario efectuar. Primeiro, vamos provar queri+2 <

12ri:

Se ri+1 ≤ 12ri, entao como ri+2 < ri+1, obtemos ri+2 <

12ri.

Se ri+1 >12ri, entao a divisao seguinte, no algoritmo de Euclides, e

ri = ri+1 + ri+2.

Portanto, ri+2 = ri − ri+1 <12ri.

Acabamos de provar que em cada dois passos do algoritmo de Euclideso resto e pelo menos reduzido a metade, donde temos no maximo 2[log2 a]divisoes. Como cada divisao envolve numeros menores ou iguais a a, o numerode operacoes bit por divisao e O(log2 a). Portanto, o algoritmo de Euclidesdemora

O(log3 a)

28

operacoes bit. 2

Definicao. Sejam a e b inteiros tais que pelo menos um deles e nao nulo. Se(a, b) = 1 entao dizemos que a e b sao primos entre si.

Teorema 3.3. Se (n, a) = 1 e n|ab, entao n|b.Demonstracao: Pelo teorema 3.1, se (n, a) = 1 entao existem inteiros u

e v, tais que nu+ av = 1, donde nbu+ abv = b. Como n|ab, obtemos n|b. 2

Teorema 3.4. Se (a, n) = 1 e ab ≡ ac mod n, entao b ≡ c mod n. Emgeral, se (a, n) = d e ab ≡ ac mod n entao

b ≡ c modn

d.

Demonstracao: Suponhamos que (a, n) = d e ab ≡ ac mod n. Entaoexiste um inteiro k tal que ab = ac+ kn. Sejam

a1 =a

d, n1 =

n

d.

Claramente, a1 e n1 sao inteiros e (a1, n1) = 1. Dividindo ambos os membrosde ab = ac + kn por d, obtem-se a1(b − c) = kn1. Donde, a1 | kn1. Como(a1, n1) = 1, temos a1 | k. Portanto, k = a1k1, para algum inteiro k1. Assim,b− c = k1n1, ou seja n1 | (b− c). Portanto, b ≡ c mod n

d. 2

Teorema 3.5. Sejam a e b inteiros nao nulos e d = (a, b). Se d - c entao aequacao

ax+ by = c (3.3)

nao tem solucoes inteiras. Se d|c, a equacao tem uma infinidade de solucoesinteiras. Se x = x0, y = y0 e uma solucao de (3.3), entao todas as solucoesde (3.3) sao dadas por

x = x0 + tb

d

y = y0 − ta

d

29

onde t e um inteiro.

Demonstracao: Como d|a e d|b, temos d|(ax + by) para quaisquer in-teiros x e y. Portanto, se c = ax + by, entao d|c. Donde, se d - c, (3.3) naotem solucoes inteiras. Agora, se d|c, existe um inteiro e tal que c = de. Peloteorema 3.1, existem inteiros u e v, tais que

au+ bv = d.

Multiplicando por e, obtemos a(ue) + b(ve) = de = c. Portanto, a equacao(3.3) tem pelo menos uma solucao. Seja (x0, y0) uma solucao de (3.3) e t uminteiro qualquer. Entao

a

(x0 + t

b

d

)+ b

(y0 − t

a

d

)= ax0 + by0 = c.

O que prova que a equacao (3.3) tem uma infinidade de solucoes.Falta-nos ainda provar que qualquer solucao de ax + by = c e da forma

descrita no teorema. Suponhamos que (x1, y1) e outra solucao. Entao

a(x1 − x0) + b(y1 − y0) = c− c = 0.

Dondea

d(x1 − x0) = − b

d(y1 − y0), (3.4)

o que implica queb

d| ad(x1 − x0).

Como

(a

d,b

d

)= 1, temos

b

d| (x1 − x0). Portanto, existe um inteiro t, tal

que

x1 = x0 + tb

d.

Substituindo em (3.4), obtemos

a

dtb

d= − b

d(y1 − y0),

dondey1 = y0 − t

a

d.

Portanto, qualquer solucao de (3.3) e forma acima descrita. 2

30

Teorema 3.6. A congruencia

ax ≡ b mod n (3.5)

tem solucoes se e so se d | b, onde d = (a, n). Se d | b entao a solucao e unica

modn

d. Se (a, n) = 1 entao (3.5) tem uma solucao que e unica mod n.

Demonstracao: Se x0 e uma solucao da equacao (3.5) entao existe uminteiro y0 tal que

ax0 = b+ ny0,

donde a equacaoax− ny = b (3.6)

tem solucao. Reciprocamente, se (x0, y0) e uma solucao de (3.6) entao

ax0 ≡ ax0 − ny0 ≡ b mod n

e, portanto, (3.5) tem solucao. Acabamos de provar que (3.5) tem solucoesse e so se (3.6) tem solucoes e a partir de uma solucao de (3.6) obtemosuma solucao de (3.5). Pelo teorema 3.5, (3.6) tem solucoes se e so se d | b.Portanto, (3.5) tem solucoes se e so se d | b.

Suponhamos agora que (3.6) tem solucoes e seja (x0, y0) uma solucao.Pelo teorema 3.5 qualquer solucao de (3.6) e da forma

x = x0 + tn

d, y = y0 − t

a

d,

onde t e um inteiro. Portanto, qualquer solucao de (3.5) e da forma

x = x0 + tn

d

Comox0 + t

n

d≡ x0 mod

n

d,

entao todas as solucoes de (3.5) sao congruentes com x0 modn

d, e portanto,

a solucao de (3.5) e unica modn

d.

A ultima parte do teorema resulta imediatamente das duas primeiraspartes. 2

31

Definicao. Sejam a e n inteiros tais que (a, n) = 1. Ao unico inteiro, que esolucao da equacao

ax ≡ 1 mod n

chamamos inverso de a mod n e denota-mo-lo por a−1 mod n.

Como o processo para escrever (a, b) como combinacao linear de a e be dado pelo algoritmo de Euclides, tambem este processo demora O(log3 a)operacoes bit. Em particular obtemos:

Corolario 3.7. Dado a, n inteiros, com n > 1 e (a, n) = 1. Entao

tempo(determinar a−1) = O(log3 a).

Exemplo. Como (543, 431) = 1 e 127 · 543− 160 · 431 = 1, entao o inversode 543 mod 431 e 127 e o inverso de 431 mod 543 e 383.

3.7 Cifra Afim

Nesta subseccao, apresentamos outro caso especial da cifra de substituicao,conhecido como cifra afim. Este tipo de criptosistema utiliza funcoes afins,i. e. funcoes da forma f(x) = ax+ b. Mais uma vez utilizamos congruenciaspara definir as regras para cifrar e para decifrar. Dado m > 1 inteiro, a, b ∈Zm, queremos que a regra para cifrar e(x) (da cifra afim com a chave (a, b))seja da forma

e(x) ≡ ax+ b mod m.

Note-se que, para podermos ter uma regra para decifrar e necessario quee(x) seja injectiva. Pelo teorema 3.6, e(x) e injectiva se e so se (a,m) = 1.Sabemos tambem que se (a,m) = 1 entao a tem inverso mod m.

Cifra (Afim). Seja m um inteiro positivo. Sejam P = C = Zm e K ={(a, b) ∈ Z2

m | (a,m) = 1}. Sejam x ∈ P e y ∈ C entao definimos

ea,b(x) ≡ ax+ b mod m

eda,b(y) ≡ a−1(y − b) mod m

32

3.8 Funcao φ de Euler

Definicao. Seja n ≥ 1. O numero de inteiros positivos menores ou iguais an que sao primos com n e denotado por φ(n). Esta funcao de n e chamadafuncao φ de Euler

Assim, o conjunto das chaves K tem mφ(m) elementos. Recordamosagora os seguinte resultados sobre a funcao φ.

Teorema 3.8. A funcao φ(n) e multiplicativa.

Demonstracao: Sejam m e n inteiros positivos tais que (m,n) = 1.Vamos meter os primeirosmn inteiros numa tabela comm colunas e n linhas.

1 2 . . . mm+1 m+2 . . . m+m2m+1 2m+2 . . . 2m+m

......

......

(n-1)m+1 (n-1)m+2 . . . (n-1)m+m

Os numeros na coluna j sao m · 0 + j, m · 1 + j, m · 2 + j, . . . ,m(n− 1) + j.Temos, (ma+ j,m) = (j,m), para qualquer inteiro a. Portanto, ou qualquerelemento da coluna j e primo comm ou nenhum elemento da coluna j e primocom m. Assim, ha exactamente φ(m) colunas contendo inteiros primos comm e qualquer elemento destas φ(m) colunas e primo com m.

Como (m,n) = 1, os n elementos de cada coluna j formam um sistemacompleto de resıduos mod n. Portanto, por definicao, cada coluna j contemexactamente φ(n) elementos primos com n. Donde, em cada uma das φ(m)colunas que tem os elementos que sao primos comm, ha exactamente φ(n) el-ementos primos com n. Mais, estes sao os unicos elementos que sao ao mesmotempo primos com m e primos com n. Isto e, ha exactamente φ(m)φ(n), el-ementos na tabela que sao primos com m e, ao mesmo tempo, primos comn.

Mas um inteiro e primo com mn se e so se for primo simultaneamentecom m e com n. Portanto,

φ(mn) = φ(m)φ(n)

e a funcao de Euler e multiplicativa. 2

33

Teorema 3.9. Suponhamos que a factorizacao de n em primos e a seguinte

n = pa11 pa22 · · · pakk

Entao

φ(n) = n(1− 1

p1)(1− 1

p2) · · · (1− 1

pk) =

k∏i=1

(paii − pai−1i )

Demonstracao: Vamos comecar por calcular φ(pa), para p primo e a ≥1. Um inteiro e primo com pa excepto se for divisıvel por p. Os numeros de1 a pa que sao divisıveis por p, sao 1 · p, 2 · p, . . . , pa−1p. Portanto,

φ(pa) = pa − pa−1 = pa(1− 1

p).

Mas como a funcao φ(n) e multiplicativa, temos

φ(n) = φ(pa11 )φ(pa22 ) · · ·φ(pakk )

= pa11 (1− 1

p1)pa22 (1− 1

p2) · · · pakk (1− 1

pk)

= pa11 pa22 · · · pakk (1− 1

p1)(1− 1

p2) · · · (1− 1

pk)

= n(1− 1

p1)(1− 1

p2) · · · (1− 1

pk)

2

3.9 Criptoanalise da Cifra Afim

Suponhamos que e interceptada uma mensagem que se sabe ter sido cifradausando um criptosistema afim, e que o alfabeto utilizado tem N = 26 letras.As duas letras mais frequentes na mensagem sao ”J”e ”C”. Sabe-se tambemque a mensagem esta em ingles, e que nesta lıngua, as letras mais frequentessao o ”E”e o ”T”(ver figura 3.1). Deduzimos assim que, provavelmente, o

34

”E”foi cifrado em ”J”e que o ”T”foi cifrado em ”C”. Para determinar aschaves so temos que resolver o sistema de congruencias

10c+ d ≡ 5 mod 26

3c+ d ≡ 20 mod 26

Exemplo. Vamos decifrar a seguinte mensagem.

ICFMGTICJWARGIJGTRWNKJGFKWABGOKWFK

RWCBKAWJZMJGCCWKGCKJOKCKFKXJGFGNJM

GFMAAWFWLMOGFGCWTRWGKCMAAMKTGJMKFG

OKPMTVGSIWGBJWNWJMGSIWTRWSIWGFKXJG

FGWWJGGCKFGFKBKJRKTITOGAWOKCWNJMG

As letras mais frequentes sao o G e o W, portanto assumimos que a foicifrado em G e e foi cifrado em W.

Obtemos as congruencias 6u + v ≡ 0 mod 26 e 22u + v ≡ 4 mod 26.Logo u = 10 ou u = 23, mas u tem de ser primo com 26, donde u = 23 ev = 18.

Portanto, a = 17 e b = 6.

Exercıcio. Decifre a mensagem que se sabe ter sido cifrada usando umacifra afim e que o texto plano esta na lıngua portuguesa.

HJHRF MRHOH XHMIZ XDFJF HQRUI TMHHZ XDTYI

TMHZH JTXRD HHQZY HJZJF DRFUH YJZUI ZHFQT

SYRDF ZJVZM HYRXI FHDFU IZDZQ FMBTZ ZXIHX

HMIZX QFOZJ XZMZA QZMRJ ZUIHO HXQFM TJFTJ

HRXOF XUFXX FXXZU IROFXQ HMHXZ HQMZD

RHMHH MIZOH JHIZJ HIRDH IZJFX OZTIR YRWHM

FMHDR FDRUR FZTJY FUVFQ ZMRFO FOZIM ZRUFR

UIZUX REF

35

3.10 Cifra de Vigenere

Nas cifras estudadas ate agora, dada uma chave, cada letra e transformadanuma so outra letra. Por esta razao, aqueles criptosistemas sao denominadosmono-alfabeticos. A cifra de Vigenere, que vamos apresentar nesta seccao, eo primeiro exemplo de um criptosistema poli-alfabetico.

Cifra (Vigenere). Sejam m e n inteiros positivos. Sejam P = C = K =(Zm)

n. Dada uma chave K = (k1, . . . , kn) e x ∈ P e y ∈ C, definimos

eK(x1, . . . , xn) ≡ (x1 + k1, . . . , xn + kn) mod m

edK(y1, . . . , yn) ≡ (y1 − k1, . . . , yn − kn) mod m.

O numero de chaves possıveis, dados m e n e mn.

Exemplo. Suponhamos que m = 26, n = 8 e a chave e PORTUGAL. EntaoK = (15, 14, 17, 19, 20, 6, 0, 11). Queremos cifrar a frase

este criptosistema nao e seguro

Primeiro codificamos o texto plano depois ciframos grupos de 8 de cada veze adicionamos a chave mod 26, da seguinte maneira

4 18 19 4 2 17 8 15 19 14 18 8 18 19 415 14 17 19 20 6 0 11 15 14 17 19 20 6 019 6 10 23 22 23 8 3 6 2 9 1 12 25 4

12 0 13 0 14 4 18 4 6 20 17 1411 15 14 17 19 20 6 0 11 15 14 1723 15 1 17 7 24 24 4 17 9 5 5

A mensagem cifrada fica

TGKXWXIDGCJBMZEXPBRHYYERJFF

36

3.11 Criptoanalise da cifra de Vigenere

O primeiro passo para criptanalisar a cifra de Vigenere consiste em encontraro comprimento da palavra chave, que denotamos por n. Vamos estudar duastecnicas que nos podem ajudar a encontrar n, nomeadamente o teste deKasiski e o ındice de coincidencia.

O teste de Kasiski foi pela primeira vez descrito por Friedrich Kasiskiem 1863. Este teste tem por base o facto de dois segmentos identicos dotexto plano serao transformados no mesmo texto cifrado sempre que a suaocorrencia no texto plano esta com x posicoes de separacao, com x ≡ 0mod n. Reciprocamente, se forem observados no texto cifrado dois segmentosidenticos com comprimento de pelo menos tres letras, entao ha uma grandechance que eles correspondam a segmentos identicos do texto plano.

O teste de Kasiski funciona do seguinte modo: Primeiro procuramos notexto cifrado pares de segmentos identicos de comprimento maior ou igual a3 e guardamos a distancia entre o inıcio de cada um dos dois segmentos. Seobtivermos as distancias d1, d2, . . . entao conjecturamos que n divide o maiordivisor comum entre todas as distancias.

Outro processo para estimar o valor de n, consiste em utilizar o ındice decoincidencia desenvolvido por Wolfe Friedman em 1920.

Definicao. Seja x = x1x2 . . . xm uma lista de m letras. O ındice de coin-cidencia de x, que denotamos por Ic(x) e a probabilidade de que dois elemen-tos de x sejam iguais. Denotemos as frequencias de A,B,C, . . . , Z em x porf0, f1, . . . , f25. Como podemos escolher dois elementos de x de

(m2

)maneiras

e, para cada 0 ≤ i ≤ 25, ha(fi2

)maneiras de escolher dois elementos e ambos

serem i entao,

Ic(x) =

∑25i=0 fi(fi − 1)

m(m− 1).

Se x e parte de um texto em ingles ou e um texto cifrado atraves de umacifra mono-alfabetica, e pi sao as probabilidades indicadas na figura 3.1 serade esperar que

Ic(x) ≈25∑i=0

p2i = 0.065.

A figura 3.3 apresenta os ındices de coincidencia de varias lınguas.

37

Portugues 0.0738Ingles 0.0661Frances 0.0778Italiano 0.0738Alemao 0.0762Japones 0.0819Russo 0.0529Texto aleatorio 0.0385

Figura 3.3: Indices de Coincidencia esperados

Vejamos agora como utilizar o ındice de coincidencia para determinar ocomprimento da palavra passe de uma cifra de Vigenere, n.

Suponhamos que y = y1y2 . . . ym foi obtido atraves de uma cifra de Vi-genere de um texto plano em ingles. Para cada inteiro r ≥ 1, escrevemos amensagem cifrada y, por colunas numa matriz do tipo r ×m/r. Denotamospor yi a linha i, desta matriz, com 1 ≤ i ≤ r. Se r = n entao e de esperarque Ic(yi) seja aproximadamente 0.0661, para qualquer 1 ≤ i ≤ r. Se r = nentao as listas yi serao mais aleatorias, pois foram obtidas utilizando cifrasde deslocamento com varias chaves. Como o ındice de coincidencia esperadode uma lıngua e muito diferente do ındice de coincidencia esperado de umtexto aleatorio, seremos capazes de descobrir o valor de n.

Apos determinarmos o comprimento da palavra passe, cada yi e obtidoatraves de uma cifra de deslocamento de um texto plano na lıngua consider-ada e pode ser utilizada a analise de frequencias para obter a palavra passe.Quando o texto plano e pequeno, a analise de frequencias pode nao ser sufi-ciente para conjecturar com grande conviccao o valor da chave. Neste caso,usamos o ındice de coincidencia mutua entre duas listas.

Definicao. Sejam x = x1x2 . . . xm e y = y1y2 . . . yt listas com m e t letras,respectivamente. O ındice de coincidencia mutua de x e y, que denotamospor MIc(x, y) e a probabilidade de um elemento de x ser igual a um elementode y. Se denotarmos as frequencias de A,B, . . . , Z em x e y por f0, f1, . . . , f25e g0, g1, . . . , g25, respectivamente, entao

MIc(x, y) =

∑25i=0 figimt

.

Ja vimos que cada yi e obtido atraves de uma cifra de deslocamento.

38

Seja K = (k1, . . . , kn) a palavra passe, entao yi obtem-se somando ki a cadai-esima letra do texto plano. Vamos primeiro estimar MIc(yi,yj). Tirandouma letra de yi e outra de yj, a probabilidade de serem ambas A e p−kip−kj ,a probabilidade de ambas serem B e p1−kip1−kj , etc. (note que os ındices saoreduzidos mod 26). Portanto,

MIc(yi,yj) ≈25∑h=0

ph−kiph−kj =25∑h=0

phph+ki−kj .

Esta estimativa depende apenas da diferenca ki − kj mod 26 a qualchamamos deslocamento relativo de yi e yj. Mais, como

25∑h=0

phph+l =25∑h=0

ph−lph,

um deslocamento relativo de u da a mesma estimativa para MIc que umdeslocamento relativo de 26− u. Portanto precisamos apenas de calcular asestimativas para os deslocamentos relativos entre 0 e 13.

Deslocamento relativo Valor esperado de MIc0 0.0651 0.0392 0.0323 0.0344 0.0445 0.0336 0.0367 0.0398 0.0349 0.03410 0.03811 0.04512 0.03913 0.043

Verifica-se que um deslocamento relativo nulo da um ındice de coin-cidencia mutua (MIc) muito distinto doMIc correspondente a qualquer outrodeslocamento relativo. Podemos usar esta informacao para tentar descobriru = ki − kj. Primeiro fixamos yi e vamos cifrar yj usando cada uma daschaves g com 0 ≤ g ≤ 25 e denotamos a mensagem cifrada obtida, por yg

j .Em seguida, calculamos os ındices MIc(yi,y

gj ), para cada 0 ≤ g ≤ 25,

39

MIc(yi,ygi ) =

∑25h=0 fh,ifh−g,j

mt,

onde fh,i e fh,j sao as frequencias da letra correspondente a h em yi e yj,respectivamente. Quando g = u o ındice MIc deve ser proximo de 0.065,mas quando g = u o ındice deve ser relativamente menor. Para cada i e jdevemos calcular 14 ındices, um para cada chave.

Vamos ilustrar estes metodos com o seguinte exemplo:

Exemplo. Sabemos que a seguinte mensagem foi cifrada utilizando um crip-tosistema de Vigenere.

CHREEV OAHMAE RATBIA XXWTNX BEEOPH BSBQMQ

EQERBWRVXUOAKXAOSX XWEAHBWGJMMQMNKGRF

VGXWTR ZXWIAK LXFPSK AUTEMN DCMGTS XMXBTU

IADNGM GPSREL XNJELX VRVPRT ULHDNQ WTWDTY

GBPHXT FALJHA SVBFXN GLLCHR ZBWELE KMSJIK

NBHWRJ GNMGJS GLXFEY PHAGNR BIEQJT AMRVLC

RREMND GLXRRI MGNSNR WCHRQH AEYEVT AQEBBI

PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHR

CLQOHP WQAIIW XNRMGW OIIFKE E

Primeiro, vamos tentar descobrir n utilizando o teste de Kasiski. Otrigrama CHR aparece cinco vezes na mensagem cifrada, comecando nasposicoes 1, 166, 236, 276 e 286. As distancias da primeira ocorrencia as out-ras sao 165, 235, 275 e 285 e o maximo divisor comum entre estes valores e5. Portanto, e de prever que o comprimento da palavra passe seja 5.

Vejamos se com o calculo dos ındices de coincidencia chegamos a mesmaconclusao. Se r = 1, o ındice de coincidencia e 0.045. Se r = 2 obtemosIc(y1) = 0.046 e Ic(y2) = 0.041. Se r = 3 obtemos Ic(y1) = 0.043, Ic(y2) =0.050 e Ic(y3) = 0.047. Para r = 4, obtemos os valores 0.042, 0.039, 0.046 e0.040. Finalmente, para r = 5, obtemos 0.063, 0.068, 0.069, 0.061 e 0.072, oque tambem sugere que n = 5.

Vamos agora tentar utilizar os ındices de coincidencia mutua para de-scobrir a palavra passe. Utilizando um programa no computador, calcula-setodos os 260 valores de MIc(yi,y

gj ), com 1 ≤ i < j ≤ 5 e 0 ≤ g ≤ 25, e

40

procura-se os valores que forem proximos de 0.065. Dado um par (i, j), sehouver um unico valor perto de 0.065, conjecturamos que esse e o valor dodeslocamento relativo.

Verifica-se haver grande evidencia que o deslocamento relativo entre y1

e y2 seja 9; o deslocamento relativo entre y2 e y3 seja 13; o deslocamentorelativo entre y2 e y5 seja 7; o deslocamento relativo entre y3 e y5 seja 20;o deslocamento relativo entre y4 e y5 seja 11. Obtemos assim as seguintesequacoes nas cinco incognitas k1, . . . , k5 (todos os calculos sao efectuadosmod 26):

k1 − k2 = 9

k1 − k5 = 16

k2 − k3 = 13

k2 − k5 = 7

k3 − k5 = 20

k4 − k5 = 11.

Donde

k2 = k1 + 17

k3 = k1 + 4

k4 = k1 + 21

k5 = k1 + 10

Assim, a chave deve ser (k1, k1 + 17, k1 + 4, k1 + 21, k1 + 10), para algum0 ≤ k1 ≤ 25, ou seja, a chave e uma das sequencias AREVK ou BSFWL ouCTGXM. . . . A unica destas sequencias que faz sentido e JANET . Note-seque a palavra passe nao tem que fazer sentido. Nesse caso, podemos experi-mentar qualquer das possıveis chaves ate que uma de um texto com sentido,ou, se quisermos utilizar o computador, verificar qual delas e que correspondea um texto plano que tenha uma analise de frequencias de acordo com a lınguaque esta a ser utilizada. Para a chave JANET Obtemos o texto plano

The almond tree was in tentative blossom. The days were longer,often ending with magnificent evenings of corrugated pink skies.

41

The hunting season was over, with hounds and guns put away forsix months. The vineyards were busy again as the well-organizedfarmers treated their vines and the more lackadaisical neighborshurried to do the pruning they should have done in November.

3.12 Cifra de Hill

Nesta seccao descrevemos outro criptosistema polialfabetico inventado em1929 por Lester S. Hill.

Cifra (Hill). Sejam m e n inteiros positivos. Sejam P = C = (Zm)n e

K = {K ∈ Mn(Zm) : K e invertıvel}. Dada uma chave

K =

k1,1 k1,2 . . . k1,nk2,1 k2,2 . . . k2,n...

......

kn,1 kn,2 . . . kn,n

e x ∈ P e y ∈ C, definimos

eK(x1, x2, . . . , xn) ≡ (x1 x2 . . . xn)K mod m

edK(y1, y2 . . . , yn) ≡ (y1 y2 . . . yn)K

−1 mod m.

Exemplo. Sejam m = 26, n = 2 e

K =

(11 83 7

)Neste caso

K−1 =

(7 1823 11

)Para cifrar o texto plano hill, dividimos primeiro nos dois grupos hi e ll eefectuamos os produtos(

7 8)( 11 8

3 7

)=

(23 8

)e (

11 11)( 11 8

3 7

)=

(24 9

)A mensagem cifrada fica XIYJ.

42

3.13 Ataque a cifra de Hill

A cifra de Hill e mais difıcil de quebrar quando so se conhece a mensagemcifrada, mas sucumbe muito facilmente quando se conhece um texto planoque deu origem a uma mensagem cifrada. Vamos assumir que o oponenteconhece o valor de n (comprimento de cada parte do texto plano a ser cifradaindividualmente) e conhece pelo menos n pares distintos de n-uplos xj =(xj,1, xj,2, . . . , xj,n) e yj = (yj,1, yj,2, . . . , yj,n), tais que yj = eK(xj), com 1 ≤j ≤ n. Sejam X = [xi,j] e Y = [yi,j], entao Y = XK, onde K e a matriz dachave desconhecida. Se X for invertıvel, o oponente pode obter K = X−1Ye quebrar o sistema. Se X nao for invertıvel sera necessario utilizar outros npares.

Exemplo. Suponha que o texto plano friday e cifrado utilizando uma cifrade Hill com n = 2, obtendo-se PQCFKU. Entao temos eK(5, 17) = (15, 16),eK(8, 3) = (2, 5) e eK(0, 24) = (10, 20). Utilizando os dois primeiros pares,obtemos a equacao matricial(

15 162 5

)=

(5 178 3

)K.

Como (5 178 3

)−1

=

(9 12 15

)a chave K e

K =

(9 12 15

)(15 162 5

)=

(7 198 3

).

Podemos utilizar o terceiro par para confirmar este resultado.

Mas pode acontecer (e e provavel que aconteca) que o oponente naoconheca n. Neste caso, ele pode usar este processo utilizando n = 2, 3, . . . ateque a chave seja descoberta. Se um valor de n e incorrecto, entao a matrizK obtida utilizando este algoritmo nao funcionara para outros pares textoplano-texto cifrado. Portanto, n pode ser facilmente determinado.

3.14 Cifra de Permutacao

Ate agora todas as cifras estudadas envolveram substituicoes das letras dotexto plano por letras da mensagem cifrada. A ideia da cifra de permutacao

43

(tambem chamada cifra de transposicao) consiste em nao alterar as letras dotexto plano, mas sim a sua posicao. Este tipo de cifras tem sido utilizadoha centenas de anos, tendo Giovanni Porta notado, ja em 1563, a distincaoentre estas cifras e as cifras de substituicao.

Cifra (Permutacao). Sejam m e n inteiros positivos. Sejam P = C = (Zm)n

e K consiste de todas as permutacoes de {1, . . . , n}. Dada uma chave π ex ∈ P e y ∈ C, definimos

eπ(x1, x2, . . . , xn) ≡ (xπ(1), xπ(2), . . . , xπ(n))

edπ(y1, y2, . . . , yn) ≡ (yπ−1(1), xπ−1(2), . . . , xπ−1(n)),

onde π−1 e a permutacao inversa de π.

A cifra de permutacao e um caso especial da cifra de Hill. A permutacaoπ de {1, . . . , n}, corresponde a matriz de permutacao Kπ cuja entrada (i, j)e 1 se i = π(j) e 0 caso contrario.

3.15 Cifras de Fluxo

Nos varios criptosistemas estudados, a chave K mantem-se fixa e e utilizadapara cifrar os sucessivos blocos de texto plano. Isto e, a mensagem cifrada,y, e obtida da seguinte maneira:

y = y1y2 · · · = eK(x1)eK(x2) · · · .

Estes criptosistemas chamam-se Cifras de bloco. Nesta seccao, vamos estudaruma generalizacao das cifras de bloco, i. e. criptosistemas que usam um fluxode chaves.

Uma cifra de fluxo funciona da seguinte forma: Dada uma chave K ∈ K eum texto plano x1x2 · · · , e gerado um fluxo de chaves, digamos z = z1z2 · · · ,definido por

zi = fi(K,x1, . . . , xi−1)

e a mensagem cifrada e obtida da seguinte forma:

y = y1y2 · · · = ez1(x1)ez2(x2) · · · .

44

Assim, para cifrar o texto plano x1x2 · · · , calcula-se sucessivamente os valoresz1, y1, z2, y2, . . . . Para decifrar y1y2 · · · , calcula-se sucessivamente os valoresz1, x1, z2, x2, . . . .

A formulacao matematica e apresentada a seguir:

Definicao. Uma cifra de fluxo e um heptuplo (P , C,K,L,F , E ,D) satis-fazendo as condicoes seguintes:

1. P e o conjunto finito dos textos planos possıveis;

2. C e o conjunto finito dos textos cifrados possıveis;

3. K e o conjunto finito das chaves;

4. L e o conjunto finito do alfabeto dos fluxos de chaves;

5. F = (f1, f2, . . . ) e o gerador de fluxos de chaves. Para cada i ≥ 1,

fi : K × P i−1 → L.

6. Para cada z ∈ L existe uma regra para cifrar ez ∈ E e uma regra paradecifrar correspondente dz ∈ D, tais que ez : P −→ C, dz : C −→ P edz(ez(x)) = x, para qualquer x ∈ P .

As cifras de bloco sao um caso particular das cifras de fluxo, onde zi = k,para qualquer i ≥ 1. Quando as funcoes fi so dependem da chave K, dizemosque temos uma cifra de fluxo sincronizada. Neste caso, K e a semente que eexpandida para gerar o fluxo z1z2 · · · .

Uma cifra de fluxo e periodica com perıodo d se zi+d = zi, para qualqueri ≥ 1. A cifra de Vegenere pode ser interpretada como uma cifra de fluxosincronizada e periodica, com perıodo n. Neste caso, zi = ki, para 1 ≤ i ≤ n.

Em muitos criptosistemas de fluxo, utiliza-se P = C = L = (Z2)n e cifrar

ou decifrar e adicionar mod 2, o que corresponde a efectuar a operacao do”ou”exclusivo, conhecida como XOR.

3.16 Cifra de Fluxo baseada no LFSR

Um metodo de geracao do fluxo de chaves e o seguinte:

45

Suponhamos que temos uma chave K = (k1, . . . , kn, c0, . . . , cn−1) ∈ K.Definimos zj = kj, para 1 ≤ j ≤ n, e geramos o fluxo de chaves atraves daseguinte recorrencia linear de grau n

zi+n ≡n−1∑j=0

cjzi+j mod 2,

para i ≥ 1.Note que so estamos realmente a cifrar quando (k1, . . . , kn) = (0, . . . , 0).

Se esta hipotese se verificar e se os valores c0, c1, . . . , cm−1 tambem nao saotodos nulos, entao vamos obter uma cifra de fluxo periodica de perıodo 2n−1.Portanto, uma chave inicial ”pequena”da origem a um fluxo de chaves comum perıodo ”grande”.

As cifras A5/1, A5/2, utilizadas nos telemoveis GSM, e a cifra EO, uti-lizada no Bluetooth, sao cifras do tipo LFSR.

Exemplo. Sejam n = 4, K = (1, 0, 0, 0) e o fluxo de chaves gerado por

zi+4 ≡ zi + zi+1 mod 2.

Entao o fluxo de chaves e

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, . . . .

e tem perıodo 15 = 24 − 1.

Este metodo pode ser eficientemente implementado em Hardware uti-lizando um Linear feedback shift register (LFSR).

3.17 Criptoanalise da cifra de fluxo baseada

no LFSR

Vejamos um metodo para quebrar a cifra de fluxo baseada no LFSR, quandose conhece um texto plano e a mensagem cifrada que lhe corresponde. Comovimos, a mensagem cifrada e obtida adicionando o texto plano ao fluxo dechaves modulo 2, i.e. yi = xi + zi. O fluxo de chaves e produzido a partir dachave secreta z1, . . . , zm e as relacoes de recorrencia linear

46

zm+i ≡m−1∑j=0

cjzi+j mod 2,

onde c0, . . . , cm−1 ∈ Z2 e c0 = 1.Suponha que o oponente conhece o texto plano x1, x2, . . . , xn e a men-

sagem cifrada correspondente y1, y2, . . . , yn, entao pode obter os valores zi ≡xi + yi mod 2, para 1 ≤ i ≤ n. Suponhamos que o oponente tambem con-hece o comprimento da chave secreta m. Entao precisa apenas de determinarc0, c1, . . . , cm−1. Como para cada i ≥ 1, temos

zm+i ≡m−1∑j=0

cjzi+j mod 2,

que e uma equacao linear com m incognitas. Se n ≥ 2m entao temos umsistema de equacoes com m equacoes e m incognitas e, portanto, pode serresolvido. A seguinte equacao matricial descreve este sistema de equacoes

(zm+1, zm+2, . . . , z2m) = (c0, c1, . . . , cm−1)

z1 z2 . . . zmz2 z3 . . . zm+1...

......

zm zm+1 . . . z2m−1

.

Pode ser mostrado que a matriz tem inversa se m for o comprimentoda chave secreta (ver exercıcio 1.9, pag 42, em Criptography: Theory andPractice de Douglas Stinson). Neste caso, obtemos

(c0, c1, . . . , cm−1) = (zm+1, zm+2, . . . , z2m)

z1 z2 . . . zmz2 z3 . . . zm+1...

......

zm zm+1 . . . z2m−1

−1

.

Vejamos um exemplo:

Exemplo. Suponhamos que Oscar obtem a mensagem cifrada

101101011110010

47

correspondente ao texto plano

011001111111000.

Entao o fluxo de chaves pode ser obtido somando bit a bit mod 2 os valoresanteriores. Portanto o fluxo de chaves sera

110100100001010.

Entao

(0, 1, 0, 0, 0) = (c1, c2, c3, c4, c5)

1 1 0 1 01 0 1 0 00 1 0 0 11 0 0 1 00 0 1 0 0

Donde, apos calcularmos a inversa da matriz e efectuar os restantes calculos,obtemos (c1, c2, c3, c4, c5) = (1, 0, 0, 1, 0). Portanto, a recorrencia para geraro fluxo de chaves e

zi+5 ≡ zi + zi+3 mod 2.

48

Capıtulo 4

Criptografia de chave publica

Os proximos sistemas criptograficos que iremos estudar ha uma chave paracifrar que e publica, mas a chave para decifrar e secreta e nao pode ser obtidaa partir da chave publica. Antes de descrevermos estes sistemas, necessitamosde recordar alguns resultados de teoria elementar dos numeros.

4.1 Teorema Chines dos Restos

Na seccao 3.6 vimos como resolver congruencias da forma

ax ≡ b mod n.

O proximo resultado diz-nos quando e que um sistema com duas congruenciastem solucao.

Teorema 4.1. Se (m,n) = 1, entao o sistema{x ≡ a mod mx ≡ b mod n

Tem uma e uma so solucao mod mn.

Demonstracao: Um inteiro x satisfaz a primeira equacao se e so seexiste um inteiro t tal que

x = a+mt (4.1)

Agora, a+mt satisfaz a segunda equacao se e so se

mt ≡ b− a mod n. (4.2)

49

Como (m,n) = 1, esta ultima equacao tem uma unica solucao, digamos c, i.e.

t ≡ c mod n.

Portanto, t satisfaz (4.2) se e so se existe um inteiro k tal que t = c + nk.Substituindo em (4.1), verificamos que x e solucao do sistema se e so se

x = a+m(c+ nk)

= (a+mc) +mnk

Logo, a+mc e solucao do sistema e e unica mod mn. 2

Este teorema e um caso especial de um resultado mais geral, que ja eraconhecido dos chineses ha mais de 2000 anos.

Teorema 4.2 (Teorema chines dos restos). Sejam m1, . . . ,mk inteiros posi-tivos que sao primos entre si dois a dois. Entao o sistema

x ≡ a1 mod m1

x ≡ a2 mod m2...x ≡ ak mod mk

tem uma unica solucao mod (m1m2 · · ·mk).

Demonstracao: Iremos usar o teorema 4.1 (k − 1) vezes. Pelo teorema4.1 as duas primeiras equacoes tem uma unica solucao mod (m1m2). Sejab2 esta solucao, i. e.

x ≡ b2 mod m1m2 (4.3)

A terceira equacao ex ≡ a3 mod m3. (4.4)

Como, por hipotese (m1,m3) = (m2,m3) = 1, entao temos (m1m2,m3) = 1(porque?). Para resolver o sistema formado pelas equacoes (4.3) e (4.4),podemos mais uma vez utilizar o teorema 4.1. Portanto, ha uma unicasolucao de (4.3) e (4.4) mod ((m1m2)m3), i. e., ha uma unica solucaodas tres primeiras equacoes mod (m1m2m3). Continuando desta maneira,

50

depois de (k − 1) aplicacoes do teorema 4.1, obtemos uma unica solucaomod (m1m2 · · ·mk) do sistema{

x ≡ bk−1 mod (m1m2 · · ·mk−1)x ≡ ak mod mk

Esta solucao, digamos x ≡ bk mod (m1m2 · · ·mk), e tambem a unica solucaodo sistema inicial mod (m1m2 · · ·mk). 2

O proximo teorema permitir-nos-a encontrar uma solucao do sistemax ≡ a1 mod m1

x ≡ a2 mod m2...x ≡ ak mod mk

sem ter que utilizar diversas vezes o teorema 4.1.

Teorema 4.3. Sejam m1, . . . ,mk inteiros positivos que sao primos entre

si dois a dois. Sejam M = m1m2 · · ·mk, Mi =M

mi

e yi o inverso de Mi

mod mi, para qualquer 1 ≤ i ≤ k. Entao

N = a1M1y1 + a2M2y2 + · · · akMkyk

e a unica solucao mod M do sistemax ≡ a1 mod m1

x ≡ a2 mod m2...x ≡ ak mod mk

Demonstracao: Pelo teorema do resto chines, sabemos que ha umasolucao unica mod M do sistema anterior. Portanto, basta-nos provar queN e essa solucao. Seja 1 ≤ i ≤ k. Como (Mi,mi) = 1, entao, pelo teorema3.6, existe yi tal que Miyi ≡ 1 mod mi. Mais, Mi ≡ 0 mod mj, paraqualquer j = i. Entao

N ≡ a1M1y1 + a2M2y2 + · · · akMkyk mod mi

≡ aiMiyi mod mi

≡ aiMi(Mi)−1 mod mi

≡ ai mod mi

51

Portanto, N e solucao da equacao x ≡ ai mod mi, para qualquer 1 ≤ i ≤ k.Donde, N e a unica solucao do sistema mod M . 2

Exemplo. A primeira mencao conhecida do teorema chines do resto e oseguinte problema extraıdo do livro Sun Tzu Suan Ching (O Manual Matema-tico do Mestre Sun), escrito por Sun Zi, por volta do terceiro seculo a.c.

Temos um certo numero de coisas, mas nao sabemos exactamentequantas sao. Se formarmos grupos de tres, sobram duas. Seformarmos grupos de cinco, sobram tres. Se formarmos gruposde sete, sobram duas. Quantas coisas temos?

Resolver este problema equivale a resolver o sistemax ≡ 2 mod 3x ≡ 3 mod 5x ≡ 2 mod 7

Primeiro iremos usar o processo descrito no teorema do resto chines. Daprimeira equacao obtemos x = 2 + 3t, para algum inteiro t. Substituindo nasegunda equacao, obtemos 2 + 3t ≡ 3 mod 5, donde 3t ≡ 1 mod 5, i. e.t ≡ 2 mod 5. Portanto, t = 2 + 5k, para algum inteiro k, e

x = 2 + 3(2 + 5k) = 8 + 15k.

Substituindo este valor na terceira equacao, obtemos

8 + 15k ≡ 2 mod 7.

Como 8 ≡ 15 ≡ 1 mod 7, resulta que k ≡ 1 mod 7. Assim, k = 1 + 7s,para algum inteiro s. Portanto

x = 8 + 15(1 + 7s) = 23 + 105s.

Provamos que qualquer solucao do sistema e da forma 23 + 105s, para sinteiro, e a unica solucao mod (3 · 5 · 7) e 23.

Agora usamos o metodo descrito no teorema anterior. Aqui M = 105,M1 = 35, M2 = 21 e M3 = 15. O inverso de 35 mod 3 e y1 = −1, o inversode 21 mod 5 e y2 = 1 e o inverso de 15 mod 7 e y3 = 1. Portanto,

N = 2 · 35 · (−1) + 3 · 21 · 1 + 2 · 15 · 1 = 23

52

4.2 Lagrange, Euler e Fermat

Seja G um grupo multiplicativo, definimos ordem de um elemento g ∈ Gcomo sendo o menor inteiro positivo m tal que gm = 1. Se G = (Z∗

n, ·) entaoG tem φ(n) elementos e, neste caso, definimos ordem de um elemento daseguinte maneira:

Definicao. Suponhamos que (a, n) = 1. Definimos a ordem de a mod ncomo sendo o menor inteiro positivo, digamos b, para o qual

ab ≡ 1 mod n

e denota-mo-lo por ordn(a).

Por exemplo, ord13(5) = 4, pois

51 ≡ 5 mod 13

52 ≡ −1 mod 13

53 ≡ −5 mod 13

54 ≡ 1 mod 13

Recordemos os famosos resultados:

Teorema 4.4 (Lagrange). Suponha que G e um grupo multiplicativo com nelementos e seja g ∈ G. Entao a ordem de g divide n.

Teorema 4.5 (Fermat). Se p e primo entao bp ≡ b mod p

Teorema 4.6 (Euler). Se (b, n) = 1 entao

bφ(n) ≡ 1 mod n.

4.3 Raızes primitivas

Quando p e primo, o grupo (Z∗n, ·) e cıclico e os elementos que geram este

grupo sao muito importantes em criptografia. Recordemos o nome desteselementos e um resultado que nos diz quantos existem.

Definicao. Se (a, n) = 1 e ordn(a) = φ(n) dizemos que a e uma raız primi-tiva de n.

Teorema 4.7. Seja p um primo e d | (p − 1). Entao ha exactamente φ(d)inteiros distintos mod p cuja ordem mod p e d. Em particular, ha exac-tamente φ(p− 1) raızes primitivas de p.

53

4.4 Exponenciacao modular rapida

Antes de passar ao sistema RSA e outros sistemas de chave publica necessita-mos ainda de um algoritmo que nos permita fazer exponenciacoes modularesrapidas.

Teorema 4.8. Sejam n,m e b inteiros, com b < m. Entao

tempo(bn mod m) = O(log n log2m)

Por um exercıcio, calcular bn demora O(n2 log2 b) operacoes bit. Pode-mos determinar bn mod m dividindo bn por m o que nos da O(n log b logm)operacoes bit. Portanto, no total terıamos

O(n2 log2 b) +O(n log b logm)

operacoes bit. Este valor e exageradamente superior a O(log n log2 m) se mnao for muito superior a n, portanto temos que utilizar um algoritmo muitomais rapido que o indicado para calcular bn. Uma das ideias deste algoritmoe nunca trabalhar com numeros muito grandes, i. e. sempre que fizermosuma multiplicacao, reduziremos logo de seguida o resultado mod m. Assim,os inteiros envolvidos nos nossos calculos nunca serao maiores que m2.

Demonstracao: Denotamos por a o produto parcial. Quando o algo-ritmo terminar, teremos a ≡ bn mod m. Comecamos por tomar a = 1 e sejan = (nk−1 · · ·n1n0)2 a representacao de n na base 2, onde k e o numero debits de n.

Se n0 = 1, entao tomar a = b, caso contrario a = 1. A seguir calculamosb2 e seja b1 = b2 mod m.

Se n1 = 1, a passa a ser ab1 mod m, caso contrario a nao e alterado.Seja b2 = b21 mod m.

Se n2 = 1, a passa a ser ab2 mod m, caso contrario a nao e alterado.Continuando desta maneira, temos, no passo j, bj ≡ b2

jmod m, com

bj < m. Se nj = 1, i. e. se 2j aparece na expansao binaria de n, entaoincluımos bj no produto para a, caso contrario, nao incluımos bj. Depois dek − 1 passos, obtemos

a ≡ bn0+n12+···nk−12k−1 ≡ bn mod m.

Em cada passo temos uma multiplicacao e uma divisao, se nj = 0, ou duasmultiplicacoes e duas divisoes se nj = 1, de numeros menores que m2. Por-tanto, cada passo demora O(log2 m2) = O(log2m) operacoes bit. Como

54

temos O(log n) passos, obtemos

tempo(bn mod m) = O(log n log2m).

2

4.5 RSA

O RSA foi inventado por Ron Rivest, Adi Shamir, e Leonard Adleman, noMIT, em 1977.

Sejam p = q dois primos grandes e seja n = pq. Ja vimos que φ(n) =(p − 1)(q − 1). Seja e um inteiro que e primo com φ(n). Os numeros n e esao publicados, daı o nome de criptosistema de chave publica. A mensagema cifrar deve ser um numero P ≤ n. A mensagem cifrada sera o unico inteiro0 < C < n tal que

C ≡ P e mod n.

E importante notar que p, q e φ(n) sao mantidos secretos. Como sabemosφ(n), podemos usar o algoritmo de Euclides para encontrar um numero d talque

ed ≡ 1 mod φ(n),

i. e. ed = 1+φ(n)k, para algum inteiro k. Para decifrar a mensagem, bastacalcular o menor resıduo nao negativo de

Cd mod n.

Vejamos porque:Se (P, n) = 1, o teorema de Euler diz-nos que

Cd ≡ P ed ≡ P 1+φ(n)k ≡ P mod n

Se (P, n) = 1 entao (P, n) = p ou (P, n) = q. Suponhamos que (P, n) = p.Entao (P, q) = 1, donde{

Cd ≡ P ed ≡ 0 mod pCd ≡ P ed ≡ P 1+φ(n)k ≡ P × (P q−1)(p−1)k ≡ P mod q

55

Pelo teorema chines dos restos, Cd ≡ P mod n.Portanto, para alguem decifrar a mensagem, ele tem que conhecer d e

n. Nao basta saber e e n. Para calcular d ele tem de saber φ(n), o querequer um conhecimento dos primos p e q. Ou seja, tem de saber factorizarn. Se os primos p e q forem suficientemente grandes (por exemplo, milharesde algarismos, cada um), entao, com os mais potentes computadores e oconhecimento matematico actual, e impossıvel descobrir os factores de nnum perıodo de tempo menor que um milhao de anos. Quem sabe p e q podecalcular φ(n), mas um oponente que queira decifrar a mensagem, falhara,pois nao sabe os primos nem uma maneira rapida de factorizar n.

Suponha que o alfabeto tem N letras, e n = pq, seja k tal que Nk < n <Nk+1. Costuma-se codificar as mensagens originais em blocos de k letras,mas descodifica-se as mensagens cifradas em blocos de k + 1 letras. Destemodo qualquer mensagem pode ser codificada e qualquer mensagem cifradapode ser descodificada.

Exemplo. Considere n = 466883 e e = 139. Decifre ”IMYMLYJCNLSK”e”LICASWZEKTIU”.

No sistema RSA, so a chave para decifrar d deve ser mantida secreta. Achave para cifrar e e o modulo n podem ser publicados. Com os conheci-mentos actuais e impraticavel obter d sabendo e e n. Portanto, pode haveruma lista publica (tipo lista telefonica) com o nome de cada utilizador, o seumodulo n e o expoente publico e (esta chave e usualmente a mesma paravarios utilizadores, devendo ser relativamente pequena para tornar o sistemaeficiente).

Para que a fatorizacao do modulo n seja impraticavel os factores primosde n devem ser escolhidos apropriadamente. Devido a forca dos algoritmosactuais para factorizar inteiros, p e q devem ter aproximadamente o mesmonumero de bits (mas nao demasiado proximos), e com pelo menos 512 bits.Se para um dos factores p, p− 1 tiver so factores primos ”pequenos”, entaoo metodo de fatorizacao ”p− 1”ira permitir factorizar n.

4.5.1 Ataque do expoente publico pequeno

A chave de cifrar e deve ser escolhida o mais pequena possıvel, de modo a fazera cifra eficiente. A escolha e = 2 e impossıvel porque φ(n) = (p−1)(q−1) quee par. Portanto, a menor chave de cifrar possıvel e e = 3. Porem, pode serperigoso usar chaves de cifrar demasiado pequenas, porque o inimigo pode

56

usar o ”ataque do expoente pequeno”: Este ataque funciona se a mesmamensagem M e cifrada e vezes, usando sempre a chave de cifrar e e usando emodulos ni primos dois a dois. Por exemplo, um banco pode enviar a mesmamensagem M a alguns dos seus clientes usando os diferentes modulos RSAdestes clientes e sempre o mesmo e. Em seguida mostramos como este ataquefunciona. Sejam ci = ne mod ni, 1 ≤ i ≤ e as correspondentes mensagenscifradas. Entao o inimigo usa o seguinte algoritmo:

1. Calcular um inteiro c tal que c ≡ ci mod ni, onde 1 ≤ i ≤ e e 1 ≤ c ≤n1n2 · · ·ne, usando o teorema chines dos restos.

2. Determinar a raiz e de c, que vai ser M .

Para verificar que este algoritmo realmente funciona, basta notar que ointeiro u = M e e menor que n1n2 · · ·ne (porque M < ni) e que claramenteverifica as congruencias u ≡ ci mod ni. Donde c = u, pelo teorema chinesdos restos (ha unicidade de solucao mod (n1 · · ·ne)), e portanto e

√c = M .

A raiz e de c pode ser calculada de um modo eficiente (por exemplo,usando um generalizacao do algoritmo para obter a raiz quadrada). Portanto,o ataque do expoente pequeno pode ser realmente eficiente. Porem, estemetodo falha se as mensagens originais forem diferentes, e isto pode serobtido se acrescentarmos a mensagem original alguns bits de texto aleatorios.Podemos tambem usar um maior expoente para cifrar. Um valor muitoutilizado e e = 216 + 1.

4.6 Resıduos quadraticos

Sejam p primo ımpar e a um inteiro, tais que p - a. Seja 1 ≤ x ≤ p − 1entao so um dos inteiros x, 2x, . . . , (p−1)x e congruente com a mod p. Ha,portanto, um unico x′ tal que

xx′ ≡ a mod p

com 1 ≤ x′ ≤ p − 1. Dizemos que x′ esta associado a x. Ha duas possibili-dades, ou existe pelo menos um 1 ≤ x ≤ p−1, que esta associado a si mesmoou nao existe tal inteiro. Vamos analisar cada caso.

1. Suponhamos que ha um inteiro x1 que esta associado a si mesmo. Entaoa congruencia

x2 ≡ a mod p (4.5)

57

tem a solucao x = x1. Neste caso, dizemos que a e um resıduoquadratico de p. Claramente, p− x1 e outra solucao de (4.5). Mais, sex2 e outra solucao de (4.5), entao

x21 − x2

2 ≡ 0 mod p

donde,(x1 − x2)(x1 + x2) ≡ 0 mod p.

Logo, x1 ≡ x2 mod p ou x1 ≡ −x2 ≡ p − x2 mod p. Portanto, aequacao (4.5) so tem duas solucoes, que sao x1 e p − x1. Podemosentao agrupar os inteiros

1, 2, . . . , p− 1

emp− 3

2pares de inteiros associados e diferentes, sobrando x1 e p−x1

que estao associados a si proprios. Temos

x1(p− x1) ≡ −x21 ≡ −a mod p

e, para cada par de associados x e x′,

xx′ ≡ a mod p.

Entao

(p− 1)! =

p−1∏i=1

i ≡ −a · ap−32 ≡ −a

p−12 mod p.

2. Se nao ha qualquer inteiro que esteja associado a si proprio, dizemosque a e um nao-resıduo quadratico de p. Neste caso, a equacao (4.5)nao tem solucoes e os inteiros

1, 2, . . . , p− 1

podem ser agrupados emp− 1

2pares de inteiros associados diferentes.

Portanto,

(p− 1)! =

p−1∏i=1

i ≡ ap−12 mod p.

58

Seja p um primo ımpar e a um qualquer inteiro nao divisıvel por p. Definimos

o sımbolo de Legendre

(a

p

), da seguinte maneira

(a

p

)=

{1 se a e um resıduo quadratico de p−1 se a e um nao-resıduo quadratico de p

Claramente,

(a

p

)=

(b

p

)se a ≡ b mod p. Acabamos de provar o seguinte

teorema:

Teorema 4.9. Se p e um primo ımpar e a nao e multiplo de p, entao

(p− 1)! ≡ −(a

p

)a

p−12 mod p.

Os dois casos mais simples deste teorema sao a = 1 e a = −1. Como aequacao x2 ≡ 1 mod p tem as solucoes 1 e −1, entao(

1

p

)= 1

para qualquer primo ımpar. O proximo teorema e baseado neste exemplo

Teorema 4.10 (Wilson). Seja p primo, entao

(p− 1)! ≡ −1 mod p

Demonstracao: Se p e ımpar entao(1

p

)= 1

Logo, considerando a = 1 no teorema anterior, obtemos o resultado enunci-ado. Se p = 2, entao (p− 1)! = 1, donde (p− 1)! ≡ −1 mod 2. 2

Juntando os dois resultados anteriores, obtemos um processo para calcularo sımbolo de Legendre:

59

Teorema 4.11 (Lema de Euler). Sejam p um primo ımpar e a um inteirotais que p - a. Entao (

a

p

)= a

p−12 mod p.

Ao contrario do teorema de Fermat, o recıproco do teorema de Wilsontambem e valido, obtendo-se um teste de primalidade.

Teorema 4.12. Seja m > 1. Entao m e primo se e so se

(m− 1)! ≡ −1 mod m

Demonstracao: Atendendo ao resultado anterior, basta-nos considerarm > 1 composto. Entao existe um inteiro 1 < d < m tal que d | m. Masentao d | (m− 1)!. Logo, d - ((m− 1)! + 1). Donde, m - ((m− 1)! + 1). 2

Infelizmente, este teorema parece ser inutil para verificar na pratica seum numero e primo ou nao.

Em seguida consideramos o caso a = −1.

Teorema 4.13. O inteiro −1 e um resıduo quadratico para os primos daforma 4k + 1 e um nao-resıduo quadratico para os primos da forma 4k + 3,i. e. (

−1

p

)= (−1)

p−12 .

Demonstracao: Resulta imediatamente do teorema 4.11. 2

Em seguida, vamos introduzir outra caracterizacao do sımbolo de Legen-dre, obtida por Gauss.

Seja p um primo ımpar e consideremos o conjunto dos resıduos mınimos:

S = {−p− 1

2,−p− 3

2, . . . ,−2,−1, 1, 2, . . . ,

p− 1

2}.

Seja (a, p) = 1 e seja µ o numero de resıduos mınimos negativos dos inteirosa, 2a, 3a, dotsap−1

2. Por exemplo, seja p = 7 e a = 4. Entao

1 ∗ 4 ≡ −3 mod 7

2 ∗ 4 ≡ 1 mod 7

3 ∗ 4 ≡ −2 mod 7

60

Portanto, neste caso, µ = 2. Os valores de µ irao permitir-nos obter uma

caracterizacao simples de(

ap

).

Lema 4.14 (Lema de Gauss).(

ap

)= (−1)µ.

Demonstracao: Seja ±ml o resıduo mınimo de la, onde ml e positivo.Claramente, µ e o numero de ocorrencias do sinal negativo, quando l tomavalores entre 1 e (p − 1)/2. Note que, se 1 ≤ l < k ≤ (p − 1)/2, entaoml = mk. Suponhamos que ml = mk. Entao

la ≡ ±ka mod p.

Como p - a, temos l ≡ ±k mod p. Mas esta congruencia e impossıvel,porque l = k e

|l ± k| ≤ l + k ≤ p− 1.

Portanto, os conjuntos {1, 2, . . . , (p − 1)/2} e {m1,m2, . . . ,m(p−1)/2} coinci-dem. Multiplicando as congruencias

1a ≡ ±m1 mod p

2a ≡ ±m2 mod p

...

p− 1

2a ≡ ±m p−1

2mod p

obtemos (p− 1

2

)!a

p−12 ≡ (−1)µ

(p− 1

2

)! mod p.

Portanto,

ap−12 ≡ (−1)µ mod p.

Pelo teorema 4.11, obtemos o resultado pretendido. 2

Este resultado, permite-nos, por exemplo, saber para que primos, 2 e umresıduo quadratico.

61

Teorema 4.15. O inteiro 2 e um resıduo quadratico para os primos da forma8k+1 e 8k− 1 e um nao-resıduo quadratico para os primos da forma 8k+3e 8k + 5, i. e. (

2

p

)= (−1)

p2−18 .

Demonstracao: Seja p um primo ımpar. Note que µ e igual ao numerode elementos do conjunto T = {2, 4, 6, 8, . . . , p− 1} que sao maiores que p−1

2.

Se p = 8k + 1 entao (p − 1)/2 = 4k e ha 2k elementos de T menores ouiguais a (p− 1)/2 e 2k elementos maiores que (p− 1)/2. Portanto, µ e par e2 e um resıduo quadratico de p.

Se p = 8k−1 entao (p−1)/2 = 4k−1 e ha 2k−1 elementos de T menoresou iguais a (p − 1)/2 e 2k elementos maiores que (p − 1)/2. Portanto, µ epar e 2 e um resıduo quadratico de p.

Se p = 8k + 3 entao (p− 1)/2 = 4k + 1 e ha 2k elementos de T menoresou iguais a (p− 1)/2 e 2k + 1 elementos maiores que (p− 1)/2. Portanto, µe ımpar e 2 e um nao-resıduo quadratico de p.

Se p = 8k+5 entao (p−1)/2 = 4k+2 e ha 2k+1 elementos de T menoresou iguais a (p− 1)/2 e 2k + 1 elementos maiores que (p− 1)/2. Portanto, µe ımpar e 2 e um nao-resıduo quadratico de p. 2

Os numeros 12, 22, 32, . . .

(p− 1

2

)2

, sao todos incongruentes mod p, pois

ser2 ≡ s2 mod p

entao r ≡ s mod p ou r ≡ −s mod p, e a segunda alternativa e impossıvel.Mais,

r2 ≡ (p− r)2 mod p,

portanto, se p for ımpar, hap− 1

2resıduos quadraticos e

p− 1

2nao-resıduos

quadraticos de p.

Teorema 4.16. Seja p um primo ımpar. O produto de dois resıduos quadra-ticos de p ou de dois nao-resıduos quadraticos de p e um resıduo quadraticode p, enquanto que o produto de um resıduo quadratico com um nao-resıduoquadratico e um nao-resıduo quadratico. Isto e,(

a

p

)(b

p

)=

(ab

p

)62

Demonstracao: Pelo teorema 4.11,(a

p

)(b

p

)≡ a

p−12 b

p−12 mod p

= (ab)p−12 mod p

=

(ab

p

)mod p

Donde, (a

p

)(b

p

)=

(ab

p

)2

Sejam p e q dois primos ımpar distintos. Se q e um resıduo quadratico dep, entao a congruencia

x2 ≡ q mod p

e soluvel. Analogamente, se p e um resıduo quadratico de q, entao a con-gruencia

x2 ≡ p mod q

tambem e soluvel. Nao parece haver qualquer conexao obvia entre estasduas congruencias. Uma das grandes descobertas da matematica efectuadasno seculo XVIII e que, de facto, ha uma relacao poderosa e subtil entre ascongruencias mencionadas, que depende apenas de p mod 4 e de q mod 4.Esta e a celebrada lei da reciprocidade quadratica de Gauss. Iremos enun-ciar este resultado e ver alguns exemplos, no entanto, nao provaremos esteresultado, pois seria demasiado pesada para esta introducao a Teoria dosNumeros.

Teorema 4.17. Sejam p e q primos ımpar distintos. Se p ≡ 1 mod 4 ouq ≡ 1 mod 4 entao p e um resıduo quadratico mod q se e so se q e umresıduo quadratico mod p. Se p ≡ q ≡ 3 mod 4, entao p e um resıduoquadratico mod q se e so se q e um nao-resıduo quadratico mod p. Isto e(

p

q

)(q

p

)= (−1)

p−12

q−12

63

Exemplo. A lei da reciprocidade quadratica da-nos um metodo efectivo paracalcular o valor do sımbolo de Legendre. Por exemplo, como

7 ≡ 59 ≡ 3 mod 4,

e 59 ≡ 3 mod 7 temos (7

59

)= −

(59

7

)= −

(3

7

)=

(7

3

)=

(1

3

)= 1

Portanto, 7 e um resıduo quadratico de 59.

Exemplo. Como 51 = 3 · 17 e 97 ≡ 17 ≡ 1 mod 4, temos(51

97

)=

(3

97

)(17

97

)=

(97

3

)(97

17

)=

(1

3

)(12

17

)=

(2

17

)2(3

17

)=

(17

3

)=

(−1

3

)= (−1)

3−12

= −1

64

Exemplo. A lei da reciprocidade quadratica tambem nos permite determinartodos os primos p para os quais um dado inteiro a e um resıduo quadratico.Por exemplo, se a = 5, entao(

5

p

)=

(p5

)=

{1 se p ≡ 1, 4 mod 5−1 se p ≡ 2, 3 mod 5

4.7 Algoritmo de Tonelli-Shanks

Teorema 4.18. Seja p um numero primo tal que p ≡ 3 mod 4. Seja a uminteiro que e um quadrado mod p (i. e., existe b tal que a ≡ b2 mod p).

Entao ap+14 e a raiz quadrada de a mod p.

Demonstracao: Se a ≡ 0 mod p entao, claramente, ap+14 e a raiz

quadrada de a mod p. Suponhamos que a ≡ 0 mod p, entao b ≡ 0 mod p.Como p ≡ 3 mod 4, temos que p+1

4e um inteiro. Basta-nos provar que o

quadrado de ap+14 e congruente com a mod p. Temos

(ap+14 )2 ≡ a× a

p−12 ≡ a

(a

p

)≡ a mod p,

pelo Lema de Euler. 2

Embora o teorema anterior mostre que a determinacao de raızes quadradasmod p e muito simples quando p ≡ 3 mod 4, estas podem tambem ser calcu-ladas qualquer primo ımpar, atraves do seguinte algoritmo, conhecido comoalgoritmo de Tonelli-Shanks.

Dado p primo ımpar e n um resıduo quadratico de p, pretende-se deter-minar uma solucao da congruencia x2 ≡ n mod p.

1. Sejam d e s inteiros positivos tais que m e ımpar e p − 1 = d2s, istoe, divida-se p− 1 por 2 tantas vezes quantas for possıvel (e denotamosesse numero de vezes por s), sendo d o resultado final.

2. Sejam r ≡ nd+12 mod p, t ≡ nd mod p e s′ = s.

3. Determinar um nao-resıduo quadratico de p, que denotamos por z. Sejac ≡ zd mod p.

65

4. Se t ≡ 1 mod p entao r2 ≡ n mod p e, portanto, r e uma das raızesquadradas de n. O algoritmo termina.

5. Caso contrario, determinar o menor i, com 1 ≤ i < s′, tal que t2i ≡ 1

mod p.

6. Seja b ≡ c2s′−i−1

mod p, r passa a ser rb mod p, t passa a ser tb2

mod p, c passa a ser b2 mod p e s′ passa a ser i. Voltar ao passo 4.

Nota: Se p ≡ 3 mod 4, obtem-se nd ≡ np−12 ≡ 1 mod p, pelo lema de

Euler, portanto o passo 4. da a solucao mencionada no teorema anterior,

nd+12 ≡ n

p+14 mod p.

Como n e um resıduo quadratico mod p, tem-se

t2s′−1 ≡ n

p−12 ≡ 1 mod p,

o que garante a existencia de i nas condicoes indicadas no passo 5.Note-se que em cada iteracao do ciclo, tem-se r2 ≡ nt mod p, portanto

se t ≡ 1 mod p entao r e uma das raızes quadradas de n.Como z e um nao-resıduo quadratico entao a ordem de c mod p e 2s o

que implica que a ordem de b2 mod p e 2i. Como a ordem de t tambemera 2i, o novo t vai ter ordem 2j com j < i. Este facto, garante-nos que oalgoritmo vai ter de parar.

Exemplo. Vamos determinar a raiz quadrada de 143 mod 193. Como 193−1 = 26 · 3, temos d = 3 e s = 6. Entao r1 ≡ 143

3+12 ≡ 184 mod 193 e

t1 ≡ 1433 ≡ 64 ≡ 1 mod 193.Um nao-resıduo quadratico de 193 e 5. Assim c1 ≡ 53 ≡ 125 mod 193. A

ordem de t mod 193 e 24, portanto, i1 = 4. Obtemos assim, b1 ≡ 12526−4−1 ≡

185 mod 193, r2 ≡ 184 · 185 ≡ 72 mod 193, c2 ≡ 1852 ≡ 64 mod 193,t2 ≡ 64 · 64 ≡ 43 mod 193 e s′2 = 4.

Continuando desta forma, obtemos as sequencias (r1, r2, r3, r4, r5) = (184, 72, 169, 126, 23)e (t1, t2, t3, t4, t5) = (64, 43, 112,−1, 1). Portanto 232 ≡ 143 mod 193.

4.8 Cifra de Rabin

Ha vantagens em utilizar criptosistemas cuja seguranca seja baseada na di-ficuldade de um problema matematico que tambem tenha interesse fora da

66

criptografia. Qualquer progresso significante para resolver este problema erapidamente tornado publico, porque havera muitos matematicos a trabalharneste problema, sem estarem preocupados com a sua relevancia criptografica,sendo assim difıcil manter secreto o progresso que e feito sobre este problemaparticular. Assim, evita-se (em princıpio) que alguem secretamente quebre ocriptosistema e que tire vantagens de outros ainda usarem um ciptosistemaque nao e mais seguro. Claro que nao ha maneira de saber com certeza ab-soluta se, por exemplo, alguem ja descobriu um metodo eficaz de atacar oRSA, talvez mesmo sem saber um algoritmo rapido para factorizar inteiros.

Ate agora nunca foi provado que quebrar o RSA e tao difıcil como fac-torizar inteiros. O sistema de Rabin, tambem e baseado na dificuldade quefactorizar inteiros, mas em contraste com o RSA, pode ser mostrado quealguem que quebre o sistema de Rabin, pode tambem factorizar inteiros deuma maneira eficiente (e portanto, pode tambem quebrar o RSA).

Tal como no RSA, precisamos de dois primos grandes p e q, so que nestesistema costuma-se impor a condicao adicional p, q ≡ 3 mod 4, para simpli-ficar os calculos. Note-se que o sistema funciona mesmo que os primos quenao verifiquem esta condicao. A chave publica da Alice e n = pq, a chaveprivada e o par (p, q). O espaco das mensagens originais e {0, 1, . . . , n− 1}.Para cifrar a mensagem m ∈ {0, 1, . . . , n− 1}, Bob determina

c ≡ m2 mod n

Para decifrar a mensagem, Alice so tem que determinar a raiz quadradade c.

Para recuperar a mensagem original m da mensagem cifrada c, Alicedetermina

mp ≡ cp+14 mod p e mq ≡ c

q+14 mod q.

Assim ±mp sao as duas raızes quadradas de c mod p e ±mq sao as duasraızes quadradas de c mod q. Usando o teorema chines do resto, obtem-sequatro inteiros x1, x2, x3 e x4 cujo quadrado e congruente com c mod p e umdeles e a mensagem original m.

Ha varios metodos para escolher a mensagem original das quatro raızesquadradas de c mod n. Por exemplo, Alice pode escolher aquela que fazsentido apos ter sido descodificada. Por vezes este metodo nao funciona: porexemplo, se a mensagem enviada e uma chave de um sistema criptograficoclassico (tambem conhecido por sistema simetrico, i. e. onde nao ha chaves

67

publicas). Se Bob cifrar apenas mensagens com uma certa forma, por exem-plo, os primeiros 64 bits sao iguais aos ultimos 64 bits, e pouco provavel quemais de uma das raızes quadradas tenha esta forma. Basta entao escolher araiz quadrada que tem esta forma. Note-se que se e escolhido este metodopara recuperar a mensagem original, a equivalencia entre quebrar o sistemade Rabin e factorizar inteiros, deixa de existir. Depois de ilustrarmos estesistema com um exemplo simples, provaremos esta equivalencia.

Exemplo. Alice usa os numeros primos p = 11 e q = 23. Entao n = 253.Bob cifra a mensagem m = 158 calculando

c ≡ m2 mod n.

Verifica-se que c = 170. Alice calcula

mp ≡ cp+14 mod p e mq ≡ c

q+14 mod q,

obtendo mp = 4 e mq = 3. Usando o teorema chines do resto, Alice obtemquatro raızes quadradas de c mod n, que sao 26, 95, 158, 227, uma delas e amensagem original.

Teorema 4.19. Quebrar o sistema Rabin e tao difıcil como factorizar in-teiros. Por outras palavras, se alguem descobrir um algoritmo que quebreo sistema de Rabin, ele pode usar este algoritmo para factorizar inteiros deuma maneira eficiente.

Demonstracao: Claramente, qualquer pessoa que consiga factorizar n ,consegue tambem quebrar o sistema de Rabin. Suponhamos agora que Olgadescobriu um algoritmo, R, para quebrar o sistema de Rabin. Seja n, omodulo publico, e sejam p e q, os seus factores primos. Dada uma mensagemcifrada c mod n, Olga obtem m = R(c). Portanto, dado um quadradoc mod n, o algoritmo R, permite determinarmos uma raiz quadrada de cmod n. Vejamos como podemos usar este algoritmo para factorizar n: Olgaescolhe, aleatoriamente, um inteiro 1 ≤ x ≤ n − 1. Se (n, x) = d = 1 entaod e um factor de n e a factorizacao de n esta encontrada (n = d · n

d). Caso

contrario, Olga determina

c = x2 mod n e m = R(c).

Sabemos que m e uma das raızes quadradas, mod n, de c, tal como x, masnao e necessariamente igual a x. No entanto, m satisfaz um dos seguintes

68

pares de congruencias:

m ≡ x mod p e m ≡ x mod q

m ≡ x mod p e m ≡ −x mod q

m ≡ −x mod p e m ≡ x mod q

m ≡ −x mod p e m ≡ −x mod q

No primeiro caso, m = x e (m− x, n) = n; no segundo caso, (m− x, n) = p;no terceiro caso, (m − x, n) = q e no ultimo caso, m = n − x e, como(n, x) = 1, obtemos (m− x, n) = 1. Portanto, este procedimento factoriza ncom 50% de probabilidade. Depois de aplicarmos este procedimento k vezes,n e factorizado com probabilidade 1− (1/2)k. 2

Exemplo. Seja n = 253. Suponhamos que Olga consegue determinar raızesquadradas mod 253 com o seu algoritmo R. Ela selecciona, x = 17 eobtem (17, 253) = 1. Depois calcula c ≡ 172 ≡ 36 mod 253. As raızesquadradas de 36 mod 253 sao 6, 17, 236 e 247. Temos (6 − 17, 253) = 11e (247 − 17, 253) = 23, portanto, se o algoritmo R obteve 6 ou 247 entaoOlga encontrou a factorizacao de 253, caso contrario, Olga escolhe outro in-teiro x e aplica o procedimento outra vez. Depois de poucas aplicacoes emuito provavel que Olga tenha encontrado a factorizacao de n sem demorardemasiado tempo.

4.9 Protocolo Diffie-Hellman

Nesta seccao, e descrito o protocolo de Diffie e Helman para troca de chavessecretas atraves de canais inseguros. Este protocolo nao e um sistema crip-tografico, mas serve de base ao sistema criptografico ElGamal, que descrever-emos na proxima seccao.

Temos a seguinte situacao: Alice e Bob pretendem usar um sistemasimetrico para a sua comunicacao atraves de um canal inseguro. Primeirotem que trocar uma chave secreta que ambos irao utilizar. O sistema de trocade chaves Diffie-Hellman, permite que Alice e Bob troquem as suas chaves emesmo que alguem intercepte esta troca de chaves, a informacao obtida naopode ser usada para construir a chave secreta.

69

O sistema de troca de chaves Diffie-Hellman utiliza um outro problemadifıcil de teoria dos numeros, nomeadamente o problema do logaritmo dis-creto. Comecemos por descrever este problema:

Seja p um numero primo e seja g uma raiz primitiva de p. Entao g gerao grupo cıclico (Z/pZ)∗. Portanto, para qualquer 1 ≤ A ≤ p − 1, existe0 ≤ a ≤ p− 2 tal que

A ≡ ga mod p

a a chamamos o logaritmo discreto de A na base g. A determinacao delogaritmos discretos e considerado um problema difıcil. Ate agora, nao existenenhum algoritmo eficiente para resolver este problema.

Voltemos ao protocolo de Diffie-Hellman. Primeiro, Alice e Bob chegam aacordo sobre um primo p grande e uma raiz primitiva de p, digamos g. Tantop como g podem ser publicos. Em seguida, Alice escolhe aleatoriamente uminteiro 0 ≤ a ≤ p − 2 e envia A ≡ ga mod p para Bob. O expoente a emantido secreto. Analogamente, Bob escolhe aleatoriamente 0 ≤ b ≤ p − 2,e envia B ≡ gb mod p para Alice. Tambem b e mantido secreto. Para obtera chave secreta comum, Alice calcula

Ba ≡ gab mod p

e Bob calculaAb ≡ gab mod p.

A chave secreta e k ≡ gab mod p.O inimigo Orlando, conhece os inteiros p, g, A e B, mas nao conhece os

logaritmos discretos a de A e b de B na base g. Portanto, ele conhece ga

mod p e gb mod p e gostaria de conhecer gab mod p. Ate agora, nunca foiencontrado um algoritmo que permita obter k, sabendo A e B. O unicoprocesso conhecido para quebrar o protocolo de Diffie-Hellman e conseguirprimeiro determinar os logaritmos discretos de A e de B, e os algoritmosexistentes para resolver este problema sao pouco eficientes (demoram muito).

4.9.1 Ataque do homem no meio

Existe um ataque a este protocolo que explora o facto de Alice nao poderverificar que as mensagens que recebe vem de facto de Bob. Este ataquechama-se o ataque do homem no meio. Orlando intercepta todas as men-sagens entre Alice e Bob. Faz-se passar por Bob e troca uma chave com

70

Alice e faz-se passar por Alice e troca uma chave com Bob. Sempre queBob envia uma mensagem cifrada a Alice, usa a chave que tinha trocadocom Orlando, pensando que esta a usar a chave de Alice. Orlando recebe amensagem e decifra-a, depois altera esta mensagem (ou nao) e envia-a paraAlice usando a chave que tinha trocado com ela.

Para prevenir este tipo de ataques, podem ser usadas assinaturas. Esteassunto sera tratado mais tarde.

4.10 Sistema ElGamal

Este sistema usa o facto de ser difıcil obter logaritmos discretos, tal como oprotocolo de Diffie-Hellman.

Alice escolhe um numero primo p e uma raiz primitiva g mod p. Depois,Alice escolhe 0 ≤ a ≤ p− 2 aleatoriamente e calcula

A ≡ ga mod p.

A chave publica de Alice e o terno (p, g, A). A sua chave secreta e o expo-nente a. O inteiro A e a parte da chave, proveniente do protocolo de Diffie-Hellman, que pertence a Alice. O espaco de mensagens originais e o conjunto{0, 1, . . . , p − 1}. Para cifrar uma mensagem e envia-la para Alice, Bob usaa chave publica de Alice, (p, g, A). Escolhe um inteiro b ∈ {1, . . . , p − 2} ecalcula

B ≡ gb mod p.

O inteiro B e a parte da chave, proveniente do protocolo de Diffie-Hellman,que pertence a Bob. Para cifrar a mensagem m, Bob calcula

c ≡ Abm mod p.

Bob envia a Alice o par (B, c). Note que B depende da chave publica deAlice (depende de A, g e p escolhidos por Alice) e, portanto nao faz parte dachave publica de Bob, i. e. da chave que Bob usa para receber mensagens.Na sua chave publica, Bob tem provavelmente outro primo q e outra raizprimitiva de q.

Para decifrar a mensagem m, Alice determina x = p−1−a e calcula Bxcmod p que vai ser a mensagem original m pois

Bxc ≡ gb(p−1−a)Abm ≡ (gp−1)b(ga)−bAbm ≡ A−bAbm ≡ m mod p.

71

4.10.1 Ataque da repeticao da chave efemera

Para cada nova mensagem que envie a Alice, Bob deve escolher um novoexpoente b, caso contrario o seguinte ataque permite decifrar as mensagens:

Se Bob escolher o mesmo expoente b para cifrar as mensagens m e m′,ele obtem

c ≡ Abm mod p e c′ ≡ Abm′ mod p

dondec′c−1 ≡ m′m−1 mod p

Um atacante que saiba m pode obter m′, usando a formula

m′ ≡ c′c−1m mod p.

4.11 Sistema Merkle-Hellman

Nesta seccao descrevemos outro tipo de criptosistema que e baseado no pro-blema do saco-mochila (em ingles, ”Knapsack”). Dados k inteiros v0, . . . , vk−1

e um inteiro V , o problema Saco-mochila consiste em determinar se existeum subconjunto dos k inteiros cuja soma seja V , i.e. se existem ϵi ∈ {0, 1},tais que

k−1∑i=0

ϵivi = V.

Note que podem haver imensas solucoes, nenhuma solucao, ou uma unicasolucao, dependendo dos vi’s e de V . Um caso particular do problema saco-mochila, e quando os vi’s, ordenados de forma crescente, tem a propriedade deque cada um e maior que a soma dos anteriores. Este caso especial e chamadosuper crescente. Por exemplo, a sequencia (2, 3, 7, 15, 31) e supercrescente.

Sabe-se que o problema geral do saco-mochila pertence a classe de pro-blemas muito difıceis conhecidos como NP-completos (i. e. problemas NPtais que qualquer outro problema NP se pode reduzir a eles). Os problemasNP-completos tem a extraordinaria propriedade de que se um deles estiverna classe P (existir um algoritmo que o resolva em tempo polinomial), entaoP=NP.

O problema do saco-mochila super crescente e, no entanto, muito maisfacil de resolver. O seguinte algoritmo (de tempo polinomial) permite-nosresolver qualquer problema do saco-mochila super crescente:

Seja v0, . . . , vk−1 uma sequencia super crescente e V um inteiro.

72

1. Faca W = V e j = k.

2. Se vi > W para 0 ≤ i ≤ j − 1 ir para o passo 4. Caso contrario,determine o maior dos vi’s, digamos vi0 , tal que vi0 ≤ W . Faca ϵi = 0para i > i0 e ϵi0 = 1.

3. Substitua W por W − vi0 e j = i0. Se W > 0, voltar ao passo 2.

4. Se W = 0 o algoritmo termina e encontrou-se a solucao

ϵ = (ϵ0, . . . , ϵk−1),

(que e unica) do problema. Se W > 0, todos os restantes vi’s saomaiores que W , portanto, nao ha solucao do problema.

Exemplo. Considere a sequencia (2, 3, 7, 15, 31) e V = 24. Entao ϵ4 = 0,ϵ3 = 1 (e substituimos 24 por 9), ϵ2 = 1 (e substitui-se 9 por 2), ϵ1 = 0 eϵ0 = 1. Portanto, a solucao e ϵ = (1, 0, 1, 1, 0).

Estamos em condicoes de descrever o criptosistema de Merkle-Hellman(tambem chamado sistema do saco-mochila), baseado no problema descritoatras. As mensagens originais vao ser inteiros com k bits. Por exemplo, seusarmos o alfabeto de 27 letras (com o espaco em branco) e k = 5, temos acodificacao (letra a letra, neste caso) 2 = (00000)2, A = (00001), . . . , Z =(11010). Em seguida, escolhemos uma sequencia super crescente v0, . . . , vk−1,um inteiro n > v0 + v1 + · · ·+ vk−1 e um inteiro 0 < a < n tal que (a, n) = 1(costuma-se tomar n primo). Calculamos b ≡ a−1 mod n e a sequencia deinteiros positivos

wi ≡ avi mod n

para qualquer 0 ≤ i ≤ k − 1. A chave secreta de Alice consiste da sequenciados vi’s e dos inteiros n, a e b. A sua chave publica e (w0, . . . , wk−1). Esta ea chave para cifrar.

Se Bob pretende enviar uma mensagem m = (ϵk−1 · · · , ϵ0)2 a Alice, usa achave {wi} e envia

c ≡k−1∑i=0

ϵiwi.

Note que para determinar a mensagem original a partir de c um atacante”so”tem que resolver um problema do saco-mochila mas, neste caso, esteproblema e difıcil porque a sequencia {wi} nao e super crescente.

73

Para decifrar c, Alice calcula V ≡ bc mod n. Como

bc ≡k−1∑i=0

ϵibwi ≡k−1∑i=0

ϵibavi ≡k−1∑i=0

ϵivi mod n

Entao V =∑k−1

i=0 ϵivi (note que V < n). Como a sequencia {vi} e supercrescente, Alice usa o algoritmo descrito atras para obter a solucao ϵ =(ϵ0, . . . , ϵk−1) e obtem a mensagem m = (ϵk−1 · · · , ϵ0)2.

Exemplo. Consideremos a codificacao em bits do nosso habitual alfabeto de27 letras. Tomemos a chave secreta

((v0, . . . , vk−1), n, a) = ((2, 3, 7, 15, 31), 61, 17)

Entao b = 18 e a chave de cifrar e (34, 51, 58, 11, 39). Queremos enviara mensagem ”SIM”. Temos que, ”S”= (10011)2, ”I”= (01001)2 e ”M”=(01101)2. Portanto, enviamos os inteiros 124 = 34+ 51+ 39, 45 = 34+ 11 e103 = 34+58+11. A mensagem cifrada 124, 45, 103 poderia ser descodificadausando, neste caso, pares de letras. Como

18 · 124 ≡ 36 mod 61, 18 · 45 ≡ 17 mod 61 e 18 · 103 ≡ 24 mod 61

obtemos os inteiros 36, 17, 24. Em seguida, usamos a nossa sequencia pararesolver o problema do saco-mochila para estes inteiros. Assim 36 = 31+3+2,obtendo-se a letra (10011) =S, 17 = 15 + 2, obtendo-se (01001) =I, e 24 =15 + 7 + 2, obtendo-se (01101) =M.

Durante algum tempo, houve algum optimismo acerca do uso deste crip-tosistema, porque a base da sua seguranca e um problema que se sabe serNP-completo (os problemas factorizacao e logaritmo discreto, sao NP, masnao se sabe se sao NP completos). Em 1982, Shamir encontrou um algoritmoque permitia quebrar este sistema em tempo polinomial. Varias variacoesdeste sistema tem sido consideradas, tendo algumas sido tambem quebradas(e. g. Brickell 1985). Uma das variacoes deste sistema que ainda nao terasido quebrado e o sistema de Chor-Rivest, que nao iremos descrever nestecurso.

74

Capıtulo 5

Primalidade

Existem imensas situacoes em que podemos necessitar de saber se um in-teiro enorme e primo. Por exemplo, nos sistemas criptograficos estudadosno capıtulo anterior, precisamos quase sempre de pelo menos um primoenorme e aleatorio. Uma interpretacao do que significa ”primo enorme ealeatorio”pode ser a seguinte: Primeiro geramos um inteiro ımpar n0, us-ando um gerador de numeros aleatorios e depois testar a primalidade de n0,n0 + 2, . . . ate que encontremos o primeiro primo p ≥ n0. Outra situacaoem que se usam testes de primalidade, e quando se quer determinar se in-teiros de formas muito especiais sao ou nao primos. Por exemplo, numerosde Mersenne (da forma 2p − 1) ou numeros de Fermat (da forma 22

k+ 1).

Um teste de primalidade probabilıstico e um criterio para um numero nnao ser primo. Se n passa uma aplicacao de um teste de primalidade, entaopode ser que seja primo. Se n falha um teste de primalidade entao e (obriga-toriamente) composto. Se passar muitas vezes um teste de primalidade entaotem grande probabilidade de ser primo (podendo por vezes ter-se a certezaque e realmente primo). No caso de n ser composto ficamos ainda com oproblema de factorizar n. Com os algoritmos existentes consegue-se verificarse um numero com alguns milhares de algarismos e primo, com grande prob-abilidade (se n tiver uma forma especial, por exemplo se for um numero deMersenne ou de Fermat, consegue-se atestar a primalidade de numeros commilhoes de algarismos), enquanto que so se consegue factorizar numeros (quenao tenham nenhuma forma particular) com perto de 200 algarismos.

75

5.1 Teste de Fermat

Antes de descrevermos este teste de primalidade recordemos algumas definicoesde teoria elementar dos numeros.

Definicao. Seja a > 1 um inteiro positivo. Chamamos pseudoprimo para abase a a um composto n tal que (a, n) = 1 e n | (an − a).

Definicao. Um composto n que e pseudoprimo para qualquer base a, talque (a, n) = 1 chama-se numero de Carmichael.

Exemplo. Os numeros 561, 1105 e 6601 sao numeros de Carmichael.

O teste de Fermat e baseado no Pequeno Teorema de Fermat. Dados n e1 < a < n, o teste consiste verificar se an−1 ≡ 1 mod n. Podemos aplica-lousando sucessivas bases a: Dado um inteiro n, comecamos por calcular

a ≡ 2n−1 mod n

se a = 1 entao n e composto. Se a = 1, calculamos

b ≡ 3n−1 mod n

Caso b = 1, temos que n e composto. Se b = 1 calculamos 5n−1 mod n eassim sucessivamente.

Infelizmente, ha inteiros que passam este teste para qualquer base, oschamados numeros de Carmichael. Portanto, nao e possıvel provar que neprimo, usando sucessivas aplicacoes deste teste.

Exemplo. Considere n = 341. Temos 2340 ≡ 1 mod 341. Mas 3340 ≡ 56mod 341. Portanto, 341 e composto. De facto, 341 = 11 · 31. Provamostambem que 341 e pseudoprimo para a base 2 mas nao e pseudoprimo paraa base 3.

Note que este teste, embora prove que n e composto, nao da qualquerindicacao sobre os factores de n. So mostra que a n falta uma propriedadeque todos os primos tem.

76

5.2 Teste de Miller-Rabin

Nesta seccao, descrevemos o teste de Miller-Rabin. Contrariamente ao testede Fermat, para este teste nao ha inteiros correspondentes aos numeros deCarmichael, i. e. o teste de Miller-Rabin pode provar que e de facto primoqualquer inteiro que passe o teste um numero suficiente de vezes.

Teorema 5.1. Seja n um primo ımpar e sejam s e d tais que n − 1 = 2sd,com d ımpar. Se a e um inteiro tal que (a, n) = 1, entao ou

ad ≡ 1 mod n

ou existe 0 ≤ r ≤ s− 1 tal que

a2rd ≡ −1 mod n

Demonstracao: Seja a tal que (a, n) = 1. Como n e primo temos queφ(n) = n−1 = 2sd. Donde, k = ordn(a

d) e uma potencia de 2. Se k = 1 = 20,temos que

ad ≡ 1 mod n.

Se k > 1 entao existe 1 ≤ l ≤ s tal que k = 2l e

a2ld ≡ 1 mod n.

Mas entao a2l−1d ≡ 1 mod n e a2

l−1d tem ordem 2 mod n. Logo a2l−1d e

solucao da congruencia x2 ≡ 1 mod n. Como n e primo, as unicas solucoesdesta congruencia sao 1 e −1. Portanto,

a2l−1d ≡ −1 mod n

2

Definicao. Seja n um composto ımpar, e sejam s e d tais que n− 1 = 2sd,com d ımpar. Seja a tal que (a, n) = 1. Se n e a satisfazem a condicao

ad ≡ 1 mod n ou existe 0 ≤ r ≤ s− 1 tal que a2rd ≡ −1 mod n (5.1)

entao dizemos que n e pseudoprimo forte para a base a.

77

Definicao. Dizemos que um inteiro a e uma testemunha de que n e compostose (a, n) = 1 e a condicao (5.1) nao e verificada.

Dados a e n, o teste de Miller-Rabin, consiste em verificar se a condicao(5.1) e ou nao verificada por estes inteiros. Se n falhar esta condicao entaon e composto e a e uma sua testemunha.

Exemplo. Seja n = 561. Ja vimos que n e um numero de Carmichael,portanto o teste de Fermat nao da para provar que n e composto. Temos que560 = 24 · 35. Consideremos a = 2. Entao

235 ≡ 263 mod 561

22·35 ≡ 166 mod 561

222·35 ≡ 67 mod 561

223·35 ≡ 1 mod 561

Portanto, 561 e composto e o inteiro 2 serve para testemunhar este facto.

Para que o teste de Miller-Rabin seja eficiente, e importante que exista umnumero suficiente de testemunhas para cada composto. O proximo resultadomostra que ha imensas testemunhas.

Teorema 5.2. Seja n ≥ 3 um composto ımpar. O conjunto {1, . . . , n − 1}contem no maximo n−1

4numeros que sao primos com n e nao sao testemunhas

de que n e composto.

Suponhamos que n e um inteiro ımpar enorme que queremos verificar se eprimo ou nao. Seja 1 < a < n− 1 escolhido aleatoriamente. A probabilidadede n ser composto e a nao ser uma testemunha e, no maximo, 0.25. Aprobabilidade de escolhermos k inteiros a que nao sejam testemunha e menorque

1

4k.

Portanto, se um inteiro n passa o teste de Miller-Rabin k vezes, e muitoprovavel que seja primo (com probabilidade pelo menos 1 − 1/4k). Parak = 20, a probabilidade de ser composto tendo passado o teste de Miller-Rabin k vezes e 1 em um biliao. No entanto, note-se que este teste nao nosgarante que n seja de facto primo.

Ja vimos que, dado um composto n, ha mais de 3(n− 1)/4 testemunhasno intervalo [2, n − 2]. Sera que ha um numero B, independente de n, tal

78

que ha sempre uma testemunha a < B de que n e composto? Infelizmente, aresposta a esta pergunta e nao (provado por Alford, Granville e Pomerance).No entanto, se a Hipotese de Riemann extendida (ERH) for verdade, temoso seguinte resultado

Teorema 5.3. Seja n um numero composto. Admitindo a ERH, ha umatestemunha a, com a < 2 log2 n de que n e composto.

Portanto, se ERH for verdadeira, existe um algoritmo polinomial paraverificar se n e primo, baseado no teste de Miller-Rabin.

5.3 Teste de Solovay-Strassen

O proximo teste que iremos estudar e baseado no lema de Euler sobre osımbolo de Legendre, ja estudado. Comecemos por definir o sımbolo deJacobi, que e uma generalizacao do sımbolo de Legendre.

Definicao. Seja a um inteiro e n =∏k

i=1 paii um inteiro ımpar. Define-se o

sımbolo de Jacobi, da seguinte maneira(an

)=

∏i = 1k

(a

pi

)ai

,

onde(

ap

)e o sımbolo de Legendre.

Para o sımbolo de Jacobi tambem e valida a lei da reciprocidade quadratica,i. e., se m e n sao inteiros impares(m

n

)= (−1)

m−12

n−12

( n

m

).

O lema de Euler diz-nos que se p um primo ımpar e a um inteiro tais quep - a. Entao (

a

p

)= a

p−12 mod p.

Dado um inteiro ımpar n e a um inteiro, o Teste de Solovay-Strassenconsiste em verificar se

an−12 ≡

(an

)mod n.

79

Definicao. Um inteiro n composto que passe o teste de Solovay-Strassenpara um dado a e chamado pseudoprimo de Euler-Jacobi para a base a

Teorema 5.4. Para qualquer numero composto n ha pelo menos n/2 basesmenores que n tais que n nao e um pseudoprimo de Euler-Jacobi para qual-quer uma dessas bases.

5.4 Teste n− 1 de Lucas

Nas seccoes anteriores encontramos alguns testes probabilisticos para veri-ficar se n e composto. O proximo teste e determinista, i. e. se n passar oteste entao n e de facto primo.

Teorema 5.5 (Lucas). Se a e n sao inteiros com n > 1, e

an−1 ≡ 1 mod n, mas an−1q ≡ 1 mod n para qualquer primo q | n− 1

entao n e primo.

Demonstracao: A primeira condicao implica que ordn(a) | n − 1. Asegunda condicao, mostra que ordn(a) nao e um divisor proprio de n − 1.Portanto, ordn(a) = n − 1. Mas pelo teorema de Euler, ordn(a) | φ(n),donde n − 1 ≤ φ(n). Mas se n e composto, φ(n) < n − 1, portanto, n eprimo. 2

Para usarmos o teorema de Lucas, e necessario saber a factorizacao emprimos de n − 1, e em geral essa factorizacao pode ser difıcil de encontrar.Alem disso, se n e de facto primo, temos que tomar a uma raiz primitiva den. Sabemos que ha φ(n − 1) raızes primitivas, mas estas podem ser difıceisde encontrar. No entanto, para inteiros com formas especiais, o teorema deLucas, permite-nos obter um teste muito eficiente.

Teorema 5.6 (Teste de Pepin). Para k ≥ 1, o numero Fk = 22k+1 e primo

se e so se3

Fk−1

2 ≡ −1 mod Fk.

Demonstracao: Seja k ≥ 1. Suponhamos que

3Fk−1

2 ≡ −1 mod Fk

80

entao o teorema de Lucas diz-nos que Fk e primo. Reciprocamente supon-hamos que Fk e primo. Como 2k e par, entao

22k ≡ 1 mod 3,

donde Fk ≡ 2 mod 3. Mas Fk ≡ 1 mod 4, logo(3

Fk

)= −1

Pelo teorema 4.11, obtemos a congruencia desejada. 2

Teorema 5.7 (Teste de Lucas-Lehmer). Seja s0 = 4 e si = s2i−1 − 2. EntaoMp = 2p − 1 e primo se e so se sp−2 ≡ 0 mod Mp.

81

Capıtulo 6

Factorizacao

Neste capıtulo, vamos descrever alguns algoritmos importantes de factor-izacao. Iremos assumir que n e composto. Este facto pode ser provadousando, por exemplo, um dos algoritmos do capıtulo anterior.

Em muitos dos algoritmos de factorizacao, verifica-se primeiro, por ex-perimentacao, se n e divisıvel por numeros primos pequenos, e. g. p ≤ B,com B fixo.

Exemplo. Queremos factorizar n = 321+1 = 10460353204. Experimentandoprimeiro todos os primos menores que 50, verifica-se que

n = 22 · 72 · 43 · 1241143.

Seja m = 1241143. Como 2m−1 ≡ 793958 mod m, o pequeno teorema deFermat implica que m e composto. Ficamos ainda com a tarefa de factorizarm.

6.1 Metodo p− 1 de Pollard

Ha algoritmos de factorizacao que funcionam muito bem para inteiros com-postos que verificam certas propriedades. O metodo p − 1, e um dessesalgoritmos e foi inventado por John Pollard. Suponhamos que n e compostoe que tem um factor primo p, tal que p−1 so tem divisores primos pequenos.Entao e possıvel obter um multiplo k de p−1 sem sabermos o valor de p−1.Basta tomar k como sendo o mınimo multiplo comum de todos os inteirosate um limite B. Podemos tambem tomar k como sendo B!.

82

Definamos k = k(B) = [2, 3, 4, . . . , B], onde [a, b] representa o mınimomultiplo comum de a e b. Se n tiver um divisor primo p tal que todos osdivisores de p − 1 que sao potencias de primos forem menores que k, entaop− 1 | k. O pequeno teorema de Fermat, implica que

ak ≡ 1 mod p,

para qualquer inteiro a, tal que (a, p) = 1. Portanto, p | (ak − 1). Sen - (ak − 1) entao (ak − 1, n) e um divisor proprio de n.

O algoritmo consiste em comecar com um limite B e uma base a. Se(ak − 1, n) nao der um divisor proprio de n (i. e. se (ak − 1, n) = 1 ou(ak − 1, n) = n), entao experimenta-se outro limite B ou outra base a.

Exemplo. Continuando o exemplo anterior, vamos agora factorizar m =1241143. Seja B = 13, entao

k = 8 · 9 · 5 · 7 · 11 · 13

e(2k − 1,m) = 547.

Entao p = 547 e um divisor de n. Portanto, m = 547 · 2269. Facilmente, severifica que 547 e 2269 sao primos.

6.2 Metodo ro de Pollard

Nesta seccao, vamos analisar outro metodo de factorizacao introduzido porJ. Pollard. Sejam l um inteiro e f uma funcao aleatoria de S = {0, 1, . . . , l}para S. Seja x0 um elemento aleatorio e considere-se a sequencia

x0, x1 = f(x0), x2 = f(x1), . . . .

Como S e finito, a sequencia ira tornar-se cıclica ao fim de um certo numerode termos. Se fizermos um diagrama que mostre este comportamento, eleassemelhar-se-a a ρ, daı a origem do nome do metodo.

Seja n um inteiro composto. O primeiro passo do metodo ro, consiste emescolher uma funcao f de Z/nZ para Z/nZ que seja facil determinar f(x).Costuma-se usar polinomios com coeficientes inteiros, e. g. f(x) = x2 + 1.Em seguida, toma-se um inteiro positivo x0, e. g. x0 = 1 ou x0 = 2.

83

Calculam-se as sucessivas iteracoes xk = f(xk−1) mod n. Depois fazem-se comparacoes entre diferentes xi’s, esperando encontrar dois que sejamdiferentes mod n mas que sejam iguais mod l para algum divisor proprio lde n. Quando encontrarmos xj e xk nestas condicoes (i. e. xj ≡ xk mod l),temos que (xj − xk, n) e um divisor proprio de n. Assim como esta, estemetodo ira tornar-se moroso, pois ao fim de k iteracoes temos de compararaproximadamente k2 pares de valores. Note que se xj ≡ xk mod l e sendom ≥ 0, temos

xj+m ≡ xk+m mod l

Portanto, em vez de efectuar todas as comparacoes possıveis podemos apenasfazer uma comparacao em cada iteracao. Por exemplo, podemos calcularsomente

(x2i − xi, n)

em cada iteracao i. Podemos tambem calcular, na iteracao k com 2j ≤ k <2r+1, o maximo divisor comum

(xk − xj, n)

onde j = 2j − 1.

Exemplo. Vamos factorizar 4087 usando f(x) = x2 + 1 e x0 = 3. Obtemossucessivamente

x1 = 10, x2 = 101 (101− 10, 4087) = 1

x2 = 101, x4 = 1263 (1263− 101, 4087) = 1

x3 = 2028, x6 = 889 (2028− 89, 4087) = 67

Portanto, 67 | 4087. Dividindo, obtem-se 4087 = 67 · 61.

Exemplo. Sejam n = 845651, f(x) = x2 + x + 1 e x0 = 2. Verifica-se que(x10− x7, n) = 571. Portanto, n = 571 · 1481.

Teorema 6.1. O metodo ro permite encontrar um factor de n em

O( 4√n log3 n)

operacoes com uma grande probabilidade. Mais exactamente, existe uma con-stante C tal que, para qualquer inteiro positivo λ, a probabilidade de o metodoro nao encontrar um factor nao trivial de n em C

√λ 4√n log3 n operacoes bit,

e menor que exp(−λ).

84

O teorema anterior garante-nos que este metodo e, com uma grande prob-abilidade, significativamente mais rapido que irmos experimentando todos osprimos ate

√n. O resultado mais espectacular, usando este metodo ocorreu

em 1981, quando Brent e Pollard factorizaram completamente F8 = 228+ 1.

A seguinte mnemonica de J. Pollard, permite-nos recordar um dos factoresde F8

I am now intirely persuaded to employ rho method, a handy trick,on gigantic composite numbers

6.3 Factorizacao de Fermat

Suponhamos que n e o produto de dois primos p e q proximos um do outro.Entao n e a diferenca de dois quadrados, um dos quais e pequeno. Neste caso,ha um processo eficiente de factorizar n chamado factorizacao de Fermat. Poreste motivo deve-se evitar usar tais inteiros n como chave publica, tanto noRSA como no sistema de Rabin.

Teorema 6.2. Seja n um inteiro positivo ımpar. Ha uma correspondenciabijectiva entre factorizacoes de n da forma n = ab, com a ≥ b > 0, erepresentacoes de n na forma t2 − s2, onde t e s sao inteiros nao negativos.A correspondencia e dada pelas equacoes

t =a+ b

2, s =

a− b

2a = t+ s b = t− s

Demonstracao: Se n = ab entao

n =

(a+ b

2

)2

−(a− b

2

2)2

donde n pode ser escrito como a diferenca de dois quadrados. Se n = t2 − s2

entao n = (t− s)(t+ s). Obtemos assim a correspondencia bijectiva. 2

Se n = ab e a e b estao proximos um do outro, entao s e pequeno e t eligeiramente maior que

√n. Neste caso, podemos factorizar n, experimen-

tando valores para t, comecando por [√n] + 1, ate que se encontre um para

o qual t2 − n e um quadrado perfeito.

85

Exemplo. Seja n = 200819. Comecamos com [√n] + 1 = 449. Agora,

4492− 200819 = 782 que nao e um quadrado perfeito. Em seguida, tentamost = 450. Temos 4502 − 200819 = 1681 = 412, donde

n = (450 + 41)(450− 41) = 491 · 409.

Note que se a e b nao estiverem proximos, este metodo ainda serve parafactorizar n, mas so apos termos usado imensos valores para t, o que o podetornar muito moroso. Ha uma generalizacao do metodo de Fermat que fun-ciona melhor nesta situacao. Comecamos por escolher um multiplicador kpequeno e tomamos

t = [√kn] + 1, t = [

√kn] + 2, . . .

ate que obtenhamos um t para o qual t2 − kn = s2 e um quadrado perfeito.Entao d = (t+ s, n) e um factor nao trivial de n.

Exemplo. Seja n = 141467. Se usarmos a factorizacao de Fermat directa-mente, precisamos de experimentar 38 t’s ate encontrar um factor de n. Masse tomarmos k = 3 e comecarmos com t = [

√3n] + 1 = 652, rapidamente

vemos que 6552 − 3n = 682. Como (655 + 68, n) = 241, concluımos quen = 241 · 587. Portanto, com k = 3 so precisamos de experimentar 4 t’s.

Mas como sabemos que devıamos usar k = 3 no exemplo anterior? Umamaneira de resolver este problema e utilizando o metodo de Lehman (que euma generalizacao do metodo de Fermat).

A ideia deste metodo e experimentarmos todos os k ate [ 3√n] e para cada

um desses k’s , experimentar somente[6√n

4√k

]valores de t. Mais exactamente, primeiro verifica-se se n tem algum divisord ≤ 3

√n. Caso contrario, para cada 1 ≤ k ≤ [ 3

√n], experimenta-se, para cada

t inteiro no intervalo (2√kn− 1, 2

√kn+

6√n

4√k

],

se t2− 4kn e um quadrado perfeito s2. Caso seja, determina-se d = (t+ s, n)que e um factor nao trivial de n. Caso nao se encontre um quadrado perfeito,podemos concluir que n e primo.

Para provarmos que este algoritmo de facto funciona, necessitamos doseguinte resultado de Dirichlet:

86

Teorema 6.3 (da Aproximacao de Dirichlet). Para qualquer numero real θe qualquer inteiro positivo m, existem inteiros a e b, com 1 ≤ a ≤ m tais que

|aθ − b| ≤ 1

m+ 1.

Demonstracao: No que se segue iremos representar a parte inteira e aparte fraccionaria de um numero real x por [x] e {x}, respectivamente.

Suponhamos que m = 1. Se {θ} ≤ 12, basta tomar a = 1 e b = [θ], se

{θ} > 12, basta tomar a = 1 e b = [θ] + 1. Suponhamos agora que m > 1 e

consideremos os m+ 2 numeros reais, 0, 1 e

ra = {aθ} = aθ − [aθ],

onde 1 ≤ a ≤ m. Note que se ri ≥ rj e i > j entao ri − rj = ri−j.Analogamente, se ri ≥ rj e j > i entao 1 − (ri − rj) = rj−i. Consideremostambem a seguinte particao do intervalo [0, 1],

Ik = [k

m+ 1,k + 1

m+ 1), com 0 ≤ k ≤ m− 1

e Im = [ mm+1

, 1]. Como temos m + 2 numeros reais em [0, 1] e a particao de[0, 1] tem m + 1 subintervalos, entao um desses intervalos, digamos Ik, tempelo menos dois dos numeros reais considerados. Se k = 0 entao existe uminteiro 1 ≤ a ≤ m tal que

ra ≤1

m+ 1, i.e. |aθ − [aθ]| < 1

m+ 1.

Se k = m entao existe um inteiro 1 ≤ a ≤ m tal que

1− ra ≤1

m+ 1, i.e. |aθ − [aθ]− 1| ≤ 1

m+ 1.

Se 0 < k < m entao existem dois inteiros 1 ≤ i, j ≤ m tais que

ri − rj ≤1

m+ 1.

Podem acontecer dois casos: Se i > j temos ri − rj = ri−j e

(i− j)θ − [(i− j)θ] ≤ 1

m+ 1.

87

Se j > i temos 1− (ri − rj) = rj−i e

|(j − i)θ − [(j − i)θ]− 1| ≤ 1

m+ 1.

2

Teorema 6.4. O metodo de Lehman esta correcto e demora O( 3√n log2 n)

operacoes bit.

Demonstracao: Suponhamos que o metodo esta correcto, e de facto nosda um divisor de n ou prova que n e primo. Vejamos quantas operacoes bitdemora. A parte inicial de experimentar se n tem algum divisor menor que3√n demora no maximo O( 3

√n log2 n) pois para cada inteiro menor que 3

√n

fazemos uma divisao (se experimentassemos so primos terıamos um factorlog n a menos). Caso tenhamos que passar a segunda parte do metodo,temos que verificar

⌈ 3√n⌉∑

k=1

[6√n

4√k

]= O( 3

√n)

vezes se t2 − 4kn e um quadrado perfeito (cada um demora O(log2 n)). Sono caso de obtermos um quadrado perfeito e que precisamos de calcular(d = t+ s, n). Portanto, no total temos O( 3

√n log2 n) operacoes bit.

Provemos agora que o metodo de Lehman esta correcto. Podemos assumirque n nao tem factores d ≤ 3

√n. Se n nao e primo entao n = pq com

p, q > 3√n. Vamos provar que existe um inteiro k ≤ [ 3

√n] , k = uv com

|uq − vp| < 3√n

Seja m = [n16 q

12p−

12 ]. Pelo teorema da aproximacao de Dirichlet, existem

inteiros positivos a e b, com 1 ≤ a ≤ m, tais que

|apq− b| ≤ 1

m+ 1.

Mas entao

|ap− qb| ≤ q

m+ 1<

q

6√n√

qp

<

√n

6√n= 3

√n.

88

Portanto, tomando u = b, v = a obtemos

|uq − vp| < 3√n

Falta provar que uv ≤ [ 3√n]. Sabemos que

u

v<

p

q+

1

vm

e v ≤ m, donde,

uv =u

vv2 <

p

qv2 +

v

m≤ p

q

q

pn

13 + 1 = n

13 + 1.

Consideremos c = uq+ vp e e = |uq− vp|. Entao 4kn = c2− e2. Em seguida,provamos que

2√kn ≤ c < 2

√kn+

n16

4√k.

Como (uq)(vp) = kn, entao c = uq+ vp ≥ 2√kn. Seja E = c− 2

√kn, entao

4kn+ 4E√kn ≤ (2

√kn+ E)2 = c2 = 4kn+ e2 < 4kn+ n

23 ,

logo

E <n

16

4√k.

Para terminar, so temos que mostrar que (c + e, n) e um factor nao trivialde n. Como n | (c + e)(c − e), basta mostrar que c + e < n. Temos, paran ≥ 21,

c+ e < 2√kn+

n16

4√k+ n

13 < 2

√(n

13 + 1)n+

n16

4√

n13 + 1

+ n13 < n.

2

89

6.4 Crivo quadratico

Actualmente sao usados essencialmente tres metodos de factorizacao, o crivoquadratico, o crivo do corpo numerico e o metodo da curva elıptica. Nestaseccao iremos descrever o primeiro destes metodos.

A ideia do crivo quadratico e encontrar inteiros x e y tais que

x2 ≡ y2 mod n

ex ≡ ±y mod n.

Entao d = (x− y, n) e um divisor proprio de n.

Exemplo. Sejam n = 7429, x = 227, e y = 210. Entao x2 − y2 = n ex− y = 17. Como (n, 17) = 17, temos 17 | n.

O crivo do corpo numerico tambem usa a ideia anterior, a diferenca e namaneira de determinar x e y. Vejamos como determinar estes inteiros nocrivo quadratico.

Sejam m = [√n] e f(X) = X2 − n. A ideia e encontrar k inteiros si, 1 ≤

i ≤ k, tais que cada f(si) so tenha factores primos pequenos (pertencentes aum conjunto B), e de tal modo que f(s1) · · · f(sk) seja um quadrado mod n,i. e. os expoentes de cada primo envolvido sao pares. Se k for suficientementegrande (basta k > #B), os expoentes mod 2 de cada primo, irao formar umsistema linear com k equacoes e #B incognitas, logo e um sistema resoluvel.Para clarificar este processo, vejamos outra vez o exemplo anterior.

Exemplo. Temos n = 7429, donde m = 86. Seja B = 8. Neste caso,f(87) = 872 − 7429 = 140 = 22 · 5 · 7 e f(88) = 882 − 7429 = 315 = 32 · 5 · 7.Consideremos v1 = (0, 0, 1, 1) e v2 = (0, 0, 1, 1) (neste caso, vi e o π(B)-uplo,que consiste dos expoentes mod 2 dos primos ate B, na decomposicao def(si)). Como v1+v2 ≡ (0, 0, 0, 0) mod 2, temos que f(1)f(2) e um quadradomod n. Portanto, x ≡ 87 · 88 ≡ 227 mod n e y ≡ 2 · 3 · 5 · 7 ≡ 210 mod n.

Ainda nos falta descrever como escolher B e como escolher os inteiros si.Ja vimos que os inteiros s tem que verificar uma propriedade que dependede B. Comecamos por definir essa propriedade.

Definicao. Dizemos que um inteiro s e B-suave se p | s ⇒ p ∈ B.

90

O conjunto B e formado pelo numero −1 e por primos menores que umvalor maximo B0 (mais tarde veremos que nao e necessario considerar todosos primos menores que B0). Se B0 for grande, este processo pode demorarmais que o metodo de Fermat (podemos necessitar de demasiados s′is paragarantir a solubilidade do sistema linear). Por outro lado, seB0 for demasiadopequeno, a propriedade de si ser B−suave pode ser tao especial que podemosdemorar muito a encontrar o primeiro inteiro B − suave depois de m. Foidemonstrado que o valor optimo para B0 e

exp(1

2

√log n log log n).

Este valor de B0 permite que possamos determinar um factor de n em

O(e√logn log logn)

operacoes bit. Portanto, muito mais rapido que o metodo de Fermat e suasvariantes.

Em vez de utilizarmos todos os primos menores que B0 (se n for enorme,podem ser demasiados), usa-se bases de factores. Queremos encontrar inteirossi perto dem = [

√n] tais que f(si) seja B-suave. Se p | f(si), entao (si)2 ≡ n

mod p, i. e. n e um resıduo quadratico mod p. Portanto, so nos interessamprimos p ≤ B0 tais que (

n

p

)= 1

ou p = 2. A base de factores e assim constituıda por estes primos e por −1.Para determinar os inteiros si tais que f(si) seja B-suave, comeca-se por

considerar um intervalo a crivar, S = {m−M,m−M +1, . . . ,m−1,m,m+1, . . . ,m+M − 1,m+M}, com M suficientemente grande, e calcula-se f(u)para qualquer u ∈ S. Dado p na base de factores, determinamos os inteiros0 ≤ t ≤ p−1, tais que t2 ≡ n mod p. Sabemos que ha duas solucoes, u1 e u2,pois n e um resıduo quadratico mod p (se p = 2 ha uma so solucao). Utiliza-se o algoritmo de Tonelli-Shanks para determinar estas solucoes. Entao pdivide f(u1) e f(u2), mas tambem divide f(ui+ kp), para i = 1, 2 e k inteiro(e desta parte do algoritmo que resulta o nome crivo quadratico). Assim,comecando em ui, divide-se cada f(ui + kp) com ui + kp ∈ S pela maiorpotencia de p possıvel, resultado este que passa a substituir f(ui + kp). Faz-se o mesmo para os outros primos da base de factores e escolhe-se os valoresque forem iguais a 1. Os ındices destas coordenadas sao os nossos si’s, e paracada um deles, f(si) e B-suave.

91

i f(m+ i) 2 3 5 7 13 171 8016 501 1672 16227 6013 24440 3055 611 474 32655 10885 2177 3115 40872 5109 1703 1316 49091 70137 57312 1791 1998 65535 21845 4369 2579 73760 2305 46110 81987 2732911 90216 11277 1253 17912 98447 579113 106680 13335 445 889 12714 114915 38305 766115 123152 769716 131391 14599 112317 139632 8727 290918 147875 1183 169 125 205632 3213 119 17 129 238680 29835 1105 221 17 155 454272 3549 1183 169 183 687960 85995 3185 637 13 1137 1143072 35721 49 1263 2227680 69615 7735 1547 221 17 1

Tabela 6.1: O crivo quadratico

92

Exemplo. Seja n = 16843009. Entao m = [√n] = 4104. Usando o valor

optimo para B0, obtemos B0 = 30. A base de factores e {2, 3, 5, 7, 13, 17}.Consideremos S = {m+ 1,m+ 2, . . . ,m+ 1000}. A tabela 6.1 mostra comofunciona o crivo. As ultimas 7 linhas representam os si’s para os quais f(si)e B-suave. Obtemos os vectores dos expoentes

(0, 0, 3, 1, 2, 0), (6, 3, 0, 1, 0, 1) (3, 3, 1, 0, 1, 1) (7, 1, 0, 1, 2, 0)

(3, 3, 1, 2, 1, 0) (5, 6, 0, 2, 0, 0) (5, 2, 1, 1, 1, 1)

Como so nos interessa a paridade dos expoentes, obtemos

(0, 0, 1, 1, 0, 0), (0, 1, 0, 1, 0, 1) (1, 1, 1, 0, 1, 1) (1, 1, 0, 1, 0, 0)

(1, 1, 1, 0, 1, 0) (1, 0, 0, 0, 0, 0) (1, 0, 1, 1, 1, 1)

Temos (0, 1, 0, 1, 0, 1)+(1, 1, 1, 0, 1, 0)+(1, 0, 1, 1, 1, 1) = (0, 0, 0, 0, 0, 0). Logo,

x ≡ 4129 ∗ 4187 ∗ 4367 ≡ 6866803 mod n

ey ≡ 27 · 34 · 5 · 72 · 13 · 17 ≡ 5556063 mod n

donde (x− y, n) = 65537. Portanto, 65537 e um factor de n = 16843009.

Em Abril de 1994, foi terminada a factorizacao do RSA-129 usando ocrivo quadratico. O RSA-129 e um numero com 129 dıgitos com dois factoresprimos, um com 64 dıgitos e o outro com 65. A base de factores para estafactorizacao continha 524339 primos. Em 1996, o crivo dos corpos de numerosfoi utilizado para factorizar o RSA-130. Desde entao todos os numeros RSAque teem sido factorizados, foram-no usando este ultimo crivo.

93

Capıtulo 7

Logaritmo Discreto

Como ja vimos alguns sistemas criptograficos dependem da complexidade doproblema do logaritmo discreto, neste capıtulo iremos descrever algoritmospara resolver este problema. Muitos destes algoritmos sao validos para qual-quer inteiro n para o qual (Z∗

n, ·) seja um grupo cıclico, mas iremos somenteconsiderar grupos cuja ordem seja um primo.

Seja p um primo ımpar e g uma raız primitiva mod p. Dado um inteirob, o problema do logaritmo discreto consiste em encontrar a menor solucaode

b ≡ gx mod p. (7.1)

7.1 Enumeracao

O metodo mais simples para resolver a equacao (7.1) e ir testar sucessiva-mente x = 0, 1, 2, 3 . . . . A este processo chamamos enumeracao.

Exemplo. A menor solucao (positiva) de 3 ≡ 5x mod 2017 e x = 1030.Portanto, usando a enumeracao, temos que experimentar 1031 valores!

Em criptografia usa-se solucoes x, com x ≥ 2160, portanto este metodo etotalmente impraticavel.

94

7.2 Algoritmo passos de bebe passos de gi-

gante

Este algoritmo foi desenvolvido por D. Shanks em 1971 e permite-nos me-lhorar consideravelmente o algoritmo anterior. Seja m = [

√p] e facamos

x = qm + r, com 0 ≤ r < m. O algoritmo passos de bebe passos de gigantedetermina q e r. Como gqm+r ≡ b mod p, entao

(gm)q ≡ bg−r mod p

Primeiro calculamos o conjunto dos passos de bebe

B = {(bg−r mod p, r) : 0 ≤ r < m}.

Se B tiver um elemento da forma (1, r), entao b ≡ gr mod p e a menorsolucao de (7.1) e x = r. Caso nao exista tal par, determinamos c = gm

mod p. Em seguida, para cada q = 1, 2, 3, . . . , verificamos se cq mod p ea primeira coordenada de algum elemento de B. Quando isto acontecer,obtemos

(gm)q ≡ cq ≡ bg−r mod p

donde x = qm+r e solucao de (7.1). Ao calculo dos elementos cq, chamamospassos de gigante. Para cada q temos que comparar cq com os elementos deB.

A solucao de 3 ≡ 5x mod 2017 e x = 1030. Usando o metodo da enu-meracao temos que efectuar 1029 multiplicacoes mod 2017. Se usarmoso algoritmo passos de bebe passos de gigante, obtemos m = 44, r = 18 eq = 23. Portanto, so necessitamos de 44 multiplicacoes para os passos debebe e de 22 multiplicacoes para os passos de gigante. Em contrapartida,para utilizarmos este algoritmo, temos que guardar todos os pares dos passosde bebe, enquanto que no algoritmo de enumeracao, so e necessario guardaros inteiros g, b e p.

Para o algoritmo da enumeracao, o numero maximo de multiplicacoes ep−1, mas o numero mınimo pode ser muito pequeno. No algoritmo passos debebe passos de gigante, temos sempre [

√p] + 1 passos de bebe, e no maximo

[√p] passos de gigante. Tambem este algoritmo e impraticavel para resolver

problemas concretos de criptoanalise.

95

7.3 Calculo de ındices

Nesta seccao descrevemos o algoritmo calculo de ındices que esta relacionadocom os algoritmos de factorizacao subexponenciais mencionados no capıtuloanterior. Mais uma vez queremos resolver o problema do logaritmo discreto

b ≡ gx mod p.

Comecamos por escolher um majorante B e consideramos a base de factoresF (B) = {q, primo : q ≤ B}. Em seguida, calculamos o logaritmo discretodos elementos da base de factores, i. e., para qualquer q ∈ F (B), resolvemosa congruencia

gxq ≡ q mod p.

Depois determinamos um expoente y ∈ {1, 2, . . . , p − 1} tal que bgy mod pe B-suave e escrevemos

bgy ≡∏

q∈F (B)

qeq mod p.

Entaobgy ≡

∏q∈F (B)

gxqeq ≡ g∑

q∈F (B) xqeq mod p

dondeb ≡ g

∑q∈F (B) xqeq−y mod p.

Portanto, a solucao do problema do logaritmo discreto e

x ≡∑

q∈F (B)

xqeq − y mod p− 1.

A determinacao do logaritmo discreto dos elementos da base de factoresparece a primeira vista tao difıcil como resolver o problema do logaritmodiscreto original, mas pode ser efectuada de um modo muito mais simples.Escolhe-se aleatoriamente z ∈ {1, 2, . . . , p− 1}, tal que gz mod p e B-suavee escrevemos

gz ≡∏

q∈F (B)

qfq,z mod p.

A cada vector (fq,z)q∈F (B) chamamos uma relacao. Deve-se verificar se cadanova relacao e linearmente dependente das anteriores. Caso seja, esta e

96

eliminada. Precisamos de tantas relacoes como o numero de elementos dabase de factores. Como

gz ≡∏

q∈F (B)

gxqfq,z ≡ g∑

q∈F (B) xqfq,z mod p

entao obtemos a congruencia linear

z ≡∑

q∈F (B)

xqfq,z mod p− 1.

Obtemos assim um sistema linear de congruencias (cujas incognitas sao osxq), que pode ser resolvido usando metodos de teoria dos numeros.

Note que se B for suficientemente grande, resolvemos o sistema de linearde congruencias uma unica vez e estes xq sao validos para a maioria dos b’s.

Exemplo. Vamos determinar x tal que 2x ≡ 13 mod 2027. Portanto, b =13, g = 2 e p = 2027. Consideremos B = 11, entao a base de factores eF (B) = {2, 3, 5, 7, 11}. Agora, escolhendo aleatoriamente z em {1, 2, . . . , p−1}, obtemos os seguintes numeros B-suaves:

3 · 11 = 33 ≡ 21593 mod 20275 · 7 · 11 = 385 ≡ 2983 mod 202727 · 11 = 1408 ≡ 21318 mod 202732 · 7 = 63 ≡ 2293 mod 202726 · 52 = 1600 ≡ 21918 mod 2027.

As relacoes obtidas sao (0, 1, 0, 0, 1), (0, 0, 1, 1, 1), (7, 0, 0, 0, 1), (0, 2, 0, 1, 0)e (6, 0, 2, 0, 0), que sao linearmente independentes. Pelo pequeno teorema deFermat, obtemos o seguinte sistema com 5 incognitas e 5 congruencias:

x2 + x5 ≡ 1593 mod 2026x3 + x4 + x5 ≡ 983 mod 20267x1 + x5 ≡ 1318 mod 20262x2 + x4 ≡ 293 mod 20266x1 + 2x3 ≡ 1918 mod 2026.

Como g = 2, entao x1 = 1. Temos que 2026 = 2 · 1013, assim devemosresolver as congruencias mod 2 e mod 1013 e depois utilizamos o teorema

97

chines dos restos para obter as solucoes mod 2026. O resultado final e

x1 = 1, x2 = 282, x3 = 1969, x4 = 1755, x5 = 1311.

Em seguida, escolhemos aleatoriamente y ∈ {1, 2, . . . , p−1}, ate que 13·2ymod 2027 seja B-suave. Encontramos

13 · 21397 ≡ 110 = 2 · 5 · 11 mod 2027.

Portanto,

x ≡ 1 + 1969 + 1311− 1397 ≡ 1884 mod 2026.

98

Capıtulo 8

Assinaturas digitais

8.1 Introducao

Em documentos em papel utilizam-se assinaturas convencionais, feitas amao para especificar a pessoa responsavel pelo documento. Estas assinat-uras sao utilizadas para assinar cartas, levantar dinheiro de um banco, assi-nar contratos, etc. Uma assinatura digital serve para assinar documentoselectronicos que sao transmitidos atraves de uma rede de computadores.Neste capıtulo iremos estudar varias assinaturas digitais, mas comecamospor observar algumas diferencas fundamentais entre assinaturas digitais eassinaturas convencionais:

1. Assinatura de um documento: Quando se utiliza uma assinaturaconvencional, esta assinatura esta fisicamente ligada ao documento queesta assinado. Quando utilizamos uma assinatura digital, esta nao estafisicamente ligada a mensagem, sendo assim necessario que o algoritmoutilizado deve de alguma maneira ligar a assinatura a mensagem quequeremos assinar.

2. Verificacao da assinatura: Numa assinatura convencional, a veri-ficacao da assinatura e verificada quando esta e comparada com umaassinatura autenticada (por exemplo, a assinatura do Bilhete de Identi-dade, do Cartao do Cidadao ou de um cartao de credito). Claramente,este metodo nao e muito seguro, porque e relativamente simples forjar aassinatura de uma outra pessoa. As assinaturas digitais sao verificadasutilizando um algoritmo de verificacao publico. Portanto qualquer pes-soa pode verificar se a assinatura digital e autentica.

99

Uma assinatura digital consiste de duas componentes: Um algoritmo paraassinar e um algoritmo de verificacao. Bob assina a mensagem x utilizandoum algoritmo (secreto) para assinar, sig. A assinatura resultante y = sig(x)e verificada utilizando um algoritmo de verificacao publico, ver. Dado o par(x, y), entao ver(x, y) = 1 se a assinatura e autentica e ver(x, y) = 0 se aassinatura nao estiver correcta.

As funcoes sig e ver devem ser de tempo polinomial e forjar uma assi-natura por um oponente deve ser computacionalmente impraticavel.

8.2 Assinatura RSA

O sistema criptografico RSA pode ser utilizado para assinaturas digitais,como passamos a descrever:

Sejam (na, ea) e (pa, qa, da) as chaves publica e privada RSA de Alice,respectivamente; e (nb, eb) e (pb, qb, db) as chaves publica e privada RSA deBob, respectivamente.

Suponhamos que a Alice pretende enviar uma mensagem cifrada e assi-nada a Bob. Dada a mensagem original x, primeiro a Alice assina x utilizandoa sua chave de RSA privada, da, obtendo

y = sigda(x) ≡ xda mod na.

Em seguida, cifra x e y utilizando a chave publica RSA de Bob, obtendo amensagem cifrada z que transmite a Bob. Quando Bob recebe z, ele primeirodecifra z utilizando a sua chave privada RSA e obtem (x, y). Para certificara autenticidade da assinatura y, Bob utiliza a chave publica RSA de Aliceverificando se a seguinte congruencia e verdadeira

yea ≡ x mod na.

Se Alice cifrar primeiro x, obtendo z, e so depois assinar z, obtendo y eenviar o par (z, y) a Bob, entao Oscar podera criar a sua assinatura y′ de z esubstituir a assinatura y de Alice, enviando o par (z, y′) a Bob. Neste caso,Bob ficara convencido que quem lhe enviou a mensagem x foi Oscar. Noteque nesta situacao, Oscar sabendo ou nao a mensagem x, consegue sempreassinar z. Por esta razao e recomendado que se assine sempre a mensagemantes de a cifrar.

100

8.3 Assinatura ElGamal

A assinatura digital ElGamal foi descrita pela primeira vez em 1985 e foidesenvolvida especificamente para ser uma assinatura, o que contrasta como RSA que pode ser usado como um sistema criptografico ou como umaassinatura. Uma modificacao desta assinatura deu origem a assinatura digi-tal standard adoptada pelo National Institute of Standards and Technology(NIST).

Passamos a descrever esta assinatura:Seja p um primo tal que a resolucao computacional do problema do log-

aritmo discreto em Zp e impraticavel. Sejam α uma raiz primitiva de p,1 < a < p − 1 um valor aleatorio e β ≡ αa mod p. Os valores p, α e βsao publicos e a e secreto. Seja K = (p, α, a, β) a chave ElGamal de Bob.Para assinar uma mensagem x, gera-se aleatoriamente k ∈ Z∗

p−1 (k deve sermantido secreto) e define-se

sigK(x, k) = (γ, δ),

ondeγ ≡ αk mod p

eδ ≡ (x− aγ)k−1 mod p− 1.

A funcao de verificacao e dada por

verK(x, γ, δ) = 1 ⇐⇒ βγγδ ≡ αx mod p

Esta verificacao esta correcta porque

βγγδ ≡ αaγαkδ ≡ αx mod p,

porque aγ + kδ ≡ x mod p− 1.Bob calcula a sua assinatura utilizando o valor secreto a, que faz parte

da sua chave e o valor secreto k (que so deve ser alterado sempre que se querassinar uma mensagem x). A verificacao e obtida usando somente informacaopublica.

Exemplo. Seja p = 467, α = 2 e a = 127. Entao β ≡ 2127 ≡ 132 mod 467.Suponhamos que Bob quer assinar a mensagem x = 100. Primeiro gera o

101

numero aleatorio k = 213 que e primo com 466 (como tinha de ser). Entao213−1 ≡ 431 mod 466. A assinatura de (x, k) passa a ser (29, 51), porque

γ ≡ 2213 ≡ 29 mod 467

eδ ≡ (100− 127 · 29) · 431 ≡ 51 mod 466.

Para verificar a assinatura basta calcular

132292951 ≡ 189 mod 467

e2100 ≡ 189 mod 467.

Portanto, a assinatura e valida.

8.3.1 Forjar assinaturas ElGamal

Vejamos agora a seguranca desta assinatura digital. Suponhamos que Olgapretende forjar uma assinatura para a mensagem x, sem saber a. Se Olgaescolher um valor γ e tentar encontrar o valor δ correspondente, tem quecalcular o logaritmo discreto logγ(α

xβ−γ) mod p. Por outro lado, se Olgaescolher δ e tentar encontrar o valor γ correspondente tem que resolver acongruencia

βγγδ ≡ αx mod p.

Ate agora nao foi encontrada uma maneira pratica (em termos computa-cionais) para resolver esta congruencia.

Resta ainda a possibilidade de que haja uma maneira de calcular γ e δsimultaneamente de tal modo que (γ, δ) seja uma assinatura de x. Ate agora,ainda ninguem descobriu uma maneira de efectuar este calculo, mas tambemninguem provou que este calculo nao pode ser efectuado.

Se Olga escolher γ e δ e depois tentar descobrir x tera mais uma vez quecalcular o logaritmo discreto logα(β

γγδ) mod p. Portanto, Olga nao podeassinar uma mensagem aleatoria utilizando este processo.

No entanto, Olga pode assinar uma mensagem aleatoria escolhendo γ, δ ex simultaneamente: Sejam i e j inteiros, com 0 ≤ i, j ≤ p−2, e (j, p−1) = 1.

102

Em seguida, calcula-se

γ ≡ αiβj mod p

δ ≡ −γj−1 mod p− 1

x ≡ −γij−1 mod p− 1.

Entao (γ, δ) e uma assinatura valida para a mensagem x porque

βγγδ ≡ βγ(αiβj)−γj−1

mod p

≡ βγα−iγj−1

β−γ mod p

≡ α−iγj−1

mod p

≡ αx mod p.

Vejamos outro metodo para forjar assinaturas em que Olga utiliza umamensagem previamente assinada por Bob. Suponhamos que (γ, δ) e umaassinatura valida para a mensagem x. Consideremos h, i e j inteiros tais que0 ≤ h, i, j ≤ p− 2 e (hγ − jδ, p− 1) = 1. Em seguida, calcula-se

λ ≡ γhαiβj mod p

µ ≡ δλ(hγ − jδ)−1 mod p− 1

x′ ≡ λ(hx+ iδ)(hγ − jδ)−1 mod p− 1.

Entao

βλλµ ≡ βλ(γhαiβj)δλ(hγ−jδ)−1

mod p

≡ βλ(βjδ−hγ)λ(hγ−jδ)−1

(βhγ)λ(hγ−jδ)−1

(γδ)hλ(hγ−jδ)−1

αiδλ(hγ−jδ)−1

mod p

≡ βλβ−λ(βγγδ)hλ(hγ−jδ)−1

αiδλ(hγ−jδ)−1

mod p

≡ αxhλ(hγ−jδ)−1

αiδλ(hγ−jδ)−1

mod p

≡ αλ(hγ−jδ)−1(xh+iδ) mod p

≡ αx′mod p.

Portanto, (λ, µ) e uma assinatura valida para x′.Ambos estes metodos servem para forjar assinaturas, mas nao parecem

permitir que um oponente consiga forjar uma assinatura para uma mensagemque ele proprio escolha, sem resolver o problema do logaritmo discreto. As-sim, estes metodos nao parecem ameacar a seguranca da assinatura ElGamal.

103

8.3.2 Falhas de protocolo

Nesta seccao vamos descrever processos para quebrar a assinatura ElGamal,quando esta e utilizada de uma maneira descuidada.

Primeiro, o valor aleatorio k usado na assinatura nao deve ser revelado,caso contrario Olga pode obter a chave secreta a, da seguinte maneira:

a ≡ (x− kδ)γ−1 mod p.

Claramente, se Olga conhecer a, pode forjar assinaturas para qualquer men-sagem.

Outra falha na utilizacao da assinatura ElGamal ocorre quando o mesmovalor k e usado para assinar duas mensagens x1 e x2. Suponhamos que (γ, δ1)e uma assinatura de x1 e (γ, δ2) e uma assinatura de x2, onde γ ≡ αk mod p.Entao

βγγδ1 ≡ αx1 mod p

eβγγδ2 ≡ αx2 mod p.

Dondeαx1−x2 ≡ γδ1−δ2 ≡ αk(δ1−δ2) mod p.

Esta ultima equacao e equivalente a

x1 − x2 ≡ k(δ1 − δ2) mod p− 1. (8.1)

Como δ1 − δ2 pode nao ter inverso mod p − 1, nao podemos calcular kimediatamente, mas este problema pode ser ultrapassado se dividirmos todosos termos pelo maximo divisor comum entre δ1 − δ2 e p− 1: Seja

d = (δ1 − δ2, p− 1)

entao d | (x1 − x2). Definimos

x′ ≡ x1 − x2

d

δ′ ≡ δ1 − δ2d

p′ ≡ p− 1

d.

104

Entao, a congruencia (8.1) fica

x′ ≡ kδ′ mod p′

e como (δ′, p′) = 1, podemos calcular o inverso de δ′ mod p′. Assim

k ≡ x′δ′−1 mod p′.

A esta solucao mod p′ correspondem d solucoes da congruencia (8.1), dadaspor k ≡ x′δ′−1 + ip′ mod p − 1, com 0 ≤ i ≤ d − 1. Para determinar asolucao correcta basta verificar quando e que γ ≡ αk mod p.

8.4 DSS

A assinatura digital standard (digital standard signature - DSS) e uma mod-ificacao da assinatura ElGamal, adoptada em 1 de Dezembro de 1994 pelogoverno federal dos Estados Unidos da America. Comecamos por explicarporque foi necessario efectuar modificacoes a assinatura ElGamal e como eque estas modificacoes foram conseguidas.

Em muitas situacoes, uma mensagem e cifrada e decifrada uma unicavez, portanto basta que o sistema criptografico seja seguro nesta ocasiao.Por outro lado, uma mensagem assinada pode ser um documento legal comopor exemplo um contracto ou um testamento, sendo assim muito provavelque seja necessario verificar a assinatura muitos anos apos a mensagem serassinada. Por esta razao e necessario tomar mais precaucoes relativamente aseguranca de uma assinatura do que relativamente a seguranca de um sistemacriptografico. Como a assinatura digital ElGamal nao e mais segura que oproblema do logaritmo discreto, temos que usar um primo p grande, com pelomenos 512 bits, para garantir alguma seguranca, sendo sugerido por muitaspessoas que p deve ter pelo menos 1024 bits, para manter a assinatura segurapor varios anos. Mas para muitas aplicacoes, varias envolvendo smart cards,e desejavel ter assinaturas mais pequenas. A assinatura digital standardmodifica a assinatura ElGamal de maneira a usar uma assinar uma mensagemcom 160 bits (usando uma assinatura de 320 bits) e onde os calculos saoefectuados usando um primo com pelo menos 512 bits. A ideia e trabalharnum subgrupo de Z∗

p com ordem 2160.A primeira alteracao e definir δ da seguinte maneira

δ ≡ (x+ aγ)k−1 mod p− 1.

105

A verificacao passa a ser

αxβγ ≡ γδ mod p.

Quando existe o inverso de δ mod p − 1 (i. e. se (x + aγ, p − 1) = 1),podemos modificar a condicao anterior para obter

αxδ−1

βγδ−1 ≡ γ mod p. (8.2)

Se existir um primo q com 160 bits tal que q | p− 1, podemos obter umelemento α em Z∗

p tal que a ordem de α mod p e q. Este elemento pode serconstruıdo a partir de uma raiz primitiva α0 de p, fazendo

α ≡ αp−1q

0 mod p.

Portanto, no DSS em vez de utilizarmos uma raiz primitiva de p iremosutilizar um elemento de Z∗

p cuja ordem tem 160 bits. Tal como na assinaturaElGamal, definimos

β ≡ αa mod p

eγ ≡ αk mod p,

onde k e gerado aleatoriamente. Entao β e γ tambem tem ordem q. Por-tanto, os expoentes de α e β em (8.2) podem ser reduzidos mod q. Masse reduzirmos γ mod q em (8.2) entao todo o lado esquerdo da congruenciatem tambem de ser reduzido mod q.

Resumindo, a assinatura digital standard e obtida do seguinte modo:Seja p um primo com pelo menos 512 bits e seja q um primo com 160

bits tal que q | p − 1. Seja α ∈ Z∗p com ordem q, a ∈ Z∗

p e β ≡ αa mod p.Os valores p, q, α e β sao publicos e a e secreto. Escolhemos 1 ≤ k ≤ q − 1aleatoriamente e definimos

sig(x, k) = (γ, δ),

onde x ∈ Z∗q,

γ ≡ (αk mod p) mod q

eδ ≡ (x+ aγ)k−1 mod q.

106

Para efectuar a verificacao, calculamos

e1 ≡ xδ−1 mod q

ee2 ≡ γδ−1 mod q

ver(x, γ, δ) = 1 ⇐⇒ γ ≡ (αe1βe2 mod p) mod q.

Precisamos que δ ≡ 0 mod q pois precisamos do inverso de δ mod qpara verificar a assinatura. Se Bob obtiver um valor δ ≡ 0 mod q deveescolher um outro valor para k e calcular novos valores para γ e δ. Note quea probabilidade de δ ≡ 0 mod q e aproximadamente 2−160, portanto muitoraramente temos que modificar os valores.

Exemplo. Suponhamos que q = 101 e p = 78q + 1 = 7879. Entao 3 e umaraiz primitiva de p e α ≡ 378 ≡ 170 mod 7879 tem ordem q. Seja a = 75.Entao β ≡ 17075 ≡ 4567 mod 7879. Suponhamos que Bob quer assinar amensagem x = 22 e escolhe aleatoriamente k = 50. Entao

k−1 ≡ 99 mod q.

Assim,γ ≡ 17050 mod 7879 ≡ 2518 ≡ 94 mod 101

eδ ≡ (22 + 75 · 94) · 99 ≡ 97 mod 101.

A assinatura da mensagem x passa a ser o par (94, 97). Para verificar aassinatura calculamos

δ−1 ≡ 25 mod 101

e1 ≡ 22 · 25 ≡ 45 mod 101

e2 ≡ 94 · 25 ≡ 27 mod 101.

Como17045456727 mod 7879 ≡ 2518 ≡ 94 ≡ γ mod 101

entao a assinatura e valida.

107

Quando DSS foi proposto, o comprimento do primo p foi fixado em 512bits. Apos varias crıticas, foi permitido ter primos cujo numero de bits edivisıvel por 64 e que tenham entre 512 e 1024 bits. Em 2000 o numero debits do primo p foi fixado em 1024 bits. Em 2006 foi sugerido o uso de primoscom 2048 bits para assinaturas cujo tempo de vida se prolongue para alem de2010. Para mais informacoes consultar os documentos publicados pelo NIST(National Institute of Standards and Technology).

108

Capıtulo 9

Funcoes de sıntese

As assinaturas que estudamos no capıtulo anterior so nos permitem assinarmensagens pequenas. Por exemplo, se utilizarmos o DSS, uma mensagemcom 160 bits e assinada com uma assinatura de 320 bits. Em geral, pre-cisamos de assinar mensagens muito maiores, e. g. documentos legais. Umamaneira de resolver este problema e dividir a mensagem em partes e assinarcada parte. Este processo levanta varios problemas: Uma mensagem enormetera uma assinatura (de facto, a uniao de varias assinaturas) enorme. Outradesvantagem deste processo e que a integridade da mensagem original e per-dida.

A maneira mais utilizada para resolver os problemas descritos e recorrera funcoes hash (ou funcoes de sıntese). Estas funcoes reduzem a mensagemoriginal a uma mensagem de tamanho aceitavel (e. g. 160 bits no caso doDSS). So a mensagem reduzida e que e assinada.

Definicao. Seja h uma funcao de sıntese. Temos uma colisao se dadas duasmensagens x e y, tivermos h(x) = h(y).

Definicao. Seja x uma mensagem. Uma funcao de sıntese h e fracamentelivre de colisoes se for computacionalmente impraticavel encontrar uma men-sagem x′ = x tal que h(x) = h(x′).

Definicao. Uma funcao de sıntese h e fortemente livre de colisoes se forcomputacionalmente impraticavel encontrar duas mensagens x e x′ diferentestais que h(x) = h(x′).

109

9.1 Ataque do Aniversario

Nesta seccao vamos determinar uma condicao necessaria para a seguranca defuncoes de sıntese que apenas depende do tamanho das mensagens reduzidas.Esta condicao resulta de um metodo para encontrar colisoes conhecido comoo ataque do aniversario e que esta relacionado com o famoso paradoxo dosaniversarios. O paradoxo dos aniversarios diz que se tivermos um grupo de23 pessoas entao ha duas pessoas que nasceram no mesmo dia, com maisde 0.5 de probabilidade e nao e realmente um paradoxo, mas simplesmentecontra-intuitivo.

Seja h : X → Z uma funcao de sıntese, com X e Z finitos e tais que|X| ≥ 2|Z|. Suponhamos que |X| = m e |Z| = n. Claramente, ha pelomenos n colisoes, o problema e como encontra-las. Uma maneira e escolheraleatoriamente k elementos x1, . . . , xk ∈ X distintos, calcular h(xi), para1 ≤ i ≤ k e depois determinar se houve colisoes. Este processo corresponde aatirar aleatoriamente k bolas para n caixas e depois verificar se alguma caixatem mais de uma bola. Vamos calcular um minorante da probabilidade deencontrar uma colisao por este metodo. Comecamos por assumir que

|h−1(z)| ≈ m

n,

para qualquer z ∈ Z. Esta hipotese e razoavel, pois se a funcao h naodistribuir os elementos de X pelos elementos de Z de maneira aproximada-mente igual, entao a probabilidade de encontrar colisoes aumentara, e nos soqueremos um minorante desta probabilidade.

Sejam z1, . . . , zk os elementos que vao sendo obtidos atraves da funcao desıntese h. O valor z1 pode ser qualquer, mas a probabilidade de z2 = z1 e1−1/n, a probabilidade de z3 = z1 e z3 = z2 e 1−2/n, e assim sucessivamente.Portanto, uma estimativa de que nao haja qualquer colisao apos k valores e

(1− 1

n)(1− 2

n) · · · (1− k − 1

n) =

k−1∏i=1

(1− i

n).

A serie de Taylor da funcao exponencial da-nos a seguinte expansao

e−x = 1− x+x2

2!− x3

3!· · · ,

o que implica que 1−x ≈ e−x quando x e pequeno. Entao a nossa estimativa

110

para a probabilidade de colisoes e

k−1∏i=1

(1− i

n) ≈

k−1∏i=1

e−in = e−

k(k−1)2n .

Portanto, estimamos a probabilidade de haver pelo menos uma colisao comosendo

ϵ = 1− e−k(k−1)

2n .

Entao

e−k(k−1)

2n ≈ 1− ϵ

−k(k − 1)

2n≈ log(1− ϵ)

k2 − k ≈ −2n log(1− ϵ)

donde

k ≈√

2n log1

1− ϵ.

Se tomarmos ϵ = 0.5 obtemos

k ≈ 1.177√n.

Portanto, se aplicarmos a funcao de sıntese a pouco mais de√n elementos

de X obtemos uma colisao com probabilidade 50%.Se considerarmos X o conjunto de todos os humanos, Y o conjunto dos

365 dias de um ano comum e h(x) a data de aniversario da pessoa x entao1.177

√365 ≈ 22.49 e ha mais de 0.5 de probabilidade de que se encontre

duas pessoas que comemorem o aniversario no mesmo dia num grupo de pelomenos 23 pessoas.

Se as mensagens reduzidas apos a aplicacao de uma funcao de sıntesetiverem 40 bits entao o ataque do aniversario diz-nos que iremos ter umacolisao com probabilidade 0.5 se efectuarmos aproximadamente 220 (poucomais de um milhao) de reducoes.

9.2 Funcoes de sıntese comprovadamente se-

guras

Ha dois tipos de funcoes de sıntese: Por um lado temos funcoes de sıntesebaseadas em problemas matematicos, e portanto a sua seguranca resulta

111

de provas matematicas rigorosas. Estas funcoes de sıntese nao sao muitoutilizadas na pratica devido a sua complexidade e por serem muito lentas. Aestas funcoes, chamamos funcoes de sıntese comprovadamente seguras. Comoexemplos temos

1. Funcao de sıntese de Chaum-van Heijst-Pfitzmann baseada no pro-blema do logaritmo discreto;

2. VSH (very smooth hash function) baseada no problema de determinarraızes quadradas modulares;

3. ECOH (elliptic curve only hash function) baseada em curvas elıpticase no problema do saco-mochila;

4. FSB (fast syndrome based hash function) baseada em teoria dos codigose relacionada com os sistemas criptograficos de McEliece e de Nieder-reiter;

5. SWIFFT baseada na transformada de Fourier rapida (fast Fourier trans-form).

A outra categoria de funcoes de sıntese inclui funcoes que tem como basenao um problema matematico difıcil mas sim sao definidas de uma maneiraad hoc, onde os bits da mensagem sao misturados de modo a obter umafuncao de sıntese. Pretende-se que sejam difıceis de quebrar, mas nao hademonstracoes formais deste facto. Como exemplos temos MD4, MD5, MD6,SHA1, SHA2 e WHIRLPOOL.

O SHA2 esta implementado em varios protocolos e aplicacoes de segu-ranca, como por exemplo TLS, SSL, PGP, SSH, S/MIME e IPsec. Vere-mos alguns destes protocolos mais tarde. O MD5 e muito utilizado paraarmazenar passwords.

O NIST (National Institute of Standards and Technology) criou umacompeticao para encontrar uma nova funcao de sıntese para substituir oSHA2, que se passara a chamar SHA3. Esta competicao ira terminar em2012. As funcoes ECOH, FSB, SWIFFT e MD6 foram eliminadas na primeiraronda. As funcoes finalistas sao

1. BLAKE;

2. Grøstl, que usa uma S-box, como o AES;

112

3. JH;

4. Keccak;

5. Skein.

9.2.1 Funcao de sıntese Chaum-van Heijst-Pfitzmann

Nesta seccao descrevemos a funcao de sıntese de Chaum, van Heijst e Pfitz-mann que e baseada no problema do logaritmo discreto.

Seja q um primo grande tal que 2q + 1 = p e primo (os primos queverificam esta condicao chamam-se primos de Sophie Germain). Sejam α eβ raizes primitivas de p. A funcao de sıntese h : Zq ×Zq → Z∗

p e definida por

h(x1, x2) ≡ αx1βx2 mod p.

O seguinte resultado descreve como e que uma so colisao pode afectar aesta funcao de sıntese.

Teorema 9.1. Uma colisao da funcao de sıntese de Chaum-van Heijst-Pfitzmann permite calcular o logaritmo discreto logα β de uma maneira efi-ciente.

Demonstracao: Suponhamos que temos uma colisao

h(x1, x2) = h(x3, x4),

onde (x1, x2) = (x3, x4). Entao

αx1βx2 ≡ αx3βx4 mod p,

ou sejaαx1−x3 ≡ βx4−x2 mod p.

Seja d = (x4−x2, p−1). Como p−1 = 2q e q e primo entao d ∈ {1, 2, q, p−1}.Vamos considerar cada um destes valores para d.

Suponhamos que d = 1 e seja y ≡ (x4 − x2)−1 mod p− 1. Entao

β ≡ β(x4−x2)y ≡ α(x1−x3)y mod p.

Portanto,logα β ≡ (x1 − x3)(x4 − x2)

−1 mod p− 1.

113

Em seguida, consideramos d = 2. Como q e ımpar, temos (x4−x2, q) = 1.Seja y ≡ (x4 − x2)

−1 mod q. Entao (x4 − x2)y = kq + 1, para algum inteirok, donde

β(x4−x2)y ≡ βkq+1 ≡ (−1)kβ mod p.

Portanto,logα β ≡ (x1 − x3)y mod p− 1

oulogα β ≡ (x1 − x3)y + q mod p− 1,

onde a ultima congruencia resulta de

αq ≡ −1 mod p.

Como e facil determinar qual daquelas congruencias e a correcta, conseguimostambem determinar o logaritmo discreto logα β.

Agora, consideramos d = q. Como 0 ≤ x2, x4 ≤ q − 1 entao q so dividex4 − x2 se x4 − x2 = 0. Mas se x4 = x2 entao p− 1 tambem divide x4 − x2.Portanto, o caso d = q nunca acontece.

Como vimos atras, se d = p− 1 entao x4 = x2. Neste caso obtemos

αx1βx2 ≡ αx3βx2 mod p,

isto eαx1 ≡ αx3 mod p,

o que implica que x1 = x3. Mas como (x1, x2) = (x3, x4), isto nao podeacontecer.

Portanto, so podemos ter dois casos e em cada um deles e possıvel calcularo logaritmo discreto de β na base α. 2

Podemos assim concluir que alguem que consiga descobrir colisoes paraesta funcao de sıntese, conseguira calcular um logaritmo discreto consideradodifıcil.

O teorema anterior mostra que se for computacionalmente impraticavelcalcular logα β em Zp entao a funcao de sıntese Chaun-van Heijst-Pfitzmanne fortemente livre de colisoes.

114

9.2.2 VSH

Seja n uma chave publica RSA (n = pq). Sejam p1 = 2, p2 = 3, . . . . Seja k,o comprimento dos blocos, o maior inteiro tal que

k∏i=1

pi < n.

Seja m = (m1,m2, . . . ,ml) uma mensagem de l bits, com mi ∈ {0, 1} eassuma-se que l < 2k. Para calcular h(m) procede-se da seguinte maneira:

1. x0 = 1;

2. Seja L = [ lk], L e o numero de blocos.Tome-se mi = 0 para l < i ≤ Lk.

Neste passo estamos a completar a mensagem com zeros.

3. Represente-se l em binario, isto e

l =k∑

i=1

li2i−1,

com li ∈ {0, 1}. Defina-se mLk+i = li, com 1 ≤ i ≤ k.

4. Para j = 0, 1, . . . , L, calcule-se

xj+1 ≡ x2j

k∏i=1

pkj+ii mod n.

5. Devolva xL+1.

Esta funcao de sıntese e fortemente resistente a colisoes.

115

Bibliografia

[1] F. L. Bauer, Decrypted Secrets, Springer, 2007.

[2] J. A. Buchmann, Introduction to cryptography, Springer, 2001.

[3] R. Crandall e C. Pomerance, Prime Numbers - A Computacional Per-spective, Springer, 2001.

[4] G. H. Hardy e E. M. Wright, An Introduction to the Theory of Numbers,Oxford, 1979.

[5] J. Hoffstein, J. Pipher & J. H. Silverman, An Introduction to Mathe-matical Cryprography, Springer, 2008.

[6] N. Koblitz, A Course in Number Theory and Cryptography, Springer,1987.

[7] R. E. Smith, Internet Cryptography, Addison-Wesley, 1997.

[8] W. Stallings, Cryptography and network security, 5th Edition, PrenticeHall, 2010.

[9] D. R. Stinson, Cryptography, Theory and Practice, 3rd Edition, CRCPress, 2006.

116