In article <[EMAIL PROTECTED]>,
John Gilmore <[EMAIL PROTECTED]> 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. [...]
>
> 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?)
El Gamal-style keys are probably more interesting in this context than
RSA keys. RSA uses new primes for each public key, so inserting a fake
"prime" only spikes a single RSA key, but El Gamal systems often re-use
one prime (modulus) for many many keys.
Replacing the intended-to-be-prime modulus of an El Gamal (or
Diffie-Hellman or DSA) system with a composite of your choosing looks
like a fairly tempting -- and perhaps practical -- way to add a backdoor.
Let's say you replace that 640-bit modulus with a product of two 320-bit
primes which only you know.
Then, recovering traffic encrypted with the system is easy -- for you,
and you only. You get to break the system by doing a pair of discrete
log computations mod each 320-bit prime (mumble mumble Chinese Remainder
Theorem), and that's a LOT easier than a single discrete log computation
mod a 640-bit prime, perhaps almost routine for someone with the
resources of a large government. Noone else gets to play these games,
because they'd have to factor a 640-bit number to find the shortcut.
Your competitive advantage is ensured.
Sure, someone might notice if they test the primality of the modulus, but
when's the last time you did that during a code review? If we're talking
about closed-source systems, maybe only the original coder ever bothers.
It might actually work, say, half the time, and that's scary.
And, from the point of view of someone like an intelligence agency,
it might look pretty tempting, because they get to insert a trapdoor
without much fear that anyone else will exploit it -- thus, one could
imagine the NSA (or whoever) rationalizing it on the grounds that they
don't have to worry that it'll endanger national security too much.
Perhaps it'd never happen, but it's still unsettling to know that it
/could/ happen.
