Posted by Common Right Group on September 27, 1997 at 05:29:35:

In Reply to: Email and privacy posted by Two Cities on September 26, 1997 at 14:56:20:

: FYI

: **************************************************

: Since I am new to this, perhaps someone could provide

: some answers to the following PGP and RSA security

: concern of mine.

: The source code for both PGP and RSA suggests that

: the two most significant bits are set by default when

: selecting the constituent primes (p,q) for the generation of

: the modulus (m). For an n-bit m, p and q both start out

: as members of the range 75% 2^(n/2) to 99.9999...% 2^(n/2).

: The resulting return value of m is thus confined to

: 56.25% 2^n to 99.9999...% 2^n, and supposedly factoring is

: hard.

: However, for return values of the modulus at the extremes of

: the available range, only a limited range of target candidate

: primes are worthy of consideration.

: I.e. the factorization of approx. 56.25% 2^n is by neccessity of

: construction approx. 75% 2^(n/2) and some other number in close

: proximity. No other inputs need to be considered. Since the

: remaining bits are assigned 'randomly', a significant statistical

: sample of modulus, will therefore fall close to the extremes of

: the possible range, and can be identified by sight, as potentially

: weak keys, and my conclusion is that not all keys are created

: equal.

: Worse than the above somewhat technical discussion, is the

: notion that what I wrote could have merit, and that it was

: pointed out by a novice. Do tell me that I am wrong.

: Posted to alt.security.pgp

It's been a few years since working at what training and education says, Electronics Engineering Assistant. Never was that proficient in the finer points of the more involved math anyway.

However, what we do know is that the keys are generated on the basis of random prime numbers, now using mostly 64 and 128 bit primaries. The decryption key is the first one generated at the site of origin, so it never leaves that site. The encription key (Public Key) is derived from the decryption key, but leaves no trai to the decription key. Also, an encoded mesage may be encoded again and again, to musltiple tiers, thus adding to the problem of "cracking" the key(s), as each key is a separate problem.

Now, your so-called Novice may have tripped onto something, but has failed to explain why the government has hated and feared RSA/pkc ==>PGP since the days when R,S, and A first developed their algorithm in primitive form back in the late '70's or early '80's. At that time, analysts said it would take two Cray-1's, running 24 hrs per day, about 1,000 years to crack a 64 bit key, except for random "hits," not unlike striking it rich in the lottery.

That's our response. Now we're waiting for the "experts" to show an example of a few keys they have cracked.