Source: http://www.google.com/patents/US7065788?dq=5,742,768
Timestamp: 2014-09-17 19:40:22
Document Index: 650598076

Matched Legal Cases: ['art 5', 'art 13', 'art 12', 'art 13', 'art 12', 'art 5', 'art 13', 'art 14', 'art 12', 'art 13']

Patent US7065788 - Encryption operating apparatus and method having side-channel attack resistance - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsCiphertext X and a constant C having relationships C>p and C>q with respect to secret keys p and q are input, and correction values C−dp and C−dq (dp=d mod (p−1), dq=d mod (q−1)) are obtained. Then, the ciphertext X is multiplied by the constant C. A remainder operation using the secret key p...http://www.google.com/patents/US7065788?utm_source=gb-gplus-sharePatent US7065788 - Encryption operating apparatus and method having side-channel attack resistanceAdvanced Patent SearchPublication numberUS7065788 B2Publication typeGrantApplication numberUS 10/278,838Publication dateJun 20, 2006Filing dateOct 24, 2002Priority dateJan 15, 2002Fee statusPaidAlso published asDE60239520D1, EP1327932A1, EP1327932B1, US20030133567Publication number10278838, 278838, US 7065788 B2, US 7065788B2, US-B2-7065788, US7065788 B2, US7065788B2InventorsJun Yajima, Kouichi Itoh, Masahiko Takenaka, Naoya ToriiOriginal AssigneeFujitsu LimitedExport CitationBiBTeX, EndNote, RefManPatent Citations (4), Non-Patent Citations (8), Referenced by (10), Classifications (11), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetEncryption operating apparatus and method having side-channel attack resistanceUS 7065788 B2Abstract Ciphertext X and a constant C having relationships C>p and C>q with respect to secret keys p and q are input, and correction values C−dp and C−dq (dp=d mod (p−1), dq=d mod (q−1)) are obtained. Then, the ciphertext X is multiplied by the constant C. A remainder operation using the secret key p or q as a remainder value is conducted with respect to the multiplication result. A modular exponentiation operation based on a Chinese remainder theorem is conducted with respect to the remainder operation result, and a correction operation using a correction value C−dp or C−dq is conducted. Thereafter, plaintext Y before being encrypted is calculated.
17. An encryption operating apparatus having side-channel attack resistance according to claim 16, further comprising a Montgomery parameter remainder operating part for conducting a remainder operation to the remainder value p or q as represented by Expression 133 with respect to the Montgomery parameters Rp and Rq Rp′=Rp mod p
Xp=X mod pXq=X mod qYp=Xp dp mod pYq=Xq dq mod q Y=(a(Y q −Y p)mod q)p+Y p (1) where a=p−1 mod q
In the case of using the SPA, the relationship in magnitude between X and p is determined based on the difference in waveform of a power consumption obtained by an operation. More specifically, as shown in FIGS. 1A�1C, assuming that a waveform of a power consumption by an operation A that does not involve a remainder operation is shown in FIG. 1A, and a waveform of a power consumption by an operation B that involves a remainder operation is shown in FIG. 1B, it can be determined from a waveform shown in FIG. 1C of a measured power consumption whether or not the operation B involving a remainder operation has been conducted.
X p ′=X*r mod p X q ′=X*r mod q Yp=Xp′dp mod pYq=Xq′dq mod q Y p ′=Y p *r −dP mod p Y q ′=Y q *r −dq mod q Y′=(a(Y q ′−Y p′)mod q)p+Y p′ (2) where a=p−1 mod q
SUMMARY OF THE INVENTION Therefore, with the foregoing in mind, it is an object of the present invention to provide an encryption operating apparatus and method having side-channel attack resistance, which is safe to the attack using side-channel attack such as timing attack and SPA, and can conduct an operation at a high speed.
X p ′=X*C mod p X q ′=X*C mod q (3)Yp=Xp′dp mod pYq=Xq′dq mod q (4) Y p ′=Y p *C −dp mod p Y q ′=Y q *C −dq mod q (5) Y=(a(Y q ′−Y p′)mod q)p+Y p′ (6) where a=p−1 mod q Because of the above configuration, even in the case where any input is made, a remainder operation is always conducted. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, since a correction value is calculated based on a constant C, an operation for obtaining a correction value only needs to be conducted once, and it can be expected that an operation processing overhead is reduced as a whole.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (7) X p ′=X*R mod p X q ′=X*R mod q (8) Y p=MONT_EXP(X p ′,dp,R,p) Y q=MONT_EXP(X q ′,dq,R,q) (9) where dp=d mod(p−1), dq=d mod(q−1)
Y=(a(Y q ′−Y p′)mod q)p+Y p′ (10) where a=p−1 mod q Because of the above configuration, even in the case where any input is made, a remainder operation is always conducted. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be revealed based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, since it is not required to conduct a correction operation, it can be expected that an operation processing overhead is reduced as a whole.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (11)Rp′=R mod pRq′=R mod q (12) X p ′=X*R p′ X q ′=X*R q′ (13)Xp=Xp′mod pXq=Xq′mod q (14) Y p=MONT_EXP(X p ,d p ,R,p) Y q=MONT_EXP(X q ,d q ,R,q) (15) where dp=d mod(p−1), dq=d mod(q−1)
Y=(a(Y q −Y p)mod q)p+Y p (16) where a=p−1 mod q Because of the above configuration, whether or not a remainder operation is conducted is determined based on the magnitude of the product between the input value and the Montgomery parameter remainder operation result Rp′ or Rq′. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, since it is not required to conduct a correction operation, it can be expected that an operation processing overhead is reduced as a whole.
X p ′=X*C mod p X q ′=X*C mod q (17)Yp=Xp′dp mod pYq=Xq′dq mod q (18) Y p ′=Y p *C −dP mod p Y q ′=Y q *C −dq mod q (19) Y=(a(Y q ′−Y p′)mod q)p+Y p′ (20) where a=p−1 mod q Because of the above configuration, by loading the program onto a computer for execution, even in the case where any input is made, a remainder operation is always conducted. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, a correction value is calculated based on a constant C, so that an operation for obtaining a correction value needs to be conducted once, and an encryption operating apparatus having side-channel attack resistance can be realized in which an operation processing overhead is expected to be reduced as a whole.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (21) X p ′=X*R mod p X q ′=X*R mod q (22) Y p=MONT_EXP(X p ′,dp,R,p) Y q=MONT_EXP(X q ′,dq,R,q) (23) where dp=d mod(p−1), dq=d mod(q−1)
Y=(a(Y q ′−Y p′)mod q)p+Y p′ (24) where a=p−1 mod q Because of the above configuration, by loading the program onto a computer for execution, even in the case where any input is made, a remainder operation is always conducted. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, since it is not required to conduct a correction operation, an encryption operating apparatus having side-channel attack resistance can be realized in which an operation processing overhead is expected to be reduced as a whole.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (25)Rp′=R mod pRq′=R mod q (26) X p ′=X*R p′ X q ′=X*R q′ (27)Xp=Xp′mod pXq=Xq′mod q (28) Y p=MONT_EXP(X p ,dp,R,p) Y q=MONT_EXP(X q ,dq,R,q) (29) where dp=d mod(p−1), dq=d mod(q−1)
Y=(a(Y q −Y p)mod q)p+Y p (30) where a=p−1 mod q Because of the above configuration, by loading the program onto a computer for execution, whether or not a remainder operation is conducted is determined based on the magnitude of the product between the input value and the Montgomery parameter remainder operation result Rp′ or Rq′. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived based on the difference in operation processing time, a wavelength of a power consumption, and the like, which enables a decoding operating method with high security against side-channel attack to be provided. Furthermore, since it is not required to conduct a correction operation, an encryption operating apparatus having side-channel attack resistance can be realized in which an operation processing overhead is expected to be reduced as a whole.
BRIEF DESCRIPTION OF THE DRAWINGS FIGS. 1A to 1C illustrate waveforms of a power consumption.
DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiment 1 Hereinafter, an encryption operating apparatus having side-channel attack resistance in Embodiment 1 according to the present invention will be described with reference to the drawings. Embodiment 1 is characterized in that an input X is multiplied by a constant C that is larger than secret keys p and q, instead of being multiplied by a random number r.
Xp′=X′mod pXq′=X′mod q (32)
Y P = X p ′ ⁢ ⁢ dp ⁢ mod ⁢ ⁢ p = ( X dp * C dp ) ⁢ ⁢ mod ⁢ ⁢ p Y q = X q ′ ⁢ ⁢ dq ⁢ ⁢ mod ⁢ ⁢ q = ( X dq * C dq ) ⁢ ⁢ mod ⁢ ⁢ q ( 33 ) Reference numeral 12 denotes a correction processing part for conducting modular exponentiation operations with respect to the input values X and Y, using the previously calculated correction values C−dp and C−dq stored in the correction value storing part 5. The correction operations are expressed by Expression 34. Since C is a constant, the correction values C−dp and C−dq are also constants. It only needs to conduct operation processing for obtaining correction values C−dp and C−dq once. The correction operation values Yp′ and Yq′ are stored in a correction result storing part 13.
Y p ′ = Y p * C - dp ⁢ mod ⁢ ⁢ p = X dp ⁢ ⁢ mod ⁢ ⁢ p Y q ′ = Y q * C - dq ⁢ ⁢ mod ⁢ ⁢ q = X dq ⁢ ⁢ mod ⁢ ⁢ q ( 34 ) Reference numeral 14 denotes a plaintext output part for calculating plaintext Y before being encrypted as represented by Expression 35 with respect to the correction operation values Yp′ and Yq′ corrected in the correction processing part 12 and stored in the correction result storing part 13. In the case where an input value is the dummy ciphertext Xd, an erroneous calculated value is output; however, there is no problem in a calculated value with respect to side-channel attack.
Y′=(a(Y q ′−Y p′)mod q)p+Y p′ (35) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead that is substantially the same as that of ordinary operation processing. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*C mod p X q ′=X*C mod q (36)
Yp=Xp′dp mod pYq=Xq′dq mod q (37) Y p ′=Y p *C −dp mod p Y q ′=Y q *C −dq mod q (38)
Y=(a(Y q ′−Y p′)mod q)p+Y p′ (39) where a=p−1 mod q Thus, remainder operations and modular exponentiation operations are conducted with respect to the operation results obtained by multiplying the input ciphertext X by the constant C (where C>p and C>q), and thereafter, correction is made, whereby remainder operations are always conducted even in the case where any input is made. Therefore, the relationship in magnitude between the input value and the secret keys p and q cannot be obtained based on the difference in operation processing time and the difference in waveform of a power consumption. Accordingly, an operating apparatus strong to side-channel attack such as timing attack and SPA can be provided.
X p =X*C p X q =X*C q (40)
Xp′=Xp mod pXq′=Xq mod q (41)
Y P = X p ′ ⁢ ⁢ dp ⁢ mod ⁢ ⁢ p = ( X dp * C dp ) ⁢ ⁢ mod ⁢ ⁢ p Y q = X q ′ ⁢ ⁢ dq ⁢ ⁢ mod ⁢ ⁢ q = ( X dq * C q dq ) ⁢ ⁢ mod ⁢ ⁢ q ( 42 ) In the correction processing part 12, the input values X or Xd are corrected to operation results in the case where a modular exponentiation operation is conducted by using the previously calculated correction values Cp −dp and Cq −dq stored in the correction value storing part 5 in accordance with Expression 43. Cp and Cq are constants, so that the correction values Cp −dp and Cq −dq are also constants. The operation processing for obtaining correction values C−dp and C−dq need to be conducted only once. The correction operation values Yp′ and Yq′ are stored in the correction result storing part 13.
Y p ′ = Y p * C - dp ⁢ mod ⁢ ⁢ p = X dp ⁢ ⁢ mod ⁢ ⁢ p Y q ′ = Y q * C - dq ⁢ ⁢ mod ⁢ ⁢ q = X dq ⁢ ⁢ mod ⁢ ⁢ q ( 43 ) Finally, in the plaintext outputting part 14, plaintext Y before being encrypted is calculated as represented by Expression 44, based on the correction operation values Yp′ and Yq′ corrected in the correction processing part 12 and stored in the correction result storing part 13.
Y′=(a(Y q ′−Y p′)mod q)p+Y p′ (44) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain the plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead, in the same way as in multiplication of the constant C. On the other hand, an attacker attempting to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*C p mod p X q ′=X*C q mod q (45)
Yp=Xp′dp mod pYq=Xq′dq mod q (46) Y p ′=Y p *C p −dp mod p Y q ′=Y q *C q −dq mod q (47)
Y=(a(Y q ′−Y p′)mod q)p+Y p′ (48) where a=p−1 mod q Thus, remainder operations and modular exponentiation operations are conducted with respect to the operation results obtained by multiplying the input ciphertext X by the constants Cp and Cq (where Cp>p and Cq>q), and thereafter, correction is made, whereby remainder operations are always conducted even in the case where any input is made. Therefore, the relationship in magnitude between the input value and the secret keys p and q cannot be obtained based on the difference in operation processing time and the difference in waveform of a power consumption. Accordingly, an operating apparatus strong to side-channel attack such as timing attack and SPA can be provided.
N=p(0)α(0) *p(1)α(1) * . . . *p(n)α(n) (49) where n≧2 or α(0)≧2 Thus, the relationships similar to the above-mentioned operations hold even by extending the Chinese remainder theorem to a plurality of numbers which are relatively prime numbers, and an operating apparatus strong to side-channel attack such as timing attack and SPA can be provided.
Embodiment 2 An encryption operating apparatus having side-channel attack resistance of Embodiment 2 according to the present invention will be described with reference to the drawings. In Embodiment 2, Montgomery modular exponentiation operation is applied to a modular exponentiation operation, and a Montgomery parameter R is used in place of a constant C in Embodiment 1.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (50)
R > p ⁢ ⁢ MONT_EXP ⁢ ( XR ⁢ ⁢ mod ⁢ ⁢ p , d , R , p ) ⁢ ⁢ ⁢ = ( ( XR ⁢ ⁢ mod ⁢ ⁢ p ) ⁢ R - 1 ) ⁢ mod ⁢ ⁢ p = X d ⁢ ⁢ mod ⁢ ⁢ P ⁢ ⁢ ( 51 ) The same calculation can be conducted with respect to the other secret key q, so that a modular exponentiation operation value can be obtained directly without conducting a correction operation. This makes it unnecessary to derive a correction value and conduct a correction operation using the correction value, so that an operation processing overhead can be reduced as a whole.
Xp′=X′mod pXq′=X′mod q (53)
Y p=MONT_EXP(X p ′,dp,R,p) Y q=MONT_EXP(X q ′,dq,R,q) (54) where dp=d mod(p−1), dq=d mod(q−1) A function MONT_EXP for conducting the Montgomery modular exponentiation operations is defined by Expression 55.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (55)
Y p ′=X p′dp mod p Y q ′=X q′dq mod q (56)
Y′=(a(Y q ′−Y p′)mod q)p+Y p′ (57) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*R mod p X q ′=X*R mod q (58)
Y p=MONT_EXP(X p ′,dp,R,p) Y q=MONT_EXP(X q ′,dq,R,q) (59) where dp=d mod(p−1), dq=d mod(q−1)
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (60) Yp and Yq in Expression 59 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 61, which makes it unnecessary to conduct a correction operation.
Yp=Xp′dp mod pYq=Xq′dq mod q (61)
Y=(a(Y q −Y p)mod q)p+Y p (62) where a=p−1 mod q Because of the above processing, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p =X*R p X q =X*R q (63)
Xp′=Xp mod pXq′=X q mod q (64)
Y p=MONT_EXP(X p ′,dp,R p ,p) Y q=MONT_EXP(X q ′,dq,R q ,q) (65) where dp=d mod(p−1), dq=d mod(q−1) A function MONT_EXP for conducting the Montgomery modular exponentiation operations is defined by Expression 66.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (66)
Yp′=Xp′dp mod pYq′=X q′dq mod q (67)
Y′=(a(Y q ′−Y p′)mod q)p+Y p′ (68) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*R p mod p X q ′=X*R q mod q (69)
Y p=MONT_EXP(X p ′,dp,R p ,p) Y q=MONT_EXP(X q ′,dq,R q ,q) (70) where dp=d mod(p−1), dq=d mod(q−1)
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (71) Yp and Yq in Expression 70 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 72, which makes it unnecessary to conduct a correction operation.
Yp=Xp′dp mod pYq=X q′dq mod q (72)
Y=(a(Y q −Y p)mod q)p+Y p (73) where a=p−1 mod q Hitherto, in Embodiment 2, the case where N is represented by multiplication of two numbers which are relatively prime numbers (i.e., N=p*q) has been described. However, the Chinese remainder theorem also holds even in the case where N is represented by multiplication of a plurality of numbers which are relatively prime numbers as represented by Expression 74.
N=p(0)α(0) *p(1)α(1) * . . . *p(n)α(n) (74) where n≧2 or α(0)≧2 Thus, the relationships similar to the above-mentioned operations hold even by extending the Chinese remainder theorem to a plurality of numbers which are relatively prime numbers, and an operating apparatus strong to side-channel attack such as timing attack and SPA can be provided.
Embodiment 3 An encryption operating apparatus having side-channel attack resistance of Embodiment 3 according to the present invention will be described with reference to the drawings. In Embodiment 3, a Montgomery modular exponentiation operation is applied to a modular exponentiation operation, and remainder operation values Rp′=R mod p and Rq′=R mod q with respect to a remainder value p or q of a Montgomery parameter R are used in place of the constant C in Embodiment 1 and the Montgomery parameter R in Embodiment 2.
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (75)
R > p ⁢ ⁢ MONT_EXP ⁢ ( ( X * R p ′ ) ⁢ ⁢ mod ⁢ ⁢ p , dp , R , p ) ⁢ ⁢ ⁢ = ( ( ( X * R ⁢ P ′ ) ⁢ ⁢ mod ⁢ ⁢ p ) ⁢ R - 1 ) d ⁢ mod ⁢ ⁢ p ⁢ = ( ( ( X * ( R ⁢ ⁢ mod ⁢ ⁢ ⁢ p ) ) ⁢ mod ⁢ ⁢ p ) ⁢ R - 1 ) d ⁢ mod ⁢ ⁢ p = X d ⁢ mod ⁢ ⁢ p ( 76 ) The same calculation can be conducted with respect to the other secret key q, so that a modular exponentiation operation value can be obtained directly without conducting a correction operation. This makes it unnecessary to derive a correction value and conduct a correction operation using the correction value, so that an operation processing overhead can be reduced as a whole.
Rp′=R mod pRq′=R mod q (77)
X p ′=X*R p′ X q ′=X*R q′ (78)
Xp=Xp′mod pXq=X q′mod q (79)
Y p=MONT_EXP(X p ,dp,R,p) Y q=MONT_EXP(X q ,dq,R,q) (80) where dp=d mod(p−1), dq=d mod(q−1) Yp and Yq in Expression 80 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 81, which makes it unnecessary to conduct a correction operation.
Yp=Xp dp mod pYq=X q dq mod q (81)
Y=(a(Y q −Y p)mod q)p+Y p (82) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*R mod p X q ′=X*R mod q (83)
Xp=Xp′mod pXq=Xq′mod q (84)
Y p=MONT_EXP(X p ,dp,R,p) Y q=MONT_EXP(X q ,dq,R,q) (85) where dp=d mod(p−1), dq=d mod(q−1)
R>pMONT_EXP(X,d,R,p)=(X*R −1)d mod p (86) Yp and Yq in Expression 85 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 87, which makes it unnecessary to conduct a correction operation.
Yp=Xp dp mod pYq=Xq dq mod q (87)
Y=(a(Y q −Y p)mod q)p+Y p (88) where a=p−1 mod q Because of the above processing, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
Rp>pMONT_EXP(X,d,R p ,p)=(X*R p −1)d mod p (89)
R p > p ⁢ ⁢ MONT_EXP ⁢ ( ( X * R p ′ ) ⁢ ⁢ mod ⁢ ⁢ p , dp , R p , p ) ⁢ ⁢ ⁢ = ( ( ( X * ( R p ⁢ ⁢ mod ⁢ ⁢ p ) ) ⁢ R p - 1 ) d ⁢ mod ⁢ ⁢ p = X d ⁢ ⁢ mod ⁢ ⁢ p ⁢ ⁢ ( 90 ) The same calculation can be conducted with respect to the other secret key q, so that a modular exponentiation operation value can be obtained directly without conducting a correction operation. This makes it unnecessary to derive a correction value and conduct a correction operation using the correction value, so that an operation processing overhead can be reduced as a whole.
Rp′=Rp mod pRq′=Rq mod q (91)
X p ′=X*R p′ X q ′=X*R q′ (92)
Xp=Xp′mod pXq=Xq′mod q (93)
Y p=MONT_EXP(X p ,dp,R p ,p) Y q=MONT_EXP(X q ,dq,R q ,q) (94) where dp=d mod(p−1), dq=d mod(q−1) Yp and Yq in Expression 94 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 95, which makes it unnecessary to conduct a correction operation.
Yp=Xp dp mod pYq=Xq dq mod q (95)
Y=(a(Y q −Y p)mod q)p+Y p (96) where a=p−1 mod q Because of the above configuration, an authorized user who knows the secret keys p and q can obtain plaintext Y with an operation processing overhead comparable to the ordinary operation processing overhead even in the case where the Montgomery parameters are varied with respect to the secret keys p and q. On the other hand, an attacker who attempts to analyze without authorization cannot obtain the secret keys by side-channel attack.
X p ′=X*R p mod p X q ′=X*R q mod q (97)
Xp=Xp′mod pXq=Xq′mod q (98)
Y p=MONT_EXP(X p ,dp,R p ,p) Y q=MONT_EXP(X q ,dq,R q ,q) (99) where dp=d mod(p−1), dq=d mod(q−1)
Rp>pMONT_EXP(X,d,R p ,p)=(X*R p −1)d mod p (100) Yp and Yq in Expression 99 become identical with the results obtained by conducting modular exponentiation operations directly, using Chinese remainder theorem, as represented by Expression 101, which makes it unnecessary to conduct a correction operation.
Yp=Xp dp mod pYq=Xq dq mod q (101)
Y=(a(Y q −Y p)mod q)p+Y p (102) where a=p−1 mod q As described above, in Embodiment 3, whether or not the remainder operation is conducted is determined based on the magnitude of the product between the input value and the remainder operation value of the Montgomery parameter R. Therefore, the relationship in magnitude between the input value and the secret key p or q cannot be derived only based on the difference in operation processing time, waveform of power consumption, and the like. Thus, a decoding operating method having high security with respect to side-channel attack can be provided.
N=p(0)α(0) *p(1)α(1) * . . . *p(n)α(n) (103) where n≧2 or α(0)≧2 Thus, the relationships similar to the above-mentioned operations hold even by extending the Chinese remainder theorem to a plurality of numbers which are relatively prime numbers, and an operating apparatus strong to side-channel attack such as timing attack and SPA can be provided.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4723284 *Feb 14, 1983Feb 2, 1988Prime Computer, Inc.Authentication systemUS4979832 *Nov 1, 1989Dec 25, 1990Ritter Terry FFor combining a first data source and a second data source into result dataUS5048086 *Jul 16, 1990Sep 10, 1991Hughes Aircraft CompanyEncryption system based on chaos theoryUS5142577 *Dec 17, 1990Aug 25, 1992Jose PastorMethod and apparatus for authenticating messages* Cited by examinerNon-Patent CitationsReference1Itoh, K., et al., "Fast Implementation of Public-Key Cryptography on a DSP TMS320C6201", Y.Kurihara-Cryptographic Hardware and Embedded Systems, CHES '99 Lecture Notes in Computer Science, vol. 1717, Springer-Verlig, pp. 61-72.2Kocher, Paul C., "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems", Advances in Cryptology-CRYPTO '96, Lecture Notes in Computer Science, vol. 1109, Springer-Verlag, pp. 104-113.3Kocher, Paul, et al., "Differential Power Analysis", Advances in Cryptology-CRYPTO '99, Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, pp. 388-397.4Menezes, A.J., "Handbook of Applied Cryptography", CRC press, 1997, pp. 612-613.5Montgomery, Peter L., "Modular Multiplication Without Trial Division", Mathematics of Computation 44, No. 170, 1985pp. 519-521.6Okamoto, Eiji, "Power Remainder Operation Using Chinese Remainder Theorem; Introduction to Encryption Theory", published Kyoritsu Shuppan, 1993, pp. 96-97 (with English language translation).7Schindler, Werner, "A Timing Attack Against RSA with the Chinese Remainder Theorem", Cryptographic Hardware And Embedded Systems, 2nd International Workshop, CHES 200, Worchester MA, Aug. 17-18, 2000, Proceedings, Lecture Notes In Computer Science, Berlin: Springer, DE, vol. 1965, Aug. 17, 2000, pp. 109-124.8Walter, C.D., "Mongomery Exponentiation Needs No Final Substractions", Electronics Letters, IEE Stevenage, GB, vol. 35, No. 21, Oct. 14, 1999.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS7512231 *Jul 19, 2004Mar 31, 2009Hitachi, Ltd.Computation method for modular exponentiation operation in decryption or signature generationUS8280042 *Jan 19, 2010Oct 2, 2012Fujitsu LimitedDecryption processor and decryption processing methodUS8638927 *Sep 20, 2010Jan 28, 2014Fujitsu LimitedCryptographic processing method, computer readable storage medium, and cryptographic processing deviceUS8689087 *Jan 9, 2009Apr 1, 2014OrangeMethod and entity for probabilistic symmetrical encryptionUS8799343Sep 22, 2011Aug 5, 2014Intel CorporationModular exponentiation with partitioned and scattered storage of Montgomery Multiplication resultsUS20100177887 *May 2, 2008Jul 15, 2010Gemalto SaMontgomery-based modular exponentiation secured against hidden channel attacksUS20100232603 *Jan 19, 2010Sep 16, 2010Fujitsu LimitedDecryption processor and decryption processing methodUS20100281336 *Jan 9, 2009Nov 4, 2010France TelecomMethod and entity for probabilistic symmetrical encryptionUS20110007894 *Sep 20, 2010Jan 13, 2011Fujitsu LimitedCryptographic processing method, computer readable storage medium, and cryptographic processing deviceWO2013043405A2 *Sep 10, 2012Mar 28, 2013Intel CorporationModular exponentiation with partitioned and scattered storage of montgomery multiplication results* Cited by examinerClassifications U.S. Classification726/23, 726/26, 726/28International ClassificationG06F7/72, G06F1/24, G09C1/00Cooperative ClassificationG06F7/723, G06F2207/7238, G06F7/728European ClassificationG06F7/72M, G06F7/72ELegal EventsDateCodeEventDescriptionNov 20, 2013FPAYFee paymentYear of fee payment: 8Nov 18, 2009FPAYFee paymentYear of fee payment: 4Dec 12, 2006CCCertificate of correctionOct 24, 2002ASAssignmentOwner name: FUJITSU LIMITED, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:YAJIMA, JUN;ITOH, KOUICHI;TAKENAKA, MASAHIKO;AND OTHERS;REEL/FRAME:013423/0176Effective date: 20021007RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google