+

CN104125061A - RSA encryption algorithm based attack defending method applied to electronic component - Google Patents

RSA encryption algorithm based attack defending method applied to electronic component Download PDF

Info

Publication number
CN104125061A
CN104125061A CN201410394751.6A CN201410394751A CN104125061A CN 104125061 A CN104125061 A CN 104125061A CN 201410394751 A CN201410394751 A CN 201410394751A CN 104125061 A CN104125061 A CN 104125061A
Authority
CN
China
Prior art keywords
invq
mod
calculating
message
encryption algorithm
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN201410394751.6A
Other languages
Chinese (zh)
Inventor
房伟如
刘忠志
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Beijing KT Micro Ltd
Original Assignee
Beijing KT Micro Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Beijing KT Micro Ltd filed Critical Beijing KT Micro Ltd
Priority to CN201410394751.6A priority Critical patent/CN104125061A/en
Publication of CN104125061A publication Critical patent/CN104125061A/en
Pending legal-status Critical Current

Links

Landscapes

  • Storage Device Security (AREA)

Abstract

The invention relates to an RSA encryption algorithm based attack defending method applied to an electronic component. The RSA encryption algorithm based attack defending method includes the steps of generating random numbers: u, t, s and r; randomizing information x and secret keys including n, p, q, invQ and d with the random numbers u, t, s and r to obtain randomized results x', n', p', q', invQ' and d'; computing to obtain xp, xq, dp, dq, yp, yq and y according to the randomized x', p', q', invQ' and d', wherein p and q refers to two prime numbers which are identical in position length and unequal in size. The RSA encryption algorithm based attack defending method has the advantages that an SCA (side channel attacker) can be prevented from obtaining signatures or secret parameters of a decipherment algorithm via extraneous information of intermediate data processed by a microprocessor, and the effect of attack defending is reached.

Description

Anti-attack method in electronic component using RSA encryption algorithm
Technical Field
The invention relates to the field of anti-attack, in particular to an anti-attack method in an electronic component using an RSA encryption algorithm.
Background
The cryptosystem is divided into a private key cryptosystem and a public key cryptosystem, and represented by a symmetric encryption algorithm DES developed by the national institute of standards and IBM corporation in 1977 and a public key encryption algorithm RSA proposed by R.rivest, A.Shair and L.Adleman in 1978, respectively. The private key cryptosystem is not beneficial to key management and digital signature, but has high speed. Public key cryptosystems may be used for key management and digital signatures, but at a slower rate. The mechanism of the public key cryptosystem is as follows: a pair of keys is generated for each user: a public encryption key and a private decryption key, it must not be possible to find the private decryption key (short: private key) from the public encryption key (short: public key) by calculation. For example: A. when B two parties communicate, A obtains the public key of B through any way, the public key of B is used for encrypting information, the encrypted information is sent through any unsafe channel, and B receives the ciphertext information and then uses the private key thereof to decrypt and recover the plaintext.
The RSA encryption algorithm is used in the smart card, and the method has wide application in the aspects of accessing a database, financial application, remote payment application and the like. The principle of the RSA encryption algorithm can be divided into three different parts:
a first part: generating a pair of RSA keys;
a second part: encrypting a plaintext into a ciphertext; and
and a third part: and decrypting the ciphertext into the plaintext.
Wherein, the first part comprises the following 5 steps:
step one, generating two large prime numbers p and q with the same length and different sizes;
step two, calculating n as p multiplied by q, keeping secret;
step three, randomly selecting an integer e to meet the requirementAnd is
Step four, calculating d to satisfy
And step five, wherein the public key is (e, n) and the private key is (d, p, q).
The second part is calculated according to the following formula: c is me mod n。
The third part is calculated according to the following formula: m ═ cd mod n。
Where m denotes plaintext, c denotes ciphertext, 1< m < n, 1< c < n, e is an encryption exponent, and d is a decryption exponent.
When signature is performed by adopting RSA encryption algorithm, the following formula is calculated: c is md mod n。
From the above analysis, it can be seen that when signature or decryption is performed by using RSA encryption algorithm, it needs to be calculated according to the following formula: y is xdmod n, with the input as message x and the output as message y.
The security of the RSA encryption algorithm is based on the difficulty of factoring large numbers formed by the product of two prime numbers, in other words, given two large prime numbers p and q, it is easy to obtain their product n, but given n, finding out prime numbers p and q is very difficult, due to the fact that a secure RSA algorithm must satisfy that n is long enough, for example: 512 bits, 1024 bits, 2048 bits, etc.
For the RSA encryption algorithm, the longer the key is, the better the encryption effect is, but the larger the overhead of encryption and decryption is. Using the RSA signature or decryption operation of Chinese Remainder Theory (CRT) to calculate the exponential form y of modulo n as xdThe condition that mod n is converted into congruence equation set can improve the speed of signature or decryption operation by about 4 times, and a CRT (cathode ray tube) is usedThe RSA signature or decryption algorithm of (a) may comprise the steps of:
step one, precalculation: dp ═ d mod (p-1), dq ═ d mod (q-1), invQ ═ q mod (q-1)-1mod p;
Step two, calculating: xp ═ x mod p and xq ═ x mod q;
step three, calculating: yp ═ xpdp mod p,yq=xqdq mod q;
Step four, calculating: y ═ yq + q × [ (yp-yq) × invq (mod p) ];
wherein, the input is: n, d, p, q, dp, dq, invQ, c; the output is y ═ xd mod n。
When calculating, using the RSA signature or decryption algorithm of CRT, first perform mod p and mod q operations, where two prime numbers p and q need to have the same bit length but different sizes, and then perform two modular exponentiations, namely: xpdpmod p and xqdqmod q, and combining the calculation results of the modular exponential operation by using a CRT to obtain a plaintext m.
The implementation of the RSA encryption algorithm using CRT on the smart card is vulnerable to SCA (side channel attack) and other channel attacks such as power consumption, execution time, input and output behaviors at the time of failure, and thus reveals key information, wherein a Differential Power Analysis (DPA) attack and an electromagnetic radiation attack (EMA) are very effective attack methods. DPA and EMA attacks exploit the fact that: the instantaneous power consumption or electromagnetic consumption of the cryptographic device depends on the data processed by the device and on the operation performed by the device, the principle being that the smart card consumes power during the execution of the encryption and decryption, generating electromagnetic radiation, which can be detected and analyzed by using special electronic gauges and mathematical statistical techniques, in order to obtain specific critical information in the chip. For example: the energy consumed by the smart card to execute one instruction is related to the operand of the instruction, wherein when a specific bit is unchanged and other bits are changed, the analysis of the current consumption related to the instruction shows that when the specific bit takes the value of 0 or 1, the average energy consumption of the instruction is different, and the specific bit can be determined to be 0 or 1 according to the energy consumption. SCA attacks such as DPA and EMA are therefore likely to get extraneous information of the intermediate data processed by the microprocessor on the card during the execution of the encryption algorithm, which in some cases may reveal secret parameters of the signature or decryption algorithm, making the encryption system insecure.
Disclosure of Invention
The invention provides an anti-attack method in an electronic component using an RSA encryption algorithm, which is used for preventing an SCA attacker from obtaining a secret parameter of a signature or decryption algorithm through additional information of intermediate data processed by a microprocessor so as to achieve the effect of defending against attacks.
The invention provides an anti-attack method in an electronic component using an RSA encryption algorithm, which is adopted to realize that y is x when an RSA signature using a Chinese remainder theorem or a decryption algorithm is executed each timedmod n, the method having as input a message x, a secret key n, p, q, invQ, d, and as output a message y, the method comprising:
generating a random number: u, t, s, r;
randomizing the message x, the secret keys n, p, q, invQ and d by adopting the random numbers u, t, s and r, wherein the randomized result is x ', n', p ', q', invQ 'and d';
calculating according to the randomized x ', p ', q ', invQ ', d ' to obtain xp, xq, dp, dq, yp, yq and y;
wherein p and q are two prime numbers with the same bit length but different sizes.
The invention also provides an anti-attack method in the electronic component using the RSA encryption algorithm, which is adopted each time when the RSA signature or the decryption algorithm using the Chinese remainder theorem is executedUsing said method to realize y ═ xdmod n, the method taking as input a message x, a key n, p, q, invQ, dp, dq, the method comprising:
generating a random number: u, t, s, r, h;
randomizing the message x, the secret keys n, p, q, invQ, dp and dq by using the random numbers u, t, s, r and h, wherein the randomized result is x ', n ', p ', q ', invQ ', dp ' and dq ';
calculating according to the randomized x ', p', q ', invQ', dp 'and dq' to obtain xp, xq, yp, yq and y;
wherein p and q are two prime numbers with the same bit length but different sizes.
In the invention, the RSA signature or the decryption algorithm of the CRT is randomized each time, the secret key of the modular exponential operation of the CRT and the intermediate result are covered, an SCA attacker is prevented from obtaining the secret parameter of the decryption algorithm through the additional information of the intermediate data processed by the microprocessor, and the effect of defending the SCA attack is achieved.
Drawings
FIG. 1 is a schematic flow chart of a first embodiment of an anti-attack method in an electronic component using an RSA encryption algorithm according to the present invention;
fig. 2 is a schematic structural diagram of an attack-prevention device in an electronic component using an RSA encryption algorithm according to a second embodiment of the present invention.
Detailed Description
As shown in fig. 1, which is a schematic flow chart of a first embodiment of the anti-attack method in an electronic component using an RSA encryption algorithm according to the present invention, a method is adopted each time an RSA signature or decryption algorithm using CRT is executed, the method takes a message x, keys n, p, q, invQ, d as inputs, and the method may include the following steps:
step 11, generating random numbers: u, t, s, r;
step 12, randomizing the message x, the secret keys n, p, q, invQ and d by using random numbers u, t, s and r, wherein the randomized results are x ', n', p ', q', invQ 'and d';
wherein, p and q are two prime numbers with the same bit length but different sizes;
and step 13, calculating according to the randomized x ', p ', q ', invQ ' and d ' to obtain xp, xq, dp, dq, yp, yq and y.
The meaning of each parameter is the same as that of the background art, and is not described herein again.
According to the above countermeasure method, it is possible to protect the modular exponentiation y ═ x using CRTdmod n, for example: decryption operation m ═ c of RSA algorithmdmod n and signature operation c ═ md mod n。
In this embodiment, the RSA signature or decryption algorithm using the CRT is randomized each time, d, p, q, invQ using the modular exponentiation of the CRT and the intermediate results xp, xq, dp, dq, yp, yq are masked, so as to prevent the SCA attacker from obtaining the secret parameters of the decryption algorithm through the additional information of the intermediate data processed by the microprocessor, thereby achieving the effect of defending against SCA attacks.
Optionally, in step 12, the following method may be specifically adopted for randomization: n ' ═ uxn, x ' ═ x + n ',p ' ═ p × t, q ' ═ q × s, invQ ' ═ invQ × t; wherein,is an euler function of n.
Optionally, in step 13, specifically, xp, xq, dp, dq, yp, yq, and y may be calculated by the following method:
step 131, calculating xp ═ x 'mod p' and xq ═ x 'mod q';
step 132, calculateAndwherein,euler functions of p 'and q', respectively;
step 133, calculate yp ═ xpdp mod p′,yq=xqdq mod q′;
Step 134, calculating y ═ yq + q ' × [ (yp-yq) × invQ ' (mod p ') ]/(t × s);
step 135, replace y with y mod n.
It should be noted that there is no strict timing relationship between step 13 and step 14.
Optionally, on the basis of not influencing the calculation, partial calculation order can be randomized, and the safety is further improved. For example: the calculation order of the randomization calculation in step 12 is randomized, the calculation order of the modular exponentiations in steps 131 and 132 is randomized, and the calculation order of the modular exponentiations in step 133 is randomized.
Optionally, the calculation order between steps may be randomized on the basis of not affecting the calculation, thereby further improving the security. For example, the order of computation of step 131 and step 132 is randomized; when step 131 is performed and step 132 is performed, x ', p ', q ' are calculated before step 131 is performed, d ' is calculated before step 132 is performed, and invQ ' is calculated before step 134 is performed.
As shown in fig. 2, which is a schematic structural diagram of a second embodiment of the anti-attack apparatus in an electronic component using an RSA encryption algorithm according to the present invention, a method is adopted each time an RSA signature or decryption algorithm using a CRT is executed, the method takes a ciphertext c, a key n, p, q, invQ, dp, dq as input, and the method may include the following steps:
step 21, generating random numbers: u, t, s, r, h;
step 22, randomizing the message x, the secret key n, p, q, invQ, dp, dq by using the random number u, t, s, r, h, wherein the randomized result is x ', n ', p ', q ', invQ ', dp ', dq ';
wherein, p and q are two prime numbers with the same bit length but different sizes;
and step 23, calculating according to the randomized x ', p', q ', invQ', dp 'and dq' to obtain xp, xq, yp, yq and y.
The meaning of each parameter is the same as that of the background art, and is not described herein again.
The difference from the previous embodiment is that the present embodiment generates a random number h along with u, t, s, r four random numbers, and randomizes p, q, dp, dq, invQ and intermediate results mp, mq, but does not randomize a key d.
In this embodiment, the decryption algorithm using the CRT is randomized each time, and p, q, dp, dq, invQ and intermediate results xp, xq, yp, yq calculated using the modular exponentials of the CRT are masked, so as to prevent an SCA attacker from obtaining secret parameters of the decryption algorithm through additional information of intermediate data processed by the microprocessor, thereby achieving the effect of defending SCA attacks.
Optionally, in step 22, specifically, the following method may be adopted for randomization: calculating n '═ uxn, x' ═ x + n ', p' ═ p × t, q '═ qxs, invQ' ═ invQ × t,andh wherein the content of the organic acid is,euler functions of p and q, respectively.
Optionally, in step 22, the following method may also be adopted for randomization: calculating n '═ uxn, x' ═ x + n ', p' ═ p × t, q '═ qxs, invQ' ═ invQ × t,andh wherein the content of the organic acid is,p ', q', respectively.
Alternatively, in step 23, cp, cq, mp, mq, and m may be calculated specifically by the following method:
step 231, calculating xp ═ x 'mod p' and xp ═ x 'mod p';
step 232, calculate yp ═ xpdp′mod p′,yq=xqdq′mod q′;
Step 233, calculating y ═ yq + q ' × [ (yp-yq) × invQ ' (mod p ') ]/(t × s);
step 234, replace y with y mod n.
Optionally, in this embodiment, part of the calculation order may be randomized without affecting the calculation. For example: the order of computation of the randomization computation in step 22 is randomized, the order of computation of the two modular exponentiations in step 231 is randomized, and the order of computation of the two modular exponentiations in step 232 is randomized.
Finally, it should be noted that: although the present invention has been described in detail with reference to the preferred embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the spirit and scope of the present invention.

Claims (7)

1. An anti-attack method in an electronic component using an RSA encryption algorithm, characterized in that said method is employed each time an RSA signature or decryption algorithm using the Chinese remainder theorem is executed to achieve y xdmod n, the method having as input a message x, a secret key n, p, q, invQ, d, and as output a message y, the method comprising:
generating a random number: u, t, s, r;
randomizing the message x, the secret keys n, p, q, invQ and d by adopting the random numbers u, t, s and r, wherein the randomized result is x ', n', p ', q', invQ 'and d';
calculating according to the randomized x ', p ', q ', invQ ', d ' to obtain xp, xq, dp, dq, yp, yq and y;
wherein p and q are two prime numbers with the same bit length but different sizes.
2. The method according to claim 1, wherein the randomizing the message x, the key n, p, q, invQ, d with the random number u, t, s, r is specifically:
n ' uxn, x ' x + n ' are calculated,p ' ═ p × t, q ' ═ q × s, invQ ' ═ invQ × t; wherein,is an euler function of n.
3. The method according to claim 1 or 2, wherein the calculating of xp, xq, dp, dq, yp, yq, and y is specifically:
calculating xp ═ x 'mod p' and xq ═ x 'mod q';
computingAnd
calculate yp ═ xpdp mod p′,yq=xqdq mod q′;
Calculating y ═ yq + q ' × [ (yp-yq) × invQ ' (mod p ') ]/(t × s);
y is replaced by y mod n;
wherein,p ', q', respectively.
4. An anti-attack method in an electronic component using an RSA encryption algorithm, characterized in that said method is employed each time an RSA signature or decryption algorithm using the Chinese remainder theorem is executed to achieve y xdmod n, the method taking as input a message x, a key n, p, q, invQ, dp, dq, the method comprising:
generating a random number: u, t, s, r, h;
randomizing the message x, the secret keys n, p, q, invQ, dp and dq by using the random numbers u, t, s, r and h, wherein the randomized result is x ', n ', p ', q ', invQ ', dp ' and dq ';
calculating according to the randomized x ', p', q ', invQ', dp 'and dq' to obtain xp, xq, yp, yq and y;
wherein p and q are two prime numbers with the same bit length but different sizes.
5. The method according to claim 4, wherein the randomizing the message x, the key n, p, q, invQ, dp, dq with the random number u, t, s, r, h is specifically:
calculating n '═ uxn, x' ═ x + n ', p' ═ p × t, q '═ qxs, invQ' ═ invQ × t,andh wherein the content of the organic acid is,euler functions of p and q, respectively.
6. The method according to claim 4, wherein the randomizing the message x, the key n, p, q, invQ, dp, dq with the random number u, t, s, r, h is specifically:
calculating n '═ uxn, c' ═ c + n ', p' ═ p × t, q '═ qxs, invQ' ═ invQ × t,andh wherein the content of the organic acid is,p ', q', respectively.
7. The method according to claim 4, wherein the calculation of xp, xq, yp, yq, and y is specifically:
calculating xp ═ x 'mod p' and xp ═ x 'mod p';
calculate yp ═ xpdp′mod p′,yq=xqdq′mod q′;
Calculating y ═ yq + q ' × [ (yp-yq) × invQ ' (mod p ') ]/(t × s);
y is replaced by y mod n.
CN201410394751.6A 2014-08-12 2014-08-12 RSA encryption algorithm based attack defending method applied to electronic component Pending CN104125061A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201410394751.6A CN104125061A (en) 2014-08-12 2014-08-12 RSA encryption algorithm based attack defending method applied to electronic component

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201410394751.6A CN104125061A (en) 2014-08-12 2014-08-12 RSA encryption algorithm based attack defending method applied to electronic component

Publications (1)

Publication Number Publication Date
CN104125061A true CN104125061A (en) 2014-10-29

Family

ID=51770334

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201410394751.6A Pending CN104125061A (en) 2014-08-12 2014-08-12 RSA encryption algorithm based attack defending method applied to electronic component

Country Status (1)

Country Link
CN (1) CN104125061A (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107466453A (en) * 2017-03-16 2017-12-12 深圳大趋智能科技有限公司 The method and device of the anti-DPA attacks of DES softwares
CN110730072A (en) * 2019-10-22 2020-01-24 天津津航计算技术研究所 Side channel attack resisting method for RSA password application

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1411644A (en) * 1999-10-14 2003-04-16 格姆普拉斯公司 Countermeasures in Electronic Components Using RSA Type Public Key Encryption Algorithms
CN103209073A (en) * 2013-01-17 2013-07-17 北京昆腾微电子有限公司 Anti-attack method and device in electronic component using Rivest-Shamir-Adleman (RSA) public-key encryption algorithm

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1411644A (en) * 1999-10-14 2003-04-16 格姆普拉斯公司 Countermeasures in Electronic Components Using RSA Type Public Key Encryption Algorithms
CN103209073A (en) * 2013-01-17 2013-07-17 北京昆腾微电子有限公司 Anti-attack method and device in electronic component using Rivest-Shamir-Adleman (RSA) public-key encryption algorithm

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
C. AUMULLER ET AL: ""Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures"", 《CHES》 *
DAVID VIGILANT: ""RSA with CRT: A New Cost-Effective Solution to Thwart Fault Attacks"", 《CHES》 *
JULIANE KRAMER ET AL: ""Weaknesses in current RSA signature schemees"", 《INTERNATIONAL CONFERENCE ON INFORMATION SECURITY AND CRYPTOLOGY》 *

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107466453A (en) * 2017-03-16 2017-12-12 深圳大趋智能科技有限公司 The method and device of the anti-DPA attacks of DES softwares
CN107466453B (en) * 2017-03-16 2020-11-24 深圳大趋智能科技有限公司 Method and device for preventing DPA attack of DES software
CN110730072A (en) * 2019-10-22 2020-01-24 天津津航计算技术研究所 Side channel attack resisting method for RSA password application
CN110730072B (en) * 2019-10-22 2023-02-03 天津津航计算技术研究所 Side channel attack resisting method for RSA password application

Similar Documents

Publication Publication Date Title
EP2553866B1 (en) System and method for protecting cryptographic assets from a white-box attack
US7162033B1 (en) Countermeasure procedures in an electronic component implementing an elliptical curve type public key encryption algorithm
JP2006340347A (en) An authentication system that performs an elliptic curve digital signature encryption process for signing data
Nagaraj et al. Data encryption and authetication using public key approach
JP2008252299A (en) Cryptographic processing system and cryptographic processing method
EP3698262B1 (en) Protecting modular inversion operation from external monitoring attacks
US6914986B2 (en) Countermeasure method in an electronic component using a public key cryptography algorithm on an elliptic curve
US20200287712A1 (en) Method and device to protect a cryptographic exponent
CN103067164A (en) Anti-attack method for electronic components using RSA public key encryption algorithm
US7286666B1 (en) Countermeasure method in an electric component implementing an elliptical curve type public key cryptography algorithm
JP2004304800A (en) Prevention of side channel attacks in data processing equipment
US7903814B2 (en) Enhancing the security of public key cryptosystem implementations
Somani et al. An improved RSA cryptographic system
Houria et al. A comparison between the secp256r1 and the koblitz secp256k1 bitcoin curves
Rui et al. A k-RSA algorithm
KR100772550B1 (en) Secure Message Blinding Method for Power Analysis Attacks
CN104125061A (en) RSA encryption algorithm based attack defending method applied to electronic component
KR101112570B1 (en) Apparatus and Method for digital signature immune to power analysis and fault attacks, and Recording medium thereof
EP3166013B1 (en) Modular exponentiation using randomized addition chains
Mahanta et al. Comparative modular exponentiation with randomized exponent to resist power analysis attacks
Mahanta et al. A randomization based computation of RSA to resist power analysis attacks
Hanley et al. Exploiting collisions in addition chain-based exponentiation algorithms using a single trace
KR20100039048A (en) Method and apparatus of digital signature using crt-rsa modula exponentiation algorithm against fault attacks, and recording medium using it
KR100953716B1 (en) Digital signature method using crt-rsa based bit operation, apparatus and recording medium recording the same
Tunstall et al. Coordinate blinding over large prime fields

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
WD01 Invention patent application deemed withdrawn after publication

Application publication date: 20141029

WD01 Invention patent application deemed withdrawn after publication
点击 这是indexloc提供的php浏览器服务,不要输入任何密码和下载