雙方參與的隨機(jī)數(shù)生成和驗(yàn)證方案

劉建湘，劉憶寧

1.長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410076

2.桂林電子科技大學(xué) 可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

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

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

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

2 單向函數(shù)

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

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

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

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

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

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

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

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

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

2.2 單向函數(shù)的應(yīng)用實(shí)例

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

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

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

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

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

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

3 雙方參與的隨機(jī)數(shù)生成和驗(yàn)證方案

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

方案分為隨機(jī)數(shù)生成階段和隨機(jī)數(shù)驗(yàn)證階段。

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

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

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

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

3.2 隨機(jī)數(shù)驗(yàn)證階段

Alice懷疑Bob公布的隨機(jī)數(shù)R時(shí)，Alice可以申請(qǐng)驗(yàn)證R。

步驟1 Alice對(duì)Bob提出申請(qǐng)，要求驗(yàn)證R。

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

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

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

3.3 實(shí)例應(yīng)用

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

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

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

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

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

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

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

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

步驟1U對(duì)M提出申請(qǐng)，要求驗(yàn)證R。

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

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

4 分析

4.1 安全性分析

在整個(gè)過(guò)程中，Alice和Bob只交換了隨機(jī)數(shù)，并沒(méi)有個(gè)人信息的交換，Alice和Bob無(wú)法獲取對(duì)方的個(gè)人信息，外部惡意攻擊者無(wú)法得到Alice和Bob的個(gè)人信息，不存在隱私信息的泄露。對(duì)Alice和Bob來(lái)說(shuō)，該方案保護(hù)了雙方的身份隱私性。

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

4.2 公平性分析

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

4.3 可驗(yàn)證性分析

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

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

4.4 不可偽造性分析

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

4.5 適用性

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

4.6 不可預(yù)測(cè)性

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

4.7 高效性

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

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

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

表2 生成可驗(yàn)證性隨機(jī)數(shù)R的時(shí)間ms

5 總結(jié)

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