Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 Catherine 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
2  
Why do you say that google.com/patents/US4405829 is not about RSA? –  Dmitry Khovratovich Feb 18 at 13:45
    
@Dmitry Khovratovich: I fail to see how I reached this conclusion, and retract that; thanks for pointing it. –  fgrieu Feb 18 at 18:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.