Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Feasibility of constructing backdoors in nonopensource RSA software
Posted:
Oct 31, 2011 8:09 PM


RSA public key cryptography relies on the general computational difficulty of factorizing a product of two large primes to fulfill its purposes. Nonopensource software that are used to generate such keys are clearly by nature potentially susceptible of being secretly implanted with backdoors by Mafia & Co. that render the factorization task easy, thus enabling the security of the communications involved to be compromised. From diverse internet discussions the following apparently feasible ways of subverting the RSA scheme are known to me to date:
1. The software contains a predetermined list of public keys and their corresponding private keys. These are somehow randomly selected and output by the software on demand. A recent posting in a usenet group (de.comp.security.misc) claims that the current versions of PGP that are available in a large part of the world outside US have this rather simple backdoor as a consequence of the US export regulations that prohibit exportation of strong crypto. (I have no knowledge to check that claim.)
2. A little bit more complex method consists in storing in the software a predetermined list of the approximate values of the ratios of the two prime numbers that are to be chosen to form the public keys. Each time when a key is to be generated by the software, one of the ratios from the list is somehow randomly selected and used. It is clear that the factorization of N = P * Q is highly facilitated by knowing the approximate value of P/Q.
3. An idea for a more involved and consequently more difficult to be detected method stems from the following observation: If one requires the key to be a number of n digits and specifies in addition that k of its leading digits (say k is about 1/4 of n) to be a constant M, then there exist under these constraints in general lots of pairs of prime numbers P_i and Q_i such that the product N_i = P_i * Q_i is a reasonable candidate for a RSA key. This means that, conversely, one could rather flexibly choose a function f(M) such that, given an arbitrary k digit value M, P = f(M) is a prime and at the same time one can always find another prime number Q to result in a reasonable pair of primes for a RSA key that satisfies the condition that N = f(M) * Q = P * Q is a n digit number and further has M as its k leading digits. (Note that a small amount of variation of the trailing digits of Q doesn't have any influence on the leading digits of the product N, which ensures the existence of the prime Q in general. Digits in our argument could of course be replaced by bits, if desired.) Thus f, if appropriately designed, could serve as a backdoor of the software which, on generating a n digit RSA key, first somehow randomly chooses a k digit number M and then determines P and Q as described above to output a key N, which can be readily factorized with knowledge of f, which appears however to the uninitiated outsiders as if it were the product of two entirely randomly chosen primes (under the general constraints for RSA keys), in which case the factorization would have been computationally infeasible.
Does anyone happen to know or have ideas of additional and perhaps more elegant methods?
M. K. Shen



