US5870478A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Modular exponentiation calculation apparatus and method
Assignee: Toshiba Corp
•
Filing: 1997-01-24
•
Granted: 1999-02-09
•
Expires: 2017-01-24
Abstract
Abstract In the modular exponentiation calculation apparatus of the present invention, a computer calculates a modular exponentiation C=M E modN (M,N: integral number, E: exponent expressed in base m, C: calculation result expressed in base b). A table generation section calculates values of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1) and generates a table having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements. A first calculation section calculates a multiplication sum ##EQU1## (Ci: value of each digit of C, ej: non-zero value of j-th digit of E, M ej • b i modN: row elements of ej-column of the table) as updated C. A second calculation section calculates C m modN for the updated C. A control section controls the first calculation section and the second calculation section to repeat the calculation for each non-zero value of each digit of E from MSB to LSB by unit of digit.
Inventors
- 👤 Shinichi Kawamura
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 20:49
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/723
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
168 words
A modular exponentiation calculation apparatus for calculating a modular exponentiation C=M E modN (M,N: integral numbers, E: exponent expressed in base m, C: calculation result expressed in base b), comprising: table generation means for calculating values of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1), and for generating a table having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; first calculation means for calculating a multiplication sum ##EQU9## as updated C (wherein Ci: value of each digit of C, ej: non-zerovalue of j-th digit of E, M ej • b i modN; row elements of ej-column of the table); second calculation means for calculating C m modN for the updated C calculated by said first calculation means; and control means for controlling said first calculation means and second calculation means to repeat the calculation for each non-zero value of each digit of E from MSB to LSB by unit of digit.
Claim 2
Dependent Claim
168 words
A modular exponentiation calculation apparatus for calculating a modular exponentiation C=M E modN (M,N: integral numbers, E: exponent expressed in base m, C: calculation result expressed in base b), comprising: table generation means for calculating values of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1), and for generating a table having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; first calculation means for calculating a multiplication sum ##EQU9## as updated C (wherein Ci: value of each digit of C, ej: non-zerovalue of j-th digit of E, M ej • b i modN; row elements of ej-column of the table); second calculation means for calculating C m modN for the updated C calculated by said first calculation means; and control means for controlling said first calculation means and second calculation means to repeat the calculation for each non-zero value of each digit of E from MSB to LSB by unit of digit.
Claim 3
Dependent Claim
32 words
The modular exponentiation calculation apparatus according to claim 1, further including an input means for inputting M as a plain text to be enciphered and N and E as an encryption key.
Claim 4
Dependent Claim
103 words
The modular exponentiation calculation apparatus according to claim 1, wherein said table generation means first calculates each element (M,M • b modN, M • b 2 modN, . . . , M • b n-1 modN) of the 1st column of the table using M and N, second calculates M 2 modN using the elements of the 1st column and M, and third calculates each element (M 2 bmodN, M 2 • b 2 modN, . . . , M 2 • b n-1 modN) of the 2nd column except for M 2 modN of the table using M 2 modN and N.
Claim 5
Dependent Claim
44 words
The modular exponentiation calculation apparatus according to claim 3, wherein said table generation means calculates a multiplication sum ##EQU10## to calculate M 2 modN (wherein Mi: value of each digit of M, M • b i modN: each element of 1st-column of the table).
Claim 6
Dependent Claim
64 words
The modular exponentiation calculation apparatus according to claim 4, wherein said table generation means divides (M 2 modN)b by N to calculate the surplus as M 2 •b modN, divides (M 2 • b modN)b by N to calculate the surplus as M 2 • b 2 midN, and repeats the division untill the surplus as M 2 • b n-1 modN is calculated.
Claim 7
Dependent Claim
59 words
The modular exponentiation calculation apparatus according to claim 3, wherein said table generation means calculates M j modN using the elements of 1st column and M j-1 modN, calculates each element of the jth-column except for M j modN using M j modN and N, and repeats the calculation untill each element of (m-1)th-column of the table is calculated.
Claim 8
Dependent Claim
34 words
The modular exponentiation calculation apparatus according to claim 1, wherein said second calculation means calculates C m modN without the calculation performed by said first calculation means in case of zero value of ej.
Claim 9
Dependent Claim
41 words
The modular exponentiation calculation apparatus according to claim 2, further including an output means for outputting C as an encryption result of the plain text when said first calculation means and second calculation means finish the calculation for LSB of E.
Claim 10
Independent Claim
151 words
A method for calculating a modular exponentiation C=M E modN (M,N: integral numbers, E: exponent expressed in base m, C: calculation result expressed in base b), comprising the step of: calculating value of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1); generating a table in a machine readable memory having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; first-calculating a multiplication sum ##EQU11## as updated C (wherein Ci: value of each digit of C, ej: non-zero value of j-th digit of E, M ej • b i modN: row elements of ej-column of the table); second-calculating C m modN for the updated C calculated at the first-calculating step: and repeating the first-calculating step and the second-calculating step for each non-zero value of each digit of E from MSB to LSB by unit of digit.
Claim 11
Independent Claim
151 words
A method for calculating a modular exponentiation C=M E modN (M,N: integral numbers, E: exponent expressed in base m, C: calculation result expressed in base b), comprising the step of: calculating value of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1); generating a table in a machine readable memory having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; first-calculating a multiplication sum ##EQU11## as updated C (wherein Ci: value of each digit of C, ej: non-zero value of j-th digit of E, M ej • b i modN: row elements of ej-column of the table); second-calculating C m modN for the updated C calculated at the first-calculating step: and repeating the first-calculating step and the second-calculating step for each non-zero value of each digit of E from MSB to LSB by unit of digit.
Claim 12
Dependent Claim
181 words
A computer readable memory containing computer-readable instructions to calculate a modular exponentiation C=M E modN (M,N: integral number, E: exponent expressed in base m, C: calculation result expressed in base b), comprising: instruction means for causing a computer to calculate value of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1); instruction means for causing a computer to generate a table having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; instruction means for causing a computer to calculate a multiplication sum ##EQU12## as updated C (wherein Ci: value of each digit of C, ej: non-zero value of j-th digit of E, M ej • b i modN: row elements of ej-column of the table); instruction means for causing a computer to calculate C m modN for the updated c; and instruction means for causing a computer to repeat the calcution of the multiplication sum and C m modN for each non-zero value of eact digit of E from MSB to LSB by unit of digit.
Claim 13
Dependent Claim
181 words
A computer readable memory containing computer-readable instructions to calculate a modular exponentiation C=M E modN (M,N: integral number, E: exponent expressed in base m, C: calculation result expressed in base b), comprising: instruction means for causing a computer to calculate value of M j • b i modN (b,n,m: constant, j=1,2, . . . , m-1, i=0,1, . . . , n-1); instruction means for causing a computer to generate a table having (m-1)-columns and n-rows in which the calculation values are stored as corresponding elements; instruction means for causing a computer to calculate a multiplication sum ##EQU12## as updated C (wherein Ci: value of each digit of C, ej: non-zero value of j-th digit of E, M ej • b i modN: row elements of ej-column of the table); instruction means for causing a computer to calculate C m modN for the updated c; and instruction means for causing a computer to repeat the calcution of the multiplication sum and C m modN for each non-zero value of eact digit of E from MSB to LSB by unit of digit.
References Cited (Backward Citations)
JPH04362988A
Cited
US5313530A
Cited
US5321752A
Cited
US5274707A
Cited
US5299262A
Cited
US5499299A
Cited
US5349551A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |