blocksight 2021-04-26 13:36:47 阅读数:857
In the last section, we introduced Elliptic curve encryption and decryption in discrete domain , This section continues to introduce the process of elliptic curve signature and verification over discrete fields , And give an example to illustrate .
First, make the following symbol convention ： The key pair of the user who initiated the signature :（d, Q）;(d For private key ,Q For public key ), The last section said d It's a secret big integer ,D It's a point on the elliptic curve .G: The generator [ Primitives ] Information to be signed ：M;
Choose the order of elliptic curve point group ：n
Signature result ：Signature(M) = ( r, s)
Next, let's look at the signature process ：1、 Pick an integer at random k, And 0 < k < n2 Calculation R = k * G=（） notes ：1,2 The steps can also be described as ： Randomly generate a key pair (k, R), R=（）3、 Make r = mod n, If r = 0, Then go back to step 14、 Calculation H = Hash(M)5、s = (H + rd) mod n, if s = 0, Then go back to step 16、 Output S =(r,s) Is the signature .r yes R The abscissa of , Some articles say that the signature result S =(R,s) use R As the first part , It's OK, too , It's essentially the same , Just take it out at verification time r.
Use the same symbol rules as above , received Signature(M) = ( r, s) The signature result of , The verification process is as follows ：1、 Calculation H = Hash(M)2、 Calculation u1 = mod n, u2 = mod n3、 Calculation R = (, ) = u1G + u2Q, If R = zero , Verify that the signature is invalid 4、 Make v = mod n5、 if v == r, Then the signature is valid , otherwise , The signature is invalid .
You can see , The verification process uses <r,s>, The signer's public key Q, And news M And so on . Why can it be verified like this ？ Let's deduce ：R=u1G + u2Q=( mod n)G + ( mod n)Q= ( mod n)G + ( mod n) dG=G((H + rd) mod n)=G*ks=kG=R
r yes R The abscissa module of n, This is the end of the validation .
The parameter in the elliptic curve equation is selected as ：𝑎=0, 𝑏=−4,𝑝=199,𝐺=(2,2), The elliptic curve equation is ：mod 199−4) mod 199【 Be careful ： If written −4 It's a rogue writing 】 here n=217, hypothesis B The selected private key is d=13, Its public key :Q=13𝐺=(165,33) The message assumes that the message M After the summary H=58. Signature process ： Random selection k=23, Calculation R = k * G=23(2,2)=(15,171) Make r = mod n= 15 mod 217=15 Calculation ：s = (H + rd) mod n=(58+15*13)/23 mod 217 = 11
Get the signature result ：Signature(M) = ( r, s)=（15,11）
Verification process ： Use the same symbol rules as above , received Signature(M) = ( r, s)=（15,11） The signature result of , The verification process is as follows ：1、 Calculation H = 58 （ Suppose the content ）2、 Calculation u1 = mod n=58*79 mod 217=25, （1/s Modular inverse ：79）u2 = mod n = 1579 mod 217=1003、 Calculation R = (, ) = u1G + u2Q= 25(2,2) + 100(165,33)=(160,175)+ (5,11)=(15,171)4、 Make v = mod n = 15 mod 217 =15=r Verify that the signature is valid .
As mentioned in the previous section , Practical elliptic curve algorithm chooses very large integer as each parameter , But the principle is the same .
The next section talks about the process of Duffy Herman key exchange . Welcome to forward , If you have any questions, please leave a message ！！