（2，2）-同源的有效計算

張 婷 李夢東

北京電子科技學(xué)院密碼科學(xué)與技術(shù)系，北京市 100070

0 引言

在過去幾年里，基于橢圓曲線之間同源映射的密碼學(xué)因為其可以抵抗量子攻擊且密鑰長度短的性質(zhì)而取得了很大的進(jìn)展，而其代表算法SIDH（Supersingular Isogeny Diffie Hellman）的改進(jìn)算法SIKE［1］進(jìn)入到NIST 的第四輪篩選。 但最近Castryck 和Decru 提出了有效破解SIDH 的攻擊方法［2］，使得SIKE 不再安全。 其主要攻擊點為SIDH 中附加的撓點信息，采用的方法是計算橢圓曲線乘積及粘連后形成的超橢圓曲線Jicobian 之間的（2n，2n）-同源。

超橢圓曲線密碼（HECC）是橢圓曲線密碼（ECC）的推廣，其中考慮了超橢圓曲線的雅可比（Jacobian）上的群運算。 雖然這種雅可比的群計算比橢圓曲線更復(fù)雜，但它允許使用比橢圓曲線更小的素數(shù)域。 G2SIDH 是將SIDH 方案推廣到虧格2 的超橢圓曲線上的密鑰協(xié)商協(xié)議［3］。正如預(yù)期的那樣，G2SIDH 與SIDH 相比只需要其三分之一的比特長。 雖然這允許更快的素數(shù)域算術(shù)，但此時計算同源更加復(fù)雜。 其中主要計算步驟也是超橢圓曲線的Jacobian、橢圓曲線乘積之間（2n，2n） 同源計算。

（2n，2n）-同源是（2，2）- 同源的n 次迭代，因此（2，2）-同源的快速計算具有重要價值。 一般的計算（2，2）- 同源的方法是Richelot 對應(yīng)［4］。 Richelot 對應(yīng)提供了一種計算元素J ∈（為一個Jacobian）的像的方法，包括四個步驟（參見2.1 的算法一），特別是需要計算一個表示J 的除子∑k i＝1Pi∈Div（C） 的支撐度。 這涉及多次平方根計算，還在大約一半的情況需要用到基域的2 階擴(kuò)展。 2022 年S.Kunzweile 提出交換曲面之間的特定形式的同源核的（2，2） -同源一個計算公式和相應(yīng)快速算法［5］，雖然該算法計算（2，2）-同源的方法也依賴于Richelot 對應(yīng)，但不需要計算平方根，并且只需要在基域中進(jìn)行標(biāo)準(zhǔn)加法和乘法運算。 該算法可顯著提高（2，2）-同源的計算速度。

本文主要在已有算法［5］基礎(chǔ)上，對（2，2） -同源計算過程進(jìn)行了優(yōu)化和改進(jìn)，重點對除子的Mumford 表示形式中多項式系數(shù)的計算進(jìn)行改進(jìn)。通過分析各表達(dá)式中各參數(shù)的前后關(guān)系，預(yù)先計算顯示公式中的部分信息，以提高顯示公式部分計算的速率，從而相比原算法實現(xiàn)進(jìn)一步提高了整個同源計算的效率。 本文通過實驗編程驗證了改進(jìn)算法的正確性，并與原算法的復(fù)雜度進(jìn)行了對比。 改進(jìn)算法節(jié)省了27m＋10s 的計算成本，使用Python編程隨機(jī)選取參數(shù)并取100 組平均值的實現(xiàn)結(jié)果中，改進(jìn)算法相比于原算法節(jié)省了12456ns。

1 背景知識

1.1 超橢圓曲線

設(shè)Fq是域Fq的代數(shù)閉包。 域Fq上虧格為g且g≥2 的超橢圓曲線C 定義如下：

其中f（x） ∈Fq［x］ 是一個次數(shù)為2g＋1 的首一多項式，h（x） ∈Fq［x］ 是次數(shù)至多為g 的多項式，并且沒有解可以同時滿足方程y2＋h（x）y＝f（x） 和兩個偏導(dǎo)數(shù)方程2y＋h（x）＝0 和h′（x）y-f′（x）＝0。 若點（x，y）同時滿足兩個偏微分方程，那么稱其為奇異點，因此，C 是一個非奇異的超橢圓曲線，在無窮遠(yuǎn)處只有一個點P∞。 對于Fq的任何代數(shù)擴(kuò)張F(tuán)qk，考慮集合C(Fqk) ∶＝｛（x，y）∈Fqk×Fqk｜y2＋h（x）y＝f（x）｝∪｛P∞｝，稱為C 上的Fqk-有理點的集合。

本文主要討論虧格為2 且h（x）＝0 的超橢圓曲線，其曲線方程主要有兩種形式：

其中A，B，C，E∈Fq。

1.2 除子和Jacobian

超橢圓曲線C 的除子群Divc是在Fq（C）／Fq上的交換群。 一個元素D∈Divc被稱為除子，其定義如下：

其中ni∈Z，且只有有限個ni不為零。

除子D 的次數(shù)表示為系數(shù)的和，即

1.3 Mumford 表示

由一個多項式對＜a（x），b（x）＞可唯一地表示超橢圓曲線C 上Jacobian 中的非單位元素，其中一個有效除子D∈Div（C） 是在一般位置，形式如下：

令D＝P1＋…＋Pd是一個一般位置的除子，a，b∈K［x］ 具有下面性質(zhì)：

（1）a 是次數(shù)為d、首一的多項式；

（2）b 的次數(shù)小于d；

（3） f ≡b2mod a；

（4）a（ui）＝0，b（ui）＝vi，其中Pi＝（ui，vi），1 ≤i≤d。

則稱（a，b）是D 的Mumford 表示（細(xì)節(jié)見［5］）。

一般位置的每個除子都滿足一個Mumford表示，由于本文研究的是虧格為2 的超橢圓曲線，因 此deg（b） ≤deg（a） ≤2， 每 個 元 素［D］ ∈具有［P1＋P2-D∞］ 形式的唯一表示，其中

為避免歧義，對Mumford（a，b）引入以下符號：

2 已有算法

2.1 Richelot 同源［4］

對于虧格為2 的超橢圓曲線之間的同源，［4］構(gòu)造一個對應(yīng)關(guān)系，使得（2，2）-同源可依據(jù)顯式公式進(jìn)行計算，這也就是一般計算（2，2）-同源的過程。 一般的計算（2，2）-同源的方法又稱Richelot-同源的計算。 所謂的Richelot-同源提供了一種在這種同源性下計算元素J∈（是一個Jacobian）的像的方法，該算法包括四個步驟偽代碼，見表1。

2.2 Sabrina Kunzweiler 的算法［5］

［5］中提出的算法應(yīng)用于類型-1 方程的Richelot 同源。

類型-1 方程定義的虧格2 曲線C 如下：

2.2.1 計算C′

令C 是虧格2、由類型-1 方程定義的曲線：y2＝Ex（x2-Ax＋1）（x2-Bx＋），

C′是形如下面的曲線：

算法1：計算（2，2）-同源輸入：橢圓曲線C：y2 ＝g1（x）g2（x）g3（x），G ＝＜J（g1，0），J（g2，0） ＞，元素J（a，b） ∈ （C）。輸出：橢圓曲線C′，J（a′，b′） ∈ （C′）Step 1 計算C′δ ＝det（（gij）1 ≤i ≤3，0 ≤j ≤2）for i＝1 to 3｛ hi ＝δ-1（g′i＋1gi＋2 - gi＋1g′i＋2）｝C′：y2 ＝h1h2h3 Step 2 計算P，Q ∈C (K- ) ，J（a，b） ＝［P ＋Q - D∞］計算a 的根，即a（u） ＝a（s） ＝0，v ＝b（u），t ＝b（s） 得到P ＝（u，v），Q ＝（s，t）Step 3 計算計算支撐度DP，DQ ∈Div（C′）DP ＝D（aP，bP），DQ ＝D（aQ，bQ）aP ＝monic（g1（u）h1（x） ＋g2（u）h2（x））bP ＝g1（u）h1（u）（u - x）·v-1（modaP）aQ ＝monic（g1（s）h1（x） ＋g2（s）h2（x））bQ ＝g1（s）h1（s）h1（s - x）·t-1（modaQ）Step 4 使用cantor 算法計算［D′］ ＝［DP ＋DQ - 2D∞］a：組合D（a′，b′） ＝Dp ＋DQ ∈Div（C′）b：約束［D′］ ＝J（a″，b″） ∈images/BZ_62_1602_1521_1636_1564.png（C′）

點（P，P′）＝ （（u，v），（u′，v′））∈R?C×C′。2.2.3 計算P，Q

計算a的根，得到u，s，考慮到：a（u）＝a（s）＝0，v＝b（u），t＝b（s），得到P＝（u，v），Q＝（s，t），可以看到，只要考慮這個域的擴(kuò)展就足夠了

那么u＝u，s＝-a1-u，v＝b0＋ub1，t＝b0＋sb1。

2.2.4 計算支撐度

對Richelot 對應(yīng)關(guān)系中的第一個方程進(jìn)行歸一化，得到aP。 然后將Richelot 對應(yīng)中第二個等式的右側(cè)除以v 并模aP來獲得bP。

aQ，bQ是通過將（u，v） 替換為（s，t），具體結(jié)果見［5］。

2.2.5 顯式公式

算法一［4］中的前三步對應(yīng)到［5］分別是2.2.1，2.2.3，2.2.4，對于第四步，［5］提出了Richelot 同源?的顯示公式，這一公式可理解為計算任意元素J（a，b） ∈（C） 的像?（J（a，b））。 該顯示公式有如下三個條件：

（1） 0 ≠a0B2＋（a0＋1）a1B＋（a0- 1）2＋a21等價于要求u2- Bu ＋1 和s2- Bs ＋1 不零。

（2） 0 ≠-b1（a1b0-a0b1）＋b20 意味著P 和Q 都不是Weierstrass 點，因此v，t≠0。

（3） 0 ≠（a0- 1）（a21- 4a0）， 意 味 著gcd（aP，aQ）＝1，此時a′＝aP·aQ。

執(zhí)行Cantor 算法的合成步驟，輸出Mumford表示D（a′，b′）＝DP＋DQ時，我們的目標(biāo)是消除元素u∈L＼K以獲得在K 上定義的公式。 利用條件3，使a′＝aP·aQ，由于aP和aQ表達(dá)式的對稱性，可以發(fā)現(xiàn)a′ ∈K［x］L［x］。 ［5］中定理4.7 提供了a′ 系數(shù)的公式。 對于b′ 的計算，有限制條件：b′（ui）＝vi，b′（si）＝ti，i∈｛1，2｝ 這是由下述多項式來滿足的

對于計算，有必要進(jìn)一步擴(kuò)展定義域到M＝L［u1，s1］／（aP（u1），aQ（s1）） 使得：

計算b′的表達(dá)式同時考慮不同變量之間的關(guān)系，從［5］中定理4.7 得到了b′ ∈K［x］的公式。 從而得到D（a′，b′）。

通過計算得到如下顯示公式：

其 中 對 于a′，b′ 的 系 數(shù) 的 具 體 公 式請見［5］。

上述顯示公式取代算法一的步驟1，2，3，4（a）。 這導(dǎo)致同源計算的一個主要提速，因為所有平方根計算、域擴(kuò)展都可避免。 為發(fā)現(xiàn)除子類（C） 的Mumford 表示（a″，b″）， 只剩下步驟4（b）。 這包括兩個計算：

（1）計算商（f-b′2）／a′， 其中f＝（x2-1）（x2-A′）（E′x2-B′x＋C′） 是C′的定義多項式，這個商的正規(guī)化是次數(shù)最多2 的首一多項式（即把最高次項系數(shù)變成1）。

（2）計算剩余-b′moda″， 這個剩余是多項式b″，其次數(shù)小于a″。

經(jīng)過第一步的計算可以得到a″， 第二步的計算可以得到b″， 由此得到了?（J（a，b））＝［D′］＝J（a″，b″）。

3 改進(jìn)的實現(xiàn)算法

由于Jacobian 群運算的復(fù)雜性，使得同源的運算需要大量時間。 S.Kunzweile 算法［5］主要是將對類型二的超橢圓曲線的同源算法進(jìn)行改進(jìn)，將類型二的虧格為2 的超橢圓曲線轉(zhuǎn)為類型一，進(jìn)而對求根過程進(jìn)行擴(kuò)域中計算，但是最后其執(zhí)行Cantor 算法步驟時消除了擴(kuò)域元素，得到的結(jié)果依舊在基域中，經(jīng)過計算之后得到?（J（a，b）） 的顯示公式。 而本文在S.Kunzweile 等學(xué)者的工作基礎(chǔ)上對其（2，2）-同源計算公式進(jìn)行了進(jìn)一步優(yōu)化，而原公式是未經(jīng)優(yōu)化的。 預(yù)先存儲顯示公式中的部分信息，可提高顯示公式部分計算的效率。

上述顯示公式中：

經(jīng)觀察，上述系數(shù)的顯示公式中出現(xiàn)多個相同項 即（a0- 1）2＋a21，（a0＋1）a1，因此可進(jìn)行預(yù)先計算該相同項，減少公式的計算成本。 偽代碼如表2 所示。

4 性能分析

一般情況下，我們用m，s 表示有限域中的乘法運算和平方運算，用ns 表示納秒。 根據(jù)顯示公式可知未改進(jìn)之前對于a′多項式系數(shù)的計算成本是29m ＋11s，對于b′多項式系數(shù)的計算首先有2m 的預(yù)計算（即μ） 成本以及67m＋8s的公式計算成本，因此改進(jìn)之前的顯示公式的總計算成本為98m＋19s。 各參數(shù)計算成本如下：

算法2：改進(jìn)的顯示公式輸入：a0，a1，b0，b1，A，B，C輸出：a′4，a′3，a′2，a′1，a′0，b′3，b′2，b′1，b′0，b′den Step 1 預(yù)計算M，N，μ（a0 - 1）2 ＋a21 ＝M（a0 ＋1）a1 ＝N μ ＝a1b0 - a0b1 Step 2 給出a′系數(shù)公式a′0 ＝C（CM ＋BN） ＋a0B2 a′1 ＝（C - 1）（2CN ＋4Ba0）a′2 ＝- 2CM-B（C ＋1）N ＋2（- B2 ＋2（C - 1）2）a0 a′3 ＝2·（1 - C）·（2a0B ＋N）a′4 ＝M ＋B（N ＋Ba0）Step 3 給出b′系數(shù)公式b′0 ＝μ（C（M ＋Aa1） ＋Ba0（a1 ＋A）） ＋a0b0（a0 -1）（AC-B）b′1 ＝a0（2（C - 1）a1μ ＋（（C - 2）A ＋B）μ ＋（AB ＋2）b0 ＋Bb1） ＋C（A（（N - a1）b0 ＋μ） ＋b0（（a1 - a0）（a1 ＋a0） ＋1）） ＋2a20b0 b′2 ＝- 1（M ＋B（N - a1） ＋A（Ba0 ＋a0））μ ＋a0（（B-A）（a0 - 1）b0 ＋2（b1 ＋（C - 1）（b0A ＋b1 ＋μ）））b′3 ＝- a0b0AB ＋（- a20b1 - μ）A - a0（μ ＋b1）B -b0（（a0 - 1）2 ＋a1）b′den ＝（a0 - 1）·（- μb1 ＋b20）

改進(jìn)后，需要在原有基礎(chǔ)上預(yù)計算兩個元素M，N，此時需要m ＋2s 的計算成本，但改進(jìn)后對于a′多項式系數(shù)的計算成本為24m ＋5s，對于b′多項式系數(shù)的計算成本為47m ＋4s， 因此改進(jìn)之后的顯示公式的總計算成本為71m ＋9s，相對節(jié)省了27m ＋10s。

本文在windows 系統(tǒng)，CPU 為Intel（R）Core（TM）i5-8265U 的環(huán)境下，使用Python 語言對所提優(yōu)化方法進(jìn)行了編程實現(xiàn)，計算出了改進(jìn)前后方法的使用時間，其中方法所需參數(shù)根據(jù)［5］所提供的代碼選取的參數(shù)長度（30 位）隨機(jī)生成，其對比由表4 給出。

文獻(xiàn)［4］ 本文a′中系數(shù)的計算成本 29m＋11s 24m＋5s b′中系數(shù)的計算成本 67m＋8s 47m＋4s總計算成本 98m＋19s 71m＋9s

由表4、5 可以看出，改進(jìn)算法相比于原算法節(jié)省了27m＋10s 的運行成本，節(jié)省了12456ns 的時間。

python 程序運行時間（取100 組平均時間） 35273ns 22817ns

5 結(jié)束語

已有的（2，2）-同源算法中對于除子的Mumford 表示形式D（a′，b′） 中多項式系數(shù)的計算有非常復(fù)雜的公式，并且該部分的計算速度是主要影響整個（2，2）-同源的計算速度的關(guān)鍵。因此本文提出了對于計算實現(xiàn)方面的優(yōu)化辦法，即預(yù)先計算部分信息，并且與已有方法的計算成本進(jìn)行對比。