Cryptome DVDs are offered by Cryptome. Donate $25 for two DVDs of the Cryptome 12-years collection of 46,000 files from June 1996 to June 2008 (~6.7 GB). Click Paypal or mail check/MO made out to John Young, 251 West 89th Street, New York, NY 10024. The collection includes all files of,,, and, and 23,000 (updated) pages of counter-intelligence dossiers declassified by the US Army Information and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere worldwide without extra cost.

Web cryptome

26 March 1999

To: cryptography[at]
From: Vin McLellan <vin[at]>
Subject: Silverman on X9.31 RSA Primes
Cc: coderpunks[at],John Young <jya[at]>
Date: Fri, 26 Mar 1999 04:36:03 -0500

        Bob Silverman <bobs[at]> of RSA Labs, in a sci.crypt debate with
Roger Schlafly <nospam.schlafly[at]>, just posted a brief description
of the logic and method by which ANSI X9.31, the new RSA Digital Signature
Standard for Financial Services, mandates the selection of primes for RSA
keys. I thought his terse explanation might be of broader interest.  The
whole exchange, of course, is posted to the sci.crypt newsgroup under the
header: "RSA Key Distribution."


Subject: Re: RSA key distribution
Date: Wed, 24 Mar 1999 15:39:30 GMT
From:  bobs[at]
Newsgroup: sci.crypt

<Gentlemanly fencing with Prof. Schlafly snipped.>


ANSI X9 does crypto standards for the banking community. Bankers are
excessively paranoid. (with multi-billion dollar IMF transactions, I don't
blame them.  They are very worried about liability).

(1) The method I suggested was *forced* upon me because the banking
industry insisted that RSA keys be made from strong primes.  In fact, I
argued long and hard for merely using random primes, but the political
climate was such that such a proposal was doomed to failure.  My views are
exactly opposite to what you think they are. I do NOT advocate strong primes.
The banking industry demanded strong primes, so I gave them a simple and
fast technique for generating them. If you had been present at the meetings,
you would know this.

(2) The method is anything but complicated.  It simply requires that N=pq
have p+/- 1  and  q+/-1  with at least one prime factor >= 100 bits.
This is done by randomly selecting 4 100+ bit primes which are those factors.
One then randomly chooses a starting point to look for p,q and uses the CRT to
construct an arithmetic progression such that every number in the progression
has p,q +/-1 divisible by the 100 bit primes. One sieves out the candidates in
the progression which are divisible by small primes, then progressively tests
the numbers which survive the sieve for primality.  The method is VERY fast.

(3) Please name the "many" experts you cite. The experts (those who know
factoring algorithms) are all in agreement that strong primes are NOT
necessary.  This includes me, Peter Montgomery, A. Lenstra, H. Lenstra,
C. Pomerance,  H. Cohen,  S. Wagstaff Jr., and  H. Williams.  And while
requiring strong primes may not be a mathematical necessity, it makes the
user community more at ease with the standard.  This last fact, in and of
itself, gives value to the technique.

(4) Having a slightly sub-optimal standard now is better than waiting several
years to try to force an optimal one. ANSI standards are voted upon by the
banking industry.  It is they who decide what is acceptable for them to use.

<end Silverman quote>
      Vin McLellan + The Privacy Guild + <vin[at]>
  53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
                         -- <[at]><[at]> --