王 穎 李夢(mèng)東 朱屹霖
北京電子科技學(xué)院,北京市 100070
同源密碼是一種新型的后量子密碼形式,其基本方案是SIDH(Supersingular Isogeny Diffie-Hellman)密鑰交換協(xié)議[1]。 同源密碼具有高安全性和公鑰長(zhǎng)度較小的優(yōu)點(diǎn),根據(jù)SIDH 的改進(jìn)而成的SIKE 算法,已經(jīng)成為NIST 后量子密碼征集活動(dòng)第三輪的備用算法之一。 但相對(duì)于其他后量子密碼類(lèi)型,SIDH 也有相對(duì)較長(zhǎng)的計(jì)算時(shí)間的缺點(diǎn),如何提升SIDH 實(shí)現(xiàn)效率是需要加以解決的問(wèn)題。
在SIDH 密鑰交換協(xié)議中公鑰生成和傳輸方面,最初的公鑰是使用(E,xP,xQ) 形式的三元組完成的[2],其中E:y2=x3+ax+b,xP,xQ是P 和Q 的橫坐標(biāo)。 因此,公鑰的傳輸實(shí)質(zhì)上是使用四個(gè)元素a,b,xP,xQ∈Fp2,需要8log p比特。
文獻(xiàn)[3] 等人提出形如PK= [xφ(P),xφ(Q),xφ(Q-P)]∈F3p2的公鑰表示,將其大小減小為6log p比特,這也方便在解壓縮過(guò)程中使用三點(diǎn)階梯函數(shù)[4],使計(jì)算效率更高。
文獻(xiàn)[5]提出SIDH 公鑰壓縮的思路,將公鑰中的點(diǎn)展開(kāi)為撓基的線性組合,只傳遞其中的系數(shù)可進(jìn)一步實(shí)行公鑰長(zhǎng)度的縮短。 首先用j不變量來(lái)表示曲線E, 它也是Fp2的一個(gè)元素,同源類(lèi)是由j不變量唯一決定的。 其次用?t⊕?t中的元素來(lái)表示點(diǎn)P、Q,將公鑰表示減小到4log p比特。 然而,這種公鑰尺寸的減少也帶來(lái)了相當(dāng)高的計(jì)算開(kāi)銷(xiāo)。
文獻(xiàn)[6]等人進(jìn)一步壓縮點(diǎn)P、Q 的表示,將公鑰大小減少到3.5log p比特,并在撓基的生成階段采用2-下降算法進(jìn)行提速。 文獻(xiàn)[7]等人提出糾纏基和反向基分解的概念,很大程度上減少了SIDH 壓縮和解壓縮的運(yùn)行時(shí)間。 文獻(xiàn)[8]等人對(duì)公鑰壓縮技術(shù)進(jìn)一步的研究,降低了生成2e2-撓基的復(fù)雜度,對(duì)生成3e3-撓基的解壓過(guò)程也提出了改進(jìn)。 文獻(xiàn)[9]等人提出對(duì)偶同源,對(duì)生成3e3-撓基和配對(duì)過(guò)程進(jìn)行了結(jié)合,提高了整體實(shí)現(xiàn)效率。
本文詳細(xì)分析和描述了之前學(xué)者提出的關(guān)于生成3e3-撓基的實(shí)現(xiàn)步驟,并進(jìn)行補(bǔ)充。 同時(shí)提出了新的改進(jìn)方法,使得生成撓基時(shí)在隨機(jī)點(diǎn)的階為2r的情況下,減少e2-r次點(diǎn)2 倍計(jì)算,從而提高整體生成基的效率。
超奇異同源Diffie-Hellman(SIDH)密鑰交換算法是依賴(lài)同源問(wèn)題的Diffie-Hellman 算法,不受量子攻擊的影響[10],文獻(xiàn)[2]中也證明了:在SSDDH(Supersingular Decision Diffie-Hellman)假設(shè)下,SIDH 密鑰協(xié)商協(xié)議在Canetti 和Krawczyk[11]的認(rèn)證鏈路對(duì)抗模型中具有會(huì)話(huà)密鑰安全性。
SIDH 協(xié)議雙方需要交換他們的公開(kāi)密鑰,每個(gè)公開(kāi)密鑰由橢圓曲線E′和E′上的兩點(diǎn)P,Q 組成[12]。 設(shè)有限域Fp2上定義一個(gè)形式為p=lelmem ±1 的大素?cái)?shù),其中l(wèi)和m都是小素?cái)?shù)且lel≈mem,l和m通常分別等于2 和3。 選擇一個(gè)超奇異橢圓曲線E, 滿(mǎn)足#EA(Fp2)= (lelmem)2。SIDH 密鑰交換過(guò)程可以概括為以下步驟:
①Alice 和Bob 分別在公共橢圓曲線E/Fp2上產(chǎn)生兩個(gè)獨(dú)立點(diǎn)PA,QA和PB,QB;
②Alice 通過(guò)兩個(gè)階為lel的獨(dú)立點(diǎn)生成E的撓子群E[lel]=PA,QA,群中元素階為lel;Bob通過(guò)兩個(gè)階為mem的獨(dú)立點(diǎn)生成E的撓子群E[mem]=PB,QB,群中元素階為mem;
③Alice 隨機(jī)選取秘密整數(shù)sA和tA∈? /lel? ,且兩者都不能被l整除,生成點(diǎn)RA=[sA]PA+ [tA]QA,RA的階為lel;Bob 隨機(jī)選取秘密整數(shù)sB和tB∈? /mem? ,且兩者都不能被m整除,生成點(diǎn)RB= [sB]PB+ [tB]QB,RB的階為mem;
④Alice 得到RA生成的循環(huán)群RA,#RA=lel;Bob 得到RB生成的循環(huán)群RB,#RB=mem;
⑤Alice 根據(jù)核KerφA=RA,得到同源φA:E→EA(唯一)[13],作為Alice 的私鑰,這里EA=E/RA; Bob 根據(jù)核KerφB=RB,得到同源φB:E→EB(唯一)[13],作為Bob 的私鑰,這里EB=E/RB;
⑥ Alice 將φA(PB)、φA(QB)、EA發(fā)送給Bob;Bob 將φB(PA)、φB(QA)、EB發(fā)給Alice,這些是雙方的公開(kāi)信息;
⑦Alice 和Bob 通過(guò)計(jì)算得到的EAB=EBA=E/RA,RB,可以作為對(duì)稱(chēng)加密的共享秘鑰。
SIDH 的公鑰壓縮是指將傳輸?shù)墓€以更小比特的形式表示出來(lái),文獻(xiàn)[6]將公鑰大小壓縮到了3.5log p比特,但是其壓縮過(guò)程所用的計(jì)算成本仍然較高。
以Alice 端為例,定義在Fp2上的橢圓曲線E和E/RA,撓子群E[lel] 的生成點(diǎn)PA和QA, 點(diǎn)φA(PB) 和φA(QB) 作為她公開(kāi)參數(shù)。
公鑰壓縮(解壓縮)過(guò)程可以概括為以下步驟:
①生成撓基:壓縮時(shí)Alice 生成撓子群E/RA[lel] 的二維撓基{R1,R2}∈Fp2[lel];解壓縮時(shí)Bob 按照順序生成相同的撓基{R1,R2};
生成2e2-撓基的過(guò)程通過(guò)糾纏基技術(shù)在實(shí)現(xiàn)效率上得到了很大的提升,但是由于很難應(yīng)用到3e3的情況下,現(xiàn)有的方法仍然需要分別生成不相關(guān)撓點(diǎn)。
下降算法減少了在判斷階數(shù)時(shí)使用余因子乘法的頻率,但是在尋找3 階點(diǎn)P3時(shí),也需要大量的余因子乘法來(lái)判斷階數(shù)。
Zanon 等人[7]通過(guò)實(shí)驗(yàn)觀察到,l= 2 時(shí),na?ve 方法總是比3-下降算法快。 但兩者都需要大量的余因子乘來(lái)判斷階數(shù),計(jì)算成本較高。本文對(duì)此進(jìn)行了優(yōu)化,具體描述在下一節(jié)給出。
為了降低余因子乘的次數(shù),本文在已有的撓基生成技術(shù)基礎(chǔ)上,對(duì)隨機(jī)點(diǎn)的階數(shù)是否為2r進(jìn)行判斷,在生成3e3-撓基的情況下,減少e2-r次點(diǎn)2 倍計(jì)算。 因?yàn)閚a?ve 算法和3-下降算法都需要余因子乘來(lái)判斷階數(shù),所以本文的這項(xiàng)優(yōu)化分別應(yīng)用在兩種算法上,同時(shí)提高生成基效率。
在3-下降方法中,尋找3-撓點(diǎn)P3時(shí)也通過(guò)乘余因子的方法來(lái)判斷階數(shù)。 所以同樣在計(jì)算點(diǎn)2 倍算法時(shí)添加判斷,若出現(xiàn)Z=0 的情況,就舍棄,立即進(jìn)入下一輪的迭代來(lái)減少不必要的成本本支出。
針對(duì)3-下降算法改進(jìn)如下:
無(wú)論是na?ve 算法還是3-下降算法,都應(yīng)用了最基礎(chǔ)的點(diǎn)2 倍算法,所以本文提出的改進(jìn)是在點(diǎn)2 倍算法中實(shí)現(xiàn)的。 在SIKE 說(shuō)明文件[17]中點(diǎn)2 倍算法也就是用Double 函數(shù)來(lái)完成的。根據(jù)本文的改進(jìn),在循環(huán)的最后一步添加了判斷,如果得到了可以使z= 0 的點(diǎn),就立即終止計(jì)算,主函數(shù)就要重新生成隨機(jī)點(diǎn)。
改進(jìn)后的算法1 如下:
算法1 在Montgomery 曲線E/Fp2:y2 = x3 +Ax2 +x 上計(jì)算r次點(diǎn)2 倍后的x 坐標(biāo)輸入:曲線系數(shù)A24 = (A + 2)/4,點(diǎn)(x,z) 和整數(shù)r。輸出:點(diǎn)(x’,z’) = [2r](x,z) ∈E。1for j = 1 to r do 2a ←x + z;3b ←x - z;4 aa ←a2;5bb ←b2;6c ←aa - bb;7x ←aa·bb;8 z ←c(bb + A24·c);9 if z = 0 then 10 Abort; / /說(shuō)明生成點(diǎn)的階為2i 11return x,z;
表1 列出了優(yōu)化方案的成本對(duì)比。
表1 減少成本對(duì)比
在3-下降算法中確定一個(gè)非平凡3-撓點(diǎn)P3仍然是一個(gè)需要乘余因子的高消耗過(guò)程,本文觀察到,在尋找3-撓點(diǎn)P3時(shí),同樣沒(méi)有考慮Elligator 2 的生成點(diǎn)階數(shù)為2r(1<r≤e2)的可能性,當(dāng)生成點(diǎn)R∈[3e3]E時(shí),無(wú)法得到階為3的點(diǎn)或者是階為3e3的點(diǎn),所以立即重新生成隨機(jī)點(diǎn)可以省去e2-r次點(diǎn)2 倍的計(jì)算。
在SIDH 公鑰壓縮生成3e3-撓基的這一步中,已有的na?ve 和3-下降算法都無(wú)法避免大量的余因子乘法,而余因子乘法所用成本又相對(duì)較高,所以本文通過(guò)在點(diǎn)2 倍乘法的過(guò)程中判斷隨機(jī)點(diǎn)階數(shù)是否為2r,來(lái)排除[3e3]E中的點(diǎn),從而加快生成正確階數(shù)撓點(diǎn)的速度。
提高SIDH 公鑰壓縮計(jì)算速度的是一項(xiàng)十分有意義的工作,本文只針對(duì)生成隨機(jī)點(diǎn)階數(shù)為2r(1<r≤e2)的情況進(jìn)行了優(yōu)化,其他情況下仍然需要高成本的計(jì)算,所以仍然有進(jìn)一步研究的必要。