SIDH 中3e3 -撓基的快速生成*

王 穎 李夢(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ì)算，從而提高整體生成基的效率。

1 預(yù)備知識(shí)

1.1 SIDH 密鑰交換協(xié)議

超奇異同源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)加密的共享秘鑰。

1.2 SIDH 公鑰壓縮

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}；

1.3 Elligator 2 生成隨機(jī)點(diǎn)

2 已有3e3 -撓基生成的算法分析

2.1 na?ve 算法

2.2 3-下降算法

2.3 算法分析

生成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é)給出。

3 改進(jìn)后的SIDH 的3e3 -撓基生成

為了降低余因子乘的次數(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.1 在na?ve 方法中的改進(jìn)

3.2 在3-下降方法中的改進(jìn)

在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)如下:

3.3 點(diǎn)2 倍算法改進(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；

4 改進(jìn)算法效果分析

4.1 在na?ve 算法中的改進(jìn)效果分析

表1 列出了優(yōu)化方案的成本對(duì)比。

表1 減少成本對(duì)比

4.2 在3-下降算法中的改進(jìn)效果分析

在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ì)算。

5 結(jié)論

在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)一步研究的必要。