非對稱加密與橢圓曲線

易衡知行 2017-09-29

展開全文

加密一直是通信領(lǐng)域的重要話題，我們經(jīng)常聽說各類算法，什么對稱加密，非對稱加密等等這類名詞，云山霧繞，不得所以，經(jīng)過這段時間的了解，接下來讓我用九淺一深的語言，解釋這個聽上去深不可測，其實更是一頭霧水的概念。
要解釋加密技術(shù)，首先就要了解一下什么是對稱加密。

對稱加密

維基百科的解釋如下：

對稱密鑰加密（英語：Symmetric-keyalgorithm）又稱為對稱加密、私鑰加密、共享密鑰加密，是密碼學(xué)中的一類加密算法。這類算法在加密和解密時使用相同的密鑰，或是使用兩個可以簡單地相互推算的密鑰。實務(wù)上，這組密鑰成為在兩個或多個成員間的共同秘密，以便維持專屬的通訊聯(lián)系。與公開密鑰加密相比，要求雙方取得相同的密鑰是對稱密鑰加密的主要缺點之一。

上面這段話看上去太抽象，不好理解，舉個例子，假如把A-Z的26個字母，用某種方式替換成另一套符號，比如，就把A替換成01，B替換成02，C替換成03，以依此類推Z替換成26，那么當(dāng)我要寫一個單詞happy的時候，就成了0801161625，以上這串?dāng)?shù)字雖然看上去不明所以，但因為明文和密電文之間是一一對應(yīng)關(guān)系的，A永遠(yuǎn)對應(yīng)1，Z永遠(yuǎn)對應(yīng)26，這種加密與解密一一對應(yīng)的加密方式，就叫做對稱加密。

對稱加密的缺點是，看似復(fù)雜，實則破解難度不高，雖然以上數(shù)字0801161625，看著不明覺厲，但因為語言書寫總有一定的規(guī)律性，比如對于英文，字母e的出現(xiàn)頻率遠(yuǎn)高于其他字母，而z的出現(xiàn)頻率又遠(yuǎn)低于其他字母，所以，只要有足夠的樣本，通過比對和暴力破解，就不難找出明文和密電碼的對應(yīng)關(guān)系，即使不用數(shù)字，而使用某些特殊字符代替，甚至是圖片，也一樣容易破解。

比如，《福爾摩斯探案集》里，有一章《跳舞小人符號案件》就是一種對稱加密技術(shù)：

福爾摩斯看到畫有小人的紙條后，是真么分析的：

交給我的第一張紙條很短，我只有把我斷定，其中一個符號代表E，大家都知道，英文中字母E最常用，即使在短句中，它的出現(xiàn)頻率也最高。第一張紙條上有15個符號，其中四個完全一樣，因此有理由認(rèn)為這個符號代表E。這些圖形中，有的帶一面小旗，有的沒有，從小旗的分布來看，帶旗的圖形可能代表了單詞之間的空格。

有網(wǎng)友總結(jié)過跳舞小人代表的26個字母，典型的對稱加密。

摘自《福爾摩斯探案全集》之《跳舞小人符號案件》

所以，對稱加密可以寫成以下形式

明文 <-> 密鑰 <-> 密文

常見的對稱加密算法有DES、3DES、AES、Blowfish、IDEA、RC5、RC6。

好了，既然對稱加密安全性不高，于是人們開始尋找一種更安全，更不容易被破解的加密技術(shù)—非對稱加密。

非對稱加密

非對稱加密，簡單來說就是“在已知x的情況下，通過算法很容易求得y，但是知道了y，反過來求x卻非常非常的困難”。

舉個最最簡單的例子，公式：y=3x^3 2x^2-1，假設(shè)x=1，然后你馬上算出y=4。

那現(xiàn)在y=1的時候，x等于多少呢，開始掰手指頭了吧，對普通人來說，這個求解有點難度，但是對計算機(jī)來說，還是小菜一碟。

橢圓曲線加密-ECC

真正的非對稱算法比這復(fù)雜多了，常見的非對稱加密算法有RSA，還有橢圓曲線加密-ECC-Elliptic Curve Crytograph。

接下去就重點講下，這個什么橢圓，什么曲線，是個什么鬼？

橢圓曲線

簡單說它就是一套數(shù)學(xué)公式，比如：y^2 = x^3 ax b

（當(dāng)a和b滿足4a3 27b2 ≠ 0的，才是一根有效的橢圓曲線）

當(dāng)然，橢圓曲線有多種變化，通過系數(shù)a和b的變換，可以有以下形狀：

(b = 1, a 取值由 2 變化至 -3)

實際上真正拿來加密用的曲線，a和b的取值都是天文數(shù)字

為了簡單理解，我們假設(shè)有根曲線，其公式是y^2=x^3-x 1，

該曲線有個特點，任意一根穿過該橢圓曲線的直線，最多和曲線有三個交點。

假設(shè)1

我們在曲線上有A點和B點，兩點成直線后的延伸線又和曲線相交，于是就有了C點，見下圖。

A，B，C三點C點滿足以下關(guān)系：

A B C = 0

另外，橢圓曲線是相對于x軸對稱，所以，由C點可以得到鏡像點C’，兩者滿足關(guān)系

C = -C’

請注意，這里的加法是幾何意義上的加法，不同于普通的加減乘除

到這里，你會問，知道了這些又如何，這根曲線有個卵用阿？別急，接下來，我們把C’和A點相連，新的直線相交曲線得到D，

把D鏡像為D’，再與A相連，新的直線與曲線相交，又得到點E，

這個過程持續(xù)重復(fù)，就會得到點G，如下圖：

然后根據(jù)橢圓曲線上點的加減規(guī)則，把過程中所有點的關(guān)系列出來
A B C = 0
A D C’ = 0
A D’ E = 0
A F E’ = 0
A F’ G = 0
C = -C’
D = -D’
E = -E’
F = -F’

經(jīng)過一系列的加法運(yùn)算

得到：

-G=5A B

看明白了么，就是說終點G的值，只和曲線上初始點A和B的位置有關(guān)系。

有人把這個過程比作彈子球不斷碰撞反彈，再碰撞再反彈的過程。

假設(shè)2

現(xiàn)在考慮一種特殊的情況，當(dāng)初始點A=B的時候，此時，從A點出發(fā)的直線與橢圓曲線相切，重復(fù)上述過程：

以上過程表達(dá)為：
A A C = 0
C’ C’ D = 0
D’ D’ E = 0
E’ E’ F = 0
C = -C’
D = -D’
E = -E’
F = -F’

最終得到：

F’=16A，

其中A被稱作起始點，16其實是2的k次方，k為迭代次數(shù)

在ECC加密算法里，其幾何學(xué)的意義，正是通過對“生成點”做反復(fù)切線，最終得到一個點，這個點正是公鑰-K，而迭代的次數(shù)就是私鑰

K=k*G

生成點：G，Generator，

迭代次數(shù)：k，“私鑰”—一個256比特的二進(jìn)制數(shù)字

在已知k和G的情況下，進(jìn)行的其實是相加的計算，并通過一種叫做square and multiply-的方式，可以快速算出K。

但如果反過來，知道了K和G，反算k就非常困難，辦法倒不是沒有，就一招—老老實實一步一步計算，英文叫做-Baby-step giant-step，有個更直白的稱呼，你一定知道，叫—暴力破解，不過迭代的范圍是2的256次方，即1.15×10^77，按照現(xiàn)階段的計算機(jī)算力，大概要算上幾百萬年吧。

請注意上面公式變換成k = K/G是不成立的，k ≠ K/G。

這套密碼的好處，是私鑰和公鑰對，隨時可以變化，隨機(jī)生成一個，就有完全不同的密鑰來加密信息了，相比對稱加密一塵不變的密碼對，要安全很多。

以上就是ECC橢圓曲線加密的基本原理。

有限域

在真正的ECC算法里，會對橢圓曲線進(jìn)行有限域轉(zhuǎn)換，變成下面這個鬼樣子：

像不像23×23的圍棋棋盤？有沒有完全看不懂？

是的，我也完全看不懂，反復(fù)糾結(jié)和琢磨后，大致可以理解成，把一個復(fù)雜的曲線，進(jìn)行歸一化，離散化，整數(shù)化的方法。

比如我們的表盤就是個模-mod為12的有限域，無論時間走了8小時，14小時，20小時，還是49小時，表盤上顯示的只是8，2，8，1，相當(dāng)于把無限的線性時間，折疊在有限的表盤內(nèi)，這樣的好處是，當(dāng)你看著表盤上的8點(公鑰)，你根本不知道，究竟是上午8點，下午8點，還是n天后的8點，因為你完全不知道指針走了幾圈啊(私鑰)，從而增加了密碼的強(qiáng)壯性。（具體我還沒完全懂，吹不下去了）

把y^2=x^3-x 1寫成有限域內(nèi)的公式就有y^2 mod p=(x^3-x 1) mod p，p表示網(wǎng)格的范圍，是個素數(shù)，比如上圖的p=23，又是個玄乎的東西

實際的ECC加密算法secp256k1里，有限域的模p = 2^256 – 2^32 – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1，你自己掰手指頭數(shù)吧，反正你可以把它想象成一張無比巨大的網(wǎng)格。
經(jīng)過上面的一系列計算，得到K-公鑰后，給到對方，就能進(jìn)行信息的加密了，但是對方只能用公鑰對信息進(jìn)行加密，并不能對信息進(jìn)行解密，解密需要私鑰k，也就是只有手握私鑰的你才能打開這把鎖。(對應(yīng)數(shù)字貨幣世界，只能向公鑰地址發(fā)送貨幣，但沒有私鑰是不能對賬戶內(nèi)的金額進(jìn)行轉(zhuǎn)賬操作的)