Algoritmo de euclides estendido (calcula o D RSA)
Publicado por Elgio Schlemer (última atualização em 21/08/2009)
[ Hits: 26.758 ]
Homepage: https://profelgio.duckdns.org/~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"); }
Faz um crash no Kernel do Linux
Esse código pode ser considerado um vírus?
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Flatpak: remover runtimes não usados e pacotes
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
estou com chromebook legalzinho. (2)
Estou com sede em aprender sobre o nosso querido Linux. (1)
big linux sem audio como resolver (2)
Como faz para dar um update-grub por shell script [RESOLVIDO] (3)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta