一、“橢圓曲線”命名由來

橢圓曲線和橢圓其實(shí)是兩種不同的東西充包，它是指滿足特定方程的平面上的點(diǎn)的集合多柑。之所以帶上“橢圓”二字，是因?yàn)槿藗冊谟?jì)算橢圓周長引出橢圓積分瑞佩，第一類橢圓積分的反函數(shù)引出橢圓函數(shù)聚磺，橢圓函數(shù)可以參數(shù)化為非奇異三次代數(shù)曲線，有理域上的非奇異三次代數(shù)曲線被取名為 橢圓曲線炬丸。

二瘫寝、橢圓曲線方程及圖像

方程中 a 與 b 的取值是實(shí)數(shù)范圍蜒蕾，隨著兩個值的變動，其圖像大致如下焕阿，可以看到橢圓曲線是關(guān)于x軸對稱：

圖片來源參考1

三咪啡、定義在橢圓曲線上的運(yùn)算

3.1 加法運(yùn)算

加法運(yùn)算示意圖

在橢圓曲線上定義兩個點(diǎn) 和 ，連接兩點(diǎn)使得所得直線與橢圓曲線相交于 點(diǎn)暮屡，過 點(diǎn)做 軸垂線交橢圓曲線于 點(diǎn)撤摸，由橢圓曲線的性質(zhì)可知 點(diǎn)與 點(diǎn)對稱，同時(shí)我們可以得到橢圓曲線的加法運(yùn)算：

同理連接 點(diǎn)和 點(diǎn)褒纲，交橢圓曲線于點(diǎn)准夷，同樣過 點(diǎn)做軸的垂線交橢圓曲線于 點(diǎn)，如下圖所示：

這樣繼續(xù)連接點(diǎn)和點(diǎn)...就可以得到如下過程：

3.2 乘法運(yùn)算

乘法運(yùn)算示意圖

如圖所示莺掠，過點(diǎn)做切線(因?yàn)橐ＷC橢圓曲線上的每個點(diǎn)都有切線衫嵌，所以限定)，交橢圓曲線于點(diǎn)彻秆，同樣過點(diǎn)做軸垂線交橢圓曲線于點(diǎn)楔绞，這樣我們認(rèn)為在這種 切點(diǎn) 情況下加法運(yùn)算為 ，即點(diǎn)為掖棉。同樣在點(diǎn)做切線，我們可以得到點(diǎn)膀估。而不在通過的結(jié)果來尋找幔亥。如此引入的概念可以極大的降低運(yùn)算次數(shù)，幫助我們快速尋找到要找的點(diǎn)察纯。例如我們想得到帕棉，該怎么做呢？

這樣一共需要計(jì)算12次即可得到的結(jié)果饼记。

3.3 性質(zhì)說明

橢圓曲線密碼ECC是橢圓曲線在ElGamal體系下的應(yīng)用香伴，ElGamal體系就是定義在群上的，那么同樣的在橢圓曲線上的一些運(yùn)算需要具有“群”的性質(zhì)：

• 封閉性具则，定義在橢圓曲線上的點(diǎn)的運(yùn)算結(jié)果肯定還在橢圓曲線上即纲，要么就是無窮遠(yuǎn)點(diǎn)。
• 結(jié)合律博肋，滿足低斋，三點(diǎn)共線并沒有規(guī)定順序，所以(P+Q)+R=0=P+(Q+R)
• 單位元匪凡，就是無窮遠(yuǎn)點(diǎn)0膊畴，每個點(diǎn)加無窮遠(yuǎn)點(diǎn)還等于這個點(diǎn)
• 逆元，每個點(diǎn)的逆元肯定存在病游，因?yàn)闄E圓曲線關(guān)于x軸對稱

四唇跨、橢圓曲線算法與數(shù)字簽名的關(guān)系

為什么說橢圓曲線可以用來做數(shù)字簽名呢？我們知道判斷某種方法是否適用于簽名或者加密的前提是對于正向操作是容易的，而對于是逆向操作是無法實(shí)現(xiàn)的或者說實(shí)現(xiàn)起來是非常困難的买猖。如下圖4.1所示：

圖4.1

選定點(diǎn)改橘，在經(jīng)過10次相加后得到的位置，即點(diǎn)政勃。如果在不知道經(jīng)過幾次相加唧龄，只知道點(diǎn)的位置的情況下：，想通過的方式來計(jì)算是無法實(shí)現(xiàn)的(均為坐標(biāo)點(diǎn))奸远。簡單打比方說既棺，我在一個房間前門開始踢球，踢了一段時(shí)間之后球落在房間的某個位置懒叛，這時(shí)讓你來回答我踢了多少次才將球踢到這個位置丸冕？對于你來說，能做的方法就是從前門開始將球向房間的各個方向踢一點(diǎn)一點(diǎn)的嘗試薛窥。我們從這個例子中可以看出對于我來講胖烛，踢球是簡單的，但是回答踢了幾次是困難的诅迷，所以這符合簽名或加密的要求佩番。

回到圖4.1中的問題，我們無法通過直接計(jì)算來確定的值罢杉，只能通過比較來做：

錯
錯
.....
對

這樣最終確定的值是10趟畏。那么如果這個的值非常大呢？比如：

滩租，此時(shí)如果再一個一個的計(jì)算是非常費(fèi)時(shí)的赋秀，因此在非對稱加密算法中，將一個非常大的數(shù)作為私鑰律想，而將得到的點(diǎn)作為公鑰分發(fā)出去猎莲。限于算力的影響是無法推算出的。

現(xiàn)在我們以實(shí)際應(yīng)用中的曲線來做說明：在橢圓曲線方程中取 技即，是比特幣所使用的曲線 ：

在比特幣中著洼，選擇的初始點(diǎn)或者基點(diǎn)是Generator,這里用 來表示，注意當(dāng)選定一條曲線之后基點(diǎn)就已經(jīng)確定而叼，假如我們選定了一個很大的私鑰郭脂，那么公鑰就是個相加之后的結(jié)果：

Generator：
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Private Key:
= 0xD45E369D8C7D3F3D8FDBE7A1DC5D00C0291D8C58B5B9C6F7A6E9B1D45D754F1B

Public Key:
= 0xBBA8D8A3F09D3F1F4E9B1D70EF3E8D3E1A2D8A4A9B704D2C3C20C3F8A0B2A7E4
= 0x4F465D8F7D8F89D7A3E6E6B191EDC5FAFA5E2A55A7D08B807B46A5C9D0A2E1A9

注意這里公鑰通常是以未壓縮形式或者壓縮形式表示的，未壓縮形式的公鑰由標(biāo)識符0X04和組合而成澈歉，而壓縮形式的公鑰由標(biāo)識符0X02或者0X03和坐標(biāo)的值以及根據(jù)坐標(biāo)的奇偶性計(jì)算出的一個比特組成展鸡。

好了現(xiàn)在我們有了公鑰和私鑰，即：

現(xiàn)在我們來根據(jù)上面的內(nèi)容來分析一下簽名驗(yàn)簽的過程：

Alice 向 Bob發(fā)送消息：“我愛你”埃难，假設(shè)這個消息為M莹弊，Alice 的私鑰為涤久，所以簽名過程就是使用私鑰乘以M的哈希值作為簽名：

現(xiàn)在將M和發(fā)送給 Bob，公鑰在消息發(fā)送前就已經(jīng)給了Bob忍弛，Bob拿到消息后先使用公鑰與M的哈希值相乘得到X响迂，再使用與基點(diǎn)點(diǎn)相乘得到 Y，如果 X == Y 則驗(yàn)證通過细疚，示意圖如下：

可以看到 X == Y 是成立的蔗彤，同時(shí)可以明確沒有私鑰 就無法證明，這個過程中的計(jì)算Alice是清楚的疯兼，但Bob不清楚然遏，但他只需要驗(yàn)證 X == Y 成立就明確消息是Alice發(fā)出的。

但這個過程是有問題的吧彪，Bob 是可以通過 得到私鑰 的待侵，注意這里和上面的不一樣，上面是坐標(biāo)點(diǎn)姨裸，而這里的每個值都是數(shù)字秧倾！所以就有如下解決方案：

引入 R，其存在類似公鑰傀缩，這樣同樣可以證明 X == Y那先，因此這種情況下簽名文件的內(nèi)容是 R 和 _s 的組合，需要注意的是這兩個值是和曲線的位數(shù)有關(guān)赡艰，例如本例中 曲線售淡，則 R 和 _s都是32字節(jié)， 曲線瞄摊，則 R 和 _s都是24字節(jié)勋又，因此在不考慮ASN.1之類的存儲結(jié)構(gòu)苦掘，最精簡的簽名文件换帜，就是單純的R 和 _s的組合，以本例來說是64字節(jié)鹤啡， 曲線簽名文件則是48字節(jié)惯驼；

五、橢圓曲線的離散化

為什么要將橢圓曲線離散化递瑰，究其原因有如下幾點(diǎn)：

1祟牲、橢圓曲線密碼學(xué)使用的有限域是一個離散域，其中元素?cái)?shù)量有限抖部，所有的運(yùn)算操作封閉
2说贝、安全性：離散化可以增強(qiáng)橢圓曲線密碼學(xué)的安全性，在橢圓曲線上慎颗。離散對數(shù)問題是一個非常困難的問題乡恕。
3言询、計(jì)算精度問題：在實(shí)數(shù)域上計(jì)算橢圓曲線時(shí)，會涉及到除法傲宜，比如在ECDSA簽名需要計(jì)算一個參數(shù)K的逆元运杭，即

因此需要對上面的橢圓曲線做取模運(yùn)算：

代入本例來說即：

這里需要說明的是模需要盡可能的大，其位數(shù)由曲線位數(shù)決定函卒，比方說本例曲線辆憔，模的長度為256位。

參考文獻(xiàn)

[ 1. ] SM2國密算法/橢圓曲線密碼學(xué)ECC之?dāng)?shù)學(xué)原理 !
[ 2. ] 橢圓曲線演示工具