改進的滑動窗口模冪計算方法
2023-12-06 10:17:46 1
改進的滑動窗口模冪計算方法
【專利摘要】本發明涉及密碼學、信息安全領域，為提出一種提高效率的預計算方法，能夠有效降低滑動窗口算法的計算複雜度，為此，本發明採取的技術方案是，改進的滑動窗口模冪計算方法，包括如下步驟：首先需要確定一個最大窗口長度d，窗口定義為對數字按位進行劃分的分組，每個分組的位數不大於d，然後根據具體策略將指數e劃分為零窗口與非零窗口；計算時掃描指數遇到零窗口則進行模平方操作，遇到非零窗口先進行模平方操作，再從預計算存儲值中獲取相應模冪值進行模乘操作。本發明主要應用於數據處理及機要通信。
【專利說明】改進的滑動窗口模冪計算方法
【技術領域】
[0001] 本發明涉及密碼學、信息安全領域；主要用於提高公鑰密碼體系中大數模冪計算 的計算效率。具體講，涉及改進的滑動窗口模冪計算方法。 技術背景
[0002] 公鑰密碼體制是目前應用非常廣泛的一種密碼體制。在信息系統安全中，特別是 在數字籤名、認證和密鑰分配與管理中，公鑰密碼都扮演著必不可少的角色。公鑰密碼體 制的產生源自對稱密碼中存在的兩個問題。第一個是密鑰的分配問題，對稱密碼需要通信 雙方共享同一個密鑰，而且需要一個密鑰分配中心，第二個就是數字籤名的問題。Diffie和 Heilman於1976年提出了一種思想從根本上異於之前的所有密碼體制。
[0003] 公鑰密碼體制屬於非對稱密碼，依賴於一個加密密鑰和一個不同的解密密鑰。一 個完整的公鑰密碼體制加解密過程大致包含六個要素：公鑰、私鑰、加密算法、解密算法、明 文、密文。
[0004] 在這種密碼體制中，所有用戶都可以獲得其他用戶的公鑰，而每個用戶各自產生 並保留私鑰，不需同特定用戶共享。用戶保持私鑰的安全性，那麼信息的交換都是安全的。 用戶可以隨時更換私鑰，只需將更換後伴隨產生的公鑰分發替換舊的公鑰。
[0005]Diffie和Heilman提出的這種新的密碼思想使得密碼學家們競相提出了許多算 法試圖滿足公鑰密碼體制的性質，但是其中的很多算法都是不健全的。1977年，MIT的三 位科學家RonRivest、AdiShamir和LenAdleman提出了以他們三人姓氏首字母命名的 算法--RSA算法，並於1978年發表。RSA算法是目前應用最為廣泛的公鑰密碼方案之一， 也是第一個能同時用於信息加解密與數字籤名的算法。RSA算法的安全性基於這樣一個事 實--計算兩個大質數的乘積十分容易，而將兩個大質數的乘積進行因數分解十分困難。 也就是說，如果一個大數隻包含兩個大的質因數，那麼對其進行因數分解將十分困難。但由 於公鑰密碼在加解密時所進行的模冪計算運算複雜，速度緩慢，而公鑰密碼加解密算法的 速度主要取決於模冪與模乘算法的效率高低，這就使得模冪算法的計算效率成為了公鑰密 碼體系的瓶頸，因此如何實現快速的模冪算法是密碼學界普遍關注的問題。
[0006] 模冪的研究對象是：假設N、M、e都為k位的二進位大整數，k很大（如k>256) 時，快速計算：
【權利要求】
1. 一種改進的滑動窗口模幕計算方法，其特徵是，包括如下步驟：首先需要確定一個 最大窗口長度d，然後根據具體策略將指數e劃分為零窗口序列Zi，…，Zi與非零窗口序列 計算時掃描指數遇到零窗口則進行模平方操作，遇到非零窗口先進行模平方操 作，再從預計算存儲值中獲取相應模幕值進行模乘操作；其中，給出滑動窗口法的窗口劃分 策略具體為；用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 = ]\r mod n ; 其中，M代表要發送的消息，用二進位數字表示，e表示指數，n表示模數，d表示滑動窗 口的最大長度，C為計算結果，mod代表模運算，即求M6除W n所得的餘數； (1) 將滑動窗口的最大長度設置為d ; (2) 根據W下策略由左至右劃分指數e : (2. 1)初始狀態S為零窗口狀態用ZW表示，非零窗口狀態用NW表示； (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. 3)，直到掃描完指數e的所有位，最終得到非零窗口F,，… ，Fs，和零窗口 Zi，Z2,…，Zk，其中S得到的表示掃描非零窗口的數量，k表示掃描得到的零窗 口的數量； (3) 根據W下策略對非零窗口進行預計算，得出加法鏈： (3. 1)對F2,…，F傑升序排列且每個值只記一次，得到序列W。= W。1，"。2,…，Wm; (3. 2)保存 a〇= W M，計算 t〇= W 若t〇已在W〇中出現或t〇= 1，則在W衝刪去Wm，得到Wi=Wm，W〇2,…， 否則在W。中用t。替換Wm，得到Wi=W〇i，W〇2,…，W〇H，t。； (3. 3) w上一步中得到的Wh序列為輸入，重複化1)-(3. 2)步驟，直至Wi中只剩下一 個元素Wii; (3. 4)用任何一種計算可行的方法求出Wii的一條加法鏈，得到a。心，…，屯； 化5)對A = a。，a。…，a傑升序排列； (4) 使用加法鏈A = a。，a。…，屯，計算的值，其中F i為非零窗口，i = 1，2,…，S ; 妨初始C = M"，i從2到S做循環： (5. 1)C = (C*MM)mod n ; (6) 對零窗口 Zi，Z2,…，Zk，i從1到k做循環： (6.1)0 =〔61111〇(1。，該裡&=2。山為窗口！^的長度； (7) 輸出密文C。
3.如權利要求2所述的改進的滑動窗口模幕計算方法，其特徵是，隨著指數長度的增 力口，滑動窗口的長度也應當相應增加W獲得更好地計算效率；當指數長度為3時，滑動窗口 的長度應為4位，而指數長度增加到1024時，滑動窗口長度選擇為6為，指數長度為4096 時，滑動窗口長度為7。
【文檔編號】H04L9/30GK104468100SQ201410726861
【公開日】2015年3月25日 申請日期:2014年12月3日 優先權日:2014年12月3日
【發明者】孫達志, 楊博為, 李曉紅 申請人:天津大學