Criptografia e Segurança

Transcrição

Criptografia e Segurança
Paulo J. Almeida
Departamento de Matemática da Universidade de Aveiro
18 de Julho de 2012
Conteúdo
1 Preliminares
1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Vocabulário . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 História . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
4
4
6
2 Complexidade
12
2.1 Estimativas de tempo . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3 Criptografia Simétrica
3.1 Introdução . . . . . . . . . . . . . . . . . . . . .
3.2 Cifra de Substituição . . . . . . . . . . . . . . .
3.3 Criptoanálise clássica . . . . . . . . . . . . . . .
3.4 Criptoanálise da Cifra de Substituição . . . . .
3.5 Cifra de Deslocamento . . . . . . . . . . . . . .
3.6 Algoritmo de Euclides e inversos mod n . . . .
3.7 Cifra Afim . . . . . . . . . . . . . . . . . . . . .
3.8 Função φ de Euler . . . . . . . . . . . . . . . .
3.9 Criptoanálise da Cifra Afim . . . . . . . . . . .
3.10 Cifra de Vigenère . . . . . . . . . . . . . . . . .
3.11 Criptoanálise da cifra de Vigenere . . . . . . . .
3.12 Cifra de Hill . . . . . . . . . . . . . . . . . . . .
3.13 Ataque à cifra de Hill . . . . . . . . . . . . . . .
3.14 Cifra de Permutação . . . . . . . . . . . . . . .
3.15 Cifras de Fluxo . . . . . . . . . . . . . . . . . .
3.16 Cifra de Fluxo baseada no LFSR . . . . . . . .
3.17 Criptoanálise da cifra de fluxo baseada no LFSR
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
19
20
22
25
26
32
33
34
36
37
42
43
43
44
45
46
4 Criptografia de chave pública
4.1 Teorema Chinês dos Restos . . . . . . . . . .
4.2 Lagrange, Euler e Fermat . . . . . . . . . . .
4.3 Raı́zes primitivas . . . . . . . . . . . . . . . .
4.4 Exponenciação modular rápida . . . . . . . .
4.5 RSA . . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Ataque do expoente público pequeno .
4.6 Resı́duos quadráticos . . . . . . . . . . . . . .
4.7 Algoritmo de Tonelli-Shanks . . . . . . . . . .
4.8 Cifra de Rabin . . . . . . . . . . . . . . . . .
4.9 Protocolo Diffie-Hellman . . . . . . . . . . . .
4.9.1 Ataque do homem no meio . . . . . . .
4.10 Sistema ElGamal . . . . . . . . . . . . . . . .
4.10.1 Ataque da repetição da chave efemera .
4.11 Sistema Merkle-Hellman . . . . . . . . . . . .
5 Primalidade
5.1 Teste de Fermat . . . . . .
5.2 Teste de Miller-Rabin . . .
5.3 Teste de Solovay-Strassen
5.4 Teste n − 1 de Lucas . . .
6 Factorização
6.1 Método p − 1 de Pollard
6.2 Método ró de Pollard . .
6.3 Factorização de Fermat .
6.4 Crivo quadrático . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
49
53
53
54
55
56
57
65
66
69
70
71
72
72
.
.
.
.
75
76
77
79
80
.
.
.
.
82
82
83
85
90
7 Logaritmo Discreto
94
7.1 Enumeração . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
7.2 Algoritmo passos de bebé passos de gigante . . . . . . . . . . . 95
7.3 Cálculo de ı́ndices . . . . . . . . . . . . . . . . . . . . . . . . . 96
8 Assinaturas digitais
8.1 Introdução . . . . . . . .
8.2 Assinatura RSA . . . . .
8.3 Assinatura ElGamal . .
8.3.1 Forjar assinaturas
. . . . . .
. . . . . .
. . . . . .
ElGamal
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
99
99
100
101
102
8.4
8.3.2 Falhas de protocolo . . . . . . . . . . . . . . . . . . . . 104
DSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
9 Funções de sı́ntese
9.1 Ataque do Aniversário . . . . . . . . . . . . . . . . . .
9.2 Funções de sı́ntese comprovadamente seguras . . . . . .
9.2.1 Função de sı́ntese Chaum-van Heijst-Pfitzmann
9.2.2 VSH . . . . . . . . . . . . . . . . . . . . . . . .
3
.
.
.
.
.
.
.
.
.
.
.
.
109
. 110
. 111
. 113
. 115
Capı́tulo 1
Preliminares
1.1
Introdução
Alice deseja enviar uma mensagem a Bob sem que Olga a perceba, no caso
desta interceptar a mensagem. Com este objectivo, Alice pode cifrar a
mensagem antes de a enviar a Bob. Bob recebe a mensagem e decifra-a.
Critografia é a ciência que estuda estas duas acções. Se Carla intercepta
a mensagem cifrada, pode tentar quebrar a cifra e ler a mensagem. Criptoanálise é a ciência em que se estuda métodos ou processos para quebrar
cifras. Criptologia engloba tanto a Criptografia como a Criptoanálise.
Durante este curso iremos aprender vários sistemas criptográficos, alguns dos quais são correntemente usados nas diversas comunicações de mensagens (militares, espionagem, números de PIN, conversações telefónicas,
transacções bancárias, Internet, e-mail, etc.). Ao mesmo tempo, Estudaremos métodos para quebrar certos cifras e a razão pela qual alguns dos sistemas criptográficos são considerados inquebráveis. Iremos também estudar
funções de sı́ntese (que são uma espécie de impressão digital), assinaturas
e identificação digital e diversos protocolos de segurança. As ferramentas
essenciais deste curso serão Teoria dos Números e algumas noções de Álgebra.
1.2
Vocabulário
Mensagem original (ou texto plano) - Mensagem que se pretende tornar secreta, por exemplo OLA;
Mensagem cifrada - A mensagem secreta que se obtém após ter sido
4
cifrada, por exemplo ROD (usando o sistema criptográfico utilizado por Júlio
César);
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;
Codificação simples - Transformar a mensagem original em números ou
bits1 . Por exemplo, se fizermos a transformação 2 → 0, A→ 1, ..., Z→ 26
então a palavra OLA passava a 15 12 1. Usualmente utiliza-se o código
ASCII, que representa cada sı́mbolo por 8 bits (byte): A→ 01000001, B→
01000010, a→ 01100001, 0 → 00110000, ? → 00111111, etc;
Descodificar - Transformar números ou bits em mensagens;
Monogrâmica (ou monográfica) - Uma cifra que traduz um a um os
sı́mbolos do texto original em texto cifrado;
Poligrâmica (ou poligráfica - Uma cifra que traduz vários sı́mbolos do
texto original, em grupo e ao mesmo tempo, em texto cifrado;
Cifra de transposição ou permutação - Uma cifra que re-arranja e/ou
permuta as letras, sı́mbolos ou bits do texto plano;
Cifra de substituição - Uma cifra que substitui letras, sı́mbolos ou bits
por outros sem lhes alterar a ordem;
Sistema criptográfico - Conjunto de procedimentos para cifrar e decifrar
uma mensagem;
Chave - Num sistema criptográfico, corresponde a um nome, uma palavra,
uma frase, etc, que permite cifrar ou decifrar uma mensagem.
Sistema criptográfico de chave simétrica - Necessita de uma chave secreta
partilhada pelo emissor e pelo receptor. O emissor e o receptor têm que
concordar com uma chave antes do inı́cio da transmissão da mensagem;
Sistema criptográfico de chave pública - Cada utilizador tem uma chave
para cifrar que é pública e foi publicada e uma chave para decifrar que é
secreta (normalmente só utilizadores autorizados têm a chave secreta);
Assinatura - Processo pelo qual o emissor pode certificar o receptor da sua
identidade. Nos sistemas de chave pública este processo evita que utilizadores
inimigos enviem mensagens enganosas;
1
bits é o plural de bit - binary digit
5
Criptoanálise - É o processo pelo qual o inimigo (quem não está autorizado
a decifrar a mensagem) tenta transformar a mensagem cifrada na mensagem
original.
Os processos para cifrar e decifrar devem ser fáceis de aplicar para os
utilizadores autorizados mas deve ser difı́cil um inimigo ou utilizador não
autorizado decifrar as mensagens. Teoria dos números é uma excelente fonte
de problemas com alguns mecanismos fáceis e alguns mecanismos difı́ceis,
portanto aparenta ser uma óptima área para ser usada em criptologia.
1.3
História
A história da criptografia aparenta ter sido iniciada no antigo Egipto, cerca
de 1900 a.C. pelo arquitecto Khnumhotep II, na tempo do faraó Amenemhet
II. O escriba de Khnumhotep II substituiu alguns trechos e palavras de documentos importantes por sı́mbolos estranhos de modo a dificultar que ladrões
chegassem a tesouros reportados nesses documentos.
Alguns séculos mais tarde aparecem outros métodos de transmitir mensagens de modo secreto, por exemplo na Mesopotâmia, Assı́ria, China, India
e Egipto. Exemplos desses métodos são:
Tatuagens com mensagens na cabeça de escravos. Infelizmente
era preciso esperar o cabelo crescer antes de ”enviar”a mensagem.
A decifração era feita no barbeiro;
Marcas na madeira de placas de cera. As marcas eram escondidas
com cera nova. Para decifrar, bastava derreter a cera;
Mensagens dentro do estômago de animais de caça.
Este tipo de ocultação de mensagens toma o nome de esteganografia e
distingue-se da criptografia porque neste caso a mensagem não é alterada e
baseia-se no facto de um interceptor não saber da existência 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 ocultação de mensagens em imagens digitais, através da alteração de
alguns bits em cada componente da cor e marcas ocultas nas notas bancárias
6
para evitar a sua falsificação. Apesar da sua aparente semelhança com criptografia, os métodos de esteganografia são muito distintos dos utilizados em
criptografia e não serão estudados durante este curso.
Cerca de 600 a.C., os hebreus criaram alguns sistemas criptográficos
aquando da escrita do livro de Jeremias, nomeadamente o Atbash, que consiste de uma troca simples entre as letras do hebraico, por ordem inversa.
O primeiro sistema criptográfico de uso militar terá sido o Scytale ou
Bastião de Licurgo, utilizado pelo general espartano Pasanius, em 475 a.C..
O scytale consiste em escrever a mensagem numa tira estreita de couro ou
pergaminho quando esta está enrolada em torno de um bastião de madeira.
A mensagem original é escrita no sentido do comprimento do bastião e, portanto, quando a tira é desenrolada obtém-se a mensagem cifrada. Para voltar
a obter a mensagem original, deve-se enrolar outra vez a tira num bastião
com o mesmo perı́metro e forma. Este é um exemplo de uma cifra de transposição. Esta é ainda a ideia de muitas técnicas populares actuais.
Na India, por volta de 300 a. C., apareceu um livro intitulado Arthasastra, atribuı́do a Kautilya, onde são referidos os primeiros métodos de
criptoanálise. Estes processos são recomendados para diplomatas. O famoso
Kama Sutra de Vatsayana, menciona a criptografia nas artes (yogas) 44 e
45, de entre a sua lista de 64 artes e ciências que todos devem saber (Part I,
capı́tulo 3, http://www.sacred-texts.com/sex/kama/index.htm).
Júlio César utilizou uma cifra que consistia em substituir cada letra pela
letra que se encontra três posições depois no alfabeto. Este é um exemplo de
uma cifra de deslocamento.
No século VIII, al-Khalil, escreveu o livro Kitab al Mu’amma (que significa ”O livro das mensagens criptográficas”). Infelizmente este livro desapareceu. al-Khalil decifrou um criptograma bizantino antigo quando supôs,
correctamente, que o inı́cio do criptograma era ”Em nome de Deus”. Este
método, conhecido como o método da palavra provável, foi usado para ajudar a decifrar mensagens cifradas pelo Enigma, durante a Segunda Guerra
Mundial. Cerca de 100 anos depois, al-Kindi, escreveu um outro livro sobre
criptografia, ainda existente, intitulado Risalah fi Istikhraj al Mu’amma (Escritos sobre a decifração de mensagens criptográficas). al-Kindi considerou
análises estatı́sticas para quebrar cifras, processo ainda usado na actualidade.
Em 1466, Leon Battista Alberti, escreveu um ensaio, no qual menciona
uma cifra em disco, criando a noção de cifra poli-alfabética.
Giovan Batista Belaso inventou, em 1553, um sistema criptográfico polialfabético a que actualmente se chama cifra de Vigenère, por ter sido fal7
samente atribuı́do a Blaise de Vigenère durante o século XIX. Este sistema
tem uma chave e uma série de diferentes cifras de César e foi considerado
indecifrável durante muito tempo, porém é facilmente quebrado utilizando
análise estatı́stica. Em 1585, Vigenère criou a noção de auto-chave, processo
ainda hoje utilizado, por exemplo no sistema DES.
Durante os séculos XVIII e XIX, assistiu-se à proliferação de Cameras
Escuras, gabinetes de espionagem, onde se utilizava a criptologia para fins
militares e fins civis, nomeadamente para decifrar mensagens diplomáticas.
Em Viena, é criada uma das mais eficientes cameras escuras, onde se decifrava cerca de 100 mensagens diplomáticas internacionais, por dia. França,
Inglaterra e Alemanha também criam os seus centros de criptoanálise, tendo
empregado diversos matemáticos famosos.
Durante a Primeira Guerra Mundial assiste-se a uma proliferação de sistemas criptográficos para usos militares. Como exemplos, temos o Playfair e
o ADFGVX.
A cifra inglesa Playfair (guerra dos Boers e Primeira Guerra Mundial)
consiste em escrever a palavra chave (que não pode ter letras repetidas)
seguida das restantes letras num quadrado cinco por cinco. Se considerarmos
a palavra chave Palmerston, obtemos
P
R
B
H
V
A L
S T
C D
IJ K
W X
M E
O N
F G
Q U
Y Z
Para cifrar um par de letras, forma-se um rectângulo do qual as letras são
vértices. A mensagem cifrada consiste dos outros dois vértices. Por exemplo,
PI é cifrado em AH. Se duas letras estão na mesma linha (resp. mesma
coluna), 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 X
a separá-las, e. g. a mensagem ASSIM passa a ser AS XS IM.
A cifra alemã ADFGVX (Primeira Guerra Mundial), utiliza uma tabela
fixa para efectuar uma substituição da mensagem original. Cada letra é
transformada no par de letras correspondente à linha e coluna onde a letra
original está.
8
A
D
F
G
V
X
A
K
9
K
E
8
U
D F
Z W
B 6
7 J
V Y
O D
4 I
G
R
C
P
3
H
S
V X
1 F
L 5
G X
A N
0 2
T M
Assim, ACHTUNG é primeiro cifrado em GV DG VG XV XA GX FV.
Esta é a parte da substituição da cifra.
Em seguida, efectua-se um deslocamento, utilizando uma chave sem letras repetidas, neste caso a chave é DEUTSCH. Constrói-se uma tabela em
que, na primeira linha está a palavra chave, na segunda linha o numeral correspondente à ordem alfabética de cada letra da primeira linha e, nas linhas
seguintes é escrita a mensagem que resultou do processo de substituição efectuado anteriormente. A mensagem cifrada é obtida, escrevendo as letras das
colunas seguindo a ordem indicada na segunda linha.
D E U T S C H
2 3 7 6 5 1 4
G V D G V G X
V X A G X F V
No nosso exemplo, a mensagem cifrada correspondente à mensagem original ACHTUNG é GF GV VX XV VX GG DA.
A grande fraqueza da cifra ADFGVX é usar uma tabela fixa para a parte
da substituição. A alternância entre substituições e deslocações permite obter
cifras bastante seguras, sendo este processo a base do DES (Data Encryption
Standard) e do AES (Advanced Encryption Standard).
Após esta guerra começam a aparecer as primeiras máquinas cifrantes que
usam rotores mecânicos. Em 1923, Arthur Scherbius, desenvolve o ENIGMA,
talvez a mais famosa máquina cifrante. O ENIGMA é utilizado pelos alemães
durante a Segunda Guerra Mundial para comunicações com os submarinos
e para deslocar as suas tropas. O ataque criptoanalı́tico ao ENIGMA foi
iniciado pelo matemático polaco Marian Rejewski (juntamente com Jerzy
Rozycki e Henryk Zygalski), que após a Polónia ter sido invadida conseguiu
passar a sua informação para França. Esta informação acabou por chegar
a 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 alemães e o envio mensagens enganosas para os alemães localizados
em França, conseguindo assim facilitar a invasão por Dunquerque. Japão
tinha a Máquina Púrpura, cujo sistema foi quebrado por equipa liderada
por William Frederick Friedman (criador da palavra criptoanálise). O sistema criptográfico utilizado pelos EUA durante Segunda Guerra Mundial,
encontra-se ainda classificado.
Nos anos 60, o Dr. Horst Feistel, liderando um projecto de pesquisa no
IBM Watson Research Lab, desenvolve a cifra Lucifer. Em 1974, a IBM apresenta Lucifer ao NBS (National Bureau of Standards), o qual, após algumas
alterações, adopta esta cifra como cifra padrão nos EUA, criando assim o
DES (Data Encryption Standard). Este sistema foi criticado desde o inı́cio
por vários investigadores e acabou por ser quebrado, usando força bruta, em
1997.
Whitfield Diffie e Martin Hellman publicam, em 1976, o artigo ”New Directions in Cryptography”, onde introduzem a ideia de criptografia de chave
pública, neste caso baseada no problema do logaritmo discreto, e avançam
com a ideia de autenticação utilizando funções de um só sentido (one way
functions). Inspirados por aquele artigo, Ronald L. Rivest, Adi Shamir e
Leonard M. Adleman, desenvolvem uma cifra de chave pública, que também
pode ser usada para assinaturas digitais, baseada no contraste entre a dificuldade de factorizar números grandes e a relativa facilidade de identificar
números primos grandes. Este sistema passou a ser conhecido como RSA
e foi patenteado. Em 1984, Taher Elgamal desenvolve o sistema ElGamal
também utilizando o problema do logaritmo discreto.
Nos anos 90 aparecem diversos sistemas criptográficos em particular o
IDEA (International Data Encryption Algorithm) de Xuejia Lai e James
Massey, que pretende ser um substituto do DES. A criptografia quântica é
introduzida em 1990. O PGP (Pretty Good Privacy) de Phil Zimmermann,
desenvolvido em 1991, ainda é um dos programas mais utilizados para proteger a privacidade do e-mail e dos arquivos guardados no computador do
utilizador. Nas versões mais recentes do PGP, é utilizado o sistema ElGamal.
Em 1997, o NIST solicitou propostas para a substituição do DES. Em 2000, o
NIST escolheu o Rijndael (de entre os finalistas estava MARS da IBM, RC6
de RSA Laboratories, Rijndael de Joan Daemen e Vincent Rijmen, Serpent
de 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́ que
o NIST (National Institute of Standards and Technology), que substituiu o
NBS, publica um plano de transição com a duração de dois anos, para que as
10
agências governamentais deixassem de utilizar o DES e passassem a utilizar
o AES.
11
Capı́tulo 2
Complexidade
Tudo indica que seja praticamente impossı́vel criar cifras absolutamente inquebráveis. É mais razoável e suficiente para o uso concreto, requerer que
um sistema seja praticamente inquebrável por um inimigo, isto é, requerer
que um sistema demore demasiado tempo (usando milhões de computadores
super-potentes) a ser quebrado. Durante este curso, iremos ver o que isto
significa em casos concretos.
2.1
Estimativas de tempo
Um tópico que é central em complexidade é a estimação do número de
operações bit necessárias para efectuar operações aritméticas ou cálculos
matemáticos num computador. Vamos começar com algumas noções básicas.
Um inteiro n pode ser escrito em qualquer base b com b > 0 inteiro.
Usamos a notação (dk−1 dk−2 · · · d1 d0 )b para significar que
n = dk−1 bk−1 + dk−2 bk−2 + · · · d1 b + d0 ,
onde os algarismos di são sı́mbolos que podem tomar valores entre 0 e b −
1 e dk−1 é não nulo. Esta representação é única dependendo apenas da
base escolhida. Quando a base é 10 escreve-se apenas dk−1 dk−2 · · · d1 d0 , sem
indicação 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 fracções podem também ser representadas em qualquer base, usandose neste caso o ponto flutuante para distinguir a parte inteira da parte fraccionária, i. e.
n = (dk−1 dk−2 · · · d1 d0 .d−1 d−2 · · · d−m )b ,
se
n=
k−1
∑
dj b j .
j=−m
Diz-se que um inteiro n tem k algarismos, quando escrito na base b, se
n = (dk−1 dk−2 · · · d1 d0 )b . Note-se que
[
]
log n
número de algarismos = [logb n] + 1 =
.
log b
Estamos em condições de calcular o tempo necessário para fazer certas
operações aritméticas. Começaremos com a adição. Os computadores trabalham no sistema binário, portanto iremos fazer as nossas operações neste
sistema, daı́ o nome de operações bit (binary digit). Consideremos a seguinte
adição:
1111
1111000
+0011110
10010110
Suponhamos que ambos os números têm k bits, adicionando-se zeros à
esquerda caso necessário. Vejamos em detalhe em que consiste esta adição.
Basicamente, temos que repetir k vezes os seguintes passos:
1. Se ambos os bits numa coluna são zero e não há transporte. Neste caso,
mete-se um zero e se estivermos na coluna k + 1 o processo termina.
Se não estivermos na coluna k + 1 passa-se à coluna seguinte;
2. Se ou (a) ambos os bits são zero e há transporte, ou (b) um dos bits é
zero e o outro é um e não há transporte, então mete-se um 1 e passa-se
à coluna seguinte; se estivermos na coluna k + 1 o processo termina.
13
3. Se ou (a) ambos os bits são um e não há transporte, ou (b) um dos bits
é zero e o outro é um e há transporte, então mete-se um 0, mete-se um
transporte na coluna seguinte e passa-se à frente;
4. Se ambos os bits são um e há transporte, mete-se um 1, mete-se um
transporte na coluna seguinte e passa-se à frente.
Chamamos operação bit a uma implementação deste processo. Portanto,
adicionar dois números com k bits demora k + 1 operações bit. Iremos ver
como descobrir o número de operações bit de várias outras operações aritméticas. O tempo que um computador demora a efectuar uma certa tarefa
é, essencialmente, proporcional ao número de operações bit. No entanto, a
constante de proporcionalidade (o número de nano-segundos que um computador demora a fazer uma operação bit) depende do computador em particular. Quando falarmos de estimar o tempo que se demora a efectuar certa
tarefa estaremos a falar do número de operações bit requeridas.
Vejamos agora o processo de multiplicar um número n com k bits por um
número m com l bits. Por exemplo,
11101
×1101
00011101
01110100
11101000
101111001
Obtemos, no máximo l linhas, onde cada linha consiste de uma cópia de
n deslocada para a direita uma certa distância. Portanto, cada linha tem
no máximo k + l − 1 bits. Temos assim que fazer, no máximo l − 1 adições,
de inteiros com k + l − 1 bits. Portanto, temos (l − 1)(k + l) operações bit.
Note-se que neste cálculo, negligenciámos o tempo necessário para ”deslocar
para a direita”e o tempo de acesso à memória. No entanto, este tempo é
considerado irrisório, quando comparado a um grande número de operações
bit. Assim, só nos interessa majorar o número de operações bit. Convém
também simplificar ao máximo as nossas estimativas. Por exemplo, se k ≥ l,
podemos estimar
tempo(k-bit× l-bit) ≤ 2kl ≤ 2k 2
14
Definição. Sejam f, g, duas funções aritméticas, i. e. funções cujo conjunto
de partida consiste dos inteiros positivos e o conjunto de chegada consiste
dos números reais (por vezes, o conjunto de chegada será o conjunto dos
complexos). 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 + a1 d + · · · + ad nd é um polinómio de grau d, com
ad > 0 então f = O(nd ).
Exemplo. log n = O(nϵ ), para qualquer ϵ > 0.
Exemplo. O número de algarismos de n na base b é O
(
log n
log b
)
= O(log n).
Exemplo. Tempo para efectuar a adição de n com m, com m ≤ n, é
O(log n).
Exemplo. Tempo para efectuar o produto de n por m, com m ≤ n, é
O(log2 n).
Note-se que os dois exemplos anteriores referem-se aos processos descritos
para efectuar estas operações. Claramente, existem outros processos para
efectuar as operações mencionadas, podendo estes demorar mais, ou menos
tempo. Por exemplo, poderı́amos ter multiplicado m por n, fazendo a adição
de n com ele próprio, m − 1 vezes. Há processos de multiplicação rápida que
permitem multiplicar dois números m ≤ n em
O(log n(log log n)(log log log n))
operações bit. A cada procedimento que nos permite efectuar certa operação
(ou resolver certa questão), chamamos algoritmo.
O algoritmo da divisão ensinado no ensino básico também tem O(kl)
operações bit, quando se divide um número com k bits por um com l bits.
15
Exemplo. Converter o inteiro n com k bits para a sua representação na base
10. Dividir n por 1010 demora O(4k) e temos que efectuar
[
]
log n
+1
log 10
divisões (tantas quantos os dı́gitos na base 10 de n). Obtemos assim
tempo(converter n para décimal) = O(k 2 ) = O(log2 n).
Exemplo. Converter o inteiro n com k bits para a sua representação na base
b. Suponhamos que b tem l bits. Dividir n por b demora O(lk) e temos que
efectuar
[
]
log n
+1
log b
divisões (tantas quantos os algarismos na base b de n). Obtemos assim
tempo(converter n para a base b) = O(lk)O(k/l) = O(k 2 ) = O(log2 n).
Exemplo. Tempo requerido para obter n!. Temos que efectuar O(n) (mais
exactamente n − 2) multiplicações, cada uma entre um número com, no
máximo, nk bits e outro, com, no máximo, k bits. Portanto, cada multiplicação demora O(nk 2 ) operações bit. Assim,
tempo(calcular n!) = O(n2 k 2 ) = O(n2 log2 n).
2.2
P versus NP
Definição. Um algoritmo para efectuar uma computação (ou responder a
uma questão), envolvendo inteiros n1 , . . . , nr de k1 , . . . , kr bits, respectivamente, é um algoritmo de tempo polinomial se existirem inteiros d1 , . . . , dr
tais que
número de operações bit = O(k1d1 · · · krdr )
Definição. Uma operação (questão, computação, tarefa) é de tempo polinomial se existir um algoritmo de tempo polinomial para a efectuar (resolver).
Dizemos que estas operações estão na classe P.
Definição. Se a prova de uma resposta, dada a uma questão, pode ser efectuada em tempo polinomial, dizemos que esta questão está na classe NP.
16
Claramente, temos que P⊂NP.
Exemplo. Questão: factorizar o número n. Se alguém conseguir resolver a
questão, basta publicar essa factorização n = m1 · · · mt . Para verificarmos
se a resposta está correcta, basta multiplicarmos os inteiros m1 , . . . , mt . Esta
verificação pode ser efectuada em tempo polinomial (t − 1 multiplicações,
onde t é muito pequeno). Portanto, a factorização está na classe NP. No
entanto, ainda não foram descobertos algoritmos para efectuar factorizações
em tempo polinomial. Assim, a factorização pode não estar na classe P.
Um dos problemas do milénio consiste em provar ou provar que é falsa,
a afirmação P = N P .
17
Capı́tulo 3
Criptografia Simétrica
Criptografia é a arte e ciência de enviar mensagens secretas. O emissor usa
uma chave para cifrar a mensagem, esta é enviada até ao receptor que usa
outra chave para a decifrar. Escrevendo letras e sinais de pontuação como
números, podemos assumir que a mensagem a enviar é um inteiro P que
é codificado num outro inteiro C. O problema consiste em inventar chaves
que tornem impossı́vel ou computacionalmente irrealizável que o inimigo (ou
qualquer pessoa que não queiramos que leia a mensagem) decifre a mensagem interceptada. Muitas vezes a criptografia usa chaves secretas que só
são conhecidas pelo emissor e pelo receptor. Se o inimigo descobre a chave
de cifrar e intercepta a mensagem cifrada, ele pode conseguir descobrir a
chave de decifrar e recuperar a mensagem original. Este foi o método que os
matemáticos ingleses usaram para decifrar o Enigma, usado pelos alemães
para comunicar entre si e, em particular, com os submarinos, na segunda
guerra mundial.
Neste capı́tulo iremos estudar alguns exemplos clássicos de criptosistemas.
3.1
Introdução
Normalmente, o primeiro passo para inventar um criptosistema consiste em
codificar a mensagem, i. e. transformar a mensagem original em números
ou 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 a
x, 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 número 125. A codificação pode
também ser feita a n-uplos de letras, n ≥ 3, fazendo-se a correspondência:
se a letra αi corresponde ao número xi então o n-uplo α1 · · · αn corresponde
a inteiro
26n−1 x1 + · · · 26xn−1 + xn .
Durante este curso, usaremos essencialmente as codificações
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 código ASCII.
Definição. Um criptosistema é um quı́ntuplo (P, C, K, E, D) que satisfaz as
seguintes condições:
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 para
decifrar correspondente dK ∈ D, tais que eK : P −→ C, dK : C −→ P
e dK (eK (x)) = x, para qualquer x ∈ P.
3.2
Cifra de Substituição
As cifras de Substituição são utilizadas à centenas de anos. Actualmente
ainda aparecem em Criptogramas nas revistas recreativas. Como o próprio
nome indica, estas cifras consistem em substituir cada letra por uma outra
letra. Nestas cifras não é necessário codificar a mensagem primeiro.
Cifra (Substituição). Seja m um inteiro positivo. Sejam P = C = Zm .
O conjunto das chaves K consiste de todas as permutações dos números
0, 1, . . . , m − 1. Sejam x ∈ P e y ∈ C. Para cada permutação π ∈ K,
definimos
eπ (x) = π(x)
19
e
dπ (y) = π −1 (y),
onde π −1 é a permutação inversa de π.
Estas cifras têm m! chaves possı́veis. No caso de m = 26, obtemos mais
de 4.0 × 1026 chaves, o que torna impraticável a busca exaustiva da chave de
um sistema criptográfico deste tipo. Mais tarde veremos como quebrar estes
sistemas.
Exercı́cio. Considere m = 26. Sabendo que foi utilizada uma cifra de substituição, decifre a seguinte mensagem na lı́ngua inglesa.
MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA
3.3
Criptoanálise clássica
Suponhamos que se deseja decifrar uma mensagem, mas não se sabe a chave.
Para isso usa-se criptoanálise. Diz-se quebrar o código ao processo de descobrir como decifrar mensagens num dado criptosistema sem se saber as
chaves. Para quebrar um código necessitamos de dois tipos de informação:
que tipo de criposistema temos, e quais são as chaves desse criptosistema.
Iremos assumir que o tipo de criptosistema a quebrar é conhecido (princı́pio
de Kerckhoff) e iremos só estudar como descobrir as chaves.
Há vários nı́veis de ataques a um criptosistema, os mais comuns são
Só mensagem cifrada(ciphertext-only): O oponente possui uma mensagem cifrada;
Texto plano conhecido (known plaintext): O oponente possui um texto
plano e a mensagem cifrada correspondente;
Texto plano escolhido (chosen plaintext): o oponente obteve acesso temporário à máquina de cifrar. Portanto pode escolher um texto plano e
cifrá-lo.
Mensagem cifrada escolhida (chosen ciphertext): O oponente obteve
acesso temporário à máquina de decifrar. Portanto pode escolher uma
mensagem cifrada e decifrá-la.
20
Letra
Probabilidade
Letra
Probabilidade
Letra
Probabilidade
Letra
Probabilidade
E
0.127
H
0.061
W
0.023
K
0.008
T
0.091
R
0.060
F
0.022
J
0.002
A
0.082
D
0.043
G
0.020
X
0.001
O
0.075
L
0.040
Y
0.020
Q
0.001
I
0.070
C
0.028
P
0.019
Z
0.001
N
0.067
U
0.028
B
0.015
S
0.063
M
0.024
V
0.010
Figura 3.1: Distribuição de Frequências na Lı́ngua Inglesa
Letra
Probabilidade
Letra
Probabilidade
Letra
Probabilidade
Letra
Probabilidade
A
0.146
D
0.050
H
0.013
J
0.004
E
0.126
M
0.047
G
0.013
X
0.002
O
0.107
T
0.047
Q
0.012
K
0.001
S
0.078
U
0.046
B
0.010
W
0.001
R
0.065
C
0.039
F
0.010
Y
0.001
I
0.062
L
0.028
V
0.009
N
0.051
P
0.025
J
0.004
Figura 3.2: Distribuição de Frequências na Lı́ngua Portuguesa
Normalmente, é preferı́vel usar textos planos sem espaços nem pontuação,
tornando o criptosistema mais seguro.
Muitas técnicas de criptoanálise utilizam as propriedades estatı́sticas de
uma lı́ngua. Nas figuras 3.1 e 3.2 estão representadas as frequências relativas
das lı́nguas Inglês e Português, respectivamente. Por vezes temos também de
usar as frequências relativas de duas ou três letras consecutivas (digramas e
trigramas). Os digramas mais frequentes na lı́ngua inglesa são: 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 na
lı́ngua inglesa são: THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS,
ETH, FOR e DTH.
21
3.4
Criptoanálise da Cifra de Substituição
Vamos complicar um pouco e analisar como se pode quebrar a cifra de substituição. 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 análise de frequência desta mensagem
cifrada
Letra
Frequência
Letra
Frequência
Letra
Frequência
A
0
J
11
S
3
B
1
K
1
T
2
C
15
L
0
U
5
D
13
M
16
V
5
E
7
N
9
W
8
F
11
O
0
X
6
G
1
P
1
Y
10
H
4
Q
4
Z
20
I
5
R
10
Como o Z aparece significativamente mais vezes que qualquer outra letra,
podemos conjecturar que dK (Z) = e. As outras letras que aparecem pelo
menos de 9 vezes são M, C, D, F, J, R, Y, N e será de esperar que estas
letras sejam obtidas a partir de t, a, o, i, n, s, h, r, mas por termos um texto
tão pequeno, as frequências não variam de modo suficiente para nos dar a
correspondência correcta.
Nesta altura, é aconselhável considerar digramas, especialmente aqueles
que contém a letra Z. Verifica-se que os digramas DZ e ZW aparecem quatro
vezes cada, que os digramas NZ e ZU aparecem três vezes cada e que os digramas RZ, HZ, XZ, FZ, ZR, ZV, ZC, ZD, ZJ aparecem duas vezes cada. Como
ZW aparece quatro vezes, WZ nunca aparece e W não é das letras que mais
aparecem, podemos conjecturar que dK (W ) = d. Como DZ aparece quatro
vezes e ZD aparece duas vezes, podemos esperar que dK (D) ∈ {r, s, t}, mas
não conseguimos, de uma maneira clara, prever qual das três possibilidades
é a correcta.
22
Assumindo dK (W ) = d, verifica-se que os únicos digramas com W no
fim, que aparecem mais que uma vez são ZW e RW. Entre os digramas mais
frequentes na lı́ngua inglesa, os únicos que terminam em d são ed e nd, donde
somos levados a conjecturar que dK (R) = n.
Antes de continuarmos a nossa análise, vejamos quais são os digramas que
mais aparecem na mensagem cifrada. Além dos digramas DZ e ZW também
MD e MR aparecem quatro vezes cada, e, além de NZ e ZU, também CD, CH,
FM, IF e NM aparecem três vezes. Atendendo aos digramas mais frequentes
na 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 são frequentes, então provavelmente temos
dK (N M ) ∈ {ha, hi}.
A última afirmação permite-nos conjecturar que dK (N ) = h e dK (M ) ∈
{a, i}.
Vejamos como fica a frase se efectuarmos as substituições conjecturadas:
-----end - - -----e----n
YIFQFM ZRWQFY VECFMD ZPCVMR
-----h------e---e---CDDUMJ NDIFEF MDZCDM QZKCEY
en - - - e-h--e
he - - - n
-----ZREXCH ZUNMXZ NZUCDR JXYYSM
e---e- ne - nd
he - e - - ed - - ZVYFZU MRZCRW NZDZJJ XZWGCH
-h-----e--- ed - - ----dHNCMFQ CHZJMX
JZWIEJ YUCFWD
edh - - e
-----ZWNMDZ VEJBTX
-----n
h-d--FCJMYR NCWJCS
n----- ed - - RTMEYI FZWDYV
- - nh - SMRNMD
- he - - n
JNZDIR
A sequência ne - nd sugere que devemos substituir C por a o que implica
que dK (M ) = i. Donde
23
-----i
end - - --a-ie - a - in
a---ih----i - ea - i
-e-a-CDDUMJ NDIFEF MDZCDM QZKCEY
en - - a e - hi - e
he - a - n
-----i
ZREXCH ZUNMXZ NZUCDR JXYYSM
e---eineand
he - e - - ed - a ZVYFZU MRZCRW NZDZJJ XZWGCH
- hai - a-e-i- ed - - --a-dHNCMFQ CHZJMX
JZWIEJ YUCFWD
edhi - e
-----ZWNMDZ VEJBTX
-a-i-n
had - a FCJMYR NCWJCS
n-i--- ed - - RTMEYI FZWDYV
- inhi SMRNMD
- he - - n
JNZDIR
Das vogais mais frequentes só nos falta determinar a letra que corresponde a o. Sabemos que esta letra é muito comum, portanto será aceitável
supor que é uma das letras D, F, J, Y. Mas D, F, J são facilmente eliminadas senão provocavam sequências de muitas vogais no texto plano. Conjecturamos então que dK (Y ) = o. Quando se faz esta substituição, obtém-se
as sequências a-ion o que sugere a terminação ation muito comum em inglês.
Assim, dK (J) = t.
o----i
end - - o
--a-ie - a - in
a - - - it
h----i - ea - i
-e-a-o
CDDUMJ NDIFEF MDZCDM QZKCEY
en - - a e - hi - e
he - a - n
t - oo - i
e-o-eineand
he - ett
- ed - a ZVYFZU MRZCRW NZDZJJ XZWGCH
- hai - a - eti ted - - t
o-a-dHNCMFQ CHZJMX
JZWIEJ YUCFWD
edhi - e
--t--ZWNMDZ VEJBTX
- ation
hadta FCJMYR NCWJCS
n-i-o- ed - o RTMEYI FZWDYV
- inhi SMRNMD
the - - n
JNZDIR
Já tı́nhamos reparado que dK (D) ∈ {r, s, t}. Atendendo à sequência dthe, faz sentido considerar que dK (D) = s. Das letras mais frequentes só nos
sobram F e r. Donde dK (F ) = r.
24
o - r - ri
end - ro
- - aris
e - a - in
ass - it
hs - r - r
iseasi
-e-a-o
CDDUMJ NDIFEF MDZCDM QZKCEY
en - - a e - hi - e
he - asn
t - oo - i
e - ore ineand
hesett
- ed - a ZVYFZU MRZCRW NZDZJJ XZWGCH
- hair a - eti ted - - t
o - a - ds
HNCMFQ CHZJMX
JZWIEJ YUCFWD
edhise
--t--ZWNMDZ VEJBTX
ration
hadta FCJMYR NCWJCS
n-i-oredso RTMEYI FZWDYV
- inhis
SMRNMD
thes - n
JNZDIR
Agora, facilmente se obtém
Our friend from Paris examined his empty glass with surprise, as
if evaporation had taken place while he wasn’t looking. I poured
some more wine and he settled back in his chair, face tilted up
towards the sun
3.5
Cifra de Deslocamento
Nesta subsecção, apresentamos as cifras de deslocamento, da qual o sistema
criptográfico utilizado por Júlio César é um exemplo. A base desta cifra,
assim como de outras cifras que estudaremos posteriormente, é a aritmética
modular.
Definição. 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
dK (y) ≡ y − K
mod m
e
25
A cifra de César é uma cifra de deslocamento, com K = 3 e m = 23. O
ROT-13, actualmente utilizado online, em newsgroups e usenet, para ocultar
mensagens ofensivas, respostas a puzzles, etc., é outro exemplo de uma cifra
de deslocamento, neste caso com K = 13 e m = 26. Note-se que, neste caso
eK (eK (x)) = x.
As cifras de deslocamento são exemplos de cifras de substituição.
As cifras de deslocamento são muito inseguras, porque há somente m
chaves possı́veis, e m é normalmente muito pequeno. Uma busca exaustiva
da chave quebra rapidamente um destes sistemas criptográficos.
Exercı́cio. A seguinte mensagem foi cifrada com uma cifra de deslocação
com m = 27. Decifre-a.
OCUAE SCMRUMLQLDQSFCMZOM
3.6
Algoritmo de Euclides e inversos mod n
Antes de vermos mais sistemas criptográficos, necessitamos de alguns resultados elementares da Teoria dos Números.
Definição. Sejam a e b dois inteiros tais que pelo menos um deles é não
nulo. Chamamos máximo divisor comum ao maior elemento do conjunto dos
divisores comuns de a e b e denotamos este elemento por (a, b).
Sejam a e b dois inteiros positivos. Pelo algoritmo da divisão, existem
dois inteiros q0 e r0 , tais que
a = q0 b + r0 , com 0 ≤ r0 < b
Se r0 ̸= 0 podemos utilizar o algoritmo da divisão para os inteiros b por r0 .
Então existem q1 e r1 tais que
b = q1 r0 + r1 , com 0 ≤ r1 < r0
Procedendo desta forma obtemos uma sequência de inteiros não negativos
r0 , r1 , . . . , rn , tais que r0 > r1 > · · · > rn ≥ 0. Note que este processo tem
de terminar ao fim de um número finito de passos e que o último resto, que
denotamos por rk+1 , é nulo.
26
Teorema 3.1. Se a e b são dois inteiros positivos e rk é o último resto não
nulo obtido pelo algoritmo de Euclides, então rk = (a, b). Mais, o algoritmo
de Euclides permite encontrar inteiros u e v tais que
au + bv = (a, b)
Demonstração: O algoritmo de Euclides pode ser esquematizado pelo
seguinte sistema de equações:


a = bq0 + r0




b
= r 0 q1 + r 1


 r 0 = r 1 q2 + r 2
(3.1)
..

.




rk−2 = rk−1 qk + rk


 r
=r q
k−1
k k+1
Seja d = (a, b). Vamos provar por indução que d|ri e d|ri+1 , para todo
o 0 ≤ i ≤ k − 1. Como d|a e d|b, temos d|(a − bq0 ), i.e., d|r0 . Como
d|b e d|r0 então d|(b − r0 q1 ) = r1 . Agora, suponhamos que d|ri e d|ri+1 ,
queremos provar que d|ri+1 e d|ri+2 . Usando a hipótese de indução, obtemos
que d|(ri − ri+1 qi+2 ). Mas ri − ri+1 qi+2 = ri+2 . Portanto d|ri+2 .
Acabámos de provar que d|ri para todo 0 ≤ i ≤ k. Em particular, d|rk .
Como d, rk > 0, temos d ≤ rk .
Reciprocamente, a última equação em (3.1) e o facto de rk ̸= 0, diz-nos
que rk |rk−1 . Usando a penúltima equação, obtemos rk |rk−2 . Por indução,
concluı́mos que rk |ri , para qualquer 0 ≤ i ≤ k. Usando a segunda equação,
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−1 qi ,
(3.2)
para qualquer 0 ≤ i ≤ k. Vamos provar por indução que, para qualquer
0 ≤ i ≤ k, existem inteiros ui e vi tais que ri = ui a + vi b. Como r0 = a − bq0 ,
o resultado é válido para i = 0. Suponhamos, por hipótese de indução que o
resultado é verdadeiro para i e para i − 1. Então
ri+1 = ri−1 − ri qi+1
= ui−1 a + vi−1 b − (ui a + vi b)qi+1
= (ui−1 − ui qi+1 )a + (vi−1 − vi qi+1 )b
= ui+1 a + vi+1 b
27
Portanto, para qualquer 0 ≤ i ≤ k, ri = ui a + vi b. Em particular, existem
inteiros u e v, tais que rk = ua + vb.
2
Exemplo. Seja a = 543 e b = 431. A seguinte tabela esquematiza o algoritmo de Euclides para calcular d = (a, b) e descobrir u e v tais que
au + bv = 1.
i
qi
ri
ui
vi
−2
−1
543
1
0
431
0
1
0
1
112
1
−1
1
3
95
−3
4
2
1
17
4
−5
3
5
10
−23
29
4
1
7
27
−34
5
1
3
−50
63
6
2
1
127
−160
Então (a, b) = 1 e 127a − 160b = 1. Mais, para cada −2 ≤ i ≤ k
ri = aui + bvi .
Teorema 3.2. Suponhamos que a > b. Então
tempo(determinar (a, b) usando o algoritmo de Euclides) = O(log3 a).
Demonstração: O algoritmo de Euclides consiste em efectuar sucessivas divisões, onde os sucessivos restos formam uma sequência estritamente
decrescente. Portanto, para estimar o número de operações bit, precisamos
de saber quantas divisões é necessário efectuar. Primeiro, vamos provar que
ri+2 < 12 ri :
Se ri+1 ≤ 12 ri , então como ri+2 < ri+1 , obtemos ri+2 < 12 ri .
Se ri+1 > 12 ri , então a divisão seguinte, no algoritmo de Euclides, é
ri = ri+1 + ri+2 .
Portanto, ri+2 = ri − ri+1 < 12 ri .
Acabámos de provar que em cada dois passos do algoritmo de Euclides
o resto é pelo menos reduzido a metade, donde temos no máximo 2[log2 a]
divisões. Como cada divisão envolve números menores ou iguais a a, o número
de operações bit por divisão é O(log2 a). Portanto, o algoritmo de Euclides
demora
O(log3 a)
28
2
operações bit.
Definição. Sejam a e b inteiros tais que pelo menos um deles é não nulo. Se
(a, b) = 1 então dizemos que a e b são primos entre si.
Teorema 3.3. Se (n, a) = 1 e n|ab, então n|b.
Demonstração: Pelo teorema 3.1, se (n, a) = 1 então 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, então b ≡ c mod n. Em
geral, se (a, n) = d e ab ≡ ac mod n então
n
b ≡ c mod .
d
Demonstração: Suponhamos que (a, n) = d e ab ≡ ac mod n. Então
existe um inteiro k tal que ab = ac + kn. Sejam
a
n
a1 = , n 1 = .
d
d
Claramente, a1 e n1 são inteiros e (a1 , n1 ) = 1. Dividindo ambos os membros
de ab = ac + kn por d, obtém-se a1 (b − c) = kn1 . Donde, a1 | kn1 . Como
(a1 , n1 ) = 1, temos a1 | k. Portanto, k = a1 k1 , para algum inteiro k1 . Assim,
b − c = k1 n1 , ou seja n1 | (b − c). Portanto, b ≡ c mod nd .
2
Teorema 3.5. Sejam a e b inteiros não nulos e d = (a, b). Se d - c então a
equação
ax + by = c
(3.3)
não tem soluções inteiras. Se d|c, a equação tem uma infinidade de soluções
inteiras. Se x = x0 , y = y0 é uma solução de (3.3), então todas as soluções
de (3.3) são dadas por
b
d
a
y = y0 − t
d
x = x0 + t
29
onde t é um inteiro.
Demonstração: Como d|a e d|b, temos d|(ax + by) para quaisquer inteiros x e y. Portanto, se c = ax + by, então d|c. Donde, se d - c, (3.3) não
tem soluções inteiras. Agora, se d|c, existe um inteiro e tal que c = de. Pelo
teorema 3.1, existem inteiros u e v, tais que
au + bv = d.
Multiplicando por e, obtemos a(ue) + b(ve) = de = c. Portanto, a equação
(3.3) tem pelo menos uma solução. Seja (x0 , y0 ) uma solução de (3.3) e t um
inteiro qualquer. Então
(
)
(
b
a)
a x0 + t
+ b y0 − t
= ax0 + by0 = c.
d
d
O que prova que a equação (3.3) tem uma infinidade de soluções.
Falta-nos ainda provar que qualquer solução de ax + by = c é da forma
descrita no teorema. Suponhamos que (x1 , y1 ) é outra solução. Então
a(x1 − x0 ) + b(y1 − y0 ) = c − c = 0.
Donde
a
b
(x1 − x0 ) = − (y1 − y0 ),
d
d
(3.4)
o que implica que
(
Como
que
a b
,
d d
b a
| (x1 − x0 ).
d d
)
= 1, temos
b
| (x1 − x0 ). Portanto, existe um inteiro t, tal
d
b
x1 = x0 + t .
d
Substituindo em (3.4), obtemos
a b
b
t = − (y1 − y0 ),
d d
d
donde
a
y1 = y0 − t .
d
Portanto, qualquer solução de (3.3) é forma acima descrita.
30
2
Teorema 3.6. A congruência
ax ≡ b
mod n
(3.5)
tem soluções se e só se d | b, onde d = (a, n). Se d | b então a solução é única
n
mod . Se (a, n) = 1 então (3.5) tem uma solução que é única mod n.
d
Demonstração: Se x0 é uma solução da equação (3.5) então existe um
inteiro y0 tal que
ax0 = b + ny0 ,
donde a equação
ax − ny = b
(3.6)
tem solução. Reciprocamente, se (x0 , y0 ) é uma solução de (3.6) então
ax0 ≡ ax0 − ny0 ≡ b
mod n
e, portanto, (3.5) tem solução. Acabámos de provar que (3.5) tem soluções
se e só se (3.6) tem soluções e a partir de uma solução de (3.6) obtemos
uma solução de (3.5). Pelo teorema 3.5, (3.6) tem soluções se e só se d | b.
Portanto, (3.5) tem soluções se e só se d | b.
Suponhamos agora que (3.6) tem soluções e seja (x0 , y0 ) uma solução.
Pelo teorema 3.5 qualquer solução de (3.6) é da forma
n
a
x = x0 + t , y = y 0 − t ,
d
d
onde t é um inteiro. Portanto, qualquer solução de (3.5) é da forma
x = x0 + t
Como
x0 + t
n
≡ x0
d
n
d
mod
n
,
d
n
então todas as soluções de (3.5) são congruentes com x0 mod , e portanto,
d
n
a solução de (3.5) é única mod .
d
A última parte do teorema resulta imediatamente das duas primeiras
partes.
2
31
Definição. Sejam a e n inteiros tais que (a, n) = 1. Ao único inteiro, que é
solução da equação
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 combinação linear de a e b
é dado pelo algoritmo de Euclides, também este processo demora O(log3 a)
operações bit. Em particular obtemos:
Corolário 3.7. Dado a, n inteiros, com n > 1 e (a, n) = 1. Então
tempo(determinar a−1 ) = O(log3 a).
Exemplo. Como (543, 431) = 1 e 127 · 543 − 160 · 431 = 1, então o inverso
de 543 mod 431 é 127 e o inverso de 431 mod 543 é 383.
3.7
Cifra Afim
Nesta subsecção, apresentamos outro caso especial da cifra de substituição,
conhecido como cifra afim. Este tipo de criptosistema utiliza funções afins,
i. e. funções da forma f (x) = ax + b. Mais uma vez utilizamos congruências
para 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́ necessário que
e(x) seja injectiva. Pelo teorema 3.6, e(x) é injectiva se e só se (a, m) = 1.
Sabemos também que se (a, m) = 1 então a tem inverso mod m.
Cifra (Afim). Seja m um inteiro positivo. Sejam P = C = Zm e K =
{(a, b) ∈ Z2m | (a, m) = 1}. Sejam x ∈ P e y ∈ C então definimos
ea,b (x) ≡ ax + b
e
da,b (y) ≡ a−1 (y − b)
32
mod m
mod m
3.8
Função φ de Euler
Definição. Seja n ≥ 1. O número de inteiros positivos menores ou iguais a
n que são primos com n é denotado por φ(n). Esta função de n é chamada
função φ de Euler
Assim, o conjunto das chaves K tem mφ(m) elementos. Recordamos
agora os seguinte resultados sobre a função φ.
Teorema 3.8. A função φ(n) é multiplicativa.
Demonstração: Sejam m e n inteiros positivos tais que (m, n) = 1.
Vamos meter os primeiros mn inteiros numa tabela com m colunas e n linhas.
1
m+1
2m+1
..
.
2
m+2
2m+2
..
.
...
...
...
..
.
m
m+m
2m+m
..
.
(n-1)m+1 (n-1)m+2 . . . (n-1)m+m
Os números na coluna j são 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 qualquer
elemento da coluna j é primo com m ou nenhum elemento da coluna j é primo
com m. Assim, há exactamente φ(m) colunas contendo inteiros primos com
m e qualquer elemento destas φ(m) colunas é primo com m.
Como (m, n) = 1, os n elementos de cada coluna j formam um sistema
completo de resı́duos mod n. Portanto, por definição, cada coluna j contém
exactamente φ(n) elementos primos com n. Donde, em cada uma das φ(m)
colunas que têm os elementos que são primos com m, há exactamente φ(n) elementos primos com n. Mais, estes são os únicos elementos que são ao mesmo
tempo primos com m e primos com n. Isto é, há exactamente φ(m)φ(n), elementos na tabela que são primos com m e, ao mesmo tempo, primos com
n.
Mas um inteiro é primo com mn se e só se for primo simultaneamente
com m e com n. Portanto,
φ(mn) = φ(m)φ(n)
2
e a função de Euler é multiplicativa.
33
Teorema 3.9. Suponhamos que a factorização de n em primos é a seguinte
n = pa11 pa22 · · · pakk
Então
∏
1
1
1
φ(n) = n(1 − )(1 − ) · · · (1 − ) =
(pai i − pai i −1 )
p1
p2
pk
i=1
k
Demonstração: Vamos começar por calcular φ(pa ), para p primo e a ≥
1. Um inteiro é primo com pa excepto se for divisı́vel por p. Os números de
1 a pa que são divisı́veis por p, são 1 · p, 2 · p, . . . , pa−1 p. Portanto,
1
φ(pa ) = pa − pa−1 = pa (1 − ).
p
Mas como a função φ(n) é multiplicativa, temos
φ(n) = φ(pa11 )φ(pa22 ) · · · φ(pakk )
1
1
1
= pa11 (1 − )pa22 (1 − ) · · · pakk (1 − )
p1
p2
pk
1
1
1
= pa11 pa22 · · · pakk (1 − )(1 − ) · · · (1 − )
p1
p2
pk
1
1
1
= n(1 − )(1 − ) · · · (1 − )
p1
p2
pk
2
3.9
Criptoanálise da Cifra Afim
Suponhamos que é interceptada uma mensagem que se sabe ter sido cifrada
usando um criptosistema afim, e que o alfabeto utilizado tem N = 26 letras.
As duas letras mais frequentes na mensagem são ”J”e ”C”. Sabe-se também
que a mensagem está em inglês, e que nesta lı́ngua, as letras mais frequentes
são 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 as
chaves só temos que resolver o sistema de congruências
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 são o G e o W, portanto assumimos que a foi
cifrado em G e e foi cifrado em W.
Obtemos as congruências 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 e
v = 18.
Portanto, a = 17 e b = 6.
Exercı́cio. Decifre a mensagem que se sabe ter sido cifrada usando uma
cifra 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 Vigenère
Nas cifras estudadas até agora, dada uma chave, cada letra é transformada
numa só outra letra. Por esta razão, aqueles criptosistemas são denominados
mono-alfabéticos. A cifra de Vigenère, que vamos apresentar nesta secção, é
o primeiro exemplo de um criptosistema poli-alfabético.
Cifra (Vigenère). 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
e
dK (y1 , . . . , yn ) ≡ (y1 − k1 , . . . , yn − kn ) mod m.
O número de chaves possı́veis, dados m e n é mn .
Exemplo. Suponhamos que m = 26, n = 8 e a chave é PORTUGAL. Então
K = (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 vez
e adicionamos a chave mod 26, da seguinte maneira
4 18 19 4 2 17 8
15 14 17 19 20 6 0
19 6 10 23 22 23 8
12 0 13 0
11 15 14 17
23 15 1 17
14
19
7
4
20
24
15
11
3
18
6
24
19
15
6
4
0
4
6
11
17
14
14
2
20
15
9
18
17
9
17
14
5
A mensagem cifrada fica
TGKXWXIDGCJBMZEXPBRHYYERJFF
36
8
19
1
14
17
5
18
20
12
19
6
25
4
0
4
3.11
Criptoanálise da cifra de Vigenere
O primeiro passo para criptanalisar a cifra de Vigenere consiste em encontrar
o comprimento da palavra chave, que denotamos por n. Vamos estudar duas
técnicas que nos podem ajudar a encontrar n, nomeadamente o teste de
Kasiski e o ı́ndice de coincidência.
O teste de Kasiski foi pela primeira vez descrito por Friedrich Kasiski
em 1863. Este teste tem por base o facto de dois segmentos idênticos do
texto plano serão transformados no mesmo texto cifrado sempre que a sua
ocorrência no texto plano está com x posições de separação, com x ≡ 0
mod n. Reciprocamente, se forem observados no texto cifrado dois segmentos
idênticos com comprimento de pelo menos três letras, então há uma grande
chance que eles correspondam a segmentos idênticos do texto plano.
O teste de Kasiski funciona do seguinte modo: Primeiro procuramos no
texto cifrado pares de segmentos idênticos de comprimento maior ou igual a
3 e guardamos a distância entre o inı́cio de cada um dos dois segmentos. Se
obtivermos as distâncias d1 , d2 , . . . então conjecturamos que n divide o maior
divisor comum entre todas as distâncias.
Outro processo para estimar o valor de n, consiste em utilizar o ı́ndice de
coincidência desenvolvido por Wolfe Friedman em 1920.
Definição. Seja x = x1 x2 . . . xm uma lista de m letras. O ı́ndice de coincidência de x, que denotamos por Ic (x) é a probabilidade de que dois elementos de x sejam iguais. Denotemos as frequências de A, B, C, . . .(, Z) em x por
f0 , f1 , . . . , f25 . Como podemos escolher dois elementos de x de m2 maneiras
( )
e, para cada 0 ≤ i ≤ 25, há f2i maneiras de escolher dois elementos e ambos
serem i então,
∑25
fi (fi − 1)
Ic (x) = i=0
.
m(m − 1)
Se x é parte de um texto em inglês ou é um texto cifrado através de uma
cifra mono-alfabética, e pi são as probabilidades indicadas na figura 3.1 será
de esperar que
25
∑
Ic (x) ≈
p2i = 0.065.
i=0
A figura 3.3 apresenta os ı́ndices de coincidência de várias lı́nguas.
37
Português
Inglês
Francês
Italiano
Alemão
Japonês
Russo
Texto aleatório
0.0738
0.0661
0.0778
0.0738
0.0762
0.0819
0.0529
0.0385
Figura 3.3: Índices de Coincidência esperados
Vejamos agora como utilizar o ı́ndice de coincidência para determinar o
comprimento da palavra passe de uma cifra de Vigenere, n.
Suponhamos que y = y1 y2 . . . ym foi obtido através de uma cifra de Vigenere de um texto plano em inglês. Para cada inteiro r ≥ 1, escrevemos a
mensagem cifrada y, por colunas numa matriz do tipo r × m/r. Denotamos
por yi a linha i, desta matriz, com 1 ≤ i ≤ r. Se r = n então é de esperar
que Ic (yi ) seja aproximadamente 0.0661, para qualquer 1 ≤ i ≤ r. Se r ̸= n
então as listas yi serão mais aleatórias, pois foram obtidas utilizando cifras
de deslocamento com várias chaves. Como o ı́ndice de coincidência esperado
de uma lı́ngua é muito diferente do ı́ndice de coincidência esperado de um
texto aleatório, seremos capazes de descobrir o valor de n.
Após determinarmos o comprimento da palavra passe, cada yi é obtido
através de uma cifra de deslocamento de um texto plano na lı́ngua considerada e pode ser utilizada a análise de frequências para obter a palavra passe.
Quando o texto plano é pequeno, a análise de frequências pode não ser suficiente para conjecturar com grande convicção o valor da chave. Neste caso,
usamos o ı́ndice de coincidência mútua entre duas listas.
Definição. Sejam x = x1 x2 . . . xm e y = y1 y2 . . . yt listas com m e t letras,
respectivamente. O ı́ndice de coincidência mútua de x e y, que denotamos
por M Ic (x, y) é a probabilidade de um elemento de x ser igual a um elemento
de y. Se denotarmos as frequências de A, B, . . . , Z em x e y por f0 , f1 , . . . , f25
e g0 , g1 , . . . , g25 , respectivamente, então
∑25
fi gi
M Ic (x, y) = i=0
.
mt
Já vimos que cada yi é obtido através de uma cifra de deslocamento.
38
Seja K = (k1 , . . . , kn ) a palavra passe, então yi obtém-se somando ki a cada
i-ésima letra do texto plano. Vamos primeiro estimar M Ic (yi , yj ). Tirando
uma letra de yi e outra de yj , a probabilidade de serem ambas A é p−ki p−kj ,
a probabilidade de ambas serem B é p1−ki p1−kj , etc. (note que os ı́ndices são
reduzidos mod 26). Portanto,
M Ic (yi , yj ) ≈
25
∑
ph−ki ph−kj =
h=0
25
∑
ph ph+ki −kj .
h=0
Esta estimativa depende apenas da diferença ki − kj mod 26 à qual
chamamos deslocamento relativo de yi e yj . Mais, como
25
∑
ph ph+l =
h=0
25
∑
ph−l ph ,
h=0
um deslocamento relativo de u dá a mesma estimativa para M Ic que um
deslocamento relativo de 26 − u. Portanto precisamos apenas de calcular as
estimativas para os deslocamentos relativos entre 0 e 13.
Deslocamento relativo Valor esperado de M Ic
0
0.065
1
0.039
2
0.032
3
0.034
4
0.044
5
0.033
6
0.036
7
0.039
8
0.034
9
0.034
10
0.038
11
0.045
12
0.039
13
0.043
Verifica-se que um deslocamento relativo nulo dá um ı́ndice de coincidência mútua (M Ic ) muito distinto do M Ic correspondente a qualquer outro
deslocamento relativo. Podemos usar esta informação para tentar descobrir
u = ki − kj . Primeiro fixamos yi e vamos cifrar yj usando cada uma das
chaves g com 0 ≤ g ≤ 25 e denotamos a mensagem cifrada obtida, por yjg .
Em seguida, calculamos os ı́ndices M Ic (yi , yjg ), para cada 0 ≤ g ≤ 25,
39
∑25
fh,i fh−g,j
,
mt
onde fh,i e fh,j são as frequências da letra correspondente a h em yi e yj ,
respectivamente. Quando g = u o ı́ndice M Ic deve ser próximo de 0.065,
mas quando g ̸= u o ı́ndice deve ser relativamente menor. Para cada i e j
devemos calcular 14 ı́ndices, um para cada chave.
Vamos ilustrar estes métodos com o seguinte exemplo:
M Ic (yi , yig )
h=0
=
Exemplo. Sabemos que a seguinte mensagem foi cifrada utilizando um criptosistema de Vigenere.
CHREEV OAHMAE RATBIA XXWTNX BEEOPH BSBQMQ
EQERBW RVXUOA KXAOSX XWEAHB WGJMMQ MNKGRF
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
PEEWEV KAKOEW ADREMX MTBHHC HRTKDN VRZCHR
CLQOHP WQAIIW XNRMGW OIIFKE E
Primeiro, vamos tentar descobrir n utilizando o teste de Kasiski. O
trigrama CHR aparece cinco vezes na mensagem cifrada, começando nas
posições 1, 166, 236, 276 e 286. As distâncias da primeira ocorrência às outras são 165, 235, 275 e 285 e o máximo divisor comum entre estes valores é
5. Portanto, é de prever que o comprimento da palavra passe seja 5.
Vejamos se com o cálculo dos ı́ndices de coincidência chegamos à mesma
conclusão. Se r = 1, o ı́ndice de coincidência é 0.045. Se r = 2 obtemos
Ic (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 e
0.040. Finalmente, para r = 5, obtemos 0.063, 0.068, 0.069, 0.061 e 0.072, o
que também sugere que n = 5.
Vamos agora tentar utilizar os ı́ndices de coincidência mútua para descobrir a palavra passe. Utilizando um programa no computador, calcula-se
todos os 260 valores de M Ic (yi , yjg ), com 1 ≤ i < j ≤ 5 e 0 ≤ g ≤ 25, e
40
procura-se os valores que forem próximos de 0.065. Dado um par (i, j), se
houver um único valor perto de 0.065, conjecturamos que esse é o valor do
deslocamento relativo.
Verifica-se haver grande evidência que o deslocamento relativo entre y1
e y2 seja 9; o deslocamento relativo entre y2 e y3 seja 13; o deslocamento
relativo 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 seguintes
equações nas cinco incógnitas k1 , . . . , k5 (todos os cálculos são efectuados
mod 26):
k1 − k2
k1 − k5
k2 − k3
k2 − k5
k3 − k5
k4 − k5
=
=
=
=
=
=
9
16
13
7
20
11.
Donde
k2
k3
k4
k5
=
=
=
=
k1 + 17
k1 + 4
k1 + 21
k1 + 10
Assim, a chave deve ser (k1 , k1 + 17, k1 + 4, k1 + 21, k1 + 10), para algum
0 ≤ k1 ≤ 25, ou seja, a chave é uma das sequências AREVK ou BSFWL ou
CTGXM. . . . A única destas sequências que faz sentido é JAN ET . Note-se
que a palavra passe não tem que fazer sentido. Nesse caso, podemos experimentar qualquer das possı́veis chaves até que uma dê um texto com sentido,
ou, se quisermos utilizar o computador, verificar qual delas é que corresponde
a um texto plano que tenha uma análise de frequências de acordo com a lı́ngua
que 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 for
six months. The vineyards were busy again as the well-organized
farmers treated their vines and the more lackadaisical neighbors
hurried to do the pruning they should have done in November.
3.12
Cifra de Hill
Nesta secção descrevemos outro criptosistema polialfabético inventado em
1929 por Lester S. Hill.
Cifra (Hill). Sejam m e n inteiros positivos. Sejam P = C = (Zm )n e
K = {K ∈ Mn (Zm ) : Ké invertı́vel}. Dada uma chave


k1,1 k1,2 . . . k1,n
 k2,1 k2,2 . . . k2,n 


K =  ..
..
.. 
 .
.
. 
kn,1 kn,2 . . . kn,n
e x ∈ P e y ∈ C, definimos
e
eK (x1 , x2 , . . . , xn ) ≡ (x1 x2 . . . xn )K
mod m
dK (y1 , y2 . . . , yn ) ≡ (y1 y2 . . . yn )K −1
mod m.
Exemplo. Sejam m = 26, n = 2 e
(
K=
11 8
3 7
(
)
)
7 18
K =
23 11
Para cifrar o texto plano hill, dividimos primeiro nos dois grupos hi e ll e
efectuamos os produtos
(
)
(
) 11 8
(
)
7 8
= 23 8
3 7
e
(
)
(
) 11 8
(
)
11 11
= 24 9
3 7
A mensagem cifrada fica XIYJ.
Neste caso
−1
42
3.13
Ataque à cifra de Hill
A cifra de Hill é mais difı́cil de quebrar quando só se conhece a mensagem
cifrada, mas sucumbe muito facilmente quando se conhece um texto plano
que deu origem a uma mensagem cifrada. Vamos assumir que o oponente
conhece o valor de n (comprimento de cada parte do texto plano a ser cifrada
individualmente) 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 ], então Y = XK, onde K é a matriz da
chave desconhecida. Se X for invertı́vel, o oponente pode obter K = X −1 Y
e quebrar o sistema. Se X não for invertı́vel será necessário utilizar outros n
pares.
Exemplo. Suponha que o texto plano friday é cifrado utilizando uma cifra
de Hill com n = 2, obtendo-se PQCFKU. Então temos eK (5, 17) = (15, 16),
eK (8, 3) = (2, 5) e eK (0, 24) = (10, 20). Utilizando os dois primeiros pares,
obtemos a equação matricial
)
) (
(
5 17
15 16
K.
=
8 3
2 5
Como
)
)−1 (
(
9 1
5 17
=
2 15
8 3
a chave K é
(
K=
9 1
2 15
)(
15 16
2 5
)
(
=
7 19
8 3
)
.
Podemos utilizar o terceiro par para confirmar este resultado.
Mas pode acontecer (e é provável que aconteça) que o oponente não
conheça n. Neste caso, ele pode usar este processo utilizando n = 2, 3, . . . até
que a chave seja descoberta. Se um valor de n é incorrecto, então a matriz
K obtida utilizando este algoritmo não funcionará para outros pares texto
plano-texto cifrado. Portanto, n pode ser facilmente determinado.
3.14
Cifra de Permutação
Até agora todas as cifras estudadas envolveram substituições das letras do
texto plano por letras da mensagem cifrada. A ideia da cifra de permutação
43
(também chamada cifra de transposição) consiste em não alterar as letras do
texto plano, mas sim a sua posição. Este tipo de cifras tem sido utilizado
há centenas de anos, tendo Giovanni Porta notado, já em 1563, a distinção
entre estas cifras e as cifras de substituição.
Cifra (Permutação). Sejam m e n inteiros positivos. Sejam P = C = (Zm )n
e K consiste de todas as permutações de {1, . . . , n}. Dada uma chave π e
x ∈ P e y ∈ C, definimos
eπ (x1 , x2 , . . . , xn ) ≡ (xπ(1) , xπ(2) , . . . , xπ(n) )
e
dπ (y1 , y2 , . . . , yn ) ≡ (yπ−1 (1) , xπ−1 (2) , . . . , xπ−1 (n) ),
onde π −1 é a permutação inversa de π.
A cifra de permutação é um caso especial da cifra de Hill. A permutação
π de {1, . . . , n}, corresponde à matriz de permutação Kπ cuja entrada (i, j)
é 1 se i = π(j) e 0 caso contrário.
3.15
Cifras de Fluxo
Nos vários criptosistemas estudados, a chave K mantém-se fixa e é utilizada
para cifrar os sucessivos blocos de texto plano. Isto é, a mensagem cifrada,
y, é obtida da seguinte maneira:
y = y1 y2 · · · = eK (x1 )eK (x2 ) · · · .
Estes criptosistemas chamam-se Cifras de bloco. Nesta secção, vamos estudar
uma generalização das cifras de bloco, i. e. criptosistemas que usam um fluxo
de chaves.
Uma cifra de fluxo funciona da seguinte forma: Dada uma chave K ∈ K e
um texto plano x1 x2 · · · , é gerado um fluxo de chaves, digamos z = z1 z2 · · · ,
definido por
zi = fi (K, x1 , . . . , xi−1 )
e a mensagem cifrada é obtida da seguinte forma:
y = y1 y2 · · · = ez1 (x1 )ez2 (x2 ) · · · .
44
Assim, para cifrar o texto plano x1 x2 · · · , calcula-se sucessivamente os valores
z1 , y1 , z2 , y2 , . . . . Para decifrar y1 y2 · · · , calcula-se sucessivamente os valores
z1 , x 1 , z 2 , x 2 , . . . .
A formulação matemática é apresentada a seguir:
Definição. Uma cifra de fluxo é um heptuplo (P, C, K, L, F, E, D) satisfazendo as condições 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 para
decifrar correspondente dz ∈ D, tais que ez : P −→ C, dz : C −→ P e
dz (ez (x)) = x, para qualquer x ∈ P.
As cifras de bloco são um caso particular das cifras de fluxo, onde zi = k,
para qualquer i ≥ 1. Quando as funções fi só dependem da chave K, dizemos
que temos uma cifra de fluxo sincronizada. Neste caso, K é a semente que é
expandida para gerar o fluxo z1 z2 · · · .
Uma cifra de fluxo é periódica com perı́odo d se zi+d = zi , para qualquer
i ≥ 1. A cifra de Vegenere pode ser interpretada como uma cifra de fluxo
sincronizada e periódica, 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 operação do
”ou”exclusivo, conhecida como XOR.
3.16
Cifra de Fluxo baseada no LFSR
Um método de geração 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 através da
seguinte recorrência linear de grau n
zi+n ≡
n−1
∑
cj zi+j
mod 2,
j=0
para i ≥ 1.
Note que só estamos realmente a cifrar quando (k1 , . . . , kn ) ̸= (0, . . . , 0).
Se esta hipótese se verificar e se os valores c0 , c1 , . . . , cm−1 também não são
todos nulos, então vamos obter uma cifra de fluxo periódica de perı́odo 2n −1.
Portanto, uma chave inicial ”pequena”dá origem a um fluxo de chaves com
um perı́odo ”grande”.
As cifras A5/1, A5/2, utilizadas nos telemóveis GSM, e a cifra EO, utilizada no Bluetooth, são 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.
Então 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 método pode ser eficientemente implementado em Hardware utilizando um Linear feedback shift register (LFSR).
3.17
Criptoanálise da cifra de fluxo baseada
no LFSR
Vejamos um método para quebrar a cifra de fluxo baseada no LFSR, quando
se conhece um texto plano e a mensagem cifrada que lhe corresponde. Como
vimos, a mensagem cifrada é obtida adicionando o texto plano ao fluxo de
chaves módulo 2, i.e. yi = xi + zi . O fluxo de chaves é produzido a partir da
chave secreta z1 , . . . , zm e as relações de recorrência linear
46
zm+i ≡
m−1
∑
cj zi+j
mod 2,
j=0
onde c0 , . . . , cm−1 ∈ Z2 e c0 = 1.
Suponha que o oponente conhece o texto plano x1 , x2 , . . . , xn e a mensagem cifrada correspondente y1 , y2 , . . . , yn , então pode obter os valores zi ≡
xi + yi mod 2, para 1 ≤ i ≤ n. Suponhamos que o oponente também conhece o comprimento da chave secreta m. Então precisa apenas de determinar
c0 , c1 , . . . , cm−1 . Como para cada i ≥ 1, temos
zm+i ≡
m−1
∑
cj zi+j
mod 2,
j=0
que é uma equação linear com m incógnitas. Se n ≥ 2m então temos um
sistema de equações com m equações e m incógnitas e, portanto, pode ser
resolvido. A seguinte equação matricial descreve este sistema de equações

z1
z2
..
.


(zm+1 , zm+2 , . . . , z2m ) = (c0 , c1 , . . . , cm−1 ) 

z2
z3
..
.
...
...

zm
zm+1
..
.


.

zm zm+1 . . . z2m−1
Pode ser mostrado que a matriz tem inversa se m for o comprimento
da chave secreta (ver exercı́cio 1.9, pag 42, em Criptography: Theory and
Practice de Douglas Stinson). Neste caso, obtemos



(c0 , c1 , . . . , cm−1 ) = (zm+1 , zm+2 , . . . , z2m ) 

z1
z2
..
.
z2
z3
..
.
...
...
zm
zm+1
..
.
zm zm+1 . . . z2m−1
Vejamos um exemplo:
Exemplo. Suponhamos que Oscar obtém a mensagem cifrada
101101011110010
47
−1




.
correspondente ao texto plano
011001111111000.
Então o fluxo de chaves pode ser obtido somando bit a bit mod 2 os valores
anteriores. Portanto o fluxo de chaves será
110100100001010.
Então



(0, 1, 0, 0, 0) = (c1 , c2 , c3 , c4 , c5 ) 


1
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
0






Donde, após calcularmos a inversa da matriz e efectuar os restantes cálculos,
obtemos (c1 , c2 , c3 , c4 , c5 ) = (1, 0, 0, 1, 0). Portanto, a recorrência para gerar
o fluxo de chaves é
zi+5 ≡ zi + zi+3
48
mod 2.
Capı́tulo 4
Criptografia de chave pública
Os próximos sistemas criptográficos que iremos estudar há uma chave para
cifrar que é pública, mas a chave para decifrar é secreta e não pode ser obtida
a partir da chave pública. Antes de descrevermos estes sistemas, necessitamos
de recordar alguns resultados de teoria elementar dos números.
4.1
Teorema Chinês dos Restos
Na secção 3.6 vimos como resolver congruências da forma
ax ≡ b
mod n.
O próximo resultado diz-nos quando é que um sistema com duas congruências
tem solução.
Teorema 4.1. Se (m, n) = 1, então o sistema
{
x ≡ a mod m
x ≡ b mod n
Tem uma e uma só solução
mod mn.
Demonstração: Um inteiro x satisfaz a primeira equação se e só se
existe um inteiro t tal que
x = a + mt
(4.1)
Agora, a + mt satisfaz a segunda equação se e só se
mt ≡ b − a
49
mod n.
(4.2)
Como (m, n) = 1, esta última equação tem uma única solução, 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́ solução do sistema se e só se
x = a + m(c + nk)
= (a + mc) + mnk
Logo, a + mc é solução do sistema e é única mod mn.
2
Este teorema é um caso especial de um resultado mais geral, que já era
conhecido dos chineses há mais de 2000 anos.
Teorema 4.2 (Teorema chinês dos restos). Sejam m1 , . . . , mk inteiros positivos que são primos entre si dois a dois. Então o sistema


x ≡ a1 mod m1


 x ≡ a2 mod m2
..

.


 x ≡ a mod m
k
k
tem uma única solução
mod (m1 m2 · · · mk ).
Demonstração: Iremos usar o teorema 4.1 (k − 1) vezes. Pelo teorema
4.1 as duas primeiras equações têm uma única solução mod (m1 m2 ). Seja
b2 esta solução, i. e.
x ≡ b2 mod m1 m2
(4.3)
A terceira equação é
x ≡ a3
mod m3 .
(4.4)
Como, por hipótese (m1 , m3 ) = (m2 , m3 ) = 1, então temos (m1 m2 , m3 ) = 1
(porquê?). Para resolver o sistema formado pelas equações (4.3) e (4.4),
podemos mais uma vez utilizar o teorema 4.1. Portanto, há uma única
solução de (4.3) e (4.4) mod ((m1 m2 )m3 ), i. e., há uma única solução
das três primeiras equações mod (m1 m2 m3 ). Continuando desta maneira,
50
depois de (k − 1) aplicações do teorema 4.1, obtemos uma única solução
mod (m1 m2 · · · mk ) do sistema
{
x ≡ bk−1 mod (m1 m2 · · · mk−1 )
x ≡ ak mod mk
Esta solução, digamos x ≡ bk mod (m1 m2 · · · mk ), é também a única solução
do sistema inicial mod (m1 m2 · · · mk ).
2
O próximo teorema permitir-nos-á encontrar uma solução do sistema


x ≡ a1 mod m1


 x ≡ a2 mod m2
..

.


 x ≡ a mod m
k
k
sem ter que utilizar diversas vezes o teorema 4.1.
Teorema 4.3. Sejam m1 , . . . , mk inteiros positivos que são primos entre
M
si dois a dois. Sejam M = m1 m2 · · · mk , Mi =
e yi o inverso de Mi
mi
mod mi , para qualquer 1 ≤ i ≤ k. Então
N = a1 M1 y1 + a2 M2 y2 + · · · ak Mk yk
é a única solução
mod M do sistema


x ≡ a1 mod m1


 x ≡ a2 mod m2
..

.


 x ≡ a mod m
k
k
Demonstração: Pelo teorema do resto chinês, sabemos que há uma
solução única mod M do sistema anterior. Portanto, basta-nos provar que
N é essa solução. Seja 1 ≤ i ≤ k. Como (Mi , mi ) = 1, então, pelo teorema
3.6, existe yi tal que Mi yi ≡ 1 mod mi . Mais, Mi ≡ 0 mod mj , para
qualquer j ̸= i. Então
N ≡ a1 M1 y1 + a2 M2 y2 + · · · ak Mk yk
≡ ai Mi yi mod mi
≡ ai Mi (Mi )−1 mod mi
≡ ai mod mi
51
mod mi
Portanto, N é solução da equação x ≡ ai mod mi , para qualquer 1 ≤ i ≤ k.
Donde, N é a única solução do sistema mod M .
2
Exemplo. A primeira menção conhecida do teorema chinês do resto é o
seguinte problema extraı́do do livro Sun Tzu Suan Ching (O Manual Matemático do Mestre Sun), escrito por Sun Zi, por volta do terceiro século a.c.
Temos um certo número de coisas, mas não sabemos exactamente
quantas são. Se formarmos grupos de três, sobram duas. Se
formarmos grupos de cinco, sobram três. Se formarmos grupos
de sete, sobram duas. Quantas coisas temos?
Resolver este problema equivale a

 x≡2
x≡3

x≡2
resolver o sistema
mod 3
mod 5
mod 7
Primeiro iremos usar o processo descrito no teorema do resto chinês. Da
primeira equação obtemos x = 2 + 3t, para algum inteiro t. Substituindo na
segunda equação, 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 equação, 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.
Provámos que qualquer solução do sistema é da forma 23 + 105s, para s
inteiro, e a única solução mod (3 · 5 · 7) é 23.
Agora usamos o método descrito no teorema anterior. Aqui M = 105,
M1 = 35, M2 = 21 e M3 = 15. O inverso de 35 mod 3 é y1 = −1, o inverso
de 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 ∈ G
como sendo o menor inteiro positivo m tal que g m = 1. Se G = (Z∗n , ·) então
G tem φ(n) elementos e, neste caso, definimos ordem de um elemento da
seguinte maneira:
Definição. Suponhamos que (a, n) = 1. Definimos a ordem de a mod n
como 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
52
53
54
≡ 5 mod 13
≡ −1 mod 13
≡ −5 mod 13
≡ 1 mod 13
Recordemos os famosos resultados:
Teorema 4.4 (Lagrange). Suponha que G é um grupo multiplicativo com n
elementos e seja g ∈ G. Então a ordem de g divide n.
Teorema 4.5 (Fermat). Se p é primo então bp ≡ b mod p
Teorema 4.6 (Euler). Se (b, n) = 1 então
bφ(n) ≡ 1
4.3
mod n.
Raı́zes primitivas
Quando p é primo, o grupo (Z∗n , ·) é cı́clico e os elementos que geram este
grupo são muito importantes em criptografia. Recordemos o nome destes
elementos e um resultado que nos diz quantos existem.
Definição. Se (a, n) = 1 e ordn (a) = φ(n) dizemos que a é uma raı́z primitiva de n.
Teorema 4.7. Seja p um primo e d | (p − 1). Então há exactamente φ(d)
inteiros distintos mod p cuja ordem mod p é d. Em particular, há exactamente φ(p − 1) raı́zes primitivas de p.
53
4.4
Exponenciação modular rápida
Antes de passar ao sistema RSA e outros sistemas de chave pública necessitamos ainda de um algoritmo que nos permita fazer exponenciações modulares
rápidas.
Teorema 4.8. Sejam n, m e b inteiros, com b < m. Então
tempo(bn
mod m) = O(log n log2 m)
Por um exercı́cio, calcular bn demora O(n2 log2 b) operações bit. Podemos determinar bn mod m dividindo bn por m o que nos dá O(n log b log m)
operações bit. Portanto, no total terı́amos
O(n2 log2 b) + O(n log b log m)
operações bit. Este valor é exageradamente superior a O(log n log2 m) se m
não for muito superior a n, portanto temos que utilizar um algoritmo muito
mais rápido que o indicado para calcular bn . Uma das ideias deste algoritmo
é nunca trabalhar com números muito grandes, i. e. sempre que fizermos
uma multiplicação, reduziremos logo de seguida o resultado mod m. Assim,
os inteiros envolvidos nos nossos cálculos nunca serão maiores que m2 .
Demonstração: Denotamos por a o produto parcial. Quando o algoritmo terminar, teremos a ≡ bn mod m. Começamos por tomar a = 1 e seja
n = (nk−1 · · · n1 n0 )2 a representação de n na base 2, onde k é o número de
bits de n.
Se n0 = 1, então tomar a = b, caso contrário a = 1. A seguir calculamos
b2 e seja b1 = b2 mod m.
Se n1 = 1, a passa a ser ab1 mod m, caso contrário a não é alterado.
Seja b2 = b21 mod m.
Se n2 = 1, a passa a ser ab2 mod m, caso contrário a não é alterado.
j
Continuando desta maneira, temos, no passo j, bj ≡ b2 mod m, com
bj < m. Se nj = 1, i. e. se 2j aparece na expansão binária de n, então
incluı́mos bj no produto para a, caso contrário, não incluı́mos bj . Depois de
k − 1 passos, obtemos
k−1
a ≡ bn0 +n1 2+···nk−1 2
≡ bn
mod m.
Em cada passo temos uma multiplicação e uma divisão, se nj = 0, ou duas
multiplicações e duas divisões se nj = 1, de números menores que m2 . Portanto, cada passo demora O(log2 m2 ) = O(log2 m) operações bit. Como
54
temos O(log n) passos, obtemos
tempo(bn
mod m) = O(log n log2 m).
2
4.5
RSA
O RSA foi inventado por Ron Rivest, Adi Shamir, e Leonard Adleman, no
MIT, 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 números n e e
são publicados, daı́ o nome de criptosistema de chave pública. A mensagem
a cifrar deve ser um número P ≤ n. A mensagem cifrada será o único inteiro
0 < C < n tal que
C ≡ P e mod n.
É importante notar que p, q e φ(n) são mantidos secretos. Como sabemos
φ(n), podemos usar o algoritmo de Euclides para encontrar um número d tal
que
ed ≡ 1 mod φ(n),
i. e. ed = 1 + φ(n)k, para algum inteiro k. Para decifrar a mensagem, basta
calcular o menor resı́duo não negativo de
Cd
mod n.
Vejamos porquê:
Se (P, n) = 1, o teorema de Euler diz-nos que
C d ≡ P ed ≡ P 1+φ(n)k ≡ P
mod n
Se (P, n) ̸= 1 então (P, n) = p ou (P, n) = q. Suponhamos que (P, n) = p.
Então (P, q) = 1, donde
{ d
C ≡ P ed ≡ 0 mod p
C d ≡ P ed ≡ P 1+φ(n)k ≡ P × (P q−1 )(p−1)k ≡ P mod q
55
Pelo teorema chinês dos restos, C d ≡ P mod n.
Portanto, para alguém decifrar a mensagem, ele tem que conhecer d e
n. Não basta saber e e n. Para calcular d ele tem de saber φ(n), o que
requer um conhecimento dos primos p e q. Ou seja, tem de saber factorizar
n. Se os primos p e q forem suficientemente grandes (por exemplo, milhares
de algarismos, cada um), então, com os mais potentes computadores e o
conhecimento matemático actual, é impossı́vel descobrir os factores de n
num perı́odo de tempo menor que um milhão de anos. Quem sabe p e q pode
calcular φ(n), mas um oponente que queira decifrar a mensagem, falhará,
pois não sabe os primos nem uma maneira rápida de factorizar n.
Suponha que o alfabeto tem N letras, e n = pq, seja k tal que N k < n <
N k+1 . Costuma-se codificar as mensagens originais em blocos de k letras,
mas descodifica-se as mensagens cifradas em blocos de k + 1 letras. Deste
modo qualquer mensagem pode ser codificada e qualquer mensagem cifrada
pode 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. A
chave para cifrar e e o módulo n podem ser publicados. Com os conhecimentos actuais é impraticável obter d sabendo e e n. Portanto, pode haver
uma lista pública (tipo lista telefónica) com o nome de cada utilizador, o seu
módulo n e o expoente público e (esta chave é usualmente a mesma para
vários utilizadores, devendo ser relativamente pequena para tornar o sistema
eficiente).
Para que a fatorização do módulo n seja impraticável os factores primos
de n devem ser escolhidos apropriadamente. Devido à força dos algoritmos
actuais para factorizar inteiros, p e q devem ter aproximadamente o mesmo
número de bits (mas não demasiado próximos), e com pelo menos 512 bits.
Se para um dos factores p, p − 1 tiver só factores primos ”pequenos”, então
o método de fatorização ”p − 1”irá permitir factorizar n.
4.5.1
Ataque do expoente público pequeno
A chave de cifrar e deve ser escolhida o mais pequena possı́vel, de modo a fazer
a cifra eficiente. A escolha e = 2 é impossı́vel porque φ(n) = (p−1)(q−1) que
é par. Portanto, a menor chave de cifrar possı́vel é e = 3. Porém, pode ser
perigoso usar chaves de cifrar demasiado pequenas, porque o inimigo pode
56
usar o ”ataque do expoente pequeno”: Este ataque funciona se a mesma
mensagem M é cifrada e vezes, usando sempre a chave de cifrar e e usando e
módulos ni primos dois a dois. Por exemplo, um banco pode enviar a mesma
mensagem M a alguns dos seus clientes usando os diferentes módulos RSA
destes clientes e sempre o mesmo e. Em seguida mostramos como este ataque
funciona. Sejam ci = ne mod ni , 1 ≤ i ≤ e as correspondentes mensagens
cifradas. Então o inimigo usa o seguinte algoritmo:
1. Calcular um inteiro c tal que c ≡ ci mod ni , onde 1 ≤ i ≤ e e 1 ≤ c ≤
n1 n2 · · · ne , usando o teorema chinês dos restos.
2. Determinar a raiz e de c, que vai ser M .
Para verificar que este algoritmo realmente funciona, basta notar que o
inteiro u = M e é menor que n1 n2 · · · ne (porque M < ni ) e que claramente
verifica as congruências u ≡ ci mod ni . Donde c = u, pelo teorema
chinês
√
e
dos restos (há unicidade de solução mod (n1 · · · ne )), e portanto c = M .
A raiz e de c pode ser calculada de um modo eficiente (por exemplo,
usando um generalização do algoritmo para obter a raiz quadrada). Portanto,
o ataque do expoente pequeno pode ser realmente eficiente. Porém, este
método falha se as mensagens originais forem diferentes, e isto pode ser
obtido se acrescentarmos à mensagem original alguns bits de texto aleatórios.
Podemos também usar um maior expoente para cifrar. Um valor muito
utilizado é e = 216 + 1.
4.6
Resı́duos quadráticos
Sejam p primo ı́mpar e a um inteiro, tais que p - a. Seja 1 ≤ x ≤ p − 1
então só um dos inteiros x, 2x, . . . , (p − 1)x é congruente com a mod p. Há,
portanto, um único x′ tal que
xx′ ≡ a
mod p
com 1 ≤ x′ ≤ p − 1. Dizemos que x′ está associado a x. Há duas possibilidades, ou existe pelo menos um 1 ≤ x ≤ p − 1, que está associado a si mesmo
ou não existe tal inteiro. Vamos analisar cada caso.
1. Suponhamos que há um inteiro x1 que está associado a si mesmo. Então
a congruência
x2 ≡ a mod p
(4.5)
57
tem a solução x = x1 . Neste caso, dizemos que a é um resı́duo
quadrático de p. Claramente, p − x1 é outra solução de (4.5). Mais, se
x2 é outra solução de (4.5), então
x21 − x22 ≡ 0 mod p
donde,
(x1 − x2 )(x1 + x2 ) ≡ 0 mod p.
Logo, x1 ≡ x2 mod p ou x1 ≡ −x2 ≡ p − x2 mod p. Portanto, a
equação (4.5) só tem duas soluções, que são x1 e p − x1 . Podemos
então agrupar os inteiros
1, 2, . . . , p − 1
p−3
em
pares de inteiros associados e diferentes, sobrando x1 e p − x1
2
que estão associados a si próprios. Temos
x1 (p − x1 ) ≡ −x21 ≡ −a
mod p
e, para cada par de associados x e x′ ,
xx′ ≡ a
Então
(p − 1)! =
p−1
∏
i ≡ −a · a
mod p.
p−3
2
≡ −a
p−1
2
mod p.
i=1
2. Se não há qualquer inteiro que esteja associado a si próprio, dizemos
que a é um não-resı́duo quadrático de p. Neste caso, a equação (4.5)
não tem soluções e os inteiros
1, 2, . . . , p − 1
podem ser agrupados em
Portanto,
p−1
pares de inteiros associados diferentes.
2
(p − 1)! =
p−1
∏
i≡a
i=1
58
p−1
2
mod p.
Seja p um primo ı́mpar (
e a)
um qualquer inteiro não divisı́vel por p. Definimos
a
o sı́mbolo de Legendre
, da seguinte maneira
p
( ) {
a
1
se a é um resı́duo quadrático de p
=
−1
se a é um não-resı́duo quadrático de p
p
( ) ( )
b
a
=
se a ≡ b mod p. Acabámos de provar o seguinte
Claramente,
p
p
teorema:
Teorema 4.9. Se p é um primo ı́mpar e a não é múltiplo de p, então
( )
p−1
a
(p − 1)! ≡ −
a 2
mod p.
p
Os dois casos mais simples deste teorema são a = 1 e a = −1. Como a
equação x2 ≡ 1 mod p tem as soluções 1 e −1, então
( )
1
=1
p
para qualquer primo ı́mpar. O próximo teorema é baseado neste exemplo
Teorema 4.10 (Wilson). Seja p primo, então
(p − 1)! ≡ −1
mod p
Demonstração: Se p é ı́mpar então
( )
1
=1
p
Logo, considerando a = 1 no teorema anterior, obtemos o resultado enunciado. Se p = 2, então (p − 1)! = 1, donde (p − 1)! ≡ −1 mod 2.
2
Juntando os dois resultados anteriores, obtemos um processo para calcular
o sı́mbolo de Legendre:
59
Teorema 4.11 (Lema de Euler). Sejam p um primo ı́mpar e a um inteiro
tais que p - a. Então
( )
p−1
a
=a 2
mod p.
p
Ao contrário do teorema de Fermat, o recı́proco do teorema de Wilson
também é válido, obtendo-se um teste de primalidade.
Teorema 4.12. Seja m > 1. Então m é primo se e só se
(m − 1)! ≡ −1
mod m
Demonstração: Atendendo ao resultado anterior, basta-nos considerar
m > 1 composto. Então existe um inteiro 1 < d < m tal que d | m. Mas
então d | (m − 1)!. Logo, d - ((m − 1)! + 1). Donde, m - ((m − 1)! + 1). 2
Infelizmente, este teorema parece ser inútil para verificar na prática se
um número é primo ou não.
Em seguida consideramos o caso a = −1.
Teorema 4.13. O inteiro −1 é um resı́duo quadrático para os primos da
forma 4k + 1 e um não-resı́duo quadrático para os primos da forma 4k + 3,
i. e.
( )
p−1
−1
= (−1) 2 .
p
Demonstração: Resulta imediatamente do teorema 4.11.
2
Em seguida, vamos introduzir outra caracterização do sı́mbolo de Legendre, obtida por Gauss.
Seja p um primo ı́mpar e consideremos o conjunto dos resı́duos mı́nimos:
p−1 p−3
p−1
S = {−
,−
, . . . , −2, −1, 1, 2, . . . ,
}.
2
2
2
Seja (a, p) = 1 e seja µ o número de resı́duos mı́nimos negativos dos inteiros
. Por exemplo, seja p = 7 e a = 4. Então
a, 2a, 3a, dotsa p−1
2
1 ∗ 4 ≡ −3 mod 7
2 ∗ 4 ≡ 1 mod 7
3 ∗ 4 ≡ −2 mod 7
60
Portanto, neste caso, µ =(2.) Os valores de µ irão permitir-nos obter uma
caracterização simples de ap .
( )
Lema 4.14 (Lema de Gauss).
a
p
= (−1)µ .
Demonstração: Seja ±ml o resı́duo mı́nimo de la, onde ml é positivo.
Claramente, µ é o número de ocorrências do sinal negativo, quando l toma
valores entre 1 e (p − 1)/2. Note que, se 1 ≤ l < k ≤ (p − 1)/2, então
ml ̸= mk . Suponhamos que ml = mk . Então
la ≡ ±ka
mod p.
Como p - a, temos l ≡ ±k mod p. Mas esta congruência 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 } coincidem. Multiplicando as congruências
1a ≡ ±m1 mod p
2a ≡ ±m2 mod p
..
.
p−1
a ≡ ±m p−1 mod p
2
2
obtemos
(
)
(
)
p−1
p−1
p−1
µ
!a 2 ≡ (−1)
! mod p.
2
2
Portanto,
a
p−1
2
≡ (−1)µ
mod p.
Pelo teorema 4.11, obtemos o resultado pretendido.
2
Este resultado, permite-nos, por exemplo, saber para que primos, 2 é um
resı́duo quadrático.
61
Teorema 4.15. O inteiro 2 é um resı́duo quadrático para os primos da forma
8k + 1 e 8k − 1 e um não-resı́duo quadrático para os primos da forma 8k + 3
e 8k + 5, i. e.
( )
p2 −1
2
= (−1) 8 .
p
Demonstração: Seja p um primo ı́mpar. Note que µ é igual ao número
de elementos do conjunto T = {2, 4, 6, 8, . . . , p − 1} que são maiores que p−1
.
2
Se p = 8k + 1 então (p − 1)/2 = 4k e há 2k elementos de T menores ou
iguais a (p − 1)/2 e 2k elementos maiores que (p − 1)/2. Portanto, µ é par e
2 é um resı́duo quadrático de p.
Se p = 8k −1 então (p−1)/2 = 4k −1 e há 2k −1 elementos de T menores
ou iguais a (p − 1)/2 e 2k elementos maiores que (p − 1)/2. Portanto, µ é
par e 2 é um resı́duo quadrático de p.
Se p = 8k + 3 então (p − 1)/2 = 4k + 1 e há 2k elementos de T menores
ou iguais a (p − 1)/2 e 2k + 1 elementos maiores que (p − 1)/2. Portanto, µ
é ı́mpar e 2 é um não-resı́duo quadrático de p.
Se p = 8k +5 então (p−1)/2 = 4k +2 e há 2k +1 elementos de T menores
ou iguais a (p − 1)/2 e 2k + 1 elementos maiores que (p − 1)/2. Portanto, µ
é ı́mpar e 2 é um não-resı́duo quadrático de p.
2
(
2
2
2
Os números 1 , 2 , 3 , . . .
se
p−1
2
)2
, são todos incongruentes mod p, pois
r 2 ≡ s2
mod p
então r ≡ s mod p ou r ≡ −s mod p, e a segunda alternativa é impossı́vel.
Mais,
r2 ≡ (p − r)2 mod p,
p−1
p−1
portanto, se p for ı́mpar, há
resı́duos quadráticos e
não-resı́duos
2
2
quadráticos de p.
Teorema 4.16. Seja p um primo ı́mpar. O produto de dois resı́duos quadráticos de p ou de dois não-resı́duos quadráticos de p é um resı́duo quadrático
de p, enquanto que o produto de um resı́duo quadrático com um não-resı́duo
quadrático é um não-resı́duo quadrático. Isto é,
( )( ) ( )
a
b
ab
=
p
p
p
62
Demonstração: Pelo teorema 4.11,
( )( )
p−1 p−1
b
a
≡a 2 b 2
p
p
p−1
= (ab) 2
( )
ab
=
p
Donde,
mod p
mod p
mod p
( )( ) ( )
b
ab
a
=
p
p
p
2
Sejam p e q dois primos ı́mpar distintos. Se q é um resı́duo quadrático de
p, então a congruência
x2 ≡ q mod p
é solúvel. Analogamente, se p é um resı́duo quadrático de q, então a congruência
x2 ≡ p mod q
também é solúvel. Não parece haver qualquer conexão óbvia entre estas
duas congruências. Uma das grandes descobertas da matemática efectuadas
no século XVIII é que, de facto, há uma relação poderosa e subtil entre as
congruências mencionadas, que depende apenas de p mod 4 e de q mod 4.
Esta é a celebrada lei da reciprocidade quadrática de Gauss. Iremos enunciar este resultado e ver alguns exemplos, no entanto, não provaremos este
resultado, pois seria demasiado pesada para esta introdução à Teoria dos
Números.
Teorema 4.17. Sejam p e q primos ı́mpar distintos. Se p ≡ 1 mod 4 ou
q ≡ 1 mod 4 então p é um resı́duo quadrático mod q se e só se q é um
resı́duo quadrático mod p. Se p ≡ q ≡ 3 mod 4, então p é um resı́duo
quadrático mod q se e só se q é um não-resı́duo quadrático mod p. Isto é
( )( )
p−1 q−1
p
q
= (−1) 2 2
q
p
63
Exemplo. A lei da reciprocidade quadrática dá-nos um método efectivo para
calcular 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 quadrático de 59.
Exemplo. Como 51 = 3 · 17 e 97 ≡ 17 ≡ 1 mod 4, temos
( ) ( )( )
51
3
17
=
97
97
97
( )( )
97
97
=
3
17
( )( )
1
12
=
3
17
( )2 ( )
2
3
=
17
17
( )
17
=
3
( )
−1
=
3
= (−1)
= −1
64
3−1
2
Exemplo. A lei da reciprocidade quadrática também nos permite determinar
todos os primos p para os quais um dado inteiro a é um resı́duo quadrático.
Por exemplo, se a = 5, então
( ) ( ) {
5
p
1
se p ≡ 1, 4 mod 5
=
=
−1 se p ≡ 2, 3 mod 5
p
5
4.7
Algoritmo de Tonelli-Shanks
Teorema 4.18. Seja p um número primo tal que p ≡ 3 mod 4. Seja a um
inteiro que é um quadrado mod p (i. e., existe b tal que a ≡ b2 mod p).
p+1
Então a 4 é a raiz quadrada de a mod p.
p+1
Demonstração: Se a ≡ 0 mod p então, claramente, a 4 é a raiz
quadrada de a mod p. Suponhamos que a ̸≡ 0 mod p, então b ̸≡ 0 mod p.
Como p ≡ 3 mod 4, temos que p+1
é um inteiro. Basta-nos provar que o
4
p+1
quadrado de a 4 é congruente com a mod p. Temos
( )
p+1
p−1
a
2
4
2
(a ) ≡ a × a
≡a
≡ a mod p,
p
2
pelo Lema de Euler.
Embora o teorema anterior mostre que a determinação de raı́zes quadradas
mod p é muito simples quando p ≡ 3 mod 4, estas podem também ser calculadas qualquer primo ı́mpar, através do seguinte algoritmo, conhecido como
algoritmo de Tonelli-Shanks.
Dado p primo ı́mpar e n um resı́duo quadrático de p, pretende-se determinar uma solução da congruência x2 ≡ n mod p.
1. Sejam d e s inteiros positivos tais que m é ı́mpar e p − 1 = d2s , isto
é, divida-se p − 1 por 2 tantas vezes quantas for possı́vel (e denotamos
esse número de vezes por s), sendo d o resultado final.
2. Sejam r ≡ n
d+1
2
mod p, t ≡ nd mod p e s′ = s.
3. Determinar um não-resı́duo quadrático de p, que denotamos por z. Seja
c ≡ z d mod p.
65
4. Se t ≡ 1 mod p então r2 ≡ n mod p e, portanto, r é uma das raı́zes
quadradas de n. O algoritmo termina.
5. Caso contrário, determinar o menor i, com 1 ≤ i < s′ , tal que t2 ≡ 1
mod p.
i
s′ −i−1
6. Seja b ≡ c2
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.
p−1
Nota: Se p ≡ 3 mod 4, obtém-se nd ≡ n 2 ≡ 1 mod p, pelo lema de
Euler, portanto o passo 4. dá a solução mencionada no teorema anterior,
n
d+1
2
≡n
p+1
4
mod p.
Como n é um resı́duo quadrático mod p, tem-se
s′ −1
t2
≡n
p−1
2
≡1
mod p,
o que garante a existência de i nas condições indicadas no passo 5.
Note-se que em cada iteração do ciclo, tem-se r2 ≡ nt mod p, portanto
se t ≡ 1 mod p então r é uma das raı́zes quadradas de n.
Como z é um não-resı́duo quadrático então 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 também
era 2i , o novo t vai ter ordem 2j com j < i. Este facto, garante-nos que o
algoritmo vai ter de parar.
Exemplo. Vamos determinar a raiz quadrada de 143 mod 193. Como 193−
3+1
1 = 26 · 3, temos d = 3 e s = 6. Então r1 ≡ 143 2 ≡ 184 mod 193 e
t1 ≡ 1433 ≡ 64 ̸≡ 1 mod 193.
Um não-resı́duo quadrático de 193 é 5. Assim c1 ≡ 53 ≡ 125 mod 193. A
6−4−1
ordem de t mod 193 é 24 , portanto, i1 = 4. Obtemos assim, b1 ≡ 1252
≡
2
185 mod 193, r2 ≡ 184 · 185 ≡ 72 mod 193, c2 ≡ 185 ≡ 64 mod 193,
t2 ≡ 64 · 64 ≡ 43 mod 193 e s′2 = 4.
Continuando desta forma, obtemos as sequências (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 segurança seja baseada na dificuldade de um problema matemático que também tenha interesse fora da
66
criptografia. Qualquer progresso significante para resolver este problema é
rapidamente tornado público, porque haverá muitos matemáticos a trabalhar
neste problema, sem estarem preocupados com a sua relevância criptográfica,
sendo assim difı́cil manter secreto o progresso que é feito sobre este problema
particular. Assim, evita-se (em princı́pio) que alguém secretamente quebre o
criptosistema e que tire vantagens de outros ainda usarem um ciptosistema
que não é mais seguro. Claro que não há maneira de saber com certeza absoluta se, por exemplo, alguém já descobriu um método eficaz de atacar o
RSA, talvez mesmo sem saber um algoritmo rápido para factorizar inteiros.
Até agora nunca foi provado que quebrar o RSA é tão difı́cil como factorizar inteiros. O sistema de Rabin, também é baseado na dificuldade que
factorizar inteiros, mas em contraste com o RSA, pode ser mostrado que
alguém que quebre o sistema de Rabin, pode também factorizar inteiros de
uma maneira eficiente (e portanto, pode também quebrar o RSA).
Tal como no RSA, precisamos de dois primos grandes p e q, só que neste
sistema costuma-se impor a condição adicional p, q ≡ 3 mod 4, para simplificar os cálculos. Note-se que o sistema funciona mesmo que os primos que
não verifiquem esta condição. A chave pública da Alice é n = pq, a chave
privada é o par (p, q). O espaço 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 quadrada
de c.
Para recuperar a mensagem original m da mensagem cifrada c, Alice
determina
p+1
q+1
mp ≡ c 4
mod p e mq ≡ c 4
mod q.
Assim ±mp são as duas raı́zes quadradas de c mod p e ±mq são as duas
raı́zes quadradas de c mod q. Usando o teorema chinês do resto, obtém-se
quatro inteiros x1 , x2 , x3 e x4 cujo quadrado é congruente com c mod p e um
deles é a mensagem original m.
Há vários métodos para escolher a mensagem original das quatro raı́zes
quadradas de c mod n. Por exemplo, Alice pode escolher aquela que faz
sentido após ter sido descodificada. Por vezes este método não funciona: por
exemplo, se a mensagem enviada é uma chave de um sistema criptográfico
clássico (também conhecido por sistema simétrico, i. e. onde não há chaves
67
públicas). Se Bob cifrar apenas mensagens com uma certa forma, por exemplo, os primeiros 64 bits são iguais aos últimos 64 bits, é pouco provável que
mais de uma das raı́zes quadradas tenha esta forma. Basta então escolher a
raiz quadrada que tem esta forma. Note-se que se é escolhido este método
para recuperar a mensagem original, a equivalência entre quebrar o sistema
de Rabin e factorizar inteiros, deixa de existir. Depois de ilustrarmos este
sistema com um exemplo simples, provaremos esta equivalência.
Exemplo. Alice usa os números primos p = 11 e q = 23. Então n = 253.
Bob cifra a mensagem m = 158 calculando
c ≡ m2
mod n.
Verifica-se que c = 170. Alice calcula
mp ≡ c
p+1
4
mod p e mq ≡ c
q+1
4
mod q,
obtendo mp = 4 e mq = 3. Usando o teorema chinês do resto, Alice obtém
quatro raı́zes quadradas de c mod n, que são 26, 95, 158, 227, uma delas é a
mensagem original.
Teorema 4.19. Quebrar o sistema Rabin é tão difı́cil como factorizar inteiros. Por outras palavras, se alguém descobrir um algoritmo que quebre
o sistema de Rabin, ele pode usar este algoritmo para factorizar inteiros de
uma maneira eficiente.
Demonstração: Claramente, qualquer pessoa que consiga factorizar n ,
consegue também quebrar o sistema de Rabin. Suponhamos agora que Olga
descobriu um algoritmo, R, para quebrar o sistema de Rabin. Seja n, o
módulo público, e sejam p e q, os seus factores primos. Dada uma mensagem
cifrada c mod n, Olga obtém m = R(c). Portanto, dado um quadrado
c mod n, o algoritmo R, permite determinarmos uma raiz quadrada de c
mod n. Vejamos como podemos usar este algoritmo para factorizar n: Olga
escolhe, aleatoriamente, um inteiro 1 ≤ x ≤ n − 1. Se (n, x) = d ̸= 1 então
d é um factor de n e a factorização de n está encontrada (n = d · nd ). Caso
contrário, 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, mas
não é necessariamente igual a x. No entanto, m satisfaz um dos seguintes
68
pares de congruências:
m≡x
m≡x
m ≡ −x
m ≡ −x
mod
mod
mod
mod
p
p
p
p
e
e
e
e
m ≡ x mod q
m ≡ −x mod q
m ≡ x mod q
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 último caso, m = n − x e, como
(n, x) = 1, obtemos (m − x, n) = 1. Portanto, este procedimento factoriza n
com 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ı́zes
quadradas mod 253 com o seu algoritmo R. Ela selecciona, x = 17 e
obtém (17, 253) = 1. Depois calcula c ≡ 172 ≡ 36 mod 253. As raı́zes
quadradas de 36 mod 253 são 6, 17, 236 e 247. Temos (6 − 17, 253) = 11
e (247 − 17, 253) = 23, portanto, se o algoritmo R obteve 6 ou 247 então
Olga encontrou a factorização de 253, caso contrário, Olga escolhe outro inteiro x e aplica o procedimento outra vez. Depois de poucas aplicações é
muito provável que Olga tenha encontrado a factorização de n sem demorar
demasiado tempo.
4.9
Protocolo Diffie-Hellman
Nesta secção, é descrito o protocolo de Diffie e Helman para troca de chaves
secretas através de canais inseguros. Este protocolo não é um sistema criptográfico, mas serve de base ao sistema criptográfico ElGamal, que descreveremos na próxima secção.
Temos a seguinte situação: Alice e Bob pretendem usar um sistema
simétrico para a sua comunicação através de um canal inseguro. Primeiro
têm que trocar uma chave secreta que ambos irão utilizar. O sistema de troca
de chaves Diffie-Hellman, permite que Alice e Bob troquem as suas chaves e
mesmo que alguém intercepte esta troca de chaves, a informação obtida não
pode ser usada para construir a chave secreta.
69
O sistema de troca de chaves Diffie-Hellman utiliza um outro problema
difı́cil de teoria dos números, nomeadamente o problema do logaritmo discreto. Comecemos por descrever este problema:
Seja p um número primo e seja g uma raiz primitiva de p. Então g gera
o grupo cı́clico (Z/pZ)∗ . Portanto, para qualquer 1 ≤ A ≤ p − 1, existe
0 ≤ a ≤ p − 2 tal que
A ≡ g a mod p
a a chamamos o logaritmo discreto de A na base g. A determinação de
logaritmos discretos é considerado um problema difı́cil. Até agora, não existe
nenhum algoritmo eficiente para resolver este problema.
Voltemos ao protocolo de Diffie-Hellman. Primeiro, Alice e Bob chegam a
acordo sobre um primo p grande e uma raiz primitiva de p, digamos g. Tanto
p como g podem ser públicos. Em seguida, Alice escolhe aleatoriamente um
inteiro 0 ≤ a ≤ p − 2 e envia A ≡ g a mod p para Bob. O expoente a é
mantido secreto. Analogamente, Bob escolhe aleatoriamente 0 ≤ b ≤ p − 2,
e envia B ≡ g b mod p para Alice. Também b é mantido secreto. Para obter
a chave secreta comum, Alice calcula
B a ≡ g ab
mod p
Ab ≡ g ab
mod p.
e Bob calcula
A chave secreta é k ≡ g ab mod p.
O inimigo Orlando, conhece os inteiros p, g, A e B, mas não conhece os
logaritmos discretos a de A e b de B na base g. Portanto, ele conhece g a
mod p e g b mod p e gostaria de conhecer g ab mod p. Até agora, nunca foi
encontrado um algoritmo que permita obter k, sabendo A e B. O único
processo conhecido para quebrar o protocolo de Diffie-Hellman é conseguir
primeiro determinar os logaritmos discretos de A e de B, e os algoritmos
existentes para resolver este problema são pouco eficientes (demoram muito).
4.9.1
Ataque do homem no meio
Existe um ataque a este protocolo que explora o facto de Alice não poder
verificar que as mensagens que recebe vêm de facto de Bob. Este ataque
chama-se o ataque do homem no meio. Orlando intercepta todas as mensagens 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 que
Bob envia uma mensagem cifrada a Alice, usa a chave que tinha trocado
com Orlando, pensando que esta a usar a chave de Alice. Orlando recebe a
mensagem e decifra-a, depois altera esta mensagem (ou não) e envia-a para
Alice usando a chave que tinha trocado com ela.
Para prevenir este tipo de ataques, podem ser usadas assinaturas. Este
assunto será tratado mais tarde.
4.10
Sistema ElGamal
Este sistema usa o facto de ser difı́cil obter logaritmos discretos, tal como o
protocolo de Diffie-Hellman.
Alice escolhe um número 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 pública de Alice é o terno (p, g, A). A sua chave secreta é o exponente a. O inteiro A é a parte da chave, proveniente do protocolo de DiffieHellman, que pertence a Alice. O espaço de mensagens originais é o conjunto
{0, 1, . . . , p − 1}. Para cifrar uma mensagem e enviá-la para Alice, Bob usa
a chave pública de Alice, (p, g, A). Escolhe um inteiro b ∈ {1, . . . , p − 2} e
calcula
B ≡ g b 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 ≡ Ab m
mod p.
Bob envia a Alice o par (B, c). Note que B depende da chave pública de
Alice (depende de A, g e p escolhidos por Alice) e, portanto não faz parte da
chave pública de Bob, i. e. da chave que Bob usa para receber mensagens.
Na sua chave pública, Bob tem provavelmente outro primo q e outra raiz
primitiva de q.
Para decifrar a mensagem m, Alice determina x = p − 1 − a e calcula B x c
mod p que vai ser a mensagem original m pois
B x c ≡ g b(p−1−a) Ab m ≡ (g p−1 )b (g a )−b Ab m ≡ A−b Ab m ≡ m
71
mod p.
4.10.1
Ataque da repetição da chave efemera
Para cada nova mensagem que envie a Alice, Bob deve escolher um novo
expoente b, caso contrário o seguinte ataque permite decifrar as mensagens:
Se Bob escolher o mesmo expoente b para cifrar as mensagens m e m′ ,
ele obtém
c ≡ Ab m mod p e c′ ≡ Ab m′ mod p
donde
c′ c−1 ≡ m′ m−1
mod p
Um atacante que saiba m pode obter m′ , usando a fórmula
m′ ≡ c′ c−1 m
4.11
mod p.
Sistema Merkle-Hellman
Nesta secção descrevemos outro tipo de criptosistema que é baseado no problema do saco-mochila (em inglês, ”Knapsack”). Dados k inteiros v0 , . . . , vk−1
e um inteiro V , o problema Saco-mochila consiste em determinar se existe
um subconjunto dos k inteiros cuja soma seja V , i.e. se existem ϵi ∈ {0, 1},
tais que
k−1
∑
ϵi vi = V.
i=0
Note que podem haver imensas soluções, nenhuma solução, ou uma única
solução, dependendo dos vi ’s e de V . Um caso particular do problema sacomochila, é quando os vi ’s, ordenados de forma crescente, têm a propriedade de
que cada um é maior que a soma dos anteriores. Este caso especial é chamado
super crescente. Por exemplo, a sequência (2, 3, 7, 15, 31) é supercrescente.
Sabe-se que o problema geral do saco-mochila pertence à classe de problemas muito difı́ceis conhecidos como NP-completos (i. e. problemas NP
tais que qualquer outro problema NP se pode reduzir a eles). Os problemas
NP-completos têm a extraordinária propriedade de que se um deles estiver
na classe P (existir um algoritmo que o resolva em tempo polinomial), então
P=NP.
O problema do saco-mochila super crescente é, no entanto, muito mais
fácil de resolver. O seguinte algoritmo (de tempo polinomial) permite-nos
resolver qualquer problema do saco-mochila super crescente:
Seja v0 , . . . , vk−1 uma sequência super crescente e V um inteiro.
72
1. Faça W = V e j = k.
2. Se vi > W para 0 ≤ i ≤ j − 1 ir para o passo 4. Caso contrário,
determine o maior dos vi ’s, digamos vi0 , tal que vi0 ≤ W . Faça ϵi = 0
para 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 solução
ϵ = (ϵ0 , . . . , ϵk−1 ),
(que é única) do problema. Se W > 0, todos os restantes vi ’s são
maiores que W , portanto, não há solução do problema.
Exemplo. Considere a sequência (2, 3, 7, 15, 31) e V = 24. Então ϵ4 = 0,
ϵ3 = 1 (e substituimos 24 por 9), ϵ2 = 1 (e substitui-se 9 por 2), ϵ1 = 0 e
ϵ0 = 1. Portanto, a solução é ϵ = (1, 0, 1, 1, 0).
Estamos em condições de descrever o criptosistema de Merkle-Hellman
(também chamado sistema do saco-mochila), baseado no problema descrito
atrás. As mensagens originais vão ser inteiros com k bits. Por exemplo, se
usarmos o alfabeto de 27 letras (com o espaço em branco) e k = 5, temos a
codificação (letra a letra, neste caso) 2 = (00000)2 , A = (00001), . . . , Z =
(11010). Em seguida, escolhemos uma sequência 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 sequência de
inteiros positivos
wi ≡ avi mod n
para qualquer 0 ≤ i ≤ k − 1. A chave secreta de Alice consiste da sequência
dos vi ’s e dos inteiros n, a e b. A sua chave pública é (w0 , . . . , wk−1 ). Esta é
a chave para cifrar.
Se Bob pretende enviar uma mensagem m = (ϵk−1 · · · , ϵ0 )2 a Alice, usa a
chave {wi } e envia
k−1
∑
c≡
ϵ i wi .
i=0
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, este
problema é difı́cil porque a sequência {wi } não é super crescente.
73
Para decifrar c, Alice calcula V ≡ bc mod n. Como
bc ≡
k−1
∑
i=0
ϵi bwi ≡
k−1
∑
ϵi bavi ≡
i=0
k−1
∑
ϵ i vi
mod n
i=0
∑k−1
Então V =
i=0 ϵi vi (note que V < n). Como a sequência {vi } é super
crescente, Alice usa o algoritmo descrito atrás para obter a solução ϵ =
(ϵ0 , . . . , ϵk−1 ) e obtém a mensagem m = (ϵk−1 · · · , ϵ0 )2 .
Exemplo. Consideremos a codificação em bits do nosso habitual alfabeto de
27 letras. Tomemos a chave secreta
((v0 , . . . , vk−1 ), n, a) = ((2, 3, 7, 15, 31), 61, 17)
Então b = 18 e a chave de cifrar é (34, 51, 58, 11, 39). Queremos enviar
a 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 e
103 = 34+58+11. A mensagem cifrada 124, 45, 103 poderia ser descodificada
usando, 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 sequência para
resolver 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 criptosistema, porque a base da sua segurança é um problema que se sabe ser
NP-completo (os problemas factorização e logaritmo discreto, são NP, mas
não se sabe se são NP completos). Em 1982, Shamir encontrou um algoritmo
que permitia quebrar este sistema em tempo polinomial. Várias variações
deste sistema tem sido consideradas, tendo algumas sido também quebradas
(e. g. Brickell 1985). Uma das variações deste sistema que ainda não terá
sido quebrado é o sistema de Chor-Rivest, que não iremos descrever neste
curso.
74
Capı́tulo 5
Primalidade
Existem imensas situações em que podemos necessitar de saber se um inteiro enorme é primo. Por exemplo, nos sistemas criptográficos estudados
no capı́tulo anterior, precisamos quase sempre de pelo menos um primo
enorme e aleatório. Uma interpretação do que significa ”primo enorme e
aleatório”pode ser a seguinte: Primeiro geramos um inteiro ı́mpar n0 , usando um gerador de números aleatórios e depois testar a primalidade de n0 ,
n0 + 2, . . . até que encontremos o primeiro primo p ≥ n0 . Outra situação
em que se usam testes de primalidade, é quando se quer determinar se inteiros de formas muito especiais são ou não primos. Por exemplo, números
k
de Mersenne (da forma 2p − 1) ou números de Fermat (da forma 22 + 1).
Um teste de primalidade probabilı́stico é um critério para um número n
não ser primo. Se n passa uma aplicação de um teste de primalidade, então
pode ser que seja primo. Se n falha um teste de primalidade então é (obrigatoriamente) composto. Se passar muitas vezes um teste de primalidade então
tem grande probabilidade de ser primo (podendo por vezes ter-se a certeza
que é realmente primo). No caso de n ser composto ficamos ainda com o
problema de factorizar n. Com os algoritmos existentes consegue-se verificar
se um número com alguns milhares de algarismos é primo, com grande probabilidade (se n tiver uma forma especial, por exemplo se for um número de
Mersenne ou de Fermat, consegue-se atestar a primalidade de números com
milhões de algarismos), enquanto que só se consegue factorizar números (que
não tenham nenhuma forma particular) com perto de 200 algarismos.
75
5.1
Teste de Fermat
Antes de descrevermos este teste de primalidade recordemos algumas definições
de teoria elementar dos números.
Definição. Seja a > 1 um inteiro positivo. Chamamos pseudoprimo para a
base a a um composto n tal que (a, n) = 1 e n | (an − a).
Definição. Um composto n que é pseudoprimo para qualquer base a, tal
que (a, n) = 1 chama-se número de Carmichael.
Exemplo. Os números 561, 1105 e 6601 são números de Carmichael.
O teste de Fermat é baseado no Pequeno Teorema de Fermat. Dados n e
1 < a < n, o teste consiste verificar se an−1 ̸≡ 1 mod n. Podemos aplicá-lo
usando sucessivas bases a: Dado um inteiro n, começamos por calcular
a ≡ 2n−1
mod n
se a ̸= 1 então 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 e
assim sucessivamente.
Infelizmente, há inteiros que passam este teste para qualquer base, os
chamados números de Carmichael. Portanto, não é possı́vel provar que né
primo, usando sucessivas aplicações deste teste.
Exemplo. Considere n = 341. Temos 2340 ≡ 1 mod 341. Mas 3340 ≡ 56
mod 341. Portanto, 341 é composto. De facto, 341 = 11 · 31. Provámos
também que 341 é pseudoprimo para a base 2 mas não é pseudoprimo para
a base 3.
Note que este teste, embora prove que n é composto, não dá qualquer
indicação sobre os factores de n. Só mostra que a n falta uma propriedade
que todos os primos têm.
76
5.2
Teste de Miller-Rabin
Nesta secção, descrevemos o teste de Miller-Rabin. Contrariamente ao teste
de Fermat, para este teste não há inteiros correspondentes aos números de
Carmichael, i. e. o teste de Miller-Rabin pode provar que é de facto primo
qualquer inteiro que passe o teste um número suficiente de vezes.
Teorema 5.1. Seja n um primo ı́mpar e sejam s e d tais que n − 1 = 2s d,
com d ı́mpar. Se a é um inteiro tal que (a, n) = 1, então ou
ad ≡ 1 mod n
ou existe 0 ≤ r ≤ s − 1 tal que
rd
a2
≡ −1
mod n
Demonstração: Seja a tal que (a, n) = 1. Como n é primo temos que
φ(n) = n−1 = 2s d. Donde, k = ordn (ad ) é uma potência de 2. Se k = 1 = 20 ,
temos que
ad ≡ 1 mod n.
Se k > 1 então existe 1 ≤ l ≤ s tal que k = 2l e
l
a2 d ≡ 1 mod n.
Mas então a2 d ̸≡ 1 mod n e a2 d tem ordem 2 mod n. Logo a2 d é
solução da congruência x2 ≡ 1 mod n. Como n é primo, as únicas soluções
desta congruência são 1 e −1. Portanto,
l−1
l−1
a2
l−1 d
l−1
≡ −1 mod n
2
Definição. Seja n um composto ı́mpar, e sejam s e d tais que n − 1 = 2s d,
com d ı́mpar. Seja a tal que (a, n) = 1. Se n e a satisfazem a condição
rd
ad ≡ 1 mod n ou existe 0 ≤ r ≤ s − 1 tal que a2
≡ −1 mod n (5.1)
então dizemos que n é pseudoprimo forte para a base a.
77
Definição. Dizemos que um inteiro a é uma testemunha de que n é composto
se (a, n) = 1 e a condição (5.1) não é verificada.
Dados a e n, o teste de Miller-Rabin, consiste em verificar se a condição
(5.1) é ou não verificada por estes inteiros. Se n falhar esta condição então
n é composto e a é uma sua testemunha.
Exemplo. Seja n = 561. Já vimos que n é um número de Carmichael,
portanto o teste de Fermat não dá para provar que n é composto. Temos que
560 = 24 · 35. Consideremos a = 2. Então
235 ≡ 263 mod 561
22·35 ≡ 166 mod 561
22
2 ·35
23 ·35
2
≡ 67 mod 561
≡ 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 um
número suficiente de testemunhas para cada composto. O próximo resultado
mostra que há imensas testemunhas.
Teorema 5.2. Seja n ≥ 3 um composto ı́mpar. O conjunto {1, . . . , n − 1}
contém no máximo n−1
números que são primos com n e não são testemunhas
4
de que n é composto.
Suponhamos que n é um inteiro ı́mpar enorme que queremos verificar se é
primo ou não. Seja 1 < a < n − 1 escolhido aleatoriamente. A probabilidade
de n ser composto e a não ser uma testemunha é, no máximo, 0.25. A
probabilidade de escolhermos k inteiros a que não sejam testemunha é menor
que
1
.
4k
Portanto, se um inteiro n passa o teste de Miller-Rabin k vezes, é muito
provável que seja primo (com probabilidade pelo menos 1 − 1/4k ). Para
k = 20, a probabilidade de ser composto tendo passado o teste de MillerRabin k vezes é 1 em um bilião. No entanto, note-se que este teste não nos
garante que n seja de facto primo.
Já vimos que, dado um composto n, há mais de 3(n − 1)/4 testemunhas
no intervalo [2, n − 2]. Será que há um número B, independente de n, tal
78
que há sempre uma testemunha a < B de que n é composto? Infelizmente, a
resposta a esta pergunta é não (provado por Alford, Granville e Pomerance).
No entanto, se a Hipótese de Riemann extendida (ERH) for verdade, temos
o seguinte resultado
Teorema 5.3. Seja n um número composto. Admitindo a ERH, há uma
testemunha a, com a < 2 log2 n de que n é composto.
Portanto, se ERH for verdadeira, existe um algoritmo polinomial para
verificar se n é primo, baseado no teste de Miller-Rabin.
5.3
Teste de Solovay-Strassen
O próximo teste que iremos estudar é baseado no lema de Euler sobre o
sı́mbolo de Legendre, já estudado. Comecemos por definir o sı́mbolo de
Jacobi, que é uma generalização do sı́mbolo de Legendre.
∏
Definição. Seja a um inteiro e n = ki=1 pai i um inteiro ı́mpar. Define-se o
sı́mbolo de Jacobi, da seguinte maneira
( )a i
(a) ∏
a
k
=
i=1
,
n
pi
( )
onde ap é o sı́mbolo de Legendre.
Para o sı́mbolo de Jacobi também é válida a lei da reciprocidade quadrática,
i. e., se m e n são inteiros impares
(m)
(n)
m−1 n−1
= (−1) 2 2
.
n
m
O lema de Euler diz-nos que se p um primo ı́mpar e a um inteiro tais que
p - a. Então
( )
p−1
a
=a 2
mod p.
p
Dado um inteiro ı́mpar n e a um inteiro, o Teste de Solovay-Strassen
consiste em verificar se
(a)
n−1
2
≡
mod n.
a
n
79
Definição. Um inteiro n composto que passe o teste de Solovay-Strassen
para um dado a é chamado pseudoprimo de Euler-Jacobi para a base a
Teorema 5.4. Para qualquer número composto n há pelo menos n/2 bases
menores que n tais que n não é um pseudoprimo de Euler-Jacobi para qualquer uma dessas bases.
5.4
Teste n − 1 de Lucas
Nas secções anteriores encontrámos alguns testes probabilisticos para verificar se n é composto. O próximo teste é determinista, i. e. se n passar o
teste então n é de facto primo.
Teorema 5.5 (Lucas). Se a e n são inteiros com n > 1, e
an−1 ≡ 1 mod n, mas a
n−1
q
̸≡ 1 mod n para qualquer primo q | n − 1
então n é primo.
Demonstração: A primeira condição implica que ordn (a) | n − 1. A
segunda condição, mostra que ordn (a) não é um divisor próprio 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 é
primo.
2
Para usarmos o teorema de Lucas, é necessário saber a factorização em
primos de n − 1, e em geral essa factorização pode ser difı́cil de encontrar.
Além disso, se n é de facto primo, temos que tomar a uma raiz primitiva de
n. Sabemos que há φ(n − 1) raı́zes primitivas, mas estas podem ser difı́ceis
de encontrar. No entanto, para inteiros com formas especiais, o teorema de
Lucas, permite-nos obter um teste muito eficiente.
Teorema 5.6 (Teste de Pepin). Para k ≥ 1, o número Fk = 22 + 1 é primo
se e só se
Fk −1
3 2 ≡ −1 mod Fk .
k
Demonstração: Seja k ≥ 1. Suponhamos que
3
Fk −1
2
≡ −1 mod Fk
80
então o teorema de Lucas diz-nos que Fk é primo. Reciprocamente suponhamos que Fk é primo. Como 2k é par, então
k
22 ≡ 1 mod 3,
donde Fk ≡ 2 mod 3. Mas Fk ≡ 1 mod 4, logo
( )
3
= −1
Fk
Pelo teorema 4.11, obtemos a congruência desejada.
2
Teorema 5.7 (Teste de Lucas-Lehmer). Seja s0 = 4 e si = s2i−1 − 2. Então
Mp = 2p − 1 é primo se e só se sp−2 ≡ 0 mod Mp .
81
Capı́tulo 6
Factorização
Neste capı́tulo, vamos descrever alguns algoritmos importantes de factorização. Iremos assumir que n é composto. Este facto pode ser provado
usando, por exemplo, um dos algoritmos do capı́tulo anterior.
Em muitos dos algoritmos de factorização, verifica-se primeiro, por experimentação, se n é divisı́vel por números primos pequenos, e. g. p ≤ B,
com B fixo.
Exemplo. Queremos factorizar n = 321 +1 = 10460353204. Experimentando
primeiro 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 de
Fermat implica que m é composto. Ficamos ainda com a tarefa de factorizar
m.
6.1
Método p − 1 de Pollard
Há algoritmos de factorização que funcionam muito bem para inteiros compostos que verificam certas propriedades. O método p − 1, é um desses
algoritmos e foi inventado por John Pollard. Suponhamos que n é composto
e que tem um factor primo p, tal que p − 1 só tem divisores primos pequenos.
Então é possı́vel obter um múltiplo k de p − 1 sem sabermos o valor de p − 1.
Basta tomar k como sendo o mı́nimo múltiplo comum de todos os inteiros
até um limite B. Podemos também tomar k como sendo B!.
82
Definamos k = k(B) = [2, 3, 4, . . . , B], onde [a, b] representa o mı́nimo
múltiplo comum de a e b. Se n tiver um divisor primo p tal que todos os
divisores de p − 1 que são potências de primos forem menores que k, então
p − 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). Se
n - (ak − 1) então (ak − 1, n) é um divisor próprio de n.
O algoritmo consiste em começar com um limite B e uma base a. Se
k
(a − 1, n) não der um divisor próprio de n (i. e. se (ak − 1, n) = 1 ou
(ak − 1, n) = n), então experimenta-se outro limite B ou outra base a.
Exemplo. Continuando o exemplo anterior, vamos agora factorizar m =
1241143. Seja B = 13, então
k = 8 · 9 · 5 · 7 · 11 · 13
e
(2k − 1, m) = 547.
Então p = 547 é um divisor de n. Portanto, m = 547 · 2269. Facilmente, se
verifica que 547 e 2269 são primos.
6.2
Método ró de Pollard
Nesta secção, vamos analisar outro método de factorização introduzido por
J. Pollard. Sejam l um inteiro e f uma função aleatória de S = {0, 1, . . . , l}
para S. Seja x0 um elemento aleatório e considere-se a sequência
x0 , x1 = f (x0 ), x2 = f (x1 ), . . . .
Como S é finito, a sequência irá tornar-se cı́clica ao fim de um certo número
de termos. Se fizermos um diagrama que mostre este comportamento, ele
assemelhar-se-á a ρ, daı́ a origem do nome do método.
Seja n um inteiro composto. O primeiro passo do método ró, consiste em
escolher uma função f de Z/nZ para Z/nZ que seja fácil determinar f (x).
Costuma-se usar polinómios 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 iterações xk = f (xk−1 ) mod n. Depois fazemse comparações entre diferentes xi ’s, esperando encontrar dois que sejam
diferentes mod n mas que sejam iguais mod l para algum divisor próprio l
de n. Quando encontrarmos xj e xk nestas condições (i. e. xj ≡ xk mod l),
temos que (xj − xk , n) é um divisor próprio de n. Assim como está, este
método irá tornar-se moroso, pois ao fim de k iterações temos de comparar
aproximadamente k 2 pares de valores. Note que se xj ≡ xk mod l e sendo
m ≥ 0, temos
xj+m ≡ xk+m mod l
Portanto, em vez de efectuar todas as comparações possı́veis podemos apenas
fazer uma comparação em cada iteração. Por exemplo, podemos calcular
somente
(x2i − xi , n)
em cada iteração i. Podemos também calcular, na iteração k com 2j ≤ k <
2r+1 , o máximo divisor comum
(xk − xj , n)
onde j = 2j − 1.
Exemplo. Vamos factorizar 4087 usando f (x) = x2 + 1 e x0 = 3. Obtemos
sucessivamente
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
(x1 0 − x7 , n) = 571. Portanto, n = 571 · 1481.
Teorema 6.1. O método ró permite encontrar um factor de n em
√
O( 4 n log3 n)
operações com uma grande probabilidade. Mais exactamente, existe uma constante C tal que, para qualquer inteiro positivo λ, a√probabilidade
de o método
√
3
4
ró não encontrar um factor não trivial de n em C λ n log n operações bit,
é menor que exp(−λ).
84
O teorema anterior garante-nos que este método é, com uma grande probabilidade, significativamente
mais rápido que irmos experimentando todos os
√
primos até n. O resultado mais espectacular, usando este método ocorreu
8
em 1981, quando Brent e Pollard factorizaram completamente F8 = 22 + 1.
A seguinte mnemónica de J. Pollard, permite-nos recordar um dos factores
de F8
I am now intirely persuaded to employ rho method, a handy trick,
on gigantic composite numbers
6.3
Factorização de Fermat
Suponhamos que n é o produto de dois primos p e q próximos um do outro.
Então n é a diferença de dois quadrados, um dos quais é pequeno. Neste caso,
há um processo eficiente de factorizar n chamado factorização de Fermat. Por
este motivo deve-se evitar usar tais inteiros n como chave pública, tanto no
RSA como no sistema de Rabin.
Teorema 6.2. Seja n um inteiro positivo ı́mpar. Há uma correspondência
bijectiva entre factorizações de n da forma n = ab, com a ≥ b > 0, e
representações de n na forma t2 − s2 , onde t e s são inteiros não negativos.
A correspondência é dada pelas equações
t=
a+b
a−b
, s=
a=t+s b=t−s
2
2
Demonstração: Se n = ab então
(
)2 (
)2
a+b
a − b2
−
n=
2
2
donde n pode ser escrito como a diferença de dois quadrados. Se n = t2 − s2
então n = (t − s)(t + s). Obtemos assim a correspondência bijectiva.
2
Se n = ab e a e b estão
√ próximos um do outro, então s é pequeno e t é
ligeiramente maior que n. Neste caso,
√ podemos factorizar n, experimentando valores para t, começando por [ n] + 1, até que se encontre um para
o qual t2 − n é um quadrado perfeito.
85
√
Exemplo. Seja n = 200819. Começamos com [ n] + 1 = 449. Agora,
4492 − 200819 = 782 que não é um quadrado perfeito. Em seguida, tentamos
t = 450. Temos 4502 − 200819 = 1681 = 412 , donde
n = (450 + 41)(450 − 41) = 491 · 409.
Note que se a e b não estiverem próximos, este método ainda serve para
factorizar n, mas só após termos usado imensos valores para t, o que o pode
tornar muito moroso. Há uma generalização do método de Fermat que funciona melhor nesta situação. Começamos por escolher um multiplicador k
pequeno e tomamos
√
√
t = [ kn] + 1, t = [ kn] + 2, . . .
até que obtenhamos um t para o qual t2 − kn = s2 é um quadrado perfeito.
Então d = (t + s, n) é um factor não trivial de n.
Exemplo. Seja n = 141467. Se usarmos a factorização de Fermat directamente, precisamos de experimentar 38 t’s até encontrar
um factor de n. Mas
√
se tomarmos k = 3 e começarmos com t = [ 3n] + 1 = 652, rapidamente
vemos que 6552 − 3n = 682 . Como (655 + 68, n) = 241, concluı́mos que
n = 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? Uma
maneira de resolver este problema é utilizando o método de Lehman (que é
uma generalização do método de Fermat).
√
A ideia deste método é experimentarmos todos os k até [ 3 n] e para cada
um desses k’s , experimentar somente
[√
]
6
n
√
4 k
valores
se n tem algum divisor
√ de t. Mais exactamente, primeiro verifica-se
√
d ≤ 3 n. Caso contrário, para cada 1 ≤ k ≤ [ 3 n], experimenta-se, para cada
t inteiro no intervalo
(
]
√
6
√
√
n
2 kn − 1, 2 kn + √ ,
4 k
se t2 − 4kn é um quadrado perfeito s2 . Caso seja, determina-se d = (t + s, n)
que é um factor não trivial de n. Caso não se encontre um quadrado perfeito,
podemos concluir que n é primo.
Para provarmos que este algoritmo de facto funciona, necessitamos do
seguinte resultado de Dirichlet:
86
Teorema 6.3 (da Aproximação de Dirichlet). Para qualquer número real θ
e qualquer inteiro positivo m, existem inteiros a e b, com 1 ≤ a ≤ m tais que
|aθ − b| ≤
1
.
m+1
Demonstração: No que se segue iremos representar a parte inteira e a
parte fraccionária de um número 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 números reais, 0, 1 e
ra = {aθ} = aθ − [aθ],
onde 1 ≤ a ≤ m. Note que se ri ≥ rj e i > j então ri − rj = ri−j .
Analogamente, se ri ≥ rj e j > i então 1 − (ri − rj ) = rj−i . Consideremos
também a seguinte partição do intervalo [0, 1],
Ik = [
k
k+1
,
), com 0 ≤ k ≤ m − 1
m+1 m+1
m
e Im = [ m+1
, 1]. Como temos m + 2 números reais em [0, 1] e a partição de
[0, 1] tem m + 1 subintervalos, então um desses intervalos, digamos Ik , tem
pelo menos dois dos números reais considerados. Se k = 0 então existe um
inteiro 1 ≤ a ≤ m tal que
ra ≤
1
1
, i.e. |aθ − [aθ]| <
.
m+1
m+1
Se k = m então existe um inteiro 1 ≤ a ≤ m tal que
1 − ra ≤
1
1
, i.e. |aθ − [aθ] − 1| ≤
.
m+1
m+1
Se 0 < k < m então 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)θ] ≤
87
1
.
m+1
Se j > i temos 1 − (ri − rj ) = rj−i e
|(j − i)θ − [(j − i)θ] − 1| ≤
1
.
m+1
2
√
Teorema 6.4. O método de Lehman está correcto e demora O( 3 n log2 n)
operações bit.
Demonstração: Suponhamos que o método está correcto, e de facto nos
dá um divisor de n ou prova que n é primo. Vejamos quantas operações bit
demora.
A parte inicial de √
experimentar se n tem algum divisor menor que
√
√
3
n demora no máximo O( 3 n log2 n) pois para cada inteiro menor que 3 n
fazemos uma divisão (se experimentássemos só primos terı́amos um factor
log n a menos). Caso tenhamos que passar à segunda parte do método,
temos que verificar
√
⌈ 3 n⌉ [ √
∑ 6n]
√
√ = O( 3 n)
4 k
k=1
vezes se t2 − 4kn é um quadrado perfeito (cada um demora O(log2 n)). Só
no caso de obtermos um quadrado perfeito
√ é que precisamos de calcular
(d = t + s, n). Portanto, no total temos O( 3 n log2 n) operações bit.
Provemos agora que o método
√ de Lehman está correcto. Podemos assumir
que n √
não tem factores d ≤ 3 n. Se n não é primo
então n = pq com
√
3
3
p, q > n. Vamos provar que existe um inteiro k ≤ [ n] , k = uv com
√
|uq − vp| < 3 n
Seja m = [n 6 q 2 p− 2 ]. Pelo teorema da aproximação de Dirichlet, existem
inteiros positivos a e b, com 1 ≤ a ≤ m, tais que
1
1
1
1
p
.
|a − b| ≤
q
m+1
Mas então
√
q
q
n √
|ap − qb| ≤
< √ √ < √
= 3 n.
6
q
6
m+1
n
n p
88
Portanto, tomando u = b, v = a obtemos
|uq − vp| <
√
3
n
√
Falta provar que uv ≤ [ 3 n]. Sabemos que
u
p
1
< +
v
q vm
e v ≤ m, donde,
uv =
1
u 2 p 2
v
pq 1
v < v +
≤
n 3 + 1 = n 3 + 1.
v
q
m
qp
Consideremos c = uq + vp e e = |uq − vp|. Então 4kn = c2 − e2 . Em seguida,
provamos que
1
√
√
n6
2 kn ≤ c < 2 kn + √ .
4 k
√
√
Como (uq)(vp) = kn, então c = uq + vp ≥ 2 kn. Seja E = c − 2 kn, então
√
√
2
4kn + 4E kn ≤ (2 kn + E)2 = c2 = 4kn + e2 < 4kn + n 3 ,
logo
1
n6
E< √ .
4 k
Para terminar, só temos que mostrar que (c + e, n) é um factor não trivial
de n. Como n | (c + e)(c − e), basta mostrar que c + e < n. Temos, para
n ≥ 21,
1
1
√
1
1
n6
n6
1
c + e < 2 kn + √ + n 3 < 2 (n 3 + 1)n + √ 1
+ n 3 < n.
4 k
4 n3 + 1
√
2
89
6.4
Crivo quadrático
Actualmente são usados essencialmente três métodos de factorização, o crivo
quadrático, o crivo do corpo numérico e o método da curva elı́ptica. Nesta
secção iremos descrever o primeiro destes métodos.
A ideia do crivo quadrático é encontrar inteiros x e y tais que
x2 ≡ y 2
mod n
x ̸≡ ±y
mod n.
e
Então d = (x − y, n) é um divisor próprio de n.
Exemplo. Sejam n = 7429, x = 227, e y = 210. Então x2 − y 2 = n e
x − y = 17. Como (n, 17) = 17, temos 17 | n.
O crivo do corpo numérico também usa a ideia anterior, a diferença é na
maneira de determinar x e y. Vejamos como determinar estes inteiros no
crivo quadrático.√
Sejam m = [ n] e f (X) = X 2 − n. A ideia é encontrar k inteiros si , 1 ≤
i ≤ k, tais que cada f (si ) só tenha factores primos pequenos (pertencentes a
um conjunto B), e de tal modo que f (s1 ) · · · f (sk ) seja um quadrado mod n,
i. e. os expoentes de cada primo envolvido são pares. Se k for suficientemente
grande (basta k > #B), os expoentes mod 2 de cada primo, irão formar um
sistema linear com k equações e #B incógnitas, logo é um sistema resolúvel.
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 decomposição de
f (si )). Como v1 +v2 ≡ (0, 0, 0, 0) mod 2, temos que f (1)f (2) é um quadrado
mod 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 têm que verificar uma propriedade que depende
de B. Começamos por definir essa propriedade.
Definição. Dizemos que um inteiro s é B-suave se p | s ⇒ p ∈ B.
90
O conjunto B é formado pelo número −1 e por primos menores que um
valor máximo B0 (mais tarde veremos que não é necessário considerar todos
os primos menores que B0 ). Se B0 for grande, este processo pode demorar
mais que o método de Fermat (podemos necessitar de demasiados s′i s para
garantir a solubilidade do sistema linear). Por outro lado, se B0 for demasiado
pequeno, a propriedade de si ser B−suave pode ser tão especial que podemos
demorar muito a encontrar o primeiro inteiro B − suave depois de m. Foi
demonstrado que o valor óptimo para B0 é
1√
exp(
log n log log n).
2
Este valor de B0 permite que possamos determinar um factor de n em
O(e
√
log n log log n
)
operações bit. Portanto, muito mais rápido que o método de Fermat e suas
variantes.
Em vez de utilizarmos todos os primos menores que B0 (se n for enorme,
podem ser demasiados),
usa-se bases de factores. Queremos encontrar inteiros
√
si perto de m = [ n] tais que f (si ) seja B-suave. Se p | f (si ), então (si )2 ≡ n
mod p, i. e. n é um resı́duo quadrático mod p. Portanto, só nos interessam
primos p ≤ B0 tais que
( )
n
=1
p
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, começa-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 inteiros
0 ≤ t ≤ p−1, tais que t2 ≡ n mod p. Sabemos que há duas soluções, u1 e u2 ,
pois n é um resı́duo quadrático mod p (se p = 2 há uma só solução). Utilizase o algoritmo de Tonelli-Shanks para determinar estas soluções. Então p
divide f (u1 ) e f (u2 ), mas também divide f (ui + kp), para i = 1, 2 e k inteiro
(é desta parte do algoritmo que resulta o nome crivo quadrático). Assim,
começando em ui , divide-se cada f (ui + kp) com ui + kp ∈ S pela maior
potência de p possı́vel, resultado este que passa a substituir f (ui + kp). Fazse o mesmo para os outros primos da base de factores e escolhe-se os valores
que forem iguais a 1. Os ı́ndices destas coordenadas são os nossos si ’s, e para
cada um deles, f (si ) é B-suave.
91
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
25
29
55
83
137
263
f (m + i)
8016
16227
24440
32655
40872
49091
57312
65535
73760
81987
90216
98447
106680
114915
123152
131391
139632
147875
205632
238680
454272
687960
1143072
2227680
2
501
3
167
601
3055
5109
10885
1703
5
611
2177
7
13
17
47
311
131
7013
1791
199
21845
2305
4369
461
27329
11277 1253
257
179
5791
13335
445
38305
889
7661
127
7697
8727
14599
2909
1123
1183
3213
29835
3549
85995
35721
69615
119
1105
1183
3185
49
7735
169
17
221
637
1547
169
13
1
221
Tabela 6.1: O crivo quadrático
92
1
17
1
1
17
1
1
1
√
Exemplo. Seja n = 16843009. Então m = [ n] = 4104. Usando o valor
óptimo 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 como
funciona o crivo. As últimas 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
e
y ≡ 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 factorização do RSA-129 usando o
crivo quadrático. O RSA-129 é um número com 129 dı́gitos com dois factores
primos, um com 64 dı́gitos e o outro com 65. A base de factores para esta
factorização continha 524339 primos. Em 1996, o crivo dos corpos de números
foi utilizado para factorizar o RSA-130. Desde então todos os números RSA
que teem sido factorizados, foram-no usando este último crivo.
93
Capı́tulo 7
Logaritmo Discreto
Como já vimos alguns sistemas criptográficos dependem da complexidade do
problema do logaritmo discreto, neste capı́tulo iremos descrever algoritmos
para resolver este problema. Muitos destes algoritmos são válidos para qualquer inteiro n para o qual (Z∗n , ·) seja um grupo cı́clico, mas iremos somente
considerar grupos cuja ordem seja um primo.
Seja p um primo ı́mpar e g uma raı́z primitiva mod p. Dado um inteiro
b, o problema do logaritmo discreto consiste em encontrar a menor solução
de
b ≡ g x mod p.
(7.1)
7.1
Enumeração
O método mais simples para resolver a equação (7.1) é ir testar sucessivamente x = 0, 1, 2, 3 . . . . A este processo chamamos enumeração.
Exemplo. A menor solução (positiva) de 3 ≡ 5x mod 2017 é x = 1030.
Portanto, usando a enumeração, temos que experimentar 1031 valores!
Em criptografia usa-se soluções x, com x ≥ 2160 , portanto este método é
totalmente impraticável.
94
7.2
Algoritmo passos de bebé passos de gigante
Este algoritmo foi desenvolvido por D. Shanks em 1971 e permite-nos me√
lhorar consideravelmente o algoritmo anterior. Seja m = [ p] e façamos
x = qm + r, com 0 ≤ r < m. O algoritmo passos de bebé passos de gigante
determina q e r. Como g qm+r ≡ b mod p, então
(g m )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), então b ≡ g r mod p e a menor
solução de (7.1) é x = r. Caso não exista tal par, determinamos c = g m
mod p. Em seguida, para cada q = 1, 2, 3, . . . , verificamos se cq mod p é
a primeira coordenada de algum elemento de B. Quando isto acontecer,
obtemos
(g m )q ≡ cq ≡ bg −r mod p
donde x = qm + r é solução de (7.1). Ao cálculo dos elementos cq , chamamos
passos de gigante. Para cada q temos que comparar cq com os elementos de
B.
A solução de 3 ≡ 5x mod 2017 é x = 1030. Usando o método da enumeração temos que efectuar 1029 multiplicações mod 2017. Se usarmos
o algoritmo passos de bebé passos de gigante, obtemos m = 44, r = 18 e
q = 23. Portanto, só necessitamos de 44 multiplicações para os passos de
bebé e de 22 multiplicações para os passos de gigante. Em contrapartida,
para utilizarmos este algoritmo, temos que guardar todos os pares dos passos
de bebé, enquanto que no algoritmo de enumeração, só é necessário guardar
os inteiros g, b e p.
Para o algoritmo da enumeração, o número máximo de multiplicações é
p−1, mas o número mı́nimo pode ser muito pequeno. No algoritmo passos de
√
bebé passos de gigante, temos sempre [ p] + 1 passos de bebé, e no máximo
√
[ p] passos de gigante. Também este algoritmo é impraticável para resolver
problemas concretos de criptoanalise.
95
7.3
Cálculo de ı́ndices
Nesta secção descrevemos o algoritmo cálculo de ı́ndices que está relacionado
com os algoritmos de factorização subexponenciais mencionados no capı́tulo
anterior. Mais uma vez queremos resolver o problema do logaritmo discreto
b ≡ gx
mod p.
Começamos por escolher um majorante B e consideramos a base de factores
F (B) = {q, primo : q ≤ B}. Em seguida, calculamos o logaritmo discreto
dos elementos da base de factores, i. e., para qualquer q ∈ F (B), resolvemos
a congruência
g xq ≡ q mod p.
Depois determinamos um expoente y ∈ {1, 2, . . . , p − 1} tal que bg y mod p
é B-suave e escrevemos
∏
q eq mod p.
bg y ≡
q∈F (B)
Então
bg y ≡
∏
g x q eq ≡ g
∑
q∈F (B)
xq eq
mod p
q∈F (B)
donde
b≡g
∑
q∈F (B)
xq eq −y
mod p.
Portanto, a solução do problema do logaritmo discreto é
∑
xq eq − y mod p − 1.
x≡
q∈F (B)
A determinação do logaritmo discreto dos elementos da base de factores
parece à primeira vista tão difı́cil como resolver o problema do logaritmo
discreto original, mas pode ser efectuada de um modo muito mais simples.
Escolhe-se aleatoriamente z ∈ {1, 2, . . . , p − 1}, tal que g z mod p é B-suave
e escrevemos
∏
gz ≡
q fq,z mod p.
q∈F (B)
A cada vector (fq,z )q∈F (B) chamamos uma relação. Deve-se verificar se cada
nova relação é linearmente dependente das anteriores. Caso seja, esta é
96
eliminada. Precisamos de tantas relações como o número de elementos da
base de factores. Como
∏
∑
gz ≡
g xq fq,z ≡ g q∈F (B) xq fq,z mod p
q∈F (B)
então obtemos a congruência linear
∑
z≡
xq fq,z
mod p − 1.
q∈F (B)
Obtemos assim um sistema linear de congruências (cujas incógnitas são os
xq ), que pode ser resolvido usando métodos de teoria dos números.
Note que se B for suficientemente grande, resolvemos o sistema de linear
de congruências uma única vez e estes xq são válidos 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, então a base de factores é
F (B) = {2, 3, 5, 7, 11}. Agora, escolhendo aleatoriamente z em {1, 2, . . . , p −
1}, obtemos os seguintes números B-suaves:
3 · 11
5 · 7 · 11
27 · 11
32 · 7
26 · 52
=
=
=
=
=
33
385
1408
63
1600
≡
≡
≡
≡
≡
21593
2983
21318
2293
21918
mod
mod
mod
mod
mod
2027
2027
2027
2027
2027.
As relações obtidas são (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 são linearmente independentes. Pelo pequeno teorema de
Fermat, obtemos o seguinte sistema com 5 incógnitas e 5 congruências:
x2 + x 5
x3 + x 4 + x5
7x1 + x5
2x2 + x4
6x1 + 2x3
≡
≡
≡
≡
≡
1593
983
1318
293
1918
mod
mod
mod
mod
mod
2026
2026
2026
2026
2026.
Como g = 2, então x1 = 1. Temos que 2026 = 2 · 1013, assim devemos
resolver as congruências mod 2 e mod 1013 e depois utilizamos o teorema
97
chinês dos restos para obter as soluções
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·2y
mod 2027 seja B-suave. Encontramos
13 · 21397 ≡ 110 = 2 · 5 · 11 mod 2027.
Portanto,
x ≡ 1 + 1969 + 1311 − 1397 ≡ 1884
98
mod 2026.
Capı́tulo 8
Assinaturas digitais
8.1
Introdução
Em documentos em papel utilizam-se assinaturas convencionais, feitas à
mão para especificar a pessoa responsável pelo documento. Estas assinaturas são utilizadas para assinar cartas, levantar dinheiro de um banco, assinar contratos, etc. Uma assinatura digital serve para assinar documentos
electrónicos que são transmitidos através de uma rede de computadores.
Neste capı́tulo iremos estudar várias assinaturas digitais, mas começamos
por observar algumas diferenças fundamentais entre assinaturas digitais e
assinaturas convencionais:
1. Assinatura de um documento: Quando se utiliza uma assinatura
convencional, esta assinatura está fisicamente ligada ao documento que
está assinado. Quando utilizamos uma assinatura digital, esta não está
fisicamente ligada à mensagem, sendo assim necessário que o algoritmo
utilizado deve de alguma maneira ligar a assinatura à mensagem que
queremos assinar.
2. Verificação da assinatura: Numa assinatura convencional, a verificação da assinatura é verificada quando esta é comparada com uma
assinatura autenticada (por exemplo, a assinatura do Bilhete de Identidade, do Cartão do Cidadão ou de um cartão de crédito). Claramente,
este método não é muito seguro, porque é relativamente simples forjar a
assinatura de uma outra pessoa. As assinaturas digitais são verificadas
utilizando um algoritmo de verificação público. Portanto qualquer pessoa pode verificar se a assinatura digital é autentica.
99
Uma assinatura digital consiste de duas componentes: Um algoritmo para
assinar e um algoritmo de verificação. Bob assina a mensagem x utilizando
um algoritmo (secreto) para assinar, sig. A assinatura resultante y = sig(x)
é verificada utilizando um algoritmo de verificação público, ver. Dado o par
(x, y), então ver(x, y) = 1 se a assinatura é autentica e ver(x, y) = 0 se a
assinatura não estiver correcta.
As funções sig e ver devem ser de tempo polinomial e forjar uma assinatura por um oponente deve ser computacionalmente impraticável.
8.2
Assinatura RSA
O sistema criptográfico RSA pode ser utilizado para assinaturas digitais,
como passamos a descrever:
Sejam (na , ea ) e (pa , qa , da ) as chaves pública e privada RSA de Alice,
respectivamente; e (nb , eb ) e (pb , qb , db ) as chaves pública e privada RSA de
Bob, respectivamente.
Suponhamos que a Alice pretende enviar uma mensagem cifrada e assinada a Bob. Dada a mensagem original x, primeiro a Alice assina x utilizando
a sua chave de RSA privada, da , obtendo
y = sigda (x) ≡ xda
mod na .
Em seguida, cifra x e y utilizando a chave pública RSA de Bob, obtendo a
mensagem cifrada z que transmite a Bob. Quando Bob recebe z, ele primeiro
decifra z utilizando a sua chave privada RSA e obtém (x, y). Para certificar
a autenticidade da assinatura y, Bob utiliza a chave pública RSA de Alice
verificando se a seguinte congruência é verdadeira
y ea ≡ x
mod na .
Se Alice cifrar primeiro x, obtendo z, e só depois assinar z, obtendo y e
enviar o par (z, y) a Bob, então Óscar poderá criar a sua assinatura y ′ de z e
substituir 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 Óscar. Note
que nesta situação, Óscar sabendo ou não a mensagem x, consegue sempre
assinar z. Por esta razão é recomendado que se assine sempre a mensagem
antes de a cifrar.
100
8.3
Assinatura ElGamal
A assinatura digital ElGamal foi descrita pela primeira vez em 1985 e foi
desenvolvida especificamente para ser uma assinatura, o que contrasta com
o RSA que pode ser usado como um sistema criptográfico ou como uma
assinatura. Uma modificação desta assinatura deu origem à assinatura digital standard adoptada pelo National Institute of Standards and Technology
(NIST).
Passamos a descrever esta assinatura:
Seja p um primo tal que a resolução computacional do problema do logaritmo discreto em Zp é impraticável. Sejam α uma raiz primitiva de p,
1 < a < p − 1 um valor aleatório e β ≡ αa mod p. Os valores p, α e β
são públicos 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 ser
mantido secreto) e define-se
sigK (x, k) = (γ, δ),
onde
γ ≡ αk
e
mod p
δ ≡ (x − aγ)k −1
mod p − 1.
A função de verificação é dada por
verK (x, γ, δ) = 1 ⇐⇒ β γ γ δ ≡ αx
mod p
Esta verificação 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 quer
assinar uma mensagem x). A verificação é obtida usando somente informação
pública.
Exemplo. Seja p = 467, α = 2 e a = 127. Então β ≡ 2127 ≡ 132 mod 467.
Suponhamos que Bob quer assinar a mensagem x = 100. Primeiro gera o
101
número aleatório k = 213 que é primo com 466 (como tinha de ser). Então
213−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
13229 2951 ≡ 189 mod 467
e
2100 ≡ 189 mod 467.
Portanto, a assinatura é válida.
8.3.1
Forjar assinaturas ElGamal
Vejamos agora a segurança desta assinatura digital. Suponhamos que Olga
pretende forjar uma assinatura para a mensagem x, sem saber a. Se Olga
escolher um valor γ e tentar encontrar o valor δ correspondente, tem que
calcular o logaritmo discreto logγ (αx β −γ ) mod p. Por outro lado, se Olga
escolher δ e tentar encontrar o valor γ correspondente tem que resolver a
congruência
β γ γ δ ≡ αx mod p.
Até agora não foi encontrada uma maneira prática (em termos computacionais) para resolver esta congruência.
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 ninguém descobriu uma maneira de efectuar este cálculo, mas também
ninguém provou que este cálculo não pode ser efectuado.
Se Olga escolher γ e δ e depois tentar descobrir x terá mais uma vez que
calcular o logaritmo discreto logα (β γ γ δ ) mod p. Portanto, Olga não pode
assinar uma mensagem aleatória utilizando este processo.
No entanto, Olga pode assinar uma mensagem aleatória escolhendo γ, δ e
x 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.
Então (γ, δ) é uma assinatura válida para a mensagem x porque
β γ γ δ ≡ β γ (αi β j )−γj
≡ βγ α
−iγj −1
−1
β −γ
mod p
mod p
−iγj −1
≡α
≡ αx
mod p
mod p.
Vejamos outro método para forjar assinaturas em que Olga utiliza uma
mensagem previamente assinada por Bob. Suponhamos que (γ, δ) é uma
assinatura válida para a mensagem x. Consideremos h, i e j inteiros tais que
0 ≤ 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.
Então
β λ λµ ≡ β λ (γ h αi β j )δλ(hγ−jδ)
≡ β λ (β jδ−hγ )
−1
λ(hγ−jδ)−1
≡α
xhλ(hγ−jδ)−1
≡α
λ(hγ−jδ)−1 (xh+iδ)
≡α
x′
α
−1
−1
−1
(β hγ )λ(hγ−jδ) (γ δ )hλ(hγ−jδ) αiδλ(hγ−jδ)
hλ(hγ−jδ)−1
≡ β λ β −λ (β γ γ δ )
mod p
α
iδλ(hγ−jδ)−1
iδλ(hγ−jδ)−1
mod p
mod p
mod p
mod p
mod p.
Portanto, (λ, µ) é uma assinatura válida para x′ .
Ambos estes métodos servem para forjar assinaturas, mas não parecem
permitir que um oponente consiga forjar uma assinatura para uma mensagem
que ele próprio escolha, sem resolver o problema do logaritmo discreto. Assim, estes métodos não parecem ameaçar a segurança da assinatura ElGamal.
103
8.3.2
Falhas de protocolo
Nesta secção vamos descrever processos para quebrar a assinatura ElGamal,
quando esta é utilizada de uma maneira descuidada.
Primeiro, o valor aleatório k usado na assinatura não deve ser revelado,
caso contrário 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 mensagem.
Outra falha na utilização da assinatura ElGamal ocorre quando o mesmo
valor 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.
Então
β γ γ δ1 ≡ αx1 mod p
e
β γ γ δ2 ≡ αx2
Donde
mod p.
αx1 −x2 ≡ γ δ1 −δ2 ≡ αk(δ1 −δ2 )
mod p.
Esta última equação é equivalente a
x1 − x2 ≡ k(δ1 − δ2 ) mod p − 1.
(8.1)
Como δ1 − δ2 pode não ter inverso mod p − 1, não podemos calcular k
imediatamente, mas este problema pode ser ultrapassado se dividirmos todos
os termos pelo máximo divisor comum entre δ1 − δ2 e p − 1: Seja
d = (δ1 − δ2 , p − 1)
então d | (x1 − x2 ). Definimos
x1 − x2
d
δ1 − δ2
′
δ ≡
d
p−1
′
p ≡
.
d
x′ ≡
104
Então, a congruência (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 solução mod p′ correspondem d soluções da congruência (8.1), dadas
por k ≡ x′ δ ′−1 + ip′ mod p − 1, com 0 ≤ i ≤ d − 1. Para determinar a
solução correcta basta verificar quando é que γ ≡ αk mod p.
8.4
DSS
A assinatura digital standard (digital standard signature - DSS) é uma modificação da assinatura ElGamal, adoptada em 1 de Dezembro de 1994 pelo
governo federal dos Estados Unidos da América. Começamos por explicar
porque foi necessário efectuar modificações à assinatura ElGamal e como é
que estas modificações foram conseguidas.
Em muitas situações, uma mensagem é cifrada e decifrada uma única
vez, portanto basta que o sistema criptográfico seja seguro nesta ocasião.
Por outro lado, uma mensagem assinada pode ser um documento legal como
por exemplo um contracto ou um testamento, sendo assim muito provável
que seja necessário verificar a assinatura muitos anos após a mensagem ser
assinada. Por esta razão é necessário tomar mais precauções relativamente à
segurança de uma assinatura do que relativamente à segurança de um sistema
criptográfico. Como a assinatura digital ElGamal não é mais segura que o
problema do logaritmo discreto, temos que usar um primo p grande, com pelo
menos 512 bits, para garantir alguma segurança, sendo sugerido por muitas
pessoas que p deve ter pelo menos 1024 bits, para manter a assinatura segura
por vários anos. Mas para muitas aplicações, várias envolvendo smart cards,
é desejável ter assinaturas mais pequenas. A assinatura digital standard
modifica a assinatura ElGamal de maneira a usar uma assinar uma mensagem
com 160 bits (usando uma assinatura de 320 bits) e onde os cálculos são
efectuados usando um primo com pelo menos 512 bits. A ideia é trabalhar
num subgrupo de Z∗p com ordem 2160 .
A primeira alteração é definir δ da seguinte maneira
δ ≡ (x + aγ)k −1
105
mod p − 1.
A verificação 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 condição anterior para obter
−1
αxδ β γδ
−1
≡γ
mod p.
(8.2)
Se existir um primo q com 160 bits tal que q | p − 1, podemos obter um
elemento α em Z∗p tal que a ordem de α mod p é q. Este elemento pode ser
construı́do a partir de uma raiz primitiva α0 de p, fazendo
p−1
α ≡ α0 q
mod p.
Portanto, no DSS em vez de utilizarmos uma raiz primitiva de p iremos
utilizar um elemento de Z∗p cuja ordem tem 160 bits. Tal como na assinatura
ElGamal, definimos
β ≡ αa mod p
e
γ ≡ αk
mod p,
onde k é gerado aleatoriamente. Então β e γ também têm ordem q. Portanto, os expoentes de α e β em (8.2) podem ser reduzidos mod q. Mas
se reduzirmos γ mod q em (8.2) então todo o lado esquerdo da congruência
tem também 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 β são públicos e a é secreto. Escolhemos 1 ≤ k ≤ q − 1
aleatoriamente e definimos
sig(x, k) = (γ, δ),
onde x ∈ Z∗q ,
γ ≡ (αk
e
mod p) mod q
δ ≡ (x + aγ)k −1
106
mod q.
Para efectuar a verificação, calculamos
e
e1 ≡ xδ −1
mod q
e2 ≡ γδ −1
mod q
ver(x, γ, δ) = 1 ⇐⇒ γ ≡ (αe1 β e2
mod p) mod q.
Precisamos que δ ̸≡ 0 mod q pois precisamos do inverso de δ mod q
para verificar a assinatura. Se Bob obtiver um valor δ ≡ 0 mod q deve
escolher um outro valor para k e calcular novos valores para γ e δ. Note que
a probabilidade de δ ≡ 0 mod q é aproximadamente 2−160 , portanto muito
raramente temos que modificar os valores.
Exemplo. Suponhamos que q = 101 e p = 78q + 1 = 7879. Então 3 é uma
raiz primitiva de p e α ≡ 378 ≡ 170 mod 7879 tem ordem q. Seja a = 75.
Então β ≡ 17075 ≡ 4567 mod 7879. Suponhamos que Bob quer assinar a
mensagem x = 22 e escolhe aleatoriamente k = 50. Então
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 a
assinatura calculamos
δ −1 ≡ 25
e1 ≡ 22 · 25 ≡ 45 mod 101
e2 ≡ 94 · 25 ≡ 27 mod 101.
mod 101
Como
17045 456727
mod 7879 ≡ 2518 ≡ 94 ≡ γ
então a assinatura é válida.
107
mod 101
Quando DSS foi proposto, o comprimento do primo p foi fixado em 512
bits. Após várias crı́ticas, foi permitido ter primos cujo número de bits é
divisı́vel por 64 e que tenham entre 512 e 1024 bits. Em 2000 o número de
bits do primo p foi fixado em 1024 bits. Em 2006 foi sugerido o uso de primos
com 2048 bits para assinaturas cujo tempo de vida se prolongue para além de
2010. Para mais informações consultar os documentos publicados pelo NIST
(National Institute of Standards and Technology).
108
Capı́tulo 9
Funções de sı́ntese
As assinaturas que estudámos no capı́tulo anterior só nos permitem assinar
mensagens pequenas. Por exemplo, se utilizarmos o DSS, uma mensagem
com 160 bits é assinada com uma assinatura de 320 bits. Em geral, precisamos de assinar mensagens muito maiores, e. g. documentos legais. Uma
maneira de resolver este problema é dividir a mensagem em partes e assinar
cada parte. Este processo levanta vários problemas: Uma mensagem enorme
terá uma assinatura (de facto, a união de várias assinaturas) enorme. Outra
desvantagem deste processo é que a integridade da mensagem original é perdida.
A maneira mais utilizada para resolver os problemas descritos é recorrer
a funções hash (ou funções de sı́ntese). Estas funções reduzem a mensagem
original a uma mensagem de tamanho aceitável (e. g. 160 bits no caso do
DSS). Só a mensagem reduzida é que é assinada.
Definição. Seja h uma função de sı́ntese. Temos uma colisão se dadas duas
mensagens x e y, tivermos h(x) = h(y).
Definição. Seja x uma mensagem. Uma função de sı́ntese h é fracamente
livre de colisões se for computacionalmente impraticável encontrar uma mensagem x′ ̸= x tal que h(x) = h(x′ ).
Definição. Uma função de sı́ntese h é fortemente livre de colisões se for
computacionalmente impraticável encontrar duas mensagens x e x′ diferentes
tais que h(x) = h(x′ ).
109
9.1
Ataque do Aniversário
Nesta secção vamos determinar uma condição necessária para a segurança de
funções de sı́ntese que apenas depende do tamanho das mensagens reduzidas.
Esta condição resulta de um método para encontrar colisões conhecido como
o ataque do aniversário e que está relacionado com o famoso paradoxo dos
aniversários. O paradoxo dos aniversários diz que se tivermos um grupo de
23 pessoas então há duas pessoas que nasceram no mesmo dia, com mais
de 0.5 de probabilidade e não é realmente um paradoxo, mas simplesmente
contra-intuitivo.
Seja h : X → Z uma função de sı́ntese, com X e Z finitos e tais que
|X| ≥ 2|Z|. Suponhamos que |X| = m e |Z| = n. Claramente, há pelo
menos n colisões, o problema é como encontrá-las. Uma maneira é escolher
aleatoriamente k elementos x1 , . . . , xk ∈ X distintos, calcular h(xi ), para
1 ≤ i ≤ k e depois determinar se houve colisões. Este processo corresponde a
atirar aleatoriamente k bolas para n caixas e depois verificar se alguma caixa
tem mais de uma bola. Vamos calcular um minorante da probabilidade de
encontrar uma colisão por este método. Começamos por assumir que
|h−1 (z)| ≈
m
,
n
para qualquer z ∈ Z. Esta hipótese é razoável, pois se a função h não
distribuir os elementos de X pelos elementos de Z de maneira aproximadamente igual, então a probabilidade de encontrar colisões aumentará, e nós só
queremos um minorante desta probabilidade.
Sejam z1 , . . . , zk os elementos que vão sendo obtidos através da função de
sı́ntese h. O valor z1 pode ser qualquer, mas a probabilidade de z2 ̸= z1 é
1−1/n, a probabilidade de z3 ̸= z1 e z3 ̸= z2 é 1−2/n, e assim sucessivamente.
Portanto, uma estimativa de que não haja qualquer colisão após k valores é
∏
1
2
k−1
i
(1 − )(1 − ) · · · (1 −
)=
(1 − ).
n
n
n
n
i=1
k−1
A série de Taylor da função exponencial dá-nos a seguinte expansão
e−x = 1 − x +
x2 x3
−
··· ,
2!
3!
o que implica que 1 − x ≈ e−x quando x é pequeno. Então a nossa estimativa
110
para a probabilidade de colisões é
k−1
∏
∏ i
k(k−1)
i
(1 − ) ≈
e− n = e− 2n .
n
i=1
i=1
k−1
Portanto, estimamos a probabilidade de haver pelo menos uma colisão como
sendo
k(k−1)
ϵ = 1 − e− 2n .
Então
k(k−1)
e− 2n ≈ 1 − ϵ
k(k − 1)
≈ log(1 − ϵ)
−
2n
k 2 − k ≈ −2n log(1 − ϵ)
√
donde
k≈
Se tomarmos ϵ = 0.5 obtemos
2n log
1
.
1−ϵ
√
k ≈ 1.177 n.
√
Portanto, se aplicarmos a função de sı́ntese a pouco mais de n elementos
de X obtemos uma colisão 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 aniversário da pessoa x então
1.177 365 ≈ 22.49 e há mais de 0.5 de probabilidade de que se encontre
duas pessoas que comemorem o aniversário no mesmo dia num grupo de pelo
menos 23 pessoas.
Se as mensagens reduzidas após a aplicação de uma função de sı́ntese
tiverem 40 bits então o ataque do aniversário diz-nos que iremos ter uma
colisão com probabilidade 0.5 se efectuarmos aproximadamente 220 (pouco
mais de um milhão) de reduções.
9.2
Funções de sı́ntese comprovadamente seguras
Há dois tipos de funções de sı́ntese: Por um lado temos funções de sı́ntese
baseadas em problemas matemáticos, e portanto a sua segurança resulta
111
de provas matemáticas rigorosas. Estas funções de sı́ntese não são muito
utilizadas na prática devido à sua complexidade e por serem muito lentas. A
estas funções, chamamos funções de sı́ntese comprovadamente seguras. Como
exemplos temos
1. Função de sı́ntese de Chaum-van Heijst-Pfitzmann baseada no problema do logaritmo discreto;
2. VSH (very smooth hash function) baseada no problema de determinar
raı́zes quadradas modulares;
3. ECOH (elliptic curve only hash function) baseada em curvas elı́pticas
e no problema do saco-mochila;
4. FSB (fast syndrome based hash function) baseada em teoria dos códigos
e relacionada com os sistemas criptográficos de McEliece e de Niederreiter;
5. SWIFFT baseada na transformada de Fourier rápida (fast Fourier transform).
A outra categoria de funções de sı́ntese inclui funções que têm como base
não um problema matemático difı́cil mas sim são definidas de uma maneira
ad hoc, onde os bits da mensagem são misturados de modo a obter uma
função de sı́ntese. Pretende-se que sejam difı́ceis de quebrar, mas não há
demonstrações formais deste facto. Como exemplos temos MD4, MD5, MD6,
SHA1, SHA2 e WHIRLPOOL.
O SHA2 está implementado em vários protocolos e aplicações de segurança, como por exemplo TLS, SSL, PGP, SSH, S/MIME e IPsec. Veremos alguns destes protocolos mais tarde. O MD5 é muito utilizado para
armazenar passwords.
O NIST (National Institute of Standards and Technology) criou uma
competição para encontrar uma nova função de sı́ntese para substituir o
SHA2, que se passará a chamar SHA3. Esta competição irá terminar em
2012. As funções ECOH, FSB, SWIFFT e MD6 foram eliminadas na primeira
ronda. As funções finalistas são
1. BLAKE;
2. Grøstl, que usa uma S-box, como o AES;
112
3. JH;
4. Keccak;
5. Skein.
9.2.1
Função de sı́ntese Chaum-van Heijst-Pfitzmann
Nesta secção descrevemos a função de sı́ntese de Chaum, van Heijst e Pfitzmann que é baseada no problema do logaritmo discreto.
Seja q um primo grande tal que 2q + 1 = p é primo (os primos que
verificam esta condição chamam-se primos de Sophie Germain). Sejam α e
β raizes primitivas de p. A função 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́ colisão pode afectar a
esta função de sı́ntese.
Teorema 9.1. Uma colisão da função de sı́ntese de Chaum-van HeijstPfitzmann permite calcular o logaritmo discreto logα β de uma maneira eficiente.
Demonstração: Suponhamos que temos uma colisão
h(x1 , x2 ) = h(x3 , x4 ),
onde (x1 , x2 ) ̸= (x3 , x4 ). Então
ou seja
αx1 β x2 ≡ αx3 β x4
mod p,
αx1 −x3 ≡ β x4 −x2
mod p.
Seja d = (x4 −x2 , p−1). Como p−1 = 2q e q é primo então 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. Então
β ≡ β (x4 −x2 )y ≡ α(x1 −x3 )y
Portanto,
logα β ≡ (x1 − x3 )(x4 − x2 )−1
113
mod p.
mod p − 1.
Em seguida, consideramos d = 2. Como q é ı́mpar, temos (x4 −x2 , q) = 1.
Seja y ≡ (x4 − x2 )−1 mod q. Então (x4 − x2 )y = kq + 1, para algum inteiro
k, donde
β (x4 −x2 )y ≡ β kq+1 ≡ (−1)k β mod p.
Portanto,
logα β ≡ (x1 − x3 )y
mod p − 1
ou
logα β ≡ (x1 − x3 )y + q
mod p − 1,
onde a última congruência resulta de
αq ≡ −1
mod p.
Como é fácil determinar qual daquelas congruências é a correcta, conseguimos
também determinar o logaritmo discreto logα β.
Agora, consideramos d = q. Como 0 ≤ x2 , x4 ≤ q − 1 então q só divide
x4 − x2 se x4 − x2 = 0. Mas se x4 = x2 então p − 1 também divide x4 − x2 .
Portanto, o caso d = q nunca acontece.
Como vimos atrás, se d = p − 1 então 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 não pode
acontecer.
Portanto, só podemos ter dois casos e em cada um deles é possı́vel calcular
o logaritmo discreto de β na base α.
2
Podemos assim concluir que alguém que consiga descobrir colisões para
esta função de sı́ntese, conseguirá calcular um logaritmo discreto considerado
difı́cil.
O teorema anterior mostra que se for computacionalmente impraticável
calcular logα β em Zp então a função de sı́ntese Chaun-van Heijst-Pfitzmann
é fortemente livre de colisões.
114
9.2.2
VSH
Seja n uma chave pública RSA (n = pq). Sejam p1 = 2, p2 = 3, . . . . Seja k,
o comprimento dos blocos, o maior inteiro tal que
k
∏
pi < n.
i=1
Seja m = (m1 , m2 , . . . , ml ) uma mensagem de l bits, com mi ∈ {0, 1} e
assuma-se que l < 2k . Para calcular h(m) procede-se da seguinte maneira:
1. x0 = 1;
2. Seja L = [ kl ], L é o número de blocos.Tome-se mi = 0 para l < i ≤ Lk.
Neste passo estamos a completar a mensagem com zeros.
3. Represente-se l em binário, isto é
l=
k
∑
li 2i−1 ,
i=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
∏
pikj+i
mod n.
i=1
5. Devolva xL+1 .
Esta função de sı́ntese é fortemente resistente a colisões.
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 Perspective, 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 Mathematical 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, Prentice
Hall, 2010.
[9] D. R. Stinson, Cryptography, Theory and Practice, 3rd Edition, CRC
Press, 2006.
116

Criptografia e Segurança

Transcrição

Documentos relacionados

solicitação de registro de minuta, contrato modelo ou padrão

06/06/2015 à 06/06/2015

23 anos tudo para profissionais

Ricardo Primi

Modelo de Impressos

O PRINCÍPIO DE “LOCAL PARA GLOBAL” Hoje a gente vai colocar

CV16-PX-CV28X-1 e X-2_FB-FS-88-XV-1CAA_FB-FS

Baixar - Prefeitura Municipal de Cerro Largo

LEI MUNICIPAL Nº