没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记125(2005)55-66www.elsevier.com/locate/entcs用交换公钥加密判定协议的安全性YannickChevaliera,1RalfKu?stersb,4Micha?elRusinowitcha,2 Mathieu Turuania,3a法国LORIA-INRIA54506 Vandoeuvre-les-Nancy cedex,法国b斯坦福大学计算机科学系,斯坦福CA 94305,美国摘要许多密码协议和对这些协议的攻击利用了这样的事实,即执行加密的顺序不影响加密的结果,即,加密是可交换的。然而,大多数密码协议的自动分析模型不能处理这样的加密功能,因为在这些模型中的消息空间被认为是一个自由项代数。在本文中,我们提出了一个NP判决过程的不安全协议,采用RSA加密,这是一个最重要的情况下,交换公钥加密。关键词:密码协议,Dolev-Yao模型的扩展,演绎模和复杂性。*这项工作得到PROCOPE、DFG和FET Open的部分支持ProjectIST-2001-3925 2http://www.avis“A V I S P A:A ut omm a t e d V a l i d a t i o n of I n t e r n e t S ec u ri t y Pro t o c ol s and A pp lic a t i o n s“,www.example.com p a - p r o je c t. 或g/。1电子邮件:chevalie@loria.fr2 电子邮件地址:rusi@loria.fr3 电子邮件地址:turuani@loria.fr4电子邮件地址:kuesters@theory.stanford.edu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.05.01956Y. Chevalier等人理论计算机科学电子笔记125(2005)551介绍大多数安全协议的自动分析技术都假设密码算法是完美的:需要解密密钥才能从密文中提取明文,并且只有使用适当的密钥和消息才能生成密文(无冲突)。在这些假设下,并给定协议会话数量的界限,不安全问题是可判定的(参见[1,15,5,10])。然而,这是一个悬而未决的问题是否仍然有效时,入侵者模型扩展到考虑到甚至简单的代数属性的低级别的密码原语。这个问题是重要的,因为许多安全算法是这些属性的结果,并且许多协议是基于这些运算符的(参见,例如,[16、14])。直到最近,协议分析的完美加密假设才稍微放松。在[12]中,统一化算法被设计用于处理Di Schie-Hellman密码系统的属性。虽然这些结果是有用的,他们没有解决更普遍的不安全问题。在[7,8]中,安全性的可判定性已经被证明是使用异或的协议。在[6]中,我们将这个结果推广到了基于Di-Hellman指数的协议.在[13]和[3]中也研究了Di_(?)e-Hellman指数然而,在前者的工作中没有提供决策过程,在后者的协议和入侵者模型施加了严格的在本文中,我们证明了使用可交换公钥加密运算符的协议(如具有共模的RSA加密)的不安全问题允许有限数量会话的NP判定过程(参见第4节的主要结果)。在第2节中,我们提出了一个非常简单的协议,说明协议和对这些协议的攻击可能依赖于加密的可交换性。这个问题可以与[6]中研究的Di Jie-Hellman协议的分析相关,因为Di Jie-Hellman幂运算和交换公钥加密(在RSA的情况下也涉及幂运算)共享代数性质。然而,存在重大分歧。首先,入侵者的能力不同。在公钥加密的情况下,入侵者不能计算指数的倒数,例如,给定公钥(n,e)和密文c=memodn,入侵者不能计算私钥d,然后通过计算cdmodn获得m。相反地,在Di Bie-Hellman设置中,取幂是以公知的素数为模进行的,因此,计算指数的倒数在计算上是可行的e. G. ,givenm=ga·b和b,其中g产生诱导的多个重复组Y. Chevalier等人理论计算机科学电子笔记125(2005)5557KAKA}KBK一KB一通过eprimep,入侵者c可以很容易地找到bmodulop−1o得到b−1(如果存在逆),并通过计算mb−1得到ga。第二,在[6]中,intrudercn不能在相反的消息中操作,例如b-1直接使用,但只能在指数中使用。然而,在我们这里考虑的公钥设置中,这是不现实的,因为逆对应于私钥,当然,我们需要允许入侵者拥有这样的密钥(自己的私钥和不诚实主体的私钥)。由于这些不同,证明也不同。首先,虽然在[6]中粗略地说,我们将不安全问题简化为求解整数线性方程,但现在我们得到非负整数线性方程此外,我们需要扩展入侵者以允许她拥有私钥。与[6]中的证明相比,为了最大限度地减少必要的更改,我们将私钥视为原子消息,并扩展规范化函数以确保公钥和私钥在指数中相互抵消。这使我们能够将[6]中提出的证明提升到这里考虑的设置2依赖交换加密的协议示例让我们通过[17]中给出的两个简单的例子来说明公钥加密方案的交换性质是如何在密码协议中使用的第一个协议是由于沙米尔。该协议的目的是允许两个既不共享对称密钥也不知道另一个代理的公钥的代理之间的安全通信该协议使用commuta-RSA加密方案的有效性:1. A→B:{secret}p2. B→A:{{secret}p p3. A→B:{secret}p在该协议中,假设一个公共RSA模数n。A的公钥是(n,KA),B的公钥是(n,KB)。 消息秘密是一些非负的<整数;整数术语{secret}p代表秘密KAmodn。由代数KA啪啪啪啪求幂的性质,我们有K={{secret}KK.在协议的步骤3中,A计算{secret}pA}pB}p=BpAKAKBJ{secret}K其中KJ是A 因此,协议本身使用交换性加密技术 由于B在该协议中未被认证,因此很明显,入侵者I可以通过简单地扮演B的角色同时使用她自己的公钥KI来模仿B可交换公钥加密方案或签名方案可以B58Y. Chevalier等人理论计算机科学电子笔记125(2005)55K1KA}KB}KBKA也适用于组协议。受[17]第23章中给出的协议的启发,考虑一组l个代理。可信服务器生成两个大素数p和q,计算n = p·q,以及l + 1个数k0,.,kl,使得:k0···kl1 mod(p−1)·(q−1)每个代理Ai,1 ≤i≤l,接收公钥Kj= k0·. ·kl·kj−1对于每个j和私钥ki。注意并且特别地,pk0···kl{{M}p}p=M,=M。ki Ki一旦密钥分发完成,消息就可以由子集签名{Ai}i∈I,I∈ [1,..,(一)集团成员。例如,假设l= 4,A1想要与A2和A4签署一个合同,比如消息M。可能的消息序列是:1. A1→A2:{M}p2. A2→A4:{{M}p}pk1k23. A4→A1:{M}p}p}pK1k2k4在接收到第二消息时,A4可以通过测试是否{{{{M}p}p}p={M}p}p}p}p=M。k1k2K1K2K1K1k2K2然后代理A4也可以使用她的私钥k4签署合同。这里的要点是,由于交换性属性,A4不需要知道代理以什么顺序签署消息。当然,这个协议,当例如用作合同签署协议,具有许多问题,然而,我们不想在这里讨论这些问题。3协议和入侵者模型我们描述的协议和入侵者模型在两个方面扩展了安全协议自动分析的标准模型。首先,可以使用运算符{ }p来构建消息,它代表通过被描述为公钥/私钥的乘积的公钥/私钥因为-站在这里,我们有pKA·KBpKB·KA ={{m}p p{M}={m}={m}.Y. Chevalier等人理论计算机科学电子笔记125(2005)5559一根··特别地,我们可以对公钥加密的交换性进行建模。其次,除了标准的Dolev-Yao入侵者能力之外,入侵者还具有使用她所知道的任何公钥或私钥集合来执行这种广义加密的能力(我们甚至允许任意消息)。例如,如果她碰巧知道A和消息c ={m}p,那么她可以计算{c}pJ={m}pJ={m}p=m。在KAKAKA·KA1接下来,我们通过定义术语对我们的模型进行正式定义消息、协议、入侵者和攻击。3.1条款和信息项的集合term被定义为根(也称为标准项)和产品(也称为非标准项)的并集,如下所示:root::= A| V|根,根|{root}% sp产品product::= root IN|根IN·产品其中A是一组有限的常量(原子消息),包含主体名称,随机数,密钥以及常量1和秘密; K是A的子集,表示公钥和私钥的集合; V是一组有限的变量;IN是非负整数的集合。 我们假设K上有一个双射·J,它将每个公钥(私钥)k映射到其对应的私钥(公钥)kJ。二进制符号·,·称为配对,二进制符号{·}s称为对称加密,二进制符号{·}p称为公钥加密。请注意,对称密钥可以是任何标准项,对于公钥加密,密钥可以是任何非标准项(乘积)。出现在乘积中的非负整数称为乘积指数。将术语t设想为树结构,其中每个内部节点由构造器标记,每个叶子是变量或常量。 如果表示u的树是表示t的树的子树,并且如果u是根项,则项u是子项。我们记Sub(t)为项t的子项的集合。通过推广,如果E是项的集合,我们记Sub(E)为集合Sub(t)对于t∈E的并集。项t的大小表示为|不|是表示的大小, 有向无环图(DAG)它与Sub(t)的基数加上以二进制表示系数所需的空间基础项(也称为消息)是没有变量的项。 像 一个术语,它可以是标准的或非标准的。一个(基)替换是从V到标准(基)项集合的映射。将替换σ应用于项t(一组项E)记为tσ(Eσ),并按预期定义。| {根}60Y. Chevalier等人理论计算机科学电子笔记125(2005)551M1}M2现在我们用公式表示项的代数性质。除了乘积算子的交换性和结合性外,我们考虑以下性质:其中t是标准项,M1,M2是乘积,k∈ K,KJ是k对应的逆键,z,ZJ是非负整数:t1=t t· 1 =t{t}p=tt0=1tz·tzJ=tz+zJ{{t}p ppM1·M21z = 1k·kJ = 1通过从左到右穷尽地应用这些恒等式,得到了一个t的正规形式t'。 注意,它直接决定了乘积算子的可互变性和结合性。如果t ' = t j ',则两项t和tJ相等。正规形的概念在上述两个方面都得到了扩展。的方式来设置术语和替换。 我们解释了一个非-malfbysomex amples:若a,b,c,d∈K,则theni)(a2·b1)·BJ2ii){{a}p}p回想一下,因为b1·c1cJ·dJ2b·dJ2b3·cj6·bj3C6例如,BJ表示对应于b的解密密钥。一个很容易显示:3.2协议协议定义如下。定义3.1协议规则的形式为RS,其中R和S是标准术语。Ap ro colPisa tuple({RiSi|i∈I},
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功