CN115801264B - Physical attack method, medium, equipment and system for elliptic curve digital signature - Google Patents
Physical attack method, medium, equipment and system for elliptic curve digital signature Download PDFInfo
- Publication number
- CN115801264B CN115801264B CN202211244166.9A CN202211244166A CN115801264B CN 115801264 B CN115801264 B CN 115801264B CN 202211244166 A CN202211244166 A CN 202211244166A CN 115801264 B CN115801264 B CN 115801264B
- Authority
- CN
- China
- Prior art keywords
- bit
- private key
- reduction algorithm
- column
- matrix
- 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 60
- 238000004422 calculation algorithm Methods 0.000 claims abstract description 42
- 230000009467 reduction Effects 0.000 claims abstract description 41
- 239000012634 fragment Substances 0.000 claims abstract description 25
- 239000011159 matrix material Substances 0.000 claims description 27
- 239000013598 vector Substances 0.000 claims description 24
- 238000004590 computer program Methods 0.000 claims description 12
- 238000001514 detection method Methods 0.000 claims description 5
- 230000008569 process Effects 0.000 claims description 5
- 230000000903 blocking effect Effects 0.000 claims description 3
- 101100257800 Ipomoea batatas WAXY gene Proteins 0.000 claims description 2
- 101000879465 Solanum tuberosum Sucrose synthase Proteins 0.000 claims description 2
- 238000003491 array Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 4
- 238000004458 analytical method Methods 0.000 description 2
- 238000004364 calculation method Methods 0.000 description 2
- 230000007547 defect Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 239000002699 waste material Substances 0.000 description 2
- PXFBZOLANLWPMH-UHFFFAOYSA-N 16-Epiaffinine Natural products C1C(C2=CC=CC=C2N2)=C2C(=O)CC2C(=CC)CN(C)C1C2CO PXFBZOLANLWPMH-UHFFFAOYSA-N 0.000 description 1
- TVZRAEYQIKYCPH-UHFFFAOYSA-N 3-(trimethylsilyl)propane-1-sulfonic acid Chemical compound C[Si](C)(C)CCCS(O)(=O)=O TVZRAEYQIKYCPH-UHFFFAOYSA-N 0.000 description 1
- 230000004888 barrier function Effects 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000005336 cracking Methods 0.000 description 1
- 238000005265 energy consumption Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 230000008092 positive effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
Landscapes
- Complex Calculations (AREA)
- Storage Device Security (AREA)
Abstract
The invention discloses a physical attack method, medium, equipment and system of elliptic curve digital signature, belonging to the technical field of password security, comprising the following steps: and expanding wider physical attack on the pseudo-random generator, detecting and intercepting discontinuous multi-segment bit fragments through side channel attack, and solving a private key or evaluating the calculated amount of the private key by utilizing a lattice reduction algorithm according to the situation. The invention can be used as a physical attack method for ECDSA on one hand, and can evaluate the capability of ECDSA to resist side channel attack according to the complexity of Ying Geji reduction algorithm on the other hand.
Description
Technical Field
The invention relates to a physical attack method, medium, equipment and system for elliptic curve digital signature, belonging to the technical field of password security.
Background
Elliptic curve cryptography has important application in real network communication, and the digital signature system ECDSA based on elliptic curve has become the standard issued by NIST 1, ANSI 2,3, etc. The physical attack on the pseudo-random generator of the ECDSA can reveal part of random number bits, and then the private key of the ECDSA can be obtained by solving the corresponding hidden number problem (Hidden Number Problem, abbreviated as HNP), so that the security of the digital signature system is seriously threatened. HNP refers to recovering a private key on a residual ring based on part of the high order bits information of the affine function value of the private key. The main methods for solving HNP at present are a lattice reduction algorithm [4] and a Bleichenbacher algorithm [5], wherein the lattice reduction method needs less acquired information and has weaker preconditions for attack. The HNP is cracked by using a lattice reduction algorithm to play an important role in the physical security of the password, and the computational complexity is an important reference index for measuring the resistance of certain password systems to side channel attacks.
Existing techniques for physical attack on ECDSA using HNP problems mainly use pseudo random numbers to reveal the consecutive high bit(s) [4], and therefore may not fully use the side channel information obtained by physical detection. When more output signal fragments of the pseudo-random generator are obtained through physical attack such as energy consumption or the like, or the positions of the output bits of the intercepted pseudo-random generator are not regular enough, the existing technology does not support analysis of all information obtained through physical attack detection.
The related main concrete background technology is as follows:
1. Elliptic curve digital signature system ECDSA
The system parameters of the ECDSA signature system include a selected elliptic curveAnd a q-order base point G on this curve. Randomly selecting a positive integer d as a private key of the signature (d < q is more than or equal to 0), and calculating d times point [ d ] G of the base point G as a corresponding public key. Given the hash value h of a message m, the signature process is as follows: the signer firstly generates a random number w to meet, then calculates the x coordinate of the k times point [ k ] G of the base point G, calculates r' =x ([ k ] G), and then calculates the x coordinate of the k times point [ k ] G
s＝w-1·(h+d·r′)mod q，#(1)
Finally, the signature (r', s) of the message m is obtained.
2. Hidden Number Problem (HNP)
Recording deviceIs the remaining class ring of base point order q. Is provided withIs an unknown variable (hidden number). Taking outThe number alpha 1,α2,...,αn,β1,β2,...,βn is uniformly distributed on the upper part, and gamma i≡αix0+βi (mod q) is calculated, wherein i is more than or equal to 1 and n is more than or equal to n. HNP refers to the higher order bits of given base point order q and α 1,α2,...,αn and γ 1,γ2,...,γn, solving for x 0. The prior grid reduction solving method for solving HNP mainly comprises the steps of firstly converting into a form with error learning problem (LEARNING WITH error, abbreviated as LWE), then embedding and converting into a unique shortest vector (uSVP) in a solving grid by using Kannan, and finally constructing a proper grid model, and solving by using a grid reduction algorithm [4].
3. Problem with error Learning (LWE)
The problem with error Learning (LWE) here [5] is: given modulus q, dimension d, and remaining class ringThe distribution χ is input into n LWE samples to obtainIs provided. Given modulus q, dimension d, complianceA LWE sample comprising uniformly distributed secret vectors sA vector a and (< a, s > +e) mod q, where e is a sample subject to a random distribution χ.
Prior art references
[1]National Institute of Standards and Technology,FIPS186-4Digital Signature Standard(DSS),July 2013,
https://csrc.nist.gov/publications/detail/fips/186/4/final
[2]ANSI X9.62-1998Public Key Cryptography For The Financial Services Industry:The Elliptic Curve Digital Signature Algorithm(ECDSA)
[3]ANSI X9.62:2005Public key cryptography for the financial services industry-the elliptic curve digital signature algorithm(ECDSA),American Bankers Association,November 16,
2005,https://webstore.ansi.org/Standards/ASCX9/ansix9621998#PDF[4]Albrecht,M.R.,Heninger,N.(2021).On Bounded Distance Decoding with Predicate:Breaking the"Lattice Barrier"for the Hidden Number Problem.
In:Canteaut,A.,Standaert,FX.(eds)Advances in Cryptology–EUROCRYPT 2021.EUROCRYPT 2021.Lecture Notes in Computer Science,vol 12696.Springer,Cham.
https://doi.org/10.1007/978-3-030-77870-5_19
[5]Benger,N.,van de Pol,J.,Smart,N.P.,Yarom,Y.:“ooh aah...just a little bit":
A small amount of side channel can go a long way.In:Batina,L.,Robshaw,M.(eds.)CHES2014.LNCS,vol.8731,pp.75-92.Springer,Heidelberg
(Sep 2014)
[6]O.Regev.On lattices,learning with errors,random linear codes,and cryptography.Journal of the ACM,56(6):34,2009.Preliminary version in STOC 2005.
Disclosure of Invention
The invention aims to overcome the defects of the prior art and provides a physical attack method, medium, equipment and system for elliptic curve digital signature. The invention expands wider physical attack to the pseudo-random generator, detects and intercepts discontinuous multi-segment bit fragments, and aims at the situation to calculate the private key by using a lattice reduction algorithm or evaluate the calculated amount of calculating the private key. The invention can be used as a physical attack method for ECDSA on one hand, and can evaluate the capability of ECDSA to resist side channel attack according to the complexity of Ying Geji reduction algorithm on the other hand.
The invention aims at realizing the following scheme:
a physical attack method of elliptic curve digital signature includes the following steps:
s1: inputting ECDSA base point order q, measuring bit number m of the base point order q, and determining a pseudo-random number bit detection possible range of physical attack;
S2: determining a bit fragment position set and S for attack on a pseudo-random generator; starting bit position markers from 0 according to the low order to the high order of the data, one bit fragment position [ i, j) refers to the set of markers of bits { i, i+1,., j-1};
S3: acquiring a message hash value h and signature information (r', S) of the ECDSA, and intercepting a pseudo random number w used in the signature generation process in a bit fragment position set and bit fragments of S through a side channel attack means; a pseudo-random number is noted as b and b = b 0+2b1+22b2+…+2m-1bm -1, where b 0,b1,...,bm-1 e {0,1}, specifies bit segment positions [ i, j), then the notation bits (b, i, j) represents bit segments (b j-1,bj-2,...,bi);
s4: calculating a sample A according to the data acquired in the step S3, wherein the sample A comprises alpha= (r'. S -1)mod q、β＝-(h·s-1) mod q and a plurality of bit fragment bits (w, i, j) of the pseudo-random number, and the bit fragment positions [ i, j ] traverse all bit fragment positions in the S;
S5: repeating the step S3 and the step S4 until enough samples A 1,A2,...,An are obtained;
S6: according to the acquired sample A 1,A2,...,An, solving a private key by using a lattice reduction algorithm or evaluating complexity according to the calculated amount of the required lattice reduction algorithm;
S7: and outputting the private key or the required calculated amount, and ending.
Further, in step S6, the method for solving the private key by using the lattice reduction algorithm or evaluating the complexity according to the calculated amount of the required lattice reduction algorithm includes the following sub-steps:
S61, inputting a base point order q, and obtaining n samples a k＝(αk,βk, bits (w, i, j)), k=1, 2, …, n;
s62, recording that the unknown bit segment position set in the pseudo random number is S R＝{[ik,jk): k=1, 2, & r;
S63, calculating the length of each bit segment position in S R and finding the maximum value thereof, i.e., for k=1, 2,..r, calculating c k＝jk-ik, and c max＝max1≤k≤rck;
S64, constructing a matrix A of r rows and r+1 columns, wherein the elements of the 1 st row and the 1 st column are Here if i k-cmax+ck < 0, thenMod q refers to the remaining class ringIn (a)Is a multiplicative inverse of (a); the k+1th column element of the k row of the matrix A is the base point order q; the other elements of matrix A are 0; matrix a-shape is as follows:
s65, calculating a short vector v short with the length r and the rest class ring by using a lattice reduction algorithm aiming at the column vector of A The element lambda in (2) satisfies lambda.A [: 1] ≡v short mod q, wherein a [: 1 represents the first column of matrix a; i.e. in the remaining class ringIn the operational sense of (a), the short vector v short is equal to the first column of matrix a times λ; let v short＝(d1,d2,...,dr)T, i.e. row k of v short be d k;
S66, constructing an example of LWE problem with error learning, wherein the modulus is q, the dimension of the secret is 1, the error distribution is approximately regarded as0 and the standard deviation is N LWE samples in total, where the kth sample is the data pair (λ·α kmod q,bk), where:
Here for the integer b and m-bit segment positions [ i, j ], the integer b satisfies 0.ltoreq.b < q and b=b 0+2b1+22b2+…+2m-1bm-1, where b 0,b1,…,bm-1 e {0,1}, e (b, i, j) represents the integer 2 0bi+21bi+1+…+2j-i-1bj-1;
s67, solving the problem instance in the step S66 according to a method for solving the LWE problem, or evaluating the complexity of the problem instance in the step S66 according to a method for evaluating the calculated amount of the LWE problem.
Further, in step S6, the method for solving the private key by using the lattice reduction algorithm or evaluating the complexity according to the calculated amount of the required lattice reduction algorithm includes the following sub-steps:
SS61, input base point order q, n samples a l＝(αl,βl,bits(wl, i, j) obtained, l=1, 2, …, n;
SS62, noting that the unknown set of bit segment positions in the pseudorandom number is S R＝{[ik,jk): k=1, 2, & r;
SS63, calculating the length of each bit segment position in S R, i.e., for k=1, 2,..r, calculating c k＝jk-ik;
SS64, traversal l=1, 2,.. from the hidden number problem sample a l of the first discontinuous multi-segment bit leakage, calculate:
SS65, vector length r-1:
constructing a blocking matrix M of 2+nr rows and 2+nr columns:
Wherein row 1 and column 1 are 1; for l=1, 2,..n, sub-arrays of rows 2+ (l-1) (r-1) to 1+l (r-1), rows 2+ (l-1) (r-1) to 1+l (r-1) are unit arrays of the scale (r-1) × (r-1), rows 1+n (r-1) +l are columns a l, 1+n (r-1) +l rows 2+ (l-1) (r-1) through 1+l (r-1) columns are 1× (r-1) scale subarrays C, 1+n (r-1) +l rows 1+n (r-1) +l columns are q, and 1+n (r-1) +l rows 2+nr columns are b l; row 2+nr column 1; the rest elements are 0;
SS66, calculate the short vector to the column vector of matrix M by lattice reduction algorithm, note the 1 st coordinate eta 1 of the short vector, 2+nr coordinate eta nr+2; if the absolute value of η nr+2 is equal to 1, then x 0＝-η1·ηnr+2 is calculated and the private key x 0 is output; otherwise, failure;
And SS67, acquiring x 0 as a private key to output, and obtaining information in the corresponding real password problem, or giving out the calculated amount of the matrix M lattice reduction algorithm as the calculated amount for solving the private key x 0.
Further, in step S3, the side channel attack means includes a power consumption side channel attack means.
Further, in step S67, the method for solving the LWE problem adopts an existing method.
Further, in step S67, the method of evaluating the calculation amount of the LWE problem adopts an existing method.
Further, in step SS67, the information in the real-world cryptographic question includes a private key.
A readable storage medium having stored therein a computer program, the computer program being loaded by a processor and executing the method according to any of the preceding claims.
A computer device comprising a processor and a memory, the memory having stored therein a computer program which, when loaded by the processor, performs the method of any of the preceding claims.
A physical attack system for elliptic curve digital signatures comprising a computer device as described above.
The beneficial effects of the invention include:
Compared with the prior physical attack technology of elliptic curve digital signature system, the invention has the following positive effects: the invention provides a physical attack method of elliptic curve digital signature based on lattice reduction algorithm, which has the main advantages that:
(1) The method allows more elastic side channel attack to be carried out on the pseudo random generator adopted by the cryptosystem, the bit positions detected by the physical attack are wider, and the method is not limited to fixedly detecting continuous high-order bits of the pseudo random number, so that the feasibility of the physical attack is stronger.
(2) By the technical scheme of the lattice reduction algorithm, discontinuous multi-section bit fragment information of pseudo random number intercepted by physical attack can be fully utilized, and compared with the traditional hidden number problem method which only can use pseudo random number high-order continuous bit fragments, the method can fully utilize information detected by physical attack, and greatly reduce waste of intercepted data by attack.
(3) According to the technical scheme of the lattice reduction algorithm, the ECDSA cracking problem of discontinuous multi-segment bit fragments of the intercepted pseudo random number is converted into the LWE problem or the SVP problem, so that more quantifiable information can be provided for evaluating the physical safety of the ECDSA and realizing the safety by utilizing deep research and extensive results of the LWE or SVP solving method.
Drawings
In order to more clearly illustrate the embodiments of the invention or the technical solutions of the prior art, the drawings which are used in the description of the embodiments or the prior art will be briefly described, it being obvious that the drawings in the description below are only some embodiments of the invention, and that other drawings can be obtained according to these drawings without inventive faculty for a person skilled in the art.
FIG. 1 is a flow chart of steps of a method according to an embodiment of the present invention;
FIG. 2 is a flowchart illustrating a sixth embodiment of the method according to the present invention;
FIG. 3 is a flowchart of another embodiment of the method of the present invention.
Detailed Description
All of the features disclosed in all of the embodiments of this specification, or all of the steps in any method or process disclosed implicitly, except for the mutually exclusive features and/or steps, may be combined and/or expanded and substituted in any way.
In order to solve the problems existing in the background, the inventor of the present invention has found that in the existing similar work, physical attacks can only acquire the high-order bit information of the pseudo-random generator through side channel attacks, and the information can be used as integer linear constraint on the private key, and the following defects exist: (1) If a physical attack is required to just intercept the high order bits of the pseudo random number, a certain limit on the side channel attack is formed; (2) If the physical attack pseudo-random generator obtains more and more complex information, such as discontinuous bit sub-string information of pseudo-random number obtained by side channel attack, the analysis of the existing attack does not utilize the bit information of the middle segment and the bit segment, which causes the waste of the physical attack interception information. Thus, the present invention recognizes that it is necessary to present an ECDSA attack method that intercepts and exploits pseudo random number multiple pieces of bit information.
The invention aims to solve the following technical problems in the aspect of physical attack of elliptic curve digital signature system: the method is characterized by allowing the side channel attack of the pseudo random generator to intercept any position bit information, not only using the high-order bit of the pseudo random number detected to leak, but also detecting discontinuous multi-segment bit information of the intercepted pseudo random number, acquiring private key information by using a lattice reduction algorithm according to the intercepted pseudo random number bit information, and performing physical attack on an elliptic curve digital signature system or evaluating the capability of the elliptic curve digital signature system to resist the physical attack.
In a further inventive concept, the invention provides a physical attack method of elliptic curve digital signature based on a lattice reduction algorithm, which intercepts discontinuous multi-section bit fragment information of a pseudo-random generator through side channel attack, and solves private key information or estimates the calculated amount of solving the private key by using the lattice reduction algorithm.
Example 1
The technical scheme adopted by the invention for solving the technical problems is as follows: a physical attack method of elliptic curve digital signature based on lattice reduction algorithm includes the following steps:
step one: and inputting the ECDSA base point order q, measuring the bit number m of the base point order q, and determining the pseudo-random number bit detection possible range of the physical attack.
Step two: a set of bit fragment positions and S for the attack on the pseudo-random generator are determined. Starting with bit position markers from 0 according to the low order to high order of the data, one bit fragment position [ i, j) refers to the set of markers of bits { i, i+1,..j-1 }.
Step three: and acquiring a message hash value h and signature information (r', S) of the ECDSA, and intercepting and capturing a pseudo random number w used in the signature generation process in a bit fragment position set and bit fragments of S through side channel attack means such as power consumption. A pseudo-random number is noted b and b=b 0+2b1+22b2+…+2m-1bm-1, where b 0,b1,...,bm-1 e {0,1}, specifies the bit segment position i, j, then the notation bits (b, i, j) represents the bit segment (b j-1,bj-2,...,bi).
Step four: from the data obtained in step three, a sample a is calculated comprising α= (r' ·s -1)mod q、β＝-(h·s-1) mod q and a pseudo-random number of bit segment bits (w, i, j), wherein bit segment positions [ i, j ] traverse all bit segment positions in S.
Step five: and repeating the third and fourth steps until enough samples A 1,A2,...,An are obtained.
Step six: based on the obtained sample a 1,A2,...,An, the private key is solved using the lattice reduction algorithm or the complexity is assessed based on the calculated amount of the required lattice reduction algorithm.
Step seven: the private key or the required calculation amount is output. And (5) ending.
Example 2
A physical attack method of elliptic curve digital signature based on lattice reduction algorithm (the step six) can also comprise the following steps:
Step one: input base point order q, n samples a k＝(αk,βk, bits (w, i, j)), k=1, 2,..n.
Step two: the unknown set of bit segment positions in the pseudorandom number is recorded as S R＝{[ik,jk): k=1, 2,..r }.
Step three: the length of each bit segment position in S R is calculated and the maximum value thereof is found, i.e., for k=1, 2,..r, c k＝jk-ik, and c max＝max1≤k≤rck are calculated.
Step four: constructing a matrix A of r rows and r+1 columns, wherein the elements of the 1 st column of the k row areHere if i k-cmax+ck < 0, thenRefers to the remaining class ringIn (a)Is a multiplicative inverse of (a); the k+1th column element of the k row of the matrix A is the base point order q; the other elements of matrix a are 0. Matrix A-shaped like
Step five: calculating a short vector v short with length r and a residual class ring by using a lattice reduction algorithm aiming at the column vector of AThe element lambda in (2) satisfies lambda.A [: 1] ≡ Vshort mod q, wherein a [: 1 represents the first column of matrix a. I.e. in the remaining class ringIn the operational sense of (a), the short vector V short is equal to the first column of matrix a times λ. Let v short＝(d1,d2,...,dr)T, i.e. row k of v short, be d k.
Step six: constructing an example of a problem with error learning (LEARNING WITH Errors, abbreviated LWE), modulus q, secret dimension 1, error distribution can also be considered approximately as an expected value of 0, standard deviationN LWE samples in total, wherein the kth sample is the data pair (. Lambda. Alpha. k mod q,bk), wherein
Here for the integer b and m-bit segment positions [ i, j ], the integer b satisfies 0+.b < q and b=b 0+2b1+22b2+…+2m-1bm-1, where b 0,b1,…,bm-1 ε {0,1}, e (b, i, j) represents the integer 2 0bi+21bi+1+…+2j-i-1bj-1.
Step seven: the problem instance is solved according to the existing method for solving the LWE problem, or the complexity evaluation is carried out according to the existing method for evaluating the calculated amount of the LWE problem.
Example 3
A physical attack method of elliptic curve digital signature based on lattice reduction algorithm (the step six) can also comprise the following steps:
step one: input base point order q, n samples a l＝(αl,βl,bits(wl, i, j) taken, l=1, 2, …, n.
Step two: the unknown set of bit segment positions in the pseudorandom number is recorded as S R＝{[ik,jk): k=1, 2,..r }.
Step three: the length of each bit segment position in S R is calculated, i.e., for k=1, 2.
Step four: traversing l=1, 2, n, based on the first discrete multi-segment bit leakage concealment problem sample A l, calculating
Step five: record the vector of length r-1
Constructing a blocking matrix M of 2+nr rows and 2+nr columns
Wherein row 1, column 1 is 1; for l=1, 2,..n, sub-arrays of rows 2+ (l-1) (r-1) to 1+l (r-1), rows 2+ (l-1) (r-1) to 1+l (r-1) are unit arrays of the scale (r-1) × (r-1), rows 1+n (r-1) +l are columns a l, 1+n (r-1) +l rows 2+ (l-1) (r-1) through 1+l (r-1) columns are 1× (r-1) scale subarrays C, 1+n (r-1) +l rows 1+n (r-1) +l columns are q, and 1+n (r-1) +l rows 2+nr columns are b l; row 2+nr column 1; the remaining elements are 0.
Step six: a short vector is calculated by using a lattice reduction algorithm for the column vector of the matrix M, and the 1 st coordinate eta 1 and the 2+nr th coordinate eta nr+2 of the short vector are recorded. If the absolute value of η nr+2 is equal to 1, then x 0＝-η1·ηnr+2 is calculated and the private key x 0 is output; otherwise, failure occurs.
Step seven: and obtaining x 0 as a private key to output, so as to obtain information (such as the private key and the like) in the corresponding real password problem, or giving out the calculated amount of a matrix M lattice reduction algorithm as the calculated amount for solving the private key x 0.
In other embodiments of the present invention, there is also provided a readable storage medium in which a computer program is stored, the computer program being loaded by a processor and executing the method described in any of embodiments 1 to 3.
In other embodiments of the present invention, there is also provided a computer device comprising a processor and a memory, the memory having stored therein a computer program which, when loaded by the processor, performs the method of any one of embodiments 1 to 3.
In other embodiments of the present invention, there is also provided a physical attack system for elliptic curve digital signatures, including the computer device in the above embodiment.
The units involved in the embodiments of the present invention may be implemented by software, or may be implemented by hardware, and the described units may also be provided in a processor. Wherein the names of the units do not constitute a limitation of the units themselves in some cases.
According to one aspect of the present application, there is provided a computer program product or computer program comprising computer instructions stored in a computer readable storage medium. The computer instructions are read from the computer-readable storage medium by a processor of a computer device, and executed by the processor, cause the computer device to perform the methods provided in the various alternative implementations described above.
As another aspect, the present application also provides a computer-readable medium that may be contained in the electronic device described in the above embodiment; or may exist alone without being incorporated into the electronic device. The computer-readable medium carries one or more programs which, when executed by the electronic device, cause the electronic device to implement the methods described in the above embodiments.
The invention is not related in part to the same as or can be practiced with the prior art.
The foregoing technical solution is only one embodiment of the present invention, and various modifications and variations can be easily made by those skilled in the art based on the application methods and principles disclosed in the present invention, not limited to the methods described in the foregoing specific embodiments of the present invention, so that the foregoing description is only preferred and not in a limiting sense.
In addition to the foregoing examples, those skilled in the art will recognize from the foregoing disclosure that other embodiments can be made and in which various features of the embodiments can be interchanged or substituted, and that such modifications and changes can be made without departing from the spirit and scope of the invention as defined in the appended claims.
Claims (6)
1. A physical attack method of elliptic curve digital signature is characterized by comprising the following steps:
s1: inputting ECDSA base point order q, measuring bit number m of the base point order q, and determining a pseudo-random number bit detection possible range of physical attack;
S2: determining a bit fragment position set S for attack on a pseudo-random generator; starting bit position markers from 0 according to the low order to the high order of the data, one bit fragment position [ i, j ] refers to the set { i, i+1, …, j-1} of the markers of bits;
S3: acquiring a message hash value h and signature information (r', S) of the ECDSA, and intercepting a pseudo random number w used in the signature generation process in a bit fragment position set and bit fragments of S through a side channel attack means; a pseudo-random number is noted b and b=b 0+2b1+22b2+…+2m-1bm-1, where b 0,b1,…,bm-1 e {0,1}, specifies bit segment positions [ i, j ], then the notation bits (b, i, j) represents bit segments (b j-1,bj-2,…,bi);
S4: calculating a sample A according to the data acquired in the step S3, wherein the sample A comprises alpha= (r ′·s-1)mod q、β＝-(h·s-1) mod q and a plurality of bit fragment bits (w, i, j) of a pseudo-random number, and the bit fragment positions [ i, j ] traverse all bit fragment positions in the step S;
S5: repeating the step S3 and the step S4 until enough samples A 1,A2,…,An are obtained;
S6: according to the acquired sample A 1,A2,…,An, solving a private key by using a lattice reduction algorithm or evaluating complexity according to the calculated amount of the required lattice reduction algorithm;
S7: outputting the private key or the required calculated amount, and ending;
in step S6, the method for solving the private key by using the lattice reduction algorithm or evaluating the complexity according to the calculated amount of the required lattice reduction algorithm includes the following steps:
s61, inputting a base point order q, and obtaining n samples a k＝(αk,βk, bits (w, i, j)), k=1, 2, …, n;
s62, recording that the unknown bit segment position set in the pseudo random number is S R＝{[ik,jk) k=1, 2, …, r };
S63, calculating the length of each bit segment position in S R and finding the maximum value thereof, i.e. calculating c k＝jk-ik for k=1, 2, …, r, and c max＝max1≤k≤r ck;
S64, constructing a matrix A of r rows and r+1 columns, wherein the elements of the 1 st row and the 1 st column are Here if i k-cmax+ck <0, thenRefers to the remaining class ringIn (a)Is a multiplicative inverse of (a); the k+1th column element of the k row of the matrix A is the base point order q; the other elements of matrix A are 0; matrix a-shape is as follows:
s65, calculating a short vector v short with the length r and the rest class ring by using a lattice reduction algorithm aiming at the column vector of A The element lambda in (2) satisfies lambda.A [: 1] ≡v short mod q, where A [: 1] represents the first column of matrix A; i.e. in the remaining class ringIn the operational sense of (a), the short vector v short is equal to the first column of matrix a times λ; let v short＝(d1,d2,…,dr)T, i.e. row k of v short be d k;
S66, constructing an example of LWE problem with error learning, wherein the modulus is q, the dimension of the secret is 1, the error distribution is approximately regarded as0 and the standard deviation is N LWE samples in total, where the kth sample is the data pair (λ·α k mod q,bk), where:
Here for the integer b and m-bit segment positions [ i, j ], the integer b satisfies 0.ltoreq.b < q and b=b 0+2b1+22b2+…+2m- 1bm-1, where b 0,b1,…,bm-1 e {0,1}, e (b, i, j) represents the integer 2 0bi+21bi+1+…+2j-i-1bj-1;
S67, solving the problem instance in the step S66 according to a method for solving the LWE problem, or evaluating the complexity of the problem instance in the step S66 according to a method for evaluating the calculated amount of the LWE problem;
Or, in step S6, the method for solving the private key by using the lattice reduction algorithm or evaluating the complexity according to the calculated amount of the required lattice reduction algorithm includes the following steps:
SS61, input base point order q, n samples a l＝(αl,βl,bits(wl, i, j) obtained, l=1, 2, …, n;
SS62, note that the unknown set of bit segment positions in the pseudorandom number is S R＝{[ik,jk) k=1, 2, …, r;
SS63, calculating the length of each bit segment position in S R, i.e. calculating c k＝jk-ik for k=1, 2, …, r;
SS64, traversing l=1, 2, …, n, calculates from the hidden number problem sample a l of the first discontinuous multi-segment bit leakage:
SS65, vector length r-1:
constructing a blocking matrix M of 2+nr rows and 2+nr columns:
Wherein row 1 and column 1 are 1; for the unit array of scale (r-1) for columns l=1, 2, …, n, 2+ (l-1) (r-1) to 1+l (r-1), 2+ (l-1) (r-1) to 1+l (r-1), 1+n (r-1) +l row 1 is a l, 1+n (r-1) +l row 2+ (l-1) (r-1) to 1+l (r-1) is 1× (r-1) scale subarray C, 1+n (r-1) +l row 1+n (r-1) +l column is q, and 1+n (r-1) +l row 2+nr column is b l; row 2+nr column 1; the rest elements are 0;
SS66, calculate the short vector to the column vector of matrix M by lattice reduction algorithm, note the 1 st coordinate eta 1 of the short vector, 2+nr coordinate eta nr+2; if the absolute value of η nr+2 is equal to 1, then x 0＝-η1·ηnr+2 is calculated and the private key x 0 is output; otherwise, failure;
And SS67, acquiring x 0 as a private key to output, and obtaining information in the corresponding real password problem, or giving out the calculated amount of the matrix M lattice reduction algorithm as the calculated amount for solving the private key x 0.
2. The elliptic curve digital signature physical attack method according to claim 1 wherein in step S3 the side channel attack means comprises power consumption side channel attack means.
3. The method of elliptic curve digital signature physical attack according to claim 1 wherein in step SS67 the information in the real crypto problem includes a private key.
4. A readable storage medium, characterized in that a computer program is stored in the readable storage medium, which computer program is loaded by a processor and carries out the method according to any one of claims 1-3.
5. A computer device, characterized in that it comprises a processor and a memory, in which a computer program is stored, which computer program is loaded by the processor and carries out the method according to any of claims 1-3.
6. A physical attack system of elliptic curve digital signatures comprising a computer device according to claim 5.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211244166.9A CN115801264B (en) | 2022-10-12 | 2022-10-12 | Physical attack method, medium, equipment and system for elliptic curve digital signature |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211244166.9A CN115801264B (en) | 2022-10-12 | 2022-10-12 | Physical attack method, medium, equipment and system for elliptic curve digital signature |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115801264A CN115801264A (en) | 2023-03-14 |
| CN115801264B true CN115801264B (en) | 2024-09-13 |
Family
ID=85432833
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211244166.9A Active CN115801264B (en) | 2022-10-12 | 2022-10-12 | Physical attack method, medium, equipment and system for elliptic curve digital signature |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115801264B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117081724B (en) * | 2023-10-18 | 2023-12-26 | 中国电子科技集团公司第三十研究所 | Estimation method for instance calculated amount of problem with error learning |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104836808A (en) * | 2015-05-12 | 2015-08-12 | 中国科学院软件研究所 | Method for verifying safety of SM2 signature algorithm based on improved difference error attack |
| CN104852805A (en) * | 2015-05-11 | 2015-08-19 | 中国科学院软件研究所 | SM2 signature algorithm protection method for resisting error attack based on lattice |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8027466B2 (en) * | 2007-03-07 | 2011-09-27 | Research In Motion Limited | Power analysis attack countermeasure for the ECDSA |
| US10516541B2 (en) * | 2017-09-13 | 2019-12-24 | Nxp B.V. | Nonce to message binding in digital signature generation |
| CN114465728B (en) * | 2020-11-09 | 2023-05-16 | 上海复旦微电子集团股份有限公司 | Method, device, equipment and storage medium for attacking elliptic curve signature algorithm |
| CN113271200A (en) * | 2021-05-26 | 2021-08-17 | 陕西理工大学 | Lattice attribute signature method for resisting quantum attack |
| CN114785478B (en) * | 2022-03-30 | 2024-07-09 | 南京航空航天大学 | Side channel correlation energy analysis method and system applied to polynomial hardware multiplication |
-
2022
- 2022-10-12 CN CN202211244166.9A patent/CN115801264B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104852805A (en) * | 2015-05-11 | 2015-08-19 | 中国科学院软件研究所 | SM2 signature algorithm protection method for resisting error attack based on lattice |
| CN104836808A (en) * | 2015-05-12 | 2015-08-12 | 中国科学院软件研究所 | Method for verifying safety of SM2 signature algorithm based on improved difference error attack |
Also Published As
| Publication number | Publication date |
|---|---|
| CN115801264A (en) | 2023-03-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Aoki et al. | Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1 | |
| Faust et al. | Practical leakage-resilient symmetric cryptography | |
| CN109376540B (en) | Image encryption method based on Duffing mapping and genetic operation | |
| US20100169644A1 (en) | Message authentication code with elliptic polynomial hopping | |
| Guo et al. | A new algorithm for solving ring-lpn with a reducible polynomial | |
| JP2011510579A (en) | Countermeasure method and device for asymmetric cryptosystem using signature diagram | |
| CN115801264B (en) | Physical attack method, medium, equipment and system for elliptic curve digital signature | |
| Li et al. | Leakage Resilient Leveled $\mathsf {FHE} $ FHE on Multiple Bits Message | |
| Kuznetsov et al. | Testing of code-based pseudorandom number generators for post-quantum application | |
| CN109660329B (en) | Two-party quantum secret communication method capable of resisting external attack | |
| Zhang et al. | Tolerating sensitive-leakage with larger plaintext-space and higher leakage-rate in privacy-aware Internet-of-Things | |
| Barenghi et al. | A novel fault attack against ECDSA | |
| Wang et al. | Single-Trace Side-Channel Attacks on CRYSTALS-Dilithium: Myth or Reality? | |
| Bucerzan et al. | Improved timing attacks against the secret permutation in the McEliece PKC | |
| CN114244517A (en) | Data encryption and signature method and device, computer equipment and storage medium | |
| JPWO2016063512A1 (en) | MAC tag list generation device, MAC tag list verification device, MAC tag list generation method, MAC tag list verification method, and program recording medium | |
| CN111444522B (en) | Random blocking chaotic image encryption method | |
| Ming et al. | Revealing the weakness of addition chain based masked SBox implementations | |
| Zheng et al. | Confidential assets on mimblewimble | |
| JP2017073716A (en) | Tag list generation device, tag list verification device, tag list updating device, tag list generation method, and program | |
| Zhang et al. | Side‐Channel Attacks and Countermeasures for Identity‐Based Cryptographic Algorithm SM9 | |
| Qin et al. | Leakage-resilient lossy trapdoor functions and public-key encryption | |
| Zhang et al. | Efficient Cloud-Based Private Set Intersection Protocol with Hidden Access Attribute and Integrity Verification. | |
| Xuelong et al. | A symmetric cryptography based on extended cellular automata | |
| Brunetta et al. | Code-based zero knowledge PRF arguments |
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 |