[發明專利]基于RSA密碼算法的密鑰生成系統及方法

在審

• 申請號: 201710129114.X
• 申請日: 2017-03-06
• 公開（公告）號: CN106850212A
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 董慶寬;吳克強;樊凱;薄星;李軍輝;陶雅欣
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L9/08
• 分類號: H04L9/08;H04L9/30;H04L9/32
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 田文英,王品華

技術領域

本發明屬于通信技術領域，更進一步涉及信息安全技術領域中的一種公鑰密碼體制中基于RSA密碼算法的密鑰生成系統及方法。本發明通過對大素數進行預處理，結合Miller-Rabin檢測，在計算私鑰是采用改進的歐幾里得算法，有效避免了除法問題，生成符合RSA算法要求的密鑰。

背景技術

隨著通信及信息安全技術的發展，公鑰密碼體制越來越受到人們的重視。在眾多的公開密鑰密碼算法中，RSA密碼算法是最成熟，也是使用最廣泛的一種密碼算法。它不僅具有傳統的信息加密能力，并且能夠用于驗證信息的真實性、完整性和有效性，從而受到了廣大用戶的青睞，并已經成為了公鑰密碼的國際標準。但是實際上RSA密碼算法也有著它本身不可避免的缺點，產生密鑰很麻煩，受到素數產生技術的限制，難以做到一次一密；速度太慢，由于RSA的分組長度太大，為保證安全性，n至少也要600比特以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數量級。因此如何在短時間內產生大量符合RSA算法要求的密鑰成為當前的研究熱點。

龍建超在其發表的論文“公鑰算法中大素數生成方法的研究改進”(云南大學碩士學位論文,2014)中提出了一種改進的公鑰算法中大素數的生成方法。該方法在大素數傳統生成方法的基礎上，利用隨機遞增搜索，結合準梅森素數的特性，生成隨機數后增加預過濾過程，再進行素性檢測得到大素數，減少了大素數的生成時間。該方法存在的不足之處是，素性檢測結果是素數的概率不夠大，導致RSA密碼算法不安全。

南京郵電大學在其申請的專利文獻“一種改進的快速生成大素數的方法”(專利申請號：201510814574.1，申請公布號：CN1015770A)中公開了一種改進的快速生成大素數的方法。該方法能夠快速生成大素數，是基于Miller-Rabin素性檢測算法，并且采用蒙哥馬利算法對原Miller-Rabin算法檢測素數進行了優化。蒙哥馬利算法采用的是模加右移的方法，有效地避免了求模運算中比較耗時的除法運算，減少了原算法中模冪運算的次數，從而提高了對素數的檢測速度。但是，該方法仍然存在的不足之處是，在計算模逆時，需要循環1024次導致計算復雜而影響RSA密碼的實際應用。

深圳數字電視國家工程實驗室股份有限公司在其申請的專利文獻“RSA密鑰生成方法及裝置”(專利申請號：201410092851.3，申請公布號：CN103812648A)中公開了一種RSA密鑰生成方法及裝置。該裝置將生成密鑰所需的高運算量的計算轉移到可信平臺外部，減輕了可信平臺模塊的計算負擔。但是，該裝置仍然存在的不足之處是，RSA密鑰參數創建時，沒有對大素數進行預處理的模塊，導致系統在進行素數檢測時計算量太大而影響RSA的密鑰生成速度。

發明內容

本發明的目的在于克服上述已有技術的不足，提出一種基于RSA密碼算法的密鑰生成方法。本發明通過對大素數進行預處理，結合Miller-Rabin檢測，在獲得私鑰時采用改進的歐幾里得方法，有效避免了除法問題，進一步提高了RSA密鑰生成效率。

為實現上述目的，本發明的系統包括乘法器模塊、隨機數模塊、預處理模塊、判決模塊、模值生成模塊、模逆模塊、輸出模塊，其中：

所述的乘法器模塊，用于計算500以內的所有素數的積；

所述的隨機數模塊，用于隨機生成一個512位的整數；

所述的預處理模塊，用于計算500以內所有素數的積與所生成整數的最大公約數；

所述的判決模塊，用于對所生成的與500以內所有素數的積互素的整數進行米勒-拉賓Miller-Rabin素性檢測；

所述的模值生成模塊，用于計算RSA的模值；

所述的模逆模塊，用于計算RSA的私鑰指數；

所述的輸出模塊，用于輸出模值、第一因子、第二因子、私鑰指數。

本發明的方法的具體實現步驟如下：

(1)生成RSA模值的第一因子：

采用RSA模值因子的生成方法，生成羅納德·李維斯特、阿迪·薩莫爾、倫納德·阿德曼RSA模值的第一因子p；

(2)生成RSA模值的第二因子：

采用RSA模值因子的生成方法，生成羅納德·李維斯特、阿迪·薩莫爾、倫納德·阿德曼RSA模值的第二因子q；

(3)生成模值：

模值生成模塊將第一因子p與第二因子q相乘，得到羅納德·李維斯特、阿迪·薩莫爾、倫納德·阿德曼RSA的模值；

(4)計算RSA的私鑰指數：

(4a)將傳統的歐幾里得算法中的除法操作轉變為移位操作后，得到改進的歐幾里得算法；