參加比特幣源碼研讀班后首次寫作化撕，看到前輩black寫的有關(guān)密鑰宫补，地址寫的很好了粉怕，就選了他沒有寫的橢圓曲線抒巢，斗膽寫這一篇。
在密碼學(xué)上有兩種加密方式崇堵，分別是對稱密鑰加密和非對稱密鑰加密客燕。
對稱加密：加密和解密使用的同樣的密鑰也搓。
非對稱加密：加密和解密是使用的不同的密鑰。
二戰(zhàn)中圖靈破解德軍的恩尼格碼應(yīng)該就是用的對稱加密幔摸，因?yàn)樗募用芎徒饷苁峭粋€密鑰抚太。比特幣的加密是非對稱加密昔案，而且用的是破解難度較大的橢圓曲線加密踏揣，簡稱ECC捞稿。
非對稱加密的通用原理就是用一個難以解決的數(shù)學(xué)難題做到加密效果，比如RSA加密算法彰亥。RSA加密算法是用求解一個極大整數(shù)的因數(shù)的難題做到加密效果的任斋。就是說兩個極大數(shù)相乘耻涛，得到乘積很容易抹缕，但是反過來算數(shù)一個極大整數(shù)是由哪兩個數(shù)乘積算出來的就非常困難卓研。
下面簡要介紹一下橢圓曲線加密算法ECC。
首先橢圓曲線的通式是這個樣子的：
一般簡化為這個樣子：
()簡書發(fā)公式必須吐槽一下带膀，太麻煩了橙垢。)
其中
這樣做就排除了帶有奇點(diǎn)的橢圓曲線柜某，可以理解為所有的點(diǎn)都有一條切線喂击。
圖像有幾種翰绊，下面列舉幾個：[1]
橢圓曲線其實(shí)跟橢圓關(guān)系不大监嗜，也不像圓錐曲線那樣，是有圓錐的物理模型為基礎(chǔ)的桐猬。在計(jì)算橢圓曲線的周長時溃肪，需要用到橢圓積分音五，而橢圓曲線的簡化通式：
躺涝，周長公式在變換后有一項(xiàng)是這樣的：诞挨，平方之后兩者基本一樣惶傻。
我們大體了解了橢圓曲線银室，就會有一個疑問，這個東西怎么加密的呢辜荠？也就是說橢圓曲線是基于怎樣的數(shù)學(xué)難題呢伯病？在此之前還得了解一些最少必要知識：橢圓曲線加法否过，離散型橢圓曲線苗桂。
橢圓曲線加法
數(shù)學(xué)家門從普通的代數(shù)運(yùn)算中煤伟，抽象出了加群（也叫阿貝爾群或交換群），使得在加群中围辙，實(shí)數(shù)的算法和橢圓曲線的算法得到統(tǒng)一酌畜。
數(shù)學(xué)中的“群”是一個由我們定義了一種二元運(yùn)算的集合桥胞，二元運(yùn)算我們稱之為“加法”考婴，并用符號“+”來表示沥阱。為了讓一個集合G成為群考杉，必須定義加法運(yùn)算并使之具有以下四個特性：
1. 封閉性：如果a和b是集合G中的元素，那么（a + b)也是集合G中的元素咽袜。
2. 結(jié)合律：(a + b) + c = a + (b + c);
3. 存在單位元0询刹，使得a + 0 = 0 + a =a;
4. 每個元素都有逆元凹联，即：對于任意a，存在b住闯，使得a + b = 0.
如果我們增加第5個條件：
5. 交換律： a + b = b + a
那么寞秃，稱這個群為阿貝爾群偶惠。[1]
運(yùn)算法則：任意取橢圓曲線上兩點(diǎn)P忽孽、Q （若P兄一、Q兩點(diǎn)重合出革，則做P點(diǎn)的切線）做直線交于橢圓曲線的另一點(diǎn)R’，過R’做y軸的平行線交于R耳璧。我們規(guī)定P+Q=R展箱。（如圖）[2]
特別的旨枯，當(dāng)P和Q重合時，P+Q=P+P=2P混驰，對于共線的三點(diǎn)攀隔，P，Q栖榨，R’有P+Q+R’=0∞.
這里的0∞不是實(shí)數(shù)意義的0昆汹，而是指的無窮遠(yuǎn)點(diǎn)(這里的無窮遠(yuǎn)點(diǎn)就不細(xì)說了，你可以理解為這個點(diǎn)非常遙遠(yuǎn)婴栽，遙遠(yuǎn)到兩條平行線都在這一點(diǎn)相交了。具體介紹可以看參考文獻(xiàn)[2])居夹。
注意這里的R與R’之間的區(qū)別败潦，P+Q=R，R并沒有與P准脂，Q共線劫扒，是R’與P，Q共線狸膏，不要搞錯了沟饥。
法則詳解：
這里的+不是實(shí)數(shù)中普通的加法，而是從普通加法中抽象出來的加法湾戳，他具備普通加法的一些性質(zhì)贤旷，但具體的運(yùn)算法則顯然與普通加法不同。
根據(jù)這個法則砾脑，可以知道橢圓曲線無窮遠(yuǎn)點(diǎn)O∞與橢圓曲線上一點(diǎn)P的連線交于P’幼驶，過P’作y軸的平行線交于P，所以有無窮遠(yuǎn)點(diǎn) O∞+ P = P 韧衣。這樣盅藻，無窮遠(yuǎn)點(diǎn) O∞的作用與普通加法中零的作用相當(dāng)（0+2=2），我們把無窮遠(yuǎn)點(diǎn) O∞ 稱為零元畅铭。同時我們把P’稱為P的負(fù)元（簡稱氏淑，負(fù)P；記作硕噩，-P）假残。（參見下圖）
離散型橢圓曲線
上面給出的很好看的橢圓曲線是在實(shí)數(shù)域上的連續(xù)曲線，這個是不能用來加密的炉擅，原因我沒有細(xì)究辉懒，但一定是連續(xù)曲線上的運(yùn)算太簡單。真正用于加密的橢圓曲線是離散型的坑资。要想有一個離散型的橢圓曲線耗帕，先得有一個有限域。
域：在抽象代數(shù)中袱贮，域（Field）之一種可進(jìn)行加仿便、減、乘攒巍、除運(yùn)算的代數(shù)結(jié)構(gòu)嗽仪。它是從普通實(shí)數(shù)的運(yùn)算中抽像出來的。這一點(diǎn)與阿貝爾群很類似柒莉。只不過多了乘法闻坚，和與乘法相關(guān)的分配率。
域有如下性質(zhì)[3]：
1.在加法和乘法上封閉兢孝，即域里的兩個數(shù)相加或相乘的結(jié)果也在這個域中窿凤。
2.加法和乘法符合結(jié)合律仅偎，交換率，分配率雳殊。
3.存在加法單位橘沥，也可以叫做零元。即存在元素0夯秃，對于有限域內(nèi)所有的元素a座咆，有a+0=a。
4.存在乘法單位仓洼，也可以叫做單位元介陶。即存在元素1，對于有限域內(nèi)所有的元素a色建，有1*a=a哺呜。
5.存在加法逆元，即對于有限域中所有的元素a箕戳，都存在a+(-a)=0.
6.存在乘法逆元弦牡，即對于有限域中所有的元素a，都存在a*=0.
在掌握了這些知識后漂羊，我們將橢圓曲線離散化驾锰。我們給出一個有限域Fp，這個域只有有限個元素走越。Fp中只有p(p為素?cái)?shù))個元素0,1,2 …… p-2,p-1椭豫；
Fp 的加法（a+b）法則是 a+b≡c (mod p)；它的意思是同余旨指，即（a+b）÷p的余數(shù)與c÷p的余數(shù)相同赏酥。
Fp 的乘法(a×b)法則是 a×b≡c (mod p)；
Fp 的除法(a÷b)法則是 a/b≡c (mod p)谆构；即 a×b∧-1≡c (mod p)裸扶；（也是一個0到p-1之間的整數(shù)，但滿足b×b∧-1≡1 (mod p)搬素；
Fp 的單位元是1呵晨，零元是 0（這里的0就不是無窮遠(yuǎn)點(diǎn)了，而是真正的實(shí)數(shù)0）熬尺。
下面我們就試著把
這條曲線定義在Fp上：
選擇兩個滿足下列條件的小于p(p為素?cái)?shù))的非負(fù)整數(shù)a摸屠、b，且a粱哼，b滿足
則滿足下列方程的所有點(diǎn)(x,y)季二，再加上無窮遠(yuǎn)點(diǎn)O∞ ，構(gòu)成一條橢圓曲線。
其中 x,y屬于0到p-1間的整數(shù)胯舷，并將這條橢圓曲線記為Ep(a,b)刻蚯。
圖是我手畫的，大家湊合看哈桑嘶。不得不說芦倒，p取7時，別看只有10個點(diǎn)不翩，但計(jì)算量還是很大的。
Fp上的橢圓曲線同樣有加法麻裳，法則如下：
? ? ? ? 1. 無窮遠(yuǎn)點(diǎn) O∞是零元口蝠，有O∞+ O∞= O∞，O∞+P=P
? ? ? ? 2. P(x,y)的負(fù)元是 (x,-y)津坑，有P+(-P)= O∞
3. P(x1,y1),Q(x2,y2)的和R(x3,y3) 有如下關(guān)系：
x3≡-x1-x2(mod p)
y3≡k(x1-x3)-y1(mod p)
其中若P=Q 則 k=(3+a)/2y1 若P≠Q(mào)妙蔗，則k=(y2-y1)/(x2-x1)
通過這些法則，就可以進(jìn)行離散型橢圓曲線的計(jì)算疆瑰。
例：根據(jù)我畫的圖眉反，（1，1）中的點(diǎn)P（2穆役，4）寸五，求2P。
解：把點(diǎn)帶入公式k=(3*x∧2+a)/2y1
有（3*2∧2+1）/2*4=6（mod 7）.
(注意耿币，有些小伙伴可能算出13/8,這是不對的梳杏，這里是模數(shù)算數(shù)，就像鐘表一樣淹接，過了12點(diǎn)又回到1點(diǎn)十性，所以在模為7的世界里，13=6塑悼，8=1).
x=6*6-2-2=4（mod 7）
y=6*（2-4）-4=2 （mod 7）
所以2P的坐標(biāo)為（2劲适，4）
那橢圓曲線上有什么難題呢？在模數(shù)足夠大的情況下厢蒜，上面這個計(jì)算過程的逆運(yùn)算就足夠難霞势。
給出如下等式：
K=kG （其中 K,G為Ep(a,b)上的點(diǎn)，k為小于n（n是點(diǎn)G的階）的整數(shù)）不難發(fā)現(xiàn)斑鸦，給定k和G支示，根據(jù)加法法則，計(jì)算K很容易鄙才；但給定K和G颂鸿，求k就相對困難了。
這就是橢圓曲線加密算法采用的難題攒庵。我們把點(diǎn)G稱為基點(diǎn)（base point）嘴纺，k稱為私鑰败晴，K稱為公鑰。
現(xiàn)在我們描述一個利用橢圓曲線進(jìn)行加密通信的過程[2]：
1栽渴、用戶A選定一條橢圓曲線Ep(a,b)尖坤，并取橢圓曲線上一點(diǎn)，作為基點(diǎn)G闲擦。
2慢味、用戶A選擇一個私鑰k，并生成公鑰K=kG墅冷。
3纯路、用戶A將Ep(a,b)和點(diǎn)K，G傳給用戶B寞忿。
4驰唬、用戶B接到信息后 ，將待傳輸?shù)拿魑木幋a到Ep(a,b)上一點(diǎn)M（編碼方法很多腔彰，這里不作討論）叫编，并產(chǎn)生一個隨機(jī)整數(shù)r（r<n）。
5霹抛、用戶B計(jì)算點(diǎn)C1=M+rK搓逾；C2=rG。
6杯拐、用戶B將C1恃逻、C2傳給用戶A。
7藕施、用戶A接到信息后寇损，計(jì)算C1-kC2，結(jié)果就是點(diǎn)M裳食。因?yàn)?/p>
C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M
再對點(diǎn)M進(jìn)行解碼就可以得到明文矛市。
整個過程如下圖所示：
密碼學(xué)中，描述一條Fp上的橢圓曲線诲祸，常用到六個參量：
T=(p,a,b,G,n,h)浊吏，p 、a 救氯、b 用來確定一條橢圓曲線找田，G為基點(diǎn)，n為點(diǎn)G的階着憨，h 是橢圓曲線上所有點(diǎn)的個數(shù)m與n相除的整數(shù)部分
這幾個參量取值的選擇墩衙，直接影響了加密的安全性。參量值一般要求滿足以下幾個條件：
1、p 當(dāng)然越大越安全漆改，但越大心铃，計(jì)算速度會變慢，200位左右可以滿足一般安全要求挫剑；
2去扣、p≠n×h；
3樊破、pt≠1 (mod n)愉棱，1≤t<20；
4哲戚、4a3+27b2≠0 (mod p)奔滑；
5、n 為素?cái)?shù)惫恼；
6、h≤4澳盐。
200位位的一個數(shù)字祈纯，那得多大？而且還是素?cái)?shù)叼耙，所以這種方式是非常安全的腕窥。而且再一次交易中，區(qū)塊被記錄下來只有10分鐘的時間筛婉，也就是說要想解決這個難題必須在10分鐘以內(nèi)簇爆。即便有技術(shù)能夠在10分鐘以內(nèi)破解了現(xiàn)在這個難度的加密算法，比特幣社區(qū)還可以予以反制爽撒，提高破解難度入蛆。所以比特幣交易很安全，除非自己丟掉密鑰硕勿，否則不存在被破解可能哨毁。
第一次寫一個完全陌生的數(shù)學(xué)領(lǐng)域的知識，也許我有錯誤的地方源武，也許有沒講明白的地方扼褪，留言討論吧×黄埽總之寫完后對比特比系統(tǒng)的安全性表示很放心话浇。
參考文獻(xiàn)
[1] 橢圓曲線密碼學(xué)簡介
[2] 什么是橢圓曲線加密（ECC）
區(qū)塊鏈研習(xí)社源碼研讀班 高若翔
