RSA加密算法在扑克游戏中的应用

RSA加密算法目前的应用相当的广泛，那么我们今天就来看看RSA加密算法在扑克游戏中是如何应用的。

一、采用公开密钥密码的抛币协议

这个协议既可与公开密钥密码又可与对称密码一起工作，其唯一要求是算法满足交换律，即：一般地，对称加密算法中这个特性并不满足，但对某些公开密钥算法是正确的。协议如下：

1）A和B都产生一个公开/私钥密钥对。

2）A产生两个消息，其一指示正面，另一个指示反面。这些消息中包含有某个唯一的随机串，以便以后能够验证其在协议中的真实性.A用公开密钥将两个消息加密，并以随机的顺序把消息发给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时;或结果为EB（M2）当M=M2时。

5）B用私钥解密消息，得到抛币结果。并将解密后的消息送给A，即:DB（EB（M1））=M1或DB（EB（M2））=M2。

6）A读抛币结果，并验证随机串的正确性。

7）A和B出示各自的密钥对以便双方能验证对方没有欺诈。

二、RSA加密算法在扑克游戏中的应用

由公平硬币抛掷到扑克游戏将要解决的问题是：

1）消息不再是两个，而是N个，我们可以用一个数组来解决这个问题。

2）实现公平硬币抛掷的方法很多，但应用到本模型，用公开密钥密码的抛币协议是较好的选择。

3）该模型使用的RSA加密解密算法以及所涉及到的随机数和强素数等问题。

4）双方的游戏需要进行的通讯。

1、RSA加密算法

RSA（rivestshamiradlemen）是第一个既能用于数据加密也能用于数字签名的算法，它易于操作。其加密解密过程如图1。

（1）RSA加密算法原理

RSA是第一个既能用于数据加密也能用于数字签名的算法，RSA的安全性依赖于大数分解。公钥和私钥都是两个大素数（大于100个十进制位）的函数，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。密钥对的产生是选择两个大素数p和q。计算:n=p*q然后随机选择加密密钥e，要求e和（p-1）*（q-1）互质。最后，计算解密密钥d，满足：

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

其中n和d也要互质.数e和n是公钥，d是私钥.两个素数p和q不再需要，应该丢弃。

当加密信息为m（二进制表示）时，首先把m分成等长数据块m1，m2...mi，块长s，其中s[n]，s要尽可能的大。对应的密文是：

ci=mie（modn） （a）式

解密时作如下计算:

mi=cid（modn） （b）式

RSA可用于数字签名，方案是用（a）式签名，（b）式验证。

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

RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，即没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，也可以修改成大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。其中，分解n是最常见的方法。现在，人们已能分解多个十进制位的大素数。

（3）RSA加密算法注意问题

参数选取原则:p与q之差要大。若p与q之差很小，则可由n=p*q估计（p+q）/2=n12，则由（（p+q）/2）2-n=（（p-q）/2）2式右边为小的平方数试验给出p，q的值。

e的选取原则：

（e，y（n））=1的条件易于满足，其中y=（（x*e）modn），由于两个随机数为互素的概率约为3/5，建议采用e=3，但e太小存在一些问题。当x*e<n，则未取模，由y直接开e次方可求x。

d的选取原则：

e选定后可用Euclidean算法在多项式时间内求出d。d要大于n/4.d若小，则签字和解密运算快，这在IC卡中尤为重要（复杂的加密和验证签字可由主机来做）。类似于加密下的情况，d不能太小，否则由已知明文攻击，构造（迭代地做）y=（（x*e）modn），再猜测d值，做（（x*d）modn），直到试凑出d值即可。对小d的系统攻击法，证明了当d长度小于n的1/4时，由连分式算法，可在多项式时间内求出d值。

不可用公共模：

一个网，由一个密钥产生中心（KGC）采用一个公共模，分发多对密钥，并公布相应公钥e，这会使密钥管理简化，存储空间小，且无重新分组（Reblocking）问题，但在安全上会带来问题。

2、随机数

智力扑克游戏中当产生每个牌的位置时要用到随机数，并且随机数在实现RSA时也很重要。最好的计算机能产生的是伪随机序列产生器，密码的应用比其他大多数应用对伪随机序列的要求更严格。密码学的随机性并不仅仅意味着统计的随机性，密码学意义上安全的伪随机数，还必须具有下面的性质：它是不可预测的，即使给出产生序列的算法或硬件和所有以前产生的比特流的全部知识，也不可能通过计算来预测下一个随机比特应是什么。

3、素数

计算随机数时要涉及到素数，Miller-Rabin算法是应用最广泛的测试强伪素数的算法。该算法的理论基于以下事实:令n-1=2sr，其中r是奇数。任取一个a，使得a/n<1，那么r满足ar=1（modn）或存在某个j，其中0<j<s-1，有a2jr=-1（modn）。

Miller-Rabin算法:

输入:奇整数n;

输出:n是素数（合数）。

步骤:

1）令n-1=2s*m，其中m是奇数。

2）选择一个随机整数a，1<a<n-1。

3）计算b=am（modn）。

4）如果b=1（modn）则n是素数，停止。

5）for（i=0to（s-1））do，如果b=-1（modn）则n是素数，停止，否则计算b=b2（modn）n是合数。

如果n是两个素数p和q之积，那么p和q采用强素数将更可取。强素数是满足某些特性的素数，使得用某些特殊的因子分解方式对它的乘积n进行分解很困难。特性如下：p-1和q-1的最大公因子应该较小;p-1和q-1都应有大的素因子，分别记为pc和qc；pc-1和qc-1都应有大的素因子；p+1和q+1都应有大的素因子;（p-1）/2和（q-1）/2都应是素数。使用强素数的优点是一个素数的长度比它的结构更重要。

4、通信

完成智力扑克游戏还要完成消息的传递。WinSock提供了对TCP（传输控制协议）的支持，通过TCP协议我们可以与指定IP地址的主机建立连接，同时利用建立的连接可以双向的交换数据。双方函数调用的客户端代码如下:

BOOLCMyclientDlg：：OnInitDialog（）

{
CDialog：：OnInitDialog（）；

//创建本地套接口m-sockRecv.Create（）；

//发起连接请求

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

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

//启动定时器，定时接收数据SetTimer（1，3000，NULL）；

，

}

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

{

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

//接收TCP数据

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

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

{

szRecv[iRecv]=-\0；

m-szRecv=szRecv；

UpdateData（FALSE）；

}

，

}

本文阐述了游扑克戏中用到随机数时伪随机序列的产生和涉及到的素数，提出Miller-Rabin加密算法是较好的测试强伪素数的算法。相信通过不断地总结会更加完善游戏的机制。

admin普通用户

海报分享