Silverman on X9.31 RSA Primes

Vin McLellan (vin@shore.net)
Fri, 26 Mar 1999 04:36:03 -0500

• Next message: Robert Hettinga: "MicroMint demo program"
• Previous message: Vin McLellan: "Georgoudis on AES2, Day 2, Rome (FW)"

        Bob Silverman <bobs@rsa.com> of RSA Labs, in a sci.crypt debate with
Roger Schlafly <nospam.schlafly@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@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@shore.net>
  53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
                         -- <@><@> --

• Next message: Robert Hettinga: "MicroMint demo program"
• Previous message: Vin McLellan: "Georgoudis on AES2, Day 2, Rome (FW)"