[發明專利]一種SIDH特殊域快速模乘方法

有效

• 申請號: 201910947892.9
• 申請日: 2019-09-30
• 公開（公告）號: CN111064567B
• 公開（公告）日: 2022-04-08
• 發明（設計）人: 劉偉強;倪子穎;倪健
• 申請（專利權）人: 南京航空航天大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L9/40
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 劉珊珊

本發明提出一種SIDH中特殊域快速模乘方法，該方法通過設置基數將乘數A和B表示成以R為基數的展開式；將運算A·B(mod p)轉化為計算：本發明多次使用對2移位操作，再利用數學公式將大數化小，簡化運算步驟，使得運算速度相較于之前大大提高。

技術領域

本發明涉及SIDH中特殊域模乘計算領域，尤其是一種SIDH特殊域快速模乘方法。

背景技術

由于量子計算機的研究愈發深入，量子計算機的出現只是時間問題。當量子計算機出現后現有加密方式如RSA加密和ECC(橢圓曲線加密)將失效，因此后量子密碼應運而生。

在現有的后量子密碼中，主要有格加密、代碼加密、哈希加密和超奇異同源點Diffie-Hellman(SIDH)等。相對比其他的加密方式，SIDH密鑰交換協議有著公鑰秘鑰長度短的優勢。2011年，Jao和Deo等人首先提出了SIDH密鑰交換協議。該協議中的建議使用模數為但是由于同源計算的方便，主流的實現方案中采用模數為p＝f·2^al^b-1。SIDH密鑰交換協議一直存在計算速度慢和占用資源較大的缺點。而作為算法最底層的模乘算法若對于速度和資源有所提升會對整個SIDH密鑰交換協議的實現進行提升。

發明內容

發明目的：為解決上述技術問題，本發明提出一種SIDH特殊域快速模乘方法。

技術方案：本發明提出一種SIDH特殊域快速模乘方法，在基本不增加資源的情況下，加快模乘的運算速度和提升模乘的運行頻率，該方法包括SIDH單個模乘的計算步驟：

(1)記SIDH中單個模乘計算公式為：A·B(mod p)，設置基數將乘數A和B表示成以R為基數的展開式：

A＝a₁R+a₂

B＝b₁R+b₂

其中，p為素數域，l表示一個小的素數，a和b可以為任意數，用于調節加密等級，f為將p調節為素數的參數，A和B為素數域p中的任意兩個元素，a₁、a₂分別表示用R截取的操作數A的高半段和低半段，b₁、b₂表示用R截取的操作數B的高半段和低半段；

(2)計算得到A·B(mod p)，包括依次執行步驟(2-1)至(2-7)：

(2-1)C表示為A和B相乘的積，C用R表示為：

C＝c₁·R+c₂

式中，c₁、c₂為系數變量；

(2-2)計算a₁b₁、a₁b₂、a₂b₁、a₂b₂，計算中間變量r₁＝a₁b₁mod 2^a、再計算r₁R；

(2-3)計算

(2-4)計算c₁＝q₁+(a₁b2+a₂b₁)mod 2^a+r₁Rmod 2^a；

(2-5)對c₂進行Barrett約減，約減結果記為r，即c₂＝r，約減的商記為q，計算c₁＝c₁+q；