Introdução a Criptografia Rsa

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 36INTRODUOACRIPTOGRAFIARSARafaelLimaOliveira,Prof.Dr.FernandoPereiradeSouza.CPTL/UFMS,TrsLagoas,MS,Brasil,oliveiralimarafael@hotmail.com.CPTL/UFMS,TrsLagoas,MS,Brasil.RESUMONo trabalho foi estudado o conceito de Criptografia RSA, que uma aplicao da teoria dosnmerosmuitousadaembancos,transaescomcartodecrdito,comprasonline,mensagensde email emuitomais. Tal algoritmo oumtodo de criptografar oferece tanta segurana emquaisquertransaesqueamaisusadaemaplicaescomerciaisemtodoomundo.Adescriodoporquetantaseguranaequalidadedestemtodoseroenunciadosnestetrabalho,utilizandoemseudesenvolvimentoconceitosqueseroempregadosdemaneirarelativamenteelementar,com o objetivo de fazer uma descrio simples e de boa compreenso de todos sobre aCriptografiaRSA.Palavraschave:CriptografiaRSA,Codificar,Mensagem,Segurana,Algoritmo.INTRODUOEOBJETIVO

ATeoriadosnmerosumareamuitoestudadaeconhecidanaMatemticaporoferecerum lequeenormederesultados importantesutilizandonmeros.Taisconceitosqueateoriadosnmerosestudaemgeralsopropriedadesdosnmeros inteiros,enodequaisquernmeros.Alguns exemplos so fatorao, mximo divisor comum, critrios de divisibilidade, nmerosprimosearitmticamodular.

A criptografia estuda os mtodos para codificar uma mensagem de modo que seudestinatrio legtimo consiga interpretla. Tal fato expressamente necessrio para que amensagememhiptesealguma,mesmoquesejacondicionadaporescutas,sejainterpretadaporquemestcomminteno.CriptografiadotipoRSA,levaestenomedevidoaosseusinventoresR.L.Rivest,A.ShamireL.Adlemanem1977.

Oqueserapresentadonestetrabalhoomtododecriptografarutilizandochavepblicachamado RSA, e em seu desenvolvimento ser apresentado alguns conceitos de teoria dosnmerosbemcomoametodologiaparacodificaredecodificarmensagens.METODOLOGIA

Nodesenvolvimentodestetrabalho foramrealizadosestudosdirigidoscomoorientadoreapresentao de seminrios expositivos, bem como matria bibliogrfica especificada quepossibilitouumaboaapreciaosobreotema.Entrediversasdiscussesqueotemaproporcionoudentreelesoestudodemximodivisor comum, fatorao, critriosdedivisibilidade,nmerosColloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 37primosearitmticamodularoquesedeveaterdetodosestesitensosresultadosdosteoremaseproposiesvistosemtodooestudo.

RESULTADOS Para formalizar o mtodo da criptografia consideramse alguns teoremas, proposies edefiniesimportantesenecessriasoriundasdoestudodateoriadosnmeros:Definies:

Umnmero ditoprimosefordivisvelsomentepor1eporsiprprio. Sejam e fixo. Dizse que congruente a mdulo

se,esomentese, . Seja um inteiro. Chamase inverso de um inteiro tal que

Algoritmo da Diviso: Sejam . Ento, existem nicos tais que

(Se dizemosquebdividea(ba),qchamadodequocienteerderestodadivisodeaporb).Lema:Se ,entoo .AlgoritmodeEuclides:Sejam dois inteiros cujomximodivisorcomumsedesejadeterminar.Aplicandosucessivamenteoalgoritmodadivisotemos:

Comoosrestos sotodosinteirospositivostaisque

e existem apenas inteiros positivos menores que , necessariamente se chega a umadivisocujoresto

Oultimoresto queaparecenestasequnciadedivisesomximodivisorcomumprocuradodeaeb,isto,o .

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 38 Paramelhorentendera criptografiaRSA,utilizasedois resultados, tais resultadospodemser encontrados em Teoria Elementar dosNmeros de Edgar de Alencar Filho pgina 183 epgina193.TeoremaChinsdoResto:Sejam inteirospositivostaisqueo ,sempreque .Ento,osistemadecongruncias

Admiteumanicasoluomdulo PequenoteoremadeFermat:Seja umnmeroprimo.Se ento

AsdemonstraesnovoserapresentadasparaquesejapossvelapresentarmaisdetalhesdomtodoRSA.Criptografia RSA: Consideramse trs etapas para realizar a codificao e decodificao damensagem.PrimeiraEtapa:PrCodificao:Estaetapa se refereescolhadamensagempara codificao.Considerase para simplificar que nesta mensagem no h nmeros e todas as letras somaisculas.Attulodeexemplo,consideraseamensagemUNOESTE.Utilizaseparaconverteramensagemaseguintetabela

A B C D E F G H I J K L M10 11 12 13 14 15 16 17 18 19 20 21 22N O P Q R S T U V W X Y Z23 24 25 26 27 28 29 30 31 32 33 34 35

Obs:Oespaoentreduaspalavrasdefinidopelonmero99quandofeitaaconverso.

Emnmeroamensagemficaescritacomo30232414282914.importanteseguiratabeladeconversoparaevitarproblemasmaisadiante.

Definese alguns parmetros antes de continuar: Seja dois primos distintos quedenotaremosrespectivamenteporpeqtaisqueorestonadivisopor6temdeser5.Usaseesteparmetro com intuito de simplificar um poucomais e tambm para utilizar um resultado deCoutinho (2008,p.99).Definese ,nosquaisparaoexemplo tomamsedoisprimos,17e23,logoimplicaque .Altimafasedoprocessodeprcodificaoconsiste

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 39em quebrar em blocos o nmero formado pela converso damensagem tal que, estes blocossejamestritamentemenoresque .Nocasodoexemplo,amensagemseguiradaforma:

Obs1:Amaneiradeescolhertaisblocosnonica,masprecisamobedeceraofatodeno

comearemcom0.Obs2:Osblocosnocorrespondemanenhumaunidadelingstica.

SegundaEtapa:Codificao:Paracodificarprecisoapenasde queoprodutodeprimos.Dizque a chave de codificao do sistema RSA e dita chave pblica que pode ser enviada aqualquerpessoa.Adefiniodecodificao:NOTAO:C(b)oblococodificadodefinidopor

Noexemplotemosque .Destaformaosblocosqueforamquebradosseguem:

Amensagemcodificadaser:

Feito este processo finalizase esta etapa. importante citar que depois de feita acodificaodestesblocosnosepode juntlosnovamente,poisseacontece,noseriapossveldistinguilosunsdosoutrosparaaetapaseguinte.Terceira Etapa: Decodificao: Para decodificar usamse dois nmeros: e oinverso Fatoesteporquefoiconsideradooparmetrodefinidoacima.Apropriandodadefiniodeinverso(Definio3)segue

Defineseopar dechavededecodificao.Estamantidaemsegredo.

Notao:Se oblococodificado,denotapor oprocessodedecodificao,emque

Paracalcular ,utilizado fatoque foiconsideradonoparmetrodefinidoanteriormente,emque deixamresto5nadivisopor6.Segueque

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 40

Assim,

onde

Como ,ponto3emevidncia

assim,

ento

. Logo, oinversode3mdulo .Como negativo,adequamostalnmerodemaneiraaencontrarorestomdulo .Assim quepositivopara todo Logo mesmo o resto de . Portantopodemostomar .

Comonoexemploconsiderasep=17eq=23,deformaque

queigual:.

Portanto Aplicandoareceitadada,temosque ,onde

a o bloco codificado.Desta forma o clculode tal potncia seria complicado se no fosse oalgoritmo chinsdo restoeoTeoremade Fermat.Aplicando tais ferramentasparadecodificartemosquecomo391=17.23,faremos .DestaformaseguepeloteoremadeFermat:

Da NovamentepeloteoremadeFermat, ,assim

Obtmseportantoosistema:

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012 41 Usa para resolver o sistema o teorema chins do resto. Como

, substituindo na segunda congruncia temos, somando 13 de ambos os lados da congruncia temos

. Mas o inverso de , logo como ,usandoofatode4ser inversode17mdulo

23 segue que , sendo assim como, substituindo temse

Portando segue novamente o nmero correspondente ao bloco original que passou por estasetapas.Fazendoomesmoprocessocomosoutrosblocosqueforamcodificados:

Juntando novamente estes blocos a fim de formar um nmero novamente:

UsandoatabeladeconversoobtmseamensagemUNOESTE,queeraoquerealmentesetinhaanteriormente.DISCUSSO

Considerandooexemplodadoanteriormente,observouqueescolheudoisprimos talqueobedecesseaoparmetroinformadoequeforamnmerosbempequenos.Enfim,nasaplicaesdeRSAemempresasquerealmenteprecisamdemuitaseguranaachave chegaaserformadapornmeroscomcercade2470algarismosdeacordocomCoutinho(2008,p.158).Considerandootamanhodestenmero,eraaindaprecisosaberosprimos quesomentepossvelatravsdafatoraode .Paraseterumaideiadotempoparaseconseguirfatorar consideraseumafatorao finalizadaporF.BahrnoEscritrioFederaldeSeguranade InformaodaAlemanhaemqueosclculosforamem80computadoresde2.2GHz,mesmoassimfoinecessrio5mesesparacompletarascontasquepossibilitou fatorarumachavede193algarismos.Podeverquepossvel fatorar, mas como as chaves pblicas utilizadas por empresas possuem at 2470algarismos,definitivamenteimpossvelqueseobtenhanovamenteosprimos.Massuponhaquese conseguiu encontrar os primos, como possui estes tantos algarismos o bloco em que amensagem foiquebradadependendodamensagem jmuitogrande,enfim, comoaprximaetapaconsisteemelevaresteenormenmeroapotnciade3,ouseja,nestaalturaamemriadocomputador j no tem mais espao suficiente para tantos clculos. Mesmo que na pior das

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

Encontro de Ensino, Pesquisa e Extenso, Presidente Prudente, 22 a 25 de outubro, 2012

Colloquium Exactarum, vol. 4, n. Especial, jul-dez, 2012

42

hipteses sejapossvel,naetapadedecodificaoonmeroemque foielevadonapotncia3precisa serelevadoao inversoqueobtidopela congruncia (*)queumapotnciaenorme,sendoassim,definitivamenteonmerosergigantesco, logosemnenhumapossibilidadedeserdescobertaoblocooriginal.

CONCLUSES Nestetrabalhosefezumabreve introduodomtododecriptografarchamadodeRSA,deformaque,otemafoicondicionadodemaneiraintrodutriaafimdedeixarotrabalhocomleiturae entendimentoparadiferentespblicos.Almdisso, foipossvel reafirmarqueoprocessodecriptografarusandoomtodoRSAtotalmenteseguroe livredequalquerperigodamensagemserdescobertadesdequeosprimosescolhidossejambemgrandes.REFERNCIASAlencarFilho,Edgardde.TeoriaElementardosnmeros,NOBEL,SoPaulo,1988.Hefez,Abramo,Elementosdearitmtica,SBM,RiodeJaneiro,2011.COUTINHO,S.C.,Criptografia,ProgramadeIniciaoCientfica,RiodeJaneiro,2008.