elgio
(usa OpenSuSE)
Enviado em 05/08/2009 - 15:08h
Como N foi gerado a partir de dois números primos, P e Q, somente existem DOIS divisores, ou seja, apenas UM P e um Q.
Contudo, caso tenha havido um erro na geração das chaves (P e Q não eram primos), não importa. Ao achar UM P e um Q, qualquer que seja, quebrou-se o algoritmo.
Veja um exemplo.
Tenho um N MUITO GRANDE:
N = 1308881339770618216278492249627915044337069338458164167832695
Este N foi gerado pelos números P e Q também grandes:
P = 1214031856739561104303265096777
Q = 1078127672271951424306891641535
Achar estes valore de P e Q levaria DIAS mesmo com a melhor ferramenta.
Contudo, houve um grande equívoco na escolha, pois Q não é primo.
Ao se executa a ferramenta para encontrar P e Q, ela em MICROSSEGUNDOS acha a resposta:
p = 5
q = 261776267954123643255698449925583008867413867691632833566539
GRANDE VACILO, pois o N gigantão divide por 5. Paciência, a "grande" chave N acaba de ser quebrada. Jogando estes valores no teorema de euclides ele retornará sim um valor d que pode ser usado para reverter a criptografia.
Portanto o programa de vocês acaba quando encontrar UM DIVISOR, seja qual for (ou outro não precisa ser buscado, né. Bata fazer N/P para achar o Q).
Uma dica importante: sempre testem se os valores fecham. Os programas podem estar bugados e gerarem valores absurdos de P e Q. Ao achar ou pensar ter achado um valor de P e Q, façam um:
echo "P * Q"|bc
E vejam se isto resulta mesmo no N publicado.
