現(xiàn)代密碼學(xué)(第六章)

1、2022-4-261第六章：第六章：密碼技術(shù)應(yīng)用一、秘密共享一、秘密共享二、不經(jīng)意傳輸二、不經(jīng)意傳輸三、電子投票三、電子投票四、零知識(shí)證明四、零知識(shí)證明五、電子現(xiàn)金支付五、電子現(xiàn)金支付2022-4-262一、秘密共享一、秘密共享“海盜分割藏寶圖”是秘密共享方案的原始模型。設(shè)共有n個(gè)海盜有權(quán)參加寶物分配。為了防止獨(dú)吞或聯(lián)手作弊，規(guī)定：t個(gè)人以上同時(shí)到場(chǎng)才能找到寶物，而t-1個(gè)人以下同時(shí)到場(chǎng)是不能找到寶物的。恰當(dāng)?shù)胤指畈貙殘D就是解決這個(gè)問題的有效方法。在這里，一個(gè)秘密被分成了n份，任何t份并在一起，都能復(fù)原秘密。t被稱為門限值。 t n。2022-4-263一、秘密共享一、秘密共享秘密共享方案有多

2、種用途。比如：n遺產(chǎn)的分配與公證。遺產(chǎn)的分配與公證。n多用戶通信。多用戶通信。n電子商務(wù)中的各種交易方案。電子商務(wù)中的各種交易方案。n重大決策的控制閥（如核按鈕等）。重大決策的控制閥（如核按鈕等）。2022-4-264一、秘密共享一、秘密共享例：一個(gè)最簡(jiǎn)單的秘密共享方案例：一個(gè)最簡(jiǎn)單的秘密共享方案設(shè)保險(xiǎn)柜有三把鎖，分別編號(hào)為、。張三擁有、號(hào)鎖的鑰匙。李四擁有、號(hào)鎖的鑰匙。王五擁有、號(hào)鎖的鑰匙。三個(gè)人中，任何兩個(gè)以上的人同時(shí)到場(chǎng)均可以打開保險(xiǎn)柜；任何一個(gè)以下的人到場(chǎng)均打不開保險(xiǎn)柜。此處，一個(gè)秘密指的是“、號(hào)鎖的鑰匙”；n=3（個(gè)人）；門限值t=2 （個(gè)人）。2022-4-265一、秘密共享一、秘

3、密共享Shamir的秘密共享門限方案的秘密共享門限方案選擇一個(gè)大素?cái)?shù)p。選擇一個(gè)t-1次的整系數(shù)多項(xiàng)式h(x)：)(mod)(012211paxaxaxaxhtttt2022-4-266一、秘密共享一、秘密共享n設(shè)一共有n個(gè)參與者。n設(shè)第k位參與者擁有的公開身份名是ID(k)，其中ID(k)是整數(shù)。n設(shè)第k位參與者擁有的秘密身份名是h(ID(k)。此處k=1, 2, 3, , n。n多項(xiàng)式h(x)對(duì)所有參與者保密。換句話說，多項(xiàng)式h(x)的系數(shù)a0, a1, a2, , at-2, at-1對(duì)所有參與者保密。n第k位參與者擁有（ID(k)，h(ID(k)）。其中ID(k)對(duì)其他參與者公開，h(

4、ID(k)對(duì)其他參與者保密。此處k=1, 2, 3, , n。2022-4-267一、秘密共享一、秘密共享多項(xiàng)式h(x)（即多項(xiàng)式h(x)的系數(shù)a0, a1, a2, , at-2, at-1）就是n個(gè)參與者所共享的秘密。任何t個(gè)人以上同時(shí)到場(chǎng)，每個(gè)人交出自己的身份名（ID(k)，h(ID(k)），拼在一起，就能計(jì)算出h(x)。任何t-1個(gè)人以下同時(shí)到場(chǎng)，每個(gè)人交出自己的身份名（ID(k)，h(ID(k)），拼在一起，則不能計(jì)算出h(x)。以下詳細(xì)說明。2022-4-268一、秘密共享一、秘密共享不失一般性,不妨設(shè)第1位第t位參與者同時(shí)到場(chǎng)，每個(gè)人交出自己的身份名：（ID(k)，h(ID(k)

5、）， k=1, 2, 3, , t。于是得到了如下的方程組：對(duì)于k=1, 2, 3, , t，)(mod)()()()()(112222110pkIDakIDakIDakIDaakIDhtttt2022-4-269一、秘密共享一、秘密共享即)(mod)()(1)2()2(1)1()1(1)()2()1(110111111paaatIDtIDIDIDIDIDtIDhIDhIDhtttt2022-4-2610一、秘密共享一、秘密共享這是一個(gè)關(guān)于未知系數(shù)a0, a1, a2, , at-2, at-1的t元一次方程組（請(qǐng)注意，是模(modp)運(yùn)算的t元一次方程組），有t個(gè)方程，因此容易解出a0, a

6、1, a2, , at-2, at-1。當(dāng)任何t-1個(gè)人以下同時(shí)到場(chǎng)，每個(gè)人交出自己的身份名（ID(k)，h(ID(k)），則獲得了關(guān)于未知系數(shù)的t元一次方程組，有t-1個(gè)以下方程，因此無法唯一地確定h(x)。2022-4-2611一、秘密共享一、秘密共享在在Shamir秘密共享方案中秘密共享方案中檢測(cè)檢測(cè)“欺騙者欺騙者”設(shè)有設(shè)有t+1個(gè)以上參與者同時(shí)到場(chǎng)。個(gè)以上參與者同時(shí)到場(chǎng)。其中有一個(gè)參與者是“欺騙者”Eve，他出示的是身份名（ID(k)，h(ID(k)）是假的。設(shè)任何t個(gè)誠實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量都是真實(shí)的a0, a1, a2, , at-2, at-1。設(shè)Eve與

7、某t-1個(gè)誠實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量是a0, a1, a2, , at-2, at-1。設(shè)Eve與另外t-1個(gè)誠實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量是 a0”, a1”, a2”, , at-2”, at-1”。2022-4-2612一、秘密共享一、秘密共享由于Eve難以由自己的所謂ID(k)求出對(duì)應(yīng)的h(ID(k)，因此他的所謂身份名（ID(k)，h(ID(k)）很難成為“配套的”。因此，a0, a1, a2, , at-2, at-1，a0, a1, a2, , at-2, at-1，a0”, a1”, a2”, , at-2”, at-1”，三個(gè)系數(shù)向量中

8、的任何兩個(gè)向量都很難相互相等。2022-4-2613一、秘密共享一、秘密共享檢測(cè)結(jié)論（一）檢測(cè)結(jié)論（一）當(dāng)某t個(gè)參與者組合計(jì)算出的系數(shù)向量與另外t個(gè)參與者組合計(jì)算出的系數(shù)向量不相等時(shí)，這兩次被組合的全部人員中必有“欺騙者”。檢測(cè)結(jié)論（二）檢測(cè)結(jié)論（二）當(dāng)某t個(gè)參與者組合計(jì)算出的系數(shù)向量與另外t個(gè)參與者組合計(jì)算出的系數(shù)向量相等時(shí)，（幾乎可以斷定）這兩次被組合的全部人員都是誠實(shí)的參與者。2022-4-2614一、秘密共享一、秘密共享習(xí)題習(xí)題 設(shè)：p=17；n=5；t=3；(ID(1), h(ID(1)=(1, 8)；(ID(2), h(ID(2)=(2, 7)；(ID(3), h(ID(3)=(3

9、, 10)；(ID(4), h(ID(4)=(4, 0)；(ID(5), h(ID(5)=(5, 11)。當(dāng)?shù)?位第3位參與者同時(shí)到場(chǎng)，求共享的秘密)17(mod)(2210 xaxaaxh2022-4-2615二、不經(jīng)意傳輸二、不經(jīng)意傳輸“不經(jīng)意傳輸協(xié)議不經(jīng)意傳輸協(xié)議”的特性的特性（不經(jīng)意傳輸協(xié)議；（不經(jīng)意傳輸協(xié)議；Oblivious Transfer；OT）設(shè)Alice欲告訴Bob 某個(gè)秘密。 Alice使用一個(gè)“不經(jīng)意傳輸協(xié)議”將此秘密發(fā)送給Bob。則發(fā)送/接收過程就具有以下的性質(zhì)。2022-4-2616二、不經(jīng)意傳輸二、不經(jīng)意傳輸（1）Bob能夠獲得此秘密的概率是1/2。換句話說，Bo

10、b不能獲得此秘密的概率也是1/2 。再換句話說，無論Alice或Bob怎樣努力，只要Alice和Bob使用的是不經(jīng)意傳輸協(xié)議，則Bob成功地獲得秘密的概率就只能是1/2。再換句話說，Alice或Bob都無法影響秘密的成功接收。影響秘密的成功接收的因素只有一個(gè)，那就是概率分布。再換句話說，發(fā)/收過程實(shí)際上就是一個(gè)動(dòng)作：高拋硬幣，落地后正面朝上和反面朝上的概率各占1/2，任何人也無法干預(yù)落地后的結(jié)果。2022-4-2617二、不經(jīng)意傳輸二、不經(jīng)意傳輸（2）發(fā)送/接收過程完結(jié)時(shí)， Alice無法確知Bob是否得到了秘密。換句話說，在發(fā)/收過程結(jié)束后， Alice仍然僅僅知道： Bob得到秘密和未得到

11、秘密的可能性各占1/2。除此之外， Alice得不到任何新的消息。2022-4-2618二、不經(jīng)意傳輸二、不經(jīng)意傳輸不經(jīng)意傳輸?shù)膽?yīng)用實(shí)例不經(jīng)意傳輸?shù)膽?yīng)用實(shí)例n設(shè)Alice欲向Bob 行賄。 nBob不愿讓Alice知道自己是否接受了賄賂。n而Alice也愿意讓Bob放心，只關(guān)心自己行賄，不愿知道對(duì)方是否受賄。n于是他們使用一個(gè)“不經(jīng)意傳輸協(xié)議”傳輸賄金帳號(hào)。這樣，即使發(fā)現(xiàn)Alice行賄，也無法證明Bob受賄。2022-4-2619二、不經(jīng)意傳輸二、不經(jīng)意傳輸Rabin的的“不經(jīng)意傳輸協(xié)議不經(jīng)意傳輸協(xié)議” 預(yù)備知識(shí)：計(jì)算數(shù)論的一些結(jié)果預(yù)備知識(shí)：計(jì)算數(shù)論的一些結(jié)果設(shè)有兩個(gè)大素?cái)?shù)p和q。令N=pq。

12、取整數(shù)x，1xN。令a=x2(modN)。2022-4-2620二、不經(jīng)意傳輸二、不經(jīng)意傳輸結(jié)果一結(jié)果一 已知N，求p和q困難。（大數(shù)分解）結(jié)果二結(jié)果二 a一共有4個(gè)(modN)平方根，他們是：x；N-x；y；N-y。即： ax2(N-x)2y2(N-y)2(modN)，且x、N-x、y、N-y互不相等。 4個(gè)(modN)平方根的關(guān)系如下：設(shè)xu(modp)，xv(modq)；則N-xp-u(modp)，N-xq-v(modq)；yu(modp)，yq-v(modq)；N-yp-u(modp)，N-yv(modq)。2022-4-2621二、不經(jīng)意傳輸二、不經(jīng)意傳輸結(jié)果三結(jié)果三 （1）如果已知

13、p，q，a，則可以求出a的4個(gè)(modN)平方根x，N-x，y，N-y 。（2）如果僅僅已知N，a，則不能求出a的任何一個(gè)(modN)平方根。結(jié)果四結(jié)果四（1）如果已知N，x，y或已知N，x，N-y或已知N，N-x，y或已知N，N-x，N-y，則可以求出p和q。（2）如果僅僅已知N，x，N-x或僅僅已知N， y，N-y ，則不能求出p和q。2022-4-2622結(jié)果一2022-4-2623結(jié)果二與結(jié)果三（2）2022-4-2624結(jié)果三（1）2022-4-2625結(jié)果四（1）2022-4-2626結(jié)果四（2）2022-4-2627二、不經(jīng)意傳輸二、不經(jīng)意傳輸Rabin的不經(jīng)意傳輸協(xié)議的不經(jīng)意傳

14、輸協(xié)議（1）Alice取定兩個(gè)大素?cái)?shù)p和q， p，q就是Alice要發(fā)送給Bob的秘密。（2）Alice計(jì)算N=pq，并將N發(fā)送給Bob。（3）Bob取定整數(shù)x，1xN，計(jì)算a=x2(modN)，并將a發(fā)送給Alice 。（4）Alice根據(jù)結(jié)果三， Alice計(jì)算出了a的4個(gè)(modN)平方根x，N-x，y，N-y 。（5）Alice在4個(gè)平方根x，N-x，y，N-y中隨機(jī)地選擇一個(gè)，并將它發(fā)送給Bob。2022-4-2628二、不經(jīng)意傳輸二、不經(jīng)意傳輸（6） Bob收到了Alice發(fā)送的一個(gè)“平方根”z。 Bob首先檢查是否z2(modN)=a。若是，則z是a的(modN)平方根；否則說明

15、Alice作弊。再根據(jù)結(jié)果四，有：如果z=x，則Bob不能求出p和q；如果z=N-x，則Bob不能求出p和q；如果zx，zN-x，則Bob可以求出p和q。2022-4-2629二、不經(jīng)意傳輸二、不經(jīng)意傳輸Bob在4個(gè)(modN)平方根x，N-x，y，N-y中隨機(jī)地選擇一個(gè)，因此他選擇x或N-x的概率為1/2，他選擇y或N-y的概率也為1/2。因此Bob獲得秘密p，q和未獲得秘密p，q的概率各占1/2。2022-4-2630三、電子投票三、電子投票一般投票所需滿足的安全特性：一般投票所需滿足的安全特性：（1）合法性：只有合格者才能投票；（2）唯一性：一人只能投一次票；（3）匿名性：每個(gè)人投票的內(nèi)

16、容對(duì)他人保密，僅僅提交選舉委員會(huì)；（4）不可追蹤性：一個(gè)人投票的內(nèi)容提交到選舉委員會(huì)后，選舉委員會(huì)無法由所投的票追蹤到投票人。（5）可驗(yàn)證性：每位投票人都能夠檢驗(yàn)，自己投的票是否被正確地記入。2022-4-2631三、電子投票三、電子投票回憶對(duì)盲簽名的特殊要求：（1）簽名者在對(duì)文件簽名的時(shí)候，“看不見”自己所簽名的文件的內(nèi)容，只能“看見”要求自己簽名的人。（2）簽名者對(duì)文件的“封皮”簽名。該簽名值能夠透過“封皮”印在文件上，形成對(duì)文件本身的簽名。（3）日后當(dāng)簽名者“看見了”文件的內(nèi)容以及自己對(duì)文件的簽名，簽名者也無法“回憶起”當(dāng)時(shí)簽名的場(chǎng)景（這份當(dāng)時(shí)是誰來找自己簽名的？等等）2022-4-26

17、32三、電子投票三、電子投票盲簽名電子投票協(xié)議盲簽名電子投票協(xié)議（ 核心是核心是Chaum的的盲簽名算法）盲簽名算法）選舉委員會(huì)選擇兩個(gè)大的素?cái)?shù)p和q；選擇兩個(gè)正整數(shù)e和d，使ed是(p-1)(q-1)的倍數(shù)加1；計(jì)算n=pq。選舉委員會(huì)的公鑰是（n，e），選舉委員會(huì)的私鑰是（p，q ，d）。2022-4-2633三、電子投票三、電子投票（一）投票人：按照自己的意愿選擇投票的內(nèi)容m。再隨機(jī)地選擇一個(gè)整數(shù)R，計(jì)算C=Rem(modn)。將C連同自己的身份發(fā)送給選舉委員會(huì)。2022-4-2634三、電子投票三、電子投票（二）選舉委員會(huì)：檢查投票人的身份。檢查兩點(diǎn)：投票人的身份是否符合規(guī)定；投票人的

18、身份先前是否已經(jīng)用過。如果投票人通過了檢驗(yàn)，選舉委員會(huì)將備注“此人的身份已經(jīng)用過”。然后選舉委員會(huì)進(jìn)行簽名過程。計(jì)算T=Cd(modn)。將T送還給投票人。（請(qǐng)注意，此時(shí)T=Cd(modn)=(Rem)d(modn)=Rmd(modn)2022-4-2635三、電子投票三、電子投票（三）投票人：計(jì)算S=R-1T(modn)。檢查是否Se(modn)=m。若是，則將S作為選舉委員會(huì)對(duì)投票內(nèi)容m的簽名；否則認(rèn)為選舉委員會(huì)在欺騙。（請(qǐng)注意，如果選舉委員會(huì)是誠實(shí)的，即T=Cd(modn)，則必有Se(modn)=(R-1T)e(modn)=(R-1Rmd)e(modn)=m。如果選舉委員會(huì)在欺騙，即T

19、Cd(modn)，則Se(modn)m。）2022-4-2636三、電子投票三、電子投票（四）投票人：將投票內(nèi)容m與簽名S聯(lián)立成簽名消息(m, S)。將(m, S) 發(fā)送給選舉委員會(huì)，完成投票。請(qǐng)注意：投票人此時(shí)并不發(fā)送自己的身份，這就是說，選舉委員會(huì)不知道是誰在投票。2022-4-2637三、電子投票三、電子投票（五）選舉委員會(huì)：檢查是否S=md(modn)。若是，則(m, S)是一張誠實(shí)的、經(jīng)過選舉委員會(huì)簽名的選票；否則認(rèn)為投票者在欺騙。驗(yàn)票完成。張榜公布所有的簽名選票。2022-4-2638三、電子投票三、電子投票（六）投票人：檢查所有的簽名選票中是否有一張為(m, S)。若有，則該投票

20、人認(rèn)為選舉委員會(huì)對(duì)自己是誠實(shí)的。若沒有，則該投票人認(rèn)為選舉委員會(huì)在欺騙自己。2022-4-2639三、電子投票三、電子投票（七）附加步驟。投票人：若發(fā)現(xiàn)榜上沒有(m, S) ，則可以持(m, S)質(zhì)詢選舉委員會(huì)，并將(m, S) 公布于眾。任何人在見到(m, S)后，都可以計(jì)算出Se(modn)=m。這就是說，任何人都知道(m, S) 是被選舉委員會(huì)簽名的票。選舉委員會(huì)一定敗訴。2022-4-2640三、電子投票三、電子投票S是選舉委員會(huì)對(duì)投票內(nèi)容是選舉委員會(huì)對(duì)投票內(nèi)容m的盲簽名。的盲簽名。（1）選舉委員會(huì)在對(duì)投票內(nèi)容m進(jìn)行簽名時(shí)，知道了投票人的身份，但并不知道被簽名的投票內(nèi)容m。（2）選舉委

21、員會(huì)實(shí)際上是在對(duì)C簽名：T=Cd(modn)。而C=Rem(modn)，其中R是一個(gè)隨機(jī)選擇的整數(shù)，掩蓋了投票內(nèi)容m。（3）在投票時(shí)，選舉委員會(huì)只能檢驗(yàn)是否(m, S)是經(jīng)過自己簽名的票，而看不見投票人的身份。綜上所述，選舉委員會(huì)不能由選票來追蹤投票人。2022-4-2641三、電子投票三、電子投票此電子投票方案是否滿足安全特性？此電子投票方案是否滿足安全特性？n合法性：滿足。在方案的第（二）步，選舉委員會(huì)檢查投票人的身份是否符合規(guī)定 。n唯一性：滿足。在方案的第（二）步，選舉委員會(huì)檢查投票人先前是否已經(jīng)投過票。2022-4-2642三、電子投票三、電子投票n匿名性：滿足。在方案的第（二）步，

22、雖然投票人的身份暴露給了選舉委員會(huì)，但隨機(jī)數(shù)R掩蓋了投票內(nèi)容m，使選舉委員會(huì)不知道該投票人投的什么票。n不可追蹤性：滿足。在方案的第（五）步，選舉委員會(huì)僅僅看見簽名票(m, S) ，而看不見投票人的身份，也無法將(m, S) 與前面見過的C聯(lián)系起來。因此選舉委員會(huì)無法知道簽名票(m, S) 是誰投的。2022-4-2643三、電子投票三、電子投票n可驗(yàn)證性：不滿足。投票人能夠向別人證明(m, S)是一張被選舉委員會(huì)簽名的合法選票，并且當(dāng)榜上沒有自己投的票(m, S) 時(shí)，提出必勝的訴訟。但是，當(dāng)榜上有(m, S)時(shí)，卻不能說明選舉委員會(huì)沒有欺騙自己。注意到對(duì)投票內(nèi)容m的簽名值是唯一的： S=m

23、d(modn)。別人也可能選擇m為投票內(nèi)容，因此一個(gè)(m, S)有可能是別人投的票。2022-4-2644三、電子投票三、電子投票投票人進(jìn)行的攻擊投票人進(jìn)行的攻擊投票人所擁有的工具：選舉委員會(huì)的公鑰（n，e）。投票人的攻擊方法：利用基本RSA的安全性漏洞。（1）投票人選擇一個(gè)“簽名” S，用選舉委員會(huì)的公鑰（n，e），計(jì)算“投票內(nèi)容”m：m=Se(modn)。2022-4-2645三、電子投票三、電子投票（2）投票人繞過投票過程的第（一）、（二）、（三）步，直接進(jìn)入投票過程的第（四）步，將(m, S) 發(fā)送給選舉委員會(huì)，完成投票。由于完成投票時(shí)是不需要顯示身份的，因此投票人既可以無資格投票，也

24、可以重復(fù)投票。（3）選舉委員會(huì)進(jìn)入投票過程的第（五）步， 驗(yàn)證了S=md(modn)，即認(rèn)定(m, S) 是自己簽名的合法票。攻擊成功。2022-4-2646三、電子投票三、電子投票投票人攻擊的局限性投票人攻擊的局限性注意到投票人是先選定了簽名S的值，然后反過來對(duì)投票內(nèi)容m進(jìn)行偽造：m=Se(modn)。當(dāng)規(guī)定投票內(nèi)容只能是少數(shù)幾個(gè)值時(shí)，偽造的投票內(nèi)容m很難恰好是這幾個(gè)值。比如：投票內(nèi)容只能是“同意”或“反對(duì)”；又比如：投票內(nèi)容只能是“張三”、“李四”等少數(shù)幾個(gè)人的姓名。2022-4-2647三、電子投票三、電子投票如果是這樣的話，攻擊難以成功。但如果先選定投票內(nèi)容m，然后對(duì)簽名S的值進(jìn)行偽造

25、，則投票人不知道選舉委員會(huì)的私鑰d，無法計(jì)算S。當(dāng)不規(guī)定投票內(nèi)容，或投票內(nèi)容限定值的數(shù)量極大時(shí)，攻擊的成功率就很大。投票人選擇 S，再計(jì)算m=Se(modn)，m就會(huì)以很大的概率“撞進(jìn)”投票內(nèi)容限定的值范圍，此時(shí)攻擊就成功了。2022-4-2648三、電子投票三、電子投票對(duì)協(xié)議的改進(jìn)對(duì)協(xié)議的改進(jìn)改進(jìn)的協(xié)議克服了原來協(xié)議不滿足可驗(yàn)證性的缺陷，并且能夠抵抗投票人攻擊。改進(jìn)的協(xié)議額外使用一個(gè)公開的雜湊函數(shù)H和一個(gè)隨機(jī)數(shù)U，并在協(xié)議中用H(m, U)來代替m。2022-4-2649三、電子投票三、電子投票（一）投票人：按照自己的意愿選擇投票的內(nèi)容m。再隨機(jī)地選擇兩個(gè)整數(shù)R和U，計(jì)算C=ReH(m, U

26、)(modn)。將C連同自己的身份發(fā)送給選舉委員會(huì)。（二）選舉委員會(huì)：檢查投票人的身份：投票人的身份是否符合規(guī)定；投票人先前是否已經(jīng)用過。如果投票人通過了檢驗(yàn)，選舉委員會(huì)將備注“此人的身份已經(jīng)用過”，并簽名T=Cd(modn)。2022-4-2650三、電子投票三、電子投票（三）投票人：計(jì)算S=R-1T(modn)。檢查是否Se(modn)=H(m, U)。若是，則將S作為選舉委員會(huì)對(duì)投票內(nèi)容m的簽名；否則認(rèn)為選舉委員會(huì)在欺騙。（四）投票人：將投票內(nèi)容m，隨機(jī)數(shù)U，簽名S聯(lián)立成簽名消息(m, U, S)。將(m, U, S)發(fā)送給選舉委員會(huì)，完成投票。投票人此時(shí)并不發(fā)送自己的身份，因此選舉委員

27、會(huì)不知道(m, U, S)是誰的投票。2022-4-2651三、電子投票三、電子投票（五）選舉委員會(huì)：檢查是否S=H(m, U)d(modn)。若是，則(m, U, S)是一張誠實(shí)的、經(jīng)過選舉委員會(huì)簽名的選票；否則認(rèn)為投票者在欺騙。驗(yàn)票完成。張榜公布所有的簽名選票。（六）投票人：檢查所有的簽名選票中是否有一張為(m, U, S)。若有，則選舉委員會(huì)對(duì)自己是誠實(shí)的。若沒有，則選舉委員會(huì)在欺騙自己。2022-4-2652三、電子投票三、電子投票（七）附加步驟。投票人：若發(fā)現(xiàn)榜上沒有(m, U, S)，則可以持(m, U, S)質(zhì)詢選舉委員會(huì)，并將(m, U, S)公布于眾。任何人在見到(m, U,

28、 S)后，都可以計(jì)算出Se(modn)=H(m, U)。這就是說，任何人都知道(m, S) 是被選舉委員會(huì)簽名的票。2022-4-2653三、電子投票三、電子投票改進(jìn)的協(xié)議的安全性改進(jìn)的協(xié)議的安全性n合法性：滿足。（與原協(xié)議相同）n唯一性：滿足。（與原協(xié)議相同）n匿名性：滿足。（與原協(xié)議相同）n不可追蹤性：滿足。（與原協(xié)議相同）n可驗(yàn)證性：滿足。當(dāng)投票人發(fā)現(xiàn)榜上沒有(m, U, S)，則將(m, U, S)公布于眾。任何人都可以計(jì)算出Se(modn)=H(m, U)。這樣就向公眾證明了選舉委員會(huì)欺騙。兩個(gè)投票人選擇的投票內(nèi)容m可能相同，但隨機(jī)數(shù)U幾乎不可能相同，因此簽名值S幾乎不可能相同。20

29、22-4-2654三、電子投票三、電子投票n投票人攻擊對(duì)于改進(jìn)的協(xié)議方案：無效。設(shè)投票人試圖要偽造一個(gè)簽名票(m, U, S)， 滿足Se(modn)=H(m, U)。如果投票人先選定了簽名S的值，然后對(duì)(m, U)進(jìn)行偽造，則他面臨著“給定H(m, U)的值，要計(jì)算(m, U)”的任務(wù)。由雜湊函數(shù)的特性，這個(gè)任務(wù)是不可能完成的。如果投票人先選定了(m, U)的值，然后對(duì)簽名S進(jìn)行偽造，則他面臨著“給定H(m, U)的值，要計(jì)算S=(H(m, U)d(modn)”的任務(wù)。由于投票人不知道選舉委員會(huì)的私鑰d，這個(gè)任務(wù)也是不可能完成的。2022-4-2655三、電子投票三、電子投票選舉委員會(huì)進(jìn)行的

30、攻擊選舉委員會(huì)進(jìn)行的攻擊（對(duì)于改進(jìn)的協(xié)議方案來說，）選舉委員會(huì)不能對(duì)一個(gè)真的投票人進(jìn)行假簽名、榜上不公布票。但它卻能偽裝成一個(gè)投票者投票。這是因?yàn)檫x舉委員會(huì)同時(shí)擁有公鑰和私鑰。因此必須用物理手段斷絕選舉委員會(huì)的投票行為，只允許它簽名、驗(yàn)票、張榜公布票。2022-4-2656四、零知識(shí)證明四、零知識(shí)證明概述概述示證者：示證者：P（prover）。驗(yàn)證者：驗(yàn)證者：V（verifier）。P知道某個(gè)秘密；他想讓V相信他知道該秘密。最大泄露證明最大泄露證明：完整地泄露該秘密。最小泄露證明：最小泄露證明： P使用一種證明方法，讓V相信他知道該秘密，但對(duì)該秘密的泄露程度最小。2022-4-2657四、零知

31、識(shí)證明四、零知識(shí)證明最小泄露證明滿足下述條件最小泄露證明滿足下述條件： (1) P無法欺騙V。這就是說，若P真的知道該秘密，則使V確信P知道該秘密；若P不知道該秘密，則他不能使V相信他知道該秘密。 (2) V無法欺騙P。這就是說，在驗(yàn)證/證明過程中，無論P(yáng)怎樣努力都不可能得到該秘密的更多信息。特別是， V不可能向其他人證明P知道該秘密。2022-4-2658四、零知識(shí)證明四、零知識(shí)證明零知識(shí)證明零知識(shí)證明： P使用一種證明方法，讓使用一種證明方法，讓V相信他知相信他知道該秘密，又能保證不泄露該秘密。道該秘密，又能保證不泄露該秘密。即即(1) P無法欺騙V。這就是說， P只有真的知道該秘密，才能

32、使V相信他知道該秘密。(2) V無法欺騙P。這就是說，在驗(yàn)證/證明過程中，無論P(yáng)怎樣努力都只知道“P知道該秘密”，除此以外一無所獲。特別是， V不可能向其他人證明P知道該秘密。2022-4-2659四、零知識(shí)證明四、零知識(shí)證明一般的公鑰加解密不是零知識(shí)證明一般的公鑰加解密不是零知識(shí)證明設(shè)P公布公鑰，他想讓V相信他知道私鑰。V隨機(jī)地取一個(gè)明文m用公鑰加密，將密文c送給P。如果P能夠?qū)正確解密，則V相信P知道私鑰。當(dāng)V將一個(gè)明文m用公鑰加密得到密文c 時(shí)，他實(shí)際上已經(jīng)獲得了私鑰的一條知識(shí)：“私鑰對(duì)c解密會(huì)得到m”。當(dāng)然這條知識(shí)不足為患，但絕對(duì)破壞了零知識(shí)證明的前提條件。2022-4-2660四、

33、零知識(shí)證明四、零知識(shí)證明關(guān)于零知識(shí)證明的若干說明關(guān)于零知識(shí)證明的若干說明驗(yàn)證/證明過程不能由P決定，而應(yīng)該由V決定。V提問（challenge），P回答（reply）。因此零知識(shí)證明是一個(gè)交互證明過程。每一次V向P提問，若P知道秘密則可正確回答V的提問；若P不知道秘密，則對(duì)提問給出正確回答概率僅為1/2。V以足夠多的提問就可推定P是否知道秘密。要保證這些提問及其相應(yīng)的回答不會(huì)泄露秘密。2022-4-2661四、零知識(shí)證明四、零知識(shí)證明 零知識(shí)證明的基本協(xié)議零知識(shí)證明的基本協(xié)議 例例Quisquater等1989 。 A 設(shè)P知道咒語，可打開C和 D之間的秘密門，不知道者 B 都將走向死胡同中。

34、 C D 2022-4-2662四、零知識(shí)證明四、零知識(shí)證明協(xié)議協(xié)議1： (1) V站在洞口A點(diǎn)； (2) P進(jìn)入洞中任一點(diǎn)C或D； (3) 當(dāng)P進(jìn)洞之后，V走到B點(diǎn)； (4) V叫P：(a)從左邊出來，或(b)從右邊出來； (5) P按要求實(shí)現(xiàn)(以咒語，即解數(shù)學(xué)難題幫助)； (6) P和V重復(fù)執(zhí)行 (1)(5)共n次。若A不知咒語，則在B點(diǎn)，只有50 %的機(jī)會(huì)滿足B的要求。協(xié)議執(zhí)行n次，則只有2-n的機(jī)會(huì)完全滿足，若n=16，則若每次均通過B的檢驗(yàn)，B受騙機(jī)會(huì)僅為1/65536。2022-4-2663四、零知識(shí)證明四、零知識(shí)證明此協(xié)議又稱作分割和選擇分割和選擇(Cut and Choose)

35、協(xié)議，是一個(gè)實(shí)現(xiàn)公平分享的經(jīng)典協(xié)議。即其功能等價(jià)于 協(xié)議協(xié)議 2：(1) A將東西切成兩半；(2) B選其中之一；(3) A拿剩下的一半。顯然，A為了自己的利益在(1)中要公平分割，否則(2)中B先于他的的選擇將對(duì)其不利。2022-4-2664四、零知識(shí)證明四、零知識(shí)證明實(shí)現(xiàn)零知識(shí)身份證明的密碼體制實(shí)現(xiàn)零知識(shí)身份證明的密碼體制簡(jiǎn)化簡(jiǎn)化F-F-S識(shí)別體制識(shí)別體制?？尚刨囍俨眠x定一個(gè)隨機(jī)模m=p1p2，m為512 bits或1024 bits。證明者共用此m，仲裁可實(shí)施公鑰私鑰的分配，他產(chǎn)生隨機(jī)數(shù)y，計(jì)算y2=v ，即v為模m的平方剩余，且有v-1 modm。以v作為P的公鑰，而后計(jì)算滿足下式的最

36、小的正整數(shù)s（一定能計(jì)算出?。?，作為P的私鑰分發(fā)給P。mvsmod)/1(2022-4-2665四、零知識(shí)證明四、零知識(shí)證明實(shí)施身份證明的協(xié)議如下。(1) P取隨機(jī)數(shù)r(m)，計(jì)算x= r2 modm，將x送給V。(2) V將一隨機(jī)比特b送給P。(3)若b=0，則P將r送給V；若b=1，則P將y=rs送給V。(4)若b=0，則V證實(shí)x=r2 modm；若b=1，則V證實(shí)x=y2 v modm。P和V可將此協(xié)議重復(fù)t次，直到B相信A知道s為止。2022-4-2666四、零知識(shí)證明四、零知識(shí)證明安全性（一）：安全性（一）： P騙V的可能性注意到動(dòng)作順序是：P將x送給V； V將隨機(jī)比特b送給P； P

37、根據(jù)b=0或b=1將r或y送給V。設(shè)P不知道s。他事先設(shè)計(jì)(x, r)的方法只能是：先選r，后計(jì)算x=r2 modm。他事先設(shè)計(jì)(x, y)的方法只能是：先選y，后計(jì)算x=y2v modm 。他不可能事先設(shè)計(jì)(x, r , y)同時(shí)滿足x=r2 modm 和 x=y2v modm。因此他在協(xié)議中騙V成功的概率為1/2。將此協(xié)議重復(fù)t次， P騙V全部成功的概率為1/2t。2022-4-2667四、零知識(shí)證明四、零知識(shí)證明安全性（二）：安全性（二）： V騙P的可能性設(shè)V騙P以獲取s的信息。注意到在協(xié)議中V的獲得：當(dāng)b=0時(shí)： V獲得(x, r)滿足x=r2 modm；當(dāng)b=1時(shí)： V獲得(x, y

38、)滿足x=y2v modm 。v是公開的。(x, r)或(x, y)除了滿足各自的方程以外，不含有s的任何信息。因此，在協(xié)議中V完全得不到關(guān)于s的任何信息。換句話說，該協(xié)議是一個(gè)零知識(shí)協(xié)議。2022-4-2668五、電子現(xiàn)金支付五、電子現(xiàn)金支付傳統(tǒng)支付與電子支付傳統(tǒng)支付與電子支付電子支付具有以下特征：（1）電子支付是采用全電子化的信息流來控制全電子化的資金流；而傳統(tǒng)支付常常是采用非電子化的信息流（口述、發(fā)票等）來控制實(shí)物化的資金流（現(xiàn)金、支票等）。（2）電子支付的工作環(huán)境是一個(gè)開放的系統(tǒng)平臺(tái)（即因特網(wǎng)），而傳統(tǒng)支付的工作環(huán)境常常是一個(gè)封閉的系統(tǒng)（如收銀臺(tái)）。2022-4-2669五、電子現(xiàn)金支

39、付五、電子現(xiàn)金支付（3）電子支付比傳統(tǒng)支付對(duì)軟硬件設(shè)施的要求高得多。（4）電子支付比傳統(tǒng)支付具有方便、快捷、高效、經(jīng)濟(jì)等方面的優(yōu)勢(shì)。當(dāng)然，這里所說的“經(jīng)濟(jì)”是指在進(jìn)行電子支付時(shí)的費(fèi)用低廉，而不是指建立電子支付系統(tǒng)的成本低廉。通常建立電子支付系統(tǒng)的成本并不低廉，需要大量的設(shè)備。2022-4-2670五、電子現(xiàn)金支付五、電子現(xiàn)金支付（5）電子支付帶來了新的風(fēng)險(xiǎn)。特別是安全問題，一直是困擾電子支付發(fā)展的一個(gè)關(guān)鍵問題。安全問題包括：完整地認(rèn)證客戶，信息完整地傳輸，無拒付的支付，有效的查帳機(jī)制，隱私權(quán)的保護(hù)，可靠的信息服務(wù)。這些安全問題在傳統(tǒng)支付中也存在，但電子支付使得這些安全問題更加突出。（因?yàn)椋弘娮?/p>

40、信息易變更；交易對(duì)象不謀面）2022-4-2671五、電子現(xiàn)金支付五、電子現(xiàn)金支付(電子支付方式共有五種：電子現(xiàn)金；銀行卡；電子支票；電子錢包；智能卡支付方式。)電子現(xiàn)金與真實(shí)現(xiàn)金的比較電子現(xiàn)金與真實(shí)現(xiàn)金的比較電子現(xiàn)金（E-cash），又稱為數(shù)字現(xiàn)金。是一種以數(shù)字形式存在，通過計(jì)算機(jī)網(wǎng)絡(luò)流通的貨幣。電子現(xiàn)金中的“一張鈔票”實(shí)際上是一個(gè)加密序列數(shù)。注意到，真實(shí)的現(xiàn)金有許多優(yōu)點(diǎn)和缺點(diǎn)。那么，從技術(shù)上來說，電子現(xiàn)金能夠繼承真實(shí)現(xiàn)金的這些特點(diǎn)嗎？不妨做以下的比較。2022-4-2672五、電子現(xiàn)金支付五、電子現(xiàn)金支付當(dāng)場(chǎng)可驗(yàn)證性當(dāng)場(chǎng)可驗(yàn)證性真實(shí)現(xiàn)金當(dāng)場(chǎng)可以驗(yàn)證真?zhèn)?，而不需要時(shí)間的等待和任何其它的證明材

41、料。這是因?yàn)?，真?shí)現(xiàn)金本身就被制造成防偽的（雖然防偽標(biāo)志未必完善）。真實(shí)現(xiàn)金的這種當(dāng)場(chǎng)可驗(yàn)證性還說明，鈔票丟失就意味著用戶的錢確實(shí)不再有了。因?yàn)閺脑砩蟻碚f，真實(shí)現(xiàn)金沒有設(shè)置輔助的掛失功能，鈔票本身是唯一的證據(jù)。2022-4-2673五、電子現(xiàn)金支付五、電子現(xiàn)金支付電子現(xiàn)金能夠比較容易地繼承真實(shí)現(xiàn)金的這個(gè)優(yōu)點(diǎn)（或者說，這個(gè)缺點(diǎn)）。加密和認(rèn)證等密碼技術(shù)幫助電子現(xiàn)金比較容易地實(shí)現(xiàn)當(dāng)場(chǎng)可驗(yàn)證性。而且，電子現(xiàn)金的當(dāng)場(chǎng)可驗(yàn)證性比真實(shí)現(xiàn)金的當(dāng)場(chǎng)可驗(yàn)證性更加可靠。由于實(shí)物防偽技術(shù)的局限性，真實(shí)現(xiàn)金始終處在偽造和防偽的斗爭(zhēng)中。而電子現(xiàn)金幾乎是一勞永逸地解決了防偽問題。2022-4-2674五、電子現(xiàn)金支付五、

42、電子現(xiàn)金支付匿名性和不可追蹤性匿名性和不可追蹤性真實(shí)現(xiàn)金在進(jìn)行支付的時(shí)候，接受的一方無法獲取支付的一方的任何身份信息，稱之為匿名性。在支付完成雙方分手以后，接受的一方無法追蹤支付的一方，稱之為不可追蹤性。這兩種性質(zhì)保護(hù)了消費(fèi)者的隱私權(quán)。電子現(xiàn)金可以被設(shè)計(jì)得具有匿名性，也可以被設(shè)計(jì)得具有不可追蹤性。但如果同時(shí)具有這兩種性質(zhì)，則會(huì)給電子商務(wù)帶來極大的威脅。2022-4-2675五、電子現(xiàn)金支付五、電子現(xiàn)金支付為什么這樣說呢？實(shí)際上，真實(shí)現(xiàn)金的支付如果出現(xiàn)了欺騙或犯罪，仍然有蛛絲馬跡可以“追蹤”（面相，聲音，指紋，現(xiàn)金票號(hào)與近期銀行付出的現(xiàn)金票號(hào)之比對(duì)等等）。電子現(xiàn)金的支付如果出現(xiàn)了欺騙或犯罪，而電

43、子現(xiàn)金又同時(shí)具有匿名性和不可追蹤性的話，則犯罪分子將逃脫得無影無蹤。因此，現(xiàn)在一般的電子現(xiàn)金系統(tǒng)都被設(shè)計(jì)成具有匿名性，但必須是在一定條件下可以追蹤的。2022-4-2676五、電子現(xiàn)金支付五、電子現(xiàn)金支付可重復(fù)使用性可重復(fù)使用性真實(shí)現(xiàn)金可以重復(fù)使用。任何人在任何時(shí)候，只要持有一張鈔票，他就有資格把這張鈔票支付給任何其他人。電子現(xiàn)金必須被設(shè)計(jì)成“一次性的”，即使其不能重復(fù)使用。Alice將“一張電子鈔票”付給Bob，則“這張電子鈔票”立即進(jìn)入銀行，結(jié)算后被銷毀。以后如果再見到“這張電子鈔票”，則會(huì)被檢驗(yàn)出是“假鈔”。2022-4-2677五、電子現(xiàn)金支付五、電子現(xiàn)金支付這樣做的原因是，電子現(xiàn)金太

44、容易被復(fù)制了，電子現(xiàn)金太容易被復(fù)制了，復(fù)制的電子現(xiàn)金可以做到不留任何痕跡。復(fù)制的電子現(xiàn)金可以做到不留任何痕跡。實(shí)現(xiàn)“一次性的”電子現(xiàn)金有多種辦法。其中最典型的兩種辦法介紹如下。辦法一：在線電子現(xiàn)金。銀行隨時(shí)監(jiān)視電子現(xiàn)金的支付過程，并設(shè)有數(shù)據(jù)庫存放已經(jīng)使用過的電子現(xiàn)金號(hào)碼。一旦發(fā)現(xiàn)有重復(fù)使用，立即報(bào)警。實(shí)用的電子現(xiàn)金采用這個(gè)辦法。2022-4-2678五、電子現(xiàn)金支付五、電子現(xiàn)金支付辦法二：離線電子現(xiàn)金。銀行并不實(shí)時(shí)地監(jiān)視電子現(xiàn)金的支付過程，支付過程僅僅是用戶向商家支付的過程。而在用戶支付完畢已經(jīng)離開以后，商家才與銀行進(jìn)行資金清算。但電子現(xiàn)金中存有用戶的身份秘密信息，保證：如果用戶按照規(guī)定使用電

45、子現(xiàn)金一次，則用戶的秘密身份不會(huì)被泄露；而如果重復(fù)使用電子現(xiàn)金，則用戶的秘密身份就會(huì)被泄露，因而被追蹤。2022-4-2679五、電子現(xiàn)金支付五、電子現(xiàn)金支付綜合以上可以看出：在線電子現(xiàn)金對(duì)重復(fù)花費(fèi)電子現(xiàn)金的用戶當(dāng)場(chǎng)拒絕，無論如何不會(huì)暴露用戶的秘密身份。離線電子現(xiàn)金對(duì)重復(fù)花費(fèi)電子現(xiàn)金的用戶事后懲罰，但必須事先存儲(chǔ)用戶的秘密身份信息，一旦重復(fù)花費(fèi)，就會(huì)泄露出用戶的身份。在線電子現(xiàn)金比較簡(jiǎn)單，離線電子現(xiàn)金似乎更加人性化。然而離線電子現(xiàn)金違背了“匿名性” 。2022-4-2680五、電子現(xiàn)金支付五、電子現(xiàn)金支付不可分性不可分性真實(shí)現(xiàn)金是不可分割的。一張100元的鈔票不能分為兩張50元的鈔票。彌補(bǔ)此缺

46、陷的方法是“找零錢”。一般的電子現(xiàn)金也是不可分割的。由于對(duì)電子現(xiàn)金“找零錢”非常復(fù)雜，因此一般的電子現(xiàn)金支付時(shí)不“找零錢”，而將電子現(xiàn)金的票面價(jià)值設(shè)計(jì)得盡可能小，以“電子硬幣”形式出現(xiàn)。近年來人們?cè)O(shè)計(jì)了可分割的電子現(xiàn)金，還處在科研階段?？傮w來說，可分割的電子現(xiàn)金成本過高。2022-4-2681五、電子現(xiàn)金支付五、電子現(xiàn)金支付真實(shí)現(xiàn)金與電子現(xiàn)金的比較：真實(shí)現(xiàn)金與電子現(xiàn)金的比較：真實(shí)現(xiàn)金真實(shí)現(xiàn)金電子現(xiàn)金電子現(xiàn)金當(dāng)場(chǎng)可驗(yàn)證性當(dāng)場(chǎng)可驗(yàn)證性匿名性匿名性不可追蹤性不可追蹤性（）（）可重復(fù)使用性可重復(fù)使用性不可分性不可分性（）2022-4-2682五、電子現(xiàn)金支付五、電子現(xiàn)金支付離線電子現(xiàn)金離線電子現(xiàn)金離線

47、電子現(xiàn)金就是可以脫離銀行實(shí)時(shí)監(jiān)視進(jìn)行支付的電子現(xiàn)金，它是目前正在進(jìn)行的科研項(xiàng)目。離線電子現(xiàn)金要保證進(jìn)行支付時(shí)，銀行不在場(chǎng)。支付完畢后，銀行再參與資金清算。一旦發(fā)現(xiàn)重復(fù)使用的電子現(xiàn)金，就能夠追蹤重復(fù)使用者的身份。未重復(fù)使用的電子現(xiàn)金，使用者的身份不會(huì)暴露。2022-4-2683五、電子現(xiàn)金支付五、電子現(xiàn)金支付第和第是很容易保證的。困難在于第。銀行或商家不能預(yù)先獲得顧客的秘密身份信息，必須恰好在顧客兩次花費(fèi)同一個(gè)電子現(xiàn)金之后才能獲得顧客的秘密身份信息。公鑰密碼原理使這個(gè)問題得以解決，解決方案就是Schnorr協(xié)議（為了方便理解，本課程只介紹Schnorr協(xié)議的簡(jiǎn)化版）。在Schnorr協(xié)議的初始化

48、階段，選擇一個(gè)大素?cái)?shù)p，一個(gè)正整數(shù)g。 p和g都被公開。2022-4-2684五、電子現(xiàn)金支付五、電子現(xiàn)金支付設(shè)顧客的身份秘密信息是(m, b)，其中m和b都是正整數(shù)。顧客的身份公開信息是(c, n)，其中c=gb(modp)； n=gm(modp)。Schnorr支付協(xié)議如下。第一步：顧客出示電子現(xiàn)金。電子現(xiàn)金上有其身份公開信息(c, n)。第二步：商家隨機(jī)地選擇一個(gè)正整數(shù)x，發(fā)送給顧客。（詢問）2022-4-2685五、電子現(xiàn)金支付五、電子現(xiàn)金支付第三步：顧客用自己的身份秘密信息(m, b)，計(jì)算：y=mx+b(modp-1)。顧客將y發(fā)送給商家。（回答）第四步：商家用顧客的身份公開信息(c, n)，驗(yàn)證是否有g(shù)y=nxc(modp)。若成立則接受這個(gè)電子現(xiàn)金；否則拒絕接受該電子現(xiàn)金。（檢驗(yàn)）2022-4-2686五、電子現(xiàn)金支付五、電子現(xiàn)金支付Schnorr支付協(xié)議的支付協(xié)議的分