RSA computation method for efficient batch processing

• US 4,964,164 A
• Filed: 08/07/1989
• Issued: 10/16/1990
• Est. Priority Date: 08/07/1989
• Status: Expired due to Term

• Current Assignee: Algorithmic Research Limited
• Original Assignee: Algorithmic Research Limited
• Inventors: Fiat, Amos
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Swann, Tod
• Application Number:
  US07/389,915
• Time in Patent Office: 435 Days
• Field of Search: 380/28, 380/37, 380/49, 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A computation for batch processing public key encryption method using a processor. The method batch processes an e1^th root of a first message-data signal, M1, as M1^1/e1, and an e2^th root of a second message-data signal, M2,. where e1 and e2 are relatively prime, using the steps of computing an exponent product, e, by multiplying e1 times e2; computing a message product, M, wherein M=M1 .sup.(e/e1) M2.sup.(e/e2) ; computing a batch root, R, wherein R=M^1/e ; computing the euclidean inverse, t, of e2 modulo e1; and computing R^e2*t /(M1.sup.(e2*t-1)/e1 M2^t), thereby generating M1 .sup.(1/e1). For a plurality of message-data signals, the method batch processes a plurality of message-data-signal roots as the e1, e2, . . ., ek, roots for a plurality of message-data signals, M1, M2, . . . Mk, respectively, where the ei and ej are pairwise relatively prime for i≠j.

Claims

1. A method, using a processor, for batch processing a first message-data-signal root as an e1^th root of a first message-data signal, M1, as M1^1/e1, and a second message-data-signal root as an e2th root of a second message-data signal, M2, an M2^1/e2, where e1 and e2 are relatively prime, comprising the steps, using said processor, of:

computing an exponent product, e, by multiplying el times e2;

computing a message product, M, wherein

space="preserve" listing-type="equation">M=M1.sup.(e/e1) M2.sup.(e/e2) ;

computing a batch root, R, wherein

space="preserve" listing-type="equation">R=M.sup.1/e ;

computing an euclidean inverse, t, of e2 modulo e1; and

computing

space="preserve" listing-type="equation">R.sup.e2*t /(M1.sup.(e2*t-1) M2.sup.t)

thereby generating the first message-data-signal roots M1.sup.(1e1).

2. The method as set forth in claim 1 wherein the step of computing the message product, M, includes the step of computing

3. A method, using a processor, for batch processing a plurality of message-data-signal roots as the e1, e2, . . . , ek, roots for a plurality of message-data signals, M1, M2, . . . Mk, respectively, where the ei and ej are pairwise relatively prime for i≠

j, comprising the steps, using said processor, of;

computing an exponent product, e, by multiplying e1 * e2 * . . . * ek;

computing a message product, M, wherein

space="preserve" listing-type="equation">M=M1.sup.(e/e1) M2.sup.(e/e2) * . . . *Mk.sup.(e/ek) ;

computing a batch root, R, wherein

space="preserve" listing-type="equation">R=M.sup. 1/e;

splitting the batch root, R, into subproducts; and

extracting the message-data-signal roots as the e1, e2, . . . , ek roots of the message-data signals, M1, M2, . . . , Mk, from said subproducts.

4. A method, using a processor, for batch processing a plurality of roots, e1, e2, . . . , en, for a single message-data signal, M1, where the roots ei and ej are pairwise relatively prime for i≠

j, comprising the steps, using said processor, of;

computing an exponent product, e, by multiplying e1 * e2 * . . . * ek;

computing a message product, M, wherein

space="preserve" listing-type="equation">M=M1.sup.(e/e1+e/e2+ . . . +e/ek) ;

computing a batch root, R, wherein

space="preserve" listing-type="equation">R=M.sup.1/e ;

splitting the batch product root, R, into subproducts; and

extracting the roots of the message-data signal, M1, from said subproducts.

5. An apparatus for batch processing a plurality of message-data-signal roots as the e1, e2, . . . , ek, roots for a plurality of message-data signals, M1, M2, . . . Mk, respectively, where the ei and ej are pairwise relatively prime for i=j, comprising:

exponent means responsive to the e1, e2, . . . , ek, roots for computing an exponent product, e, by multiplying e1 * e2 * . . . * ek;

message means responsive to the message-data signals, M1, M2, . . . Mk, for computing a message product, M, wherein

space="preserve" listing-type="equation">M=M1.sup.(e/e1) M2.sup.(e/e2) * . . . *Mk.sup.(e/ek) ;

means coupled to said exponent means and said message means for extracting a batch root, R, wherein

space="preserve" listing-type="equation">R=M.sup.1/e ; and

means coupled to said extracting means for splitting the batch root, R, into subproducts and extracting the message-data signal roots as the e1, e2, . . . , ek roots of the message-data signals, M1, M2, . . . , Mk, from said subproducts.

6. An apparatus for batch processing a plurality of roots, e1, e2, . . . , en, for a single message-data signal, M1, where the roots ei and ej are pairwise relatively prime for i=j, comprising:

exponent means responsive to the e1, e2, . . . , roots for computing an exponent product, e, by multiplying e1 * e2 * . . . * ek;

message means responsive to the message-data signal, M1, for computing a message product, M, wherein

space="preserve" listing-type="equation">M=M1.sup.(e/e1+e/e2)+ . . . +e/ek) ;

means coupled to said exponent means and said message means for extracting a batch root, R, wherein

space="preserve" listing-type="equation">R=M.sup.1/e ; and

means coupled to said extracting means for splitting the batch root, R, into subproducts and extracting the data-signal roots as the e1, e2, . . . ek roots of the message-data-signals, M1, M2, . . . Mk, from said subproducts.