Multi-prime RSA is now a well known technique (described here): 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 effort saving relative to 2-primes RSA is next to $(k/2)^2$, assuming standard modular multiplication techniques and huge prime factors; and $k$ CPUs can be put to near full use. 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 still under examination in 2013 if my understanding is correct. I'm NOT wanting to be part of a patent war, and that's why I have waited until the end of the opposition period 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 it (which could be essential to an answer).

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.

  • 2
    $\begingroup$ Why do you say that google.com/patents/US4405829 is not about RSA? $\endgroup$ – Dmitry Khovratovich Feb 18 '14 at 13:45
  • $\begingroup$ @Dmitry Khovratovich: I fail to see how I reached this conclusion, and retract that; thanks for pointing it. $\endgroup$ – fgrieu Feb 18 '14 at 18:25
  • $\begingroup$ @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." $\endgroup$ – Robert NACIRI Feb 4 '15 at 8:34
  • 2
    $\begingroup$ @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}$. $\endgroup$ – Robert NACIRI Feb 4 '15 at 8:40
  • 2
    $\begingroup$ @fGrieu, Without wishing to mitigate the subsequent works, the RSA patent had already mentioned these two elements since 1977. However for 3 or more RSA factors, the Garner algorithm, with the recombination principle was already largely detailed in Knuth, vol 2, 1980. This was the essential reason, why I compared all the confidentials threads of this period, as "secret de Polichinelle". With the dramatic increase in VLSI technology, the interest of 3 or more RSA factors, became quickly caduca as well as employing alternative moduli of the form $p^2.q$ Thanks for your valuable feedback. $\endgroup$ – Robert NACIRI Feb 4 '15 at 22:02

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.