[發明專利]一種基于信息泄露的公鑰密碼系統的私鑰獲取方法

有效

• 申請號: 201710121266.5
• 申請日: 2017-03-02
• 公開（公告）號: CN106850223B
• 公開（公告）日: 2020-01-17
• 發明（設計）人: 呂克偉;劉加寧
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: H04L9/30
• 分類號: H04L9/30;H04L9/00
• 代理公司: 11200 北京君尚知識產權代理有限公司
• 代理人: 司立彬

本發明公開了一種基于信息泄露的公鑰密碼系統的私鑰獲取方法。本方法首先從通信數據中檢測出通信泄漏私鑰的范圍信息；然后通過預定義可區分點條件和利用三角函數進行周期迭代的方式，優化了Pollard’s kangaroos算法中每次跳躍過程中的計算代價；并且只有當相關結果滿足本發明給定的可區分條件時才進行完全乘法運算操作，從而使得Pollard’s kangaroos算法總的時間代價降低。

技術領域

本發明屬于信息安全技術領域，具體內容涉及一種基于信息泄露的公鑰密碼系統的私鑰獲取方法。

背景技術

隨著計算機技術和信息安全技術的推廣，企業界信息安全意識的逐步加強，為了滿足日益增長的用戶需求，密碼設備的密碼運算速度被一再的提升。在保證高性能密碼運算的前提下，每臺密碼設備的安全性也至關重要。

許多密碼系統和協議(如Diffie-Hellman密鑰交換協議、ELGamal加密系統、ELGamal數字簽名系統、DSA簽名系統等)的安全性都是基于離散對數問題的困難性。這些加密系統和協議被有效的應用于互聯網(保證電子郵件，家庭銀行業務以及網頁瀏覽器的安全性)、金融服務業(電子現金，信用卡交易，即時提款等服務)以及無線通信(尋呼機，手機)中。目前存在的解決經典離散對數問題的算法有baby-step giant-step method、Pollard’s rho method、index calculus method以及Pollard’s kangaroos method。其中indexcalculus method是目前最快的算法，當群元素的光滑密度適當的時候其時間復雜度是亞指數，否則仍是其中n是群的階。其他幾種算法平均情況下的時間復雜度均是隨著密碼學的發展，出現了一些特殊的離散對數問題用于解決實際中的密碼學問題，比如在某個區間上的離散對數問題。該問題的出現是由于在實際應用中，如果沒有進行有效的保護措施，敵手可能通過某些側信道攻擊的手段獲取關于離散對數的某些比特位信息，從而推斷出待求解離散對數問題的指數所在的區間范圍，之后敵手在進行離散對數求解時只需要在該區間范圍內求解即可。因此關注區間上離散對數問題的求解，在實際密碼系統安全中有重要的用途。

Pollard's kangaroos method(即袋鼠算法)是求解該問題的一個經典算法，而此時本發明求得即對應于相應密碼系統、協議的私鑰或者隨機數，實現了相關密碼系統或隨機數的攻擊。對該算法的改進也一直倍受人們關注。本發明提出一個新的改進Pollard’skangaroos算法，使得區間離散對數問題的求解效率得到提高。

發明內容

本發明提出了一種基于信息泄露的公鑰密碼系統的私鑰獲取方法，主要是通過預定義可區分點條件和利用三角函數進行周期迭代的方式，優化了Pollard’s kangaroos算法中每次跳躍過程中的計算代價；并且只有當相關結果滿足本發明給定的可區分條件時才進行完全乘法運算操作，從而使得Pollard’s kangaroos算法總的時間代價降低。