第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等

第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等
三、特殊用途的数字签字四、数字签字体制中的潜信道五、身份证明的基本概念六、通行字认证系统七、利用个人特征的身份证明技术八、零知识证明技术九、灵巧卡技术 2018/12/5

第七讲：数字签字与身份证明数字签字：数字签字在信息安全，包括身份认证、数据完整性、不可否认性以及匿名性等方面有重要应用，特别是在大型网络安全通信中的密钥分配、认证以及电子商务系统中具有重要作用。数字签字是实现认证的重要工具。身份证明：在一个有竞争和争斗的现实社会中，身份欺诈是不可避免的，因此常常需要证明个人的身份。传统的身份证明一般靠人工的识别，正逐步由机器代替。在信息化社会中，随着信息业务的扩大，要求验证的对象集合也迅速加大，因而大大增加了身份验证的复杂性和实现的困难性。如何以数字化方式实现安全、准确、高效和低成本的认证？本章将讨论几种可能的技术。 2018/12/5

第七讲：数字签字与身份证明一、数字签字基本概念
数字签字应满足的要求： ① 收方能够确认或证实发方的签字，但不能伪造，简记为R1-条件。 ②发方发出签字的消息给收方后，就不能再否认他所签发的消息，简记为S-条件。 ③收方对已收到的签字消息不能否认，即有收报认证，简记作R2- 条件。 ④ 第三者可以确认收发双方之间的消息传送，但不能伪造这一过程，简记作T-条件。 2018/12/5

与手书签字的区别：手书签字是模拟的，且因人而异。数字签字是0和1的数字串，因消息而异。与消息认证的的区别：消息认证使收方能验证消息发送者及所发消息内容是否被窜改过。当收者和发者之间有利害冲突时，就无法解决他们之间的纠纷，此时须借助满足前述要求的数字签字技术。安全的数字签字实现的条件：发方必须向收方提供足够的非保密信息，以便使其能验证消息的签字;但又不能泄露用于产生签字的机密信息，以防止他人伪造签字。此外，还有赖于仔细设计的通信协议。 2018/12/5

数字签字的种类：（1）对整体消息的签字（2）对压缩消息的签字。每一种中又可分为两个子类： (a)确定性(Deterministic)数字签字，其明文与密文一一对应，它对一特定消息的签字不变化，如RSA、Rabin等签字； (b) 随机化的(Randomized)或概率式数字签字。 2018/12/5

签字体制的组成：签字体制=(M , S , K , V) M:明文空间， S:签字的集合， K:密钥空间， V :证实函数的值域，由真、伪组成。 (1) 签字算法：对每一MM和每一kK，易于计算对M的签字 S=Sigk(M)S (7—1—1) 签字算法或签字密钥是秘密的，只有签字人掌握； (2)验证算法： Verk(S, M){真，伪}={0，1} (7—1—2) 2018/12/5

(7—1—3) 证实算法应当公开，已知M，S易于证实S是否为M的签字，以便于他人进行验证。体制的安全性：从M和其签字S难于推出K或伪造一个M’使M’ 和S可被证实为真。与消息加密不同点：消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一个签字的消息可能作为一个法律上的文件，如合同等，很可能在对消息签署多年之后才验证其签字，且可能需要多次验证此签字。 2018/12/5

第七讲：数字签字与身份证明二、几种常用的数字签字
1. RSA签字体制。 (1) 体制参数：令n=p1p2，p1和p2是大素数，令M=C=Zn，选 e并计算出d使ed1 mod (n)，公开n和e，将p1,p2和d保密。 K=(n,p,q,e,d)。 (2) 签字过程：对消息M Zn的签字 S=Sigk(M)=Md mod n (7—2—1) (3) 验证过程：对给定的M和 S，可按下式验证： Verk(M, S)=真  MSe mod n (7—2—2) (4) 安全性：由于只有签字者知道d，由RSA体制知，其他人不能伪造签名，但可易于证实所给任意M，S对是否消息M 和相应签字构成的合法对。 2018/12/5

(5) 标准化：ISO/IEC 9796和ANSI X X已将RSA作为建议数字签字标准算法。PKCS #1是一种采用杂凑算法(如MD2或MD5等)和RSA相结合的公钥密码标准。 2. ElGamal签字体制。由T.ElGamal在1985年给出，是Rabin体制的一种变型。 (1) 体制参数 p：一个大素数，可使Zp中求解离散对数为困难问题； g：是Zp中乘群Zp*的一个生成元或本原元素； M：消息空间，为Zp*； S：签字空间，为Zp*×Zp－1； x：用户秘密钥xZp*； ygx mod p (7—4—1) 密钥：K=(p, g, x, y)，其中p，g，y为公钥，x为秘密钥。 2018/12/5

(2) 签字过程：给定消息M，发端用户进行下述工作。 (a) 选择秘密随机数k,满足0<k<p-1,且(k, p-1)=1； (b) 计算： H(M), r=gk mod p (7—4—2) s=(H(M)－xr)k-1 mod (p－1) (7—4—3) (c) 将Sigk(M, k) =S=(r||s)作为签字，将M，(r||s)送给对方。 (3) 验证过程：收信人收到M，(r||s)，先计算H(M)，并按下式验证 Verk(H(M), r, s)=真  yrrsgH(M) mod p (7—4—4) 这是因为yrrsgrxgskg(rx+sk) mod p，由(7-4-3)式有 (rx+sk) H(M) mod(p－1) (7—4—5) 故有 yrrsgH(M) mod p (7—4—6) 2018/12/5

在此方案中，对同一消息M，由于随机数k不同而有不同的签字值S=(r||s)。它是一种非确定性的双钥体制。例选p=467, g=2, x=127则有ygx2127132 mod 467。若待送消息为M，其杂凑值为H(M)=100，选随机数k=213(注意： (213,466)=1且213-1 mod 466=431)，则有r221329 mod 467。s(100－ 127×29)43151 mod 466。验证：收信人先算出H(M)=100，而后验证 189 mod 467， 2100189 mod 467。 (4) 安全性。方案的安全性基于求离散对数的困难性。  不知明文密文对攻击。攻击者不知用户秘密钥x下，若想伪造用户的签字，可选r的一个值，然后试验相应s取值。 2018/12/5

为此必须计算logrgH(M)y-r。也可先选一个s的取值，而后求出相应r的取值，试验在不知r条件下分解方程 yrrsabgM mod p 这些都是离散对数问题。至于能否同时选出a和b，然后解出相应M，这仍面临求离散对数问题，即需计算loggyrrs。  已知明文密文对攻击。假定攻击者已知(r||s)是消息M的合法签字。令h, i, j是整数，其中h  0, i, jp－2，且(hr－js， p－1)=1。攻击者可计算 r’=rhyi mod p (7—4—7) s’=s(hr－js)-1 mod (p－1) (7—4—8) M’=(hM＋is)(hr－js)-1 mod (p－1) (7—4—9) 2018/12/5

则(r’||s’)是消息M’的合法签字。但这里的消息M’并非由攻击者选择的利于他的消息。如果攻击者要对其选定的消息得到相应的合法签字，仍然面临解离散对数问题。如果攻击者掌握了同一随机数r下的两个消息M1和M2合法签字 (r||s1)和(r||s2)，则由 H(M1)=s1k＋xr mod p－ (7—4—10) H(M2)=s2k＋xr mod p－ (7—4—11) 就可以解出用户的秘密钥x。在实用中，对每个消息的签字，都应变换随机数k。而且对某消息M签字所用的随机数k不能泄露，否则将可由式(7-9-5)解出用户的秘密钥x。 2018/12/5

(5) 应用：其修正形式已被美国NIST作为数字签字标准DSS。此体制专门设计作为签字用。ANSI X X已将ElGamal签字体制作为签字标准算法。 2018/12/5

3. Schnorr签字体制。C. Schnorr于1989年提出。 (1) 体制参数 p, q：大素数，q|p-1，q是大于等于160 bits的整数，p是大于等于512 bits的整数，保证Zp中求解离散对数困难； g：Zp*中元素，且gq1 mod p； x：用户密钥1<x<q； y：用户公钥ygx mod p。消息空间M=Zp*，签字空间S=Zp*×Zq；密钥空间 K={(p,q,g,x,y): ygx mod p} (7—5—1) (2) 签字过程：令待签消息为M，对给定的M做下述运算： (a) 发用户任选一秘密随机数kZq 。 2018/12/5

(b) 计算 rgk mod p (7—5—2) sk＋xe mod q (7—5—3) 式中 e=H(r||M) (7—5—4) (c) 将消息M及其签字S=Sigk(M)=(e||s)送给收信人。 (3) 验证过程：收信人收到消息M及签字S=(e||s)后， (a) 计算 r’gsy-e mod p (7—5—5) 而后计算H(r’||M)。 (b) 验证 Ver(M, r, s)  H(r’||M)=e (7—5—6) 因为，若(e||s)是M的合法签字，则有gsyegk+xeg-xegkr mod p，(7-5-6)等号必成立。 2018/12/5

(4) Schnorr签字与ElGamal签字的不同点：  在ElGamal体制中，g为Z*p的本原元素；而在Schnorr体制中，g为Zp*中子集Zq*的本原元素，它不是Zp*的本原元素。显然ElGamal的安全性要高于Schnorr。  Schnorr的签字较短，由|q|及|H(M)|决定。  在Schnorr签字中，r=gk mod p可以预先计算，k与M无关，因而签字只需一次mod q乘法及减法。所需计算量少，速度快，适用于灵巧卡采用。 2018/12/5

4. DSS签字体制。DSS (Digital Signature Standard)签字标准是1991年8月由美国NIST公布、1994年5月19日正式公布，1994年12月1日正式采用的美国联邦信息处理标准。其中，采用了第6章中介绍的SHA，其安全性基于解离散对数困难性，它是在ElGamal和Schnorr (1991)两个方案基础上设计的DSS中所采用的算法简记为DSA(Digital Signature Algorithm)。此算法由D. W. Kravitz设计。这类签字标准具有较大的兼容性和适用性，已成为网中安全体系的基本构件之一。 (1) 签字和验证签字的基本框图(图7-6-1) 2018/12/5

M ‖ M h EKus(h(M)) 比较 (a) h E D (RSA或LUC) KUS KUP M ‖ M h KUG KUS s KUG KUP (b) r (DSS) h 签字证实比较 M：消息，E：加密，D：解密， k：随机数，KUS：用户秘密钥， KUP：用户公开钥，KUG：部分或全局用户公钥。 2018/12/5

(2) 算法描述: (a) 全局公钥( p, q, g )， p：是2L-1 < p < 2L中的大素数，512  L  1024，按64 bits递增； q：(p－1)的素因子，且2159 < q < 2160，即字长160 bits；g：= hp-1 mod p，且1< h < (p－1)，使h(p-1)/q mod p >1。 (b) 用户秘密钥 x：x为在0<x<q内的随机或拟随机数。 (c) 用户公钥 y：=g x mod p。 (d) 用户每个消息用的秘密随机数k：在0<k<q内的随机或拟随机数。 (e) 签字过程：对消息MM=Zp*，其签字为 S=Sigk(M, k)=(r, s) (7—6—1) 2018/12/5

其中，SS=Zq×Zq, r(gk mod p) mod q (7—6—2) s[k-1 (h(M)＋xr)] mod q (7—6—3) (f) 验证过程：计算 w=s-1 mod q ; u1 =[H(M)w] mod q ; u2=rw mod q ; v=[(gu1yu2) mod p] mod q。 Ver(M, r, s)=真  v=r (7—6—4) (3) DSS签字、验证框图 2018/12/5

p q g r f2 M h y q g k s q r f f4 M f s v h 比较 (a). 签字 (b). 证实图 DSS签字和验证框图 (a).签字，(b).证实 2018/12/5

(4) 公众反应：RSA Data Security Inc(DSI)想以RSA算法做为标准，因而对此反应强烈。在标准公布之前就指出采用公用模可能使政府能够进行伪造签字。许多大的软件公司早已得到RSA的许可证而反对DSS。主要批评意见有：① DSA不能用于加密或密钥分配；② DSA由NSA开发的，算法中可能设有陷门；③ DSA比RSA慢；④ RSA已是一个实际上的标准，而DSS与现行国际标准不相容；⑤ DSA未经公开选择过程，还没有足够的时间进行分析证明；⑥ DSA可能侵犯了其它专利(Schnorr签字算法，Diffie- Hellman的公钥密钥分配算法；⑦ 由512 bit所限定密钥量太小。现已改为512～1 024中可被64除尽的即可供使用。 2018/12/5

(5) 实现速度予计算：随机数r与消息无关，选一数串k，预先计算出其r。对k-1也可这样做。预计算大大加快了DSA的速度。对DSA和RSA比较如下表： DSA RSA DSA采用公用p.q.g 总计算 Off Card(P) N/A Off Card(P) 密钥生成 s Off Card(S) s 预计算 s N/A s 签字 s s s 证实 s s s 注：脱卡(Off Card)计算以33 MHz的80386 PC机，S：脱卡秘密参数，模皆为512 bit。 2018/12/5

5.其它签字体制： GOST签字标准，为俄国采用的数字签字标准，自1995启用，正式称为 GOST R 。算法与Schnorr模式下的ElGamal签字及NIST的DSA很相似。算法中也有一个类似于SHA的杂凑函数H(x)，其标准号为GOST R 。 ESIGN签字体制。日本NTT的T. Okamoto等设计的签字方案。宣称在密钥签字长度相同条件下，至少和RSA，DSA一样安全，且比它们都快。 OSS签字体制，Ong，Schnorr和Shamir[1984]提出的一种利用mod n下多项式的签字算法。方案基于二次多项式。离散对数签字体制， ElGamal、DSA、GOST、ESIGN、Okamoto等签名体制都是基于离散对数问题。这些体制都可以归结为一般的称之为离散对数签字体制之特例。 2018/12/5

第七讲：数字签字与身份证明三、特殊用途的数字签字
1. 不可否认签字。1989年由Chaum和Antwerpen引入，这类签字有一些特殊性质，其中最本质的是在无签字者合作条件下不可能验证签字，从而可以防止复制或散布他所签文件的可能性，这一性质使产权拥有者可以控制产品的散发。这在电子出版系统知识产权保护中将有用场。普通数字签字，可以精确地对其进行复制，这对于如公开声明之类文件的散发是必须的，但对另一些文件如个人或公司信件、特别是有价值文件的签字，如果也可随意复制和散发，就会造成灾难。这时就需要不可否认签字。否认协议(Disavowal Protocol)：在签字者合作下才能验证签字，这会给签字者一种机会，在不利于他时他拒绝合作以达到否认他曾签署的文件。为了防止此类事件而引入。 2018/12/5

构成签字算法的第三个组成部分，签字者可利用否认协议向法庭或公众证明一个伪造的签字确是假的；如果签字者拒绝参与执行否认协议，就表明签字事实上是真的由他签署的。 2. 防失败签字。由B.Pfitzmann和M.Waidner引入。这是一种强化安全性的数字签字，可防范有充足计算资源的攻击者。当A的签字受到攻击，甚至分析出A的秘密钥条件下，也难于伪造A的签字，A亦难以对自己的签字进行抵赖。 3. 盲签字。一般数字签字中，总是要先知道文件内容而后才签署，这正是通常所需要的。但有时需要某人对一个文件签字，但又不让他知道文件内容，称此为盲签字(Blind Signature)，它是由Chaum[1983]最先提出的。 2018/12/5

在选举投票和数字货币协议中将会碰到这类要求。利用盲变换可以实现盲签字，参看图7-14-1。 M M’ S(M’) S(M) 消息盲变换签字解盲变换图盲签字框图 (1) 完全盲签字。B是一位仲裁人，A要B签署一个文件，但不想让他知道所签的是什么，而B并不关心所签的内容，他只是要确保在需要时可以对此进行仲裁。可通过下述协议实现。完全盲签字协议: 2018/12/5

(a) A取一文件并以一随机值乘之，称此随机值为盲因子。 (b) A将此盲文件送给B。 ( c) B对盲文件签字。 (d) A以盲因子除之，得到B对原文件的签字。若签字函数和乘法函数是可换的，则上述作法成立。否则要采用其它方法(而不是乘法)修改原文件。安全性讨论： B可以欺诈吗？是否可以获取有关文件的信息？若盲因子完全随机，则可保证B不能由(b)中所看到的盲文件得出原文件的信息。即使B将(c)中所签盲文件复制，他也不能(对任何人)证明在此协议中所签的真正文件，而只是知道其签字成立，并可证实其签字。即使他签了100万个文件，也无从得到所签文件的信息。 2018/12/5

例．反间谍组织的成员的身份必须保密，甚至连反间谍机构也不知道他是谁。反间机构的头头要给每个成员一个签字的文件，文件上注明：持此签署文件人(将成员的掩蔽名字写于此)有充分外交豁免权。每个成员都有他自己的掩蔽名单。成员们不想将他们的掩蔽名单送给反间谍机构，敌人也可能会破坏反间谍机构的计算机。另一方面，反间机构也不会对成员给他的任何文件都进行盲签字，例如，一个聪明的成员可能用“成员(名字)已退休，并每年发给100万退休金”进行消息代换后，请总统先生签字。此情况下，盲签字可能有用。 2018/12/5

假定每个成员可有10个可能的掩护名字，他们可以自行选用，别人不知道。假定成员们并不关心在那个掩护名字下他们得到了外交豁免，并假定机构的计算机为Agency’s Intelligent Computing Engine，简记为 ALICE。则可利用下述协议实现。协议： (a)每个成员准备10份文件，各用不同的掩护名字，以得到外交豁免权。 (b)成员以不同的盲因子盲化每个文件。 (c)成员将10个盲文件送给ALICE。 (d)ALICE随机选择9个，并询问成员每个文件的盲因子。 (e)成员将适当的盲因子送给ALICE。 (f)ALICE从9个文件中移去盲因子，确信其正确性。 (g)ALICE将所签署10个文件送给成员。 (f) 成员移去盲因子，并读出他的新掩护名字：“The Crimson Streak”，在该名字下这份签署的文件给了他外交豁免权。 2018/12/5

这一协议在抗反间成员欺诈上是安全的，他必须知道哪个文件不被检验才可进行欺诈，其机会只有10%。(当然他可以送更多的文件)ALICE对所签第10个文件比较有信心，虽然未曾检验。这具有盲签性，保存了所有匿名性。反间成员可以按下述方法进行欺诈，他生成两个不同的文件，ALICE只愿签其中之一，B找两个不同的盲因子将每个文件变成同样的盲文件。这样若ALICE要求检验文件，B将原文件的盲因子给他；若ALICE不要求看文件并签字，则可用盲因子转换成另一蓄意制造的文件。以特殊的数学算法可以将两个盲文件做得几乎一样，显然，这仅在理论上是可能的。 (3) 信封。D. Chaum将盲变换看作是信封，盲化文件是对文件加个信封，而去掉盲因子过程是打开信封。文件在信封中时无人可读它，而在盲文件上签字相当于在复写纸信封上签字，从而得到了对真文件(信封内)的签字。 2018/12/5

（4）盲签字算法。D. Chaum曾提出第一个实现盲签字的算法，他采用了RSA算法。令B的公钥为e，秘密钥为d，模为n。（a) A要对消息m进行盲签字，选1<k<m，作 tmke mod n  B (7—14—1) (b) B对t签字, td (mke)d mod n A (7—14—2) (c) A计算 Std/k mod n 得 S md mod n (7—14—3) 这是B对m按RSA体制的签字。证明：td (mke)d mdk mod n  td/kmd k/kmd mod n (7—14—4) 2018/12/5

4. 群签字群体密码学(Group-Oriented Cryptography)1987年由Desmedt 提出。它是研究面向社团或群体中所有成员需要的密码体制。在群体密码中，有一个公用的公钥，群体外面的人可以用它向群体发送加密消息，密文收到后要由群体内部成员的子集共同进行解密。本节介绍群体密码学中有关签字的一些内容。 2018/12/5

（1）群签字。群签字(Group Signature)是面向群体密码学中的一个课题，1991年由Chaum和van Heyst提出。它有下述几个特点： ①只有群中成员能代表群体签字； ② 接收到签字的人可以用公钥验证群签字，但不可能知道由群体中那个成员所签； ③ 发生争议时可由群体中的成员或可信赖机构识别群签字的签字者。 2018/12/5

例如，这类签字可用于投标中。所有公司应邀参加投标，这些公司组成一个群体，且每个公司都匿名地采用群签名对自己的标书签字。事后当选中了一个满意的标书，就可识别出签字的公司，而其它标书仍保持匿名。中标者若想反悔已无济于事，因为在没有他参加下仍可以正确识别出他的签字。这类签字还可在其它类似场合使用。群签字也可以由可信赖中心协助执行，中心掌握各签字人与所签字之间的相关信息，并为签字人匿名签字保密；在有争执时，可以由签字识别出签字人。 Chaum和Heyst曾提出四种群签字方案。有的由可信赖中心协助实现群签字功能，有的采用不可否认并结合否认协议实现。Chaum所提方案，不仅可由群体中一个成员的子集一起识别签字者，还可允许群体在不改变原有系统各密钥下添加新的成员。群签字目标是对签字者实现无条件匿名保护，而又能防止签字者的抵赖，因此称其为群体内成员的匿名签字更合适些。 2018/12/5

（2）面向群体的不可抵赖签字前面已介绍过不可抵赖签字，这里将介绍在一个群体中由多个人签署文件时能实现不可抵赖特性的签字问题。 Desmedt等所提出的实现方案多依赖于门限公钥体制。一个面向群体的(t, n)不可抵赖签字，其中t是阈值，n是群体中成员总数，群体有一公用公钥。签字时也必须有t人参与才能产生一个合法的签字，而在验证签字时也必须至少有群体内成员合作参与下才能证实签字的合法性。这是一种集体签字共同负责制。 2018/12/5

第七讲：数字签字与身份证明四、数字签字体制中的潜信道
潜信道(Subliminal Channel)是在公开信道中所建立的一种实现隐蔽通信(Covert Communications)的信道。潜信道由Simmons 在1978年提出，其目的在于证明当时美国用于(SALT ——第二阶段限制战略武器会谈条约)核查系统中的安全协议的基本缺陷。1984年Simmons等证明，绝大多数签字体制中都可能存在潜信道，能否利用它进行隐蔽通信？如何能使公开信道的接收者要提取通过潜信道传送的消息在计算上不可行？我们将通过讨论各种签字体制，如ElGamal、DSS等签字体制中的潜信道的生成过程、性质、基本缺陷等来回答上述问题。利用系统接入控制机制中的漏洞建立隐信道(Covert Channel)实施隐蔽通信的问题将在后面介绍。 2018/12/5

1. 隐蔽通信。在实际通信中，有许多隐蔽信道和隐蔽通信的例子例如：① 二战期间，美国战俘用字母i表示Morse电码中的 “点”，用字母t表示“划”，来实现秘密消息传递，躲过敌方电报检查员的检查。②在保密数据网上通过在预定时间控制正在处理公共业务的请求的网络仲裁者的状态实现隐蔽bit传送。这一潜信道的发送和接收者在有相同时钟条件下可以访问这些隐蔽码元。由于仲裁者也要接受其它用户的请求，因此这类信道实际上具有一定的不确定性，可以用差错控制方法改进，而能提供一个可用的隐蔽信道。③令A，B因犯罪被捕入狱，分在不同狱中。看守W允许A，B交换信件，但不能加密且需经W检查，而A、B又要防止W用伪造消息欺骗A或B，故采用可靠的签名实现，并且要传递秘密信息，讨论如何协调越狱，为此他们要在公开信道中建立一个潜信道来实现。 2018/12/5

实施隐蔽通信的协议： ① A生成一个无意义消息M，类似于随机数； ② A利用与B共享秘密钥对M进行签字，同时将潜信息嵌入签字中； ③ A将签字消息交W转送给B； ④ W检阅A的消息并检验其签字，未发现可疑之处后转送给B； ⑤ B验证A的签字； ⑥ B用与A共享秘密钥从接收的无意义消息中提取潜信息。 W虽对A和B不信任，并可随时中断A与B的通信，但他既不可能提取潜信息(因无A与B共享秘密钥)，又不可能用伪造A 的消息欺骗B(因他无A的签字用秘密钥)。 2018/12/5

如何防止A与B之间的相互欺诈?这是一个棘手的问题，一些潜信道下，B需要读的潜信息正是A需要签署的无意义消息，这使得B可以伪装A签一个似乎来自A但A根本不知道的消息。因此潜信道的通信双方必须彼此信任，不会滥用共享秘密钥，这是I型潜信道。还有另一类潜信道，可以使A向B送潜消息，但B不能伪装A来签署任何这类消息，称作II型潜信道。在间谍系统中广泛采用这类潜信道进行通信。无潜信道的签字体制(Subliminal-free Signature Scheme)可参看[Desmedt 1988]。 2018/12/5

2.TRW方案美国TRW公司为美国征集执行SALT 核查系统而设计的方案被采用。TRW方案能准确检查出导弹发射中心状态(是否装载导弹)又能确保美苏双方对信息完整性(防伪、防替代、防欺诈、防否定)的要求。 TRW方案采用防窜传感器盒，将其放入发射井内能探测出导弹的现状，它具有遥感性能，可以进行高精度探测，发现对方导弹的移动和靠近发射井的行为，并能测出处于临战状态的导弹。这种传感器也可由对方提供。中心关键是如何确保信息的完整性，满足SALT 条约的需要。 2018/12/5

3. 潜信道 1-bit潜信道。可设计一个密码，它对每一明文可产生两个密文，都可用同一解密钥解密。密文可分成奇数和偶数两类，发方可以自由选用一种密文来表示明文，从而构成1-bit无条件保密的潜信道。可用Vernam密码来隐蔽阈下比特，参看图。公开收信者由于不掌握密钥ki(i=1, 2,…)，即使他怀疑潜信道可能传送可疑信息，也无法查出潜信道是否正被使用。可将1-bit潜信道推广至多bit潜信道。若能构造出一种密码，可使任一明文有l种可能的密文，则可构造出log2 l bit的潜信道。这类潜信道可用于实际中。 2018/12/5

例如，用于SALT 核查系统，若俄方提供的一个发射井的传感器的密码只生成奇数类密文，而另一个井安装的算法只产生偶数类密文，从而可以鉴别各个发射井，并搞清楚哪个发射井装载弹头。因此，仅需10 bit 潜信道就足以精确查出美方哪些发射井装载了导弹，这就排除了隐蔽导弹的可能性。公开收方W收潜信息bit 到的解密消息发信者 bi 奇/偶密密文认证提取奇/ bi 潜信息 A 文选择偶信息  接收者B ki KPKP KPKS ki 一次一密密钥公开信道的保密通信系统一次一密密钥潜信道的保密通信系统图 bit潜信道的保密通信系统 2018/12/5

4.签名体制中的潜信道离散对数型数字签字体制中，消息和签字可用三元组(M, r, s)或(H(M), r,s)表示。若H(M)、r和s的长度近于n bit，整个传送三元组长度为(|M|＋2n) bit，即增加了2n bit，其中，n bit 用于提供对签字的保护(防修改、抗伪、防移植等，伪造成功率为2-n)；另外的n bit则可用于构造潜信道。而且如果发方牺牲一些保密度，还可以加大潜信道的容量。一般一个有 bit的签字，若抗伪能力为 bit，则潜信道容量可达(－) bit。若能以(－) bit传送潜信息，则称其为宽带潜信道；若仅能以<(－) bit传送潜信息，则称其为窄带潜信道。关键是计算复杂性将随所用潜信道的bit数指数地增大。 2018/12/5

宽带潜信道致命问题是要恢复阈下信息，则必须知道发方秘密签名密钥，从而意味收方可以伪造发方签名而不被检测出来。如果发方不相信潜信道的接收者，就无法实现以(－ ) bits速率传阈下信息。若发信者将签字秘密钥交给接收者，则称此宽带潜信道为Ⅰ-型潜信道。若发信者不把签字秘密钥交给潜信息接收者，则称此窄带潜信道为Ⅱ-型潜信道。 5.ElGamal数字签字方案的潜信道 6.DSS中的潜信道 7.有关纠错码用于认证的系统中的潜信道研究 2018/12/5

第七讲：数字签字与身份证明五、身份证明的基本概念
身份证明必要性：在一个有竞争和争斗的现实社会中，身份欺诈是不可避免的，因此常常需要证明个人的身份。通信和数据系统的安全性也取决于能否正确验证用户或终端的个人身份。传统的身份证明：一般是通过检验“物”的有效性来确认持该物的的身份。“物”可以为徽章、工作证、信用卡、驾驶执照、身份证、护照等，卡上含有个人照片(易于换成指纹、视网膜图样、牙齿的X适用的射像等)，并有权威机构签章。这类靠人工的识别工作已逐步由机器代替。信息化社会对身份证明的新要求：随着信息业务的扩大，要求验证的对象集合也迅速加大，因而大大增加了身份验证的复杂性和实现的困难性。实现安全、准确、高效和低成本的数字化、自动化、网络化的认证。 2018/12/5

1. 身份欺诈的方式 (1) 象棋大师问题。A不懂象棋，但可向G. Kasparov和A. Karpov同时挑战，在同一时间和地点进行(不在一个房子)对弈，以白子棋对前者以黑子棋对后者，而两位大师彼此不通气，参看图8-1-1。Karpov持白子棋先下一步，A记下走到另一房下同样一着，而后看Kasparov如何下黑子棋，A记下这第二步对付Karpov，以此类推。这是一种中间人欺诈。 Karpov Kasparov A 图象棋大师问题 2018/12/5

(2) The Mafia欺诈。 A在Mafia集团成员B开的饭馆吃饭，Mafia集团另一成员C到D的珠宝店购珠宝，B和C之间有秘密无线通信联络，A和D 不知道其中有诈。 A向B证明A的身份并付账，B通知C开始欺骗勾当，A 向B证明身份，B经无线通知C，C以同样协议与D实施。当D询问C时，C 经B向A问同一问题，B再将A的回答告诉C，C向D回答，参看图8-1-2。实际上，B和C起到中间人作用完成A向D的身份证明，实现了C向D购买了值钱珠宝，而把账记在A的账上。这是中间人B和C合伙进行的欺诈。 A B C D 图中间人合伙欺诈 2018/12/5

3．恐怖分子欺诈无线 A C D 有合法身份者恐怖分子移民局图另一种中间人合伙欺诈假定C是一名恐怖主义者，A要帮助C进入某国，D是该国移民局官员， A和C之间有秘密无线电联络，参看图8-1-3。A协助C得到D的入境签证。这类欺诈可以用防电磁幅射泄露和精确时戳等技术来抗击。 (4) 多身份欺诈(Multiple identity frand)。A首先建立几个身份并公布之。其中之一他从来未用过，他以这一身份作案，并只用一次，除目击者(Witness)外无人知道犯罪人的个人身份。由于A不再使用此身份，而无法跟踪。采用一种机构，且每人只能有一个身份证明就可抗击这类欺诈。 2018/12/5

2. 身份证明系统的组成和要求组成：  示证者P(Prover)，出示证件的人，又称作申请者 (Claimant)，提出某种要求；  验证者V(Verifier)，检验示证者提出的证件的正确性和合法性，决定是否满足其要求；  攻击者，可以窃听和伪装示证者骗取验证者的信任。  可信赖者，参与调解纠纷。必要时的第四方。 2018/12/5

身份证明技术，又称作识别(Identification)、实体认证(Entity authenticotion)、身份证实(Identity verification)等。实体认证与消息认证的差别在于，消息认证本身不提供时间性，而实体认证一般都是实时的。另一方面实体认证通常证实实体本身，而消息认证除了证实消息的合法性和完整性外，还要知道消息的含义。对身份证明系统的要求： (1) 验证者正确识别合法示证者的概率极大化。 (2) 不具可传递性(Transferability)，验证者B不可能重用示证者A提供给他的信息来伪装示证者A，而成功地骗取其他人的验证，从而得到信任。 2018/12/5

(3) 攻击者伪装示证者欺骗验证者成功的概率要小到可以忽略的程度，特别是要能抗已知密文攻击，即能抗攻击者在截获到示证者和验证者多次(多次式表示)通信下伪装示证者欺骗验证者。 (4) 计算有效性，为实现身份证明所需的计算量要小。 (5) 通信有效性，为实现身份证明所需通信次数和数据量要小。 (6) 秘密参数能安全存储。 (7) 交互识别，有些应用中要求双方能互相进行身份认证。 (8) 第三方的实时参与，如在线公钥检索服务。 (9) 第三方的可信赖性。 (10) 可证明安全性。 7～10是有些身份识别系统提出的要求。 2018/12/5

3. 身份证明的基本分类  身份证实(Identity Verification)，要回答“你是否是你所声称的你？” 即只对个人身份进行肯定或否定。一般方法是输入个人信息，经公式和算法运算所得的结果与从卡上或库中存的信息经公式和算法运算所得结果进行比较，得出结论。  身份识别(Identity Recogniton)，要回答“我是否知道你是谁？”一般方法是输入个人信息，经处理提取成模板信息，试着在存储数据库中搜索找出一个与之匹配的模板，而后给出结论。例如，确定一个人是否曾有前科的指纹检验系统。显然，身份识别要比身份证明难得多。 2018/12/5

4. 实现身份证明的基本途径身份证明可以依靠下述三种基本途径之一或它们的组合实现，如图8-1-4所示。  所知(Knowlege)，个人所知道的或所掌握的知识，如密码、口令等。  所有(Possesses)，个人所具有的东西，如身份证、护照、信用卡、钥匙等。  个人特征(Characteristics)，如指纹、笔迹、声纹、手型、脸型、血型、视网膜、虹膜、DNA以及个人一些动作方面的特征等。 2018/12/5

所知 1 所有个人特征图身份证明的基本途径根据安全水平、系统通过率、用户可接受性、成本等因素，可以选择适当的组合设计实现一个自动化身份证明系统。 2018/12/5

身份证明系统的质量指标  拒绝率FRR( False Rejection Rate)或虚报率(Ⅰ型错误率)：合法用户遭拒绝的概率。  漏报率FAR (False Acceptance Rate) (Ⅱ型错误率)：非法用户伪造身份成功的概率。为了保证系统有良好的服务质量，要求其型错误率要足够小；为保证系统的安全性，要求其型错误率要足够小。这两个指标常常是相悖的，要根据不同的用途进行适当的折中选择，如为了安全(降低FAR)，则要牺牲一点服务质量(增大 FRR)。设计中除了安全性外，还要考虑经济性和用户的方便性。 2018/12/5

第七讲：数字签字与身份证明六、通行字认证系统
1. 概述。通行字(也称口令、护字符)是一种根据已知事物验证身份的方法，也是一种最广泛被研究和使用的身份验证法。如中国古代调兵用的虎符、阿里巴巴打开魔洞的“芝麻”密语、军事上采用的各种口令以及现代通信网的接入协议。通行字选择原则：① 易记；② 难以被别人猜中或发现；③ 抗分析能力强。在实际系统中需要考虑和规定选择方法、使用期限、字符长度、分配和管理以及在计算机系统内的保护等。在一般非保密的联机系统中，多个用户可共用一个通行字。要求的安全性高时，每个用户需分别配有专用的通行字。在要求较高的安全性时，可采用随时间而变化的一次性通行字。 2018/12/5

防止泄露是系统设计和运行中的关键问题。一般，通行字及其响应在传送过程中均要加密，而且常常要附上业务流水号和时戳等，以抗击重放攻击。为了避免被系统操作员或程序员利用，个人身份和通行字都不能以明文形式在系统中心存放。可用软件进行加密处理。一个更好的办法是采用通行短语(Pass Phrases)代替通行字，通过密钥碾压(Key Crunching)技术，如杂凑函数，可将易于记忆的足够长的短语变换为较短的随机性密钥。分发通行字的安全性是极为重要的一环。通行字可由用户个人选择，也可由系统管理人员选定或由系统自动产生。 2018/12/5

2. 通行字的控制措施 (1) 系统消息(System Message)。一般系统在联机和脱机时都显示一些礼貌性用语，而成为识别该系统的线索，因此这些系统应当可以抑制这类消息的显示。 (2) 限制试探次数。不成功送口令一般限制为3～6次，超过限定试验次数，系统将对该用户ID锁定。 (3) 通行字有效期。限定通行字的使用期限。 (4) 双通行字系统。允许联机用通行字，和允许接触敏感信息还要送一个不同的通行字。 (5) 最小长度。限制通行字至少为6～8个Bytes以上，防止猜测成功概率过高，可采用掺杂(Salting)或采用通行短语(等加长和随机化。 2018/12/5

(6) 封锁用户系统。可以对长期未联机用户或通行字超过使用期的用户的ID封锁。直到用户重新被授权。 (7) 根通行字的保护。根(Root)通行字是系统管理员访问系统所用口令，由于系统管理员被授予的权利远大于对一般用户的授权，因此它自然成为攻击者的攻击目标。因此在选择和使用中要倍加保护。要求必须采用16进制字符串、不能通过网络传送、要经常更换(一周以内)等。 (8) 系统生成通行字。有些系统不允许用户自己选定通行字，而由系统生成、分配通行字。系统如何生成易于记忆又难以猜中的通行字是要解决的一个关键问题；另一危险是若生成算法被窃，则危及整个系统的安全。UAX IVM S V.4.3系统能保证所产生的通行字具有可拼读性。 2018/12/5

3. 通行字的检验  反应法(Reactive )：利用一个程序(Cracker)，让被检通行字与一批易于猜中的通行字表中成员进行逐个比较。若都不相符则通过。这类反应检验法有些缺点：① 检验一个通行字太费时，试想一个攻击者可能要用几小时甚至几天来攻击一个通行字。②现用通行字都有一定的可猜性，但直到采用反应检验后用户才更换通行字。  支持法(Proactive)：用户先自行选一个通行字，当用户第一次使用时，系统利用一个程序检验其安全性，如果它易于被猜中，则拒绝并请用户重新选一个新的。通过准则要考虑可猜中性与安全性的之间的折衷，若算法太严格，则用户所选通行字屡遭拒绝而招致用户报怨。另一方面如果很易猜中的通行字也能通过，则影响系统的安全性。 2018/12/5

4. 通行字的安全存储  一般方法 (1) 对于用户的通行字多以加密形式存储，入侵者要得到通行字，必须知道加密算法和密钥，算法可能是公开的，但只有管理者才知道密钥。 (2) 许多系统可以存储通行字的单向杂凑值，入侵者即使得到此杂凑值也难于推出通行字的明文。 Unix系统中的通行字存储。通行字为8个字符，采用7-bit ASCII码，即为56 bit串，加上12 bit填充(一般为用户键入通行字的时间信息)。第一次输入64 bit全“0”数据加密，第二次则以第一次加密结果作为输入数据，迭代25次，将最后一次输出变换成11个字符(其中，每个字符是A-Z, a-z, 0-9, “0”, “1”等共64个字符之一)作为通行字的密文，参看图8-2-3。 2018/12/5

64 bit 全“0”数据用户ID 填充加密通行字 25次通行字56 bit 填充(12bit) DES 最后一次输出加密的通行字图 UNIX的通行字存储检验时用户送ID和通行字，由ID检索出相应填充值(12 bits)并与通行字一起送入加密装置算出相应密文，与由存储器中检索出的密文进行比较，若一致则通过。 2018/12/5

 灵巧(有源)Token卡采用的一次性通行字这种通行字本质上是一个随机数生成器，可以用安全服务器以软件方法生成，一般用在第三方认证，参看图8-2-4。优点：① 即使通行字被攻击者截获也难以使用；② 用户需要送PIN(只有持卡人才知道)，因此，即使卡被偷也难以使用卡进行违法活动。 (3)用户 (1)用户ID (2)用户ID 灵 PIN 持工巧卡作卡 (4)一次性人 (5)一次性站 (6)1次性通行字通行字通行字应用程序用户证实图灵巧卡接入系统服务器 2018/12/5

第七讲：数字签字与身份证明七、利用个人特征的身份证明技术
在安全性要求较高的系统，由护字符和持证等所提供的安全保障不够完善。护字符可能被泄露，证件可能丢失或被伪造。更高级的身份验证是根据被授权用户的个人特征来进行的确证，它是一种可信度高而又难以伪造的验证方法。这种方法在刑事案件侦破中早就采用了。自1870年开始沿用了40年的法国Bertillon体制对人的前臂、手指长度、身高、足长等进行测试，是根据人体测量学(Anthropometry)进行身份验证。这比指纹还精确，使用以来未发现过两个人的数值完全相同的情况。伦敦市警厅已于1900年采用了这一体制。新的含义更广的生物统计学(Biometrics)正在成为自动化世界所需要的自动化个人身份认证技术中的最简单而安全的方法。它利用个人的生理特征来实现。 2018/12/5

个人特征种类：有静态的和动态的，如容貌、肤色、发长、身材、姿式、手印、指纹、脚印、唇印、颅相、口音、脚步声、体味、视网膜、血型、遗传因子、笔迹、习惯性签字、打字韵律以及在外界刺激下的反应等。当然采用哪种方式还要为被验证者所接受。有些检验项目如唇印、足印等虽然鉴别率很高，但难于为人们接受而不能广泛使用。有些可由人工鉴别，有些则须借助仪器，当然不是所有场合都能采用。个人特征都具有因人而异和随身携带的特点，不会丢失且难以伪造，极适用于个人身份认证。有些个人特征会随时间变化。验证设备须有一定的容差。容差太小可能使系统经常不能正确认出合法用户，造成虚警概率过大；实际系统设计中要在这两者之间作最佳折衷选择。有些个人特征则具有终生不变的特点，如DNA、视网膜、虹膜、指纹等。 2018/12/5

1. 手书签字验证。传统的协议、契约等都以手书签字生效。发生争执时则由法庭判决，一般都要经过专家鉴定。由于签字动作和字迹具有强烈的个性而可作为身份验证的可靠依据。机器自动识别手书签字：机器识别的任务有二：一是签字的文字含义；二是手书的字迹风格。后者对于身份验证尤为重要。识别可从已有的手迹和签字的动力学过程中的个人动作特征出发来实现。前者为静态识别，后者为动态识别。静态验证根据字迹的比例、斜的角度、整个签字布局及字母形态等。动态验证是根据实时签字过程进行证实。这要测量和分析书写时的节奏、笔划顺序、轻重、断点次数、环、拐点、斜率、速度、加速度等个人特征。可能成为软件安全工具的新成员，将在Internet的安全上起重要作用。 2018/12/5

可能的伪造签字类型：一是不知真迹时，按得到的信息(如银行支票上印的名字)随手签的字，另一是已知真迹时的模仿签字或映描签字。前者比较容易识别，而后者的识别就困难得多。 2. 指纹验证。指纹验证早就用于契约签证和侦察破案。由于没有两个人(包括孪生儿)的皮肤纹路图样完全相同，相同的可能性不到10－10，而且它的形状不随时间而变化，提取指纹作为永久记录存档又极为方便，这使它成为进行身份验证的准确而可靠手段。每个指头的纹路可分为两大类，即环状和涡状；每类又根据其细节和分叉等分成50～200个不同的图样。通常由专家来进行指纹鉴别。近来，许多国家都在研究计算机自动识别指纹图样。 2018/12/5

将指纹验证作为接入控制手段会大大提高其安全性和可靠性。但由于指纹验证常和犯罪联系在一起，人们从心理上不愿接受按指纹。此外，这种机器识别指纹的成本目前还很高，所以还未能广泛地用在一般系统中。 3. 语音验证。每个人的说话声音都各有其特点，人对于语音的识别能力是很强的，即使在强干扰下，也能分辨出某个熟人的话音。在军事和商业通信中常常靠听对方的语音实现个人身份验证。美国AT&T公司为拨号电话系统研制一种称作语音护符系统VPS(Voice Passsword System)以及用于ATM 系统中的智能卡系统的，它们都是以语音分析技术为基础的。 2018/12/5

4. 视网膜图样验证。人的视网膜血管的图样(即视网膜脉络)具有良好的个人特征。这种识别系统已在研制中。其基本方法是利用光学和电子仪器将视网膜血管图样记录下来，一个视网膜血管的图样可压缩为<35字节的数字信息。可根据对图样的节点和分支的检测结果进行分类识别。被识别人必须合作允许采样。研究表明，识别验证的效果相当好。如果注册人数小于200万时，其Ⅰ型和Ⅱ型错误率都为0，所需时间为秒级，在要求可靠性高的场合可以发挥作用，已在军事和银行系统中采用。其成本比较高。 5. 虹膜图样验证。虹膜是巩膜的延长部分，是眼球角膜和晶体之间的环形薄膜，其图样具有个人特征，可以提供比指纹更为细致的信息。可以在35～40厘米的距离采样，比采集视网膜图样要方便，易为人所接受。存储一个虹膜图样需要256字节，所需的计算时间为100毫秒。其Ⅰ型和Ⅱ型错误率都为1/ 。可用于安全入口、接入控制、信用卡、POS、ATM(自动支付系统)、护照等的身份认证。 2018/12/5

6. 脸型验证。Harmon等设计了一种从照片识别人脸轮廓的验证系统。对100个“好”对象识别结果正确率达百分之百。但对“差”对象的识别要困难得多，要求更细致地实验。对于不加选择的对象集合的身份验证几乎可达到的完全正确，可作为司法部门的有力辅助工具。目前有多家公司从事脸型自动验证新产品的研制和生产。他们利用图像识别、神经网络和红外扫描探测人脸的“热点”进行采样、处理和提取图样信息。目前已有能存入5 000个脸型，每秒可识别20个人的系统。将来可存入100万个脸型但识别检索所需的时间将加大到2分钟。Ture Face系统，将用于银行等的身份识别系统中。Visionics公司的面部识别产品FaceIt已用于网络环境中，其软件开发工具(SDK)可以集入信息系统的软件系统中，作为金融、接入控制、电话会议、安全监视、护照管理、社会福利发放等系统的应用软件。 2018/12/5

7. 身份证实系统的设计。选择和设计实用身份证实系统是不容易的。Mitre公司曾为美国空军电子系统部评价过基地设施安全系统规划。分析比较语音、手书签字和指纹三种身份证实系统的性能。表明选择评价这类系统的复杂性，需要从很多方面进行研究。美国NBS的自动身份证实技术的评价指南[NBS 1977]提出了下述12个需要考虑的问题：①抗欺诈能力；② 伪造容易程度；③ 对于设陷的敏感性；④ 完成识别的时间；⑤ 方便用户；⑥ 识别设备及运营的成本；⑦ 设备使用目的所需的接口；⑧ 更新所需时间和工作量；⑨ 为支持验证过程所需的计算机系统的处理工作；⑩ 可靠性和可维护性；(11)防护器材费用；(12) 分配和后勤支援费用。总之，要考虑三个方面问题：一是作为安全设备的系统强度；二是对用户的可接受性；三是系统的成本。 2018/12/5

第七讲：数字签字与身份证明八、零知识证明技术
1. 概述。示证者：P；验证者：V；最大泄露证明：出示或说出此事物，使别人相信，但同时使别人也知道或掌握了这一秘密；最小泄露证明和零知识证明：以一种有效的数学方法，使V可以检验每一步成立，最终确信P知道其秘密，而又能保证不泄露P所知道的信息。 2018/12/5

最小泄露证明满足下述条件： (1) 示证者几乎不可能欺骗验证者，若P知道证明，则可使V 几乎确信P知道证明；若P不知道证明，则他使V相信他知道证明的概率近于零。 (2) 验证者几乎不可能得到证明的信息，特别是他不可能向其他人出示此证明。零知识证明满足条件(1)、(2)外还要满足： (3) 验证者从示证者那里得不到任何有关证明的知识。交互作用协议：V向P提问，若P知道证明则可正确回答V的提问；若P不知道证明，则对提问给出正确回答概率仅为1/2。 V以足够多的提问就可推定P是否知道证明，且要保证这些提问及其相应的回答不会泄露出有关P所知道的知识。 2018/12/5

2. 零知识证明的基本协议例[Quisquater等1989] 。 A 设P知道咒语，可打开C和 D之间的秘密门，不知道者 B 都将走向死胡同中。 C D 图零知识证明概念图解 2018/12/5

协议 1： (1) V站在A点； (2) P进入洞中任一点C或D； (3) 当P进洞之后，V走到B点； (4) V叫P：(a)从左边出来，或(b)从右边出来； (5) P按要求实现(以咒语，即解数学难题帮助)； (6) P和V重复执行 (1)～(5)共n次。若A不知咒语，则在B点，只有50 %的机会猜中B的要求，协议执行n次，则只有2-n的机会完全猜中，若n=16，则若每次均通过B的检验，B受骗机会仅为1/65 536。 2018/12/5

此协议又称作分割和选择(Cut and Choose)协议，是公平分享东西时的经典协议。即协议 2： (1) A将东西切成两半； (2) B选其中之一； (3) A拿剩下的一半。显然，A为了自己的利益在(1)中要公平分割，否则(2)中B 先于他的的选择将对其不利。Rabin[1978]最早将此用于密码学，后来发展为交互作用协议和零知识证明[Golrreich等 1985,1989]。此洞穴问题可以换成数学问题，A知道解决某个难题的秘密信息，而B通过与A交互作用验证其真伪。 2018/12/5

协议 3： (1) A用其信息和某种随机数将难题转成另一种难题，且与原来的同构，A可用其信息和随机数解新的难题； (2) A想出新的难题的解，采用Bit承诺方案； (3) A将新难题出示给B，但B不能由此新难题得到有关原问题或其解； (4) B向A提下述问题之一：(a) 向B证明老的和新的问题是同构的，(b) 公开(2)中的解，并证明它是新难题的解； (5) A按B的要求执行； (6) A和B重复执行 (1)～(5)共n次。必须仔细选择适当问题和随机信息，使B即使重复执行多次协议也得不到有关原问题的任何信息。并非所有“难题”都可用于零知识证明，但有不少可用于此。 2018/12/5

例哈米尔顿回路。图论中有一个著名问题，对有n个顶点的全连通图G，若有一条通路可通过且仅通过各顶点一次，则称其为哈米尔顿回路。Blum[1986] 最早将其用于零知识证明。当n大时，要想找到一条Hamilton回路，用计算机做也要好多年，它是一种单向函数问题。若 A知道一条回路，如何使B相信他知道，且不告诉他具体回路？协议 4： (1) A将G进行随机置换，对其顶点进行移动，并改变其标号得到一个新的有限图H。因，故G上的Hamilton回路与H上的Hamilton回路一一对应。已知G上的Hamilton回路易于找出H上的相应回路； (2)A将H的复本给B； (3) B向A提出下述问题之一：(a) 出示证明G和H同构，(b) 出示H上的 Hamilton回路； (4) A执行下述任务之一：(a) 证明G和H同构，但不出示H上的Hamilton回路，(b) 出示H上的Hamilton回路但不证明G和H同构； (5) A和B重复执行 (1)～(4)共n次。 2018/12/5

若A知道G上的Hamilton回路，则总能正确完成(4)。若A不知道G上的 Hamilton回路，则不能建一个图能同时满足(4)中(a)和(b)的要求，他最多能做到构造一个图或同构于G，或H上有一条有同样顶点和线数的 Hamilton回路，只有50 %的机会能正确应付B的挑战。对于n次重复，则无能为力应付。显然这是一类零知识证明。B不可能知道原图G，告诉你，由H上找一个新的Hamilton回路，这和在G中找一样难。另一方面，告诉新图上的一条Hamilton回路，要找到新旧图之间的同构同样困难(A每次置换都不一样)，B不可能得到任何信息。例设A知道两个图同构，Goldreich等[1986]利用图的同构构造的零知识证明协议。由协议 5实现： (1) A将G1和G2随机置换为和(其他人要找，或都如找一样难)； (2) A将H传送给B； (3) B向A提出下述问题之一： (a) 证明，或(b) 证明； (4) A回答：(a) 证明，但不证明，或(b) 证明，但不证明； (5) A和B重复执行 (1)～(4)n次。 2018/12/5

安全性： (1) 若A不知，不可能找到H与两者同构。他可以找一个 H与G1同构，或与G2同构，故在第(4)步只有1/2的机会可以骗得B的信任。 (2) 证明未给出B有关的任何证明信息，由于每一回合， A都产生一个新的H。 2018/12/5

3. 并行零知识证明。执行n次协议可以并行方式实施。协议6: (1) A用其信息及某种随机数将难题变换成n个不同的同构问题，而后用其信息和随机数解n个新的难题； (2) A完成n个新的难题的解； (3) A向B披露n个新的难题，而B不能从中得到原问题或其解的信息； (4) B向A提出有关n个新的难题的提问：(a) 出示新旧难题的同构性证明，或(b) 公布(2)中新的难题的解，并证明是新难题的解； (5) A回答提问。此协议安全，且交互作用次数减少。 2018/12/5

4. 使第三者相信的协议(零知识) B若想使C相信A知道某信息，他将与A执行协议的复本给C 能否使C相信？否，因为两个不知秘密信息的人可以串通一起来骗C。例如，诈骗者A可以假装知道秘密，并与B串通，让B只提出A可以答对的问题，这样得到的A与B执行协议的复本就可能骗C。 5. 非交互式零知识证明上述二中的协议都是交互式的，难以令C相信A与B没有勾结。若要使C和其他人相信，应采用非交互式(Non interactive) 零知识证明。对于非交互式零知识证明，A可以公布证明，任何人可以花时间去检验该证明的正确性。 2018/12/5

协议 7： (1) A用其信息和随机数将难题变成n个难题，并以其掌握的信息和随机数解n个难题； (2) A构成n个新难题的解； (3) A将这些承诺(Commitments)送入单向Hash函数计算Hash值，将其前n个bit存好； (4) A将(3)中的前n比特，称其为承诺矢量，按其为0或1进行： (a) 证明新旧问题同构， (b) 公布(2)中问题的解，并证明它是新问题的解； (5) A将(2)中构成的问题及(4)中的数据公布； (6) B，C或任何有兴趣的人可以证实(1)～(5) 2018/12/5

关键是要使单向Hash函数为无偏的随机数，而使A不能进行欺诈，若A不知难题之解，则在(4)中可以做对(a)或 (b)，但不能同时正确完成(a)和(b)。如果他能预先知道单向Hash函数要问的问题也可能行骗，但他不知道，也不可能控制Hash值。这里，单向Hash函数起到了代替B随机提问的作用！与交互式相比，无交互作用下，n要取得大得多。在交互式证明中，n＝20足够了；而在非交互式证明中n＝ 64～128，否则易被A钻空子。 2018/12/5

6. 一般化理论结果 (1) Blum证明：任何数学问题可化为图论中问题，其证明等价于Hamiltonian回路问题，由此可以构成零知识证明问题，任何掌握这一数学问题的人都可以利用零知识证明来公布这一结果，使别人相信而不泄露证明方法。 (2) Burmester等提出广播交互式证明问题。 (3) 一些密码学家证明可以用交互证明的问题都可以化为零知识交互证明的问题。可由此给出各种变型、协议及应用。 2018/12/5

7. 零知识身份证明的密码体制 (1) Feige-Fiat-Shamir体制。A.Fiat和A.Shamir曾提出认证和数字签字体制，后来U.Feige参与将其修改成为一个零知识身份证明方案。 (2) 简化F-F-S识别体制。可信赖仲裁选定一个随机模 m=p1×p2，m为512 bit或长达1024 bits。证明者共用此m，仲裁可实施公钥私钥的分配，他产生随机数v，且使x2=v ，即v为模m的平方剩余，且有v-1 mod m。以v作为公钥，而后计算最小的整数s， (8—5—1) 作为秘密钥分发给用户A。实施身份证明的协议如下。 2018/12/5

协议 1： (1) 用户A取随机数r(<m)，计算x= r2 mod m，送给B； (2) B将一随机bit b送给A； (3) 若b=0，则A将r送给B；若b=1，则A将y=rs送给B； (4) 若b=0，则B证实x=r2 mod m，从而证明A知道，若b=1，则B证实x=y2 ·v mod m，从而证明A知道。这是一次鉴定(Accreditation)，A和B可将此协议重复t次，直到B相信A知道s为止。这就是8-4节中的分割-选择协议。 2018/12/5

安全性： (1) A骗B的可能性。A不知道s，他也可取r，送x=r2 mod m给B，B送b给A。A可将r送出，当b=0时则B可通过检验而受骗，当b=1时，则B可发现A不知s，B受骗概率为1/2，但连续t次受骗的概率将仅为2-t。 (2) B伪装A的可能性。B和其他验证者C开始一个协议，第一步他可用A用过的随机数r，若C所选的b值恰与以前发给A的一样，则B可将在第(3)步发的重发给C，从而可成功地伪装A，但C随机选b为0或1，故这种攻击成功概率仅为1/2，要执行t次，则可使其降为2－t。 2018/12/5

(3) F-F-S识别体制。Feige等在[1987, 1988]中给出采用并行结构增加每轮鉴定次数的方案。可信赖仲裁选 m=p1×p2，并选k个随机数v1, v2, …, vk，各vi是mod m的平方剩余，且有逆。以v1, v2, …, vk为A的公钥，计算最小正整数si，使，将s1, …, sk作为A的秘密钥。协议 2： (1) A选随机数r(<m)，计算x=r2 mod m送给B； (2) B选k bit随机数b1, b2, …, bk，给A； (3) A计算并送给B； (8—5—2) (4) B证实 (8—5—3) 2018/12/5

此协议可执行t次，直到B相信A知道s1, s2, …, sk，A能骗 B的机会为2-kt。建议选k=5，t=4。例 8-5-1： m=35(5×7)。计算平方剩余： 1：x2=1 mod 35，解x=1, 6, 29或34；：x2=16 mod 35，解x=4, 11, 4：x2=4 mod 35，解x=2, 12, 23或33；或31； 9：x2=9 mod 35，解x=3, 17, 18或32； 21：x2=21 mod 35，解x=14或21； 11：x2=11 mod 35，解x=9, 16, 19或26；25：x2=25 mod 35，解x=5或30； 14：x2=14 mod 35，解x=7或28；：x2=29 mod 35，解x=8, 13, 22或27； 15：x2=15 mod 35，解x=15或20；：x2=30 mod 35，解x=10或25。 2018/12/5

选v=1，4，9，11，16，29，相应逆元为v-1=1，9，4，16，11，29；秘密钥=1，3，2，4，9，8。(14, 15, 21, 25和30在mod 35下不存在逆，因与35不互素。)若选k=4，A可用{4,11,16,29}作为公钥，相应的 {3,4,9,8}为秘密钥。协议执行 (1) A选随机数r=16，计算162 mod 35=11，送给B； (2) B选随机bit串{1101}给A； (3) A计算16·31·41·90·81 mod 35=31给B； (4) B验证312·41·111·160·291 mod 35=11。 A和B可重复执行此协议，每次以不同的r和b串。若m小，则无安全可言，若m为512 bit以上，则B不可能得到任何有关A的秘密钥知识，只能相信A掌握它 2018/12/5

(4) 增强方案。可将A的身份信息I，包括姓名、住址、社会安全号码、喜欢的软饮料牌子等，加上一个随机选的数 j，经过单向Hash函数H(x)，计算得H(I, j)作为A的识别符 (Identificator)。可以选这样的k个随机数，使H(I, j)为mod m的平方剩余，并将得出相应的v1, v2, …, vk(各vi在mod m 下有逆)作为公钥。A将I及k个H(I, j)送给B，B可由H(I, j) 生成v1, v2, …, vk。这样A，B就可完成前述协议。 2018/12/5

例：B确信某人知道m的分解可证实I与A的关系，并将从I 导出的vi的平方根给了A。Feige等给出下述实际建议： (1) 若Hash函数不完善，可用加长随机串R来随机化I，由仲裁选R并和I一起向B公布； (2) 一般k选1到18，k值大可以降低协议执行轮数而减少了通信复杂性； (3) m至少为512 bits； (4) 若所有用户选用自己的m并公开在公钥文件中，从而可以免去仲裁，但这种类似RSA的变型使方案很不方便。 2018/12/5

(5) Fiat-Shamir签字体制。上述识别方案可以变成一个数字签字方案，只需将B的工作变为H函数运算。这一签字方法优于RSA签字，因为它的模乘运算量只为RSA的 1%～4%，所以要快得多。方案建立过程同识别方案，选 n=p1·p2，生成公钥v1, v2, …, vk和秘密钥s1, s2, …, sk，使。协议 3： (1) A选t个小于m的数r1, …, rt，并计算x1, …, xt使xi=ri2 mod m； (2) A将待传消息M和xi串链接，并产生Hash值H(M, x1, x2, …, xt)，取前k×t bit作为的值，i=1, …, t，j=1, …, k； 2018/12/5

(3) A计算y1, y2, …, yt，其中 (8—5—4) (4) A将m，及yi都送给B，而B有A的公钥v1, v2, …, vk； (5) B计算z1, z2, …, zk，其中 (8—5—5) (6) B证实计算H(M, z1, …, zk)的前k×t个bit看是否与收到的各一致。类似于识别体制，其安全性与成比例，破译等价于m 的分解，Fiat和Shamir指出，当分解m的复杂度远大于，伪造一个签字就容易得多。建议kt要从20增加到72以上，如选k=9，t=8。 2018/12/5

改进：S. Micali和A. Shamir提出对上述方案的改进。选v1, v2, …, vk为前k个素数，如v1=2，v2=3，v3=5，…作为公钥，秘密钥s1, s2, …, sk是由的随机平方根。每个用户有一个不同的m，修正使之更容易证实一个签字。而产生签字的时间和签字的安全性不受影响。 (6) 其它强化提案。Brickell提出基于F-F-S的N-方识别体制。Ong等提出Fiat-Shamir签字的两种改进方案。Ohta- Okamoto提出几种识别体制是F-F-S方案的修正，以分解因子困难来保证体制的安全性。此外，还提出多签字方法，几个人依次签署同一消息，并建议用于Smart Card中。 Burmester等对Ohta-Okamoto体制进行了分析。 2018/12/5

第七讲：数字签字与身份证明九、灵巧卡技术
个人持证(token)为个人所有物，可用来验证个人身份，磁卡和灵巧卡(IC卡)都是用来验证个人身份的，它又称为身份卡，简称ID卡。后者更先进、更安全和可靠的。 IC卡又称有源卡(Active card)、灵巧卡(Smart card)或智能卡(Intelligent card)。它将微处理器芯片嵌在塑卡上代替无源存储磁条。存储信息量远大于磁条的250 byte，且有处理功能。卡上的处理器有4 kbyte的程序和小容量EPROM，有的甚至有液晶显示和对话功能。灵巧卡的工作原理框图示于图8-6-1中（参看讲义）。以灵巧卡代替无源卡使其安全性大大提高，因为对手难以改变或读出卡中的存数。它还克服了普通信用卡如下的一些严重缺点。 2018/12/5

普通卡的缺点： ① 透支问题：由于大多数购买活动不会立刻报告给发卡公司，所以持卡人可以多次进行小笔交易或一大笔交易，所需金额大大超过持卡人的存款额； ② 转录信息：用复写信纸留下信用卡突出部分的印痕就可将信用卡磁条上存储的信息复制到空白卡上； ③ 泄露护字符：监视存取机的工作的人可能会在持卡人送护字符时窃得其护字符。 2018/12/5

灵巧卡的特点：  存储量大：在灵巧卡上有一存储用户永久性信息的ROM，在断电下信息不会消失。每次使用卡进行的交易和支出总额都被记录下来，因而可确保不能超支。  有CPU：卡上的中央处理器对输入、输出数据进行处理。卡中存储器的某些部分信息只由发卡公司掌握和控制。  密码控制：通过中央处理器、灵巧卡本身就可检验用卡人所提供的任何密码，将它同储于秘密区的正确密码进行比较，并将结果输出到卡的秘密区中，秘密区还存有持卡人的收支账目，由公司选定的卡的编号一组字母或数字，用以确定其合法性。 2018/12/5

 访问控制：存储器的公开区存有持卡人姓名、住址、电话号码和账号，任何读卡机都可读出这些数据，但不能改变它。系统的中央处理机也不会改变公开区内的任何信息。 高度个人化：更强的密码算法将用于灵巧卡系统，可完成认证、签字、杂凑、加解密运算，从而大大增强系统的安全性，使其用于安全性要求更高、处理功能要求更强的系统。不久，个人签字、指纹、视网膜图样等信息就可能存入灵巧卡，成为身份验证的更有效手段。未来的灵巧卡所包含的个人信息将越来越多，将成为的持证。正在研究将强的密码算法嵌入灵巧卡系统  灵巧卡的安全：涉及如芯片的安全技术、卡片的安全制造技术、软件的安全技术，以及安全密码算法和安全可靠协议的设计。灵巧卡的管理系统的安全设计也是其重要组成部分，如卡的制造、发行、使用、回收、丢失或损坏后的安全保障及补发、防伪造等是实用中要解决的重要研究课题 2018/12/5

灵巧卡的初始化。灵巧卡发行时都要经过个人化或初始化阶段，其具体内容随所生产的卡和应用模式不同而异。发卡机构根据系统设计要求将应用信息（如发行代码等）和购卡人的个人信息写入卡中，使该卡成为购卡人可用于特定应用模式且具有其个人特征的专有物。一般IC卡的个人化有以下几方面的内容： ① 软硬件逻辑的格式化； ② 写入系统应用信息和个人有关信息； ③ 印上卡的名称、发行机构的名称、持卡人的照片等。 2018/12/5

应用：有些国家已成批生产灵巧卡。自80年代中期法国就已大量使用灵巧卡，到现在已有2 000万张。欧洲已有2.5亿张灵巧卡，其中大部分是一次性预付款电话卡。1985年9月 Mastercard这一世界性信用卡公司在美国首都和佛罗里达州的棕榈泉就发行了5万张。除了银行系统外，在付费电视系统中也有实用。付费广播电视系统每20秒改变一次加密电视节目信号的密钥，用这类灵巧卡可以同步地更换解密钥，实现正常接收。灵巧卡的存储容量和处理功能的进一步加强，会使它成为身份验证的一种更为变通的工具，可进一步扩大其应用范围，如作护照、电话电视等计费卡、个人履历记录、电子锁的开锁钥匙、如电子货币、Internet上的电子商业、医疗保险、医疗信息等系统等。 2018/12/5

第七讲：数字签字与身份证明本讲到此结束。谢谢大家！。 2018/12/5

第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等

Similar presentations

Presentation on theme: "第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

第七讲：数字签字与身份证明 一、数字签字的基本概念 二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等

Similar presentations

Presentation on theme: "第七讲：数字签字与身份证明 一、数字签字的基本概念 二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等"— Presentation transcript:

Similar presentations

About project

反馈

第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等

Presentation on theme: "第七讲：数字签字与身份证明一、数字签字的基本概念二、几种常用的数字签字：RSA、ElGamal 、 Schnorr 、DSS等"— Presentation transcript: