當(dāng)前位置:首頁 > 物聯(lián)網(wǎng) > 區(qū)塊鏈
[導(dǎo)讀] 橢圓曲線密碼學(xué)(ECC),是一種基于橢圓曲線數(shù)學(xué)誕生的非對稱秘鑰加密的算法,加密過后只有特定的人才能對其進(jìn)行解密。例如,ECC可用于確保用戶在發(fā)送電子郵件時,除了收件人之外,沒有人可以閱讀這封郵

橢圓曲線密碼學(xué)(ECC),是一種基于橢圓曲線數(shù)學(xué)誕生的非對稱秘鑰加密的算法,加密過后只有特定的人才能對其進(jìn)行解密。例如,ECC可用于確保用戶在發(fā)送電子郵件時,除了收件人之外,沒有人可以閱讀這封郵件。

橢圓曲線是近幾十年來被廣泛探索的一個重要數(shù)學(xué)新領(lǐng)域。它作為一種解決復(fù)雜數(shù)字問題的工具,以及在密碼學(xué)中的應(yīng)用顯示出巨大的潛力。

本文內(nèi)容整理自Trias技術(shù)團(tuán)隊與北大軟微學(xué)院的學(xué)術(shù)沙龍活動。

橢圓曲線數(shù)學(xué)

在探究ECC之前,我們有必要回顧一下橢圓曲線數(shù)學(xué)。

我們定義平行線相交于無窮遠(yuǎn)點P∞,使平面上所有直線都統(tǒng)一為有唯一的交點,而區(qū)別于無窮遠(yuǎn)點的原來平面上的點為平常點。通過無窮遠(yuǎn)點和平常點我們可以引入射影平面的概念。

射影平面:平面上全體無窮遠(yuǎn)點與全體平常點構(gòu)成射影平面。

而橢圓曲線,指的就是在射影平面上滿足威爾斯特拉斯方程(Weierstrass)所有點的集合,且曲線上所有點都是非奇異的。

所謂非奇異,指的是曲線上任意一點的偏導(dǎo)數(shù)不能同時為0。

明白了橢圓曲線的由來,我們再來看橢圓曲線在密碼學(xué)上應(yīng)用的方案。首先面對的問題就是橢圓曲線是連續(xù)的,并不適合用于加密。因此,橢圓曲線密碼學(xué)的第一要務(wù)就是把橢圓曲線定義在有限域上,(有限域Fp ,p為素數(shù)),并提出一條適于加密的曲線:y2=x3+ax+b (modp)。

相比起在商業(yè)中被廣泛采用的RSA加密算法,ECC優(yōu)勢是可以使用更短的密鑰,來實現(xiàn)與RSA相當(dāng)或更高級別的安全。通過下圖我們清楚的發(fā)現(xiàn),160位ECC加密安全性相當(dāng)于1024位RSA加密,而210位ECC加密安全性甚至相當(dāng)于2048位RSA加密。

眾所周知,比特幣中的公私鑰生成以及簽名算法ECDSA都是基于橢圓曲線加密算法而誕生的。ECDSA算法可以說是應(yīng)用最廣泛的橢圓曲線簽名算法,從比特幣開始,并且已經(jīng)被其它區(qū)塊鏈項目所廣泛使用。在區(qū)塊鏈中使用的公鑰生成算法是SECP256K1。

其中以太坊和比特幣的在ECDSA中的區(qū)別在于二者使用的哈希算法不同,在比特幣中使用的是SHA2-256,在以太坊中使用的是SHA3-256,同樣字節(jié)數(shù)的SHA3比SHA2更安全。

橢圓曲線加密與并行性

學(xué)術(shù)界已經(jīng)提出了很多不同的ECC選擇標(biāo)準(zhǔn),每一個都試圖確保橢圓曲線離散對數(shù)問題(ECDLP)是困難的。而ECDLP是在給定用戶公鑰的情況下查找ECC用戶密鑰的問題。

但遺憾的是,雖然標(biāo)準(zhǔn)曲線在安全實現(xiàn)理論上可行,但實踐卻表明,ECDLP并不足以完全保障ECC的安全性。人們發(fā)現(xiàn),很多攻擊可以繞過困難問題,在不解決ECDLP的情況下破壞了現(xiàn)實中在使用的ECC。

因此,如何選擇更優(yōu)質(zhì)的曲線來保障安全,并能夠比較簡單的高效率實現(xiàn),就成了安全曲線相關(guān)課題擺在明面上的難題。

為了達(dá)到上述目的,許多解決方案通過各國的學(xué)術(shù)論文被提了出來。但隨后很多的研究表明,許多所謂能提高效率的決策都不靠譜,有的并沒有作用,還有的雖然有用,但是會損害安全性。

通過研究發(fā)現(xiàn),基于橢圓曲線的密碼系統(tǒng)主要有7個系統(tǒng)參數(shù)T=(q,F(xiàn)R,a,b,G,n,h),其中q表示所選擇的有限域;FR是有限域上的元素的表示方法;a和b表示橢圓曲線的參數(shù);G是在曲線上選擇的基點;n表示該基點的階,是一個足夠大的素數(shù);h是n的余因子,是一個小整數(shù)。

在所有橢圓曲線公鑰密碼體系的實現(xiàn)中,有兩種類型的基本運(yùn)算:一類是在密碼體系設(shè)計階段要用到的基本運(yùn)算,另一類是運(yùn)行階段所要用到的。第一類是橢圓曲線密碼體系基本參數(shù)的選取,包括安全橢圓曲線的尋找和基點的選取兩部分;第二類是橢圓曲線有限域上的各種代數(shù)運(yùn)算,包括點加、倍點和數(shù)乘三種運(yùn)算。

另外,曲線系數(shù)的選取必須滿足判別式δ=4a3+27b2≠0,這是曲線選取的必要條件。異常曲線和超奇異曲線已經(jīng)被證明是不安全曲線,一定要避免使用。

關(guān)于橢圓曲線并行加速

同 RSA 公鑰密碼相比,橢圓曲線密碼提供了更高的單位比特安全強(qiáng)度 , 160 位密鑰長度的橢圓曲線密碼提供的安全強(qiáng)度,相當(dāng)于 1024 位密鑰長度的 RSA 密碼提供的安全強(qiáng)度。在這種背景下,對運(yùn)算進(jìn)行優(yōu)化便具有重要意義,并行加速便是優(yōu)化運(yùn)算的一種方式。

橢圓曲線加密的并行性處理方式到目前尚在學(xué)術(shù)界討論階段,是一個比較前沿的研究方向。就目前從技術(shù)角度而言,并行性存在著安全隱患和效率提升不明顯等問題,所以這項技術(shù)尚未大規(guī)模落地投入應(yīng)用。即便是以比特幣為代表的加密貨幣這樣的輕量級應(yīng)用,出于種種顧慮,也未采用并行加速。

北大方躍堅老師提出了4種提升橢圓加密算法效率的方式:

1、多線程并行

2、GPU并行

3、專用硬件并行處理器

4、SSE指令加速

這4種方法各有優(yōu)劣,如GPU并行雖然單位時間內(nèi)總吞吐量較高,但單個運(yùn)算卻不如CPU;專用硬件雖然能較為容易的將點乘轉(zhuǎn)化為點加提升速度,在抗攻擊等方面則存在一些問題。

馮新宇博士從等式Q=KP出發(fā),提出了幾種可能提高算法效率的方法。在這個等式中,K是一個大整數(shù),P相當(dāng)于私鑰,Q相當(dāng)于公鑰,所有這些算法都是通過對整數(shù)K進(jìn)行轉(zhuǎn)化來減少點運(yùn)算的次數(shù)。想要提升效率,就要找到一個快速計算出K·P結(jié)果的辦法,既然P不能變,那就只能從K來入手。

二進(jìn)制算法:將K轉(zhuǎn)換成2進(jìn)制(即2的冪)的形式,然后再進(jìn)行背點運(yùn)算和點加運(yùn)算,時常和滑動窗口方法結(jié)合起來使用。

窗口NAF方法:通過編碼來減少比特位中含1的個數(shù),從而減少點加的次數(shù)。但是有一個缺點,即不能抗邊信道攻擊。

邊信道攻擊(SCA, Side Channel Attack)是一種通過分析密碼設(shè)備泄露的邊信道信息來推測秘鑰的密碼分析方法。

滑動窗口方法:通過跳過比特值為0的位來減少點加的次數(shù)。

Montgomery:Montgomery 型橢圓曲線定義為E :By2 =x3 +Ax2 +x。此處 , A , B ∈ Fpn并且B(A2 -4)≠0。Euclid 加法鏈?zhǔn)菨M足如下條件的加法鏈 :v1 =1 , v2=2 , v3 =v1 +v2,對所有的 3 ≤i ≤l -1 ,如果 vi =vi -1 +vj(j 《i -1),則 vi +1 =vi +vi -1或 vi +1 =vi +vj。通過輾轉(zhuǎn)相減可以求得計算任意整數(shù) k 的加法鏈,但該加法鏈的長度取決于選取的減數(shù)g ,求最短加法鏈問題是一個 NP 完全問題。

NP完全問題,是世界七大數(shù)學(xué)難題之一。NP的英文全稱是Non-deterministic Polynomial的問題,即多項式復(fù)雜程度的非確定性問題。簡單的寫法是 NP=P?,問題就在這個問號上,到底是NP等于P,還是NP不等于P。

固定窗口方法:預(yù)存P的i倍來減少點加次數(shù)。這種方法很容易理解,即將幾種可能的情況提前算好,使用的時候直接拿來取用,提升效率的辦法。

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉