張 婷 李夢(mèng)東

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

0 引言

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

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

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

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

1 背景知識(shí)

1.1 超橢圓曲線

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

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

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

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

1.2 除子和Jacobian

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

其中ni∈Z，且只有有限個(gè)ni不為零。

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

1.3 Mumford 表示

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

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

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

（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é)見(jiàn)［5］）。

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

為避免歧義，對(duì)Mumford（a，b）引入以下符號(hào)：

2 已有算法

2.1 Richelot 同源［4］

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

2.2 Sabrina Kunzweiler 的算法［5］

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

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

2.2.1 計(jì)算C′

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

C′是形如下面的曲線：

算法1：計(jì)算（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 計(jì)算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 計(jì)算P，Q ∈C (K- ) ，J（a，b） ＝［P ＋Q - D∞］計(jì)算a 的根，即a（u） ＝a（s） ＝0，v ＝b（u），t ＝b（s） 得到P ＝（u，v），Q ＝（s，t）Step 3 計(jì)算計(jì)算支撐度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 算法計(jì)算［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′）

點(diǎn)（P，P′）＝ （（u，v），（u′，v′））∈R?C×C′。2.2.3 計(jì)算P，Q

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

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

2.2.4 計(jì)算支撐度

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

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

2.2.5 顯式公式

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

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

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

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

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

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

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

通過(guò)計(jì)算得到如下顯示公式：

其 中 對(duì) 于a′，b′ 的 系 數(shù) 的 具 體 公 式請(qǐng)見(jiàn)［5］。

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

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

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

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

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

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

上述顯示公式中：

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

4 性能分析

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

算法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ù)計(jì)算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ù)計(jì)算兩個(gè)元素M，N，此時(shí)需要m ＋2s 的計(jì)算成本，但改進(jìn)后對(duì)于a′多項(xiàng)式系數(shù)的計(jì)算成本為24m ＋5s，對(duì)于b′多項(xiàng)式系數(shù)的計(jì)算成本為47m ＋4s， 因此改進(jìn)之后的顯示公式的總計(jì)算成本為71m ＋9s，相對(duì)節(jié)省了27m ＋10s。

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

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

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

python 程序運(yùn)行時(shí)間（取100 組平均時(shí)間） 35273ns 22817ns

5 結(jié)束語(yǔ)

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