（计算机软件与理论专业论文）智能卡身份识别协议的研究.pdf

西华大学硕士学位论文 智能卡身份识别协议的研究 计算机软件与理论专业 研究生黄海指导老师蔺大正教授 身份认证协议是密码学协议研究的重要内容。身份认证对于保障信息只被 台法授权用户访问起到至关重要的作用，它是系统的第一道防线，因而加强对 身份认证协议的研究是非常必要的。 近年来，基于智能卡的应用越来越多，因而本文主要关注适用于智能卡领 域的身份识别协议。 本文主要的工作如下： 第一部分首先对智能卡领域的身份识别协议进行了分析和研究，并介绍几 种适用于智能卡的常用身份识别协议，并在v i t o rs h o u p 的2 “次根识别协议 的基础上经过适当变动，并从另外的角度用证明了其在主动攻击对手模型之下 不可模仿性，这种证明方法是构造性的，而原文的证明方法是非构造性的。 第二部分构造了一个基于身份的交互式共享验证的身份认证方案，该方案 是由一个身份识别协议和一个一股接入结构的秘密共享方案有机地结合。该方 案对已有的群体验证的身份认证协议进行了改进，较好地解决了n 个验证者是 有不同权利时的共享验证的身份认证的问题。在此方案中，每一个验证组成员 只需保存一个子秘密，而且每个成员的子秘密可以重复使用。 关键词：身份认证身份识别零知识证明证据不可区分一般接入结构 基于身份的密码学 西华大学硕士学位论文 r e s e a r c ho ni d e n t i f i c a t i o np r o t o c o l i ns m a r tc a r d c o m p u t e rs o f t w a r ea n dt h e o r y m a s t e rc a n d i d a t e ：h u a n gh a is u p e r v i s o r ：d a z h e nl i n i d e n t i t ya u t h e n t i c a t i o np r o t o c o li sap a r to fc r y p t o g r a p h yp r o t o c o la n dp l a ya i m p o r t a n t r u l ei n p r o t e c t i n g i n f o r m a t i o nf r o mu n a u t h o r i z e d a c c e s s i d e n t i t y a u t h e n t i c a t i o ni st h ef i r s td e f e n c ef o rs y s t e m ，t h u si ti sn e c e s s a r yt os t r e n g t ht h e r e s e a r c hf o ri d e n t i t ya u t h e n t i c a t i o n r e c e n t l y , m o r ea n dm o r ea p p l i c a t i o n sa r eb a s e do rs m a r tc a r d 、s o t h i sp a p e r m a i n l yp a ya t t e n t i o nt oi d e n t i f i c a t i o np r o t o c o li ns m a r tc a r d i nt h ef o r m e rp a r to ft h i s p a p e r w ea n a l y s es o m ei d e n t i t yi d e n t i f i c a t i o n s c h e m e su s e df o rs m a r tc a r df i e l da n di n t r o d u c es o m gi d e n t i f i c a t i o np r o t o c o l s s u i t a b l ef o rs m a r tc a r d t h e nae f f i c i e n tp r o t o c o li sp r o p o s e dw h i c hb a s e do na k n o w ni d e n t i f i c a t i o np r o t o c o la n dp r o v e db yc o n s t r u c t i v er e d u c t i o nm e t h o d s s u b s e q u e n t l y , ai d - b a s e di n t e r a c t i v ei d e n t i t ya u t h e n t i c a t i o ns c h e m ew i t hs h a r e d v e r i f i c a t i o ns c h e m ei sp r o p o s e d t h i ss c h e m ec o m b i n eai d e n t i f i c a t i o np r o t o c o lw i t h as e c r e ts h a r i n gs c h e m ew i t ha c c e s ss t r u c t u r ea n di m p r o v ek n o w na u t h e n t i a t i o n s c h e m ew i t hs h a r e dv e r f i c a t i o na n dr e s o l v et h es i t u a t i o ni nw h i c hnv e r i f i e r sh a v e d i f f e r e n tr i g h t e v e r yv e r i f i e rh o l d so n l yo n es u b s e c r e ta n de v e r y o n e ss n b s e c r e tc a n b eu s e dr e p e a t e d l y k e yw o r d s ：i d e n t i t ya u t h e n t i c a t i o n ，i d e n t i t yi d e n t i f i c a t i o n ，z e r o k n o w l e d g e ，w i t n e s s i n d i s t i n g u i s h a b l e ，a c c e s ss t r u c t u r e ，i d e n t i t y - b a s e dc r y p t o g r a p h y i l 西华大学硕士学位论文 1 绪论 1 1 研究目的及意义 信息安全的内容主要是信息安全涉及到信息的保密性 ( c o n f i d e n t i a l i t y ) 、完整性( i n t e g r i t y ) 、可用性( a v a i l a b i l i t y ) 、可控性 ( c o n t r o l l a b i l i t y ) 、不可否认性( n o n r e p u d i a t i o n ) 。综合起来说，就是要保 障电子信息的有效性【”。但是开放的网络环境中，d o l e v - y a o 2 】的攻击模型下， 对手m a l i c e 甚至拥有控制整个网络的能力，发送到网中的任何消息都可看成 发送给m a l i c e 处理的。m a l i c e 能截听、篡改、伪造、重放网络中任何消息， 互联网的开放性大大降低了网络环境的可信性。 保密技术和认证技术是保障信息安全的两个关键技术。认证技术又可分为 数据源认证、实体认证、认证的密钥交换【3 1 ，和数据源认证相关的概念是消息 完整性，数字签名。实体认证则用于鉴别用户身份，限制非法用户访问系统资 源。有时认证比加密还重要。 通信双方的信任问题是信息安全的主要问题和关键问题之一。信任是交易 的基础，因此美国国防部在今后1 0 年的信息安全发展纲要中，将身份认证技 术作为重点的科研项目l ”。身份认证( i d e n t i t ya u t h e n t i c a t i o n ) 又称识别 ( i d e n t i f i c a t i o n ) 、实体认证( e n t i t ya u t h e n t i c a t i o n ) 、身份验证( i d e n t i t y v e r i f i c a t i o n ) 。身份认证对于保障信息被合法授权用户访问起到至关重要的 作用，它是系统的第一道防线，用户在访问安全系统之前，必须首先经过身份 认证系统识别身份，然后访问监视器，监视器根据用户的身份和授权数据库来 决定用户是否有权利访问系统资源。访问控制和审计系统都要依赖身份认证系 统提供的身份信息。可见，身份认证系统在安全系统中地位十分重要，可以说 是一种最基本的安全服务。其它安全服务都要依赖于它。一旦身份认证系统被 攻破，其它安全服务将形同虚设。黑客攻击的目标往往就是身份认证系统。因 而身份认证是系统安全的一个关键环节。因此要加快我国信息安全的建设，加 强身份认证机制的研究是一个非常重要的课题【4 】。 西华大学硕士学位论文 f i g u r e1 1 1l o g i c a lc o n s t r u c t i o no f s e c u r t ys y s t e m 图1 1 1 安全系统的逻辑结构 严格来说：身份认证和身份识别的定义是不一样的，按照文献1 5 l 的说法： 身份认证：a 向b 证明他是a ，而其他人不能向b 证明他是a ； 身份识别：a 向b 证明他是a ，而b 不能向其他人证明他是a 。 身份认证往往和密钥交换结合在一起，身份识别则往往不考虑密钥交换。 提到身份认证，人们可能马上就会想到口令方式，但是口令方式的弱点是 显然的：首先，口令可能被验证者或者其它窃听者获取，这样对手就能利用口 令模仿最初的认证者了，所以一次性i z i 令，动态口令方案相继被提1 6 , 7 1 ；其次， 我们一般把口令设计成容易记住的字母和数字的组合，这样，容易受到离线的 字典猜测攻击【。一个更好的认证方法是挑战一应答方式，验证者发送给申请者 一个随机数，申请者对这个随机数进行某种运算( 如加密、签名运算) ，并把 运算结果送还给验证者，然后验证者验证这个应答是否正确。这方面有许多协 议被提出，但总的来说还存在一些不足。 在身份认证的历史上，人们曾经提出了许许多多身份认证协议，但提出一 段时间后可能发现某些安全漏洞，于是对协议再进行改动，然后继续使用。正如 文献归】所言，这一过程可能周而复始。这样的设计方法存在以下问题：( 1 ) 我 2 西华大学硕士学位论文 们无法预料新的分析技术的提出时间，在任何时候都有可能提出新的分析技 术：( 2 ) 这种做法使我们很难确信协议的安全性，反反复复的修补更增加了人 们对安全性的担心，也增加了实现代价或成本。 可证明安全性理论1 1 0 】就是针对上述问题而提出的一种解决方案。 首先在所有的密码算法和协议中，我们必须考虑两个问题： 1 确定所设计的安全方案或协议的安全目标。例如，识别协议安全目标是 证据隐藏，加密方案的安全目标是确保信息的机密性、语义安全性，签名方案的 安全目标是确保签名的不可伪造性。 2 根据敌手的能力构建一个形式的敌手模型。如对加密算法的选择密文攻 击、对识别协议的主动攻击，并发攻击。 然后针对以上2 个问题，我们提出算法和协议并证明其安全性。 也就是说，可证明安全性理论是在一定的敌手模型下证明了安全方案或协 议能够达到特定的安全目标，如抗选择密文情况攻击模型下的语义安全性，抗主 动攻击模型之下的不可模仿性。因此，定义合适的安全目标、建立适当的敌手模 型是我们讨论可证明安全性的必要的前提条件【9 】。 可证明安全性理论的应用价值是显而易见的：我们可以把主要精力集中在 “极微本原”的研究上，如大整数因子分解，离散对数或者其它n p 问题。这是 一种古老的、基础性的、带有艺术色彩的研究工作。如果你相信极微本原的安 全性，则不必进一步分析协议即可相信此算法或协议的安全性【9 】。 当然，可证明安全性理论也存在一定的局限性：首先必须注意模型规划， 即注意所建立的模型都涵盖了哪些攻击。历史上的身份认证协议设计的反反复 复主要是因为我们没有给出在分布式环境下的合适的认证模型，在文献【1 1 l 中， b e ll a r e 和r o g a w a y 首次给出了一个基于对称密钥的双方实体认证协议的安全 性证明，从而为认证协议开辟了一个正确的方向。但是由于基于双方对称秘密 的身份认证不可否认性方面不够好，因为p 和v 双方都有同一个秘密，每三方 无法区别是哪一方进行非法活动，因而现在国内外更多考虑的是基于非对称秘 密的协议，所以本文主要考虑的是公钥识别协议。 初看起来，构造公钥识别协议是很简单的，我们可以考虑采用数字签名f 1 2 】。 西华大学硕士学位论文 v f f g ) _ ! 一- l 皿i 止 c c ”ti fr e t r y ( p 。jc u l f i g u r e1 1 + 2s i g n a t u r ef o ra u t h e n t i c a t i o n 图1 1 2 用数字签名做认证 其中，s k 是p 方的私钥，p k 是p 方的公钥，k 是安全参数。 如果一个对手m 扮演验证者v 的角色，和诚实证明者p 交互多项式次( 以k 为参数) ，在这期间，m 可以发送任何它想要的e l ，”，e 。到证明者p ，证明者对 随机数e ；进行签名送回给验证者m ，之后，m 可以扮演证明者角色，这时候m 试图向验证者v 证明它是合法的用户，v 发送给随机数e 给m 。 1 如果e e e i j “，e 。j ，这发生的概率为n 2 。，由于n 多项式次，故这个 概率是可忽略的； 2 、如果e 圣f e l i “，e 。 ，在这种情况下，模仿诚实证明者p 相当于伪造一 个新的对随机数e 的签名。 当然我们也可以采用加解密的方法来进行身份认证，其中e 是p 方对v 方消息的解密输出【1 2 l 。 v a l ， ； ! ! ! ! ：! 。1 i l - f i g u r e1 1 3 e n c r y p t i o n d e c r y p t i o n f o ra u t h e n t i c a t i o n 图1 1 3 用加解密做认证 4 西华大学硕士学位论文 可以看出，上述两种方案都是基于询问应答方式的。事实上，i s o ( 国际 标准化组织) 和i e c ( 国际电子协会) 已经把我们提到的这2 种方式标准化为 单向实体认证的标准方式l ”j 。 虽然上述识别体制是简单的，它们把识别协议的安全性证明归结为所使用 的密码学算法的安全性( 签名和加解密) ，从而似乎我只需要设计安全的签名 和加密算法就可以得到安全的识别协议了。但是这些体制有下面一些缺点： 1 上面的体制留下了一些证明者执行识别协议的不可否认的踪迹，人们 可能希望避免留下这些踪迹1 1 2 j ； 2 有些密码学加密和签名算法是有专利的，我们可能尽量不希望在设计 识别协议时用到别人的专利； 3 也许更加重要的一点剧1 2 】：协议1 给了攻击者m 以最强的适应性选择 消息下对数字签名的攻击的机会，协议2 给了攻击者m 以最强的适应性选择密 文下对加密算法的攻击的机会。一般来说，抗适应性选择消息下的数字签名和 抗适应性选择密文的加密算法是很难构造的，尤其是我们在标准模型下考虑时 ( 非随机o r a c l e 模型) ，因此，我们很自然地去想构造不依赖上面两种工具( 加 密和签名) 的识别协议。实际上，我们一般不用数字签名来构造识别协议，而 是相反，我们应用f i a t s h a m i r 方法转换某种形式的被动攻击下安全识别协议 至安全的随机o r a c l e 模型【1 4 】下存在性不可伪造的数字签名体制【1 5 l 。我们知道 数字签名体制是识别体制的重要应用领域，我们这里研究的识别协议是适用于 智能卡的，对于互联网环境的认证协议，我们必须考虑认证的密钥交换，无密 钥交换的识别协议基本上没有什么用处【1 6 1 。 本文的第一部分首先针对特定智能卡应用环境，介绍了几种识别协议，并 在v i t o rs h u o p 的2 4 次根识别协议【1 7 】的基础上经过适当变动，并从另外的角 度用证明了其在主动攻击对手模型之下不可模仿性，这种证明方法是构造性 的，而原文的证明方法是非构造性的。 本文的第二部分对身份认证和秘密共享1 1 8 】的结合进行了研究。前面我们讨 论的身份认证方案只适用于一个体向另一个体或系统进行身份认证，但是有时 也存在某些有着特殊安全性要求的系统，如对于涉及多个团体和行业的敏感数 西华大学硕士学位论文 据的访问，必须经过各团体代表或若干管理人员的验证身份方可实施；或者为 了防止某几个服务器的非正常工作或拒绝服务可能造成对合法用户认证的失 败。因此，设计一种安全可靠的面向群体的身份认证方案显得很重要。面向群 体的身份认证系统应具有如下特征：( 1 ) 认证系统的任意t 名验证者可合作验 证用户的身份；( 2 ) 任意t - 1 名或少于t 一1 名验证者不能验证面向群体的密码系 统。面向群体的身份认证方案的显著优点是：( 1 ) 可以防止认证系统内部个别 管理人员的作弊；( 2 ) 可提高认证系统的安全级别。t 名以上验证者共同合作 参与，才能实现用户身份的认证，提高了系统访问控制的安全性；( 3 ) 可提 高认证系统的可用性。认证系统只要有t 名以上验证者在场即可提供认证服 务，个别验证者缺席或出现拒绝服务等问题都不会影响认证服务i ”。 1 9 8 8 年，d e s m e d t 1 9 l 最先提出了面向群体的密码学的概念，他指出，社会 上存在以个体为单位存在的实体以外，也存在由众多个体组成的群体，而群体 中由于结构的复杂和彼此间纷繁复杂的关系，使得安全保护执行起来更加复 杂。 本文第二部分构造了一个基于身份的交互式用户共享验证身份认证方案， 该方案是和一个具有一般接入结构的秘密共享方案相结合，每一个成员只需保 存一个子秘密，而且每个成员的子秘密可以重复使用。该方案较好地解决了n 个验证者是有不同权利时的共享验证的身份认证问题。 1 2 国内外研究现状 1 2 1 身份认证的分类 身份认证按所用的物理介质进行分类，主要有口令、磁卡、条码卡、i c 卡、 智能令牌、指纹等。 按身份认证中与系统的通信次数分类，有一次认证、两次认证。 按身份认证所应用的系统来分，有单机系统身份认证和网络系统身份认 证。 从身份认证的基本原理上来说，身份认证可以分为静态身份认证和动态身 西华大学硕士学位论文 份认证。 此外，又可分为单向认证、双向认证、基于可信第三方的认证。 本文认为，身份认证协议总体上可分为基于对称秘密的协议和基于非对称 的秘密证明协议两大方面。比如口令方案也可算作一个对称秘密。 同时，就算法构造的角度来说，强的身份认证协议又可以分为基于密码学 算法( 加密、签名、伪随机函数) 的协议和直接基于基本单向函数( 因子分解、 离散对数，其他n p 问题) 之上构造的协议，本文考虑的是后面一种情况。 1 2 2 智能卡领域的身份识别协议 在密码协议中，零知识证明( g o l d w a s s e rm i c a l ia n dr a c k o f f ) 1 2 0 l 是一个非 常漂亮的方法来限制证明者p 泄漏给验证者v 的信息的技术。在g m r 论文中，p 向v 的证明的是语言成员判定问题，即证明输入i 语言l 是否成立的问题) 。 1 9 8 7 年，f e i g e ，f i a ta n ds h a m i r ( f f s ) 设计了一个基于零知识证明技术的识别协 议1 2 “，该文把成员零知识证明( 它泄漏了一位信息) 扩展到了知识的零知识证 明( 它没有泄漏任何信息) 。一个成员证明系统可被看作是证明一个特定的断 言是真的，一个知识的证明系统可被看作是证明了证明者知道为什么断言是真 的。我认为知识证明概念的引入主要是出于安全性证明技术上的需要，但也存 在一些实际的例子来说明知识证明为什么是必需的。举例：g 是一个阶为q 的有 限循环群，设g 是g 的生成元，假设在g 中计算离散对数是困难的。设l g = h l x e z q 使得矿：h ) 。显然k 是群g 本身，因此证明h e l g 是无意义的，也就是说成员 证明是无意义的。但知识证明，证明p 知道相应的h 的离散对数l o g g h 却是有意义 的，以下当提到零知识证明，除非特别指出，我们一般指的是知识的零知识证 明。 一个识别协议是指p 经过多项式次向v 证明他知道某个秘密x ，之后v 却不 能得到足够信息假冒p 向其它人证明他是p 。零知识证明的典型应用是识别协议 的设计，历史上也已经提出了许多可行的基于零知识证明的识别协议【2 1 , 2 2 , 2 3 l ， 然而，零知识证明的识别技术有下面几个缺点： 1 、一个零知识识别协议要求超过3 次交互执行，由于在网络通讯中，交互 通讯的时间开销往往比计算的执行开销更大。 7 西华大学硕士学位论文 2 、零知识识别协议不能转化为数字签名方案。这是因为：如果识别协议 是零知识的，那么经过由该识别协议经过f f s 技术转化而来的数字签名可以通 过使用证明零知识的模仿器的算法来伪造。因此，4 轮和5 轮零知识识别协议不 能用于构造数字签名【驯。 因此，为了效率的缘故，人们往往采用3 轮的非零知识证明技术来构造识 别协议。现在已知的是：3 轮交互识别协议不可能是零知识的，但它是可证明 安全的吗? 1 9 8 7 年，f c i g c ，h a ta n ds h a m i r f f 陌s ) 设计了一个基于零知识证明技术的识别 协议1 2 1 1 ，它也是主动攻击模型之下可证明安全的，这个方案为后来的识别方案 铺平了道路，它也是后来识别协议的公认框架，同时该文中也通过并行化方法提 出了一个3 轮执行的识别协议，并且在相应的模型之下证明了协议的安全性。 后来g u i l l o u q u i s q u a n c r 提出了一个基- = r s a 求逆困难的g q 识别协议i “，这个 协议是诚实验证者零知识的，它是被动攻击模型下可证明安全的。s c h n o r r 提出 了一个基于离散对数困难的识协议1 2 6 】，这个协议是诚实验证者零知识的，它是 被动攻击模型下可证明安全的。虽然g q 和s c h n o r r 是很高效的识别协议，但可 惜它们没有在标准假设之下被证明是安全的。2 0 0 2 年，文献1 1 6 j 证明了在r s a u n d e r o n e m o r e i n v e r s i o n 假设之下g q 协议是可证明安全的，当然这一假设比标 准r s a l 段设更强，但仍然有其积极意义。此外近年来还有许多基于其他n p 困难 问题的识别协议被提出【巩2 8 瑚】，比如基于l a t t i c e 区分问题的识别协议【册，基于 对映射的识别协议哪! ，合数模离散对数问题的识别协议【2 9 】等等。但所有的3 向 识别协议都是如下形式1 3 0 i ： p v c 它e p ( z ，d ，c ，r ) 三l f i g u r e1 2 1 b a s i ct h r e e - r o u n di d e n t i f i c a t i o np r o t o c o l 图1 2 1 基本的三向识别协议 享一 西华大学硕士学位论文 其中a 是一个p 发出的随机数，叫承诺；c 是一个v 发出的随机数，叫挑战； r 是p 对v 的响应；然后v 计算p ( x ，a ，c ，r ) ，如果= 1 则通过p 的认证，否则拒绝。 这里特别要说明的是e 的取值范围大小对协议的性质有很大影响，设k 是输 入长度时，我们区别多项式大小的e 和指数大小e ，当e 是多项式大小时，指的 是存在整数c ，使得i e f 任何k 的多项式。一般的基 本三向协议是不满足正确性定义的，为了达到正确性，我们需要下面2 种合成 方法【如l ： 1 串行合成；串行地执行基本协议t 次，验证者接受p 的证明当且仅当t 次验证 都通过： 2 并行合成，这又分2 种情况； ( a ) e 是多项式大小，并行执行协议如下：a = ( a i a 2 ，a ) ，c = ( c 1 ，c 2 ，c t ) ，并且 r = ( r l r 2 ，r 0 ， c i e ，i = l ，2 ，t 。验证者接受p ( x ，a i ，c i ，r i ) = l ，i = l ，2 ，t 。 ( b ) e 是指数大小，欺骗者成功的概率比任何多项式的倒数都小。 一般的实用的执行一轮的三向协议( 如g q 和s c h n o r r ) 是类型2 的并行。 我们知道存在许多类型的针对身份识别协议的攻击： 1 被动攻击对手在仅仅知道公钥而不知道相应的私钥的情况下，试图向验 证者证实自己是p 。 2 诚实验证者攻击或者窃听攻击：相当于攻击者可以窃听通讯线路或者可以 假冒验证者和诚实证明者进行交互，但必须遵守协议规则。这种类型的攻 击其实相当于被动攻击，我们本文不考虑。 3 主动攻击对手首先被允许扮演验证者v 的角色和诚实证明者p 交互多项 式次，这里v 4 不一定按照协议规定的角色运行，然后v + 扮演证明者p 的角 色，试图向证实验证者证实自己。 本文我们只关注1 ，3 两种类型的攻击： 很明显，主动攻击下安全的识别协议比被动攻击下安全的更为强大。主动 攻击很好地建模了智能卡环境下的对手的能力，比如合法用户有一张l c 卡，该 合法用户向某设备( 比如a t m 机) 申请服务的时候，假如设备是假冒的，那么 经过多次交互之后，该假冒设备的主人也不能在其后的时间里面扮演合法用户 西华大学硕士学位论文 的身份向真正的设备( 比如a t m 机) 成功申请服务。我们还应该看到，i c 卡和 a t m 机之间的通信信道是假设安全的，当i c 卡和a t m 机之间的识别协议完成之 后，对手不能介入通信信道( 你的i c 卡在a t m 机里面) 。也就是说，合法i c 向 a t m 证明身份之后所进行的服务操作( 比如抽取现金) 是不需要加密的，这显 然与互联网环境下的情况不一样，在互联网环境下，通信信道显然不能假设是 安全的，在用户和服务器之间的识别协议完成之后，对手能劫持通信信道，假 冒合法证明者继续向服务器申请服务。为了停止这类攻击，一个办法是双方在 识别协议完成之后，生成一个会话密钥，然后双方用这个会话密钥加密所进行 的操作和所传送的数据1 3 1 j 。没有建立会话密钥的身份认证在互联网环境是没有 什么用处的，这是认证会话密钥研究的范围，本文没有涉及。 1 2 3 基于一般接入结构的共享验证的身份认证协议 在保密通信中，为了实现信息的安全保密，人们主要采用密钥加密信息， 从而使不拥有密钥的非法用户无法窃获信息。这使得信息的安全保密主要维系 于密钥的安全，从而如何有效地管理密钥就成为密码学中十分重要的课题。 1 9 7 9 年，s h a m i r 和b l a k l e y 独立地提出了密钥分散管理( 也称为秘密共享) 的概念 1 1 8 , 3 2 】，实现这一思想的协议称为秘密共享方案。 结合秘密共享思想，人们进行了大量的门限密码学的研究i ”j ，比如门限加 密，门限解密，门限签名，门限验证，例如文献 3 4 1 进行了( 1 ，n ) 1 7 限共享验证 签名方案的研究。但是共享验证的身份认证研究却并不多见，特别是当n 个验 证者有等级的情况下，这方面的研究更加少。在传统的身份认证方案当中，验 证方都是一个单一实体，共享验证的身份认证是验证者v 不是单一个体，而是 由n 个个体组成，这些个体还可能是不同权利的。在文献m j 中，作者首先提出 了一个门限共享验证签名方案，随后作者将它应用并设计了一个口令共享认证 方案。但该方案中各验证者的子秘密虽然经过f ( x ) 单向函数运算，但是并不是 每次身份认证都是随机变化的，所以将受到重放攻击。文献1 4 】中，作者提出一 个门限共享身份验证方案，但作者并没有解决当n 个验证者不同权力时的问题。 文献【2 2 j 中，作者利用e l g a m a l 签名设计了一个基于身份的交互式用户认证方案。 1 0 西华大学硕士学位论文 但是同样没有考虑n 个验证者有等级时的问题。 1 3 本文研究的特点 身份识别协议的研究一般是朝几个方向发展： 一是基于新的数学难题用原有的协议框架构造新的方案，这方面的改进主 要是数学难题安全强度增加了，从而使识别协议的效率提高了，然而协议框架 基本没有变化。 另外一个是在原有常用的数学难题基础上构造抵抗更强的攻击( 并发攻 击，重置攻击) 的识别协议1 3 ”。同时识别协议的可证明安全是越来越受到人们 的关注，本文的第一个方面的工作是对已有识别方案进行适当的改造并进行了 与原文非构造性的安全性证明方法有所不同的构造性证明。 在一般接入结构的共享验证的身份认证协议的研究历史上，怎么将秘密共 享和身份认证的有机结合是需要考虑的，本文第一次用基于知识证明的三向识 别协议和一个一般接入结构相结合。从而从另外的角度实现了个群体共享验证 的身份认证方案。这个三向识别协议中的随机的承诺数恰好被用来随机化验证 群体的子秘密的发送，从而隐藏了验证群体的子秘密，使该协议具有子秘密可 以重复使用的性质。 1 4 内容组织 本文分为5 章： 第一章是本文的是绪论，主要说明了本文的研究目的和意义回顾了国内 外智能卡身份识别协议的历史和群体共享验证的身份认证的研究现状，还介绍 了本文的研究特点。 第二章主要介绍了本文中所涉及的基础数学理论知识，比如计算复杂性理 论和基于身份的密码学。 1 1 西华大学硕士学位论文 第三章首先回顾了智能卡身份识别领域的前人的成果，并进行了分析，在 此基础上对一个已有的高效识别协议进行了适当的变动并进行了新的安全性 归约证明。 第四章结合身份识别和一般接入结构方案，设计了一个一般接入结构的共 享验证的身份认证方案，并进行了安全性分析。 第五章对本文进行了总结，也以今后的研究打算进行了展望。 西华大学硕士学位论文 2 基础理论 密码学算法和协议是建立在严密的数学理论基础之上的，其中涉及到数 论、抽象代数、信息论、计算机复杂性理论，本文研究的身份识别协议和零知 识证明有紧密的关系，而零知识证明被认为是密码学和计算复杂性理论关系最 紧密的一个领域。下面我将以本章专门对计算机复杂性相关的基础理论和结论 进行简要介绍，以期对理解本文有所裨益。 2 1 计算复杂性基本理论 本节介绍论文中用到的计算复杂性理论方面的基本知识，大部分内容来自 于文献【3 那l ，由于篇幅所限，我们将不给出详细的定义和深入的探讨，感兴趣的 读者可以参考文献【3 州 2 i 1 确定性图灵机 图灵机是一种计算模型，确定性图灵机指的是输出结果完全由输入和初始 状态决定，也就是说，对于同样的输入和初始状态运行一个确定性图灵机两次， 两次的结果相同。 p 类语言l 在p 类中，如果存在一个确定图灵机m 和一个多项式p ( n ) 使得对非负整数n ，m 可以在时间t - ( n ) n 。，都有f ( n ) p ( n ) 。 如果函数f ( r 1 ) 不是非多项式有界的，那么就是称为多项式有界的。 例：2 “是非多项式有界量。 西华大学硕士学位论文 与多项式时间相比，时间复杂度为非多项式有界的问题视为在计算上难处 理的或不可行的。这是因为，求解这种问题的资源增长的很快，以至于机器很 快受不了。 2 1 6 可忽略量 函数f ( n ) ：n 一 r 称为关于n 的可忽略量，条件是其倒数1 f ( n ) 是关于n 的一个非多项式有界的量。 例如：对任意多项式p ，p ( n ) 2 “，就是一个可忽略的量。 如果f ( n ) 是可忽略量，那么卜f ( n ) 是压倒性的量。 如果一个量不是不可忽略量的，那么称它为一个不可忽略量或者显著量。 2 1 7 多项式时间可归约 称语言l 可多项式归约到另一个语言l o ，如果存在一个多项式时间界定的 图灵机m 可以将任何实例i e l 转化成另一个实例i 。l 0 ，满足i e l 当且仅当 i o l 0 。 2 1 8 可证明安全性 通过有效的转化，将对密码体制的任何有效的攻击归约到解一类己知n p 问题的一实例。通常，该n p 问题是广泛接受的困难问题。这种归约通称为归 约为矛盾。因为人们广泛相信，广为接受的困难问题没有有效解法。 上述定义较为抽象，下面以r s a 为例加以说明。 给定某个基于r s a 的协议p ，如果设计者或分析者给出了从r s a 单向函数 到协议p 的安全性的归约，那么协议p 具有以下转换性质：对于任何声称破译 协议p 的敌手( 程序) a ，以a 为“转换算法”的输入，必然导致一个协议q ，q 可被证明破译r s a 结论是：只要你不相信r s a 是可破译的，那么上述的q 就不 存在，因而p 是安全的。 对可证明安全性的精确形式化有多种形式，一般是在计算复杂性理论框架 1 7 西华大学硕士学位论文 下加以讨论，如主要考虑“概率多项式时p q ( p r r ) ”的敌手a 的转换算法，以及“可 忽略”的成功概率。这是一种“渐近”观点，有着广泛的适用范围。具体内容可 参见g o l d r e i c h 的研究综述【3 9 1 。 2 2 交互式证明协议 零知识协议不只是在密码学中有重要的应用价值，在交互式证明框架中， 这一主题已成为计算复杂性理论和密码学的虽大交叉点，它包括很多相关定 义，本章我们只介绍基本概念。具体可参考文献1 3 9 1 。 2 2 1 交互式证明i p 为了定义交互式证明，我们假设一台是证明者p ，它拥有无限计算能力， 另外一台叫验证者v 是多项式时间界限的。这两台机器得到一个公共输入串x 。 然后p 和v 运行协议，协议结果后，v 输出接受或拒绝并停机。 设l 是 0 ，1 ) 上的语言。口协议( p ，v ) 称为语言l 的一个交互式证明系统， 如果它满足下面2 个条件： p r o b ( p v ) ( x ) = a c c e p tx l = e 和 p r o b ( p ，v ) ( x ) = a c c e p t i x 譬l 一，否则它设1 v = i i 中。它然后发送v 给v ，v 检查是否 ( h ) = g 。，如果不是则拒绝。 验证者只当n 次重复执行协议每次都接受才算成功。 首先，让我们看一下这个证明系统，完备性是显然的，如果h ( g o ) = g l ， 那么v 无论在b 是0 还是1 时都将接受p 的证明。正确性证明如下：假设证明 者p 的声称是错误的，意思是g o ，g 。不是同态的，在n 轮重复执行中的一轮，p 能回答v 的两个提问b = 0 , 1 。设v 。是对应于b = 0 ，l 的应答。我们知道v 。( h ) = g o ，1 l ，( h ) = g l 。那么在v 。_ l l ，i - i ( g d = g l ，即l i j 。v 。是一个g o 到g l 的同态映射， 矛盾。因此，在n 次重复执行过程的每一次，p 只能回答提问b = 0 ，1 中的一个， 即p 只能猜测，成功概率是2 ，这个概率是关于n 可忽略的。 最后，我们看一下这个问题协议是零知识的。首先我们必须建立一个模仿 器，模仿器实际上是一个算法，扮演了证明者p 的角色，当然没有秘密输入h 和没有无穷计算能力。 下面是模仿器m ： 1 启动v + ： 2 模仿一轮协议： ( a ) 随机选择一位b 和随机置换，设h = q j 。1 ( g b - ) ，并且送h 给v ； ( b ) 从v + 接受b ，如果b = b ，输出h ，b ，q ，退出循环；否则重置v + 到最近 一个h 被选择之前，g o t o2 a 西华大学硕士学位论文 如果我们已经完全模仿了n 次执行，则停止。 在模仿一轮过程中，模仿器准备回答提问b ，并希望b 是v 的提问，如果 下好b = b ，那么很好，我们完成了一轮模仿，否则的话，重置v 从第2 a 步重 新开始模仿。 要使模仿器正确工作，我们必须检查一下是否模仿器工作在期望多项式时 间和模仿器输出的分布和真实协议输出的分布是相同的。 首先b 是独立于b 的，因此概率p r o b ( b = b ) = 1 2 ，因此模仿器的一轮模仿 成功的期望的次数是2 次。所有的n 轮协议，模仿器可以在2 n 时问内完成， 而2 n 是关于n 的多项式的。 最后我们看一下模仿器输出的概率分布和真实交互协议的分布之间的关 系。在每一轮成功模仿后，模仿器产生了三元组( h b ，v ) ，h 和真实交互中产 生的一样，是一个均匀分布，同时b 总是v 看到h 之后想发送的值，最后v 是一个h 到g b 的随机置换，这可真实交互中也是一样的，因此模仿器产生的 三元组饵，b , v t ) 确切和真实协议产生的输出同分布，所以这是一个完备零知识 证明协议。 这个例子反映了零知识证明协议设计的一般方法：首先证明者随机选择一 个与原问题同构的问题作为承诺，然后验证者从一些问题中选出一个问题作为 挑战( 提问) ，最后证明者对提问作出应答。挑战数的选择范围大小是很重要的， 和零知识性密切相关，本文讨论的身份识别协议都是基于这样的基本三向协议 框架( 不一定是零知识的) 。 2 2 5 证据不可区分性 如果一个n p 断言有多个证据，p 使用其中一个证据，而v + 不能区别p 倒 底使用了哪一个证据( 即使v 知道所有的证据) ，这就叫证据不可区分性i 榭。 正式定义如下： 证明系统( p ，v ) 是n p 关系r 上证据不可区分的( w i t n e s si n d i s t i n g u i s h a b l e ) ， 如果任何足够大的x ，任何w l ，w 2 e w ( x ) ，任何的辅助输入y ，v 唪p ( 。，。( x 。y ) 和v 郜m ( x ，y ) 是多项式不可区分的。 西华大学硕士学位论文 不象零知识性，证据不可区分的定义没有涉及模仿器。 例：y = x 2 ( m o dn ) ，设y 是公钥，则相对应的秘密有多个，那么它就可能是一 个合适的具有证据不可区分性的函数。 2 3 基于身份的密码学 通常的公钥密码中，密钥的生成过程通常是1 3 l 公钥= f ( 私钥) 其中f 是一上从私钥空间映射到公钥空间的有效的单向函数。由于函数f 的单向性，由私钥计算所得的公钥总包含了一段看似随机的成份。由于每一个 公钥有一段随机成份，显然有必要让主体公钥以一种可验证的和可信的方式与 主体用户的身份相关。很显然，为了传递一条用公钥加密的秘密信息，发送者 必须确信这个看似随机的公钥确实属于所声称的对方的。因此，通常是采用基 于证书的公钥基础设施( p k i ) 。 有理由相信，如果公钥看起来不随机，那么这个系统的复杂度和建立与维 护公钥认证框架的代价就会减小。可以想像，如果一个主体的公钥本身与主体 的身份信息如名字、电子邮件、地址等附属信息相联系，那么，本质上就不需 要认证主体的公钥。事实上，我们的电子邮政系统就是这样工作的。 s h a m i r 4 3 】最早提出了基于身份的密码学的概念，并构造了基于身份的签名 方案，同时他猜想基于身份的加密也是存在的，后来也有人提出基于身份的方 案，不过不太实用。真正有效的基于身份的加密算法是2 0 0 0 年由b o n e h 和 f r a n k l i n i 删提出的。 基于身份的密码中用户私钥生成： 私钥- - f ( 主密钥，公钥1 这个计算过程是由可信机构t a 执行的，t a 拥有专有的主密钥，这里的公 钥是用户的身份i d ，如e m a i l 地址。这样的方法叫基于身份的公钥密码学。 显然，上述用户私钥产生方式是t a 提供给用户的一种服务。这种服务本 2 4 西华大学硕士学位论文 质一种认证服务：t a 根据主体的身份i d 作为公钥为其生成私钥，用它的身份 作为公钥使得系统中任何用户都能有效地识别并使用它。在为主体生成私钥以 前，t a 应该对主体的身份消息进行一次全面的物理的检查。并且，t a 提供的 身份消息必须使t a 相信该身份消息能唯一地识别该主体。 在基于身份的签名方案中，意识到b o b 不需要执行一个密钥信道的建立的 认证是十分重要的【3 j 。当b o b 验证