Anderson's RSA Trapdoor Can Be Broken

[Matt Thomlinson <phantom@u.washington.edu>]

The name of the article I cited earlier is in the subject line. Written 
by Burton S. Kaliski Jr, of RSA Labs, on **March 19, 1994**. An abstract:


-------------
	A recent letter by Ross Anderson proposes a ``trapdoor'' in the
RSA public-key cryptosystem whereby ahardware device generates RSA primes
p and p' in such a way that the hardware manufacturer can easily factor
the RSA modulus n = pp'. Factoring the modulus hopefully remains difficult
for all other parties. 

	The proposed trapdoor is based on a secret value A known only to 
the manufacturer. For 256-bit RSA primes, the secret value A is 200 bits 
long. The device generates primes p of the form

p = rA + q = r(q,A)A + q. (1)

where q is at most about 100 bits long, and  is 56 bits long and a 
function of A and q. To factor the RSA modulus n = pp', the manufacturer 
reduces the modulus modulo A to recover the product qq', following the 
relationship 

n = pp' = rr'A^2 + (rq' + r'q)A + qq'. (2)

	The 200-bit product qq' is easily factored and the manufacturer
recovers the primes p and p' accordingly. 


	While the trapdoor is indeed practical, it can be broken:
Factoring such ``trapped'' moduli is easy. 

[...goes into easy-to-tex, hard-to-ascii derivation...]

...Such inequalities are called ``simultaneous Diophantine 
approximations,'' ... [and these will be solvable for these parameter 
lengths when (number of keys) >= 13]

[...]


	One way to overcome this attack is to assign a different secret
value to each device [...] The user does not need 14 moduli to find A,
however.  Two prime factors p and p' suffice, since the fraction r'/r is
such a good approximation to the fraction p'/p that it is guaranteed to be
a convergent in the continued fraction expansion of p'/p. The user can
therefore detect a trapdoor even if the device generates each modulus with
a different secret value. 

	The manufacturer's only recourse, at least as far as the proposed
trapdoor is concerned, is for the device to generate each modulus with a
different secret value and to keep the prime factors secret. In such a
sitiation, the manufacturer may as well preload the device with the primes
and escrow copies--a practical ``trapdoor'' to which all cryptosystems,
not just RSA, are vulnerable. 


burt@rsa.com

--------------------------
check out rsa.com for the real copy: I left out about 3 equations 
relating to the diophantine approximations, but the text is pretty much 
copied in its entirety. 



Matt Thomlinson                               Say no to the Wiretap Chip!
University of Washington, Seattle, Washington.
Internet: phantom@u.washington.edu      	    phone: (206) 548-9804
PGP 2.2  key available via email or finger phantom@hardy.u.washington.edu