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