Groups | Search | Server Info | Login | Register

Groups > comp.security.misc > #279

Feasibility of constructing backdoors in non-open-source RSA software

Show all headers | View raw

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

Back to comp.security.misc | Previous | Next — Next in thread | Find similar

Thread

Feasibility of constructing backdoors in non-open-source RSA software Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-11-01 09:42 +0100
  Re: Feasibility of constructing backdoors in non-open-source RSA software unruh <unruh@physics.ubc.ca> - 2011-11-01 15:26 +0000
    Re: Feasibility of constructing backdoors in non-open-source RSA software Barry Margolin <barmar@alum.mit.edu> - 2011-11-02 00:10 -0400
    Re: Feasibility of constructing backdoors in non-open-source RSA software Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-11-03 21:45 +0100

csiph-web