[發明專利]一種RSA加密算法中的大素數生成方法及裝置

在審

• 申請號: 201611254464.0
• 申請日: 2016-12-30
• 公開（公告）號: CN108270564A
• 公開（公告）日: 2018-07-10
• 發明（設計）人: 吳劍文;何偉潮;單小紅;麻建
• 申請（專利權）人: 廣東精點數據科技股份有限公司
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 北京隆源天恒知識產權代理事務所(普通合伙) 11473
• 代理人: 閆冬

本發明公開一種RSA加密算法中的大素數生成方法及裝置，其方法包括：步驟S1，進行大素數的搜索，生成偽素數；步驟S2，預處理單元2，其對所述偽素數進行預處理；步驟S3，檢測單元3，其對預處理后的所述偽素數的素性進行檢測，得到大素數；其裝置包括對應的搜索單元、預處理單元和檢測單元。這樣，可以快速生成大素數，時間短，效率高。

技術領域

本發明涉及加密技術領域，具體涉及一種RSA加密算法中的大素數生成方法及裝置。

背景技術

隨著互聯網的飛速發展和計算機技術的廣泛應用，網絡時代確保信息安全至關重要。信息加密技術是保證網絡中數據安全的最主要最基本的措施之一，其中RSA加密算法被認為是最優秀、最完善，同時也是應用最為廣泛的算法。

RSA加密算法是一種典型的公鑰密碼算法，具有加密密鑰和解密密鑰兩個相關但是不同的密鑰。在公鑰密碼算法中，加密密鑰可以公開作為公鑰，而解密密鑰作為保密的私鑰。在RSA加密算法中，公鑰和密鑰都可以用來進行數據的加密。而另外一個可以作為相應的解密密鑰，并且可以保證無法從公鑰中推導出私鑰，也無法從密文中推導出明文。

在RSA加密算法中，需要生成數量級很大的素數，目前能預測保證在2030年之前足夠安全的RSA密鑰長度是2048bit，但生成這種長度的大素數(即數量級很大的素數)是很困難的事情。目前生成素數的方法主要有概率性生成素數和確定性生成素數兩種；但概率性生成素數由于素數分布的不確定性，生成時很是耗時，且生成的很可能只是一個接近于素數的偽素數；確定性生成的素數可以保證所生成的數一定是素數，但是這種方法所生成的素數具有一定的規律，而攻擊者可以使用較小的代價來推導出素數生成的規律。

因此，需要一種高效率的大素數生成方法及裝置。

鑒于上述缺陷，本發明創作者經過長時間的研究和實踐終于獲得了本發明。

發明內容

為解決上述技術缺陷，本發明采用的技術方案在于，首先提供一種RSA加密算法中的大素數生成方法，其包括：

步驟S1，進行大素數的搜索，生成偽素數；

步驟S2，對所述偽素數進行預處理；

步驟S3，對預處理后的所述偽素數的素性進行檢測，得到大素數。

較佳的，所述步驟S2包括：

步驟S22，使用小素數整除法排除所述偽素數中能被小素數整除的數；

步驟S23，使用Miller-Rabin算法對所述偽素數進行5次檢測，保留通過檢測的所述偽素數。

較佳的，所述步驟S2還包括：

步驟S21，使用偶數排除法排除所述偽素數中的偶數。

較佳的，所述步驟S3包括：

步驟S31，通過p＝a×2i+1(1＜i＜1000)，求p，并且采用Miller-Rabin算法來檢測p的素性，如果通過，則執行步驟S32，否則，i＝i+1，繼續執行步驟S31；

步驟S32，通過q×2j＝p+1(1＜j＜1000)，求q，并且采用Miller-Rabin算法來檢測q的素性，如果通過，則p為安全的大素數，否則，j＝j+1，繼續執行步驟S32；

其中，a表示預處理后的所述偽素數。

較佳的，還包括：

步驟S4，使用Pocklington定理對所述大素數進行驗證。

較佳的，所述步驟S4包括：

步驟S41，對p-1進行分解，使得

步驟S42，對F進行分解，使得