Loading ...
Global Do...
News & Politics
7
0
Try Now
Log In
Pricing
UNIVERSIDADE DO VALE DO RIO DOS SINOS CIÊNCIAS EXATAS E TECNOLÓGICAS, PROGRAMA INTERDISCIPLINAR DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO APLICADA - PIPCA Criptografia com Caos por DANIEL FORMOLO Dissertação submetida à avaliação como requisito parcial para a obtenção do grau de Mestre em Computação Aplicada Prof Dr. Luiz Paulo Luna de Oliveira Orientador São Leopoldo, abril de 2009. 2 CIP — CATALOGAÇÃO NA PUBLICAÇÃO Formolo, Daniel Criptografia com Caos / por Daniel Formolo. — São Leopoldo: Ciências Exatas e Tecnológicas da UNISINOS, 2009. 114 f.: il. Dissertação (mestrado) — Universidade do Vale do Rio dos Sinos. Ciências Exatas e Tecnológicas, Programa Interdisciplinar de Pós-Graduação em Computação Aplicada - PIPCA, São Leopoldo, BR–RS, 2009. Orientador: de Oliveira, Luiz Paulo Luna. I. de Oliveira, Luiz Paulo Luna. II. Título. UNIVERSIDADE DO VALE DO RIO DOS SINOS Reitor: Dr. Marcelo Fernandes de Aquino Vice-Reitor: Dr. Aloysio Bohnen Pró-Reitor Acadêmico: Dr. Pedro Gilberto Gomes Diretora de Pós-Graduação e Pesquisa: Profa. Dra. Ione Maria Ghislene Bentz Coordenador do PIPCA: Prof. Dr. Arthur Tórgo Gómez 3 O hóspede sabe que nada é seu: um quarto, uma janela, a rua que se perde onde o chão vira céu. Ele entendeu que tudo está de passagem e não adianta arame, areia, cimento, casa de madeira, de palha, de vento. Não lhe peçam assinatura de proprietário no papel. O hóspede tem outra escritura, a dos seus versos. O universo é o seu hotel. (Mario Quintana) 4 TITLE: “CRYPTOGRAPHY WITH CHAOS” Abstract The technological advance and value of information in the preset days lead to a constant search for more efficient, secure and adaptable ciphers. While de security is based on the complicated behavior of the algorithms, its efficiency is based on the simplicity of the mathematical operations involved. The chaotic systems are characterized by the property of showing complex behavior even being defined by simple algebraic mathematical expressions. Therefore, the proposal of ciphers based on chaotic dynamics has became an active research field. This work deals with the efficiency and security of one of the most complete chaotic cipher proposed so far. Based on this study, improvements are proposed for both efficiency and security. The final result is an optimized version, which is denominated chaotic cipher (CC) towards this work. This cipher does not suffer from the weaknesses of the chaotic ciphers proposed so far. Moreover, experimental comparisons shows that the CC performance is comparable with those of some of the most efficient ciphers of commercial usage (AES, RC4 and Sosemanuk). These results suggest that chaotic cryptography has a promising future as a method for commercial usage. Keywords: Cryptography, Chaos, Algorithm. 5 Resumo O avanço tecnológico e o valor que as informações representam no mundo moderno conduzem a uma constante busca por cifradores mais velozes, seguros e adaptáveis à diversos ambientes. Enquanto a segurança se baseia no comportamento complicado dos algoritmos, a eficiência se baseia na simplicidade das operações matemáticas envolvidas. Os sistemas caóticos têm a propriedade de exibir comportamento complicado mesmo sendo definido de modo determinístico por funções algebricamente simples. Portanto, a proposta de algoritmos de cifração baseados em sistemas caóticos é um tema de ativa pesquisa. Este trabalho estuda a eficiência e a segurança de um dos mais completos cifradores caóticos. Com base nesse estudo, melhorias são propostas tanto quanto à sua eficiência quanto à sua segurança. Com isto, chega-se a uma versão otimizada, a qual é referida ao longo deste trabalho como cifrador caótico (CC). O cifrador resultante não possui as fraquezas dos algoritmos caóticos propostos até então. Além disso, comparações experimentais mostram que o CC tem performance comparável com alguns dos mais eficientes algoritmos de cifragem de uso comercial (AES, RC4 e Sosemanuk). Tais resultados mostram que a criptografia caótica tem futuro promissor como método ce cifragem de uso comercial. Palavras-chave: Criptografia, Caos, Algoritmo. 6 Sumário Abstract 4 Resumo 5 Lista de Abreviaturas 8 Lista de Figuras 10 Lista de Tabelas 13 1 Introdução 14 2 Criptologia Moderna 20 2.1 Cifradores Assimétricos . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Cifradores Simétricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Componentes Utilizados em Cifradores Simétricos . . . . . . . . . . . 26 2.4 Criptoanálise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Algoritmo AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.6 Algoritmo Sosemanuk . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.7 Algoritmo RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3 Dinâmica Caótica Aplicada à Criptografia 44 3.1 Conceitos Básicos de Mapas Caóticos . . . . . . . . . . . . . . . . . . 44 3.2 O Cifrador de Baptista . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 O Cifrador de De Oliveira e Sobottka . . . . . . . . . . . . . . . . . . 55 7 4 Algoritmo Proposto 59 4.1 Modelo criptográfico do CC . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Processos de cifração e decifração . . . . . . . . . . . . . . . . . . . . 64 4.3 Formatação do arquivo cifrado . . . . . . . . . . . . . . . . . . . . . . 66 4.4 Gerenciamento da ε-segurança . . . . . . . . . . . . . . . . . . . . . . 67 5 Resultados 70 5.1 Teste de desempenho . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 Analise de segurança . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.3 Características do CC . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6 Conclusão 100 Bibliografia 109 8 Lista de Abreviaturas AES Advanced Encryption Standard BIC Bits Independence Criterion CBC Cipher Block Chaining CCM Counter CBC Mode CCOS Cifrador Caótico De Oliveira e Sobottka CFB Cipher FeedBack DES Data Encryption Standard EAX Encryptation Autentication mode eEstream Projeto que visa identificar um cifrado de fluxo simétrico para ser adotado como padrão de criptografia de fluxo simétrica ECB Eletronic Code Book ECRYPT European Network of Excellence for Cryptology FIFO First in fisrt out IV Initialization Vector KB Kilo Byte GCM Galois Counter Mode HSM Hardware Security Module. IAPM Integrity Aware Parallelizable Mode LFSR Linear Feedback Shift Register 9 LRU Least Recently Used MB Mega Byte MEF Máquina de Estados Finitos MHz Mega Hertz ms Milisegundos NIST National Institut of Standards and Technology OCB Offset Code Book OFB Output Feedback SAC Strict Avalanche Criterion SB Sistema de Baptista UML Unified Modeling Language. 10 Lista de Figuras FIGURA 2.1 – cifração dos modos ECB e CBC. No modo CBC, o vetor IV deve conter valores conhecido entre emissor e receptor [1]. . . . . . . . 24 FIGURA 2.2 – cifração do Modo CFB [1]. . . . . . . . . . . . . . . . . . . 25 FIGURA 2.3 – Modo OFB [1]. . . . . . . . . . . . . . . . . . . . . . . . . 26 FIGURA 2.4 – Estrutura da Rede Feistel. . . . . . . . . . . . . . . . . . . . 27 FIGURA 2.5 – Exemplo genérico de uma Caixa-S (utilizada na cifração) e sua Caixa-S inversa (utilizada na decifração) [2]. . . . . . . . . . . . . 28 FIGURA 2.6 – Fluxo de cifração e decifração do Algoritmo AES [3]. . . . . 35 FIGURA 2.7 – Operação de DeslocamentoLinha usada no algoritmo AES [4]. 36 FIGURA 2.8 – Operação de MixColumns no algoritmo AES, sendo Nk o número de bytes da chave e Nb o número de bytes de cada bloco [4]. . . 37 FIGURA 2.9 – Processo de cifração do Algoritmo Sosemanuk [5]. . . . . . . 39 FIGURA 3.1 – Mapas de tabelamento para condição inicial x0 = 0.1 e valores em (A), µ = 2, 9 (ponto fixo); em (B), µ = 3, 2 (período 2); em (C), µ = 3, 5 (período 4) e em (D), µ = 3, 86 (caos). . . . . . . . . . 47 FIGURA 3.2 – Diagrama de bifurcações do mapa logístico para 2.5 < µ < 4 (eixo horizontal). No eixo vertical estão representados os pontos fixos/periódicos. Note a seqüência de duplicações de períodos até que os (vários) regimes caóticos se estabeleçam. . . . . . . . . . . . . . . . 49 FIGURA 3.3 – Expoentes de Lyapunov e diagrama de bifurcação do mapa logístico plotados juntos para 3.5 ≤ µ ≤ 4. . . . . . . . . . . . . . . . 51 FIGURA 3.4 – Mapeamento dos símbolos do alfabeto dentro do intervalo do Mapa Caótico definido por Baptista [6]. . . . . . . . . . . . . . . . . . 52 11 FIGURA 3.5 – Representação hipotética da cifração e decifração do texto plano P = (d, i, d), utilizando um mapa caótico fµ, com condição inicial x0. O mapa fµ está dividido em sítios relacionados aos símbolos do alfabeto utilizado. Os valores sobre o mapa correspondem as iterações para cifrar C1 → (1, 2, 3), C2 → (1′, 2′, 3′, 4′) e C3 → (1′′, 2′′). 54 FIGURA 3.6 – Gráfico deHp e o respectivo expoente de Lyapunov local para p=2 ((a) e (c)) e p=4 ((b) e (d)). Os valores mostrados de lp são limitados ao intervalo [-3,2] para facilitar a comparação [7]. . . . . . . . . . . . . 58 FIGURA 4.1 – Exemplo de varredura dos dígitos de p √ x0, com p = 3 e x0 = 5, para d = 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 FIGURA 4.2 – Fluxograma geral do cifrador caótico. . . . . . . . . . . . . . 63 FIGURA 5.1 – Comparação de velocidade de cifração e decifração com variação no tamanho dos textos, entre CC (linha sólida), Sosemanuk (linha com tracejado e ponto), RC4 (linha tracejado e cruz), e o AES (linha tracejada). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 FIGURA 5.2 – Média de histogramas h−(n), ho(n) e h+(n) das versões cifradas de conjuntos de textos viesados e não-viesados. O histograma obtido para o conjunto de textos não-viesado (a) é estatísticamente similar ao conjunto viesado onde o símbolo a aparece com dez vezes mais freqüência do que qualquer outro símbolo (b). Os Histogramas (c) e (d) mostram resultados similares para textos planos com o mesmo viés para os grupos de símbolos ab e the, respectivamente. . . . . . . . . . . 77 FIGURA 5.3 – Histograma de iterações para cifração de símbolos partindo de "a"para "b"(linha cheia) e de símbolos partindo de "a"para "c"(linha ponto-traço). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 FIGURA 5.4 – Histograma de iterações para cifração de símbolos partindo de "b"para "a"(linha cheia) e de símbolos partindo de "b"para "c"(linha ponto-traço). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 FIGURA 5.5 – Histograma de iterações para cifração de símbolos partindo de "c"para "a"(linha cheia) e de símbolos partindo de "c"para "b"(linha ponto-traço). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 FIGURA 5.6 – Diagrama de Estados do algoritmo CC. . . . . . . . . . . . . 90 12 FIGURA 5.7 – Diagrama de Seqüencia do algoritmo CC. . . . . . . . . . . . 91 FIGURA 5.8 – Variação do método de procura dentro tabela Γ do cifrador CC, particionando Γ para processamento paralelo de textos planos. . . . 92 FIGURA 5.9 – Variação do método de procura dentro tabela Γ do cifrador CC, sem particionamento de Γ para processamento paralelo de textos planos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 FIGURA 5.10 – Gráfico que mostra a variação no tempo de codificação (milisegundos), em função dos tamanhos dos d-blocos (d) e do expoente de lyapunov (l0), para um texto de 10MB de tamanho. . . . . . . . . . . 95 13 Lista de Tabelas TABELA 2.1 – Número de Rodadas em Função do tamanho dos blocos e das chave no AES [4]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 TABELA 3.1 – Entropia ideal e obtida com o cifrador de Baptista para textos planos cifrados com alfabetos de entrada de diferentes tamanhos [8]. . . 55 TABELA 4.1 – Exemplo de uso da tabela Γ. . . . . . . . . . . . . . . . . . 61 TABELA 5.1 – Exemplo de tabela de ataque de entropia. . . . . . . . . . . . 75 TABELA 5.2 – Tabela de ataque de entropia para o cifrador CC. . . . . . . . 75 TABELA 5.3 – Mapa caótico do CC para chave √ 2 e d-bloco=3, onde ∆(x) é o valor do x-ésimo d-bloco. . . . . . . . . . . . . . . . . . . . . . . . 80 TABELA 5.4 – Tabela de Jakimoski - Kocarev comparando os símbolos planos e o total de iterações desde o início da cifração até atingir os sítios relacionados a estes símbolos [9]. . . . . . . . . . . . . . . . . . 81 TABELA 5.5 – Amostra do resultado do teste de Ataque Diferencial ao CC. Sendo P n=textos planos e Cn=textos cifrados. . . . . . . . . . . . . . . 83 TABELA 5.6 – Lista de sub-processos internos do CC. . . . . . . . . . . . . 88 TABELA 5.7 – Resumo comparativo de desempenho do CC em relação aos outros algoritmos estudados. . . . . . . . . . . . . . . . . . . . . . . . 97 TABELA 5.8 – Resumo comparativo da segurança do CC em relação aos outros algoritmos estudados. . . . . . . . . . . . . . . . . . . . . . . . 98 TABELA 5.9 – Resumo comparativo das características do CC em relação aos outros algoritmos estudados. . . . . . . . . . . . . . . . . . . . . . 99 14 Capítulo 1 Introdução Criptologia é a ciência que estuda técnicas para restringir e obter acesso a informações sigilosas. Modernamente, ela é dividida em criptografia e criptoanálise. A primeira, estuda os métodos de cifração de dados. A segunda, estuda as maneiras de quebrar o sigilo criado pela criptografia, através de seus cifradores e protocolos de transporte de dados [10]. A criptografia é tão antiga, que estava presente até mesmo em hieroglífos egípcios [11]. Os romanos utilizavam códigos secretos para comunicar planos militares com a chamada Cifra de Cesar [11]. Com o passar do tempo e o advento dos circuitos micro-processados, os métodos de criptografia se modificaram. Hoje eles estão fortemente fundamentados em algoritmos matemáticos. Da mesma forma, a criptoanálise também acompanhou esta evolução [3]. Atualmente, com o aumento do poder de processamento de informações, é muito fácil quebrar textos cifrados com a maioria dos algoritmos clássicos de criptografia. Nos sistemas modernos, a construção de algoritmos criptográficos é dada por uma composição de funções matemáticas, denominadas primitivas. Para serem utilizadas na cifração/decifração de dados, tais primitivas devem possuir características convenientes como velocidade (eficiência), facilidade na troca de chaves, e altos índices de difusão e confusão [12, 13]. Existem critérios definidos para se avaliar e classificar as primitivas. Conforme estes critérios, pode-se dividir os algoritmos criptográficos em cifradores simétricos e assimétricos [10, 12]. Os algoritmos assimétricos usam chaves diferentes para cifrar 15 e decifrar dados. Por outro lado, os algoritmos simétricos usam a mesma chave para cifração e decifração. Os cifradores simétricos são divididos ainda em cifradores de fluxo e cifradores de bloco. Os cifradores de fluxo cifram as unidades de texto plano individualmente, a cada iteração, enquanto os cifradores de bloco cifram um bloco de unidades de texto plano a cada iteração [1]. Embora cifradores simétricos sejam mais rápidos que assimétricos, o uso da mesma chave dificulta a logística de troca de chaves [14]. Por conseqüência disso, a maioria dos sistemas criptográficos utilizam um modelo híbrido, isto é, a troca de chaves dos cifradores simétricos é realizada com um algoritmo assimétrico, e a troca de dados é feita com um algoritmo simétrico. O uso de cifradores simétricos para troca de dados se justifica pela sua velocidade e uso de poucos recursos de hardware. Essas características vão ao encontro das necessidades atuais da criptografia [15, 16]. Neste trabalho são estudados os cifradores simétricos e assimétricos, focando principalmente os cifradores simétricos de fluxo. A criptografia esta presente nas mais diversas áreas, sua importância é muito maior do que em outros tempos. A criptografia é usada na cifração de mensagens, cifração de documentos, acesso a sistemas, envio de sinais de longa distância como nas transmissões de TV-Digital, de modo geral nas transações financeiras, como em bolsas de valores, operações entre bancos, cartões de crédito, caixas eletrônicos, entre outros [10]. A crescente utilização de equipamentos portáteis e novas tecnologias de informação estimulam a comunicação entre pessoas, entre empresas, e entre pessoas e empresas. Aliado a isso, é cada vez mais comum o uso de meios não seguros para troca de informação como wireless, bluetooth e comunicação via rádio. A conjunção desses fatores aumenta a demanda na transmissão de dados por mais segurança e eficiência, isto é, cifração mais veloz e com menor uso de memória. Visando agrupar segurança com pouco uso de recursos computacionais, há vinte anos, pesquisadores vêm estudando as características dos sistemas caóticos e sua aplicabilidade na criptografia. Existem dois modos principais de utilização de sistemas caóticos: o Modo de Sincronização e o Modo de Busca. O primeiro foi inicialmente proposto por Pecora e Carroll. Este modo se baseia em sistemas caóticos com sincronização analógica [17]. Além deste trabalho, outros autores propuseram sistemas criptográficos baseados em sistemas caóticos síncronos, como em [18, 19]. Outro exemplo deste tipo de sistema foi o apresentado por Álvarez et al. em [20]. Nesse trabalho, Álvarez apresenta um cifrador baseado em um oscilador caótico não 16 linear, neste caso, um atrator de Lorentz-3D, o qual gera sinais pseudo-aleatórios que são combinados com o texto plano para gerar uma seqüencia de caracteres cifrados. O receptor regenera o sinal pseudo-aleatório de forma invertida. Combinando este sinal com o texto cifrado ele consegue recuperar o texto plano. Essa forma de cifrar dados tem alguns problemas, principalmente referentes a ruídos de comunicação e segurança, conforme apresentado em [21, 22, 9, 23]. O método de criptografia caótica classificado como Modo de Busca surgiu recentemente. Ele utiliza mapas caóticos sem a necessidade de sincronização de sistemas entre emissor e receptor. O Modo de Busca parte do princípio que, sendo P = (Pj)1≤j≤L o texto plano com tamanho L escrito em um alfabeto finito A e, sendo fp : I → I , a família de mapas caóticos escolhida, com intervalo I e parâmetro p. O intervalo I é dividido em N subintervalos semi-abertos Ik, k = 1, 2, . . . , N denominados sítios. Cada sítio é associado de forma uniforme à um símbolo de A. O processo de cifração consiste em iterar fp consecutivamente, partindo da condição inicial (chave) x0 ∈ I , computando o número de iterações necessárias para a correspondente órbita cair dentro de cada sítio Ik associado com a sucessão de símbolos que compõem P . A versão cifrada de P é a seqüencia C = (Cj)1≤j≤L dos valores Cj , correspondentes a quantidade de iterações de fp, necessárias para a órbita (xj) = (f j p (x0)) atingir os sítios associados a cada um dos símbolos consecutivos de P . Mais precisamente, C é a seqüencia de números naturais C = (Cj)1≤j≤L tal que f Cj p (xCj−1) é a primeira ocorrência, em um intervalo Ik, associado à Pj . A decifração de C é feita usando a mesma chave, de maneira óbvia: lendo cada Cj como um símbolo Pj associado com o subintervalo Ik para que f ∑j i=1 Ci p (x0). A viabilidade desses sistemas se baseia na capacidade que os sistemas caóticos têm de exibir comportamentos complexos, mesmo com formulação matemática simples. Isto indica uma boa aplicação em sistemas criptográficos devido às características de confusão e difusão que o caos provê e pela simplicidade (baixo uso de processamento e memória) com que este método utiliza as propriedades do caos. O mais estudado destes algoritmos foi proposto por Baptista [6]. Em seu trabalho, ele propôs um sistema de cifração baseado em um mapa caótico unidimensional, a saber, o mapa logístico, dado por fµ(x) = µx(1− x). Seu sistema tem um subdomínio apropriado de fµ, com 3 ≤ µ ≤ 4, e utiliza as iterações do mapa logístico para cifrar os dados. Tal sistema será detalhado na Seção 3.2. 17 Sobre a proposta de Baptista, surgiram críticas quanto à segurança do método contra ataques com texto plano conhecido. Um dos ataque desses tipo foi proposto por Jakimoski e Kocarev em [24]. Entretanto, este método de ataque foi criticado por Li et al. que não o consideram viável [9]. Outros autores também apontaram críticas ao modelo de Baptista. Em seu trabalho, Álvarez et al. apontam deficiências de segurança, sugerindo outras três formas de ataque [8]. Uma delas é parecida com o método de ataque proposto por Jakimoski e Kocarev; a segunda utiliza análise de entropia e estatística; e a terceira, possibilita a dedução do valor do parâmetro µ da função logística, caso este faça parte da chave. Por outro lado, Wong [25] propõem um método para resolver o problema de entropia, utilizando o mesmo mapa de Baptista, porém cifrando os dados em blocos de texto plano, ao invés de símbolo a símbolo, conforme definido originalmente. Além das críticas quanto à segurança, o método de Baptista apresenta algumas deficiências de outros tipos. Uma delas é a não uniformidade da freqüência com que os sítios associados aos símbolos do alfabeto utilizado são visitados pela órbita escolhida. Isso pode prejudicar muito a taxa de cifração/decifração, caso existam, na mensagem, símbolos associados à sítios de escassa visitação. Outro problema é quanto à escolha do valor do parâmetro µ. De fato, dentro da restrição 3 < µ ≤ 4, há muitos valores para os quais fµ não é caótico. Estes valores de µ não podem ser utilizados no mapa fµ para cifração de dados. Além disso, o sistema de Baptista é dependente do hardware, isto é, temos que utilizar máquinas com a mesma precisão e mesma metodologia determinística de arredondamento numérico para cifrar os dados, caso contrário, a decifração dos dados fica comprometida. Isto restringe e muito seu uso generalizado. Recentemente, foi proposto um método de cifração que utiliza as mesmas idéias básicas de Baptista, mas sem os problemas acima citados [26] [7]. No lugar da aplicação logística, foram usados mapas do tipo Hp(x) = r−1 p ◦ G ◦ rp(x) definidos no intervalo [0, 10p) para um parâmetro racional positivo p, onde G(x) = 10x(mod 10) e rp(x) = p √ x. É possível mostrar que este tipo de mapa unidimensional é caótico para todo valor do parâmetro p, ao contrário do que acontece no sistema de Baptista. A divisão do seu domínio é feita de tal forma que os sítios são visitados pelas órbitas deHp, com a mesma probabilidade. Além disso, é independente de máquina. Os resultados do presente trabalho mostram que com algumas importantes 18 modificações, esta forma de cifrar dados é eficiente e segura, podendo se candidatar ao uso comercial. Este trabalho apresenta, em detalhes, ambos os métodos: Sistema de Baptista e o sistema proposto de De Oliveira e Sobottka [26, 7]. O trabalho propõe ainda, melhorias na forma de cifrar os dados no sistema de De Oliveira e Sobottka, as quais, em momento algum ferem as prerrogativas definidas em [26, 7]. As três principais modificações abrangem o aumento da velocidade de cifração/decifração com a disposição das órbitas caóticas geradas em uma Tabela de Endereçamentos; aumento na segurança tornando o cifrador estatístico; diminuição no tamanho do texto cifrado através de um novo método de armazenar os símbolos cifrados. O cifrador com suas melhorias é aqui referido como Cifrador Caótico (CC). Além disso, o trabalho apresenta um software que implementa o cifrador CC, além de outros três algoritmos da criptografia moderna: o cifrador de bloco AES (Advanced Encryption Standard) [27], que é o cifrador simétrico mais usado comercialmente; o Cifrador RC4, que há muito tempo é um dos cifradores de fluxo mais utilizados comercialmente; e o cifrador de fluxo Sosemanuk [28], cogitado como um dos possíveis vencedores do projeto eEstream, organizado por um convênio de empresas, instituições e universidades européias chamado de ECRYPT. O eEstream visa identificar cifradores de fluxo promissores, e que possam ser aplicados comercialmente [28]. A eficiência do CC é então comparada com as dos outros métodos. Além disso, o trabalho apresenta um estudo detalhado sobre a segurança do CC, em relação aos ataques mais consagrados. Com isso, este trabalho se constitui num estudo inédito para a viabilidade do uso, em escala comercial, do CC e de cifradores similares a ele. Mais especificamente, este trabalho tem por objetivo: • Propor um cifrador simétrico (CC) baseado em mapas caóticos de uso comercial viável. • Avaliar sua eficiência em termos de velocidade, segurança e características de uso. Essa dissertação está dividida em seis capítulos e, ao final dela, um glossário esclarece os termos da área de criptografia que foram utilizados no trabalho. No Capítulo 2, é apresentada uma breve revisão dos conceitos básicos da criptografia moderna, incluindo os cifradores AES, RC4 e Sosemanuk. No Capítulo 3 é apresenta a dinâmica caótica dos mapas unidimensionais a qual, introduz a descrição do sistema de Baptista e do sistema 19 proposto por De Oliveira e Sobottka. O Capítulo 4 refere-se ao CC. No Capítulo 5 são apresentados os resultados da avaliação do CC. As conclusões sobre esta análise são apresentadas no Capítulo 6. 20 Capítulo 2 Criptologia Moderna Conforme citado no capítulo anterior, a criptografia estuda os métodos de cifração de dados e a criptoanálise estuda as maneiras de quebrar o sigilo criado pela criptografia. A união dessas duas áreas forma a criptologia. A criptografia utiliza cifradores para proteger as informações contidas nos dados. Estes cifradores são classificados segundo suas primitivas e as funcionalidades providas por estas. As primitivas são todo tipo de função de criptografia de baixo nível que compõem um cifrador. Elas podem ser utilizadas de forma isolada, como um cifrador simples, ou combinadas, formando um cifrador, em geral, mais robusto em termos de segurança. As primitivas têm características diferentes entre si. O uso delas e a maneira com que são combinadas, também geram cifradores com diferentes características. Segundo Menezes et. al. [12], os principais critérios para a avaliação das primitivas quanto ao uso pretendido são: segurança, funcionalidade e desempenho. Conforme esses critérios, os cifradores são classificados como simétricos ou assimétricos. Os cifradores assimétricos utilizam chaves diferentes para cifrar e decifrar dados. Já os cifradores simétricos utilizam a mesma chave para cifrar e decifrar dados. As discussões neste trabalho serão focadas nos cifradores simétricos sem, no entanto, deixar de falar brevemente sobre os cifradores assimétricos, que são um ramo importantíssimo da criptografia e que complementam a criptografia simétrica nos sistemas de segurança usados hoje em dia. 21 2.1 Cifradores Assimétricos Cifradores assimétricos ou de chave pública, têm como principal característica o uso de duas chaves distintas: uma para cifrar e outra para decifrar o texto. A chave de cifração costuma ser de domínio público, enquanto que a chave de decifração deve ser mantida sob sigilo absoluto. Para isso, são utilizadas funções matemáticas do tipo C = Fc(P,Kc) (cifração) e D = Fd(C,Kd) (decifração), (2.1) onde • P é o texto plano (original) • C é o texto cifrado; • D é o texto plano decifrado, tal que D = P ; • Fc é o algoritmo de cifração; • Fd é o algoritmo de decifração; • Kc é a chave de cifração; • Kd é a chave de decifração. Usualmente, tem-se Fd = Fc = F , isto é, a ação destas funções sobre os textos P e C só dependem das chaves Kc e Kd, respectivamente [1]. Em tais funções, o valor de saída é muito fácil de se encontrar a partir do valor de entrada. Porém, é exigido que o contrario seja extremamente difícil e computacionalmente inviável, sem se conhecer um determinado número (chave) que torne o cálculo do valor de entrada simples. Em outras palavras, enquanto a cifração é de fácil implementação, a decifração é efetivamente inviável sem o conhecimento da chave privada. Nos cifradores assimétricos, o protocolo de cifração segue os seguintes passos: • Cada usuário do sistema gera um par de chaves, uma de cifração e outra de decifração. 22 • Os usuários publicam suas chaves de cifração em um repositório público. • Se o usuário B deseja enviar uma mensagem para o usuário A, ele cifra a mensagem com a chave pública de A. • Por sua vez, ao receber a mensagem codificada, A decifra a mensagem com a sua chave privada, que somente ele conhece. Esta assimetria de chaves traz profundas conseqüências nas áreas de confidencialidade, distribuição de chaves e autenticação. No protocolo acima, não é necessário um canal seguro para troca de chaves. Isso mostra claramente a facilidade na distribuição de chaves e a garantia de confidencialidade das informações. No caso da autenticação o protocolo deve ser modificado, incorporando um segundo par de chaves: • Cada usuário do sistema gera dois pares de chaves, duas de cifração e outras duas de decifração. • Os usuários publicam um chave de cifração, que será usada para codificar a mensagem e uma chave de decifração, que será usada como assinatura da mensagem, garantindo a procedência da mensagem. Ambas são disponibilizadas em um repositório público. • Se B deseja enviar uma mensagem para o usuário A, ele assina a mensagem cifrando-a com sua chave de cifração, depois cifra a mensagem assinada com a chave pública de A. • Por sua vez, ao receber a mensagem codificada, A decifra a mensagem com a sua chave privada e depois autentica a origem da mensagem com a chave de decifração publicada por B. Alguns cifradores, como o RSA, permitem que qualquer uma das chaves seja escolhida como a chave de cifração, enquanto a outra automaticamente torna-se a chave de decifração [1]. 23 2.2 Cifradores Simétricos Os cifradores simétricos são divididos em dois conjuntos: cifradores de bloco e cifradores de fluxo. Os cifradores de bloco operam geralmente cifrando blocos de 64 bits de informação. Um mesmo bloco de texto plano gera o mesmo bloco de texto cifrado [1, 10]. Isto significa que, usando a mesma chave para cifrar blocos de texto plano iguais, o resultado serão blocos de texto cifrados idênticos, independente da quantidade e conteúdo dos blocos cifrados entre estes. Os cifradores de fluxo operam cifrando bit a bit (ou byte a byte) as informações e usam a mesma chave para cifração e decifração . Assim, um bit de entrada, gera um bit cifrado diferente na saída do sistema [1]. Existem vários modos de cifradores de bloco e de fluxo operar. Estes modos tem por objetivo realizar um pré-tratamento dos dados de entrada do algoritmo e adicionar características como dependência entre blocos cifrados ou proteção contra ruídos na transmissão de dados do canal ou ainda transformar um cifrador de bloco em um cifrador de fluxo. Mas a função principal dos modos de operação é criar uma dependência entre a seqüência de blocos de texto cifrado, isto torna os cifradores mais seguros. Existem quatro modos básicos de operação, dos quais foram derivados muitos outros ao longo do tempo, como os modos IAPM, CCM, EAX, GCM e OCB. A seguir, os quatro modos básicos são brevemente descritos, a fim de se mostrar a influência que cada Modo de Operação tem no resultado final da cifração, quando combinado com as primitivas de criptografia. • Eletronic CodeBook (ECB): Esse é o modo mais simples. Cada parte do texto plano entra diretamente no algoritmo de cifração. Igualmente, a mesma chave, sem qualquer alteração, é utilizada na cifração de cada parte do texto plano. Isso significa que que para o texto plano P = (P1, P2, Pi..., Pi+n) se Pi = Pi+n, as partes de texto cifrado Ci e Ci+n sempre serão iguais. Este modo é ideal para cifrar quantidades pequenas de dados. A Figura 2.1 mostra seu uso na cifração. A decifração se dá de forma similar. • Cipher Block Chaining (CBC): O CBC trabalha de forma similar ao ECB, usando a mesma chave para cifrar os blocos de dados. Para evitar o problema de gerar blocos cifrados idênticos para os mesmos blocos de textos planos, o CBC realiza 24 uma operação de XOR entre cada bloco de texto plano e o bloco anteriormente cifrado. Na primeira cifração, com não existe um bloco cifrado para ser combinado com P1, se aplica a operação de XOR com um vetor de inicialização (IV). Este IV contém uma seqüência de dados com o mesmo tamanho do bloco de texto plano P1 e é conhecido apenas pelo emissor e pelo receptor. A Figura 2.1 mostra o processo de cifração. Se algum bit de um Bloco B for alterado o CBC consegue se recuperar após B+2 blocos. Porém ele não consegue se recuperar quando mais de um bit for alterado, perdido ou incluído. Este tipo de situação ocorre geralmente quando existe ruído no canal. Encriptação P1 K C1 Encriptação C2 ... P2 K Modo ECB Encriptação C1 Encriptação C2 ... P1 IV P2 K K Modo CBC FIGURA 2.1 – cifração dos modos ECB e CBC. No modo CBC, o vetor IV deve conter valores conhecido entre emissor e receptor [1]. • Cipher FeedBack (CFB): Nesse modo a operação o vetor de inicialização IV, é conhecido apenas pelo emissor e pelo receptor, e é cifrado com a chave K. Depois uma função simples seleciona apenas a quantidade de bits que define um bloco ou unidade de texto plano. Chamamos todo este conjunto de operações de função de cifração. Sendo s a quantidade de bits de cada bloco do texto plano P = (P1, P2, ..., Pn), uma operação de XOR é realizada entre o bloco P1 e o resultado da função de cifração. A cifração dos próximos blocos segue a mesma operação de XOR entre os blocos do texto plano P2, P3, ..., Pm e o vetor de bits, porém a cada operação o vetor de bits agrega s bits a sua direita e descarta os s bits mais a esquerda (bits mais significativos). 25 A decifração ocorre pela mesma forma, exceto que a operação de XOR se dá com cada bloco de texto cifrado para se obter os blocos de texto plano. Este Modo de Operação transforma cifradores de bloco em cifradores de fluxo. Além disso, ele provê auto-sincronismo do sistema de cifração. A Figura 2.2 demonstra o processo de cifração do modo CFB. s s s+n s+n s s s Encriptação IV - shift register |n|+|s|bits P2 K C2 Seleciona s bits|descarta n bits .... .... s+n s+n Encriptação IV - shift register |n|+|s|bits P1 K C1 Seleciona s bits|descarta n bits s FIGURA 2.2 – cifração do Modo CFB [1]. • Output Feedback (OFB): Este modo é similar ao CFB, a única mudança esta na operação de XOR de cada bloco, que é alimentada pela função de cifração. Isto traz como benefícios a garantia de que se ocorrer um erro em um bit do bloco n os blocos seguintes não serão afetados, isto é, este modo é resistente a ruídos no canal de transmissão. A desvantagem deste modo são os ataques que modificam o texto cifrado. A Figura 2.3 demonstra o processo de cifração do modo OFB. Em geral, não se adotam cuidados extremos com a segurança no Modo de Operação, pois ela esta fundada na função do algoritmo de cifração. Quanto mais forte a segurança gerada pelo algoritmo de cifração, menor o compromisso com segurança do Modo de Operação do algoritmo. De qualquer forma, alguns cuidados são necessários, como: padrões nos textos planos não devem aparecer nos textos cifrados; a entrada de dados no algoritmo deve ser aleatória; a manipulação do texto plano pela introdução de erros no texto cifrado deve ser evitada; e por fim, deve ser possível cifrar com segurança mais de um texto plano com a mesma chave [10]. 26 s s s+n s+n s s s Encriptação IV - shift register |n|+|s|bits P2 K C2 Seleciona s bits|descarta n bits .... .... s+n s+n Encriptação IV - shift register |n|+|s|bits P1 K C1 Seleciona s bits|descarta n bits s FIGURA 2.3 – Modo OFB [1]. Além da segurança, a eficiência do Modo de Operação não deve ser significantemente inferior à cifração dos dados e em certas circunstâncias o texto cifrado deve ter o mesmo tamanho do texto plano. A terceira consideração é a tolerância a falhas. Algumas aplicações necessitam serializar a cifração e decifração dos dados enquanto outras necessitam cifrar a maior quantidade de dados possíveis ao mesmo tempo. Outras ainda necessitam recuperar bits do texto cifrado que, devido a ruídos no canal, tenham sido alterados. Cada Modo de Operação tem um diferente conjunto de características e aplicabilidades que atendem mais, ou menos cada um destes critérios[12]. 2.3 Componentes Utilizados em Cifradores Simétricos A estruturação de algoritmos de cifração modernos foi introduzida por Claude Shannon, sob a ótica de que um criptoanalista, conhecendo algumas características estatísticas do sistema, poderia quebrar a chave ou mesmo o texto cifrado. A partir desta idéia, surgiram os conceitos de difusão e confusão aplicados aos algoritmos criptográficos [13]. O princípio de confusão procura eliminar a relação estatística entre o texto cifrado e a chave [13]. Por outro lado, o princípio de difusão consiste em dissipar 27 as características estatísticas do texto plano, através de operações de permutação. Assim, padrões existentes nos textos planos não aparecem nos textos cifrados. Um dos primeiros componentes de difusão criado foi a Rede Feistel. Ela se propõe a gerar um cifrador seguro através da composição de dois ou mais cifradores simples de substituição. Inicialmente a rede divide o bloco de dados a ser cifrado em duas partes, L0 e R0. Em cada rodada n, o algoritmo recebe os valores resultantes da rodada anterior Ln−1 e Rn−1. Conforme mostra a Figura 2.4, todas as rodadas têm a mesma estrutura e são parametrizadas com sub-chaves Kn advindas da chave original. Na rodada n, aplica-se uma função F sobre Rn−1, na forma F (Rn−1, Kn). Ao final da rodada faz-se uma operação de XOR entre Ln−1 e F (Rn−1, Kn). O resultado desta operação gera Rn. O valor de Ln é o próprio Rn−1 [1]. F Rodada 2 L2 K2 R2 F L1 Rodada 1 R1 K1 w bits L0 w bits R0 Texto Cifrado (2w bits) F Rodada n Ln Kn Rn Texto Plano (2w bits) ... FIGURA 2.4 – Estrutura da Rede Feistel. Um outro mecanismo muito utilizado para promover difusão em cifradores de bloco como o AES, são as caixas de substituição, aqui referidas como Caixa-S. Essas caixas são formadas por uma matriz composta de símbolos, que podem ser criados dinamicamente através de um algoritmo ou previamente definido. Com uma de suas principais funções é introduzir não linearidade no algoritmo, os valores contidos nelas são cuidadosamente escolhidos para gerar o máximo de não linearidade possível. Isso é importante para evitar ataques como criptoanálises linear e diferenciais, discutidos mais adiante. No caso da cifração, quando um dado é operado em uma Caixa-S, o resultado desta operação gera um símbolo correspondente ao dado de entrada. Para inverter a operação aplica-se uma segunda matriz que realiza a operação inversa, retornando o dado cifrado anteriormente. A difusão ocorre quando varias Caixas-S são aplicadas repetidas vezes sobre o mesmo texto plano. Com isso, mesmo sendo uma operação determinística, a 28 mudança de um bit no texto plano pode gerar um texto cifrado totalmente diferente. A combinação de várias operações com Caixas-S eleva a incerteza, de forma que, a obtenção do texto plano se torna impraticável. Somente dispondo de vários textos planos e cifrados, e com ataques estatísticos muito refinados é, possível tentar desvendar a chave ou um texto plano que foi cifrado. São recomendadas algumas diretrizes para criar uma Caixa-S. Ela deve ser bijetiva e não linear. É altamente recomendado que ela respeite o Strict Avalanche Criterion (SAC). Segundo este critério, a mudança de um bit do texto de entrada deve mudar, pelo menos, cinqüenta por cento dos bits de saída da Caixa-S [29]. Outro critério importante é o output Bits Independence Criterion (BIC). Segundo o qual, quando aplicado o SAC, os de bits do texto cifrado devem variar independentemente uns dos outros [30]. Por fim, outro critério desejável é a eqüiprobabilidade de entrada e saídas. Segundo este critério, qualquer entrada deve gerar como saída qualquer símbolo do alfabeto com a mesma probabilidade. O ataque diferencial explora justamente falhas neste critério. Existem outros critérios que podem ser avaliados, porém estes são os principais. Geralmente uma Caixa-S gera na saída a mesma quantidade de bits que recebeu na entrada porém, isso não é necessariamente uma regra [31]. Um exemplo de aplicação de Caixas-S é mostrado na Figura 2.5. Neste exemplo, o dado hexadecimal 19 gera o código cifrado D4. Na mesma figura esta a Caixa-S inversa onde, a partir do código cifrado D4, se recupera o dado hexadecimal 19. FIGURA 2.5 – Exemplo genérico de uma Caixa-S (utilizada na cifração) e sua Caixa-S inversa (utilizada na decifração) [2]. 29 As Caixas-S são geralmente utilizadas em cifradores de bloco, por outro lado, os cifradores de fluxo utilizam com freqüência um componente chamado Linear Feedback Shift Register (LFSR). Este componente é um vetor de dados onde cada unidade do vetor pode ser um bit, byte ou word. O LFSR combina rotação de cada unidade que o compõe com algumas operações como XOR ou ADD (adição). Por ser um componente linear, ele é utilizado junto com funções não lineares para aumentar a segurança do cifrador. Geralmente utiliza-se alguns LFSR e a chave como entrada de uma função não linear. A saída desta função é combinada com o texto plano através de uma operação de XOR. O resultado desta última operação é o texto cifrado. Na primeira operação dos LFSR, se utilizam vetores de inicialização (IVs). Estes vetores são préviamente fixados com valores conhecidos apenas pelos emissor e receptor. Existem duas formas de alimentar os LFSR nas operações subseqüentes . Uma delas é através da combinação de uma função aleatória (clock irregular). A outra alternativa combina os LFSR da entrada da função não linear de forma que, além de gerar bits para função não-linear, estes mesmos bits re-alimentam os próprios LFSR, como num ciclo (auto-sincronizados). Apesar de lineares, quando combinados com funções não lineares geram bons cifradores, além de serem simples e com baixo custo computacional [32]. O Sosemanuk utiliza este componente em sua arquitetura. A inicialização dos componentes que formam um algoritmo geralmente é aleatória. Mesmo assim, existem muitas instruções que também poderiam ser aleatórias, mas por questões de otimização e segurança, têm valores pré-determinados. Um exemplo são as Caixas-S, as quais têm seus valores cuidadosamente escolhidos. Mesmo que existam cifradores que gerem Caixas-S dinamicamente, a maioria deles possuem Caixas-S fixas. Além das Caixas-S, existem outros exemplos de componentes com valores pré-determinados e dispostos de maneira a maximizar difusão e confusão na cifração. Estes componentes são específicos de cada cifrador. De forma geral, são componentes como multiplicação do bloco de dados por um valor fixo, rotação de bytes dentro de um bloco de dados com um número fixo de bytes para esquerda ou para direita, ou ainda multiplicação de matrizes agregando pesos diferentes para cada linha das matrizes multiplicadas, entre outros. Todos cuidadosamente pensados para gerar o máximo de confusão e difusão. 30 2.4 Criptoanálise Criptoanálise é a ciência de recuperar textos planos sem acesso direto à chave. O sucesso do criptoanalista se dá quando ele recupera os dados originais ou a chave. Uma suposição fundamental em criptoanálise foi definida por Kerckhoffs [11], segundo ele, o segredo da cifração dos dados deve residir exclusivamente na chave. Existem sete tipos gerais de ataques. Todos assumem que o criptoanalista tem total conhecimento do algoritmo de cifração [10]. No que se segue, E representa o algoritmo de cifração, D o algoritmo de decifração, P j são os textos planos e Cj = E(P j, K), suas versões cifradas com a chave K. 1. Ataque por Texto Cifrado: O criptoanalista tem vários textos cifrados com o mesmo algoritmo E. Ele tenta deduzir os textos planos ou a chave K, comparando varias mensagens cifradas com a mesma chave. Dados: C1 = E(P 1, K), C2 = E(P 2, K), ..., Cj = E(P j, K). Deduz-se: P 1, P 2, . . . , P j , K, ou um algoritmo para inferir P j+1 de Cj+1 = E(P j+1, K). 2. Ataque por Texto Plano: O criptoanalista tem acesso a várias mensagens e seus respectivos textos cifrados. Ele tem como meta deduzir as chaves ou um algoritmo que quebre a codificação de outras mensagens cifradas com as chaves usadas nos textos cifrados de sua posse. Dados: P 1 e C1 = E(P 1, K), P 2 e C2 = E(P 2, K), ..., P j e Cj = E(P j, K). Deduz-se: K, um algoritmo para inferir P n+1 de Cj+1 = E(P j+1, K), ou ambos. 3. Ataque por Texto Plano Escolhido: O criptoanalista tem acesso a um conjunto de textos cifrados e seus respectivos textos planos, mas também escolhe quais textos planos deseja cifrar. Dados: P 1 e C1 = E(P 1, K), P 2 e C2 = E(P 2, K), ..., P j e Cj = E(P j, K). Onde P 1, P 2, ..., P j são escolhidos. Deduz-se: K, um algoritmo para inferir P n+1 de Cj+1 = E(P j+1, K), ou ambos. 4. Ataque por Texto Plano Escolhido e Adaptado: é um caso especial de Ataque por Texto Plano Escolhido, pois o criptoanalista pode subdividir a escolha dos pares 31 de textos cifrados e planos, desta forma a escolha de um subconjunto destes textos é baseada no resultado da cifração obtida de um subconjunto anterior. 5. Ataque por Texto Cifrado Escolhido: O criptoanalista pode escolher diferentes textos cifrados e ter acesso a seus respectivos textos planos. Seu trabalho é deduzir a chave. Esse tipo de ataque é comumente aplicado em cifradores de chave pública e algumas vezes efetivo contra cifradores simétricos. Dados: C1 e P 1 = D(C1, K), C2 e P 2 = D(C2, K), ..., Cj e P j = D(Cj, K). Deduz-se: K. 6. Ataque por Chave Escolhida: Esse ataque não significa que o criptoanalista pode escolher a chave desejada para cifrar um texto plano. Nele o criptoanalista tem algum conhecimento da relação existente entre as chaves geradas para cifrar os textos. Através desse conhecimento ele gera um conjunto de textos cifrados e tenta de alguma maneira encontrar as chaves utilizadas na cifração. É um ataque obscuro que depende da quantidade e qualidade das informações que o criptoanalista tem sobre as chaves. Não é um ataque prático. 7. Ataque por Intimidação: Conhecido como engenharia social, usa de métodos como suborno, ameaças ou tortura para se conseguir a chave. Ataque por Texto Plano Conhecido e por Texto Plano Escolhido são comumente utilizados pela facilidade de acesso a cifração de textos, possibilitando a introdução dos textos planos desejado. David Kahn relata exemplos históricos em seu livro a respeito destes ataques [11]. O que facilita a quebra do algoritmo através destes dois métodos de ataques é o fato de, na troca de mensagens, existirem padrões que se repetem como cabeçalhos e finalizadores de mensagens, estruturas internas de códigos fonte, programas executáveis, trechos de texto, imagens, etc. Baseados nesses tipos gerais de ataques, foram criadas técnicas de criptoanálise que exploram fragilidades de determinados grupos de cifradores. A seguir são apresentadas algumas das técnicas modernas mais aplicadas na quebra dos cifradores avaliados neste trabalho. De uma forma ou de outra, todas elas se utilizam de estatística para realizar a criptoanálise dos cifradores. 32 • Ataque Diferencial: Esta técnica compreende um conjunto de diferentes ataques. Todos utilizam o princípio de comparar textos cifrados. Seus respectivos textos planos têm pequenas diferenças e são cifrados com a mesma chave. Esta técnica foi inicialmente aplicada a cifradores de bloco e posteriormente expandida a cifradores de fluxo e funções hash. Ela se caracteriza por ser um ataque de texto plano escolhido. Sendo P = (P 1, P 2, ...P n) os textos planos e C = (C1, C2, ...Cn) os respectivos textos cifrados, se juntam em pares P e C através de uma operação ⊕ (XOR) na forma P ′m = Pm ⊕ Pm+1 e C ′m = Cm ⊕ Cm+1. O conjunto de textos planos têm poucas diferenças previamente escolhidas. Após a escolha dos textos planos e a obtenção dos respectivos textos cifrados, analisa-se estatísticamente possíveis desbalanços de cifração no conjunto C ′m, ou seja, como o conjunto P tem poucas diferenças, um bom cifrador deve gerar um conjunto C bem diversificado (balanceado). Com esta técnica, o criptoanalista explora estatísticamente algum padrão de P ′ e C ′ que apareçam com mais freqüência [33]. • Ataque por escorregamento (slide attack): Ele é utilizado sobre cifradores que podem ser dividido em partes iguais. Desta forma, o ataque trata essas partes como uma função Fi que produz saídas mediante determinadas entradas. Esta característica indica que o algoritmo utiliza ciclicamente a chave, dando indícios de vulnerabilidade à ataques por texto plano escolhido. Além disso, este ataque é independente do número de rodadas de cifração aplicadas ao texto plano e pode ser utilizado em cifradores de bloco ou de fluxo. Assumindo que o cifrador divide a chave em Kn partes e a mesma função Fi é aplicada sobre cada parte da chave, o criptoanalista escolhe 2n/2 pares de textos planos e cifrados, cada par denotado por (P,C). A idéia é encontrar a função exata que torne verdadeiras as equações P 0 = F (P 1, K1) e C0 = F (C1, k1), para os pares de texto ((P 0, C0), (P 1, C1)). Este ataque mostrou-se eficiente contra cifradores DES-X, Brown-Seberry, Even-Mansour e cifradores que utilizam redes Feistel [34, 35]. • Ataque Linear: É classificado como um tipo de Ataque por Texto Plano. Ele tenta linearizar o comportamento do cifrador através da criação de funções lineares de entrada e saída utilizando operações XOR na forma Pi1 ⊕ Pi2... ⊕ Pin ⊕ Ci1 ⊕ Ci2 ⊕ ...Cin = 0. Onde Pij é o j-ésimo bit do byte i do texto plano e Cij é o 33 j-ésimo bit do byte i do respectivo texto cifrado. As relações necessárias para se obter uma aproximação linear efetiva são: – Escolhe-se um subconjunto dos bits da entrada e calcula-se a paridade (operação de XOR) dos mesmos; – Escolhe-se um subconjunto dos bits da saída e calcula-se a paridade dos mesmos; – A análise acima é repetida até que todos os subconjuntos de entrada e saída sejam verificados; – Os valores acima são tabelados de tal forma que as linhas da tabela contenham os subconjuntos possíveis de entrada, enquanto as colunas contenham os subconjuntos possíveis de saída; – As entradas desta tabela representaram o número de vezes que para um dado subconjunto de bits de entrada, a paridade do mesmo é igual a paridade do subconjunto de bits de saída correspondente; A partir dessa tabela, se relaciona a probabilidade de ocorrência de valores das saídas geradas, diante dos resultados das entradas geradas em rodadas internas do algoritmo. Se a tabela mostrar algumas relações (de linha de bits de entrada com colunas de bits de saída), que se destacam por ter maior ocorrência, é possível inferir a chave utilizada pelo cifrador [36]. Esse ataque foi inicialmente aplicado ao cifrador DES, mas pode ser extendido a outros cifradores. • Ataque por Correlação: Este ataque é aplicado à cifradores de fluxo. Ele busca descobrir a chave através da relação existente entre os primeiros bits de entrada e o resultado da cifração destes bits. Muitas vezes, tal relação é procurada por comparação exaustiva de textos planos e cifrados. Uma forma de aplicar este ataque é em sistemas pequenos. Aplicações Bluetooth, são um bom exemplo pois, contém uma grande quantidade de mensagens pequenas [16]. Existem outras formas mais eficientes de criptoanálise por correlação, um delas é definida em [37] 34 2.5 Algoritmo AES Com a evolução das máquinas, uma chave de 56 bits, como era normalmente usada, não poderia mais garantir a segurança desejada. Portanto, em 1997, o National Institut of Standards and Technology (NIST), órgão do governo americano, iniciou um processo de escolha do sucessor do algoritmo DES até então utilizado [3]. O algoritmo escolhido foi o Rijndael, criado por Joan Daemen e Vicent Rijmen [27]. Após a escolha, este algoritmo foi batizado de AES (Advanced Encryption Standard) e adotado como padrão de cifração do governo americano para cifradores simétricos. O AES é um cifrador simétrico de blocos, originalmente projetado para cifrar blocos de texto plano de 128, 192 e 256 bits. Diferente da maioria dos cifradores modernos, ele não usa Redes Feistel. Para garantir a difusão dos dados cifrados, ele utiliza camadas de passos que misturam linearmente os dados e Caixas-S, como visto mais adiante [27]. Para aplicar o conceito de confusão, o AES utiliza um gerador de sub-chaves e a função AdicionaChaveRodada. O tamanho das chaves também varia entre 128, 192 e 256 bits [3]. Ele trabalha de forma iterativa, isto é, as mesmas operações são realizadas varias vezes sobre o mesmo grupo fixo de bytes, provocando assim a difusão dos dados [15, 2, 27]. Segundo Daemen e Rijmen, cada uma dessas operações pode ser divididas em funções. Denomina-se rodada cada uma das vezes que o conjunto total de operações é aplicado sobre o texto plano. Este conjunto de operações é mostrado na Figura 2.6. A chave é subdividida em várias sub-chaves, cada uma delas é usada em uma rodada. O número de rodadas varia conforme o tamanho da chave e do bloco de dados. Entretanto, um número mínimo de rodadas é necessário para garantir confusão e difusão suficientes para resistir a ataques criptográficos [38]. A Tabela 2.1 mostra a relação de rodadas e tamanho da chave utilizadas pelo AES. TABELA 2.1 – Número de Rodadas em Função do tamanho dos blocos e das chave no AES [4]. Tamanho da chave Tamanho do bloco Número de rodadas AES-128 128 128 10 AES-192 192 128 12 AES-256 256 128 14 35 não Ultima rodada? sim Chave AdicionaChaveRodada Bloco Pj, com n bytes de texto plano ByteSub DeslocamentoLinha MixColumn AdicionaChaveRodada AdicionaChaveRodada ByteSub DeslocamentoLinha n bytes de texto cifrado Expansão e seleção da Chave K1 K2.. Kn-1 Kn a) Fluxo de Cifragem AdicionaChaveRodada InvByteSub InvDeslocamentoLinha InvByteSub InvDeslocamentoLinha InvMixColumn AdicionaChaveRodada não Ultima rodada? sim n bytes de texto plano Bloco Cj, com n bytes de texto cifrado AdicionaChaveRodada b) Fluxo de Decifragem K1 K2.. Kn-1 Kn FIGURA 2.6 – Fluxo de cifração e decifração do Algoritmo AES [3]. O processo se inicia com a função geradora de sub-chaves a qual se divide em duas rotinas: expansão da chave e seleção da chave. Na expansão da chave, as primeiras Nk palavras de 32 bits contém a chave original. O restante das sub-chaves são geradas recursivamente através de dois algoritmos, um para chaves de origem menores ou iguais a 128 bits e outro para chaves de origem maiores que 128 bits. A descrição deste algoritmo, escrito em linguagem C, pode ser vista em [38]. Após a geração do conjunto de sub-chaves o AES entra no ciclo de cifração propriamente dito. Selecionando, a cada rodada, seis palavras consecutivas do vetor de sub-chaves. Conforme Berent em [2] e Daemen em [27], o ciclo de cifração é composto das seguintes funções mostradas na Figura 2.6: • AdicionaChaveRodada: Uma operação de XOR é realizada entre o bloco de texto plano e a sub-chave da rodada, a qual possui o mesmo tamanho do bloco de dados. • ByteSub: Os bytes de cada bloco, resultante da operação AdicionaChaveRodada são substituídos por seus equivalentes em uma tabela de substituição (Caixa-S), seguindo a mesma metodologia descrita na Seção 2.3. Esta operação foi projetada 36 para atuar contra ataques lineares, diferenciais e de interpolação [39]. • DeslocamentoLinha: Os bytes de entrada da função são rotacionados em grupos de 4 bytes Sij com i, j = (0, 1, 2, 3, ...). Esta rotação depende do tamanho do bloco. A Figura 2.7 mostra um exemplo de rotação de bloco de 16 bytes (128 bits) divididos em blocos de 4 bytes. Nota-se que a primeira parte do bloco não é rotacionada, a segunda é rotacionada de 1 byte, a terceira de 2 bytes e a parte final de 3 bytes. Esta função protege o algoritmo contra ataques Multiset [39]. Além de aumentar a difusão dos dados [3]. FIGURA 2.7 – Operação de DeslocamentoLinha usada no algoritmo AES [4]. • MixColumns: Tomando como base o exemplo da Figura 2.7, e sendo 0 ≤ c < número de blocos, ela pode ser definida como uma operação matricial conforme: S ′ 0,c S ′ 1,c S ′ 2,c S ′ 3,c = 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 S0,c S1,c S2,c S3,c A escolha da matriz é fixa e pré-definida, de modo a favorecer a segurança do cifrador. Tomando S ′ = A ⊗ S, como o resultado desta multiplicação, os quatro bytes das colunas são trocados por: S ′ 0,c = (02 · S0,c)⊕ (03 · S1,c)⊕ S2,c ⊕ S3,c 37 S ′ 1,c = S0,c ⊕ (02 · S1,c)⊕ (03 · S2,c)⊕ S3,c S ′ 2,c = S0,c ⊕ S1,c ⊕ (02 · S2,c)⊕ (03 · S3,c) S ′ 3,c = (03 · S0,c)⊕ S1,c ⊕ S2,c ⊕ (02 · S3,c) Isto proporciona a cada byte do grupo influenciar todos os outros bytes, conforme pode ser visto na Figura 2.8, o que provoca grande difusão entre os dados [27]. FIGURA 2.8 – Operação de MixColumns no algoritmo AES, sendo Nk o número de bytes da chave e Nb o número de bytes de cada bloco [4]. Conforme dito anteriormente, o AES utiliza-se de rodadas sobre operações simples para cifrar e decifrar os dados. Como ilustra a Figura 2.6 a cifração inicia-se com uma operação de AdicionaChaveRodada, entre o bloco de texto plano Pj e a parte Kn da chave total. O resultado é a entrada de uma Rodada. Na cifração, uma rodada é composta pelas funções básicas descritas anteriormente: ByteSub, DeslocamentoLinha, MixColumns e AdicionaChaveRodada, executadas na respectiva ordem. O resultado de cada operação é o valor de entrada da operação seguinte. Ao final, a função AdicionaChaveRodada faz uma operação de XOR entre o resultado de MixColumns e a parte Kn+1 da chave. O resultado passa a ser o inicio de uma nova Rodada. A quantidade de rodadas é definida pelo tamanho da chave e dos blocos de dados, conforme a Tabela 2.1. Nota-se que ao final, a última rodada não realiza a operação de MixColumns. A decifração (ver Figura 2.6) é realizada aplicando-se as funções inversas a ByteSub, DeslocamentoLinha e MixColumns. Inicialmente, um bloco Pj 38 de bytes cifrados é aplicado a entrada da primeira rodada. A função AdicionaChaveRodada executa uma operação de XOR com a parte final Kn da chave. Ainda na primeira rodada, aplica-se as funções inversas InvDeslocamentoLinha e InvBytesSub. A partir da segunda rodada até a final são aplicadas as funções AdicionaChaveRodada, InvMixColumns, InvDeslocamentoLinha, InvByteSub. A última operação, AdicionaChaveRodada, aplica um XOR entre a saída da Rodada final e a parte inicial K1 da chave. As operações executadas pelas funções inversas são computacionalmente mais custosas. Como conseqüência, a decifração é mais demorada que a cifração. 2.6 Algoritmo Sosemanuk O Sosemanuk é um cifrador de fluxo que utiliza tamanhos de chave de 128 bits. Surgiu como um candidato do projeto eEstream, organizado por um convênio de empresas e universidades européias chamado de ECRYPT. Este projeto visa identificar cifradores de fluxo promissores, e que possam ser aplicados comercialmente [28]. Atualmente ele está na fase 3 de avaliação do projeto eEstream. Conforme as análises feitas até o momento, ele demonstra ser um cifrador simétrico muito promissor. O Sosemanuk utiliza princípios básicos do cifrador Snow 2.0, e transformações derivadas do cifrador Serpent, ambos descritos abaixo. Tem como principais características a utilização de uma rotina muito rápida de preenchimento do vetor de inicialização IV e o uso de uma reduzida quantidade de dados estáticos. Estas características mantém seu desempenho constante para diferentes hardwares. Além disso, o compartilhamento de técnicas de diferentes algoritmos de cifração aumenta a segurança, principalmente para ataques de correlação. Mais ainda, o uso de pouca memória somado ao descarte freqüente de dados em memória sujeitos a exploração, reforça sua segurança. Para entender o funcionamento do Sosemanuk devemos conhecer alguns detalhes dos dois cifradores nos quais ele é baseado: Serpent: É um cifrador de blocos de 128 bits que divide-os em quatro blocos de 32 bits. O Sosemanuk utiliza algumas rodadas desde algoritmo. Uma rodada do Serpent é a aplicação dos 4 blocos de entrada sobre oito Caixas-S distintas. Seu 39 resultando são 4 novos blocos de 32 bits de saída. Em cada rodada do Serpent não existem transformações lineares. Mais detalhes sobre a transformação linear e o funcionamento completo do Serpent podem ser vistos em [40]. Snow: Assim como a maioria dos cifradores de fluxo, o Snow utiliza o LFSR. Geralmente, cada cifrador utiliza seu próprio conjunto de LFSRs. Entretanto, o Sosemanuk utiliza um LFSR similar ao algoritmo Snow [5]. Além das Caixas-S do Serpente e o LFSR modificado do Snow, o Sosemanuk utiliza também uma máquina de estados finitos (MEF). A interação entre estes três componentes pode ser vista na Figura 2.9. Como foi mencionado, o Sosemanuk processa unidades de 32 bits de textos planos. Os registradores R1 e R2 são a área de entrada de textos planos, eles recebem 32 bits de texto plano cada um. St St+1 St+3 St+7 St+9 α-1 α Ft(x4) Texto Cifrado R2 Trans R1 Serpent1 mux lbs X1 X2 Texto Plano Texto Plano MEF Herança do Serpent (Caixa-S) Herança do SNOW (LFSR) FIGURA 2.9 – Processo de cifração do Algoritmo Sosemanuk [5]. O Sosemanuk combina um LFSR com operações de rotação, XOR, α(X) e β(X). As operações α(X) e β(X) são definidas como sendo: α(X) = X4 + β23(X)X3 + β245(X)X2 + β48(X)X + β239(X) β(X) = X8 +X7 +X5 +X3 + 1 X = Posição S0 e S3 do LFSR 40 A MEF pode ser vista na Figura 2.9, e é definida como: MEFt(R1t−1, R2t−1, st+1, st+8, st+9) → (R1t, R2t, Ft) , onde (2.2) R1t = (R2t−1 +mux(lsb(R1t−1), st+1, st+1 ⊕ st+8))mod232, R2t = Trans(R1t−1), Ft = (st+9 +R1tmod2 32)⊕R2t. Sendo lbs(x) o bit menos significativo de x e mux(c, x, y) igual x se c = 0 ou y se c = 1. A função Trans é definida como Trans(z) = (M × z mod232) <<< 7. M é a constante hexadecimal 54655307, propositalmente escolhida para aumentar a segurança do algoritmo. A operação <<< 7 é o deslocamento de bits para esquerda em 7 unidades. As funções X1 e X2 são operações de XOR definidas como: X1 = st+9 +R1tmod2 32, X2 = (R2t−1 +mux(lbs(R1t−1), st+1, st+1 ⊕ st+8))mod232. O processo de inicialização da MEF e a entrada da chave ocorre em duas partes. A primeira chamada de key schedule utiliza o Serpent24. O Serpent24 é uma variação do Serpent. Ele utiliza apenas 24 rodadas para cifrar os dados, ao invés das 32 normalmente utilizadas. Nesta fase a chave do usuário é injetada no Serpent24 que gera 25 sub-chaves de 128 bits cada. O Serpent aceita chaves de 1 a 256 bits porém, o Sosemanuk foi projetado para trabalhar com chaves de 128 bits. Desta forma, a entrada de chaves superiores a 128 bits não garante o aumento da segurança na cifração [5]. A segunda parte do processo utiliza novamente o Serpent24, previamente inicializado pelo processo key schedule. Nesta fase, a entrada do algoritmo é o vetor de inicialização IV de 128 bits, o qual é compartilhado secretamente por ambos: emissor e receptor. Os valores da décima segunda (Y 12 3 , Y 12 2 , Y 12 1 , Y 12 0 ), décima oitava (Y 18 3 , Y 18 2 , Y 18 1 , Y 18 0 ) e vigésima quarta rodadas (Y 24 3 , Y 24 2 , Y 24 1 , Y 24 0 ) são utilizados para inicializar a MEF da seguinte maneira: (s7, s8, s9, s10) = (Y 12 3 , Y 12 2 , Y 12 1 , Y 12 0 ) 41 (s5, s6) = (Y 18 1 , Y 18 3 ) (s1, s2, s3, s4) = ((Y 24 3 , Y 24 2 , Y 24 1 , Y 24 0 ) R10 = Y 18 0 R20 = Y 18 2 A cada rodada, novas unidades de texto plano de 32 bits cada são inseridos nos registradores R1 e R2. Após a MEF gerar quatro ft, se aplica o Serpent1 sobre (ft, ft+1, ft+2, ft+3). A exemplo do Serpent24, o Serpent1 é a aplicação de uma rodada do Serpent sobre os dados de entrada. A saída do Serpent1 é combinada com as quatro primeiras posições do LSRF através de uma operação de XOR. Conforme segue: (R0, R1, R2, R3) = Serpent1(ft, ft+1, ft+2, ft+3 ⊕ (St, St+1, St+2, St+3) Os valores resultantes desta operação são a saída do cifrador. Na decifração a inicialização da MEF é idêntica a cifração. O processo de decifração aplica as operações da MEF na ordem invertida para extrair o texto plano. Como observado, o Sosemanuk procura unir a segurança do conhecido cifrador de blocos Serpent a outros padrões de projeto de cifração. Estes padrões são: não aplicação direta de IV e da chave na cifração; o uso de um tipo de LFSR; rápida inicialização; rápida cifração e uso de pouca memória. Mesmo assim, ele tem alguns problemas. Um deles é a não garantia de que chaves superiores à 128 bits promovam maior segurança. Além disso, o Sosemanuk ainda esta sobre avaliação. Mesmo com os promissores resultados dos estudos preliminares contra ataques de correlação, entre outros, ainda não se pode garantir que ele seja um cifrador totalmente seguro. Serão necessários mais estudos e testes para que o Sosemanuk tenha as garantias de segurança que o AES provê, após anos de estudos e aplicações práticas. 2.7 Algoritmo RC4 O RC4 é um cifrador de fluxo amplamente utilizado no mundo. Embora já exista uma nova versão do algoritmo (RC5) e, atualmente, outros cifradores mais seguros e velozes, ele ainda é muito utilizado [41]. Seu funcionamento é simples, ele tem uma 42 fase de inicialização da chave chamada de key-scheduling algorithm (KSA). O RC4 aceita chaves de 1 a 256 bits. Ele utiliza um vetor S que é primeiramente inicializado em sua totalidade, conforme mostra a Equação 2.3. for i from 0 → 255 S[i] := i end for (2.3) Após, o vetor S é processado com 256 iterações do algoritmo PRGA e, ao mesmo tempo, combina o resultado do algoritmo PRGA aos valores da chave. A Equação 2.4 mostra a segunda parte do processo de inicialização do RC4. j := 0 for i from 0 to 255 j := (j + S[i] + key[i mod keylength]) mod256 swap(S[i], S[j]) end for (2.4) sendo keylength o tamanho da chave. O fluxo principal de cifração também utiliza o algoritmo FRGA. A cada iteração, o algoritmo PRGA modifica o seu estado interno e gera um byte de saída. O FRGA permanece ativo até que todos os valores do texto plano (input) sejam processados. A saída é o resultado de uma operação de ⊕ (XOR) entre o byte de entrada e o módulo de 256 do valor do vetor S, na posição S[i] + S[j]. Cada valor da posição S[i] é trocado com a posição S[j], a cada 256 iterações. Essa troca não é uma regra fixa, existem variações do RC4 que fazem a troca com mais freqüência, o que aumenta a segurança do algoritmo [42, 41]. A Equação 2.5 mostra o processo de cifração do RC4. 43 i := 0, j := 0, idx := 0 while idx < input.length i := (i+ 1) mod 256 j := (j + S[i]) mod 256 swap(S[i], S[j]) output S[(S[i] + S[j]) mod 256]⊕ input[idx] idx := idx+ 1 end while (2.5) Embora seja muito utilizado e de construção simples, o RC4 é alvo de diversos ataques criptoanalíticos como os citados em [43, 44]. O RC4 não utiliza LFSR, que é um elemento comun em cifradores de fluxo. Para gerar símbolos cifrados, ele implementa uma máquina de estados sobre operações simples, iteradas em um número finito de rodadas. Desta forma, ele utiliza a base de cifradores de fluxo, a qual é gerar símbolos pseudo-aleatórios, baseados em um estado inicial e chave secreta, combinados com os símbolos planos. 44 Capítulo 3 Dinâmica Caótica Aplicada à Criptografia Neste Capítulo, serão considerados dois algoritmos de cifração/decifração baseados em mapas caóticos. O primeiro é o de Baptista [6], que usa a dinâmica de um mapa logístico. O outro, proposto recentemente por De Oliveira e Sobottka [26], segue a mesma filosofia do algoritmo de Baptista, mas com aperfeiçoamentos importantes. Para tal, será feita uma breve revisão de conceitos em dinâmica caótica de mapas, e depois, as descrições desses dois algoritmos. 3.1 Conceitos Básicos de Mapas Caóticos Um sistema dinâmico é um conjunto V de estados, denominado de espaço de estados, junto com uma regra que determina o estado presente xn em função dos estados passados xn−1, xn−2, .... Os sistemas dinâmicos podem ser classificados como determinísticos ou estocásticos. Um exemplo de sistema determinístico é dado por uma função ou mapa bem definida f : V → V como xn = f(xn−1). Nesta função pode-se determinar o estado atual unicamente observando-se o estado anterior. Nos sistemas estocásticos, o estado atual é definido através de uma regra aleatória. Por exemplo, estando no estado xn = 5, e supondo-se que existem 50% de chances de xn+1 = 6 e outros 50% de chances de xn+1 = 4, conforme o resultado do lançar de uma moeda, não existe como determinar com certeza o estado xn+1 através de seu estado anterior xn 45 [45]. Os sistemas dinâmicos também podem ser classificados como contínuos e discretos. Nos sistemas discretos a variável tempo é incrementada a cada iteração do sistema e assume valores no domínio dos inteiros não negativos, (incluindo o zero), conforme o exemplo citado acima, definido por um mapa f : V → V . Nos sistemas contínuos, a variável tempo assume valores contínuos, isto é, em intervalos dos números dos reais. Talvez os exemplos mais famosos sejam aqueles definidos pela segunda lei de Newton, F = ma, que relaciona a força que age em um objeto de massa m com a sua aceleração a. Com efeito, esta equação pode ser escrita sob a forma ẍ−F/m = 0, onde cada ponto define uma derivada no tempo. Esta é uma equação diferencial ordinária, cujas soluções x(t) são trajetórias que definem qual o estado no tempo contínuo t, dado que em t = 0 tem-se a condição inicial x(0) = x0. No caso das aplicações criptográficas consideradas neste trabalho, os sistemas dinâmicos usados são determinísticos, discretos e unidimensionais. Mais precisamente, são dados por uma função ou mapa f : V → V em um subconjunto V ⊂ R. Neste trabalho tais sistemas serão denotados genericamente por S. A órbita γ de S correspondente à condição inicial x0 é a seqüência γ = (x0, x1, x2, . . .), onde xn = f n(x0). Neste caso, a variável temporal n de S é discreta, e seus estados são os pontos x ∈ V . As órbitas de S podem ser abertas, eventualmente periódicas ou periódicas. As periódicas são aquelas em que existe m ∈ N tal que xn+m = xn para todo n ∈ N. O menor valor de m é o período da órbita. As eventualmente periódicas são aquelas que, a partir de um certo k ∈ N, tornam-se periódicas. As que não são periódicas, nem eventualmente periódicas, são denominadas de órbitas abertas [45]. Portanto, se o mapa f : V → V é simples, o correspondente sistema dinâmico S define uma maneira fácil de se obter uma progressão de valores numéricos. A simplicidade é uma das características requeridas para o uso na criptografia. Entretanto, para ser usado na cifração de mensagens, S precisa apresentar comportamento complexo, pois é isto que garantirá a segurança do sistema criptográfico. A maneira de um sistema determinístico apresentar comportamento complexo é a caoticidade. Segundo Devaney [46], um sistema dinâmico S definido pelo mapa f : V → V é caótico se (a) exibe sensibilidade às condições iniciais, (b) é topologicamente transitivo, e (c) o conjunto Cper dos pontos periódicos de f é denso em seu domínio V . A sensibilidade de S às condições iniciais implica que as órbitas originadas 46 em duas condições iniciais próximas, eventualmente ficarão completamente descorrelacionadas, e portanto afastadas uma da outra. Esta é a raiz do comportamento complexo dos sistemas caóticos e da sua imprevisibilidade computacional. A transitividade topológica implica que órbitas típicas visitam todos as partes do domínio V de S. Por causa disto, o afastamento entre órbitas distintas, mesmo que inicialmente próximas, assume valores próximos ao diâmetro do domínio V , o que implica em incerteza total. E, finalmente, a densidade de órbitas periódicas sinaliza a regularidade da dinâmica. Afinal, S é determinístico. Entretanto, os pontos de Cper pertencem a órbitas instáveis, ou repulsoras. Isto significa que órbitas próximas às órbitas em Cper tendem a se afastar delas. Por outro lado, as órbitas abertas de um sistema caótico S costumam ter um comportamento contrário, ou seja, são atratoras. Isto impede o overflow computacional. Talvez o mais importante e popular exemplo de sistema dinâmico discreto unidimensional seja a família dos mapa quadráticos, dados por fµ(x) = µx(1− x), (3.1) com parâmetro real µ > 1, também conhecidos como mapas logísticos. Esta família de mapas exibe, a depender do valor do parâmetro µ, muitos dos regimes dinâmicos observados em sistemas dinâmicos em geral, inclusive regimes caóticos. A seguir, desenvolve-se um estudo mais detalhado da dinâmica dessa família de mapas. Pode-se verificar facilmente que os mapas logísticos possuem xa = 0 e xb = (µ − 1)/µ como pontos fixos, isto é, com período fixo m = 1. Nota-se que, qualquer que seja o valor de µ > 1, o ponto xb pertence ao interior do intervalo I = [0, 1], e o ponto xa = 0 é sempre repulsor. Se 1 < µ < 3 então xb será atrator enquanto que, se µ > 3, será repulsor. No primeiro caso, o mapa fµ tem uma dinâmica inteiramente dominada por xb, isto é, para toda condição inicial x0 no interior do intervalo I , tem-se limn→+∞ fnµ (x0) = xb, enquanto que fora do intervalo I, tem-se limn→+∞ f n µ (x0) = −∞. Quando a barreira µ = 3 é ultrapassada, xb perde sua estabilidade e surgem, próximo a ele, dois outros pontos periódicos de período 2 estáveis. Tem-se então uma órbita de período 1 (ponto fixo) instável e uma de período 2 estável. Na medida que µ continua crescendo, tais pontos estáveis vão se distanciando um do outro até que perdem 47 suas estabilidades e dão origem a dois novos pontos cada um, desta vez de período 4 e estáveis. Tem-se agora 3 pontos instáveis (períodos 1 e 2) e 4 estáveis (de período 4). Em termos de órbitas, temos duas instáveis (de períodos 1 e 2) e uma estável (de período 4). Tal seqüência de duplicação de período vai acontecendo mais rapidamente (em relação às variações de µ) até que o número de órbitas instáveis seja infinito. Como se verá mais tarde, é nesse ponto (valor de µ) que se tem caos (conforme definido por Devaney [46]). A Figura 3.1 ilustra essas transições, onde se pode notar a existência de muitas janelas de periodicidade [45] 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 Xn Xn+10 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 Xn Xn+10 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Xn Xn+10 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Xn Xn+1A B C D FIGURA 3.1 – Mapas de tabelamento para condição inicial x0 = 0.1 e valores em (A), µ = 2, 9 (ponto fixo); em (B), µ = 3, 2 (período 2); em (C), µ = 3, 5 (período 4) e em (D), µ = 3, 86 (caos). 48 Depois de atingido este primeiro regime caótico, o sistema volta a ficar regular (não caótico). Passa a ter uma só órbita estável que perde sua estabilidade dando origem a duas novas órbitas estáveis que, posteriormente, perdem sua estabilidade dando origem a quatro novas órbitas estáveis e assim por diante, repetindo o comportamento anterior. Desta forma, no intervalo 3 < µ ≤ 4 o mapa logístico alterna seu comportamento entre caótico e não caótico. As transições sofridas pelo mapa logístico quando se varia o parâmetro µ chamam-se de bifurcações. De uma maneira geral, chama-se de bifurcação qualquer mudança estrutural ou qualitativa sofrida por um sistema dinâmico pela variação de seus parâmetros. As principais mudanças qualitativas sofridas por sistemas dinâmicos são: perda de estabilidade de órbitas periódicas estáveis, surgimento de novas órbitas periódicas, aniquilação de órbitas periódicas e mudanças no conjunto dominante (atrator ou repulsor). A Figura 3.2 mostra as bifurcações do mapa logístico para 2, 5 < µ < 4, 0. Tal gráfico de bifurcações pode ser obtido adotando-se o seguinte procedimento para cada valor de µ. Primeiramente, (a) escolhe-se um conjunto suficientemente ‘grande’ de condições iniciais no interior do intervalo I , depois (b) obtém-se as órbitas de cada uma dessas condições iniciais iterando-se fµ um ’grande’ número de vezes (então cada órbita tenderá ao mesmo atrator) e, finalmente, (c) descarta-se um ‘grande’ número de pontos iniciais de cada uma das órbitas obtidas (digamos metade dos pontos). O primeiro e o segundo passos servem para se detectar todos os pontos atratores, enquanto que o último serve para descartar os pontos (transientes) inicias das órbitas, mantendo-se assim, somente aqueles pontos que se confundem com os estados assintóticos, de tão numericamente próximos que estão. A palavra ’grande’ é usada (três vezes) o que de fato não confere ao procedimento um caráter muito preciso. Realmente não há uma maneira geral e rigorosa de se estabelecer o quão grande têm que ser os ’grandes’ mencionados acima. Decidir isso requer um procedimento do tipo tentativa-e-erro no sentido de que, a partir de um determinado valor, qualquer noção de ’grande’ serve, isto é, conduz ao mesmo resultado gráfico. Finalmente, observamos que, no caso do mapa logístico, o passo (a) acima pode ser relaxado e ser executado a partir de uma única condição inicial. Entretanto, o processo como descrito acima é mais geral e aplicável a qualquer sistema. Para 1 < µ ≤ 4, intervalo I = [0, 1] é um conjunto invariante do mapa logístico fµ, isto é, fµ(x) ∈ I para todo x ∈ I . Para µ > 4, I deixa de ser invariante de 49 2.6 2.8 3 3.2 3.4 3.6 3.8 4 0.2 0.4 0.6 0.8 1 x µ FIGURA 3.2 – Diagrama de bifurcações do mapa logístico para 2.5 < µ < 4 (eixo horizontal). No eixo vertical estão representados os pontos fixos/periódicos. Note a seqüência de duplicações de períodos até que os (vários) regimes caóticos se estabeleçam. fµ, mas continua sendo caótico num subconjunto Λ ⊂ I , este sim invariante de fµ. É possível mostrar que Λ é de fato um conjunto de Cantor, que sabidamente tem geometria fractal, ou seja, é invariante por mudanças de escala. Este conjunto entretanto não possui órbitas estáveis. Portanto, Λ é um repulsor pois as órbitas que começam próximas de seus pontos divergem para −∞. Por esta razão, não é possível qualquer explicitação de Λ por procedimentos computacionais que envolvam operações com ponto flutuante, pois os erros de arredondamento ocasionam divergências. Como dito anteriormente, as características dinâmicas encontradas nos mapas logísticos são também encontradas em muitos outros sistemas dinâmicos, tanto discretos quanto contínuos. Por isto são muito importantes. Além disso, é neste tipo de mapa que se baseia um dos métodos de criptografia caótica abordados neste trabalho. Conforme citado anteriormente, um sistema dinâmico S definido pelo mapa deve possuir dinâmica complexa para garantir a segurança do método de criptografia que o utiliza. Por isto, é conveniente que S seja caótico. Uma das maneiras de se quantificar a 50 caoticidade de um sistema dinâmico é através de seu expoente de Lyapunov. Por causa da transitividade topológica, é possível se definir o expoente de Lyapunov L de S a partir de qualquer uma de suas órbitas típicas. Com efeito, se γ = (x0, x1, x2, . . .) é uma órbita típica de S , então L(γ) := lim N→∞ 1 N N−1∑ n=0 logb |f ′(xn)|, (3.2) onde xn = fn(x0). Os expoentes de Lyapunov locais de f em xn são calculados pela equação: l(xn) := logb |f ′(xn)| (3.3) Tais expoentes medem a separação (se l(xn) > 0) ou aproximação (se l(xn) < 0) local das órbitas próximas a γ em torno de xn, para cada instante n. A Equação (3.2) diz que L(x0) é a média aritmética dos expoentes de Lyapunov locais avaliados nos pontos de γ. Como uma órbita típica visita todas as partes do domínio de S, tem-se que L(x0) é uma medida global da sensibilidade de S às condições iniciais. Por isto, muitas vezes L = L(x0) é denominado expoente de Lyapunov global de S [45]. Em (3.2), a base b do logaritmo pode ser qualquer número positivo maior que 1, dizendo respeito à unidade em que a separação esta sendo medida. Os valores mais utilizados são b = 2, b = 10 e b = e (número de Napier). No primeiro caso, o expoente é medido em bits por unidade de tempo. Note que γ é repulsora se L(γ) > 0 e atratora se L(γ) < 0. A Figura 3.3 mostra o expoente de Lyapunov do mapa logístico (3.1), para 3.5 ≤ µ ≤ 4, junto com seu diagrama de bifurcação. Nela pode-se notar claramente que, nas janelas de periodicidade, tem-se L < 0. Os expoente de Lyapunov são importantes em termos de criptografia, na medida que quantificam a taxa de produção de incerteza do mapa caótico no tempo. Como regra geral, quanto mais caótico for o sistema, mais segura será a criptografia nele baseado. O algoritmo de De Oliveira e Sobottka [7] utiliza os expoentes de Lyapunov para aumentar a segurança da cifração de dados. O expoente de Lyapunov, juntamente com a propriedade de ergodicidade são a base da segurança do algoritmo de De Oliveira e Sobottka. Por ser ergódico, o algoritmo garante que as chances de ocorrer visitação não uniforme dos sítios de seu 51 FIGURA 3.3 – Expoentes de Lyapunov e diagrama de bifurcação do mapa logístico plotados juntos para 3.5 ≤ µ ≤ 4. mapa caótico tende a zero. Para se ter uma idéia de quão pequena é a chance de gerar um mapa com visitação não uniforme, podemos comparar isso a chance de um gerador pseudo-aleatório sortear um milhão de vezes seguidas o mesmo número. A chance existe, porém tende a zero. A Teoria Ergódica usa o termo técnico "quase"para referenciar-se a essa propriedade. Conforme o sentido dado, esse termo técnico pode definir tanto eventos que tendem a nunca ocorrer, quanto eventos que tendem a ocorrer sempre. 3.2 O Cifrador de Baptista No que se segue, P = (P1, P2, . . . , PL) é o texto plano e C = (C1, C2, . . . , CL) a sua versão cifrada. A denota o alfabeto utilizado com #A símbolos. Em seu modelo, Baptista [6] escolhe um subintervalo X = [xmin, xmax] ⊂ [0, 1] do domínio de um mapa Logístico (3.1) caótico com 3 < µ < 4. O intervalo X é então 52 dividido em #A sítios de tamanho e = ( xmax − xmin)/#A. A cada um dos sítios Ik é associado um símbolo do alfabeto A, definindo um mapeamento dos símbolos de A aos subintervalos Ik. A Figura 3.4 mostra o esboço do mapeamento adotado por Baptista. FIGURA 3.4 – Mapeamento dos símbolos do alfabeto dentro do intervalo do Mapa Caótico definido por Baptista [6]. A chave de cifração é dada por um valor x0 ∈ (0, 1), a partir do qual fµ = µx(1 − x) é iterada, dando origem à órbita γ = (x0, x1, x2, . . .) com xn = fnµ (x0), n = 0, 1, 2, . . .. A cifração se baseia na órbita γ associada a uma condição inicial x0 (a chave). De modo breve, a versão cifrada de cada símbolo Pj constituinte de um texto plano P = (P1, P2, . . . , PL) é dada pelo número de iterações de fµ necessárias para que a órbita γ visite o sítio associado a Pj . Por cifrar um símbolo de cada vez, o sistema de Baptista é classificado com um sistema de cifração de fluxo (stream cipher). A viabilidade do processo de cifração se baseia na transitividade dos mapas caóticos, que garante que cada um dos sítios será visitado depois de um certo número de iterações de fµ. Portanto, o parâmetro µ deve ser muito bem escolhido, de modo a garantir a caoticidade de fµ. Por exemplo, valores de µ < 3 não podem ser aceitos pois ai fµ não é caótico. Além disso, valores de µ > 3 onde o expoente de Lyapunov não é positivo, também não devem ser aceitos. Como pode se ver na Figura 3.3, mesmo escolhendo valores 3 ≤ µ ≤ 4, não se pode garantir que fµ é caótico. Isto se constitui num importante inconveniente do método de Baptista. Na versão cifrada C = (C1, C2, . . . , CL) de P = (P1, P2, . . . , PL), cada componente Cj é o número de iterações de fµ, a partir do ponto anterior 53 fC1+C2+...+Cj−1(x0), necessárias para a órbita γ visitar um sítio correspondente ao símbolo Pj que se deseja cifrar. Portanto, para cada símbolo do texto plano, um novo valor de iterações é gerado no texto cifrado [6]. Notasse que a contagem do número de iterações para cifrar Pj se inicia sempre do ponto usado para cifrar o símbolo anterior Pj−1. Portanto, a cifração de Pj depende da cifração de todos os símbolos planos anteriores, de P1 a Pj−1. Esta é uma característica desejável em códigos de cifração pois causa a difusão das características estatísticas de P em relação à sua versão cifrada C [1]. Como exemplo hipotético de funcionamento, supondo-se que, é aplicado o mapa fµ, a partir de um certo x0 (chave), sobre o texto plano "did", isto é, P = (d, i, d). Desta cifração obtém-se o texto cifrado C = (3, 4, 2), conforme representado na Figura 3.5. Isto significa que partindo do sítio x0, o mapa foi iterado três vezes até alcançar um sítio correspondente ao símbolo plano ”d”. O valor três se torna então o primeiro caractere do texto cifrado. A partir deste sítio, foram iteradas mais quatro vezes para alcançar o sítio do símbolo plano ”i”. O número quatro, é o segundo caractere do texto cifrado. Por fim, a partir do sítio ”i”, são necessárias mais duas iterações para alcançar novamente um outro sítio ”d”. O número dois compõe então o último caractere do texto cifrado. A decifração se faz de maneira óbvia: calcula-se as iteradas x1 = f 3µ(x0), x2 = f 4 µ(x1) e x3 = f 2 µ(x2), e verifica-se qual dos símbolos de A está associado aos sítios Ik aos quais pertencem cada um dos valores x1, x2 e x3. É importante notar que, em geral, fµ necessita de um número mínimo de iterações até que, a partir de x0, exibam comportamento caótico. Antes disso, condições iniciais parecidas podem gerar os mesmos resultados em termos de cifração. Portanto, o algoritmo de Baptista define como N0 o número mínimo de iterações sobre a função logística antes de iniciar a cifração do primeiro símbolo. Como exemplo adicional, citaremos o exemplo dado por Baptista [6], onde se tem a cifração de "hi", P = (h, i), com os seguintes parâmetros: N0 = 250; µ = 3.8 e x0 = 0, 232323000000000 e a letra "h", associada ao sítio 104 que represento pelo intervalo [0,44140625000000, 0,44375000000000). A letra "i"associada ao sítio 105 que representa o intervalo [0,44375000000000, 0,44609375000000). Uma possível versão cifrada de P é C = (1713, 364). O primeiro valor C1 corresponde a um número de iterações, necessárias para xn cair no sítio 104. A partir de x0, para o segundo valor C2 inicia-se novamente a contagem de iterações a partir da posição de x1713 no sítio 104 54 b ... X0 ... a c d e f g h i j k l m n o 1’’ 1 3, 2’’ 2 4’ 3’ 2’ 1’ FIGURA 3.5 – Representação hipotética da cifração e decifração do texto plano P = (d, i, d), utilizando um mapa caótico fµ, com condição inicial x0. O mapa fµ está dividido em sítios relacionados aos símbolos do alfabeto utilizado. Os valores sobre o mapa correspondem as iterações para cifrar C1 → (1, 2, 3), C2 → (1′, 2′, 3′, 4′) e C3 → (1′′, 2′′). até que xn atinja o sítio 105. Críticas ao Modelo de Baptista Segundo Li e Lian [47], as características de sensibilidade as condições iniciais e parâmetros de controle e variabilidade podem ser ligadas aos princípios de difusão e confusão propostos por Shannon [13] e que, atualmente, são características necessárias a um bom sistema criptográfico. O algoritmo proposto por Baptista sofreu críticas quanto a falhas de segurança. Em seu artigo, Álvarez et. al. [8] tratam de algumas dessas potenciais falhas, algumas utilizando métodos clássicos como Ataque por Texto Plano Escolhido, com os quais é possível descobrir a chave x0 com facilidade. Outra forma de ataque proposta por Álvarez et. al., é através da análise da entropia dos dados gerados. A Tabela 3.1 dá um idéia do nível de entropia máxima e o atingido pelo cifrador de Baptista para textos planos contendo 1000 bytes. Nesse estudo nota-se que para textos planos com alfabeto grande, a relação entre a entropia ideal e a real se aproximam. Porém, ainda assim existe uma diferença na distribuição de símbolos que pode ser explorada. Li et al. [9], criticam a visitação não uniforme dos sítios na dinâmica de fµ, o que 55 TABELA 3.1 – Entropia ideal e obtida com o cifrador de Baptista para textos planos cifrados com alfabetos de entrada de diferentes tamanhos [8]. Tamanho do alfabeto 2 4 8 16 32 64 128 256 Entropia do cifrador de Baptista 0.71 1.58 2.75 3.84 4.87 5.89 6.88 7.86 Entropia ideal 1 2 3 4 5 6 7 8 é considerado um facilitador para ataques que analisam a entropia do sistema (ataque diferencial e ataque linear). Estes mesmos autores fazem questionamentos quanto a algumas características indesejadas em cifradores como o tamanho do texto cifrado ser maior que o do texto plano, o que segundo Schneier, é um fator limitante para algumas aplicações [10]. Devido a estes e outros problemas como os citados em [48, 49, 9], algumas propostas de modificação do algoritmo de Baptista surgiram [48]. Além disso, novos algoritmos foram propostos como em [50, 18]. A maioria destes sistemas sofrem de algum problema quanto ao desempenho, segurança e, principalmente, degradação dinâmica de métodos de cifração caóticos, aplicados a sistemas digitais [49, 48]. Este problema ocorre quando o cifrador é dependente de máquina, como é o caso do cifrador de Baptista. Isto é, conforme o número de iterações aumenta, pode existir a perda de precisão no cálculo do mapa. Como conseqüência o sistema pode divergir ou, convergir para um ou mais pontos fixos. 3.3 O Cifrador de De Oliveira e Sobottka Recentemente, De Oliveira e Sobottka [7] propuseram um cifrador baseado no modelo definido por Baptista. Este sistema será aqui referido como Cifrador Caótico, e denotado por CC. O sistema baseia-se na família de mapas Hp com parâmetro p ∈ Qx∗ , racional positivo, definidos como Hp : [0, 10p) → [0, 10p) com Hp(x) = r−1 p ◦G ◦ rp(x), (3.4) 56 onde G(x) = 10x(mod 10) e rp(x) = p √ x. As funções rp e r−1 p definem uma equivalência entre Hp e G. Como G é sabidamente caótica, o mapa Hp é caótico para todo p ∈ Q∗+. Portanto, ao contrário do algoritmo de Baptista, o parâmetro p ∈ Q∗+ poderia ser adotado como parte da chave [26]. Com este modelo, De Oliveira e Sobottka se propõem a resolver três problemas encontrados no algoritmo de Baptista. O primeiro refere-se à limitação do espaço de escolha do parâmetro µ da família de funções logísticas, que no sistema de Baptista é bastante limitado. Aqui, este problema não existe pois Hp é caótico para todo p ∈ Q∗+. Outro problema é quanto à não homogeneidade na probabilidade em que os sítios são visitados pelas órbitas. O terceiro se deve ao fato de que o uso do sistema de Baptista é dependente da máquina usada, pois é sensível aos métodos de arredondamento, enquanto que no CC não há degradação do caos. Basicamente o algoritmo CC deve, inicialmente, escolher os parâmetro p e d, depois, divide-se o domínio [0, 10p) em 10d subintervalos semi-abertos à direita Ik, e define-se uma associação uniforme dos símbolos de A para os sítios Ik. Então, segue-se a idéia original de Baptista [6], que consiste em iterar Hp sucessivamente a partir da chave x0 ∈ [0, 10p), o número necessário de vezes para a órbita γ = (x0, x1, . . .) atinja consecutivamente os sítios correspondente a cada símbolo Pj do texto plano P = (P1, P2, . . . , PL). A mensagem cifrada C é então a seqüência composta de número Cj de iterações de Hp, necessários para a órbita γ = (x0, x1, . . . , xn), dada por (xn) = (Hnp (x0)), visitar os sítios associados a cada um dos consecutivos símbolos de P . Mais precisamente C = (C1, C2, . . . , CL) é a seqüência natural de números Cj tais que HCj p (xCj−1), cai, pela primeira vez, no intervalo Ik associado a Pj . A decifração de C é feita usando a mesma chave, de maneira obvia: lendo cada Cj como o símbolo Pj associado ao sub-intervalo Ik ao qual pertence H ∑j i=1 Ci p (x0). Para cada p ∈ Q+, a medida λp associada a Hp é dada por λp ( (a, b) ) = p√ b− p√a 10 , para todo (a, b) ⊆ [0, 10p). Segundo De Oliveira e Sobottka, se definido que Ik = [ kp 10p(d−1) , (k+1)p 10p(d−1) ) , k ∈ Kd, isto significa que a freqüência de visitação de cada sítio Ip é a mesma e igual a 1/10p. Portanto o cifrador é isento de tendências quanto à cifragens de sílabas do alfabeto A utilizado [26]. 57 Ajuste do Grau de Segurança O grau de confusão aplicado ao texto cifrado pode ser regulado através do expoente de Lyapunov Lp, dado por (3.2) e dos expoentes de Lyapunov locais lp(xn), dados por (3.3), pois eles quantificam diretamente a sensibilidade de Hp às condições iniciais, e portanto, a segurança do sistema. A Figura 3.6 mostra o comportamento dos expoentes de Lyapunov locais deHp em cada ponto de seu domínio [0, 10p), para p = 2 e p = 4. Pode-se notar que sempre existem 10 regiões (intervalos) Rr, r = 0, 1, . . . , 9, bem definidas e similares onde o expoente de Lyapunov local varia de modo estritamente crescente. Nas discussões, abaixo adota-se a seguinte Definição de segurança, conforme De Oliveira e Sobottka [7]. Definição: Diz-se que o sistema criptográfico é ε-seguro contra ataque por força bruta quando, para quase todo par de condições iniciais x0 e x′0 tais que |x0−x′0| ≥ ε, tem-se que as órbitas correspondentes assumem uma distância superior a 0.9× 10p, antes que o primeiro símbolo P1 de P seja cifrado. Em outras palavras, se |x0 − x′0| ≥ ε, tem-se uma incerteza maior que noventa por cento do tamanho total do domínio Hp, antes de decifrar P1. Para prevenir a quebra de sigilo, o CC usa a sensibilidade às condições iniciais de Hp para garantir um grande grau de incerteza a partir de erros na chave. Para isto, escolhe-se um valor l0 < 1 como limite para o mínimo de sensibilidade às condições nos pontos correspondentes aos símbolos Cj da versão cifrada de Pj . Assim, para a ε-segurança, é necessário que somente sejam aceitos como versão cifrada de Pj valores de Cj tais que, nos pontos de [0, 10p) correspondentes, se tenha expoente de Lyapunov local maior do que ou igual a l0. Com a exigência acima, cada uma das regiões Rr, mencionadas, fica dividida em duas regiões disjuntas Rr,p,l0 = Br,p,l0 ∪̇ Cr,p,l0 onde lp(x) < l0 em Br,p,l0 e lp(x) ≥ l0 em Cr,p,l0 . Denotando Br,p,l0 = [r p, ar,p,l0) e Cr,p,l0 = [ar,p,l0 , (r+1) p), pode-se mostrar 58 que o ponto divisor ar,p,l0 é dado pela seguinte fórmula [7]: ar,p,l0 = [ r 1− 10(p−l0)/(1−p) ]p r = 0, 1, 2, . . . , 9. (3.5) 20 40 60 80 100 x -2 -1 1 2 HcL 2000 4000 6000 8000 10000 x -3 -2 -1 1 2 HdL 20 40 60 80 100 x 20 40 60 80 100 HaL 2000 4000 6000 8000 10000 x 2000 4000 6000 8000 10000 HbL FIGURA 3.6 – Gráfico de Hp e o respectivo expoente de Lyapunov local para p=2 ((a) e (c)) e p=4 ((b) e (d)). Os valores mostrados de lp são limitados ao intervalo [-3,2] para facilitar a comparação [7]. Com a fórmula acima, pode-se comparar diretamente o ponto encontrado x em [0, 10p) com ar,p,l0 , verificando se ele atende à condição do expoente de Lyapunov local mínimo, e se o sítio correspondente ao valor Cj pode ser aceito como versão cifrada de Pj . 59 Capítulo 4 Algoritmo Proposto Como descrito na Seção 3.3, o sistema de De Oliveira e Sobottka está baseado nas iterações do mapa Hp e segue o modelo de cifração proposto por Baptista. Neste capítulo, será apresentado o algoritmo CC e a arquitetura de software proposta para ele. As modificações do modelo teórico otimizam a cifração e evitam inconvenientes de cifradores baseados no modelo proposto até agora. 4.1 Modelo criptográfico do CC A implementação se baseia na relação entre a seqüencia de visitação dos sítios Ik (ver Seção 3.3) percorridos por uma órbita γ = (x0, x1, . . .) e a seqüencia dos dígitos da representação decimal de p √ x0, dada pela seguinte Proposição [7]: Proposição: O d-bloco de dígitos sn+1 . . . sn+d da representação decimal de p √ x0 determina o subintervalo (sítio) Ik ao qual xn = Hnp (x0) pertence, isto é, xn ∈ Ik com k = sn+1 . . . sn+d. Na Proposição acima, o mapa caótico dado por Hp(x0) é iterado n vezes a partir da condição inicial x0 pertencente ao intervalo [0, 10p). Enquanto que, xn é o valor da n-ésima iterada do mapa caótico, seu valor esta dentro do intervalo definido para o sítio Ik. Por fim, d é o tamanho, em dígitos, de cada sítio. Como mencionado na Seção 3.3, esta Proposição implica que, iterarHp a partir de 60 x0 sucessivamente, equivale a percorrer progressivamente os dígitos de p √ x0 em janelas de tamanho d, para encontrar os d-blocos de dígitos associados aos símbolos do alfabeto A que compõem o texto plano. Como existem métodos de cálculo de p√x0 para qualquer precisão desejada, tem-se uma implementação independente da máquina utilizada. O funcionamento do cifrador consiste em calcular os dígitos de p √ x0 e agrupá-los em d-blocos. Cada d-bloco esta associado a um símbolo do alfabeto. Iniciando-se sempre a partir do último d-bloco lido, procura-se o próximo d-bloco associado ao símbolo que se deseja cifrar. O símbolo cifrado corresponde ao número de procuras (iterações) feitas até encontrar o d-bloco relacionado com o símbolo que se deseja cifrar. A Figura 4.1 mostra com são agrupados os dígitos para formar d-blocos e como é feita a iteração sobre eles. A Figura mostra quatro iterações sobre uma órbita não periódica, dividida em d-blocos de tamanho d=3. Nota-se que, na busca, a parte inteira de p √ x0 é sempre ignorada. FIGURA 4.1 – Exemplo de varredura dos dígitos de p √ x0, com p = 3 e x0 = 5, para d = 3. A descrição apresentada acima define o método de cifração apresentado em [26] e [7]. Essa forma de cifração traz vantagens sobre a maioria dos outros cifradores caóticos, como a visitação uniforme dos sítios Ik. Em especial, essa forma de cifrar dados resolve o problema da dependência de máquina, a qual é um dos principais problemas do cifrador de Baptista e outros similares. De fato, é sabido que as máquinas têm precisão finita e isso afeta as órbitas dos mapas caóticos devido a sensibilidade desses sistemas às condições iniciais. Portanto, a maioria dos cifradores caóticos, exige que a máquina de cifração tenha a mesma precisão da máquina de decifração (8, 32, 64 bits, ...), caso contrário, há medida que os mapas são iterados, a órbita de decifração vai divergir da órbita gerada na cifração, impedindo a decifração da mensagem de forma correta, mesmo conhecendo-se a chave. Alguns cifradores propõem contra-medidas 61 para evitar esse inconveniente, como em [48, 50]. No CC esse problema não existe pois o uso da operação de raiz para extrair o mapa caótico tem cálculo exato. Além das vantagens já existentes no cifrador, novas características foram introduzidas no CC originalmente proposto, tornando-o ainda mais seguro e eficiente. Foi adicionada ao CC uma tabela de endereços Γ. Essa tabela é montada com as posições dos d-blocos associados à cada símbolo do alfabeto A, na representação decimal de p √ x0. Mais precisamente, cada linha está associada a um elemento de A, enquanto as colunas contém os d-blocos de cada elemento. Note que o símbolo Pj+1 está associado a posição ΓlPj+1 ,c, sendo lPj+1 a linha referente ao símbolo Pj+1 e a coluna c, é a c-ésima vez que o símbolo Pj+1 aparece na representação decimal de p √ x0. A Tabela 4.1 mostra um exemplo de Γ, com A = {a, b, c}. Neste exemplo, as posições 10, 106, 215, ..., 2567 correspondem a sítios do símbolo a. As posições 29, 198, 327, ..., 2608 correspondem ao símbolo b e por fim, 5, 77, 284, ..., 2670 correspondem ao símbolo c. TABELA 4.1 – Exemplo de uso da tabela Γ. Alfabeto Coluna 1 Coluna 2 Coluna 3 ... Coluna n a 10 106 215 ... 2567 b 29 198 327 ... 2608 c 5 77 284 ... 2670 Dado que, em geral, Γ é montada apenas uma vez, o processamento principal de cifração/decifração constitui uma seqüencia de procuras e salvamentos. O uso de Γ é basicamente como segue. Primeiro, encontra-se a linha correspondente ao símbolo corrente, isto é, o símbolo Pj+1 do texto plano P . Então, na linha lPj+1 toma-se o primeiro endereço de d-bloco maior do que o anteriormente usado para cifrar (iteração). A versão cifrada é a diferença entre o endereço encontrado e o endereço imediatamente anterior. Por exemplo, de acordo com a Tabela 4.1, a versão cifrada do texto "aabc"é a 7→ 10, a 7→ 106− 10 = 96, b 7→ 198− 106 = 92, c 7→ 284− 198 = 86. Nota-se que a opção 29 de b é ignorada, pois ela é menor que a posição do bloco
