{"id":323,"date":"2012-08-09T14:11:11","date_gmt":"2012-08-09T17:11:11","guid":{"rendered":"http:\/\/linuxrs.com.br\/?p=323"},"modified":"2012-08-09T14:11:11","modified_gmt":"2012-08-09T17:11:11","slug":"criptografia-assimetrica-com-o-rsa","status":"publish","type":"post","link":"https:\/\/blog.clusterweb.com.br\/?p=323","title":{"rendered":"Criptografia assim\u00e9trica com o RSA"},"content":{"rendered":"\n\n\n\n\n\n\n\n
Introdu\u00e7\u00e3o<\/strong><\/p>\n
Este artigo n\u00e3o pode ser considerado um artigo isolado. Ele faz parte de uma sequ\u00eancia de outros artigos sobre o tema. Se voc\u00ea n\u00e3o \u00e9 versado no assunto da criptografia, talvez queira ler os artigos anteriores antes de prosseguir a leitura deste.<\/p>\n

A primeira vez que escrevi sobre criptografia foi em fevereiro de 2009, com o artigo Introdu\u00e7\u00e3o a criptografia<\/a>. Neste eu defini algumas terminologias, explicando o que \u00e9 chave, criptoan\u00e1lise e for\u00e7a bruta, al\u00e9m de conceituar os tipos de algoritmos existentes.<\/p>\n

Na sequ\u00eancia, em mar\u00e7o de 2009, dei continuidade ao tema com o artigo Criptografia chave sim\u00e9trica de bloco e de fluxo<\/a>, que descrevia o primeiro tipo, os de cifras sim\u00e9tricas.<\/p>\n

Por fim, em Julho de 2009, desejava completar a s\u00e9rie falando sobre os algoritmos assim\u00e9tricos. Por\u00e9m ao perceber que o artigo estava ficando demasiadamente grande, optei em divid\u00ed-lo em duas partes, sendo que a primeira parte tratou dos fundamentos matem\u00e1ticos que permitiram a constru\u00e7\u00e3o do RSA, bem como situ\u00e1-lo na hist\u00f3ria (Fundamentos da criptografia assim\u00e9trica<\/a>).<\/p>\n

Este artigo \u00e9, portanto, uma segunda parte sobre algoritmos assim\u00e9tricos e traz, n\u00e3o apenas a descri\u00e7\u00e3o de um algoritmo assim\u00e9trico, como tamb\u00e9m um passo a passo de como ele realmente funciona, podendo qualquer um testar.<\/p>\n

Para usar um algoritmo de criptografia \u00e9 necess\u00e1rio que as partes envolvidas possuam um segredo em comum, uma chave. Ao transmitir uma mensagem o emissor pode cifrar ela com um algoritmo de criptografia usando esta chave. O receptor recupera a mensagem usando a mesma chave.<\/p>\n

Por\u00e9m existe um problema que \u00e9 o compartilhamento desta chave, ou seja, de que forma o emissor e receptor chegaram a um consenso sobre seu valor. Se existe a possibilidade de um encontro pessoal e f\u00edsico o compartilhamento desta informa\u00e7\u00e3o pode ser realizado com seguran\u00e7a, mas se o \u00fanico meio de transmiss\u00e3o existente entre eles \u00e9 inseguro, tem-se um problema s\u00e9rio. N\u00e3o se pode enviar a chave pela Internet, pois em caso de algu\u00e9m estar escutando, este ver\u00e1 esta informa\u00e7\u00e3o. Por isto que durante muitos anos pesquisadores procuraram um algoritmo que fosse assim\u00e9trico<\/em>.<\/p>\n

Um algoritmo assim\u00e9trico possui mais de uma chave, tipicamente duas. Uma delas \u00e9 usada para cifrar e a outra serve apenas para decifrar. Caso tal algoritmo existisse, o emissor poderia enviar pela Internet apenas a chave que cifra, mantendo em segredo a chave que decifra, ou vice versa.<\/p>\n

A comunidade cient\u00edfica desistiu desta busca, classificando o problema como sem solu\u00e7\u00e3o, mas Whitfield Diffie<\/em> e Martin Hellman<\/em> insistiram na utopia de um algoritmo assim\u00e9trico. Suas buscas frustraram-se tentativa por tentativa at\u00e9 que finalmente fizeram uma importante descoberta ao explorar a matem\u00e1tica modular (detalhes em Fundamentos da criptografia assim\u00e9trica<\/a>).<\/p>\n

Infelizmente esta descoberta n\u00e3o resultou, de imediato, em um algoritmo assim\u00e9trico mas sim em um protocolo de troca de chaves que recebeu o nome de Diffie-Hellman, usado at\u00e9 hoje. Mesmo tendo continuado sua busca, foram os pesquisadores Ronald Rivest<\/em>, Adir Shamir<\/em> e Leonard Adlemann<\/em> que chegaram ao primeiro algoritmo de cifra assim\u00e9trico, o popularmente conhecido algoritmo RSA<\/em> (mais tarde tornou-se p\u00fablico que o governo brit\u00e2nico j\u00e1 possu\u00eda quatro anos antes um algoritmo assim\u00e9trico e que este seguia os mesmos princ\u00edpios do RSA).<\/p>\n

Talvez n\u00e3o seja do interesse de muitos entender como o RSA funciona. Afinal, n\u00f3s, da \u00e1rea de TI, n\u00e3o os elaboramos, apenas os usamos. Muitos destes algoritmos s\u00e3o baseados em princ\u00edpios matem\u00e1ticos que nos s\u00e3o distantes e, n\u00e3o raro, nos resignamos a aceitar e acreditar nas informa\u00e7\u00f5es que os matem\u00e1ticos nos contam.<\/p>\n

Por exemplo, se eles nos dizem que a opera\u00e7\u00e3o exponencial de aritm\u00e9tica modular n\u00e3o pode ser revertida, que seja! Se nos dizem que a descoberta de dois divisores primos de um n\u00famero s\u00f3 pode ser feita por tentativa e erro, que seja. Lemos, implementamos e usamos.<\/p>\n

Contudo eu, particularmente, acredito que conhecer as coisas, as entranhas, o como \u00e9 feito, ter o poder de fazer no bra\u00e7o, \u00e9 um prazer indescrit\u00edvel.<\/p>\n

Estejam com suas calculadores bc na m\u00e3o.<\/p>\n<\/div>\n<\/td>\n<\/tr>\n

A teoria dos algoritmos assim\u00e9tricos<\/strong><\/p>\n
Um algoritmo de criptografia assim\u00e9trico, mais popularmente conhecido como algoritmos de chave p\u00fablica e privada<\/em>, consiste no uso de duas chaves distintas. Uma delas \u00e9 usada para cifrar dados e a outra para decifrar, ou seja, o que uma chave faz, a outra desfaz.<\/p>\n

Como exemplo, considere que duas pessoas desejam enviar dados sigilosos pelos correios. Usar\u00e3o uma caixa fechada com um cadeado para isto. O problema \u00e9 como enviar a chave, j\u00e1 que uma pessoa poderia captur\u00e1-la e realizar uma c\u00f3pia. Diffie e Hellman pensaram na ideia de dois cadeados, com duas chaves, conforme descrito no artigo Fundamentos da criptografia assim\u00e9trica<\/a>. Por\u00e9m tem uma maneira ainda mais f\u00e1cil de realizar esta comunica\u00e7\u00e3o.<\/p>\n

Caso um emissor C queira enviar dados para um receptor F usando os correios, o procedimento poderia ser o seguinte:<\/p>\n

RSA passo a passo<\/strong><\/p>\n
E quase que o algoritmo recebeu o nome de ARS!<\/p>\n

Ronald Rivest teve um momento de brilhantismo ap\u00f3s uma grande quantidade de vinho e passou a noite de p\u00e1scoa escrevendo um artigo cient\u00edfico sobre sua descoberta. Ap\u00f3s terminar, como s\u00f3 chegara a este algoritmo ap\u00f3s anos de trabalho junto com seus colegas, enumerou os autores em ordem alfab\u00e9tica: Adleman, Rivest, Shamir<\/em>.<\/p>\n

Adleman n\u00e3o concordou em ser citado como autor do artigo pois julgara que o trabalho maior fora de Rivest e, conforme confidenciou mais tarde, n\u00e3o considerava aquilo realmente algo brilhante. Ap\u00f3s longa discuss\u00e3o e negocia\u00e7\u00e3o, Adleman aceitou seu nome no trabalho, desde que fosse o \u00faltimo autor citado, nascendo assim o algoritmo mais conhecido da criptografia, batizado pelas iniciais de seus criadores Rivest, Shamir e Adleman, o RSA (O livros dos c\u00f3digos<\/em>, p\u00e1ginas 297 a 299).<\/p>\n

O cora\u00e7\u00e3o do RSA consiste na mesma fun\u00e7\u00e3o de m\u00e3o \u00fanica descoberta por Whitfield Diffie e Martin Hellman, a fun\u00e7\u00e3o modular. Novamente, assim como no algoritmo Diffie-Hellman, a seguran\u00e7a est\u00e1 no emprego de n\u00fameros realmente gigantes, hoje da ordem de 512 bits. Zelando pela compreens\u00e3o, ser\u00e3o usados valores num\u00e9ricos pequenos nesta demonstra\u00e7\u00e3o, assim todos os leitores podem reproduzir facilmente em suas calculadoras de linha de comando, bc ou dc.<\/p>\n

A primeira etapa do algoritmo RSA \u00e9 a cria\u00e7\u00e3o do par de chaves, a p\u00fablica e a privada. Deixando Alice e Bob de lado, pois ningu\u00e9m mais os aguenta, Luiza quer criar seu par de chaves.<\/p>\n

Luiza cria seu par de chaves<\/h1>\n

Luiza come\u00e7a escolhendo dois n\u00fameros primos, chamados de p<\/em> e q<\/em>, que mant\u00e9m em segredo. Um n\u00famero primo \u00e9 aquele que n\u00e3o possui nenhum divisor, exceto 1 e ele mesmo. Luiza escolheu os n\u00fameros p=17<\/em>, q=23<\/em>.<\/p>\n

Ap\u00f3s Luiza calcula o produto destes dois n\u00fameros, chamado de n<\/em>. No caso, n = p*q<\/em>, sendo que n=17*23<\/em>.<\/p>\n

Agora Luiza computa o quociente de Euler<\/strong>, que nada mais \u00e9 do que (p-1)*(q-1)<\/em>. Neste exemplo este valor ser\u00e1 representado por qq<\/em>.<\/p>\n

Neste momento Luiza tem os seguintes n\u00fameros:<\/p>\n

p = 17
\nq = 23
\nn = 391 (17 *23)
\nqq = 352 (16 * 22)<\/div>\n

Luiza agora precisa encontrar um n\u00famero e<\/em> que seja primo relativo a qq<\/em>. Um primo relativo \u00e9 apenas aquele que n\u00e3o possui divisor em comum, ou seja, sendo qq=352<\/em> e possuindo v\u00e1rios divisores (352 possui 10 divisores: 2, 4, 8, 11, 16, 22, 32, 44, 88 e 176 ) qualquer n\u00famero que n\u00e3o tenha nenhum destes divisores serve. Na pr\u00e1tica se e<\/em> for tamb\u00e9m um n\u00famero primo, ou seja, n\u00e3o possuir divisor algum, ele ser\u00e1 com certeza um primo relativo a qq<\/em>. Assim qualquer n\u00famero primo serve como e<\/em> (de fato, o RSA atual fixa este n\u00famero para todas as chaves, normalmente 65537).<\/p>\n

Luiza decidiu ficar com o n\u00famero 7 para e<\/em>.<\/p>\n

Agora vem a parte mais interessante do algoritmo. Luiza precisa encontrar um n\u00famero d<\/em>, que satisfa\u00e7a a express\u00e3o (d*e) mod qq = 1<\/em>, ou seja, um n\u00famero d<\/em> que ao se multiplicar por e<\/em>, realizando o m\u00f3dulo com o quociente de Euler (qq<\/em>), resulte em 1. Pode-se, para n\u00fameros pequenos, simplesmente escolher um d<\/em> que sirva, mas isto n\u00e3o \u00e9 uma boa ideia para n\u00fameros grandes. Contudo o n\u00famero d<\/em> pode ser calculado atrav\u00e9s de uma varia\u00e7\u00e3o do teorema de Euclides, chamada de euclides estendido, para c\u00e1lculo do m\u00e1ximo divisor comum. Uma implementa\u00e7\u00e3o em C deste algoritmo pode ser encontrada em Algoritmo de euclides estendido (calcula o D RSA)<\/a><\/p>\n

Luiza calculou o valor d=151<\/em>, pois (151*7) mod 352<\/em> \u00e9 realmente igual a 1, conforme voc\u00ea mesmo pode verificar com o seu bc:<\/p>\n

$ echo “(151 * 7) % 352” | bc<\/strong>
\n1<\/p>\n

Desta forma, Luiza possui os seguintes n\u00fameros:<\/p>\n

p \u00a0= \u00a017<\/strong> \u00a0 \u00a0escolhido aleatoriamente, desde que primo<\/em>
\nq \u00a0= \u00a023<\/strong> \u00a0 \u00a0escolhido aleatoriamente, desde que primo<\/em>
\nn \u00a0= 391<\/strong> \u00a0 \u00a0pela opera\u00e7\u00e3o p*q<\/em>
\nqq = 352<\/strong> \u00a0 \u00a0pela opera\u00e7\u00e3o (p-1) * (q-1) <\/em>
\ne \u00a0= \u00a0 7<\/strong> \u00a0 \u00a0que seja primo relativo a qq.<\/em>
\nd \u00a0= 151<\/strong> \u00a0 \u00a0calculado pelo teorema de Euclides<\/em>
\n<\/tt><\/div>\n

Luiza agora precisa apagar e remover quaisquer vest\u00edgios de p, q e qq, mantendo apenas o e, d e o n (e aconselha-se escrever na mem\u00f3ria v\u00e1rias vezes lixo nas vari\u00e1veis que tem p, q e qq, a fim de que n\u00e3o fiquem vest\u00edgios dela nem mesmo na \u00e1rea de troca do sistema, o swap).<\/p>\n

Luiza agora j\u00e1 tem o seu par de chaves, a saber:<\/p>\n

N\u00e3o frite seu processador<\/strong><\/p>\n
O RSA \u00e9 brilhante, mas seu uso foi considerado como n\u00e3o pr\u00e1tico durante muitos anos. Seu uso de forma segura requer a escolha de n\u00fameros p e q muito grandes, fazendo com que o d, principalmente, seja igualmente de muitos bits.<\/p>\n

Considere o uso do e<\/em> em um espa\u00e7o de 17 bits, como o usado oficialmente pelo RSA: e = 65537<\/em>. Ao usar este valor como e<\/em>, a f\u00f3rmula de euclides calcular\u00e1 d = 65<\/em>, pois:<\/p>\n

$ echo “(65 * 65537) % 352” | bc
\n1
\n$<\/div>\n

Agora, com esta pequena varia\u00e7\u00e3o, cifrar algo, como por exemplo, a letra ‘z’, cujo valor decimal \u00e9 122, significa elevar na pot\u00eancia 65 e extrair o m\u00f3dulo 391:<\/p>\n

$ echo “(122 ^ 65) % 391” | bc
\n309
\n$<\/div>\n

Muito embora a parte 12265<\/sup><\/em> resulte em um n\u00famero com 136 d\u00edgitos<\/em>, o c\u00e1lculo em um processador normal pode ser realizado em milisegundos.<\/p>\n

J\u00e1 a decifragem deve ser feita com o 65537 sendo que decifrar significa elevar a este n\u00famero:<\/p>\n

30965537<\/sup> mod 391<\/strong><\/p>\n

No meu processador foram necess\u00e1rios dois segundos para completar a opera\u00e7\u00e3o, sendo que a opera\u00e7\u00e3o de exponencia\u00e7\u00e3o gerou um n\u00famero com mais de 160 mil d\u00edgitos<\/em>!<\/p>\n

E se est\u00e1 pegando muito leve, pois uma chave real, verdadeira, usada pelo RSA deve ser de, pelo menos, 1024 bits. N\u00e3o tente fazer isto em sua calculadora bc, mas ai est\u00e1 um exemplo real de uma chave oficial do RSA gerada atrav\u00e9s do openssl. E pasmem: \u00e9 apenas uma “chavesinha fraquinha” de 256 bits:<\/p>\n

p = 334534313289524152888573174586934053249
\nq = 276472048961512623704414856403001554787
\nn = 92489387043087324784734008299373122418017833935069759252445487098782848852963
\ne = 65537
\nd = 36109769233737818015273648021057724389187611534029825167304543901118715705601<\/div>\n

Algu\u00e9m ai tem coragem de cifrar um simples caractere com esta chave? \u00c9 s\u00f3 elevar a 65537. Moleza. E para decifrar, basta elevar ao simp\u00e1tico n\u00famero 36109769233737818015273648021057724389187611534029825167304543901118715705601!<\/p>\n

Este foi um dos impasses a que chegaram os pesquisadores do GCHQ e que os fizeram achar o algoritmo impratic\u00e1vel devido ao fato de que os c\u00e1lculos exigiam muito processamento, muito al\u00e9m do hardware existente na \u00e9poca. Ainda hoje isto \u00e9 uma completa utopia se n\u00e3o fosse poss\u00edvel simplificar a opera\u00e7\u00e3o atrav\u00e9s de redu\u00e7\u00f5es matem\u00e1ticas.<\/p>\n

N\u00e3o vou descrever como \u00e9 poss\u00edvel reduzir drasticamente o esfor\u00e7o matem\u00e1tico desta opera\u00e7\u00e3o, mas eu tenho uma implementa\u00e7\u00e3o deste princ\u00edpio em C\u00e1lculo de X na pot\u00eancia Y modulo N<\/a>. Para usar este programa, digite VOL como matricula, j\u00e1 que o script PHP destina-se ao uso de alunos enquanto solucionando problemas de aula. Fa\u00e7a uma teste: veja quanto tempo o teu processador levar\u00e1 para calcular 1234765531<\/sup> mod 107803 = 39618<\/em> (fazendo um echo “12347 ^ 65531 % 107803” | bc). Dependendo do seu processador, isto poder\u00e1 demorar uns 10 segundos. Depois veja quanto tempo o script PHP, que usa a redu\u00e7\u00e3o matem\u00e1tica, precisou.<\/p>\n

Sem este atalho matem\u00e1tico o RSA seria invi\u00e1vel, pois os meros 256 bits anteriores ainda s\u00e3o insuficientes para garantir seguran\u00e7a. Com os atalhos matem\u00e1ticos, o RSA pode ser usado, mas ainda assim ele \u00e9 considerado um algoritmo que consome uma monstruosidade de processamento. Por isto seu emprego deve ser muito, mas muito restrito.<\/p>\n

No protocolo SSL, por exemplo, ele \u00e9 usado apenas o tempo necess\u00e1rio para que ambas as partes estabele\u00e7am uma chave de sess\u00e3o. Todo o tr\u00e1fego de dados s\u00e3o cifrados usando um sim\u00e9trico, mas r\u00e1pido, e esta chave que ambos estabeleceram. Economia de processamento. Em assinaturas digitais, o mesmo princ\u00edpio, pois se usa o RSA para assinar o hash da mensagem, que sempre tem o mesmo tamanho (128 bits no caso do MD5).<\/p>\n<\/div>\n<\/td>\n<\/tr>\n

Quebrando o RSA: um desafio para voc\u00ea valendo um livro<\/strong><\/p>\n
A quebra do algoritmo RSA consiste simplesmente em se descobrir o valor de d<\/em> da chave privada Kd<\/em>. O d<\/em> pode ser calculado pelo teorema de euclides, desde que se conhe\u00e7am os valores do e<\/em> e de qq<\/em> (quociente de euclides).<\/p>\n

Ora, o valor de e<\/em> \u00e9 publicamente conhecido, pois est\u00e1 exposto na chave p\u00fablica Ke<\/em>. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq<\/em>, o quociente de euclides.<\/p>\n

Como qq<\/em> \u00e9 calculado? Pela multiplica\u00e7\u00e3o de (P-1) por (Q -1)<\/em>, ent\u00e3o, quebrar o RSA consiste simplesmente em encontrar os valores de P<\/em> e Q<\/em>.<\/p>\n

Pensar em uma forma de encontrar os valores de P e Q \u00e9 muito f\u00e1cil, afinal sabe-se que o valor de N resultou da multiplica\u00e7\u00e3o destes dois n\u00fameros. Como o valor de N tamb\u00e9m \u00e9 conhecido, pois est\u00e1 exposto na chave p\u00fablica, quebrar o RSA \u00e9 simplesmente respondera a pergunta<\/p>\n

Quais os dois n\u00fameros que multiplicados um pelo outro resulta em N?<\/em><\/p>\n

Se lhe \u00e9 dito que o N \u00e9 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13<\/em> e Q=23<\/em>. Pronto. F\u00e1cil f\u00e1cil. Um simples la\u00e7o em qualquer linguagem de programa\u00e7\u00e3o resolve isto rapidamente. Que tal uma vers\u00e3o do la\u00e7o em bash:<\/p>\n

N=299
\nfor P in `seq 2 $N`
\ndo
\n[ “`echo “$N % $P”|bc`” == “0” ] || continue
\nQ=”`echo $N \/ $P|bc`”
\necho P=$P Q=$Q
\nbreak
\ndone<\/div>\n

Programadores em C, Java, PHP, Perl e at\u00e9 Basic n\u00e3o ter\u00e3o dificuldades em construir seus c\u00f3digos para quebrar o RSA.<\/p>\n

Se considerou isto uma tarefa f\u00e1cil, topas um desafio<\/em>?<\/p>\n

Desafio 1 (VENCIDO)<\/strong><\/p>\n

Como incentivo ser\u00e1 dado 500 pontos no Viva o Linux<\/a> para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou t\u00e9cnica usada e o tempo de processamento. Alunos e ex-alunos meus n\u00e3o podem participar, pois estudaram em sala de aula t\u00e9cnicas que os colocariam em vantagem em rela\u00e7\u00e3o aos demais. Vamos l\u00e1, tente, j\u00e1 que n\u00e3o estou realmente enviando valores imposs\u00edveis.<\/p>\n

Para o gerenciamento deste desafio foi criado o t\u00f3pico Desafio RSA n\u00famero 1 <\/a>. L\u00e1 estar\u00e3o todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes ser\u00e3o colocados dois dias ap\u00f3s a publica\u00e7\u00e3o deste artigo. Assim, caso o desafio ainda n\u00e3o tenha sido publicado, voc\u00ea tem um tempinho para ajustar sua ferramenta.<\/p>\n

Desafio 2 (VALE LIVRO)<\/strong><\/p>\n

Ap\u00f3s o desafio 1 ter sido vencido, criei outro valendo um livro. A defini\u00e7\u00e3o e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)<\/a><\/p>\n

Devo deixar claro que s\u00f3 ser\u00e3o aceitas respostas se voc\u00ea mesmo implementou sua pr\u00f3pria ferramenta e disponibilizou o c\u00f3digo fonte, conforme instru\u00e7\u00f5es do f\u00f3rum. Outro aviso de extrema import\u00e2ncia \u00e9 que este desafio ser\u00e1 realizado com a concord\u00e2ncia do administrador do Viva o Linux, j\u00e1 que envolvem pontos.<\/p>\n<\/div>\n<\/td>\n<\/tr>\n

Conclus\u00e3o<\/strong><\/p>\n
Toda a seguran\u00e7a do RSA est\u00e1 focada em um problema matem\u00e1tico ainda sem solu\u00e7\u00e3o, que \u00e9 o c\u00e1lculo de divisores de um n\u00famero. Ainda hoje a \u00fanica forma conhecida para se calcular quais n\u00fameros dividem exatamente, sem resto, um outro n\u00famero \u00e9 atrav\u00e9s da tentativa e erro, ou seja, a for\u00e7a bruta. Muitos avan\u00e7os se tem feito e muitas t\u00e9cnicas usadas para acelerar em muito esta tarefa, mas ela ainda \u00e9 um problema que demanda muito tempo.<\/p>\n

Contudo, basta que algum matem\u00e1tico descubra como calcular os divisores de um n\u00famero de forma eficiente e pronto, fim do RSA. Se \u00e9 que algum pesquisador secreto j\u00e1 n\u00e3o o tenha descoberto.<\/p>\n

Faz alguns anos o RSA foi posto em cheque devido a uma descoberta envolvendo n\u00fameros primos. O desafio de determinar se um n\u00famero \u00e9 ou n\u00e3o primo tamb\u00e9m demanda tempo. Como tu poderias dizer que o n\u00famero 65537 \u00e9 ou n\u00e3o primo? A princ\u00edpio tentando dividir ele por todos os n\u00fameros primos anteriores a ele. Tenta-se dividir por 2, por 3, por 5 (n\u00e3o teria sentido tentar por 4, pois se fosse divis\u00edvel por 4, j\u00e1 o teria sido por 2), por 7, 11, 13… Se n\u00e3o se encontrar um divisor at\u00e9 o valor da raiz quadrada de 65537, pode-se com seguran\u00e7a eleger este n\u00famero como sendo primo.<\/p>\n

Esta parte foi um desafio para o RSA. Como o algoritmo, que precisa escolher P e Q primos, pode ter certeza de que s\u00e3o primos? O n\u00famero P=339837669899793087932310819184919452667<\/em> gerado pela biblioteca openssl \u00e9 primo? Como o RSA tem certeza? O fato \u00e9 que n\u00e3o tem! Quando da escolha de P e Q n\u00e3o se tem certeza de que eles realmente s\u00e3o primos. O impacto caso n\u00e3o sejam \u00e9 que o algoritmo ficar\u00e1 mais fraco, mas funcionar\u00e1 tranquilamente.<\/p>\n

Chegar a conclus\u00e3o de que P \u00e9 realmente primo demandaria o mesmo esfor\u00e7o que um atacante teria para quebrar o N. Por isto o RSA limita-se a aplicar os 3 testes da primaridade. Se ele reprovar em um dos testes, n\u00e3o \u00e9 primo e ser\u00e1 descartado. Se passar em todos os testes, tem uma chance de X% de ser primo. Ao executar os testes v\u00e1rias vezes refina-se a precis\u00e3o tendo-se, hoje, quase certeza de que s\u00e3o primos.<\/p>\n

Pois bem, a descoberta recente (e nem t\u00e3o recente assim) foi de um algoritmo que d\u00e1 100% de certeza de que um n\u00famero \u00e9 primo. Isto, por si s\u00f3, n\u00e3o compromete o RSA pois o que se precisa \u00e9 de um algoritmo que descubra o P e o Q a partir do N. Contudo aquela “luzinha vermelha” acabou se acendendo e uma n\u00e9voa de suspeita paira sobre o RSA.<\/p>\n

Pretendia tornar este artigo ainda mais extenso, com muitos anexos descrevendo o teorema de Euclides e os atalhos matem\u00e1ticos para c\u00e1lculo de m\u00f3dulo. Por\u00e9m, estes conceitos s\u00e3o necess\u00e1rios para alunos meus resolverem alguns desafios e n\u00e3o pretendo publicar algo que lhes tire o prazer da descoberta!<\/p><\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"

Introdu\u00e7\u00e3o Este artigo n\u00e3o pode ser considerado um artigo isolado. Ele faz parte de uma sequ\u00eancia de outros artigos sobre o tema. Se voc\u00ea n\u00e3o \u00e9 versado no assunto da criptografia, talvez queira ler os artigos anteriores antes de prosseguir a leitura deste. A primeira vez que escrevi sobre criptografia foi em fevereiro de 2009, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[1,51,68],"tags":[154,155,59],"class_list":["post-323","post","type-post","status-publish","format-standard","hentry","category-viazap","category-linux-linuxrs","category-redes-2","tag-criptografia","tag-rsa","tag-versao-facil-de-usar"],"_links":{"self":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/323","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=323"}],"version-history":[{"count":1,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/323\/revisions"}],"predecessor-version":[{"id":324,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=\/wp\/v2\/posts\/323\/revisions\/324"}],"wp:attachment":[{"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=323"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=323"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.clusterweb.com.br\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=323"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}