零知识证明协议研究
零知识证明是零信任吗
零知识证明是零信任吗 导语 虽然零知识证明和零信任这两个词，都带有“零”，都与“信任”有关，但并不是一回事。两者本质上都要增强「信任」，但在增强「信任」的过程中，零知识证明强调不泄露知识；零信任强调不要过度授权。简单说，零知识是为了隐藏知识；零信任是为了控制信任。零知识证明解决了信任与隐私的矛盾：既通过「证明」提升「信任」，又通过「零知识」保护「隐私」。是两全其美的方案。探索零知识证明的过程，可以探索到安全的本质。安全之终极定义，不是启发式的CIA三性，而是采用形式化验证的可证明安全——上帝（“模拟者”）与科学（数学、计算复杂度）完美结合的推演过程。 一、了解零知识证明 1、零知识证明的定义 零知识证明（ZKP，Zero-Knowledge Proof）的定义为：证明者（prover）能够在不向验证者（verifier）提供任何有用信息的情况下，使验证者（verifier）相信某个论断是正确的。根据定义，零知识证明具有以下三个重要性质： (1)完备性（Completeness）： 只要证明者拥有相应的知识，那么就能通过验证者的验证，即证明者有足够大的概率使验证者确信。 （关于这里提到的“概率”，详见后面的“色盲游戏”）
(2)可靠性（Soundness）： 如果证明者没有相应的知识，则无法通过验证者的验证，即证明者欺骗验证者的概率可以忽略。 (3)零知识性（Zero-Knowledge）： 证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述，不会泄露任何关于知识的额外信息。 从定义中，还可以提取到两个关键词：“不泄露信息”+“证明论断有效”。再浓缩一下就是：隐藏+证明。所以，零知识证明的核心目的是：隐藏并证明需要它隐藏的各类秘密。（感觉很矛盾是吧） 2、零知识证明的源头 零知识证明是1984年由Goldwasser、Micali、Rackoff三个人提出，论文题目是《The Knowledge Complextiy of Interactive Proof Systems》（《交互式证明系统中的知识复杂性》）。 这篇论文其实发表在1989年。原因在于这篇论文的思想太过超前，以至于从1984年写出初稿到1989年正式被采纳发表，经历了整整五年时间。正是由于零知识证明这项开创性工作，Goldwasser和Micali两人在2012年分享了图灵奖——计算机领域最高奖项，也有“计算机界的诺贝尔奖”之称。 3、零知识证明的核心价值：消灭可信第三方 当互联?电?商务和在线交易蓬勃发展到今天，可信第三方（TTP，Trusted Third Party）几乎不可或缺。但大家体会不到的事实是，可信第三方引入了巨大的「信任成本」。对第三方的过度信任，会带来严重的「隐私泄露」、「单点失效」、「个?信息滥?」等问题。虽然学术界也提出“半可信第三方”（Semi-trusted
零知识证明及其应用
《网络安全》课程论文 题目零知识证明理论及其应用 学院计算机与信息科学学 软件学院 专业 年级 学号 姓名 指导教师 成绩_____________________ 2014年11月16 日
零知识证明理论及其应用 摘要：“零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。本文介绍了零知识证明的概念,并对零知识证明的一般过程进行分析.同时,阐述零知识证明的性质和优点.最后,综述了零知识证明的应用。 关键字：零知识证明身份认证交互式非交互式 一、引言 21世纪是信息时代，信息已经成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。 密码学的出现给这些安全带来了保证，而大量事实证明，零知识证明在密码学中非常有用。Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。 80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。在零知识证明中,一个人(或器件)可以在不泄漏任何秘密的情况下,证明他知道这个秘密..如果能够将零知识证明用于验证,将可以有效解决许多问题。 二、概念 “零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。 零知识证明分为交互式零知识证明和非交互式零知识证明两种类型。 三、零知识证明的一般过程 证明方和验证方拥有相同的某一个函数或一系列的数值.零知识证明的一般过程如下: 1.证明方向验证方发送满足一定条件的随机值,这个随机值称为"承 诺".[1] 2.验证方向证明方发送满足一定条件的随机值,这个随机值称为"挑 战".[1]
身份认证技术论文.doc
身份认证技术 摘要：身份认证是实现信息安全的基本技术，在本文中简要的介绍下几种不同类别的身份认证以及身份认证中的协议。 关键词：身份认证基于密码基于地址生物特征零知识Kerberos SSL 正文： 引言：现今已经是信息化的社会，信息技术成为了我们生活不可缺少的部分，所以信息的安全就成为了我们不得不关注的问题，而身份认证则是实现安全通信的重要手段，因此在这里简要的介绍下身份认证技术。 论文正文： 身份认证的概念 身份认证是系统审查用户身份的过程，从而确定该用户是否具有对某种资源的访问和使用权限。身份认证通过标识和鉴别用户的身份，提供一种判别和确认用户身份的机制。 计算机网络中的身份认证是通过将一个证据与实体身份绑定来实现的。实体可能是用户、主机、应用程序甚至是进程。 身份认证技术在信息安全中处于非常重要的地位，是其他安全机制的基础。只有实现了有效的身份认证，才能保证访问控制、安全审计、入侵防范等安全机制的有效实施。 在真实世界中，验证一个用户的身份主要通过以下三种方式： 所知道的。根据用户所知道的信息来证明用户的身份。 所拥有的。根据用户所拥有的东西来证明用户的身份。 本身的特征。直接根据用户独一无二的体态特征来证明用户的身份，例如人的指纹、笔迹、DNA、视网膜及身体的特殊标志等。 基于密码的身份认证： 密码认证的特点 密码是用户与计算机之间以及计算机与计算机之间共享的一个秘密，在通信过程中其中一方向另一方提交密码，表示自己知道该秘密，从而通过另一方的认证。密码通常由一组字符串来组成，为便于用户记忆，一般用户使用的密码都有长度的限制。但出于安全考虑，在使用密码时需要注意以下几点： （1）不使用默认密码、（2）设置足够长的密码、（3）不要使用结构简单的词或数字组合、（4）增加密码的组合复杂度、（5）使用加密、（6）避免共享密码、（7）定期更换密码 就密码的安全使用来说，计算机系统应该具备下列安全性： （1）入侵者即使取得储存在系统中的密码也无法达到登录的目的。这需要在密码认证的基础上再增加其他的认证方式，如地址认证。 （2）通过监听网络上传送的信息而获得的密码是不能用的。最有效的方式是数据加密。 （3）计算机系统必须能够发现并防止各类密码尝试攻击。可使用密码安全策略。 密码认证中的其它问题：
一个安全的广义指定验证者签名证明系统
第31卷第2期电子与信息学报Vol.31No.2 2009年2月 Journal of Electronics & Information Technology Feb. 2009 一个安全的广义指定验证者签名证明系统 陈国敏陈晓峰 (中山大学计算机科学系广州 510275) 摘要：广义指定验证者签名(UDVS) 可以实现任意的签名持有者能向任意的验证者证明签名者确实签署了该签名，而且验证者没有能力向第三方证明该签名是有效的。这种签名方案可以保护签名持有者的隐私信息，因而在证书系统中有着重要的应用。然而，UDVS需要签名持有者(designator)与指定的验证者(designated-verifier)通过签名者(signer)的公钥体系来生成自己的密钥对，这在现实情况下是不合理的。最近，Baek等人(2005)在亚洲密码会提出UDVSP (Universal Designated Verifier Signature Proof)来解决这个问题。该文首先指出Baek等人所给出的UDVSP协议存在一个安全性缺陷，即不满足UDVS系统中的不可传递性(non-transferability)，然后提出一种新的UDVSP协议，并证明该方案满足所定义的安全属性。 关键词：广义指定验证者签名证明；双线性对；承诺协议 中图分类号：TN918 文献标识码：A 文章编号：1009-5896(2009)02-0489-04 A New Secure Universal Designated Verifier Signature Proof System Chen Guo-min Chen Xiao-feng (Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China) Abstract: The notion of Universal Designated Verifier Signature (UDVS) allows any holder of a signature to convince any designated verifier that the signer indeed generated the signature without revealing the signature itself, while the verifier can not transfer the proof to convince anyone else of this fact. Such signature schemes can protect the privacy of signature holders and have applications to certification systems. However, they require the designated verifier to create a public key using the signer’s public key parameter and have it certified to ensure the resulting public key is compatible with the setting that the signer provided. This is unrealistic in some situations. Very recently, Baek et al introduced the concept of Universal Designated Verifier Signature Proof (UDVSP) to solve this problem in Asiacrypt 2005. In this paper, it is first showed that there exits a security flaw in this UDVSP, i.e., it does not satisfy the non-transferability. A new secure UDVSP system is proposed and the system is proved to achieve the desired security notions. Key words: Universal Designated Verifier Signature Proof (UDVSP); Bilinear pairings; Commitment protocol 1引言 近几年来很多学者力图解决现有数字签名中认证性和隐私性之间的冲突。Chaum 和 Van Antwerpen[1]首次提出了不可否认性数字签名的概念，它可以让签名者决定什么时候他或她的签名可以被验证。在另一些情况中，让签名者决定的不仅有特定的时间而且还有特定的人才能验证该数字签名是很重要的。这就是指定验证者签名[2](DVS)提出的动机。近年来，许多学者对不可否认签名及指定验证者签名进行了大量的研究，并给出了许多高效的方案[37]?。 Steinfeld等人[8]首次在2003年亚洲密码会提出了有关广义指定验证者签名(UDVS)的概念，这种方案可以看成是 2007-09-29 收到，2008-04-14改回 国家自然科学基金(60503006)和中韩国际合作研究基金(60611140543)资助课题对DVS的延伸，以解决类似以下例子的信用问题：假设Alice 是A大学的毕业生，她想去B公司找工作，负责面试她的考官Bob要验证她是否拿到A大学的毕业证，而Alice却不想让除Bob外的人知道自己获得了A大学的学位或者没有证据说明她获得了A大学的学位。由于一般的数字签名满足广义可验证性，所以很难实现Alice的要求。而广义指定验证者签名(UDVS)可以解决这个问题。但Steinfeld等人[8]的方案有个缺点是签名持有者(designator在上例中指的是Alice)要与指定的验证者(designated verifier在上例中指的是考官Bob)要通过签名者(signer在这里指的是学校A)的公钥体系来生成自己的公钥和私钥，这样就有个成本问题(可以想像，公司B面对的可能不是一个学校的学生，这就需要存储并计算数量巨大的公钥和私钥，带来巨大的成本，很多公司可能负担不起)，如果指定的验证者(desinated-verifier在上例中指的是考官Bob)不合作，那么这种数字签名机制就不
零知识证明
零知识证明 “零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。在Goldwasser等人提出的零知识证明中，证明者和验证者之间必须进行交互，这样的零知识证明被称为“交互零知识证明”。80年代末，Blum等人进一步提出了“非交互零知识证明”的概念，用一个短随机串代替交互过程并实现了零知识证明。非交互零知识证明的一个重要应用场合是需要执行大量密码协议的大型网络。大量事实证明，零知识证明在密码学中非常有用。 在零知识证明中,一个人(或器件)可以在不泄漏任何秘密的情况下,证明他知道这个秘密..如果能够将零知识证明用于验证,将可以有效解决许多问题.. 这是我前几天在网络上看到得，觉得很有意思，但现的问题是：要怎么做? 诸位发表点看法： 附相关零知识证明材料： 零知识证明不是证明在条款的数学感觉因为有一个固定的可能性p 在任一零知识证明Peggy 能提供对挑战的正确反应即使她不知道钥匙。但是如果测试被重覆n 计时欺诈被减少Peggy 的可能性p n , 和由增加测试胜者的数字可能使Peggy 的可能性降低欺诈到一个任意水平。 例子战略 Peggy 的公开密钥是一张大图表, 我们将称G。Peggy 被组建的G 某时从前,和广泛然后出版它。由于她特别地制造了它为目的, Peggy 知道一个汉密尔顿的周期在G。Peggy 将证明她的身份对胜者由证明, 她知道一个汉密尔顿的周期在G。即使G 是公开信息, 没人可能做这, 因为没人知道G 的一个汉密尔顿的周期, 并且发现汉密尔顿的周期在图表是一个困难的问题(参见NP 完整性) 。 但是, Peggy 不能简单地显露汉密尔顿的周期对胜者, 胜者(或偷听者) 从那以后能在将来扮演Peggy 。Peggy 不能显露任何信息在所有周期, 因为偷听者也许收集信息关于几个不同的场合和装配它入足够的信息能扮演Peggy 。 证明她的身份, Peggy 和胜者扮演以下比赛的几个圆: Peggy 标记G 端点以随机号。边缘可能然后代表作为一对这些数字。她列出G 边缘, 和编成密码各个边缘以一个另外密钥。她然后寄发被编成密码的边缘到胜者。 胜者翻转硬币。 * 如果硬币过来头, Peggy 向随机号投降密钥和测绘从端点。胜者解码边缘和然后核实, 被编成密码的边缘被派在步骤1 实际上做graph.g 和没有某一其它图表。 * 如果硬币过来尾巴, Peggy 投降密钥只为实际上形成汉密尔顿的周期的边缘。胜者解码这些边缘和核实, 他们的确形成正确长度的周期。
零知识证明
阿里巴巴的零知识证明--淘自科学松鼠会 战争中你被俘了，敌人拷问你情报。你是这么想的：如果我把情报都告诉他们，他们就会认为我没有价值了，就会杀了我省粮食，但如果我死活不说，他们也会认为我没有价值而杀了我。怎样才能做到既让他们确信我知道情报，但又一丁点情报也不泄露呢？ 这的确是一个令人纠结的问题，但阿里巴巴想了一个好办法，当强盗向他拷问打开山洞石门的咒语时，他对强盗说：“你们离我一箭之地，用弓箭指着我，你们举起右手我就念咒语打开石门，举起左手我就念咒语关上石门，如果我做不到或逃跑，你们就用弓箭射死我。” 强盗们当然会同意，因为这个方案不仅对他们没有任何损失，而且还能帮助他们搞清楚阿里巴巴到底是否知道咒语这个问题。阿里巴巴也没损失，因为处于一箭之地的强盗听不到他念的咒语，不必担心泄露了秘密，而且他确信自己的咒语有效，也不会发生被射死的杯具。 强盗举起了右手，只见阿里巴巴的嘴动了几下，石门果真打开了，强盗举起了左手，阿里巴巴的嘴动了几下后石门又关上了。强盗还是有点不信，说不准这是巧合呢，他们不断地换着节奏举右手举左手，石门跟着他们的节奏开开关关，最后强盗们想，如果还认为这只是巧合，自己未免是个傻瓜，那还是相信了阿里巴巴吧。 “零知识证明”说的是示证者向验证者表明他知道某种秘密，不仅能使验证者完全确信他的确知道这个秘密，同时还保证一丁点秘密也不泄露给验证者。阿里巴巴的这个方案，就是认证理论“零知识证明”的一个重要协议。 除了被俘后如何靠情报保命这个问题，零知识证明在社会领域中还有着很多应用场合。例如你证明了一个世界级的数学难题，但在发表出来之前，总是要找个泰斗级的数学家审稿吧，于是你将证明过程发给了他，他看懂后却动了歪心思，他把你的稿子压住，把你的证明用自己的名义发表，他名利双收，你郁闷至死，你去告他也没用，因为学术界更相信的是这位泰斗，而不是你这个无名之辈。 这并不是天方夜谭，而是学术界常见的难题，前些年有个博士生告他的泰斗级导师剽窃他的成果，但除了令师生关系恶化外没有任何效果，最后他使出了撒手锏，称他在给导师审阅的论文的关键公式中，故意标错了一个下标，而这会导致整个推导失败。学术委员会一查果真如此，但还是有倾向于泰斗的声音，有人说那是泰斗的笔误，只不过让你发现了而矣，并不能证明那公式就是你推导出来的。 这个博士生故意标错下标，不能说他没有心眼，但他没有把“零知识证明”理论用好，以致于落到这种地步。“零知识证明”早在1986年就被A.Fiat和A.Shamir用数学的方法给出了解决方案，并在同年申请了美国专利，但由于该理论可能被用于军事领域，专利局被军方密令搁置，6个月后，军方命令：“该申请发表后会有害于国家安全……所有美国人的研究未经许可而泄露将会被判刑罚款”。看来军方认为作者肯定是美国人了，但作者实际上是在美国申请专利的以色列人，研究也是在以色列的大学里做的，军方这个命令摆了个大乌龙，虽然两天后撤消了，但已经成为了学术界的笑柄。 这个笑柄也说明了一个问题，即“零知识证明”非常重要。基于数学的推理虽然非常复杂，但思路却很简单，上述的阿里巴巴方案就是其中之一。其它的一些方案，也都是像这样遵循着分割和选择（Cut and Chose）协议的。
身份识别技术
身份识别技术 我们生活的现实世界是一个真实的物理世界，每个人都拥有独一无二的物理身份。而今我们也生活在数字世界中，一切信息都是由一组特定的数据表示，当然也包括用户的身份信息。如果没有有效的身份认证管理手段，访问者的身份就很容易被伪造，使得任何安全防范体系都形同虚设。因此，在计算机和互联网络世界里，身份认证是一个最基本的要素，也是整个信息安全体系的基础。 身份认证是证实客户的真实身份与其所声称的身份是否相符的验证过程。目前，计算机及网络系统中常用的身份认证技术主要有以下几种： 用户名/密码方式：用户名/密码是最简单也是最常用的身份认证方法，是基于“what you know”的验证手段。每个用户的密码是由用户自己设定的，只有用户自己才知道。只要能够正确输入密码，计算机就认为操作者就是合法用户。实际上，由于许多用户为了防止忘记密码，经常采用诸如生日、电话号码等容易被猜测的字符串作为密码，或者把密码抄在纸上放在一个自认为安全的地方，这样很容易造成密码泄漏。即使能保证用户密码不被泄漏，由于密码是静态的数据，在验证过程中需要在计算机内存中和网络中传输，而每次验证使用的验证信息都是相同的，很容易被驻留在计算机内存中的木马程序或网络中的监听设备截获。因此，从安全性上讲，用户名/密码方式一种是极不安全的身份认证方式。 智能卡认证：智能卡是一种内置集成电路的芯片，芯片中存有与用户身份相关的数据，智能卡由专门的厂商通过专门的设备生产，是不可复制的硬件。智能卡由合法用户随身携带，登录时必须将智能卡插入专用的读卡器读取其中的信息，以验证用户的身份。智能卡认证是基于“what you have”的手段，通过智能卡硬件不可复制来保证用户身份不会被仿冒。然而由于每次从智能卡中读取的数据是静态的，通过内存扫描或网络监听等技术还是很容易截取到用户的身份验证信息，因此还是存在安全隐患。 动态口令：动态口令技术是一种让用户密码按照时间或使用次数不断变化、每个密码只能使用一次的技术。它采用一种叫作动态令牌的专用硬件，内置电源、密码生成芯片和显示屏，密码生成芯片运行专门的密码算法，根据当前时间或使用次数生成当前密码并显示在显示屏上。认证服务器采用相同的算法计算当前的有效密码。用户使用时只需要将动态令牌上显示的当前密码输入客户端计算机，即可实现身份认证。由于每次使用的密码必须由动态令牌来产生，只有合法用户才持有该硬件，所以只要通过密码验证就可以认为该用户的身份是可靠的。而用户每次使用的密码都不相同，即使黑客截获了一次密码，也无法利用这个密码来仿冒合法用户的身份。动态口令技术采用一次一密的方法，有效保证了用户身份的安全性。但是如果客户端与服务器端的时间或次数不能保持良好的同步，就可能发生合法用户无法登录的问题。并且用户每次登录时需要通过键盘输入一长串无规律的密码，一旦输错就要重新操作，使用起来非常不方便。 USB Key认证：基于USB Key的身份认证方式是近几年发展起来的一种方便、安全的身份认证技术。它采用软硬件相结合、一次一密的强双因子认证模式，很好地解决了安全性与易用性之间的矛盾。USB Key是一种USB接口的硬件设备，它内置单片机或智能卡芯片，可以存储用户的密钥或数字证书，利用USB Key内置的密码算法实现对用户身份的认证。基于USB Key身份认证系统主要有两种应用模式：一是基于冲击/响应的认证模式，二是基于PKI体系的认证模式。 生物特征认证：基于生物特征的身份识别技术主要是指通过可测量的身体或行为等生物特征进行身份认证的一种技术，是基于“what you are”的身份认证手段，。生物特征是指唯一的可以测量或可自动识别和验证的生理特征或行为方式。生物特征分为身体特征和行为特征两类，身体特征包括：指纹、掌型、视网膜、虹膜、人体气味、脸型、手的血管和DNA等；
零知识身份认证
4．零知识身份认证 零知识证明（zero-knowledge proof）的思想是：证明者Peggy拥有某些知识（如某些长期没有解决的难问题的解决方法），零知识证明就是在不将该知识的内容泄露给验证者Victor的前提下，Peggy向Victor证明自己拥有该知识。首先，我们看下面Peggy和Victor之间的一段对话： Peggy：“我可以对密文为C的消息进行解密。” Victor：“我不相信。请证明。” Peggy（糟糕的回答）：“密钥是K，您可以看到消息解密成了M。” Victor：“哈哈！现在我也知道了密钥和消息。” 这里，Peggy虽然证明了自己拥有某些知识（密钥K及明文M），却向Victor 泄露了这些知识。一个更好的对话是： Peggy：“我可以对加密为C的消息进行解密。” Victor：“我不相信。请证明。” Peggy（好的回答）：“让我们使用一个零知识协议，我将以任意高的概率证明我的知识（但是不会将关于消息的任何情况泄露给您）。” Victor：“好”。 Peggy 和 Victor 通过该协议…… 可以使用洞穴例子来解释零知识，C和D之间存在一个密门，并且只有知道咒语的人才能打开。Peggy知道咒语并想对Victor证明，但证明过程中不想泄露咒语。
图7.13 零知识洞穴 步骤如下： （1）Victor站在A点； （2）Peggy一直走进洞穴，到达C点或者D点； （3）在Peggy消失在洞穴中之后，Victor走到B点； （4）Victor随机选择左通道或者右通道，要求Peggy从该通道出来； （5）Peggy从Victor要求的通道出来，如果有必要就用咒语打开密门； （6）Peggy和Victor重复步骤（1）至（5）n次。 如果Peggy不知道这个咒语，那么只能从进去的路出来，如果在协议的每一轮中Peggy都能按Victor要求的通道出来，那么Peggy所有n次都猜中的概率是1/2n。经过16轮后，Peggy只有65536分之一的机会猜中。于是Victor可以假定，如果所有16次Peggy的证明都是有效的，那么她一定知道开启C点和D 点间的密门的咒语。 我们来看一个零知识证明的例子。图是否同构是NP完全问题，对于一个非 常大的图，判断两个图是否同构是非常困难的。对于图G 1和G 2 ，如果存在一个 一一对应的函数F：F的定义域是G 1的顶点集。F的值域是G 2 的顶点集。当且仅 当[g1,g2]是G 1中的一条边，[F(g1),F(g2)]才是G 2 中的一条边，称G 1 和G 2 同构 的。 假设Peggy知道图G 1和G 2 之间同构，Peggy使用下面的协议将使Victor相 信G 1和G 2 同构： （1）Peggy随机置换G 1 产生另一个图H，并且H和G 1 同构。因为Peggy知 道G 1和H同构，也就知道了H和G 2 同构。 （2）Peggy把H送给Victor。 （3）对如下两个问题Victor选择其中的一个，要求Peggy证明。但是，Victor 不要求两者都证明。 证明G 1 和H同构，或者 证明G 2 和H同构。 （4）Peggy按Victor的要求证明。 （5）Peggy和Victor重复步骤（1）至（4）n次。
网络安全方面题目
第一章 1、端口号的分类范围 ●Well-known 端口0-1023：一般固定分配给一些服务 ●注册端口：1024-49151：它们被LANA分配给每个专用程序 ●动态或私有端口：49152-65535: 2、OSI7层 物理层（最底层、第一层），这一层的数据叫比特；数据链路层，交换机，这一层的数据叫帧；网络层，路由器，这一层的数据叫数据包；传输层，定义了一些传输数据的协议和端口号（WWW端口80等；工作在传输层的一种服务是T C P / I P 协议套中的T C P （传输控制协议），另一项传输层服务是I P X / S P X 协议集的S P X （序列包交换）。这一层数据叫段；会话层，通过传输层（端口号：传输端口与接收端口）建立数据传输的通路；表示层，表示层管理数据的解密与加密，如系统口令的处理；表示层协议还对图片和文件格式信息进行解码和编码；应用层，终端应用；文件传输、文件管理及电子邮件的信息处理。 3、常见端口号 ●21端口分配给FTP(文件传输协议)服务 ●25端口分配给SMTP（简单邮件传输协议）服务， ●80端口分配给HTTP服务， ●135端口分配给RPC（远程过程调用）服务等等。 4、危险的端口号，是什么服务：135； 端口：135 服务：Location Service 说明：Microsoft在这个端口运行DCE RPC end-point mapper为它的DCOM服务。这与UNIX 111端口的功能很相似。使用DCOM和RPC的服务利用计算机上的end-point mapper注册它们的位置。远端客户连接到计算机时，它们查找end-point mapper找到服务的位置。HACKER扫描计算机的这个端口是为了找到这个计算机上运行Exchange Server吗？什么版本？还有些DOS攻击直接针对这个端口。 5、137端口号，主要作用是什么，IP地址查询；138，136，139 端口：137、138、139 ，服务：NETBIOS Name Service 说明：其中137、138是UDP端口，当通过网上邻居传输文件时用这个端口。而139端口：通过这个端口进入的连接试图获得NetBIOS/SMB服务。这个协议被用于windows 文件和打印机共享和SAMBA。还有WINS Regisrtation也用它。 6、TCP三次握手，四次挥手连接断开 第二章 1、什么是对称加密，什么是非对称加密，意义在哪里，区别在哪里，要理解掌握 2、公钥(非对称加密)跟私钥（对称加密）要理解，相关关系要明白。 3、流密码和分组密码都属于对称密钥算法。流密码的基本思想是利用密钥产生一个密钥流，并通过相应的规则对明文串进行寄卖合计没处理。而分组密码是将明文分为固定长度的分组，然后通过若干轮函数的迭代操作来产生密文。函数由于在每一轮的操作中都是用，所以称为轮函数，其本轮的输入时上一轮的输出加上密钥。 4、流密码有：基于移位寄存器及硬件实现的A5/1算法；基于软件实现的流密码RC4算法。 5、分组加密有：DES、3DES、AES、IDEA、RC5/RC6，TEA。 6、非对称加密算法：RSA，DH算法，椭圆曲线算法 7、Des加密算法（大题），流程图，怎么实现这个加密，要看懂
5零知识证明
零知识证明
零知识证明的概念 设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。 体设是明这事实的实体 某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。 这些信息是什么我们称实现了最小泄露证明 如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作任何知识我们称实现了零知识证明相应的协议称作 零知识协议。
零知识证明的概念 在最小泄露协议中满足下述两个性质： (1)P换言之若不知道个定理的证 (1) P无法欺骗V。换言之，若P不知道一个定理的证 明方法，则P使V相信他会证明定理的概率很低。 （正确性） (2) V无法欺骗P。换言之，若P知道一个定理的证明 方法，则P使V以绝对优势的概率相信他能证明。 （完备性） 在零知识协议中，除满足上述两个条件以外，还满足下述性质： 还满足下述性质 (3) V无法获取任何额外的知识。（零知识性）
零知识洞穴 设P知道咒语，可打开C和D之间的秘密门，不知道者则走向死胡同。现在来看P如何向V出示证明使其相信他知道这个秘密，但又不告诉V有关咒语。 协议1：洞穴协议 V站在A点； P进入任一点C或D； 进洞之后点 当P进洞之后，V走向B点； V叫P：(a)从左边出来，或(b)从右边出来 P按照要求实现（有咒语）； P和V重复执行(1)~(5)共n次。
零知识洞穴 A B C D 若P不知道咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有50% n次机会完全猜中。 要求协议执行次则只有50%次机会完全猜中此洞穴问题可以转化为数学问题，P知道解决某个难题的秘密信息，而V通过与P交互作用验证其真伪。
北京科技大学 数字签名与身份认证作业答案汇总
1）网络安全攻击的形式主要有哪些？可分为哪两大类？ 解：主要分为被动攻击和主动攻击两种形式。被动攻击：析出信息内容，通信量分析；主动攻击：中断攻击，篡改攻击，伪造攻击，重放攻击。 2）实体认证、数据（消息）认证、完整性证明有什么区别？ 解：实体认证，数据（消息）认证，完整性证明对信息系统各个不同的部分进行验证。实体认证是对信息系统的使用者（实体）的身份进行确认的过程，消息认证是对信息系统中的数据或通信中的消息来源进行认证，完整验证确保信息没有被未经授权的或未知的手段所修改。3）如何进行双向认证？ 解：数字认证过程被认为是一个交互式的证明过程，交互式过程中包括两个实体：证明者和验证者，交互式证明系统是一个计算模型，像其它计算模型一样，我们的目标是一个语言类L，和一个给定的输入X，判断X是否在L中，所以称为双向认证。 4) 简述什么是身份管理？其目的何在？ 解：身份管理系统是指一个广义的管理区,对该系统内的个人进行身份识别管理,其目的是通过授权或加以限制来控制个人接近系统内部的资源 5）简单讨论数字认证技术是一个系统性学科。 解：系统性学科是各种知识由组合关系和聚合关系构成的严整有序的规则系统，数字认证技术是一门多学科的综合性技术，分为密码学技术，信息隐藏技术，模式识别技术等，所以说它是一个系统型学科。 6）讨论TCP/IP协议各层的安全目标以及改进措施 解：可用性和效率是Internet系统的重点，没有进行安全设计,分为三层。物理层的安全目标是信道加密，改进措施是信道安全；IP层的安全目标是寻路安全，改进措施是路由认证；TCP层的安全目标是端对端安全，改进措施是端对端认证，安全套接字SSL 1）简述交互式证明系统的三个性质？ 能力假设：验证者具有多项式时间确定图灵机的计算机能力，但是证明者具有无限大的计算能力； 运行规则：博弈双方共走m步，且由验证者（或证明者）先行； 胜负规则：x属于L，当且仅当，证明者在以x为输入的对局中有必胜策略。 2）证明基于二次非剩余的证明协议是一个交互证明系统，并说明如何将Soundness概率降为任意小？ 基于二次非剩余问题的证明协议 第一步：验证者随机选择整数b∈{0，1}，以及一个自然数z∈Z，然后计算数值w如下： w=z*z（mod n）（if b=1），w=x*z*z（mod n）（if b=0），并将其送给证明者。 第二步：证明者判定w是否属于QNRn，如果是，则令b’=0；否则，令b’=1，并将所得结果b’∈{0，1}传送给验证者。 第三步：验证者检测是否b=b’，如果是，输出1，否则输出0。 证明： 完备性：如果x是二次非剩余类，那么证明者P能以概率1判定w是否是非剩余类，因此验证者V将以概率1接受证明者P的证明； 可靠性：如果x是二次剩余类，那么无论验证者V选择何种b，所发送的w都是二次剩余的，因此，P将无法进行判定b，因此只能以概率1/2猜对b。因此，V将以概率1/2接受P的证明。 当x为二次剩余类时，V只能以概率1/2接受P的证明。我们可以增加证明的次数，使得验证成功的概率为1/2的多次方，Soundness的概率能降为任意小。 3）论述当n＝pq，p和q为2个RSA型大素数时，基于二次非剩余的证明协议中证明者与验证者的能力差异？ 当x为二次剩余类时，证明者无论具有怎样（无穷）的计算能力都无法欺骗验证者。 当x为二次非剩余类是，证明者是诚实的，验证这都无法推翻证明者的结论。 4）分析当n=21,x=15时,对基于二次非剩余问题的证明协议进行安全性分析 QR21={0,1,4,7,9,14,15,16,18} QNR21={2,3,5,6,8,10,11,12,13,17,19,20} x=15是二次非剩余类，那么P能以概率1判定w是否是剩余类， V选择b=1，z=6，w=15是二次剩余类； V选择b=0，z=6，w=15是二次剩余类； 所以，无论V选择何种b，所发送的w都是二次剩余的，因此，P将无法进行判定b，因此只能以概率1/2猜对b。 5）零知识证明是指验证者能获得最后的证明结果,但是却无法获得待验证的信息,请改进山洞证明系统加以举例说明 假设一个山洞有两个通路，但是中间有一堵墙隔离开，证明者知道墙上的机关，能通过这堵墙，那么就可以到达墙的另一边来证明他知道机关怎么打开，同时墙恢复原来的样子。可以看出，如果通过证明，那么可以知道证明者具有通过墙的方法，但是验证者无法知道是什么方法。 1.RSA解密的有效性证明 解：要验证RSA解密的有效性，只需验证解密是加密的逆运算：定义为欧拉函数，则 由于ab(mod()),所以存在某个整数t≥1有ab=t,对所有与n互素的整数x有 2.Elgamal密码系统？ 密钥对产生办法。首先选择一个素数p，获取一个素数p的一个原根g(若g模p的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）) 和一个随机数x，且g和 x 均小于 p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算a = g^k ( mod p )再用扩展 Euclidean 算法对下面方程求解b：M = xa + kb ( mod p - 1 )签名就是( a, b )。随机数k须丢弃。 验证时要验证下式：y^a * a^b ( mod p ) = g^M ( mod p )同时一定要检验是否满足1<= a < p。否则签名容易伪造。ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算 a = g^k ( mod p ), b = y^k M ( mod p )( a, b )为密文，是明文的两倍长。解密时计算M = b / a^x ( mod p ) ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数.因子以抵抗Pohlig& Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。
《密码学》总复习试题模拟卷6(试题部分)
系名____________班级____________姓名____________学号____________ 密封线内不答题 一、 填空题（35分，1分/空） 1．同余式具有传递性，即是说：如果a ≡b （mod n ），b ≡c （mod n ），那么 a ≡c （mod n ） 。 2．密码学是研究通信安全保密的科学，它包含两个相对独立的分支： 密码编码学 、 密码分析学 。 3．在无干扰的条件下，假定密码分析者可以得到密文C ，还假定密码分析者知道明文的统计特性、加密体制及其密文的统计特性（这正是Kerchkhoffs 假设）但不知道所截获的密文C 所用的特定密钥。因此，在这种假设下，密码的安全 性完全取决于 所选用的密钥安全性 。 4．从熵的基本性质可推知，保密系统的 密钥量 越小，其密文中含有的关于明文的信息量就越大。（至于密码分析者如何有效地提取这些信息是另外的问题）从密码系统设计者确度看，自然要选择足够大的 密钥量 ，而且希望从密文中提取的有关明文的信息尽可能地小。 5．为保证安全性，在设计分组密码时，密码变换必须足够复杂，尽量使用 混淆 与 扩散 原则。这样使攻击者除了用 穷举 攻击以外，找不到其他简洁的数学破译方法。 6．DES 是一个 分组密码 算法，它使用 56位 位的密钥，以64位（一个分组）为单位对数据分组进行加/解密，密文与明文长度 相同均为 64位 。DES 是一个对称密码体制，加/解密使用同一密钥，同时DES 的加密与解密使用同一算法（这样，在硬件与软件实现时，有利于加密单元的重用）。DES 的保密性依赖于 密钥 。 7．设),,,,(1111D E K C M =Φ和 ),,,,(2221D E K C M =Φ是两个密码体制，它们的明文和密文空间相同，1Φ和2 Φ的乘积定义为密码体制(D E K K M C ,,,,21?)，记为21Φ?Φ，这就是 所谓的 乘积 密码体制。 8．群是一个代数系统，它由一个非空集合G 组成，在集合G 中定义了一个二元运算“·”，满足：（1）封闭性，即：对任意的a,b ∈G ，有a ·b ∈G ；（2）单位元结合律，即：对任何a,b,c ∈G ，有a ·b ·c=(a ·b)·c=a ·(b ·c)；（3）逆元，即：存在1G ∈一个元素，对任意元素a ∈G,(乘法运算满足)a ·1=1·a=a ；（4）即对任意a ∈G ，存在一个元素a 1 -∈G ， 使得a ·a 1 -= a 1 -·a=1；把满足上面性质的代数系统称为群,记作
密码学基础大作业
《密码学基础》大作业 班级： 学号： 姓名： 完成时间：
参考题目：（可选择其中一个完成） 1.DES解密算法的程序实现（将上机实验1的密文解为明文） 2.AES加密算法的程序实现（将上机实验1的明文加密） 3.RSA加密算法的程序实现（将上机实验1的明文加密） 4.MD5压缩函数的程序实现（将文件test.txt的信息压缩为128比特） 5.SHA-1压缩函数的程序实现（将文件test.txt的信息压缩为160比特） 6.数字签名技术的原理探讨 7.最新密码学理论研究动态 8.密码学发展简史 9.密码学在实体认证和身份识别中的应用 10.现代密码学中对称密码体制和非对称密码体制的比较与分析 要求：条理清楚，表达准确，将查找的各类资料整理清楚，形成自己的语言表达清楚；同时在最后部分注明参考资料的来源。 大作业上交时间为1月8日24:00前，电子版资料发送至ap08123@https://www.wendangku.net/doc/7e11891558.html,，邮件名格式为：学号+姓名+大作业。如选做非程序实现题目，大作业字数不少于6000字，如大作业中能合理引用图片和表格会酌情加分。
?《Handbook of Applied Cryptography》: Chapter 10 ?《Applied Cryptography: Protocols, algorithms, and source code in C》：Section 3.2-3.3，5.1-5.2；Chapter 21 密码学在实体认证和身份识别中的应用 随着时代的进步，科技的逐渐发达，网络上的虚拟世界也发展的越来越广泛，可是与此同时，产生的问题也越来越多，身份识别便是其中之一，如何辨识网络另一端的身份已经成为一个很迫切的问题。能够正确认证用户的身份在许多情况下都有对身份识别认证的要求，在实体认证和身份识别中，密码学便充当了一个至关重要的角色，例如使用6位密码在自动取款机（ATM）上取钱；通过计算机网络登录远程计算机，给出用户名和密码，保密通信双方交换密钥时需要确保对方的身份等。 现代密码学 首先介绍一下密码学这一门学科。现代密码学研究信息从发端到收端的安全传输和安全存储，是研究“知己知彼”的一门科学。其核心是密码编码学和密码分析学。前者致力于建立难以被敌方或对手攻破的安全密码体制，即“知己”；后者则力图破译敌方或对手已有的密码体制，即“知彼”。《现代密码学》系统地讲述了密码学的基础理论与应用技术。主要内容包括密码学的信息论基础、密码学的复杂性理论、流密码、分组密码、公钥密码、Hash函数、数字签名、密码协议和密钥管理。《现代密码学》内容丰富，取材经典、新颖，概念清楚，各章后面配有大量习题。《现代密码学》可作为高等院校信息安全、通信工程等相关专业本科生的教材，也可供研究生与相关技术人员学习参考。 实体认证 实体认证：又称为鉴别、身份识别。它是这样一个过程，即其中一方确信参与协议的第二方的身份，并确信第二方真正参与了该过程。用户的身份识别是许多应用系统的第一道防线，其目的在于识别用户的合法性，从而阻止非法用户访问系统。身份识别（认证）对确保系统和数据的安全保密是极其重要的。 身份识别的基础：已知事物：口令、个人识别码(PIN)、挑战-响应协议中已被证实的秘密或私钥。已拥有的事物：通常是物理配件。如，磁卡、智能卡(或IC卡)、口令生成器。固有事物(对某个人)：利用人类物理特征和无意行为。如，手写签名、指纹、声音、视网膜模式、手的几何形状等。（非密码学的） 身份识别协议的目的：1、在诚实的情况下，声称者A能向验证者B证明他确实是A；2、在声称者A向验证者B声称他的身份后，验证者B不能获得任何有用的信息，B也不能模仿A向其他第三方证明他就是A。3、任何不同于A的实体C以A的身份，让B相信C是A的概率可忽略不计 身份识别协议的性质：