CN110730072B - Side channel attack resisting method for RSA password application - Google Patents
Side channel attack resisting method for RSA password application Download PDFInfo
- Publication number
- CN110730072B CN110730072B CN201911005724.4A CN201911005724A CN110730072B CN 110730072 B CN110730072 B CN 110730072B CN 201911005724 A CN201911005724 A CN 201911005724A CN 110730072 B CN110730072 B CN 110730072B
- Authority
- CN
- China
- Prior art keywords
- attack
- side channel
- rsa
- modulus
- randomizing
- 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.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 36
- 125000004122 cyclic group Chemical group 0.000 claims description 4
- 238000007781 pre-processing Methods 0.000 claims description 4
- 230000007480 spreading Effects 0.000 claims description 3
- 238000004364 calculation method Methods 0.000 description 3
- 230000007123 defense Effects 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 1
- 230000036039 immunity Effects 0.000 description 1
- 238000002347 injection Methods 0.000 description 1
- 239000007924 injection Substances 0.000 description 1
- 230000008569 process Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/3033—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters details relating to pseudo-prime or prime number generation, e.g. primality test
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/002—Countermeasures against attacks on cryptographic mechanisms
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/002—Countermeasures against attacks on cryptographic mechanisms
- H04L9/003—Countermeasures against attacks on cryptographic mechanisms for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
- H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Computing Systems (AREA)
- Theoretical Computer Science (AREA)
- Storage Device Security (AREA)
Abstract
The invention belongs to the technical field of password application, and particularly relates to a side channel attack resisting method for RSA password application. To avoid the variable R2 having a value of 1 or N-1 after a modulo N operation with a special message input, the method takes the measure of extending the modulus N while randomizing the initial values of the registers R0, R1 and R2. To enhance randomness, the largest prime number c of L bits of the random number used to spread the modulus is typically chosen so that any one integer of L bits cannot be divided by c. The method can theoretically resist common side channel attack modes such as selective message attack, SPA and DPA attack, DFA attack and the like.
Description
Technical Field
The invention belongs to the technical field of password application, and particularly relates to a side channel attack resisting method for RSA password application.
Background
The cryptograph security product not only needs to have theoretical security, but also needs to reach the security level in actual work, and the cryptograph analysis or attack on the cryptograph security system is helpful to discover the security vulnerability of the cryptograph system and improve the security of the cryptograph system and the cryptograph security equipment, so that the cryptograph analysis is always an important branch in the cryptograph.
The crypto chip is the core of the information security platform, and the security of the crypto chip is crucial to the information security. The power consumption attack is a main attack mode of side channel attack, and can acquire real-time side channel power consumption information of a cryptographic chip in the execution process of the cryptographic chip on the premise of not damaging any equipment and the cryptographic chip, and then acquire cryptographic information such as a secret key through specific analysis.
At present, a side channel power consumption attack means applied by a wide RSA cipher in the industry is more and more diversified, the attack efficiency is higher and higher, and the cost is lower and lower. In particular, the modular exponentiation algorithm loop step of the RSA cipher core has high vulnerability to attack. Therefore, there is a need for continuous anti-attack defense measures such as blinding the modular exponentiation algorithm (especially the loop operation of the modular exponentiation algorithm) in the RSA cipher.
The modular exponentiation method proposed by Boscher, which is commonly used for RSA cryptography, was once thought to be highly effective against almost all side-channel attacks (SPA, DPA and DFA). The algorithm resists selective message attacks by randomizing the registers. The blind BNP modular power algorithm is successfully overcome by selecting the message CPA attack method, and the message (a.N +/-1) is selected b Under the condition of considering actual hardware environment, N-1,1 and N +1 can be used as input selection messages, and a correlation power consumption analysis (CPA) means is combined.
RSA cipher for an incoming plaintext message M e G, key d =(d m-1 ,...,d 1 ,d 0 ) 2 And modulus N, as follows:
the first step is as follows: generating a random number r;
the second step is that: three variables R [0] are configured]＝r，R[1]＝r -1 mod N，R[2]＝M；
The third step: for the count value i from 0 to m-1, the following operation is performed in a loop: r1-d i ]＝R[1-d i ]·R[2]mod N，R[2]＝R[2] 2 mod N；
The fourth step: judging the relationship of three variables, if satisfying (R0)]·R[1]·M＝R[2]mod N), then the result is: (r) -1 ·R[0]mod N); otherwise, the calculation is erroneous.
As can be seen from the above steps, the current bit value of the key is only equal to the first modular multiplication operation R [1-d ] in the third step of the step i ]＝R[1-d i ]·R[2]mod N.
If d is i =0, third of the steps the first modular multiplication operation
R[1-d i ]＝R[1-d i ]·R[2]mod N performs: r1]＝R[1]·R[2]mod N；
If d is i =1, third step of the third modular multiplication operation in step
R[1-d i ]＝R[1-d i ]·R[2]mod N performs: r0]＝R[0]·R[2]mod N；
Thus, the key value can also be obtained by determining what operands are executed, and since R [0] and R [1] are independent of each other, their values do not interfere with each other. Then, if R [2] is set to 1 in the loop iteration, registers R [0] and R [1] will remain unchanged at the current value in the next loop iteration, as summarized below:
if d is i =0, the algorithm performs the sixth step in loops i to m-1: r1]＝R[1]·1mod N；
If d is i =1, algorithm sixth step is executed in loop i to m-1: r0]＝R[0]·1mod N；
Thus, register R [0] when the message M =1 is selected for plaintext]Is always equal to the random number r. There are two ways in which register R [2] can be used]Is set to 1. First, aThe method is to directly initialize a register R2 at the input part of the algorithm]1. Another method is to make R2] 2 mod N equals 1. We found (N-1) 2 mod N =1 and (N + 1) 2 mod N =1, if the algorithm input is N-1 or N +1, then register R [2 ″]Will equal 1 after the first cycle. Thus, there are two more rules that can be used to recover the key together with the plaintext 1 approach.
Disclosure of Invention
Technical problem to be solved
The technical problem to be solved by the invention is as follows: how to provide a more secure implementation method of the RSA password requires that the method can make the RSA password application able to resist common Simple Power Attack (SPA), selective message attack, differential Power Attack (DPA), and false power attack (DFA). The method can improve the safety of an RSA public key cipher application system, and has important significance for wide RSA application and information safety protection.
(II) technical scheme
In order to solve the above technical problems, the present invention provides a side channel attack resistant method for RSA cipher application, which performs data preprocessing of the side channel attack resistant method for input plaintext message M, modulus N, based on RSA cipher, before cyclic operation in which modular exponentiation operation step is vulnerable, the method comprising the steps of:
the first step is as follows: generating a random integer r;
the second step is that: configuring three variables R [0]]＝r，R[1]＝r -1 mod N，R[2]＝M；
The third step: randomizing the modulus N such that N' = nxc;
the fourth step: randomize variable R [0 ]: r [0] = (1 + R × N) mod N';
the fifth step: randomizing variable R [1 ]: r1 ] = (1 + R × N) mod N';
and a sixth step: randomizing variable R < 2 >: r [2] = (M + R × N) mod N'.
Wherein the random integer r is not less than 32.
Wherein c is a random number for spreading the modulus.
Wherein the c requirement is the maximum prime number under L bit length.
Wherein L is not less than 32.
Wherein L is the length of the binary representation of c, such that any integer of L bits cannot be divided by c.
(III) technical effects
Compared with the prior art, the invention provides an anti-side channel attack method based on RSA password, which can theoretically resist common side channel attack modes such as selective message attack, SPA and DPA attack, DFA attack and the like.
1) Defending against selective message attacks
The side-channel attack resistant method changes the assignment of R2 to R2 = (M + R N) mod N' by extending the modulus N and randomizing the initial values of the registers R0, R1 and R2, which has the advantage that the initial value of R2 is set uncontrollably by selecting the input message.
After loop j (0, 1, \ 8230;, m-1), the value of register R [2] at different input message inputs is as follows:
wherein R is t [2]T in (1) represents an incoming message. It can be seen that R2]The value of (A) is always in change, and the attack of the selective message cannot be realizedAnd then the implementation is carried out.
2) Defending against SPA and DPA attacks
The proposed defense method maintains the regularity of the calculations of the original BNP algorithm and is therefore resistant to SPA attacks. The method is also resistant to DPA attacks, since all intermediate results and register values involved in the computation are randomized.
3) Defending DFA attacks
The final condition judgment of the anti-attack method ensures the immunity of DFA. The method can meet the following requirements under normal operation and normal calculation: r0 x R1 x M R2 mod N, once there is an error injection, the equilibrium relation of the identity is broken, the condition judgment is no longer satisfied, and therefore an error message is returned, so that an attacker cannot use the error message to implement effective attack.
Detailed Description
In order to make the objects, contents, and advantages of the present invention clearer, the following detailed description of the embodiments of the present invention will be given in conjunction with examples.
In order to solve the above technical problems, the present invention provides a side channel attack resistant method for RSA cipher application, which performs data preprocessing of the side channel attack resistant method for input plaintext message M, modulus N, based on RSA cipher, before cyclic operation in which modular exponentiation operation step is vulnerable, the method comprising the steps of:
the first step is as follows: generating a random integer r;
the second step: configuring three variables R [0]]＝r，R[1]＝r -1 mod N，R[2]＝M；
The third step: randomizing the modulus N such that N' = nxc;
the fourth step: randomize variable R [0 ]: r [0] = (1+r × N) mod N';
the fifth step: randomizing variable R [1 ]: r1 ] = (1 + R × N) mod N';
and a sixth step: randomizing variable R < 2 >: r [2] = (M + R × N) mod N'.
Wherein the random integer r is not less than 32.
Wherein c is a random number for spreading the modulus.
Wherein the c requirement is the maximum prime number under L bit length.
Wherein L is not less than 32.
Wherein L is the length of the binary representation of c, such that any integer of L bits cannot be evenly divided by c.
Example 1
In this embodiment, the main reasons why the selective message inputs N-1,1 and N +1 can implement selective message attack on the RSA modular exponentiation operation are as follows:
1) Variable R0]、R[1]And R2]Under different settings, the first modular multiplication operation R [1-d ] in the third step of the modular exponentiation step can be performed i ]＝R[1-d i ]·R[2]mod N performs the operations as follows.
2) Collision of power consumption
Generally, for the modular multiplication operations with the same parameters, the same waveform changes can be reflected on the acquired power consumption curve, and the modular multiplication operations with different parameters have larger differences in the waveform changes reflected on the acquired power consumption curve, so that an attacker can easily distinguish the differences through the power consumption curve, and even if the differences are not easy to observe visually, the identical operations in the power consumption curve can be easily found through means such as difference.
Based on the above analysis, we can consider defending against the chosen message attack from two aspects. The first aspect is to avoid power consumption collision caused by the same operation, which needs to consider the application implementation scheme of a specific RSA password; the second aspect is to prevent the cyclic modular multiplication operation in the RSA cipher step from being tied to the key bits fixedly.
The method proposed by the embodiment is a side channel attack resisting defense method based on the principle of the second aspect.
The principle of the method is as follows: to avoid the variable R2 having a value of 1 or N-1 after a modulo N operation with a special message input, the method takes the measure of extending the modulus N while randomizing the initial values of the registers R0, R1 and R2. To enhance randomness, the largest prime number c of L bits (L being the length of the binary representation of c and generally not less than 32) of the random number L bits used to spread the modulus is typically chosen so that any one L-bit integer cannot be evenly divided by c. Based on RSA password, before the vulnerable circulation operation of the modular exponentiation operation step, the data preprocessing of the following steps is carried out:
the first step is as follows: generating a large random integer r;
the second step is that: randomizing the modulus such that N' = nxc;
the third step: randomize variable R [0 ]: r [0] = (1 + R × N) mod N';
the fourth step: randomizing variable R [1 ]: r [1] = (1+r × N) mod N';
the fifth step: randomizing variable R < 2 >: r [2] = (M + R × N) mod N'.
The above description is only a preferred embodiment of the present invention, and it should be noted that, for those skilled in the art, several modifications and variations can be made without departing from the technical principle of the present invention, and these modifications and variations should also be regarded as the protection scope of the present invention.
Claims (5)
1. A side channel attack resisting method for RSA password application is characterized in that for an input plaintext message M and a modulus N, data preprocessing is carried out before cyclic operation which is easy to attack in a modular exponentiation operation step based on the RSA password, and the method comprises the following steps:
the first step is as follows: generating a random integer r;
the second step is that: three variables R [0] are configured]＝r，R[1]＝r -1 modN，R[2]＝M；
The third step: randomizing the modulus N such that N' = nxc;
the fourth step: randomize variable R [0 ]: r [0] = (1 + R × N) modN';
the fifth step: randomizing variable R [1 ]: r1 ] = (1 + R × N) modN';
and a sixth step: randomizing variable R < 2 >: r [2] = (M + R × N) modN';
wherein c is a random number used for spreading the modulus N.
2. A method of resisting side channel attacks for RSA cryptographic applications as claimed in claim 1 wherein the random integer r is not less than 32.
3. A method for side channel attack resistance for RSA cryptographic applications as claimed in claim 1 wherein c is the maximum prime number at L bit length.
4. A method of resisting side channel attacks for RSA cryptographic applications as claimed in claim 3 wherein said L is not less than 32.
5. A method for side-channel attack resistance against RSA cryptographic applications as recited in claim 4, wherein L is the length of the binary representation of c such that any integer number of L bits cannot be evenly divided by c.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911005724.4A CN110730072B (en) | 2019-10-22 | 2019-10-22 | Side channel attack resisting method for RSA password application |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911005724.4A CN110730072B (en) | 2019-10-22 | 2019-10-22 | Side channel attack resisting method for RSA password application |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110730072A CN110730072A (en) | 2020-01-24 |
| CN110730072B true CN110730072B (en) | 2023-02-03 |
Family
ID=69220705
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201911005724.4A Active CN110730072B (en) | 2019-10-22 | 2019-10-22 | Side channel attack resisting method for RSA password application |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110730072B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114978641B (en) * | 2022-05-13 | 2025-01-10 | 北京紫光展锐通信技术有限公司 | Data processing method, device and equipment |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2399904A (en) * | 2003-03-28 | 2004-09-29 | Sharp Kk | Side channel attack prevention in data processing by adding a random multiple of the modulus to the plaintext before encryption. |
| CN104125061A (en) * | 2014-08-12 | 2014-10-29 | 昆腾微电子股份有限公司 | RSA encryption algorithm based attack defending method applied to electronic component |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2888690A1 (en) * | 2005-07-13 | 2007-01-19 | Gemplus Sa | CRYPTOGRAPHIC PROCESS FOR THE SECURE IMPLEMENTATION OF AN EXPONENTIATION AND ASSOCIATED COMPONENT |
| EP2535804A1 (en) * | 2011-06-17 | 2012-12-19 | Thomson Licensing | Fault-resistant exponentiation algorithm |
| FR2977952A1 (en) * | 2011-07-13 | 2013-01-18 | St Microelectronics Rousset | PROTECTION OF A MODULAR EXPONENTIATION CALCULATION BY MULTIPLICATION BY A RANDOM QUANTITY |
-
2019
- 2019-10-22 CN CN201911005724.4A patent/CN110730072B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB2399904A (en) * | 2003-03-28 | 2004-09-29 | Sharp Kk | Side channel attack prevention in data processing by adding a random multiple of the modulus to the plaintext before encryption. |
| CN104125061A (en) * | 2014-08-12 | 2014-10-29 | 昆腾微电子股份有限公司 | RSA encryption algorithm based attack defending method applied to electronic component |
Non-Patent Citations (1)
| Title |
|---|
| 嵌入式加密芯片功耗分析攻击与防御研究进展;李浪 等;《计算机研究与发展》;20100415;第47卷(第4期);第595-604页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110730072A (en) | 2020-01-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Goubin et al. | DES and differential power analysis the “Duplication” method | |
| Rivain et al. | Provably secure higher-order masking of AES | |
| Clavier | Secret external encodings do not prevent transient fault analysis | |
| Wyseur et al. | Cryptanalysis of white-box DES implementations with arbitrary external encodings | |
| EP1648111B1 (en) | Tamper-resistant encryption using a private key | |
| US8422671B2 (en) | Methods of encryption and decryption using operand ordering and encryption systems using the same | |
| US8595513B2 (en) | Method and system for protecting a cryptography device | |
| EP3596876B1 (en) | Elliptic curve point multiplication device and method for signing a message in a white-box context | |
| US9544132B2 (en) | Cryptographic method for protecting a key hardware register against fault attacks | |
| KR100737171B1 (en) | Low memory masking method for power analysis attack against aria | |
| CN104410490B (en) | The method of non-linear extruding protection password S boxes | |
| KR100834096B1 (en) | Encryption method of block cipher algorithm ARRIA corresponding to higher power analysis attack | |
| US10461922B2 (en) | Method and system for protecting a cryptographic operation | |
| GB2399904A (en) | Side channel attack prevention in data processing by adding a random multiple of the modulus to the plaintext before encryption. | |
| CN110730072B (en) | Side channel attack resisting method for RSA password application | |
| EP4449663A1 (en) | Method secured against side-channel attacks performing a | |
| WO2008064704A1 (en) | Method and device for preventing information leakage attacks on a device implementing a cryptographic function | |
| WO2017114739A1 (en) | System and method for hiding a cryptographic secret using expansion | |
| KR102327771B1 (en) | How to counter a degree 2 or higher DCA attack in a table-based implementation | |
| Lee et al. | Table redundancy method for protecting against fault attacks | |
| Ha et al. | Power Analysis Attacks on the Right-to-Left Square-Always Exponentiation Algorithm. | |
| JP3878853B2 (en) | Modular power algorithm for electronic components using public key cryptography algorithms | |
| Le et al. | On double exponentiation for securing RSA against fault analysis | |
| Mahanta et al. | Comparative modular exponentiation with randomized exponent to resist power analysis attacks | |
| Chen et al. | On hardening leakage resilience of random extractors for instantiations of leakage-resilient cryptographic primitives |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |