Criptografia Contemporânea

Raul Fernando Weber
Instituto de Informática – UFRGS
Porto Alegre – RS
e­mail:[email protected]

1 Introdução

Segurança é um atributo muito complexo e difícil de implementar consistentemente em um sistema,
principalmente   em   ambientes   computacionais.   Projetar   e   implementar   um   sistema   visando
segurança significa analisar um conjunto complexo de situações adversas onde o projetista e um
oponente elaboram estratégias de modo completamente independente. O resultado desta análise
depende   fortemente   das   escolhas   e   técnicas   feitas   por   cada   um   dos   oponentes.   A   segurança   é
essencialmente um atributo negativo. É fácil caracterizar um sistema inseguro, mas não existe uma
metodologia capaz de provar que um sistema é seguro. Assim, um sistema é considerado seguro se
não foi possível, até o momento atual, determinar uma maneira de torná­lo inseguro. Com muita
frequência isto decorre simplesmente do fato que não foram testados todos os métodos de ataque
(ou até mesmo menosprezados alguns) ou que não foram identificados todos os possíveis atacantes.

Conforme a tecnologia de armazenamento e manipulação da informação se torna mais complexa, as
oportunidades para que ela seja utilizada por indivíduos não autorizados são cada vez maiores. É
neste contexto  que a criptografia  tem um papel  muito importante.  Criptografia  é caracterizada
como a ciência (ou arte) de escrever em códigos ou em cifras, ou seja, é um conjunto de métodos
que   permite   tornar   incompreensível   uma   mensagem   (ou   informação),   de   forma   a   permitir   que
apenas   as   pessoas   autorizadas   consigam   decifrá­la   e   compreendê­la.   Por   outro   lado,   a   arte   ou
ciência de recuperar uma determinada informação criptografada sem possuir a autorização (a chave,
a senha ou até mesmo o conhecimento do algoritmo utilizado) é denominada de  criptoanálise. É
tarefa de um criptoanalista determinar um método que possa quebrar a codificação. Uma tentativa
de criptoanálise é comumente chamada de ataque.

Até o advento dos computadores, um dos fatores determinantes do sucesso ou fracasso de um dado
método de criptografia era a habilidade que os seus usuários tinham para realizar as transformações
necessárias.  Muitas  vezes  isto  tinha   que ser  feito  em  condições   adversas, como   um campo   de
batalha, e com equipamento mínimo, para reduzir as chances de captura da máquina de criptografia.
Estes  métodos   tradicionais  são   hoje   em   dia   facilmente   criptoanalisados   com   o   auxílio   de
computadores, e todo um novo conjunto de métodos de criptografia baseados em computadores foi
desenvolvido a partir da segunda guerra mundial.
A criptografia contemporânea não é mais baseada em obscuridade, ou seja, não se utiliza mais a
suposição   de   que   qualquer   sistema   pode   ser   seguro   na   medida   em   que   ninguém,   exceto   seus
criadores, tem acesso à metodologia ou aos algoritmo utilizados internamente ao sistema. Para uso
moderno,   um   criptosistema   deve   ter   sua   segurança   baseada   não   nos   algoritmos   de   cifragem   e
decifragem (ou codificação e decodificação, ou criptografia e decriptografia), mas sim em um valor
secreto – uma chave. O mecanismo deve ser tão seguro que nem mesmo o autor de um algoritmo
deve ser capaz de decifrar um texto cifrado sem dispor da chave apropriada. Assim, assume­se que
um criptoanalista conhece todo o criptosistema, exceto as chaves utilizadas. Esta é conhecida como
a premissa de Kerckhoffs, matemático holandês do século XIX. Note­se que isto exclui a segurança
por obscuridade

Os requisitos de segurança são, na realidade, ainda maiores. Para um algoritmo ser analisado do
ponto de vista de sua robustez a ataques são assumidas as seguintes premissas [SCH96]:
• o criptoanalista tem acesso à descrição completa do algoritmo.
• o   criptoanalista   tem   acesso   a   grandes   volumes   de   mensagens   originais   e   suas   mensagens
cifradas correspondentes.
• o criptoanalista é capaz de escolher quais mensagens serão cifradas e receber as mensagens
cifradas correspondentes.

Obviamente, a maioria dos sistemas utiliza normas para evitar que estas premissas se realizem, mas
um criptosistema que não se baseie nestas premissas é automaticamente assumido como inseguro.

2 Modelo de criptosistema

A finalidade básica de um criptosistema é cifrar (codificar e criptografar são aqui considerados
sinônimos) uma mensagem (também chamada de texto normal, texto claro, texto original ou texto
compreensível) através de um método de cifragem, que recebe como entrada a própria mensagem e
uma   chave   de   cifragem,   produzindo   como   resultado   uma   mensagem   cifrada   (texto   cifrado   ou
criptograma). Esta mensagem cifrada é então armazenada em um meio qualquer ou transmitida até
um receptor. Para decifrar a mensagem (ou decodificar, ou decriptografar) utiliza­se um método de
decifragem, que recebe como entradas a mensagem cifrada e uma chave de decifragem e fornece
como saída a mensagem original. A figura 1 ilustra estes componentes.
 
Figura 1 – Modelo de criptosistema

Obviamente, a mensagem M e a mensagem cifrada C podem ser de qualquer tipo e formato. Os
métodos de cifragem E e de decifragem D normalmente são distintos, embora isto não seja um pré­
requisito. Caso as chaves de cifragem Ke  e de decifragem Kd  sejam iguais, fala­se então de um
sistema de chaves simétricas, ou chave única, ou chave secreta, onde elas devem ser mantidas
secretas. Caso estas chaves sejam diferentes, fala­se de um sistema de chaves assimétricas, ou de
chave pública. Matematicamente, tem­se:
 • C = E ( M, Ke )

• M = D ( C, Kd ) = D ( E ( M, Ke ), Kd )

Uma pessoa não autorizada que tem acesso a alguns do elementos acima  é denominada de um
atacante.   Um   atacante   passivo   somente   consegue   obter   cópias   destes   elementos,   enquanto   um
atacante ativo consegue não somente obter cópias como também modificar os elementos. Assim,
por exemplo, um atacante ativo poderia interceptar uma mensagem cifrada M1 e alterá­la ou trocá­
la por uma mensagem M2. A robustez de um criptosistema não é analisada em termos do tipo de
atacante; um ataque ativo deve ser impedido através de um protocolo criptográfico adequado (e não
somente pelos métodos de cifragem e decifragem).

Existem seis tipos gerais de ataque (ou criptoanálise), listados a seguir em ordem crescente de
efetividade [SCH96]. Todos eles supõe que o criptoanalista possui um conhecimento total sobre os
métodos de cifragem e decifragem utilizados, mas não sobre as chaves.

Ataque do texto cifrado (cyphertext­only)

Neste tipo de ataque, o criptoanalista tem a sua disposição uma grande quantidade de mensagens
cifradas, mas desconhece as mensagens originais e as chaves utilizadas. Sua tarefa é recuperar as
mensagens normais (ou melhor ainda deduzir as chaves utilizadas).
• Dado: C1 = E(M1,Ke), C2 = E(M2,Ke), . . . Cn = E(Mn,Ke).

• Deduzir: M1, M2, . . . Mn; ou Ke (Kd); ou um método para inferir Mn+1 a partir de Cn+1.

Ataque do texto conhecido (known­plaintext)

Neste   ataque,   o   criptoanalista   não   somente   tem   a   sua   disposição   uma   grande   quantidade   de
mensagens   cifradas,   mas   conhece   também   as   mensagens   originais   equivalentes.   Sua   tarefa   é
deduzir   as   chaves   utilizadas   (ou   um   método   para   recuperar   mensagens   cifradas   com   a   mesma
chave).
• Dado: M1, C1 = E(M1,Ke), M2, C2 = E(M2,Ke), . . . Mn, Cn = E(Mn,Ke).

• Deduzir: Ke (Kd); ou um método para inferir Mn+1 a partir de Cn+1.

Ataque do texto escolhido (choosen­plaintext)

Neste ataque, o criptoanalista não somente tem a sua disposição pares de mensagens cifradas com
as respectivas mensagens originais, como também pode escolher um determinado texto e obter o
texto cifrado. Sua tarefa é deduzir as chaves utilizadas (ou um método para recuperar mensagens
cifradas com a mesma chave).
 • Dado: M1, C1 = E(M1,Ke), M2, C2 = E(M2,Ke), . . . Mn, Cn = E(Mn,Ke), onde o critoanalista
escolhe alguns dos Mi e obtém o Ci correspondente.
• Deduzir: Ke (Kd); ou um método para inferir Mn+1 a partir de Cn+1.

Ataque adaptativo do texto escolhido (adaptative­choosen­plaintext)

Este   ataque   se   diferencia   do   anterior   porque   agora   pode   existir   uma   realimentação   entre   uma
mensagem escolhida para cifragem e a próxima mensagem. No método anterior, por exemplo, o
criptoanalista poderia ser capaz de fornecer somente uma grande quantidade de mensagens de uma
única vez; agora ele pode fornecer um pequeno conjunto, analisar os resultados, fornecer outro
conjunto, e assim por diante. Este ataque é bem mais efetivo, pois permite o teste de novas idéias e
a sua posterior confirmação. Sua tarefa é deduzir as chaves utilizadas (ou um método para recuperar
mensagens cifradas com a mesma chave).
• Dado: M1, C1 = E(M1,Ke), M2, C2 = E(M2,Ke), . . . Mn, Cn = E(Mn,Ke), onde o criptoanalista
escolhe M1, M2, . . . Mn em diferentes instantes no tempo, após analisar C1, C2, . . . Cn.

• Deduzir: Ke (Kd); ou um método para inferir Mn+1 a partir de Cn+1.

Ataque do texto cifrado escolhido (choosen­ciphertext)

Neste tipo de ataque, o criptoanalista não somente tem a sua disposição uma grande quantidade de
mensagens e seus equivalentes cifrados, mas pode produzir uma mensagem cifrada específica para
ser decifrada e obter o resultado produzido. Este ataque é utilizado quando se tem uma “caixa­
preta” que faz decifragem automática. Sua tarefa é deduzir as chaves utilizadas.
• Dado: C1, M1 = E(C1,Kd), C2, M2 = E(C2,Kd), . . . Cn, Mn = E(Cn,Kd), onde o criptoanalista
escolhe C1, C2, . . . Cn.

• Deduzir: Kd (Ke).

Ataque da chave escolhida (choosen­key)

Embora não considerado por muitos especialistas como sendo um ataque (não é um ataque quando
a chave é conhecida), um criptoanalista pode testar o sistema com diversas chaves diferentes, ou
pode convencer diversos usuários legítimos do sistema a utilizarem determinadas chaves. Neste
último caso, a finalidade imediata seria poder decifrar as mensagens cifradas com estas chaves.

Segurança de criptosistemas

Criptosistemas distintos possuem diferentes graus de segurança, dependendo da facilidade ou da
dificuldade com que eles são atacados e quebrados. Um sistema é dito incondicionalmente seguro
se ele é teoricamente inquebrável, ou seja, não interessa qual a quantidade de texto normal ou
cifrado   a   disposição,   nunca   se   tem   informação   suficiente   para   deduzir   as   chaves   utilizadas   ou
decifrar um texto cifrado qualquer.

Até o momento, só se conhece um método nesta categoria: a Cifra de Vernam ou “one­time pad”
(cifra   de   uso   único),   desenvolvida   na   década   de   20   por   Gilbert   Vernam,   da   AT&T   e   Joseph
Mauborgne,   do   Exército   americano.   Em   essência,   dois   elementos   que   desejam   se   comunicar
dispõem de cópias idênticas de uma sequência randômica de valores, que são usados como chave.
O   método,   entretanto,   exige   que   cada   chave   seja   usada   somente   uma   única   vez,   e   que   o
comprimento da sequência (a chave) seja maior ou no mínimo igual ao comprimento da mensagem
a ser cifrada.

Todos os demais métodos desenvolvidos e em uso atualmente são quebráveis, desde que sejam
fornecidos tempo e recursos computacionais suficientes. Para muito deles, entretanto, o tempo e o
custo necessários para quebrá­los é muito grande (alguns se aproximam de infinito). Se o custo
requerido para quebrar um sistema (ou decifrar uma mensagem) é maior que o valor da informação
que será obtida, então para todos os fins práticos, o sistema é seguro. Deve­se observar, entretanto,
que   o   poder   de   processamento   dos   computadores   está   sempre   crescendo,   e   que   o   valor   da
informação armazenada diminui com o passar do tempo. Se para um determinado sistema estas
duas linhas se cruzarem, o sistema torna­se inseguro.

A criptologia atual está mais preocupada com os aspectos computacionais do que com o valor da
informação, e assim os criptosistemas normalmente são classificados como  computacionalmente
seguros  ou   não.   Sob   este   aspecto,   um   sistema   é   seguro   se,   com   os   recursos   computacionais
disponíveis   (atualmente  ou  em   um  futuro   próximo),  ele  não  pode   ser  quebrado  em   um  tempo
razoável.   Exatamente   o   que   são   “recursos   disponíveis”   e   “tempo   razoável”   está   aberto   a
interpretações, mas atualmente se considera que computadores com processamento da ordem de
Tera operações por segundo e um tempo de alguns milhares de anos se enquadram nas definições
acima.

3 Criptografia tradicional

Antes da era computacional,  a maioria  dos métodos  de criptografia  era orientado a caracteres,

substituindo um caracter por outro ou trocando caracteres de posição. Os métodos mais seguros
realizavam ambas operações, e de preferência várias vezes. Atualmente a complexidade aumentou e
em vez de caracteres se trabalham com bits, mas os métodos básicos continuam a ser utilizados.
Note­se que todos os métodos da criptografia tradicional são sistemas simétricos, ou seja, utiliza­se
para a decifragem a mesma chave da cifragem.

Cifras de substituição

Nestes métodos, cada caracter (ou grupo de caracteres) na mensagem é substituído por outro na
mensagem   cifrada.   Esta   substituição   é   realizada   para   tornar   o   texto   cifrado   mais   obscuro   e
incompreensível. A decifragem é feita realizando­se a substituição inversa, de forma a restaurar os
caracteres do texto original. Normalmente são considerados somente as 26 letras maiúsculas.
• Substituição monoalfabética: neste caso simples, cada caracter é substituído por outro, de
acordo com uma tabela ou uma regra simples. A cifra mais antiga conhecida é a chamada Cifra
de César, onde cada caracter é substituído por três caracteres adiante do alfabeto. Assim, A é
substituído por D, B por E, etc, até W por Z, X por A, Y por B e Z por C. Para a decifragem,
cada caracter é retrocedido de três posições.
Uma generalização deste método pode ser obtida se o alfabeto é deslocado de k posições, onde
k  é a chave a ser utilizada.  Ainda empregado nos dias de hoje, este método é usado pelo
algoritmo ROT13 (por exemplo na Usenet News), onde os caracteres avançam 13 posições (A
se torna N, B é O, . . ., N é A, O é B, etc). Note­se que os algoritmos de cifragem e decifragem
são   iguais,   ou   seja,   M   =   ROT13(ROT13(M)).   Este   método   não   visa   segurança,   mas
simplesmente impedir a leitura descuidada de texto sensível, ofensivo ou que revele alguma
pista de um quebra­cabeças ou mistério.
Outra melhoria no método é fazer um mapeamento individual de cada caracter, em vez de
utilizar um deslocamento constante. Isto exige o uso de uma tabela, com uma entrada para cada
caracter do alfabeto.
• Substituição monofônica: opera como a substituição monoalfabética, mas agora cada caracter
da mensagem original pode ser mapeado para um ou vários caracteres na mensagem cifrada.
Por exemplo, a letra A seria substituída pelos números 5, 13, 25 ou 56; a letra B por 7, 19, 31
ou 42, e assim por diante.
• Substituição   polialfabética:   é   uma   combinação   do   uso   de   várias   substituições   mono­
alfabéticas, usadas em rotação de acordo com algum critério ou chave. Assim, por exemplo,
poderiam ser usadas 4 tabelas, usadas em alternância a cada quatro caracteres: a primeira para
os caracteres localizados nas posições 1, 5, 9, 13, etc; a segunda nas posições 2, 6, 10, 14, etc;
a terceira nas posições 3, 7, 11, 15, etc, e a quarta nas posições 4, 8, 12, 16, etc.
Um exemplo clássico é a Cifra de Vigenère, constituída de 26 Cifras de César, cada uma com
um deslocamento diferente. A primeira linha, associada à letra A, tem deslocamento zero; a
segunda linha (B) tem deslocamento um; a terceira (C) tem deslocamento dois; e assim por
diante até a última (Z), que desloca 26 posições. A chave utilizada (uma palavra ou frase)
define quais  linhas  devem  ser usadas, e em  qual ordem. Assim, se a chave  for “DARK”,
significa que a primeira letra da mensagem é substituída de acordo com a linha D, a segunda de
acordo com a linha A, a terceira segundo a linha R, a quarta segundo a linha K, a quinta de
novo com a linha D, e assim por diante. Note­se que a chave é duplicada tantas vezes quantas
as necessárias para atingir­se o comprimento total da mensagem a ser cifrada.
Em vez de 26 Cifras de César, pode­se usar 26 tabelas aleatórias, o que torna a criptoanálise
mais complexa, mas também exige que a tabela seja memorizada ou armazenada em algum
lugar, tornando­a passível de ser descoberta.
 • Substituição por polígramos: é uma substituição que utiliza grupos de caracteres em vez de
trabalhar com caracteres individuais. Assim, por exemplo, se forem considerados trigramas,
“ABA” poderia ser substituído por ”RTQ”, “ABB” por “KXS”, etc. Note­se que as tabelas de
substituição   aumentam   rapidamente   (262  para   digramas,   263  para   trigramas,   e   assim   por
diante).

Em uma primeira análise, os métodos de substituição podem parecer seguros. Para uma simples
substituição monoalfabética, com 26 caracteres, existem 26! = 4 x 10 26 tabelas possíveis. Mesmo
tentando uma tabela a cada micro­segundo, seriam necessários 1013 anos para tentar todas elas.

Entretanto, as cifras de substituição podem ser facilmente quebradas, simplesmente analisando­se a
frequência de cada caracter no texto cifrado e comparando­se estas frequências com aquelas que
normalmente   aparecem   em   uma   determinada   língua.   As   vogais   tem   maior   frequência   que   as
consoantes, e alguns caracteres possuem frequência baixíssima em relação aos demais. Além disto,
a maioria das linguagens possui uma redundância tão alta que é necessária uma quantidade bem
pequena de texto  cifrado para que uma criptoanálise  baseada em  frequência  possa ser iniciada
[TAN88], [SCH96].

A substituição polialfabética é inquestionavelmente melhor que a monoalfabética, mas pode ser
quebrada pelo mesmo método. O primeiro passo é determinar o comprimento  k  da chave. Se a
estimativa for correta, analisando­se a frequência dos caracteres amostrando­se o texto de k em k,
chega­se a uma distribuição bem semelhante a da língua utilizada. Se a distribuição for incorreta, a
distribuição é bem distinta. O segundo passo simplesmente forma k tabelas de substituição, ou seja,
o texto é tratado de  k  em  k  caracteres para fins de análise. Naturalmente, a quantidade de texto
disponível deve ser k vezes maior do que a quantidade necessária para analisar uma substituição
monoalfabética. Com o auxílio de computadores, a análise é enormemente facilitada [DAN95].

Cifras de transposição

Nestes métodos, cada caracter permanece inalterado, mas sua posição na mensagem é alterada de
acordo com alguma regra ou função (que também podem estar baseadas em alguma chave). Por
exemplo, em uma transposição colunar o texto é inicialmente escrito em linhas de tamanho fixo e
depois re­escrito percorrendo­se as colunas. Para uma criptoanálise destas cifras, é necessário um
conhecimento do contexto da mensagem. Sabendo­se algumas das palavras que deveriam aparecer
no texto, procura­se pelos caracteres que formam estas palavras e procura­se deduzir como suas
posições foram alteradas, determinando­se primeiro o tamanho da linha e depois as permutações
que ocorreram entre as colunas.

A   diferenciação   entre   um   texto   cifrado   por   substituição   e   outro   por   transposição   é   bem   fácil,
novamente  utilizando­se análise  de frequência  dos  caracteres.  Se a frequência  for a  mesma  da
língua, trata­se de uma transposição. Se não, tem­se uma substituição.
4 Criptografia computacional de chave única

Atualmente   os   métodos   criptográficos   tradicionais   cederam   lugar   a   criptografia   computacional,

onde as operações são implementadas por um computador ou por um circuito integrado especial.
Isto acelera enormemente os processos de cifragem e decifragem (e também a criptoanálise), e com
isto diversos passos extras de substituição e transposição podem ser utilizados, de modo a mascarar
a frequência dos símbolos utilizados e dificultar sua análise.

Idealmente,  o método  de cifragem  deve ser tal  que  a probabilidade  de ocorrência  de qualquer

símbolo na mensagem cifrada seja exatamente igual às probabilidades de todos os demais símbolos,
ou seja, a distribuição das frequências dos símbolos é homogênea (“flat”). Com isto, a alteração de
um único símbolo na mensagem normal tem a probabilidade de alterar metade dos símbolos da
mensagem   cifrada,   e   vice­versa.   Em   termos   computacionais,   a   inversão   de   um   único   bit   na
mensagem normal (ou na cifrada) altera idealmente metade dos bits da mensagem cifrada (ou da
normal). Isto naturalmente impede qualquer análise por frequência de símbolos, mas por outro lado
torna   a   mensagem   cifrada   muito   sensível   a   erros   ou   alterações   intencionais.   Ganha­se   em
privacidade   e  segurança,   mas  perde­se  em  confiabilidade   e  autenticidade.   Para  compensar   esta
desvantagem são normalmente utilizados códigos de detecção de erros.

Algoritmo DES

O exemplo mais difundido de um cifrador computacional de chave única é o DES (Data Encryption
Standard), originalmente desenvolvido pela IBM e adotado como padrão nos Estados Unidos em
1977. O DES trabalha dividindo a mensagem em blocos de 64 bits (8 caracteres) e cifrando cada
um destes blocos com uma chave de 56 bits (mais 8 bits de paridade, o que também completa 64
bits).

O algoritmo inicia realizando uma transposição inicial sobre os 64 bits da mensagem, seguida de 16
passos de cifragem e conclui realizando uma transposição final, que é a inversa da transposição
inicial (figura 2). As transposições são independentes da chave. Para os 16 passos de cifragem
utilizam­se   16   sub­chaves,   todas   derivadas   da   chave   original   através   de   deslocamentos   e
transposições.   Cada   passo   divide   o   bloco   em   duas   metades   de   32   bits   (L   e   R)   e   realiza
transposições, substituições, expansões (duplicações) de bits e reduções (eliminações) de bits, além
de utilizar operações lógicas do tipo ou­exclusivo.
 
Figura 2 – Processo de cifragem do DES

Permutação Inicial (IP)
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Permutação Final (IP­1)
40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Figura 3 ­ Permutações iniciais e finais no DES

Um passo de cifragem do DES, mostrado na figura 4, tem dois objetivos básicos: a difusão e a
confusão. A difusão visa eliminar a redundância existente na mensagem original, distribuindo­a
pela mensagem cifrada. O propósito da confusão é tornar a relação entre a mensagem e a chave tão
complexa   quanto   possível,   de   forma   a   impedir   a   dedução   da   chave   a   partir   de   características
especiais da mensagem.
 
Figura 4 – Um passo do DES

Cada passo trabalha com uma das duas metades do bloco de 64 bits da mensagem. As operações
são realizadas sobre a metade Ri­1, que ao mesmo tempo que é operada transforma­se na metade L i
do  passo  seguinte.  A  metade  Li­1, por sua  vez,  é  simplesmente  utilizada  para  realizar  um  ou­
exclusivo com o resultado das operações sobre Ri­1, e o resultado forma a metade Ri  do passo
seguinte.

Inicialmente é gerada uma sub­chave Ki, deslocando individualmente cada uma das metades da
chave   K,   reunindo   as   duas   metades,   realizando   uma   transposição   dos   56   bits   seguida   de   uma
seleção que elimina 8 bits e mantém 48 bits. Os 32 bits de R i­1 são também transpostos e a seguir
expandidos para 48 bits, através da duplicação de alguns destes bits. Estes 48 bits são operados,
através de um ou­exclusivo, com a sub­chave Ki. Os 48 bits de resultados  são divididos em 8
grupos de 6 bits, e cada grupo é substituído por 4 bits, através de oito tabelas de substituição e
seleção.   Os   32   bits   resultantes   são   transpostos   para   serem   operados   com   Li­1.   As   tabelas   de
manipulação dos bits e as 8 caixas S do DES podem ser vistas nas figuras 5 e 6, respectivamente.
Nestas tabelas, os números se referem aos índices dos bits.

Maiores   detalhes   sobre   o   funcionamento   do   DES   podem   ser   encontrados   na   literatura,

especialmente em [LUC86], [CIK92], [SCH96].

Compressão inicial (de 64 para 56 bits) da chave
57 49 41 33 25 17 9 1 58 50 42 34 26 18
10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4

Deslocamentos da chave por rodada (cifragem: para esquerda; decifagrem: para direita)
Rodada 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Desloc. 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

Permutação de compressão da sub­chave (reduz de 56 para 48 bits)
14 17 11 24 1 5 3 28 15 6 21 l0
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32

Permutação de expansão de metade do bloco (expande de 32 para 48 bits)
32 1 2 3 4 5 4 5 6 7 8 9
8 9 l0 11 12 13 12 13 14 15 16 17
16 17 .18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 1

Caixa de Permutação (P­Box) (sobre 32 bits)
16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24  P 32 27 3 9 19 13 30 6 22 11 4 25

Figura 5 –Permutações no DES

Caixa­S1 (reduz de 6 para 4 bits)
14 4 13 1 2 15 11 8 3 l0 6 12 5 9 0 7
0 15 7 4 14 2 13 1 l0 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 l0 5 0
15 12 8 2 4 9 1 7 5 11 3 14 l0 0 6 13

Caixa­S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

Caixa­S3
l0 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

Caixa­S4
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

Caixa­S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 l0 4 5 3

Figura 6 ­ Caixas S no DES (primeira parte)
Caixa­S6
12 l l0 15 9 2 6 8 0 13 3 4 14 7 5 ll
l0 15 4 2 7 12 9 5 6 l 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 l 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

Caixa­S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 l
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

Caixa­S8
13 2 8 4 6 15 11 1 l0 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Figura 6 ­ Caixas S no DES (segunda parte)

Desde a sua aprovação como padrão, o DES tem sido alvo de intensa crítica e debate. O projeto
original da IBM, que previa blocos de 128 bits, foi reduzido pela NSA (National Security Agency)
para 64 bits, sem maiores explicações. Como as notas de projeto e a criptoanálise do DES são
classificados pelos Estados Unidos como material secreto, até hoje ninguém sabe dos motivos, e se
isto enfraqueceu o DES ou não.

O DES pode ser quebrado pelo método da força bruta, tentando­se todas as combinações possíveis
para a chave. Como a chave tem 56 bits, tem­se um total de 256 chaves possíveis, ou aproximada­
mente 1017 possibilidades. Utilizando­se um ataque de texto plano escolhido e adaptativo, já foi de­
monstrado que o DES pode ser quebrado com 247 ou até mesmo com 243 tentativas [SCH96]. Outras
análises foram realizadas  sobre o número de iterações, mostrando­se que, apesar da difusão da
informação já ser alcançada depois de 8 passos, são necessários no mínimo 16 passos para tornar
impraticável um ataque do tipo texto normal escolhido. As oito tabelas de substituição também
foram exaustivamente analisadas, e verificou­se que, alterando um dos 6 bits de entrada, altera­se
no mínimo 2 dos 4 bits  de saída. Segundo a NSA, estas  tabelas  foram escolhidas  de forma a
minimizar   a   diferença   entre   o   número   de   zeros   e   uns   na   saída   quando   a   entrada   for   mantida
constante (sempre em zero ou sempre em um). As figuras 7, 8 e 9 mostram diversas análises do
DES.

Núm. Texto Claro Texto cifrado Distância   de

Hamming
1 A B C D E F A B C D E F A B C D C D E 8 7 2 D 4 A 4 7 1 3 4 6 ­­­
 F
2 8 B C D E F A B C D E F A B C D C D 3 D 0 A A 4 C 4 0 2 4 B 4 29
A
3 A 9 C D E F A B C D E F A B C D 8 0 1 F 8 A 2 9 6 8 B C 4 4 7 38
3
4 A B D D E F A B C D E F A B C D 5 D 9 8 C 4 7 D D D B A 6 F 3 36
0
5 A B C F E F A B C D E F A B C D 9 9 8 9 5 6 2 A 8 4 F 4 0 1 C 26
9
6 A B C D 6 F A B C D E F A B C D 6 7 C 2 6 9 F 2 5 4 2 7 9 1 F 30
9
7 A B C D E B A B C D E F A B C D F 8 C 9 8 F 7 9 A D C 0 6 E A 33
4
8 A B C D E F D B C D E F A B C D 8 7 D 3 2 4 0 A B B F 4 4 0 7 34
4
9 A B C D E F A 9 C D E F A B C D D B 9 9 8 B 6 7 0 4 6 C D C E 30
7
10 A B C D E F A B E D E F A B C D 2 F 6 E 5 4 7 0 E 4 E 3 5 1 A 25
C
11 A B C D E F A B C C E F A B C D B 5 3 E 4 2 D E 3 0 F 9 7 A D 29
0
12 A B C D E F A B C D 6 F A B C D 4 F 4 0 6 7 7 2 6 B 3 5 B 0 1 28
4
13 A B C D E F A B C D E 7 A B C D A B 1 5 5 2 8 9 6 6 0 C 6 0 B 35
2
14 A B C D E F A B C D E F 2 B C D 5 B D A 9 3 F 7 D 4 2 7 B 8 D 30
2
15 A B C D E F A B C D E F A F C D 9 8 5 3 C 5 1 1 E D 5 6 8 8 7 34
E
16 A B C D E F A B C D E F A B D D 7 0 A A 2 4 0 7 9 5 9 F 0 4 B 34
1
17 A B C D E F A B C D E F A B C 5 8 9 2 B E C 4 7 C 9 7 1 2 B E 26
3
Média: 31,06
Chave = 0 1 2 3 4 5 6 7 8 9 A B C D E F

Figura 7 ­ Análise da dependência do texto claro para o texto cifrado 

Núm. Chave Texto cifrado Distância   de

Hamming
1 0 1 2 3 4 5 6 7 8 9 A B C D E F C D E 8 7 2 D 4 A 4 7 1 3 4 6 ­­­
F
2 8 0 2 3 4 5 6 7 8 9 A B C D E F 1 B 7 3 F E 8 B C 0 B 8 8 6 0 35
6
3 0 2 2 3 4 5 6 7 8 9 A B C D E F 0 F 9 2 F 6 0 D 2 F D 4 D 8 B 32
7
4 0 1 6 2 4 5 6 7 8 9 A B C D E F 3 1 A F D 8 C 5 4 F B F 4 B C 37
D
5 0 1 2 6 4 5 6 7 8 9 A B C D E F C 7 9 F 5 9 6 3 D 4 6 5 A 7 E 29
E
6 0 1 2 3 0 4 6 7 8 9 A B C D E F 3 6 5 2 9 C C 1 0 7 1 7 A 3 8 39
9
7 0 1 2 3 4 6 6 7 8 9 A B C D E F 7 F 3 5 F 7 E 6 C E C 5 7 E E 30
3
8 0 1 2 3 4 5 4 6 8 9 A B C D E F C 9 F 3 F D 9 2 6 0 C 6 8 1 8 27
A
9 0 1 2 3 4 5 6 4 8 9 A B C D E F E 6 9 2 8 3 2 2 E E 8 B 9 A 6 36
9
10 0 1 2 3 4 5 6 7 A 8 A B C D E F 0 9 9 7 A 5 A F 6 E 4 E 1 4 6 37
0
11 0 1 2 3 4 5 6 7 8 A A B C D E F C 7 B 4 1 C 4 F 3 8 D 9 A F 7 31
A
12 0 1 2 3 4 5 6 7 8 9 E A C D E F 4 B 4 A A 2 0 A B 2 1 4 4 D D 30
D
13 0 1 2 3 4 5 6 7 8 9 A 8 C D E F 1 2 9 9 7 E E 8 0 0 1 B D 2 7 32
C
14 0 1 2 3 4 5 6 7 8 9 A B 4 C E F 4 2 D 1 7 B 7 D F 5 3 4 3 B 7 28
9
15 0 1 2 3 4 5 6 7 8 9 A B C E E F 8 7 F 6 4 9 3 C 4 C 8 9 8 3 2 33
7
16 0 1 2 3 4 5 6 7 8 9 A B C D 6 E F C 3 0 F 6 F 7 6 B D 4 2 5 9 31
2
17 0 1 2 3 4 5 6 7 8 9 A B C D E C 1 C B D E C 4 B 7 9 B C A 7 A 39
1
Média: 32,88
Texto claro = A B C D E F A B C D E F A B C D

Figura 8 ­ Análise da dependência da chave para o texto cifrado 

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

Rodada Reg. L Reg. R Reg. L Reg. R Distância

1 00000000 00000000 00000080 00000000 1
2 00000000 AF0D68FD 00000000 AF0D687D 1
3 AF0D68FD CE0A36EA AF0D687D CE3A32E2 5
4 CE0A36EA 0BDCC5FE CE3A32E2 81BDED5F 15
5 0BDCC5FE 5D181CC3 81BDED5F F8CA39B2 26
6 5D181CC 1744B978 F8CA39B2 A994B918 26
7 1744B978 9B1CB0D8 A994B918 3E9D05D8 22
8 9B1CB0D8 7AE8C7E0 3E9D05D8 23F48DFF 26
9 7AE8C7E0 A2AC7B3F 23F48DFF 9D58DCFB 34
10 A2AC7B3F 580E51EF 9D58DCFB 3F076303 34
11 580E51EF 2865DBD4 3F076303 97AE4AE3 35
12 2865DBD4 BF68F77C 97AE4AE3 68ABB612 37
13 BF68F77C 8F57F629 68ABB612 09D9C398 32
14 8F57F629 0827B240 09D9C398 44B0435C 31
15 0827B240 F2DEBFAC 44B0435C 319FD3B8 29
16 F2DEBFAC 16CD0EB8 319FD3B8 42684FF9 24
Texto cifrado 1 = 2 5 D D A C 3 E 9 6 1 7 6 4 6 7
Texto cifrado 2 = 1 B D D 1 8 3 F 1 6 2 6 F B 4 3
Diferença em bits = 22

Figura 9 ­ Análise do número de iterações 

Complementação

Uma característica notável do DES é a complementação, ou seja, invertendo­se todos os bits do
texto claro e todos os bits da chave, então obtém­se o complemento do texto cifrado original. Isto
pode ser surpreendente, considerando­se a não­linearidade introduzida pelas caixas S. Entretanto,
este efeito é inteiramente devido à presença de duas operações de ou­exclusivo.

Chaves Fracas

Uma chave é dita fraca para o DES se todas as sub­chaves forem iguais. Com isto, o efeito de cifrar
ou decifrar uma mensagem é o mesmo, pois a sequência de chaves K1 a K16 é idêntica à sequência
K16 a K1. Assim, se um texto for cifrado com uma chave fraca e a seguir cifrado novamente com a
mesma chave, obtem­se no final o texto original. As quatro chaves fracas são mostradas a seguir
(em hexadecimal; note­se que oito dos bits são na realidade bits de paridade):

Chave (com paridade) Chave real
01 01 01 01 01 01 01 01 00000000  00000000
FE FE FE FE FE FE FE FE FFFFFFFF  FFFFFFFF
1F 1F 1F 1F 0E 0E 0E 0E 00000000  FFFFFFFF
E0 E0 E0 E0 F1 F1 F1 F1 FFFFFFFF  00000000

Figura 10 ­ Chaves fracas do DES 

Chaves Semi­fracas

Um par de chaves é dito semi­fraco para o DES se a sequência de sub­chaves gerada por uma das
chaves do par for exatamente o inverso da sequência de sub­chaves gerada pela outra chave. Com
isto, se um texto for cifrado com uma das chaves do par e a seguir cifrado novamente com a outra
chave, obtem­se no final o texto original. Os seis pares de chaves semi­fracas são mostrados a
seguir (em hexadecimal):

Primeira chave Segunda chave
01 FE 01 FE 01 FE 01 FE FE 01 FE 01 FE 01 FE 01
1F E0 1F E0 0E F1 E0 F1 E0 1F E0 1F F1 0E F1 0E
01 E0 01 E0 01 F1 01 F1 E0 01 E0 01 F1 01 F1 01
1F FE 1F FE 0E FE 0E FE FE 1F FE 1F FE 0E FE 0E
01 1F 01 1F 01 0E 01 0E 1F 01 1F 01 0E 01 0E 01
E0 FE E0 FE F1 FE F1 FE FE E0 FE E0 FE F1 FE F1

Figura 11 ­ Chaves semi­fracas do DES 

Ciclos Hamiltonianos

As conexões das saídas das caixas S até as suas entradas (no ciclo de iteração seguinte) formam
uma estrutura regular. Para identificar perfeitamente esta estrutura, é necessário seguir o caminho
percorrido por cada um dos quatro bits de saída de cada caixa S até atingir­se um dos seis bits de
entrada de uma outra caixa S. A tabela a seguir indica estes caminhos. Na tabela, as saídas são
numeradas de 0 a 3, e as entradas são denominadas de A, B, C, D, E e F.

Caixa Saída 0 Saída 1 Saída 2 Saída 3

S1 F2, B3 F4, B5 D6 D8
S2 F3, B4 E7, A8 C1 C5
S3 E6, A7 E4, A5 C8 C2
S4 C7 E5, A6 C3 F8, B1
S5 E2, A3 C4 F6, B7 D1
S6 E1, A2 F7, B8 D3 D5
 S7 E8, A2 F7, B8 D3 D5
S8 F1, B2 D7 D4 F5, B6

Figura 12 ­ Caminhos pelas Caixas S

O fluxo dos bits pode ser melhor visualizado na forma de grafos, mostrados na figura 13 a seguir.
Grafo para as entradas CD Grafo para as entradas EF
 Grafo para as entradas AB

Figura 13 ­ Ciclos Hamiltonianos no DES

Note­se que os grafos para CD e EF tem forma idêntica, se considerarmos uma reflexão ao redor de
uma linha vertical. O grafo CD pode ser expresso por dois ciclos hamiltonianos (nós 87654321 e
84725163), e o grafo EF por outros dois (nós 12345678 e 36152748). Infelizmente, o mesmo não é
válido para o grafo AB, que não paresenta uma estrutura tão regular como os demais. O grafo AB
possui   um   ciclo   hamiltoniano   (13574682),   mas   os   arcos   restantes   não   formam   outros   ciclos
hamiltonianos. Note­se que a única ligaçào entre os subgrafos 1357 e 2468 é através do nó 4.
Critérios de projeto das caixas S

Segundo a IBM, o projeto das caixas S levou em conta as seguintes considerações:
∑ Não deve existir uma função linear das entradas para as saídas
∑ Se duas entradas diferem em exatamente um bit, suas saídas devem diferir ao menos em dois
bits
∑ Se duas entradas diferem em dois bits intermediários (que selecionam a coluna), suas saídas
devem diferir ao menos em dois bits
∑ Se duas entradas diferem nos dois primeiros bits e são iguais nos dois últimos bits, suas saídas
não devem ser iguais
∑ Os   4   bits   de   saída   de   uma   caixa   S   devem   ser   distribuídos   de   forma   que   dois   afetem   bits
intermediários e dois afetem bits das extremidades da caixa seguinte
∑ Os 4 bits de saída devem afetar seis caixas diferentes; não pode haver uma caixa repetida

Algorimo IDEA

O algoritmo IDEA começou a ser desenvolvido em 1990, por Xuejia Lai e James Massey, da Suiça.
Foi chamado inicialmente  de PES (Proposed Encryption  Standard). As primeiras  criptoanálises
demonstraram   alguns   pontos   fracos   potenciais,   e   os   autores   modificaram   o   algoritmo   original,
denominando a nova versão de IPES ( Improved Proposed Encryption Standard). Em 1992, o nome
foi alterado para IDEA (International Data Encryption Algorithm). Segundo vários autores, é o
algoritmo mais forte disponível atualmente em domínio público.

IDEA é um cifrador de bloco, operando sobre blocos de 64 bits de cada vez. Utiliza uma chave de
128 bits. O mesmo algoritmo básico é utilizado para cifragem e para decifragem. Existem muitos
pontos semelhantes entre DES e IDEA. Os principais são enumerados a seguir:
• Operação sobre blocos de 64 bits.
• Operação com um certo número de passos ou rodadas (16 em DES, 17 (ou 8 grupos) em
IDEA).
• Sub­chaves geradas a partir de uma chave inicial (de 56 bits em DES, e de 128 bits em IDEA).
• Cifragem e decifragem se diferenciam pela ordem de uso das sub­chaves.

Como todos os algoritmos  de chave  única, IDEA também usa confusão e difusão. No caso do

IDEA,   isto   é   obtido,   segundo   seus   autores,   “misturando­se   operações   de   grupos   algébricos
diferentes”. Existem três operações básicas (de três grupos algébricos), que manipulam quantidades
de 16 bits e que são facilmente implementadas tanto em hardware quanto em software:
• Ou­exclusivo sobre 16 bits.

• Soma em módulo de 216, ou seja, soma sempre em 16 bits, ignorando­se o carry.

• Multiplicação em módulo de 216+1, ou seja, o resto do resultado quando dividido por 216+1.
Todas estas operações atuam sobre quantidades  de 16 bits (não existe necessidade de números
maiores). Não são utilizadas permutações.

Passo elementar

IDEA usa 17 passos elementares, sendo que as operações dos passos ímpares são diferentes das
operações dos passos pares. Em cada passo, o bloco de dados de entrada de 64 bits é dividido em
quatro sub­blocos de 16 bits, denominados aqui de X1, X2, X3 e X4. Os quatros sub­blocos de
saida (denominados de X1', X2', X3' e X4'), formam a entrada para o passo seguinte. Os passos
ímpares utilizam quatro sub­chaves (Ka, Kb, Kc, Kd), enquanto que os passos pares utilizam duas
sub­chaves (Ke, Kf).

Passo ímpar

Neste passo, os novos valores dos sub­blocos X1', X2', X3' e X4' são calculados como segue:

• X1' recebe X1 multiplicado por Ka em módulo de 216+1

• X2' recebe X3 somado com Kc em módulo de 216

• X3' recebe X2 somado com Kb em módulo de 216

• X4' recebe X4 multiplicado por Kd em módulo de 216+1

Note­se que estas operações são reversíveis, ou seja, dado Xi' pode­se calcular Xi, uma vez que a
sub­chave equivalente seja conhecida. Isto é feito na operação de decifragem.

Passo par

Neste passo, os novos valores dos sub­blocos X1', X2', X3' e X4' são calculados como segue (A, B,
C, D, E e F são usados como variáveis auxiliares:
• A recebe X1 ou exclusivo X2
• B recebe X3 ou exclusivo X4

• C recebe A multiplicado por Ke em módulo de 216+1

• D recebe C somado com B em módulo de 216

• E recebe D multiplicado por Kf em módulo de 216+1

• F recebe C somado com E em módulo de 216
• X1' recebe X1 ou exclusivo E
• X2' recebe X2 ou exclusivo E
• X3' recebe X3 ou exclusivo F
 • X4' recebe X4 ou exclusivo F

A função realizada pelo passo par é a sua própria função inversa, ou seja, dado Xi calcula­se Xi', e
dado Xi' calcula­se Xi.

Geração de sub­chaves

Os 17 passos de IDEA necessitam de 52 sub­chaves (9x4 chaves + 8x2 chaves). Estas sub­chaves
são geradas a partir de uma chave de 128 bits, e a geração é diferente para a cifragem e para a
decifragem.

Sub­chaves para cifragem

As primeiras  8 sub­chaves  (K1 a  K8) são simplesmente  obtidas  da chave,  da esquerda  para a

direita, agrupando­se os bits de 16 em 16. A chave é então rotacionada 25 bits para a esquerda (com
os bits mais significativos sendo realimentados para os mais significativos). As próximas 8 sub­
chaves (K9 a K16) são então obtidas como as primeiras, ou seja, agrupando­se os bits de 16 em 16,
da esquerda para a direita. O processo é repetido até que 52 sub­chaves tenham sido geradas. Estas
sub­chaves são então utilizadas nos diversos passos do algoritmo, em ordem. O passo 1 usa as
chaves K1 a K4, o passo 2 usa as chaves K5 e K6, o passo 3 usa as chaves K7 a K10, e assim por
diante, até o passo 17, que usa as chaves K49 a K52.

Sub­chaves para decifragem

A decifragem usa exatamente as mesmas operações que a cifragem, mas as sub­chaves devem ser
usadas em ordem inversa (usam­se primeiro as chaves K52, K51, K50 e K49). Além disto, em cada
passo ímpar, deve­se usar os inversos multiplicativos e aditivos, a fim de reverter as operações (Isto
não é necessário nos passos pares).
• Ou exclusivo: se Xi' é o resultado do ou exclusivo entre Xi e Ki, então calcula­se Xi através do
ou exclusivo entre Xi' e Ki.

• Soma: se Xi' é o resultado da soma Xi + Ki em módulo de 2 16, então calcula­se Xi através da
subtração  Xi' – Ki (também em módulo de 216).

• Multiplicação:  se Xi' é o resultado da multiplicação  Xi * Ki em módulo de 216+1, então,

calcula­se Xi através da operação  Xi' * Ki­1 (também em módulo de 216+1). Note­se que Ki­1
é o inverso multiplicativo de Ki, em módulo de 216+1. Em aritmética normal, se Ki é um
inteiro, então Ki­1 seria uma fração. Mas em aritmética de módulo, Ki ­1 também é um número
inteiro, tal que (Ki * Ki­1) mod 216+1 = 1. Por exemplo, para aritmética de módulo 7,  tem­se
que 1­1 = 1, 2­1=4, 3­1=5, 4­1=2, 5­1=3, 6­1=6. Como 216+1 é um número primo, garante­se que
todos os números até 216 tem um inverso multiplicativo.
Assim, antes de iniciar a decifragem, devem­se calcular os inversos multiplicativos daquelas sub­
chaves envolvidas em operações de multiplicação.

Diversos outros algoritmos de cifragem de blocos com chave única foram e estão sendo propostos.
A lista a seguir indica os mais comumente encontrados na literatura.
• Triple­DES: um método onde o DES é aplicado três vezes. Inicialmente cifra­se com uma
chave K1, depois decifra­se com uma chave K 2 e a seguir cifra­se novamente com a chave K 1.
Para a decifragem, usam­se os passos na ordem inversa, ou seja, decifra­se com K 1, cifra­se
com K2 e decifra­se com K1. O método da força bruta necessitaria então de 2112 tentativas.

• Lucifer: desenvolvido pela IBM no início dos anos 70, foi usado como base do DES e depois
desenvolveu­se separadamente. Em sua versão atual de 128 bits, ainda  é considerado mais
fraco   que   o   DES,   podendo   ser   quebrado   com   2 33  tentativas   de   um   ataque   do   tipo   texto
escolhido.
• Madryga: desenvolvido em 1984, trabalha com blocos de 8 bits, e não utiliza transposições.
Suas operações estão baseadas em ou­exclusivo e deslocamento de bits, e é considerado bem
fraco, pois não apresenta o efeito avalanche (o fato da mudança de um bit no texto normal
modificar metade dos bits no texto cifrado).
• NewDES: desenvolvido em 1985, é baseado no DES, utilizando blocos de 64 bits e uma chave
de 120 bits. É orientado a byte, não realizando em nenhum momento operações sobre bits
individuais. Pelas análises realizadas até o momento, é um pouco mais fraco que o DES.
• FEAL­N: projetado para ser mais simples e operar mais rápido que o DES, possui um número
variável de passos (o N do nome). Trabalha com blocos e chave de 64 bits, mas é muito fraco
se usado com menos de 8 passos. FEAL­4 pode ser quebrado com 5 textos escolhidos, FEAL­6
com 100 textos escolhidos e FEAL­8 com 215 textos escolhidos.
• REDOC   II   e III: desenvolvidos   para  operarem  somente   com  bytes,  e assim  poderem   ser
facilmente implementados em software, estes dois algoritmos são bem distintos. REDOC II
usa substituições, transposições e ou­exclusivo sobre blocos de 80 bits usando uma chave de
160 bits. É considerado bem seguro. Por outro lado, REDOC III usa somente ou­exclusivos
sobre um bloco de 64 bits e uma chave de tamanho variável (até 2560 bytes) e, apesar de ainda
não analisado a fundo, aparenta ser muito fraco.
• LOKI: desenvolvido na Austrália em 1990, é muito semelhante ao DES, trabalhando com
blocos   e   chave   de   64   bits.   Possui   duas   versões,   LOKI89   e   LOKI91,   sendo   a   primeira
considerada fraca. Não é patenteado.
• Khufu e Khafre: projetados por Ralph Merkle com os nomes de dois faraós egípcios, ambos
algoritmos pretendem, segundo o autor, eliminar alguns dos pontos fracos do DES. Trabalham
de forma semelhante ao DES, mas com tabelas de substituição de 256 posições de 32 bits,
contra as de 6 posições de 4 bits do DES. Usam chaves de 512 bits e um número de passos
flexível (múltiplos de 8). Enquanto Khufu usa a chave para gerar estas tabelas, e não pode ser
atacado exceto por força bruta, Khafe usa tabelas fixas e é muito mais fraco (uma versão de 16
 passos pode ser quebrada com 1500 tentativas em um ataque de texto escolhido; uma versão de
24 passos requereria 253 tentativas para o mesmo ataque).
• MMB: (Modular Multiplication­based Block cipher) apresentado em 1993, usa praticamente
as mesmas operações de IDEA, mas trabalha com blocos de 128 bits, chave de 128 bits e sub­
blocos de 32 bits (sobre os quais são realizadas operações de ou­exclusivo e multiplicação).
Ainda não foi analisado.
• Skipjack: desenvolvido pela NSA de 1985 a 1990, usa uma chave de 80 bits e realiza 32
passos de processamento para cifragem ou decifragem. Maiores informações são classificadas
como   secretas.   Este   algoritmo   deve   ser   implementado   nos   circuitos   integrados   Clipper   e
Capstone, também da NSA.

5 Cifragem de blocos

Um algoritmo que realiza a cifragem sobre blocos pode operar de diversas maneiras distintas, que
lhe conferem propriedades diferentes, quer quanto a sua robustez contra criptoanálise, quer quanto
a recuperação de erros.

Modo do Livro de Códigos (Electronic Code Book)

Este modo, denominado abreviadamente de ECB, é a maneira mais óbvia e a mais simples de um
cifrador de blocos ser utilizado. Cada bloco da mensagem normal é individual e independentemente
cifrado para produzir os blocos da mensagem cifrada. O bloco típico tem atualmente 64 bits, o que
produz   um   livro   de   códigos   de   264  entradas,   o   que   é   complexo   o   suficiente   para   dificultar   a
criptoanálise. E note­se que para cada chave possível existe um livro de códigos diferente.

A grande vantagem deste método é exatamente sua simplicidade e a independência entre os blocos.
Não é necessário decifrar um arquivo inteiro caso somente se deseje modificar alguns registros (isto
é particularmente útil para bancos de dados). Além disto, um erro ou uma modificação intencional
de alguns bits somente afetam o bloco ao qual os bits pertencem. Os demais blocos permanecem
intactos.

Entretanto, a principal desvantagem reside no fato de um criptoanalista poder começar a compilar
um livro de códigos, mesmo sem conhecer a chave. Na maioria das aplicações práticas, diversos
trechos   de   mensagens   tendem   a   se   repetir.   Estruturas   de   dados   manipuladas   e   geradas
automaticamente por computadores possuem uma estrutura regular (como o cabeçalho de correio
eletrônico,   por   exemplo)   ou   apresentam   um   grande   número   de   zeros   binários.   Assim,   se   o
criptoanalista   descobre   que   o   bloco   “5edg1m32”   quando   cifrado   representa   “7ea8mde0”,   ele
consegue   decifrar   instantaneamente   este   bloco,   onde   quer   que   ele   apareça.   Se   um   programa
aplicativo gera informações com um grande grau de redundância, com poucas entradas no livro de
códigos já é possível realizar um ataque complexo. Esta vulnerabilidade é maior no início e no fim
das mensagens uma vez que estes trechos tendem a ser estereotipados.
Um problema mais sério que ocorre no método ECB é a chamada  repetição de bloco, onde um
atacante ativo pode modificar mensagens de forma consistente mesmo sem saber a chave ou o
conteúdo que foi modificado. Para ilustrar este caso, suponha­se um sistema de transferência entre
bancos que utilize ECB. As informações estão distribuídas em diversos campos, e pode ocorrer que
alguns campos (ou grupo de campos) mapeiem exatamente para um número inteiro de blocos. Isto
não é muito difícil de ocorrer, já que os computadores trabalham normalmente com comprimentos
baseados em potências de dois. Imagine­se agora um atacante passivo, que consegue monitorar as
transferências bancárias e determinar em quais blocos está contida a informação do beneficiário da
transferência. Basta agora o atacante realizar, através de dois bancos, uma transferência onde ele é o
beneficiário  e assim  obter uma  cópia  (cifrada)  destes  blocos.  Como ele   é o beneficiário,  estes
blocos contém informação a seu respeito. Realizando agora um ataque ativo, basta interceptar uma
transferência, substituir o conteúdo do campo do destinatário pelos blocos copiados e assim receber
uma grande série de depósitos. Note­se que é irrelevante o conteúdo dos outros blocos (depositário,
quantia, etc). Mesmo o balanço diário dos bancos não conseguirá detectar o problema, pois todas as
transações   se   compensam   mutuamente.   Somente   quando   os   destinatários   reais   começarem   a
reclamar é que o problema será detectado.

Modo de Encadeamento de Blocos (Cipher Block Chaining)

Para evitar os problemas do modo ECB, o modo CBC realimenta a cifragem do bloco atual com os
resultados da cifragem dos blocos anteriores. A operação mais utilizada é o ou­exclusivo: o bloco
cifrado Ci­1 é operado através de um ou­exclusivo com o bloco normal M i, e somente depois este
bloco é cifrado. Assim, ao invés de calcular Ci = E(Mi, Ke), calcula­se Ci = E(Mi xor Ci­1,Ke). Com
isto, cada bloco cifrado sofre a influência dos blocos anteriores, e dois blocos iguais serão cifrados
para blocos distintos, caso no mínimo um dos blocos anteriores seja diferente nas duas mensagens.

Caso não ocorram blocos diferentes, entretanto, o problema ainda persiste. Duas mensagens iguais
serão cifradas para os mesmos blocos. E duas mensagens que possuam um início idêntico serão
cifradas   da   mesma   maneira   até   que   ocorra   a   primeira   diferença.   A   maneira   empregada   para
contornar este problema é a inclusão de um vetor de inicialização (IV) distinto para cada mensagem
a ser cifrada. Este vetor não necessita ter qualquer significado, pode ser randômico e pode ser
descartado assim que a mensagem for decifrada. Com o bloco inicial distinto garantido pelo IV,
mesmo duas mensagens iguais serão cifradas para blocos diferentes.

Para a decifragem, deve­se reverter o processo. Para o primeiro bloco, vale:
cifragem: C1=E(M1 xor IV,K)
decifragem: M1 = IV xor D(C1,K) = IV xor D(E(M1 xor IV),K),K) = IV xor M 1 xor IV =
M1

Para os demais blocos, tem­se:
cifragem: Ci = E(Mi xor Ci­1,K)
 decifragem: Mi = Ci­1 xor D(Ci,K) = Ci­1 xor Mi xor Ci­1 = Mi

O  uso do encadeamento,  entretanto,  se por um lado  aumenta  a segurança  contra  criptoanálise,

diminui a tolerância a erros. No modo ECB, um erro em um bloco fica restrito a este bloco, mas no
modo CBC um erro em um bloco é realimentado para o bloco vizinho. Caso um bloco cifrado tenha
um único bit alterado, isto afetará a decifragem deste bloco e do seguinte. O bloco atingido será
completamente afetado (pelo efeito avalanche dos métodos de cifragem, metade dos bits do bloco
decifrado serão afetados, o que mascara toda a informação contida neste bloco). O bloco decifrado
seguinte apresentará um bit em erro, na mesma posição onde o erro original ocorreu. Os demais
blocos serão decifrados sem erro. Assim, o modo CBC é auto­recuperável para erros de inversão de
bits. Para erros de perda de bits, entretanto, o efeito pode ser catastrófico, afetando todos os blocos
seguintes.

Modo de Realimentação de Cifra (Cipher FeedBack)

No modo CBC, assim como no ECB, a cifragem não pode iniciar até que um bloco seja formado.
Isto pode ser um problema para aplicações de rede, onde por exemplo os caracteres de um terminal
devem ser enviados para o computador destino a medida em que forem sendo digitados. Quando os
dados devem ser separados em grupos menores que um bloco, a solução é empregar o modo CFB.
A realimentação é realizada da mesma maneira, através de uma operação ou­exclusivo, mas agora
somente sobre o grupo, e não mais sobre todo o bloco. A figura 4 ilustra o caso para grupos de 8
bits e blocos de 64 bits. O método é o mesmo para outros tamanhos de grupos (até mesmo para
grupos de um bit).

Um registrador de deslocamento é preenchido com um valor inicial de 8 bytes, como o vetor IV no
caso CBC. Este valor é cifrado, e o byte mais a esquerda (c i­1) é operado com o byte mi  a ser
cifrado, ci = ci­1 xor mi. O valor ci é ser transmitido, os oitos bytes do registrador de deslocamento
são deslocados para esquerda, sendo o byte mais a esquerda descartado e o byte vago mais a direita
preenchido com ci. A decifragem é o processo reverso, com o byte recebido (c i) sendo operado com
ci­1  para restabelecer mi. O deslocamento entretanto se realiza da mesma maneira, ou seja, c i  é
deslocado para a posição mais a direita do registrador.
 Figura 14 – Modo de realimentação de cifra de 8 bits

O efeito de um bit em erro no texto cifrado (ci) é bem interessante. Inicialmente, produz­se um erro
em um bit no texto decifrado pi. Depois que o grupo em erro entra no registrador de deslocamento,
ele   vai   afetar   todos   os   grupos   subsequentes,   até   sair   do   registrador.   Os   demais   grupos   serão
decifrados sem erro.
Modo de Realimentação de Saída (Output FeedBack)

O modo OFB é bem similar ao CFB, com a diferença que agora o grupo c i­1 é realimentado, e não
mais o grupo do texto cifrado. A figura 5 ilustra o caso para grupos de 8 bits e blocos de 64 bits.

Figura 15 – Modo de realimentação de saída de 8 bits
Este   método   é   muitas   vezes   denominado   de   realimentação   interna,   porque   o   mecanismo   de
realimentação   é   independente   dos   textos   normal   e   cifrado.   O   grande   benefício   do   OFB   é   sua
imunidade a erros. Um erro no texto cifrado produz um único erro no texto normal. Não existe
nenhuma propagação do erro.

Modo de Encadeamento de Blocos (Block Chaining)

Neste   modo,   a   entrada   do   cifrador   é   operada   (com   um   ou­exclusivo)   ou­exclusivo   com   o   ou­
exclusivo de todos os blocos cifrados anteriormente. Matematicamente tem­se:
• Ci = E (Mi xor Fi, Ke) Fi+1 = Fi xor Ci

• Mi = Fi xor D (Ci, Kd) Fi+1 = Fi xor Ci

O valor inicial de F0 é o vetor de inicialização. O problema principal com o modo BC é o fato de
um erro em um bloco cifrado ser estendido a todos os blocos decifrados seguintes. Para resolver
isto, pode­se incluir um bloco padrão de verificação no fim da mensagem

Modo de Encadeamento com propagação (Propagating Cipher Block Chaining)

No modo PCBC, a entrada do cifrador é operada (com ou­exclusivos) com os blocos normal e
cifrado anteriores. Matematicamente tem­se:
• Ci = E (Mi xor Ci­1 xor Mi­1, Ke)

• Mi = Ci­1 xor Mi­1 xor D (Ci, Kd)

Um erro em um bloco cifrado é estendido a todos os blocos decifrados seguintes. Mas o problema
principal com este modo é o fato de uma eventual troca de ordem nos blocos cifrados provoca erro
na decifragem deste blocos, mas devido a natureza da operação ou­exclusivo, estes erros vão se
cancelar e não são detectados examinando­se o bloco padrão final. Este modo havia sido sugerido
para o Kerberos (uma metodologia de autenticação) na sua versão 4, mas foi substituído pelo modo
CBC na versão 5 quando a característica acima foi descoberta.

Modo de Encadeamento com verificação (Cipher Block Chaining with Checksum)

O modo CBCC é idêntico ao modo CBC. Adicionalmente, entretanto, todos os blocos normais são
operados   entre   si   através   de   um   ou­exclusivo.   Ao   fim   de   toda   a   cadeia,   tem­se   um   bloco   de
checksum: 

S = M1 xor M2 xor M3 xor . . . xor Mi­1 xor Mi xor Mi+1 xor . . . . xor Mn­1 xor Mn

O bloco S pode ser usado para adiconar informação de checksum ao texto cifrado.
6 Cifragem de fluxo

Um algoritmo que converte uma mensagem normal para a mensagem cifrada um bit de cada vez é
chamado de cifrador de fluxo (stream cipher). Sua estrutura simplificada é mostrada na figura 5.
 
Figura 5 – Criptosistema de fluxo

Os bits  mi  da mensagem a ser cifrada são operados através de um ou­exclusivo com os bits  ki

produzidos por um gerador de fluxo a partir de uma chave K, produzindo assim um fluxo de bits
cifrados  ci  =  mi  xor  ki. Para  a  decifragem   usa­se exatamente  o  mesmo  método,  restaurando   a
mensagem, pois mi = (mi xor ki) xor ki. Naturalmente, os dois geradores de fluxo devem produzir
exatamente a mesma sequência de bits, quando alimentados com a mesma chave K. Assim, os
geradores de fluxo devem ser determinísticos. Por outro lado, a sequência gerada deve ser pseudo­
randômica, de um período grande, de forma a fornecer ao método uma boa segurança: se o gerador
produzir uma sequência de zeros (ou uns), todas as demais operações ficam sem sentido. E se a
sequência for curta (por exemplo, 16 bits), o método se transforma em um simples  XOR com
baixíssima segurança. Idealmente o gerador deveria produzir uma sequência randômica infinita,
mas todas as implementações práticas utilizam sequências pseudo­randômicas periódicas.

A diferença entre cifradores de bloco e de fluxo é mais de caráter prático do que teórico. Cifradores
de fluxo trabalham com um bit de cada vez, e por causa disto não são facilmente implementáveis
em software. Cifradores de blocos podem ser implementados mais facilmente, mas suas operações
são   mais   complexas   e   demoradas.   Em   termos   de   criptografia,   cifradores   de   bloco   são   mais
utilizados, e os seus algoritmos podem ser modificados para se tornarem mais seguros. Por outro
lado, cifradores de fluxo são mais fáceis de serem analisados matematicamente.

A escolha final é determinada pela aplicação. Se ela pode trabalhar com blocos de dados, então
normalmente   se   utilizam   cifradores   de   bloco.   Por   outro   lado,   se   os   bits   devem   ser   cifrados
continuamente, a medida que forem sendo produzidos, e uma blocagem pode introduzir demoras
não toleráveis, então deve ser utilizado um cifrador de fluxo.

7 Criptografia computacional de chave pública

O conceito de criptosistemas de chave pública, ou chaves assimétricas, foi introduzido em 1976 por
Whitfield  Diffie e Martin Hellman  [DIF76] e independentemente  por Ralph Merkle. Até então
aceitava­se  como  fato  natural   que as   chaves   de  cifragem   e decifragem,   quer fossem  iguais   ou
diferentes, deveriam ambas ser mantidas secretas. E um dos grandes problemas era justamente o da
distribuição de chaves por canais inseguros, o que exigia um protocolo complexo e uma grande
quantidade de troca de dados.
Nos criptosistemas de chave pública, uma das chaves é de conhecimento público, e somente a outra
é que deve ser mantida secreta. O problema de distribuição de chaves é eliminado, pois as chaves
públicas podem circular livremente, e não existe nenhuma necessidade de enviar a chave secreta a
qualquer outro participante do sistema. Para este sistema ser viável, cada um dos participantes deve
ser capaz de gerar seu par de chaves Ke e Kd com as seguintes propriedades:

1 Se C = E ( M, Ke), então M = D ( C, Kd ) para todos M.

2 É computacionalmente intratável tentar deduzir Kd a partir de Ke.

3 É computacionalmente tratável calcular um par Kd e Ke que satisfaça os dois requisitos acima.

Dentro destes requisitos, nada impede que K e seja tornada pública. E a existência de um sistema
deste   tipo   permite   uma   comunicação   segura   e   instantânea   entre   participantes   que   nunca   se
encontraram nem se comunicaram antes. Supondo que o usuário A queira enviar uma mensagem
para o usuário B. Ele somente necessita cifrar sua mensagem com a chave pública de B, ou seja, ele
calcula C = E(M,KeB). Para decifrar a mensagem após seu recebimento, B simplesmente calcula M
= D(C,KdB). Como nenhum outro participante conhece KdB, ninguém mais consegue decifrar a
mensagem, a não ser seu destinatário legítimo.

Todos os algoritmos de chave pública propostos ao longo do tempo baseiam­se em problemas NP­
completos para garantir o requisito (2) acima. Destes, o mais fácil de compreender e ao mesmo
tempo um dos mais robustos é o RSA, assim denominado pelos seus três autores, Ron Rivest, Adi
Shamir e Leonard Adelman [RIV78].

O   RSA   obtém   sua   segurança   da   dificuldade   de   fatorar   números   grandes.   As   chaves   pública   e
privada são funções de um par de números primos grandes (entre 100 a 200 dígitos decimais). Para
gerar as duas chaves, escolhe­se inicialmente dois números primos, p e q, com a propriedade acima.
A seguir calcula­se n = p x q. Então escolhe­se randomicamente um número e, tal que e e (p–1)x(q–
1) sejam primos entre si, ou seja, não tenham fatores comuns. Depois, calcula­se um número d tal
que (e x d) módulo (p–1)x(q–1) seja igual a 1, ou seja, e x d = 1 mod (p–1)x(q–1). Os números e e n
formam a chave pública; os números  d  e n  são a chave privada. Os números  p e  q não são mais
necessários e devem ser esquecidos.

Para cifrar uma mensagem M, primeiro divide­se esta mensagem em blocos de  t  bits, onde  t  é

calculado de tal forma que o valor numérico de cada bloco (o valor obtido interpretando­se a sua
cadeia de bits como um número) seja menor que  n. Em termos práticos, utiliza­se o maior valor
para t de tal forma que a condição 2t < n ainda seja satisfeita. Sob o ponto de vista decimal, se n
tiver 200 dígitos, então cada bloco mi também terá cerca de 200 dígitos, mas sempre de forma que
mi < n. A mensagem cifrada C também será formada por blocos ci, cada um calculado por ci = mie
mod n, ou seja eleva­se o bloco numérico mi a potência e, em aritmética módulo n.
Para decifrar a mensagem C, basta tomar cada bloco numérico cifrado ci e calcular mi = cid mod n,
ou seja, eleva­se ci a potência d, em aritmética módulo n. Já que nesta aritmética módulo n, devido
à escolha de d e e, tem­se que cd = (me)d = med = mk(p­1)(q­1)+1 = mx1 = m, a fórmula recupera a
mensagem. Note­se que a mensagem poderia, da mesma forma, ser cifrada com d e decifrada com
e, a escolha é arbitrária.

A segurança do RSA está baseada no problema de fatorar números grandes. Embora na prática o
melhor caminho para deduzir d a partir de n e e seja fatorar n para determinar os números p e q,
tecnicamente ainda não foi provado que este é o único caminho. É perfeitamente admissível que
uma maneira alternativa de criptoanalisar o RSA possa ser descoberta. Entretanto, se uma nova
técnica permitisse calcular d, ela também poderia ser utilizada para fatorar grandes números, e este
problema vem sendo analisado a vários séculos, sem que tenha sido encontrada uma solução que
não envolvesse um crescimento exponencial da complexidade. No presente momento, o melhor
algoritmo de fatoração tem um tempo de solução na ordem de O(esrqt(ln n x ln(ln n))). Se n tem 200
dígitos (aproximadamente 664 bits), a fatoração levará na ordem de 2,7x1023 passos. Assumindo­se
um computador que possa realizar um milhão de passos por segundo (uma suposição generosa,
dada a magnitude dos números envolvidos), levará 3,8x109  anos para a fatoração. Mesmo que o
poder computacional aumente um milhão de vezes, a fatoração ainda consumiria 4 milhões de anos.
E se mais segurança for necessária, basta aumentar n por alguns bits.

Um dos outros fatores que determinam a popularidade do RSA é o fato de ele também poder ser
usado para assinatura digital; mais detalhes a respeito serão apresentados na seção 8. Muitos outros
métodos criptográficos de chave pública vendo sendo propostos. A lista a seguir indica os mais
comumente encontrados na literatura. Nem todos se destinam a cifragem de mensagens. Alguns
orientam­se mais à distribuição de chaves, outros somente para assinatura digital. Todos algoritmos
são lentos, o que torna muito lenta a cifragem e decifragem de uma grande quantidade de dados.
• Diffie­Hellman:   o   primeiro   método   de   chave   pública   proposto,   destina­se   a   resolver   o
problema da distribuição de chaves, e não pode ser usado para cifragem de mensagens. Baseia­
se na operação X = gx mod n, onde g e n são públicos (assim como X, que é transmitido) e x é
secreto. O valor x é usado como base para calcular uma chave comum a ser usada entre dois
participantes. Para determinar x a partir de X, g e n, é necessário computar o logaritmo discreto
de X na base g em módulo n, o que é um problema NP completo. É descrito em [DIF76].
• Método da Mochila (Knapsack): desenvolvido por Merkle e Hellman a partir do problema da
mochila: dados uma série de pesos de valores distintos, quais devem ser colocados em uma
mochila para que se obtenha um determinado peso total?. Uma mensagem é cifrada como uma
solução para uma série de problemas da mochila, um que pode ser resolvido em tempo linear
(o   problema   da   mochila   super­crescente,   onde   cada   peso   é   maior   que   a   soma   dos   seus
antecessores) e outro que tem complexidade NP (onde os pesos possuem valores quaisquer). O
problema NP é a chave pública, utilizada para cifragem. O problema linear é a chave privada.
Em teoria, somente quem tem a chave privada consegue resolver o problema (e decifrar a
mensagem)   em   tempo   razoável;   atacantes   necessitam   resolver   o   problema   complexo.   Na
 prática, entretanto, o método já foi quebrado. Descrições podem ser encontradas em [BOR94],
[LEI82], [SCH92].
• Pohlig­Hellman: muito  semelhante  ao RSA, mas  não exige  que  n  seja  o produto de  dois
primos.   Não   é   um   algoritmo   simétrico,   pois   usa   chaves   diferentes   para   a   cifragem   e
decifragem, mas também não é um algoritmo de chave pública, pois ambas chaves devem ser
mantidas secretas. Pode ser encontrado em [POH78].
• Rabin:   este   método   retira   sua   segurança   da   dificuldade   de   se   extrair   raiz   quadrada   em
aritmética de módulo de um número composto. Inicialmente são escolhidos dois primos, p e q,
ambos congruentes a 3 módulo 4, ou seja, p mod 4 = q mod 4 = 3. Estes primos são a chave
privada; o produto n = p x q é a chave pública. Para cifrar uma mensagem M, calcula­se C =
M2 mod n. Para decifrar a mensagem, calcula­se quatro possibilidades: M  = C(p+1)/4 mod n;
1

M2 = p – C(p+1)/4 mod n; M3 = C(q+1)/4 mod n; e M4 = q – C(q+1)/4 mod n. Uma destas
quatro mensagens será igual a M, as outras três terão conteúdo randômico. Se a mensagem M
for textual, isto não representa um problema maior, mas é impossível aplicar este método se as
mensagens forem compostas de padrões binários. É descrito em [WIL80].
• Feige­Fiat­Shamir: um método para assinatura digital e para identificação com conhecimento
zero   (zero­knowledge   proof   of   identity),   é   composto   por   uma   série   de   algoritmos,   todos
baseados em resíduos quadráticos módulo n. O número n é o produto de dois primos, deve ter
entre 512 a 1014 bits e é compartilhado entre todos os participantes. Um participante em parti­
cular escolhe um número v que seja um resíduo quadrático modulo n, ou seja, x2 = v mod n
tem uma solução e 1/v mod n existe. Esta é a chave pública. A seguir calcula­se o menor s para
o qual s = sqrt(1/v) mod n. Esta é a chave privada. As chaves não são usadas para criptografia,
mas   sim   para   implementar   um   protocolo   de   identificação   através   de   credenciamento:   o
processo é repetido tantas vezes entre dois participantes até que cada um esteja convencido de
que o outro é quem diz ser. Isto é feito utilizando­se operações para as quais é necessário (mas
não obrigatório) o conhecimento de s. No primeiro passo, um intruso tem 50% de chances de
acertar, mas após t passos estas chances estão reduzidas a 1/2t. É descrito em [SCH96].
• Guillou­Quisquater: um método de identificação com conhecimento zero. Cada participante
possui um bloco de bits J, que é público e equivale a suas credenciais e outro bloco B, que é
secreto e calculado de forma que JBv mod n = 1. Os números v e n são compartilhados, e n é
produto de dois primos secretos. O participante que deseja se identificar envia J e a seguir é
executado um protocolo destinado a provar que este participante conhece o B equivalente. Este
protocolo é executado em um único passo, e assim é bem rápido.
• Ong­Schnorr­Shamir: um método de assinatura digital baseado em polinôminos módulo n. O
número n deve ser grande, mas não é necessário conhecer sua fatoração. A seguir escolhe­se
um número k qualquer, que seja primo em relação a n. Calcula­se então h = –(k­1)2 mod n. A
chave pública são h e n; a chave privada é k. Uma mensagem M é assinada calculando­se um
par de números S1  = 1/2  x  (M/r  +  r)  mod  n  e S2  = k/2 x (M/r  –  r) mod  n. Para verificar a
 assinatura, comprova­se que M = (S12 + h x S22) mod n. Este método já foi quebrado, tanto
para polinômios quadráticos como cúbicos e de potência 4. É citado em [SCH96].
• ElGamal: um método capaz de realizar cifragem e assinatura digital. Sua segurança é baseada
na dificuldade de cálculo de logaritmos discretos e aritmética de módulo. Para gerar um par de
chaves, deve­se escolher um número primo p e dois números quaisquer g e x, ambos menores
que  p. Então calcula­se  y =  gx  mod p. A chave pública é  y,  g e  p, e a chave secreta é  x. Os
números  g  e  p  podem ser compartilhados por um grupo de participantes. Assim como RSA,
ElGamal   é um dos  poucos  métodos  que pode ser usado tanto  para  cifragem  como  para a
assinatura de mensagens (veja­se a seção 8 para maiores detalhes, assim como [ELG85]).
• Schnorr: um método utilizado para identificação (credenciamento) e assinatura digital, baseia­
se também na dificuldade de cálculo de logaritmos discretos. O método inicialmente escolhe
dois primos, p e q, tal que q é um fator primo de (p–1). Depois escolhe­se um a (maior que 1)
tal que aq mod p = 1. Todos estes números são públicos e podem ser compartilhados por um
grupo de participantes. Para gerar um par de chaves, escolhe­se um número qualquer s menor
que q. Esta é a chave privada. Calcula­se então  v = a–s mod p. Esta é a chave pública. Com
estas chaves, pode­se implementar um protocolo de autenticação e um algoritmo de assinatura
digital.
• DSA: (Digital Signature Algorithm) é o algoritmo proposto pelo NIST (National Institute of
Standards and Technology) para uso no padrão DSS (Digital Signature Standard). Como seu
nome indica, foi desenvolvido exclusivamente para assinatura digital, e não pode ser usado
para cifragem. Utiliza os seguintes elementos: um número primo p com comprimento entre 512
e 1024 bits; um número q de 160 bits, que seja um fator primo de (p–1); um número g = h(p–
1)/q, onde  h  é qualquer número menor que  p–1 de forma que  h(p–1)/q  mod  q  > 1. Estes três

números   podem   ser   compartilhados   entre   diversos   participantes.   Para   uma   chave   privada
escolhe­se um número x, menor que q. Para a chave pública, calcula­se y = gx mod p (veja­se a
seção 8 para maiores detalhes, assim como [NIS92]).
• ESIGN: um método de assinatura digital, que utiliza dois números primos grandes (mais de
192 bits), p e q. Estes números são a chave privada. A chave pública é n = p2 x q. O método
necessita de uma função de hash, H(x). Para tornar o método mais seguro, também é necessário
o uso de k, um parâmetro de segurança. Maiores detalhes podem ser encontrados em [SCH96].
• LUC:   um   dos   métodos   de   cifragem   mais   recente,   difere   dos   demais   por   não   empregar
exponenciação, mas sim utilizar séries de Lucas. Nestas séries, tem­se que, para dois inteiros P
e Q, os elementos Vi da série V(P,Q) são definidos como V0 = 2, V1 = P, e Vi+1 = P.Vi–Q.Vi–
1. No método LUC, como no RSA, utiliza­se um número  n,  produto de dois primos, e duas
chaves de cifragem  e e de decifragem  d. A chave  e é pública e d é privada. Para cifrar uma
mensagem M, calcula­se C = Ve(M,1) mod n, ou seja, o resíduo módulo n do e­ésimo termo da
série definida for V(M,1). Para decifrar calcula­se M = V d(C,1) mod  n.  Basicamente, LUC
substitui   a   exponenciação   do   RSA   pelo   cálculo   de   séries   de   Lucas.   Detalhes   podem   ser
encontrados em [SMI93] e [BOR94].
8 Assinatura digital

Nos sistemas de criptografia de chave pública, qualquer pessoa pode cifrar uma menagem, mas
somente o destinatário desta mensagem pode decifrá­la. Isto é obtido justamente pelo uso de duas
chaves: uma pública, para cifragem, disponível para qualquer um, e outra privada, para decifragem,
conhecida apenas por uma pessoa. Mensagens cifradas pela chave pública somente poderão ser
decifradas pela chave privada. Invertendo a ordem de uso das chaves, obtém­se uma mensagem que
só pode ser cifrada por uma pessoa, mas pode ser decifrada por qualquer um. Naturalmente, não se
pode falar em privacidade ou segredo neste caso, mas obtém­se um efeito de personalização do
documento (somente uma pessoa pode tê­lo cifrado), semelhante a uma assinatura. Um sistema
deste tipo é denominado de assinatura digital.

Sistemas  de chave única também poder ser utilizados  para realizarem as funções de assinatura

digital (normalmente com o uso de um árbitro), mas nos criptosistemas de chave pública a geração
de assinaturas digitais é muito mais direta. Supondo que o usuário A queira enviar uma mensagem
assinada para o usuário B. Ele somente necessita aplicar na sua mensagem a sua chave privada, ou
seja, ele calcula C = S(M,KprivA), onde S é o algoritmo de assinatura. Para decifrar a mensagem
após   seu   recebimento,   B   simplesmente   calcula   M   =   V(C,K pubA),   onde   V   é   o   algoritmo   de
verificação. Pelo fato da chave pública de A ter conseguido restaurar a mensagem, isto significa
que somente A pode tê­la enviado. Naturalmente, qualquer outro participante também dispõe de
KpubA, e qualquer um também pode restaurar M. Mas o objetivo é individualizar a mensagem, e
não torná­la secreta.

Um sistema de assinatura digital possui as seguintes propriedades:
• a assinatura é autêntica: quando o usuário B usa KpubA (a chave pública de A), ele confirma
que foi A e somente A quem assinou a mensagem.
• a assinatura não pode ser forjada: somente A conhece sua chave privada KprivA, e ninguém
mais pode assinar o documento no lugar de A.
• o documento assinado não pode ser alterado: se houver qualquer modificação em C, ele não irá
mais ser restaurado para M com o uso de KpubA (a chave pública de A).

• a   assinatura   não   é   reutilizável:   a   assinatura   é   uma   função   do   documento   e   não   pode   ser
transferida para outro documento.
• a assinatura não pode ser repudiada: o usuário B não necessita de nenhuma ajuda de A para
verificar a assinatura de A, ou seja, o usuário A não pode posteriormente negar ter assinado o
documento.

Existem  muitos  métodos  de assinatura digital.  Todos eles  são criptosistemas  de chave  pública:

existe uma informação secreta que somente um participante conhece e que ele usa para assinar as
mensagens,   e   existe   uma   informação   pública   que   todos   conhecem   e   usam   para   verificar   a
assinatura.   Muitas   vezes   o   processo   de   assinatura   é   denominado   de   “cifragem   com   a   chave
privada”,   e   o   processo   de   verificação   é   chamado   de   “decifragem   com   a   chave   pública”.
Formalmente isto não é correto, uma vez que só é verdadeiro para um único método (o RSA,
justamente   o   mais   conhecido   e   que   combina   cifragem   e   assinatura).   Outros   métodos   usam
algoritmos   distintos   para   cifragem   e   para   assinatura,   e   uma   grande   maioria   deles   somente
implementa   assinatura,   e   não   cifragem.   Por   isto   deve­se   usar   a   função   S(M,   K privada)   para
representar a assinatura de uma mensagem M com uma chave privada, e a função V(C,Kpública)
para representar a verificação de uma mensagem assinada C com uma chave pública.

No   método   RSA,   tem­se   que   E(D(M,Kq),Ke)   =   M,   em   adição   a   propriedade   usual   de   que

D(E(M,Ke),Kd) = M. Isto permite  que ele seja utilizado  sem modificações  tanto para cifragem
como para assinatura, e inclusive para ambas funções na mesma mensagem, conforme ilustrado a
seguir. Na Tabela 1 encontra­se o resumo do método RSA.
• Cifragem:   se   A   quer   enviar   uma   mensagem   cifrada   para   B,   ele   calcula   C   =   E(M,K eB),
utilizando a chave pública de B. O usuário B restaura a mensagem calculando M = D(C,K dB),
usando sua chave privada. Neste caso D(E(M,KeB),KdB) = M.

• Assinatura: se A quer enviar uma mensagem assinada para B, ele calcula C = D(M,K dA),
utilizando sua chave privada. O usuário B verifica a mensagem calculando M = E(C,K eA),
usando a chave pública de A. Neste caso E(D(M,KdA),KeA) = M.

• Assinatura e Cifragem: se A quer enviar uma mensagem assinada e cifrada para B, ele primeiro
assina M, calculando C1 = D(M,KdA), utilizando sua chave privada. A seguir, ele calcula C =
E(C1,KeB),   utilizando   a   chave   pública   de   B.   Tem­se   então   C   =   E(D(M,KdA),KeB),   que   é
enviada. O usuário B inicialmente restaura a mensagem calculando C1  = D(M,KdB), usando
sua chave privada. Depois B verifica a mensagem calculando M = E(C 1,KeA), usando a chave
pública de A. Neste caso E(D(E(D(M,KdA),KeB),KdB),KeA) = M.

Chave pública n: produto de dois primos, p e q (devem ser secretos)
e: primo relativo a (p–1).(q–1)
Chave privada d: (e.d) mod (p–1).(q–1) = 1, ou d = 1/e mod (p–1).(q–1)
Cifragem C = Me mod n
Decifragem M = Cd mod n
Assinatura A = Md mod n
Verificação Aceitar se Ae mod n = M
Tabela 1 – Método RSA

O método ElGamal também implementa cifragem e assinatura digital, conforme mostrado na tabela
2. Somente RSA e ElGamal implementam estas duas funções. Os demais métodos de chave pública
somente podem ser usados ou para cifragem ou para assinatura. Alguns podem adicionalmente ser
utilizados   para   identificação   (credenciamento)   de   usuários.   Um   lista   resumida   dos   principais
métodos de chave pública pode ser encontrada na seção 9 e em [SCH96].
 Chave pública p: primo (pode ser compartilhado por vários usuários)
g: menor que p (pode ser compartilhado por vários usuários)
y: igual a gx mod p
Chave privada x: menor que p
Cifragem k: qualquer, primo relativo a p–1
a (texto cifrado) = gk mod p
b (texto cifrado) = yk.M mod p
Decifragem M = ( b / (ax) ) mod p
Assinatura k: qualquer, primo relativo a p–1
a (assinatura) = gk mod p
b (assinatura) tal que M = ( x.a + k.b ) mod (p–1)
Verificação Aceitar se (ya.ab ) mod p = gM mod p
Tabela 2 – Método ElGamal

O algoritmo de assinatura digital DSA foi desenvolvido pela NSA e proposto pelo NIST para ser
utilizado no padrão DSS (Digital Signature Standard). Foi bastante combatido, principalmente pelo
autores do RSA. Seu uso está resumido na tabela 3. Embora DSA tenha sido projetado para ser
usado em assinatura digital, é possível utilizá­lo para cifragem e decifragem nos métodos de RSA e
ElGamal. Assuma­se que DSA está disponível sob a forma de uma chamada de função:
DSAsign(p,q,g,k,x,h,r,s)
Fornecendo­se p, q, g, k, x e h, a função devolve os valores de r e s. Para implementar a cifragem de
RSA, com módulo n, uma mensagem M e uma chave pública e, utiliza­se:
DSAsign(n,n,M,e,0,0,r,s)
O valor de  r  é o texto cifrado C; o valor de  s  não tem significado e pode ser desprezado. Para
decifrar usa­se o mesmo método, agora com uma chave privada d:
DSAsign(n,n,C,d,0,0,r,s)

Chave pública p:   primo   entre   512   e   1024   bits   (pode   ser   compartilhado   por   vários
usuários)
q: fator primo de p–1, de 160 bits (pode ser compartilhado)
g: dado por h(p–1)/q, onde h é qualquer número menor que  p–1 de forma
que h(p–1)/q mod q > 1 (pode ser compartilhado por vários usuários)
H(M): função de hash sobre a mensagem (função compartilhada)
y = gx mod p (chave pública)
Chave privada x: menor que q (um número de 160 bits)
Assinatura k: qualquer, menor que q
r (assinatura) = ( gk mod p ) mod q
s (assinatura) = ( k­1. ( H(M) + x.r )) mod q
Verificação w = s–1 mod q
 u1 = ( H(M) . w ) mod q
u2 = ( r . w ) mod q
v = ( ( gu1 . yu2 ) mod p ) mod q; aceitar se v = r
Tabela 3 – Método DSA

Para implementar a cifragem de ElGamal sobre uma mensagem M e uma chave pública y, escolhe­
se um número qualquer k e calcula­se:
DSAsign(p,p,g,k,0,0,r,s)
O valor retornado para r é o valor a de ElGamal. O valor de s pode ser desprezado. Agora calcula­
se:
DSAsign(p,p,y,k,0,0,r,s)
Renomeia­se r para ser u; despreza­se s. A seguir calcula­se:
DSAsign(p,p,M,1,u,0,r,s)
Despreza­se r, o valor de s é o valor b em ElGamal. Com isto obtêm­se a e b, o texto cifrado. Para
decifrar, usando uma chave privada x e as mensagens cifradas a e b, calcula­se:
DSAsign(p,p,a,x,0,0,r,s)
O valor retornado para r é ax mod p; seja este valor denominado de e. Agora calcula­se:
DSAsign(p,p,1,e,b,0,r,s)
O valor s é a mensagem decifrada M.

9 Funções unidirecionais

Em  implementações  práticas,  o uso de  algoritmos  de chave  pública  para  assinatura  digital  são
muitas vezes ineficientes para assinar documentos longos. A fim de reduzir o tempo necessário,
muitos  protocolos  de assinatura  digital  são implementados  com funções  de hash unidirecionais
(one­way  hash functions).  No lugar  de  assinar  um  documento,   calcula­se  o hash  e  aplica­se  a
assinatura somente sobre o hash, que normalmente é de tamanho reduzido (128 a 512 bits). O
processo segue então os seguintes passos:
• o usuário A produz um hash unidirecional do documento.
• o usuário A assina o hash com sua chave privada, assinando assim o documento.
• o usuário A envia o documento e o hash assinado para o usuário B.
• o usuário B calcula o hash do documento. A seguir, B restaura o hash assinado, usando a chave
pública de A. Se o hash produzido e o hash restaurado foram iguais, então o documento e a
assinatura são válidos.

Este   protocolo   tem   outras   vantagens   adicionais.  O  documento  pode   ser  armazenado  em   forma
legível,  o que facilita  o acesso e a leitura.  Documento e hash podem ser guardados em locais
diferentes, o que dificulta mais ainda adulterações. O espaço necessário para guardar o hash é bem
reduzido. E o mais interessante, relacionado com privacidade e outros aspectos legais: o documento
pode ser mantido secreto; somente o seu hash assinado necessita ser tornado público. Só quando a
autoria  de  um documento  (ou de uma  idéia)  deve  ser provada  é  que o documento  precisa  ser
tornado público.

Uma função de hash unidirecional, H(M), opera sobre uma mensagem de comprimento qualquer,
M, e retorna um valor de hash de comprimento fixo, h, ou seja, h = H(M). Existem muitas funções
que   realizam   hash,   mas   para   serem   unidirecionais   estas   funções   devem   ter   características
adicionais:
• Dado M, deve ser rápido e fácil calcular h.
• Dado h, é muito demorado e difícil calcular M.
• Dado um M, deve ser muito difícil encontrar outra mensagem M' tal que H(M) = H(M').

O termo “difícil” depende da segurança desejada, mas para a maioria das aplicações atuais é uma
ordem de 264 a 2128 operações, ou mesmo até mais.

Existem dois ataques contra uma função de hash unidirecional. O primeiro é o mais óbvio: dado o
hash de uma mensagem, h = H(M), o atacante procura criar outro documento M' que produza o
mesmo valor de hash, ou seja, H(M) = H(M'). Com isto ele pode comprometer toda a segurança do
protocolo que usa este hash. Por exemplo, se o usuário A assina o hash H(M), o atacante poderia
apresentar M' e alegar que este foi o documento assinado por A.

O segundo ataque é mais sutil. Deve ser difícil encontrar duas mensagens quaisquer, M e M', que
produzam o mesmo valor de hash. Este ataque é muito mais fácil que o primeiro, pois não necessita
obedecer a um valor de hash já existente. Ele é conhecido como ataque do aniversário, por refletir
um paradoxo estatístico. Quantas pessoas devem ser reunidas até que exista uma probabilidade
maior que 50% de uma delas fazer aniversário em uma data específica? A resposta é 183, ou seja,
365/2 (Este corresponde ao primeiro ataque). Agora, quantas pessoas devem ser reunidas para que
existam mais de 50% de chance de duas delas terem aniversário no mesmo dia ? A resposta é
surpreendentemente baixa: 24. Podem existir poucas pessoas, mas existem 276 pares possíveis de
pessoas (este corresponde ao segundo ataque). Com o ataque do aniversário, um atacante prepararia
dois documentos, M e M'. Um destes documentos seria mostrado ao usuário A, que produziria um
hash assinado. O atacante pode mais tarde mostrar M' e alegar que foi este o documento assinado.

Considere­se que uma função de hash unidirecional tenha as propriedades discutidas acima, que ela
produz   uma   saída   de  m  bits   e   que   o   melhor   meio   de   ataque   é   o   da   força   bruta.   Achar   uma
mensagem que produza um determinado valor de hash irá então requerer testar 2m  mensagens,
enquanto que achar duas mensagens que produzam o mesmo hash irá requerer o teste de 2 m/2
mensagens. Supondo um hash de 64 bits, uma máquina que consiga realizar um milhão de hashs
por segundo necessitará 600.000 anos para achar uma segunda mensagem que possua um dado
valor de hash, mas encontra duas mensagens que produzam o mesmo hash em cerca de uma hora.
Por este motivo, o tamanho mínimo recomendado para o comprimento de um hash é 128 bits.
A maioria das implementações das funções de hash unidirecionais são implementadas a partir de
uma função que produz uma saída de m bits dadas duas entradas de m bits cada. Estas duas entradas
são   normalmente   um   bloco   de   texto   e   o   hash   resultante   do   processamento   do   bloco   anterior.
Matematicamente, tem­se que  hi  = f (Mi,  hi–1). A saída hash do último bloco torna­se o hash de
toda a mensagem. Desta maneira, uma função de hash unidirecional produz sempre uma saída de
tamanho  fixo, independente  do tamanho  a mensagem.  Tipicamente,  alguma  informação  binária
sobre o tamanho da mensagem M é anexada a M antes do hash ser realizado, a fim de resolver um
eventual problema se segurança resultante do fato de duas mensagens de comprimento diferentes
produzirem o mesmo valor de hash.

Algoritmo MD5

O algoritmo mais utilizado para hash é o MD5 (Message Digest 5), desenvolvido por Ron Rivest
[RIV92]. O MD5 é uma melhoria do MD4, com o acréscimo de mais funções de embaralhamento e
mais rodadas. Inicialmente, a mensagem é dividida em blocos de 512 bits (com 16 sub­blocos de 32
bits). Ao último bloco é acrescentado um “1” binário, seguidos de tantos “0” até que o bloco tenha
um comprimento de 448 bits (512­64). Após, completa­se este bloco com a representação binária
do comprimento da mensagem. 

A seguir inicializam­se quatro variáveis:
A = 0x01234567
B = 0x89ABCDEF
C = 0xFEDCBA98
D = 0x76543210

Em cada laço do algoritmo, que processa um bloco de 512 bits, são utilizadas quatro funções :
F(x,y,z) = (x and y) or (not(x) and z)
G(x,y,z) = (x and z) or (y and not(z))
H(x,y,z) = x xor y xor z
I(x,y,z) = y xor (x or not(z))

Com estas quatro funções são construídas as quatro etapas de cada laço do algoritmo:
FF(a,b,c,d,Mi,s,t): a = b + ((a + F(b,c,d) + Mi + t) <<< s)
GG(a,b,c,d,Mi,s,t): a = b + ((a + G(b,c,d) + Mi + t) <<< s)
HH(a,b,c,d,Mi,s,t): a = b + ((a + H(b,c,d) + Mi + t) <<< s)
II(a,b,c,d,Mi,s,t): a = b + ((a + I(b,c,d) + Mi + t) <<< s)

onde  o índice I da mensagem M indica o uso do i­ésimo bloco de 32 bits de M (I varia entre 0 e
15). As quatro etapas (ou 64 passos) são então:

Início: a = A, b = B, c = C, d = D
Etapa 1:
FF(a,b,c,d,M0,7,0xd76aa478)
FF(d,a,b,c,M1,12,0xe8c7b756)
FF(c,d,a,b,M2,17,0x242070db)
FF(b,c,d,a,M3,22,0xc1bdceee)
FF(a,b,c,d,M4,7,0xf57c0faf)
FF(d,a,b,c,M5,12,0x4787c62a)
FF(c,d,a,b,M6,17,0xa8304613)
FF(b,c,d,a,M7,22,0xfd469501)
FF(a,b,c,d,M8,7,0x698098d8)
FF(d,a,b,c,M9,12,0x8b44f7af)
FF(c,d,a,b,M10,17,0xffff5bb1)
FF(b,c,d,a,M11,22,0x895cd7be)
FF(a,b,c,d,M12,7,0x6b901122)
FF(d,a,b,c,M13,12,0xfd987193)
FF(c,d,a,b,M14,17,0xa6794383)
FF(b,c,d,a,M15,22,0x49b40821)

Etapa 2:
GG(a,b,c,d,M1,5,0xf61e2562)
GG(d,a,b,c,M6,9,0xc040b340)
GG(c,d,a,b,M11,14,0x265e5a51)
GG(b,c,d,a,M0,20,0xe9b6c7aa)
GG(a,b,c,d,M5,5,0xd62f105d)
GG(d,a,b,c,M10,9,0x02441453)
GG(c,d,a,b,M15,14,0xd8a1e681)
GG(b,c,d,a,M4,20,0xe7d3fbc8)
GG(a,b,c,d,M9,5,0x21e1cde6)
GG(d,a,b,c,M14,9,0xc33707d6)
GG(c,d,a,b,M3,14,0xf4d50d87)
GG(b,c,d,a,M8,20,0x455a14ed)
GG(a,b,c,d,M13,5,0xa9e3e905)
GG(d,a,b,c,M2,9,0xfcefa3f8)
GG(c,d,a,b,M7,14,0x676f02d9)
GG(b,c,d,a,M12,20,0x8d2a4c8a)

Etapa 3:
HH(a,b,c,d,M5,4,0xfffa3942)
HH(d,a,b,c,M8,11,0x8771f681)
HH(c,d,a,b,M11,16,0x6d9d6122)
HH(b,c,d,a,M14,23,0xfde5380c)
HH(a,b,c,d,M1,4,0xa4beea44)
HH(d,a,b,c,M4,11,0x4bdecfa9)
 HH(c,d,a,b,M7,16,0xf6bb4b60)
HH(b,c,d,a,M10,23,0xbebfbc70)
HH(a,b,c,d,M13,4,0x289b7ec6)
HH(d,a,b,c,M0,11,0xeaa127fa)
HH(c,d,a,b,M3,16,0xd4ef3085)
HH(b,c,d,a,M6,23,0x04881d05)
HH(a,b,c,d,M9,4,0xd9d4d039)
HH(d,a,b,c,M12,11,0xe6db99e5)
HH(c,d,a,b,M15,16,0x1fa27cf8)
HH(b,c,d,a,M2,23,0xc4ac5665)

Etapa 4:
II(a,b,c,d,M0,6,0xf4292244)
II(d,a,b,c,M7,10,0x432aff97)
II(c,d,a,b,M14,15,0xab9423a7)
II(b,c,d,a,M5,21,0xfc93a039)
II(a,b,c,d,M12,6,0x655b59c3)
II(d,a,b,c,M3,10,0x8f0ccc92)
II(c,d,a,b,M10,15,0xffeff47d)
II(b,c,d,a,M1,21,0x85845dd1)
II(a,b,c,d,M8,6,0x6fa87e4f)
II(d,a,b,c,M15,10,0xfe2ce6e0)
II(c,d,a,b,M6,15,0xa3014314)
II(b,c,d,a,M13,21,0x4e0811a1)
II(a,b,c,d,M4,6,0xf7537e82)
II(d,a,b,c,M11,10,0xbd3af235)
II(c,d,a,b,M2,15,0x2ad7d2bb)
II(b,c,d,a,M9,21,0xeb86d391)

Observação:   no   passo   “i”,   o   valor   da   constante   é   dado   por   232.abs(sen(i)),   onde   i   é   dado   em
radianos.

Após estes 64 passos, A = a+A, B= b+B, C=c+C, D = d+D, e o algoritmo continua com o próximo
bloco de dados. Após a última etapa, o hash é dado pela concatenação de A, B, C e D.

Algoritmo SHA

Outro algoritmo, projetado pelo NIST e NSA, é o SHA [STA94], nitidamente inspirado no MD5,
mas com a diferença de produzir um hash de 160 bits, em vez de 128 bits. O início é exatamente o
mesmo, ou seja, a mensagem é dividida em blocos de 512 bits (com 16 sub­blocos de 32 bits). Ao
último bloco é acrescentado um “1” binário, seguidos de tantos “0” até que o bloco tenha um
comprimento de 448 bits (512­64). Após, completa­se este bloco com a representação binária do
comprimento da mensagem. A seguir inicializam­se cinco variáveis:
 A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
E = 0xc3d2e1f0

Em cada laço do algoritmo, que processa um bloco de 512 bits, são utilizadas quatro funções :
Ft(x,y,z) = (x and y) or (not(x) and z), para t entre 0 e 19
Ft(x,y,z) =x xor y xor z, para t entre 20 e 39
Ft(x,y,z) = (x and y) or (x and z) or (y and z), para t entre 40 e 59
Ft(x,y,z) = x xor y xor z. Para t entre 60 e 79

Também são empregadas 4 constantes:
Kt = 0x5a827999, para t entre 0 e 19
Kt = 0x6ed9eba1, para t entre 20 e 39
Kt = 0x8f1bbcdc, para t entre 40 e 59
Kt = 0xca62c1d6, para t entre 60 e 79

Os 16 blocos Mi (i variando de 0 a 15)são utilizados para construir os blocos Wi (i variando de 0 a
79), de acordo com o seguinte algoritmo:
Wt =Mt, para t entre 0 e 15
Wt = (W(t­3) xor W(t­8) xor W(t­14) xor W(t­16)) <<< 1, para t entre 16 e 79

Finalmente, os 80 passos do SHA são implementados: 

Início: a = A, b = B, c = C, d = D, e = E

FOR t = 0 to 19
temp = (a <<< 5) + Ft(b,c,d) + e + Wt + Kt
e = d
d = c
c = b <<< 30
b = a
a = temp

Após estes 80 passos, A = a+A, B= b+B, C=c+C, D = d+D, E = e+E e o algoritmo continua com o
próximo bloco de dados. Após a última etapa, o hash é dado pela concatenação de A, B, C e D.

Existem muitas  outras  propostas  de funções de hash unidirecionais. As principais  são descritas

brevemente   a   seguir.   Para   o   funcionamento   detalhado   de   cada   uma,   deve­se   consultar   artigos
específicos sobre cada uma.
 • Snefru: desenvolvida por Ralph Merkle e baseada no nome de um faraó egípcio. Produz um
hash de 128 ou de 256 bits. A mensagem é dividida em blocos de 512–m, onde m é igual a 128
ou 256. A sua segurança é baseada em uma função que randomiza os dados em vários passos.
Cada   passo   é   constituído   de   64   etapas,   e   em   cada   etapa   realiza­se   uma   cifragem   por
substituição combinada com operações de ou­exclusivo e rotação. Atualmente utilizam­se no
mínimo 8 passos. Para 2, 3 e 4 passos já foi demonstrado que Snefru é inseguro (pode ser
atacado com métodos melhores que o da força bruta).
• N­HASH:   foi   desenvolvido   pelos   mesmo   autores   de   FEAL,   usando   inclusive   funções   de
randomização semelhantes as de FEAL. Trabalha sobre blocos de mensagem de 128 bits, e
produz um hash também de 128 bits. Seu bloco básico utiliza funções de soma, ou­exclusivo e
rotação. Este bloco pode ser encadeado, formando assim uma função total de diversos passos.
Para qualquer número de passos menor que 15, já foi demonstrado que N­HASH é inseguro.
• MD2:   (Message   Digest   2)   desenvolvida   por   Ron   Rivest,   produz   um   hash   de   128   bits.
Comparada   com   MD4   e   MD5,   do   mesmo   autor,   é   lenta   e   menos   segura.   Não   é   mais
recomendada para uso. Pode ser encontrado em [KAL92] e [SPO95].
• MD4: (Message Digest 4) também de Rivest, produz um hash de 128 bits. Trabalha sobre
blocos de 512 bits, divididos em 16 sub­blocos de 32 bits. A saída do método é um conjunto de
4  blocos  de  32  bits,  que são  concatenados   para  formar  o hash  de 128  bits.  As   operações
utilizadas internamente compreendem soma, deslocamento, ou­exclusivo e operações lógicas
“ou” e “e”. Como um todo, MD4 não pode ser atacado a não ser pelo método da força bruta,
mas   diversos   estágios   internos   já   foram   criptoanalisados   individualmente   com   sucesso.
Descrições podem ser encontradas em [RIV90] e [SPO95].
• HAVAL: é uma função de hash de comprimento variável. Trabalha sobre blocos de 1024 bits,
utiliza um número variável de passos (entre 3 e 5), e pode produzir valores de hash de 92, 128,
160, 224 ou 256 bits. Seu projeto foi baseado no MD5.

É possível utilizar um sistema de criptografia de chave simétrica que trabalhe com blocos como
uma função de hash unidirecional. Se o método de criptografia é seguro, então a função de hash
também o será. O método mais óbvio é utilizar um algoritmo de criptografia em modo CBC, com
um vetor de inicialização igual a zero (seção 5). O valor do último bloco cifrado é o valor de hash.
Existem entretanto dois problemas: os algoritmos de criptografia simétrica trabalham normalmente
com blocos de 64 bits, o que os torna suscetíveis ao ataque do aniversário, e é necessário o uso de
uma chave de cifragem, que deve ser mantida secreta.

Um método de adaptação mais elaborado é usar o bloco da mensagem como a chave de cifragem, o
valor prévio de hash como entrada (no lugar da mensagem) e obter o valor de hash atual da saída.
Além disto, adiciona­se operações de ou­exclusivo no laço de realimentação e outros operadores
para gerar valores de hash com o dobro do tamanho do bloco, obtendo­se assim tamanhos mínimos
de 128 bits.
Também é possível utilizar um sistema de criptografia de chave pública como uma função de hash
unidirecional.   Basta   simplesmente   descartar   a   chave   secreta,   e  trabalhar   somente   com   a   chave
pública. No RSA, por exemplo, se M é a mensagem, n é o produto de dois primos p e q, e e é um
número primo em relação a (p–1).(q–1), então a função de hash seria H(M) = Me mod n. A única
desvantagem com os algoritmos de chave pública é a sua lentidão quando comparados com as
demais funções de hash.

As   funções   de   hash   unidirecionais   podem   também   utilizar   uma   chave   secreta.   Neste   caso   são
denominadas  MAC (Message Authentication Code). Somente alguém que possua a chave pode
verificar   o   hash.   Isto   é   útil   quando   se   deseja   apenas   proteger   a   autenticidade   sem   incluir
privacidade.   Uma   função   de   hash   unidirecional   convencional   pode   ser   usada   como   MAC:
concatena­se a chave K à mensagem M e calcula­se o hash. Este valor é o MAC. Somente quem
conhece a chave K poderá repetir o processo sobre M e verificar sua integridade.

10 Protocolos criptográficos

Os criptosistemas apresentados nas seções anteriores possuem uma utilidade muito restrita quando
usados isoladamente. Naturalmente, dados sensíveis podem ser cifrados, de forma que só possam
ser processados (decifrados) pelas pessoas autorizadas (que possuam a chave de decifragem). Mas a
criptografia  pode ser empregada em  muitas  outras  aplicações  quando  é utilizado  um protocolo
criptográfico para resolver um determinado problema.

Um protocolo criptográfico é basicamente um protocolo que utiliza criptografia em um ou mais de
seus passos. Os participantes podem se conhecer e confiar plenamente uns nos outros, ou podem ser
desconhecidos   que   desconfiam   de   todos   os   demais.   Embora   envolvendo   um   criptosistema,   o
objetivo do protocolo normalmente é algo além da simples ocultação ou privacidade de dados. Os
participantes   podem   compartilhar   parte   dos   seus   segredos   para   realizar   alguma   computação,
convencer um do outro da sua identidade,  assinar simultaneamente um contrato ou até mesmo
realizar uma votação secreta.

Um   protocolo   é   dito  arbitrado  se   envolver   uma   outra   pessoa   (ou   computador)   além   dos
participantes normais. O árbitro deve ser confiável, isto é, todos os participantes confiam nele e
respeitam suas decisões, e deve ser desinteressado, ou seja, não tem nenhum interesse particular na
finalidade do protocolo nem qualquer preconceito contra qualquer participante. No caso que um dos
participantes não querer finalizar um protocolo, o árbitro deve ajudar a completar este protocolo.
Na   vida   real,   o   papel   de   árbitro   é   desempenhado   por   advogados,   banqueiros,   juizes,   regentes,
padres, etc.  No caso de computadores,  o  árbitro  deve  ser uma  entidade  centralizada,  capaz  de
armazenar toda a informação envolvida. Isto tem vários inconvenientes: uma entidade central é
normalmente um gargalo na rede de comunicação e ao mesmo tempo um ponto vulnerável em
termos de segurança. Além disto, todas as transações devem ser tratadas pelo árbitro, e isto introduz
um atraso nas comunicações.
Um protocolo é dito  adjudicado  se ele pode ser dividido em duas partes. A primeira parte não é
arbitrada, e é executada em casos normais. A segunda parte envolve um árbitro, mas só necessita
ser  executada   no  caso  de  uma   disputa   ou  desentendimento   entre   os  participantes.   Note­se  que
durante a primeira parte os participantes devem produzir bastante evidências das suas ações, para
que se for necessário recorrer a um árbitro este possa tomar uma decisão.

Um protocolo é dito auto­sustentado se não requer nunca o uso de um árbitro, nem em situações
normais nem em casos de desentendimento. O próprio protocolo garante justiça e imparcialidade. O
protocolo é construído de tal maneira que não possam ocorrer disputas ou trapaças. Se um dos
participantes tenta ser desonesto, os outros participantes detectam isto imediatamente, e o protocolo
para antes que o trapaceiro possa ter algum ganho ou obter alguma informação confidencial.

Um   protocolo   pode   ser   atacado   de   diversas   maneiras,   além   das   maneiras   tradicionais   de
criptoanálise quanto ao criptosistema em si:
• comprometimento  das chaves: qualquer protocolo ou criptosistema  somente   é seguro se as
chaves privadas permanecerem secretas. Se elas forem roubadas, reveladas (intencionalmente
ou não) ou comprometidas de alguma forma, então toda a segurança é perdida. Uma chave
também é considerada comprometida se for usada repetidas vezes ou a sua regra de formação
for facilmente deduzível (chave fraca).
• ataque do homem­no­meio: ocorre quando um atacante não só tem condições de interceptar as
mensagens trocadas entre os participantes (ataque passivo), mas também consegue introduzir
suas   próprias   mensagens   de   tal   maneira   que   os   demais   participantes   julguem   que   ela   foi
enviada por um participante legítimo (ataque ativo).
• ataque   dos   participantes:   um  ou mais  dos   participantes  pode  querer  trapacear,  e  isto  pode
ocorrer de diversas maneiras. A mais elementar é renegar o protocolo, ou seja, se recusar a
realizar um de seus passos. Um protocolo bem definido deve permitir que isto seja detectado, e
quem   se   sentir   prejudicado   deve   poder   abandonar   o   protocolo   antes   de   revelar   qualquer
informação vital. Um ataque mais sutil é demorar a completar um determinado passo, de forma
a tentar deduzir alguma informação sensível a partir dos elementos já informados pelos demais
participantes.   Justamente   para   evitar   isto   é   que   os   criptosistemas   devem   ser   complexos   o
suficiente  para  evitar   que  isto  aconteça   em  tempo  hábil.   Um terceiro  tipo   de ataque  pode
ocorrer   se   um   participante   alega   que   sua   chave   foi   roubada   e   alguém   a   está   utilizando
indevidamente.

Um grande número de protocolos  criptográficos  já foram e estão sendo desenvolvidos.. Vários

deles podem ser implementados de diversas formas, com criptosistemas de chave única ou pública,
com   ou   sem   o   uso   de   árbitros,   etc.   Outros   requerem   o   uso   de   algoritmos   específicos   ou   de
propriedades que nem todos os métodos possuem. Um bom estudo geral pode ser encontrado em
[BRA88], [FAV94],[SCH93] e [SCH96]. A lista a seguir define a situação em que cada protocolo é
empregado.
• Distribuição de chaves: quando duas pessoas decide ter uma conversação secreta ou uma
troca  de mensagens  privadas,  é  necessário que  elas  concordem  com  o uso de uma  chave,
denominada da chave da sessão. O problema é justamente transmitir esta chave por um canal
inseguro. Um criptosistema de chave pública resolve isto automaticamente, enquanto que um
de chave única precisa usar um árbitro ou um método especial [MER78]. Atenção especial
deve   ser   dado   ao   ataque   do   homem­no­meio,   ou   seja,   um   usuário   C   que   intercepta   a
comunicação entre A e B, fornecendo para B a sua chave no lugar da chave que A envia, e
vice­versa.   Para   evitar   isto   usa­se   um   protocolo   de   entrelaçamento   (interlock),   onde   cada
participante envia inicialmente metade da mensagem cifrada, e somente após o recebimento
envia a outra metade.
• Autenticação de usuário: esta situação ocorre quando o usuário de um sistema deve provar
que   é   um   usuário   legítimo   antes   de   ter   acesso   aos   recursos   deste   sistema.   Este   problema
envolve necessariamente o uso de uma chave (senha), e pode ser resolvido por funções de hash
unidirecionais [LAM81], ou por criptosistemas de chave única ou pública, com ou sem o uso
de   uma   central   de   autenticações.   Entre   exemplos   de   implementação   podem   ser   citados
Kerberos, Wide­Mouth Frog Protocol e EKE (encrypted key exchange), todos analisados em
[SCH96]. Detalhes também são encontrados em [NEE78].
• Divisão de segredo: neste caso um segredo deve ser dividido entre diversos participantes, de
forma de cada um individualmente não obtenha informação suficiente para deduzir o segredo
sozinho. Todos os participantes devem se reunir para regenerar a informação. Esta técnica é
normalmente implementada com o uso de ou­exclusivo e cadeias de bits pseudo­randômicos.
• Compartilhamento de segredo: no item anterior, se uma das partes é perdida, a informação
não pode ser regenerada. Para resolver isto, as  n  partes do segredo (denominadas  sombras)
devem ser tais que  m  delas reconstroem a informação, mas  m–1 não. Um método deste tipo
recebe o nome de esquema limite(m, n). Alguns exemplos são encontrados em [SCH96].
• Autenticação de tempo: este problema surge quando é importante saber quando determinada
informação   foi   criada   ou   alterada.   As   soluções   normalmente   utilizam   carimbos   de   tempo
(timestamps) e funções de hash unidirecionais.
• Assinatura digital não­contestável: esta situação ocorre quando a assinatura não deve ser
verificado   por   qualquer   um,   mas   somente   aquelas   pessoas   que   o   signatário   da   mensagem
aprova. Ou seja, a assinatura não pode ser verificada sem o consentimento do signatário. Para
implementar isto, deve­se empregar um criptosistema de chave pública modificado. exemplos
podem ser encontrados em [SCH96].
• Cara   ou   coroa:  esta   situação   foi   apresentada   por   Blum   em   [BLU82]   e   permite   que   dois
usuários joguem cara ou coroa por um meio de comunicação, sem estarem frente a frente e até
mesmo sem se confiarem mutuamente. O problema pode ser resolvido com funções de hash
unidirecionais [BRA88], mas um criptosistema de chave pública também pode usado, desde
que   as   funções   de   cifragem   e   de   decifragem   sejam   comutativas   (RSA   satisfaz   esta
propriedade). O usuário A gera duas mensagens, uma para cara e outra para coroa, cifra as
duas com sua chave pública e envia ambas para B. O usuário B não pode decifrá­las (somente
 A pode), mas escolhe uma delas, cifra com a sua chave pública e envia para A. Este, por sua
vez, não pode reconhecer a mensagem, mas a decifra com sua chave privada e a envia para B.
Quando B receber esta mensagem, ele a decifra com sua chave privada e obtém finalmente
uma das duas mensagens originais, que envia para A. Neste ponto os dois conhecem qual
mensagem foi sorteada. Se houver dúvidas, basta os usuários revelarem suas chaves secretas
para  que  cada  um  possa  verificar  o  processo  sem  o auxílio  do  outro. Note­se que  para  o
protocolo ser possível deve a decifragem de A deve poder ser comutada com a cifragem de B,
ou seja:
D(D(E(E(M,keA),keB),kdA),kdB) = D(E(D(E(M,keA),kdA),keB),kdB)

• Poquer mental: um protocolo semelhante ao anterior, mas estendido para mais de dois valores
e mais de dois participantes. O princípio de operação é o mesmo, mas agora as mensagens são
inicialmente cifradas  sucessivamente  pelos  n  participantes  e somente depois  decifradas  por
todos. Um detalhamento pode ser visto em [SCH92].
• Comprometimento com bit revelado: (bit commitment) este caso surge quando o usuário A
quer se comprometer com uma previsão, mas não quer revelar esta previsão para B antes de
um certo momento. O usuário B, por sua vez, quer ter certeza que A não vai mudar de opinião
depois de ter se comprometido. O protocolo por ser implementado por hash, chave única ou
chave pública, mas todos seguem o mesmo padrão. Em uma primeira fase, B gera uma cadeia
aleatória de bits e envia para A. Este por sua vez, concatena a cadeia com sua previsão, cifra o
resultado e o envia para B. Na segunda fase, quando a previsão deve ser revelada, A envia a
chave de cifragem para B, que decifra a mensagem em seu poder, confirma a presença de sua
cadeia de bits e pode ler a previsão. Detalhes do funcionamento podem ser encontrados em
[SCH96] e [FAV95].
• Assinatura cega: (blind signature) neste caso se deseja que uma pessoa assine uma mensagem
sem conhecer o seu conteúdo. Por si só esta situação não é muito útil, mas pode ser empregada
como parte de um sistema de votação (onde um voto deve ser validado pelo juiz eleitoral sem
ser lido) ou de transferência bancária (onde o banco deve validar a transação mas mantendo o
anonimato da transferência). O método é relativamente simples: o usuário A multiplica sua
mensagem   por   um   número   qualquer   (blinding   factor)   e   envia   para   B,   que   assina   esta
mensagem. Recebendo a mensagem assina, A a divide pelo mesmo número inicial, deixando
assim   somente   a   mensagem   original   assinada.   Para   este   protocolo   funcionar,   a   função   de
assinatura   e   a   multiplicação   devem   ser   comutativas.   Este   método   também   é   chamado   de
assinatura em um envelope.
• Prova de conhecimento com informação zero: nesta situação, A deseja provar para B que
conhece um determinado segredo, sem entretanto revelá­lo para B. Um protocolo que consiga
convencer   B   deste   fato,   sem   que   B   descubra   nada   sobre   o   segredo,   é   um   protocolo   com
informação zero. A técnica a ser utilizada é iterativa (é repetida até que B esteja convencido), e
cada passo é do tipo “corte­e­escolha” (cut and choose, assim chamado por ser uma maneira de
divisão honesta: uma pessoa faz a divisão e a outra escolhe uma das metades). Em cada passo,
B pede para A realizar uma escolha binária baseada em uma computação, que só pode ser
 realizada   com   sucesso   por   A   se   este   realmente   conhecer   o   segredo.   O   usuário   A   pode
trapacear, mas suas chances de ser bem sucedido a longo prazo são reduzidas à metade em
cada iteração.
• Assinatura simultânea de contrato: algumas maneiras de resolver esta situação para duas
pessoas que não estão frente a frente estão descritos em [BEN90], [SCH93] e [SCH96]. O
método básico consiste em fazer as duas pessoas assinarem alternadamente, “letra a letra”.
Para isto usa­se criptografia e um outro protocolo denominado  transferência cega, onde um
usuário A transmite duas mensagens para B, este escolhe uma das duas e pode eventualmente
confirmá­la com A, sem que este saiba qual das duas foi escolhida.
• Votação segura: para que uma votação totalmente computadorizada seja possível, deve ser
desenvolvido   um   protocolo   que   tenha   cinco   propriedades   básicas:   somente   eleitores
autorizados podem votar; cada eleitor somente pode votar uma vez; ninguém deve determinar
os votos dos outros; ninguém pode alterar os votos sem ser descoberto; e todos eleitores podem
verificar o processo de contagem dos votos e se certificarem que seus votos foram apurados
corretamente.   Uma   boa   visão   geral   sobre   este   problema   e   as   soluções   propostas   pode   ser
encontrada em [SCH96].
• Dinheiro digital: um sistema de transações bancárias, onde um pode controlar a legitimidade
das   transações   efetuadas,   mas   sem   invadir   a   privacidade   de   cada   transação.   Assim,   por
exemplo, o banco não sabe para onde o usuário A está transferindo seu dinheiro; ele somente
pode determinar  que A tem  a quantia  que está transferindo. Detalhes  sobre este problema
também podem ser encontrados em [SCH96], assim como todos os demais desta lista.

11 Conclusões

A   criptografia   contemporânea   segue   dois   rumos   distintos.   Um   deles,   o   empregado   pelos

criptosistemas   de   chave   única,   emprega   um   grande   número   de   funções   elementares   de   um
computador   (soma,   deslocamentos,   substituições,   transposições,   ou­exclusivo,   etc)   para   gerar
difusão e confusão na mensagem cifrada. Estes métodos são fáceis de serem implementados em um
computador, e apresentam grande velocidade de processamento. A segurança destes métodos   é
julgada pela criptoanálise: se não for desenvolvido nenhuma maneira de ataque mais eficaz que o
da força bruta, então o método é considerado seguro.

Criptosistemas   de   chave   pública   são   especialmente   orientados   para   protocolos   de   rede   de

computadores,   e   baseiam­se   em   funções   computacionalmente   complexas.   Definido   o
funcionamento de um sistema de chave pública, é muito fácil determinar quais as funções a serem
executadas por um atacante para quebrar o sistema. Mas estas funções são computacionalmente
intratáveis e exigem uma quantidade impraticável de tempo e recursos de processamento, de modo
que o sistema  é seguro para todos os fins práticos. Criptosistemas  de chave pública trabalham
normalmente com grandes números (mais de 512 bits), o que não é suportado pelos computadores
atuais. Assim, todas as operações aritméticas devem ser implementadas em software (utilizando­se
as chamadas bibliotecas de grandes números ou de múltipla precisão), o que torna estes métodos
bem mais lentos que os de chave única.

Decidir   entre   criptosistemas   de   chave   única   e   de   chave   pública   é   uma   tarefa   que   depende   de
diversos fatores. A criptografia de chave pública é melhor para distribuição de chaves, autenticação
e protocolos criptográficos. Neste sentido, ela pode realizar tarefas  que a criptografia de chave
única não pode fazer. Por outro lado, criptosistemas de chave única são várias ordens de magnitude
mais rápidos. São ideais para cifrar arquivos e canais de comunicação.

Criptosistemas   de   chave   única   e   de   chave   pública   trabalham   melhor   juntos.   O   sistema   PEM
(Privacy Enhanced Mail), utilizado na Internet, utiliza DES no modo CBC para cifragem, MD2 ou
MD5 para autenticação e RSA para gerência de chaves. O sistema PGP (Pretty Good Privacy),
desenvolvido por Philip Zimmerman e colocado em domínio público, usa IDEA para cifragem,
RSA para gerência de chaves e MD5 como função de hash. Este sistema, e muitos outros métodos
citados aqui, estão disponíveis por ftp anônimo em ftp.dsi.unimi.it, no diretório pub/security.

Para   maiores   informações   sobre   os   tópicos   abordados   neste   tutorial   recomenda­se   [BRA88],
[DAV84], [LEI82], [LUC86], [SCH96] e [SIM92].

Bibliografia

[AKL83] Akl, S. G. Digital signatures: a tutorial survey. Computer, vol 16, no 2, fevereiro 1983,
p.15­24.
[BAR92] Barlow, J. P. Decrypting the puzzle palace. Communications of the ACM, vol 35, no 7,
julho 1992, p.25­31.
[BEN90] Ben­Or, M.; Goldreich, O.; Micali, S.; Rivest, R. A fair protocol for signing contracts.
IEEE Transactions on Information Theory, vol 36, no 1, janeiro 1990, p. 40­46.
[BLU82] Blum,   M.  Coin   flipping   by   telephone:   a   protocol   for   solving   impossible   problems.
Proceedings of the 24th IEEE Computer Conference, 1982, p. 133­137.
[BOO81] Booth, K. S. Authentication of signatures using public key encryption. Communications
of the ACM, vol 24, no 11, novembro 1981, p.772­774.
[BOR92] Borella, A.  Criptosistemas de chave pública: segurança na comunicação de dados.
Projeto de diplomação, curso de ciências de computação, UFRGS, Porto Alegre, 1992.
[BOR94] Borella, A. A criptografia assimétrica e seus principais métodos. Trabalho individual,
Pós­Graduação em Ciência da Computação, UFRGS, Porto Alegre, 1994.
[BRA88] Brassard, G. Modern Criptology. Lectures notes in computer science. Springer Verlag,
New York, 1988.
[CHA85] Chaum, D.  Security without identification: transactions systems to make Big Brother
obsolete. Communications of the ACM, vol 28 no 10, outubro 1985, p. 1030­1044.
[CIK92] Cikoski, M. J. Criptografia: a segurança dos dados. Projeto de diplomação, curso de
ciências de computação, UFRGS, Porto Alegre, 1992.
[COP87] Coppersmith, D.  Cryptography. IBM Journal of Research and Development, vol 31,
no 2, março 1987, p.244­248.
[DAN95] Dandrea, M. M. Sistema de criptoanálise. Projeto de diplomação, curso de ciências de
computação, UFRGS, Porto Alegre, 1995.
[DAV83] Davies, D. W. Applying the RSA Digital Signature to Electronic Mail. Computer, vol
16, no 2, fevereiro 1983, p.55­62.
[DAV84] Davies, D. W.; Price, W. L. Security for Computer Networks. John Wiley & Sons, New
York, 1984.
[DEM83] Demillo, R.; Merrit, M. Protocols for Data Security. Computer, vol 16, no 2, fevereiro
1983, p. 39­51.
[DEN83] Denning, D. E. Protecting Public Keys and Signatures Keys. Computer, vol 16, no 2,
fevereiro 1983, p. 27­35.
[DEN84] Denning,   D.   E.  Digital   signatures   with   RSA   and   other   public­key   cryptosystems.
Communications of the ACM, vol 27, no 4, abril 1984, p. 388­392.
[DIF76] Diffie, W.; Hellman, M. E.  New Directions in Cryptography. IEEE Transactions on
Information Theory, vol IT­22, novembro 1976, p. 644­654.
[DIF79] Diffie,   W.;   Hellman,   M.   E.  Privacy   and   authentication:   an   introduction   to
cryptography. Proceedings of the IEEE, vol 67, no 3, março 1979, p. 397­342.
[ELG85] ElGamal,   T.  A   public­key   cryptosystem   and   a   signature   scheme   based   on   discrete
logarithms. IEEE Transactions on Information Theory, vol IT­31, 1985, p. 468­472.
[FAV94] Fava,   S.   L.  Um   estudo   preliminar   sobre   protocolos   criptográficos.   Projeto   de
diplomação, curso de ciências de computação, UFRGS, Porto Alegre, 1994.
[JUE83] Jueneman, R. R.; Matyas, S. M.; Meyer, C. H. Message Authentication. IEEE Commu–
nications magazine, vol 23, no 9, agoso 1983, p 29­40.
[KAH80] Kahn,   D.  Cryptology   goes   Public.   IEEE   Communications   magazine,   vol   18,   no   3,
março 1980, p. 19­28.
[KAK83] Kak, S. C.  Data Security in Computer Networks. Computer, vol 16, no 2, fevereiro
1983, p 8­10.
[KAL92] Kaliski, B. S. The MD2 Message Digest Algorithm. Request for Comments RFC 1319,
abril 1992.
[LAM81] Lamport, L.  Password authentication with insecure communication. Communications
of the ACM, vol 24, no 11, novembro 1981, p. 770­774.
[LEI82] Leiss, E. L. Principles of Data Security. Plenum Press, New York, 1982.
[LEM79] Lempel, A.  Cryptology in Transiction. Computing Surveys, vol 11, no 4, dezembro
1979, p 285­303.
[LUC86] Lucchesi,   C.   L.  Introdução   à   Criptografia   Computacional.   UNICAMP,   Campinas,
1986.
[MER78] Merkle, R. C. Secure Communications over an insecure channel. Communications of
the ACM, vol 21, no 4, abril 1978, p. 294­299.
[MER81] Merkle, R. C.; Hellman, M. E. On the security of multiple encryption. Communications
of the ACM, vol 24, no 7, julho 1981, p. 465­467.
[MON94] Montenegro,   F.   S.  Uma   implementação   do   método   de   Blum­Goldwasser   para
criptografia probabilística. Projeto de diplomação, curso de ciências de computação,
UFRGS, Porto Alegre, 1994.
[NEE78] Needham,   R.   M.;   Schroeder,   M.   D.  Using   encryption   for   authentication   in   large
networks. Communications of the ACM, vol 21, no 12, dezembro 1978, p. 993­999.
[NIS92] NIST; Rivest, R.; Hellman, M.; Anderson, J.  DSS: The Digital Signature Standard.
Communications of the ACM, vol 35, no 7, julho 1992, p.33­54.
[PEL79] Peleg, S.; Rosenfeld, A. Breaking Substitution Ciphers using a Relaxation Algorithm.
Communications of the ACM, vol 22, no 11, novembro 1979, p.598­605.
[POH78] Pohlig, S. C.; Hellman,  M. E.  An improved algorithm for computing logarithms in
GF(p)   and   its   cryptographic   significance.   IEEE   Transactions   on   Information
Theory,vol 24, no 1, janeito 1978, p. 106­111.
[RIV78] Rivest, R. L.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and
public key cryptography. Communications of the ACM, vol 21, no 2, fevereiro 1978, p.
120­126.
[RIV84] Rivest,   R.   L.;   Shamir,   A.  How   to   expose   a   eavesdropper.   Communications   of   the
ACM, vol 27, no 4, abril 1984, p. 393­395.
[RIV90] Rivest, R.  The MD4 Message Digest Algorithm. Request for Comments RFC 1186,
1990.
[RIV92] Rivest, R.  The MD5 Message Digest Algorithm. Request for Comments RFC 1321,
1992.
[SCH92] Schneier, B.  Untangling public­key cryptography. Dr. Dobb's Journal, vol 17, no 5,
maio 1992, p. 16­28.
[SCH93] Schneier,   B.  The   IDEA   encryption   algorithm.   Dr.   Dobb's   Journal,   vol   18,   no   13,
dezembro 1993, p. 50­56.
[SCH96] Schneier, B.  Applied Cryptography, second edition. John Wiley & Sons, New York,
1996.
[SHA79] Shamir,   A.  How   to   share   a   secret.  Communications   of   the   ACM,   vol   22,   no   11,
novembro 1979, p. 612­613.
[SIM79] Simmons, G. J. Symmetric and asymetric encryption. Computing Surveys, vol 11, no 4,
dezembro 1979, p. 305­330.
[SIM92] Simmons, G.  Contemporany Cryptology ­ The science of information integrity.  IEEE
Press, 1992.
[SMI81] Smid,   M.  Integrating   the   data   encryption   standard   into   computer   networks.   IEEE
Transactions on Communications, vol com­29, no 6, junho 1981, p. 762­772.
[SMI93] Smith, P. LUC Public key encryption. Dr. Dobb's Journal, vol 18, no 1, janeiro 1993, p.
44­49.
[SPO95] Spohn,   M.   A.  Uma   análise   de   funções   de   hash   em   assinatura   digital.   Projeto   de
diplomação, curso de ciências de computação, UFRGS, Porto Alegre, 1995.
[STA94] Stallings, W. SHA: the secure hash algorithm. Dr. Dobb's Journal, vol 19, no 4, abril
1994, p. 32­34.
[STE94] Stevens, A. Hacks, spooks and data encryption. Dr. Dobb's Journal, vol 19, no 4, abril
1994, p. 127­134, 147­149.
[TAN88] Tannenbaum, A. S. Computer Network, 2.ed. Englewood Cliffs, Prentice Hall 1988, p.
496­518.
[WIL80] Williams,  H.  C.  A  modification  of  the  RSA   public­key  encryption   procedure.  IEEE
Transactions on Information Theory, vol IT­26, no 6, novembro 1980, p. 726­729.