Routo Terada, Phd Departamento de Ciéncia da Gomputacao da USP Seguranc¢a de dados Criptografia em redes de computador 2" edicdo revista e ampliadaSeguranca de dados criptografa em redes de computador 1512008 Routo Terada 1" reimpressio = 2011 Eeaitora Edigard Blacher ida Blucher ‘Rua Pedroso Alvarenga, 1245, ‘andar (04531-012. Sao Paulo SP ral ‘Terss 11 30785366 editora@bluchercom br ‘wbluchercom br £ proibida a reproducio total ou parcial por qual ‘quer melos, sem autorizagao escta da Eltora “Todos os direitos reservados pela Eitora Edgard ldcher Lda, FICHA CATALOGRAFICA ‘Terada, Route ‘Seguranga de dados: crptografia em cedes de computador - S30 Paulo: Blucher, 2008, IsQ 978.85.212.06398 1. Computadores ~Seguranca 2. Criptografia, 3. Dados” Protege |. Titulo 08-7846 c00-005.82 indices para catlogo sstematico: Tcriptograa: Dados: Seguranca : Computa ores Processamento de dados ‘005.82Prefécio da segunda edicéo Nos tltimos cinco anos as dreas de criptografia e seguranca de dados se de- senvolveram répida e substancialmente, tanto cientifica como tecnologicamente, com aplicagées diversas em varios segmentos industriais, principalmente em telecomunicagoes Nesta edigdo foram atualizados e expandidos os Capftulos 3, 4 e 7, ¢ os Apén- dices A, Ce H. A eventual errata ¢ exercicios esto disponiveis no URL: [Link] rtfivrocripto/ Prefacio da primeira edi¢éo Nos tiltimos anos tem havido um avanco extraordindrio na disseminagao e popularizagao da rede Internet, e no advento das chamadas “lojas virtuais” para co- mércio pela Internet, e das “home-bankings” que possibilitam transacdes bancarias através de uma senha (ou chave) de conhecimento apenas da pessoa autorizada. HA também diversos servicos de noticias e informagdes econémicas, sociais, artis- ticas, médicas, técnico-cientificas, etc. Tais servigos oferecem conforto, economia e rapidez em tarefas outrora cansativas, custosas e demoradas. Essa democratizagéo da informacao motivou a cunhagem da expresso Sociedade da Informagao para designar a sociedade da década de 90. Por outro lado, com a disseminacao e a popularizacao da Internet, a protegéo da privacidade se tornou extremamente importante para cada cidadao, pois os seus dados pessoais trafegam na Internet e podem ser “grampeados”. Criptografia 6 a chave que permite solucionar tecnologicamente este problema. Para tornar seguro 0 comércio eletrénico ha necessidade de se ter criptografia de alto nivel, tanto de seguranga como de eficiéncia, nas varias plataformas. Criptossistemas sao algoritmos para “esconder” informagGes sigilosas das pes- soas desautorizadas a lé-las, isto é, das pessoas que néo conhecem a chamada cha- ve secreta de criptografia Até 0 fim da década de 70, todos os criptossistemas eram secretos, princi- palmente aqueles utilizados pela diplomacia e pelas forcas armadas de cada pais. Mas recentemente a seguranga de sistemas criptogréficos se baseia apenas no co- nhecimento da chave secreta; os algoritmos sao publicados principalmente nas reunides técnicas anuais, como as renomadas conferéncias CRYPTO e EuroCRYPT. que congregam cientistas, engenheiros, ususrios civis e militares internacionais, ha mais de vinte anos.6 PREFACIO Mais recentemente a necessidade de know-how e desenvolvimento de cripto- grafia se tornou mais critica com as possibilidades de falsificagbes e fraudes que sao facilitadas com a disseminacao e popularizagao da telefonia celular digital Padrées de criptografia esto sendo desenvolvidos em varios paises. Nos EUA, o AES — Advanced Encryption Standard — foi desenvolvido para substituir 0 DES. Na Europa foram padronizados varios esquemas de assinatura ¢ integridade criptogréficas com 0 nome NESSIE. O governo japonés padronizou a criptografia na administracdo federal implantada em 2004 Objetivos Os objetivos deste livro sao de apresentar os problemas e de fornecer as res- pectivas solugdes praticas em seguranca de redes de computador. Sao: 1. AplicagGes e técnicas de protecdo de informacao sigilosa. 2, Autenticacdo da origem e destino de documentos eletronicos: assinatura eletrénica, 3. Técnicas de identificacao de usuarios em redes de computador: protegio de cartao magnético de identificagao ou senha. 4, Protegdo de integridade de banco de dados. 5. Detecco e controle de presenca de virus eletronico. Os algoritmos DES RSA, largamente utilizados em sistemas comerciais, so detalhados e analisados. Outros criptossistemas de chave secreta importantes sio apresentados: IDEA, SAFER, RC5, RC6, FEAL. Além do RSA, sdo descritos outros algoritmos de chave ptiblica: Rabin, ElGamal, MH, G@, Schnorr e Curvas Elipticas. Ademais sao apresentados algorit mos de hashing como MD4, MD5, SHA, e o algo- ritmo de compactacao L277. Nos apéndices ha informagoes sobre os sistemas PGP, TLS, e um programa RSA na linguagem Java. Os conceitos fundamentais de Teoria da Informagao e Teoria dos Nuimeros sao fornecidos para tornar o livro auto-suficiente, Organizacao do livro Capitulo 1 apresenta as motivagdes e definigdes dos conceitos basicos, e © Capitulo 2, os conceitos fundamentais de Teoria de Informagio, como entropia. Capitulo 3 apresenta os principais algoritmos de chave secreta, como o DES. No Capftulo 4 tem-se os principais algoritmos de chave ptiblica, como 0 RSA. OPREFACIO 7 Capitulo 5 apresenta algoritmos para autenticaco de informacao, como senha, € 0 Capitulo 6, os algoritmos para assinar criptograficamente alguma informagao. No Capitulo 7 vemos as fungdes espalhamento, como o SHA. No Apéndice B apresentamos os conceitos bisicos de Algebra. No Apéndice C vemos os conceitos e algoritmos fundamentais da Teoria dos Niimeros. No Apéndice D é apresentado um algoritmo de compressao muito eficiente, 0 LZ77, muito titil para uso combinado com algoritmos criptograficos. O software popular PGP — Pretty Good Privacy — muito usado na Internet para troca de e-mail — é apresentado de forma resumida no Apéndice E. O Apéndice F resume a biblioteca de rotinas chamada TLS — Transport Layer Socket. O Apéndice G lista uma imple- mentacao do algoritmo RSA em Java. A quem se destina Estelivro éparaestudantese profissionaisde Informatica, deTelecomunicacoes e de Engenharia de Computacao. Em particular, destina-se a: + Usudrios de sistemas criptogréficos que queiram comparar as necess dades com as solugées existentes na area de seguranga de dados. * Projetistas de sistemas de seguranga de informacao em redes de compu- tagao distribuida em banco de dados. Como usar o livro Este livro tem sido usado em cursos semestrais de fim de graduagao ou infcio de pés-graduacao, na USP. Tem sido usado também em cursos intensivos de cerca de 40 horas, para profissionais da 4rea de seguranga de redes e telecomunicagoes. Os exercicios so enunciados logo apés os conceitos relevantes. As referéncias bi- bliogréficas sdo fornecidas no corpo do texto. E apropriado também para estudo auténomo ou para consultas. Agradecimentos Agradeco ao Departamento de Ciéncia de Computagao do Instituto de Mate- mética e Estatistica da USP por possibilitar um ambiente propicio para desenvolver pesquisa e ensino. Agradego & Editora Edgard Blucher pela eficiéncia. Ea Don Knuth pelo desenvolvimento do sistema TEXutilizado.Contesdo 1 _Introdugao e motivagdes eee 1.1 Problemas de sigilo e autenticidade..... 1.2. Organizagao do texto ... 1.3. Oque ¢ criptografia’ . 13.1 Giffra de Cé8aP oom 13.2 Criptografiae decriptografia.. 13.3 Quebrae ataque em criptografia 1.3.4 Criptografia aberta .. . 1.3.5 Como provar que um algoritmo criptografico € seguro? O caso ABS... 21 14 Criptandlise e seus tipos 22, 14.1 Freqiéncia de letras na lingua — vulnerabilidade. 25 Substituigao simples. 25 Cifra de Vigenére. 26 : 27 28 Composigéo. 28 2 Teoria da informagio — Entropia .. 2.1 Difusdo e confusio 22 23 23.1 Chaves igualmente provaveis 2.32 Condigao necesséria e suficiente para seguranca perfeita. 36 23.3 One-time-pad 2.4 Criptossistema aleatrio. 24.1 Redundancia . 242 Distancia de unicidade... 2.4.3 Exemplo de redundaneia e distancia de unicidade- 3 Criptografia de chave secreta... 3.1 Data Bneryption Standard —DES ... Esquema geral do DES... ‘Uma iteracaio DES. A fungio de iteragao f,, (D) Gerago de subchaves K, Deserigdo das S-boxes.... Decriptografia DES ...0. ‘Tabelas DES... Quebrar o DES?, Exercicio. 32. International Data Encryption Algorithm — IDEA 32.1 Astrés operagdes basicas do IDEA. : Geragao das subehaves... Uma iteragao (rownd) do IDEA. Decriptografia pelo algoritmo IDEA.10 CONTEUDO 3.2.5 Dados paratteste... a seen seven TO B26 EXETCICIO. nw nonun 70 38. Secure And Fast Encryption Routine — SAPER K-64... 7 3.3.1 Descrigdo de uma iteragao,.. oT 38.2 Descrigho da transformagao final. soe TB 3.3.3 Descrigdo da geragao das subchaves . son TB 3.3.4 Descrigao do algoritmo inverso do SAFER... soe TB 3.3.5 _ Ilustragao do algoritmo SAFER. 74 BA ROB orca st se TB 34.1 Parametros do RCS... so TB B42 Operagdes bésicas do RGS.. TB 34.3 Algoritmo de geragao de subchaves RCS. 8 344 Algoritmo de criptografia RCS... 8 3.4.5 Algoritmo de decriptografia RCS... 78 3.4.6 Dados para testes do RB... “79 BB ROB scrnnsnninnnsnensnsnns 79 3.5.1 Parametros do RC6..... 7 sve TO 3.5.2 Operagdes basicas do RC6.......... so TD 3.5.3 Algoritmo de criptografia RC6....... sesnssnnsnnan vs sssesseersneees BO 3.5.4 Decriptografia RC6. al 35.5 Geracio de subchaves RC6. 82 35.6 Dados para teste do RC6 . 2.83 3.6 Fast Encryption Algorithm — FEAL....... 85 3.7 Advanced Encryption Standard — AES... 89 3.7.1 Esquema geral do AES-Rijndael............ seansonnsnvansen pevseeeee OL 3.7.2 SubBytes (Bloco) 4 37.3 ShiftRows (Bloco) 99 3.7.4 MixColumns (Bloco) 100 3.7.5 AddRoundKey (Bloco, ExpandedKey) 104 37.6 Geragio de subchaves (key schedule)... 104 3.7.7 Valores de teste da gerago de SubChaVES ...scnssnsnnnnnnnnans, 109 3.7.8 Valores de teste do AES. 10 3.7.9 Inversa do AES-Rijndael 10 3.7.10 Criptandlise do Rijndael. 2 37.11 ABS simplificado 113 3.8 Criptandlise diferencial — CD 113 3.9 Criptandlise linear — CL. 4 3.10 Fortalecimento contra CDe Cl. 14 3.11 Modos de operagao. 115 3.11.1 Modo ECB — Electronic Code Book Mode 116 3.112 Modo CBC —Cipher Block Chaining Mode 116 3.11.3 Modo CFB —s-Cipher Feedback Mode. 8 3.114 Modo OFB—s-Output Feedback Mode. 120 3.11.5 Modo Contador (Counter Mode) 122 4 Criptografia de chave piblica: 4.1 Problema do logaritmo discretoCONTEUDO lL 4.2. Diffie-Hellman, . sw BT 42.1 Ataque ativo do tipo ‘an-in-the-midale’ : 128 4.2.2 Protocolo Diffie-Hellman modificado ....s0u:nnnnnonnnnnnnsn 129 4.2.3 Um exemplo do protocolo modificado «nmin innnnennnnnnsnee 129 43° Algoritmo RSA. : : — 129 43.1 Caleulo de um par de chaves... 130 43.2 Algoritmo de criptografia e decriptogratia.. vom 130 ‘Autenticagdio do receptor... soo IB Criptandiise do RSA —“caleanhar-de-aquiles” 131 Autenticagao do remetente.... 138 Verificacao de integridade — “Cheque” eletrénico .. 135 Exemplo numérico maior de RSA ....nennee 135 Demonstragao da inversa do algoritmo RSA... 135 Algoritmo de exponenciagao modular 136 ‘Seguranga do RSA — fatoragao e outras formas de recaleular a chave secreta do RSA... — Como calcular primos longos..... EXerefCI08 ser 444 Algoritmo Rabin de criptografia soo 136 139 46 ses M7 44.1 Célculo de um par de chaves 14s. 4.4.2 Algoritmo de criptografia. us. 44.3 Algoritmo de decriptografia. soon 48 ‘Autenticagiio do receptor soo 149 Criptandlise do algoritmo, 149 Exemplo do algoritmo. 149 4.5. O Algoritmo ElGamal de chave publica. 150 4.5.1 Algoritmo de criptografia 150 4.52 Algoritmo de decriptografia. 151 453 Umexemplo numérico. 151 4.54 Seguranca do Algoritmo ElGamal.... 151 455 Observacoes. sn sense UBB, 45.6 Demonstragao da funcao inversa 152 4.6 Problema do logaritmo discreto geral 152 4.7 O Algoritmo ElGamal geral 153 4.7.1 Algoritmo de criptografia. 153 4.7.2 Algoritmo de decriptografia. 154 4.7.3. Exemplos de grupos G para EiGamal 154 4.7.4 Corpo finito de Galois. 154 48 Curvas elipticas 160 48.1 Problema do logaritmo discreto sobre curvas elipticas — PLD-CE 167 482 Criptossistema ElGamal sobre curva eliptica 168 4.83 Criptossistema Menezes-Vanstone. 169 484 Curvas elipticas sobre GF (2m) 171 4.85 Algoritmo ElGamal sobre curvas elipticas em Corpo Finito de Galois... 172 486 Curvas elipticas na web, 173 4.9 Algoritmo MH 173 4.9.1 Calculo de um par de chaves MH 17412 4.10 411 51 52 5a BA 61 62 63 64 CONTEUDO 4.9.2 Algoritmo de criptografia MH............ hoseneenen Zs 174 4.9.3 Algoritmo de decriptografia MH........ 174 4.9.4 Algoritmo auxiliar para a decriptografia MH ... 176 4.9.5 Autenticagao do receptor..... vs 176 4.9.6 Criptandlise do Algoritmo MH.......... 176 4.9.7 Exemplo do Algoritmo MH...... AIT 4.9.8 Algoritmo MH iterado 178 Smartcard. ses 178 Exercicios .... 179 Autenticagio e identificagio... sneeneenee Jogo de cara-e-coroa por telefone..... Protocolo de identificagao Feige, Fiat e Shamir. 52.1 Seno houvesse desafio. 5.2.2 Primeira forma de personificar Alice ..... 52.3 Segunda forma de personificar Alice ... 5.2.4 _Informagao secreta revelada por Alice... 52.5 Como generalzar para mais de um segredo para Alice 187 52.6 Smart Cards. sens 188 Protocolo de identificagao GQ 188 5.3.1 Escolha dos parametros, 188, 5.3.2 Escolha dos pardmetros para cada usuario .. 188 5.3.3 Protocolo de identificagao.... o 199 53.4 Personificagto.... 190 535 Exemplo... — — 190 Protocolo de identificagdo Schnorr 191 54.1 Escolha dos parametros. 192, 5.4.2 Escolha dos pardmetros para cada usuério 192, 54.3 Protocolo de identificagio 192, 54.4 Um exemplo numérico....ncnnninnnnnnnnnn seonnrnenee 198 54.5 Personificagao.... 194 Assinatura criptografica. “Assinatura RSA. Algoritmo Rabin de assinatura 197 62.1 Propriedades preliminares, 197 62.2 Pardmetros da Alice. 198 62.3 Assinatura da Alice sobre uma mensagem m. 198 62.4 Verificagdo da assinatura 198 62.5 Esquema de assinatura Rabin falsificavel. 199 Assinatura Feige-Fiat-Shamir. 200 6.3.1 Criago da assinatura por Alice 201 63.2. Verificagao da assinatura 202, 6.3.3 Falsificacio de uma assinatura. 202, Esquema de assinatura GQ. 203 64.1 Escolha dos parametros, 203 64.2 Criagdo da assinatura GQ. 204CONTEUDO 13 6.4.3 Verificagao da assinatura GQ. renee 6.4.4 Probabilidade de falsificagio de uma assinatura 6.5. 0 Algoritmo BlGamal de assinatura Algoritmo para assinar : Algoritmo para verifcar assinatura (y, 2) Observacoes: ‘Um exemplo numérico .....csccsessesssenenneeincenneein Demonstragao da verifcagao 6.5.6 Sequranga da assinatura ElGamal 6.6 O Algoritmo DSS — Digital Signature Standard. Algoritmo para Alice assinar 2 Z, Algoritmo para Beto verificar a assinatura Observagies...... Seguranga.. Um exemplo numérico Demonstragao da verificagdo da assinatura........... 6.7 Algoritmo Schnorr de assinatura. 67.1 Algoritmo para assinar 6.7.2 Algoritmo para verificar uma assinatura. 6773 Demonstragio da verificagao da assinatura 6.7.4 Um exemplo numérico. 6.7.5 Exercicios......... 6.8 Assinatura criptografica na Web 7 Fungdes espathamentto swssssnniensnensennntennsee 7.1 Método Merkle-Damgird 7.2 Ataque pelo Paradoxo de Aniversério 7.21 Paradoxo de Aniversétio.. 7.2.2 Algoritmo de Ataque pela Raiz Quadrada... 7.3 Little-endian e big-endian. TA Algoritmo MD4 onsen 74.1 Primeiro passo de MD4 7.42 Segundo passo de MD4 7.43. Terceiro passo de MD4. 74.4 Hist6rico da criptandlise do MD4 7.5 Algoritmo MD5 7.5.1 Primeiro passo de MDB... 7.5.2 Segundo passo de MDS. 7.5.3. Terceiro passo de MDS. 7.5.4 Quarto paso de MDB .....nnmnnnnnnennnnsn 7.5.5. Hist6rico da criptandlise do MD5, 7.6 Algoritmo SHA — Secure Hash Algorithm. 7.6.1 Histérico da criptandlise do SHA. 7.7 Futuro da fungées de espalhamento.... A. As tabelas SBOX ..scmissnnnensse14 a moo oo Conceitos fundamentais. Bl Grupo B2 — Anel B3 Corpo BA —_Notacio 00 e 00... B5 — Complexidade de algoritmo. Elementos de Teoria dos Nimeros. C1 Resto de divisao e médulo ©2 Soma produto mod m 3 Ntimeros primos C4 Algoritmo de Buclides e mde. C.4.1_ Exemplo de execugao do Algoritmo de Euclides.. C42 Algoritmo de Euctides. C5 Algoritmo de Buctides estendido G6 — Céleulo de inversa multiplicativa mod m. C7 Teorema Chinés do Resto —TCR. C71 Aplicagao do TCR em irmplementagao do RSA C8 — Rafzes quadradas de 1 mod n. C9 Z,eZ," C10. Fungio F de Euler. C11 Gerador ou elemento primitive de 2,” C12 Residue quadratico mod n. C13 Simbolo de Legendre .14 _Simboto de Jacobi 14.1 Caso particular de a pa, p = q=3 mod 4 C142 Exercicios 14.3 Pseudoprimos. C15. Teorema de Euler €.16 Céleulo de quatro raizes quadradas. CAT Fatoragao dem C18 Algoritmo de exponenciacéo €.18.1 Bxercicios €.19 Corpo Finito deGalois €.19.1 Soma e produto em GF(2") ©1922 Base de espagovetrial pare GF(2") C193. Exercicios “ os Algoritmo de compressio de dados L277 279 D.1 Algoritmo L277 em processo de descompressio D2 — Conclusoes. Pretty Good Privacy — PGP. ‘Transport Layer Socket — TLS (SSL) Implementagéo do RSA em JAVA... Padronizacées de criptografia eletrénica e IACR... CONTEUDOCapitulo 1 Introdugao e motivagoes A habilidade humana ndo pode inventar cédigo que a habili- dade humana néo possa decifrar. Edgar A. Poe (1809-1849) Voce consegue ir mais longe com uma palavra gentil e wna arma de fogo do que vocé consegue 86 com uma palavra gentil. Willy Sutton, assaltante de banco, 1994 Na pritica, a eficécia de uma protegao depende muito do modo como ela € usada; 0 melhor cofre do mundo é intitil se ninguém se lembrar de fechar a sua porta. Computer at Risk, 1991 Drama ¢ conflito so inerentes em criptografia, que, de fato, pode ser definida como ciéncia de transmissdo e gestao de infor- magéo na presenga de um adversério. A mentalidade de “espido versus espido” de competicdo e rivalidade constantes € estendida para a cultura disciptinar da drea, Bla pode se tornar excessi- va ~ e @s vezes até infantil — mas ela explica também em parte porque pode ser téo divertido pesquisar cientificamente a crip- tografia. Neal Koblitz, 2007 Nos tltimos dez anos tem havido um avango extraordinario na dissemi- nagao ¢ popularizagdo da rede Internet e 0 advento das chamadas “lojas virtuais” para coméreio pela Internet, e das “home-bankings” que possibili- tam transagoes bancérias através de uma senha (ou chave) de conhecimento apenas da pessoa autorizada, Ha também diversos servicos de noticias e infor- magées econdmicas, sociais, artisticas, médicas, técnico-cientfficas, etc. Tais servigos oferecem conforto, economia e rapidez em tarefas outrora cansativas, custosas e demoradas. Essa democratizagao da informacao motivou a cu- 1516 CAPITULO 1. INTRODUGAO E MOTIVACOES: nhagem da expressio Sociedade da Informagio para designar a sociedade da década de 90. Sistemas de comnnicagio como a Internet so controlados por computa- dores em rede, pelos quais a informagao trafega desde a origem onde ela est armazenada ou foi criada até o destino onde o solicitante da informagéo se encontra, Muitas vezes hé mais de um computador que repassa a informacao entre a origem e o destino, principalmente quando estao geograficamente dis- tantes. Na ilustragio abaixo vamos chamar a pessoa usando 0 computador origem de Alice, e a pessoa usando 0 computador destino de Beto. Alter- nativamente tanto Alice como Beto podem ser um programa de computador automatizando algum servico de informacao. O computador X 6, por e- xemplo, o provedor Internet da Alice, ¢ Y 0 provedor do Beto. A linha de comunicagio pode ser, por exemplo, uma linha telefonica. Capac Goat do ite hee aisen) asi) nguactr x |} 4] aur ¥ iene) ae rosin) 1.1 Problemas de sigilo e autenticidade Diversas preocupagées muito importantes existem neste cendrio: 1. Como esconder informacées sigilosas, como o niimero de cartio de crédito da Alice, das pessoas que controlam as linhas de comunicagdo e os computadores intermedirios como X e Y; ou seja, Alice deseja que s6 Beto consiga ler a informagao enviada — isto é chamado de autenticagdio do destino; 2. Como evitar que um mal-intencionado leia ¢ altere parte da informagio transitando na linha de comunicagio antes de chegar ao Beto, ou seja, Beto gostaria de detectar se alguma alteracao parcial foi feita na linha ~ isto é chamado de detecgio de integridade de informagéo. Por exemplo, © nome de uma pessoa 6 alterado,1.1, PROBLEMAS DE SIGILO E AUTENTICIDADE qT -— acer ca ‘Mil-imencionad | ‘Computactor do LJ ‘Beto cm ‘(destine) i eles : ernie) fini de oar (gre) 3. Uma variagio do problema anterior 6 como evitar que uma falsa Alice envie informagao para Beto, on seja, Beto deseja ter certeza de que foi a Alice verdadeira que enviou a informagao — isto 6 chamado autenticagdo da origem. Por exemplo, o miimero de cartio de crédito que Beto recebe 6 mesmo da Alice? Compuadd Capua do ie ao (eigen) sino) —- Ciampi X Conpucer ¥ (eos) ae (rosa) 4, Como evitar que alguma pessoa desautorizada leia as informagoes ja en- viadas ¢ armazenadas no computador do Beto. Por exemplo, o cadastro de cartées de crédito dos clientes de Beto. Temaaials Gogh eso) ¥ CampuitrX§ |+} apres ¥ (res) pe (wove) 5. Uma variagao do problema anterior 6 como evitar que alguma pessoa desautorizada leia e altere as informagées jé enviadas e armazenadas no computador do Beto ~ isto ¢ chamado também de detecgo de in- tegridade de informagéo . Veremos que estes problemas podem ser resolvidos por criptografia. O problema (1) nos Capitulos 3 e 4, 0 (2) nos Capitulos 4, 5 e 6, 0 (3) nos Capitulos 4 e 6, 0 (4) nos Capitulos 3 e 4, 0 (5) nos Capitulos 3 e 4.18 CAPITULO 1. INTRODUGAO E MOTIVAGOES: 1.2 Organizagao do texto O Capitulo 1 apresenta as motivagées e definigoes dos conceitos bésicos e © Capitulo 2, os conceitos fundamentais de Teoria de Informagio, como en- tropia. O Capitulo 3 apresenta os principais algoritmos de chave secreta, como 0 DES. No Capitulo 4 tem-se os principais algoritmos de chave pibli- ca, como 0 RSA. O Capitulo 5 apresenta algoritmos para autenticagio de informagao, como senha, ¢ o Capitulo 6 os algoritmos para assinar criptografi- camente alguma informagio. No Capitulo 7 vemos as fungdes espalhamento, como 0 SHA. No Apéndice B apresentamos os conceitos bésicos de Algebra. No Apéndi- ce C vemos os conceitos ¢ algoritmos fundamentais da Teoria dos Niimeros. No Apéndice D ¢ apresentado um algoritmo de compressio muito eficiente, LZ77, muito titil para uso combinado com algoritmos criptogréficos. O software popular PGP - Pretty Good Privacy — muito usado na Internet para troca de email 6 apresentado de forma resumida no Apéndice E. O Apéndice F resume a biblioteca de rotinas chamada TLS ~ Transport Layer Socket. O Apéndice G lista uma implementagao do algoritmo RSA em Java. 1.3. O que é criptografia? Algoritmos criptograficos basicamente objetivam “esconder” informagées sigi- losas de qualquer pessoa desautorizada a Ié-las, isto é de qualquer pessoa que ndo conheca a chamada chave secreta de criptografia, Tal pessoa in- trusa ou mal-intencionada sera chamada de Carlos. Eventualmente Carlos ser o nome ficticio de um especialista em criptografia, cujo objetivo é anali- sar 0 algoritmo inventado por outra pessoa e, sem conhecer a chave, aplica os seus conhecimentos avancados para descobrir alguma vulnerabilidade do algoritmo; ¢ entao ele 6 qualificado de criptanalista. 1.3.1 Cifra de César Para ilustrar 0 conceito de criptografia, veremos a seguir um exemplo sim- ples e clissico de algoritmo criptogréfico chamado Cifra de César (do Im- pério Romano). Criptografias elementares sio chamadas de cifras. Vamos supor que Alice e Beto combinam previamente que usardo apenas as 26 le- tras maitisculas do alfabeto. A Cifra de César consiste em substituir cada1.3. O QUE E CRIPTOGRAFIA? 19 letra da primeira linha na tabela abaixo pela letra na segunda linha. Assim, a palavra SATURNO ¢ criptografada para ZHABYUV, ficando ininteligivel para um criptanalista Carlos que consiga capté-la. hr [s [ele fof [olr[e[e[s [> A segunda linha na tabela acima é apenas o alfabeto deslocado para a direita de 19 posigdes de forma circular, isto 6 apés a letra G na segunda linha as letras seguintes continuam no extremo esquerdo como se o alfabeto estivesse escrito sobre uma fita circular. A chave neste caso 6 o niimero 19. Beto ao receber 0 cédigo ZHABYUV vai utilizar este valor 19 para obter a tabela acima e recuperar a palavra original SATURNO. sar sari Congr —— cos ay | lo wm —_t (Compute X BABY Computador Y won) [—— ——) “eee endemic one crs Por este exemplo, nota-se claramente que a chave 19 deve ser: 1. previamente combinada entre Alice e Beto através de um meio sigiloso; 2. e mantida em segredo para que um criptanalista Carlos nio consiga recuperar a palavra original. Por estas duas razdes, este tipo de algoritmo ¢ chamado de criptografia de chave secreta, (Ha também um outro tipo de eriptografia chamada de chave puiblica que permite criar assinatura criptografica.)