UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE CENTRO DE CIÊNCIAS EXATAS E DA TERRA
DEPARTAMENTO DE MATEMÁTICA E INFORMÁTICA APLICADA GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
RELATÓRIO DE GRADUAÇÃO
PAPÍLIO VERSÁTIL: UM ALGORITMO CRIPTOGRÁFICO
ALUNO: JOÃO BATISTA DE SOUZA LEÃO NETO ORIENTADOR: BENJAMIN RENÉ CALLEJAS BEDREGAL
NATAL 05-2009
II
João Batista de Souza Leão Neto
PAPÍLIO VERSÁTIL: UM ALGORITMO CRIPTOGRÁFICO
Monografia apresentada à Universidade Federal do Rio Grande do Norte - UFRN como parte dos requisitos para obtenção do título de Bacharel em Ciência da Computação.
NATAL 05-2009
III
João Batista de Souza Leão Neto
PAPÍLIO VERSÁTIL: UM ALGORITMO CRIPTOGRÁFICO
Monografia apresentada à Universidade Federal do Rio Grande do Norte - UFRN como parte dos requisitos para obtenção do título de Bacharel em Ciência da Computação.
Aprovada em ___/___/___.
Banca Examinadora:
__________________________________________________
Prof. Dr. Benjamin René Callejas Bedregal
__________________________________________________
Profa. Dra. Karla Darlene Nepomuceno Ramos
__________________________________________________
Prof. Dr. Ivan Saraiva da Silva
IV
Dedico este trabalho a todos que comigo conviveram durante a graduação, especialmente à minha família, pelo incentivo constante.
V
AGRADECIMENTOS
Aos meus pais, o Senhor Jorge Eduardo Dantas de Souza Leão e a
Senhora Rose Anne Barros de Souza Leão pela educação e ensinamentos a
mim fornecidos.
Ao orientador, Dr. Benjamin Renés Callejas Bedregal, pela
inestimável ajuda oferecida na elaboração deste trabalho.
Aos colegas de classe, que conviveram comigo durante todo o
curso, compartilhando aprendizado e momentos de descontração.
À minha vó, Senhora Maria do Socorro Dantas de Souza Leão, pelo
incentivo e ajuda na compra do computador, no qual produzi este trabalho.
À Senhorita Áurea Flaviana Oliveira da Silva pelo incentivo e
motivação a mim concebidos durante a elaboração deste trabalho.
VI
“O que um peixe sabe sobre a água da qual nada a vida inteira.”
“É espantosamente óbvio que nossa tecnologia excede nossa humanidade."
Albert Einstein
VII
RESUMO
Este trabalho apresenta um algoritmo criptográfico, o Papílio Versátil, desenvolvido como uma extensão do Papílio XP (Araújo, 2003). Consiste em um algoritmo simétrico de bloco, baseado na cifra de Feistel. Utiliza o algoritmo decodificador Viterbi modificado como função de substituição na função rodada e na geração de subchaves. Opera com bloco de 16 Bytes e chave variando de 16 a 128 Bytes. Ocorre variação na função de substituição e na subchave utilizada em determinada rodada, assim como na quantidade de rodadas processadas. Estas variações são dependentes tanto da chave como do texto claro, o que confere maior segurança ao algoritmo. Obtém índices consideráveis de confusão, difusão e efeito avalanche, características desejáveis em um algoritmo criptográfico.
Palavras-chave: Criptografia. Cifra de Feistel. Simétrico. Chave variável. Rodadas Variáveis. Subchaves Variáveis.
VIII
ABSTRACT This paper presents a cryptographic algorithm, the Papílio Versátil, developed as an extension of Papílio XP (Araújo, 2003). Is to a symmetric algorithm for block based on the cipher of Feistel. Uses the Viterbi algorithm decoder modified as a function of substitution in the round function and the generation of subkeys. Process with block of 16 Bytes and Key ranging from 16 to 128 Bytes. Variation occurs in function of substitution and the subkey used in given round, as well as the number of rounds processed. These variations are dependent on both the key and the clear text, which gives greater security the algorithm. Have indices of considerable confusion, diffusion and avalanche effect, desirable characteristics in a cryptographic algorithm. Key word: Cryptography. Cipher of Feistel. Symmetrical. Key Variable. Rounds Variables. Subkeys Variables.
IX
LISTA DE ILUSTRAÇÕES
Figura 1 – Cifra de Feistel .................................................................................. 8
Figura 2 – Representação do Codificador Convolucional (n/s = 2, Q = 3, m = 2)
......................................................................................................................... 11
Figura 3 – Treliça do Codificador Convolucional (n/s = 2, Q = 3, m = 2) .......... 12
Figura 4 – Algoritmo Papílio ............................................................................. 15
Figura 5 – Criptografia no Modo ECB .............................................................. 17
Figura 6 – Descriptografia no Modo ECB ......................................................... 18
Figura 7 – Criptografia no Modo CBC .............................................................. 19
Figura 8 – Descriptografia no Modo CBC ......................................................... 19
Figura 9 – Criptografia no Modo CFB ............................................................... 20
Figura 10 – Descriptografia no Modo CFB ....................................................... 21
Figura 11 – Criptografia no Modo OFB ............................................................ 21
Figura 12 – Descriptografia no Modo OFB ....................................................... 22
Figura 13 – Geração de Subchaves no Papílio Versátil ................................... 30
Figura 14 – Inteface Gráfica do Usuário do Papílio Versátil ............................. 35
X
LISTA DE TABELAS
Tabela 1 – Máquina de Estado do Codificador Convolucional (n/s = 2, Q = 3, m
= 2) ................................................................................................................... 11
Tabela 2 – Decodificador Viterbi (n/s = 2, Q = 3, m = 2) .................................. 12
Tabela 3 – Exemplo de processamento da função Viterbi modificada ............. 14
Tabela 4 – Máquina de Estados da Função Viterbi Modificada........................ 15
XI
LISTA DE EQUAÇÕES
Equação 1 – Reversibilidade da Operação Xor .................................................. 6
Equação 2 – Processamento da Rodada na Cifra de Feistel ............................. 8
Equação 3 – Função Rodada do Algoritmo Papílio .......................................... 16
Equação 4 – Criptografia no Modo CBC .......................................................... 18
Equação 5 – Descriptografia no Modo CBC ..................................................... 18
Equação 6 – Criptografia no Modo CFB ........................................................... 20
Equação 7 – Descriptografia no Modo CFB ..................................................... 20
Equação 8 – Escolha da Função de Substituição da Rodada .......................... 26
Equação 9 – Escolha do Estado Inicial da Máquina de Estado da Função de
Substituição ...................................................................................................... 26
Equação 10 – Primeiro Bloco usado na Geração de Subchaves do Papílio
Versátil ............................................................................................................. 29
Equação 11 – Fator “C” Utilizado no Deslocamento de Blocos para Formação
das Subchaves ................................................................................................. 29
Equação 12 – Equivalência Entre os Blocos Utilizados na Criptografia e
Descriptografia ................................................................................................. 31
Equação 13 – Função de Dispersão Dupla que Determina a Subchave Utilizada
na Rodada ........................................................................................................ 32
Equação 14 – Função de Dispersão Dupla que Determina o Processamento ou
Não da Rodada Variável .................................................................................. 33
XII
Sumário
1. Introdução ........................................ .......................................................... 1
1.1. Motivação .............................................................................................. 2
1.2. Objetivos ............................................................................................... 2
1.3. Justificativa ............................................................................................ 3
1.4. Ferramentas utilizadas .......................................................................... 3
1.5. Organização do trabalho ....................................................................... 4
2. Embasamento Teórico ............................... ............................................... 5
2.1. A criptografia ......................................................................................... 5
2.2. Confusão, Difusão e Efeito Avalanche .................................................. 6
2.3. Cifra de bloco de Feistel ........................................................................ 7
3. Papílio ........................................... ........................................................... 10
3.1. Viterbi Modificado ................................................................................ 10
3.2. Algoritmo Papílio ................................................................................. 15
3.3. Modos de Operação ............................................................................ 16
3.3.1. Modo Livro de Código Eletrônico (ECB) ....................................... 17
3.3.2. Modo Codificador de Encadeamento de Bloco (CBC) .................. 18
3.3.3. Modo Codificador Realimentado (CFB) ........................................ 19
3.3.4. Modo de Saída com Realimentação (OFB) .................................. 21
4. Papílio XP ........................................ ......................................................... 23
5. Papílio Versátil .................................. ...................................................... 28
5.1. Chave variável .................................................................................... 28
5.2. Rodadas e alocação de subchaves variáveis ..................................... 31
5.3. Implementação .................................................................................... 34
6. Considerações Finais .............................. ............................................... 37
7. Bibliografia ...................................... ........................................................ 38
1
1. Introdução
A confidencialidade da informação é algo antigo buscado pela
humanidade. Por motivo de privacidade ou de buscar vantagem sobre alguma
informação, tem-se a procura pela confidencialidade da mesma.
Com o advento da Internet e até os dias atuais, ocorre a distribuição
de informações pela rede mundial, fazendo com que a demanda por segurança
da informação crescesse bastante, pois a Internet é utilizada para transações
bancárias, comércio, entre outras utilizações que demandam a
confidencialidade da informação enviada.
Com isso ocorre a utilização em escala global da criptografia, que
objetiva codificar um texto qualquer de modo que um eventual terceiro não
saiba qual é o texto original, permitindo, todavia, a recuperação do texto
original posteriormente por aqueles autorizados.
Neste contexto surge o algoritmo Papílio, resultado de um trabalho
de dissertação de mestrado (Ramos, Silva, & Bedregal, 2002). Consistindo em
um algoritmo de criptografia simétrico, estruturado na rede Feistel, que utiliza
como função de substituição e geração de subchaves, o algoritmo de
decodificação Viterbi modificado, o que confere ao algoritmo características de
confusão, difusão e efeito avalanche, desejáveis em algoritmos criptográficos.
Após, o Papílio teve alguns incrementos resultado de um trabalho de
graduação em Engenharia da Computação pela UFRN (Araújo, 2003),
possibilitando ao algoritmo utilização de várias funções de substituição,
passando este algoritmo incrementado a ser denominado de Papílio XP
(eXtreme).
Tendo como ponto de partida o algoritmo Papílio XP, o Papílio
Versátil busca acrescentar determinadas funcionalidades, conferindo ao
algoritmo maior versatilidade e segurança na criptografia, dificultando,
conseqüentemente, a criptoanálise (técnicas utilizadas para tentar decifrar
mensagens criptografadas).
2
1.1. Motivação
Este trabalho é motivado pelo interesse na área da criptografia,
especialmente no que concerne ao desenvolvimento do algoritmo Papílio, já
que alguns testes realizados com o mesmo em (Ramos, Silva, & Bedregal,
2002) e em (Araújo, 2003), demonstram que o algoritmo possui características
como confusão, difusão e efeito avalanche, o que o torna apto a ser utilizado
como algoritmo de criptografia seguro.
Desta forma, a busca por melhorias neste algoritmo tornando-o mais
seguro contra eventuais ataques é uma proposta interessante, já que o mesmo
pode obter índices de segurança semelhantes ou superiores aos algoritmos
criptógraficos mais difundidos atualmente.
1.2. Objetivos
O presente objetivo deste trabalho é implementar funcionalidades
adicionais ao algoritmo Papílio XP, de modo a dificultar a quebra da mensagem
e da chave através da criptoanálise, conferindo ao mesmo maior proteção na
criptografia.
As funcionalidades a serem implementadas são:
• A chave do algoritmo deve poder variar de tamanho, sendo apenas
limitada por um tamanho máximo e mínimo. Independente do tamanho
da chave, todos os seus bits devem ser utilizados na geração das
subchaves.
• A quantidade de rodadas efetuadas pelo algoritmo deve variar de acordo
com a mensagem a ser codificada e a chave utilizada.
• As subchaves alocadas para cada rodada também deve variar de
acordo com a mensagem a ser codificada e a chave utilizada.
3
1.3. Justificativa
A criptografia é uma área de estudo de grande importância
atualmente, tendo em vista a larga utilização da mesma na distribuição de
informação pela rede mundial de computadores (Internet).
Neste contexto insere-se o algoritmo Papílio como uma solução de
algoritmo criptográfico simétrico de bloco, baseado na cifra de Feistel.
Utilizando-se da função Viterbi modificado como função de substituição, a
mesma confere ao algoritmo características importantes a um algoritmo
criptográfico como a confusão, difusão e o efeito avalanche.
As funcionalidades acrescidas neste trabalho ao algoritmo Papilio,
confere ao mesmo maior proteção contra eventuais ataques, já que busca
dificultar a quebra de código por um eventual criptoanalista (pessoa que utiliza
técnicas para tentar decifrar códigos).
1.4. Ferramentas utilizadas
A implementação do Papílio Versátil foi realizada através da
linguagem de programação C, padrão ANSI, por ter sido a mesma utilizada no
trabalho anterior do Papílio XP, como também pelo fato da mesma conferir
facilidade em operações sobre bits e conferir melhor desempenho em relação a
outras linguagens de alto nível, como Java, Visua Basic, entre outras.
Para testes e depuração utilizou-se a ferramenta GNU Project
Debugger - GDB, possibilitando a correção de eventuais falhas e omissões. A
utilização deveu-se por ser uma ferramenta gratuita e por sua simplicidade no
uso.
Para o desenvolvimento da Interface gráfica do usuário foi utilizado a
ferramenta Microsoft Visual C++ 2008, por ser uma ferramenta que possibilita o
rápido desenvolvimento de interfaces gráficas para o ambiente Windows,
sendo também gratuito seu uso.
4
1.5. Organização do trabalho
O trabalho está organizado em 7 capítulos, de modo a discorrer de
modo geral sobre a criptografia e a cifra de feistel, o algoritmo Papílio
desenvolvido em (Ramos, Silva, & Bedregal, 2002), passando pelo Papílio XP
desenvolvido (Araújo, 2003), sendo após discorrido sobre o Papílio Versátil,
objeto deste trabalho.
O Capítulo 1 oferece uma introdução ao trabalho, apresentando o
tema, a motivação, os objetivos, a justificativa do tema, as ferramentas
utilizadas no desenvolvimento do Papílio Versártil, além desta seção que
apresenta a organização deste trabalho.
O Capítulo 2 apresenta embasamento teórico utilizado no
desenvolvimento do Papílio Versátil, discorre sobre a criptografia de um modo
geral, além da cifra de Feistel, base do algoritmo Papílio.
O Capítulo 3 apresenta o algoritmo Papílio original, desenvolvido em
(Ramos, Silva, & Bedregal, PAPÍLIO: Proposta de um Algoritmo de Criptografia
Baseado no Algoritmo Viterbi e Codificação Convolucional, 2002).
O Capítulo 4 apresenta o algoritmo Papílio XP, que é o Papílio
original com alguns incrementos, base deste trabalho, desenvolvido em
(Araújo, PapílioXP - Uma Extensão do Algoritmo Criptográfico Papílio, 2003).
O Capítulo 5 apresenta o algoritmo Papílio Versátil objeto deste
trabalho.
O Capítulo 6 apresenta algumas considerações finais sobre o
trabalho, enfatizando trabalhos futuros que podem ser realizados a partir deste.
O Capítulo 7 apresenta a bibliografia consultada e utilizada para a
realização deste trabalho.
5
2. Embasamento Teórico
2.1. A criptografia
A função da criptografia é cifrar um texto claro de modo que um
eventual terceiro não possa decodificar a mensagem, mas sim, apenas
autorizados.
Os algoritmos criptográficos utilizam duas técnicas de codificação: a
permutação e a substituição. Aquela consiste em trocar posições do texto,
fazendo um “embaralhamento” da mensagem; enquanto que esta consiste em
substituir partes do texto por outro texto.
Como exemplo de permutação e substituição, considere a
mensagem “ABC”, se permutamos a primeira letra pela última, a mensagem
fica “CBA”, podendo em seqüência aplicar uma substituição das letras “C” pela
letra “D”, ficando a mensagem como “DBA”.
Assim, os algoritmos criptográficos utilizam estas técnicas para gerar
texto codificado. Algoritmos que realizam vários estágios de permutação e
substituição são denominados de algoritmos produtos (Stallings, 2008, p. 19).
Por razões de segurança, os algoritmos de criptografia devem ser
conhecidos, ficando secreta apenas a chave/chaves que vai ser utilizada na
codificação e na decodificação, já que é mais conveniente tentar manter
secreta a chave e sua distribuição do que o algoritmo em si.
Algoritmos criptográficos que utilizam a mesma chave para a
criptografia e a descriptografia são denominados de simétricos ou de chave
privada, caso utilizem duas chaves distintas são denominados de assimétricos
ou de chave pública.
Sobre o modo como é processada a entrada, os algoritmos
criptográficos podem realizar processamento por bloco ou fluxo, naquele caso
o algoritmo processa um bloco de elementos da entrada, enquanto que neste
caso o algoritmo processa cada elemento da entrada por vez.
Tomando-se como exemplo a mensagem “ABC”, um algoritmo
criptográfico poderia processar o bloco “ABC” como um todo, sendo
6
considerado cifra de bloco, ou então, processar cada letra da mensagem em
separado sendo considerado cifra de fluxo.
Os algoritmos criptográficos têm como característica importante que
todo código cifrado tem que ser reversível, ou seja, deve se conseguir a
mensagem original, caso se tenha o código cifrado e a chave usada no
algoritmo criptográfico.
Para se conseguir isto, os algoritmos criptográficos utilizam funções
reversíveis como é o caso da operação Xor, conforme demonstrado a seguir:
����� ��� � �ℎ � = ����� �����
���� ����� � �ℎ � = ����� ���
Equação 1 – Reversibilidade da Operação Xor
Assim, o texto claro fica ocultado pela chave que não deve ser
conhecida por um eventual atacante. Considerando isso, os algoritmos
criptográficos utilizam desta operação Xor, além de técnicas de permutação e
substituição, para codificar um texto.
2.2. Confusão, Difusão e Efeito Avalanche
Os termos difusão e confusão foram introduzidos por Claude
Shannon com intuito de estabelecer classificação quanto à segurança de um
algoritmo criptográfico, pois os mesmos buscam frustrar a criptoanálise
estatística1 (Shannon, 1949 apud Stallings, 2008, p. 43).
Na difusão procura-se tornar a relação entre o texto claro e o cifrado
mais complexa possível, com intuito de tornar a descoberta do texto claro o
mais impraticável possível. Isto é feito, fazendo com que um bit do texto claro
tenha influência em vários outros do cifrado.
Na confusão semelhante à difusão, procura-se tornar a relação entre
o texto claro e a chave utilizada mais complexa possível, com intuito de tornar a
1 A criptoanálise estatística busca decifrar textos codificados, através de padrões
de texto encontrados no texto cifrado, como é o caso de letras e palavras que ocorrem mais
freqüentemente em uma determinada língua.
7
descoberta da chave o mais impraticável possível. Isto é feito através de uma
função de substituição complexa, que seja menos linear possível.
Já o efeito avalanche é uma propriedade do algoritmo que se
alterarmos um bit no texto claro ou na chave utilizada, haverá alteração de
vários bits no texto cifrado.
Juntos a confusão, a difusão e o efeito avalanche são propriedades
que conferem ao algoritmo criptográfico maior segurança contra a
decodificação do texto cifrado por um intruso.
2.3. Cifra de bloco de Feistel
Como proposta de algoritmo criptográfico simétrico que conferisse
maior difusão e confusão, Feistel (Feistel, 1973 apud Stallings, 2008, p. 43)
propôs o uso de uma cifra de bloco, que ficou conhecida como cifra de bloco de
Feistel.
Considerando a busca de maior difusão e confusão, Feistel criou
uma cifra de bloco de produto, que é “a execução de duas ou mais cifras
simples em seqüência, de tal forma que o resultado ou produto final seja
criptograficamente mais forte do que qualquer uma das cifras correspondentes”
(Feistel, 1973 apud Stallings, 2008, p. 43).
Esta cifra utiliza-se de funções de permutação e substituição para
criptografar o texto, de modo que seja empregada várias rodadas do algoritmo,
permitindo que a saída de uma rodada N seja a entrada de uma rodada N + 1.
A Figura 1 mostra a estrutura da rede de bloco de Feistel com 16
rodadas, Ei e Di representam os lados esquerdo e direito de cada bloco na
rodada de índice i, sendo utilizada em cada rodada subchaves (K1, K2, ..., K16)
que são geradas a partir da chave.
8
Figura 1 – Cifra de Feistel
A rede Feitel processa blocos de texto, de modo que inicialmente há
a divisão ao meio do bloco, gerando o lado esquerdo E e o lado direito D, estes
lados são processados a cada rodada de acordo com o polinômio a seguir:
E(i+1) = D(i)
D(i+1) = E(i) � F(D(i), K(i))
Equação 2 – Processamento da Rodada na Cifra de Feist el
Onde ‘i’ representa o índice da rodada e ‘F(D(i), K(i))’ representa a
função rodada que recebe como parâmetro o lado direito proveniente da
rodada anterior ou da divisão inicial caso seja a primeira rodada e a subchave
utilizada na rodada, proveniente de uma função de geração de subchaves que
utiliza a chave empregada no algoritmo como parâmetro.
9
Assim, e de acordo com (Stallings, 2008, p. 45), o projeto de um
algoritmo de criptografia estruturado na rede de bloco de Feistel, tem como
parâmetros que devem ser analisados:
• Tamanho do bloco: Blocos maiores oferecem maior segurança,
porém reduzem a perfomance do algoritmo.
• Tamanho da chave: Tamanho de chave maior significa maior
segurança, mas pode reduzir a perfomance dependendo do
algoritmo empregado.
• Número de rodadas: Pouca quantidade de rodadas pode significar
maior desempenho, porém a segurança é obtida com várias
rodadas, tipicamente utiliza-se 16 rodadas.
• Algoritmo de geração das subchaves: Deve oferecer a
complexidade suficiente para se atingir índices razoáveis de
confusão e efeito avalanche em torno da chave, dificultando o
máximo possível a criptoanálise.
• Algoritmo utilizado na função da rodada: Deve oferecer a
complexidade suficiente para se atingir índices razoáveis de
difusão e efeito avalanche em torno do texto claro, dificultando o
máximo possível a criptoanálise.
• Perfomance do algoritmo: Muitas vezes o algoritmo criptógrafico é
utilizado como utilitário embutido em alguma aplicação, o que
torna importante a perfomance do algoritmo.
10
3. Papílio
Este Capítulo é uma adaptação do descrito em (Ramos, Silva, &
Bedregal, 2002).
O algoritmo criptográfico Papílio desenvolvido em (Ramos, Silva, &
Bedregal, 2002) é uma cifra simétrica em bloco, baseado na cifra de bloco de
Feistel, no algoritmo Viterbi e na Codificação Convolucional.
Adotando como base o algoritmo de decodificação Viterbi, o mesmo
foi modificado de modo a atuar na função de substituição inserida na função
rodada do cifrador, como também na geração das subchaves a serem
utilizadas em cada rodada do algoritmo.
O Papílio, baseado na cifra de bloco de Feistel, tem como
características peculiares a utilização de bloco de entrada de tamanho de 8
Bytes (64 bits), como também a utilização de chave de tamanho de 16 Bytes
(128 bits), possuindo 16 rodadas no processo de cifragem.
3.1. Viterbi Modificado
O algoritmo proposto por Andrews Viterbi em (Viterbi, 1967) é
utilizado para decodificar códigos convolucionais, ou seja, processa códigos
gerados por determinado codificador convolucional com intuito de gerar o
código original antes da codificação.
O codificador convolucional codifica uma seqüência de bits em
ciclos, sendo descrito através de três parâmetros: a taxa “n/s” indica a razão de
bits de entradas e bits de saídas, por exemplo, a taxa 1/2 indica que a cada bit
de entrada, há dois de saída; o parâmetro Q indica em quantas saídas uma
dada entrada no ciclo irá influenciar; o parâmetro “m” indica quantos ciclos uma
dada entrada irá permanecer armazenada no codificador.
Assim, para um codificador convolucional com os parâmetros (n/s =
2, Q = 3, m = 2), pode-se ter o seguinte exemplo:
11
Figura 2 – Representação do Codificador Convolucion al (n/s = 2, Q = 3, m = 2)
A Figura 2 demonstra um codificador convolucional com entrada “Ti”
e saídas C1 e C2. Há o armazenamento de dois ciclos anteriores Ti-1 e Ti-2 de
modo que estes são iniciados zerados. Os polinômios que definem a saída do
codificador são definidos como C1 = (Ti Xor Ti-1) Xor Ti-2 e C0 = Ti Xor Ti-2,
sendo C1 o bit mais significativo.
O codificador pode ser representado através de uma máquina de
estados, de modo que os estados são representados pelos bits armazenados
em Ti-1 e Ti-2, a entrada pelo bit Ti, e a saída composta pelos bits C1 e C0.
Estado
Entrada = 0 Entrada = 1
Saída Estado Saída Estado
00 00 00 11 10
01 11 00 00 10
10 10 01 01 11
11 01 01 10 11
Tabela 1 – Máquina de Estado do Codificador Convoluc ional (n/s = 2, Q = 3, m = 2)
O decodificador Viterbi tem a finalidade de reconstruir os bits de
entrada do codificador convolucional, dado uma entrada codificada. Para isso,
utiliza-se de um diagrama denominado treliça, que representa a transição de
estados do codificador convolucional em função da entrada. A Figura 3
representa a treliça para o codificador convolucional supra descrito, com
parâmetros (n/s = 1/2, Q = 3, m = 2).
12
Figura 3 – Treliça do Codificador Convolucional (n/ s = 2, Q = 3, m = 2)
Através do diagrama treliça acima pode se construir uma máquina
de estados que representa o decodificador utilizado para decodificar códigos
gerados pelo codificador convolucional anteriormente descrito.
O decodificador terá 4 estados, já que o parâmetro “m” do
codificador é igual a 2. Pela treliça, considerando o codificador em t=0, se
entrarmos “0” teremos “00” como saída e “00” como estado, caso entrarmos “1”
teremos “11” como saída e “10” como estado.
Desta forma o decodificador receberá “00” ou “11” como entrada no
estado “0”, caso seja entrado “00” terá “0” como saída e permanecerá no
estado “00”; caso seja entrado “11” terá “1” como saída e transitará para o
estado “10”.
Sendo isto feito em diante para t1, t2, ..., com intuito de se
determinar quais são todas as saídas e transições de estado correspondente
na máquina de estados que representa o decodificador para este tipo de
codificador convolucional. A Tabela 2 mostra a máquina de estados
correspondente.
Estado Atual Entrada Saída Próximo Estado
00 00 0 00
11 1 10
01 00 1 10
11 0 00
10 01 1 11
10 0 01
11 01 0 01
10 1 11
Tabela 2 – Decodificador Viterbi (n/s = 2, Q = 3, m = 2)
13
Como se percebe na Tabela 2, para cada estado do decodificador
há uma quantidade limitada de entradas, não contemplando todas as entradas
possíveis.
Isso é válido para qualquer decodificador Viterbi (taxa de codificação
1/2, 2/3, 3/4, ...), já que o código a ser processado é decorrente do
processamento de um codificador convolucional.
Consideração esta limitação em torno das entradas possíveis a
serem processadas pelo algoritmo Viterbi, o trabalho desenvolvido em (Ramos,
Silva, & Bedregal, 2002) implementa o algoritmo Viterbi modificado que busca
ampliar o campo de entradas possíveis a serem processadas, permitindo que
seja processada qualquer entrada.
Para isso, ocorre a geração de duas saídas (S0 e S1), sendo S0 o
processamento do decodificador Viterbi propriamente dito, gerando um rótulo
de saída para cada um de entrada; sendo S1 a saída que contém a informação
se o rótulo de entrada é tratável ou não pelo decodificador Viterbi, ocorrendo o
bit ‘0’ caso não seja e o bit ‘1’ caso contrário.
De acordo com o extraído em (Ramos, Silva, & Bedregal, 2002, p.
41):
“No caso dos rótulos de entrada que não podem ser tratados pelo
estado atual, a proposta apresentada nesta dissertação é que o rótulo
não tratável passe pelo processo de codificação convolucional
considerando isoladamente cada bit formador do rótulo. Para o
processo de codificação convolucional usa-se como estado inicial o
estado atual. Nota-se que a codificação convolucional vai gerar [s/n]
de rótulos adicionais, sendo n/s a taxa de codificação convolucional.
Com este procedimento os rótulos gerados podem ser tratados pelo
algoritmo Viterbi. A aplicação do algoritmo Viterbi geraria um rótulo de
tamanho n para cada um dos rótulos adicionais gerados. Entretanto o
que interessa para a codificação é a geração de um único rótulo de
tamanho n. A solução adotada consiste em considerar, para compor o
fluxo S0, apenas o primeiro dos [s/n] rótulos de tamanho n (o fluxo
S1, nestes casos, e só nestes casos recebe o valor 1). Para a
continuação do processo de codificação usando o algoritmo Viterbi
adota-se como estado atual o estado final do processo de codificação
convolucional, até que um novo rótulo não tratável seja encontrado ou
terminar a codificação.”
14
Como exemplo de como o algoritmo Viterbi modificado funciona é
considerado o decodificador exposto anteriormente na Tabela 2. Tendo como
entrada “11011000”, tem-se o seguinte processamento:
Estado Entrada Saídas Observação
“00” “11” S0=”1”,
S1=”0’
Rótulo tratável
“10” “01” S0=”11”,
S1=”00”
Rótulo tratável
“11” “10” S0=”111”,
S1=”000”
Rótulo tratável
“11” “00” S0=”1110”,
S1=”0001”
Rótulo não tratável, aplica-se codificador
convolucional na entrada “00”, gerando “01” e “11”
como saída, aplicando-se, em seguida, Viterbi no
primeiro rótulo “01”, tendo como saída “0” que
comporá o S0
Tabela 3 – Exemplo de Processamento da Função Viterb i Modificada
Este processo que gera as saídas S0 e S1 pode ser representado
utilizando-se uma máquina de estados. Como exemplo de máquina de estados
considerando um codificado convolucional com parâmetros (n/s=1/2,Q=3,
m=2), de acordo com o descrito no exemplo anterior tem-se:
Estado Atual Entrada S0 S1 Próximo Estado
00
00 0 0 00
01 0 1 10
10 1 1 01
11 1 0 10
01
00 1 0 10
01 0 1 10
10 1 1 01
11 0 0 00
10
00 0 1 00
01 1 0 11
10 0 0 01
15
11 1 1 11
11
00 0 1 00
01 0 0 01
10 1 0 11
11 1 1 11
Tabela 4 – Máquina de Estados da Função Viterbi Modif icada
A função Viterbi modificada é implementada no algoritmo Papílio
através de tabelas como a Tabela 4. Esta máquina de estado disposta através
de uma tabela garante a geração de duas saídas S0 e S1 de N Bytes cada
para qualquer entrada fornecida de 2N Bytes.
3.2. Algoritmo Papílio
A Figura 4 demonstra como é a estrutura do algoritmo Papílio. O
algoritmo tem a mesma estrutura da cifra de Feistel, utiliza-se de blocos de 64
bits como entrada, chave de 128 bits, e realiza 16 rodadas.
Figura 4 – Algoritmo Papílio
16
O diferencial do algoritmo é a utilização da função Viterbi modificado,
utilizada como função de substituição dentro da função rodada, como também
na geração das subchaves.
A função rodada utilizada no algoritmo tem a seguinte forma:
F(LD(i), SC(i)) = VM(LD(i) � SC(i))
Equação 3 – Função Rodada do Algoritmo Papílio
Onde ‘i’ é o índice da rodada, LD(i) é o lado direito do bloco entrado,
SC(i) é a chave utilizada na rodada e VM é a função Viterbi modificado.
Para a geração das subchaves utiliza-se a função Viterbi modificado
tendo a chave de 128 bits como parâmetro, gerando duas saídas de 64 bits,
estas são processadas novamente pela função Viterbi modificado gerando
quatro subchaves. Para a geração das demais subchaves concatena-se as
quatro subchaves anteriormente geradas, aplicando o mesmo procedimento, e
assim por diante, até serem geradas as 16 subchaves que serão aplicadas em
cada função rodada.
O processo de descriptografia utiliza o mesmo algoritmo, apenas
ocorrendo a inversão das rodadas, como também da ordem das subchaves
utilizadas.
3.3. Modos de Operação
O algoritmo Papílio por ser uma cifra de bloco, cifra cada bloco
considerando-o isoladamente, porém com intuito de se estabelecer uma
cifragem considerando o texto cifrado como um todo, o algoritmo pode operar
em modos diferentes.
Como mostrado a seguir estes modos de operação não modificam a
forma como um bloco é processado no processo de codificação/decodificação.
O que ocorre são operações realizadas sobre estes blocos de modo a adaptar
o texto cifrado a uma finalidade específica.
17
3.3.1. Modo Livro de Código Eletrônico (ECB)
Este modo é o mais simples de ser implementado, consiste em
considerar cada bloco isoladamente no texto cifrado. A cada bloco cifrado o
mesmo é disposto no texto cifrado em ordem, de modo que a descriptação da
mensagem ocorra de forma independente entre os blocos, ou seja, pode
descriptar um bloco qualquer, sem que ocorra a necessidade de descriptar
outro bloco.
Como ocorre a utilização independente dos blocos, este modo traz
vantagens para operação em banco de dados e sistemas de arquivos em geral,
pois pode se buscar a mensagem de forma aleatória.
Outras vantagens estão na codificação de mensagens pequenas
como senhas e chaves, já que neste tipo de mensagem tem-se um único ou
poucos blocos; como também no fato de se ter maior robustez contra erro, já
que se ocorrer um erro em algum bloco, o mesmo não afeta os demais.
Para mensagens maiores este modo mostra-se inseguro, já que
pode ter padrões estruturados na mensagem, que podem ser captados pela
repetição de blocos iguais.
A Figura 5 e a Figura 6 demonstram graficamente como se dar o
processo de criptografia e descriptografia neste modo, respectivamente.
Figura 5 – Criptografia no Modo ECB
18
Figura 6 – Descriptografia no Modo ECB
3.3.2. Modo Codificador de Encadeamento de Bloco (CBC)
Neste modo, diferentemente com o que ocorre no modo ECB,
procura-se evitar repetição de padrões de bloco no texto cifrado. Para isso, o
bloco de entrada de cada processo de codificação consiste no resultado da
operação Xor do bloco cifrado anterior com o bloco de entrada a ser
processado, ocorrendo na descriptação estas mesmas operações Xor com o
texto cifrado a fim de que se possa recuperar a mensagem original.
No primeiro bloco a ser cifrado, por não possuir ciframento anterior,
utiliza-se um Vetor de Inicialização como se fosse o bloco cifrado anterior.
Desta forma o processo de criptografia dar-se da seguinte forma:
�� = �����������, �� = ��
Equação 4 – Criptografia no Modo CBC
Onde “i” é o índice referente à seqüência do bloco no texto, “��” é o
bloco cifrado de índice i, “��” é a função de encriptação, “��” é o bloco de texto
claro de índice i, “VI” é o Vetor de Inicialização.
Sendo o processo de descriptografia composto da seguinte forma:
�� = �����������, �� = ��
Equação 5 – Descriptografia no Modo CBC
Onde “i” é o índice referente à seqüência do bloco no texto, “��” é o
bloco cifrado de índice i, “��” é a função de descriptação, “��” é o bloco de
texto claro de índice i, “VI” é o Vetor de Inicialização.
A Figura 7 e a Figura 8 demonstram graficamente como se dar o
processo de criptografia e descriptografia neste modo, respectivamente.
19
Figura 7 – Criptografia no Modo CBC
Figura 8 – Descriptografia no Modo CBC
3.3.3. Modo Codificador Realimentado (CFB)
No modos anteriores ocorre a necessidade de se trabalhar com
blocos completos para a codificação, de modo que é inviabilizado utilizar-se de
partes de bloco.
Para evitar esta restrição e conseguir trabalhar semelhante a um
codificador de fluxo, existem os modos CFB e OFB. Assim, se precisar
trabalhar com fluxo de dados, como numa transmissão de dados em rede por
exemplo, estes modos podem ser utilizados.
No modo CFB é definida uma unidade de transmissão s, ocorrendo
o ciframento do bloco cifrado anterior, realizando-se a operação Xor dos s bits
mais significativos do resultado do ciframento com o bloco de texto claro. Da
mesma forma que no modo CBC, necessita-se utilizar um Vetor de Inicialização
- VI, já que não existe o bloco cifrado anterior no início da cifragem.
Assim a criptografia deste modo é disposta da seguinte forma:
20
�� = �����[��������], �� = ��
Equação 6 – Criptografia no Modo CFB
Onde “i” é o índice referente à seqüência do bloco no texto, “��” é o
bloco cifrado de índice i, “��” é a função de encriptação, “��” é o bloco de texto
claro de índice i, “VI” é o Vetor de Inicialização e “��” são os i bits mais
significativos.
Sendo o processo de descriptação disposto da seguinte forma:
�� = �����[��������], �� = ��
Equação 7 – Descriptografia no Modo CFB
Onde “i” é o índice referente à seqüência do bloco no texto, “��” é o
bloco cifrado de índice i, “��” é a função de encriptação, “��” é o bloco de texto
claro de índice i, “VI” é o Vetor de Inicialização e “��” são os i bits mais
significativos.
A Figura 9 e a Figura 10 demonstram graficamente como se dar o
processo de criptografia e descriptografia neste modo, respectivamente.
Figura 9 – Criptografia no Modo CFB
21
Figura 10 – Descriptografia no Modo CFB
3.3.4. Modo de Saída com Realimentação (OFB)
Este modo é semelhante ao CFB, alterando que a entrada que
alimenta o cifrador em cada bloco processado é a saída da função de
criptografia, ao invés do texto cifrado anterior.
Isto faz com que os erros ocorridos na cifragem anterior não se
propaguem em diante, por exemplo, caso ocorra um erro em algum bit de ��, o
erro não irá se propagar para ��"� em diante, sendo �� o texto cifrado do bloco
de índice i.
A Figura 11 e a Figura 12 demonstram graficamente como se dar o
processo de criptografia e descriptografia neste modo, respectivamente.
Figura 11 – Criptografia no Modo OFB
23
4. Papílio XP
O algoritmo Papílio XP é uma extensão do algoritmo Papílio, sendo
desenvolvido em (Araújo, PapílioXP - Uma Extensão do Algoritmo Criptográfico
Papílio, 2003), que utiliza blocos de 16 Bytes (128 bits) para processamento,
ao invés dos blocos de 8 Bytes (64 bits) utilizados anteriormente no Papílio
original.
Este trouxe inovações ao aumentar o número de máquinas de
estados que podem ser utilizadas como função de substituição (Viterbi
modificado) na função rodada, ao invés de uma única como antes, como
também possibilitar a variação do estado inicial destas máquinas.
A escolha das 8 novas máquinas de estados utilizadas deu-se a
partir de um programa de seleção das máquinas, denominado “torneio”.
A escolha da máquina dentre as oito que será utilizada como função
de substituição na rodada, como também seu estado inicial, é determinada por
uma função de dispersão dupla, que de acordo com (Szwarcfiter & Markenzon,
1994 apud Araújo, 2003, p. 33): “A razão para o uso de uma função de
dispersão dupla é que elas retornam índices que são equiprováveis para um
vasto conjunto de entradas”.
A função de dispersão dupla é composta por duas funções de
dispersão, tendo como finalidade fornecer um índice a partir de uma
determinada entrada, que será utilizado para a escolha da máquina de estados.
As funções de dispersão recebem como parâmetro de entrada um
bloco de N Bytes e os N Bytes tamanho do bloco. A seguir são descritos os
algoritmos em linguagem C das funções de dispersão utilizadas pela função de
dispersão dupla:
/* dispercao pelo metodo Xor */
unsigned long dispXor (unsigned char* key, int
size)
{
unsigned long disp;
unsigned char* pt;
int x, half;
24
disp = 0;
pt = (unsigned char*)&disp;
half = sizeof(unsigned long)/2;
for (x=0; x < size; x++)
pt[x%half] ^= key[x];
return disp;
}
/* dispercao metodo da multiplicacao */
unsigned long dispMul (unsigned char* key, int
size)
{
unsigned long disp;
unsigned char* pt;
int x, half;
disp = 0;
pt = (unsigned char*)&disp;
half = sizeof(unsigned long)/2;
/* metodo da dobra com XOR */
for (x=0; x < size; x++)
pt[x%half] ^= key[x];
disp = disp*disp; /* produto */
disp >>= (8*half)/2; /* depreza a metade dos
bits */
25
return disp;
}
A função de dispersão dupla recebe como parâmetros um bloco de
N Bytes e um índice. Utilizando as funções de dispersão supra descritas gera
um número que é limitado dentro de um determinado conjunto pela operação
módulo. Assim a função é descrita em linguagem C a seguir:
void dispDupla (unsigned char* block, int round)
{
unsigned long machine, disp1, disp2;
disp1 = dispXor (block, HALF_BLOCK);
disp2 = dispMul (block, HALF_BLOCK);
if ((disp2%2)==0)
disp2++;
return (disp1 + round * disp2) % RANGE;
}
Cabe destacar que o último comando da função adota uma
constante “RANGE” que vai limitar a quantidade de números na saída. Isto é
realizado para se conseguir um número dentro de um determinado conjunto,
por exemplo, se há 16 máquinas de estados e deve-se escolher uma, a
constante “RANGE” deve ser ajustado igual a 16, pois assim fornecerá um
número entre 0 e 15, determinando qual máquina de estado será utilizada.
O algoritmo Papílio XP (Araújo, 2003) utiliza esta função para a
escolha da máquina de estados a ser utilizada como função de substituição na
rodada da seguinte forma:
26
DISP(LD(i) � Subchave(i), i) = [1 … 16]
Equação 8 – Escolha da Função de Substituição da Roda da
Onde ‘DISP’ é a função de dispersão dupla, ‘LD(i)’ é o lado direito do
bloco entrado da rodada ‘i’, ‘subchave(i)’ é a subchave utilizada na rodada ‘i’,
‘i’ é o índice da rodada.
Além da escolha da máquina de estado, referente à função de
substituição, ocorre também a escolha do seu estado inicial, dentre os 4
estados possíveis.
Para a escolha do estado inicial da máquina o algoritmo utiliza a
função de dispersão dispXor anteriormente descrita, da seguinte forma:
DISPXOR(LD(i) � Subchave(i), 8) = [1 … 4]
Equação 9 – Escolha do Estado Inicial da Máquina de Est ado da Função de
Substituição
Onde ‘DISPXOR’ é a função de dispersão dispXor, ‘LD(i)’ é o lado
direito do bloco entrado da rodada ‘i’, ‘subchave(i)’ é a subchave utilizada na
rodada ‘i’, o parâmetro ‘8’ refere-se ao tamanho do bloco entrado em Bytes,
que no caso é igual a 8.
Nota-se que desta forma a escolha da máquina de estado fica
dependente tanto do texto entrado como da chave, o que confere ao algoritmo
grande variação na cifragem do texto claro, já que para variar as funções de
substituição utilizadas basta modificar o texto claro entrado, servindo a
subchave para ocultar o texto utilizado.
Se compararmos com o Papílio em sua versão original, há uma
grande versatilidade no total de combinações de máquinas que podem ser
utilizadas desta forma. Com 8 máquinas de estados disponíveis e com cada
uma contendo 4 estados diferentes, em 16 rodadas, iremos ter �4 × 8��& ≈
12 × 10+, combinações de funções de substituições que poderão ser
utilizadas.
Esta possibilidade de variar a máquina de estado por rodada, assim
como seu estado inicial, oferecendo o equivalente a 12 × 10+, combinações
de funções de substituição, confere ao algoritmo Papílio XP maior proteção
27
contra a criptoanálise, já que a escolha da máquina depende do texto claro e
da chave utilizados, informações que não estão disponíveis a um eventual
criptoanalista.
28
5. Papílio Versátil
Tendo como base o Papílio XP (Araújo, PapílioXP - Uma Extensão
do Algoritmo Criptográfico Papílio, 2003), este trabalho implementou algumas
mudanças no mesmo buscando conferir maior versatilidade e segurança contra
a criptoanálise. Assim considerando a versatilidade alcançada pelo algoritmo, o
mesmo ficou denominado de Papílio Versátil.
Assim como no Papílio XP, o Papílio Versátil processa blocos de 16
Bytes (128 bits) de tamanho.
As implementações, conforme descritas nos objetivos do trabalho,
passam a ser explicadas a seguir.
5.1. Chave variável
A chave do Papílio XP tem tamanho de 16 Bytes (128 bits), sendo
esta de tamanho fixo, não permitindo variação de tamanho. Considerando isso,
o Papílio Versátil alterou esta rigidez, possibilitando utilização de chaves de
tamanho variável, podendo ser utilizadas chaves de tamanho entre 16 Bytes
(128 bits) e 128 Bytes (1024 bits).
Para isso, houve alteração no modo como são construídas as
subchaves do Papílio. Considerando que são processado blocos de 16 Bytes
(128 bits), devem-se gerar subchaves de tamanho de 8 Bytes (64 bits), tendo
em vista a utilização das mesmas na operação Xor com a metade direita do
bloco da rodada, que contém 8 Bytes (64 bits).
O algoritmo de construção das subchaves consiste em formar blocos
de 16 Bytes (128 bits) a partir da chave, de modo que estes possam servir de
entrada para a função Viterbi Modificado, que a partir desta entrada gera duas
subchaves de 8 Bytes (64 bits) cada.
Como a quantidade máxima de rodadas é igual a 16, devem-se ser
formados 8 blocos de 16 Bytes (128 bits) a partir da chave, de modo que estes,
após serem processados pela função Viterbi modificado, gerem as 16
subchaves de 8 Bytes (64 bits), conforme pretendido.
29
A geração do primeiro bloco de 16 Bytes é realizada concatenando
os primeiros 8 Bytes da chave com o inverso dos últimos 8 Bytes. Assim tem-
se que o primeito bloco será:
Bloco1[1 ... 8] = Chave [1 ... 8]
Bloco1[9 ... 16] = Chave [N ... N - 7]
Equação 10 – Primeiro Bloco usado na Geração de Subcha ves do Papílio Versátil
Onde N é o tamanho da chave em Bytes.
A geração dos demais blocos é realizada percorrendo-se toda a
chave de modo a aproveitar todos os bits dispostos na mesma.
Desta forma, para a geração dos subseqüentes blocos é definido
preliminarmente um fator “C” definido da seguinte forma:
C = N / 16
Equação 11 – Fator “C” Utilizado no Deslocamento de Blocos para Formação das
Subchaves
Onde N é o tamanho da chave em Bytes e “16” refere-se à
quantidade de subchaves a serem geradas.
Tendo sido definido o fator “C”, os subseqüentes blocos são gerados
acrescentando à primeira metade do bloco e subtraindo à outra metade deste,
o referido fator multiplicado pelo índice ‘i’, usado como variável de iteração.
Sendo então as subchaves geradas da seguinte forma:
Para i = 1; i < 8; i++ faça
Bloco[1 ... 8] = Chave[i*C, i*C + 8]
Bloco[9 ... 16] = Chave[(N – 7) – i*c, N - i*C]
Com isso, os blocos de 16 Bytes são formados pela concatenação
de dois blocos de 8 Bytes, gerados a partir da chave, percorrendo-a das pontas
em direção ao seu centro, de modo a aproveitar todos os bits, sendo este
aproveitamento possibilitado pelo deslocamento afetado pelo fator ‘C’.
Cabendo destacar que sempre ocorre a inversão dos bits na
segunda metade do bloco formado.
30
A Figura 13 demonstra esquematicamente como ocorre a geração
das subchaves no Papílio Versátil.
CHAVE DE N BYTES
8 Bytes 8 Bytes
FUNÇÃO VITERBI MODIFICADO
SUBCHAVE DE 8 BYTES SUBCHAVE DE 8 BYTES
Figura 13 – Geração de Subchaves no Papílio Versátil
Assim são gerados 8 blocos de 16 Bytes, que são aplicados à
função Viterbi Modificado, gerando as 16 subchaves de 8 Bytes cada, que
serão utilizadas em cada função rodada.
Percebe-se deste modo que as subchaves são formadas
aproveitando todos os bits dispostos na chave, o que eleva a dificuldade de se
conseguir um ataque por força bruta (tentativa de se conseguir a chave
vasculhando todas as possibilidades de combinações de bits da mesma).
Se considerarmos o tamanho mínimo da chave (16 Bytes) tem-se
2�+- ≈ 3,4 ∗ 10,- combinações de chaves, caso seja considerado o tamanho
máximo (128 Bytes) tem-se 2��+0 ≈ 1,79 ∗ 10,�-, que é o pior caso a ser
considerado, porém como um eventual criptoanalista desconhece o tamanho
da chave, em tese, as combinações no total dar-se pela soma das
combinações em cada tamanho da chave, ou seja, ∑ 2�∗-�+-�4�& combinações.
Outro ponto a se destacar, é que a utilização de chaves maiores
detrimento a de chaves menores, não prejudica o desempenho do algoritmo, já
que o processamento das subchaves é o mesmo, só alterando o deslocamento
dos blocos capturados da chave através do fator “C” supra descrito.
31
5.2. Rodadas e alocação de subchaves variáveis
A implementação destas funcionalidades no algoritmo baseia-se na
idéia adotada na escolha das máquinas de estado e seu estado inicial no
Papílio XP (Araújo, 2003), descrita a seguir.
De acordo com a Equação 2:
LE(i+1) = LD(i)
LD(i+1) = LE(i) � F(LD(i), SC(i))
Implicando no fato de que o semibloco de lado direito não é
modificado durante o processamento da rodada, ocorrendo apenas uma
permutação na qual o mesmo passa a ser o lado esquerdo seguinte.
Assim o semibloco do lado direito pode ser recuperado no processo
de descriptografia, pois neste processo ocorre o processamento do mesmo
algoritmo invertendo as rodadas, fazendo com que:
ED(0) = DC(16), DD(0) = EC(16)
ED(1) = DC(15), DD(1) = EC(15)
[…]
ED(16) = DC(0), DD(16) = EC(0)
Equação 12 – Equivalência Entre os Blocos Utilizados n a Criptografia e
Descriptografia
Onde ED(i) e DD(‘i’) referem-se, respectivamente, ao lado esquerdo
e ao lado direito do bloco de entrada da rodada ‘i’ do processo de
descriptografia; EC(i) e DC(i) referem-se, respectivamente, ao lado esquerdo e
ao lado direito do bloco de entrada da rodada ‘i’ do processo de criptografia.
Assim, tendo que DD(0) = EC(16), e utilizando a Equação 2
referente ao processamento da rodada, temos que EC(16) = DC(15), o que
resulta em DD(0) = DC(15), demonstrando que o lado direito do bloco entrado
numa determinada rodada do processo de criptografia é o mesmo entrado na
mesma rodada do processo de descriptação, já que as rodadas são invertidas.
Sendo válido a mesma demonstração para todas rodadas.
32
Isto implica no fato de que se for utilizada a informação contida no
lado direito do bloco no processo de criptografia, a mesma pode ser
recuperada no processo de descriptografia, sem precisar guardar nenhuma
informação adicional no texto cifrado.
Este fato de que a informação contida no lado direito do bloco de
cada rodada pode ser recuperada no processo de descriptografia é a idéia
principal para tornar possível a escolha da máquina de estado e seu estado
inicial no Papílio XP (Araújo, 2003). Assim como, a mesma idéia foi adotada
neste trabalho para possibilitar a variação de rodadas no algoritmo, como
também a variação das subchaves alocadas nas rodadas.
A utilização desta informação é combinada com informação contida
na chave através da operação Xor, possibilitando a ocultação da mesma pela
chave. Isto implica na impossibilidade de um eventual criptoanalista decifrar
qual máquina de estado e seu estado inicial foram utilizados na rodada;
quantas rodadas foram processadas pelo algoritmo; assim como qual subchave
foi utilizada em cada rodada; já que não há o conhecimento da chave pelo
mesmo.
No Papílio XP (Araújo, 2003), as subchaves são alocadas em ordem
para cada rodada, tendo cada uma delas um rótulo de 1 a 16, que designará à
qual rodada a mesma será alocada.
Contudo o Papílio Versátil alterou esta rigidez, de modo que as
subchaves alocadas em cada rodada são escolhidas aplicando-se a função de
dispersão dupla abordada no Capítulo 4, implementada no Papílio XP (Araújo,
2003).
Retornando a função valor entre 1 e 16, tendo como parâmetros o
resultado da operação Xor dos 4 Bytes iniciais concatenados com os 4 finais da
chave com o lado direito do semibloco da rodada, além do índice da rodada
corrente. Definida então a função da seguinte forma:
SH[1 ... 4] = Chave[1 ... 4]
SH[5 ... 8] = Chave[N – 3 ... N]
DISP(LD(i) � SH, i) = [1 … 16]
Equação 13 – Função de Dispersão Dupla que Determina a Subchave Utilizada na
Rodada
33
Onde ‘Chave’ é a chave utilizada, ‘DISP’ é a função de dispersão
dupla, ‘SH’ é o vetor auxiliar que armazena o início e o final da chave, ‘i’ é o
índice da rodada e ‘LD’ é o semibloco do lado direito.
Assim, a função de dispersão dupla irá retornar um valor na faixa de
1 a 16 indicando qual é a subchave que será utilizada na rodada corrente.
A possibilidade de variar as rodadas é outra funcionalidade
implementada que conferiu ao Papílio ainda mais versatilidade. As rodadas do
algoritmo variam de 8 a 16.
Isso é realizado, fixando o número mínimo de rodadas fixas (foi
atribuído 8) que são obrigatoriamente processadas, e variando o restante, de
modo a permitir o processamento de 0 a 8 rodadas a mais.
As rodadas fixas são processadas normalmente, enquanto que para
definir o processamento das demais rodadas variáveis é utilizada a função de
dispersão dupla abordada no Capítulo 4, implementada no Papílio XP (Araújo,
2003).
A função de dispersão dupla recebe como parâmetros o resultado da
operação Xor do lado direito do bloco da rodada com a subchave da rodada,
além do índice da rodada, retornando o valor ‘0’ ou ‘1’. Assim esta função tem a
seguinte forma:
DISP(LD(i) � Subchave(i), i) = {0, 1}
Equação 14 – Função de Dispersão Dupla que Determina o Processamento ou Não da
Rodada Variável
Onde ‘LD’ é o semibloco do lado direito da rodada ‘i’, ‘Subchave’ é a
subchave utilizada na rodada ‘i’, ‘i’ é o índice da rodada e ‘DISP’ é a função de
dispersão dupla.
Caso esta função de dispersão retorne ‘1’ a rodada é processada
normalmente, caso contrário não ocorre o processamento normal da rodada,
mas apenas a troca dos lados direito e esquerdo do bloco entrado na rodada.
O não processamento da rodada implica então em não utilizar a
função de substituição (Viterbi modificado) na rodada, ocorrendo apenas uma
simples permutação, que é a troca das metades do bloco.
O incremento destas variações no algoritmo confere ao algoritmo
que utiliza 8 máquinas de estado para função Viterbi, contendo cada 4 estados,
34
além de 16 subchaves que são alocadas independentemente da rodada, 48 (8
* 4 + 16) possibilidades de combinações por rodada, o que resultaria no total
de 48�& ≈ 794 × 10+0 combinações caso fossem efetuadas 16 rodadas.
Porém como a quantidade de rodadas varia entre 8 e 16 no Papílio
Versátil não se tem a princípio a quantidade de rodadas que será efetuada pelo
algoritmo, o que implica em considerar as combinações totais para cada
quantidade de rodada
Assim para se chegar à quantidade de combinações resultante, sem
que se tenha o conhecimento da quantidade rodadas, tem-se ∑ 48��4-
�&
combinações totais considerando a variação da máquina de estado, seu estado
inicial, das subchaves, além das rodadas a serem processadas.
Dar-se maior processamento efetuado para se conseguir estas
variações, devido ao processamento utilizado nas funções de dispersão
dispostas no Capítulo 4, o que é viável devido à rápida execução destas
funções, dada em complexidade polinomial.
Cabendo destacar que apesar da variação de rodadas conferir uma
maior segurança contra a criptoanálise, esta não implica em redução no
desempenho do algoritmo, mas sim, em aumento, já que pode ocorrer menos
processamento de rodadas de acordo com um determinado bloco de texto.
5.3. Implementação
O Papílio Versátil foi implementado utilizando a linguagem C, padrão
ANSI, exceto para o desenvolvimento da Interface Gráfica do Usuário, que foi
utilizada a ferramenta Microsoft Visual C++ 2008.
Desta forma, a interface gráfica é implementada utilizando a
linguagem C++, fazendo uso das bibliotecas que fazem parte da plataforma
.NET da Microsoft. Esta plataforma oferece diversos recursos gráficos para
construção de interfaces gráficas do usuário.
Com isso, para se fazer uso da Interface Gráfica com Usuário
implementada é necessário executar o software no sistema operacional
Windows, tendo que ser instalada a plataforma .NET com versão igual ou
superior à 2.0.
35
A Figura 14 demonstra a interface gráfica do usuário do Papílio
Versátil.
Figura 14 – Inteface Gráfica do Usuário do Papílio Ve rsátil
O arquivo de entrada que será criptografado/descriptografado é
aberto através do botão “Abrir Entrada”, sendo a caixa “Arquivo de Entrada
Carregado” marcada após o carregamento do arquivo.
A chave é entrada no campo de texto que tem o rótulo “Chave (16 a
128 Chars)”, podendo também ser aberta através de um arquivo específico
pelo botão “Abrir Chave”.
O Vetor de Inicialização, utilizado nos modos de operação CBC,
CFB e OFB, é entrado no campo de texto que tem o rótulo “Vetor de
Inicialização (16 Chars)”, podendo também ser aberto através de um arquivo
específico pelo botão “Abrir Vetor de Inicialização”.
36
A Unidade de Transmissão, utilizada nos modos de operação CFB e
OFB, é entrada no campo numérico que tem o rótulo “Unidade de
Transmissão”.
O modo de operação (ECB, CBC, CFB, OFB) e a operação
(Criptografia, Descriptografia) são selecionados através de botões redondos,
contidos em painéis nominados “Modo de Operação” e “Operação”
respectivamente.
Para executar o algoritmo utiliza-se o botão “Executar”, sendo o
botão “Limpar” utilizado para limpar todos os campos.
Após a execução do algoritmo o texto cifrado/descrifrado é
armazenado num local determinado pelo usuário, o qual poderá servir
posteriormente de entrada para o algoritmo.
37
6. Considerações Finais
Foram alcançados neste trabalho algumas implementações que
conferiram ao Papílio maior versatilidade, tornando-o mais resistente contra a
criptoanálise.
Outra implementação, que pode ser realizada para aumentar a
versatilidade e proteção contra a criptoanálise, é a variação do tamanho do
bloco a ser processado, o que pode torna-se objeto de trabalho futuro.
Não houve testes de perfomance e complexidade do algoritmo
Papílio Versátil, não podendo se constatar os resultados práticos decorrente
deste trabalho.
Logo, testes que experimentem índices de difusão, confusão e efeito
avalanche são importantes para fazer uma análise comparativa da
complexidade deste algoritmo com outros algoritmos criptográficos mais
difundidos.
Outros testes que podem ser realizados para verificar a
complexidade do algoritmo são os relacionados à criptoanálise, especialmente
no campo da criptoanálise linear e diferencial.
Todos estes testes descritos também podem ser objeto de trabalho
futuro, no qual poderá ser mais bem analisada a força do algoritmo Papílio
Versátil.
O algoritmo, por ser um algoritmo que processa blocos de texto,
fornece a mesma saída caso tenha-se blocos iguais, o que ocorre
freqüentemente em textos estruturados e em imagens.
Para que isso não ocorra, tem-se como solução operar um
deslocamento circular na chave em cada bloco a ser processado, fazendo com
que sejam utilizadas chaves diferentes para diversos blocos, o que implica em
textos cifrados distintos na utilização de blocos iguais.
Desta forma, esta solução pode ser adotada em trabalhos futuros.
38
7. Bibliografia
Araújo, F. S. (2003). PapílioXP - Uma Extensão do Algoritmo
Criptográfico Papílio. Natal: Relatório de Graduação em Engenharia da
Computação/UFRN.
Araújo, F. S., Ramos, K. D., Bedregal, B. R., & Silva, I. S. (2004).
Papílio cryptography algorithm. International symposium on computational and
information science No1. 3314, pp. 928-933. Shanghai-CHINA: Springer, Berlin,
Alemanha.
Feistel, H. (1973). Cryptography and computer privacy. Scientific
American .
Ramos, K. D., Silva, I. S., & Bedregal, B. R. (2002). PAPÍLIO:
Proposta de um Algoritmo de Criptografia Baseado no Algoritmo Viterbi e
Codificação Convolucional. Natal: Dissertação de Mestrado -
UFRN/CCET/DIMAP.
Ramos, K. D., Silva, I. S., & Bedregal, B. R. (2002). PAPÍLIO: Um
algoritmo de criptografia. Revista do CCEI , 6 (10), 24-32.
Shannon, C. (1949). Communication theory of secrecy systems. Bell
Systems Technical Journal, nº 4.
Stallings, W. (2008). Criptografia e segurança de redes. São Paulo:
Pearson Prentice Hall.
Szwarcfiter, J., & Markenzon, L. (1994). Estruturas de Dados e Seus
Algoritmos. Rio de Janeiro: LTC.
Viterbi, A. J. (1967). Error bounds for convolutional codes and na
Asymptotically Optimum. IEEE Transactions on Information Theory.