US4964164A
Expired / Lapsed
US
⏱️ 0.0 years remaining
RSA computation method for efficient batch processing
Assignee: Algorithmic Research Ltd
•
Filing: 1989-08-07
•
Granted: 1990-10-16
•
Expires: 2009-08-07
Abstract
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.
Inventors
- 👤 Amos Fiat
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 05:21
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; H04L9/32; H04L9/3247; H04L9/3249
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
108 words
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 M=M1.sup.(e/e1) M2.sup.(e/e2) ; computing a batch root, R, wherein R=M.sup.1/e ; computing an euclidean inverse, t, of e2 modulo e1; and computing R.sup.e2*t /(M1.sup.(e2*t-1) M2.sup.t) thereby generating the first message-data-signal roots M1.sup.(1e1).
Claim 2
Independent Claim
108 words
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 M=M1.sup.(e/e1) M2.sup.(e/e2) ; computing a batch root, R, wherein R=M.sup.1/e ; computing an euclidean inverse, t, of e2 modulo e1; and computing R.sup.e2*t /(M1.sup.(e2*t-1) M2.sup.t) thereby generating the first message-data-signal roots M1.sup.(1e1).
Claim 3
Dependent Claim
36 words
The method as set forth in claim 1 wherein the step of computing the message product, M, includes the step of computing M=M1.sup.(e/e1+e/e2), when the first message-data signal is identical to the second message-data signal, M1=M2.
Claim 4
Independent Claim
128 words
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 M=M1.sup.(e/e1) M2.sup.(e/e2) * . . . *Mk.sup.(e/ek) ; computing a batch root, R, wherein 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.
Claim 5
Independent Claim
128 words
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 M=M1.sup.(e/e1) M2.sup.(e/e2) * . . . *Mk.sup.(e/ek) ; computing a batch root, R, wherein 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.
Claim 6
Independent Claim
100 words
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 M=M1.sup.(e/e1+e/e2+ . . . +e/ek) ; computing a batch root, R, wherein 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.
Claim 7
Independent Claim
100 words
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 M=M1.sup.(e/e1+e/e2+ . . . +e/ek) ; computing a batch root, R, wherein 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.
Claim 8
Independent Claim
167 words
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 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 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.
Claim 9
Independent Claim
167 words
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 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 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.
Claim 10
Independent Claim
145 words
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 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 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.
Claim 11
Independent Claim
145 words
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 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 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.
References Cited (Backward Citations)
US4200770A
Cited
US4218582A
Cited
US4405829A
Cited
US4424414A
Cited
US4514592A
Cited
US4567600A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-10-15 | 1994-04-16 | 1994-10-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-10-15 | 1998-04-16 | 1998-10-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-10-15 | 2002-04-16 | 2002-10-16 | $7700.00 | Window Closed / Lapsed |