Aplicações da Matemática em Criptografia

AS APLICAÇÕES DA MATEMÁTICA EM CRIPTOGRAFIA Algumas pessoas ainda associam mensagens codificadas a agentes secretos mas hoje existe uma variedade de transações e informações que são transmitidas eletronicamente como mensagens de aplicativos de comunicação WhatsApp Telegram e transações que envolvem dinheiro como transferências bancárias aplicativos de banco e PIX As informações referentes a essas transações são codificadas para evitar que em algum ponto da transmissão os dados sejam interceptados Os processos pelos quais as informações são enviadas eletronicamente dependem do uso da matemática Um fato curioso é que até os anos 1960 a teoria dos números que é a parte da matemática mais utilizada nas aplicações de criptografia era considerada muito teórica e com pouca utilidade na prática O estudo da teoria dos números é o estudo das propriedades dos números inteiros tais como fatoração de inteiros cálculo do máximo divisor comum números primos congruências entre outros Mas como é feita essa codificação Primeiramente vamos ver a etimologia da palavra criptografia que no grego cryptos significa secreto A criptografia estuda os métodos para codificar uma mensagem que apenas o destinatário pode decodificar Para codificar uma mensagem basta substituir uma letra por outro símbolo trocar letras por números ou escrevêla de trás para frente Cada uma dessas opções pode ser combinada com o receptor da mensagem porém para efeitos computacionais devem ter uma lógica matemática Entre os mais conhecidos métodos de decodificação temos as criptografias RSA DES IDEA SAFER AES e a chave simétrica Vamos explicar superficialmente como funciona o método RSA dando maior ênfase aos aspectos matemáticos para que possa ser realizada a atividade Para quem tem curiosidade no tema indicamos a leitura da dissertação de Daniele Helena Bonfim com o título Criptografia RSA do ano de 2017 que está disponível em httpstesesuspbrtesesdisponiveis5555136tde 06042017 164507enphp Primeiramente você precisa escolher dois números primos distintos p e q e multiplicálos obtendo um número n Na prática esses números primos são muito grandes tendo entre 100 e 200 algarismos ou seja números maiores que 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 Para codificar a mensagem usamos n e para decodificála p e q n pode ser tornado público enquanto p e q precisam ser mantidos em segredo Quebrar o RSA consiste em fatorar n o que levará muito tempo se ele for grande Para codificar uma mensagem no RSA calculamos sua potência no módulo n relativamente a um expoente especialmente escolhido Para que isso seja viável a mensagem deve ser um número inteiro Mas não é isso que ocorre em geral a maior parte das mensagens é um texto Assim a primeira ação se desejamos usar o método RSA é inventar uma maneira de converter a mensagem em uma sequência de números Vamos fazer uma précodificação usando apenas texto sem números para o espaço entre as palavras empregaremos 99 A B C D E F G H I J K L M 10 11 12 13 14 15 16 17 18 19 20 21 22 N O P Q R S T U V W X Y Z 23 24 25 26 27 28 29 30 31 32 33 34 35 Exemplo Vamos précodificar a mensagem AMO ARITMETICA Associando a cada letra um número correspondente temos 1022249910271829221429181210 Antes de continuar precisamos determinar os parâmetros do sistema RSA que vamos usar Esses parâmetros são dois primos distintos que vamos denotar por p e q devendo o resto na divisão por 6 ser 5 Vamos escolher p 17 e q 23 assim n 391 Agora vamos dividir os números em blocos menores que n Assim ficamos com 102 224 99 102 71 82 92 214 291 81 210 Não é a única maneira de escolher os blocos que não precisam sequer ter o mesmo tamanho Contudo certos cuidados devem ser tomados Por exemplo não é permitido escolher um bloco que comece por 0 porque isso traria problemas na decodificação visto que por exemplo não temos como distinguir o bloco 023 do bloco 23 Para codificar precisamos apenas de n que é a chave de codificação que pode ser tornada pública A mensagem codificada será a sequência dos blocos codificados Isso é muito importante porque depois de codificados os blocos não podem mais ser reunidos de modo a formar um longo número Se isso for feito será impossível decodificar a mensagem Digamos então que a chave de codificação é n Como faremos para codificar um bloco b sendo b um inteiro positivo menor que n Vamos denotar o bloco codificado por Cb A receita para calcular Cb é a seguinte Cb resto da divisão de b³ por n Temos n 391 Fazendo a congruência de cada bloco temos 102 3 102 2 102 238 102 24276 34 𝑚𝑜𝑑 391 224 3 224 2 224 128 224 28672 129 𝑚𝑜𝑑 391 99 3 99 2 99 26 99 2574 228 𝑚𝑜𝑑 391 102 3 102 2 102 238 102 24276 34 𝑚𝑜𝑑 391 71 3 71 2 71 349 71 24779 146 𝑚𝑜𝑑 391 82 3 82 2 82 77 82 6314 58 𝑚𝑜𝑑 391 92 3 92 2 92 253 92 23276 207 𝑚𝑜𝑑 391 214 3 214 2 214 49 214 10486 320 𝑚𝑜𝑑 391 291 3 291 2 291 225 291 65475 178 𝑚𝑜𝑑 391 81 3 81 2 81 305 81 24705 72 𝑚𝑜𝑑 391 210 3 210 2 210 308 210 64680 165 𝑚𝑜𝑑 391 Reunindo todos os blocos descobrimos que a mensagem codificada é 34 129 228 34 146 58 207 320 178 72 165 Para decodificação de um bloco da mensagem necessitamos do bloco codificado e da chave pública para reconstruir o bloco original antes da codificação Para decodificar precisamos de dois números n e o inverso d 0 de 3 módulo p 1 q 1 Por definição de inverso devemos ter 3𝑑 1 𝑚𝑜𝑑 𝑝 1 𝑞 1 Chamaremos o par n d de chave de decodificação que tem de ser mantida secreta Quem a descobrir poderá decodificar qualquer mensagem que a use De posse do par n d como devemos proceder para decodificar uma mensagem Se a for um bloco codificado denotaremos por Da o resultado do processo de decodificação do bloco a Para calcular Da temos 𝐷𝑎 𝑟𝑒𝑠𝑡𝑜 𝑑𝑎 𝑑𝑖𝑣𝑖𝑠ã𝑜 𝑑𝑒 𝑎 𝑑 𝑝𝑜𝑟 𝑛 𝐷𝐶𝑏 𝑏 Como estamos supondo que p e q deixam resto 5 na divisão por 6 temos 𝑝 5 𝑚𝑜𝑑 6 𝑒 𝑞 5 𝑚𝑜𝑑 6 Assim 𝑝 1 𝑞 1 4 4 16 4 2 𝑚𝑜𝑑 6 Em que 𝑝 1 𝑞 1 6 𝑘 2 para algum inteiro positivo k Contudo o inverso de 3 módulo 6 k 2 é igual a 4 k 1 Logo podemos tomar d 4 k 1 Considerando p 17 e q 23 temos p 1q 1 16 22 352 6 58 4 Isso é igual a p 1q 1 6 59 2 Portanto neste caso k 59 e d 4 59 1 235 Aplicando no primeiro bloco da mensagem codificada temos que D34 é igual ao resto da divisão de 34 235 por n 391 Fazer essa conta sem o auxílio de um computador seria totalmente impossível se não tivéssemos o algoritmo chinês do resto e o teorema de Fermat Vamos calcular 34 235 módulo 17 e módulo 23 que são os primos em que n se fatora Inicialmente 34 0 𝑚𝑜𝑑 17 e 34 11 𝑚𝑜𝑑 23 Assim 34 235 0 235 0 𝑚𝑜𝑑 17 Aplicando o teorema de Fermat na outra congruência temos 11 235 11 22 10 11 15 11 15 𝑚𝑜𝑑 23 Mas 11 15 121 7 11 6 7 11 𝑚𝑜𝑑 23 Por outro lado 6 7 11 279936 11 3 11 33 10 𝑚𝑜𝑑 23 Referência COUTINHO S Criptografia Rio de Janeiro IMPA 2016 Disponível em httpscdnportaldaobmepimpabrportaldaobmepuploadsmaterialteorico83bhrw1mjmgwopdf Acesso em 4 jul 2022 P lanejamento da experiência de aprendizagem semanal P lanejamento da experiência de aprendizagem semanal 0 0 P lanejamento da experiência de aprendizagem semanal P lanejamento da experiência de aprendizagem semanal 0 0