Click here to load reader

Criptologia: uma abordagem historica e matematica

  • View
    16

  • Download
    1

Embed Size (px)

DESCRIPTION

Abordagem de uma técnica de criptologia

Text of Criptologia: uma abordagem historica e matematica

  • UNIVERSIDADE FEDERAL DE SAO CARLOS

    CENTRO DE CIENCIAS EXATAS E DE TECNOLOGIA

    LICENCIATURA EM MATEMATICA

    Criptologia: uma abordagem historica e matematica

    Diego Felipe Silveira Seabra

    Sao Carlos SP

    Perodo: marco a novembro de 2010

  • UNIVERSIDADE FEDERAL DE SAO CARLOS

    CENTRO DE CIENCIAS EXATAS E DE TECNOLOGIA

    LICENCIATURA EM MATEMATICA

    Trabalho de Conclusao de Curso A

    e Trabalho de Conclusao de Curso B

    Criptologia: uma abordagem historica e matematica

    Diego Felipe Silveira Seabra, R.A. 282421

    Dissertacao apresentada ao

    Departamento de Matematica

    da UFSCar como parte dos

    requisitos para a obtencao

    do ttulo de Licenciado em

    Matematica.

    Orientador: Prof. Dr. Joao Carlos Vieira Sampaio

    Sao Carlos SP

    marco a novembro de 2010

  • A` minha famlia e ao meu padrinho

    Jose Maria.

  • Resumo

    A historia dos codigos e seus decifradores em suas eternas batalhas acompanha a

    propria historia humana. Ao longo do tempo, codigos, cifras e mensagens secretas

    estiveram presentes nas mais diversas situacoes onde desempenharam papel essencial

    decidindo resultados de guerras e o destino de pessoas e civilizacoes inteiras.

    Nos mais diversos setores sociais e tipos de atividades humanas, a crip-

    tografia interferiu diretamente. Em assuntos polticos e diplomaticos, atividades

    civis ou militares, onde se fez necessaria a transmissao de informacoes de maneira

    segura e secreta ela esteve presente e a consciencia das consequencias de uma men-

    sagem interceptada por maos erradas fez com que as nacoes criassem departamentos

    especficos para a criacao e implementacao de codigos cada vez mais seguros.

    Nesse contexto a ciencia da Criptologia foi colocada num patamar de grande

    importancia e muita atencao lhe foi dispensada no sentido em que fosse cada vez

    mais desenvolvida e implementada.

    Se de um lado temos os criadores de codigos, do outro estao os decifradores

    em suas arduas e incessantes batalhas por organizar o aparente caos e encontrar o

    verdadeiro significado por tras de sequencias misteriosas de letras e smbolos. E uma

    batalha intelectual constante e contnua cujos resultados interferem diretamente no

    dia-a-dia das pessoas e em todo o contexto social.

    Conforme o ttulo deste trabalho, atraves de uma abordagem historica e

    matematica da Criptologia farei uma viagem pela historia dos codigos e sua in-

    fluencia na sociedade humana bem como um estudo mais detalhado da matematica

    4

  • 5envolvida na criacao e quebra de codigos e cifras. Serao utilizados resultados da

    Teoria dos Numeros e outros que eventualmente sejam necessarios.

    Neste trabalho, a enfase e dada a` parte historica e ao conteudo matematico

    que sera necessario ao estudo mais detalhado de topicos da Criptologia, particular-

    mente o sistema RSA, foco do trabalho de graduacao B.

    Palavras-chave: criptologia, criptografia, aritmetica modulo m, funcao

    de Euler.

  • Sumario

    I Trabalho de Conclusao de Curso A 10

    1 Um pouco de historia 13

    1.1 A evolucao da escrita secreta . . . . . . . . . . . . . . . . . . . . . . . 13

    1.2 Ramos da criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    1.2.1 Transposicao . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    1.2.2 Substituicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

    1.2.3 Cifras de substituicao atraves de aritmetica modular . . . . . 19

    1.3 Os criptoanalistas arabes . . . . . . . . . . . . . . . . . . . . . . . . . 24

    1.4 Criptoanalise de um texto cifrado . . . . . . . . . . . . . . . . . . . . 27

    2 Elementos da teoria dos numeros 34

    2.1 Inteiros modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    2.2 Inteiros modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

    3 A funcao de Euler 44

    II Trabalho de Conclusao de Curso B 51

    4 A criptografia de chave publica 54

    6

  • 74.1 O nascimento da criptografia de chave publica . . . . . . . . . . . . . 56

    5 Teoria dos numeros para RSA 58

    5.0.1 Algoritmo Euclidiano para o calculo de mdc . . . . . . . . . . 60

    5.0.2 Calculando inteiros r e s tais que mdc(a, b) = ra+ sb . . . . . 61

    5.1 Uma aplicacao interessante . . . . . . . . . . . . . . . . . . . . . . . . 62

    5.2 Implementacao de RSA . . . . . . . . . . . . . . . . . . . . . . . . . . 63

    5.3 Exemplo numerico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

    6 Metodos de fatoracao 70

    6.1 Teste de fatoracao de Fermat . . . . . . . . . . . . . . . . . . . . . . 71

    6.2 Metodo Pollard p 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

  • Lista de Figuras

    1.1 Primeiro aparelho criptografico militar, o citale espartano. . . . . . . 17

    1.2 O relacionamento entre algoritmo e chave. . . . . . . . . . . . . . . . 18

    1.3 Tabela de frequencias baseada em passagens extradas de jornais e ro-

    mances cuja amostragem consistia em 100.362 caracteres do alfabeto.

    Tabela compilada por H. Beker e F. Piper. . . . . . . . . . . . . . . . 26

    1.4 Analise de frequencia da mensagem cifrada. . . . . . . . . . . . . . . 28

    1.5 Dados referentes ao comportamento das letras em estudo. . . . . . . . 29

    1.6 Dados referentes a` letra O. . . . . . . . . . . . . . . . . . . . . . . . . 31

    1.7 Nosso alfabeto cifrado parcial. . . . . . . . . . . . . . . . . . . . . . . 32

    1.8 Alfabeto cifrado completo. . . . . . . . . . . . . . . . . . . . . . . . . 33

    8

  • Lista de Tabelas

    1.1 Alfabeto cifrado deslocado um determinado numero de casas (neste

    caso, tres) em relacao ao alfabeto original. . . . . . . . . . . . . . . . 19

    1.2 A cifra de Cesar aplicada a uma mensagem curta. . . . . . . . . . . . 19

    1.3 Os numerais equivalentes para as letras. . . . . . . . . . . . . . . . . 20

    1.4 A correspondencia entre as letras para a Cifra de Cesar . . . . . . . . 20

    1.5 A correspondencia entre as letras para cifra com C 7P +10 (mod 26). 23

    5.1 Lista dos numeros 1 x 51 coprimos com 51. . . . . . . . . . . . . 63

    5.2 Correspondencia alfa numerica . . . . . . . . . . . . . . . . . . . . . . 67

    9

  • Parte I

    Trabalho de Conclusao de Curso A

    10

  • Introducao

    A criptografia esta presente no cotidiano das pessoas mesmo que muitas vezes elas

    nao tenham consciencia/conhecimento disso. Uma simples mensagem trocada via

    e-mail, uma compra realizada atraves do cartao de credito ou mesmo o envio e rece-

    bimento de mensagens de texto por celular, em todas essas situacoes esta presente a

    criptografia. E se tudo isso hoje e possvel e e feito com velocidade impressionante

    e porque ao longo da historia houve quem se dedicasse a` Criptologia e em meio a`s

    batalhas entre criadores e decifradores de codigos tivessemos grandes avancos em

    diversas areas e ciencias diretamente ligadas a` tematica. Certamente devemos a`

    historia dos codigos por tamanho desenvolvimento cientfico e tecnologico nos dias

    atuais.

    Varios assuntos entram em pauta quando o assunto e criptografia. Manu-

    tencao da lei e seguranca nacional, direitos civis e privacidade individual, atividades

    civis e militares. Em todo esse conjunto a criptografia exerce papel central e gera al-

    gumas questoes que para serem respondidas exigem que sejam considerados diversos

    aspectos. Vejamos. Ha tempos os servicos policiais fazem uso de escuta telefonica

    para fins de investigacao e/ou coleta de informacoes que servirao como provas con-

    tra criminosos e recentemente com o desenvolvimento de codigos ultra-resistentes o

    grampo ve sua funcionalidade ameacada.

    No tocante a` privacidade individual ha uma corrente que defende o uso

    generalizado da criptografia de tal forma que tenhamos esse direito assegurado e

    mantido. Paralelamente temos aqueles que trabalham com negocios e necessitam da

    criptografia e de codigos seguros para a manutencao de suas atividades comerciais.

    11

  • 12

    Ao mesmo tempo encontramos as forcas da lei na defesa de um uso mais restrito da

    criptografia.

    Nesse contexto, onde interesses individuais e coletivos entram em choque

    temos a criptografia sendo utilizada com as mais diversas finalidades, mas desem-

    penhando sempre um papel importante e ocupando posicao central.

    A historia da Criptologia e extremamente vasta e rica em episodios inter-

    essantes e que por muitas vezes mudaram o rumo de acontecimentos importantes

    da historia humana. Sao comuns as situacoes onde o destino de reis, rainhas, civi-

    lizacoes e tramas de assassinato dependeram da manutencao ou quebra de mensagens

    secretas. No entanto, algumas partes ficarao de fora deste trabalho em virtude da

    necessidade de escolha daquilo que esteja mais fortemente ligado ao que estamos

    estudando por conta de espaco e foco.

  • Captulo 1

    Um pouco de historia

    1.1 A evolucao da escrita secreta

    Um dos primeiros relatos acerca de escrita secreta data de Herodoto, que escreveu

    As historias e narrou os conflitos entre Grecia e Persia, ocorridos no seculo V a.C.

    A escrita secreta desempenhou um papel essencial ao evitar que a Grecia

    fosse conquistada por Xerxes, o despota lder dos persas. Xerxes comecara a con-

    struir a cidade de Persepolis que seria a nova capital de seu reino. Vindos de todas

    as regioes do imperio e de estados vizinhos, tributos comecaram a chega