基于網絡的可驗證電子搖號系統的開發及實現

馬國群 涂榮范 崔威銘 劉憶寧 黃娟

桂林電子科技大學數學與計算科學學院 廣西 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.