[發明專利]用于數據安全通信的并行模乘方法

在審

• 申請號: 201911005389.8
• 申請日: 2019-10-22
• 公開（公告）號: CN110865794A
• 公開（公告）日: 2020-03-06
• 發明（設計）人: 王暉
• 申請（專利權）人: 天津津航計算技術研究所
• 主分類號: G06F7/72
• 分類號: G06F7/72
• 代理公司: 中國兵器工業集團公司專利中心 11011
• 代理人: 周恒

1.一種用于數據安全通信的并行模乘方法，其特征在于，所述并行模乘方法將兩個操作乘數輸入A，B都拆分為(w₀,w₂,……w_r)多比特位的表示形式，進行逐字掃描運算；將乘法和約減操作分布在同一內循環之內，模乘運算就被分解為r-bit×r-bit乘法器能夠實現的操作。

2.如權利要求1所述的用于數據安全通信的并行模乘方法，其特征在于，所述并行模乘方法針對256位的大數模乘，其模乘運算被分解為r-bit×r-bit乘法器能夠實現的操作，其中r取值為64。

3.如權利要求1所述的用于數據安全通信的并行模乘方法，其特征在于，所述并行模乘方法包括如下步驟：

步驟1：設置存放模乘結果的數R＝0，將操作數A拆分為(A₀,A₁,A₂,A₃)，操作數B拆分為(B₀,B₁,B2,B₃)，模數N也拆分為(N₀,N1,N₂,N3)；

步驟2：拆分出四個無數據依賴的乘法，t₀到t₃分別存放計算結果：t₀＝B₀A₀ mod 2^r，t₁＝B₁A₀ mod 2^r，t₂＝B₂A₀ mod 2^r，t₃＝B₃A₀ mod 2^r；

步驟3：對于計數值i從0到3執行以下步驟，P_i0到P_i3存放計算結果：{P_i0＝A₀B_i，P_i1＝A₁B_i，P_i2＝A₂B_i，P_i3＝A₃B_i}；

同樣本步驟的四個乘法操作無數據依賴，可進行全部并行化運行；

步驟4：對于計數值i從0到3執行以下步驟，s_i0到s_i3存放計算結果：{s_i0＝N₀t_i，s_i1＝N₁t_i，s_i2＝N₂t_i，s_i3＝N₃t_i}；

同樣本步驟的四個乘法操作無數據依賴，可進行全部并行化運行；

步驟5：計算臨時計算結果變量的累加和：R＝∑(p_ij+s_ij)2^(i+j)r；

其中，i＝0,1,2,3；j＝0,1,2,3；

步驟6：如果R>N，則進行計算R＝R-N；

步驟7：最后，得到模乘運算的結果：R。

4.如權利要求1所述的用于數據安全通信的并行模乘方法，其特征在于，所述步驟2中，四個乘法可進行并行化運算，64位乘法運算的并行能夠將運算時間減少為之前1/4。

5.如權利要求1所述的用于數據安全通信的并行模乘方法，其特征在于，所述方法通過將蒙哥馬利模乘的操作數進行拆分重排，避免了原模乘運算各步間的數據依賴。

6.如權利要求1所述的用于數據安全通信的并行模乘方法，其特征在于，所述方法中，每步運算均可由4個64-bit乘法器并行執行，運算的結果作為模乘的部分積在步驟5中統一進行壓縮。