php生成ecdsa算法簽名,php 簽名算法

本文目錄一覽：

• 1、ECDSA（橢圓曲線數字簽名算法）
• 2、ecdsa算法是不是只能用於簽名而不能用於加密文件？
• 3、[譯]你知道ECDSA是如何保護你的數據的么？
• 4、ECDSA的最簡理解

ECDSA（橢圓曲線數字簽名算法）

ECDSA（Elliptic Curve Digital Signature Algorithm）

在現實工作和生活中，我們使用簽名的方式表達對一份文件的認可，其他人可以識別出你的簽名並且無法偽造你的簽名。數字簽名就是對顯示簽名的一種電子實現，它不僅可以完全達到現實簽名的特點，甚至能夠做的更好。

常用的數字簽名算法有RSA（Rivest-Shamir-Adleman Scheme）、DSS（Digital Signature Standard）等。 比特幣使用ECDSA來生成賬戶的公私鑰以及對交易和區塊進行驗證。

1.Alice（密碼學中常用A到Z開頭的人名代替甲乙丙丁等，字母越靠後出現頻率越低）生成一對密鑰，一個是sk（signing key），是非公開的；另一個是vk（verification key），是公開的。

這一對密鑰同時生成，並且在數學上是相互關聯的，同時，根據vk無法推測出關於sk的任何信息。

2.數字簽名算法接收兩個輸出：信息M和sk，生成一個數字簽名Sm

3.驗證函數接收信息M、Sm以及vk作為輸入，，返回結果是yes或者no。這一步的目的是為了驗證你看到的針對信息M的數字簽名確實是由Alice的sk來簽發的，用於確認信息與簽名是否相符。

與手寫簽名不同，手寫簽名基本都是相似的，但是數字簽名卻受輸入影響很大。對輸入輕微的改變都會產生一個完全不同的數字簽名。一般不會對信息直接進行數字簽名，而是對信息的哈希值進行簽名。由加密哈希函數的無碰撞性可知，這樣和對原信息進行簽名一樣安全。

在數學上，任何滿足以下方程的點所形成的曲線稱為隨機橢圓曲線： 並且 ，a和b可以為任意值。下面展示幾個隨機橢圓函數的示例：

在了解如何通過基於secp256k1橢圓曲線的ECDSA算法生成公私鑰之前，我們需要了解在隨機橢圓曲線里，點的加法是如何實現的。

首先定義橢圓曲線上點的加法。設橢圓曲線上有兩點，A和B點，那麼作過這兩點的直線與該曲線相交於第三點（C點），然後關於X軸對稱得到D點，則D為這兩個點的和，記作D=A+BD=A+BD=A+B。很明顯，D點也在該曲線上。所以橢圓曲線上兩點之和也是曲線上的點。

特例：

1.如果兩點重合，則做該點的切線，與曲線相交點的對稱點為和，即A+A=C

如圖：

有了加法以後，乘法實現是不過是進行多次加法運算。有了一個基準點P以後，我們可以對其進行乘法運算，最後可以得到曲線上的另外一個點。

設PPP是橢圓曲線上的一個點，那麼正整數kkk乘以點PPP的結果由下面的式子定義，注意式子中的加法是上面提到的橢圓曲線上點的加法：

點的運算滿足結合律：

很顯然，通過累加 的方式計算 是一種很笨的辦法，其時間複雜度是線性的。上面我們提到過，橢圓曲線上點的加法是滿足結合律的，即 ，擴展一下，就有

於是就有這麼一種騷操作，比如計算 ，我們可以先計算 ；然後計算 ；再計算 ；最後計算 。這裡我們把15次加法減少到了4次。

當然，k的值不可能總是2的冪。實際上上面的操作可以推廣到k為任意正整數的情況。比如計算23P，首先計算 ，然後

因為 ，所以 。總共只需要7次加法。

分析一下，對於任意正整數k，我們都可以利用這個方法將計算k∗P所需的加法計算次數降低到

也就是說，從時間複雜度的角度來看，這個算法是一個 的算法。

這個方法被稱為快速冪算法，原本常用於快速計算某個數的k次冪，這裡將其推廣到橢圓曲線點乘的快速計算中。

為什麼要在介紹了橢圓曲線上點的乘法後突然冒出一個快速冪算法？快速冪算法對於橢圓曲線加密有什麼意義？因為數學家/密碼學家發現，利用快速冪算法計算 的時間複雜度是對數級的，但是要在知道 和 的前提下，倒推出 的值，沒有比挨個嘗試 的值快太多的算法。於是橢圓曲線加密依賴的數學難題就這麼誕生了。

如果我們改一種記法，把橢圓曲線上點的加法記作乘法，原來的乘法就變成了冪運算，那麼上述難題的形式跟離散對數問題應該是一致的。即：

所以這個難題叫橢圓曲線上的離散對數問題。

儘管兩者形式一致，但是他們並不等價。實際上這個問題比大整數質因子分解（RSA）和離散對數（DH）難題都要難得多，目前還沒有出現亞指數級時間複雜度的算法（大整數質因子分解和離散對數問題都有），以致於同樣的安全強度下，橢圓曲線加密的密鑰比RSA和DH的短不少，這是橢圓曲線加密的一大優勢。

假設隨機取一個 ~ 位之間的值x，計算 ，最後的結果一定會落在曲線上的一點。假設該點為 ，在公開 以及具體曲線的方程的情況下，能否反推出最初的隨機值 ？

證：尋找 的過程只能通過暴力計算， 的可能值為 ~ 中的一個，平均來說需要計算 次能夠找到一次 值。那麼問題來了，運行一次 的計算需要多長的時間呢？

假設我們使用的是超級計算機，主頻為 （一秒鐘可以進行一萬億次運算），從宇宙誕生的那一刻開始計算，到現在也就進行了 次。找到 值的概率為 。這個概率和下一秒地球被巨型隕石撞擊而毀滅的概率接近，既然我們讀到了這裡，那麼說明這件事沒有發生。

在上面的案例中， 是 ~ 位的一個隨機數，可以作為私鑰。 是隨機橢圓曲線上的一個點，也就是由私鑰生成的公鑰，因此優點可以1得證。

但是密碼學中，並不能使用上面介紹的實數域上的橢圓曲線。因為

所以我們需要引入有限域上的橢圓曲線。

要證明優點2，還需要將隨機橢圓曲線做一些改動：為了保證最後計算出來的點的坐標值相加是512位，secp256k1引入了一個對質數取模的機制。具體來說，隨機橢圓曲線從

變為了 其中 ，是小於 的最大質數。

此時的隨機橢圓曲線函數圖如下：

具體來說，就是向別人證明我知道 ，但不暴露 的任何信息。（有些類似於零知識證明）

證：前面介紹過結合律： 添加一個hash函數，簡單修改可以得出： 使 ，那麼可知 為 。此時方程為： 為了簡單起見，我們記 和 。此時方程化簡為： 上面這個方程是什麼意思呢？

可以這樣假設：在已知 的情況下，如果能夠提供一個 和 滿足上面的方程，就可以證明一個人擁有 。這個假設有一個前提，如果一個人不知道x，那麼他就無法提供 和 滿足上面的等式。

詳細探討這個前提：如果一個人不知道x，又想計算出 和 ，能夠辦到嗎？結論是不能，首先我們無法從 計算出 （在有限時間內）。

還有一個問題：在已知 和 的情況下，能否計算出關於 的任何信息？

根據公式： 只要解出 就可以了。

要想計算出x，就需要知道r，但是在r沒有公開的情況下，有什麼辦法可以計算r嗎？我們知道R=r*P；但是根據這個公式無法倒推出r（剛才介紹的那個數學難題），所以x也是安全的。

至此，可以證明算法的第二個優點。

ecdsa算法是不是只能用於簽名而不能用於加密文件？

ECDSA只能用於簽名，但是有一種基於ECC的方法可以實現公鑰加密

首先選好曲線Ep(a,b,G,n,h)，隨機選取私鑰k，計算公鑰：K=kG，信息被編碼在點M上

加密：隨機選取r，密文為(rG,M+rK)

解密：計算(M+rK)-k(rG)，因為它等於(M+rK)-r(kG)=M+rK-rK=M

[譯]你知道ECDSA是如何保護你的數據的么？

每個人都可能以某種形式聽說過ECDSA。當我說「數字簽名」時，有些哥們會更好地認識到這一點，當然有些哥們根本不知道我在說什麼。

我曾經試着去了解ECDSA是如何工作的，但很難搞清楚，因為大多數在線參考文獻是不夠的。他們要麼是太基本了 – 他們只是解釋算法的基礎知識， 或者他們太牛叉-「它是如何工作的？」 。所以你在「它是如何工作的」和「我們是如何到達這裡的？」之間掙扎着。所以，如果你沒有數學或密碼學的學位，但仍然想知道它是如何工作的（除非「奇蹟發生，或者你是天才」），那麼，恭喜你，你來對地方了。

ECDSA 全稱 「 Elliptic Curve Digital Signature Algorithm 」，它用於創建數據的數字簽名（例如文件），以便在不影響安全性的情況下驗證其真實性。把它想像成一個真實的簽名，你可以識別某人的簽名，但是如果沒有其他人知道你就不能偽造它。 ECDSA簽名與真實簽名之間的區別在於，偽造ECDSA簽名是不可能的。

理解 ECDSA 要注意區分其與用於加密數據的 AES（高級加密標準）的區別。ECDSA不會加密或阻止某人查看或訪問你的數據，但它可以防止數據被篡改。

在「ECDSA」這裡有兩個詞值得注意，那就是「曲線」和「算法」，因為這意味着 ECDSA 基本上都是關於數學的。所以我認為首先要說：「嗨，兄弟們，你現在還在扯學的那些高數完全沒有什麼卵用么！「ECDSA涉及到的數學是相當複雜的，所以我盡量庸俗化，讓非技術人員可以理解，但你仍然可能需要一些在數學知識正確理解。下面，我將分兩部分來處理，一部分是關於它是如何工作的一個高層次的解釋，另一部分是深入理解其內部的工作原理。

其實原理很簡單，你拿出紙來，繪製一個數學上的曲線方程，然後你在該曲線上隨機選擇一點作為你起始的點，然後你生成一個隨機數，這是你的私鑰，你用這個隨機數和「起點」來做一些神奇的數學方程，並且在曲線上得到第二個點，那就是你的公鑰。

當你想簽署一個文件時，你將使用這個私鑰（隨機數）和一個散列的文件（一個唯一的數字來表示文件）為一個神奇的方程，這會給你你的簽名。簽名本身分為兩部分，分別稱為R和S.為了驗證簽名是否正確，您只需要公鑰（使用私鑰生成的曲線上的那個點），然後將其放入另一個神奇的方程與簽名的一部分（S），如果它使用私鑰正確簽名，它會給你另一部分的簽名（R）。所以為了簡短起見，一個簽名由兩個數字R和S組成，你用一個私鑰生成R和S，如果一個使用公鑰和S的數學方程給你R，那麼簽名是有效的。沒有辦法知道私鑰或僅使用公鑰創建簽名。

OK，目前你只了解了一點基礎知識，你或許沒意識到，ECDSA 是複雜的，公鑰、私鑰又是什麼鬼？別擔心，你馬上就會明白，但首先解釋一下，為什麼使用ECDSA以及它可能有什麼用？

除了上述提到的「我需要簽署合同/文件」之外，下面是一些別的用例：例如，我們不希望其數據被用戶破壞或修改，例如只允許用戶你加載官方地圖但不可以進入國防部或電話或其他類型的設備，只允許你安裝官方的應用程序。

在這種情況下，文件（應用程序，遊戲地圖，數據）將用 ECDSA 簽名，公鑰將與應用程序/遊戲/設備捆綁在一起並驗證簽名，以確保數據沒有被修改，而私鑰被鎖在一個安全的地方。雖然你可以使用公鑰驗證簽名，但是你不能用它創建/偽造一個新的簽名，那麼這個公鑰就可以隨應用/遊戲/設備一起分發，而不用擔心。

這與AES加密系統不同，後者允許您對數據進行加密，但您需要密鑰進行解密，而這樣的應用程序需要捆綁你的密鑰。

一個很好的例子就是PlayStation 3遊戲機被打開了，所有的文件都可以被解密，PS3文件中的所有密鑰都可以被提取出來，但是還有一件東西需要破解，就是ECDSA簽名，它可以防止任何人使應用程序運行在最新的固件上

再通俗一點的解釋，http與https的區別，我們擁有一個SA認證機構，私鑰拿在自己手裡，公鑰廣播出去，我拿私鑰驗證公鑰（這個僅僅是用來理解公鑰和私鑰，到此為止啊）。

OK，接下來建議你備好垃圾桶，可能會感到噁心或者不適。

讓我們從基本知識開始（對於知道這個知識的人可能是無聊的，但對於那些不了解的人是必須的）：ECDSA只使用整數數學，沒有浮點數（這意味着可能的值是1，2，3等等，但不是1.5, 2.5等），而且數字的範圍受到簽名中使用多少比特的限制（更多比特意味着更大的數字，更高的安全性，因為猜測變得更難（在這個等式中使用的關鍵數字）。計算機使用「位」來表示數據，一位是二進制符號（0和1）中的「數字」，而8位代表一個位元組。每增加一位，可以表示的最大數量加倍，4位可以表示0到15（總共16個可能的值），5位可以表示32位數值，6位，您可以表示64個值等。一個位元組（8位）可以表示256個值，32位可以表示4294967296個值（4千兆）。通常ECDSA將使用總共160位，嗯哼，一個 49 位大的數字…..

你需要知道的另一個數學結構是模數，可以通過說它是整數的其餘部分來簡化模數。例如，x mod 10意味着x除以10的其餘部分，它將始終是0和9之間的數字，所以142 mod 10例如給出2。另一個例子是x mod 2，其中偶數和0分別為0和1。

ECDSA 與消息的 SHA1 加密散列一起使用來簽名（文件）。哈希是另一個數學方程式，適用於每個數據位元組，這將給一個數據唯一的數字。例如，所有位元組的值的總和可以被認為是非常 low 的散列函數。所以如果消息（文件）有任何變化，那麼哈希將是完全不同的。在 SHA1 哈希算法的情況下，它總是 20 個位元組（160位）。這對於驗證文件沒有被修改或損壞是非常有用的，對於任何大小的文件，你都會得到 20 位元組的哈希值，你可以輕鬆地重新計算哈希值以確保匹配。 ECDSA 所標記的實際上就是散列，所以如果數據發生變化，散列會發生變化，而且簽名不再有效。

為了理解，我們來一個例子。我們將使用最簡單的（和最 low 的）散列函數，其中我們將所有數據的總和作為結果的模數10。

首先，你需要明白一點，世間萬物將被用一個數字來表示。一個文本文件是一系列的位元組，正如我們前面所解釋的，它代表了8位，這意味着它可以表示一個介於0和255之間的數字。所以，如果我們將每個位元組作為一個數字並添加文件的每個位元組，那麼我們結果為 10 的模數，我們將以 0 到 9 之間的數字作為結果散列。數據相同，我們將總是得到相同的哈希值，如果更改了文件中的一個位元組，結果可能會不同。當然，你也會明白，為了獲得相同的散列值，改變文件將是非常容易的，因為只有10種可能性（0到9），那麼就有十分之一的機會獲得相同的散列值通過改變文件的內容。

這就是 SHA1 起作用的地方，SHA1 算法比我們簡單的「模數 10 」散列函數複雜得多，它將給出非常大的數字（160位，所以是一個十進制的49位數），它的特殊性使得我們如果從文件中修改了一位數據，結果就會徹底改變。

這使得 SHA1 成為一個非常好的哈希算法，這種算法是不可預知的，這是非常安全的，並且幾乎不可能得到「衝突」（當兩個不同的文件具有相同的哈希），並且不可能偽造數據來獲得特定的哈希，如果你 OK 的話，不要聽我逼逼了，建議你參加最強大腦。

那麼，它是如何工作的呢？ECDSA是基於下面的一個方程等式：

y^2 = (x^3 + a * x + b) mod p

你首先需要注意的是有一個模（mod），並且 ‘y’ 是平方的（不要忘記這是圖上曲線的方程）。這意味着對於任何x坐標（不要忘記，我們只使用整數），您將有兩個y值，並且曲線在X軸上是對稱的。該模是一個素數，並確保所有的值在160位的範圍內，它允許使用「 modular square root 」和 「 modular multiplicative inverse 」

的數學，使計算的東西更容易。由於我們有一個模（p），這意味着 y ^ 2 的可能值在 0 和 p-1 之間，這之間便是所有可能的值。因為，ECDSA規定只能是整數，只有那些值較小的子集才能構成一個「完美平方」（兩個整數的平方值），這給了 N 個可能的點，其中 N p（N 是數字 0 和 p 之間的完美平方）。到目前為止，你確定還能跟着我的思路么？哈哈，不着急，剛剛開始。。。)

由於每個 x 將產生兩個點（y ^ 2的平方根的正值和負值），這意味着有 N / 2 個可能的 「x」 坐標是有效的，並在曲線上給出一個點。因為整數計算和模數的限制，所以符合這些條件的點在橢圓曲線上是有限的。

總結一下，然後再繼續。 ECDSA方程為我們提供了一個有限數量的有效點的曲線（N），因為 Y 軸受模量（p）的約束，並且需要是在 X 軸上具有對稱性的完美平方（y ^ 2） 。我們總共有 N / 2 個可能的，有效的 x坐 標，不要忘記 N p。

關於橢圓曲線你需要知道的另一件事是「點加法」的概念。它被定義為增加一個點 P 到另一個點 Q 將導致一個點 S，使得如果你繪製一條線從 P 到 Q，它將與第三個點 R 上的曲線相交，這是 S 的負值（記住該曲線在X軸上是對稱的）。在這種情況下，我們定義了R = -S來表示R在X軸上的對稱點。看上面的圖來理解。

所以你可以看到一個形式為y ^ 2 = x ^ 3 + ax + b（其中a = -4和b = 0）的曲線，它在 X 軸上是對稱的，其中 P + Q 是對稱點 R 點是從 P 到 Q 的直線的第三個交點。

同樣的，如果你做 P + P，它將是 R 的對稱點，它是與點 P 相切的線的交點。P + P + P 是所得點之間的相加點由於 P + P + P可以寫成（P + P）+ P，這就定義了「點乘法」，其中 k * P 是點 P 到點 K 的相加點。看看上面的兩個圖像點乘法的例子。

在這裡，你可以看到兩條橢圓曲線和一條從中畫出切線的點 P，它與曲線相交於第三點，其對稱點是 2P，然後從那裡你從 2P 和 P 畫出一條直線，會與曲線相交，對稱點為3P。等等…你可以繼續做點乘法。現在是否明白了為什麼在進行加法時需要取 R 的對稱點，因為相同點的多次加法總會給出相同的直線和相同的三個交點。

點乘法的一個特殊性是，如果你有一個點 R = k * P，那麼你知道 R 並且知道 P，但是沒有辦法找出 ‘k’ 的值是什麼。由於沒有點減法或點除法，所以不能只求解 k = R / P。另外，由於你可能做了數百萬次的增加，你只能在曲線上的另一個點上，你不知道你是怎麼到達的。你不能扭轉這個操作，而且你找不到與你的點 P 相乘的值 「k」，給你的結果點 R.

即使你知道原始點和終點也不能找到被乘數的東西是ECDSA算法背後安全的基礎，這個原理被稱為 「 陷阱門函數 「。

上面是對 ECDSA 的鋪墊，接下來讓我們認識一下 ECDSA 簽名算法的廬山真面目。

對於 ECDSA，首先需要知道曲線參數，參數是 a，b，p，N 和 G. 您已經知道 a 和 b 是曲線函數的參數（y ^ 2 = x ^ 3 + ax + b），即 ‘p’ 是質量模數，’N’ 是曲線的點數，但也有 ‘G’ 是ECDSA所需要的，它代表一個’參考點’或者你可以理解為一個起點。參考點可以是曲線上的任何點。

曲線上的參數是非常重要的，不知道它們，你顯然不能簽名或驗證簽名。是的，驗證簽名不僅僅是知道公鑰，還需要知道公鑰的派生參數。 NIST（美國國家標準技術研究院）和SECG（高效密碼學標準組織）提供已知安全和高效的預製和標準化曲線參數。

所以首先，你將擁有一個私鑰和一個公鑰。私鑰是一個隨機數（也是160位），並且公鑰是由 G 的點乘所生成的曲線上的一個點與私鑰。我們把’dA’作為私鑰（隨機數）和’Qa’作為公鑰（一個點），所以我們有：Qa = dA * G（其中G是曲線參數中的參考點）。

那麼你如何簽署一個文件/消息？

首先，你需要知道簽名是 40 個位元組，並且用兩個 20 位元組的值來表示，第一個被稱為 R，第二個被稱為 S ..所以這個對（R，S）一起是你的 ECDSA 簽名..現在這裡是如何創建這兩個值，以簽署一個文件..首先你必須生成一個隨機值 ‘k’（20個），並使用點乘法來計算點 P = k * G。那個點的 x 值將代表 ‘R’。由於曲線 P 上的點由其坐標（x，y）表示（每個坐標長度為20個位元組），因此只需要簽名的 「x」 值（20個位元組），該值將被稱為「R」 。現在你需要的是 「S」 值。

為了計算 S，你必須做一個消息的 SHA1 哈希值，這會給你一個 20 位元組的值，你會認為它是一個非常大的整數，我們稱它為 ‘z’。現在你可以用下面的公式計算S：

S = k ^ -1（z + dA * R）mod p

這裡注意到k ^ -1是k的 「模乘法逆」，它基本上是 k 的倒數，但由於我們正在處理整數，所以這是不可能的，所以它是一個數字，使得（k ^ -1 * k）mod p等於1.再次提醒，k 是用於生成 R 的隨機數，z 是要簽名的消息的哈希，dA 是私鑰，R 是 k 的 x 坐標 * G（其中G是曲線參數的原點）。

現在你已經簽名了，你想驗證一下，它也很簡單，你只需要公鑰（當然是曲線參數）就可以做到這一點。你用這個公式來計算一個點P：

P = S ^ -1 * z * G + S ^ -1 * R * Qa

如果點P的x坐標等於R，表示簽名有效，否則不是。

很簡單，是吧？現在讓我們看看為什麼..這將需要一些數學來驗證：

我們有 ：

P = S ^ -1 * z * G + S ^ -1 * R * Qa

但是 Qa = dA * G，所以：

P = S ^ -1 * z * G + S ^ -1 * R * dA * G = S ^ -1（z + dA * R）* G

但是P的x坐標必須與R相匹配，而 R 是k * G的 x坐標，這意味着：

k * G = S ^ -1（z + dA * R）* G

我們可以通過刪除G來簡化：

k = S ^ -1（z + dA * R）

通過反轉K和S，我們得到：

S = k ^ -1（z + dA * R）

這就是用來生成簽名的公式。所以它是匹配的，這就是為什麼你可以用上面第一個方程驗證簽名的原因。

你可以注意到，為了計算 S，您需要 ‘k’（隨機數）和 ‘dA’（私鑰），但只需要 R和 Qa（公鑰）來驗證簽名。由於 R = k * G 和 Qa = dA * G，並且由於ECDSA 點乘法中的陷阱門函數（在步驟9中說明），所以我們不能通過知道 Qa 和 R 來計算 dA 或 k，這使得 ECDSA 算法是安全的，找不到私鑰，沒有辦法在不知道私鑰的情況下偽造簽名。

所以你還記得產生一個簽名所需的等式吧。 R = k * G 和 S = k ^ -1（z + dA * R） 模 p 這個等式的強度是事實上你有一個等式未知數（k和dA），所以無法確定其中之一。

然而，算法的安全性是基於其實現的，確保「k」是隨機生成的，並且沒有辦法讓某人可以猜測，計算或使用計時攻擊或任何其他類型的攻擊為了找到隨機值’k’。但索尼在實現上犯了一個巨大的錯誤，他們在每個地方都使用相同的「k」值，這意味着如果你有兩個相同的k，那麼它們將具有相同的R值，這意味着您可以使用兩個文件的兩個S簽名（分別為哈希z和z’以及簽名S和S’）來計算k：

S – S』 = k^-1 (z + dA*R) – k^-1 (z』 + da*R) = k^-1 (z + da*R – z』 -dA*R) = k^-1 (z – z』)

So : k = (z – z』) / (S – S』)

一旦你知道了k，那麼S的方程就變成了一個方程，其中有一個未知數，然後很容易解析為dA：

dA =（S * k-z）/ R

一旦你知道了私鑰dA，你現在就可以簽名你的文件，PS3將把它識別為索尼簽署的真實文件。這就是為什麼確保用於生成簽名的隨機數實際上是「密碼隨機」的原因。這也是為什麼不可能擁有高於 3.56 的自定義固件的原因，僅僅是因為自從 3.56 版本以來，索尼已經固定了他們的 ECDSA 算法實現並且使用了現在不可能找到私鑰的新密鑰。

這個問題的另一個例子是，當一些比特幣客戶端使用非密碼隨機數生成器（在某些瀏覽器和某些Android客戶端上）導致他們使用相同的「k」值簽名交易時，惡意人員能夠找到他們的比特幣錢包的私鑰和竊取他們的資金。

這顯示了每次簽名時使用真正的隨機數字的重要性，因為如果（R，S）簽名對的R值在兩個不同的簽名上相同，您將公開私鑰。

關於這個的一個笑話在xkcd漫畫221（見上圖）中顯示，這成為了解釋這個問題的前景。每當這種算法的執行錯誤發生時，圖像經常被重新使用。

ECDSA算法是非常安全的，不可能找到私鑰……只要實現正確完成就行了。如果有辦法找到私鑰，那麼每個計算機，網站，系統的安全性可能會受到影響，因為很多系統都依靠 ECDSA 來保證安全性，這是不可能的。

但願這能夠幫助大家初步理解ECDSA算法，也希望對大家有所幫助。

原文鏈接： Understanding-how-ECDSA-protects-your-data

ECDSA的最簡理解

y^2 = (x^3 + a * x + b) mod p

上述的曲線是在整數，一定bit數量（假設是160bit）內可以表達的，p是 160bits內可以表示的大整數。

為什麼是這種曲線定義呢，我個人覺得有3個原因：

在橢圓曲線上隨意取兩個點 A，B，連接A，B兩個點的直線與曲線的新的交點稱為C，C關於X對稱的-C點表示為 A+B。

乘法可以用加法表示，但是算法複雜堵是 log(n)。

其實為什麼選擇上述的橢圓曲線實際上是由這個加法規則選出來的，總是要求解這個新的交點更加簡單。

R=k*P 的性質，已知R與P的值，無法推出k的值, 而知道k值於P值是很容易計算R值(log(n))。這是ECDSA簽名算法的理論基礎。

如何利用這個門限函數來做一個簽名算法呢？

一個順理成章的想法是： 給驗證人一個 R和P，那只有簽名人才能提供K，那K是不是可以作為一個簽名指紋呢？

ok，咱先生成一個公私鑰對， Qa = dA * G , Qa 就是公鑰， dA 是一個隨機數，就當是一個私鑰吧，當然這個橢圓曲線的 a , b , p , G 值都是要公開的。這個 G 就是橢圓曲線上隨機挑選的一個節點，我們叫原點，也是要公開的。

每次對一個數據做簽名，都隨機生成一個隨機數 K 吧， P = K * G 。咱們把 P的x軸坐標R作為簽名的一部分。另一部分簽名數據叫 S 。

顯然這個 S 既要和 dA 相關，也要和被簽名的信息 z 相關。我們就假定：

S = Sig(dA, G, z, R, K) , 那這個函數就是簽名函數。

而驗證函數應該只有 S,R ,而不會有 K，dA

P = h(S, G, z, R) , h 就是簽名函數。

密碼學專家想到了一個實現：

S = k^-1 (z + dA * R) mod p

k^-1 表示的是關於p的模逆元。（ k^-1 * k mod p = 1）。

可以推倒初驗證函數：

== k = S^-1 (z + dA * R) mod p

== k*G = S^-1 (z + dA * R) *G

== P = S^-1*z*G + S^-1*dA*R*G

== P = S^-1*z*G + S^-1*R*Qa

對於驗證者來說，需要計算： S^-1*z*G + S^-1*R*Qa 的x坐標是否就是 R 。

go的橢圓曲線 a 為固定的-3， 而 b 可以自由的選擇，而p224, p256曲線的其實指的是 曲線的bit位數是224和256。

算法實現着為了更加快速地執行曲線上的加法和乘法，對笛卡爾坐標做了投射成(x,y,z)的雅各布坐標，投射關係：

可以加速在雅各布坐標繫上的運算，在需要最終結果的時候再投射回笛卡爾坐標系。

一個曲線的表示：

公私鑰對的表示：

可以看出曲線，公鑰，私鑰擁有的信息越來越全。

公鑰是 曲線信息+ dA*G的信息。

私鑰是 公鑰信息 + dA信息。

美國國安局發佈的曲線其實是 secp256k1 ， 對於其參數其實沒有很好的解釋，大家猜測是國安局找到了這是一條弱化的橢圓曲線，因此BTC在設計之初也沒有採用這個曲線，而是用了 Koblitz Curve , b 是7， a 是0，btcsuit的package中，對 KoblitzCurve 是golang的 curvparam 的一層封裝(主要是為了加速)，但是有更多的參數， 是因為a和b等參數都是預先設定的，增加更多的參數來加速計算。至於公私方法和golang基本一樣。

Ed25519 從某種意義上來說也屬於橢圓曲線密碼學，不同的是它採用扭曲愛德華茲曲線作為橢圓曲線，同時採用的簽名機制也不同於 ECDSA 算法。EdDSA 的重要實現 ED25519 是 Daniel J. Bernstein 等人設計的 EdDSA 算法，採用的曲線參數完全公開，並說明了參數選取的意義，保證曲線中並未內置後門。

曲線：

y^2 = (x^3 + x^2 + {一個很大的隨機數}x ) mod p

他生成公私鑰的流程有一些區別，seed作為私鑰，seed計算出的hash值去和G相乘得到公鑰，為了防止多次計算，把這部分公鑰擴展到私鑰的後面作為一個完整的私鑰。計算簽名的時候，普通ecdsa會生成一個隨機數K，而ec25519為了避免偽隨機數被猜測到，因此是私鑰和msg的hash值作為這個隨機數。