（计算机应用技术专业论文）金融智能卡加密算法的研究与实现.pdf

沈阳工业大学硕士学位论文 摘要 智能卡作为种新的信息载体，在金融、电信领域得到了越来越广泛的应用。尽管 智能卡的设计从物理安全、交易安全上予以考虑，但在智能卡的生命周期中，攻击者仍 然会破坏智能卡的双向认证过程，甚至分析得到智能卡系统的交易数据。 金融智能卡加密算法包括用于智能卡与外部设备相互认证的r s a 算法及用于加密 交易数据的d e s 算法。但一方面，d e s 算法密钥长度过短、易受到差分密码分析和线 性密码分析方法的攻击，从而威胁着交易数据的安全性。另一方面，为提高智能卡系统 的效率，减少智能卡系统的出错率，需尽可能提高d e s 算法的加密速度。本文正是针 对传统d e s 算法的不足，从加密强度和速度上改进算法，通过对传统d e s 算法和改进 d e s 算法的比较，证明了改迸算法更适合应用到智能卡当中。 课题首先简要探讨了智能卡技术，包括智能卡操作系统、智能卡国际标准、智能卡 加密算法。其次，探讨了伪随机理论及产生伪随机序列的各种方法，包括线性同余生成 法、混沌序列生成法、线性反预移位寄存器生成法。第三，为保证交易数据的安全性， 重点构造了基于线性反馈移位寄存器的d e s 算法，并给出了该算法的模型，通过理论 证明算法能够有效抵制线性密码分析、差分密码分析对传统d e s 算法的安全威胁。第 四，构造d e s 算法的新s 盒，新s 盒满足输入是输出的非线性关系，因此并没有破坏 d e s 算法的安全性。实验结果证明，基于新s 盒的d e s 算法与原算法具有相同的f 运 算结果，在保证安全性的同时，提高了传统d e s 算法的加密速度。 关键词：智能卡，加密技术，新s 盒，d e s 算法 沈阳工业大学硕士学位论文 一_ _ _ l 一 r e s e a r c ha n d r e a l i z a t i o no nf i n a n c es m a r t c a r d c r y p t o g r a p h y a b s t r a c t a san e wi n f o r m a t i o nc a r r i e r ，t h es m a r t c a r di sa p p l i e di nf i n a n c ea n dt e l e g r a p h yf i e l d a l t h o u g h t h e d e s i g no f t h es m a r t c a r d i sc o n s i d e r e di np h y s i c a ls e c u r i t ya n db u s i n e s ss e c u r i t y ，i n t h ep e r i o do f t h es m a r t c a r d ，t h ea t t a c k e rc a ns t i l ld e s t r o yt h ea u t h e n t i c a t i o np r o c e s sa n d a n a l y z e b u s i n e s sd a t ar e l a t e dt ot h es m a r t c a r d a l g o r i t h mi nf i n a n c es m a r t c a r dc o n c l u d e d t h er s a u s i n g i nt h ea u t h e n t i c a t i o np r o c e s sb e t w e e nt h es m a r t c a r da n de q u i p m e n ta n dd e su s i n gi nt h e b u s i n e s sp r o c e s s b u to nt h eo n eh a n dd e sh a ss h o r tk e ya n df a l lu n d e rt h ed i f f e r e n c ea n d l i n e a r i t ya n a l y s i s ，a n dt h eb u s i n e s sd a t a a r ee a s yt oc r a c kb y u s i n gd e s o n t h eo t h e rh a n d ，i n o r d e rt oi m p r o v ee f f i c i e n c ya n dr e d u c et h em i s t a k eo fs m a r t c a r ds y s t e m , w eh a v et oi m p r o v e t h es p e e do fd e s t h ea r t i c l ea i m e da tt h ed e f i c i e n c yo fd e s ，a n di m p r o v e dt h er a t ea n d i n t e n s i t yo fi t t h r o u g ht h ec o m p a r i s o no f d e sa n d i m p r o v e dd e s ，p r o v e d t h ei m p r o v e dd e s i sm o r ea d a p t i v ei ns m a r t c a r dt h a nd e s f r i s t ，t h ea r t i c l ed i s c u s st h et e c h n o l o g yo ft h es m a r t c a r d ，i n c l u d i n gt h eo p e r a t i n gs y s t e m a n di n t e r n a t i o n a ls t a n d a r da n dt h ec r y p t o g r a p h yo ft h es m a r t c a r d s e c o n dd i s c u s st h ef a k e r a n d o m i c i t yt h e o r y ，a n ds o m ew a y st op r o d u c ef a k er a n d o m i c i t ys e q u e n c e 删，i n o r d e rt o g u a r a n t e e t h es e c u r i t yo f b u s i n e s sd a t a , u s i n gt h es e q u e n c ee n c r y p f i o na n d g r o u p i n ge n c r y p f i o n s y s t e m ，a n dp u tf o r w a r dt h ed e so fl i n e a r i t yf e e d b a c ks h i f tr e g i s t e r , a n dg i v et h em o d e l ， d e s e r i p t i o na n dt h e o r ya n a l y s i so f t h ea l g o r i t h m f o u r t h ，c o n s w a c tt h esb o x ，a n di ts a t i s f yt h e n o n l i n e a r i t ya n d n o tt od e s t r o yt h es e c u r i t yo fd e s ，i nt h eo t h e rw a yi th a st h es a m e o p e r a t i o n r e s u l ta st h esb o x t h ec r y p t o g r a p h yn o to n l ya s s b l e st h es e c u r i t yo ft h ed e s ，b u ta l s o i m p r o v e s t h es p e e do f i t k e yw o r d s ：s m a r t c a r d ，c r y p t o g r a p h yt e c h n o l o g y ，n e wsb o x ，d e sa l g o r i t h m 一2 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表 示了谢意。 签名：i 醛日期：磁兰圈目 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 签名：寻飞 导师签名：盘 兰垒一目期：蛐 沈阳工业大学硕士学位论文 1 绪论 1 1 课题的研究背景 智能卡的概念是7 0 年代初提出的，法国人罗兰德莫瑞诺于1 9 7 6 年第一次成功的 将可进行编程设置的i c ( i n t e g r a t e dc i r c u i t ) 芯片放于卡片中，使卡片具备更强大的功 能。智能卡由于内部集成c p u 、r o m 、r a m 、e e p r o m 、片内操作系统，因此被认为 是世界上最小的个人计算机，它不仅具备数据存储能力，而且具备数据处理能力，甚至 可以实现各种加密运算。由于其较磁卡具有安全性高、存储容量大等优点，因此该技术 已经应用到了金融、交通、医疗、身份证明等多个行业，形成了金融智能卡、交通卡、 健康卡等。 8 0 年代，智能卡在法国、美国、英国等西方国家得到了广泛应用i l j 。由于法国政府 的大力支持，使得智能卡在法国得到广泛普及。仅金融智能卡，该国就已经发行了6 0 0 多万张。截止1 9 9 6 年底，欧洲智能卡的市场总值为8 6 1 亿美元，智能卡销售总额为 3 9 2 亿张，到2 0 0 3 年欧洲智能卡市场的总值达到2 4 亿美元。在中国，1 9 9 7 年底，为 促进中国金融i c 卡的发展，中国人民银行在e m v9 6 规范的基础上组织制定了中国 金融集成电路卡规范。该规范自发布以来，很好地指导和推动了我国银行i c 卡和其 它行业i c 卡的发展，相继出现了中国银行海南智能卡、上海浦东发展银行的东方智能 卡、工行的牡丹智能卡、农行的广州智能卡等【2 j 。 但同时我们看到现阶段我国银行发行的智能卡仍然处于试点发行阶段，诸多原因制 约了我国金融智能卡的推广应用，其中智能卡的成本偏高是其中最重要的原因。造成金 融智能卡成本偏高的原因是其不仅需要数据存储、数据处理、更重要的是能够支持加密 运算，为此金融智能卡不得不采用较高的c p u 频率、较大的存储器容量。由上面分析 我们不难发现，促成金融智能卡在中国得到进一步普及的基本前提是尽可能采用较低的 智能卡主频，获得较高的安全性和较快的加密速度。这也是本课题研究的一个重要意 义。 从另一个角度分析，尽管金融智能卡的设计从物理安全、逻辑安全、交易安全上予 以考虑，但其仍然存在定的安全隐患。以下从实际及理论上对该安全隐患进行分析。 沈阳工业大学硕士学位论文 ( 1 ) 2 0 0 3 年2 月1 7 日一名电脑黑客窃取了威士和万事达帐户，帐户数目达到2 2 0 万个，报道援引两家公司发吉人的话称，这名黑客是在破坏了家第三方代理机构的安 全系统后入侵整个账户系统的叫。 ( 2 ) 2 0 0 3 年6 月的一次黑客袭击造成1 2 0 0 多家银行帐号、密码被盗，其中包括 中国工商银行。 从理论上分析金融智能卡在智能卡的生命周期中，会受到各种各样的攻击： ( 1 ) 使用伪造的智能卡，以期望进入某一系统。该方法试图破坏智能卡系统的内 部认证过程。 ( 2 ) 冒用他人遗失或盗窃所得的智能卡，以图冒充别的合法用户进入系统，对系 统进行实质上未经授权的访问。这类行为还包括私自拆卸，改装智能卡的读写设备等， 改装智能卡的读写设备实际上是试图破坏智能卡系统的外部认证过程。 ( 3 ) 直接对智能卡与外部通信时所交换的信息流( 包括数据和控制信息) 进行截 听、破译等非法攻击，以谋取非法利益或破坏系统。 金融智能卡系统中采取r s a 公钥密码体制进行智能卡系统的双向认证 4 】包括内部认 证和外部认证，从而抵制前两种攻击方式。针对第三种攻击方式，根据中国人民银行 金融规范，采用d e s 算法对智能卡与外部通信时所交换的信息流进行加密并以密文的 方式传输1 5 但一方面传统d e s 算法密钥长度过短，并且易受到差分密码分析、线性密 码分析、相关密钥分析1 6 1 的威胁，从而潜在的威胁着金融用户信息的安全，另一方面为 节约智能卡成本、提高智能卡的系统效率、减少系统出错率，需尽可能快的对交易信息 加密。 本课题j 下是针对目前智能卡与外部设备信息交换所使用的d e s 加密算法的不足之 处，从算法的安全性和效率两方面对传统d e s 算法进行改进。通过上述分析研究智能 卡加密算法具有两方面的意义： ( 1 ) 将新算法应用到金融智能卡中可以使用较低的智能卡主频，获得较高的安全 性和较快的加密速度，有利于金融智能卡的进一步普及。 ( 2 ) 提高现有d e s 算法的强度和速度可以进步保证交易数据的安全性和及时 性。 沈阳工业火学硕上学位论文 1 2 课题的国内外研究现状 为保证智能卡系统交易的安全性，国内外提出了三种解决方案：第一种利用3 d e s 算法i7 】代替传统d e s 算法，第二种利用分组反馈链接式、密码反馈模式、分组反馈模 式、s 盒的随机化来提高现有d e s 算法的加密强度1 7 1 ，第三种采用分组密码体制和序列 密码体制相结合婵j 的加密思想。 ( 1 ) 采用d e s 算法的变形算法3 d e s 算法加密交易信息，3 d e s 算法的加密密钥 长度为1 2 8 位，对其攻击的复杂度从0 ( 2 5 6 ) 增至0 ( 2 “2 ) ，提高了d e s 算法的强度。但 另一方面其算法的加密速度约为d e s 算法的3 倍，限制了其在金融智能卡中的应用。 ( 2 ) 采用分组反馈链接式、密码反馈模式、分组反馈模式、s 盒的随机化等改进 算法，上述算法均可以在一定程度上提高现有d e s 算法的强度，但传统的密码分析方 法依然对其构成很大威胁，并且改进模式的加密速度略高于传统的加密算法。 ( 3 ) 分组密码体制和序列密码体制相结合的加密思想的典型代表是采用基于线性 同余发生器的d e s 算法。该加密思想已被证明可以有效的抵制线性密码分析、差分密 码分析的威胁。基于线性同余发生器的d e s 算法很好的利用了该种加密思想，但该算 法具有序列流产生速度慢、具有较强的自相关性、序列周期依赖于机器字长的缺点。在 智能卡中无法获得较长的序列周期，并且算法的加密速度较慢。 1 3 课题的主要研究内容 课题的主要研究内容是分析在智能卡系统认证、智能卡与外部设备信息交换时受到 的各种各样潜在攻击的基础上，对智能卡中的各种加密算法进行深入的探讨。 通过一年多学习和研究，本文主要完成以下几个方面的工作：首先探讨了用于智 能卡双向认证的r s a 算法和椭圆曲线加密算法。其次，对用于加密智能卡和外部设备 之间的通信数据的d e s 算法进行改进，构造了基于线性反馈移位寄存器的d e s 算法， 并给出了该算法的模型、理论证明及实现，通过理论证明该算法具有抵制线性密码分 析、差分密码分析的优点。同时在深入研究d e s 算法的基础上，构造新的s 盒，通过 理论证明、程序实现和实验结果分析，基于新s 盒的d e s 算法在保证算法安全性的同 沈阳工业大学硕上学位论文 时，提高了原d e s 算法的加密速度。最后分析了改进算法较传统d e s 算法及其他改进 算法更适合应用于智能卡当中。 沈阳工业大学硕十学位论文 2 智能卡技术 智能卡，又称i c 卡、集成电路卡，英文名称为“i n t e g r a t e dc i r c u i tc a r d ”或“s m a r t c a r d ”，是法匡1 人罗兰德于1 9 7 4 年发明的，距今已有近3 0 年历史 9 1 。它结台现代微电 子技术和计算机技术，是人与社会信息系统间信息交流的纽带，大大提高了人们生活和 工作的现代化程度。今天，智能卡的应用程度已成为一个国家科技发展水平的标志之 一。从结构上看，智能卡是一个完备的微型计算机系统，有独立的硬件资源和操作系 统。是硬件和软件技术的高度结合。智能卡硬件主要由c p u 及加密逻辑、r o m 、 黜蝴、e e p r o m 、输入输出接口、安全逻辑、加密解密运算协处理器等一系列功能部 件组成。其中c p u 及加密逻辑保证e e p r o m 中数据的安全性，减少外界非法获取 e e p r o m 数据的可能性。r o m 区域存放固化的监控程序即片内操作系统c o s ，该区 域为卡片生产商保密区域，一经写入不能修改和读出。e e p r o m 是智能卡用户能够真 正访问到的存储区域，该区域存储了智能卡的各种信息密码以及应用文件，采用电可擦 写且掉电不易丢失数据的半导体材料，使得智能卡成本相对昂贵，但能有效的提高信息 可靠性，减少易失性，并且如果满足用户规定的安全条件可以对该区域进行读或写。 r a m 区域存放工作时的命令参数、返回结果、安全状态以及临时工作密钥。 2 1 智能卡的分类 根据卡中的集成电路的不同将智能卡分为以下三类 9 1 ： ( 1 ) 存储器卡：这种卡仅具有数据存储能力，没有数据处理能力。存储器卡上的 信息与磁卡上的信息一样，很容易读出也很容易修改，其安全性较差。一般用于对安全 性要求不高的场合如健康卡。其内部由e e p r o m ( 电可擦可编程只读存储器) 和一些 读写电路构成。存储卡的容量一般在1 - 1 6 k b 之间。 ( 2 ) 逻辑加密卡：这种卡除具有数据存储能力外还具备一定的数据保护机制，其 由于采用密码控制逻辑来控制对e e p r o m 的访问，在使用之前需要校验密码才可以进 行相应操作，密码存放于逻辑加密卡卡内，当外界输入密码与卡内所存密码一致时，才 允许使用该卡，因此与存储器卡相比提高了卡内数据的安全性，但仍旧存在如下不安全 因素：一方面，密码在线路上以明文方式传输容易被截取。另一方面，无法认证应用是 沈阳工业火学硕士学位论文 否具有合法性。例如：有人伪造了a t m 机，逻辑加密卡无法知其合法性，当插卡输入 p i n 时，卡密码就被伪造的a t m 机截获。 ( 3 ) c p u 卡：这种卡本身相当于一个微型计算机( 有人称其为世界上最小的计算 机) ，它具有计算机的主要组成部分：c p u 及加密逻辑、r o m 、r a m 、e e p r o m 、片 内操作系统。其不仅具备数据存储能力而且具备数据处理能力和数据加密能力，卡内存 储了用户的各种信息以及加密算法，其容量比逻辑加密卡大，可以实现一卡多用。 根据智能卡使用时与卡设备是否接触将其分为接触型智能卡和非接触型智能卡。接 触型智能卡为当前使用最广泛的智能卡，卡的左上角有8 个触点，用于与外部卡设备接 触。非接触型智能卡的集成电路不向外引出触点，因此除具有接触型智能卡的电路外， 还具有射频收发电路。 2 2 智能卡操作系统 智能卡操作系统c o s ! o 】( c a r do p e r a t i o ns y s t e m ) 主要由文件系统、安全管理模块 所组成。文件系统负责存取空间的管理，安全管理模块负责数据安全控制。 2 2 1 文件系统 智能卡的文件结构系统是由主文件m f 、目录文件d f 、基本文件e f 组成。主文件 m f 在i c 卡中唯一存在，在m f 下可以有多个目录文件d f 和基本文件e f 。一般的 c o s 支持二或三级目录结构。我们又称包含下级目录的目录文件为d d f ，不含下级目 录的目录文件为a d f 。 ( 1 ) m f 文件：是卡片文件系统的根。i c 卡复位后，卡片自动选择m f 文件为当 前文件。m f 中存放全卡共用的逻辑信息，一般为目录文件和主控密钥文件a ( 2 ) d f 文件：即目录文件，相当于d o s 的子目录。任何一个子目录在物理上和 逻辑上都保持独立，都有自己的安全机制和应用数据，可以通过应用选择实现对其逻辑 结构的访问。 ( 3 ) e f 文件：基本文件e f 用于存放数据和密钥，存放用户数据的文件称为工作 基本文件，在满足一定的安全条件下，用户可对文件进行相应的操作。存放密钥的文件 沈阳工业大学硕士学位论文 称为内部基本文件，不可由外界读出，但当获得许可的权限时，可在卡内进行相应的加 密运算，在满足写权限时可以修改其中的密钥。其中主文件m f 、目录文件d f 和基本 文件e f 之间的关系如图2 1 所示。 图2 1 智能卡的文件结构示意图 2 2 2 安全管理模块 智能卡的安全管理模块【l j 】是智能卡c o s 中非常重要的组成部分。安全管理模块在 概念上包括三大部分：安全状态、安全属性、安全机制。 ( 1 ) 安全状态：智能卡当前所处的一种状态，为二进制八位寄存器，高四位为 m f 所处安全级别，低四位为当前目录所处的安全级别，即所有d f 可设为1 6 种安全级 别中的任一种。 ( 2 ) 安全属性：定义了执行某个命令所需要的一些条件，只有满足这些条件该命 令才可以执行。如对某个e f 的读写，均需满足一定的访问权限。只有安全状态的改变 满足某个文件安全属性的要求时才可访问。 ( 3 ) 安全机制：是安全状态实现转移所采取的转移方法和手段，包括密码鉴别、 数据鉴别及数据加密。安全状态的改变只有通过二种手段：口令认证( p i n ) 和加密。 沈| 5 几_ 【业大学硕士学位论文 将智能卡当前所处的安全状态与某个操作所具有的安全属性相比较，根据比较的结 果就可以容易的判断出一个命令在当前状态下是否允许执行，从而达到安全控制的目 的。 2 3 智能卡国际标准 智能卡的国际标准为其广泛应用提供了必要的保障( 1 2 】，目前智能卡存在很多标准， 各种通用标准及行业标准有几十种之多，其中i s 0 7 8 1 6 和e t s is m g 9 是得到广泛应用 的标准。 i s 0 7 8 1 6 ：描述主机到智能卡底层接口标准。目前i s 0 7 8 1 6 已经陆续发布了9 个部 分，主要定义了：智能卡的物理特性，如卡片大小，接脚排布，以及相关的电气特性的 约定；读卡器和智能卡之i b j 女n 何传递字节流，命令单元格式等；智能卡和应用的全球统 一标识分配办法以及一些基本安全机制的描述。这个标准得到了几乎所有智能卡生产厂 商的支持，是目前得到最广泛支持的智能卡标准之一。 e t s is m g 9 ：主要定义的是s i m ( s u b s c r i b e ri d e n t i t ym o d u l e ) 卡的相关标准。主 要用于移动电话，随着移动通信的飞速发展，s i m 卡也成为当前最成功的智能卡应用之 一。它存储了移动电话用户的身份识别密钥用于在和基行通信时确定用户的身份。同 时s i m 卡还可以用来存储用户的一些其他信息。目前，e t s i 正致力于制定一个智能卡 平台标准，旨在为所有的通信设备定义一个通用的身份识别内核模块，称作：u n i v e r s a l i n t e g r a t e dc i r c u i tc a r d ( u i c c ) 。将包括所有的移动电话、机顶盒、互联网电视、元线 设备等。这个项目的目标是制定一个智能卡框架，同时支持所有这些应用的身份认证。 p c s c ：这是由m i c r o s o f t 所牵头定义的运行w i n 3 1 w i n 9 5 n t 的机器与智能 卡之间的接口标准。现在已有l i n u x 下符合p c s c 标准的应用程序。其主要贡献还在 于为p c 和读写器之间的接口做了标准化。 o c f ( o p e n c a r df r a m e w o r k ) ：定义从j a v a 应用环境到智能卡之间的访问标准，该 标准完全是j a v a 接口。 j a v a c a r d ：描述了在智能卡上运行j a v a 程序的标准【1 3 】，在其标准中定义了如何在智 能卡上创建j a v a c a r d 虚拟机和应用程序接口a p i 。 沈| 5 e | _ 工业大学硕士学位论文 m o n d e x ：一个基于智能卡实现的数字现金标准，它无需第三方的认证。 v i s a c a s h ：一种借贷卡的标准。 e m v ：是由e u r o p a y ，m a s t e r c a r d ，v i s a 为了与m o n d e x 竞争，而共同制定的支付 系统智能卡标准。 然而i s 0 7 8 1 6 、e m v 、g s m 、p c s c 等均面向底层或特定领域的应用，都试图让 智能卡生产商或智能卡读卡器生产商遵循这样的标准。同时i s 0 7 8 1 6 标准只是定义了一 致的文件系统、以及访问卡上安全服务的协议，却没有对如何建立文件系统，以及涉及 到非密钥体系的加密、解密、签名和认证等进行规范，造成了智能卡行业间的差异较 大。 2 4 智能卡认证算法 在智能卡的生命周期中，可能会受到各种各样的攻击，例如使用非法卡作弊，冒用 他人遗失或盗窃所得的智能卡，以图冒充别的合法用户进入系统，对系统进行实质上未 经授权的访问。这类行为还包括私自拆卸，改装智能卡的读写设备等。上述过程实际上 是试图破坏智能卡系统的双向认证过程。金融智能卡系统中采取r s a 公钥密码算澍1 4 】 对智能卡系统进行双向认证，包括内部认证和外部认证。尽管r s a 公钥密码算法加密 速度较私钥密码算法慢，但智能卡系统的双向认证只需加密随机产生的伪随机数，其信 息量很少。因此加密速度可以满足双向认证的需要，另外r s a 加密算法的安全性较 高，能够有力保障智能卡系统的双向认证的可靠性。 公钥加密算法也称为非对称加密算法，它使用的加密密钥与解密密钥不同，其中加 密密钥可以公开称为公钥，任何人都可以用公钥加密消息：解密密钥称为私钥，只有拥 有相应私钥的人才能够解密密文。公钥加密算法不仅可以用于信息加密，还可以用于数 字签名和身份认证，其中r s a 算法是公钥密码算法中的经典算法。 r s a 算法与d e s 算法相比较其主要优势在于安全性较高，但由于其算法的思想是 基于大素数难分解，算法加密速度较慢，不适合加密智能卡与外部设备之间的交易数 据，但r s a 算法是非对称加密算法，它可以应用于智能卡系统的身份认证中，对于智 能卡来说，认证是指智能卡和终端之间互相验证对方的合法性。由于智能卡本身具有运 沈i 5 1 工业大学硕上学位论文 算能力，这为智能卡与终端设备之间的双向认证提供了可能。以下探讨r s a 算法的工 作原理【1 5 】： ( 1 ) 取两个素数p 和q ( 保密) 。 ( 2 ) 计算n m p q ( 公开) ，x ( n ) = 0 1 ) ( q - 1 ) ( 保密) 。 ( 3 ) 随机选择整数e ，满足g c d ( e ，x ( n ) ) = 1 ( 公开) 。 ( 4 ) 计算d ，满足d e ；l ( m o d x ( n ) ) ( 保密) 则加密、解密如式( 2 ，1 ) ( 2 2 ) 所示： c = g ( m ) = m 。( m o d n ) d ( c ) ic “( m o d n ) ( 2 1 ) ( 2 2 ) 一般的r s a 算法分为三个主要过程，即大素数的产生、密钥对的产生和r s a 消息 处理。 2 4 1 算法的大素数产生 即产生两个大素数p 、q ，大素数的产生是r s a 算法体制中一个重要过程，是r s a 算法的基础，一般大素数的产生包括以下两种主要方法。 ( 1 ) 确定性素数产生方法：这一类方法主要包括两类：基于p o d d i n g t o n 定理的确 定性素数产生方法和基于l u c a s 定理的确定性素数产生方法。欲得到素数n ，l u c a s 定 理的确定性素数产生方法需要知道n 1 个素因子。 【定理2 1 】设n n ，若存在一整数a ，1 口 0 且z = l ，则n 不是素数。 令j = j + l 。若j b 且z , - - 1 ，令：iz 2 r o o d n ，然后转到( 4 ) 。 若j = b 且2 胛一1 ，则1 1 不是素数。 对a 选取k 个不同的随机值，重复k 次这样测试。如果1 1 都能通过测试，则可断定 n 不是素数的概率不超过4 - k 。 沈阳工业火学硕士学位论文 s o l o v a y - - s t r a s s e n 检测法和l e h m a n n 检测法每次误判概率为1 2 ，m i l l e r - r a b i n 检测 法每次误判的概率为1 4 ，故m i l l e r - r a b i n 检测法的收敛速度最快。概率性素数产生方法 的优点在于产生伪素数速度快，构造的伪素数无规律性。 缺点在于产生的数是伪素数也就是它存在是合数的可能，尽管这种可能性比较小。 实际为避免产生的是合数，将由此大素数得到的密钥对，对明文、密文加解密处理一 次，若可以正确运行，说明产生的大素数确实为素数，否则则认为是伪素数，将其舍 弃。 3 ) 实际使用的素数检测方法：理论上，虽然上述素数检测法可以很快产生一个伪素 数，但事实上并非如此。例如m i l l e r - - r a b i n 检测法中，随机选取的a ( 1 ，n ) ，9 9 9 无法确定n 为素数。故而实际应用中为加速素数的产生常采用下述方法： 产生一个n 比特的随机数p 。 设置最高位和最低位为l ( 最高位为l 确保素数达到要求的位数，最低位为1 确保 它是奇数) 。 对p 用小素数3 、5 、7 、1 1 等筛值。在具体的实现中可以测试p 是否被小于2 5 6 的所有素数整除，或者测试p 对所有小于2 0 0 0 的素数的整除性。 用一个随机数a 对p 作r a b i n - - m i l l e r 测试。若p 通过测试，贝产生另一个a 重 新测试。通常做5 次测试后，p 为素数的概率已经很高超过9 9 9 。如果p 未能通过5 次测试，生成另一个p 重新进行测试。 另一神方法是：不是每次产生个随机数p ，而是先确定一个搜索范围( 必须保证 在该范围内存在素数) ，然后按递增的方式以某随机数为起点开始在该范围内搜索，直 至找到一个素数。 2 4 2 算法密钥对的产生 通过素数产生方法产生大素数后，下一个问题是计算密钥指数对d 和e l t 6 。 ( 1 ) 计算p ( n ) ，p ( 妒睁1 ) 4 ( q - 1 ) 。 ( 2 ) 随机选取1 e p ( n ) ，使之与p ( n ) 互素，即g c d ( e , p ( n ) ) = 1 ，若不互素，重新选取 e ，直至与p ( n ) 互素。 沈阳工业大学硕十学位论文 ( 3 ) 求d ，满足e d = l ( r n o d p ( n ) 1 。 可见，由e 和p ( n ) 求d 实际上是求模逆元。关于模逆元作有如下结论：一般而论， 如果a 和n 互素，那么口；x m o d n 有唯一解，如果a 和n 不互素，那么 a ；x m o d n 无解。 在选择加密指数e 时，首先确保其与p ( n ) 互素。所以，解密指数d 是必然存在的， 且唯一存在。同时，有d 与p ( n ) 也互素。根据模逆元的性质有加密指数e 也是解密指数d 模p ( n ) 的逆元。因此先由e 加密，然后用d 解密，或者先由d 加密，然后用e 解密都成 立。所谓加密指数、解密指数只是相对概念，该性质也使得r s a 既可以用于加解密运 算( 由e 加密，然后由d 解密) ，也可以用于签名验证( 由d 加密，然后用e 解密) 。因此， 在进行r s a 消息处理时，可以将加解密与签名验证归纳为同一模型。 以下给出智能卡系统认证过程： r s a 加密算法可以用于智能卡系统的认证，包括智能卡片的认证( 内部认证) 、智能 卡读卡器的认证( 外部认证) 。 外部认证过程： ( 1 ) 首先智能卡产生一个随机数，并保存在卡中同时送往终端设备。 ( 2 ) 终端设备通过自己的私有密钥对随机数进行加密，形成密文。 ( 3 ) 智能卡用终端的公共密钥，对随机数进行解密得到明文，并与保存在智能卡 中的随机数比较。若相同，则智能卡承认终端设备是合法的，若不同则认为终端设备是 伪造的。 外部认证说明如下：因为每个终端都有自己的私有密钥，而公有密钥是公开的，如 果智能卡解密的数据与原数据不相同，则认为终端设备的私有密钥是错误的，而只有合 法的终端设备拥有正确的私有密钥，私有密钥的错误说明终端设备是伪造的，这时卡进 入自琐状态。 内部认证过程： ( 1 ) 终端设备产生一个随机数并送往智能卡。 ( 2 ) 智能卡用自己的私有密钥对随机数加密后，回送给终端。 沈阳t 业大学硕士学位论文 ( 3 ) 终端解密密文，形成明文并且与产生的随机数比较。若相同则终端承认智能 卡的合法性，若不相同则认为智能卡是伪造的。 内部认证说明如下：因为每个智能卡都有自己的私有密钥，而公有密钥是公开的， 如果终端设备解密的数据与原数据不相同，则认为该智能卡的私有密钥是错误的，而只 有合法的智能卡才拥有正确的私有密钥，私有密钥的错误说明智能卡是伪造的。智能卡 系统的外部认证如图2 2 所示，其中a k 为终端的私有密钥，a k 为终端的公有密钥。 图2 , 2 智能卡系统的外部认证示意图 2 5 智能卡系统认证新算法 安全椭圆曲线引进公钥密码体制的优点是与目前应用较普遍的l i s a 算法相比，在 同等安全的情况下，其所需的密钥长度远比r s a 低，并且由于计算复杂性的原因，利 用r s a 算法在智能卡中产生密钥需要大量的时间，但在椭圆曲线加密算法中，产生密 钥对的时间是非常短的，即使在计算能力有限的智能卡中也能够很快产生。因此用椭圆 曲线密码算法取代r s a 算法，完成智能卡与智能卡读卡器之间的双向认证是智能卡能 够得到进一步普及的基本前提，也是智能卡发展的必然趋势。以下探讨椭圆曲线密码体 沈阳工业大学硕士学位论文 制的基本原理，关于利用椭圆曲线进行智能卡系统的双向认证过程与利用r s a 算法大 体一样( 以下不再赘述) ，只是效率及安全性较r s a 算法具有明显提高。 2 5 1 椭圆曲线的定义及运算规则 让k 是一个域，k 可以是实数域、复数域或有限域a f ( q ) ，这里q 具有p “个元 素，且p 为素数。定义在有限域k 上的一条椭圆曲线e 是满足下列非齐次( 仿射坐 标) w e i e r s t r a s s 方程的解( x ，y ) k 2 的集合，如式( 2 3 ) 所示： e ：y 2 + a l x y + a 3 y = 工3 + 口2 x 2 + a 4 x + a 6 ( 2 3 ) 其中：a 1 , a 玎。k 及一个无穷远点0 组成。这个点可以看成是位于y 轴上的无穷远 处。对椭圆曲线可以在不同特征值的域上进行分析，通过坐标变换可以简化成下列三种 形式： 当特征值k = 2 ，3 ，4 时，如式( 2 4 ) 一( 2 6 ) 所示： e ：y 2 + y ：x 3 + 甜十6 e ：v 2 = x3 + a x 2 + b x + c e ：v 2 = z 3 + 甜+ b ( 2 4 ) ( 2 5 ) ( 2 6 ) 式中：a ，b ，c k ，判另h 式4 拉2 + 2 7 b 3 0 。 然而，由于特征值k = 3 有限域上的椭圆曲线在密码体制的实现上不具有实际意 义，因此将忽略该种形式的曲线。 下面介绍椭圆曲线的运算规则： ( 1 ) 点加运算的定义：设p 和q 是椭圆曲线上的任意两点，l 是p q 连线。若p 和q 重合与一点，即p = - q ，则l 便退化为p 的切点。设l 和曲线相交与另一点r 。w 是r 点和无穷远点o 的连线，也就是说，w 是过r 点引y 轴平行线，w 和曲线交于一 点m ，表示为m = p + q ，即p 和q 点加运算结果，点加运算如图2 3 所示。 沈阳丁业大学硕士学位论文 y 一仁多一。卉。 0 、n 7 m = 沁 图2 3 点加运算示意图口q ) x ( 2 ) 椭圆曲线群运算规则：文献 1 7 给出了椭圆曲线群运算规则，探讨如下：e o ( ) 表示有限域k 上椭圆曲线解的集合，以及一个无穷远点o 。椭圆曲线e 上的二个点相 加的群运算规则可以通过正切余弦加法运算及这个无穷远点来定义。在描述正切余弦操 作之前，先定义点q e 的负元- q ，其与点q 具有相同的x 坐标。 正切余弦操作可以看作获取椭圆曲线上二点之和的几何方法。该方法在e r r ) 域上最 容易描述。注意到与椭圆曲线相交任何直线都有一个精确的第三点。 为了对二个具有不同x 坐标的点p l 、p 2 进行相加，画一条通过这二个点的直线以 获得与椭圆曲线相交的第三个点p 3 ，则p l + p 2 将由- p 3 给出( 即第三个交点的x 轴的镜 像) 。 若p 是曲线上的无穷远点o ，目, l j - - p = o ，且p + q = q ，o 可视为加法群中的么元， 假设下面的p 、q 均不为无穷远点。 若p - - ( x , y ) ，则- p = ( x ，一y ) 。显然一y 是曲线e 上的点。 若p = ( x 1 ，y 1 ) ，q = ( x 2 ，y 2 ) ，p + q = ( x 3 ，y 3 ) ，在p cq 的情况下，即( x l x 2 , y l o ) ，点加 运算如式( 2 7 ) 所示： x 3 = 矛一z l x 2y 3 = 丑( _ 一x 3 ) 一y 其中，若p q ，则如式( 2 8 ) 所示 ( 2 7 ) 沈m t t k 大学硕士学位论殳 旯= y 2 - y l x 2 - x l 若：p = q ，则如式( 2 9 ) 所示 a = 3 9 + 口2 y 当k = 2 时，加法的公式如下，若p q ，则如式( 2 1 0 ) 所示： ( 2 8 ) ( 2 ，9 ) x 3 = ( y 1 + y 2 x l + x 2 ) 2 + ( y l + y 2 x l + x 2 ) + x l + x 2 + 口2 y 3 = ( y l + y 2 x l + x 2 ) ( x 1 + x 3 ) + x 3 + y l ( 2 1 0 ) 若p = q ，则如式( 2 1 1 ) 所示 屯= x ；+ 口2 x ? y 3 = x ? + ( x 1 + y l x 1 ) x 3 + 工3 ( 2 1 1 ) ( 3 ) 椭圆曲线点群的阶：k 为有限域g f ( q ) ，这里q = p ”个元素，因此，特征值 引入k = p 。为了强调椭圆曲线e ，是定义在有限域上，用e 表示。椭圆曲线上点p 的阶n 是使n p = 0 的最小整数。让# ( e ) 表示在椭圆曲线e 上的点的数量，显然至多有2 q + 1 个点，即无穷远点与2 q 个点对( x ，y ) 。然而这是一个比较弱的上界，因为在g f ( q ) 上随 机选择的二次曲线有5 0 机会可以求解。# ( 疋) 较理想的值是接近q 值。h a s s e 定理 1 8 】证明了有限域g f ( q ) 上的椭圆曲线点群的阶满足公式( 2 1 2 ) ： 式中：= 2 知。 # ( e 。) = q + l + t ( 2 1 2 ) 沈m t 业大学硕l 学位论文 要计算有艮域，计算一条椭圃曲线t 的点群的阶，总的说是比较困难的。s c h o o p ”1 算法是一个在多项式时间内确定阶的方法，但当q 很大时，该算法不是很实用。 ( 4 ) 椭圆曲线离散对数问题：有限域上椭圆曲线点群运算规则，可以看出椭圆曲 线上的点加运算类似于有限域g f ( q 聿) 上的二个元素相乘。因此，椭圆曲线上的点与有限 域上的整数的倍乘f 点积) r a p 的运算，如式( 2 1 3 ) 所示： m p = p 十p + - + p ( 共m 个p ) ( 2 1 3 ) 这里m n 。对于2 p 的形式，称为点p 的平方。 对于有限域上某一元素的k 次幂，其运算可以通过重复平方方法，在 o ( 1 0 9 k l o g 3 g ) 位运算步骤内完成。类似地，点积印e 。运算可以通过重复点倍加方 法，在o ( 1 0 9 k l 0 9 3g ) 位运算步骤内完成，如1 0 0 p = 2 ( 2 ( 1 十2 ( 2 ( 2 ( 1 + 2 p ) ) ) ) ) 。如果恰好知 道椭圆曲线e 。上的点的数量，则由于n p = 0 ，在计算k p 之前，可以用k m o d n 的非负 余数替代k 。下面对椭圆曲线离散对数进行定义。 给定- 条有限域g r ( q ) j 埔椭圆曲线e 。及二个点尸，b e ，寻找个整数，使得p = x b ，如果这样的数存在，这就是椭圆曲线离散对数。也就是说选取该椭圆曲线上的一 个点g ( x ，作为基点，那么给定一个整数m ，计算m g - = q 容易，但是从o 点及g 点推 导出整数m ，则非常困难，即没有多项式时间内求解算法。椭圆曲线离散对数问题是构 造e c c 的数