Feasibility of backdoors in RSA key generation

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

Threaded View

Recently in a discussion elsewhere on feasibility of backdoors in
proprietary (non-opensource) software for RSA key generation, I pointed
out the possibility of having one or more real-valued r such that,
choosing q in the neighbourhood of r*p in key generation, one could
easily factor N=p*q with the knowledge of r. Another person (maaartin)
subsequently proposed a more versatile, principally simple and yet
apparently hard to detect backdoor. He suggested first generating a
random number RN of the magnitude of the key desired, then using the
first half of the bits of RN to (in a suitably choosen way) determine
a prime p, and finally finding a prime q that is close to RN/p, giving
N=p*q as the RSA key required.

The secret knowledge needed for an easy factorization of N of course is
the algorithm of computing p, which is apparently fairly widely open to
individual creativeness. It may be remarked that (1) the algorithm
needs not deliver only a unique candidate but can also produce a
limited number of alternative candidates of p for random selection and
(2) the input to the algorithm could be a combination of the first half
of the bits of RN together with some other (partly variable)
informations, e.g. the licence number of the software and the date and
time etc.

According to information supplied by one person most, if not all, CAs
(trust centres) use proprietary software from a few vendors like
Entrust, Certicom, RSA etc. How could one exclude potential existence
of backdoors in such blackbox software that mafias or secret agencies
eventually manage to implant? A scenario that could be fairly critical
IMHO is one in which a backdoor rests dormant all the time until a
critical moment arrives that is particularly favourable for the bad
guys to exploit in order to reap the maximum profit, causing thereby
also indirect effects through mass psychology etc.

A related issue is trustworthiness of CAs. A CA, whose service is used
exclusively within the domain of a firm or organization, can certainly
easily be a trustworthy one. Otherwise, how is one as a rule to develop
trust towards a particular CA? If I don't err, CAs have generally to
work together. Thus a question of mine is: If CAs are involved in
international transactions of common business nature, how many (on
average) different CAs are normally "in effect" ínvolved and hence are
to be directly or indirectly trusted?


M. K. Shen

Re: Feasibility of backdoors in RSA key generation

It is interesting to see a recent news of a start of open source work on
something parallelly important in informatics: "Open Source Parallel
Filesystem Group Launched in Europe", see

In this connection one may also remember some motivations behind EU's
Galileo Project.

M. K. Shen

Site Timeline