While the RSA/Security Dynamics second letter to the P1363 committee
http://grouper.ieee.org/groups/1363/P1363/letters/SecurityDynamics2.jp
g
pretty much alleviates my concerns about using the "RSA" name from a
legal perspective, the two messages below demonstrate why I think an
unambiguous generic name is also needed.
The RSA algorithm with a modulus that is the product of three primes
is a different cryptographic algorithm from RSA with a modulus that
is the product of two primes. In cryptography, a little bit different
is like a little bit pregnant. In particular, the three prime
approach appears more vulnerable to an advance in quadratic sieving
than the two prime approach. I am not saying three prime approach
should never be used, just that its security must be evaluated
separately.
That RSA Security Inc. is considering allowing the use of three prime
moduli under the umbrella of the RSA name doesn't change the fact
that this is a different design. I think it is important to have some
nomenclature (triprime?) that reflects exactly which method is in
use. If I had recommended to a client that they use a particular
product based, in part, on the claim that they employed the RSA
algorithm and it turned out later that they used a triprime modulus,
I would be quite annoyed.
Also, someone sending a secret message using PKC depends on the
security of the recipient's algorithm and keys. With triprime
moduli, there would not even be a change in algorithm to alert the
sender. There needs to be some way to let people know what security
they are getting. I am not aware of any efficient test to distinguish
numbers with two factors from numbers with more than two. Does anyone
know of one?
By the way, I could not find the April 2000 RSA Data Security
Bulletin on three primes at
http://www.rsasecurity.com/rsalabs/bulletins/index.html Is there a
better link?
Arnold Reinhold
At 1:06 PM -0700 7/28/2000, Steve Reid wrote:
>On Thu, Jul 27, 2000 at 03:00:16PM -0400, Arnold G. Reinhold wrote:
>> I like "Biprime Cryptography," or maybe "Biprime Public Key
>> Cryptography," where a biprime is defined as the product of two prime
>> numbers. I doesn't get close to any trademark and it is descriptive
>> of the algorithm.
>
>Sounds like "composite modulus cryptography" which I think has been
>mentioned on the crypto lists before.
>
>"Biprime cryptography" is not really accurate, because RSA doesn't
>require that the modulus be the product of two primes. I seem to
>remember someone (I think it was Richard Schroeppel) a few years ago
>advocating RSA with a three-prime modulus. The idea was that having
>three primes instead of two would not weaken the algorithm in any
>practical way, but it could make CRT operations even faster. It
>wouldn't make the number field sieve any easier because the number of
>primes doesn't affect NFS workfactor. It would make (I think) the
>quadratic sieve more efficient, but at normal keysizes (1024 bits?) the
>three primes would all be large enough that quadratic sieve would still
>be less efficient than the number field sieve.
At 6:26 PM -0400 7/28/2000, dmolnar added:
>...
>Note that Compaq is trying to push this under the name "Multiprime."
>Bob Silverman has a nice analysis of the number of factors and size of
>factors vs. security tradeoff in the April 2000 RSA Data Security
>bulletin. It's only in the PDF version (or was), though.
>PKCS #1 is also being amended to allow for multiple distinct primes.
...
