雙方參與的隨機數(shù)生成和驗證方案

劉建湘，劉憶寧

1.長沙理工大學 計算機與通信工程學院，長沙 410076

2.桂林電子科技大學 可信軟件重點實驗室，廣西 桂林 541004

1 引言

密碼技術被廣泛地應用于信息系統(tǒng)中，以保證信息的安全性、完整性、可處理性、可傳遞性和不可否認性。隨機數(shù)是密碼技術應用的一個重要部分，密鑰協(xié)商[1-2]、密鑰管理[3]、數(shù)字簽名[4-6]和身份認證[7]等都需要隨機數(shù)參與。隨機數(shù)分為真隨機數(shù)和偽隨機數(shù)。真隨機數(shù)是利用手工方法或物理方法選取隨機源產(chǎn)生的隨機數(shù)，真隨機數(shù)因產(chǎn)生速度慢、缺乏可移植性、通信雙方同步困難，不適合大規(guī)模的使用。偽隨機數(shù)是利用數(shù)學算法[8-10]產(chǎn)生的隨機數(shù)，由于其依照特定算法產(chǎn)生的，并不是真正的隨機數(shù)，但由于其周期很長，在現(xiàn)實中可以看成是沒有反復滿足各項指標的隨機數(shù)。目前在計算機系統(tǒng)中使用的隨機數(shù)，基本上都是偽隨機數(shù)。除了真隨機數(shù)、偽隨機數(shù)，在不少電子商務的場合，還需要可驗證隨機數(shù)，即不僅需要其結果是隨機的，而且要求這種隨機性能被驗證。真隨機數(shù)當然不具可驗證性，偽隨機數(shù)的驗證則需要提供隨機數(shù)生成算法及種子給驗證者，這當然是不現(xiàn)實的。比如在電子彩票[11]中，可信第三方可以產(chǎn)生不受人為因素控制的隨機數(shù)中獎號碼，彩票發(fā)行機構不能預知彩票中獎號碼，杜絕了彩票發(fā)行機構和彩票購買者合謀從而牟取非法利益的情況，這需要隨機性來保障。但僅僅這樣還不夠，如果彩票購買者無法驗證中獎號碼是否是隨機的，就有理由對結果提出質(zhì)疑，從而影響了彩票發(fā)行的信譽。劉憶寧等提出了基于可驗證性隨機數(shù)的電子彩票方案[12]，滿足可驗證性。

關于如何產(chǎn)生滿足要求的隨機數(shù)始終是研究熱點[13-15]，主要是利用RSA和BDH的困難性問題生成可驗證性隨機數(shù)，但是RSA和BDH的困難性問題都需要復雜的運算，效率不高。劉憶寧的方案則是基于有限域上插值多項式的可驗證隨機數(shù)方案[16]，方案中n個用戶共同生成一個隨機數(shù)r，而且用戶能夠驗證自己參與生成隨機數(shù)r。每個用戶選擇一對隨機數(shù)并發(fā)送給計算中心CC。CC收到后，加上自己任選的，依據(jù)這n+1個點構造一個n次插值多項式a0,其中令，CC公布可驗證性隨機數(shù)r。在上述方案中，隨機數(shù)r的生成，雖然滿足了安全性、可驗證性，但需要可信的計算中心。隨著隨機數(shù)應用環(huán)境的不斷變化，多方參與的可驗證性隨機數(shù)，不能很好地滿足兩方參與隨機數(shù)生成的相關要求。

本文利用單向函數(shù)設計了面向雙方的可驗證性隨機數(shù)方案，雙方平等參與隨機數(shù)的生成，并且都可以驗證自己參與了生成，協(xié)議的安全性不需要計算中心或可信第三方，降低了計算消耗及通信瓶頸，具有可驗證性、公平性、安全性、高效性、適用性。

2 單向函數(shù)

2.1 單向函數(shù)的基礎知識

單向函數(shù)是密碼學領域中的一個基本要素，其存在性意味著安全密碼系統(tǒng)的存在性。由于單向函數(shù)特殊的性質(zhì)，其被廣泛應用到安全協(xié)議，如在電話擲幣協(xié)議、承諾協(xié)議。協(xié)議是指多個參與實體之間執(zhí)行的規(guī)程，具有適當?shù)亩x。單向函數(shù)在保證協(xié)議安全執(zhí)行的過程中發(fā)揮著重要作用。單向函數(shù) f()x具有性質(zhì)如下：

（1）對于任意的整數(shù)x，由x計算 f(x)是容易的；而給出 f(x)計算x是不可能的。

（2）不可能找出一對整數(shù) x1,x2，滿足且

在單向函數(shù)的應用中，假設有兩方（A和B）來參與執(zhí)行協(xié)議。參與方A利用單向函數(shù) f(x)和信息x計算：y=f(x)，并且將y發(fā)送給B。當A公開信息x，B驗證A發(fā)送的y。這個過程必須滿足以下特性：

（1）隱私性：在公開信息x之前，任何人（除A以外）無法得到信息x。

（2）綁定性：在計算并發(fā)送y之后，任何人（包括A）無法改變x。

（3）可驗證性：公開信息x之后，任何人都可以驗證信息x，并且A無法否認。單向函數(shù)的性質(zhì)使其得到廣泛的應用，如：零知識證明、安全多方計算、身份認證等。

單向函數(shù)在這里的作用，主要是使用其綁定性，事實上是數(shù)據(jù)承諾的功能，可把單向函數(shù)看成是承諾的一個特例。

2.2 單向函數(shù)的應用實例

Hash函數(shù)是一種單向函數(shù)，即y=h(x)，由x計算y是簡單可行的，但由y計算x是不可行的。根據(jù)這一特性，可以用Hash函數(shù)。Alice利用Hash函數(shù)實現(xiàn)可驗證性，具體步驟如下：

步驟1 Alice根據(jù)消息x計算y=h(x)，是一種Hash函數(shù)。

步驟2 Alice把 y發(fā)給Bob。

步驟3 Alice需要公開信息x時，將x發(fā)給Bob。

步驟4 Bob計算 y′=h()x ，比較 y′=y是否成立，從而實現(xiàn)可驗證性。

利用Hash函數(shù)的單向性，在公開信息x之前，Bob無法得到x，也無法改變x。在公開信息x之后，Bob可以驗證y是由x生成的。

3 雙方參與的隨機數(shù)生成和驗證方案

利用單向函數(shù)，構造雙方參與的隨機數(shù)生成方案和驗證方案，雙方都可以驗證自己參與了隨機數(shù)的生成，并且實現(xiàn)了安全性、高效性、公平性、可驗證性、適用性、隨機性、不可偽造性、不可預測性。該方案中有兩個參與者：Alice和Bob。Alice和Bob需要協(xié)商一個隨機分布于區(qū)間[a ,b]上的整數(shù)，整數(shù)出現(xiàn)是相互獨立的。隨機整數(shù)不能由一個參與方單獨控制大小，但雙方都可以驗證自己參與隨機數(shù)的生成。假設在生成隨機數(shù)之前，[a ,b]和單向函數(shù)h(?)是公開的參數(shù)，且雙方之間不存在合謀的可能，因為只有兩方參與，他們的合謀是沒有意義的。

方案分為隨機數(shù)生成階段和隨機數(shù)驗證階段。

3.1 隨機數(shù)生成階段

步驟1 Alice向Bob發(fā)送請求，要求生成隨機數(shù)。

步驟2 Bob選擇的隨機數(shù)r2，計算y2=h(r2)，并將y2發(fā)送給Alice。

步驟3 Alice收到 y2后，選擇隨機數(shù)r1并發(fā)送給Bob。Bob計算 R=h(r1,r2)mod(b-a)+a+1。Bob令 R為雙方協(xié)商的隨機數(shù)，并將其發(fā)送給Alice。

3.2 隨機數(shù)驗證階段

Alice懷疑Bob公布的隨機數(shù)R時，Alice可以申請驗證R。

步驟1 Alice對Bob提出申請，要求驗證R。

步驟2 Bob把r2發(fā)送給Alice。

步驟3 Alice收到r2，計算 R′=h(r1,r2)mod(b-a)+a+1和，判斷R′=R和是否成立，從而驗證是否參與生成R。

雙方參與的隨機數(shù)生成和驗證方案可以生成滿足雙方要求的隨機數(shù)，并且隨機數(shù)是均勻分布在區(qū)間[ ]a,b上的，而且每個整數(shù)出現(xiàn)是相互獨立的。該方案滿足安全性、隨機性、公平性、可驗證性、不可偽造性、高效性、不可預測性，另外該方案還具有較強的使用性，不論在雙方參與還是多方參與都具有適用性和高效性。

3.3 實例應用

雙方參與的隨機數(shù)生成和驗證方案在實際生活中有著廣泛的應用，例如構造可驗證性隨機數(shù)電子優(yōu)惠卷、電話擲幣等。假設在隨機數(shù)電子優(yōu)惠券方案中，有兩個參與者：用戶（U）和商家（M）。首先M通過公共渠道發(fā)布優(yōu)惠信息，任何用戶在該商店購買商品，當商品價格大于m時，用戶使用電子支付均可通過抽獎獲取1到m元的電子優(yōu)惠券。方案分為優(yōu)惠券金額生成階段和優(yōu)惠金額驗證階段。

3.3.1 優(yōu)惠金額生成階段

U在M處購買商品，看到商家發(fā)布的優(yōu)惠信息，決定電子支付，并和商家一起生成電子優(yōu)惠券。

步驟1U向M發(fā)送支付請求，M選擇隨機數(shù)r2，計算y2=h(r2)，并將y2發(fā)送給U。

步驟2U收到y(tǒng)2后，選擇隨機數(shù)r1并發(fā)送給M。

步驟3M計算R=h(r1,r2)modm+1，令R為雙方生成的優(yōu)惠金額值，并在U的支付賬單中減少R。

3.3.2 優(yōu)惠金額驗證階段

U使用電子支付時，如果懷疑商家每次惡意的分配小金額優(yōu)惠券，可以申請驗證R。

步驟1U對M提出申請，要求驗證R。

步驟2M把r2發(fā)送給U。

步驟3U收到r2，計算R′=h(r1,r2)mod(b-a)+a+1和，判斷R′=R和是否成立，從而驗證是否參與生成優(yōu)惠金額值R。

4 分析

4.1 安全性分析

在整個過程中，Alice和Bob只交換了隨機數(shù)，并沒有個人信息的交換，Alice和Bob無法獲取對方的個人信息，外部惡意攻擊者無法得到Alice和Bob的個人信息，不存在隱私信息的泄露。對Alice和Bob來說，該方案保護了雙方的身份隱私性。

隨機數(shù)的生成是相互獨立的，并且不受Alice和Bob的控制，對與Alice和Bob來說隨機數(shù)是安全的。實例中，用戶和商家生成了區(qū)間上的隨機優(yōu)惠值，并且其中一方無法控制隨機數(shù)的生成，而且用戶還可以驗證自己參與優(yōu)惠值的生成。整個方案中只有隨機數(shù)的交換，商家和用戶無法損害對方利益，外部惡意攻擊者也不會損害到用戶和商家的利益。

4.2 公平性分析

實例中，U和M共同參與生成優(yōu)惠值R，并且U可以驗證自己參與了生成優(yōu)惠值。U收到y(tǒng)2后，無法根據(jù)y2得到r2，也就無法選擇期望的隨機數(shù)r1，所以用戶無法控制優(yōu)惠值的生成。M無法根據(jù)r1的大小來改變r2的大小，從而得到期望的R值，所以M無法控制優(yōu)惠值的生成，防止了M惡意分配小額優(yōu)惠值，保證了雙方在交易過程中的公平性。

4.3 可驗證性分析

Alice對Bob公布的隨機數(shù)產(chǎn)生了懷疑，可以申請驗證。Alice根據(jù)判斷R′=R和是否成立從而驗證自己是否參與了隨機數(shù)的生成。另外Bob將y2發(fā)送給Alice，Alice無法根據(jù)y2得到r2，也就無法選擇期望的隨機數(shù)r1，雙方都無法控制隨機數(shù)的生成，并且雙方都可以驗證參與了隨機數(shù)的生成，滿足可驗證性。

實例中，用戶可以驗證自己是否參與了優(yōu)惠值的生成，滿足了可驗證性。

4.4 不可偽造性分析

分布于區(qū)間上的隨機數(shù)R是由隨機數(shù)r1和r2共同生成的。隨機數(shù)r1和r2分別是Alice和Bob隨機選取的，并且選取之后，Bob無法更改r2，生成的隨機數(shù)滿足不可偽造性。

4.5 適用性

雙方參與的可驗證隨機數(shù)生成方案不僅適用于雙方，還可以多方選擇隨機數(shù)來生成共同使用的隨機數(shù)。基于插值多項式的隨機數(shù)生成方案中，當人數(shù)較多時，多項式次數(shù)較大，生成多方使用的隨機數(shù)隨著參與方的增加，所需計算量增加較多造成效率較低。而且，插值多項式方案中需要計算中心的參與，因此雙方參與的隨機數(shù)生成和驗證方案適用性更好。

4.6 不可預測性

在Alice向Bob發(fā)送請求，要求生成隨機數(shù)。Bob選擇的隨機數(shù)r2，計算 y2=h(r2)，并將 y2發(fā)送給Alice；Alice無法根據(jù)y2計算得到r2，從而選擇合適的r1來得到期望的R。Bob選擇的隨機數(shù)r2時，不知道r1的大小，所以無法選擇合適的r2來得到期望的R。Bob收到r1后無法更改r2，來得到期望的R，所以隨機數(shù)R的生成是不可預測的，滿足不可預測性。

4.7 高效性

方案主要采用Hash函數(shù)做計算，不必要進行高次數(shù)的指數(shù)運算，具有高效的特性。在方案中，Alice只需要提供隨機數(shù)r1就可以生成共用的隨機數(shù)R，和有限域上插值多項式生成隨機數(shù)的方法相比，減少了計算中心的參與，降低了通訊量。假設1 000個人中有一個Alice要求驗證，一個數(shù)據(jù)是1 000 bit，和插值多項式生成隨機數(shù)比較，得到結果如表1。

表1 1 000人生成隨機數(shù)的通訊量比較

由表1可知，雙方參與的隨機數(shù)生成和驗證方案在計算時間和通訊上更加高效。另外基于插值多項式生成隨機數(shù)方案中人數(shù)成倍數(shù)增加時，生成可驗證性隨機數(shù)的計算負擔發(fā)幅度增加。利用電腦參數(shù)為：系統(tǒng)Ubuntu 14.0403LTS，CPU：2.50 GHz，內(nèi)存：8 GB的電腦分別計算生成可驗證性隨機數(shù)的時間，得到結果如表2，本文單向函數(shù)以SHA-256為例。

表2 生成可驗證性隨機數(shù)R的時間ms

5 總結

雙方參與的隨機數(shù)生成和驗證方案將Bob作為計算中心，Alice只需要提供隨機數(shù)r1即可參與隨機數(shù)R的生成，運算過程中無需計算中心和可信第三方參與。在隨機數(shù)R公布之后，Alice如果需要驗證，Bob把自己選擇的隨機數(shù)r2和時間t發(fā)送給Alice，Alice做Hash運算從而驗證。因此，用戶承擔的計算量、通訊量都得到了降低，該方案比較適用于移動終端的使用。