（计算机软件与理论专业论文）椭圆曲线公钥密码体制在无线终端上的应用.pdf

椭圆曲线公钥密码体制在无线终端上的应用摘要 摘要 随着移动业务的不断拓展，无线安全问题也越来越受到关注。1 5 1 前应用较广泛的无线 应用协议( w a p ) 罩包括了一个安全层次w t l s ，w t l s 类似于有线网络里的s s l ，w t l s 在一般情况下能满足用户的安全需要。但是使用w t l s 的终端设备必须支持w a p 协议，而 且w t l s 是需要w a p 网关的支持。另外，使用w t l s l q - ，数据在w a p 网关f = 某段时间内是 以明文形式存在的，这无疑是一个安全隐患。 公钥密码的观点是d i f f i e 1 h e l l m a n 于1 9 7 6 年在他们的论文“密码学的新方向”一文中 首次提出的。1 9 8 5 年，v i c t o r m i l l e r 和n e a lk o b l i t z 提出把椭圆曲线理论应用到密码学的 构想，从此，椭圆曲线公钥密码体制的研究逐渐成为一个十分活跃的密码学分支。与当前 得到广泛应用的r s a 系统相比，椭圆曲线公钥密码体制具有以下优点：安全性高，计算量 小，存储消耗小，带宽要求低。无疑，这些优点使得椭圆曲线公钥密码体制更适合在无线 终端上应用。 本文针对无线终端存储容量小、计算能力弱的特点，结合椭圆曲线公钥密码理论，提 出了一种无线安全模型，所有的安全操作都是存无线终端上进行，不需要无线网关或者其 他服务器的支持。 关键字：无线安全，w t l s ，公钥密码体制，椭圆曲线公钥密码体制，椭圆曲线数字 签名方案 塑塑堕堕丝塑堡堡型垄垂垡竺塑圭塑生旦 ! ! ! ! ! 型 a b s t r a c t w i t ht h ec o n t i n u o u s l yd e v e l o p i n go fw i r e l e s sb u s i n e s s ，w i r e l e s ss e c u r i t yh a sb e e nm o r ea n d m o r ec o n c e r n e d w t l s ，al a y e ro fw a p ，p r o v i d e sa u t h e n t i c a t i o na n de n c r y p t i o nf u n c t i o n a l i t y a n a l o g o u st os s li nn e t w o r k i ng e n e r a l ，w t l sc a ns a t i s f yt h eu s e r sr e q u i r e m e n tf o rs e c u r i t y b u tw t l sc a no n l yb eu s e do nt h em o b i l et e m l i n a lw h i c hs u p p o r t sw i r e l e s sa p p l i c a t i o np r o t o c o l a n dw t l sc a nn o tw o r kw i t h o u tt h es u p p o r to fw t l s g a t e w a y f u r t h e rm o r e ，t h ed a t ai nw t l s g a t e w a yi sp l a i nt e x ts o m e t i m e s ，u n d o u b t e d l y ，t h i si sa h i d d e nt r o u b l et h e r ea r ea t t a c kc h a n c e s a i m e da tt h ep l a i nt e x to nw t l sg a t e w a y t h ef i r s tt h e o r e t i c a lc o n c e p t so fp u b l i c k e yc r y p t o g r a p h yw e n th a c kt oi 9 7 6w h e nd i f f i e a n dh e l l m a np r e s e n t e di ti na r t i c l e 1 n e wd i r e c t i o n si nc r y p t o g r a p h y ”i n1 9 8 5 n e a lk o b l i t za n d v i c t o rm i l l e ri n d e p e n d e n t l ys h o w e dh o we l l i p t i cc u r v e sc o u l db eu s e dt oi m p l e m e n tp u b l i c k e y p r o t o c o l s f r o mt h e no n ，e l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) b e c a m eah o tb r a n c ho fa s y m m e t r i c c r y p t o g r a p h y c o m p a r e dw i t hr s a ，e l l i p t i cc u r v ec r y p t o g r a p h yc a np r o v i d et h es a m es e c u r i t y l e v e lw i t has h o r t e rk e yl e n g t h ，t h u s ，e l l i p t i cc u r v ec r y p t o g r a p h yh a sa d v a n t a g e sa sb e l o w ：h i g h e r s e c u r i t yl e v e l ，l e s sc o m p u t a t i o n ，l e s sm e m o r yr e q u i r e m e n ta n dl e s sb a n d w i d t hd e m a n d o b v i o u s l y ，t h e s ea d v a n t a g e sm a k ee c c m o r es u i t a b l et h a nr s af o ra p p l i c a t i o n so nw i r e l e s s e n v i r o n m e n t ，s u c ha sm o b i l ep h o n e c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fs m a l lc a p a c i t ya n dw e a kc o m p u t i n gp o w e ro fw i r e l e s s t e r m i n a l ，t h i sp a p e rb r i n gf o r w a r daw i r e l e s ss e c u r i t ym o d u l eb yc o m b i n i n gw i t he l l i p t i cc u r v e c r y p t o g r a p h y i nt h i sm o d u l e ，a l lt h es e c u r i t yp r o c e s s e sa r eo p e r a t e do nw i r e l e s st e r m i n a lw i t h o u t t h es u p p o r to fw i r e l e s sg a t e w a yo ra n yo t h e rs e r v e r s k e y w o r d s ：w i r e l e s ss e c u r i t y , w t l s ，p u b l i c k e yc r y p t o g r a p h y ，e c c ，e c d s a 2 椭圆曲线公钥密码体制在无线终端j ：的应用 第一章 第一章绪论 近年来，无线网络技术发展迅速，从模拟通信网到数字通信网，从简单的语音通信到 语音、数据、图像的综合业务，移动通信几乎涵盖了我们生活的方方面面。 随着手机用，- 的急剧增跃、无线网络带宽的逐步增加和移动终端硬件性能的改善，很 多传统的i n t e m e t 服务都可以平移到无线网络上，比如无线电子商务，无线支付等：伴随着 移动业务的不断拓展，无线安全问题也越来越受到关注。 1 1 无线网络的特点 无线网络与依赖有线信道的互联网有很大的不同，总的说来，无线网络有以下特点 数据传输受到时问拳j 空问的限制比较小，随机性和突发性较强，只要 在有信号的地方都可以进行无线数据传输； 信道环境差，带宽较窄，时延较大，通信稳定性差： 无线终端的运算能力较差，内存小； 数据传输受到的安全威胁比有线信道更多； 无线通信的特点决定了无线安全问题是无线通信系统中一个非常重要而又非常有难 度的一个环节：本文将从介绍无线安全的现状和密码学发展的基础上针对移动终端运算 能力弱、内存小的特点，提出一种新的移动通讯安全模型。 1 2 无线安全的现状 1 2 1w a p w a p ( w i r e l e s sa p p l i c a t i o np r o t o c 0 1 ) 就是”无线应用协议”之意a 它是由系列西议纽 成，用来标准化无线通信设备。例如蜂窝电话，无线电收发机，也可用于i n t e m e t 访问，包 括e ，m a i l ，w w w ，n e w s g f o u p s 和己c ( i n t e m e tr e l a yc h a t ) 。w a p 由e r i c s s o n ，m o t o r o l a ，n o k i a ， u n w i r e dp l a n e t 四家公司发起，现在其会员以包括像a l c a t e l ，a t & t ，西门子，英国电信， 法国电信贝尔大西洋，贝尔南方等大公司。w a p 包括以下几个层次： iw i r e l e s sa p p l i c a t i o ne n v i r o n m e n t ( w a e ) 1 椭圆曲线公钥密码体制在无线终端上的应用第一章 l lw i r e l e s ss e s s i o nl a y e r ( w s l ) i i iw i r e l e s st r a n s p o r tl a y e rs e c u r i t y ( w t l s ) i vw i r e l e s st r a n s p o r tl a y e r ( w t p ) w a p 协议的每一层可以由上一层协议访问，也可以被其他的应用或服务直接访问，这 种灵活性使得某些层的协议可以被屏蔽，也使得一些尚未标准化的协议或服务可以得到支 持，w a p 为移动通信设备上的应用开发定义了一个可扩充和伸缩的环境。 1 2 2w a p 的安全问题 其中w t l s 就是用来确保w a p 的安全：如同t l s s s l x , 于互连网的作用一样，一般情 况下w t l s 足以保证信息在w a p 网关 n w a p 终端之间的安全性：w t l s a 2 作模型如下图： 图1 ：w t l s 工作模型图 w a p 网关在w a p 终端和w a p 服务器之问起翻译作用，数据从w a p 终端发送到w a p 服 务器时，w a p 暖j 关需要将w t l s ) 3 1 密的数据解密，然后发送给w a p j 务器，为了保证在 w a p i n 关和w a p ) 报务器之间的传输安全，可以在w a p 网i 关和w a p 服务器之间应用 t l s s s l 协议；数据从w a p j 臣务器发送到w a p 终端时，w a p 网关先将从w a p j j 务器传来 的数据还原成明文的形式，然后用w t l s 加密，再传送给w a p 终端1 。 w t l s 为无线网络提供以下几个方面的安全服务1 3 1 ： 数据完整性( d a t ai n t e g r i t y ) ：w t l sn t 以确保在终端和w a p 网关之间完整的传输 数据； 数据保密瞄i ( p r i v a c y ) ：w t l s 对发送终端的明文数据进行了加密，在无线终端和 一2 椭圆曲线公钥密码体制在无线终端上的应用第一章 w a p 网关之间数据以密文形式传输； 认证( a u t h e n t i c a t i o n ) ：通过认证机制，w t l s 口7 防止第三方冒充： 拒绝服务保护( d e n i a l o f - s e r v i c ep r o t e c t i o n ) ：w 1 1 j 可以检测和拒绝那些没有通过验 证的数据和重传的数据，避免了很多拒绝服务攻击。 1 。2 。3w t l s 的缺陷 数据无论是从终端手机传送到w a p 服务器还是从w a p j 务器传送到终端，在某段时间 内，数据都是以明文形式存在于w a p 网关上，而且w a p 服务器可能在日志文件q 1 保存着数 据明文，这都是潜在的安全威胁；另外，w t l s 作为w a p 标准的一个部分，只有支持w a p 标准的手机才能使用w t l s 。 从上面的论述可以看出，目前无线安全的解决办法基本上都是集中在无线终端和w a p 网关之问的安全，安全w a p 网关的研究尤其多1 2 1 。 1 3 公钥密码学介绍 公钥密码算法是公钥基础设施( p u b l i ck e yi n f r a s t r u c t u r e ，简称p 赳) 非常重要的一个 组成郝分，p k i 是通过使用公钥密码技术和数字证书来确保系统信息安全并负责验证数字 证书持有者身份的一种体系，是目前网络安全建设的基础与核心。同时，公钥密码算法的研 究也是密码学领域的一个热点问题”1 1 2 1 1 6 1 。 1 3 i 应用密码学简介 密码学( c r y p t o l o g y ) 是个有着悠久历史的学科，早在古希腊罗马时期- 人们就开始 使用了密码技术。当时使用的方法很简单，将原始的文件资料( 即密码学中的“明文”， p l a i n t e x t ) 中的每个字母向右移动( 或回转) 三个位置，印a 变成d ，b 变成e ，经过 这样的转换后资料就变成了密文( c i p h e r t e x t ) ，接收资料的人再将密文反向运算即“j 褥出 原始的文件内容。像这样的密码系统其关键是在于加密算法只有收发双方知道，如果其他 人也知道，机密性将不复存在。很显然，这种将机密性建立在密码算法的不公开性的基础 上的密码系统只适用于封闭环境中。一个通用的密码系统，密码算法必须公开，为了满足 这一需要，现代的密码系统都使用了密钥( k e y ) 的概念，加解密都必须配合密钥，由特定 的密码算法进行，而使用的密码算法是公开的，密码系统的机密性在于密钥的保密性。 一3 一 椭圆曲线公钥密码体制在无线终端上的应用 第一奄 根据密钥的不同，可以将密码系统分为对称密钥系统和公钥密码系统( 非对称密钥系 统) 。在对称密钥系统中，加密解密使用的密钥是相同的或者很容易相互推出：在公钥密 码系统中，加密和解密使用的密钥则是不同的。 最常见的对称密钥系统是于1 9 7 6 年提出的d e s ( d a t ae n c r y p t i o ns t a n d a r d ) ，1 9 7 7 年被 美国政府采用为国家标准；对称密钥系统的收发双方都使用同一个密钥，因此密钥的安全 传输和分发管理是对称密钥系统的关键【z “。 1 9 7 6 年w h i t f i e l dd i f f i e 和m a r t i ne h e l l m a n 首次提出了公钥密码学( p u b l i c k e y c r y p t o g r a p h y ) 的概念，解决了对称密钥系统中密钥安全传输和分发管理困难的问题。1 9 7 8 年r o n a l dl r i v e s t ，a d is h a m i r - 和l e o n a r da d l e m a n 设计出了一个应用非常广泛的的公钥密 码系统r s a ，r s a 的基础是数论的欧拉定理，它的安全性依赖于大数的因数分解的困难 性4 “。 对称密钥的优点是算法简单，容易实现，密钥相对较短，加解密的速度较快，而其问 题是密钥的安全传输和分发管理比较困难，而且对称密钥没有签名功能( 即：当主体a 收 到主体b 发来的数据时，a 无法向第三方证明此数据确实来自于b ) ；公钥密码的优点是密 钥的管理上跟对称密钥体制有本质的不同，公钥密码的加解密密钥互不相同，其中公钥是 公开的，私钥必须保密，而且在己知公钥的情况下计算私钥不具有可操作性，公钥密码的 缺点是运算量大：因此在实际的应用密码系统中通常是这两种方法结合使用。 1 3 2 公钥密码系统 公钥密码系统即可以用于加密也可用于数字签名，是密码学发展史上的个重大突 破，公钥密码系统可以提供以下几种安全服务3 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 ) ：保证收发信息的双方的身份的真实性，通过数字签名 实现； 数据完整性( d a t ai n t e g r i t y ) ：保证消息没有被篡改，入侵者不可能用假消息代替合 法消息，通过数字签名来实现； 不可抵赖性( n o n r e p u d i a t i o n ) ：发送者不可事后否认他发送过消息，消息的接收者可 以向中立的第三方证实所指的发送者确实发送了该消息，通过数字签名实现。 出上可见，公钥密码系统能满足信息安全的所有主要目标。 椭圆曲线公钏密码体制在无线终端上的应用第一章 一个成熟的公钥密码系统一般都有一个数学难题作基础，现在主流的公钥密码系统一 般都是基j 二以f 三个数学难题的2 6 1 ： 1 大整数分解问题( i n t e g e r f a c t o r i z a t i o np r o b l e m ，i f p ) 2 离散对数问题( d i s c r e t el o g a r i t h mp r o b l e m ，d l p ) 3 椭圆曲线上的离散对数问题( e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ，e c d l p ) 上述难题都有一个共同的特征，就是函数的单向性，即函数的正向计算很容易，而在 缺少陷阱信息的情况下函数的反向计算非常困难：比如大整数分解问题，已知两个大整数 求其积很容易，而把一个大整数分解成若干因子的乘积还没找到一个可行的算法能在多项 式时间复杂度上完成。这些数学上特别是数论上多年悬而未决的难题是公开密钥加密系统 的安仝保证，基于这些难题设计出的公开密钥加密体制的加密解密过程的计算相对容易， 但在不知道陷阱信息( 如解密密钥) 的情况下，破译不具有可操作性。从抽象的观点看， 公铡密码系统就是一个单向的陷阱函数。 上面提到，r s a 是目前应用最广泛的一种公钥密码系统，r s a 的数学背景是i f p ，而大 整数分解算法的发展迅速，其中被认为最有效率的i n d e xc a l c u l u s 方法已经达到亚指数阶 ：广1 9 9 9 年5 1 2 位的r s a 算法已经被攻破，随着计算机硬件性能的改善和协同计算技术的发 展，安全的r s a 系统的密钥会越来越长，而随着密钥长度的增加，加解密运算的运算量、 复杂度和系统开销会急剧增长。与同等安全强度的r s a 相比，基于椭圆曲线的密码系统只 需要卡h 对较短的密钥长度，这样，运算量和系统开销都会大幅降低，因此椭圆曲线密码 系统近年来受到了越来越多的关注，尤其是在无线终端上椭圆曲线密码系统有着广阔的应 用前景。 椭圆曲线公铜密码体制在无线终端上的应用 第二章 第二章椭圆曲线密码系统相关理论的研究 椭圆曲线理论是代数几何、数论等多个数学分支的交叉点，一直被认为是个纯理论 学科，对其的研究也取得了丰硕的成果，例如费玛( p i e r r ed e f e r m a t ) 大定理( f e m a t s l a s t t h e o r e m ) 的证明就用到了椭圆曲线的相关理论：近年来，由于公钥密码学的产生和发展， 椭圆曲线理论也找到了它的应用领域。在r s a 密码体制的基础性问题大整数的分解矛u 素数判定的研究方面，椭圆曲线就是一个很好的工具。1 9 8 5 年，v i c t o rm i l l e r 和n e a lk o b l i t z 分别提出把椭圆曲线理论应用到密码学的构想，从此，椭圆曲线公钥密码体制的研究逐渐 成为一个十分活跃的密码学分支【6 l 。 2 1 椭圆曲线相关概念 为了叙述方便，首先引入几个概念。 ( 1 ) 无穷远点：平面几何认为平行线永不相交，我们也可以想象平行线在很远很远的 地方相交，即两条平行线交于无穷远点，记为p 。o 。这样就把平面上直线的平行与相交统 一了；为了和无穷远点相区别，我们把原来平面上的点叫做平常点。 无穷远点有以下性质： l 平面上一组平行线有一一个公共的无穷远点； 2 所有的无穷远点构成一个无穷远直线。 ( 2 ) 射影平面：平面上全体无穷远点和全体平常点构成射影平面。 射影平面坐标系；射影平i ! i j 坐标系是对普通平面直角坐标系的扩展。我们知道普通平 面直角坐标系没有为无穷远点设计坐标，不能表示无穷远点。为了表示无穷远点，产生了 射影平面嫩标系，当然射影平面坐标系同样能很好的表示旧有的平常点2 ”。 我们对普通平面直角坐标系。卜的点a 的坐标( x ，y ) 做如下改造： 令x = x z ，y = y ，z ( z 0 ) ：则a 点可以表示为( x ：y ：z ) ，这就为平面上的点建立了 一个新的坐标系。如点( 1 ，2 ) 在射影平面上的坐标可按下面方法求解：x z = l ，y z = 2 + x = z ，y = 2 z ，故( 1 ，2 ) 在射影平面坐标系下的坐标可表示为( 1 ：2 ：1 ) ，( 2 ：4 ：2 ) 等形如 ( z ：2 z ：z ) ( z o ) 的形式。无穷远点可以表示为( x ：y ：o ) ，与之对应的，无穷远直线则可表示 为z = 0 。 下面将介绍椭圆曲线的概念。 考察w e i e r s t r a s s 方程： 6 椭圆曲线公钥密码体制在无线终端上的应用 第二章 y2 z + a l x y z + a 3 y z2=x 3 + 以2 x2 z + 4 x z2 + d6 z 3 令f ( x ，y ，z ) = y2 z + a i x y z + a 3 y z 2 一x3 一a 2 x2 z a 4 x z2 一a 6 z 3 d x o f - ，面o f ， o 则称w e i e r s t r a s s 曲线是非奇异( 光滑) 的。 若上述w e i e r s t r a s s 曲线是非奇异( 光滑) 的，则满足w e i e r s t r a s s 方程的所有点的集合构 成一条椭圆曲线。很显然无穷远点( 0 ：1 ：o ) 满足上述方程，所以无穷远点也在椭圆曲线上。 为了方便，通常将w e i e r s t r a s s 方程( 1 ) 用仿射坐标x = x ，z ，y = y ，z 的形式化为： f ( x ，y ) = y2 + 1 2 1 x y + a 3 y x 3 一a 2 工2 一4 x 一口6 椭圆曲线理论有着复杂的数学背景，涉及到数论，群论，射影几何等学科，下面对本 文中经常用到的几个概念做简单介绍，相关方面更加深入的研究请参阅参考文献1 。 定义l ：设g 是一个非空集合，若在g 上定义一个二元运算“+ ”满足： 结合律：对任何口，b ，c g ，有( a + 6 ) + c = “+ ( b + c ) 。则称g 是一个半群， 若还满足： 存在单位元e 使对任何a g 有e + a = a 十e = n ； 对任何a g 有逆元a 。使a - 1 + a = a + 一= a 。则称( g ，+ ) 是一个群。如果 ( g ，+ ) 适合交换律，则称g 是可换群或阿贝尔( a b e l ) 群。 定义2 ：设g 是一个非空集合，在g 中定义两种二元运算，一个叫加法，记做“+ ”， 一个叫乘法，记做“”。且满足： ( a ，+ ) 是一个可换群； ( a ，) 是一个半群： 左、右分配律成立：对任何a ，b ，c a 有 a ( b + c ) = a b + a c ，( a + b ) c = a c + b 。c - 则称代数系( a ，+ ，) 是一个环。 定义3 ：设( a ，+ ，) 是环。若a 满足： a 至少有两个元0 和1 ； a + = a o 构成乘法群； a 可交换： 则称a 是域。具有有限个元素的域称为有限域。 在前面的讨论中，椭圆曲线是定义在任意域上的，在实际的密码系统里，椭圆曲线都 一7 椭圆曲线公钥密码体制在无线终端上的应用 第二章 是定义在特定的域上。在本文中，用f 表示一个有限域。在密码学中，我们一般只对两种 域感兴趣： ( 1 ) f 是大素域z 。：p 是大于3 的素数，该域中包含p 个元素，每个5 i l 素都是被p 模的 整数，定义在该域上的所有运算都要模p ； ( 2 ) 特征为2 的有限域g f ( 2 “) ：域中包含2 ”个元素，m 称为该域的度( d e g r e e ) ，域 中的元素是一个长度为m 的位串，定义在该域上的运算要模一个不可约多项式( i n - e d u c i b l e p o l y n o m i a l ，既该多项式不能分解为两个多项式卉勺乘积) 。特征为2 的有限域又称为二迸制 域( b i n a r y f i e l d ) 。 为方便起见，本文中q 阶有限域简记为g f ( q ) 或者f 。 若方程( 1 ) 中，a 。f ，( x ，y ) f 2 且曲线没有非奇异点，则称集合e ( f ) = ( x ，y ) i f ( x ，y ) = 0 uf o 为定义在有限域f 上的椭圆曲线，其中。是无穷远点。奉文后面提到 的椭圆曲线都是定义在有限域上，为了叙述方便，约定用e ( f ) 表示有限域f 上的椭圆曲线。 在椭圆曲线e ( f ) 中可按“弦切法”定义加法运算“+ ”，使得( e ( f ) ，+ ) 构成一个a b e l 群，其中，o 是单位元。有关椭圆曲线的更加详细的介绍请参照参考文献2 5 6 ”。 定义4 ： 设k 是一整数，p ce ( f ) 是曲线上的一个点，k p 表示k 个点p 相加，称k p 为点p 的标量乘( s c a l a rm u l t i p l i c a t i o n ) 。 定义5 ：对椭圆曲线上的点p ，若存在最小的正整数n ，使得n p = o ( 0 是无穷远点) ， i j , fe j n ；n 为点p 的阶。若n 不存在，则称p 是无限阶的。 事实上，定义在有限域上的椭圆曲线上的所有点的阶都是存在的。 定义6 ：已知p 和q 是椭圆曲线e ( f ) 上的点，求整数n 使得q - n p ( 其中n 是整数) 称为 椭圆曲线上的离散对数问题( e c d l p ) 。 当已知n ，p 的隋况下求q 我们使用被点运算可以在o ( 1 0 9 ：i 1 ) 时间复杂度上解决，比如 当n = 1 0 2 4 时。我们只需要计算2 p ，4 p ，8 p ，5 1 2 p ，1 0 2 4 p 这l o 个点：在实际使用的系统 中n 的取值非常大，而已知p ，q 求n 时如果用穷举的方法，需要极大的计算量，不具有可行 性，关于e c d l p 的攻击研究下面还有详细的论述。 椭圆曲线公钥密码体制在无线终端上的应用第二章 2 2 椭圆曲线公钥密码体制的应用和标准化 e c c 作为公开密钥密码体制中的一种，在丰厚的理论基础上实现高度安全，具有存储 效率、通讯带宽的节约及计算效率高等多方面的优越性，是一种非常有前途的密码体制。 目前国外有大量的厂商己经使用或者准备使用椭圆曲线密码体制，m o t o r o l a 公司将e c c 用 于它的c i p h e rn e t ，以此把安全特性加入到应用软件，s e t ( s e c u r ee l e c t r o n i ct r a n s a c t i o n ) 协 议的创立者v i s 和m a t e c a r d 公司都计划使用e c c ；加拿大的c e r t i c o m 是一个专门生产e c c 产品的公司，该公司在e c c 产品的应用开发方面的技术优势已经得到了广泛的、认可，全球 各大公司和机构开始竞相采用c e r t i c o m 的e c c 技术或与之建立战略联盟。其中包括 m o t o r o l a 、p i t n e yb o w e s 、3 c o m p a l mc o m p u t i n g 、n t t 、c y b e r c a s h 、h p 、a m e r i c a ne x p r e s s 、 v i s ai n t e r n a t i o n a l ，a v a n t g o 、n e w c o mt e c h n o l o g y 、3 c o mp a l m 、p u m at e c h n o l o g y ， s c h l u m b e r g e r ，c y b e r s a f e 、c o m p a q ，r a i n b o w ，o r a c l e 、s i e m e n s 、c i s c o ，s o n y 、n e c 、r s a 等几百家全球性大公司以及美国政府等政府机构和团体。 1 9 9 9 年a n s ix 9 6 2 标准的发布成为e c c 标准化的一个重要里程碑。同年美国政府的 国家标准与技术委员会( n i s t ) 发布了新的规定f i p s l 8 6 - 2 确定7 ( e c c 的地位。现已颁布 的有关e c c 的标准有i e e ep 1 3 6 3 及p 1 3 6 3 a 、a n s ix 9 6 2 、a n s ix 9 6 3 、i s o i e c1 4 8 8 8 3 ( 1 9 9 8 年) 、i e t f 、a t mf o r u m 等，这些标准的公布将提高e c c 技术在世界范围内的通 用性，使e c c 技术在全球的广泛应用成为可能口“。 2 3 椭圆曲线公钥密码体制安全性的现状 椭圆曲线密码体制的安全性取决于e c d l p 问题的难解性。一般而言，群g 上的离散对 数算法可分成两类：指数计算法和指数搜索法。对一般的d l p 问题，已有亚指数算法，对 于e c d l p ，到现在的研究表明并不存在亚指数算法，已知的攻击算法有【3 0 1 3 “： l 穷举法 连续计算p 的倍数p ，2 p ，3 p ，直至等于q 。在实际使用的密码系统中，n 的取值非常 大，所以穷举法不可行。 2p o h l i g h e l l m a n 攻击 这种攻击依靠对点p 的阶( o r d e r ) n 的分解，将求解k 的问题转变为求解k 模每个n 的因 子的问题，之后k 可以通过中国剩余定理求解。当所求问题中的点p 的阶是平滑的时候，这 种攻击十分有效。 q 椭圆曲线公钥密码体制在无线终端上的应用第二章 3p o l l a r d 类攻击 p o l l a r d 在提出了一种随机的b a b y - s t e pg i a n t s t e p 算法( p o l l a r dr h o 算法) ，该算法时间复 杂度为o ( 也；万) ，但需要很少的存储空间。 w i e n e r 和z u c c h e r a t o 将该算法时间复杂度改进为o ( 磊，2 ) 。p o l l a r dr h o 算法可以并行 实现，线性提高运行速度，使用r 个处理器的运行时间大概是o ( 焉2 r ) 。p o l l a r d 提出的 i a m b d a 算法在所求k 位于【o ，b l ( b 2 ，因此硬件攻击在实际中并不奏效。 由目前的对e c d l p 攻击的研究情况看，椭圆曲线密码系统目前还是相当安全。 2 4e c c 与r s a 的比较 第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：基于大整数因 子分解问题( i f p ) 的r s a 算法和基于椭圆曲线上离散对数计算问题( e c d l p ) 的e c c 算 法。r s a 算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全 强度相对较低。目前用国际上公认的对于r s a 算法最有效的攻击方法一一般数域筛( n f s ) 方法去破译和攻击r s a 算法，它的破译或求解难度是亚指数级的。e c c 算法的数学理论非 常深奥和复杂，在工程应用中比较难于实现，但它的单位安全强度相对较高。如上节所述， 用国际上公认的对于e c c 算法最有效的攻击方法一p o l l a r dr h o 方法去破译和攻击e c c 算法， 它的破译或求解难度基本上是指数级的。关于r s a 与e c c 同等安全长度下的密钥长度见下 表1 t 2 ”。 椭圆曲线公钥密码体制在无线终端上的应用第二章 表1 ：r s a 与e c c 密钥长度的比较 攻破时阃( m i p s - - 年)r s a d s a 密钥长度 e c c 密钥长度r s a e c c 密钥长度对比 1 0 45 1 21 0 65 ：l 1 0 87 6 81 3 26 ：l l o l l1 0 2 41 6 0 7 ：i 1 0 2 02 0 4 8 2 l o1 0 ：1 1 0 7 81 0 2 46 0 03 5 ：1 在执行速度方面，难以对椭圆曲线密码体制和现存密钥体制， 拗n r s a ，d s a 等作出准 确的定量比较，粗略的说，椭圆曲线密钥体制较对应的离散对数体制要快，且在签名和解 密方面较r s a 夹，但在验证签名和加密方面较r s a 慢。表2 1 2 t 是1 6 0 位e c c 与1 0 2 4 位r s a 和 1 0 2 4 位离散对数系统的计算开销的比较。 表2 ：各系统的计算开销比较 但是如果应用到内存较小的无线终端，r s a , i 会受到内存容量的制肘，e c c 贝, i j 不然 其密钥长度短的优点会显示出r s a 无法比拟的优越性。 椭圆曲线公钥密码体制在无线终端上的应用 第三章 第三章基于椭圆曲线的无线安全模型 前面阐述过无线安全的现状及椭圆曲线公钥密码体制本文实现的系统将针对移动终 端的硬件特点提供加密和数字签名两个方面的安全保证，系统中所有的加解密运算和签 名、验证签名的运算都是在移动终端上进行的，跟通信信道和网关无关。 3 1 系统整体架构 系统总体结构如下： 趣 大 对称密钥加密算法、s h a l 摘要算法及【 、 产 二些损管醑罾辅荡商模块 萋 整 囊 数 介 曲线上点的基本运算及系统参数的生成： 廷 一 f 1 算 素域接口定义( 率特征为2 的有限域的 模 系统未实现)基本运算模块 块 有限域抽象类 图2 ：系统结构图 出于系统扩展和升级的需要，本系统对定义在大素域g f ( q ) 上的椭圆曲线做了接口定 义：本文实现的是特征为2 的有限域既g f ( 2 “) 上的椭圆曲线公钥密码系统。 3 2 安全服务流程 消息发送端用消息接收端的公钥加密明文，接收端用自己的私钥对密文进行解密，密 文在传输过程中，即使被截获也无法获得明文，因为私钥只有消息接收端才有，所以通过 加密就可以保证消息的保密性。 对消息签名时，必须先计算消息摘要，所谓的消息摘要就是对一段消息计算出一个大 椭圆曲线公钥密码体制在无线终端上的应用第三章 整数，不同的消息的摘要是不相等的；然后签名者用自己的私钥对消息摘要进行签名。消 息的接收方接收到消息之后，用发送方的公钥验汪数字签名，如果验证通过，消息发送方 则不能抵赖没有发送该消息，因为与验证数字签名时所使用的公钥匹配的私钥只有消息的 发送方拥有，与此同时，消息接收方也可以确认消息发送方身份的真实性；如果消息在传 输过程中被改动，那么验证时计算出来的消息摘要肯定跟发送者计算出来的消息摘要不 等，这样就保证了消息的完整性和不可篡改性。 如果消息发送方对消息既做加密操作又做签名操作，应该先加密，然后对密文进行数 字签名。 椭圆曲线公钥密码体制在无线终端上的应用第三章 3 2 1 加、解密流程 消息发送方加密流程如下 生成髓固曲线系统参数 0 获取消息接收方公钥 上 输入明文 对明文进行加密 0 输出( 或发送) 峦文 图3 ：消息发送方加密流程 消息接收方解密流程如下 生成椭圆曲线系统多数 上 获取消息接受方私钥 士 输入密文 土 对密文进行解露 上 输出明文 图4 ：消息接收方解密流程 椭圆曲线公钏密码体制在无线终端上的应用第三章 3 2 2 数字签名及验证数字签名流程 消息发送方数字签名流程 生成椭圆曲缝系统参数 上 获取消息签名者的私钥 输入消息明文 计簿消息的h h 摘要 上 对消息的h a s l 疽签名文 上 输出签名值 图5 ：消息发送方数字签名流程 消息接收方验汪签名流程 获取黼圆曲线系统参数 上 获取消息签名者公钥 山 验证消息签名值 l输出燃果 图6 ：消息接收方验证签名流程 椭网曲线公训密码体制在无线终端上的应用第三章 如肌面系统架构图所示，本系统分为以下几个模块：系统参数的生成，大整数运算 特征为2 的有限域上的运算，椭圆曲线上点的运算，加解密运算和数组签名运算。 3 3 安全服务应用模型 3 3 1 安全服务应用模型图 无线侍输 消息发送方 消息接收方 图7 ：安全服务应用模型图 3 3 2 模型安全性分析 从e 图可以看出，该模型的安全性是集中在收发双方的用户终端上，并不能保障无线 链路的安全性。实际上，该模型的安全性依赖于椭圆公钥密码体制的安全性，也就是e c d l p 问题的难解性，关于e c d l p 的攻击现状见2 ，3 。 3 4 系统参数的生成 在建立一个椭圆曲线密码系统的过程中，椭圆曲线系统参数的选择是摹础而又重要的 步：系统参数的选择决定了整个系统的性能。 椭嘲曲线密码系统的参数包括以下几个部分： f ：椭圆曲线所选择的有限域，一般的可以选择特征为2 的有限域或素域，本系统 使用的是特征为2 的有限域g f ( 2 ”) ； f r ：有限域上元素的表示方法，特征为2 的有限域g f ( 2 ) 上的元素一般的可以用 标准基( n o r m a lb a s i s ) 和多项式基( p o l y n o m i a lb a s i s ) 表示，素域g f ( p ) 上到元素则可以 直接目大整数表示； 椭圆曲线公钥密码体制在无线终端上的应用 第三蕈 n ，b ：定义在有限域c 上的椭圆曲线的参数，本系统使用的椭圆曲线形如 y2 + x y = j3 + a x2 十b g ：系统建立时在椭圆曲线上选择的基点( b a s ep o i n t ) ： r ：基点g 的阶： h ：余因子( c o f a c t o r ) h 满足# ( e ) = r h ，其中# ( e ) 为椭圆曲线的阶，即椭圆曲线i ： 点的个数。 3 4 1 有限域的选取 有限域的选取对整个系统的安全性和系统效率有着直接的影响。一般来讲，有限域需 要足够大，以保证在该域上的椭圆曲线的离散对数问题足够难解，从而保证系统的安全性。 但过大的有限域会使有限域上的运算很耗时，因此需要根据情况选择合适的曲线，达到安 仝和性能的平衡。在目莳情况看，1 0 2 4 位的r s a 系统是相当安全的，要达至i r s a 一1 0 2 4 f f j 安 全级别，椭圆曲线有限域位数必须1 6 0 位( b i t ) 。 2 0 0 0 年2 月，( 美) 国家标准研究所( n i s t ) 在标准f i p s1 8 6 一l 中包括进了椭圆曲线数 字签名算法( 在a n s ix 9 6 2 中被标准化) ，并推荐了一组待选择的有限域及椭圆曲线方程， 新标准被称为f i p s1 8 6 2 ，本系统选用的都是f i p s1 8 6 2 中推荐的参数。 f 1 p s1 8 6 2 推荐了1 0 个有限域，其中5 个是素域，5 个二进制域( b i n a r yf i e l d ) ，5 个 进制域分别是f 1 ( 2 ”1 ) ，f ( 2 2 ”) ，f ( 2 ”) 。f ( 2 柏9 ) ，f ( 2 ”1 ) 。素域上的模幂运算需要设 备有很强的计算能力，二进制域上的运算更适合在弱运算能力的系统如移动终端t 实现， 所以本系统选择的足二进制域。 3 4 2 基的选择 为了描述定义在有限域上的运算，我们引进“基”的概念。对于二迸制域，通常有两 种基：多项式基( p o l y n o m i a lb a s i s ) 和标准基( n o r m a lb a s i s ) ”1 。 ( 1 )