歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> 比特幣加密技術之橢圓曲線密碼學

比特幣加密技術之橢圓曲線密碼學

日期:2017/3/1 9:10:09   编辑:Linux編程

在⽐特幣系統中, 我們⽤公鑰加密創建⼀個密鑰對, ⽤於控制⽐特幣的獲取。 密鑰對包括⼀個私鑰, 和由其衍⽣出的唯⼀的公鑰。 公鑰⽤於接收⽐特幣, ⽽私鑰⽤於⽐特幣⽀付時的交易簽名。

公鑰和私鑰之間的數學關系, 使得私鑰可⽤於⽣成特定消息的簽名。 此簽名可以在不洩露私鑰的同時對公鑰進⾏驗證。

⽀付⽐特幣時, ⽐特幣的當前所有者需要在交易中提交其公鑰和簽名( 每次交易的簽名都不同, 但均從同⼀個私鑰⽣成) 。

⽐特幣⽹絡中的所有⼈都可以通過所提交的公鑰和簽名進⾏驗證, 並確認該交易是否有效, 即確認⽀付者在該時刻對所交易的⽐特幣擁有所有權。

(⼤多數⽐特幣錢包⼯具為了⽅便會將私鑰和公鑰以密鑰對的形式存儲在⼀起。 然⽽, 公鑰可以由私鑰計算得到, 所以只存儲私鑰也是可以的。)

私鑰和公鑰

⼀個⽐特幣錢包中包含⼀系列的密鑰對, 每個密鑰對包括⼀個私鑰和⼀個公鑰。 私鑰( k) 是⼀個數字, 通常是隨機選出的。

有了私鑰, 我們就可以使⽤橢圓曲線乘法這個單向加密函數產⽣⼀個公鑰( K) 。 有了公鑰( K) , 我們就可以使⽤⼀個單向加密哈希函數⽣成⽐特幣地址( A) 。 在本節中, 我們將從⽣成私鑰開始, 講述如何使⽤橢圓曲線運算將私鑰⽣成公鑰, 並
最終由公鑰⽣成⽐特幣地址。 私鑰、 公鑰和⽐特幣地址之間的關系如下圖所⽰。


私鑰

私鑰就是⼀個隨機選出的數字⽽已。 ⼀個⽐特幣地址中的所有資⾦的控制取決於相應私鑰的所有權和控制權。 在⽐特幣交易中, 私鑰⽤於⽣成⽀付⽐特幣所必需的簽名以證明資⾦的所有權。 私鑰必須始終保持機密, 因為⼀旦被洩露給第三⽅, 相當於該私鑰保護之下的⽐特幣也拱⼿相讓了。 私鑰還必須進⾏備份, 以防意外丟失, 因為私鑰⼀旦丟失就難以復原, 其所保護的⽐特幣也將永遠丟失。

⽐特幣私鑰只是⼀個數字。 你可以⽤硬幣、 鉛筆和紙來隨機⽣成你的私鑰: 擲硬幣256次, ⽤紙和筆記錄正反⾯並轉換為0和1, 隨機得到的256位⼆進制數字可作為⽐特幣錢包的私鑰。 該私鑰可進⼀步⽣成公鑰。

⽣成密鑰的第⼀步也是最重要的⼀步, 是要找到⾜夠安全的熵源, 即隨機性來源。 ⽣成⼀個⽐特幣私鑰在本質上與“在1到2^256之間選⼀個數字”⽆異。 只要選取的結果是不可預測或不可重復的, 那麼選取數字的具體⽅法並不重要。 ⽐特幣軟件使⽤操作系統底層的隨機數⽣成器來產⽣256位的熵( 隨機性) 。 通常情況下, 操作系統隨機數⽣成器由⼈⼯的隨機源進⾏初始化, 也可能需要通過⼏秒鐘內不停晃動⿏標等⽅式進⾏初始化。 對於真正的偏執狂, 可以使⽤擲骰⼦的⽅法, 並⽤鉛筆和紙記錄。

更准確地說, 私鑰可以是1和n-1之間的任何數字, 其中n是⼀個常數(n=1.158*1077, 略⼩於2^256) , 並由⽐特幣所使⽤的橢圓曲線的階所定義。要⽣成這樣的⼀個私鑰, 我們隨機選擇⼀個256位的數字, 並檢查它是否⼩於n-1。 從編程的⻆度來看, ⼀般是通過在⼀個密碼學安全的隨機源中取出⼀⻓串隨機字節, 對其使⽤SHA256哈希算法進⾏運算, 這樣就可以⽅便地產⽣⼀個256位的數字。 如果運算結果⼩於n-1, 我們就有了⼀個合適的私鑰。 否則, 我們就⽤另⼀個隨機數再重復⼀次。

以下是⼀個隨機⽣成的私鑰( k) , 以⼗六進制格式表⽰( 256位的⼆進制數, 以64位⼗六進制數顯⽰, 每個⼗六進制數占4位) :

1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD

⽐特幣私鑰空間的⼤⼩是2^256, 這是⼀個⾮常⼤的數字。 ⽤⼗進制表⽰的話, ⼤約是1077, ⽽可⻅宇宙被估計只含有1080個原⼦。

公鑰

通過橢圓曲線乘法可以從私鑰計算得到公鑰, 這是不可逆轉的過程: K = k * G 。 其中 k 是私鑰, G 是被稱為⽣成點的常數點, ⽽ K 是所得公鑰。 其反向運算, 被稱為“尋找離散對數”——已知公鑰 K 來求出私鑰 k ——是⾮常困難的, 就像去試驗所
有可能的 k 值, 即暴⼒搜索。

橢圓曲線密碼學解釋

橢圓曲線加密法是⼀種基於離散對數問題的⾮對稱( 或公鑰) 加密法, 可以⽤對橢圓曲線上的點進⾏加法或乘法運算來表達。


上圖是⼀個橢圓曲線的⽰例, 類似於⽐特幣所⽤的曲線。
⽐特幣使⽤了 secp256k1 標准所定義的⼀條特殊的橢圓曲線和⼀系列數學常數。 該標准由美國國家標准與技術研究院
( NIST) 設⽴。 secp256k1 曲線由下述函數定義, 該函數可產⽣⼀條橢圓曲線:

y^2 = (x^3 + 7)} over (Fp)

或 y^2mod p = (x^3 + 7) mod p

上述mod p( 素數p取模) 表明該曲線是在素數階p的有限域內, 也寫作Fp, 其中p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1,這是⼀個⾮常⼤的素數。
因為這條曲線被定義在⼀個素數階的有限域內, ⽽不是定義在實數范圍, 它的函數圖像看起來像分散在兩個維度上的散點圖, 因此很難畫圖表⽰。 不過, 其中的數學原理與實數范圍的橢圓曲線相似。 作為⼀個例⼦, 下圖顯⽰了在⼀個⼩了很多的素數階17的有限域內的橢圓曲線, 其形式為⽹格上的⼀系列散點。 ⽽ secp256k1 的⽐特幣橢圓曲線可以被想象成⼀個極⼤的⽹格上⼀系列更為復雜的散點。


圖為: 橢圓曲線密碼學F(p)上的橢圓曲線, 其中p = 17

下⾯舉⼀個例⼦, 這是 secp256k1 曲線上的點P, 其坐標為(x, y)。 可以使⽤Python對其檢驗:


在橢圓曲線的數學原理中, 有⼀個點被稱為“⽆窮遠點”, 這⼤致對應於0在加法中的作⽤。 計算機中, 它有時表⽰為X = Y =0( 雖然這不滿⾜橢圓曲線⽅程, 但可作為特殊情況進⾏檢驗) 。 還有⼀個 + 運算符, 被稱為“加法”, 就像⼩學數學中的實數相加。 給定橢圓曲線上的兩個點P1和P2, 則橢圓曲線上必定有第三點 P3 = P1 + P2。
⼏何圖形中, 該第三點P3可以在P1和P2之間畫⼀條線來確定。 這條直線恰好與橢圓曲線上的⼀點相交。 此點記為 P3’=(x, y)。 然後, 在x軸做映射獲得 P3=(x, -y)。

下⾯是⼏個可以解釋“⽆窮遠點”之存在需要的特殊情況。 若 P1和 P2是同⼀點, P1和P2間的連線則為點P1 的切線。 曲線上有且只有⼀個新的點與該切線相交。 該切線的斜率可⽤微分求得。 即使限制曲線點為兩個整數坐標也可求得斜率!

在某些情況下( 即, 如果P1和P2具有相同的x值, 但不同的y值) , 則切線會完全垂直, 在這種情況下, P3 = “⽆窮遠點”。

若P1就是“⽆窮遠點”, 那麼其和 P1 + P2= P2。 類似地, 當P2是⽆窮遠點, 則P1+ P2 = P1。 這就是把⽆窮遠點類似於0的作⽤。

事實證明, 在這⾥ + 運算符遵守結合律, 這意味著(A+B)C = A(B+C)。 這就是說我們可以直接不加括號書寫 A + B + C, ⽽不⾄於混淆。

⾄此, 我們已經定義了橢圓加法, 為擴展加法下⾯我們對乘法進⾏標准定義。 給定橢圓曲線上的點P, 如果k是整數, 則 kP =P + P + P + …+ P( k次) 。 注意, k被有時被混淆⽽稱為“指數”。

生成公鑰

以⼀個隨機⽣成的私鑰k為起點, 我們將其與曲線上已定義的 ⽣成點G相乘以獲得曲線上的另⼀點, 也就是相應的公鑰K。 ⽣成點是secp256k1標准的⼀部分, ⽐特幣密鑰的⽣成點都是相同的:

{K = k * G}

其中k是私鑰, G是⽣成點, 在該曲線上所得的點K是公鑰。 因為所有⽐特幣⽤⼾的⽣成點是相同的, ⼀個私鑰k乘以G將得到相同的公鑰K。 k和K之間的關系是固定的, 但只能單向運算, 即從k得到K。 這就是可以把⽐特幣地址( K的衍⽣) 與任何⼈共享⽽不會洩露私鑰( k) 的原因。

因為其中的數學運算是單向的, 所以私鑰可以轉換為公鑰, 但公鑰不能轉換回私鑰。
為實現橢圓曲線乘法, 我們以之前產⽣的私鑰k和與⽣成點G相乘得到公鑰K:

K = 1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD * G

公鑰K 被定義為⼀個點 K = (x, y):

K = (x, y)
其中,
x = F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A
y = 07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

為了展⽰整數點的乘法, 我們將使⽤較為簡單的實數范圍的橢圓曲線。 請記住, 其中的數學原理是相同的。 我們的⽬標是找到⽣成點G的倍數kG。 也就是將G相加k次。 在橢圓曲線中, 點的相加等同於從該點畫切線找到與曲線相交的另⼀點, 然後映射到x軸。


上圖顯⽰了在曲線上得到 G、 2G、 4G 的⼏何操作。

⼤多數⽐特幣程序使⽤OpenSSL加密庫進⾏橢圓曲線計算。 例如, 調⽤EC_POINT_mul() 函數, 可計算得到公鑰。

Copyright © Linux教程網 All Rights Reserved