（通信与信息系统专业论文）基于椭圆曲线移动通信认证和密钥分配协议的研究.pdf

上海大学硕士学位论文 摘要 现代密码学认为，任何加密体制的加密、解密算法都是可以公开的，其安 全性应该在于密钥的保密性，认证和密钥的分配管理由此就成了密码体制中最 至关重要的环节。作为一个网络参与者，如何知道自己所处的通信系统是否是 安全的呢? 在这一点上，传统的秘密密钥加密体制无能为力，而公开密钥加密 体制因为在通信发一收双方之间采用非对称密钥而避开了通过秘密信道传递密 钥这一问题，被誉为密码学史上的一座丰碑。 随着移动通信的发展及广泛应用，网络安全问题变得日益重要。由于移动 用户之间的信息传递是通过无线信道进行的，通信链路是公共的、开放的，所 以它比其它网络更容易遭受各种类型的攻击。将公开密钥密码体制应用于移动 通信系统是提高第二代移动通信系统安全的有效手段，尤其是在实现身份认 证、密钥分配管理等方面具有传统的秘密密钥加密体制不可比拟的优势。 目前安全协议的设计者设计的公开密钥加密体制大多基于大数分解问题、 离散对数问题和椭圆曲线离散对数问题，这些数学难题。这些密码系统都可以 为用户提供诸如机密性、鉴别、完整性等安全服务，但是还不能很好的提供相 互认证、服务的不可否认、用户身份的保密等安全服务。另外，由于移动设备 的复杂性、带宽、可用的内存空间等方面的自身特点，一些在有线网络中很好 的安全措旌不能完全照搬到无线网络中来。 本文首先简单介绍了现有的密码体制，通过比较我们看出椭圆曲线密码系 统与其他密码系统相比，效率高、速度快、密钥长度小、占用内存少和带宽需 要小，更适合在移动通信中使用，我们将其作为改进移动通信系统安全的理论 基础。 本文分析了现有的一些身份认证和密钥分配方案，指出它们的漏洞，利用 e c d s a 签名算法和d h 密钥交换思想，提出一种新的认证和密钥分配协议， 然后将该协议扩展，提出一种适用于移动通信的端到端用户认证和密钥分配协 议。将该方案简单实现并与其它方案进行比较，说明方案具有很好的安全性和 可实现性。 关键词：椭圆曲线密码体制、移动通信、认证、密钥分配 谪；大学硕士学位论文 a b s t r a c t i ti sr e a s o n a b l ei nt h ee v e n to ft h ep r e s e n tc r y p t o g r a p h yt h a ta l lc r y p t o s y s t e m s s e c u r i t i e ss h o u l dl i ei nt h es e c r e c yo ft h ek e y se m p l o y e dw h i l et h e i re n c r y p t i n ga n d d e c r y p t i n ga l g o r i t h mm a yb e m a d ep u b l i c t h e r e f o r et h ea u t h e n t i c a t i o na n dt h e d i s t r i b u t i o na n dm a n a g e m e n to ft h e k e y s b e c o m et h ec r u c i a l c o m p l i c a t i o n i n c r y p t o s y s t e m s h o wap a r t i c i p a n ti nt h en e t w o r ki s s u r eo ft h a tt h i sc o m m u n i c a t i o n c h a n n e li ss a f ea c c o m m o d a t i o nh i sn e e d ? a tt h i sp o i n t ，t h ec l a s s i c a lp r i v a t ek e y c r y p t o s y s t e mw i t hs y m m e t r i e a lk e yi sh e l p l e s sw h i l et h ep u b l i ck e yc r y p t o g r a p h i c s y s t e m ( p k c s ) i sk n o w nf o ram i l e s t o n ei n t h ec r y p t o g r a p h i ch i s t o r yb e c a u s ei t a d o p t su n s y m m e t r i c a lk e y ss oa st oa v o i dt r a n s f e r r i n gk e y st h r o u g h s e c u r ec h a n n e l w i t ht h e d e v e l o p m e n to ft h e m o b i l ec o m m u n i c a t i o n s y s t e m ，t h es e c u r i t y p r o b l e mh a sb e c o m em o r es e r i o u s s i n c et h ei n f o r m a t i o nt r a n s f e rt h r o u g ht h eo p e n a n dw i r e l e s se n v i r o n m e n t t l l ew i r e l e s sn e t w o r ki se a s i e rt os u f f e rf r o ma l lk i n d so f a t t a c k s i ti sa l le f f i c i e n tm e a s u r et oi m p r o v et h ew i r e l e s sc o m m u n i c a t i o nn e t w o r k s e c u r i t yb ya p p l y i n g t h ep k c s ，e s p e c i a l l yi nt h er e a l i z a t i o no fa u t h e n t i c a t i o np r o t o c o i k e y d i s t r i b u t i o na n dm a n a g e m e n t p r o t o c 0 1 n o wt h e s e c u r i t yp r o t o c o la p p l i e dt h e p k c sa r ea l m o s tb a s e do ni n t e g e r f a c t o r i z a t i o n p r o b l e m ，d i s c r e t el o g a r i t h mp r o b l e m ，a n de l l i p t i c c u r v ed i s c r e t e l o g a r i t h mp r o b l e m t h e s ec r y p t o s y s t e m sc a n o f f e ral o ts e c u r i t ys e r v i c e ，b u tt h e yc a n n o to f f e rs o m es e r v i c e ，s u c ha sc o n f i d e n t i a l i t yo fu s e r ，a u t h e n t i c a t i o nw i t he a c ho t h e r ， n o n r e p u d i a t i o n ，a n ds oo n a n d b e c a u s eo f m o b i l ee q u i p m e n th a si t sc h a r a c t e r i s t i ci n t h ec o m p l e x i t y ，m e m o r ya n db a n d w i d t hf i e l d s ，s o m eg o o ds e c u r i t yp r o t o c o l su s e di n t h ef i x e dn e t w o r ka r en o td e s i r a b l ei nt h ec o n s t r a i n e dm o b i l en e t w o r k i nt h i sp a p e r ，c r y p t o g r a p h i cs y s t e mh a sb e e ni n t r o d u c e da n dc o m p a r e d b a s e do n t h ea d v a n t a g eo fe c c ，i th a sb e c o m et h et h e o r yf o u n d a t i o nt oi m p r o v et h em o b i l e c o m m u n i c a t i o ns y s t e ms e c u r i t y t h es e c u r i t yo f e x i s t i n ga u t h e n t i c a t i o na n dk e y d i s t r i b u t i o np r o t o c o li sa n a l y z e d t h o r o u g h l ya n di sf o u n dt ob ei n s e c u r e an e wp r o t o c o li sd e s i g n e du s i n ge c d s a s i g n a t u r ea l g o r i t h m + d hk e ym a n a g e m e n t b a s e do n t h en e w p r o t o c o l ，t h ep a p e r h a s p r e s e n t e da ne n d - t o - e n da u t h e n t i c a t i o na n dk e ya g r e e m e n tp r o t o e o l ，w h i c h i ss u p e r i o r t oi nb e i n gs c h e m e si nb o t h s e c u r i t ya n dc o m p l e x i t y k e yw o r d s ：e l l i p t i c c u r v ec r y p t o s y s t e m ，m o b i l ec o m m u n i c a t i o n ，a u t h e n t i c a t i o n ，a n d k e y d i s t i l b u t i o n i i 上海大学硕士学位论文 1 。l 综述 第一章前言 网络安全自8 0 年代以来逐步成为热门的研究课题。密码技术无疑是获得网 络安全的最有效的方法之一。通过加密，人们可以有效的保证通信连路上的内 容不被泄漏，而且可以检验传送信息的完整性。进一步，密码技术还可以应用 于数字签名、身份识别和信息鉴定，这对于资源存储控制以及其它安全措施都 是必须的而且有效的，成为密码设计者的研究重点。 长期以来，密码学经历了传统的秘密密钥加密体制和公开密钥加密体制。 图1 1 典型通信加密系统 典型加密系统是通过密钥k 将明文p 转换成密文c ，放在公共信道上发送， 在接收方进行逆变换的解密恢复出可读明文，其安全性在于通信双方首先能在 安全信道上传递密钥。一次一密方案c e s h a n n o n 【1 】证明是绝对安全的，这 种方案计算量小，速度快，对硬件要求不高。可是对于应用系统来讲实现起来 却非常困难：既然通信双方要进行保密通信。他们首先必须获得密钥，即需要 进行获得密钥的秘密通信，但这种安全性得不到证明，通信双方对是否存在窃 听者也毫无所知。近二十年来广泛采用的数据加密标准( d e s ) 算法作为典型代 表，由于密钥空间j , ) j n 上差分密码分析理论的问世，差不多已经走到其生命的 尽头。差分密码分析是种对迭代密码体制的选择性的明文攻击，也就是一种 概率攻击方法。这一事实更进一步促使密码研究学者寻求体制上的解决方案。 上海夫学硕士学位论文 图2 2 公开密钥密码体制 解决这个问题的一种方案是现代密码学中的公开密钥密码体制：通信双方 可以建立各自的加密解密密钥对( e ，珐) ，将加密密钥e 公开的同时，各自妥 善保管好专有的解秘密钥n ，这种加密体制的安全性大多建立在一些著名的数 学难题基础上，通过设计单向陷门函数以实现加密解密算法的不可逆性( 至少 在现有的资源和算法下是不现实的) 。而且公开密钥加密体制与传统的秘密密 钥加密体制相比有着更强的安全性、开放性，尤其在于它能提供数字认证。 将公开密钥体制应用于移动通信系统是提高移动通信系统安全的有效手 段。移动通信作为一种最灵活、最方便的信息传递手段，已为越来越多的人们 所采用。然而，由于移动通信主要采用无线通信方式，而无线信道又是开放信 道，存在一些不安全因素，这就要求在移动通信网中采用加密技术来保护在无 线通信上传送的消息，包括用户的语音和数据及其某些敏感信令，并对用户对 网络的访问实施认证。 现有的认证和密钥分配协议中，有基于秘密密钥密码体制的，也有基于公 来密钥密码体制的。采用秘密密钥密码体制的，实现起来比较容易，速度快， 但是存在这么一些问题：第一，方案要求认证双方( 用户端和网络服务器端) 必须有一个保存密秘密钥的数据库，这不仅增加了网络结构的复杂性，而且带 来了数据库的安全管理问题；第二，方案不能为用户提供数字签名；第三，方 案无法从根本上消除网络内部的不安全因素。采用公来密钥密码体制的认证和 密钥分配协议可以有效的解决这些问题，而且还可以简化网络中秘密信息的管 理。但是目前采用公来密钥密码体制的主要存在这么一些问题：第一，实现起 来较为复杂，对带宽和内存要求比较商：第二，现有的一些协议中不能为用户 提供身份保密：第三，不能提供由用户到服务器的不可否认的安全服务：第 上海大学硕士学位论文 四，一些协议只能提供网络服务器对用户的认证，而不能提供用户对服务器的 认证。 本课题的研究中，富有意义的忠想是采用椭圆曲线密码算法和d h 密钥交 j 换思想构造移动通信环境下的认证和密钥分配协议，克服了消息太长、计算量 大、对内存和带宽要求高的难点，并将该协议扩展到端到端用户的通信中，有 效的实现了对用户身份的保密、双方认证和服务的不可否认，并在安全性和复 杂性两个方面对新方案和现有方案进行分析，说明方案的可行性。 1 2 论文的主要内容及论文结构 第二章主要介绍密码学的基本理论，分析、比较了秘密密钥密码体制和公 开密钥密码体制的优点和缺点，并简单介绍了包括椭圆曲线密码算法在内的几 种常见的公开密钥密码体制。 第三章对现有移动通信认证和密钥交换协议进行分析，指出他们的优点和 缺点，并总结出协议设计时的基本思路。 第四章基于e c c 提出一种新的相互认证和密钥交换协议。该协议综合了秘 密密钥密码体制和公开密钥密码体制的优点。 第五章将上一章我们设计的协议扩展，提出一种适用于移动通信的端到端 用户认证和密钥分配协议，将该方案与其它方案进行比较，并且对方案的安全 性和复杂性进行分析。 上海大学硕士学位论文 2 1 简介 第二章密码学理论 通信系统的安全性日益受到人们的关注，密码技术在电子银行、电子商 务、智能卡、移动通信、以及各种数据通信中起着越来越重要的作用。密码技 术也成为了通信系统的重要组成部分【3 4 1 。 密码系统通常在系统中为我们提供以下服务： 机密性( c o n f i d e n t i a l i t y ) 为数据在传送过程中的提供保密，并确保只有 合法的用户才能看到该信息，保护被传输的数据免受被动攻击。对于 消息内容的析出，能够确定几个层次的保护。最广义的服务可保护在 一段时间内两个用户之间传输的所有用户数据，也能够定义这种服务 较狭义的形式，包括保护单一消息中的某个特定字段。机密性的另一 个方面是保护通信量免受分析，这要求一个攻击不能够在通信设施上 观察到通信量的源和目的、频度、长度、或其它形式。 鉴别( a u t h e n t i c a t i o n ) 消息的接收者应该能够确认消息的来源，入侵者 不可能伪装成其他人。鉴别服务涉及两个方面；首先，在连接发起 时，该服务确保这两个实体是可信的( 即每个实体都的确是它们宣称 的那个实体) 。第二，该服务必须确保该连接不被干扰，使得第三方 不能假冒这两个合法方中的任何一个来达到未授权传输或接收的目 的。 完整性( i n t e g r i t y ) 消息的接收者应该能够验证在传送过程中消息没有 被修改，入侵者不可能用假消息代替合法消息。如同机密性一样，完 整性能够应用于一个消息流、单个消息或一个消息中的所选字段。同 样 不可抵赖( n o n r e p u d i a t i o n ) 又称为不可否认性，发送者事后不可能虚 假的否认他发送的消息，防止发送方或接收方抵赖所传输的消息。因 此，当发送一个消息是，接收方能够证实该消息的确是由发送方发送 l 海大学硕士学位论文 的；类似的，当接收到一个消息时，发送方能够证实该消息的确是由 所宣称的接收方接收的。 这些功能是通过计算机进行社会交流时至关重要的需求，就象面对面的交 流一样。某人是否就是他说的人，某人的身份证明文件( 驾驶证、学历或是护 照) 是否有效，声称从某人那里来的文件是否确实从那个人那里来的，这些事 情都是通过鉴别、完整性和不可抵赖来实现的。起初，这些功能是由秘密密钥 密码系统来实现的；公开密钥密码系统克服了秘密密钥密码系统在密钥分配和 密钥管理上的缺陷，而其中的椭圆曲线效率高、速度快、占用带宽窄，在移动 通信中的应用也越来越广泛。 2 1 i 什么是密码学 法 密码学是一门研究如何对数据保密的科学。历史上主要有以下三种加密方 编码( c o d e ) 是将一段信息( 例如，字母、短语、句子) 置换为另一 个中对象( 并不一定是同一种类) 的一种不变的规则。例如单词b e n t e a r 可能是h o w i t z e r 的密文。密本的方法灵活性比较差，只有在特殊 的环境中才有用。 隐写术( s t e g a n o g r a p h y ) 是将秘密消息隐藏在其它消息中，这样真正 存在的秘密被隐藏了。例如，发送者写一篇无伤大雅的消息，然后在 同一张纸中隐藏秘密消息：最近人们还发明了在图象中隐藏秘密消息 的方法。 密码( c i p h e r ) 是根据一定的规则对文本进行变换的加密方法。 我们所说的密码学是指对密码( c i p h e r ) 的研究和应用。 2 1 2 密码 密码系统有多种工作方式，但一个好的密码系统应该具备以下几个特点 输入和输出能够当作数据流来对待。 能够根据密钥对数据进行加密。 能够利用密钥对数据进行解密。 上海大学硕士学位论文 根据加密和解密时使用的密钥是否相同，密码系统可以分为对称密码系统 和非对称密码系统。非对称密码系统加密和解密时分别使用不同的密钥，又称 为公开密钥密码系统。我们将其加密时使用的密钥称为公钥，解密时使用的密 钥称为私钥。 与非对称密码系统相比，对称密码系统在软件实现的速度上要快l o o 一 1 0 0 0 倍。当用于本地存储时多采用对称密码。但是在传输过程中使用该方法 时，如何确保密钥在传输中的安全是个难题。对称密码系统的安全性与其密钥 的长度成正比。比较有名的对称密码系统有d e s 、r c 2 、r c 4 、i d e a 等。 2 1 3 数字签名 政治、军事、外交等的文件、命令和条约，商业中的契约以及个人之间的 书信等，传统上采用手书签字或印章，以便在法律上能认证、核准、生效。随 着计算机通信网的发展，人们希望通过电子设备实现快速、远距离的交易，数 字( 或电子) 签字法应运而生，并开始用于商业通信系统，如电子邮递、电子 转帐和办公自动化等系统，如电子邮递、电子转帐和办公自动化等系统。 类似于手术签名，数字签名也应满足一下要求：1 、收方能够确认或证实发 方的签名，但不能伪造：2 、发出签名的消息给收方后，就不能再否认他所签发 的消息；3 、收方对已收到的签名不能否认，即有收报认证；4 、第三者可以确 认收发双方之间的消息传递，但不能伪造这一过程。 数字签名与手书签名的区别在于，手书签名是模拟的，且因人而异。数字 签名是0 和l 的字符串，因消息而异。数字签名与消息认证的区别在于，消息 认证使收方能验证消息发送者及所发消息内容是否被篡改过。当收发者之间没 有利害冲突时，这对于预防第三者的破坏来说是足够了。但当收者和发者有之 间利害冲突时，单纯用消息认证技术就无法解决他们之间的纠纷，此时须借助 满足前述的数字签名技术。 为实现数字签名目的，发方必须向收方提供足够的非保密信怠，以便使其 能够验证消息的签名；但又不能泄漏用于产生签名的机密消息，以防止他人的 伪造签名。因此，签字者和证实者可公用的信息不能太多。任何一种产生签名 的算法或函数都应当提供这两种信息。而从公开的信息很难推测出产生签名的 机密信息。再有，任何一种数字的实现都有赖于仔细设计的通信协议。 6 上海大学硕士学位论文 一个签名体制一般包含两个组成部分，即签名算法和验证算法。下面简单 的说明一下签名的产生和签名的验证。 2 1 3 1 消息的签名 1 给定消息m ，计算得到其散列值h 。 2 用发送者得私钥对h 进行加密得到签名s 。 3 发送m s 。 2 1 3 1 签名的验证 1 接收消息m s ，并将 l 和s 分离开来。 2 根据m 计算其散列值h 、。 3 用发送者的公钥对s 解密，得到解密的散列值h 一。 4 。比较h 和h “，如果相同，说明消息是安全传送的，反之，则不 是。 2 2 秘密密钥密码系统 首先，我们介绍几个基本概念：待加密后发送的所有可能消息的集合称为 明文空间，通常用m 表示；所有密文的集合称为密文空间，常用c 表示；相应 密钥空间用k 表示。在通常的实际情况中，m 、c 、k 都是有限集。 秘密密钥密码系统是对称密钥密码系统，它包含一对函数： e 1 f ：m 呻c 和d 茁：c 斗m其中k k 对所有m 拜口e k ，都有d t c ( e r ( 聊) ) = m 。 秘密密钥密码系统的发送和接受双方必须在通信之初都知道本次通信的密 钥。这可以通过物理的方式来实现或通过可信的第三方来传递，但有些时候很 难实现，甚至是不可能的。除此之外，秘密密钥密码系统在密钥分配和密钥管 理上也有很大的缺陷，还有它不能用来签名。 2 。3 公开密钥密码系统 自1 9 7 6 年w h i t f i e l d d i f f i e 和m a r t i n h e l l m a n 提出公开密钥密码系统以来， 、 t 国内外对公开密钥密码系统【2 6 】研究很多，由于公开密钥密码系统实现效率 高、密钥管理容易，因此应用也越来越广泛。 上海大学硕士学位论文 公开密钥密码系统中常会用到陷门单向函数，r s a 和e c c 中都有用到陷门 单向函数。 陷门单向函数是一种很容易计算的函数，但它的逆计算是不可行的，除非 知道了某些特权信息。陷门是一个程序的秘密的、未加说明的入口，用来准许 存取而不需要通常存取的鉴别方法。 陷门单向函数或者是公开密钥密码系统的理论大多基于菜种比较难解的数 学函数或数学难题。目前主要的几种公开密钥密码系统及其数学基础如下： 大数分解问题：r s a 和r a b i n - - w i l lj a m s 。 离散对数问题 2 8 】：d s a ( d i g i t a ls i g n a t u r ea l g o r i t h m 数字签名 算法) ，d i f f i e - - h e l l m a n 密钥交换 4 6 1 ，e i g a m a l 加密和签名。 椭圆曲线离散对数问题：椭圆曲线密码系统。 与前两类算法相比，e c c 密钥短、速度快、占用带宽小，更适合在移动通 信中使用【3 3 】。 2 3 id i f f i e - - h e l l m a n 密钥交换算法 第一个发表的公开密钥算法出现在d i f f i e 和h e l l m a n 的影响深远的论文 【4 6 】 中，这篇论文第一次提出了公开密钥密码编码学，而这种算法通常被称为 d i f f i e - - h e l i m a n 密钥交换。该算法的安全性基于在有限域上计算离散对数比 计算指数更为困难。这种算法的目的是使得两个用户安全的进行密钥交换以便 用于以后的报文加密。但是这个算法本身限于密钥交换的用途，不能用于加密 或解密信息。该算法大致过程如下： i ( 建立) a 和b 选择一有限集g 和一个大的素数珂和a ，口是模i 的本 原元，这两个数不必是秘密的。 2 a 选择任意整数d ，在g 中计算m o d n 并将“m o d n 通过公共信道传 送给b 。 3 b 选择任意整数b ，在g 中计算r o o d n 并将m o d n 通过公共信道传 送给a 。 4 a 接收到m o d 珂后计算( ) 。m o d ，z 。 上海大学硕士学位论文 5 b 接收到口“m o d n 后计算f 口。1 6 m o d 行。 a 和b 有公共元素口“。窃听者可以获得g 、口、口4 、a 6 ，他的任务是如 何重新构建口“。除非他计算离散对数，恢复盯和b ，否则无济于事。这个问题 就是我们所常说的d i f f i e - - h e l l m a n 问题。因此f o 是a 和b 独立计算的秘密 密钥。 口和 的选取对系统的安全性有很大的影响。f h i ) i 2 应该也是一个素 数。最重要的是胛应该很大：因为系统的安全性取决于与n 同样长度的数的因 子分解的难度。可以选择任何满足是模n 的本原元的口，没有理由不选择所能 选择的最小的口通常只是个位数( 实际上口不必是素数，但它必须能产 生一个大的m o d h 的乘法组群。) 2 3 2r s a 密码系统 r s a 是第一个较为完善的公开密钥算法【2 】，它既能用于加密也能用于数 字签名，也很容易理解和实现。r s a 以它的三个发明者r o nr i v e s t ，a d i s h a m i r 和l e o n a r da d l e m a n 的名字命名。 r s a 的安全性基于大数分解的难度。其公钥和私钥是一对大素数的函数。 r s a 密码体制的加密对象是数字化信息，待加密的明文，不管是语言、文字， 还是数据或a s c i i 码，总可以用个0 一( n 一1 ) 之间的一个整数来表示，也 就是先把一条长的明文信息，按定长划分为一串分组，再分别用一个整数来代 替每一个分组。 为了产生两个密钥，选取两个大素数，p 和q 。为了获得最大程度的安全 性，两数的长度相同。计算乘积n = p q ，然后随机选取加密密钥e ，使e 和( p 一1 ) 女( q i ) 互素。最后用欧几里德扩展算法计算解密密钥d ，以满足 e d ；l m o d ( p o ( q 一1 、 则d - - - e 。m o d ( ( p - 1 ) ( q - 1 ) 1 加密消息m 时，首先将它分成比n 小的数据分组( 采用二进制数，选取小 于n 的2 的最大次幂) ，也就是说p 和q 为1 0 0 位的素数，那么将有2 0 0 位， 9 上海大学硕士学位论文 每个消息分组m 应小于2 0 0 位长。 成。加密公式简化为： c 加密后的密文c ，将由相同长度的分组c ，组 m 7 ( m o d n ) 解密消息时，取每一个加密后的分组c i 并计算： m ，= 掣( m o d n ) 由于： = ( m ? ) “= 冲r = 硝川州“= 脚，聊? 川烀1 ) = l = m 。全部( m 。d m ) 这个公式能恢复出明文。注意d 和n 也互素，( e ，n ) 是公钥，d 是私 钥。两个素数p 和q 不再需要，他们应该被舍弃，但绝不可泄漏。从个公钥 和密文中恢复出明文的难度等价于分解两个大素数之积。 2 3 3e 1 g a m a l 密码系统 该算法【3 】是由t e 1 g a m a l 在1 9 8 5 年提出来的，即可用于数字签名又可 用于加密，其安全性依赖于有限域上离散对数的难度。 要产生一对密钥，首先选择一素数p ，两个随机数g 和x ，g 和x 都小于 p ，然后计算：y = 9 4 m o d p ，公钥是y 、g 和p ，g 和p 可由一组用户共享。私 钥是x 。 对消息m 签名时，首先选择一个随机数k ，k 与p 一1 互素。然后计算 a = g 。m o d p 利用扩展欧几里德算法从下式中求出b ： m = ( x a + k b ) m o d ( p 1 ) 签名为一对数：a 和b 。随机数值k 必须保密。e 1 g a m a l 是一种非确定性的 双钥体制，即对同一明文消息，由于随机参数选择不同而有不同的签名。 要验证签名时，只要验证： y a 6 m o d p = g ”m o d p 每个e 1 g a m a l 签名或加密都需要一个新的k 值。 要加密消息m 时，首先选择随机数k ，只要k 与p 一1 互素。然后计算： 1 0 上海大学硕士学位论文 a = g 。r o o d p b = y k m m o d p a 和b 是密文对，注意密文的大小是明文的两倍。 解密a 和b 时，计算： m = b a 1 ( m o d p ) 因为b 口。三y x m 口兰g 虹m i g h = m m o d p 成立。 2 3 4 椭圆曲线密码系统 1 9 8 5 年，n e a lk o b l i t z 4 1 和v s m i l l e t 【5 】分别提出将椭圆曲线用于 公开密钥密码体制。虽然他们没有发明有限域上使用椭圆曲线的新的密码算 法，但他们用椭圆曲线实现了已存在的公开密钥密码算法，如d i f f i e h e l i m a n 算法。 椭圆曲线的吸引人之处在于提供了由“元素”和“组合规则”来组成群的 构造方式。用这些群来构造密码算法具有完全相似的特性，但他们并没有减少 密码分析的分析量。 有限域g f ( 2 ”) 和g f ( p ) 上的椭圆曲线特别有趣，域上的算术运算器很容 易构造，并且n 在1 3 0 至2 0 0 位之间的实现是相当简单。有关椭圆曲线的内容 可参见4 3 ，这里简单介绍一下椭圆曲线d i f f i e - - h e l l m a n 协议。 椭圆曲线与d i f f i e - - h e l l m a n 密钥交换算法相结合，产生了椭圆曲线 d i f f i e - - h e l l m a n 协议( e l l i p t i cc u r v ed i f f i e - - h e l l m a n ，e c d h ) 协议，该 协议可以用来在通信双方建立共享密钥。下面两个图 3 8 1 说明了如何在有限 域g f ( p ) 上，在给定椭圆参数的情况下，e c d h 协议如何在用户和服务器之间建 立共享密钥。 用户服务器 选择矾 2 ，n - 2 】 q = d u x p 发送 接收 q 。_ q 选择以 2 ，n - 2 j q = 曩p 接收 发送 上海大学硕士学位论文 k = d 。x q 。= d u d 。x p 图2 1 k = d ，x q = 攻或x 尸 e c d h 协议( 第一版) 设系统参数为( ，e ，p ，n ) ，其中是有限域，e 是定义在上的椭圆曲 线，p 是e 上的一个有理点，称为基点，p 的阶为素数 。 1 用户和服务器分别随机选择一个整数吃，反 2 ，聍一2 】； 2 计算q = 巩p 和q = d s p ； 现在用户和服务器利用椭圆曲线密码算法分别获得了自己的私钥和公 钥分别为矾和q ，和q 。 3 用户和服务器分别将自己的公钥发送给对方； 4 利用d i f f i e - - h e l m a n 密钥交换算法，用对方的公钥和自己的私钥相 乘建立共享密钥丘。 用户 选择坑f 2 ，n 一2 j e u = 町1 r o o d n q = d u k 发送 接收 s = e 。r = e u 吐也x k = d x k 发送 服务器 选择 2 ，”一2 】 e ，= 布m o d n 坌 接收 r = d ，x q = 破瓯k 基发送 s 接收 t = 巳。s = 巳哎x k = k 图2 2e c d h 协议( 第二版) 上面是e c d h 的第二版，与第一版略有不同。 1 用户和服务器分别随机选择一个整数或，t 【2 ，珂一2 】做为自己的私 钥： 2 然后分别计算气= 1 m o d n 和巳= 1 m o d n ； 上海大学硕士学位论文 3 用户用自己的私钥和选择的共享密钥k 相乘得q ，然后将q 发送给服 务器； 4 服务器用自己的私钥和得q 相乘，然后将计算结果月发送给用户； 5 用户将r 与e 。相乘得s ，然后发给服务器； 6 服务器用s 与e 。相乘便可恢复出共享密钥世。 上海大学硕士学位论文 第三章认证和密钥分配协议 对移动通信系统来说，认证和密钥分配协议非常重要。一般来说，认证和 密钥分配协议能够为系统提供以下服务：可以在两个或多个实体之间建立共享 的秘密，建立用于一次通信时所用的会话密钥；可以向一个实体提供对他想要 进行通信的另一个实体的身份的认证，认证包含消息认证、数据源认证和实体 认证；可以与另一身份已被证实的实体之间建立共享秘密 4 0 ，2 9 ，3 0 1 。 目前，有许多适用于移动通信的认证和密钥分配协议，这些协议有基于秘 密密钥密码技术的，也有基于公开密钥密码技术的。本章我们介绍并分析几种 较为常见的认证和密钥分配协议，指出它们的优点和缺点。 3 1m o l v a ，s a m f a t 和t s u d i k 协议 该协议【6 】是r m o l v a ，d s a m f a t 和g t s u d i k 于1 9 9 4 年提出的，采用秘 密密钥技术，可以为移动通信提供认证和密钥分配。实现过程参见图3 1 。 图3 1 中，k d c ( k e yd i s t r i b u t ec e n t e r ) 是密钥分配中心。虬、 帆为a 、b 和k d c 产生的随机数，k 、为用户a 和b 各自的秘密密钥，瓦。 是移动用户a 和b 的共享会话密钥，t 为密钥有效期， 纠q ( 贾) = 矗( 疋；夏) ， 表示用密钥墨做为杂凑函数h 的一个参数求消息贾= ( 五，而，靠) 的消息认证 码，其中葺g f ( 2 ) ，i = l ，n 【3 5 】。 k ：= m a c o ( b ，m ，t ) 乙：( o 如) ，b ，圯， ；m a c b ( a ，t ) 瓦。= ( o 瓦) ，a ，m ，r 从图3 1 中我们发现该协议具有以下优点： 1 执行协议时，仅需要进行少量的数据交换。即协议具有紧凑的消息数 据格式。 2 采用一次随机数来代替时戳，避免了时间同步问题。 3 具有很高的灵活性，能够适应不同的网络结构。 1 4 上海丈学硕士学位论文 4 易于采用硬件来实现，适于在低层网络协议中使用。 a 发送 a ，n o 接收 接收 发送 m a c o 。( n o ，m ，口) ，m m a c 。( n o ，峨) m a c a 。( n o ，) b 接收 发送 接收 发送 接收 n a ，nh ，a ，b m ，r ，乙， k d c 接收 发送 发送 埘e ( n o ，也) 接收 蚴q ( 虬，m ) 图3 1m o l v a ，s a m f a t 和t s u d i k 协议 虽然该协议有很多的优点，但是在移动环境中使用时，存在着一些局限 性：在图3 1 中，协议涉及三个实体，即：用户a 、用户b 以及密钥分配中心 k d c 。协议假设k d c 是a 和b 所共同依赖的。协议执行后，a 与b 完成了双向认 证，并建立起一会话密钥e 。当移动用户在访问网络中漫游时，认证协议也 涉及到三个实体，即：移动用户、访问网络认证服务器以及归属网络认证服务 器。在移动环境中，应该假设这三个实体之中的任意两个实体是互步信赖的。 由于现在的移动通信是一个全球的通信系统，因此做这样的假设合理的，这就 需要在任意两个实体间进行相互认证。 与其它基于秘密密钥的协议相似，该协议假定通信双方存在一共享密钥， 这个假定给服务器和用户的密钥管理和密钥存储带来许多问题，而且该协议不 能实现数字签名，不能为用户身份提供保密。 3 2b e l l e r 和y a c o b i 认证协议 1 9 9 3 年，m j b e l l e r 和j y a c o b i 在非对称公钥密码算法r a b i n 【2 1 ，2 2 ， 2 7 】和e 1 g a m a l 密码算法的基础上提出一种新的认证和密钥分配协议【7 】。该 协议的安全性基于求台数的模平方根的难度，其在安全性较r s a 有优势。服务 器选择两个素数n ，q ，做为私钥，然后将= p j ，q j 做为公钥发送给签证机关 上海大学硕士学位论文 c a ，c e r t i f i c a t i o na u t h o r i t y ) 【3 7 】。在用户端，用户随机选择s 做为私 钥，然后计算的其公钥p ，并将其发送给c a 。c a 对眠和# 进行签名，并将结 果返回。参见图3 2 。 该协议可以比较容易得到公钥，用户端的计算量也比较小，但是使用该协 议需要事先做预行计算，这样使得其带宽利用率降低，存储效率也比较低。 用户 接收 选择一随机数s p = 驴m o d 。 发送p 接收 存储i ，c ? ，s j ，p l ，ns ，nu 签证机关( c a ) 提取个人标识i ! ! ! ! 丝! 丛 发送 接收 q = ( f ，只) m o d p q 。 发送a 图3 2b e l l e r 和y a c o b i 认证协议 3 3a z i z d i f f i e 协议 该协议 8 1 是由a a z i z 和w d i f f i e 于1 9 9 4 年提出的。它能为移动通信 提供互互认证和密钥分配。 1 6 t 海大学硕士学位论文 当移动用户a 要和基站b 通信时，首先，a 将它的签证c 。、时间戳。以及 公开密钥算法列表l i s t 发送给基站b ，基站b 用c a 的公钥对其收到消息的内容 进行验证；如果经验证有效的话，基站b 提取a 的公钥，随机产生一数值月。， 然后用a 的密钥对其加密得k 。( ) 。然后基站b 对髟( r 。) 、时间戳n a 、算 法列表进行签名，然后将签名随同它的签证g 、髟( ) 和其算法列表一同发 送给a 。a 对收到的消息进行验证，如果验证有效的话，它同b 一样将自己的签 名值发送给b ，b 对收到的消息进行验证，完成整个认证的过程。协议的实现参 见图3 3 。 、 该协议的执行只需要在通道中传送三次消息，进行六次加密和四次解密。 与b e l l e r 和y a c o b i 认证协议相比，它不需要预行计算。相对而言，该协议的 计算量比较小，物理实现比较容易。 移动用户a基站b 发送 刍! 些! ! 垫 接收 发送 巴，髟( ) ，l i s t 2 ，巧1 础 ( 髟( ) ，l i s t 2 ，虬，l i s t 。) ( 也) ，k a 甜自( 毛( 心) ，巧( 磁) ) 图3 3a z i z 和d i f f i e 协议 3 4 其它一些协议 接收 发送 接收 3 4 1 c h a n g - - s e o pp a r k 提出的基于签名的协议 c h a n g - - s t o pp a r k 提出一种基于签名的协议 9 1 ，该协议可以在几种不 同网络实现端到端的认证和密钥交换。虽然p a r k 在该协议中没有说明具体采用 哪种公钥算法，但是p a r k 假定该协议是建立在模平方根( m s r , m o d u l a r s q u a r er o o t ) 或r s a 的基础上。对于移动通信系统，该协议主要有一下两个缺 点： 1 m s r 和r s a 的安全性都是基于大数因子分解的难度，这些公开密钥密码 系统对内存和带宽的要求比较高。 2 不能对用户身份保密。 上海大学硕士学位论文 3 4 2b e l i e r - - c h a n g - - y a c o b i 协议 该协议【l o 是一种基于m s r 的公开密钥协议，它可以隐藏用户的身份； 但是它需要占用五次通信信道，需要六次公开密钥操作( 包括公钥加密和公钥 解密) ，同样对内存和带宽的要求比较高。 3 4 3m u 和v a r a d h a r a j a n 提出的协议 m u 和v a r a d h a r a j a n 分析了b e l l e r - - c h a n g - - y a c o b i 协议，在此基础上提 出一种新的协议【1 1 】。该协议可以预防中断、篡改等攻击，有一定的用户身 份保密功能，但是功能十分有限。另外，对内存和带宽需求方面改进不大。 3 5 小结 本章我们简单介绍了几种适用于移动通信的认证和密钥分配协议。其中 m o l v a ，s a m f a t 和t s u d i k 协议采用的是对称密码技术，其它均采用