模指數(shù)外包方案ExpSOS 的格基密碼分析

鄭云海，田呈亮,2+

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

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

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

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

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

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

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

1 預備知識

1.1 常用符號及其含義

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

表1 符號說明Table 1 Symbol description

1.2 格與相關(guān)不變量

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

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

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

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

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

1.3 多項式范數(shù)

1.4 Howgrave-Graham 定理

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

2 Zhou 等ExpSOS 方案的回顧

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

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

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

3.1 Herrmann&May 方法

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

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

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

（2）構(gòu)造多項式集合：

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

3.2 對ExpSOS 的攻擊及對策

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

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

3.2.1 為素數(shù)時

（1）底數(shù)的隱私性分析

根據(jù)等式（4），有：

3.2.2 為合數(shù)時

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

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

4 攻擊實例

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

表4 N 為素數(shù)時的實驗參數(shù)及結(jié)果Table 4 Experimental parameters and results while N is prime

表4 （續(xù)）

表5 N 為合數(shù)時的實驗參數(shù)及結(jié)果Table 5 Experimental parameters and results while N is composite

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

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

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

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

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

5 結(jié)論

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