2021SC@SDUSC

secp256k1的引數

前面提到，我們要合理選取橢圓曲線的兩個引數a和b的取值，生成元P點的選取，以及選一個足夠大的素數p，讓橢圓曲線這個群足夠大，并讓生成元P經過多次幾何加法運算生成的回圈子群足夠大，大到可以遍歷橢圓曲線群內全部的點，在secp256k1的標準定義中，生成元是G，所以在下文中我們改用G描述，

在secp256k1中，定義a=0，b=7，也就是說在secp256k1中橢圓曲線方程就是y^2 = x^3 + 7 ，當然在有限域中我們應該寫作y^2 =( x^3 + 7 ) mod p，
有了這兩個引數，我們就可以在實數域中唯一確定橢圓曲線的長相了，大概就是下圖這樣：

但是想在有限域中看到這個影像的樣子卻有些困難，因為在有限域中除了需要知道a和b的值外我們還需要一個素數p，為了讓有限域足夠大，素數又選的很大，在secp256k1中，素數p值為：

這個數大概是10的77次方數量級的，可以想象在一個長寬均為這么大的正方形里面有密密麻麻的滿足y^2 =( x^3 + 7 ) mod p 的點，這些點關于 y=p/2 對稱，這么說或許腦海中已經有個雛形了，那么我們還比較感興趣的是這個影像里面到底有多少個點（包含一個無窮遠點），也就是這個橢圓曲線的秩是多少，答案是：

又是一個天文數字，但我們的擔心又來了：如果我在上面選擇一個生成元，經過標量乘法運算，構成的回圈子群很小該怎么辦，因為上文中我舉出過一個例子，群的秩大不代表群上一個點生成的回圈子群就大，但我們找到了一個生成元G，它的坐標是：

對這樣的一個點，我們不停地用它自己加它自己，也就是G+G+……+G直到最后加完的結果得到G的坐標，也就是又回到了G本身，形成一個回圈群，或者我們可以表述為滿足nG=G的n是多大，答案是這個n和橢圓曲線的秩一樣大，也就是說這一整個橢圓曲線群就是一個回圈群，它的生成元就是G，這個回圈群里面一共有n個點，可以看出來這個a和b的取值，生成元G點的選取，以及足夠大的素數p的選取都是非常巧妙的，

上文中橢圓曲線引數資料來自: https://en.bitcoin.it/wiki/Secp256k1.

公鑰生成

首先在說簽名之前先來說如何根據私鑰生成公鑰，其中私鑰就是{1，2，3……，n-1}中的隨機的一個值，這個n就是上文橢圓曲線的秩n，可見私鑰可以選擇的空間還是非常大的，那么公鑰就是通過私鑰生成的，生成的方法就是標量乘法，用nG得到的橢圓曲線上的一個點就是公鑰，由于這個回圈群遍布群的所有點，因此私鑰和公鑰其實就是一一對應的，唯一的私鑰確定公鑰，公鑰又同時對應一個私鑰，
同時我們可以看到，根據私鑰生成公鑰比較簡單，只需要計算出標量乘法的結果就行了，換句話說，對G點做“私鑰”次幾何加法得到的就是公鑰了，但我們沒必要真一個個加，可以G+G得2G，然后2G＋2G得4G……用指數方式滾雪球算，這樣的話做的次數最多就是 log以2為底2^256的對數 ，也就是幾百次的幾何加法，這對計算機來說還是非常容易完成的；但是根據公鑰找到私鑰確是非常困難的，因為{1，2，3……，n-1}中任何一個數都可能是私鑰，我們只有幾何加法和標量乘法，也沒人告訴我們反過來怎么做，更沒法用滾雪球指數的方法算，因為滾一個雪球可能就少試了一大堆私鑰的可能取值，唯一可行的辦法就是窮舉攻擊：把n代入一個個試，直到結果恰好等于公鑰為止，或許試n個數也沒那么難，但這個n這么大：
私鑰求公鑰，我們進行幾百次幾何加法運算就可以，但根據公鑰求私鑰要進行n次幾何加法運算，這個次數是 2^256 數量級的，可想而知這其中的難度跨度有多大，
對于這種數或許都不會特別敏感，只有告訴我們計算機破解這個結果到底要花多少年我們才有個更加直觀的的感受，下圖是《密碼編碼學與網路安全》中的一組資料：

可以看到128位的密鑰都要540000000年，更何況secp256k1中n的二進制表示是256位，破解所花的年數必然是個天文數字，因此這個私鑰生成公鑰還是挺安全的，

最后我們給私鑰和公鑰給出符號表示：

其中dA就是私鑰，HA就是公鑰，其中：
私鑰就是一個整數，用二進制表示的話有256位；
G就是那個有固定xy坐標的橢圓曲線回圈群生成元；
HA就是有限域橢圓曲線中的某一個點，它具有橫縱坐標，

簽名

簽名就是使用私鑰對要簽名的檔案進行簽名，所以這里要簽名的一方需要準備兩個量：發送方本人的私鑰和要簽名的檔案，簽名要經過六步，下面開始：

第一步，在{1，2，3……，n-1}中取一個亂數k，這里的n就是橢圓曲線的秩，也就是橢圓曲線中點的個數，因此亂數k就是一個二進制256位的數字，
第二步，計算P=kG，其中G是子群的生成元，這里得到的P點實際上就是橢圓曲線上的某一個點，它具有橫縱坐標，
第三步，計算r：

其中xP是P點的橫坐標，P點的橫坐標最大為素數p（當然也可能取不到最大），也就是橢圓曲線橫縱坐標能達到的最大值，前面提到p的值為

而n為

因此P點的橫坐標xP很有可能會比n大，因此需要進行一個取模運算得到一個不大于n的二進制256位數r，
第四步，計算z：

Hash就是一個函式，它可以將任意長度的位元串生成一個定長的位元串，并且將位元串即便只改變一位得到的哈希結果也會天差地別（雪崩效應），并且哈希具有不可逆性，即我可以將一個位元串哈希，但很難給定一個哈希結果說出來那個哈希前的位元串（除非這個對應關系你記錄過，用數學的方法難以求解），此外哈希還是一一對應的，哈希前的結果唯一對應哈希后的結果，反之依然成立，在區塊鏈位元幣中常使用哈希函式有SHA-256，一個任意長度的位元串被SHA-256哈希后的結果就是是256位的定長位元串，
第五步，計算s：

其中k^-1就是模n下k的乘法逆元（滿足該乘法逆元與k的乘積對n取模結果為一，用擴展歐幾里得演算法來求），z和r就是第四、三步分別介紹的，dA就是私鑰，經過有限域GF（n）加法模運算和乘法模運算運算結果就是s，
第六步，生成數字簽名（r，s），數字簽名就是r和s擺在一起組合成的512位（r和s各256位）位元串（這個程序在編譯原理中稱之為連接），這樣就得到了數字簽名，

簽名驗證

簽名驗證就是驗證簽名是否正確，防止有人偽造簽名，如果簽名驗證通過，那么至少可以證明發出這個檔案的確實就是正確的發送方而不是什么別的人，

在說驗簽之前先需要梳理一下目前我們的已知量，因為簽名是本人簽名，而驗簽是所有人都可以驗證，所以有些東西是只有我們本人知道的，有些東西可以讓任何人都知道，目前我們有簽名生成程序中的一些中間量如r、s、z，其中r和s構成了數字簽名，z是對資料的哈希結果，在區塊鏈位元幣中通常稱z為哈希數字摘要，這三個量都是公開的，此外還要橢圓曲線的兩個引數a和b，大素數p，回圈群生成元G，橢圓曲線群的秩n，secp256k1是個公開的演算法，我都可以在網上找到這些引數，那這些引數也就是公開的，此外還有公鑰HA也是公開的，在“公鑰生成”部分我也說過根據公鑰要花幾億年才能求出私鑰，此外還有一個亂數k，下一個目錄會講

驗簽的程序一共有四步：
第一步，使用如下公式求出u1和u2，其中s^-1就是s對模n的乘法逆元，z和r都是公開量，因此我們容易得到u1和u2，

第二步，計算Q，由于G和HA都是橢圓曲線上的點u1和u2都是256位位元串，因此這就相當于對G和HA進行了標量乘法運算，在“公鑰生成”部分提到最多不超過200多步就可以算出標量乘法的結果，計算出新的兩個點u1G和u2HA進行幾何加法運算，在上一篇博客中詳細闡述了計算的方法，得到的結果是Q，

第三步，計算rQ，由于Q是一個點，它必然有橫坐標值xQ，對n取模后得到一個256位位元串rQ，

第四步，驗證rQ是否與r相等，如果相等，則簽名正確，

在著整個程序中我們可以看到，我們沒有用到任何外人不該知道的量就驗證了簽名的正確性，而且計算程序并不復雜，也不需要大的算量，計算機可以很容易地完成，

k

最后你可能會發現一個問題，簽名程序中我用到了一個亂數k，在驗證簽名的時候我沒有用到它，那么這個k是不是可以隨意公開或者訊息簽名時多次使用呢？答案是k既不能泄露，也不能相同，歷史上也有許多使用相同k導致泄密的前車之鑒，

首先先說為什么k不能泄露，
首先我們有這樣一個式子：

在這個式子里面，r和s在簽名中是公開的，z是檔案哈希值也是公開的，如果我們移移項，就會有個很大的發現：

這個式子很令人激動，等于告訴別人，如果k泄露，私鑰dA就可以很容易地求出來，私鑰就泄露了，私鑰泄露你發送的資訊就都泄露了，

然后再來說說為什么k不能重復使用，
首先一般人肯定有個疑惑，一個人甚至一個公司要發送那么多檔案，我怎么知道他是不是用了重復的k，如果他只有幾份檔案用了相同的k我也很難辨別找出來，這個問題我下面會回答，
首先假設我們兩個簽名用了一樣的k，但這兩個簽名簽在了不同的檔案上，我們可以令兩個簽名分別為（r1，s1）和（r2，s2），簽名的檔案哈希分別為z1和z2，a，b，p，G，n都是公開的，哪個檔案簽名都用，公鑰HA由私鑰生成，一個人發的檔案私鑰一樣公鑰肯定也一樣，
對簽名程序生成r的時候我們是這么生成的：

在這個程序中很容易可以看出來，G固定如果k一樣，那么P一定一樣，P一樣那么它的橫坐標xP肯定定值，n固定那么r肯定也一樣，那么我們前面的r1和r2肯定會一樣，這樣就可以回答之前的問題了，判斷是不是用了重復的k很簡單，只要看簽名的前256位（也就是r部分）是不是完全一樣就行了，如果完全一樣那必然就是用了一樣的k，
接下來首先對這個數字簽名s部分生成的式子：

如果是同一個人發送的資料必然使用相同的私鑰dA，如果使用相同的k那么r1=r2，那么r dA這一項就相同，如果代入s1 z1 s2 z2不難構造下面的式子：

通過這三個式子可以看到，如果兩份檔案r的一樣我們推出來k一樣，那么我們完全可以使用兩個檔案的z1 z2 s1 s2來計算得到k，計算得到k就是k泄露問題了，上面也提到泄露了k就是泄露了私鑰，因此k也絕對不能重復使用，

不過好在上面我們推導關鍵步驟還是基于相同私鑰，也就說兩個人碰巧用了相同的k（不過這概率還是很低，畢竟k取值是{1，2，3……，n-1}中的一個，而n又無比巨大），由于使用不同的私鑰因而還是無法攻破他們各自的私鑰，因此只要是一個私鑰就別用相同的k就行了，