王 穎 李夢東 朱屹霖

北京電子科技學(xué)院，北京市 100070

引言

同源密碼是一種新型的后量子密碼形式，其基本方案是SIDH(Supersingular Isogeny Diffie-Hellman)密鑰交換協(xié)議[1]。 同源密碼具有高安全性和公鑰長度較小的優(yōu)點，根據(jù)SIDH 的改進而成的SIKE 算法，已經(jīng)成為NIST 后量子密碼征集活動第三輪的備用算法之一。 但相對于其他后量子密碼類型，SIDH 也有相對較長的計算時間的缺點，如何提升SIDH 實現(xiàn)效率是需要加以解決的問題。

在SIDH 密鑰交換協(xié)議中公鑰生成和傳輸方面，最初的公鑰是使用(E，xP，xQ) 形式的三元組完成的[2]，其中E:y2=x3+ax+b，xP，xQ是P 和Q 的橫坐標(biāo)。 因此，公鑰的傳輸實質(zhì)上是使用四個元素a，b，xP，xQ∈Fp2，需要8log p比特。

文獻[3] 等人提出形如PK= [xφ(P)，xφ(Q)，xφ(Q-P)]∈F3p2的公鑰表示，將其大小減小為6log p比特，這也方便在解壓縮過程中使用三點階梯函數(shù)[4]，使計算效率更高。

文獻[5]提出SIDH 公鑰壓縮的思路，將公鑰中的點展開為撓基的線性組合，只傳遞其中的系數(shù)可進一步實行公鑰長度的縮短。 首先用j不變量來表示曲線E， 它也是Fp2的一個元素，同源類是由j不變量唯一決定的。 其次用?t⊕?t中的元素來表示點P、Q，將公鑰表示減小到4log p比特。 然而，這種公鑰尺寸的減少也帶來了相當(dāng)高的計算開銷。

文獻[6]等人進一步壓縮點P、Q 的表示，將公鑰大小減少到3.5log p比特，并在撓基的生成階段采用2-下降算法進行提速。 文獻[7]等人提出糾纏基和反向基分解的概念，很大程度上減少了SIDH 壓縮和解壓縮的運行時間。 文獻[8]等人對公鑰壓縮技術(shù)進一步的研究，降低了生成2e2-撓基的復(fù)雜度，對生成3e3-撓基的解壓過程也提出了改進。 文獻[9]等人提出對偶同源，對生成3e3-撓基和配對過程進行了結(jié)合，提高了整體實現(xiàn)效率。

本文詳細(xì)分析和描述了之前學(xué)者提出的關(guān)于生成3e3-撓基的實現(xiàn)步驟，并進行補充。 同時提出了新的改進方法，使得生成撓基時在隨機點的階為2r的情況下，減少e2-r次點2 倍計算，從而提高整體生成基的效率。

1 預(yù)備知識

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

超奇異同源Diffie-Hellman(SIDH)密鑰交換算法是依賴同源問題的Diffie-Hellman 算法，不受量子攻擊的影響[10]，文獻[2]中也證明了:在SSDDH(Supersingular Decision Diffie-Hellman)假設(shè)下，SIDH 密鑰協(xié)商協(xié)議在Canetti 和Krawczyk[11]的認(rèn)證鏈路對抗模型中具有會話密鑰安全性。

SIDH 協(xié)議雙方需要交換他們的公開密鑰，每個公開密鑰由橢圓曲線E′和E′上的兩點P，Q 組成[12]。 設(shè)有限域Fp2上定義一個形式為p=lelmem ±1 的大素數(shù)，其中l(wèi)和m都是小素數(shù)且lel≈mem，l和m通常分別等于2 和3。 選擇一個超奇異橢圓曲線E， 滿足＃EA(Fp2)= (lelmem)2。SIDH 密鑰交換過程可以概括為以下步驟:

①Alice 和Bob 分別在公共橢圓曲線E/Fp2上產(chǎn)生兩個獨立點PA，QA和PB，QB；

②Alice 通過兩個階為lel的獨立點生成E的撓子群E[lel]=PA，QA，群中元素階為lel；Bob通過兩個階為mem的獨立點生成E的撓子群E[mem]=PB，QB，群中元素階為mem；

③Alice 隨機選取秘密整數(shù)sA和tA∈? /lel? ，且兩者都不能被l整除，生成點RA=[sA]PA+ [tA]QA，RA的階為lel；Bob 隨機選取秘密整數(shù)sB和tB∈? /mem? ，且兩者都不能被m整除，生成點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，這些是雙方的公開信息；

⑦Alice 和Bob 通過計算得到的EAB=EBA=E/RA，RB，可以作為對稱加密的共享秘鑰。

1.2 SIDH 公鑰壓縮

SIDH 的公鑰壓縮是指將傳輸?shù)墓€以更小比特的形式表示出來，文獻[6]將公鑰大小壓縮到了3.5log p比特，但是其壓縮過程所用的計算成本仍然較高。

以Alice 端為例，定義在Fp2上的橢圓曲線E和E/RA，撓子群E[lel] 的生成點PA和QA， 點φA(PB) 和φA(QB) 作為她公開參數(shù)。

公鑰壓縮(解壓縮)過程可以概括為以下步驟:

①生成撓基:壓縮時Alice 生成撓子群E/RA[lel] 的二維撓基{R1，R2}∈Fp2[lel]；解壓縮時Bob 按照順序生成相同的撓基{R1，R2}；

1.3 Elligator 2 生成隨機點

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

2.1 na?ve 算法

2.2 3-下降算法

2.3 算法分析

生成2e2-撓基的過程通過糾纏基技術(shù)在實現(xiàn)效率上得到了很大的提升，但是由于很難應(yīng)用到3e3的情況下，現(xiàn)有的方法仍然需要分別生成不相關(guān)撓點。

下降算法減少了在判斷階數(shù)時使用余因子乘法的頻率，但是在尋找3 階點P3時，也需要大量的余因子乘法來判斷階數(shù)。

Zanon 等人[7]通過實驗觀察到，l= 2 時，na?ve 方法總是比3-下降算法快。 但兩者都需要大量的余因子乘來判斷階數(shù)，計算成本較高。本文對此進行了優(yōu)化，具體描述在下一節(jié)給出。

3 改進后的SIDH 的3e3 -撓基生成

為了降低余因子乘的次數(shù)，本文在已有的撓基生成技術(shù)基礎(chǔ)上，對隨機點的階數(shù)是否為2r進行判斷，在生成3e3-撓基的情況下，減少e2-r次點2 倍計算。 因為na?ve 算法和3-下降算法都需要余因子乘來判斷階數(shù)，所以本文的這項優(yōu)化分別應(yīng)用在兩種算法上，同時提高生成基效率。

3.1 在na?ve 方法中的改進

3.2 在3-下降方法中的改進

在3-下降方法中，尋找3-撓點P3時也通過乘余因子的方法來判斷階數(shù)。 所以同樣在計算點2 倍算法時添加判斷，若出現(xiàn)Z=0 的情況，就舍棄，立即進入下一輪的迭代來減少不必要的成本本支出。

針對3-下降算法改進如下:

3.3 點2 倍算法改進

無論是na?ve 算法還是3-下降算法，都應(yīng)用了最基礎(chǔ)的點2 倍算法，所以本文提出的改進是在點2 倍算法中實現(xiàn)的。 在SIKE 說明文件[17]中點2 倍算法也就是用Double 函數(shù)來完成的。根據(jù)本文的改進，在循環(huán)的最后一步添加了判斷，如果得到了可以使z= 0 的點，就立即終止計算，主函數(shù)就要重新生成隨機點。

改進后的算法1 如下:

算法1 在Montgomery 曲線E/Fp2:y2 = x3 +Ax2 +x 上計算r次點2 倍后的x 坐標(biāo)輸入:曲線系數(shù)A24 = (A + 2)/4，點(x，z) 和整數(shù)r。輸出:點(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； / /說明生成點的階為2i 11return x，z；

4 改進算法效果分析

4.1 在na?ve 算法中的改進效果分析

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

表1 減少成本對比

4.2 在3-下降算法中的改進效果分析

在3-下降算法中確定一個非平凡3-撓點P3仍然是一個需要乘余因子的高消耗過程，本文觀察到，在尋找3-撓點P3時，同樣沒有考慮Elligator 2 的生成點階數(shù)為2r(1＜r≤e2)的可能性，當(dāng)生成點R∈[3e3]E時，無法得到階為3的點或者是階為3e3的點，所以立即重新生成隨機點可以省去e2-r次點2 倍的計算。

5 結(jié)論

在SIDH 公鑰壓縮生成3e3-撓基的這一步中，已有的na?ve 和3-下降算法都無法避免大量的余因子乘法，而余因子乘法所用成本又相對較高，所以本文通過在點2 倍乘法的過程中判斷隨機點階數(shù)是否為2r，來排除[3e3]E中的點，從而加快生成正確階數(shù)撓點的速度。

提高SIDH 公鑰壓縮計算速度的是一項十分有意義的工作，本文只針對生成隨機點階數(shù)為2r(1＜r≤e2)的情況進行了優(yōu)化，其他情況下仍然需要高成本的計算，所以仍然有進一步研究的必要。