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

第六章：密碼技術(shù)應(yīng)用一、秘密共享二、不經(jīng)意傳輸三、電子投票四、零知識(shí)證明五、電子現(xiàn)金支付2023/1/151一、秘密共享“海盜分割藏寶圖”是秘密共享方案的原始模型。設(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è)問(wèn)題的有效方法。在這里，一個(gè)秘密被分成了n份，任何t份并在一起，都能復(fù)原秘密。t被稱為門限值。t≤n。2023/1/152一、秘密共享秘密共享方案有多種用途。比如：遺產(chǎn)的分配與公證。多用戶通信。電子商務(wù)中的各種交易方案。重大決策的控制閥（如核按鈕等）。2023/1/153一、秘密共享例：一個(gè)最簡(jiǎn)單的秘密共享方案設(shè)保險(xiǎn)柜有三把鎖，分別編號(hào)為①、②、③。張三擁有①、②號(hào)鎖的鑰匙。李四擁有①、③號(hào)鎖的鑰匙。王五擁有②、③號(hào)鎖的鑰匙。三個(gè)人中，任何兩個(gè)以上的人同時(shí)到場(chǎng)均可以打開(kāi)保險(xiǎn)柜；任何一個(gè)以下的人到場(chǎng)均打不開(kāi)保險(xiǎn)柜。此處，一個(gè)秘密指的是“①、②、③號(hào)鎖的鑰匙”；n=3（個(gè)人）；門限值t=2（個(gè)人）。2023/1/154一、秘密共享Shamir的秘密共享門限方案選擇一個(gè)大素?cái)?shù)p。選擇一個(gè)t-1次的整系數(shù)多項(xiàng)式h(x)：2023/1/155一、秘密共享設(shè)一共有n個(gè)參與者。設(shè)第k位參與者擁有的公開(kāi)身份名是ID(k)，其中ID(k)是整數(shù)。設(shè)第k位參與者擁有的秘密身份名是h(ID(k))。此處k=1,2,3,…,n。多項(xiàng)式h(x)對(duì)所有參與者保密。換句話說(shuō)，多項(xiàng)式h(x)的系數(shù){a0,a1,a2,…,at-2,at-1}對(duì)所有參與者保密。第k位參與者擁有（ID(k)，h(ID(k))）。其中ID(k)對(duì)其他參與者公開(kāi)，h(ID(k))對(duì)其他參與者保密。此處k=1,2,3,…,n。2023/1/156一、秘密共享多項(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ì)說(shuō)明。2023/1/157一、秘密共享不失一般性,不妨設(shè)第1位~第t位參與者同時(shí)到場(chǎng)，每個(gè)人交出自己的身份名：（ID(k)，h(ID(k))），k=1,2,3,…,t。于是得到了如下的方程組：對(duì)于k=1,2,3,…,t，2023/1/158一、秘密共享即2023/1/159一、秘密共享這是一個(gè)關(guān)于未知系數(shù){a0,a1,a2,…,at-2,at-1}的t元一次方程組（請(qǐng)注意，是模(modp)運(yùn)算的t元一次方程組），有t個(gè)方程，因此容易解出{a0,a1,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è)以下方程，因此無(wú)法唯一地確定h(x)。2023/1/1510一、秘密共享在Shamir秘密共享方案中檢測(cè)“欺騙者”設(shè)有t+1個(gè)以上參與者同時(shí)到場(chǎng)。其中有一個(gè)參與者是“欺騙者”Eve，他出示的是身份名（ID(k)，h(ID(k))）是假的。設(shè)任何t個(gè)誠(chéng)實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量都是真實(shí)的{a0,a1,a2,…,at-2,at-1}。設(shè)Eve與某t-1個(gè)誠(chéng)實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量是{a0’,a1’,a2’,…,at-2’,at-1’}。設(shè)Eve與另外t-1個(gè)誠(chéng)實(shí)的參與者組合在一起，計(jì)算出h(x)的系數(shù)向量是{a0”,a1”,a2”,…,at-2”,at-1”}。2023/1/1511一、秘密共享由于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ù)向量中的任何兩個(gè)向量都很難相互相等。2023/1/1512一、秘密共享檢測(cè)結(jié)論（一）當(dāng)某t個(gè)參與者組合計(jì)算出的系數(shù)向量與另外t個(gè)參與者組合計(jì)算出的系數(shù)向量不相等時(shí)，這兩次被組合的全部人員中必有“欺騙者”。檢測(cè)結(jié)論（二）當(dāng)某t個(gè)參與者組合計(jì)算出的系數(shù)向量與另外t個(gè)參與者組合計(jì)算出的系數(shù)向量相等時(shí)，（幾乎可以斷定）這兩次被組合的全部人員都是誠(chéng)實(shí)的參與者。2023/1/1513一、秘密共享習(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,10)；(ID(4),h(ID(4)))=(4,0)；(ID(5),h(ID(5)))=(5,11)。當(dāng)?shù)?位~第3位參與者同時(shí)到場(chǎng)，求共享的秘密2023/1/1514二、不經(jīng)意傳輸“不經(jīng)意傳輸協(xié)議”的特性（不經(jīng)意傳輸協(xié)議；ObliviousTransfer；OT）設(shè)Alice欲告訴Bob某個(gè)秘密。Alice使用一個(gè)“不經(jīng)意傳輸協(xié)議”將此秘密發(fā)送給Bob。則發(fā)送/接收過(guò)程就具有以下的性質(zhì)。2023/1/1515二、不經(jīng)意傳輸（1）Bob能夠獲得此秘密的概率是1/2。換句話說(shuō)，Bob不能獲得此秘密的概率也是1/2。再換句話說(shuō)，無(wú)論Alice或Bob怎樣努力，只要Alice和Bob使用的是不經(jīng)意傳輸協(xié)議，則Bob成功地獲得秘密的概率就只能是1/2。再換句話說(shuō)，Alice或Bob都無(wú)法影響秘密的成功接收。影響秘密的成功接收的因素只有一個(gè)，那就是概率分布。再換句話說(shuō)，發(fā)/收過(guò)程實(shí)際上就是一個(gè)動(dòng)作：高拋硬幣，落地后正面朝上和反面朝上的概率各占1/2，任何人也無(wú)法干預(yù)落地后的結(jié)果。2023/1/1516二、不經(jīng)意傳輸（2）發(fā)送/接收過(guò)程完結(jié)時(shí)，Alice無(wú)法確知Bob是否得到了秘密。換句話說(shuō)，在發(fā)/收過(guò)程結(jié)束后，Alice仍然僅僅知道：Bob得到秘密和未得到秘密的可能性各占1/2。除此之外，Alice得不到任何新的消息。2023/1/1517二、不經(jīng)意傳輸不經(jīng)意傳輸?shù)膽?yīng)用實(shí)例設(shè)Alice欲向Bob行賄。Bob不愿讓Alice知道自己是否接受了賄賂。而Alice也愿意讓Bob放心，只關(guān)心自己行賄，不愿知道對(duì)方是否受賄。于是他們使用一個(gè)“不經(jīng)意傳輸協(xié)議”傳輸賄金帳號(hào)。這樣，即使發(fā)現(xiàn)Alice行賄，也無(wú)法證明Bob受賄。2023/1/1518二、不經(jīng)意傳輸Rabin的“不經(jīng)意傳輸協(xié)議”

預(yù)備知識(shí)：計(jì)算數(shù)論的一些結(jié)果設(shè)有兩個(gè)大素?cái)?shù)p和q。令N=pq。取整數(shù)x，1<x<N。令a=x2(modN)。2023/1/1519二、不經(jīng)意傳輸結(jié)果一已知N，求p和q困難。（大數(shù)分解）結(jié)果二a一共有4個(gè)(modN)平方根，他們是：x；N-x；y；N-y。即：

a≡x2≡(N-x)2≡y2≡(N-y)2(modN)，且x、N-x、y、N-y互不相等。4個(gè)(modN)平方根的關(guān)系如下：設(shè)x≡u(píng)(modp)，x≡v(modq)；則N-x≡p-u(modp)，N-x≡q-v(modq)；y≡u(píng)(modp)，y≡q-v(modq)；N-y≡p-u(modp)，N-y≡v(modq)。2023/1/1520二、不經(jīng)意傳輸結(jié)果三（1）如果已知{p，q，a}，則可以求出a的4個(gè)(modN)平方根{x，N-x，y，N-y}。（2）如果僅僅已知{N，a}，則不能求出a的任何一個(gè)(modN)平方根。結(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。2023/1/1521結(jié)果一2023/1/1522結(jié)果二與結(jié)果三（2）2023/1/1523結(jié)果三（1）2023/1/1524結(jié)果四（1）2023/1/1525結(jié)果四（2）2023/1/1526二、不經(jīng)意傳輸Rabin的不經(jīng)意傳輸協(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，1<x<N，計(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。2023/1/1527二、不經(jīng)意傳輸（6）Bob收到了Alice發(fā)送的一個(gè)“平方根”z。Bob首先檢查是否z2(modN)=a。若是，則z是a的(modN)平方根；否則說(shuō)明Alice作弊。再根據(jù)結(jié)果四，有：如果z=x，則Bob不能求出p和q；如果z=N-x，則Bob不能求出p和q；如果z≠x，z≠N-x，則Bob可以求出p和q。2023/1/1528二、不經(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。2023/1/1529三、電子投票一般投票所需滿足的安全特性：（1）合法性：只有合格者才能投票；（2）唯一性：一人只能投一次票；（3）匿名性：每個(gè)人投票的內(nèi)容對(duì)他人保密，僅僅提交選舉委員會(huì)；（4）不可追蹤性：一個(gè)人投票的內(nèi)容提交到選舉委員會(huì)后，選舉委員會(huì)無(wú)法由所投的票追蹤到投票人。（5）可驗(yàn)證性：每位投票人都能夠檢驗(yàn)，自己投的票是否被正確地記入。2023/1/1530三、電子投票回憶對(duì)盲簽名的特殊要求：（1）簽名者在對(duì)文件簽名的時(shí)候，“看不見(jiàn)”自己所簽名的文件的內(nèi)容，只能“看見(jiàn)”要求自己簽名的人。（2）簽名者對(duì)文件的“封皮”簽名。該簽名值能夠透過(guò)“封皮”印在文件上，形成對(duì)文件本身的簽名。（3）日后當(dāng)簽名者“看見(jiàn)了”文件的內(nèi)容以及自己對(duì)文件的簽名，簽名者也無(wú)法“回憶起”當(dāng)時(shí)簽名的場(chǎng)景（這份當(dāng)時(shí)是誰(shuí)來(lái)找自己簽名的？等等）2023/1/1531三、電子投票盲簽名電子投票協(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）。2023/1/1532三、電子投票（一）投票人：按照自己的意愿選擇投票的內(nèi)容m。再隨機(jī)地選擇一個(gè)整數(shù)R，計(jì)算C=Rem(modn)。將C連同自己的身份發(fā)送給選舉委員會(huì)。2023/1/1533三、電子投票（二）選舉委員會(huì)：檢查投票人的身份。檢查兩點(diǎn)：①投票人的身份是否符合規(guī)定；②投票人的身份先前是否已經(jīng)用過(guò)。如果投票人通過(guò)了檢驗(yàn)，選舉委員會(huì)將備注“此人的身份已經(jīng)用過(guò)”。然后選舉委員會(huì)進(jìn)行簽名過(guò)程。計(jì)算T=Cd(modn)。將T送還給投票人。（請(qǐng)注意，此時(shí)T=Cd(modn)=(Rem)d(modn)=Rmd(modn)2023/1/1534三、電子投票（三）投票人：計(jì)算S=R-1T(modn)。檢查是否Se(modn)=m。若是，則將S作為選舉委員會(huì)對(duì)投票內(nèi)容m的簽名；否則認(rèn)為選舉委員會(huì)在欺騙。（請(qǐng)注意，如果選舉委員會(huì)是誠(chéng)實(shí)的，即T=Cd(modn)，則必有Se(modn)=(R-1T)e(modn)=(R-1Rmd)e(modn)=m。如果選舉委員會(huì)在欺騙，即T≠Cd(modn)，則Se(modn)≠m。）2023/1/1535三、電子投票（四）投票人：將投票內(nèi)容m與簽名S聯(lián)立成簽名消息(m,S)。將(m,S)發(fā)送給選舉委員會(huì)，完成投票。請(qǐng)注意：投票人此時(shí)并不發(fā)送自己的身份，這就是說(shuō)，選舉委員會(huì)不知道是誰(shuí)在投票。2023/1/1536三、電子投票（五）選舉委員會(huì)：檢查是否S=md(modn)。若是，則(m,S)是一張誠(chéng)實(shí)的、經(jīng)過(guò)選舉委員會(huì)簽名的選票；否則認(rèn)為投票者在欺騙。驗(yàn)票完成。張榜公布所有的簽名選票。2023/1/1537三、電子投票（六）投票人：檢查所有的簽名選票中是否有一張為(m,S)。若有，則該投票人認(rèn)為選舉委員會(huì)對(duì)自己是誠(chéng)實(shí)的。若沒(méi)有，則該投票人認(rèn)為選舉委員會(huì)在欺騙自己。2023/1/1538三、電子投票（七）附加步驟。投票人：若發(fā)現(xiàn)榜上沒(méi)有(m,S)，則可以持(m,S)質(zhì)詢選舉委員會(huì)，并將(m,S)公布于眾。任何人在見(jiàn)到(m,S)后，都可以計(jì)算出Se(modn)=m。這就是說(shuō)，任何人都知道(m,S)是被選舉委員會(huì)簽名的票。選舉委員會(huì)一定敗訴。2023/1/1539三、電子投票S是選舉委員會(huì)對(duì)投票內(nèi)容m的盲簽名。（1）選舉委員會(huì)在對(duì)投票內(nèi)容m進(jìn)行簽名時(shí)，知道了投票人的身份，但并不知道被簽名的投票內(nèi)容m。（2）選舉委員會(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)過(guò)自己簽名的票，而看不見(jiàn)投票人的身份。綜上所述，選舉委員會(huì)不能由選票來(lái)追蹤投票人。2023/1/1540三、電子投票此電子投票方案是否滿足安全特性？合法性：滿足。在方案的第（二）步，選舉委員會(huì)檢查投票人的身份是否符合規(guī)定。唯一性：滿足。在方案的第（二）步，選舉委員會(huì)檢查投票人先前是否已經(jīng)投過(guò)票。2023/1/1541三、電子投票匿名性：滿足。在方案的第（二）步，雖然投票人的身份暴露給了選舉委員會(huì)，但隨機(jī)數(shù)R掩蓋了投票內(nèi)容m，使選舉委員會(huì)不知道該投票人投的什么票。不可追蹤性：滿足。在方案的第（五）步，選舉委員會(huì)僅僅看見(jiàn)簽名票(m,S)，而看不見(jiàn)投票人的身份，也無(wú)法將(m,S)與前面見(jiàn)過(guò)的C聯(lián)系起來(lái)。因此選舉委員會(huì)無(wú)法知道簽名票(m,S)是誰(shuí)投的。2023/1/1542三、電子投票可驗(yàn)證性：不滿足。投票人能夠向別人證明(m,S)是一張被選舉委員會(huì)簽名的合法選票，并且當(dāng)榜上沒(méi)有自己投的票(m,S)時(shí)，提出必勝的訴訟。但是，當(dāng)榜上有(m,S)時(shí)，卻不能說(shuō)明選舉委員會(huì)沒(méi)有欺騙自己。注意到對(duì)投票內(nèi)容m的簽名值是唯一的：

S=md(modn)。別人也可能選擇m為投票內(nèi)容，因此一個(gè)(m,S)有可能是別人投的票。2023/1/1543三、電子投票投票人進(jìn)行的攻擊投票人所擁有的工具：選舉委員會(huì)的公鑰（n，e）。投票人的攻擊方法：利用基本RSA的安全性漏洞。（1）投票人選擇一個(gè)“簽名”S，用選舉委員會(huì)的公鑰（n，e），計(jì)算“投票內(nèi)容”m：m=Se(modn)。2023/1/1544三、電子投票（2）投票人繞過(guò)投票過(guò)程的第（一）、（二）、（三）步，直接進(jìn)入投票過(guò)程的第（四）步，將(m,S)發(fā)送給選舉委員會(huì)，完成投票。由于完成投票時(shí)是不需要顯示身份的，因此投票人既可以無(wú)資格投票，也可以重復(fù)投票。（3）選舉委員會(huì)進(jìn)入投票過(guò)程的第（五）步，驗(yàn)證了S=md(modn)，即認(rèn)定(m,S)是自己簽名的合法票。攻擊成功。2023/1/1545三、電子投票投票人攻擊的局限性注意到投票人是先選定了簽名S的值，然后反過(guò)來(lái)對(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è)人的姓名。2023/1/1546三、電子投票如果是這樣的話，攻擊難以成功。但如果先選定投票內(nèi)容m，然后對(duì)簽名S的值進(jìn)行偽造，則投票人不知道選舉委員會(huì)的私鑰d，無(wú)法計(jì)算S。當(dāng)不規(guī)定投票內(nèi)容，或投票內(nèi)容限定值的數(shù)量極大時(shí)，攻擊的成功率就很大。投票人選擇S，再計(jì)算m=Se(modn)，m就會(huì)以很大的概率“撞進(jìn)”投票內(nèi)容限定的值范圍，此時(shí)攻擊就成功了。2023/1/1547三、電子投票對(duì)協(xié)議的改進(jìn)改進(jìn)的協(xié)議克服了原來(lái)協(xié)議不滿足可驗(yàn)證性的缺陷，并且能夠抵抗投票人攻擊。改進(jìn)的協(xié)議額外使用一個(gè)公開(kāi)的雜湊函數(shù)H和一個(gè)隨機(jī)數(shù)U，并在協(xié)議中用H(m,U)來(lái)代替m。2023/1/1548三、電子投票（一）投票人：按照自己的意愿選擇投票的內(nèi)容m。再隨機(jī)地選擇兩個(gè)整數(shù)R和U，計(jì)算C=ReH(m,U)(modn)。將C連同自己的身份發(fā)送給選舉委員會(huì)。（二）選舉委員會(huì)：檢查投票人的身份：①投票人的身份是否符合規(guī)定；②投票人先前是否已經(jīng)用過(guò)。如果投票人通過(guò)了檢驗(yàn)，選舉委員會(huì)將備注“此人的身份已經(jīng)用過(guò)”，并簽名T=Cd(modn)。2023/1/1549三、電子投票（三）投票人：計(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ā)送自己的身份，因此選舉委員會(huì)不知道(m,U,S)是誰(shuí)的投票。2023/1/1550三、電子投票（五）選舉委員會(huì)：檢查是否S=H(m,U)d(modn)。若是，則(m,U,S)是一張誠(chéng)實(shí)的、經(jīng)過(guò)選舉委員會(huì)簽名的選票；否則認(rèn)為投票者在欺騙。驗(yàn)票完成。張榜公布所有的簽名選票。（六）投票人：檢查所有的簽名選票中是否有一張為(m,U,S)。若有，則選舉委員會(huì)對(duì)自己是誠(chéng)實(shí)的。若沒(méi)有，則選舉委員會(huì)在欺騙自己。2023/1/1551三、電子投票（七）附加步驟。投票人：若發(fā)現(xiàn)榜上沒(méi)有(m,U,S)，則可以持(m,U,S)質(zhì)詢選舉委員會(huì)，并將(m,U,S)公布于眾。任何人在見(jiàn)到(m,U,S)后，都可以計(jì)算出Se(modn)=H(m,U)。這就是說(shuō)，任何人都知道(m,S)是被選舉委員會(huì)簽名的票。2023/1/1552三、電子投票改進(jìn)的協(xié)議的安全性合法性：滿足。（與原協(xié)議相同）唯一性：滿足。（與原協(xié)議相同）匿名性：滿足。（與原協(xié)議相同）不可追蹤性：滿足。（與原協(xié)議相同）可驗(yàn)證性：滿足。當(dāng)投票人發(fā)現(xiàn)榜上沒(méi)有(m,U,S)，則將(m,U,S)公布于眾。任何人都可以計(jì)算出Se(modn)=H(m,U)。這樣就向公眾證明了選舉委員會(huì)欺騙。兩個(gè)投票人選擇的投票內(nèi)容m可能相同，但隨機(jī)數(shù)U幾乎不可能相同，因此簽名值S幾乎不可能相同。2023/1/1553三、電子投票投票人攻擊對(duì)于改進(jìn)的協(xié)議方案：無(wú)效。設(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ù)也是不可能完成的。2023/1/1554三、電子投票選舉委員會(huì)進(jìn)行的攻擊（對(duì)于改進(jìn)的協(xié)議方案來(lái)說(shuō)，）選舉委員會(huì)不能對(duì)一個(gè)真的投票人進(jìn)行假簽名、榜上不公布票。但它卻能偽裝成一個(gè)投票者投票。這是因?yàn)檫x舉委員會(huì)同時(shí)擁有公鑰和私鑰。因此必須用物理手段斷絕選舉委員會(huì)的投票行為，只允許它簽名、驗(yàn)票、張榜公布票。2023/1/1555四、零知識(shí)證明概述示證者：P（prover）。驗(yàn)證者：V（verifier）。P知道某個(gè)秘密；他想讓V相信他知道該秘密。最大泄露證明：完整地泄露該秘密。最小泄露證明：P使用一種證明方法，讓V相信他知道該秘密，但對(duì)該秘密的泄露程度最小。2023/1/1556四、零知識(shí)證明最小泄露證明滿足下述條件：(1)P無(wú)法欺騙V。這就是說(shuō)，若P真的知道該秘密，則使V確信P知道該秘密；若P不知道該秘密，則他不能使V相信他知道該秘密。(2)V無(wú)法欺騙P。這就是說(shuō)，在驗(yàn)證/證明過(guò)程中，無(wú)論P(yáng)怎樣努力都不可能得到該秘密的更多信息。特別是，V不可能向其他人證明P知道該秘密。2023/1/1557四、零知識(shí)證明零知識(shí)證明：P使用一種證明方法，讓V相信他知道該秘密，又能保證不泄露該秘密。即(1)P無(wú)法欺騙V。這就是說(shuō)，P只有真的知道該秘密，才能使V相信他知道該秘密。(2)V無(wú)法欺騙P。這就是說(shuō)，在驗(yàn)證/證明過(guò)程中，無(wú)論P(yáng)怎樣努力都只知道“P知道該秘密”，除此以外一無(wú)所獲。特別是，V不可能向其他人證明P知道該秘密。2023/1/1558四、零知識(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í)證明的前提條件。2023/1/1559四、零知識(shí)證明關(guān)于零知識(shí)證明的若干說(shuō)明①驗(yàn)證/證明過(guò)程不能由P決定，而應(yīng)該由V決定。V提問(wèn)（challenge），P回答（reply）。因此零知識(shí)證明是一個(gè)交互證明過(guò)程。②每一次V向P提問(wèn)，若P知道秘密則可正確回答V的提問(wèn)；若P不知道秘密，則對(duì)提問(wèn)給出正確回答概率僅為1/2。V以足夠多的提問(wèn)就可推定P是否知道秘密。③要保證這些提問(wèn)及其相應(yīng)的回答不會(huì)泄露秘密。2023/1/1560四、零知識(shí)證明

零知識(shí)證明的基本協(xié)議

例[Quisquater等1989]。

A設(shè)P知道咒語(yǔ)，可打開(kāi)C和

D之間的秘密門，不知道者

B都將走向死胡同中。

CD

2023/1/1561四、零知識(shí)證明協(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)從左邊出來(lái)，或(b)從右邊出來(lái)；(5)P按要求實(shí)現(xiàn)(以咒語(yǔ)，即解數(shù)學(xué)難題幫助)；(6)P和V重復(fù)執(zhí)行(1)～(5)共n次。若A不知咒語(yǔ)，則在B點(diǎn)，只有50%的機(jī)會(huì)滿足B的要求。協(xié)議執(zhí)行n次，則只有2-n的機(jī)會(huì)完全滿足，若n=16，則若每次均通過(guò)B的檢驗(yàn)，B受騙機(jī)會(huì)僅為1/65536。2023/1/1562四、零知識(shí)證明此協(xié)議又稱作分割和選擇(CutandChoose)協(xié)議，是一個(gè)實(shí)現(xiàn)公平分享的經(jīng)典協(xié)議。即其功能等價(jià)于協(xié)議2：(1)A將東西切成兩半；(2)

B選其中之一；(3)A拿剩下的一半。顯然，A為了自己的利益在(1)中要公平分割，否則(2)中B先于他的的選擇將對(duì)其不利。2023/1/1563四、零知識(shí)證明實(shí)現(xiàn)零知識(shí)身份證明的密碼體制簡(jiǎn)化F-F-S識(shí)別體制?？尚刨囍俨眠x定一個(gè)隨機(jī)模m=p1×p2，m為512bits或1024bits。證明者共用此m，仲裁可實(shí)施公鑰私鑰的分配，他產(chǎn)生隨機(jī)數(shù)y，計(jì)算y2=v，即v為模m的平方剩余，且有v-1modm。以v作為P的公鑰，而后計(jì)算滿足下式的最小的正整數(shù)s（一定能計(jì)算出?。?，作為P的私鑰分發(fā)給P。2023/1/1564四、零知識(shí)證明實(shí)施身份證明的協(xié)議如下。(1)P取隨機(jī)數(shù)r(<m)，計(jì)算x=r2modm，將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=r2modm；若b=1，則V證實(shí)x=y2·vmodm。P和V可將此協(xié)議重復(fù)t次，直到B相信A知道s為止。2023/1/1565四、零知識(shí)證明安全性（一）：P騙V的可能性注意到動(dòng)作順序是：P將x送給V；V將隨機(jī)比特b送給P；P根據(jù)b=0或b=1將r或y送給V。設(shè)P不知道s。他事先設(shè)計(jì)(x,r)的方法只能是：先選r，后計(jì)算x=r2modm。他事先設(shè)計(jì)(x,y)的方法只能是：先選y，后計(jì)算x=y2vmodm。他不可能事先設(shè)計(jì)(x,r,y)同時(shí)滿足x=r2modm和x=y2vmodm。因此他在協(xié)議中騙V成功的概率為1/2。將此協(xié)議重復(fù)t次，P騙V全部成功的概率為1/2t。2023/1/1566四、零知識(shí)證明安全性（二）：V騙P的可能性設(shè)V騙P以獲取s的信息。注意到在協(xié)議中V的獲得：當(dāng)b=0時(shí)：V獲得(x,r)滿足x=r2modm；當(dāng)b=1時(shí)：V獲得(x,y)滿足x=y2vmodm。v是公開(kāi)的。(x,r)或(x,y)除了滿足各自的方程以外，不含有s的任何信息。因此，在協(xié)議中V完全得不到關(guān)于s的任何信息。換句話說(shuō)，該協(xié)議是一個(gè)零知識(shí)協(xié)議。2023/1/1567五、電子現(xiàn)金支付傳統(tǒng)支付與電子支付電子支付具有以下特征：（1）電子支付是采用全電子化的信息流來(lái)控制全電子化的資金流；而傳統(tǒng)支付常常是采用非電子化的信息流（口述、發(fā)票等）來(lái)控制實(shí)物化的資金流（現(xiàn)金、支票等）。（2）電子支付的工作環(huán)境是一個(gè)開(kāi)放的系統(tǒng)平臺(tái)（即因特網(wǎng)），而傳統(tǒng)支付的工作環(huán)境常常是一個(gè)封閉的系統(tǒng)（如收銀臺(tái)）。2023/1/1568五、電子現(xiàn)金支付（3）電子支付比傳統(tǒng)支付對(duì)軟硬件設(shè)施的要求高得多。（4）電子支付比傳統(tǒng)支付具有方便、快捷、高效、經(jīng)濟(jì)等方面的優(yōu)勢(shì)。當(dāng)然，這里所說(shuō)的“經(jīng)濟(jì)”是指在進(jìn)行電子支付時(shí)的費(fèi)用低廉，而不是指建立電子支付系統(tǒng)的成本低廉。通常建立電子支付系統(tǒng)的成本并不低廉，需要大量的設(shè)備。2023/1/1569五、電子現(xiàn)金支付（5）電子支付帶來(lái)了新的風(fēng)險(xiǎn)。特別是安全問(wèn)題，一直是困擾電子支付發(fā)展的一個(gè)關(guān)鍵問(wèn)題。安全問(wèn)題包括：完整地認(rèn)證客戶，信息完整地傳輸，無(wú)拒付的支付，有效的查帳機(jī)制，隱私權(quán)的保護(hù)，可靠的信息服務(wù)。這些安全問(wèn)題在傳統(tǒng)支付中也存在，但電子支付使得這些安全問(wèn)題更加突出。（因?yàn)椋弘娮有畔⒁鬃兏唤灰讓?duì)象不謀面）2023/1/1570五、電子現(xiàn)金支付(電子支付方式共有五種：電子現(xiàn)金；銀行卡；電子支票；電子錢包；智能卡支付方式。)電子現(xiàn)金與真實(shí)現(xiàn)金的比較電子現(xiàn)金（E-cash），又稱為數(shù)字現(xiàn)金。是一種以數(shù)字形式存在，通過(guò)計(jì)算機(jī)網(wǎng)絡(luò)流通的貨幣。電子現(xiàn)金中的“一張鈔票”實(shí)際上是一個(gè)加密序列數(shù)。注意到，真實(shí)的現(xiàn)金有許多優(yōu)點(diǎn)和缺點(diǎn)。那么，從技術(shù)上來(lái)說(shuō)，電子現(xiàn)金能夠繼承真實(shí)現(xiàn)金的這些特點(diǎn)嗎？不妨做以下的比較。2023/1/1571五、電子現(xiàn)金支付當(dāng)場(chǎng)可驗(yàn)證性真實(shí)現(xiàn)金當(dāng)場(chǎng)可以驗(yàn)證真?zhèn)?，而不需要時(shí)間的等待和任何其它的證明材料。這是因?yàn)?，真?shí)現(xiàn)金本身就被制造成防偽的（雖然防偽標(biāo)志未必完善）。真實(shí)現(xiàn)金的這種當(dāng)場(chǎng)可驗(yàn)證性還說(shuō)明，鈔票丟失就意味著用戶的錢確實(shí)不再有了。因?yàn)閺脑砩蟻?lái)說(shuō)，真實(shí)現(xiàn)金沒(méi)有設(shè)置輔助的掛失功能，鈔票本身是唯一的證據(jù)。2023/1/1572五、電子現(xiàn)金支付電子現(xiàn)金能夠比較容易地繼承真實(shí)現(xiàn)金的這個(gè)優(yōu)點(diǎn)（或者說(shuō)，這個(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)金幾乎是一勞永逸地解決了防偽問(wèn)題。2023/1/1573五、電子現(xiàn)金支付匿名性和不可追蹤性真實(shí)現(xiàn)金在進(jìn)行支付的時(shí)候，接受的一方無(wú)法獲取支付的一方的任何身份信息，稱之為匿名性。在支付完成雙方分手以后，接受的一方無(wú)法追蹤支付的一方，稱之為不可追蹤性。這兩種性質(zhì)保護(hù)了消費(fèi)者的隱私權(quán)。電子現(xiàn)金可以被設(shè)計(jì)得具有匿名性，也可以被設(shè)計(jì)得具有不可追蹤性。但如果同時(shí)具有這兩種性質(zhì)，則會(huì)給電子商務(wù)帶來(lái)極大的威脅。2023/1/1574五、電子現(xiàn)金支付為什么這樣說(shuō)呢？實(shí)際上，真實(shí)現(xiàn)金的支付如果出現(xiàn)了欺騙或犯罪，仍然有蛛絲馬跡可以“追蹤”（面相，聲音，指紋，現(xiàn)金票號(hào)與近期銀行付出的現(xiàn)金票號(hào)之比對(duì)等等）。電子現(xiàn)金的支付如果出現(xiàn)了欺騙或犯罪，而電子現(xiàn)金又同時(shí)具有匿名性和不可追蹤性的話，則犯罪分子將逃脫得無(wú)影無(wú)蹤。因此，現(xiàn)在一般的電子現(xiàn)金系統(tǒng)都被設(shè)計(jì)成具有匿名性，但必須是在一定條件下可以追蹤的。2023/1/1575五、電子現(xiàn)金支付可重復(fù)使用性真實(shí)現(xiàn)金可以重復(fù)使用。任何人在任何時(shí)候，只要持有一張鈔票，他就有資格把這張鈔票支付給任何其他人。電子現(xiàn)金必須被設(shè)計(jì)成“一次性的”，即使其不能重復(fù)使用。Alice將“一張電子鈔票”付給Bob，則“這張電子鈔票”立即進(jìn)入銀行，結(jié)算后被銷毀。以后如果再見(jiàn)到“這張電子鈔票”，則會(huì)被檢驗(yàn)出是“假鈔”。2023/1/1576五、電子現(xiàn)金支付這樣做的原因是，電子現(xiàn)金太容易被復(fù)制了，復(fù)制的電子現(xiàn)金可以做到不留任何痕跡。實(shí)現(xiàn)“一次性的”電子現(xiàn)金有多種辦法。其中最典型的兩種辦法介紹如下。辦法一：在線電子現(xiàn)金。銀行隨時(shí)監(jiān)視電子現(xiàn)金的支付過(guò)程，并設(shè)有數(shù)據(jù)庫(kù)存放已經(jīng)使用過(guò)的電子現(xiàn)金號(hào)碼。一旦發(fā)現(xiàn)有重復(fù)使用，立即報(bào)警。實(shí)用的電子現(xiàn)金采用這個(gè)辦法。2023/1/1577五、電子現(xiàn)金支付辦法二：離線電子現(xiàn)金。銀行并不實(shí)時(shí)地監(jiān)視電子現(xiàn)金的支付過(guò)程，支付過(guò)程僅僅是用戶向商家支付的過(guò)程。而在用戶支付完畢已經(jīng)離開(kāi)以后，商家才與銀行進(jìn)行資金清算。但電子現(xiàn)金中存有用戶的身份秘密信息，保證：如果用戶按照規(guī)定使用電子現(xiàn)金一次，則用戶的秘密身份不會(huì)被泄露；而如果重復(fù)使用電子現(xiàn)金，則用戶的秘密身份就會(huì)被泄露，因而被追蹤。2023/1/1578五、電子現(xiàn)金支付綜合以上可以看出：在線電子現(xiàn)金對(duì)重復(fù)花費(fèi)電子現(xiàn)金的用戶當(dāng)場(chǎng)拒絕，無(wú)論如何不會(huì)暴露用戶的秘密身份。離線電子現(xiàn)金對(duì)重復(fù)花費(fèi)電子現(xiàn)金的用戶事后懲罰，但必須事先存儲(chǔ)用戶的秘密身份信息，一旦重復(fù)花費(fèi)，就會(huì)泄露出用戶的身份。在線電子現(xiàn)金比較簡(jiǎn)單，離線電子現(xiàn)金似乎更加人性化。然而離線電子現(xiàn)金違背了“匿名性”。2023/1/1579五、電子現(xiàn)金支付不可分性真實(shí)現(xiàn)金是不可分割的。一張100元的鈔票不能分為兩張50元的鈔票。彌補(bǔ)此缺陷的方法是“找零錢”。一般的電子現(xiàn)金也是不可分割的。由于對(duì)電子現(xiàn)金“找零錢”非常復(fù)雜，因此一般的電子現(xiàn)金支付時(shí)不“找零錢”，而將電子現(xiàn)金的票面價(jià)值設(shè)計(jì)得盡可能小，以“電子硬幣”形式出現(xiàn)。近年來(lái)人們?cè)O(shè)計(jì)了可分割的電子現(xiàn)金，還處在科研階段?？傮w來(lái)說(shuō)，可分割的電子現(xiàn)金成本過(guò)高。2023/1/1580五、電子現(xiàn)金支付真實(shí)現(xiàn)金與電子現(xiàn)金的比較：真實(shí)現(xiàn)金電子現(xiàn)金當(dāng)場(chǎng)可驗(yàn)證性√√匿名性√√不可追蹤性√（×）√（×）可重復(fù)使用性√×不可分性√√（×）2023/1/1581五、電子現(xiàn)金支付離線電子現(xiàn)金離線電子現(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ì)暴露。2023/1/1582五、電子現(xiàn)金支付第①和第②是很容易保證的。困難在于第③。銀行或商家不能預(yù)先獲得顧客的秘密身份信息，必須恰好在顧客兩次花費(fèi)同一個(gè)電子現(xiàn)金之后才能獲得顧客的秘密身份信息。公鑰密碼原理使這個(gè)問(wèn)題得以解決，解決方案就是Schnorr協(xié)議（為了方便理解，本課程只介紹Schnorr協(xié)議的簡(jiǎn)化版）。在Schnorr協(xié)議的初始化階段，選擇一個(gè)大素?cái)?shù)p，一個(gè)正整數(shù)g。p和g都被公開(kāi)。2023/1/1583五、電子現(xiàn)金支付設(shè)顧客的身份秘密信息是(m,b)，其中m和b都是正整數(shù)。顧客的身份公開(kāi)信息是(c,n)，其中c=gb(modp)；n=gm(modp)。Schnorr支付協(xié)議如下。第一步：顧客出示電子現(xiàn)金。電子現(xiàn)金上有其身份公開(kāi)信息(c,n)。第二步：商家隨機(jī)地選擇一個(gè)正整數(shù)x，發(fā)送給顧客。（詢問(wèn)）2023/1/1584五、電子現(xiàn)金支付第三步：顧客用自己的身份秘密信息(m,b)，計(jì)算：y=mx+b(modp-1)。顧客將y發(fā)送給商家。（回答）第四步：商家用顧客的身份公開(kāi)信息(c,n)，驗(yàn)證是否有g(shù)y=nxc(modp)。若成立則接受這個(gè)電子現(xiàn)金；否則拒絕接受該電子現(xiàn)金。（檢驗(yàn)）2023/1/1585五、電子現(xiàn)金支付Schnorr支付協(xié)議的分析結(jié)果一：知道身份秘密信息(m,b)