Re: is it sufficient to solve factoring problem

Christian Siebert a écrit :
For the main question: I think it should be sufficient because 'e*d
\equiv 1 (mod phi(N))' or in other words 'e*d - 1 \equiv 0 (mod
phi(N))'. So 'e*d - 1' is already a multiple of 'phi(N)'. Since you
also know 'N' itself, it should be possible to determine 'phi(N)' using
a greatest common divisor algorithm and maybe Euler's theorem or
similar...

... it is even more simple because the two prime factors are nearly
of the same size in RSA: 'k*phi(N) = k*(p - 1)*(q - 1)'.
Therefore 'k*phi(N) = k*p*q - k*p - k*q + k' which can be rewritten as
'k*phi(N) = k*(N - p - q + 1)'. Since 'N' is much larger than
'p + q - 1', it is easy to find 'k': 'k = ceil(k*phi(N)/N)'.

Small example: The command "openssl genrsa -out rsa.key 100" generates
an RSA key pair with a 100 bit long modulus. Execute
"openssl rsa -in rsa.key -text" to print the key:

modulus 'N' = 1033328981239965908482322556937
public exponent 'e' = 65537
private exponent 'd' = 419137041797792997701877718877

[You'll also get the two prime numbers, but this is what we want to
calculate now.]

1st step: calculate 'k * phi(N) = e*d - 1'
( 'k * phi(N) = 27468984308301959690387960062041948' )

2nd step: calculate 'k = ceil(k * phi(N) / N)' and extract 'phi(N)'
( 'k = 26583' and 'phi(N) = 1033328981239963875047510065156' )

3rd step: use 'phi(N) = (p - 1)*(q - 1)' and 'N = p * q' to find the
factors of 'N'
( 'p, q = (N + 1 - phi(N))/2 +/- sqrt(((N + 1 - phi(N))/2)^2 - N)' )
( 'p, q = 1016717406245891 +/- 19629134555712' )
( => 'p = 1036346540801603' and 'q = 997088271690179' ) ;-)

Yes. But is "e*d - 1" always a multiple of Phi(N)? I mean, knowing
that N,e,d are RSA keys [*], it is sure that "e*d - 1" is divisible
by "p-1" and by "q-1", but is it always divisible by "(p-1)*(q-1)"?

[*] Which makes very probable that d is not "1/e mod Phi(N)" but
"1/e mod lcm(p-1,q-1)".

mm
.

Relevant Pages

  • Re: is it sufficient to solve factoring problem
    ... an RSA key pair with a 100 bit long modulus. ... private exponent 'd' = 419137041797792997701877718877 ...
    (sci.crypt)
  • Re: RSA Decryption with CryptoAPI, key in PEM format
    ... in the format CAPI understands. ... Your code blindly set the public exponent to 65537 - which is ... I reversed the byte order of the key modulus as you suggested, ... PUBLICKEYBLOB format which is a C struct with several elements. ...
    (microsoft.public.platformsdk.security)
  • Help with OpenSSL RSA
    ... I'm writing a little code to do some RSA stuff and I need to extract the ... public exponent and modulus for passing to a browser that will use them ... I can't find suitable documentation so I don't know what method ...
    (comp.lang.ruby)
  • Re: Help with OpenSSL RSA
    ... I'm writing a little code to do some RSA stuff and I need to extract the ... public exponent and modulus for passing to a browser that will use them ... I can't find suitable documentation so I don't know what method ...
    (comp.lang.ruby)