基于网络的可验证电子摇号系统的开发及实现

马国群 涂荣范 崔威铭 刘忆宁 黄娟

桂林电子科技大学数学与计算科学学院 广西 541004

0 引言

电子商务与电子政务在过去的十余年间从无到有，并随着普适计算网络的普及，其应用范围达到了无处不在、无时不在的地步。所谓的电子商务与电子政务，并不是简单地将传统的商务及政务功能移植到网络平台上，而应该结合网络的特性，使其更加便利、安全、快捷。普适计算环境中的电子商务虽然提供了无缝接入的便利性，但也造成一些不可忽视的问题，如大规模参与者之间缺乏信任基础，影响到使用者的积极性。

电子商务中的公平性，尤其是在缺乏信任基础的开放环境中的公平性，是关系电子商务活动的可持续发展的关键性因素。在缺乏可信任基础网络平台上的公平性，如何保障？最好的办法就是让所有的参与者都能验证公平性，即实现可验证的公平。现在的电子彩票、保障性住房摇号、北京新车上牌摇号、新股申购等，都是以公平性的实现为基本要求的，没有公平性的保障，上述活动就会失去存在的基础。目前，上述活动的公平性主要依赖可信任的第三方如公证机关等的参与，但过去的事实告诉我们，公证机关有可能参与舞弊行为，虽然被发现的案例不多，但确实存在。偶发性的摇奖活动造假事件，已经损害了电子商务活动的信任基础，如何从多种角度实现公平性，从而赢得参与者的广泛信任，是一个必须解决的问题。除了健全法律法规之外，从技术角度实现可参与、可验证的公平性，不失为最佳选择。

从技术角度看，公平性、随机性、不可预测性紧密联系，其实现的基础可以视为相同，如电子摇号系统的公平性，可以等同于摇号结果的随机性，或者说对于所有参与者来说，具有不可预测性。而随机性的研究，是密码学或应用数学中较为成熟的领域。利用随机数的理论与构造方法，实现普适计算环境中的可验证公平性，对于保障电子商务的健康发展，具有重要的理论价值与现实意义。

在密码学的传统应用中，随机数或伪随机数用以保障通信内容的机密性、以及认证通信者的身份等，构造随机数或伪随机数均有比较成熟的方法。随机数的构造通常采用物理方法获得，比如抛硬币、掷骰子以及随机噪音等方法，在使用前需事先将随机数序列分发给使用各方，在使用时需严格同步，造成随机数的生产、管理及使用成本较高，主要用于军事外交领域。采用数学方法构造计算上不可能重复的序列，称为伪随机数，用以适应大规模数据通信对随机性的要求。虽然不是真正的随机数，但在实际应用中，可当作真随机数使用，具有计算上的安全性。在以往的电子商务协议中，通常用随机数或伪随机数来保障协议的公平性。如体育彩票或福利彩票的获奖结果用跳动的乒乓球产生，从理论上来说，这一结果的产生是完全随机的，如果操作过程中不存在合谋造假，其结果对各方都是公平公正的，但如果摇奖器具被人为改动，其公平性就无法保证。同时，由于摇奖结果的产生是随机的，摇奖结果当然就具有不可再现性，公众对公平性的信心只能依赖于对公证机关的充分信任。因此，具有不可再现性、不可重复性的真随机数，不具有使公众验证其随机性与公平性的功能。伪随机数的产生依赖于数学函数所产生的大周期序列，由构造算法与初始值(种子)决定。若用伪随机数保障其公平性，具有可验证性，但这是有条件的可验证性，需要组织方提供伪随机数的构造算法与种子值。同样，在缺乏信任基础的普适计算环境中，组织者将种子值公布可能会给系统造成安全隐患，且初始值的选取由谁决定仍是一个问题，即使伪随机数构造算法可保障结果的不可预测性，但这一隐患仍是影响公平性的主要心理障碍。

1 可验证随机数的构造

理想的可验证随机数应该满足：不可预测，可再现，可验证，n个用户U1,U2,… ,Un各自提供r1,r2,…,rn,r1,r2, …,rn共同参与随机数r的生成，并且Ui可以凭自己ri而不需要其它参与者的rj(j≠i)即可验证ri参与了r的产生，从而确信r没有被人为控制，确信r的生成过程是公平公正的。

步骤如下：

（1）Ui任选ri= (xi,yi)发送给计算中心 CC(Computing Center)；

（2）CC收到ri=(xi,yi)(1≤i≤n)后，任选rc= (xc,yc)；

（3）CC依据n+ 1 个点 (x1,y1) ,(x2,y2),… ,(xn,yn) ,(xc,yc)构造n次插值多项式A(x) =a0+a1x+ …+anxn，计算中心CC具有较强的计算能力，当插值点数不是很多的时候，可以在较短的时间内计算出插值多项式A(x)的系数 (a0,a1,…,an)，使之满足yi=A(xi)(1≤i≤n)；

（4）令r=a0||a1||… ||an，(||表示连接符)，称为插值系数随机数，计算中心CC公布可验证随机数r。

如果用户Ui对r的随机性怀疑，可以通过如下过程验证：

（1）Ui由向量 (a0,a1,… ,an)恢复出n次多项式A(x)=a+ax+ …+axn；

01n

（2）Ui验证yi=A(xi)是否成立，如果成立，说明ri= (xi,yi)参与了随机数r的产生，否则，随机数r是不可靠的。

※不拉肚子之后可以把其他药物停掉，但益生菌建议再吃几天。另外有研究证明，定期比如每周吃1次益生菌，有助于预防腹泻。

例如：设p= 7 ，满足 (x0,y0) = ( 1,2)，(x1,y1) = ( 2,6)，(x,y) = ( 4,5)的 插 值 多 项 式A(x) =a+ax+ … +axn=

2 201n2 + 5x+ 2x2∈F[x]。

7

可验证随机数R=hash(a0||a1||a2) =hash(2||5||2)。

(x0,y0) = ( 1,2)，(x1,y1) = ( 2,6)，(x2,y2) = ( 4,5)的提供者均可独立验证A(xi) =yi(i= 0 ,1,2)。从而可确信均参与了R=hash(a0| |a1||a2) =hash(2||5||2)的生成，即生成过程不存在合谋欺骗问题，是可信的。

基于插值多项式的可验证随机数生成方案，将主要运算任务安排在计算中心一端，用户端只需提供一组随机数(x,y)参与可验证随机数R的生成，运算过程无需用户参与，在R公布后，用户如果需要验证，只需进行简单高效的多项式运算即可。因此，用户端承担的运算量、通信量，都降到了最低程度，此方案特别适合于移动通信终端的使用。

2 基于网络平台的可验证摇号系统开发

软件采用面向对象的技术，符合软件一般的设计原则——开闭原则，对于扩展开放，对于修改关闭。由于软件涉及到用户的安全性，故采用SQL数据库来管理数据，通过ODBC技术来对数据库进行访问。在保证软件的耦合性好前提下，各个模块之间相互独立，模块之间的依赖性几乎没有，这依赖的是dll技术，这利于大大的利于软件后期的维护和更新。同时，客户的验证工作采用的是Client/Server模式进行通信验证，运用多线程技术同时处理多客户连接(如图1)。

图1 客户端设计框图

软件主要是采用的C++和C语言相结合来实现，采用的是面向对象程序设计的方法来实现各个模块的功能，这使得对于软件各个模块相对的独立，便于软件的维护，主要采取了泛型程序设计的方法来进行数据的运算，利用多线程技术实现与用户的通信，并同时满足多用户的连接要求。各个模块采用的是 dll技术，算法的改变将不会影响到软件整体的性能和运行(如图2)。

图2 服务器端设计框图

3 结论

基于有限域上的插值多项式构造的可验随机数，具有可参与性、可验证性的特点，以此为基础，设计了基于网络平台的可验证摇号系统，可广泛应用于电子商务与电子政务，具有效率高、安全性好的特点，对于保障电子商务与电子政务的健康发展，具有重点的作用。

[1]http://www.hb.xinhuanet.com/zhuanti/hbbddyjadc.htm.

[2]刘忆宁,叶俊,曹建宇.基于 Fp上插值多项式的可验证随机数[J],四川大学学报(工程科学版).2010.

[3]何玉洁,李宝安.数据库系统教程[M].北京:人民邮电出版社.2010.

[4]陈维兴,陈昕.C++面向对象程序设计[M].北京:人民邮电出版社.2010.