Algoritmo de euclides estendido (calcula o D RSA)
Publicado por Elgio Schlemer (última atualização em 21/08/2009)
[ Hits: 27.037 ]
Homepage: http://profelgio.duckdns.org:8080/~elgio
Implementação do algoritmo estendido de euclides, em C. Este código permite que se encontre (calcule) o valor d da chave privada RSA Kd(N, e), desde que se conheça os valores de P, Q e do E.
No entanto este código em C só trabalha com inteiros dentro da capacidade da ULA. Pode-se portá-lo para outras linguagens ou mesmo implementar Big Numbers nele ( http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes/ ).
Este programa é parte integrante do artigo "Criptografia assimétrica com o RSA", encontrado em:
http://www.vivaolinux.com.br/artigo/Criptografia-assimetrica-com-o-RSA/
#include <stdio.h> #include <stdlib.h> /* Aritmética modular é também considerada como o "algoritmo do relógio". Ao extrair o modulo 12, como resposta possível pode-se ter números de 0 a 11. Nunca negativo, pois a ideia é de um relógio com 12 posições, sendo a primeira o zero e a última o 11. Porém o operador de módulo do C (operador %) computa apenas o resto da divisão e gera números negativos. Em C: -2 mod 12 = -2 (não está entre 0 e 11) 2 mod -12 = 2 (não está entre -11 e 0) O C dizer que -2 mod 12 é -2 significa dizer que ele está a -2 de distância do final do relógio, ou seja, está em 10 (o início e também o final do relógio é o zero). Dizer que 2 mod -12 significa um relógio ao contrário (0, -1, -2, -3, .. -11, andando no sentido anti-horário) e que o valor 2 está a 2 posições de distância do 0, ou seja, está em -10. Nesta artimética modular o resultado da operação PRECISA SER do mesmo sinal do divisor. Observou-se que o operador de módulo do python (%) não tem este comportamento, calculando o módulo não negativo. A biblioteca bn.h do openssl possui ambos, tanto a função BN_mod que simplesmente retorna o resto da divisão (comportamento igual ao %) como a função BN_nnmod que calcula o módulo não negativo. Nesta versão em C resolveu-se fazer uma pequena correção na resposta dada pelo operador de módulo, pois o algoritmo de euclides precisa do módulo positivo. */ long mod(long a, long b) { long r = a % b; /* Uma correçã é necessária se r e b não forem do mesmo sinal */ /* se r for negativo e b positivo, precisa corrigir */ if ((r < 0) && (b > 0)) return (b + r); /* Se ra for positivo e b negativo, nova correcao */ if ((r > 0) && (b < 0)) return (b + r); return (r); } long euclides_ext(long a, long b, long c) { long r; r = mod(b, a); if (r == 0) { return (mod((c / a), (b / a))); // retorna (c/a) % (b/a) } return ((euclides_ext(r, a, -c) * b + c) / (mod(a, b))); } int main(int argc, char *argv[]) { long p, q, e, qq, n, d; /* O objetivo desta implementação do algoritmo de euclides extendido é o cálculo do valor do D da chave privada correspondente a Ke=(n,e) para isto são necessários fornecer o p, o q e o valor de e */ if (argc != 4) { fprintf(stderr, "ERRO. faltou passar valor de p, q, e\n"); fprintf(stderr, "Forma de uso:\n"); fprintf(stderr, "\t%s p q e\n", argv[0]); return (1); } /* pegando os valores de p, q e n fornecidos como argumentos do main */ p = atol(argv[1]); q = atol(argv[2]); e = atol(argv[3]); /* calculando o n */ n = p * q; /* calculando o quociente de euler, chamado aqui de qq */ qq = (p - 1) * (q - 1); /* chamando a função que calcula o d. Ela retorna um número que case na expressão: d*e mod qq = X Tem-se o e e o qq. Para o RSA o X deve ser 1, pois d*e mod qq = 1 */ d = euclides_ext(e, qq, 1); printf("\nVALORES CALCULADOS:\n"); printf("N = %10li\nE = %10li\nqq = %10li\nD = %10li\n", n, e, qq, d); printf("\n*** Verifique com ***\n"); printf("\techo \"(%li * %li) %% %li\"|bc\n\n", d, e, qq); printf("\t(deve resultar em 1)\n\n\n"); }
Criptografar um Arquivo de Texto por cifra de Transposição
IntensiveDoS - ferramenta de DoS para pentesting
Cifra de Cesar - Cripto-Analise
Aprenda a Gerenciar Permissões de Arquivos no Linux
Como transformar um áudio em vídeo com efeito de forma de onda (wave form)
Como aprovar Pull Requests em seu repositório Github via linha de comando
Visualizar arquivos em formato markdown (ex.: README.md) pelo terminal
Dando - teoricamente - um gás no Gnome-Shell do Arch Linux
Como instalar o Google Cloud CLI no Ubuntu/Debian
Mantenha seu Sistema Leve e Rápido com a Limpeza do APT!
Procurando vídeos de YouTube pelo terminal e assistindo via mpv (2025)
Alguém já usou o framework Avalonia para desenvolver interfaces de usu... (4)
Ajuda Pra Melhoria do NFTABLES. (8)
Sinto uma leve lentidão ao arrastar, miniminizar e restauras as janela... (2)
Pastas da raiz foram para a área de trabalho [RESOLVIDO] (7)