At 03:48 PM 5/23/00 -0700, John Gilmore wrote:
>... I have a well-founded rumor that a major Silicon Valley company was
>approached by NSA in the '90s with a proposal to insert a deliberate
>security bug into their products. They declined when they realized
>that an allegation of the bug NSA wanted (using a "large prime" that
>was really composite) would be detectable and verifiable by customers
>and competitors. ...
>
>Turning down the offer on verifiability grounds left them wondering
>whether they really would have done it if it'd been possible to keep
>the whole thing secret. ...
>
>Anybody tested the primes in major products lately?
>
>Did you ever wonder how certain companies' products got export licenses
>when other similar companies just couldn't export?
>
>How hard is it to factor a product of two primes when one of them isn't
>really prime? (I.e. to factor a product of three primes?)
Testing primes is easy.
Testing the proper construction of an RSA composite modulus is trickier.
It's been shown that one can prove a modulus of questionable origin
to be composed of just two large primes, without revealing the factors.
(See M. Liskov and R. Silverman, "A Statistical Limited-Knowledge Proof
for Secure RSA Keys".)
But none of these approaches will guarantee that your numbers
aren't just chosen from a small secret dictionary. A smart evil
conspirator can just use "not-so-random" number generator.
Apparently a simple mistake, this gives the bad guy plausible
deniability.
---------------------------------------------------
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
www.IntegritySciences.com
