Re: RSA != RSA?

[Sandy Harris <sandy@storm.ca>]

Alexey Kirichenko wrote:

> >Sandy Harris of our team promptly came up with a proof.  So the added lcm
> >is, presumably, an optimization.
> 
> It is an optimization (and obvious one).

The gain is typically tiny. Reducing the operand by a small constant factor

	(p-1)*(q-1)/lcm(p-1,q-1) = gcd(p-1,q-1) 

saves about log2(gcd(p-1,q-1) iterations. Still, worth having since it costs
nothing and always saves at least one iteration.

> >...  It becomes an issue only when a key
> >*pair* is being generated on one system for use by another, and the
> >receiving system is being cautious and checking the key for consistency.
> 
> Then the consistency check should be (mod LCM). ...

Yes.

> So, checking (mod LCM), we check the _necessary_and_sufficient_
> condition, can't be better.
> 
> >And this is an interoperability booby-trap that ought to be noted
> >somewhere.  ...  Preferably it should get explicit mention; at
> >the very least, the IPsec RFCs should reference PKCS#1 as well as the
> >original paper.
> 
> Very true.

I agree.

---

References:

• RSA != RSA?
• From: Henry Spencer <henry@spsystems.net>
• Re: RSA != RSA?
• From: Alexey Kirichenko <Alexey.Kirichenko@F-Secure.com>

---

• Prev by Date: BOF: IP over Bluetooth for 50th Meeting of IETF.
• Next by Date: BOF: IP over Bluetooth for 50th Meeting of IETF.
• Prev by thread: Re: RSA != RSA?
• Next by thread: RE: RSA != RSA?
• Index(es):
  • Main
  • Thread