現代密碼學(第六章)

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

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

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

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

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

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

7、某t-1個誠實的參與者組合在一起，計算出h(x)的系數向量是a0, a1, a2, , at-2, at-1。設Eve與另外t-1個誠實的參與者組合在一起，計算出h(x)的系數向量是 a0”, a1”, a2”, , at-2”, at-1”。2022-4-2612一、秘密共享一、秘密共享由于Eve難以由自己的所謂ID(k)求出對應的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”，三個系數向量中

8、的任何兩個向量都很難相互相等。2022-4-2613一、秘密共享一、秘密共享檢測結論（一）檢測結論（一）當某t個參與者組合計算出的系數向量與另外t個參與者組合計算出的系數向量不相等時，這兩次被組合的全部人員中必有“欺騙者”。檢測結論（二）檢測結論（二）當某t個參與者組合計算出的系數向量與另外t個參與者組合計算出的系數向量相等時，（幾乎可以斷定）這兩次被組合的全部人員都是誠實的參與者。2022-4-2614一、秘密共享一、秘密共享習題習題 設：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)。當第1位第3位參與者同時到場，求共享的秘密)17(mod)(2210 xaxaaxh2022-4-2615二、不經意傳輸二、不經意傳輸“不經意傳輸協(xié)議不經意傳輸協(xié)議”的特性的特性（不經意傳輸協(xié)議；（不經意傳輸協(xié)議；Oblivious Transfer；OT）設Alice欲告訴Bob 某個秘密。 Alice使用一個“不經意傳輸協(xié)議”將此秘密發(fā)送給Bob。則發(fā)送/接收過程就具有以下的性質。2022-4-2616二、不經意傳輸二、不經意傳輸（1）Bob能夠獲得此秘密的概率是1/2。換句話說，Bo

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

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

12、取整數x，1xN。令a=x2(modN)。2022-4-2620二、不經意傳輸二、不經意傳輸結果一結果一 已知N，求p和q困難。（大數分解）結果二結果二 a一共有4個(modN)平方根，他們是：x；N-x；y；N-y。即： ax2(N-x)2y2(N-y)2(modN)，且x、N-x、y、N-y互不相等。 4個(modN)平方根的關系如下：設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二、不經意傳輸二、不經意傳輸結果三結果三 （1）如果已知

13、p，q，a，則可以求出a的4個(modN)平方根x，N-x，y，N-y 。（2）如果僅僅已知N，a，則不能求出a的任何一個(modN)平方根。結果四結果四（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結果一2022-4-2623結果二與結果三（2）2022-4-2624結果三（1）2022-4-2625結果四（1）2022-4-2626結果四（2）2022-4-2627二、不經意傳輸二、不經意傳輸Rabin的不經意傳輸協(xié)議的不經意傳

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

41、料。這是因為，真實現金本身就被制造成防偽的（雖然防偽標志未必完善）。真實現金的這種當場可驗證性還說明，鈔票丟失就意味著用戶的錢確實不再有了。因為從原理上來說，真實現金沒有設置輔助的掛失功能，鈔票本身是唯一的證據。2022-4-2673五、電子現金支付五、電子現金支付電子現金能夠比較容易地繼承真實現金的這個優(yōu)點（或者說，這個缺點）。加密和認證等密碼技術幫助電子現金比較容易地實現當場可驗證性。而且，電子現金的當場可驗證性比真實現金的當場可驗證性更加可靠。由于實物防偽技術的局限性，真實現金始終處在偽造和防偽的斗爭中。而電子現金幾乎是一勞永逸地解決了防偽問題。2022-4-2674五、電子現金支付五、

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

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

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

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

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

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

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