Re: A question about modular exponentiation

From: Vedat Hallac (mvhallac@crosswinds.net)
Date: 04/23/03 

From: "Vedat Hallac" <mvhallac@crosswinds.net>
Date: Thu, 24 Apr 2003 07:37:09 +1000

On Wed, 23 Apr 2003 18:33:20 +0000, Paul Schlyter wrote:

>
> In RSA, keys are usually generated in this way:
>
> 1. Generate two primes, p and q, and compute the modulus n = p * q
>
> 2. Choose a public exponent, e - a common choce is e = 65537
>
> 3. Compute the private exponent from:
>
> d = 1/e mod (p-1)(q-1)
>
>
> One can also compute the private exponent in a slightly different way:
>
> d' = 1/e mod LCM(p-1,q-1)
>
> where LCM(a,b) is the Least Common Multiple of a and b.
>
> Since p and q both are odd, p-1 and q-1 must both be even, and
> LCM(p-1,q-1) is thus always different from (p-1)(q-1) since p-1
> and q-1 at least shares the common factor 2.
>
> I ran tests on this, generating primes to produce RSA keys
> with modulus length of 512, 1024 or 2048 bits. I repeated this
> thousands of times, and gathered some statistics:
>
> In about 40% of the cases, d and d' were the same.
>
> Thus, in about 60% of the cases, d and d' were different. This of
> course also means that in these cases, p and q are most likely not
> "strong" primes.
>
> Next, I did RSA encryptions and decryptions, first using e,d,n and
> then using e,d',n (i.e. the "other" private exponent). In EACH AND
> EVERY ONE OF THOSE THOUSANDS OF CASES, the RSA worked with either of
> the private exponents d and d'. Thus, there are cases where there is
> more than one private exponent which works with each public exponent.
>
> Now, my question is: when d and d' are different, does always both
> of them work with the one and same public exponent e and modulus n ?
>
> I strongly suspect that's the case, however testing thousands of
> times and succeeding every time does of course not prove that's
> always the case, but merely that it's almost always the case.
>
> So I'm looking for some pointer to a mathematical proof that both
> d and d' always work with e and n, whenever d and d' are different.
>
> ----------------------------------------------------------------------
>
> In case someone wonders: "why would you want to compute d' as
> 1/e LCM(p-1,q-1) ? The answer to that question is the digital
> signature algorithm ISO 9697, which suggests a public+private key
> encryption algorithm which does this.
>
> So my real question is: Can every ISO 9697 key also be used as
> an RSA key ?

The short answer to the real question is: Yes, you can.

I will use the following definitions to describe the answer:
lambda:=(p-1)*(q-1)
phi:=LCM(p-1, q-1)

It can easily be seen that

lambda = GCD(p-1,q-1)*phi

Now, this means,

e*d=1+k*lambda=1+k*gcd(p-1,q-1)*phi

Therefore, d is inverse of e both for mod lambda, and for phi. It is the
inverse of d for other numbers as well.

To see how d and d' are related, just do a bit of arithmetic:

e*d'=1+l*phi
e*d - e*d' = 1+k*gcd(p-1,q-1)*phi - 1 - l*phi
e*(d-d') = (k*gcd(p-1,q-1) - l)*phi

Since e cannot divide phi, it must divide the rest, so

d-d' = m*phi.

k, l, and m above are integers whose values are of no concern to us.

Since phi is related to n=p*q, this relation means that whenever d and d'
are different, the difference depends on the modulus, n.

If you want to see why both d and d' work, do a bit of modular
exponentiation:

modexp(a, d, n) = modexp(a, d'+m*phi, n)
  = modexp(a, d', n)*modexp(a, m*phi, n)
  = modexp(a, d', n)*1

Here also lies the answer to why ISO 9697 wants the use of phi instead of
lambda. modexp(a, phi, n) is 1, which causes modexp(a, lambda, n) to be 1
as well, making the keys generated with lambda work. You can also see that
the private keys are not usnique. All values d_i=d' + i*phi which are less
than n would be good private keys. Luckily, phi is not small enough to
make this a problem for the RSA cryptosystem.

Your conclusion that when d and d' are different, p and q must not be
strong primes is also correct, in that m*phi is less than n, and hence phi
is "small" due to a "large" common factor of p-1 and q-1. This also shows
why strong primes are good for RSA.

I hope this helps.

Enjoy,
vedaT

Relevant Pages

  • Re: RSA key size and safety
    ... assymmetric (RSA) will be safe for the next 50 years. ... LEAST 768-bit RSA keys. ... so any time estimates were likely based ... your public keys your system is fairly dead in the water. ...
    (sci.crypt)
  • Re: SSH keys: RSA vs DSA
    ... >> Ssh protocol version 2 can use RSA as well as DSA keys. ... > DSA is an old and fairly weak encryption, ...
    (comp.os.linux.security)
  • Re: CryptoAPI Hard Coding Keys, Help
    ... You can use RSA, DH/DSA or ECDSA - but you should first check what Windows ... // key container name. ... printf(" Create a default container and generate keys \n"); ... "Generating Keys \n"); ...
    (microsoft.public.platformsdk.security)
  • Re: newbie Qs about RSA, OAEP
    ... > Are there recommended minimum/maximum lengths for RSA keys? ... RSA block, you encrypt the message with a block cipher, and encrypt only ... each protocol has its own way of indicating length. ...
    (sci.crypt)
  • Re: RSA - Public vs. Private Keys
    ... private exponent makes RSA trivially breakable. ... small private exponent by using continued fraction is a polynomial time ... Note that 0.292 is improved bounds for Weiner attack by Boneh ...
    (microsoft.public.dotnet.security)