Patent US6986054B2 successfully refreshed from Google Patents.
US6986054B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Attack-resistant implementation method
Assignee: Hitachi Ltd
•
Filing: 2001-12-19
•
Granted: 2006-01-10
•
Expires: 2021-12-19
Abstract
Abstract The present invention makes it difficult for unauthorized parties to estimate processing and a secret key based upon the waveforms of power consumption of an IC card chip by changing a processing order in the IC card chip so that it is not estimated by the attackers. In an information processing apparatus comprising storing means having a program storing part for storing programs and a data storing part for storing data, an operation processing unit, means for inputting data to be operated on in the operation processing unit, and means for outputting operation processing results on the data by the operation processing unit, an arithmetic operation method is provided which comprises the steps of: for two integers K 1 and K 2 , when finding a value F(K, A) of a function F satisfying F(K 1 +K 2 , A)=F(K 1 , A)◯F(K 2 , A) (◯ denotes an arithmetic operation in a communtative semigroup S. K designates an integer and A designates an element of S), decomposing the K to the sum of m integers K[ 0 ]+K[ 1 ]+ . . . K[m−1]; using T( 0 ), T( 1 ), . . . T(m−1) resulting from rearranging a string of the m integers 0, 1, . . . m−1 by permutation T (the result corresponds one for one to the integer string 0, 1, . . . m−1); and operating on terms F(K[T( 0 )], A) to F(K[T(m−1)], A) on the right side of F ( K, A )= F ( K[T ( 0 )], A )◯ F ( K[T ( 1 )], A )◯ . . . F ( K[T ( m −1)], A ) . . . (expression 1) in the order of F(K[T( 0 )], A), F(K[T( 1 )], A), . . . F(K[T(m−1)], A) to find F(K, A).
Inventors
- 👤 Masahiro Kaminaga
- 👤 Takashi Endo
- 👤 Takashi Watanabe
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 15:20
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; G06F7/723; H; H04; H04L; H04L9/00; H04L9/002; H04L9/30; H04L9/3006; H04L9/3013; H04L9/302; H04L9/3066; G06F2207/00; G06F2207/72; G06F2207/7219; G06F2207/7223; G06F2207/7252; H04L2209/00; H04L2209/04; H04L2209/043
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
220 words
A method for countering unauthorized decryption comprising a step of scrambling at least one correlation between a data decryption processing in a hardware and at least one respective hardware operational phenomenon by randomly changing at least one arithmetic operation order in the data decryption processing, wherein the correlation is scrambled by an arithmetic operation method implemented by an information processing apparatus comprising the steps of: for two integers K 1 and K 2 , when finding a value F(K, A) of a function F satisfying F(K 1 +K 2 ,A)=F(K 1 , A) ◯ F(K 2 , A) (◯ denotes an arithmetic operation in a communtative semigroup S. K designates an integer and A designates an element of S), decomposing the K to the sum of m integers K[ 0 ]+K[ 1 ]+. . . K[m−1]; using T( 0 ), T( 1 ), . . . T(m−1) resulted from rearranging a string of integers 0, 1, . . . m−1 by permutation T; and operating on terms F(K[T( 0 )], A) to F(K[T(m−1)], A) on the right side of F(K, A)=F(K[T( 0 )], A) ◯F(K[T( 1 )], A) ◯ . . . F(K[T(m−1)], A) . . . (“expression 1”) in an order of F(K[T( 0 )], A), F(K[T( 1 )], A), . . . F(K[T(m−1)], A) to find F(K, A).
Claim 2
Independent Claim
220 words
A method for countering unauthorized decryption comprising a step of scrambling at least one correlation between a data decryption processing in a hardware and at least one respective hardware operational phenomenon by randomly changing at least one arithmetic operation order in the data decryption processing, wherein the correlation is scrambled by an arithmetic operation method implemented by an information processing apparatus comprising the steps of: for two integers K 1 and K 2 , when finding a value F(K, A) of a function F satisfying F(K 1 +K 2 ,A)=F(K 1 , A) ◯ F(K 2 , A) (◯ denotes an arithmetic operation in a communtative semigroup S. K designates an integer and A designates an element of S), decomposing the K to the sum of m integers K[ 0 ]+K[ 1 ]+. . . K[m−1]; using T( 0 ), T( 1 ), . . . T(m−1) resulted from rearranging a string of integers 0, 1, . . . m−1 by permutation T; and operating on terms F(K[T( 0 )], A) to F(K[T(m−1)], A) on the right side of F(K, A)=F(K[T( 0 )], A) ◯F(K[T( 1 )], A) ◯ . . . F(K[T(m−1)], A) . . . (“expression 1”) in an order of F(K[T( 0 )], A), F(K[T( 1 )], A), . . . F(K[T(m−1)], A) to find F(K, A).
Claim 3
Dependent Claim
48 words
The method according to claim 1 , whereby the permutation processing, the permutation T prevents predicting any post-permutation data from pre-permutation data, or the permutation T is performed based on a dummy random number, and whereby the permutation processing is performed each time the expression 1 is performed.
Claim 4
Dependent Claim
56 words
The method according to claim 1 , wherein the S is a commutative semigroup in which, for a set consisting of residues by an integer N (N≧2), the arithmetic operation ◯ of a modular multiplication operation A◯B=A*B mod N is introduced, and the F satisfies F(K, A)=A^K mod N (A^K denotes the K-th power of A).
Claim 5
Dependent Claim
24 words
The method according to claim 1 , wherein the information processing apparatus is installed on an IC card, a cellular phone, or a PDA.
Claim 6
Dependent Claim
25 words
The method according to claim 3 , wherein the integer K is split in a form of K[j]=u*((2^t)^j) (0≦u≦(2^t)−1, t=1, 2, . . . ).
Claim 7
Dependent Claim
55 words
The method according to claim 5 , whereby the permutation processing, the permutation T is performed based on an information source prevents predicting any post-permutation data from pre-permutation data, or the permutation T is performed based on a dummy random number, and whereby the permutation processing is performed each time the expression 1 is performed.
Claim 8
Dependent Claim
25 words
The method according to claim 5 , wherein the integer K is split in a form of K[j]=u*((2^t)^j) (0≦u≦(2^t)−1, t=1, 2, . . . ).
Claim 9
Dependent Claim
138 words
The method according to claim 1 , wherein the S is a Mordell-Weil group on an elliptic curve E defined on a finite field GF(p) (p is a prime number) or GF(2^n) (n is an integer equal to or greater than 1), and an expression F(K,A)=KA is satisfied, wherein the A denotes a point on the elliptic curve E, the KA denotes the arithmetic operation ◯ performed on K number of As such that the KA denotes A◯A◯A . . . ◯A (K number) when the K is positive, or (−A)◯(−A)◯(−A) . . . ◯(−A) (|K|number) when the K is negative, and 0 (the point at infinity) on the E when the K is 0, the ◯ denotes an addition operation in the Mordell-Weil group, and the −A is an inverse in the Mordell-Weil group of the A.
Claim 10
Dependent Claim
18 words
The method according to claim 8 , wherein the information processing apparatus is installed on an IC card.
Claim 11
Dependent Claim
25 words
The method according to claim 8 , wherein the integer K is split in a form of K[j]=u*((2^t)^j) (0≦u≦(2^t)−1, t=1, 2, . . . ).
Claim 12
Dependent Claim
18 words
The method according to claim 10 , wherein the information processing apparatus is installed on an IC card.
Claim 13
Independent Claim
217 words
A method for calculating a value F(K, A) of a function F satisfying F(K 1 +K 2 , A)=F(K 1 , A) ◯ F(K 2 , A) for two integers K 1 and K 2 in an encryption or decryption process of a cryptosystem by means of an information processing device which comprises a processing unit and a memory device, wherein ◯ denotes an arithmetic operation in a commutative semigroup S, K designates an integer, and A designates an element of S, the method comprising: decomposing the value K in the processing unit to m integers K[ 0 ], K[ 1 ], . . . , K[m−1] each of which is a value of a n-bit unit of a binary representation of the value K, wherein the binary representation of the value K is w bit, m*n equals w; and calculating F(K[T( 0 )]*(2^n)^(m−1T[ 0 ]), A) ◯ F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) in the processing unit in an order of F(K[T( 0 ])*(2^n)^(m−1−T[ 0 ]), A), F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A), . . . F(K[T(m−1)*(2^n)^(m−1T[m−1]), A) defined by a string of integers T( 0 ), T( 1 ), . . . T(m−1) which is a random permutation of a string of integers 0, 1, . . . m−1.
Claim 14
Independent Claim
217 words
A method for calculating a value F(K, A) of a function F satisfying F(K 1 +K 2 , A)=F(K 1 , A) ◯ F(K 2 , A) for two integers K 1 and K 2 in an encryption or decryption process of a cryptosystem by means of an information processing device which comprises a processing unit and a memory device, wherein ◯ denotes an arithmetic operation in a commutative semigroup S, K designates an integer, and A designates an element of S, the method comprising: decomposing the value K in the processing unit to m integers K[ 0 ], K[ 1 ], . . . , K[m−1] each of which is a value of a n-bit unit of a binary representation of the value K, wherein the binary representation of the value K is w bit, m*n equals w; and calculating F(K[T( 0 )]*(2^n)^(m−1T[ 0 ]), A) ◯ F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) in the processing unit in an order of F(K[T( 0 ])*(2^n)^(m−1−T[ 0 ]), A), F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A), . . . F(K[T(m−1)*(2^n)^(m−1T[m−1]), A) defined by a string of integers T( 0 ), T( 1 ), . . . T(m−1) which is a random permutation of a string of integers 0, 1, . . . m−1.
Claim 15
Dependent Claim
41 words
The method according to claim 12 , the permutation being performed based on a dummy random number each time the F(K[T( 0 )]*(2^n)^(m−1−T[ 0 ]), A) ◯ F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) is calculated.
Claim 16
Dependent Claim
146 words
The method according to claim 12 , wherein the commutative semigroup S is a Mordell-Weil group on an elliptic curve E defined on a finite field GF(p) or GF(2^n), wherein p is a prime number, n is an integer equal to or greater than 1, and an expression F(K,A)=KA is satisfied, and wherein the value A denotes a point on the elliptic curve E, the value KA denotes the arithmetic operation ◯ performed on K number of As such that the value KA denotes A◯A◯A . . . ◯A when the value K is positive, or (−A)◯(−A)◯(−A) . . . ◯(−A) when the value K is negative, or 0 on the elliptic curve E when the value K is 0, the symbol ◯ denotes an addition operation in the Mordell-Weil group, and the value (−A) is an inverse in the Mordell-Weil group of the value A.
Claim 17
Dependent Claim
16 words
The method according to claim 12 , wherein the information processing device is an IC card.
Claim 18
Dependent Claim
217 words
An information processing device for calculating a value F(K,A) of a function F satisfying F(K 1 +K 2 , A)=F(K 1 , A) ◯ F(K 2 , A) for two integers K 1 and K 2 in an encryption or decryption process of a cryptosystem, wherein ◯ denotes an arithmetic operation in a commutative semigroup S, K designates an integer, and A designates an element of S, the information processing device comprising: a processing unit; and a memory device, wherein the processing unit is adapted to decompose the value K to m integers K( 0 ], K[ 1 ], . . . , K[m−1], each of which is a value of a n-bit unit of a binary representation of the value K, wherein the binary representation of the value K is w bit, m*n equals w, and the processing unit is further adapted to calculate F(K[T( 0 )]*(2^n)^(m−1−T[ 0 ]), A) ◯ F(K[T( 1 )*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) in an order of F(K[T( 0 ))*(2^n)^(m−1−T[ 0 ]), A), F(K[T( 1 )1*(2^n)^(m−1−T)[ 1 ], A), . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) defined by a string of integers T( 0 ), T( 1 ), . . . T(m−1) which is a random permutation of a string of integers 0, 1, . . . m−1.
Claim 19
Dependent Claim
217 words
An information processing device for calculating a value F(K,A) of a function F satisfying F(K 1 +K 2 , A)=F(K 1 , A) ◯ F(K 2 , A) for two integers K 1 and K 2 in an encryption or decryption process of a cryptosystem, wherein ◯ denotes an arithmetic operation in a commutative semigroup S, K designates an integer, and A designates an element of S, the information processing device comprising: a processing unit; and a memory device, wherein the processing unit is adapted to decompose the value K to m integers K( 0 ], K[ 1 ], . . . , K[m−1], each of which is a value of a n-bit unit of a binary representation of the value K, wherein the binary representation of the value K is w bit, m*n equals w, and the processing unit is further adapted to calculate F(K[T( 0 )]*(2^n)^(m−1−T[ 0 ]), A) ◯ F(K[T( 1 )*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) in an order of F(K[T( 0 ))*(2^n)^(m−1−T[ 0 ]), A), F(K[T( 1 )1*(2^n)^(m−1−T)[ 1 ], A), . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) defined by a string of integers T( 0 ), T( 1 ), . . . T(m−1) which is a random permutation of a string of integers 0, 1, . . . m−1.
Claim 20
Dependent Claim
50 words
The information processing device according to claim 16 , wherein the processing unit is adapted to perform the to permutation based on a dummy random number each time the F(K[T( 0 )]*(2^n)^(m−1T[ 0 ]), A) ◯ F(K[T( 1 )]*(2^n)^(m−1−T[ 1 ]), A) ◯, . . . F(K[T(m−1)]*(2^n)^(m−1−T[m−1]), A) is calculated.
Claim 21
Dependent Claim
153 words
The information processing device according to claim 16 , wherein the commutative semigroup S is a Mordell-Weil group on an elliptic curve E defined on a finite field GF(p) or GF(2^n), wherein p is a prime number and n is an integer equal to or greater than 1, and an expression F(K,A)=KA is satisfied, and p 1 wherein the value A denotes a point on the elliptic curve E, the value KA denotes the arithmetic operation ◯ performed on K number of As such that the value KA denotes A◯A◯A . . . ◯A when the value K is positive, or (−A) ◯(−A)◯(−A) . . . ◯(−A) when the value K is negative, or 0 on the elliptic curve E when the value K is 0, the symbol ◯ denotes an addition operation in the Mordell-Weil group, and the value (−A) is an inverse in the Mordell-Weil 25 group of the value A.
Claim 22
Dependent Claim
18 words
The information processing device according to claim 16 , wherein the information processing device is an IC card.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-01-09 | 2009-07-11 | 2010-01-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-01-09 | 2013-07-11 | 2014-01-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-01-09 | 2017-07-11 | 2018-01-10 | $7700.00 | Window Closed / Lapsed |