| 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 cryptome.org, jya.com, cartome.org, eyeball-series.org and iraq-kill-maim.org, 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 | jya.com | eyeball-series.org | cryptome.cn

26 March 1999

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

            Bob Silverman <bobs[at]rsa.com> of RSA Labs, in a sci.crypt debate with
    Roger Schlafly <nospam.schlafly[at]cruzio.com>, 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."

            _Vin

    ---------
    Subject: Re: RSA key distribution
    Date: Wed, 24 Mar 1999 15:39:30 GMT
    From:  bobs[at]rsa.com
    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]shore.net>
      53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
                             -- <[at]><[at]> --