今天終于了解了一番神奇的非對(duì)稱加密算法:橢圓曲線乘法為什么無法反推了,下面介紹一波.
1.橢圓曲線是一個(gè)二維的散點(diǎn)圖
這里用NIST設(shè)立的一條橢圓曲線函數(shù)來介紹,因?yàn)檫@條曲線就是比特幣使用的.這條曲線就是secp256k1標(biāo)準(zhǔn)定義的.公式如下:
y^2 = {{x^3+7}\over{F_p}}
y^2 \mod p = (x^3+7) \mod p
mod p 表明曲線實(shí)在素?cái)?shù)p的限定域中的，也寫作F_p，p的取值為:p = 2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1,是一個(gè)很大的整數(shù)。容易看出橢圓曲線是一個(gè)二維的散點(diǎn)圖。
函數(shù)散點(diǎn)圖很難畫,本人手繪是畫不出來滴,那么我弄了一份簡化了n倍的圖用來做說明.
2.橢圓曲線加法
小學(xué)老師告訴我們：研究乘法，必須先研究加法
在橢圓曲線中,任意兩個(gè)點(diǎn)的和必然存在于曲線上.數(shù)學(xué)定義如下:
p_3 = p_1 + p_2
這里的加法解釋為:p1和p2的連線延長會(huì)和曲線唯一相交,相交的點(diǎn)記為p_3' = (x,y),然后取相交點(diǎn)對(duì)于x軸的映射,得到p_3 = (x,-y)。
如果p1和p2是相同的,那么兩點(diǎn)的連線就是該點(diǎn)的切線.
如果p1是無窮遠(yuǎn)點(diǎn)(沒有坐標(biāo)點(diǎn)),那么p_1+p_2 = p_2,p2類比。
這就是橢圓曲線加法的定義。
3.橢圓曲線乘法
那么在乘法中的應(yīng)用就簡單了，無非就是兩兩相加。這里會(huì)介紹比特幣的那個(gè)乘法:
K = k * G。k是私鑰,G是一個(gè)隨機(jī)常數(shù)，K則是計(jì)算出來的公鑰。
那么上面的乘法等效為：
K = k * G = G+G+....+G
每兩個(gè)來看，G+G就是G的切線和曲線的交點(diǎn)對(duì)x軸映射取點(diǎn)。那么4G = 2G+2G = (G+G) + (G+G)。得G的乘法示意圖：
從一個(gè)G開始,2G就是G+G。同理可得k*G的結(jié)果,當(dāng)然了,如果k是奇數(shù),那么就是(k-1)*G+G。運(yùn)算就是做一次兩點(diǎn)連線延長相交于曲線的點(diǎn)對(duì)x軸映射即可。
4.橢圓曲線簽名很難反推
接下來思考一下，對(duì)于K=k*G，為什么已知輸出K和G,為什么推導(dǎo)不出k呢?
其實(shí)這里存在一個(gè)誤區(qū),這里的乘法是橢圓曲線乘法,并不是小學(xué)的乘法。從上面的計(jì)算可以得知，
$k*G$是在曲線上反復(fù)做切線,并對(duì)x軸取映射點(diǎn)。也就是說，你是無法通過輸出和常數(shù)點(diǎn)來知道你是通過多少次的運(yùn)算得來的，除非你一次計(jì)算每一個(gè)數(shù)值。而這個(gè)數(shù)值很大很大。
55066263022277343669578718895168534326250603453777594175500187360389116729240
這個(gè)數(shù)值是一個(gè)真實(shí)的隨機(jī)生成的私鑰k。如果你要反推，那么你一個(gè)個(gè)遍歷這個(gè)隨機(jī)數(shù)，計(jì)算量就是到k的階乘的橢圓曲線乘法運(yùn)算量了,所以在得出了大家常知的結(jié)論：橢圓曲線簽名很難反推
2018-1-30 更新
前面關(guān)于橢圓曲線簽名有一點(diǎn)補(bǔ)充.
橢圓曲線簽名很難反推,它主要是因?yàn)槟阈枰茖?dǎo)的是它的計(jì)算路徑,而不僅僅是最終結(jié)果.
在橢圓曲線乘法中,你需要反推的是從常數(shù)點(diǎn)G開始畫切線到曲線交點(diǎn),再取x軸在映射點(diǎn).如此反復(fù),得到上圖中的折現(xiàn)路徑.
如果知道私鑰k，那么我折線的路徑是確定的。如果不知道，那么其實(shí)就是要試探每一條可能的折線路徑。而這需要的計(jì)算量是極大的，就目前的計(jì)算機(jī)而言，可以認(rèn)為不可被反推。
