Embed Size (px)
Citation preview
ÁREA 1 – FACULDADE DE CIÊNCIA E TECNOLOGIA
ENGENHARIA DA COMPUTAÇÃO
DIÊGO PEREIRA DA CONCEIÇÃO
FUNDAMENTOS MATEMÁTICOS PARA GERAÇÃO DE
ALGORITMOS CRIPTOGRÁFICOS
SALVADOR
2011
DIÊGO PEREIRA DA CONCEIÇÃO
FUNDAMENTOS MATEMÁTICOS PARA GERAÇÃO DE
ALGORITMOS CRIPTOGRÁFICOS
Monografia apresentada ao Curso de Engenharia
da Computação da Faculdade AREA1, como
requisito parcial para obtenção do grau de
Bacharel em Engenharia da Computação.
Orientador: Leonardo Alexandre L. Melo, Esp.
SALVADOR
2011
DIÊGO PEREIRA DA CONCEIÇÃO
FUNDAMENTOS MATEMÁTICOS PARA GERAÇÃO DE
ALGORITMOS CRIPTOGRÁFICOS
Monografia apresentada a Área 1 – Faculdade de Ciência e Tecnologia, como
requisito parcial para obtenção do grau de Engenheiro de Computação.
Banca Examinadora
Prof. Esp. Leonardo Alexandre de L. Melo (Orientador)
Profª. MSc. Rosely O. Pestana Bervian
Prof. MSc. Alexandre Silva
Salvador,___de____________de___
Àquele que, em sua sabedoria, criou todas as coisas, Deus.
AGRADECIMENTOS
Agradeço a Deus que concretizou esse sonho e mostrou-me que tudo é
possível àquele que crê. Por toda sabedoria e inteligência, fortaleza e
conhecimento. Ele fez muito mais além daquilo que pedi ou imaginei na minha
vida. A Ele seja toda honra.
A minha mãe, por todo amor e compreensão. Você mostrou que
sacrifícios genuínos nos levam a grandes conquistas. E essa conquista é
nossa.
A minha família, por sempre acreditar em mim. Sem o auxílio de vocês
eu nunca teria chegado tão longe.
A Ivan, Binha, Rafa (prima), Rafael e Vanderlei, meus primos que me
acolheram carinhosamente em seu lar durante todo este tempo fazendo da sua
casa a minha casa. Ivan e Binha, vocês foram como verdadeiros pais pra mim.
A Camile, minha namorada, por compreender e me ajudar durante todo
o período de confecção deste trabalho.
A todos os meus amigos, nos quais encontrei alento para carregar a
carga quando esta começava a pesar e levá-la sozinho se tornava algo
impossível. A Alisson pela motivação em busca do desconhecido, a Lucas por
toda coragem quando precisei e a Vanessa pelo incentivo em perseguir esse
objetivo em meio a todos os obstáculos.
Aos amigos da faculdade, por nos mostrar que unidos sempre chegamos
mais longe. Em especial a Geydison, Luiz, Raimundo, Flávio e Leonardo por
compartilharem o conhecimento, o ânimo e serem como verdadeiros
companheiros nessa árdua jornada. Magaly, Rosana, Dudu, Rafael Valverde,
Ana Nery e Verônica vocês também fazem parte desse alicerce.
Ao meu orientador Leonardo Melo pela confiança no sucesso deste
trabalho.
Enfim, a todos que se sintam dignos de participar desta alegria.
“Em Cristo estão escondidos todos os
tesouros da sabedoria e da ciência”.
Colossenses 2:2,3
RESUMO
Desde tempos remotos o homem tem percebido a importância do sigilo da informação. Com o advento da internet, tornou-se ainda mais necessário a proteção da informação, pois emissor e receptor agora se encontram conectados a uma rede mundial, onde os dados trafegam livremente e vulneráveis a qualquer tipo de ataque. A fim de prover segurança foram criados os chamados mecanismos de segurança, entre os quais se podem destacar a cifragem, assinatura digital, controle de acesso, integridade dos dados, troca de informações de autenticação, certificação, entre outros. A utilização de cifras tornou-se um padrão na comunicação e novas técnicas vem sendo desenvolvidas desde então. Assim, este trabalho visa mostrar como os mais famosos algoritmos criptográficos foram concebidos utilizando-se uma ciência bem antiga: a Matemática.
Palavras-chaves: Criptografia simétrica. Criptografia assimétrica. Chave.
Criptoanálise.
ABSTRACT
Since ancient times the man has realized the importance of confidentiality of information. With the advent of the internet, it has become even more necessary to protect the personal information, because now the sender and receiver are connected to a global network, where data travels freely and vulnerable to any attack. In order to provide security, it has been created so-called security mechanisms, among which we can highlight the encryption, digital signature, access control, data integrity, information exchange, authentication, certification, among others. The use of figures has become a standard in the communication and new techniques have been developed since then. This work aims to show how the most popular cryptographic algorithms are designed using a very old science: mathematics.
Keywords: Symmetric encryption. Asymmetric encryption. Key. Cryptanalysis.
LISTA DE FIGURAS
Figura 1 Citale espartano ................................................................................. 18
Figura 2 Visão geral do processo de criptografia ............................................. 19
Figura 3 Frequência das letras do alfabeto português ..................................... 22
Figura 4 O quadrado de Vigenère .................................................................... 23
Figura 5 Máquina Enigma ............................................................................... 25
Figura 6 Três rotores conectados de maneira a criar um circuito elétrico ....... 25
Figura 7 Cálculo tradicional do mdc ................................................................. 28
Figura 8 Representação geral do algoritmo de criptografia DES ..................... 41
Figura 9 Disposição dos bits em formato matricial ........................................... 42
Figura 10 Permutação Inicial (IP) ..................................................................... 42
Figura 11 Inverso da Permutação Inicial (IP-1) ................................................. 42
Figura 12 Uma iteração do DES ....................................................................... 43
Figura 13 Escolha permutada PC1 .................................................................. 44
Figura 14 Deslocamento linear circular ........................................................... 44
Figura 15 Escolha permutada PC2 .................................................................. 44
Figura 16 Permutação de Expansão E ............................................................ 45
Figura 17 Função de Permutação P ................................................................. 45
Figura 18 Função F .......................................................................................... 46
Figura 19 Definição das oito S-boxes do DES ................................................. 46
Figura 20 Detalhes de uma S-box: troca de 6 bits por 4 bit ............................ 47
Figura 21 Visão geral e completa do DES ....................................................... 48
Figura 22 Inverso do DES ................................................................................ 49
Figura 23 Criptografia com DES triplo .............................................................. 50
Figura 24 Criptografia e decriptografia AES .................................................... 53
Figura 25 Organização do bloco de entrada .................................................... 53
Figura 26 Chave expandida ............................................................................. 54
Figura 27 Transformação ShiftRow .................................................................. 55
Figura 28 S-Box ............................................................................................... 56
Figura 29 S-Box inversa ................................................................................... 56
Figura 30 Expansão de chave do AES ............................................................ 60
Figura 31 Aritmética em modular 7 ................................................................. 63
Figura 32 Função de mão única genérica Yx (mod P). Alice e Bob usam neste
exemplo, em particular, 7x (mod 11) ................................................................ 65
Figura 33 Criptografia de chave assimétrica .................................................... 68
Figura 34 Autenticação usando Criptografia de Chave Pública ....................... 69
Figura 35 Esquema geral do RSA .................................................................... 71
Figura 36 Exemplo do algoritmo RSA .............................................................. 72
LISTA DE TABELAS
Tabela 1 Alguns valores da função totiente de Euler Ø(n) .............................. 35
Tabela 2 Parâmetros do AES ........................................................................... 52
Tabela 3 Comparação entre duas funções de mão dupla e única ................... 64
LISTA DE ABREVIATURAS E SIGLAS
AES Advanced Encryption Standard
ASCII American Standard Code for Information Interchange (Código
Padrão Americano para Troca de Informações)
BITS Binary Digits (Dígitos Binários)
DES Data Encryption Standard
EFF Electronic Frontier Foundation
GF Galois Field (Corpo de Galois)
IBM International Business Machines
MDC Máximo Divisor Comum
MOD Módulo
NBS National Bureau of Standards
NIST National Institute of Standards and Technology
NSA National Security Agency (Agência de Segurança Nacional)
RSA Ronald Rivest, Adi Shamir e Leonard Adleman
TCR Teorema Chinês do Resto
SUMÁRIO
1. INTRODUÇÃO ............................................................................................. 14
1.1 CONTEXTUALIZAÇÃO ........................................................................... 15
1.2 OBJETIVO GERAL ................................................................................. 15
1.3 OBJETIVO ESPECÍFICO ........................................................................ 15
1.4 JUSTIFICATIVA ...................................................................................... 16
1.5 METODOLOGIA ..................................................................................... 16
2. DAS PRIMEIRAS CIFRAS À ENIGMA ........................................................ 17
2.1 ESTEGANOGRAFIA E CRIPTOGRAFIA ................................................ 17
2.1 CIFRA DE CÉSAR .................................................................................. 20
2.2 CRIPTOANÁLISE ................................................................................... 21
2.3 CIFRA DE VIGENÈRE ............................................................................ 22
2.4 CIFRANDO COM MÁQUINAS: A ENIGMA ............................................ 24
3. CONCEITOS MATEMÁTICOS FUNDAMENTAIS ....................................... 27
3.1 ARITMÉTICA MODULAR ...................................................................... 27
3.2 ALGORITMO DE EUCLIDES ................................................................. 28
3.3 ALGORITMO DE EUCLIDES ESTENDIDO ........................................... 30
3.4 NÚMEROS PRIMOS ............................................................................... 31
3.5 TEOREMAS DE FERMAT E EULER ...................................................... 33
3.6 TEOREMA CHINÊS DO RESTO – TCR ................................................. 33
3.7 OPERAÇÕES SOBRE CORPOS FINITOS ............................................ 33
3.7.1 Operações em GF(28) ...................................................................... 37
4. CRIPTOGRAFIA DE CHAVE SECRETA ..................................................... 40
4.1 DATA ENCRYPTION STANDARD – DES .............................................. 40
4.1.1 Permutação Inicial ............................................................................ 42
4.1.2. Uma iteração do DES ...................................................................... 43
4.1.3 Geração das subchaves Kj ............................................................... 44
4.1.4 A função de iteração F ...................................................................... 45
4.1.5 As S-boxes ....................................................................................... 46
4.1.6 Processo de decriptografia do DES .................................................. 48
4.2 ADVANCED ENCRYPTION STANDARD – AES ................................... 51
4.2.1 Esquema geral do Rijndael - AES..................................................... 52
4.2.2 Adição de chave da rodada .............................................................. 54
4.2.3 Deslocamento de linhas .................................................................... 55
4.2.4 Substituição de bytes ........................................................................ 55
4.2.5 Embaralhamento de colunas ............................................................ 58
4.2.6 Expansão de chave do AES ............................................................. 59
5. CRIPTOGRAFIA DE CHAVE PÚBLICA ...................................................... 62
5.1 O ESQUEMA DE DIFFIE-HELLMAN-MERKLE ...................................... 62
5.2 PRINCÍPIOS DE CRIPTOSSISTEMAS DE CHAVE PÚBLICA ............... 67
5.3 ALGORITMO RSA .................................................................................. 69
6. CONCLUSÃO .............................................................................................. 73
REFERÊNCIAS ................................................................................................ 74
14
1. INTRODUÇÃO
À medida que o tempo passa, o sigilo da informação tem assumido um
papel relevante na comunicação. A criptografia tem sido a técnica utilizada para
fornecer um canal seguro entre o emissor e o receptor da mensagem. Por um
lado temos a busca por uma cifra inquebrável a fim de manter a privacidade
das mensagens; por outro, decifradores de códigos interessados em ler o
conteúdo destas mensagens. Essa guerra que perdura por séculos tem levado
a uma corrida do conhecimento em todo o mundo onde a informação é o objeto
de grande valor.
Segundo Singh (2010, p. 12), a codificação de mensagens vai
desempenhar um processo cada vez maior na vida diária. O aumento de
ataques à informação tem crescido com o uso da Internet e a criação de
protocolos e aplicações. Stallings (2010, p. 5) comenta que os algoritmos
criptográficos assumem maior importância na garantia da confidencialidade e
autenticidade. Na chamada Era da Informação, a busca por mecanismos de
segurança tem forçado as redes de computadores a defenderem-se de
invasores através da criptografia e diversos protocolos.
Em virtude da possibilidade existente da quebra dos algoritmos
criptográficos (apesar de sua alta eficácia) faz-se necessário uma pesquisa
contínua na criação de cifras inquebráveis e cuja implementação não gere
custos elevados. A grande questão é que a criptografia quântica (até o
presente momento indecifrável) ainda não se tornou uma tecnologia prática.
Por muitos anos os chamados quebradores de códigos estiveram um
passo a frente daqueles que desejavam ocultar as mensagens. Com o
desenvolvimento intelectual e tecnológico, essa disputa tem atingido
proporções inimagináveis e a segurança da informação se tornou prioridade.
Esse trabalho está estruturado de forma a apresentar ao leitor como a
matemática tem contribuído significativamente à criptografia. Vale ressaltar que
há muito mais algoritmos além dos que foram apresentados aqui e não há
preocupação na implementação destes em quaisquer linguagem de
15
programação, entretanto, espera-se que o conteúdo abordado seja o suficiente
para uma boa compreensão do assunto. O capítulo 2 apresenta os conceitos
básicos da criptografia e as primeiras técnicas mais relevantes. O capítulo 3
apresenta os principais conceitos da matemática utilizados na elaboração dos
algoritmos abordados. O capítulo 4 aborda dois algoritmos que utilizam uma
única chave (secreta) para cifrar e decifrar determinada mensagem. O capítulo
5 apresenta um esquema alternativo na codificação de mensagem através do
uso de chaves públicas na garantia de maior segurança na comunicação. Por
fim, o capítulo 6 conclui o trabalho com algumas observações relevantes entre
a matemática e a criptografia.
1.1 CONTEXTUALIZAÇÃO
Este trabalho surgiu do desejo de compreender melhor como os
algoritmos criptográficos fornecem um canal seguro na comunicação em redes
de computadores. Além de identificar os diversos conceitos utilizados na área
de segurança da informação referente à Criptografia, busca especificamente o
conhecimento prático da matemática na formulação de alguns algoritmos.
1.2 OBJETIVO GERAL
Compreender conceitos e termos usados na Criptografia e de que
maneira determinadas áreas da Matemática são aplicadas aos algoritmos
criptográficos a fim de prover segurança na informação.
1.3 OBJETIVO ESPECÍFICO
Apresentar um histórico da Criptografia até a Era dos Computadores.
Diferenciar Criptografia de Chave Secreta da Criptografia de Chave
Pública.
Entender conceitos matemáticos utilizados na Criptografia
16
Provar como a matemática é capaz de prover segurança na troca de
mensagens.
1.4 JUSTIFICATIVA
A Matemática proporcionou um avanço bastante significativo na
evolução da Criptografia. Portanto, faz-se necessário entender a estrutura dos
algoritmos criptográficos e os aspectos matemáticos envolvidos a fim de
compreender a importância da Matemática aplicada à Criptografia.
1.5 METODOLOGIA
A pesquisa experimental será a metodologia utilizada. A Criptografia
será o objeto de estudo e a Matemática será a variável que será aplicada a fim
de analisar a influência e o comportamento sobre esse objeto.
17
2. DAS PRIMEIRAS CIFRAS À ENIGMA
2.1 ESTEGANOGRAFIA E CRIPTOGRAFIA
A necessidade do homem em manter suas comunicações secretas tem
seus registros desde séculos antes de Cristo. Os antigos chineses escreviam
suas mensagens em seda fina, e estas eram amassadas até assumirem a
forma de uma pequena bola e depois cobertas por cera. O mensageiro engolia
a bola de cera e entregava a mensagem com segurança ao destinatário e sem
intercepções (Singh, 2010).
A essa técnica de ocultar a mensagem, dá-se o nome de esteganografia,
termo derivado das palavras gregas steganos (coberto) e graphein (escrever).
Não há qualquer alteração no conteúdo da mensagem, apenas uma forma de
evitar que a mesma seja interceptada e lida por terceiros. Existem diversas
técnicas no uso da esteganografia, por exemplo: marcação de caractere, tinta
invisível, entre outras (Singh, 2010).
Apesar de utilizada por muito tempo, a esteganografia possui uma
fraqueza fundamental: caso a mensagem seja interceptada, o conteúdo da
comunicação, até então secreta, fica comprometida.
Enquanto muitos buscavam uma forma de ocultar a mensagem, outros
desenvolviam paralelamente a criptografia, do grego kriptos (oculto). O objetivo
era esconder o significado da mensagem. O transmissor e o receptor da
mensagem combinavam previamente a maneira que iriam misturar o texto de
forma a torná-lo incompreensível para terceiros. Ao receber a mensagem
codificada, o receptor reverteria o processo para obter a mensagem original.
Por ser uma ciência mais ampla, a criptografia pode ser dividida em
duas áreas: transposição e substituição. Na transposição, as letras do texto
original são rearranjadas de forma sistemática ou aleatória. De maneira mais
simples, a palavra criptografia poderia ser permutada da seguinte forma:
patcrragifoi. Entretanto, à medida que aumenta o número de letras, torna-se
18
dificultoso o processo de decodificação e até mesmo impossível se o processo
de mistura não for conhecido.
Para cifrar a frase Criptografando seus dados na rede utilizando o
sistema de transposição chamado “cerca de ferrovias”, alterna-se cada letra da
mensagem dispondo-as em duas linhas distintas. Para conseguir o texto
cifrado, basta transcrever de forma alternada uma letra da primeira linha,
seguida por outra da segunda linha:
Mensagem: CRIPTOGRAFANDO SEUS DADOS NA REDE
1ª linha: C I T G A A D S U D D S A E E
2ª linha: R P O R F N O E S A O N R D
Texto cifrado: CITGAADSUDDSAEERPORFNOESAONRD
Fazendo o processo inverso, o receptor pode recuperar a mensagem
facilmente. É possível ainda a utilização de três linhas para aumentar a
complexidade do texto cifrado.
Figura 1. Citale espartano
Fonte: (http://www.numaboa.com.br/criptografia/transposicoes/322-bastao-de-licurgo, 2002)
Outra forma de transposição bastante utilizada por espartanos militares
foi o citale também conhecido como Bastão de Licurgo, apresentado na figura
1. O receptor enrolava uma tira de couro em volta do bastão e escrevia a
mensagem. Após desenrolar a tira, o que surgia era uma fila de caracteres
ilegíveis. Em muitos casos, o mensageiro utilizava-se da esteganografia ao
usar a tira como cinto, com as letras voltadas para dentro. Para o destinatário
decifrar a mensagem bastava apenas ter um citale de mesmo diâmetro usado
pelo remetente.
19
Na substituição, as letras do texto original são substituídas por outras
letras, números ou símbolos previamente definidos. Uma das formas
recomendadas é emparelhar as letras do alfabeto de forma aleatória e
substituir o par correspondente no texto cifrado. Por exemplo:
A B F G I K M P Q T W Y Z
L R C N U D X E H J O S V
Dessa forma, o texto original Lançado ao vento poderia ser escrito
como ALGFLKW LW ZPGJW.
Figura 2. Visão geral do processo de criptografia
Fonte: SINGH (2010)
De forma geral, um esquema criptográfico envolve o uso de uma chave
(uma palavra) e um algoritmo (conjunto de operações matemáticas) que o
emissor utiliza para cifrar (tornar ilegível) o texto original. O receptor recebe o
texto cifrado e usa o mesmo algoritmo e chave para decifrar (tornar legível) a
mensagem. A figura 2 ilustra esse processo.
20
2.1 CIFRA DE CÉSAR
A cifra de César, como ficou bastante conhecida, é uma das técnicas de
substituição mais antiga e simples. Consiste em substituir cada letra do
alfabeto original por outra letra do alfabeto cifrado com posição fixa de três
casas a frente. Sendo assim, tem-se:
Alfabeto original
a b c d e f g h i j k l m n o p q r s t u v w x y z
Alfabeto cifrado:
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Para o texto: protegendo a rede
Texto cifrado: SURWHJHQGR D UHGH
Atribuindo um valor numérico a cada letra no alfabeto original iniciando
com 0 a letra a, 1 a letra b e assim por diante, é possível expressar a cifra de
César pela seguinte equação
C = E(k,p) = (p + k) mod 26 (1)
na qual:
p = posição da letra do texto claro;
k = deslocamento entre 1 a 25;
E(k,p) é a relação entre p e k;
C = letra cifrada.
Para a cifra de César, o valor de k sempre será igual a três. Para
decriptografar basta fazer
p = D(k,C) = (C – k) mod 26 (2)
21
na qual:
D(k,C) é a relação entre k e C.
O cálculo envolvendo aritmética modular (mod) será explicado no
Capítulo 3. Por enquanto, apenas considere a Cifra de César como sendo
circular, ou seja, após a letra z retorna-se a letra a.
Entretanto, a cifra de César pode ser facilmente quebrada devido a
limitação de apenas 25 combinações possíveis. Alguém que testasse todas as
possibilidades acabaria decifrando a mensagem sem realizar muito esforço. A
essa técnica dá-se o nome de “força bruta” (Singh, 2010).
2.2 CRIPTOANÁLISE
Os árabes os primeiros a conseguir decifrar mensagens criptografadas
sem a utilização do ataque por força bruta. Eles criaram a chamada
criptoanálise, a ciência de recuperar a chave utilizada no criptossistema (Singh,
2010).
Devido ao vasto conhecimento na área de linguística, os árabes
analisaram as características do próprio alfabeto e perceberam
comportamentos interessantes. Eles verificaram que, de um modo geral,
algumas letras aparecem com maior frequência em relação às outras. Com
isso, eles puderam explorar as vulnerabilidades das mensagens e decifrá-las
através da análise de frequência das letras.
Realizando um ensaio estatístico nas letras do alfabeto português com
base em vários textos extraídos de livros e periódicos, nota-se que é possível
determinar uma frequência quase fixa dessas letras.
22
Figura 3. Frequência das letras do alfabeto português
Fonte: (http://www.numaboa.com.br/criptografia/criptoanalise/310-frequencia-portugues, 2005)
7
Na figura 3, a letra que mais aparece no nosso alfabeto é a letra a com
14,63%, seguida da letra e com 12,57% e letra o com 10,73%. Com posse
dessas informações, um criptoanalista aplica a frequência de letras no texto
cifrado e faz uma relação entre essa frequência e a do texto original. Após a
análise, caso uma letra qualquer tenha um fator estatístico de 8%, por exemplo,
é bem provável que ela seja a substituta para a letra s do alfabeto original.
2.3 CIFRA DE VIGENÈRE
A cifra de Vigenère consiste em utilizar 26 cifras de César, com
deslocamento de 1 a 26.
23
Figura 4. O quadrado de Vigenère
Fonte: STALLINGS (2008)
Inicialmente é montado o quadrado de Vigenère, conforme apresentado
na Figura 4. No topo aparece o alfabeto que representa as letras do texto
original seguido por 26 alfabetos cifrados deslocados de uma letra com relação
ao alfabeto anterior. Sendo assim, é possível cifrar qualquer texto com um ou
mais dos alfabetos cifrados disponíveis.
Para criptografar uma mensagem, é necessário o uso de uma chave que
seja tão longa quanto o texto que se deseja cifrar. Escolhida a palavra-chave,
ela é escrita acima do texto original e repetida até que cada letra da mensagem
tenha um par correspondente. Singh (2010) ilustra um exemplo em que a frase
divert troops to east ridge combinada com a palavra-chave WHITE é
codificada assim:
Palavra-chave
W H I T E W H I T E W H I T E W H I T E W H I
Texto-original
d i v e r T t r o o p s t O E a s t r i d g e
Texto cifrado
Z P D X V P A Z H S L Z B H I W Z B K M Z N M
24
A cifragem é simples. Para cifrar a primeira letra, d, observamos que a
letra W é a correspondente no alfabeto cifrado, ou seja, neste primeiro
momento será utilizada a linha 22 do quadrado de Vigenère. Basta fazer a
intersecção da letra d com a fileira que inicia com W, o que resulta na letra Z.
Portanto, a letra d no texto original será representada por Z no texto cifrado.
Esse processo é repetido com cada letra da mensagem até que esta seja
codificada completamente (Singh, 2010).
A cifra de Vigenère oferece maior segurança com relação as cifras
monoalfabéticas já que ela não pode ser decifrada pela análise de frequência,
nem por ataque por força bruta devido ao grande número de chaves, o
equivalente a 2626 (6.15611958 x 1036 possiblidades).
2.4 CIFRANDO COM MÁQUINAS: A ENIGMA
A primeira máquina criptográfica é o disco de cifras. Foi criada por Leon
Alberti e utilizava dois discos concêntricos com um alfabeto gravado em cada
um deles. Com isso, era possível cifrar mensagens utilizando o descolamento
simples de César. Para aumentar a complexidade, Alberti aprimorou o disco de
forma a gerar cifras polialfabéticas com a utilização de uma palavra chave, o
equivalente a uma versão mecanizada da cifra de Vigenère. (Singh, 2010)
Apesar de ter sido bastante utilizada devido a facilidade e agilidade em
manusear, o disco de cifras ainda não era indecifrável. Foi Arthur Scherbius,
engenheiro eletricista, que criou o mais conhecido sistema de cifragem da
história: Enigma, uma versão elétrica do disco de cifras. (Singh, 2010)
A Enigma baseava-se no princípio de máquinas de rotor1. Era formada
basicamente por três elementos: um teclado para entrada de texto, três rotores
e um painel de iluminação contendo as letras de A a Z que se acendiam a
cada tecla pressionada.
1 Máquina que consiste em um conjunto de cilindros rotativos independentes, através dos quais podem
fluir pulsos elétricos.
25
Figura 5. Máquina Enigma
Fonte: (http://pt.wikipedia.org/wiki/Enigma_%28m%C3%A1quina%29, 2011)
Figura 6. Três rotores conectados de maneira a criar um circuito elétrico
Fonte: (http://pt.wikipedia.org/wiki/Enigma_%28m%C3%A1quina%29, 2011)
A figura 5 fornece uma visão geral da Enigma. Os três discos
misturadores eram conectados entre si por fiação elétrica e no interior de cada
um destes as 26 letras do alfabeto, conforme a figura 6.
A cifragem dá-se da seguinte forma: a cada tecla pressionada pelo
operador, o primeiro cilindro desloca uma posição enquanto os outros dois
permanecem estáticos. Após completar uma volta completa, o segundo cilindro
é deslocado uma casa e o terceiro ainda permanece em sua posição inicial.
Quando o segundo cilindro então completar 26 voltas, o terceiro cilindro
desloca de sua primeira posição. Por um longo tempo a Enigma foi
considerada indecifrável porque ela fornecia 26 x 26 x 26, ou seja, 17.576
combinações possíveis dos misturadores.
26
Scherbius aprimorou a enigma inserindo mais elementos a fim de
aumentar a segurança da cifra. Primeiro, ele tornou possível a remoção e troca
da posição dos misturadores, o que aumenta o número de combinações
multiplicada por um fator de 6. Segundo, ele introduziu um painel de tomadas
para conectar o teclado ao primeiro rotor; o painel permitia a troca de seis
pares de letras fornecendo 100.391.791.500 modos distintos de se conectar.
Desta forma, a Enigma possuía um número total de chaves correspondente a
17.576 x 6 x 100.391.791.500 = 10.000.000.000.000.000
Os poloneses foram os primeiros a decifrar a terrível Enigma. O
matemático Marian Rejewski recebeu o devido mérito por conseguir
transformar em texto claro as mensagens interceptadas. Alguns anos depois, a
Inglaterra reuniu cerca de sete mil pessoas das mais diversas profissões em
uma central chamada Bletchley Park aonde mensagens alemãs chegavam
diariamente para serem decifradas. Dentre todos, Alan Turing destacou-se e
conseguiu criar um mecanismo eletro-mecânico com capacidade de decifrar os
textos ilegíveis em pouco menos de uma hora. (Singh, 2010)
A utilização de máquinas criptográficas durante a Segunda Guerra
Mundial proporcionou o desenvolvimento dos computadores. O processo de
cifragem se daria por meio da utilização de números em vez de letras. O
computador lida com um sistema binário, ou seja, sequências de zero e um
conhecidos como bits. A criptografia cresce potencialmente devido ao grande
avanço tecnológico que ocorreu desde então até a chegada da internet.
27
3. CONCEITOS MATEMÁTICOS FUNDAMENTAIS
A seguir serão apresentados os conceitos necessários para o
entendimento de alguns cálculos utilizados durante o processo criptográfico de
determinados algoritmos. O conteúdo será o abordado de uma forma aplicada
as necessidades do tema em questão, portanto, alguns elementos da Teoria
dos Números ficarão de fora deste Capítulo.
3.1 ARITMÉTICA MODULAR
Dado qualquer inteiro n positivo e qualquer inteiro a positivo, ao dividir a
por n, obtém-se o quociente q e resto r. De forma geral é possível expressar da
seguinte forma:
a = qn + r 0 ≤ r < |n|; q = [a/n] (3)
Veja os dois exemplos abaixo:
a = 11 ; n = 7; q = 1; r = 4; 11 = 1 x 7 + 4;
a = -11; n = 7; q = -2 r = 3; -11 = (-2) x 7 + 3;
Define-se a mod n como sendo o resto r da divisão de a por n. O inteiro
n é chamado módulo.
11 mod 7 = 4; -11 mod 7 = 4
Dois inteiros a e b são ditos congruentes módulo n, se (a mod n) = (b
mod n). Isso é o mesmo que a ≡ b (mod n). O símbolo “≡” e o uso dos
parênteses em “(mod n)” indicam equivalência de dois binários.
73 ≡ 4 (mod 23); 21 ≡ – 9 (mod 10)
Se a e b são dois números inteiros equivalentes mod n, então são
verdadeiras as propriedades:
28
(a + b) mod n = (a mod n) + (b mod n)
(a x b) mod n = (a mod n) x (b mod n)
3.2 ALGORITMO DE EUCLIDES
O algoritmo euclidiano é um procedimento utilizado para encontrar o
máximo divisor comum entre dois inteiros positivos (mdc). Consiste
basicamente nos seguintes passos:
1. Divida A por B;
2. O valor de B passa a ser o valor de A e o resto R passa a ser B.
3. O algoritmo termina quando o resto R for zero.
Figura 7. Cálculo tradicional do mdc
Fonte: http://professormarcello.com/index.php?option=com_content&task=
view&id=694&Itemid=47 (2010)
A figura 7 ilustra como é realizado o cálculo do mdc na forma mais
tradicional.
Sabe-se que o resto da divisão entre dois inteiros pode ser expresso
através do módulo, logo:
mdc(a, b) = mdc(b, a mod b) (4)
O mdc(a, b) é sempre um valor inteiro positivo para quaisquer valores de
a e b. Portanto, mdc(a, b) = mdc(|a|, |b|) o que permite ao algoritmo euclidiano
considerar que a > b > 0. Abaixo segue um pseudocódigo:
29
O algoritmo possui uma sequência finita garantindo que em algum
momento o resto r será zero. Stallings (2008) ilustra um exemplo:
30
3.3 ALGORITMO DE EUCLIDES ESTENDIDO
Quando os números a e b são relativamente primos, além de calcular o
mdc(a, b), o algoritmo euclidiano pode ser estendido de forma a encontrar o
inverso multiplicativo de b de modo que bb-1 = 1 mod a. O algoritmo satisfaz a
seguinte condição:
ax + by = mdc(a, b) (5)
sendo, x e y dois números inteiros.
Pelo algoritmo de Euclides, o mdc(396, 13) = (61 X 13) – (2 x 396), pois:
13 = 396 x 0 + 13
396 = 30 x 13 + 6 mdc(396, 13)
13 = 6 x 2 + 1 mdc(13, 6)
6 = 1 x 6 + 0 mdc(6, 1)
Logo, o mdc(396, 13) = 1. O algoritmo estendido de Euclides leva em
conta os restos diferentes de zero encontrados nas divisões. Pode ser
expresso da seguinte maneira:
13 = (1 x 13) - (0 x 396) (6)
13 = (1 x 13)
6 = (1 x 396) - (30 x 13) ... em (6) diz que 13 = (1 x 13) (7)
6 = (1 x 396) - (30 x (1 x 13))
6 = (1 x 396) - (30 x 13)
1 = (1 x 13) - (2 x 6) ... em (7) diz que 6 = (1 x 396) - (30 x 13) (8)
1 = (1 x 13) - 2 x ((1 x 396) - (30 x 13))
1 = (1 x 13) - (2 x 396) + (60 x 13)
1 = (61 x 13) - (2 x 396)
31
O número 61 é o inverso multiplicativo de 13. Aplicando o algoritmo
estendido na criptografia de chave pública, o número inverso é representado
por d, pois d e-1 mod (n).
3.4 NÚMEROS PRIMOS
Um número inteiro p > 0 é considerado um número primo se e somente
se seus únicos divisores forem 1 e o próprio p. O conjunto dos números primos
é infinito e a medida que se avança, a quantidade de primos diminuem.
Terada (2011) diz que a probabilidade de um inteiro n ser primo é em
torno de 1 / ln (n). Essa probabilidade é corolário da Teoria de Números Primos
e afirma que se π(x) denota o número de primos ≤ x, então
= 1
Um teorema fundamental da aritmética diz que qualquer número inteiro
pode ser representado pela multiplicação de um ou mais números primos. A
quantidade de vezes que determinado número aparece é indicado com os
expoentes. Não é fácil determinar os fatores primos de um número grande e é
essa característica que permite ao algoritmo RSA confidencialidade da chave
privada.
91 = 7 x 13
3600 = 24 x 32 x 52
11011 = 7 x 112 x 13
Existe um teorema para testar se um número é primo ou não. Não há
um meio fácil de fazer isso, mas Miller e Rabin propuseram um algoritmo que
gera um número que não é necessariamente primo, mas possui grandes
chances probabilísticas de ser primo (Stallings, 2008).
Considere que qualquer número ímpar n pode ser escrito como
32
n – 1 = 2kqcom k > 0, q ímpar (9)
Ao fazer (n – 1), tem-se um número inteiro par. Em seguida, divida (n –
1) por 2 até que o resultado q seja um valor ímpar, gerando um total de k
divisões. Stallings (2008) mostra duas propriedades necessárias para a
compreensão do algoritmo de Miller-Rabin. A primeira propriedade descrita diz
que a2 mod p = 1 se e somente se a mod p = 1 para p primo e a < p.
A segunda propriedade é expressa da seguinte forma: Seja p um
número primo maior que 2, então é verdade que p – 1 = 2kq, com k > 0, q
ímpar. Considere um inteiro a no intervalo 1 < a < p – 1. Então uma das
seguintes propriedades é verdadeira:
1. aq mod p = 1 ou aq 1 (mod p).
2. Existe algum número j no intervalo (1 ≤ j ≤ k) tal que a(2j – 1)q mod p = –1
mod p = p – 1 ou a(2j – 1)q –1 (mod p).
O pseudocódigo a seguir mostra como verificar a primalidade de
determinado número. Usando um candidato n como entrada e tendo
conclusivo como resultado mostra que o número não é primo; caso o retorno
seja inconclusivo n pode ou não ser primo.
TESTE (n)
1. Encontre inteiros k, q, com k > 0, q ímpar, de modo que (n – 1 = 2kq);
2. Selecione um inteiro aleatórios a, 1 < a < n – 1;
3. Se aq mod n = 1 então return (“inconclusivo”);
4. para j = 0 até k – 1 faça
5. Se mod n n – 1 então return (“inconclusivo”);
6. return (“composto”).
33
Stallings (2008) continua com um exemplo:
Tome como exemplo o número primo n = 29. Temos (n – 1) = 28 = 22(7) = 2kq.
Primeiro, vamos testar a = 10. Calculamos 107 mod 29 = 17, que não é 1 nem
28, de modo que o teste continua. O próximo cálculo descobre que (107)2 mod
29 = 28, e o teste inconclusivo, ou seja, 29 pode ser primo. Teste novamente
com a = 2. Tem-se os seguintes cálculos: 27 mod 29 = 12; 214 mod 29 = 28; e o
teste novamente retorna inconclusivo. Se o teste for realizado para todos os
inteiros a no intervalo de 1 a 28, obtém-se o mesmo resultado inconclusivo, que
é compatível com n sendo um número primo.
3.5 TEOREMAS DE FERMAT E EULER
Esses dois teoremas desempenham papel importantíssimo na
criptografia.
Teorema de Fermat
O Teorema de Fermat diz que: Se p é primo e a é um inteiro não
divisível por p, então:
ap-1 ≡ 1 ( mod p ) (10)
Considerando que a não seja relativamente primo de p, é possível
escrever a mesma equação anterior como:
ap ≡ a (mod p) (11)
p = 5, a = 3 ap = 35 = 243 ≡ 3(mod 5) = a(mod 5)
p = 5, a = 10 ap = 105 = 100000 ≡ 10(mod 5) = 0(mod 5) = a(mod p)
Este teorema é utilizado para calcular o resto da divisão quando o valor
do módulo é um número primo.
34
Calcular 364 mod 31
Inicialmente, o número 64 pode ser decomposto como 64 = 30 x 2 + 4.
Aplicando o Teorema de Fermat para a = 3 e p = 31
330 ≡ 1 (mod 31)
Então,
364 ≡ (330)2 x 34 ≡ 1 x 81 ≡ 19 (mod 31)
Função Totiente de Euler
A função Totiente de Euler é escrita como (n) e é definida como a
quantidade de inteiros positivos menores que n e relativamente primos de n.
Por convenção, (1) = 1.
Determine (37) e (35).
Como 37 é primo, consequentemente todos os números positivos de 1 a 36
farão parte do resultado. Assim, (37) = 36. Para determinar (35), lista-se
todos os inteiros positivos que 35 são relativamente primos dele:
1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18,
19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34
Existem 24 números na lista, de modo que (35) = 24.
É notável que para um número primo p, (p) = p – 1. Considerando dois
números primos p e q, com p ≠ q e n o resultado da multiplicação n = pq,
(n) = (pq) = (p) x (q) = (p – 1) x (q – 1) (12)
35
Tabela 1. Alguns valores da função tociente de Euler (n)
Fonte: STALLINGS (2008)
Teorema de Euler
O teorema de Euler (também conhecido como o Teorema de Fermat-
Euler) afirma que, se a e n são números relativamente primos, então:
≡ 1 (mod n) (13)
a = 3; n = 10; (10) = 4 = 34 = 81≡ 1 (mod 10) = 1 (mod n)
a = 2; n = 11; (11) = 10 = 210 = 1024≡ 1 (mod 11) = 1 (mod n)
Assim como o Teorema de Fermat, uma forma alternativa de expressar
o teorema de Euler é:
≡ a (mod n) (14)
3.6 TEOREMA CHINÊS DO RESTO – TCR
O matemático chinês Sun-Tsu descobriu como calcular inteiros N que ao
serem divididos por 3, 5, 7 respectivamente resultem em 2, 3, 2. A solução é N
36
= 23. De fato, todos os inteiros expressos por 23 + 105k para qualquer k fazem
parte dessa solução.
Segundo o Teorema Chinês do Resto (TCR), k inteiros, m1, m2,...mk,
relativamente primos entre si, é possível representar um inteiro N
N = n1 mod m1, N = n2 mod m2,...N = nk mod mk (15)
da seguinte forma:
N mod (m1 x m2 x ...mk) (16)
Assim, o inteiro 25 pode ser representado como (4 mod 7, 3 mod 11) ou
25 mod (7 x 11).
Terada (2010) diz que é fácil representar (15) a partir de (16): basta
dividir N por cada mj e obter o resto. Entretanto, obter (16) a partir de (15) não
é um caminho fácil e é disso que trata o TCR.
Tendo N = a mod A, N = b mod B, deseja-se obter N mod (AB). Como A
e B são relativamente primos, é possível calcular o inverso multiplicativo de
forma que a equação se torne verdadeira:
A’A + B’B = 1 (17)
Portanto, A‟ = A-1 mod B e B‟ = B-1 mod A. Multiplicando (17) por N tem-
se:
NA‟A + NB‟B = N (18)
É possível ainda escrever N = a mod A como N = a + rA para qualquer r,
e N = b mod B como N = b + tB para algum t. Substituindo N em (4), obtém-se:
N = (b + tB)A‟A + (a + rA)B‟B (19)
Aplicando mod (AB) em (5) chega-se a:
N = (bA’A + aB’B) mod (AB) (20)
Considere o exemplo a seguir como um teste de validade de (20):
37
a = 4, A = 7, b = 3, B = 11
A‟ = 7-1 mod 11 = 8
B‟ = 11-1 mod 7 = 2
Então (bA’A + aB’B) mod (AB) = (3 x 8 x 7 + 4 x 2 x 11) mod (77) = 25.
O RSA usa n = qr na geração do par de chaves. Tendo xp mod q e xp
mod r aplica-se o TCR para calcular xp mod n.
3.7 OPERAÇÕES SOBRE CORPOS FINITOS
Stallings (2008) define um corpo como um conjunto de elementos com
operações binárias de adição, subtração, multiplicação e divisão sem sair do
conjunto. Esse conjunto pode ser finito ou infinito. A criptografia se interessa
apenas pelos corpos finitos.
É possível definir a ordem de um corpo finito como uma potência pn,
onde p é um número primo e n é um inteiro positivo. A notação é usada como
GF(pn); GF é a sigla de Galois Field (Stallings, 2008).
3.7.1 Operações em GF(28)
O Advanced Encryption Standard (AES) utiliza a aritmética no corpo
finito GF(28), ou seja, é utilizado um polinômio na forma b7 x7+ b6 x
6 + b5 x5 + b4
x4 + b3 x3 + b2 x
2 + b1 x + b0, onde (b7b6b5b4b3b2b1b0) são os bits do byte B. A
seguir será explicado as operações sobre esse corpo:
Soma
É feito um XOR bit a bit. O símbolo é usado para indicar essa
operação. Para valores de entrada iguais a saída é 0 e para valores diferentes
é sempre 1.
38
A B Saída
0 0 0
0 1 1
1 0 1
1 1 0
Assim: 11011100 10001110 = 01010010.
Multiplicação
Inicialmente a multiplicação entre os polinômios é feita na aritmética
polinomial comum. Cada termo é distribuído por todos os demais termos do
outro polinômio. O resultado é submetido ao módulo do polinômio irredutível
de grau 8, o AES usa o m(x)= x8 + x4 + x3 + x + 1 ou (11Bh). Stallings (2008)
explica que um polinômio f(x) sobre um corpo F é chamado de irredutível se e
somente se f(x) não puder ser expresso como um produto de dois polinômios,
ambos sobre F, e ambos de grau menor que o de f(x). Isto o caracteriza como
um polinômio primo.
Exemplo: Calcular 53h * 83h.
53h = 01010011 e 83h = 10000011
Representando os valores binários em funções, tem-se:
f(x) = x6 + x4 + x2 + x + 1 e g(x) = x7 + x + 1
f(x) x g(x) = x13 + x11 + x9 + x8 + x7 +
x7 + x5 + x3 + x2 + x +
x6 + x4 + x2 + x + 1
= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1
Aplicando o módulo pelo polinômio irredutível:
x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 mod x8 + x4 + x3 + x + 1 = x7 + x6 + 1 (21)
39
Quando a multiplicação se dá entre um polinômio e uma
constante existe uma técnica simples de ser implementada. Observe a
igualdade:
x8 mod m(x) = [ m(x) – x8 ] = ( x4 + x3 + x +1 ) (22)
onde m(x) = x8 + x4 + x3 + x + 1, que é o corpo finito usado no AES.
Agora considere um polinômio em GF(2n) na forma f(x) = b7x7 + b6x
6 +
+ b5x5 + b4x
4 + b3x3 + b2x
2 + b1x + b0. Em seguida, multiplique por x e terá:
x f(x) = (b7x8 + b6x
7 + b5x6 + b4x
5 + b3x4 + b2x
3 + b1x2 + b0x) mod m(x) (23)
Se b7 = 0, o polinômio terá um grau menor que 8, o que significa que ele
se encontra na forma reduzida dispensando quaisquer cálculos adicionais. Se
b7 = 1, então é necessário a redução módulo m(x)
x f(x) = (b6x7 + b5x
6 + b4x5 + b3x
4 + b2x3 + b1x
2 + b0x) + (x4 + x3 + x +1) (24)
Dessa forma, o resultado da multiplicação x f(x), na qual x
corresponde a constante 02h :
Se b7 = 0 (b6b5b4b3b2b1b00) (25)
Se b7 = 1 (b6b5b4b3b2b1b00) (00011011) (26)
Exemplo: Calcular 57h x 13h
Inicialmente pode-se dizer que 13h = 01h + 02h + 10h. Então:
57h x 02h = 01010111 x 02h = 10101110 (AEh)
57h x 04h = 57h x 02h x 02h = (AEh) x 02h = 01011100 00011011 = 01000111 (47h)
57h x 08h = 47h x 02h = 01000111 x 02h = 10001110 (8Eh)
57h x 10h = 8Eh x 02h= 10001110 x 02h = 00011100 00011011 = 00000111 (07h)
Juntando os cálculos intermediários tem-se:
57h x 13h = 57h x (01h + 02h + 10h) = 57h + AEh + 07h = FEh.
40
4. CRIPTOGRAFIA DE CHAVE SECRETA
Como o próprio nome sugere, esse tipo de criptografia exige a utilização
de uma chave que permaneça em segredo entre as partes que se comunicam.
Também é conhecida como criptografia de chave simétrica porque a mesma
chave que se usa para cifrar a mensagem é usada para decifrá-la.
Um grande problema se torna evidente: a distribuição das chaves.
Pense na seguinte situação: Alice deseja enviar uma mensagem confidencial
para Bob; entretanto, eles necessitam obter uma cópia da mesma chave. Eles
não podem simplesmente enviar a chave pelo canal de comunicação porque
uma terceira pessoa pode estar “na escuta da linha” a fim de fazer uma
interceptação. Como eles podem então trocar mensagens de forma segura?
Apesar de muitos acreditarem na insolubilidade do problema, uma
equipe apresentou uma solução brilhante em meados da década de 1970
criando um sistema de cifragem que parecia desafiar toda a lógica. Esta
descoberta tem sido considerada a maior conquista da criptografia desde a
invenção das cifras monoalfabéticas (utilização de apenas um único alfabeto).
(Singh, 2010).
4.1 DATA ENCRYPTION STANDARD – DES
Em 1973 o National Bureau of Standards (NBS) solicitou propostas para
a criação de uma cifra com os seguintes critérios:
possuir um elevado nível de segurança com uma chave de tamanho
pequeno e que realizasse a cifragem e decifragem;
ser compreensível;
a segurança não deve depender da confidencialidade do algoritmo ;
ser adaptável e econômico ;
ser eficaz e exportável.
A IBM propôs o algoritmo Lucifer com um tamanho de chave igual a 128
bits desenvolvido por Horst Feistel, porém a National Security Agency (NSA)
41
receosa de não conseguir decodificar esse novo padrão de cifras limitou o
tamanho da chave a 56 bits. Foi em 23 de novembro de 1976 que o DES (Data
Encryption Standard), versão de 56 bits do Lucifer, foi adotado como cifra
oficial americana.
Figura 8. Representação geral do algoritmo de criptografia DES
Fonte: STALLINGS (2008)
O DES é composto por três componentes: uma entrada de texto legível,
uma chave e uma saída de texto cifrado. No esquema geral do algoritmo DES
mostrado na figura 8, a entrada é um bloco de 64 bits e a chave tem 56 bits
ditos “úteis” durante o processo criptográfico, pois os 8 bits restantes são
usados como bits de paridade, a fim de verificar a integridade da chave. O
resultado desse processo é uma saída de 64 bits de texto cifrado.
Inicialmente o texto cifrado é submetido a uma Permutação Inicial (IP) e
dividido em dois blocos de 32 bits cada. Em seguida, ocorrem 16 iterações com
subchaves distintas. Durante essas rodadas são utilizadas funções de
permutação e deslocamento linear para gerar as chaves subsequentes. Ao final
42
dessas iterações as duas metades do texto são trocadas entre si e o resultado
é submetido ao Inverso da Permutação Inicial (IP-1) gerando um texto ilegível
de 64 bits como saída.
4.1.1 Permutação Inicial
Ao receber um bloco de 64 bits como entrada, estes ficam dispostos em
um formato de matriz como ilustra a Figura 9:
Figura 9. Disposição dos bits em formato matricial
Fonte: Adaptado de Stallings (2008)
Mi corresponde a um dígito binário.
As figuras 10 e 11 ilustram as permutações que ocorrem no início e final
respectivamente durante o processo de cifragem do texto. Assumindo que cada
43
bit ocupa uma posição inicial como mostrado anteriormente, após serem
permutados, o 58º bit do texto original passará a ser o 1º bit, o 50º ocupará a 2ª
posição e assim as permutações ocorrem conforme a Figura 9.
Segundo Terada (2011), as duas permutações não acrescentam valor
criptográfico e são irrelevantes para qualquer criptoanálise que venha ser
aplicada ao DES.
4.1.2. Uma iteração do DES
A entrada de 64 bits é dividida igualmente em duas metades de 32 bits,
como mostra a Figura 12.
Figura 12. Uma iteração do DES
Fonte: Adaptado de Terada (2011)
Em seguida, aplica-se a função F (será detalhada posteriormente) no
bloco da direita (Rj), onde j indica o número da rodada. O resultado dessa
operação é submetido a um XOR com a metade do bloco da esquerda (Lj). A
saída resultante torna-se a nova metade da direita (Rj+1). Neste ponto, Rj passa
a ser a nova metade da esquerda (Lj+1).
44
4.1.3 Geração das subchaves Kj
A chave inicial K tem um comprimento de 56 bits que passam por uma
permutação PCI, vide Figura 13, e, em seguida, são divididos em dois blocos
de 28 bits cada. É aplicado um deslocamento circular Lj para a esquerda em
cada metade conforme Figura 14. Após passar por uma Permutação e
Contração PC2, como mostra a Figura 15, os 56 bits são reduzidos para 48 bits
gerando a primeira subchave K1.
Figura 13. Escolha Permutada PC1
Fonte: (STALLINGS, 2008)
Figura 14. Deslocamento Linear Circular
Fonte: (STALLINGS, 2008)
Figura 15. Escolha Permutada PC2
Fonte: (STALLINGS, 2008)
45
Para gerar as suchaves posteriores (K2, K3, ... K16) tomam-se os blocos
antes de sofrerem a Permutação PC2 para serem as novas entradas.
4.1.4 A função de iteração F
Após a divisão do bloco de entrada, a metade da direita Rj sofre uma
Expansão e Permutação E, conforme a Figura 16, expandindo o número deste
sub-bloco de 32 bits para 48 bits. O resultado dessa operação é submetido a
uma operação XOR com a subchave Kj de 48 bits.
Figura 16. Permutação de Expansão E
Fonte: STALLINGS (2008)
Em seguida, os 48 bits resultantes passam por substituições definidas
pelos oito S-boxes. No final desse processo, os bits são “contraídos” para 32
bits e sofrem uma última permutação P, como ilustra a Figura 17.
Figura 17. Função de Permutação P
Fonte: (STALLINGS, 2008)
A Figura 18 ilustra o bloco da função F.
46
Figura 18. Função F
Fonte: STALLINGS (2008)
4.1.5 As S-boxes
Essa substituição é constituída por 8 S-boxes que recebem 6 bits de
entrada e geram 4 bits de saída. A Figura 19 apresenta a definição das 4
primeiras S-boxes do DES.
Figura 19. Definição das 4 primeiras S-boxes do DES
Fonte: STALLINGS (2008)
47
Figura 20 Detalhes de uma S-box: troca de 6 bits por 4 bit
Fonte: Adaptado de Terada (2011)
Segundo Terada (2011), a substituição ocorre da seguinte forma:
1. Dos 6 bits de b1b2b3b4b5b6 os dois bits da extremidade definem o índice
de linha na tabela, o que pode resultar em um valor entre 0 e 3. No
exemplo ilustrado da Figura 20, o valor (10) na base 2 corresponde a 2
na base decimal.
2. Os bits b2b3b4b5 definem o índice de coluna. Como são 4 bits, tem-se um
valor situado entre 0 e 15 (1111 é o valor máximo para 4 bits) para um
total de 16 colunas na tabela.
Dessa forma, um mapeamento ocorre para cada grupo de 6 bits de
entrada gerando valores já definidos para uma saída de 32 bits no total. Cada
S-box é única e possui valores em posições específicas.
48
Figura 21 Visão geral e completa do DES
Fonte: (Adaptado de (TERADA, 2011))
A Figura 21 apresenta uma visão geral do DES com detalhes da entrada
do bloco de 64 bits e da chave de 56 bits. A função F mostra a interação entre
as duas partes compondo o processo completo.
4.1.6 Processo de decriptografia do DES
O processo de decriptografia consiste em realizar o caminho inverso da
criptografia. Por isso, esse método também é conhecido criptografia de chave
simétrica porque se utiliza a mesma chave para cifrar e decifrar a mensagem.
49
Figura 22. Inverso do DES
Fonte: Adaptado de Terada (2011)
Sendo assim, considere a Figura 22 como o processo de inversão do DES,
onde se tem:
1. A entrada de texto cifrado de 64 bits que passam por uma Permutação
Inicial IP e são divididos em duas metades trocadas.
2. São realizadas 16 iterações utilizando as 16 chaves começando pela
K16, K15, ...K1.
50
3. Após o processo anterior os bits são obtidos com metades ainda
trocadas. Assim como na criptografia, ocorre uma nova troca entre as
metades e o resultado dessa operação é submetido ao Inverso da
Permutação Inicial IP-1. A saída é o texto legível de 64 bits.
Há também o S-DES que é uma versão simplificada do DES para fins
didáticos. Ele possui redução na quantidade de bits do bloco de entrada (8 bits)
e da chave (10 bits), e apenas duas rodadas.
Devido a alta vulnerabilidade do DES ao ataque de força bruta, foram
realizadas melhorias para dificultar a decriptografia. Como alternativa, foi
desenvolvido o 3DES, DES triplo, com três chaves (Stallings, 2008). Ele possui
uma chave com tamanho de 168 bits e pode ser definido pela função:
C = E( K3, D ( K2 ,E ( K1 ,P ) ) )
na qual:
E = função de Criptografia (Encryption);
D = função de Decriptografia (Decryption).
A compatibilidade com o DES é mantida fazendo-se K3 = K2 ou K1 = K2.
O 3DES é muito resistente à criptoanálise, entretanto é relativamente lento
quando executado em software.
Figura 23. Criptografia com DES triplo
Fonte: Adaptado de Stallings (2008)
A Figura 23 ilustra cada um dos estágios do 3DES.
51
4.2 ADVANCED ENCRYPTION STANDARD – AES
Em julho de 1998, a Electronic Frontier Foundation (EFF) provou ter
quebrado o DES com o uso de uma máquina que eles chamaram “decifradora
de DES”. A EFF publicou os detalhes para que qualquer pessoa montasse a
sua própria máquina. Ela tinha um custo total de quase 250 mil dólares e
obteve um ataque com sucesso em menos de três dias. Tendo em vista a
tendência do barateamento do hardware e o aumento das velocidades de
processamento, ficou perceptível que o DES estava se tornando inútil
(Stallings, 2008).
Apesar da segurança do 3DES, ele não se mostrava um candidato para
ocupar o lugar do DES. Em vista disso, em 1997 o National Institute of
Standards and Technology (NIST) propôs mundialmente uma alternativa para
um novo AES com os seguintes requisitos:
1. Cifra de bloco simétrica tendo como entrada um bloco de 128 bits.
2. A chave deveria ter suporte para tamanho de 128, 192 e 256 bits.
3. Segurança igual ou superior ao Triple-DES além de uma melhor
eficiência.
4. Implementação de forma segura e eficiente em hardware e software
numa grande variedade de plataformas e aplicações.
5. Simplicidade de projeto.
Em uma primeira rodada de avaliação, 15 algoritmos propostos foram aceitos. Uma segunda rodada estreitou a competição para 5 algoritmos. O NIST completou o processo de avaliação e publicou um padrão final (FIPS PUB 197) em novembro de 2001. O NIST selecionou o Rijndael para o AES como o algoritmo AES proposto. Os dois pesquisadores que desenvolveram e enviaram o Rijndael para o AES são criptógrafos belgas: o Dr. Joan Daemen e Dr. Vincent Rijmen (STALLINGS, 2008, p. 92)
52
4.2.1 Esquema geral do Rijndael - AES
Antes de iniciar com o esquema geral do AES faz-se necessário
ressaltar a possibilidade do algoritmo em usar tamanhos diferentes para a
chave (128, 192 ou 256 bits) e o bloco de entrada (limitado até 128 bits).
Tabela 2. Parâmetros do AES
Fonte: STALLINGS (2008)
A Tabela 2 estabelece uma relação de parâmetros entre os
componentes do algoritmo.
Considere o bloco de entrada e a chave, ambos, com tamanho igual a
128 bits cada um. O AES possui apenas quatro funções que são utilizadas
durante as 10 rodadas: AddRoundKey, ShiftRows, SubBytes, e MixColumns.
Para criptografar e decriptografar, primeiramente usa-se a função
AddRoundKey (este passo não conta como uma rodada), seguido por nove
rodadas, onde cada uma delas aplica as quatro funções no bloco, e por fim,
uma rodada utilizando novamente as funções exceto MixColumns.
53
Figura 24. Criptografia e decriptografia AES
Fonte: STALLINGS (2008)
A Figura 24 ilustra os processos de criptografia e decriptografia.
Inicialmente o bloco é representado em forma matricial organizando os
bits de entrada por colunas.
Figura 25. Organização do bloco de entrada
Fonte: STALLINGS (2008)
54
Como mostra a Figura 25, a matriz tem dimensão 4x4 onde cada
elemento representa um byte e são inseridos seguindo a ordem das colunas e
não das linhas, como se faz tradicionalmente na leitura de matrizes.
Figura 26. Chave expandida
Fonte: STALLINGS (2008)
A representação matricial é a mesma para a chave, mas ao ser
expandida para gerar as demais chaves ela passa a ser representada na forma
vetorial, como ilustra a Figura 26. O vetor de words é formado por 44 words de
quatro bytes cada.
4.2.2 Adição de chave da rodada
A adição de chave da rodada (AddRoundKey) é uma operação básica e
simples do AES. De maneira clara, os 128 bits de entrada são submetidos a
um XOR bit a bit com a chave da rodada. Como pode ser visto, é possível
aplicar essa função em nível de coluna entre os 4 bytes das duas matrizes. Os
valores estão no sistema de numeração hexadecimal.
55
4.2.3 Deslocamento de linhas
O deslocamento de linhas (ShiftRows) faz uma transformação na
organização dos bytes deslocando-os de forma circular sempre para a
esquerda de acordo a linha na qual se encontram.
Figura 27 Transformação ShiftRow
Fonte: (STALLINGS, 2008)
Como ilustra a figura 27, a primeira linha permanece inalterada, a
segunda sofre deslocamento de um byte, a terceira de dois bytes e a quarta de
três bytes.
4.2.4 Substituição de bytes
Essa operação consiste no mapeamento dos bytes da matriz para novos
bytes baseado na S-Box da Figura 28. A matriz é composta por valores
hexadecimais, tem dimensão 16 x 16 e nela é possível combinar quaisquer
valores de 8 bits, o que resulta em 256 possibilidades distintas.
56
Figura 28. S-Box
Fonte: STALLINGS (2008)
Figura 29. S-Box inversa
Fonte: STALLINGS (2008)
Os 4 bits da esquerda servem como índice de linha enquanto os 4 bits
da direita indicam o índice da coluna. Assim, o byte 3Ah é permutado para o
byte cuja linha é 3 e coluna A, obtendo-se 80h. A notação usada para valores
hexadecimais será XXh, onde X pode ser um valor entre 0 e 9, A e F.
57
Segundo Terada (2011, p. 92) a operação SubBytes “trata-se de uma
transformação não-linear para tornar o Rijndael forte contra ataques
criptoanalíticos conhecidos como o Diferencial e o Linear”. Não é do escopo
desse trabalho detalhar sobre esse dois tipos de ataques.
Para uma melhor compreensão segue um exemplo completo da função
SubBytes:
Para reverter a transformação usa-se a S-Box inversa da Figura 29.
Como no exemplo anterior, a entrada 3Ah tem como saída 80h, e a entrada
80h na S-Box inversa gera como saída 3Ah.
A S-box é construída da seguinte forma:
1. Encontre o inverso multiplicativo de cada byte no corpo finito GF(28). O
valor 00h é mapeado para si mesmo.
2. Aplique a seguinte transformação nos 8 bits (b7, b6, b5, b4, b3, b2, b1, b0)
de cada byte da S-box:
b’i = bi b(i+4) mod 8 b(i+5) mod 8 b(i+6) mod 8 b(i+7) mod 8 ci
onde 0 i 8 e ci é o i-ésimo bit do byte c cujo valor é 63h (01100011).
O índice 7 corresponde ao bit mais significativo. A representação em
forma matricial é:
EA 04 65 85
83 45 5D 96
5C 33 98 B0
F0 2D AD C5
87 F2 4D 97
EC 6E 4C 90
4A C3 46 E7
8C D8 95 A6
58
4.2.5 Embaralhamento de colunas
Essa função consiste no mapeamento dos bytes de cada coluna para
um novo valor como resultado da combinação linear de todas as colunas.
=
Desta forma, é possível expressar a transformação MixColumns sobre
uma única coluna como:
Veja como fica a matriz de bytes após ser submetida a MixColumns:
É importante lembrar que as operações ocorrem em GF(28). Assim, a
adição é a operação XOR bit a bit e a multiplicação de um valor por 02h é
definida pelas equações (25) e (26).
Para s‟0,0, tem-se que:
s‟0,0 = (02h • 87h) (03h • 6Eh) 46h A6h
02h • 87h = (0000 1110) (0001 1011) = (0001 0101)
03h • 6Eh = 6Eh (02h • 6Eh) = (0110 1110) (1101 1100) = (1011 0010).
87 F2 4D 97
6E 4C 90 EC
46 E7 4A C3
A6 8C D8 95
47 40 A3 4C
37 D4 70 9F
94 E4 3A 42
ED A5 A6 BC
59
Por fim,
02h • 87h = 0001 0101
03h • 6Eh = 1011 0010
46h = 0100 0110
A6h = 1010 0110
0100 0111 47h
4.2.6 Expansão de chave do AES
A chave de 128 bits é organizada em um vetor linear de 4 words cada
uma com 16 bytes. Após a expansão tem-se um total de 44 words (176 bytes);
assim é possível utilizar uma chave de 4 words para as 10 rodadas do AES,
incluindo o estágio AddRoundKey. O pseudocódigo descreve o processo de
expansão:
KeyExpansion ( byte key[16], word w[44] )
{
word temp
for ( i = 0; i < 4; i++ ) {
w[ i ] = ( key[ 4 * i ], key[ 4 * i + 1 ], key[ 4 * i + 2 ], key[ 4 * i + 3] );
}
for ( i = 4; i < 44; i++ ) {
temp = w[ i – 1 ];
if ( i mod 4 = 0 )
temp = SubWord( RotWord( temp )) Rcon[ i / 4 ];
w[ i ] = w[ i – 4 ] temp;
}
}
60
Figura 30. Expansão de chave do AES
Fonte: STALLINGS (2008)
Como ilustra a Figura 30, os 16 bytes da chave são mapeados para
quatro words. A primeira coluna corresponde a w0, a segunda a w1 e assim
sucessivamente. Analisando cuidadosamente a figura, nota-se que w[i]
depende de w[ i – 1 ] e w[ i – 4 ]. A operação realizada é um XOR com um
diferencial na word que tiver uma posição múltipla de 4. O símbolo g é usado
para indicar a operação mais complexa realizado nessas words específicas.
Ela é composta pelas sub-funções:
1. Deslocamento circular de um byte à esquerda. RotWord transforma a
word de entrada [b0, b1, b2, b3] em [b1, b2, b3, b0].
2. SubWord faz uso da S-box para substituir cada byte da word de entrada.
3. O resultado das etapas acima são submetidos a um XOR com uma
constante de rodada, denominada Rcon[j].
Stallings (2008) diz que a constante de rodada é definida por Rcon[j] =
(RC[j], 0, 0, 0), com (RC[1] = 1, RC[j] = 2 • RC[ j - 1] ) e com multiplicação
definida sobre o corpo GF(28). Os valores de RC[j] em hexadecimal são
61
J 1 2 3 4 5 6 7 8 9 10
RC[j] 01 02 04 08 10 20 40 80 1B 36
RCon realiza um XOR apenas com os bytes mais à esquerda pois os
demais valores da word são sempre 0. Assim, para RC[4] tem-se Rcon[4] =
08000000.
Para uma melhor compreensão, considere o exemplo a seguir:
Chave da rodada 8 : EA D2 73 B5 8D BA D2 31 2B F5 60 7F 8D 29 2F
Para calcular a chave da rodada 9 são aplicada as funções descritas
anteriormente:
i(decimal) temp Após
RotWord
Após
SubWord
Rcon (9) Após XOR
com Rcon
w[i - 4] w[i] = temp
w[ i – 4 ]
36 7F8D292F 8D292F7F 5DA515D2 1B000000 46A515D2 EAD27321 AC7766F3
na qual: i é a posição da word no vetor, no caso w[36].
62
5. CRIPTOGRAFIA DE CHAVE PÚBLICA
O conceito de criptografia de chave pública surgiu da necessidade de
solucionar dois problemas da criptografia de chave secreta: a distribuição de
chaves e as “assinaturas digitais”.
Como mencionado no Capítulo 4, o grande gargalo da criptografia
simétrica era fazer com que os usuários trocassem a chave de forma secreta.
Pensando nisso, Whitfield Diffie (matemático formado pelo MIT) iniciou estudos
visando buscar uma forma alternativa de criptografia, algo que revolucionasse
o mundo criptográfico. O resultado de suas pesquisas juntamente com Martin
Hellman e Ralph Merkle resultaram na criptografia de chave assimétrica (Singh,
2010).
Esse novo tipo de cifragem utiliza duas chaves: uma chave pública, de
conhecimento de todos e uma chave privada, exclusiva do proprietário. A
primeira é usada, normalmente, para criptografar o texto claro, enquanto que a
outra é usada para decriptografar. Por isso, esse tipo de criptografia é
considerada como assimétrica porque chaves diferentes são usadas para cifrar
e decifrar a mesma mensagem.
A criptografia de chave simétrica é baseada apenas em permutações e
substituições, mas a criptografia de chave pública utiliza funções matemáticas.
De fato, “o desenvolvimento da criptografia de chave pública é a maior e talvez
a única verdadeira revolução na história da criptografia.” (STALLINGS, 2008).
O RSA (Rivest, Shamir, Adleman) é o um dos principais algoritmos de
chave pública e tem grande aceitação desde a sua publicação em 1978 pelos
pesquisadores do MIT Ron Rivest, Adi Shamir e Leonard Adleman.
5.1 O ESQUEMA DE DIFFIE-HELLMAN-MERKLE
Segundo Singh (2010), Diffie e Hellman concentraram sua pesquisa nas
funções matemáticas. Entenda como função qualquer operação matemática
que transforma um número em outro número. Assim, “triplicar” é uma função
63
que transforma o número 5 em 15. As cifragens feitas por computador também
podem serem vistas como funções, pois transformam um número (texto
original) em outro (texto cifrado).
Eles buscaram uma função de mão única, ou seja, que fosse de difícil
reversão. A função de “triplicar“ é de mão dupla porque pode ser facilmente
revertida; se um número multiplicado por 3 resultou em 15, então o número
original é obviamente o 5. Diffie e Hellman pensaram em situações do cotidiano
para ilustrar exemplos de funções de mão única e mão dupla. O ato de acender
uma lâmpada é um exemplo de mão dupla porque ao pressionar novamente o
interruptor o estado original da lâmpada (desligada) é restaurado.
Entretanto, o interesse de Diffie e Hellman eram as funções de mão
única. Tomando ainda como exemplo atividades do dia-a-dia, considere o ato
de quebrar um ovo. É fácil quebrá-lo, mas impossível restaurá-lo ao seu estado
original. Ou ainda a mistura de duas tintas de cor azul e amarela para produzir
tinta verde, contudo é impossível desfazer a mistura para recuperar qualquer
uma das cores. Nessa linha de raciocínio, eles passaram a estudar a aritmética
modular.
Figura 31. Aritmética em modular 7
Fonte: Adaptado de Singh (2010)
A Figura 31 mostra um relógio para o cálculo de valores em módulo 7.
Para calcular 2 + 3 posicione-se no número 2 e avance 3 casas obtendo o 5.
Para calcular 2 + 6, comece no 2 e avance 6 casas para obter 1 como
resultado.
2 + 3 = 5 (mod 7) e 2 + 6 = 1 (mod 7)
64
Isso é uma simples analogia do que os matemáticos realmente fazem.
Primeiro faça o cálculo usando a aritmética normal e obtenha y. Em seguida,
para saber o resultado em (mod x), divida y por x e anote o resto. Então o resto
é a resposta em (mod x). Para calcular 12 x 8 (mod 15), faça:
12 x 8 = 96
96 dividido por 15 = 6, resto 6
12 x 8 = 6 (mod 15)
Para perceber a complexidade de reversão da aritmética modular, faça
uma comparação com uma função reversível. Considere a função f(x) = 3x. Se
o resultado dado for 81, é fácil deduzir que a resposta para x é 4, pois 34 = 81.
Apenas com alguns palpites é possível encontrar o resultado. Caso fosse
sugerido o número 6 como resposta teria-se 36 = 729, o que leva a entender
que o palpite está além do valor correto de x.
Agora, considere que te seja pedido o valor de x para 3x (mod 7) = 1. Se
o palpite inicial for 5, tem-se 35 (mod 7) = 5 que é um resultado alto para o que
se deseja. Logicamente, tenta-se um valor menor para x. Mas certamente isso
seria inútil porque a resposta verdadeira para x é 6. A tabela 3 mostra que a
função 3x (mod 7) não tem uma sequência lógica de resultados como 3x.
Tabela 3 Comparação entre duas funções de mão dupla e única
X 1 2 3 4 5 6
3x 3 9 27 81 243 729
3x (mod 7) 3 2 6 4 5 1
Fonte: Adaptado de Singh (2010)
Imagine a construção da tabela para a função 453x (mod 21.997). Seria
muito dificultoso calcular um valor de x para um resultado 5.787. Veja que ao
65
escolher x é fácil calcular a função e obter 5.787, mas seria necessário horas
para construir uma tabela como a Tabela 3 e encontrar x.
Depois de dois anos, Hellman chegou a conclusão do uso de uma
função de mão única na forma Yx (mod P). Alice e Bob2 escolhem um valor
para Y e P com uma única restrição de Y ser menor do que P. Não há
problema se Eva ouvir a conversação mesmo que eles usem uma linha
telefônica para trocar essa informação porque as mesmas não secretas.
Figura 32. Função de mão única genérica Yx (mod P). Alice e Bob usam neste
exemplo, em particular, 7x (mod 11)
Alice Bob
Fase 1 Alice escolhe um número,
digamos 3, e o mantém em
segredo. Chame o número de
A.
Bob escolhe um número,
digamos 6, e o mantém em
segredo. Chame o número de
B.
Fase 2 Alice introduz o 3 na função de
mão única e o resultado de
7A(mod 11): 73(mod 11) =
343(mod 11) = 2
Bob introduz o 6 na função
de mão única e o resultado
de 7B(mod 11): 76(mod 11) =
117.649(mod 11) = 4
Fase 3 Alice chama o resultado de
seus cálculos de alfa e envia
seu resultado, 2, para Bob.
Bob chama o resultado de
seus cálculos de beta e envia
seu resultado, 4, para Alice.
A troca Normalmente este seria um momento crucial porque Alice e
Bob estão trocando informações, e portanto esta é uma
oportunidade para Eva escutar e descobrir os detalhes da
informação transmitida. Contudo, Eva pode ouvir sem
comprometer a segurança final do sistema. Alice e Bob podem
usar a mesma linha telefônica através da qual escolheram os
valores de Y e P, e Eva pode interceptar esses números que
estão sendo trocados, ou seja, 2 e 4. Contudo estes números
não são a chave, e por isso não importa que Eva os conheça.
2 Alice, Bob e Eva são personagens clássicos da criptografia (Singh, 2010).
66
Fase 4 Alice pega o resultado de Bob
e calcula a solução de βA
(mod 11): 43 (mod 11) = 64
(mod 11) = 9
Bob pega o resultado de
Alice e calcula a solução de
αB (mod 11): 26 (mod 11) = 64
(mod 11) = 9
A chave
Miraculosamente Alice e Bob terminaram com o mesmo
número 9. Esta é a chave!
Fonte: Adaptado de Singh (2011)
Os passos seguintes são descritos na Figura 32. Neste ponto, Alice e
Bob podem usar o número 9 como chave para cifrar uma mensagem através
do DES, por exemplo.
Analisando cada passo descrito na Figura 32 é possível notar que Alice
e Bob conseguiram trocar informações e obter uma chave secreta. Mas como
ter certeza que Eva não conseguirá calcular a chave através dos valores
conhecidos de Y e P?
Como Eva não conhece os valores de A e B, ela terá que calcular A
através de alfa como resultado de A na função 7x (mod 11) ou calcular B
através de beta como resultado de B na função 7x (mod 11). Contudo, essa é
uma função de mão única, o que torna esse processo de reversão difícil para
Eva, principalmente se os números forem muito grandes.
Singh (2010) traz uma analogia do esquema de Hellman para a geração
da chave secreta entre Alice e Bob. Presuma que Alice, Bob e Eva tenham um
vaso de três litros com um litro de tinta amarela, cada um. Alice e Bob
acrescentam um litro de sua cor secreta ao seu próprio vaso. Alice pode usar
um tom de vermelho enquanto Bob pode colocar verde. Eles enviam seus
vasos um para o outro. Finalmente Alice pega a mistura de Bob e acrescenta
um litro de sua própria cor secreta. Simultaneamente Bob pega o vaso de Alice
e acrescenta sua cor secreta. Ao final da mistura, Alice e Bob possuem a
mesma cor nos vasos porque ambos possuem as cores amarelo, vermelho e
verde. Entretanto, eles não têm conhecimento da cor secreta que cada um
67
usou. Quanto a Eva, ela pode ter interceptado um dos vasos após a primeira
mistura, mas não consegue descobrir qual a cor secreta usada para gerar tal
cor porque a mistura de tintas é uma função de mão única.
O problema da distribuição de chaves estava parcialmente resolvido.
Parcialmente porque era necessário que Alice e Bob estivessem “juntos” no
momento da geração da chave. Imagine que Alice deseja enviar uma
mensagem para Bob, mas ele se encontra dormindo. Alice ficaria
impossibilitada de entregar a mensagem porque antes é necessário que haja
uma troca mútua de informações para gerar uma chave secreta. Apesar de um
grande passo, esse esquema prejudicava a espontaneidade do e-mail.
5.2 PRINCÍPIOS DE CRIPTOSSISTEMAS DE CHAVE PÚBLICA
Apesar do esquema criptográfico funcional apresentado anteriormente,
nada havia sido implementado em computador. Entretanto, já se pensava na
ideia de chaves diferentes para cifrar e decifrar a mensagem. Alice teria uma
chave pública que seria do conhecimento de todos, disponível em uma lista
telefônica, por exemplo. Ela não precisa transmitir essa chave de forma
confidencial, antes expõe a todos a sua chave de cifragem pública, inclusive a
maléfica Eva. Contudo, a chave pública em nada ajuda no processo de
decifragem. Mesmo que Bob criptografe a mensagem com a chave pública de
Alice, somente ela poderá decriptografá-la com sua chave particular.
O criptossistema de chave pública pode ser representado pela analogia:
Alice projeta um cadeado e uma chave. Ela guarda a chave, mas manda fabricar milhares de réplicas do cadeado e as distribui pelas agências do correio do mundo inteiro. Se Bob quer mandar uma mensagem, ele a coloca em uma caixa, vai até a agência local dos correios e pede um „cadeado da Alice‟, usando-o para trancar a caixa. Agora ele é incapaz de abri-la, mas quando Alice a receber poderá abri-la com sua chave única. O cadeado e o processo de trancá-la são equivalentes à chave de cifragem pública, porque todos têm acesso aos cadeados e todos podem usá-los para trancar uma mensagem em uma caixa. A chave do cadeado equivale à chave de decifragem particular, porque somente Alice a possui, só ela pode abrir o cadeado e só ela pode ter acesso à mensagem na caixa. (SINGH, 2010, p. 296).
68
É possível notar duas características na elaboração de algoritmos
assimétricos:
Ser computacionalmente inviável determinar a chave de decriptografia
mesmo com o conhecimento do algoritmo e chave de criptografia.
Qualquer uma das duas chaves podem ser usadas para criptografar
desde que a outra seja usada para decriptografar.
Figura 33 Criptografia de chave assimétrica
Fonte: (STALLINGS, 2008)
A Figura 33 mostra o esquema para a criptografia de chave assimétrica.
Quando usada de forma contrária ao modo convencional, a criptografia
assimétrica provê outros benefícios além da confidencialidade dos dados.
Considere que Bob deseja enviar uma mensagem para Alice e criptografa-a
com sua chave privada. Alice pode facilmente decifrar a mensagem com a
chave pública de Bob. Portanto, a mensagem cifrada com a chave privada de
Bob serve para indicar que ele realmente enviou tal mensagem. Logo, todas as
mensagens criptografadas dessa forma servem como uma assinatura digital.
Esse processo é semelhante às assinaturas em documentos de papel para
verificar se uma mensagem foi enviada por determinada pessoa.
69
Figura 34. Autenticação usando Criptografia de Chave Pública
Fonte: STALLINGS (2008)
A figura 34 mostra a garantia da autenticação através do uso da
criptografia de chave pública.
5.3 ALGORITMO RSA
Inicialmente, Alice precisa gerar um par de chaves: a chave pública – PU
– e a chave privada – PR. Para isso, é necessário que ela escolha dois
números, p e q, inteiros e primos. Em seguida, Alice multiplica p e q obtendo N.
Suponha que Alice escolheu p = 2 e q = 11. Multiplicando os dois
números, temos que N = 2 x 11 = 22. O valor N é como a chave pública e se
torna disponível a todos, mas somente Alice deve conhecer p e q porque estes
valores são informações específicas e necessárias para a decifragem das
mensagens. Em vista de N ser uma informação acessível a todos, é necessário
que ele seja um valor suficientemente grande de tal forma que seja impossível
encontrar os valores de p e q através da fatoração. Para Singh (2010) este é
talvez o aspecto mais belo e elegante da cifra assimétrica RSA o que garante a
segurança do alogritmo.
Agora Alice deve escolher um terceiro número e que seja menor e
relativamente primo a (p – 1)(q – 1) e calcular um inteiro d que satisfaça e x d =
1 mod (p – 1 )(q – 1). Dois números inteiros são ditos relativamente primos se o
70
número 1 é o único fator inteiro positivo em comum entre eles. Considerando
os valores de p e q que têm sido utilizados até o momento tem-se:
ed 1 mod (2 – 1 )(11 – 1 )
ed 1 mod 10
Como o valor de e deve ser relativamente primo a 10, um dos valores
possíveis é e = 3. Logo, através do algoritmo de Euclides achamos d = 7, pois
21 = 1 mod 10. De forma geral, o relacionamento entre e e d pode ser expresso
como
ed mod (n) = 1
, onde (n) = (pq) = (p – 1)(q – 1). Isso é equivalente a dizer
ed 1 mod (n)
d e-1 mod (n)
Em posse de todas as informações necessárias, Alice pode enviar uma
mensagem criptografada para Bob. A criptografia e a decriptografia tem a
seguinte forma para um bloco de texto claro M e saída de texto cifrado C:
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
Por fim, a chave pública de Alice é expressa por PU = (e, n) e a chave
secreta por PR = (d, n). Para o exemplo em questão, PU = (3, 22) e PR = (7,
22).
Stallings (2008) resume os ingredientes do esquema RSA:
p,q , dois números primos (privados, escolhidos)
n = pq (público, calculado)
e, com mdc( (n), e) = 1; 1 < e < (n) (público, escolhido)
d e-1 (mod (n)) (privado, calculado)
71
Figura 35 Esquema geral do RSA
Fonte: STALLINGS (2008)
A figura 35 mostra de forma direta e clara o esquema geral do RSA.
Um exemplo extraído de Stallings (2008) mostra como calcular o par de
chaves e o processo de criptografar e decriptografar uma mensagem:
1. Selecione dois números primos, p = 17 e q = 11.
2. Calcule n = 17 x 11 = 187.
3. Calcule (n) = (p – 1)(q – 1) = 16 x 10 = 160.
4. Escolha um número e que seja menor e relativamente primo a (n) =
160; faça e = 7.
5. Determine d tal que de 1 (mod 160) e d < 160. Usando o algoritmo de
Euclides, tem-se que o valor correto de d = 23, pois 23 x 7 = 161 = 1 x
160 + 1.
As chaves resultantes são: PU = {7, 187} e PR = {23, 187}. Agora
imagine que Bob quer enviar a letra X para Alice. Em ASCII, ela é representada
por 101 1000, que vale 88 decimais. Portanto, o texto claro de entrada é M =
88. Para criptografar o código é necessário calcular C = 887 mod 187. Usando
72
as propriedades da aritmética modular o cálculo se torna mais fácil, pois 7 = 4 +
2 + 1:
887 mod 187 = [(884 mod 187) x (882 mod 187) x (881 mod 187)] mod 187
881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 59.969.536 mod 187 = 132
887 mod 187 = (88 x 77 x 132) mod 187 = 894.432 mod 187 = 11
Bob neste momento envia o texto cifrado, C = 11, para Alice. Para
decriptografar a mensagem, Alice calcula M = 1123 mod 187:
M = 1123 mod 187
1123 mod 187 = [(111 mod 187) x (112 mod 187) x (114 mod 187) x
x (118 mod 187) x (118 mod 187)]
111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14.641 mod 187 = 55
118 mod 187 = 214.358.881 mod 187 = 33
1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187 = 88
M = 88 = X em ASCII
A Figura 36 ilustra o exemplo.
Figura 36. Exemplo do algoritmo RSA
Fonte: STALLINGS (2008)
73
6. CONCLUSÃO
A criptografia tem se apresentada como uma arte tão antiga quanto
essencial nas comunicações. À medida que foi evoluindo, ela foi se adequando
a tecnologia da época, o que sempre tornava o processo de decifragem um
novo obstáculo para os quebradores de código. Contudo, a Matemática sempre
mostrou assumir papel importante no estudo da Criptografia.
Desde a invenção do computador, as mensagens passaram a ser
codificadas no sistema de numeração binária. Isso já mostrava que a
Matemática possui uma melhor capacidade de lidar com as mais variadas
técnicas criptográficas.
A primeira vista pode parecer difícil aplicar a matemática à criptografia
de uma forma que traga a segurança necessária. Mas a persistência de alguns
pesquisadores mostrou que há muito a ser explorado, pois até hoje nessa
ciência perduram problemas insolúveis. Não é o simples uso de uma função
matemática que criará a cifra indecifrável, mas a combinação lógica de
diversos dos seus elementos associados até mesmo a outras áreas do
conhecimento, como a física quântica, pode fornecer uma cifra
temporariamente segura, como a Criptografia Quântica.
É importante notar que a evolução da tecnologia está diretamente ligada
a segurança da informação, pois quanto mais poder computacional existir mais
fácil será ter acesso as mensagens criptografadas, principalmente pelo uso da
força bruta. Um grande exemplo é o algoritmo RSA que tem sua segurança
baseada na dificuldade computacional de se fatorar um número relativamente
grande.
Por fim, é importante a constante pesquisa no ramo da Matemática
aplicada à Criptografia. A NSA, por exemplo, possui os melhores matemáticos
do mundo porque sabe do potencial que o conhecimento desses profissionais
podem causar na atual Era da Informação. Em meio ao grande avanço
tecnológico, a matemática prevalece como um dos alicerces que sustém a
criptografia.
74
REFERÊNCIAS
ALMEIDA. André Tenreiro de. O uso da matemática na criptografia. Rio de Janeiro, s/i 2005. Disponível em: http://www.gta.ufrj.br/grad/05_2/aes/. Acesso em: 06 nov. 2011. BEZERRA, D. J.; MALAGUTTI, P. L.; RODRIGUES, V. C. S. Aprendendo criptologia de forma divertida. Paraíba, 2010. Disponível em: http://www.mat.ufpb.br/bienalsbm/arquivos/Oficinas_Completos/O1Completo.pdf. Acesso em: 06 set. 2011. CÓDIGOS SECRETOS. A cítala espartana. [s/l]. Disponível em: http://www.dm.ufscar.br/~caetano/iae2004/G6/citala.htm. Acesso em 12 set. 2011. DONDA, Daniel. A matemática da cifra de Vigenère. [s/l], 29 set. 2010. Disponível em: http://www.mcsesolution.com/Seguran%C3%A7a/a-matematica-da-cifra-de-vigenere.html. Acesso em: 10 out. 2011. KIOSKEA. Introdução à codificação DES. [s/l], 11 jul. 2009. Disponível em: http://pt.kioskea.net/contents/crypto/des.php3. Acesso em: 19 set. 2011. KUROSE, J. F.; ROSS, K. W. Redes de computadores e a internet. 5 ed. São Paulo: Editora Addison-Wesley, 2010. MAIER, R. R.; Teoria dos números. Brasília, 2005. 139 f. Notas de aula, Departamento de Matemática – IE/UnB. Disponível em: http://www.mat.unb.br/~maierr/tnotas.pdf. Acesso em: 22 nov. 2011. MATHIAS. Leopoldo A. P. Algoritmo de criptografia AES. Disponível em: http://www.gta.ufrj.br/grad/05_2/aes/. Acesso em: 29 out. 2011. NUMABOA. Criptografia Numaboa. Disponível em: http://www.numaboa.com.br/criptografia. Acesso em: 14 set. 2011. SINGH, Simon. O livro dos códigos: a ciência do sigilo – do Egito à criptografia quântica. 8 ed. Rio de Janeiro: Editora Record, 2010. STALLINGS, William. Criptografia e segurança de redes: princípios e práticas. 4 ed. São Paulo: Editora Pearson, 2008. TANENBAUM, A. S. Redes de computadores. 4 ed. Rio de Janeiro: Editora Campus, 2003. TERADA, Routo. Segurança de dados: criptografia em rede computador. 2 ed. São Paulo: Editora Edgar Blucher, 2011.
75
ULBRICH, Henrique Cesar; DELLA VALLE, James. Universidade Hacker: desvende todos os segredos do submundo dos hackers. 6 ed. São Paulo: Editora Digerati Books, 2009. VARGAS, Marcello. MDC. Porto Alegre, 07 out. 2010. Disponível em: http://professormarcello.com/index.php?option=com_content&task=view&id=694&Itemid=47. Acesso em: 14 nov. 2011. WIKIPÉDIA. Enigma (máquina). [s/l], 04 de nov. 2011. Disponível em: http://pt.wikipedia.org/wiki/Enigma_%28m%C3%A1quina%29. Acesso em: 13 nov. 2011.
