50
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

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE …bedregal/Tese-alunos/Monografia-Joao-Batista.pdf · desenvolvido como uma extensão do Papílio XP (Araújo, 2003). Consiste em um algoritmo

  • Upload
    lythuan

  • View
    213

  • Download
    0

Embed Size (px)

Citation preview

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

22

Figura 12 – Descriptografia 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.