基于Ｓｍａｒｔｐｈｏｎｅ的服務器輔助ＲＳＡ密鑰生成
2009-01-01 00:00:00羅啟漢曹天杰何濤
計算機應用研究 2009年5期
（1．中國礦業大學 計算機科學與技術學院 江蘇 徐州 221116； 2．東南大學 移動通信國家重點實驗室 南京 210096）
摘 要：基于Cao等人最近提出的一個能抵抗合謀攻擊的服務器輔助RSA密鑰生成協議，利用.NET Compact Framework平臺上的Windows Mobile Smartphone對該協議進行了實現。對協議實現的方案、通信中的數據傳輸以及關鍵算法的選擇與優化等進行了闡述。考慮了程序的復用性、可維護性、執行效率以及協議運行的可靠性，并且在服務器端采用了多線程處理機制來輔助多個客戶端計算。
關鍵詞：合謀攻擊; 服務器輔助計算; 智能手機; 多線程
中圖分類號：TP309文獻標志碼：A
文章編號：1001-3695(2009)05-1929-03
Server-aided RSA key generation based on Smartphone
LUO Qi-han1 CAO Tian-jie1，2 HE Tao1
(1．School of Computer Science Technology China University of Mining Technology Xuzhou Jiangsu 221116 China; 2. National Mobile Communications Research Laboratory Southeast University Nanjing 210096 China)
Abstract:Based on Cao et al.’s improved server-aided standard RSA key generation protocol implemented it based on Windows Mobile Smartphone which was in the .NET Compact Framework. This paper specified the scheme of implementation data transporting of communications and selecting and optimization of key algorithms. Many factors were also considered intensively such as the reusage maintainability execution efficiency and the reliability of protocol running. In addition also adopted the multithreading coping mechanism to assist several clients computing.
Key words：collusion attack; server-aided computation; Smartphone; multithreading
近年來，基于個人數字助理、智能卡、掌上領航員以及手機等掌上設備的應用越來越廣泛。掌上設備具有便攜性、可計算性、可存儲性和數據保護等特性，其應用領域不斷拓寬。然而，由于多數掌上設備只擁有有限的計算資源，使得它們不足以完成許多諸如密碼計算等復雜運算。利用外部服務器進行輔助計算是一個可行的方法，但網絡的開放性和外部資源的不可信使得如何在輔助計算中保證掌上設備的安全成為設計輔助計算協議的難題。
在2000年，為了解決掌上設備產生RSA密鑰的速度過慢問題，Modadugu等人[1]提出了通過讓掌上設備和不受信任的外部服務器通信，用外部服務器來輔助生成RSA密鑰的服務器輔助計算協議。文獻中[1]給出了利用單個服務器和雙服務器輔助掌上設備的標準RSA密鑰生成協議和非平衡RSA密鑰生成協議，保證了用戶私鑰的安全，加快了RSA密鑰生成的速度。需要指出的是，Modadugu等人的協議安全前提是兩個不可信服務器不能共享信息，否則服務器可利用共享的信息推導出掌上機用戶的私鑰，即該協議不能抵抗合謀攻擊。為抵抗合謀攻擊，Chen等人[2]提出了針對Modadugu等人協議的兩個修正方案。但Chen等人的協議存在安全缺陷，無論是標準RSA密鑰生成協議還是非平衡RSA密鑰生成協議，并不像他們認為的那樣能夠抵抗服務器的合謀攻擊。在文獻[3，4] 中，Cao等人給出了對修正方案的合謀攻擊方法，文獻[5]中Kong等人給出了另一種攻擊。
在ITST 2006上，Chen等人[6]為改進已有的安全缺陷，提出了兩個新的服務器輔助RSA密鑰產生協議來對抗服務器合謀攻擊。但是這兩個新的服務器輔助RSA密鑰生成協議也沒有達到宣稱的安全性。文獻[7]給出了合謀攻擊過程，同時提出了一個能抵抗合謀攻擊的服務器輔助RSA密鑰生成協議。本文的主要貢獻是利用.NET Compact Framework平臺上的Windows Mobile Smartphone實現了文獻[7]中給出的協議。
1 一個改進的服務器輔助RSA密鑰生成協議
文獻[1]中指出了一個問題：在服務器輔助標準RSA密鑰生成協議中，存在一個二次減速的問題，即由于在標準RSA密鑰生成協議中，p和q必須同時為素數，生成一個RSA模數所需要的通信輪數將大大增加，產生的時間消耗明顯超過了在每個通信過程中減少的時間。文獻[7]中提出了一個基于多服務器的輔助生成標準RSA密鑰的改進協議，這個協議既能抵抗服務器合謀攻擊，又能解決二次減速問題。協議具體運行過程如下：
a)掌上設備產生兩個512 bit的候選參數p和q，滿足條件p=q=(3 mod 4)，并保證p和q沒有小的素因子。
f)掌上設備驗證X1≡ga (mod p)和X2≡gb (mod q)是否成立。如果其中一個成立，則相應的候選參數為可能的素數。重復過程a)~f)直到得到兩個素數；然后，掌上設備用一個小梅森數在本地運行概率素性檢測程序作進一步檢查；最后將兩個素數的乘積作為RSA模數。
在步驟f)中，如果協議第一次運行產生一個素數，第二次運行產生兩個素數，那么可以使用這三個素數中的任意兩個。很明顯，協議可以擴展到多服務器輔助模型，而且同樣也適用于單服務器輔助計算的情形。由于協議不要求p和q同時為素數，不存在二次減速問題。在協議的安全性方面，盡管在輔助計算的過程中產生了許多候選參數p和q，但服務器并沒有得到關于p和q的任何有用信息。即使服務器發起合謀攻擊，通過共享獲得了個截獲掌上設備和服務器之間所有通信的惡意攻擊者來說，他要成功攻破協議的難度與服務器通過合謀攻擊手段來攻擊協議的難度是一樣的。
2 協議的實現
本協議采用C/S模式來實現，客戶端使用VS .NET Compact Framework下智能設備開發中的Windows Mobile Smart-phone實現平臺，服務器則利用Windows窗體應用程序進行設計，界面如圖1所示。
在協議的實現中，主要解決的問題有三方面：a)實現方案的選擇；b)在C/S通信方面保證協議的可靠性；c)編程實現中關鍵算法的選擇與優化。
2.1 分層實現方案
由于協議的整個過程是基于大數運算的，首先需要實現底層大數類的定義以及協議中涉及到的大數運算。協議實現采用的是基于.NET分層實現的方案。
在Smartphone端底層分別建立一個產生隨機大數的類庫GetRandomCBigInt和大數類庫CBigInt，這些類庫都是基于Windows Mobile 5.0 Smartphone平臺的。利用類庫GetRandomCBigInt中的函數隨機產生協議中所需的參數，其中包括160位的a和b，512位的k和l，以及素數的512位隨機測試數。大數類庫CBigInt提供大數類的定義，同時協議中用到的大數四則算術運算、大數比較運算、大數模冪運算、大數求公因子以及大數與字符串之間轉換運算也都在大數類庫中實現。Smart-phone端協議的執行在上層UI界面的程序設計中實現。
根據協議，服務器端需要輔助Smartphone端進行大數的模冪運算。因此在服務器端需要建立基于服務器端底層的大數類庫CBigInt。同樣服務器端協議的執行也是在上層UI界面的程序設計中實現的。
這種分層的實現方案，一方面對于任何層上的程序修改都很方便，因為各個層都在同一個工程中；另一方面，分層實現也使得開發過程與協議的執行流程清晰。因為在實現協議的代碼中只需調用底層封裝好的類庫函數，程序的可維護性得到了保證。由于底層的類庫程序代碼是基于標準C++的，具有較強的復用性。
2.2 Smartphone/服務器間的通信
在協議實現中，客戶端與服務器之間的通信是基于TCP/IP協議簇實現的，現在考慮從客戶端和服務器端提高協議運行的可靠性。由于Smartphone本身的資源限制，在實現Smart-phone與服務器通信時，采用了通信負載較小的TcpListener 和TcpClient類[8]。另一方面，在服務器端為了能夠響應多個客戶端的請求，采用了多線程處理機制。一旦有一個客戶端請求連接就創建一個子線程負責處理客戶的輔助計算請求。服務器端線程的層次關系如圖2所示。
現在考慮從通信中提高協議運行的可靠性。對于網絡中Smartphone與服務器之間的通信，重要的問題是要確保數據接收方能準確地從接收的包中提取數據。解決方案是：首先將需要傳輸的數據預先存儲到buf[]中，因為傳送的不只是字符而是大數，為了對方能準確地提取buf[]中的數據，對buf[]設定了一定的格式，如圖3所示。其中數據頭部存儲了數據單元的長度。這樣接收者就可以根據數據單元的長度獲取相應數據了。由于傳輸的是數，在區別數據頭與內容時采用了添加冗余特殊字符的方式。
2.3 大數的存儲與運算
由于本協議中生成的RSA模數是1 024 bit，需要解決大數的存儲及各種運算的實現問題。
對于大數的存儲，一個有效的方法是將大數表示為一個進制盡可能大的數組，對于目前的32位系統而言，進制的大小可以取值為2 的32次方，即每一位的取值是0~0xffffffff，本文用一個無符號長整數來表示這一數值。所以1 024位的大數就是一個有32個元素的unsigned long數組，針對該數組進行各種運算所需的循環規模至多32次。
由于大數的模冪、比較、求公因子以及模逆運算等都是基于大數的四則算術運算的，提高大數四則算術運算的效率是非常重要的。在本文的大數類中，對于大數的加、減、乘、除及模運算都是結合了移位運算來實現的，在程序測試中可以明顯看到這種實現方式比一般的豎式運算要快。
另一方面，為了上層調用大數的各種操作方便直觀，在程序實現時對大數的四則運算及比較運算都進行了運算符重載，這樣在上層程序開發時對大數的操作就與對一般整型數操作一樣了。
2.4 獲取隨機候選測試大數
協議每次運行得到的素數都必須是隨機的，而產生兩個隨機素數一般需要進行若干次的客戶/服務器交互，因此在協議實現中不能每次都在Smartphone端產生一個滿足無小素數因子且模4余3的隨機測試大數，這樣協議的運行效率會降低。為了解決這個問題，算法采用了Eratosthenes篩選法來同時獲取多個隨機測試大數供協議運行產生素數。下面對此算法進行描述。
首先利用隨機大數產生類中的函數產生一個512位的隨機大數（用十六進制表示），然后在其最低位賦值為3、7、B或F之一得到模4余3的起點大數start，接下來就是利用這個數來產生多個隨機候選測試大數。
假設要產生m個隨機候選測試大數，這m個隨機候選測試大數在start~start+1 000的范圍內搜索得到。那么讓start對素數表中的小素數因子prime求模，得到當前prime在候選測試大數搜索范圍內的最小倍數在b[]中的對應位置，將其剔除后，即設置相應的b[]=0。這樣不斷地后移prime個位置，將這個小素數因子prime在搜索范圍內的所有倍數全部剔除。在完成對所有小素數因子的類似操作后，它們的倍數在搜索范圍內的位置b[i]被全部標記為0，其余滿足無小素數因子的則標記為1。
算法接下來就是要從這些無小素數因子的大數中找出m個模4余3的大數。顯然只要滿足條件b[j]=1且j mod 4=0，則start+j就是所需要的隨機候選測試大數。由于每次的start是隨機產生的，每次根據start產生的候選測試大數也是隨機的。
下面是一次找尋15個隨機候選測試大數算法的具體程序實現：
while (true)
{UInt32 i;
for (i = 0; i < S; i++)b[i] = 1;
for (i = 0; i < 500; i++)//start對500個小素數進行求模
{p = PrimeTable1[i];//從素數表獲取素數
CBigInt res = start % p;// CBigInt是大數類型自定義關鍵字
UInt32 r = res.m_ulValue[0];//r獲取模小素數的值
if (r > 0)r = p - r;
while (r < S)//對當前小素數在搜索范圍內剔除其倍數
{ b[r] = 0;r += p; }
}
for (i = 0; i < S; i++)
{if (b[i] > 0 i % 4 == 0)
//尋找滿足協議的隨機候選測試大數
{j++; // pTable[]是大數數組
pTable[j]=start;//在pTable[j]中保存隨機候選測試大數
}
if (j == 15) break;start = (UInt32)1 + start;
}
break;
}
2.5 Montgomery模冪算法
模冪算法效率的高低對Smartphone和服務器的計算效率起著決定性的作用，而提高乘模運算的速度又是提高模冪運算速度的關鍵。一般情況下，模數n是數百位乃至千位以上的二進制整數，用普通的除法求模而進行乘模運算是不能滿足效率要求的。為此，Montgomery提出了一種模加右移的乘模算法。Montgomery算法簡述如下：
首先選擇與模數n互素的基數R= 2k，n滿足2k-1≤n≤2k，注意n應為奇數，并且選擇R-1及n′，滿足0 M(m) {μ=(m mod R)n′ mod R;0≤μ≤R; t=(m+μn)/R; if (t≥n)return (t-n); else return t; } 因為μn≡ mnn′≡ -m mod R，故t為整數；同時tR≡m mod n，得t≡mR-1 mod n。由于0≤m+μn≤Rn+μR，M(m) 中t結果范圍是0≤t<2n，返回時如果t不小于n，應返回t-n。當然如果要求ab mod n，可令m=ab；然后利用Montgomery算法求出t=m R-1 mod n；最后再計算m′=tR mod n，那么得到的m′即是所需的結果。 將上述乘模算法結合快速模冪算法，構成標準Montgomery模冪算法，在快速模冪算法中對二進制指數各位0和1的判斷均采用移位運算實現。這樣實現的模冪算法運算速度比一般的模冪算法明顯要快。經測試，對于服務器端指數和模數均為1 024 bit的模冪運算，采用一般平方乘模算法需要2 s左右的時間，而采用Montgomery模冪算法僅需要不到1 s的時間。 3 結束語 本文在提出的服務器輔助RSA密鑰生成改進協議的基礎之上，利用.NET Compact Framework平臺上的Windows Mobile Smartphone對此協議進行了實現。結果顯示，利用服務器輔助計算能夠在保證掌上設備數據安全的基礎上有效地進行復雜計算。 參考文獻： ［1］ MODADUGU N BONEH D KIM M. Generating RSA keys on a handheld using an untrusted server[C]// Proc of Cryptographer’s Track RSA Conference.Berlin:Springer 2000:271-282. [2]CHEN Y SAFAVI-NAINI R BAEK J. Server-aided RSA key generation against collusion attack[C]// Proc of Secure Mobile Ad hoc Networks and Sensors Workshop (MADNES 2005).Berlin:Springer 2006: 27-37. [3]CAO Tian-jie MAO Xian -ping，LIN Dong-dai. Security analysis of a server-aided RSA key generation protocol[C]// Proc of the 2nd Information Security Practice and Experience Conference (ISPEC 2006). 2006: 314-320. [4]CAO Tian-jie，MAO Xian-ping. Collusion attack on a server-aided unbalanced RSA key generation protocol[C]// Proc of International Conference on Communication Technology (ICCT 2006). 2006: 183-185. [5]KONG Fan-yu，YU Jia，QIN Bao-dong，et al. Cryptanalysis of server-aided RSA key generation protocols at MADNES 2005[C]// Proc of ATC 2007 LNCS vol 4610. 2007:52-60. [6]CHEN Yun，CHEN Wei-jian，XIN Yi-mu，et al. Server-aided public key generation protocols on low-power devices for Ad hoc networks[C]// Proc of the 6th International Conference on ITS Telecommunications (ITST2006).[S.l.]: IEEE Press 2006:710-714. [7]CAO Tian-jie，MAO Xian-ping，LUO Qi-han，et al. Security analysis of server-aided public key generation protocols on low-power devices for Ad hoc networks[C]// Proc of International Colloquium on Computing Communication Control and Management.2008:591-594. [8]YANG Bai-jian ZHENG Pei NI L M. Professional Microsoft smartphone programming[M].[S.l.]: Wrox Press 2007.
