Para o RSA, como faço para calcular o segredo de expoente?
-
13-09-2020 - |
Pergunta
Para o RSA, como faço para calcular o segredo de expoente?
Dado p e q dois primos, e φ=(p-1)(q-1), e o expoente público (0x10001), como faço para obter o segredo expoente 'd' ?
Eu li que eu tenho que fazer: d = e-1 mod phi usando modular inversão e o euclidiana equação mas eu não consigo entender como a fórmula acima mapas para o um-1 ≡ x mod m a fórmula de modular a inversão da página wiki, ou como ele mapeia para euclidiana GCD equação.
Alguém pode me ajudar por favor, cheers
Solução
Você pode usar o estendido algoritmo Euclidiano para resolver para d
na congruência
de = 1 mod phi(m)
Para criptografia RSA, e
é a chave de criptografia, d
é a chave de descodificação e encriptação
e descriptografia são ambos realizados pela exponenciał c ao mod m
.Se você criptografar uma mensagem a
com chave e
, e , em seguida, decifrá-la utilizando a chave d
, você calcular (ume)d = umade mod m
.Mas
desde de = 1 mod phi(m)
, Euler totient teorema diz-nos que umde é congruente
para um1 mod m -- em outras palavras, você recebe de volta o original a
.
Não existem formas mais eficientes para obter a chave de descriptografia d
sabendo apenas o
chave de criptografia e
e o módulo de elasticidade m
, sem saber o que fatoração m = pq
, então
Criptografia RSA é acreditado ser seguro.