（计算机应用技术专业论文）ecdsa在移动电子商务中的应用.pdf

东北大学硕士学位论文摘要 摘要 因特网、移动通信技术和计算机等技术的完美结合创造了移动电子商务， 移动电子商务以其灵活、简单、方便的特点将受到消费者的欢迎。 移动电了商务成功在于安全，当前移动电子商务的最大障碍是安全问题， 能否解决好电子商务系统安全可靠、快速准确等问题，是保证移动电子商务今 后健康发展的关逊因素，移动电子商务的安全性主要通过加密来实现。 在目前的加密方法中， 椭圆曲线加密方法以其安全性高、密钥长 度短、加 密和解密速度快等优点，成为当今密码学领域中最具前途的加密方法。 木文以椭圆曲线密码系统为基础，在深入分析椭圆曲线理论和 e c d s a数字 签名算法的基础 上， 使用 j a v a 语言和j c e工具， 在服务器端生成数字签名， 将 其嵌入 x m l 文档中， 发送给接收方。 接收方通过 x ml解析器对 x mi文档进行 解析，然后进行验证。 通过使用 e c d s a算法进行数字签名，达到安全交易的目的，力求打造一个 安全的移动电子商务环境。 关键词:椭圆曲线 e c d s a移动电子商务 东北大学硕士学位论文 a b s t r a c t a b s t r a c t i n t e r n e t , m o b i l e c o m m u n i c a t i o n t e c h n i q u e a n d c o m p u t e r t e c h n i q u e p e r f e c t c o mb i n e d t o c r e a t e t o mo b i l e e - c o mme r c e , mo b i l e e - c o mme r c e wi l l b e we l c o me a m o n g t h e c o n s u m e r w i t h it s v i v i d , s i m p l e a n d c o n v e n i e n t c h a r a c t e r i s t i c s . mo b i l e e - c o m m e r c e s u c c e e d i n t h e s a f e t y , t h e b i g g e s t o b s t a c l e o f t h e c u r r e n t m o b i l e e - c o m m e r c e i s s a f e t y p r o b l e m ,w e t h e r c a n r e s o l v e m o b i l e e - c o m m e r c e s y s t e m s a f e t y c r e d i b i l i t y , f a s t a c c u r a t e p r o b l e m, i s t h e a s s u r a n c e o f m o b i l e e - c o m m e r c e t o d e v e l o p h e a l t h i l y f r o m n o w o n o f k e y f a c t o r , t h e s a f e t y t h a t m o b i l e e - c o mm e r c e m a i n l y p a s s e s t o e n c r y p t t o c a r ry o u t . i n c u r r e n t l y e n c r y p t m e t h o d , t h e e l l i p t i c c u r v e e n c r y p t s m e t h o d w i t h i t s a d v a n t a g e o f s a f e t y i s h i g h , t h e k e y l e n g t h i s s h o r t , e n c r y p t s a n d d e c r y p t s s p e e d q u i c k ， h a v i n g t h e m o s t f u t u r e i n t h e c u r r e n t . t h i s t e x t t a k e t h e e c c a s t h e f o u n d a t i o n , t h r o u g h a n a l y z e t h e f o u n d a t i o n t h a t t h e e l l i p t i c c u r v e t h e o r i e s a n d e c d s a , u s e j a v a l a n g u a g e a n d t o o l o f j c e , c r e a t e d i g i t a l s i g n a t u r e i n t h e s e r v e r , i m b e d i t i n t h e x ml d o c u m e n t , s e n d o u t t o t h e r e c e i v e r . r e c e i v e r t h r o u g h t h e x ml p a r s e r t o c a r r y o n t h e r e s o l u t i o n t o t h e x ml d o c u m e n t , t h e n c a r r y o n t h e v e r i f i c a t i o n . b y u s e e c d s a , a t t a i n i n g t h e p u r p o s e o f t h e s a f e b a r g a i n , t r y i n g t o c r e a t e a s a f e ty e n v i r o n m e n t o f m o b i l e e - c o m m e r c e . . k e y w o r d s : e l l i p t i c c u r v e e c d s a mo b i l e e - c o m m e r c e i f 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中 取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发 表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示谢意。 学 位 论 文 作 者 签 名 :工薄力 日期: 2 v v 3 . / 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、 使用学 位论文的规定:即学校有权保留并向国家有关部门或机构送交论文 的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以 将学位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同 意。 ) 学 位 论 文 作 者 签 名 : 王挽 b 签字日 期: 2 v v s 人声. 导师签名: 签字日期: : j j 第二，加密方 法的安全性依赖于密钥的秘密性，而不是算法的秘密性。对称加密系统最大的 问题是密钥的分发和管理非常复杂、代价高昂。对称加密算法另一个缺点是不 能实现数字签名。所以，在当今的移动电子商务领域中的加密实现主要是依赖 于公开密钥密码体制。 公开密钥加密系统采用的加密钥匙 ( 公钥) 和解密钥匙 ( 私钥) 是不同的。 由于加密钥匙是公开的，密钥的分配和管理就很简单，公开密钥加密系统还能 够很容易地实现数字签名。因此，最适合于移动电子商务应用需要。 自公钥加密问世以来，学者们提出了许多种公钥加密方法，它们的安全性 都是基于复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目 前被认为是安全和有效的:大整数因子分解系统( 代表性的有 r s a ) ,离散对数 系统 ( 代表性的有d s a ) 和椭圆曲 线离散 对数系统 ( e c c ) a r s a方法的优点主要在于原理简单，易于使用。但是，为了 保证r s a使 用的安全性，其密钥的位数一直在增加，密钥长度的增加导致了其加解密的速 度大为降低， 硬件实现也变得越来越难以忍受， 这对使用r s a的应用带来了很 重的负担，对进行大量安全交易的电子商务更是如此，从而使得其应用范围越 来越受到制约。 d s a ( d a t a s ig n a t u r e a l g o r i th m ) 是 基于离散 对数问 题的 数字 签名标准， 它 仅提供数字签名，不提供数据加密功能。 椭圆曲 线加密算法e c c ( e l l i p t i c c u r v e c r y p t o g r a p h y ) 基于离散对数的 计 算困难性，其思想是在基于有限域的椭圆曲线上对信息进行加密解密。由于有 限域上椭圆曲线的离散对数实际上是一般有限域上的离散对数在椭圆曲线上的 一种类比物， 因此它至少在实用上比一般有限域上的离散对数的计算要困难些， 因此其安全性也要强一些， 是一种安全性更高、 算法实现性能更好的公钥系统。 另外， 椭圆曲线密码体制与其他公钥密码体制相比， 在钥的长度相同的情况下， 它的安全性要更高些。在同样安全要求下，比其它的公开密钥算法的密钥长度 短很多，这扩大了它的应用范围，非常适合于移动设备的要求。 正是基于上述这些原因，目前人们对椭圆曲线密码体制非常感兴趣。这也 东北大学硕士学位论文第一章引言 是本文采用椭圆曲线加密方法来研究移动电子商务安全的原因口 1 . 2论文结构 本文第一章简要阐明论文的研究背景和研究动机，从移动电子商务安全着 手，引入研究方向。 第二章介绍加密系统。描述了对称密钥和公开密钥加密原理和典型的加密 算法， 然后重点介绍了在移动电子商务安全领域广为使用的公开密钥加密方法， 然后通过密钥长度、安全性、灵活性等多方面的特性对这几种算法进行比较， 来论述椭圆曲线密码的优越性和其实用性。 第三章详细地介绍了椭圆曲线的数学原理。 包括椭圆曲线用到的数学理论， 椭圆曲线的定义，椭圆曲线上的数学运算等，对椭圆曲线理论进行全面、详尽 的论述。对如何利用椭圆曲线理论进行加密来进行详细论述，其中包括如何选 择合适的椭圆曲线、如何将明文嵌入到选定的椭圆曲线中、如何利用椭圆曲线 加密方法来进行密钥交换、数字签名和信息加密。 最后，以前面各章的理论为基础，使用j a v a 语言和j c e ( j a v a 加密扩展) 工具， 辅以x ml文档解析工具， 在服务器端生成数字签名， 将其嵌入 x ml文 档中， 发送给接收方。 接收方通过x ml 解析器对x ml文档进行解析， 然后进 行验证，从而达到安全交易的目的。最终设计出一个在移动电子商务中基于椭 圆曲线进行身份鉴别的实例，其中给出了实现的思想和一些和代码及其执行结 果。 东北大学硕士学位论文第一章引言 是本文采用椭圆曲线加密方法来研究移动电子商务安全的原因口 1 . 2论文结构 本文第一章简要阐明论文的研究背景和研究动机，从移动电子商务安全着 手，引入研究方向。 第二章介绍加密系统。描述了对称密钥和公开密钥加密原理和典型的加密 算法， 然后重点介绍了在移动电子商务安全领域广为使用的公开密钥加密方法， 然后通过密钥长度、安全性、灵活性等多方面的特性对这几种算法进行比较， 来论述椭圆曲线密码的优越性和其实用性。 第三章详细地介绍了椭圆曲线的数学原理。 包括椭圆曲线用到的数学理论， 椭圆曲线的定义，椭圆曲线上的数学运算等，对椭圆曲线理论进行全面、详尽 的论述。对如何利用椭圆曲线理论进行加密来进行详细论述，其中包括如何选 择合适的椭圆曲线、如何将明文嵌入到选定的椭圆曲线中、如何利用椭圆曲线 加密方法来进行密钥交换、数字签名和信息加密。 最后，以前面各章的理论为基础，使用j a v a 语言和j c e ( j a v a 加密扩展) 工具， 辅以x ml文档解析工具， 在服务器端生成数字签名， 将其嵌入 x ml文 档中， 发送给接收方。 接收方通过x ml 解析器对x ml文档进行解析， 然后进 行验证，从而达到安全交易的目的。最终设计出一个在移动电子商务中基于椭 圆曲线进行身份鉴别的实例，其中给出了实现的思想和一些和代码及其执行结 果。 东北大学硕士学 位论文第二章加密系统 第二章 加密系统 2 . 1密码学简介 密码学是一门古老而又年轻的科学，它用于保护军事和外交通信可追溯到 几千年前。在当今的信息时代，大量的敏感信息通过公共通信设施或计算机网 络来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，现代 密码学对于军事、政治和外交、商业的价值越来越重要。 明文信息可以用两种办法之一来隐藏: 一是信息隐蔽， 即隐藏信息的存在， 二是利用密码学方法通过对文本信息的不同转换而实现信息的对外不可读。 密码学的发展历史大致可划分为三个阶段: 第一个阶段为从古代到 1 9 4 9年。这一时期可看作是科学密码学的前夜时 期，这段时期的密码技术可以说是一种艺术，而不是一种科学，密码学专家常 常是凭借直觉和信念来进行密码设计和分析，而不是推理证明。例如，最早应 用替代的凯撒密码。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。 1 9 4 9 年s h a n n o n 发表的“ 保密系统的 信息理论”一文为对称密码系统建立了理论基础，从此密码学成为一门科学， 人们将此阶段使用的加密方法称为传统加密方法，其安全性依赖于密钥的秘密 性，而不是算法的秘密性，也就是说，使得基于密文和加解密算法的知识去解 密一段信息在实现上不可能。 1 9 7 7年美国国家标准局正式公布实施了美国的数据加密标准 ( d e s ) ，公 开它的加密算法，并批准用于非机密单位和商业上的保密通信。密码学的神秘 面纱从此被揭开。 第三个阶段 1 9 7 6 年至今。1 9 7 6 年d i ff i e 和h e l l m a n 的 “ 密码学的新方向” 一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传 输的保密信息是可能的，从而开创了公钥密码学的新纪元。 在密码学的发展过程中，数学和计算机科学作出了卓越的贡献。数学中许 多分支如数论、概率统计、近世代数、信息论、椭圆曲线理论、算法复杂性理 论、自动机理论、编码理论等都可以在其中找到各自的位置。它的踪影遍及数 东北大学硕士学 位论文第二章加密系统 第二章 加密系统 2 . 1密码学简介 密码学是一门古老而又年轻的科学，它用于保护军事和外交通信可追溯到 几千年前。在当今的信息时代，大量的敏感信息通过公共通信设施或计算机网 络来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，现代 密码学对于军事、政治和外交、商业的价值越来越重要。 明文信息可以用两种办法之一来隐藏: 一是信息隐蔽， 即隐藏信息的存在， 二是利用密码学方法通过对文本信息的不同转换而实现信息的对外不可读。 密码学的发展历史大致可划分为三个阶段: 第一个阶段为从古代到 1 9 4 9年。这一时期可看作是科学密码学的前夜时 期，这段时期的密码技术可以说是一种艺术，而不是一种科学，密码学专家常 常是凭借直觉和信念来进行密码设计和分析，而不是推理证明。例如，最早应 用替代的凯撒密码。 第二个阶段为从1 9 4 9 年到1 9 7 5 年。 1 9 4 9 年s h a n n o n 发表的“ 保密系统的 信息理论”一文为对称密码系统建立了理论基础，从此密码学成为一门科学， 人们将此阶段使用的加密方法称为传统加密方法，其安全性依赖于密钥的秘密 性，而不是算法的秘密性，也就是说，使得基于密文和加解密算法的知识去解 密一段信息在实现上不可能。 1 9 7 7年美国国家标准局正式公布实施了美国的数据加密标准 ( d e s ) ，公 开它的加密算法，并批准用于非机密单位和商业上的保密通信。密码学的神秘 面纱从此被揭开。 第三个阶段 1 9 7 6 年至今。1 9 7 6 年d i ff i e 和h e l l m a n 的 “ 密码学的新方向” 一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传 输的保密信息是可能的，从而开创了公钥密码学的新纪元。 在密码学的发展过程中，数学和计算机科学作出了卓越的贡献。数学中许 多分支如数论、概率统计、近世代数、信息论、椭圆曲线理论、算法复杂性理 论、自动机理论、编码理论等都可以在其中找到各自的位置。它的踪影遍及数 东北大学 硕士学位论文第二章加密系统 学许多分支，而且还推动了并行算法的研究，从而成为近若干年来非常引人入 胜的领域。 随着计算机网络不断渗透到各个领域，密码学的应用也随之扩大。数字签 名、身份鉴别等都是由密码学派生出来的新技术和应用。 现代密码学中有多种加密算法，各具特色，但算法大多是公开的，所以密 码的安全性主要依赖于密钥，对加密算法的总体分类也是以密钥为标准的，主 要分为两种:对称密钥算法，即加密密钥和解密密钥一样，密钥需要保密;非 对称密钥算法，也称公开密钥算法，即加密密钥和解密密钥不一样，称为公钥 和私钥，公钥公开，私钥保密。 2 . 2对称密钥密码体制简介 所谓对称密钥密码体制是指加密和解密均采用同一把秘密钥匙，而且通信 双方都必须获得这把钥匙，并保持钥匙的秘密。算法公开，整个系统的安全性 依赖于密钥的保密。仁们 对称算法的加密和解密过程如图2 . i 所示: 图z . 1单钥的加/ 解密 f i g . 2 . 1 p r i v a t e k e y e n c r y p t i o n a n d d e c r y p t i o n 对称加密算法可分为两类:一次只对明文中的单个比特 ( 或字节)运算的 算法称为序列算法或流密码。另一类算法是对明文的一组比特并行运算，这些 比特组称为分组，相应的算法称为分组算法或分组密码。 对称加密系统最著名的 是美国 数据加密标准 d e s , a e s ( 高级加密标准) 和 欧洲数据加密标准i d e a . 对称密码系统的安全性依赖于以下两个因素。第一，加密算法必须是足够 强的，仅仅基于密文本身去解密信息在实践上是不可能的;第二，加密方法的 安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保 算法的秘密性，而需要保证密钥的秘密性。 对称加密系统的算法实现速度极快， 从a e s 候选算法的测试结果看， 软件 东北大学 硕士学位论文第二章加密系统 学许多分支，而且还推动了并行算法的研究，从而成为近若干年来非常引人入 胜的领域。 随着计算机网络不断渗透到各个领域，密码学的应用也随之扩大。数字签 名、身份鉴别等都是由密码学派生出来的新技术和应用。 现代密码学中有多种加密算法，各具特色，但算法大多是公开的，所以密 码的安全性主要依赖于密钥，对加密算法的总体分类也是以密钥为标准的，主 要分为两种:对称密钥算法，即加密密钥和解密密钥一样，密钥需要保密;非 对称密钥算法，也称公开密钥算法，即加密密钥和解密密钥不一样，称为公钥 和私钥，公钥公开，私钥保密。 2 . 2对称密钥密码体制简介 所谓对称密钥密码体制是指加密和解密均采用同一把秘密钥匙，而且通信 双方都必须获得这把钥匙，并保持钥匙的秘密。算法公开，整个系统的安全性 依赖于密钥的保密。仁们 对称算法的加密和解密过程如图2 . i 所示: 图z . 1单钥的加/ 解密 f i g . 2 . 1 p r i v a t e k e y e n c r y p t i o n a n d d e c r y p t i o n 对称加密算法可分为两类:一次只对明文中的单个比特 ( 或字节)运算的 算法称为序列算法或流密码。另一类算法是对明文的一组比特并行运算，这些 比特组称为分组，相应的算法称为分组算法或分组密码。 对称加密系统最著名的 是美国 数据加密标准 d e s , a e s ( 高级加密标准) 和 欧洲数据加密标准i d e a . 对称密码系统的安全性依赖于以下两个因素。第一，加密算法必须是足够 强的，仅仅基于密文本身去解密信息在实践上是不可能的;第二，加密方法的 安全性依赖于密钥的秘密性，而不是算法的秘密性，因此，我们没有必要确保 算法的秘密性，而需要保证密钥的秘密性。 对称加密系统的算法实现速度极快， 从a e s 候选算法的测试结果看， 软件 东 北大学硕士学位论文第二章 加密系统 实现的速度都达到了每秒数兆或数十兆比特。对称密码系统的这些特点使其有 着广泛的应用。因为算法不需要保密，所以制造商可以开发出低成本的芯片以 实现数据加密。这些芯片有着广泛的应用，适合于大规模生产。 对称加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂。比如 对于具有n 个用户的网络， 需要n ( n - 1 ) / 2 个密钥， 在用户群不是很大的情况下， 对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密 钥的分配和保存就成了大问题。 对称加密算法另一个缺点是不能实现数字签名。 所以在移动电子商务安全领域对称密钥密码体制有其密钥分发困难、密钥 管理难、无法实现数字签名的缺点，不能满足移动电子商务安全的需要。 2 . 3公开密钥密码体制介绍 公钥密码学是整个密码学发展历史中最伟大的一次革命，公钥密码学与其 前传统的密码学完全不同，它的出现使密码学的研究发生了巨大的变化。与传 统加密系统不同的是，使用这种方法的加密系统，不仅公开加密算法本身，也 公开了加密用的密钥。 公开密钥算法的加密和解密过程如图2 . 2 所示: 加密 解密 图2 . 2公开密钥算法的加/ 解密 f i g 2 .2 p u b l i c k e y e n c ry p t i o n a n d d e c ry p t i o n 公开密钥算法是基于数学函数而不是基于替换和置换，更重要的是，与只 使用一个密钥的对称传统密码不同，公钥密码学是非对称的，它使用两个独立 的密钥。我们将会看到，使用两个密钥在消息的秘密性、密钥分配和认证领域 有着重要意义。 目前的公钥密码系统主要依赖下面三种数学难题: ( 1 )大整数因子分解问题 ( 2 )离散对数问题 ( 3 )椭圆曲线上的离散对数问题 东 北大学硕士学位论文第二章 加密系统 实现的速度都达到了每秒数兆或数十兆比特。对称密码系统的这些特点使其有 着广泛的应用。因为算法不需要保密，所以制造商可以开发出低成本的芯片以 实现数据加密。这些芯片有着广泛的应用，适合于大规模生产。 对称加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂。比如 对于具有n 个用户的网络， 需要n ( n - 1 ) / 2 个密钥， 在用户群不是很大的情况下， 对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时，密 钥的分配和保存就成了大问题。 对称加密算法另一个缺点是不能实现数字签名。 所以在移动电子商务安全领域对称密钥密码体制有其密钥分发困难、密钥 管理难、无法实现数字签名的缺点，不能满足移动电子商务安全的需要。 2 . 3公开密钥密码体制介绍 公钥密码学是整个密码学发展历史中最伟大的一次革命，公钥密码学与其 前传统的密码学完全不同，它的出现使密码学的研究发生了巨大的变化。与传 统加密系统不同的是，使用这种方法的加密系统，不仅公开加密算法本身，也 公开了加密用的密钥。 公开密钥算法的加密和解密过程如图2 . 2 所示: 加密 解密 图2 . 2公开密钥算法的加/ 解密 f i g 2 .2 p u b l i c k e y e n c ry p t i o n a n d d e c ry p t i o n 公开密钥算法是基于数学函数而不是基于替换和置换，更重要的是，与只 使用一个密钥的对称传统密码不同，公钥密码学是非对称的，它使用两个独立 的密钥。我们将会看到，使用两个密钥在消息的秘密性、密钥分配和认证领域 有着重要意义。 目前的公钥密码系统主要依赖下面三种数学难题: ( 1 )大整数因子分解问题 ( 2 )离散对数问题 ( 3 )椭圆曲线上的离散对数问题 东北大学 硕士学 位论文第二章 加密系 统 按照基于的数学问题，公钥密码体制可分为以下三类。 2 . 3 . 1整数分解和 r s a 这个公钥系统是由r i v e t , s h a m i r , a d e l m a n提出的，简称为r s a系统， 它的安全性是基于大整数因子分解的困难性，而大整数因子分解问题是数学上 的著名难题，因而可以确保 r s a算法的安全性。r s a系统是公钥系统的最具 有典型意义的方法，自 提出以来就一直是人们研究的焦点。对于密码破译者来 说，在这种系统中，已知密文而想得出明文就必须进行大整数的因子分解。 r s a算法是 “ 整数分解”密码家族中最著名的例子，采用该方案如要提高 安全性则要采用尽可能大的整数，以防止对算法采取 “ 蛮力攻击。目前，7 6 8 位的二进制整数可基本满足需要， 但采用 1 0 2 4 位整数更保险一些。 对安全性要 求很高的部门如政府，则要采用2 0 4 8 位。 目 前人们认为，r s a的安全性依赖于大整数分解的数学困难性，而系统的 加密速度则取决大整数的模指数运算。2 ) 先选择两个等长的随机大素数1 和q ， 其主要算法如所示: 表 2 . 1 r s a 算法 t a b l e 2 . 1 r s a a r i t h m e t i c 公开密钥 两个素数p 和9 的乘积( p , 4 必须保密) 随机选择，满足与( p - 1 ) ( 4 - 1 ) 互素 秘密密钥 d 满足e d - 1 ( m o d ( p 一 1 ) ( q 一 1 ) ) 加密 c=me mo d n 解密 m= c 0 m o d n 需要强调的是r s a系统的 “ 可逆性” ，即对于不同目的，可采用公开密钥 或者秘密密钥对信息进行运算。 从上述介绍中不难看出，r s a方法的优点主要在于原理简单，易于使用。 但是，随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络 的发展 ( 可以使用成千上万台机器同时进行大整数分解) ，作为r s a加解密安 全保障的大整数要求越来越大。 为了保证r s a使用的安全性， 其密钥的位数一直在增加，比如，目前一般 认为r s a需要 1 0 2 4 位以上的字长，显然，密钥长度的增加导至了其加解密的 速度大为降低， 硬件实现也变得越来越难以任受， 这对使用r s a的应用带来了 很重的负担，对进行大量安全交易的电子商务更是如此，从而使得其应用范围 越来越受到制约。 东北大学 硕士学 位论文第二章 加密系 统 按照基于的数学问题，公钥密码体制可分为以下三类。 2 . 3 . 1整数分解和 r s a 这个公钥系统是由r i v e t , s h a m i r , a d e l m a n提出的，简称为r s a系统， 它的安全性是基于大整数因子分解的困难性，而大整数因子分解问题是数学上 的著名难题，因而可以确保 r s a算法的安全性。r s a系统是公钥系统的最具 有典型意义的方法，自 提出以来就一直是人们研究的焦点。对于密码破译者来 说，在这种系统中，已知密文而想得出明文就必须进行大整数的因子分解。 r s a算法是 “ 整数分解”密码家族中最著名的例子，采用该方案如要提高 安全性则要采用尽可能大的整数，以防止对算法采取 “ 蛮力攻击。目前，7 6 8 位的二进制整数可基本满足需要， 但采用 1 0 2 4 位整数更保险一些。 对安全性要 求很高的部门如政府，则要采用2 0 4 8 位。 目 前人们认为，r s a的安全性依赖于大整数分解的数学困难性，而系统的 加密速度则取决大整数的模指数运算。2 ) 先选择两个等长的随机大素数1 和q ， 其主要算法如所示: 表 2 . 1 r s a 算法 t a b l e 2 . 1 r s a a r i t h m e t i c 公开密钥 两个素数p 和9 的乘积( p , 4 必须保密) 随机选择，满足与( p - 1 ) ( 4 - 1 ) 互素 秘密密钥 d 满足e d - 1 ( m o d ( p 一 1 ) ( q 一 1 ) ) 加密 c=me mo d n 解密 m= c 0 m o d n 需要强调的是r s a系统的 “ 可逆性” ，即对于不同目的，可采用公开密钥 或者秘密密钥对信息进行运算。 从上述介绍中不难看出，r s a方法的优点主要在于原理简单，易于使用。 但是，随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络 的发展 ( 可以使用成千上万台机器同时进行大整数分解) ，作为r s a加解密安 全保障的大整数要求越来越大。 为了保证r s a使用的安全性， 其密钥的位数一直在增加，比如，目前一般 认为r s a需要 1 0 2 4 位以上的字长，显然，密钥长度的增加导至了其加解密的 速度大为降低， 硬件实现也变得越来越难以任受， 这对使用r s a的应用带来了 很重的负担，对进行大量安全交易的电子商务更是如此，从而使得其应用范围 越来越受到制约。 东北大学硕士学 位论文第 二章 加密系 统 2 . 3 . 2离散对数和 d s a d i ff e - h e l l m a n 密钥协商方案是所有公钥密码方案的鼻祖， 它是基于离散对 数问题的。基于这个问题，t a h e r e i g a ma l提出了第一个公开密钥密码系统， 包括两类:一个用于加密，另一个用于数字签名。美国政府的d s a 算法就是基 于e i g a m a l 的成果之上， 稍加改造而形成的【a 1 离散对数问题可做以下的简单理解:对于一个模素数 p ，给定一个介于 。 到p - 1 的整数9 ，一个数y ，存在某一个x ，满足以下关系式: y = g ( m o d p ) 求离散对数，即己知 y 9 ，求 x 。就像整数分解一样，求离散对数目 前仍 没有高效的算法。 d s a签名算法如表所示1 1 表2 . 2 ds a算法 t a b l e t . 2 ds a a r i t h me t i c 公开密钥p 5 1 2 位到1 0 2 4 位二进制素数 q 1 6 0 位的p - 1 的素数因子 g = h tv - p i4 m o d p ， 其 中h 小 于p - 1 ， 且 v = ( ( g * y ) m o d p ) m o d q y = g ( m o d p ) 秘密密钥 m称为是这个同余式的模。 如:2 3 - ( 1 1 m o d 1 2 ) 模运算与普通运算相似，满足交换律、结合律和分配律。 密码学中用到很多模运算，因为计算模m的离散对数和平方根都很困难。 ( 2 )模逆 也称为乘法逆元。 即已 知a ，其模逆表示为a l ，满足 a * a = 1 ( m o d m ) .i 3 . 东 北大学硕士学位论文第三章 椭a曲 线加密算法 g f ( p) 。 椭圆曲线通常用 e表示。除了曲线e的所有点外，尚需加上一个叫无穷远 点的特殊点o( 可将此无穷远点想象成是两条平行直线在无穷远处的交点) 。 也 就是说满足方程 ( 3 - 1 )的光滑曲线加上一个无穷远点o ，组成了椭圆曲线。 3 . 2椭圆曲线的图像 椭圆曲线的形状，并不是椭圆的。由椭圆曲线的定义可以知道，椭圆曲线 是光滑的，有时对应的是一条怪异的曲线。 图3 . 1 f i g 3 . 1 y z = y z = x 3 一 3 x + 3 x 3 一 3 x + 3 图 3 .2 f i g 3 . 2 少 2 = x 3 一 x 夕 2 = x 3 一 x 3 . 3椭圆曲线中的数学定义 在详细介绍椭圆曲线数学运算之前， 先简要介绍一下其中的数学基础知识。 ( 1 )同余 若a - b = k m，我们就说a 和b 模m同余，记以 a - b ( m o d m ) 其中d a e g m称为是这个同余式的模。 如:2 3 - ( 1 1 m o d 1 2 ) 模运算与普通运算相似，满足交换律、结合律和分配律。 密码学中用到很多模运算，因为计算模m的离散对数和平方根都很困难。 ( 2 )模逆 也称为乘法逆元。 即已 知a ，其模逆表示为a l ，满足 a * a = 1 ( m o d m ) .i 3 . 东北大学硕士学 位论文第三章椭圆曲 线加密算法 其中m为模。 如:5 关于模 1 4的模逆为3 0 通常，a 与m互素，模逆有唯一解，否则，该方程无解。 求模逆的方法有多种，其中e u c l i d 算法最为简洁。 ( 3 )二次剩余 设p 为素数，a 大于0 且a 小于p ，如果存在某个x ，满足 x ， 三 a ( m o d p ) 则a 是模p 的二次剩余，否则a 是模p 的非二次剩余。 ( 4 )群5了 群的 概念: 给定一集合g = 恤b , . . 和该集合上的 运算气满足下列四 条件 的代数系统 称为群: ( a ) 封闭 性:若a , b e g，则存在。 e g，使a * b = c ( b ) 结 合 律 成 立:a , b , c e g ， 恒 有 ( a * b ) * c = a * ( b * c ) o ( c ) 存在单位元素e :即存在。 e g，对b a e g,恒有a * e = e * a = a o ( d ) 存在逆元素: 对于b a e g， 恒有 ， 使a * b = b * a = e ， 元素b 称为a 的逆 元素，用a， 表示，即b = a . 若对a , b e g，有a * b = b * a ，则称 为阿贝尔 ( a b e l )群。 ( 5 )域 域的概念: f 是至少含有两个元素的集合， 对f定义了两种运算“ + ” 和“ * ” ， 并且满足以下三条件的代数系统 称为域。 ( a ) f 的元素关于运算 “ 十 ”构成阿贝尔群，设其单位元为。 。 ( b ) f 1 0 关于运算 “ * ”构成阿贝尔群。 ( c ) 对于a , b , c e f，分配律成立。 若域f 的元素有限个，则称之为有限域或伽罗瓦( g a l o i s ) 域。 有限 域中 元素个数为 一个素 数， 或者一个素 数的 乘方， 记为g f ( p ) . 密码学中用到很多有限域中的运算，因为可以应用数论中的理论，保持数 的大小在有限的范围内 ， 且不会有取整的 误差。 很多密码系统都基于g f ( p ) , 其中p 为素数，本论文中用到的椭圆曲 线也基于此。 ( 6 )阶 一个群g所含元素的个数个数叫做群g的阶， 记作】g i 。 如果g 是有限的， 则称g是一个有限群，否则称g是一个无限群。 椭圆曲线上点的阶与椭圆曲线的阶不同。 椭圆曲线上点的阶是这样定义的: 1 4. 东北大学硕士学位论文 第三章 椭国曲线加密算法 如果椭圆曲线土 一 点p ,存在最小的正整数n ，使得数乘n p = o，则将n 称为p 的 阶，若 n 不存在，我们说p是无限阶的。 事实 卜 ，在有限域上定义的椭圆 曲线上所有的点的阶n 都是存在的。 我们常用# e ( f p ) 表示e ( f p )中点的数目， 要计算# e ( f p )的精确值是 十分困难的， 但下而的结果给出了 # e up )的一个界 定 理( h a s s e ) : 设 、 e ( f p ) = p + 1 -t , it l 2 扣 ( 7 ) 单向 哈希函 数倪 一个单向哈希函数 h ( m) ， 操作 一 个任意长度的消息 m， 返回 一 个固定长 度的值 h : h = h ( m) ,其中:h 长度为 m a 单向哈希函数的一些单向性质: ( a ) 给定m，很容易计算h ; ( b ) 给定h ，很难计算m，使h ( m) = h ; ( c ) 给定m,很难找到另一个消息m ，使h ( m) = h ( m ) . 单向哈希函数的主要目的就是要提供一个 m 的唯一 “ 指纹” ，使其它人无 法伪造。 在椭圆曲线密码系统中，用到了许多数论方面的数学知识，详细内容可参 考有关数论方面的书籍。 3 .4椭圆曲线中的数学运算 3 . 4 . 1椭圆曲线上点的加法 已经看过了椭圆曲线的图象，但点与点之间好象没有什么联系。能不能建 立一个类似于在实数轴上加法的运算法则al e ?自从近世纪代数学引入了群、 环、 域的概念，使得代数运算达到了高度的统一。 运算法则:任意取椭圆曲线上两点p . q ( 若p . q两点重合，则做p点 的切线)做直线交于椭圆曲线的另一点 r ，做 r 点和无穷远点 o的边线 ( 即 过r 做 y轴的平行线)交椭圆曲 线于r ，我们规定p (d q= r( 为方便起见， 用 + 代替， 即p + q = r ) o .1 5 . 东北大学硕士学位论文 第三章 椭国曲线加密算法 如果椭圆曲线土 一 点p ,存在最小的正整数n ，使得数乘n p = o，则将n 称为p 的 阶，若 n 不存在，我们说p是无限阶的。 事实 卜 ，在有限域上定义的椭圆 曲线上所有的点的阶n 都是存在的。 我们常用# e ( f p ) 表示e ( f p )中点的数目， 要计算# e ( f p )的精确值是 十分困难