模指數外包方案ExpSOS 的格基密碼分析

鄭云海，田呈亮,2+

1.青島大學 計算機科學技術學院，山東 青島266071

2.中國科學院 信息工程研究所 信息安全國家重點實驗室，北京100093

模指數運算又稱模冪運算，其作為一種基本運算廣泛應用于RSA 密碼體制和DSA（digital signature algorithm）的簽名算法中。通常地，指數長比特時大約需要執行1.5次模乘操作，這對于計算資源有限的本地設備來說代價十分昂貴。因此，研究模指數的安全外包具有重要的理論與現實意義。根據方案所基于的安全模型，現有的外包方案可分為兩類：基于雙服務器的外包方案和基于單服務器的外包方案。

在文獻[14]中，Zhou 等提出了一種基于單個服務器的模指數外包方案ExpSOS，旨在安全高效地實現本地端模指數的計算。文中證明了其方案能保護本地端底數、指數和模數的機密性，并能以高概率檢測出服務器端的惡意行為。最近，在文獻[13]中，Rangasamy 等模仿Chevalier 等的攻擊，對ExpSOS進行了簡略的安全分析，他們的攻擊假設用戶調用了兩次外包算法且要求兩次外包的模指數運算的指數相同，這樣的攻擊條件是十分嚴格的。本文對ExpSOS 進行了更全面的評估。具體來說，本文的貢獻可以概括如下：

（1）對方案進行了唯密文分析，指出了方案潛在的弱密鑰。通過將方案弱密鑰的求解轉化為模線性多項式的小整數解問題，調用Coppersmith 的格基構造求解算法，僅利用密文就可以在多項式時間內恢復方案中的多個私有參數。

（2）為避免弱密鑰攻擊，詳細估計了安全應用場景下底數和方案中安全參數選取的規模。

（3）實驗給出了數字簽名標準推薦參數下Exp-SOS 方案的弱密鑰攻擊實例，驗證了理論分析的正確性。

1 預備知識

1.1 常用符號及其含義

一般地，本文用小寫加粗字母表示列向量。表1列出了文中常用的專用符號及數學函數。

表1 符號說明Table 1 Symbol description

1.2 格與相關不變量

作為一種經典的數學對象，格在解決計算機科學中的許多計算問題，特別是在密碼學領域發揮著重要的作用。

（格）有個線性無關的維向量…b∈R，由{…b}張成的格L定義為：

（Minkowski 定理）設L為秩為的格，存在非零向量使得：

1982 年，著名的LLL 算法提出，它可以在多項式時間內找到格L的一個由“短”向量組成的約化基，其具有以下性質：

設L 為秩為的格，在多項式時間內，LLL 算法可以輸出一系列約化基向量v,1 ≤≤,滿足：

1.3 多項式范數

1.4 Howgrave-Graham 定理

（Howgrave-Graham 定理）設(,,…,x)∈Z[,,…,x]為包含個單項式的整系數多項式，若：

2 Zhou 等ExpSOS 方案的回顧

最近，Zhou 等提出了一種底數、指數和模數均可變的外包方案ExpSOS以計算umod。在ExpSOS中，模數的隱私性基于大整數分解的困難問題，底數使用環擴張技術隱藏，指數通過歐拉定理隱藏。即給定3 個大整數、、，它們的兩方算法過程如下所示：

3 對方案ExpSOS 的弱密鑰分析與改進

本章將給出Zhou 等外包方案ExpSOS 中潛在的安全威脅。確切地說，對此方案在使用不同參數的場景下進行了唯密文攻擊，并對安全參數的規模給出了具體的估計。攻擊中使用的主要技術是Herrmann和May的格基的求解模線性方程的小整數解的方法。

3.1 Herrmann&May 方法

設＞0，是一個足夠大的合數且有因數使＞L。設(,,…,x)∈Z[,,…,x]為有個變量的線性多項式。若滿足：

根據Herrmann 和May的分析，可以通過以下步驟將(,,…,x)的小整數解問題轉化為尋找格中短向量問題：

（1）通過乘上a-mod將方程(,,…,x)轉化為首一多項式(,,…,x)。

（2）構造多項式集合：

（4）通過求解由h(,,…,x)組成的線性系統可以找到(,,…,x)=0 mod的小整數解，其中h(,,…,x)（1 ≤≤）是代數無關的。

3.2 對ExpSOS 的攻擊及對策

本節對方案中底數與指數的隱私性進行分析。基于方程（2）～（4），根據定理4，它們的隱私性可以轉化為模多項式方程的小整數解問題。通過分析，指出了方案潛在的弱密鑰，并給出了方案適用的底數的大小以及方案邏輯拆分中參數的安全取值范圍。設ExpSOS 方案中各參數的上界表示如表2 所示。在模指數運算最常見的兩個應用場景（RSA與數字簽名標準（digital signature standard，DSS））中，模數分別為兩個大素數的乘積與一個大素數。本文的分析基于上述兩種情景，分別對為大素數和兩個大素數乘積兩種情況進行分析。

表2 變量上界Table 2 Upper-bounds of variables

3.2.1 為素數時

（1）底數的隱私性分析

根據等式（4），有：

3.2.2 為合數時

基于3.2.1 小節與3.2.2 小節安全性分析結果，為避免本文提出的弱密鑰攻擊，表3 詳細總結了不同場景下方案安全參數的選取范圍。

表3 安全參數的選取范圍Table 3 Selection range of security parameters

4 攻擊實例

本章以對方案ExpSOS 的分析為例給出了攻擊實例。在本文的例子中使用的所有參數均參考NIST的數字簽名標準以及RSA 算法標準。實驗使用Wolfram Mathematica 11.3 完成，運行環境為Windows 10，Intel Corei5-6500 3.2 GHz，8 GB RAM。攻擊實驗結果如表4 和表5 所示。

表4 N 為素數時的實驗參數及結果Table 4 Experimental parameters and results while N is prime

表4 （續）

表5 N 為合數時的實驗參數及結果Table 5 Experimental parameters and results while N is composite

首先描述為素數的攻擊實例。取模數為3 072 位的大素數，基數為1 024 位整數，指數為256 位整數。在對ExpSOS 進行仿真之后，表4 列出了云服務器擁有的參數及攻擊結果。由于對其他方程的攻擊具有極高的時間和空間復雜度，這里只給出基于方程（4）和方程（2）的底數以及指數的恢復攻擊實例。根據對等式（4）的分析過程以及實驗硬件設備性能，為了平衡空間復雜度和攻擊的時間復雜度，取=0.05，計算可得=15，=7，=16，構造對應多項式的系數矩陣，通過攻擊可以恢復底數如表4 所示。該攻擊實例敵手約化格基的時間成本小于2 min，求解方程組的時間小于0.1 s，總時間合計不超過2 min。

根據對等式（2）的分析以及實驗硬件設備性能，為了平衡空間復雜度和攻擊的時間復雜度，取=0.2，得=8,=2,=45,構造對應多項式的系數矩陣，通過分析可得如下含有(,)兩個未知數的線性多項式，且總能找到所需的根：

該攻擊實例敵手約化格基的時間成本小于2 min，求解方程組的時間小于0.1 s，總時間合計不超過2 min。

下面給出為合數時的一個攻擊實例。表5 列出了使用的參數及結果。同樣由于復雜度的問題，只給出底數的恢復攻擊。分別取兩個1 536 位的大素數、′，生成模數=′，選擇基數為2 048位。對ExpSOS 進行仿真之后，根據對等式（4）的分析過程以及實驗硬件設備性能，為了平衡空間復雜度和攻擊的時間復雜度，取=0.05，有=24，=16，=25，構造對應多項式的系數矩陣，通過攻擊可以恢復底數如表5 所示。

該實例中敵手約化格基的時間成本小于15 min，求解方程組的時間小于1 s，總時間合計不超過15 min。

5 結論

本文對Zhou 等在IEEE TIFS 2017 提出的模指數外包方案ExpSOS 的安全性進行了全面的分析。通過格基約化技術對其方案進行攻擊，并對其中的參數選擇提出了建議以抵抗這種攻擊。