Take the 2-minute tour ×

Multi-prime RSA is now a well known technique: it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed boost in private-key operation, with little (conjectured) reduction in security for small-enough $k$; the speedup factor relative to 2-primes RSA is next to $(k/2)^2$, assuming standard modular multiplication techniques and huge prime factors. In early 2000, Compaq was publicizing its use of Multi-prime RSA. There has been earlier realization it was possible and had an interest, and even some uses at least at a prototype stage (I'll describe some).

The question is: Who first published that technique, mentioning its interest?

From a patent standpoint the question appears all settled: the inventors are Thomas Collins, Dale Hopkins, Susan Langford, and Michael Sabin, describing Multi-prime RSA in patent US 5,848,159 following provisional application 60/033,271 filed Dec. 9, 1996, and patent US 7,231,040. Patenting is a slow process: one European version of these patents, EP0950302, was until recently under examination, and the opposition period has been over for just days, if my understanding is correct. I'm NOT wanting to be part of a patent war, and that's why I have waited to ask this question here.

Ronald Rivest, Adi Shamir, and Leonard Adleman themselves, in their patent US 4,405,829 filed Dec. 14, 1977, on a Cryptographic communications system and method we now know as RSA, already mention:

the present invention may use a modulus $n$ which is a product of three or more primes (not necessarily distinct). Decoding may be performed modulo each of the prime factors of $n$ and the results combined using "Chinese remaindering" or any equivalent method to obtain the result modulo $n$

However it is not clear that the motivation or effect is a speedup, which matters to the present question. Here are some of the arguments used to repel that prior art during the lengthy examination process of EP0950302.

Using CRT for a speedup in 2-factors RSA has been known since at least 1982, with the publication by Jean-Jacques Quisquater and Chantal Couvreur of Fast decipherement algorithm for RSA public-key cyptosystem. But the article has no mention of more than two factors.

By 1993-1994, several persons in the European crypto/Smart Card microcosm fully realized the interest of Multi-prime RSA. When asked in mid-December 1993 to inventory valuable knowledge about RSA that our company had, with attribution, I wrote that I had learned about RSA with 3 primes from Professor Jean-Jacques Quisquater on November 30, 1993. The context was trying to make a not-unbearably-slow software-only implementation of RSA in an 8-bit Smart Card intended as a signing tool for medical acts. The technique was described in the (confidential) answer to an official tender made in March 1994, with the technique described to experts of the jury, including Marc Girault, who went as far as confirming our arguments that given the state of the factoring art, our proposal to use 4-factors 768 bit keys, and 3-factors 528-bit keys, was reasonable. I was told some year(s) later (and can't be sure) that the winners of that early CPS tender used similar techniques. I was then working under at least a moral non-disclosure agreement about such speedup techniques; and my memo, or the work of Jean-Jacques Quisquater in that area, remained unpublished for years AFAIK.

Also, patent US 7,231,040 mentions a document RSA Moduli Should Have 3 Prime Factors, August 1996, cited by the examiner, with attribution to Captain Nemo (sic though depending on source, either Captain or the date is missing), which title seems very relevant, but that I have been unable to locate.

Update: the earliest published implementation of the RSA private-key function, using the CRT, and clearly engineered for more than two factors, that I located so far, is Michael Scott's MIRACL library version 3.23, released on January 1994. File DECODE.C (modification date October 1993) contains:

np=2; /* two primes - could be used with more */

However I located no accompanying indication that using more than two factors allows a speedup at constant modulus size, or with similar security.

share|improve this question
Why do you say that google.com/patents/US4405829 is not about RSA? –  Dmitry Khovratovich Feb 18 '14 at 13:45
@Dmitry Khovratovich: I fail to see how I reached this conclusion, and retract that; thanks for pointing it. –  fgrieu Feb 18 '14 at 18:25
@DmitryKhovratovich: Thank for your link, it's important to notice that the RSA patent contains all the features attribuated to other inventors. Snipped for the RSA pattent 1977. "... In alternative embodiments, the present invention may use a modulus n which is a product of three or more primes (not necessarily distinct). Decoding may be performed modulo each of the prime factors of n and the results combined using "Chinese remaindering" or any equivalent method to obtain the result modulo n." –  Robert NACIRI Feb 4 at 8:34
@fgrieu: Not Catherine but Chantal Couvreur, she was in same industrial group, and a good mathematician. The paper she published with JJQ as a co-author is great! But experiment with 3 or more RSA factors was know by everyone and is a "secret de polichinelle". In my compagny we trained with 3 modulus factors on embedded systems with very low ressources in the $90^{ies}$. –  Robert NACIRI Feb 4 at 8:40
@Robert NACIRI: I now have put the correct first name (my mistake, JJQ had given me the correct one, and details about how an early version of the paper, not published, mentioned more than two factors). $\;$ I concur with you that the interest of RSA with 3 factors as a speedup technique was known by those who cared to listen or think in 1995, perhaps earlier; but the question asks: who first published on that subject, turning that secret de polichinelle into public knowledge? –  fgrieu Feb 4 at 10:19

Your Answer



Browse other questions tagged or ask your own question.