US6546104B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Montgomery reduction apparatus
Assignee: Toshiba Corp
•
Filing: 1999-03-05
•
Granted: 2003-04-08
•
Expires: 2019-03-05
Abstract
Abstract In a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within the range n≧L with a bit length being represented by L when p is expressed in binary notation, this invention includes an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R, a multiplication section for obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and β calculated by the (α, β) extraction section, an addition section for obtaining α+εβ by adding α calculated by the (α, β) extraction section and εβ calculated by the multiplication section, and a calculation section for obtaining a remainder D=α+β·ε(mod p) which is congruent to α+εβ obtained by the addition section with respect to p as a modulus and is not more than p.
Inventors
- 👤 Atsushi Shimbo
- 👤 Shinichi Kawamura
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 16:17
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/728
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
149 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; a multiplication section for obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and β calculated by said (α, β) extraction section; an addition section for obtaining α+εβ by adding α calculated by said (α, β) extraction section and εβ calculated by said multiplication section; and a calculation section for obtaining a remainder D=α+β·ε(mod p) which is congruent to α+εβ obtained by said addition section with respect to p as a modulus and is not more than p.
Claim 2
Dependent Claim
149 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; a multiplication section for obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and β calculated by said (α, β) extraction section; an addition section for obtaining α+εβ by adding α calculated by said (α, β) extraction section and εβ calculated by said multiplication section; and a calculation section for obtaining a remainder D=α+β·ε(mod p) which is congruent to α+εβ obtained by said addition section with respect to p as a modulus and is not more than p.
Claim 3
Dependent Claim
159 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; a multiplication section for obtaining εβ by multiplying an integer ε satisfying R′ −1 =ε(mod p) and β calculated by said (α, β) extraction section; an addition section for obtaining α+εβ by adding α calculated by said (α, β) extraction section and εβ calculated by said multiplication section; and a calculation section for obtaining (α+εβ)·2 −w (mod p) on the basis of α+εβ obtained by said addition section and w.
Claim 4
Dependent Claim
159 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; a multiplication section for obtaining εβ by multiplying an integer ε satisfying R′ −1 =ε(mod p) and β calculated by said (α, β) extraction section; an addition section for obtaining α+εβ by adding α calculated by said (α, β) extraction section and εβ calculated by said multiplication section; and a calculation section for obtaining (α+εβ)·2 −w (mod p) on the basis of α+εβ obtained by said addition section and w.
Claim 5
Dependent Claim
158 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; multiplication means for obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and β calculated by said (α, β) extraction means; addition means for obtaining α+εβ by adding α calculated by said (α, β) extraction means and εβ calculated by said multiplication means; and calculation means for obtaining a remainder D=α+β·ε(mod p) which is congruent to α+εβ obtained by said addition means with respect to p as a modulus and is not more than p.
Claim 6
Dependent Claim
158 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; multiplication means for obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and β calculated by said (α, β) extraction means; addition means for obtaining α+εβ by adding α calculated by said (α, β) extraction means and εβ calculated by said multiplication means; and calculation means for obtaining a remainder D=α+β·ε(mod p) which is congruent to α+εβ obtained by said addition means with respect to p as a modulus and is not more than p.
Claim 7
Dependent Claim
168 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; multiplication means for obtaining εβ by multiplying an integer ε satisfying R′ −1 =ε(mod p) and β calculated by said (α, β) extraction means; addition means for obtaining α+εβ by adding α calculated by said (α, β) extraction means and εβ calculated by said multiplication means; and calculation means for obtaining (α+εβ)·2 −w (mod p) on the basis of α+εβ obtained by said addition means and w.
Claim 8
Dependent Claim
168 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; multiplication means for obtaining εβ by multiplying an integer ε satisfying R′ −1 =ε(mod p) and β calculated by said (α, β) extraction means; addition means for obtaining α+εβ by adding α calculated by said (α, β) extraction means and εβ calculated by said multiplication means; and calculation means for obtaining (α+εβ)·2 −w (mod p) on the basis of α+εβ obtained by said addition means and w.
Claim 9
Dependent Claim
120 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and calculated β; obtaining α+εβ by adding calculated α and calculated εβ; and obtaining a remainder D=α+β·ε(mod p) which is congruent to obtained α+εβ with respect to p as a modulus and is not more than p.
Claim 10
Dependent Claim
120 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; obtaining εβ by multiplying ε satisfying R −1 =ε(mod p) and calculated β; obtaining α+εβ by adding calculated α and calculated εβ; and obtaining a remainder D=α+β·ε(mod p) which is congruent to obtained α+εβ with respect to p as a modulus and is not more than p.
Claim 11
Dependent Claim
129 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; obtaining εβ by multiplying an integer satisfying R′ −1 =ε(mod p) and calculated β; obtaining α+εβ by adding calculated α and calculated εβ; and obtaining (α+εβ)·2 −w (mod p) on the basis of obtained α+εβ and w.
Claim 12
Dependent Claim
129 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR′+β on the basis of C and R when w represents a word length and R′ represents a value obtained by dividing R by 2 w ; obtaining εβ by multiplying an integer satisfying R′ −1 =ε(mod p) and calculated β; obtaining α+εβ by adding calculated α and calculated εβ; and obtaining (α+εβ)·2 −w (mod p) on the basis of obtained α+εβ and w.
Claim 13
Dependent Claim
111 words
An elliptic curve encryption apparatus comprising: a conversion section for performing Montgomery conversion of data to be encrypted; a calculation section for calculating positive integers C and p subjected to Montgomery reduction on the basis of the data having undergone Montgomery conversion in said conversion section and encryption is parameters for encrypting the data subjected to encryption; said Montgomery reduction apparatus defined in claim 1 , which receives the positive integers C and p calculated by said calculation section; and an inverse conversion section for performing inverse Montgomery conversion of a remainder D obtained by a calculation section in said Montgomery reduction apparatus defined in claim 1 and outputting encrypted data.
Claim 14
Dependent Claim
110 words
An elliptic curve encryption apparatus comprising: a conversion section for performing Montgomery conversion of data to be encrypted; a calculation section for calculating positive integers C and p subjected to Montgomery reduction on the basis of the data having undergone Montgomery conversion in said conversion section and encryption parameters for encrypting the data subjected to encryption; said Montgomery reduction apparatus defined in claim 2 , which receives the positive integers C and p calculated by said calculation section; and an inverse conversion section for performing inverse Montgomery conversion of a remainder D obtained by a calculation section in said Montgomery reduction apparatus defined in claim 2 and outputting encrypted data.
Claim 15
Dependent Claim
152 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; a multiplication section for calculating εβ by multiplying ε satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and β extracted by said (α, β) extraction section; and a calculation section for obtaining E=εβ2 −w (mod p) on the basis of εβ obtained by said multiplication section and w, and obtaining α+E(mod p) on the basis of obtained E and α calculated by said (α, β) extraction section.
Claim 16
Dependent Claim
152 words
A Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising: an (α, β) extraction section for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; a multiplication section for calculating εβ by multiplying ε satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and β extracted by said (α, β) extraction section; and a calculation section for obtaining E=εβ2 −w (mod p) on the basis of εβ obtained by said multiplication section and w, and obtaining α+E(mod p) on the basis of obtained E and α calculated by said (α, β) extraction section.
Claim 17
Dependent Claim
162 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; multiplication means for calculating εβ by multiplying ε satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and β calculated by said (α, β) extraction means; and calculation means for obtaining E=εβ2 −w (mod p) on the basis of εβ obtained by said multiplication means and w, and obtaining α+E(mod p) on the basis of obtained E and α calculated by said (α, β) extraction means.
Claim 18
Dependent Claim
162 words
A computer-readable storage medium having a program code for controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, the program code comprising: (α, β) extraction means for calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; multiplication means for calculating εβ by multiplying ε satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and β calculated by said (α, β) extraction means; and calculation means for obtaining E=εβ2 −w (mod p) on the basis of εβ obtained by said multiplication means and w, and obtaining α+E(mod p) on the basis of obtained E and α calculated by said (α, β) extraction means.
Claim 19
Dependent Claim
131 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; calculating εβ by multiplying ε Satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and calculated β; and obtaining E=εβ2 −w (mod p) on the basis of obtained εβ and w, and obtaining α+E(mod p) on the basis of obtained E and calculated α.
Claim 20
Dependent Claim
131 words
A Montgomery reduction method of controlling a Montgomery reduction apparatus for receiving positive integers C and p and calculating D=C·R −1 mod p by using R defined as R=2 n using an integer n falling within a range n≧L with a bit length being represented by L when p is expressed in binary notation, comprising the steps of: calculating an integer pair (α, β) satisfying C=αR+β on the basis of C and R; calculating εβ by multiplying ε Satisfying R′ −1 =ε(mod p) when w represents a word length and R′ represents a value obtained by dividing R by 2 w and calculated β; and obtaining E=εβ2 −w (mod p) on the basis of obtained εβ and w, and obtaining α+E(mod p) on the basis of obtained E and calculated α.
References Cited (Backward Citations)
US5159632A
Cited
US5271061A
Cited
US5463690A
Cited
US5764554A
Cited
US5724279A
Cited
US5987131A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-04-07 | 2006-10-07 | 2007-04-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-04-07 | 2010-10-07 | 2011-04-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-04-07 | 2014-10-07 | 2015-04-08 | $7700.00 | Window Closed / Lapsed |