[發明專利]采用中國剩余定理的RSA的計算方法及計算裝置

有效

• 申請號: 201310479234.4
• 申請日: 2013-10-14
• 公開（公告）號: CN103490885B
• 公開（公告）日: 2017-01-04
• 發明（設計）人: 裴超
• 申請（專利權）人: 北京華大信安科技有限公司
• 主分類號: H04L9/30
• 分類號: H04L9/30
• 代理公司: 北京弘權知識產權代理事務所(普通合伙)11363
• 代理人: 郭放,許偉群

技術領域

本發明涉及安全領域，特別涉及RSA（取名來自三位開發者的名字的首字母，三位開發者分別為Ron?Rivest、Adi?Shamirh和LenAdleman，簡稱RSA）的計算方法及計算裝置。

背景技術

RSA是信息安全領域中比較主流的公鑰密碼技術。基于RSA實現的各種物理設備，例如安全芯片及智能卡已經廣泛應用于金融、通信、社保、交通等各個領域。采用了中國剩余定理（Chinese?Remainder?Theorem，簡稱CRT）的RSA（采用了中國剩余定理的RSA以下簡稱CRT-RSA）的實現相對于傳統的RSA實現具有更高的性能優勢，尤其當采用并行設計時，這種優勢更高，因此CRT-RSA的應用更加廣泛。

涉及私鑰的CRT-RSA實現方法面臨多種側信道攻擊行為，這些攻擊行為的目的是在物理設備運行CRT-RSA運算時，通過對運行時間、溫度、功耗、電磁等外部因素的不同表現，分析獲取私鑰或私鑰的部分信息。常見的這類攻擊有簡單功耗分析攻擊（Simple?Power?Analysis，簡稱SPA）、差分功耗分析攻擊（Differential?Power?Analysis，簡稱DPA）、簡單電磁分析攻擊（Simple?Electromagnetic?Analysis，簡稱SEMA）、差分電磁分析攻擊（Differential?Electromagnetic?Analysis，簡稱DEMA）、時間攻擊（Timing?Attack）等。

現有技術中，針對上述攻擊方法已提出多種CRT-RSA的實現方式，以增加CRT-RSA運算的安全性。這些實現方式大致分為兩種，一是規則化算法的操作或執行流程，如模乘取代模平方的操作、增加虛擬運算的計算流程；或采用其他方法能夠導致模冪的實現流程，不依賴于數據，每次執行的操作大體是一致的，如此可以抵抗如SPA之類的簡單分析攻擊；二是隨機化運算數據，如使用隨機數據掩蓋模冪運算中的冪指數、底數，甚至包括隨機化數據的存儲單元，如此可以抵抗如DPA之類的差分分析攻擊。

但上述實現方式中，對于如何實施一個完整的CRT-RSA的運算沒有給出具體方案；同時在模冪運算過程中，采用什么樣的隨機數，如何求解隨機數逆元，采用什么樣的隨機數對數據進行隨機化處理和脫掩處理都沒有給出完備的說明。可見，現有的實現方式無法提高CRT-RSA的安全性能。

發明內容

本發明實施例中提供了一種采用中國剩余定理的RSA的計算方法及計算裝置，可以提高采用中國剩余定理的RSA的安全性能。

為了解決上述技術問題，本發明實施例公開了如下技術方案：

一方面，提供了一種采用中國剩余定理的RSA的實現方法，所述方法包括：

產生第一隨機數γ，所述第一隨機數的比特長度小于或等于RSA的模數N的比特長度的二分之一；

使用中國剩余定理計算所述第一隨機數的逆元γ^-1mod?N，其中γ^-1=γ^φ(N)-1mod?N,φ（N）=(p-1)*(q-1)，N=p*q，p和q為素數，且(p,q,p-2,q-2,qInv)為采用中國剩余定理的RSA的私鑰五元組，qInv=q^-1mod?p。

結合第一方面，在第一方面的第一種可能實現方式中，所述方法還包括：

計算所述第一隨機數γ的公鑰指數次冪R=γ^emod?N或所述第一隨機數的逆元γ^-1mod?N的公鑰指數次冪R=γ^-emod?N；

使用R=γ^emod?N或R=γ^-emod?N對模冪運算C^dmod?N的底數C進行隨機化處理。

結合第一方面的第一種可能實現方式，還提供了第一方面的第二種可能實現方式，使用R=γ^emod?N或R=γ^-emod?N對模冪運算C^dmod?N的底數C進行隨機化處理具體包括：

用C'=C×R?mod?N替代C，并計算M'=(C')^dmod?N。

結合第一方面的第二種可能實現方式，還提供了第一方面的第三種可能實現方式，所述方法還包括：