[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Anderson's RSA Trapdoor Can Be Broken*From*: Matt Thomlinson <[email protected]>*Date*: Mon, 28 Mar 1994 17:13:17 -0800 (PST)*Sender*: [email protected]

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. [email protected] -------------------------- 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: [email protected] phone: (206) 548-9804 PGP 2.2 key available via email or finger [email protected]

- Prev by Date:
**Re: Shirt project** - Next by Date:
**Re: cfp '94 transcript** - Prev by thread:
**please ignore this test message** - Next by thread:
**Citizen-Unit May fulfils Duty** - Index(es):