Para o RSA, como faço para calcular o segredo de expoente?

Question

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

Answer 1

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 (um^e)^d = uma^de mod m.Mas desde de = 1 mod phi(m), Euler totient teorema diz-nos que um^de é congruente para um¹ 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.