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

在審

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

技術領域

本發明涉及密碼學、信息安全領域；主要用于提高公鑰密碼體系中大數模冪計算的計算效率。具體講，涉及改進的滑動窗口模冪計算方法。

技術背景

公鑰密碼體制是目前應用非常廣泛的一種密碼體制。在信息系統安全中,特別是在數字簽名、認證和密鑰分配與管理中,公鑰密碼都扮演著必不可少的角色。公鑰密碼體制的產生源自對稱密碼中存在的兩個問題。第一個是密鑰的分配問題，對稱密碼需要通信雙方共享同一個密鑰，而且需要一個密鑰分配中心，第二個就是數字簽名的問題。Diffie和Hellman于1976年提出了一種思想從根本上異于之前的所有密碼體制。

公鑰密碼體制屬于非對稱密碼，依賴于一個加密密鑰和一個不同的解密密鑰。一個完整的公鑰密碼體制加解密過程大致包含六個要素：公鑰、私鑰、加密算法、解密算法、明文、密文。

在這種密碼體制中，所有用戶都可以獲得其他用戶的公鑰，而每個用戶各自產生并保留私鑰，不需同特定用戶共享。用戶保持私鑰的安全性，那么信息的交換都是安全的。用戶可以隨時更換私鑰，只需將更換后伴隨產生的公鑰分發替換舊的公鑰。

Diffie和Hellman提出的這種新的密碼思想使得密碼學家們競相提出了許多算法試圖滿足公鑰密碼體制的性質，但是其中的很多算法都是不健全的。1977年，MIT的三位科學家Ron?Rivest、Adi?Shamir和Len?Adleman提出了以他們三人姓氏首字母命名的算法——RSA算法，并于1978年發表。RSA算法是目前應用最為廣泛的公鑰密碼方案之一，也是第一個能同時用于信息加解密與數字簽名的算法。RSA算法的安全性基于這樣一個事實——計算兩個大質數的乘積十分容易，而將兩個大質數的乘積進行因數分解十分困難。也就是說，如果一個大數只包含兩個大的質因數，那么對其進行因數分解將十分困難。但由于公鑰密碼在加解密時所進行的模冪計算運算復雜，速度緩慢，而公鑰密碼加解密算法的速度主要取決于模冪與模乘算法的效率高低，這就使得模冪算法的計算效率成為了公鑰密碼體系的瓶頸，因此如何實現快速的模冪算法是密碼學界普遍關注的問題。

模冪的研究對象是:假設N、M、e都為k位的二進制大整數,k很大(如k>256)時,快速計算:

C＝M^e?mod?N???(1)

式(1)一般都轉化為一系列的模乘和模平方計算。如計算M¹⁵,可通過序列:

M→M²→M³→M⁴→M⁵→…M¹⁵

計算得到。顯然，這種計算方法的效率非常低下，因此，對大整數模冪和模乘算法的加速實現進行研究具有重要的理論意義和實用價值。

在實際應用中，RSA算法廣泛用于電子郵件的加密解密。電子郵件系統自動為每個用戶分配一對密鑰對(e₁,e₂)，其中，e₁為該用戶的公鑰，e₂為該用戶的私鑰，之后系統將公鑰公布出去，并將私鑰妥善保存。當用戶B向用戶A發送郵件時，通過用戶A的公鑰e₁對郵件明文M進行加密，得到密文C，并將密文C發送出去。由于RSA加密算法的性質，該密文C只有擁有對應私鑰的用戶A可以解密，從而保證了電子郵件的安全和隱私。

具體過程如下：

(1)加密過程：設M為原始郵件內容，e₁為用戶A的公鑰，N為系統統一規定的模數，則用戶B通過計算M^e1mod?N得到的密文C；

(2)解密過程：用戶A收到密文C后，使用自己的私鑰e₂，和系統規定的N進行模冪計算：C^e2mod?N，得到明文M。

發明內容

為了克服現有技術的不足，提出一種提高效率的預計算方法，能夠有效降低滑動窗口算法的計算復雜度，為此，本發明采取的技術方案是，改進的滑動窗口模冪計算方法，包括如下步驟：首先需要確定一個最大窗口長度d，窗口定義為對數字按位進行劃分的分組，每個分組的位數不大于d，然后根據具體策略將指數e劃分為零窗口與非零窗口；計算時掃描指數遇到零窗口則進行模平方操作，遇到非零窗口先進行模平方操作，再從預計算存儲值中獲取相應模冪值進行模乘操作；其中，給出滑動窗口法的窗口劃分策略具體為：用ZW表示零窗口，NW表示非零窗口，窗口長度設定為d：

初始狀態S為ZW：