Re: RSA Private Key representation

Giuliano Bertoletti <gbe32241@xxxxxxxxx> wrote:
I was wondering if it's mathematically easy to go back and forth from
the canonical RSA private key representation (modulus + private
exponent) to the CRT form (PRIME_1, PRIME_2, COEFFICIENT, EXP_1, EXP_2).

Use the secret exponent to factor the modulus.

Divide by 2 until the secrect exponent is odd, raise a random number
to that power, then square it until you get 1. If you got -1 before you
got 1, try again. Otherwise, subtract 1 from what you got before 1 and
compute the gcd with the modulus.

Or: Write d = 2^t s, s - odd. Choose random a, find smallest i s.t.
a^(2^i s) = 1 (mod n). If i=0, or a^(2^(i-1) s) = -1 (mod n), try again.
Otherwise compute gcd(n, a^(2^(i-1) s) - 1), which will be a proper
factor of n.

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: RSA Private Key representation
    ... the canonical RSA private key representation (modulus + private ... Use the secret exponent to factor the modulus. ... Divide by 2 until the secrect exponent is odd, ...
    (sci.crypt)
  • Re: RSA Private Key representation
    ... the canonical RSA private key representation (modulus + private ... compute the gcd with the modulus. ... Posted via NewsDemon.com - Premium Uncensored Newsgroup Service ... Unlimited Access, Anonymous Accounts, Uncensored Broadband Access ...
    (sci.crypt)
  • RSA Private Key representation
    ... I was wondering if it's mathematically easy to go back and forth from the canonical RSA private key representation (modulus + private ... Giuliano Bertoletti. ...
    (sci.crypt)
Quantcast