• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2022-11-04 02:23:02李夢(mèng)東朱屹霖
      關(guān)鍵詞:階數(shù)公鑰同源

      王 穎 李夢(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)一步研究的必要。

      猜你喜歡
      階數(shù)公鑰同源
      藥食同源
      ——紫 蘇
      兩岸年味連根同源
      關(guān)于無(wú)窮小階數(shù)的幾點(diǎn)注記
      以同源詞看《詩(shī)經(jīng)》的訓(xùn)釋三則
      確定有限級(jí)數(shù)解的階數(shù)上界的一種n階展開(kāi)方法
      一種基于混沌的公鑰加密方案
      HES:一種更小公鑰的同態(tài)加密算法
      虔誠(chéng)書(shū)畫(huà)乃同源
      SM2橢圓曲線公鑰密碼算法綜述
      一種新的多址信道有效階數(shù)估計(jì)算法*
      高邮市| 杭州市| 曲麻莱县| 永清县| 古交市| 平湖市| 天台县| 宜城市| 个旧市| 攀枝花市| 南江县| 印江| 民和| 加查县| 米脂县| 温泉县| 商水县| 芷江| 格尔木市| 遵义市| 湘阴县| 嵩明县| 望谟县| 新蔡县| 乐至县| 金湖县| 黄大仙区| 喜德县| 胶南市| 廊坊市| 那曲县| 东兴市| 荥经县| 海安县| 保山市| 华池县| 当涂县| 澎湖县| 大新县| 霍山县| 罗江县|