橢圓曲線加密算法 (Elliptic curve cryptography,縮寫為 ECC),1985年由Neal Koblitz和Victor Miller分別獨立提出。
那到底什麼是橢圓曲線算法呢?
讓人失望的是,橢圓曲線不像因式分解是那種我們初中就學過的知識,可以說大多數人對橢圓曲線函數的知識並不熟悉。
這部分的內容並不簡單,也沒那麼容易理解,接下來,我儘量避免羅列公式,用通俗易懂的語言介紹下橢圓曲線。
而RSA算法的單向函數體現在計算乘法很容易,因式分解則是一道數學難題。
那麼橢圓曲線的算法的單向函數是什麼呢?
首先我們來看看橢圓曲線方程組,y^2=x^3+a^x+b,有點抽象,我們來看看它長什麼樣子:
這兩種曲線都是橢圓曲線,可以說是孿生兄弟,根據參數a、b的不同,所以樣子上有點區別。
你會發現,右邊的曲線跟歐米伽特別像。
我們仔細看橢圓曲線,它有著一個非常有趣的特性,就是任何不垂直的直線穿過曲線最多有三個交點。
還有一個特性,曲線上任一點做X軸對稱後得到的點仍然在橢圓曲線上。為了避免出現大部分公式,筆者儘量用圖片來解釋橢圓曲線算法。
曲線上任意兩點的連線延長做一條直線,這條直線與曲線有一個交點,根據橢圓曲線的對稱性,我們做這個交點的x軸對稱,得一個新的點,該點仍在曲線上。
這個過程,我們叫打點,即dot。我們來看上圖,A dot B得到的是C點。(很多文獻把這個過程定義成橢圓曲線的加法)
我們持續這一過程反覆
A dot B=C
A dot C=D
A dot D=E
……
重複這一過程,我們來看看結果,我們發現了一些特性,如果圖像無限大的話,打點這一過程可以一直持續。
也就是說,我們可一直打點,我們假設進行了無數次的打點,並得到其中一點G,如果我們只知道G和A,那麼G點是A打點幾次得出的?我想這是一個很難的數學問題。
結論
在給定起始點A和終點G的情況下,我們想找出打點次數n的值是很困難的。正推容易,反推很難,這就是ECC算法的單向函數,也是ECC算法的數學基礎。
我們再來看看ECC算法的加密過程:
1. 小倩選定一條橢圓曲線Ep(a,b),並取橢圓曲線上一點,作為基點G。
2. 小倩選擇一個私有密鑰k,並生成公開密鑰K=kG。(這一步既是上文提到的打點過程)
3. 小倩將Ep(a,b)和點K,G傳給小高。
4. 小高接到信息後,將待傳輸的明文編碼到Ep(a,b)上一點M(編碼方法很多,這裡不作討論),併產生一個隨機整數r(r 5. 小高計算點C1=M+rK;C2=rG。 6. 小高將C1、C2傳給小倩。 7. 小倩接到信息後,計算C1-kC2,結果就是點M。因為 C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M 然後再對點M進行解碼就可以得到明文。 在這個加密通信中,如果有一個偷窺者H ,他只能看到Ep(a,b)、K、G、C1、C2, 而通過K、G 求k 或通過C2、G求r 都是相對困難的,原因上文已經提到。 因此,H無法得到A、B間傳送的明文信息。 橢圓曲線數字簽名算法(ECDSA)是使用橢圓曲線密碼(ECC)對數字簽名算法(DSA)的模擬。 ECDSA於1999年成為ANSI標準,並於2000年成為IEEE和NIST標準。它在1998年既已為ISO所接受,並且包含它的其他一些標準亦在ISO的考慮之中。
與普通的離散對數問題(discrete logarithm problem DLP)和大數分解問題(integer factorization problem IFP)不同,橢圓曲線離散對數問題(elliptic curve discrete logarithm problem ECDLP)沒有亞指數時間的解決方法。
秘鑰強度
因此橢圓曲線密碼的單位比特強度要高於其他公鑰體制。
橢圓曲線離散對數算法是基於ECC最難的問題。
即便最近30年的研究,數學家任然沒有找到一個能夠解決這個問題的改進方法。
也就是說,和因式分解不同,基於當前已知的數學方法,找不到可以縮小該單向函數的正反計算難度差值的辦法。
這意味著對於許多同樣位數長度的數字,解決橢圓曲線離散對數問題要比因式分解困難的多。
因為一個算法的計算空間越密集意味著一個密碼系統越強大,所以橢圓曲線密碼學系統比RSA和Diffie-Hellman更加難以攻破。
為了理解這到底有多難被攻破,Lenstra最近提出了“全球安全(Global Security)”的概念。
你可以計算攻破一個(橢圓曲線)密碼學算法需要多少能量和計算該能量能煮沸多少水進行對比。
這是一種密碼學的碳排放量的衡量。
通過這樣的測量方法,破解一個228字節的RSA秘鑰所需能量少於煮沸一勺水的能量。
相對地,破解一個228字節的橢圓曲線秘鑰所需能量足夠煮沸地球上所以水。
而RSA要達到這樣的安全強度,需要2,380個字節的秘鑰長度。
使用ECC,你可以用更簡短的秘鑰獲得相同的安全強度。
簡短秘鑰是非常重要的,尤其是在現實中密碼學算法越來越多的運行在小功率設備裡,例如手機。
儘管兩質數相乘比把結果因式分解要簡單,但當質數變得非常大,在低功率設備上僅僅只是乘法步驟都將花費很長一段時間來計算。
雖然可以通過增加秘鑰長度來保持RSA的安全性,但卻是以犧牲客戶端的性能為代價。
相對於RSA,ECC提供了一個較好的選擇:使用簡短並且快速的秘鑰來達到高安全性。而破解ECC秘鑰你至少需要250萬年。
今天這節課之後,關於非對稱加密技術的兩種核心算法,我們都已經學過了,希望能更好地幫助大家理解區塊鏈知識。
閱讀更多 AA加速器 的文章