[發明專利]改進的滑動窗口模冪計算方法

在審

• 申請號: 201410726861.8
• 申請日: 2014-12-03
• 公開（公告）號: CN104468100A
• 公開（公告）日: 2015-03-25
• 發明（設計）人: 孫達志;楊博為;李曉紅
• 申請（專利權）人: 天津大學
• 主分類號: H04L9/30
• 分類號: H04L9/30;H04L9/08
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 劉國威

1.一種改進的滑動窗口模冪計算方法，其特征是，包括如下步驟：首先需要確定一個最大窗口長度d，然后根據具體策略將指數e劃分為零窗口序列Z₁,…,Z_i與非零窗口序列F₁,…,F_i；計算時掃描指數遇到零窗口則進行模平方操作，遇到非零窗口先進行模平方操作，再從預計算存儲值中獲取相應模冪值進行模乘操作；其中，給出滑動窗口法的窗口劃分策略具體為：用ZW表示零窗口，NW表示非零窗口，窗口長度設定為d：

初始狀態S為ZW：

當S＝ZW時，掃描第1位，若是0，歸入ZW，S＝ZW；若是1，歸入新的NW，S＝NW；

當S＝NW時，掃描d-1位，將本NW結束在最后一位非零位設為i位，本次掃描的i+1至d-1位歸入ZW，S＝ZW。

2.如權利要求1所述的改進的滑動窗口模冪計算方法，其特征是，所述改進的滑動窗口模冪計算方法進一步細化為：

輸入：M、e、n、d；

輸出：C＝M^e?mod?n；

其中，M代表要發送的消息，用二進制數字表示，e表示指數，n表示模數，d表示滑動窗口的最大長度，C為計算結果，mod代表模運算，即求M^e除以n所得的余數；

(1)將滑動窗口的最大長度設置為d；

(2)根據以下策略由左至右劃分指數e：

(2.1)初始狀態S為零窗口狀態用ZW表示，非零窗口狀態用NW表示；

(2.2)當S＝ZW時，掃描1位，若是0，歸入ZW，S＝ZW；若是1，歸入新的NW，S＝NW；

(2.3)當S＝NW時，向后掃描d-1位，并向前回溯至第一個非零位，設為i，將本次掃描的第1位至第i位(包括i)歸入當前的NW，將第i+1至d-1位歸入ZW，S＝ZW；

(2.4)循環(2.2)和(2.3)，直到掃描完指數e的所有位，最終得到非零窗口F₁,F₂,…,F_s，和零窗口Z₁,Z₂,…,Z_k，其中s得到的表示掃描非零窗口的數量，k表示掃描得到的零窗口的數量；

(3)根據以下策略對非零窗口進行預計算，得出加法鏈:

(3.1)對F₁,F₂,…,F_s按升序排列且每個值只記一次，得到序列W₀＝w₀₁,w₀₂,…,w_0i；

(3.2)保存a₀＝w_0i，計算t₀＝w_0i-w_0i-1；

若t₀已在W₀中出現或t₀＝1，則在W₀中刪去w_0i，得到W₁＝w₀₁,w₀₂,…,w_0i-1；

否則在W₀中用t₀替換w_0i，得到W₁＝w₀₁,w₀₂,…,w_0i-1,t₀；

(3.3)以上一步中得到的W_i-1序列為輸入，重復(3.1)-(3.2)步驟，直至W_i中只剩下一個元素W_i1；

(3.4)用任何一種計算可行的方法求出w_i1的一條加法鏈，得到a_i,a_i+1,…,a_s；

(3.5)對A＝a₀,a₁,…,a_s按升序排列；

(4)使用加法鏈A＝a₀,a₁,…,a_s，計算M^Fi的值，其中F_i為非零窗口，i＝1,2,…,s；

(5)初始C＝M^F1，i從2到s做循環：

(5.1)C＝(C*M^Fi)mod?n；

(6)對零窗口Z₁,Z₂,…,Z_k，i從1到k做循環：

(6.1)C＝C^Ei?mod?n，這里E_i＝2^Li，L_i為窗口F_i的長度；

(7)輸出密文C。

3.如權利要求2所述的改進的滑動窗口模冪計算方法，其特征是，隨著指數長度的增加，滑動窗口的長度也應當相應增加以獲得更好地計算效率；當指數長度為3時，滑動窗口的長度應為4位，而指數長度增加到1024時，滑動窗口長度選擇為6為，指數長度為4096時，滑動窗口長度為7。