21/05/2012

Introduo a criptografia [Artigo]

Introduo a criptografia
Autor: Elgio Schlemer <elgio.schlemer at gmail.com> Data: 26/02/2009 Introduo O desejo de enviar mensagens de forma segura sem que ningum mais, a no ser o destinatrio, consiga ler, to antigo quanto a inveno da escrita. Em guerras primitivas tem-se relato de generais que raspavam a cabea de um escravo e sobre a cabea escreviam mensagens secretas de guerra. Aps o cabelo crescer, o emissrio era enviado (esta tcnica de esconder mensagens chamada de esteganografia e sua verso moderna consiste em esconder mensagens em imagens ou msicas). Basicamente existem duas formas primrias de obscurecer uma mensagem (criptografar), que pode ser pelo uso de substituio ou transposio. Na substituio troca-se alguma coisa por outra, de acordo com algum critrio. Os passatempos encontrados em bancas de revistas exploram a substituio, onde o leitor levado a descobrir que onde tem tringulo deve ser considerado a letra "A", por exemplo. J na transposio apenas troca-se as coisas de lugar. Usando transposio simples, pode-se escrever a palavra "teste" como "ettse", transpondo uma letra com a sua vizinha. O mtodo matemtico de substituio para inviabilizar a leitura mais antigo que se tem registro a cifra de Csar. Elaborada por Jlio Csar, esta cifra inaugurou as chamadas cifras de substituio monoalfabticas. Na infantil Cifra de Csar, cada letra do alfabeto substituda pela sua terceira vizinha, ou seja, o "A" transformado em "D", em um alfabeto circular, onde o "Z" vira "C" (...VWXYZABC...), conforme ilustrado na figura.

Nota-se a a existncia de duas operaes distintas: a) cifrar: para cifrar uma mensagem, deve-se substituir cada letra pela terceira vizinha subsequente. Em C usando string isto poderia ser feito com: strCIF[i] = strTXT[i] + 3; No entanto, um programador experiente ver erro na frmula acima: ela s funciona at o "W" que somado
vivaolinux.com.br//impressora.php?c 1/11

21/05/2012

Introduo a criptografia [Artigo]

com 3 virar "Z". Para as letras "X", "Y" e "Z" a frmula falha! A entraria em ao a operao de mdulo, muito utilizada em criptografia (fica como dever de casa). b) decifrar: j para recuperar a mensagem outro mtodo matemtico precisa ser usado. Ao invs de trocar pela terceira subsequente, deve-se trocar pela terceira anterior ("D" deve virar "A"). Percebe-se nitidamente duas operaes distintas para cifrar ou decifrar. Uma variao interessante da cifra de csar a Rot13, onde se troca pela dcima terceira vizinha. Ela interessante pois como o alfabeto tem exatos 26 letras, o processo de cifrar e decifrar o mesmo! Para cifrar basta achar a vizinha 13 subsequente e para decifrar tambm (a vizinha de "A" "M" e a vizinha de "M" o "A"). Ningum ir cifrar nada srio usando Csar. Serve apenas como fundamento didtico para explicar alguns conceitos, como o de chave, por exemplo. Conceito de chave A Cifra de Csar no tem chave. Toda a "segurana" est na descoberta do mtodo matemtico. Se algum descobrir que deve-se somar 3, acabou o algoritmo. Outro problema da Cifra de Csar que se eu compartilho o mtodo com 10 pessoas, todas as 10 estaro aptas a ler todas as mensagens. Mas se eu quisesse, usando esta cifra, trocar uma mensagem cifrada com a pessoa A, mas de forma que a pessoa B no possa ler, mesmo sabendo o mtodo? Uma variao da Cifra de Csar consiste em trocar a letra pela vizinha k ao invs da 3. Se eu usar k como 3, terei que o "A" troca por "D". Se eu usar k=6, terei que o "A" troca por "G", e assim por diante. A ideia deste algoritmo que todos conheam o mtodo (trocar por uma vizinha), mas ningum sabe por qual vizinha . Neste caso eu poderia combinar com a pessoa A que sempre que enviasse uma mensagem para ela eu usaria k como 3. J com a pessoa B eu combino k=6. Todos conhecem o mtodo, mas a pessoa B no saberia como ler mensagens que enviei a pessoa A pois ela no sabe que com A eu usei k=3. Eis o conceito de chave. O mtodo o mesmo, mas a chave (k) varia. Considerando que a pessoa B queira muito ler a mensagem que eu enviei para a pessoa A, tudo que ela precisa descobrir qual valor de k eu usei para o A, j que o mtodo o mesmo. A ideia que no exista segredo algum no mtodo de criptografia (muito embora alguns fabricantes insistem em basear sua segurana nisto). E como pode ser feita esta descoberta? Uma das forma atravs da fora bruta. Ataque por fora bruta Neste tipo de ataque testa-se todas as possibilidades de chave possveis, at encontrar uma que sirva. Voltando ao infantil mtodo de Csar com a modificao e presena do k, se B quisesse muito saber o que escrevi para A, ele poderia tentar usar os possveis valores de k at que a mensagem faa sentido. Neste caso k pode assumir uma variedade limitada de valores. Ele pode ser 0 (onde "A" seria trocado pelo mesmo
vivaolinux.com.br//impressora.php?c 2/11

21/05/2012

Introduo a criptografia [Artigo]

"A". Ridculo, mas matematicamente uma chave vivel), pode ser 1, 2, 3, ... 25, sendo que neste ltimo o "A" seria trocado pelo "Z". Veja que existem apenas 26 possveis valores para k neste mtodo. Um ataque por fora bruta no exigiria mais que 26 tentativas. Matematicamente se usa a estatstica aqui, sendo que ningum to sortudo para acertar na primeira tentativa e nem to azarado para acertar na ltima! Na mdia se considera que o ataque ter sucesso em 13 tentativas. Logo, neste caso, um ataque por fora bruta ter um esforo mdio de 13 tentativas. Se eu usar papel e caneta (como devia ser no tempo de Csar) e conseguir testar no ritmo de uma tentativa por minuto, levaria 13 minutos em mdia para quebrar o algoritmo. Este seria o esforo de um ataque de fora bruta Cifra de Csar, o que o torna, como disse, infantil. Mas se eu mudasse a cifra monoalfabtica um pouco. Se ao invs de ter que trocar uma letra por uma k vizinha eu usasse uma tabela de trocas:
Letra troca A B C D E F G H I J K L M ... X J M A F W C N O K B E T ...

Ser que um ataque de fora bruta seria possvel com este novo algoritmo? Um ataque de fora bruta sempre possvel, a questo quanto tempo em mdia ele levaria. O tempo de acordo com as possveis combinaes de chave. Neste caso de um algoritmo monoalfabtico com uma tabela de troca, cada letra pode ser uma das outras 25, sem poder repetir, ou seja, se j decidi que "A" troca pelo "X", ningum mais poder ser trocado pelo "X". A matemtica nos ensina que neste caso havero 26! possibilidades (fatorial de 26) para a chave. As aparncias enganam, pois fatorial de 26 resulta em 403.291.461.126.605.635.584.000.000 possveis valores para chave e isto muito, mas muito mesmo. Como calcular este fatorial no Linux? Usando bc, uma alternativa bem criativa com o comando: $ seq -s '*' 1 26|bc O comando seq ir gerar a sequncia: 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26 que ser avaliada pelo bc. Se eu tivesse um computador capaz de realizar 1 bilho de tentativas por segundo (1.000.000.000) e tiver 1 bilho destes computadores para uso, o ataque de fora bruta ainda levaria 201.645.730 segundos, ou aproximadamente 6 anos de processamento! Verifique voc mesmo no bash: $ echo "403291461126605635584000000 / 2 / 1000000000 / 1000000000 / 60 / 60 / 24 / 365" | bc Divido o nmero de tentativas por 2, pois na mdia se acerta na metade das tentativas, divido pela quantidade
vivaolinux.com.br//impressora.php?c 3/11

21/05/2012

Introduo a criptografia [Artigo]

de quebras por segundo de um computador, que um bilho, divido pelo nmero de computadores que tenho. Depois divido por 60 para transformar segundos em minutos, por 60 novamente para transformar em horas, por 24 tem-se dias e dividindo por 365 tem em anos. Logo, por fora bruta, este algoritmo de substituio monoalfabtica infalvel e inquebrvel, apenas com o desconforto de ter que memorizar uma k que uma tabela. Costumo instigar meus alunos neste momento perguntando-lhes se est a o algoritmo perfeito e inquebrvel! Ento? Por fora bruta, SIM, eis um algoritmo ideal. S que existem outros meios de se quebrar um algoritmo de cifra que atravs da criptoanlise.

Ataque por criptoanlise O ataque por fora bruta possvel em todos os casos. Ainda no existem algoritmos imunes a este ataque, ou seja, ele sempre poder ser tentado. A questo o tempo que levar. Deseja-se um algoritmo com tantas possibilidades de chave que o ataque levaria anos ou mesmo milhares de anos, de sorte que ningum sequer ir tentar este ataque por ser invivel (em tempo: estudos sobre computao quntica sugerem a possibilidade da construo de algoritmos de criptografia imunes ao fora bruta). A cifra de substituio monoalfabtica com uma tabela de trocas, citada no captulo anterior, um caso de um algoritmo para o qual demonstrou-se que o foa bruta invivel. Mas existe a criptoanlise. Simon (ver referncias) define a criptografia como a eterna guerra entre criptgrafos e criptoanalistas. Um constri para que o outro descubra como destruir! No caso mais especfico da substituio monoalfabtica ela frgil e sucumbe ao ataque de "Anlise de Frequncia". Costumo brincar de forca com meus alunos nesta hora:

Vamos l. Qual letra voc escolheria? Notoriamente todos comeam tentando a letra "A" ou, no mximo, indo pelas vogais. Porque? Ora, pelo simples fato de que em um texto em portugus a letra "A" a letra que mais se repete! improvvel que um texto no possua uma boa quantidade de letras "A"s. Isto anlise de frequncia. Se estou tentando quebrar uma cifra monoalfabtica (onde uma letra trocou por outra), sabendo que o texto em portugus a primeira coisa que fao contar as letras. Se, e ao contar, descubro que a mais repetida o "W" provvel que o "W" est substituindo a letra "A". Onde tem "W" coloco "A" e vou brincando at o texto fazer algum sentido para mim. No caso da forca, ao colocar a letra "A" ficaria assim:

vivaolinux.com.br//impressora.php?c

4/11

21/05/2012

Introduo a criptografia [Artigo]

Vamos ver quem posta o primeiro comentrio dizendo qual a palavra! Todo o algoritmo de substituio monoalfabtico vulnervel ao ataque de anlise de frequncia. Se o texto for em ingls, sabe-se que a letra que mais se repete o "E". Mas entenda que substituio monoalfabtica no quer dizer apenas letras assim como anlise de frequncia no se aplica somente a letras que mais se repetem! Posso cifrar o arquivo binrio com uma tabela de 256 trocas, onde o byte 00000000 ser trocado por 00110110, por exemplo, e assim por diante. Ainda considerado substituio monoalfabtica. No caso, se era um executvel, posso realizar anlise de frequncia nele, descobrir quais os bytes mais presentes em um EXE tpico e usar o mesmo princpio! Fabricantes de processadores fazem isto para descobrir as instrues mais usadas em programas a fim de otimiz-las. Logo, foi para o brejo nosso algoritmo perfeito: ele perece pelo ataque de "Anlise de Freqncia". Alternativas interessantes ao longo da histria foram usadas para melhorar a cifra monoalfabtica como variar a troca para os mais frequntes. Como exemplo, a letra "A", sendo a que mais se repete, pode ser trocada por "X", por "#" ou por "*". Isto, se bem usado, evita a anlise de freqncia, mas impe alguns problemas, como o fato do alfabeto de troca ter que possuir mais smbolos que o original. Enfim, a cifra de Viginre resolveu de forma criativa este problema e ficou inquebrvel por sculos at que Babage a quebrou usando, pasmem, Anlise de freqncia (Simon). Ainda existem outras tcnicas de criptoanlise como por exemplo as colas. Chama-se de cola quando um atacante tem uma vaga ideia de trechos da mensagem. Na segunda guerra mundial os alemes pisaram na bola neste sentido, pois toda a comunicao tinha a saudao nazista, logo ao menos um trecho da mensagem era previsvel (Simon). Hoje os modernos algoritmos de cifras devem ser imunes as colas, ou seja, mesmo que eu lhe d centenas de textos cifrados e as suas centenas de textos originais correspondentes, ainda assim voc no deve ser capaz de descobrir qual chave eu usei (esta propriedade muito interessante e parece utpica, mas no ).

Simtricos ou assimtricos? O que temos at agora? mtodo: o algoritmo matemtico que faz a cifra e a decifragem. No deve ser segredo. chave: nico segredo. Uma informao que alimenta o algoritmo para cifrar ou decifrar. Quanto mais possibilidades, mais invivel o fora bruta.

Assim como uma porta de uma casa com sua fechadura que s pode ser aberta por quem tiver a chave.
vivaolinux.com.br//impressora.php?c 5/11

21/05/2012

Introduo a criptografia [Artigo]

Considerando que a fechadura a prova de criptoanlise, ou seja, a prova de "chaveiros", a nica forma de abrir a porta sem a chave correta se um chaveiro viesse com uma sacola com todas as possveis chaves para aquela fechadura e ficasse tentando at uma servir. Se forem bilhes de chaves possveis, torna invivel (isto seria um fora bruta). Mas veja que neste exemplo a mesma chave que fecha tambm abre. Existe apenas uma chave e ela serve para trancar a porta e tambm para destranc-la! Neste caso tem-se o que se chama de algoritmo simtrico, onde existe apenas uma nica chave e ela serve para cifrar e decifrar. Um problema crnico existe com os algoritmos simtricos e ele atormentou os cientistas durante muito tempo: como pode ocorrer de forma segura a troca das chaves? Se eu quero trocar uma mensagem com a pessoa B como conto ao B que usarei k=10 para cifrar a mensagem? Se tiver a oportunidade de me encontrar pessoalmente com ele, ok, converso de forma reservada e lhe conto a chave. Mas e se ele estiver distante, sem a possibilidade de um encontro pessoal? Telefono para ele? E se algum estiver com uma escuta telefnica? Envio um email? Veja, no tem como realizar esta comunicao de forma segura. Este problema atormentou muita gente. Na segunda guerra o livro dos cdigos da Enigma, com chaves dirias de um ms inteiro, era entregue em mos aos operadores de rdio. Este tinha ordens para, sob ataque, imediatamente destruir a mquina e o livro. Se os aliados tivessem acesso a este livro seriam capazes de quebrar as comunicaes de um ms inteiro (o filme "U-571 - A Batalha do Atlntico" explora este fato, onde os aliados disfaram um submarino como sendo alemo a fim de tentar capturar a Enigma). Simon conta detalhes deste fato histrico e revela que uma das primeiras formas que os aliados acharam para ler as mensagens foi subornar um oficial alemo (depois eles quebraram com colas e depois com mquinas implementadas por Alan Turing chamadas de "bombas")! Seria possvel a troca de chaves de forma segura usando um meio de comunicao inseguro? Isto se consagrou como matematicamente impossvel, exceto para os "loucos" Marin Hellman e Whitfield Diffie. Loucos pois aparentemente estavam pesquisando algo impossvel, para o qual j se havia desistido: um algoritmo de troca de chaves seguro em um meio inseguro. Este artigo ficaria muito longo se comeasse a contar a histria do famoso algoritmo Diffie-Hellman e o quanto ele revolucionou a cincia da criptografia. Cabe apenas ressaltar o raciocnio que embasou estes "loucos". Eles pensaram facilmente em um protocolo de troca de informaes sigilosas via correio. interessante para ilustrar. Imagine que quero enviar documentos sigilosos pelo correio para "P" e que eu no confio no carteiro. Colocar os documentos em uma caixa com cadeado no serve, pois como enviaria a chave do cadeado para o "P"? Pelo correio? Por teletransporte? Se no confio no meio, no adianta variar os mtodos usando este meio de transporte no qual no confio. Estamos falando de criptografia onde se leva as teorias ao extremo. Mas DH pensaram em um mtodo (eu sou o "E" enviando documentos para "P"): 1. "E" compra um cadeado em uma ferragem; 2. "E" coloca os documentos em uma caixa e coloca o seu cadeado. Pressupe-se que tanto a caixa como o cadeado so inviolveis e que a nica forma de abrir a caixa com a chave; 3. "E" envia a caixa pelo Correio. Veja que ningum poder abir, pois "E" no enviou a chave. O carteiro
vivaolinux.com.br//impressora.php?c 6/11

21/05/2012

Introduo a criptografia [Artigo]

4.

5. 6. 7.

curioso nada pode fazer; "P" recebe a caixa. Bom, "P" tambm no a pode abrir pois ele no tem a chave (surpreso?). Mas "P" ao invs de abrir, compra o seu cadeado e coloca ele tambm na caixa. A caixa agora tem DOIS cadeados: o de "E" e o de "P"; "P" devolve a caixa pelo correios ao "E"; Legal, agora nem mesmo "E" consegue abrir sua caixa. Mas ele apenas usa a sua chave para tirar o seu cadeado, mantendo o cadeado de "P"; "E" devolve a caixa para "P" que agora pode abr-la.

Observe que neste protocolo jamais houve uma troca de chaves. DH pensavam que deveria existir um princpio matemtico que reproduzisse este efeito e depois de muita pesquisa o encontraram na aritmtica modular usando nmeros primos (mais tarde se soube que eles no foram pioneiros, pois pesquisas secretas neste sentido haviam sido realizadas muitos anos antes). Prometi que no ia falar do algoritmo de Diffie-Hellman e no vou. Apenas devo dizer que ele, em sua forma original, vulnervel e sua importncia histrica mais por ter abertos portas. O famoso e ainda extremamente usado algortimo RSA baseado na mesma aritmtica modular do DH. Um algoritmo assimtrico, portanto, quando se usa uma chave para cifrar, porm, magicamente, esta chave no serve para abrir o que se cifrou. No tem espao aqui para explicar isto em termos matemticos (se algum quiser, me pea), mas o fato que tais algoritmos existem. Muitos chamam estes algoritmos de chave pblica e privada, mas o nome tcnico deles algoritmos assimtricos. Esta confuso no nome porque uma das chaves, normalmente a que serve para cifrar, tornada pblica e a outra mantida sob sigilo conhecida como chave privada (eu tenho que tomar muito cuidado quando falo disto. Sempre "chave privada". No foram poucas as vezes que me peguei falando "Se voc der a sua privada para o fulano"). Para entender os assimtricos eu uso uma excelente analogia! Voltemos aos correios e ao uso das caixas. Tem uma maneira ainda mais eficiente de receber ou enviar documentos sigilosos. Digamos que eu quero enviar um documento para "P". Bastaria isto: 1. "P" compra um cadeado e me envia ele ABERTO pelo correio. No envia a chave; 2. "E" recebe o cadeado aberto de "P" e o usa para fechar a caixa. Uma vez fechada, "E" j no tem mais condies de abr-la; 3. "E" envia a caixa com o cadeado fechado de "P"; 4. "P" a abre pois tem a chave.

Nesta analogia a chave pblica seria o cadeado aberto: ele s serve para cifrar. Estendendo a analogia, "P" poderia pedir a um fabricante de cadeados que confeccionasse milhares de cadeados com a mesma chave. O cadeado de "P" estaria em todas as agncias de correios, por exemplo. Esta a ideia. Claro que para que isto funcione o cadeado deve ser forte e a chave deve possuir muitas combinaes, seno um ataque de fora bruta seria vivel. Deve tambm ser imune a criptoanlise, ou seja, nenhum chaveiro do
vivaolinux.com.br//impressora.php?c 7/11

21/05/2012

Introduo a criptografia [Artigo]

mundo seria capaz de construir uma nova chave apenas analisando o cadeado. Voltando aos termos "informticos" a ideia do cadeado foi implementada pelo algoritmo RSA baseado na fatorao de nmeros primos. Constitui em duas chaves, uma chamada de Ke (K para "e"ncriptar) e Kd (k para "d"ecriptar). Uma complementa a outra. O que cifra-se usando Ke apenas com a Kd possvel recuperar (no vou descrever o funcionamento do RSA). Um atacante conhece Ke pois a tornei pblica. Contudo, mesmo tendo ela, ele est computacionalmente inviabilizado de calcular Kd. RSA garante isto atravs do uso de nmeros primos gigantes, hoje com tamanhos de 512 bits.

Criptografia nos dias de hoje Agora que os conceitos foram colocados, vamos aos fatos prticos. Na informtica tudo se resume a bits. Em um algoritmo de criptografia o que se mede o tamanho da chave em bits. Se uma chave possui 3 bits, ela pode ser uma dentre os seguintes valores: 000 001 010 011 100 101 110 111 Isto nos d apenas 8 possibilidades para k. Na matemtica, o nmero de possveis chaves de 2 elevando ao nmero de bits (23 = 8). Assim sendo, se um algoritmo simtrico tiver 128 bits de chave, como o caso do AES, significa que ele tem 2128 possveis chaves ou 340282366920938463463374607431768211456 (nem tente ler este nmero!). Lembra do nosso computador que testa 1 bilho de possibilidades e do fato de dispormos de 1 bilho destes para usar? Com este hardware eu levaria 170141183460469231731 segundos, j considerando a metade das tentativas (2127: lembra? ningum to azarado de acertar na ltima). Em uma calculadora, dividindo isto por 60 para ter minutos, por 60 novamente para ter horas, por 24 para ter dias e por 365 para anos, chegase a estrondosa quantia de 5.395.141.535.403 anos! pura falta de conhecimento de causa quem afirma que algoritmos simtricos de 128 bits so quebrveis por fora bruta. S mesmo Dan Brown em seu livro "Fortaleza Digital" e seu computador quntico de bilhes de bits para quebrar tal algoritmo! Se considerar o AES128, no estou dizendo que ele inquebrvel pois pode ter fraquezas explorveis por criptoanlise. Se houver ou (a) no se descobriu ou (b) quem descobriu no nos contou! O que estou afirmando ser inquebrvel quanto a fora bruta!

vivaolinux.com.br//impressora.php?c

8/11

21/05/2012

Introduo a criptografia [Artigo]

Literaturas afirmam que um algoritmos simtrico de 256 bits tem segurana eterna, pois nem todo o silcio do universo daria para construir uma mquina que o quebrasse (parenteses agora: da maneira como se constri computadores hoje em dia. Alguns cientistas vem falando da computao quntica e de como ela mudaria a maneira de fazer as coisas. Computao quntica cercada de mistrio e de exageros. O fato que j existe uma mquina com sete bits qunticos disponvel). Agora o que muitos realmente confundem quanto a fora bruta dos algoritmos assimtricos! muito, mas muito diferente! Em um simtrico, se eu tenho 8 bits de chave, tenho 256 combinaes possveis. Se pegar o caso do RSA que um assimtrico e se tiver uma chave de 8 bits, significa que o valor do N de 256 bits. Sem querer descrever o RSA aqui, posso dizer que N o resultado da multiplicao de dois nmeros primos de 4 bits. Quebrar a chave significa achar um destes nmeros. E no de 2 elevado na 4 tentativas, pois os valores 2, 4, 6, 8, 9, 10 no precisam ser testados pois no so primos! No universo de 4 bits s existem estes primos: 2, 3, 5, 7, 11,13. S! Mata-se em seis tentativas no mximo! Para algoritmos assimtricos, como no caso do RSA, o clculo do esforo matemtico no simplesmente de 2NumeroDeBits . muito, mas muito menos que isto. Exatamente por isto que os algoritmos assimtricos precisam de uma chave muito maior, hoje perto dos 1024 bits. No caso do RSA, dizer que ele de 1024 bits, significa que o valor de N de 1024 bits, logo quebrar significa encontrar um nmero primo de at 512 bits que sirva. A tem gente que se acostumou a ver o RSA de 1024 bits e sai dizendo que um AES de 128 fraco, pois s 128 bits? So coisas diferentes, meu caro!

Concluses Este artigo apenas uma introduo para, quem sabe, ser continuado em artigos futuros. Muita coisa ficou de fora, como os tipos de cifras (de bloco, de fluxo), algoritmos de HASH e at mesmo a descrio dos algoritmos. Entender o funcionamento de um RSA por exemplo muito gratificante, embora no interesse a maioria. Para ns o mais importante saber como empreg-los e no os seus princpios matemticos. Se os matemticos dizem que que invivel, que seja. A gente acredita, implementa e usa! Deve-se dizer que os algoritmos assimtricos so extremamente onerosos, ou seja, consomem muita CPU. Seu uso deve ser evitado ou, pelo menos, minimizado pois o processador agradece. Como os simtricos so absolutamente seguros e rpidos, sendo seu nico problema a troca de chave, comum usar um assimtricos apenas para trocar a chave convergindo aps para um simtrico. O protocolo SSL exatamente assim (quem est por trs do SSH e o HTTPS, dentre outros). De forma muito resumida, o que o SSL faz mais ou menos o seguinte: 1. Cliente e servidor concordam em qual algoritmo simtrico iro utilizar. Exemplo: AES128; 2. Cliente solicita a chave pblica do servidor (na prtica chama-se certificado, mas como disse, estou descrevendo de forma muito resumida);
vivaolinux.com.br//impressora.php?c 9/11

21/05/2012

Introduo a criptografia [Artigo]

3. 4. 5. 6. 7.

Cliente escolhe aleatoriamente uma chave k de sesso; Cliente cifra a chave que ele escolheu com a chave pblica do servidor; Cliente envia k cifrado para o servidor. At ai se usou o algoritmo assimtrico; Servidor recebe k cifrado, decifra com a sua chave privada; Cliente e servidor agora conversam usando o AES128 usando a chave simtrica k.

Esta a ideia, usar o oneroso algoritmo assimtrico apenas o necessrio, nada alm disto. Outras aplicaes muito populares usam vrios tipos de cifras, cada uma dentro do seu contexto, de forma que os assimtricos no esto ai para substituir os simtricos, mas sim para complement-lo. Um exemplo disto quanto a assinatura digital que emprega algoritmo assimtrico e um de HASH, igualmente para poupar esforo (pense em assinar um documento de 1GB. Rodar um assimtrico sobre 1G oneroso. Mas rodar ele sobre um HASH de 256 bits bem mais prtico).

Referncias Boa parte do que aprendi sobre criptografia eu encontrei no maravilhoso livro "O Livro dos Cdigos" de Simon Singh que, espero, no esteja mais esgotado. Ele EXCEPCIONAL. Dou f! Este livro gostoso de ler e pode ser apreciado at por quem no da rea. No exatamente um livro tcnico. Simon conta o uso da criptografia ao longo da histria, sua presena em guerras e o faz de uma maneira muito leve. A descrio matemtica de alguns algoritmos ele traz em anexos. Este livro intrigante pois toda a sua narrativa com a premissa de que criptografia segredo. Todos os grandes cdigos bem como as grandes quebras s foram reveladas ao pblico muitas dcadas depois. Isto inquietante pois deixa uma sensao de conspirao no ar, j que os maiores salrios nesta rea so pagas por agncias governamentais a pessoas completamente annimas. Quando a NSA ceifou o algoritmo Lucifer da IBM tirando 8 bits de sua chave para que virasse o DES (originalmente ele era de 64 bits, foi reduzido para 56+8 bits de paridade) muitos disseram que era pelo fato da agncia ter meios de quebrar 56 bits, mas no 64 (NSA quer dizer National Security Agency. Muitos fazem uma brincadeira com o nome dizendo que NSA quer dizer "No Such Agency - agncia inexistente). O bem humorado autor (Simon) j coloca em sua introduo que ao final ele faz muitas especulaes sobre o que j existe e poder existir. Ele diz que elas podem ser inverdades dado o sigilo da rea, mas que felizmente as nicas pessoas que podem apontar os erros no livro no o podem fazer devido ao sigilo de seus empregos e ao seu anonimato! Enfim, garanto a qualquer um uma excelente leitura. Outros livros de criptografia se destinam a entrar fundo nos conceitos matemticos e sua explorao. Em um destes livros eu encontrei uma faanha interessante para quebrar o RSA o que demonstra o quanto a criatividade insupervel! Devido a sua matemtica, algumas cifragens podem levar muito mais tempo e outras menos tempo, dependendo da natureza da mensagem a ser cifrada. Se um atacante tiver a possibilidade de medir o tempo que voc leva para cifrar o que ele quer, ele pode gerar textos bem formados e com a anlise dos tempos de resposta que voc levou para cifr-los, deduzir muitos bits da chave! Depois desta descoberta alguns algoritmos deliberadamente inserem delays aleatrios para inviabilizar qualquer anlise neste sentido. O livro que descreve isto o "Criptografia e segurana de redes", de William Stallings e disponibilizado pela editora pearson em portugus. Este livro excepcional se voc realmente quer se aprofundar muito nesta cincia (e prepare-se para uma enxurrada de funes matemticas, familiarizao com termos como transformada de Fourier ou logaritmos discretos - o livro bem pesado).
vivaolinux.com.br//impressora.php?c 10/11

21/05/2012

Introduo a criptografia [Artigo]

Caso se interessem por um algoritmo de troca monoalfabtica, tem uma implementao minha em C disponvel em gravatai.ulbra.tche.br/~elgio/disciplinas/?DISC=outras&MAT=VOL (este algoritmo eu escrevi atendendo pedidos ao tpico Criptografia em C). Na mesma pgina tambm tem o cdigo em PHP para implementar um RSA de 32 bits, mas como eu no expliquei aqui como o mesmo funciona, torna-se sem sentido. Tambm escrevi e postei aqui no VOL um artigo sobre senhas em Linux, explicando como a mesma gerada utilizando HASH. Ele pode ser obtido em Armazenamento de senhas no Linux. Outro artigo de minha autoria descreve os algoritmos simtricos de bloco e de fluxo, que pode ser acessado em Criptografia chave simtrica de bloco e de fluxo. Outros artigos interessantes aqui no VOL merecem serem citados: Matheus Santana Lima escreveu em seu artigo Os segredos da criptografia com o Gcipher como usar a ferramenta Gcipher, mas como todo bom artigo, enriqueceu muito o mesmo com introdues e estrias da segunda guerra mundial, inclusive com fotos da Enigma. Ele no relata em seu artigo, mas suspeito que o Matheus leu o livro do Simon! talo Pereira de Brito fez uma boa introduo aos algoritmos simtricos, assimtricos e de hash (que ele chamou no artigo de "uma via") em seu artigo Uma breve abordagem sobre Criptografia, de 2006. Rodrigo Gomes, em seu artigo Conceitos de criptografia com chave simtrica e assimtrica de 2004, define bem os termos de confiabilidade, integridade e no repdio, todos desejveis em um protocolo de criptografia. Ele tambm destaca a necessidade das chaves assimtricas. Por fim, um usurio annimo que removeu o seu perfil, fez um interessante relado do que seria a computao quntica em Criptografia quntica, embora o artigo seja uma cpia literal de um captulo da quarta edio do livro de Redes do Tanembaum. O livro do Simon tambm muito bom na definio da computao quntica.

http://www.vivaolinux.com.br/artigo/Introducao-a-criptografia Voltar para o site

vivaolinux.com.br//impressora.php?c

11/11