Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Feasibility of constructing backdoors in non-open-source 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. Non-open-source 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
|
|
|
|
