RSA加密算法目前的應(yīng)用相當?shù)膹V泛，那么我們今天就來看看RSA加密算法在撲克游戲中是如何應(yīng)用的。

一、采用公開密鑰密碼的拋幣協(xié)議

這個協(xié)議既可與公開密鑰密碼又可與對稱密碼一起工作，其唯一要求是算法滿足交換律，即：一般地，對稱加密算法中這個特性并不滿足，但對某些公開密鑰算法是正確的。協(xié)議如下：

1）A和B都產(chǎn)生一個公開/私鑰密鑰對。

2）A產(chǎn)生兩個消息，其一指示正面，另一個指示反面。這些消息中包含有某個唯一的隨機串，以便以后能夠驗證其在協(xié)議中的真實性.A用公開密鑰將兩個消息加密，并以隨機的順序把消息發(fā)給B，即:EA（M1），EA（M2）。

3）B由于不能讀懂其中任意一消息，就隨機地選擇一個。用公開密鑰加密并回送給A，即：EB（EA（M））。M是M1或M2。

4）A由于不能讀懂送回的消息，就用私鑰解密并回送給B，即：

DA（EB（EA（M）））=EB（M1）當M=M1時;或結(jié)果為EB（M2）當M=M2時。

5）B用私鑰解密消息，得到拋幣結(jié)果。并將解密后的消息送給A，即:DB（EB（M1））=M1或DB（EB（M2））=M2。

6）A讀拋幣結(jié)果，并驗證隨機串的正確性。

7）A和B出示各自的密鑰對以便雙方能驗證對方?jīng)]有欺詐。

二、RSA加密算法在撲克游戲中的應(yīng)用

由公平硬幣拋擲到撲克游戲?qū)⒁鉀Q的問題是：

1）消息不再是兩個，而是N個，我們可以用一個數(shù)組來解決這個問題。

2）實現(xiàn)公平硬幣拋擲的方法很多，但應(yīng)用到本模型，用公開密鑰密碼的拋幣協(xié)議是較好的選擇。

3）該模型使用的RSA加密解密算法以及所涉及到的隨機數(shù)和強素數(shù)等問題。

4）雙方的游戲需要進行的通訊。

1、RSA加密算法

RSA（rivestshamiradlemen）是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，它易于操作。其加密解密過程如圖1。

（1）RSA加密算法原理

RSA是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，RSA的安全性依賴于大數(shù)分解。公鑰和私鑰都是兩個大素數(shù)（大于100個十進制位）的函數(shù)，從一個密鑰和密文推斷出明文的難度等同于分解兩個大素數(shù)的積。密鑰對的產(chǎn)生是選擇兩個大素數(shù)p和q。計算:n=p*q然后隨機選擇加密密鑰e，要求e和（p-1）*（q-1）互質(zhì)。最后，計算解密密鑰d，滿足：

e*d=1mod（（p-1）*（q-1））

其中n和d也要互質(zhì).數(shù)e和n是公鑰，d是私鑰.兩個素數(shù)p和q不再需要，應(yīng)該丟棄。

當加密信息為m（二進制表示）時，首先把m分成等長數(shù)據(jù)塊m1，m2...mi，塊長s，其中s[n]，s要盡可能的大。對應(yīng)的密文是：

ci=mie（modn） （a）式

解密時作如下計算:

mi=cid（modn） （b）式

RSA可用于數(shù)字簽名，方案是用（a）式簽名，（b）式驗證。

（2）RSA加密算法的安全性

RSA的安全性依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，即沒有證明破解RSA就一定需要作大數(shù)分解。假設(shè)存在一種無須分解大數(shù)的算法，也可以修改成大數(shù)分解算法。目前，RSA的一些變種算法已被證明等價于大數(shù)分解。其中，分解n是最常見的方法。現(xiàn)在，人們已能分解多個十進制位的大素數(shù)。

（3）RSA加密算法注意問題

參數(shù)選取原則:p與q之差要大。若p與q之差很小，則可由n=p*q估計（p+q）/2=n12，則由（（p+q）/2）2-n=（（p-q）/2）2式右邊為小的平方數(shù)試驗給出p，q的值。

e的選取原則：

（e，y（n））=1的條件易于滿足，其中y=（（x*e）modn），由于兩個隨機數(shù)為互素的概率約為3/5，建議采用e=3，但e太小存在一些問題。當x*e<n，則未取模，由y直接開e次方可求x。

d的選取原則：

e選定后可用Euclidean算法在多項式時間內(nèi)求出d。d要大于n/4.d若小，則簽字和解密運算快，這在IC卡中尤為重要（復(fù)雜的加密和驗證簽字可由主機來做）。類似于加密下的情況，d不能太小，否則由已知明文攻擊，構(gòu)造（迭代地做）y=（（x*e）modn），再猜測d值，做（（x*d）modn），直到試湊出d值即可。對小d的系統(tǒng)攻擊法，證明了當d長度小于n的1/4時，由連分式算法，可在多項式時間內(nèi)求出d值。

不可用公共模：

一個網(wǎng)，由一個密鑰產(chǎn)生中心（KGC）采用一個公共模，分發(fā)多對密鑰，并公布相應(yīng)公鑰e，這會使密鑰管理簡化，存儲空間小，且無重新分組（Reblocking）問題，但在安全上會帶來問題。

2、隨機數(shù)

智力撲克游戲中當產(chǎn)生每個牌的位置時要用到隨機數(shù)，并且隨機數(shù)在實現(xiàn)RSA時也很重要。最好的計算機能產(chǎn)生的是偽隨機序列產(chǎn)生器，密碼的應(yīng)用比其他大多數(shù)應(yīng)用對偽隨機序列的要求更嚴格。密碼學(xué)的隨機性并不僅僅意味著統(tǒng)計的隨機性，密碼學(xué)意義上安全的偽隨機數(shù)，還必須具有下面的性質(zhì)：它是不可預(yù)測的，即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的比特流的全部知識，也不可能通過計算來預(yù)測下一個隨機比特應(yīng)是什么。

3、素數(shù)

計算隨機數(shù)時要涉及到素數(shù)，Miller-Rabin算法是應(yīng)用最廣泛的測試強偽素數(shù)的算法。該算法的理論基于以下事實:令n-1=2sr，其中r是奇數(shù)。任取一個a，使得a/n<1，那么r滿足ar=1（modn）或存在某個j，其中0<j<s-1，有a2jr=-1（modn）。

Miller-Rabin算法:

輸入:奇整數(shù)n;

輸出:n是素數(shù)（合數(shù)）。

步驟:

1）令n-1=2s*m，其中m是奇數(shù)。

2）選擇一個隨機整數(shù)a，1<a<n-1。

3）計算b=am（modn）。

4）如果b=1（modn）則n是素數(shù)，停止。

5）for（i=0to（s-1））do，如果b=-1（modn）則n是素數(shù)，停止，否則計算b=b2（modn）n是合數(shù)。

如果n是兩個素數(shù)p和q之積，那么p和q采用強素數(shù)將更可取。強素數(shù)是滿足某些特性的素數(shù)，使得用某些特殊的因子分解方式對它的乘積n進行分解很困難。特性如下：p-1和q-1的最大公因子應(yīng)該較小;p-1和q-1都應(yīng)有大的素因子，分別記為pc和qc；pc-1和qc-1都應(yīng)有大的素因子；p+1和q+1都應(yīng)有大的素因子;（p-1）/2和（q-1）/2都應(yīng)是素數(shù)。使用強素數(shù)的優(yōu)點是一個素數(shù)的長度比它的結(jié)構(gòu)更重要。

4、通信

完成智力撲克游戲還要完成消息的傳遞。WinSock提供了對TCP（傳輸控制協(xié)議）的支持，通過TCP協(xié)議我們可以與指定IP地址的主機建立連接，同時利用建立的連接可以雙向的交換數(shù)據(jù)。雙方函數(shù)調(diào)用的客戶端代碼如下:

BOOLCMyclientDlg：：OnInitDialog（）

{
CDialog：：OnInitDialog（）；

//創(chuàng)建本地套接口m-sockRecv.Create（）；

//發(fā)起連接請求

BOOLfC=m-sockRecv.Connect（/20211981281990，6802）；

TRACE（/connectis%s\n0，（fC）?/OK0:/Error0）；

//啟動定時器，定時接收數(shù)據(jù)SetTimer（1，3000，NULL）；

，

}

voidCMy63-s1-clientDlg::OnTimer（UINTnIDE-vent）

{

charszRecv[20]，m-szRecv[20]；

//接收TCP數(shù)據(jù)

intiRecv=m-sockRecv.Receive（szRecv，10，0）；

TRACE（/received%dbyte\n0，iRecv）；if（iRecv>=0）

{

szRecv[iRecv]=-\0；

m-szRecv=szRecv；

UpdateData（FALSE）；

}

，

}

本文闡述了游撲克戲中用到隨機數(shù)時偽隨機序列的產(chǎn)生和涉及到的素數(shù)，提出Miller-Rabin加密算法是較好的測試強偽素數(shù)的算法。相信通過不斷地總結(jié)會更加完善游戲的機制。

admin

收藏 海報分享