ECC算法分析--數學背景-自上而下的方式

可以把ecc了解為是曲線域上的rsa，當然隻能這麼了解，它們即使放到一個域内也是有很大不同的，導緻它們分别可以被應用的數學難題就不同。既然可以了解為曲線域上的rsa(或者曲線域上的dh，dsa等)，那麼就應該知道rsa，dsa，dh等都是在什麼域上的，其實它們都是在素數域上的，所有的素數域都是一樣的，是以對于rsa，dsa或者dh來講，都是可以直接計算的，比如要産生一個大素數，那麼就直接産生好了，這一類産生數的問題是現代計算機可以解決的雖然一般機器沒有提供現成硬體接口，但是還是可以很容易程式設計實作的，可是曲線域怎麼了解，顧名思義就是定義在一條曲線上的點組成的集合加上一些操作，每一條曲線都擁有一個曲線域，這麼說來曲線域并不是唯一的，而是有無窮多個，于是我們在進行計算的時候必須要指明是在哪一條曲線上進行操作，是以必然在實作上要比rsa等素數域上的算法多一個資料結構，這個資料結構就是EC_GROUP，一旦group确定，其餘的操作流程就基本和素數域上的一緻了，不過也隻是流程的一緻，具體操作方法并不相同。不同的原因是因為域這個概念對各種操作可以實作重載(建議用OO的觀點了解群環域的概念)

     域的概念和oo中的類很相似，擁有一個資料集合，擁有加減乘除這些操作，擁有零元素和機關元素，這些對于不同的域來講可以有不同的實作，群環域就是集合和操作以及零元和機關元的抽象。既然域的加減乘除可以自定義，那麼接下來就要定義曲線上的加法，這是一個最基本的操作，因為減法可以了解為加上一個“負”元，乘法又是加法的重複，除法可以了解為乘以一個“倒”元。在叙述曲線域加法法則之前首先看一下射影面的概念。

     普通的笛卡爾坐标系中無法用數字表示“無窮”的概念，實際上笛卡爾坐标系就是量化的歐氏幾何學，所有歐氏幾何中“真理”依然在笛卡爾坐标系中成立，但是這種“有限域”的幾何學也許僅僅對工程學比較合适，理論上的幾何學應該是包羅萬象的，為了将有限和無限全部包容進一個坐标系，就需要用一種方式來記錄“無窮”這個概念，對應到幾何坐标系就是“無窮遠”的點，這個無窮遠實際上是不可達的，不要指望一個很遠很遠的點一下子跳變到無窮遠，類似量子躍遷的行為在連續的實數集合是不可能的。另外需要商定的就是無窮遠點有且隻有一個，因為我們的目的僅僅是在概念上包容無窮遠點以便我們定義新的概念，而不是要量化它進而使得計算成為可能，在新的數學理論推出之前，任何量化“無窮”的嘗試都是沒有意義的。既然不需要量化無窮遠點，那麼概念上隻有一個這樣的點就足夠了，一個平面上缺了這個點就等于缺了一半内容，加上這個點，一個平面就完整了，起碼在概念上就完整了。接下來就要看看如何去定義這個無窮遠點了。

     定義一個概念有兩種方式，一種是描述性的定義，一種是導出式的定義，描述性的定義對于無窮遠點實際上沒有什麼意義， 畢竟我們隻是用一下無窮遠這個概念，并且想将它歸并到已經存在的笛卡爾坐标系，于是就必然需要一個和它相關的概念将之導出來，于是理所當然的首選概念就是平行線的定義，歐氏幾何說不相交的兩直線平行，别小看了這個定義，就是這個定義抛棄了無窮遠點歐幾裡得的失誤在于他将相交和平行定義成了兩個概念，它們之間沒有互通的橋梁，這就導緻了兩個概念的二進制對立，于是如果是相交線，那麼它們肯定在有限伸展長度内相交，如果平行，那麼它們根本沒有交點，就更不需要在乎交點的概念以及在哪裡相交了，如果将平行的概念定義成相交于無窮遠的兩條直線的話，相交和平行的概念就全部統一于交點這個概念了，如果在有限伸展長度相交，那麼兩條直線相交，如果在無窮遠相交，那麼兩直線平行。有了這個無窮遠點的定義後，接下來就要考慮如何在坐标系表示它了，事實上，由于笛卡爾坐标系完全量化了歐氏幾何，是以不可能在這種坐标系中表示無窮遠點的，

L1：y=ax+m

L2：y=ax+n   

在m和n不等的情況下，上述直線聯立得到的方程組是無解的，是以不要指望用這種方式來定義無窮遠點，但是要想辦法使得上述方程有解，那就是再引入一個自變量z，于是上述直線化為：

L1'：zy=azx+zm

L2'：zy=azx+zn 

這樣隻要z=0，上述明顯平行的直線就會相交，相交于無窮遠點，坐标(x,y,z)就是新的射影面的坐标，當然也可以變換一下：

x'=zx

y'=zy

z'=z

于是，所有射影面坐标集合中z=0的點就是那個唯一的無窮遠點，如果由射影面坐标化到笛卡爾坐标則會出現：x=x'/z,y=y'/z的情況，很顯然z是不能為0的，這也是笛卡爾坐标系中無法表示無窮遠點的原因。有了無窮遠點的概念和坐标，整個平面就和諧了再也不用擔心兩條曲線沒有交點的問題了。

     于是曲線上兩點的加法被定義成兩點連線延長與曲線交于第三點，過第三點作y軸(笛卡爾坐标系)的平行線交曲線于第四點，這個第四點就是最後的和，在曲線域上，其零元就是無窮遠點，這個規則看起來很奇怪實際上很一般，我們國小時學的自然數加法就是最簡單的曲線加法法則，對應的曲線就是笛卡爾坐标系的x軸，也被簡稱為數軸，并且我們國小的時候就已經在使用離散點了，自然數就是數軸上的一系列離散點，那個時代我們先從離散的自然數開始學起，最後在國中的時候過渡到了連續的實數，實際上還是在同一條數軸上，但是今天這一次我們剛剛了解了連續曲線域上加法的定義，接下來要傳回離散化的定義，這次我們是先學的連續，然後再介紹離散，和國小國中時期對數軸的學習正好相反。

     ecc算法中為了使曲線上的點的坐标處于可控範圍内，ecc對曲線進行了取模操作，于是重新定義了離散曲線點的加法法則，實際上和連續曲線點的法則相似，這麼做是有原因的，畢竟最後實施計算的是機器，而機器并不是都可以做高強度運算的。具體定義就是：

a+b=c(modm);

a*b=c(modm);

這是很容易了解的，a和b的和和c相等的條件是a和b的實數域的加法和與m相除的餘數與c/m(實數域除法)的餘數相等(同餘)，乘法也是一樣的，另外這裡有個乘法逆元的概念，如果是實數域，一個數的乘法逆元就是其倒數，所謂乘法逆元就是相乘等于機關元的那個數，對于ecc算法的離散曲線域，m的乘法逆元為n，滿足m*n=1(modp);稱作n是m關于p的乘法逆元。對于ecc算法使用的離散曲線域，機關元就是1，

乘法就是相乘後取模，零元是無窮遠，加法就是相加後取模，這很簡單。但是如果在離散曲線域碰到一個表達式2/5，可不要把它當成一個數，它是一個除法表達式，這已經不是在實數域了，于是單純一個2/5沒有任何意義，一定要看mod數是多少，如果是10，那麼a=2/5的真正值是求5關于10的乘法逆元，然後再乘以2，這裡一定要注意。

     乘法逆元的求法是通過擴充歐幾裡德算法進行的，首先看一下擴充的歐幾裡德算法的描述：

ax+by=gcd(a,b)  -------(1)

這裡gcd就是歐幾裡德算法，這個等式1明顯是個不定方程，可以通過擴充歐式算法求出所有的x和y，首先如果a和b不互質且有唯一的公約數，那麼設它們的最大公約數且唯一的公約數為m于是

a'mx+b'my=m==>a'x+b'y=1 ----(2)

化為了a和b互質的情況；如果a和b存在一個以上的公約數，實際上不定方程1是無解的：

由于1已經化為了2的形式，如果a和b還有公約數n，那麼2==>a"nx+b"ny=1==>n(a"x+b"y)=1對于整數而言，除非n=1，否則上述方程不可能有解。如果a和b互質的話，就可以用擴充歐式算法求解x和y了：

擴充歐式算法使用的是遞歸的思想，根據方程1的形式，我們可以得到很多的形式：

ax1+by1=gcd(a,b)-----A

bx2+(a%b)y2=gcd(b,a%b)-----B

...

總有一天a%b會是0的，于是倒着推過來的話就得到了x和y，将A和B聯立求解得到的x和y是一個遞推式，也就是可以用xn+1來表示xn，這是最終能求出x和y的基礎。這個過程中，我們為了求x和y，借用了n多個方程1形式的方程，目的就是為了利用原始的歐幾裡德算法将這些看似不相關的方程聯系起來，得到一個遞推式。最後我們來看一下如何用擴充歐式算法求乘法逆元，乘法逆元可以表示成(a*b)mod p=1，則b是a關于p的逆元，前提是a和p互質，既然互質，并且ab mod p=1，那麼可以轉換為下面的式子：

a*b+py=1

把b看作x之後上式其實就是可以應用歐幾裡德算法求解的不定方程。之後的事情就不用多說了。

     對于密碼學應用的ecc來說，其實質是利用了一個數學難題，該數學難題和rsa以及dh的很相似，隻不過是定義在曲線域上面的，要想使用ecc加密，必然要定義一條曲線，然後選擇一個點，成為基點，随後計算該基點的階，所謂的階就是一個數字，設為p，基點設為B，p*B其實就是連續個B相加，如果pB=無窮遠點，那麼p就是B的階，然後随機選擇一個小于p的數字k，計算kB的值，将該值設為A，則kB=A，那麼A就是公鑰，k就是私鑰，該數學難題是：由k和B算A容易，由A和B算k困難。加密和解密的過程這裡就不再介紹了。

     本文簡略的介紹了ecc算法的實質以及它的部分實作，在被問到為何ecc在openssl中的實作和rsa之流不同時，你的回答可以是：ecc定義在離散曲線域上，而rsa定義在素數域上。在幾何表示上，由于曲線域基于交點定義加法，那麼交點是必然要無條件存在的，于是引入了無窮遠點作為不能處理的情況的後備處理資源。

     最後再說一個很有意思的事情，那就是歐幾裡德算法的了解，現在很多的教科書都會講到這個算法，但是如果你去翻一下古老的《幾何原本》的話就會對該算法有一種截然不同的了解方式了，歐幾裡德并沒有用除法和餘數來描述這個輾轉相除法，而是使用測量的概念，如果一個數能除盡另一個數，那麼就用“量盡”的表達方式，這種描述方式十分棒，雖然少了嚴謹性，但是了解起來十分容易，随意找兩根不等長的棍子，求它們長度的最大公約數，用短的一根去量長的一根，将長的一根按照短的一根的長度砍斷，接着将短的一根作為長棍，原來長棍被砍下的剩餘一截作為短棍，依次類推，如果有一次測量中，短棍量盡了長棍，那麼以短棍為機關将砍斷的小截再次砍斷，我們會發現我們擁有一大捆一樣長的棍子。這個形象的原理用于将很多不等長的棍子裁成等長的，要求不能浪費，并且達到最終的等長木棍盡可能的長。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1271927