今天終于了解了一番神奇的非對(duì)稱(chēng)加密算法:橢圓曲線(xiàn)乘法為什么無(wú)法反推了,下面介紹一波.

1.橢圓曲線(xiàn)是一個(gè)二維的散點(diǎn)圖

這里用NIST設(shè)立的一條橢圓曲線(xiàn)函數(shù)來(lái)介紹,因?yàn)檫@條曲線(xiàn)就是比特幣使用的.這條曲線(xiàn)就是secp256k1標(biāo)準(zhǔn)定義的.公式如下:

mod p 表明曲線(xiàn)實(shí)在素?cái)?shù)p的限定域中的，也寫(xiě)作Fp，p的取值為:p=2256?232?29?28?27?26?24?1,是一個(gè)很大的整數(shù)。容易看出橢圓曲線(xiàn)是一個(gè)二維的散點(diǎn)圖。

函數(shù)散點(diǎn)圖很難畫(huà),本人手繪是畫(huà)不出來(lái)滴,那么我弄了一份簡(jiǎn)化了n倍的圖用來(lái)做說(shuō)明.

2.橢圓曲線(xiàn)加法

小學(xué)老師告訴我們：研究乘法，必須先研究加法

在橢圓曲線(xiàn)中,任意兩個(gè)點(diǎn)的和必然存在于曲線(xiàn)上.數(shù)學(xué)定義如下:

如果p1和p2是相同的,那么兩點(diǎn)的連線(xiàn)就是該點(diǎn)的切線(xiàn).

如果p1是無(wú)窮遠(yuǎn)點(diǎn)(理解為加法中的零),那么p1+p2=p2,p2類(lèi)比。

這就是橢圓曲線(xiàn)加法的定義。

3.橢圓曲線(xiàn)乘法

那么在乘法中的應(yīng)用就簡(jiǎn)單了，無(wú)非就是兩兩相加。這里會(huì)介紹比特幣的那個(gè)乘法:K=k?G。k是私鑰,G是一個(gè)隨機(jī)常數(shù)，K則是計(jì)算出來(lái)的公鑰。
那么上面的乘法等效為：

從一個(gè)G開(kāi)始,2G就是G+G。同理可得k?G的結(jié)果,當(dāng)然了,如果k是奇數(shù),那么就是(k?1)?G+G。運(yùn)算就是做一次兩點(diǎn)連線(xiàn)延長(zhǎng)相交于曲線(xiàn)的點(diǎn)對(duì)x軸映射即可。

4.橢圓曲線(xiàn)簽名很難反推

接下來(lái)思考一下，對(duì)于K=k?G，為什么已知輸出K和G,為什么推導(dǎo)不出k呢?

其實(shí)這里存在一個(gè)誤區(qū),這里的乘法是橢圓曲線(xiàn)乘法,并不是小學(xué)的乘法。從上面的計(jì)算可以得知，k?G是在曲線(xiàn)上反復(fù)做切線(xiàn),并對(duì)x軸取映射點(diǎn)。也就是說(shuō)，你是無(wú)法通過(guò)輸出和常數(shù)點(diǎn)來(lái)知道你是通過(guò)多少次的運(yùn)算得來(lái)的，除非你一次計(jì)算每一個(gè)數(shù)值。而這個(gè)數(shù)值很大很大。

55066263022277343669578718895168534326250603453777594175500187360389116729240

這個(gè)數(shù)值是一個(gè)真實(shí)的隨機(jī)生成的私鑰k。如果你要反推，那么你一個(gè)個(gè)遍歷這個(gè)隨機(jī)數(shù)，計(jì)算量就是到k的階乘的橢圓曲線(xiàn)乘法運(yùn)算量了,所以在得出了大家常知的結(jié)論：橢圓曲線(xiàn)簽名很難反推

2018-1-30 更新

前面關(guān)于橢圓曲線(xiàn)簽名有一點(diǎn)補(bǔ)充.

橢圓曲線(xiàn)簽名很難反推,它主要是因?yàn)槟阈枰茖?dǎo)的是它的計(jì)算路徑,而不僅僅是最終結(jié)果.

在橢圓曲線(xiàn)乘法中,你需要反推的是從常數(shù)點(diǎn)G開(kāi)始畫(huà)切線(xiàn)到曲線(xiàn)交點(diǎn),再取x軸在映射點(diǎn).如此反復(fù),得到上圖中的折現(xiàn)路徑.

如果知道私鑰k，那么我折線(xiàn)的路徑是確定的。如果不知道，那么其實(shí)就是要試探每一條可能的折線(xiàn)路徑。而這需要的計(jì)算量是極大的，就目前的計(jì)算機(jī)而言，可以認(rèn)為不可被反推。

簡(jiǎn)書(shū)地址：https://www.jianshu.com/p/f5c64f21fcd5