Prev: Practical applications still using DES
Next: Australian Crypto Regulations
From: yawnmoth on 15 Apr 2010 12:19
Is there any particular reason PKCS#1 sets d to the e modular inverse
lcm(p-1, q-1) as opposed to e modular inverse (p-1) * (q-1)? The RFC
describing PKCS#1 doesn't really elaborate.
From: Pubkeybreaker on 15 Apr 2010 12:20
On Apr 15, 12:19 pm, yawnmoth <terra1...(a)yahoo.com> wrote:
> Is there any particular reason PKCS#1 sets d to the e modular inverse
> lcm(p-1, q-1) as opposed to e modular inverse (p-1) * (q-1)?  The RFC
> describing PKCS#1 doesn't really elaborate.

It is slightly faster.
From: Francois Grieu on 15 Apr 2010 12:53
On 15/04/2010 18:19, yawnmoth wrote:
> Is there any particular reason PKCS#1 sets d to the e modular inverse
> lcm(p-1, q-1) as opposed to e modular inverse (p-1) * (q-1)? The RFC
> describing PKCS#1 doesn't really elaborate.

That RFC does NOT define d as *the* modular inverse, but as *a* modular
inverse. It says

In a valid RSA private key with the first representation, the modulus
n is the same as in the corresponding public key and is the product
of two odd primes p and q, and the private exponent d is a positive
integer less than n satisfying:

ed \equiv 1 (mod \lambda(n))

with \lambda(n) defined as lcm(p-1, q-1), where n = pq

This definition is approriate since it is precisely the condition that
defines a working d, that is such that fro all x, x^(e*d) = x mod n.

The alternate definition that you consider excludes some working d,
including smaller d that allow computing x^d mod n with fewer
multiplications.

Francois Grieu
From: Tom St Denis on 15 Apr 2010 12:56
On Apr 15, 12:53 pm, Francois Grieu <fgr...(a)gmail.com> wrote:
> On 15/04/2010 18:19, yawnmoth wrote:
>
> > Is there any particular reason PKCS#1 sets d to the e modular inverse
> > lcm(p-1, q-1) as opposed to e modular inverse (p-1) * (q-1)?  The RFC
> > describing PKCS#1 doesn't really elaborate.
>
> That RFC does NOT define d as *the* modular inverse, but as *a* modular
> inverse. It says
>
>     In a valid RSA private key with the first representation, the modulus
>     n is the same as in the corresponding public key and is the product
>     of two odd primes p and q, and the private exponent d is a positive
>     integer less than n satisfying:
>
>     ed \equiv 1 (mod \lambda(n))
>
>     with \lambda(n) defined as lcm(p-1, q-1), where n = pq
>
> This definition is approriate since it is precisely the condition that
> defines a working d, that is such that fro all x, x^(e*d) = x mod n.

Strictly speaking that's only true for units in the ring formed modulo
n.

:-)

Tom
 | 
Pages: 1
Prev: Practical applications still using DES
Next: Australian Crypto Regulations