（计算机软件与理论专业论文）椭圆曲线密码系统的研究与应用.pdf

东北大学硕士学位论文摘要 椭圆曲线密码系统的研究与应用 摘 要 随着信息社会的到来，保证信息的安全可靠的传输成为一个日 益紧迫和重要 的问 题，所以密码系统的研究与应用成为计算机科学领域的一个热点。现在的密 码系统主要分为两种:对称密码系统和公钥密码系统。当今普遍应用的一些密码 系统存在着很多问 题，比如密钥过长，比如计算速度比较缓慢等等。另外，在无 线环境或者智能卡的应用中，由于带宽、计算能力和存储能力都受到了限制，使 得传统的密码系统不适合应用于这些领域。 本文针对这些问题，介绍了一种新的公钥密码系统。这种密码系统是基于椭 圆曲线的，它的安全性是基于椭圆曲线离散对数问题的难解性上。椭圆曲线密码 系统与其他公钥系统相比，在密钥长度增加程度一样的情况下，安全性却有较大 增长。所以在计算能力和存储能力受限的环境下，椭圆曲线密码系统的这个优势 尤其显得突出。另外，以椭圆曲线为基础的安全体系结构具有低功耗，代价小等 优点。椭圆曲线的这些优点使之在很多场合都适合应用，比如无线环境和智能卡 等等。 本文所作的工作包括: ( 1 ) 介绍了 椭圆曲 线密码系统的 基本原理和基本算法， 包括它所基于的数学理 论、有限域上的运算以及一些诸如密钥交换算法、加密算法和数字签名算法等一 些基本算法。 ( 2 ) 介绍了如何构造一个安全的椭圆曲线密码系统， 包括随机产生一条椭圆曲 线，并通过计算曲线的阶来判断该曲线是否安全。 ( 3 ) 利用n i s t推荐的五条曲 线， 编程实现了 一个基于二元域的椭圆曲 线密码 系统，包括密钥交换算法、加密解密算法以 及数字签名算法( e c d s a ) ，并探讨了 将椭圆曲线密钥交换算法应用到 c d m a环境中的问题，最后针对其性能与r s a 密码系统进行了比较。 关键词 椭圆曲线密码系统d i f fi e - h e l l m a n e l g a m a l 数字签名算法 东北大学硕士学位论文 abs tract t h e r e s e a r c h a n d a p p l i c a t i o n o f e l l i p t i c c u r v e c r y p t o s y s t e m s ab s t r a c t b e c a u s e o f t h e c o m i n g o f i n f o r m a t i o n t i m e s , t h e s a f e t r a n s f e r o f in f o r m a t i o n b e c o m e s m o r e im p o r ta n t . s o t h e r e s e a r c h a n d a p p l i c a t i o n o f c r y p t o s y s t e m s h a v e b e c o m e v e ry i m p o r t a n t i n c o m p u t e r s c i e n c e .t h e r e a re t w o k i n d s o f c y p t o s y s t e m s a t p r e n s e n t :s y m m e t r i c c ry p t o s y s t e m s a n d p u b l i c k e y c r y p t o s y s t e m s . b u t t h e r e a r e m a n y d i s a d v a n t a g e s i n c u r r e n t p u b l i c c y p t o s y s t e m s :t h e t o o l o n g k e y s a n d t h e s l o w c o m p u t a t i o n s p e e d .e x c e p t , t h e r e a r e s o m e e n v i r o m e n t s o f t h o s e fi e l d s a r e s p e c i a l s u c h a s i n t e l l i g e n c e c a r d o r m o b i l e e n v i r o m n e n t , in w h i c h t h e b i n d w i d t h , c o m p u t a t i o n a b l i t y a n d s t o r e a b l i t y a r e l i mit e d , s o t h e t r a d i t i o n a l p u b l i c k e y c r y p t o s y s t e m s a r e n o t f i t f o r t h o s e n e w fi e l d s . t o s o l v e t h o s e a b o v e p r o b l e m s ,t h i s p a p e r i l l u s t r a t e s a n e w p u b l i c k e y c ry p t o - s y s t e m ,w h i c h i s b ase d o n e l l ip t i c c u r v e , a n d w h o s e s e c u r i t y i s b as e d o n t h e e l l i p t i c c u r v e d i s c r e e t l o g a r i t h m p r o b l e m ( e c d l p ) .i n c o n t r as t w i t h t h o s e w e l l k n o w n p u b l i c k e y c ry p t o s y s t e m s ,t h e e l l i p t i c c u r v e c r y p t o s y s t e m s ( e c c ) m a i n t a i n r e l i a b l e s e c u r i ty w it h k e y l e n g t h s t h a t a r e s h o r t e r ( t h e r e f o r e m o r e p r a c t i c a l ) . s o i n t h e e n v i r o m e n t w h o s e c o m p u t a t i o n a b l i ty , b i n d w i d t h a n d s t o r e a b l i t y a r e l i m i t e d ,t h e a d v a n t a g e o f e c c i s m o r e i m p o r t a n t an d t h e s e c u r i t y s c h e m e b a s e d o n e c c h a v e l e s s e n e r g y c o s t .t h o s e a d v a n t a g e s o f t h e e c c l e a d i t s e l t t o w i d e r a p p l i c a t i o n in m o r e f i e l d s s u c h as m o b i l e c o m m e r c e ,c e l l p h o n e s y s t e m s , e - c as h , n o t e b o o k p c a n d i n t e ll i g e n t c a r d . t h e f o l l o w i n g a re t h e p o i n t s o f t h i s p a p e r : ( 1 ) t h e i l l u s t r a t i o n o f t h e b a s i c t h e o r i e s a n d a l g o i t h m s o f e c ci n c l u d i n g t h o s e m a t h e m a t i c t h e o ry , c o m p u a t i o n i n in f in i t e f i e l d a n d s o m e b a s i c a l g o r i t h m s s u c h a s k e y e x c h a n g e a l g o r i t h m s , e n c y p t i o n a l g o r i t h m s a n d d i g i t a l s i g n a t u r e a l g o r i t h m s ( 2 ) t b e i l l u s t r a t i o n a b o u t h o w t o c o n s t r u c t a n e w e l l i p t i c c u r v e c ry p t o s y s t e m i n c l u d i n g o b t a i n i n g a n e l l i p t i c c u r v e r a n d o m a n d j u d g in g i t s a f e o r n o t 卜c o m p u t i n g it s o r d e r . ( 3 ) u s i n g t h e f i v e e l l ip t i c c u r v e w h i c h n i s t r e c o m m e n d t o c o n s t r u c t a n e l l i p t i c c u r v e c r y p t o s y s t e m o n b in a ry f i e l d , i m p l e m e n t i n g t h e e l l i p t i c c u r v e d i ff i e - h e l l m a n k e y e x c h a n g e a l g o r i t h m ,t h e e l l i p t i c e u r v e e l g a m a l a l g o r i t h m a n d t h e e l l i p t i c c u r v e s i g i t a l s i g n a t u r e a l g o r i t h m ,a n d t ry i n g t o a p p l y e l l i p t i c c u r v e d i ff i e - h e l l m a n t o c d ma i i i 东北大学硕士学位论文abs tr act a n d t h e c o n t r a s t w i t h r s a c r y p t o s y s t e m. k e y w o r d s e l l i p t i c c u r v e c r y p t o s y s t e m, p u b l i c k e y c r y p t o s y s t e m s ,d i f f i e - h e l l m a n , e l g a m a l ,d i g i t a l s i g n a t u re a l g o r i t h m - i v- 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文 巾取得的研究成果除加以标注和致谢的地方外，不包含其他人已 经发表或撰写过的研究成果，也不包括本人为获得其他学位而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 本人签名：覆身 日期：2 口旺年月 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使 用学位论文的规定：即学校有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权东北 大学可以将学位论文的全部或部分内容编入有关数据库进行检 索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不 同意。) 学位论文作者签名：覆豸 签字b 娲：2 口，f ，6 翮签名：夕妣才 签字：j 布，3 、矗、乒 东北大学硕士学位论文第一章 绪论 第一章 绪论 当今社会已经进入信息时代，计算机己经在各行各业得到充分的使用，各种 各样的数据在各个部门单位乃至个人之间交换、传输。比如消费者通过互联网与 银行交互，存钱、取钱，通过网络与远在异地的商家进行交易;比如商家与商家 之间也互相进行各种形式的货物、现金交易;再比如某个公司内部之间互相传输 数据、信息。除此之外，有些更为机密的数据可能根本就不在网上传输，而是保 存在某台计算机上。所有这些，不管数据是否在网上传输，只要这些数据是秘密 的，是不能让不相关人士看到的，都需要进行加密;而某些特别的信息数据，比 如消费者向商家发出的订单，为了保证订单的不可抵赖性，还需要数字签名。这 些都属于密码系统应用的领域。 1 . 1研究背景 密码系统一般分为两种形式，一种是对称密码系统，比如d e s , a e s 等等; 另外一种是公钥密码系统，比如r s a，比如e l g a m a 1 等等。这两种密码系统都各 有其优点和缺点。对称密码系统计算速度快，但是安全性不如公钥密码系统，密 钥管理和分发也比较困难。而公钥密码系统虽然速度比较慢，但是安全性去 叶目 对 来说比较高。 但是随着各种攻击密码系统的技术的发展， 诸如r s a等的公钥密码 系统遇到了强有力的挑战。为了保证足够的安全性，人们不得不加大密钥长度， 就r s a而言，密钥长度至少应当在 1 0 2 4 位以上，这就加大了系统的负担，使得 这些公钥密码系统的缺点暴露得尤为明显。另外，随着移动电子商务的发展以及 智能卡的普遍应用，传统的公钥密码系统往往由于环境的限制而逐渐不适合应用 于这些新领域，所以急需一种新的效率更高的更安全的公钥密码系统，而椭圆曲 线密码系统就足以满足这些要求。 在现今普遍应用的公钥密码系统中， 椭圆曲线密码系统与其他公钥系统相比， 在密钥长度增加程度一样的情况下，安全性却有较大增长。所以在计算能力和存 储能力受限的环境下，椭圆曲线密码系统的这个优势尤其显得突出。另外，以椭 圆曲线为基础安全体系结构具有低功耗，代价小等优点。椭圆曲线的这些优点使 之在很多场合都适合应用。诸如:无线交易、蜂窝移动系统、医疗记录存储、电 子现金、笔记本电脑、及智能卡等。 1 . 2论文概括 本论文共分为六章。 东北大学硕士学位论文第一章 绪论 第一章 绪论 当今社会已经进入信息时代，计算机己经在各行各业得到充分的使用，各种 各样的数据在各个部门单位乃至个人之间交换、传输。比如消费者通过互联网与 银行交互，存钱、取钱，通过网络与远在异地的商家进行交易;比如商家与商家 之间也互相进行各种形式的货物、现金交易;再比如某个公司内部之间互相传输 数据、信息。除此之外，有些更为机密的数据可能根本就不在网上传输，而是保 存在某台计算机上。所有这些，不管数据是否在网上传输，只要这些数据是秘密 的，是不能让不相关人士看到的，都需要进行加密;而某些特别的信息数据，比 如消费者向商家发出的订单，为了保证订单的不可抵赖性，还需要数字签名。这 些都属于密码系统应用的领域。 1 . 1研究背景 密码系统一般分为两种形式，一种是对称密码系统，比如d e s , a e s 等等; 另外一种是公钥密码系统，比如r s a，比如e l g a m a 1 等等。这两种密码系统都各 有其优点和缺点。对称密码系统计算速度快，但是安全性不如公钥密码系统，密 钥管理和分发也比较困难。而公钥密码系统虽然速度比较慢，但是安全性去 叶目 对 来说比较高。 但是随着各种攻击密码系统的技术的发展， 诸如r s a等的公钥密码 系统遇到了强有力的挑战。为了保证足够的安全性，人们不得不加大密钥长度， 就r s a而言，密钥长度至少应当在 1 0 2 4 位以上，这就加大了系统的负担，使得 这些公钥密码系统的缺点暴露得尤为明显。另外，随着移动电子商务的发展以及 智能卡的普遍应用，传统的公钥密码系统往往由于环境的限制而逐渐不适合应用 于这些新领域，所以急需一种新的效率更高的更安全的公钥密码系统，而椭圆曲 线密码系统就足以满足这些要求。 在现今普遍应用的公钥密码系统中， 椭圆曲线密码系统与其他公钥系统相比， 在密钥长度增加程度一样的情况下，安全性却有较大增长。所以在计算能力和存 储能力受限的环境下，椭圆曲线密码系统的这个优势尤其显得突出。另外，以椭 圆曲线为基础安全体系结构具有低功耗，代价小等优点。椭圆曲线的这些优点使 之在很多场合都适合应用。诸如:无线交易、蜂窝移动系统、医疗记录存储、电 子现金、笔记本电脑、及智能卡等。 1 . 2论文概括 本论文共分为六章。 东北大学硕士学位论文第一章 绪论 我们首先介绍了密码学的定义、分类等一些基本概念。介绍了对称加密体制 和公钥加密体制。并针对对称加密体制，简单的介绍了一下两个典型的加密算法 d e s 和a e s ;针对公钥加密体制，我们简单的介绍了d i f fi e - h e l l m a n 密钥交换算 法、r s a加密算法和e l g a m a l 加密算法。 然后我们介绍了近年来公钥加密体制中的另外一种密码系统也就是本文着重 阐述和研究的椭圆曲线密码系统，着重介绍了椭圆曲线应用于密码系统的历史、 椭圆曲 线的数学理论基础、 椭圆曲 线上点的运算以及d i f fi e - h e l l m a n , e l g a m a l 和 d s a等算法在椭圆曲线密码系统上的变形。 介绍完一些基本知识之后，我们就来到了本篇论文的关键部分，我针对这篇 论文的具体工作大部分就体现在这一部分。在这一部分中，介绍了 如何实现椭圆 曲线密码系统。首先，我阐述了要达到的目 标和需求。然后，在接下来的部分介 绍了如何选取一条安全的椭圆曲线。由于椭圆曲线的阶是检验该曲线是否安全的 最重要的标准，所以 选取椭圆曲 线最主要的工作集中在求椭圆曲线的阶上面。为 此，我们重点介绍了一下 s c h o o f 算法和 a g m算法。在椭圆曲线选择好之后， 我 们重点研究了如何将 d i ff i e - h e l l m a n , e l g a m a l 和 d s a这些算法如何应用于椭圆 曲线密码系统当中，以实现一个简单的椭圆曲线密码系统。并介绍了将椭圆曲线 密钥交换算法应用于c d ma环境中。 接着， 我们又对整个密码系统的性能进行了分析， 并与r s a密码系统在性能 上进行了一个简单的比较。 最后一部分，是结束语，对整个研究工作做出了总结，并对此方面的工作作 出了展望。 东北大学 硕士学位论文第二章 密 码学相关理 论基a d 第二章 密码学相关理论基础 在计算机科学迅速发展的今天，计算机已经广泛应用于各行业部门。计算机 的广泛应用，给人们带来了巨大的社会、经济效益，但与此同时也带来了一些关 于信息安全方面的问题。近年来，密码学研究之所以十分活跃，主要原因是它与 计算机科学的蓬勃发展息息相关。此外还由于电信事业以及防止日益严重的计算 机犯罪的需要。由于公共和私人部门的一些机构愈来愈多地应用电子数据处理， 将数据存储在数据库中，另外有些十分重要的数据也是通过网络来传输，因此防 止非法泄漏、删除、修改等是必须正视的问题。于是，密码系统的应用便称为保 证信息安全的重要措施。在现实生活中，有许多电子平台需要加密服务，例如: 安全访问私有网络，数据银行，电子商务，蜂窝式电话及所有的数据通迅和智能 卡技术。那么，一个比较完善的密码系统应提供下列服务: 保密性:保持电子传输中的数据私有性。即被传输的数据只能由被授权的一 方读取。加密提供秘密性。 认证:保证信息或电子文档的来源已经被正确的识别。在互相认证中，通常 情况下，服务器和用户 ( 或认证双方)相互认证。这种认证典型的代表是通过校 验对方的数字签名证书来实现。 数据完整性:传输中的电子数据在没有被察觉的情况下是不能被修改的。修 改类型包括写、更改、删除等。 不可抵赖性:由服务器和用户在电子交易中所完成的行动具有不可撤消性。 他们被绑定到一起。因此，信息的发出者和接收者都不能否定这笔交易。 在历史上，加密的基本目 标是实现保密性，例如，使得两个人在不安全的信 道中相互传输消息，只有合格的接收方才能读取或理解被传信息。这个目标采用 传统的私钥加密系统能够满足。然而，私钥加密系统具有的一些缺点在某些应用 场合是不适合的。公钥加密系统克服了私钥加密系统所固有的密钥分发和管理问 题，而且更难破解。椭圆曲线公钥加密系统用较少的带宽提供更多的安全性。 2 . 1简介 z . r . i密码学的定义 密码学( c r y p t o l o g y ) 是以 研究秘密通信为目 的，即 研究 对传输信息采取何种 秘密的变换以防止第三方对信息的窃取。密码学，是研究信息系统安全保密的科 学，包含两个分支:密码编码学( c r y p t o g r a p h y ) ，对信息进行编码实现隐蔽信息 - 3 - 东北大学 硕士学位论文第二章 密 码学相关理 论基a d 第二章 密码学相关理论基础 在计算机科学迅速发展的今天，计算机已经广泛应用于各行业部门。计算机 的广泛应用，给人们带来了巨大的社会、经济效益，但与此同时也带来了一些关 于信息安全方面的问题。近年来，密码学研究之所以十分活跃，主要原因是它与 计算机科学的蓬勃发展息息相关。此外还由于电信事业以及防止日益严重的计算 机犯罪的需要。由于公共和私人部门的一些机构愈来愈多地应用电子数据处理， 将数据存储在数据库中，另外有些十分重要的数据也是通过网络来传输，因此防 止非法泄漏、删除、修改等是必须正视的问题。于是，密码系统的应用便称为保 证信息安全的重要措施。在现实生活中，有许多电子平台需要加密服务，例如: 安全访问私有网络，数据银行，电子商务，蜂窝式电话及所有的数据通迅和智能 卡技术。那么，一个比较完善的密码系统应提供下列服务: 保密性:保持电子传输中的数据私有性。即被传输的数据只能由被授权的一 方读取。加密提供秘密性。 认证:保证信息或电子文档的来源已经被正确的识别。在互相认证中，通常 情况下，服务器和用户 ( 或认证双方)相互认证。这种认证典型的代表是通过校 验对方的数字签名证书来实现。 数据完整性:传输中的电子数据在没有被察觉的情况下是不能被修改的。修 改类型包括写、更改、删除等。 不可抵赖性:由服务器和用户在电子交易中所完成的行动具有不可撤消性。 他们被绑定到一起。因此，信息的发出者和接收者都不能否定这笔交易。 在历史上，加密的基本目 标是实现保密性，例如，使得两个人在不安全的信 道中相互传输消息，只有合格的接收方才能读取或理解被传信息。这个目标采用 传统的私钥加密系统能够满足。然而，私钥加密系统具有的一些缺点在某些应用 场合是不适合的。公钥加密系统克服了私钥加密系统所固有的密钥分发和管理问 题，而且更难破解。椭圆曲线公钥加密系统用较少的带宽提供更多的安全性。 2 . 1简介 z . r . i密码学的定义 密码学( c r y p t o l o g y ) 是以 研究秘密通信为目 的，即 研究 对传输信息采取何种 秘密的变换以防止第三方对信息的窃取。密码学，是研究信息系统安全保密的科 学，包含两个分支:密码编码学( c r y p t o g r a p h y ) ，对信息进行编码实现隐蔽信息 - 3 - 东北大学 硕士学位论文第二 章 密 码学 相关 理论基础 的一门学问;密码分析学 c r y p t a n a l y t i. c s ) ，研究分析破译密码的学问。本文中 的研究只涉及到密码编码学。 2 . 1 . 2加密体制的分类 密码编码系统通常根据以 下三个独立的方面进行分类 1 1 . ( 1 ) 用于将明文转换为密文操作的类型。 所有加密算法基于两个基本原则: 替 代，即明文中的每个元素( 比特，字母，比特组合或字母组合) 被映射为另一个元 素; 置换， 即在明文中的元素被重新排列， 对它们的基本要求是不丢失信息 即所 有操作都是可逆转的) 。被称为乘积系统的多数系统涉及到多个阶段的替代和置 换。 ( 2 ) 所使用密钥的数量。 如果发送者和接收者双方使用相同的密钥， 该系统称 为对称加密、单密钥加密，秘密密钥加密或常规加密。如果发送者和接收者各自 使用一个不同的密钥，则该系统称为非对称加密，双密钥加密或公开密钥加密。 ( 3 ) 明文处理的方式。 分组加密一次处理一块元素的输入， 对每个输入块产生 一个输出块。流加密连续的处理输入元素，并随着该过程的进行，一次产生一个 元素的输出。 2 . 2对称加密体制 对称加密算法， 又称私钥加密算法， 就是加密密钥能够从解密密钥中推出来， 反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密 和解密表示为: e k ( a 刃= c d k ( c ) = m 对称加密算法的典型代表有: d e s ,a e s , 3 d e s , r c 2 ,r c 4 , r c 5 , r c 6 , i d e a等。 以d e s 为代表的对称密钥加密算法的设计原则主要基于信息论的混乱和扩散。 混 乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的统计 规律，通常依靠多轮迭代来实现;扩散则应使密钥和明文的每一位影响密文中尽 可能多的位数，这样可以防止逐段破译，并通过s 盒的非线性变换来实现。实际 上，所有的对称密钥加密算法都采用f e i s t e l 网、s 盒及多次迭代等思想。 对称加密有速度上的优点，用软件实现， 对称密钥比非对称密钥快1 0 0 - 1 0 0 0 倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安 全传输密钥。 对称加密系统用键长来衡量加密强度， 4 0比特的键长被认为比较脆 弱，1 2 8 比特比较健壮。 东北大学 硕士学位论文第二 章 密 码学 相关 理论基础 的一门学问;密码分析学 c r y p t a n a l y t i. c s ) ，研究分析破译密码的学问。本文中 的研究只涉及到密码编码学。 2 . 1 . 2加密体制的分类 密码编码系统通常根据以 下三个独立的方面进行分类 1 1 . ( 1 ) 用于将明文转换为密文操作的类型。 所有加密算法基于两个基本原则: 替 代，即明文中的每个元素( 比特，字母，比特组合或字母组合) 被映射为另一个元 素; 置换， 即在明文中的元素被重新排列， 对它们的基本要求是不丢失信息 即所 有操作都是可逆转的) 。被称为乘积系统的多数系统涉及到多个阶段的替代和置 换。 ( 2 ) 所使用密钥的数量。 如果发送者和接收者双方使用相同的密钥， 该系统称 为对称加密、单密钥加密，秘密密钥加密或常规加密。如果发送者和接收者各自 使用一个不同的密钥，则该系统称为非对称加密，双密钥加密或公开密钥加密。 ( 3 ) 明文处理的方式。 分组加密一次处理一块元素的输入， 对每个输入块产生 一个输出块。流加密连续的处理输入元素，并随着该过程的进行，一次产生一个 元素的输出。 2 . 2对称加密体制 对称加密算法， 又称私钥加密算法， 就是加密密钥能够从解密密钥中推出来， 反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密 和解密表示为: e k ( a 刃= c d k ( c ) = m 对称加密算法的典型代表有: d e s ,a e s , 3 d e s , r c 2 ,r c 4 , r c 5 , r c 6 , i d e a等。 以d e s 为代表的对称密钥加密算法的设计原则主要基于信息论的混乱和扩散。 混 乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的统计 规律，通常依靠多轮迭代来实现;扩散则应使密钥和明文的每一位影响密文中尽 可能多的位数，这样可以防止逐段破译，并通过s 盒的非线性变换来实现。实际 上，所有的对称密钥加密算法都采用f e i s t e l 网、s 盒及多次迭代等思想。 对称加密有速度上的优点，用软件实现， 对称密钥比非对称密钥快1 0 0 - 1 0 0 0 倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安 全传输密钥。 对称加密系统用键长来衡量加密强度， 4 0比特的键长被认为比较脆 弱，1 2 8 比特比较健壮。 东北大学 硕士学位论文第二 章 密 码学 相关 理论基础 的一门学问;密码分析学 c r y p t a n a l y t i. c s ) ，研究分析破译密码的学问。本文中 的研究只涉及到密码编码学。 2 . 1 . 2加密体制的分类 密码编码系统通常根据以 下三个独立的方面进行分类 1 1 . ( 1 ) 用于将明文转换为密文操作的类型。 所有加密算法基于两个基本原则: 替 代，即明文中的每个元素( 比特，字母，比特组合或字母组合) 被映射为另一个元 素; 置换， 即在明文中的元素被重新排列， 对它们的基本要求是不丢失信息 即所 有操作都是可逆转的) 。被称为乘积系统的多数系统涉及到多个阶段的替代和置 换。 ( 2 ) 所使用密钥的数量。 如果发送者和接收者双方使用相同的密钥， 该系统称 为对称加密、单密钥加密，秘密密钥加密或常规加密。如果发送者和接收者各自 使用一个不同的密钥，则该系统称为非对称加密，双密钥加密或公开密钥加密。 ( 3 ) 明文处理的方式。 分组加密一次处理一块元素的输入， 对每个输入块产生 一个输出块。流加密连续的处理输入元素，并随着该过程的进行，一次产生一个 元素的输出。 2 . 2对称加密体制 对称加密算法， 又称私钥加密算法， 就是加密密钥能够从解密密钥中推出来， 反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密 和解密表示为: e k ( a 刃= c d k ( c ) = m 对称加密算法的典型代表有: d e s ,a e s , 3 d e s , r c 2 ,r c 4 , r c 5 , r c 6 , i d e a等。 以d e s 为代表的对称密钥加密算法的设计原则主要基于信息论的混乱和扩散。 混 乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的统计 规律，通常依靠多轮迭代来实现;扩散则应使密钥和明文的每一位影响密文中尽 可能多的位数，这样可以防止逐段破译，并通过s 盒的非线性变换来实现。实际 上，所有的对称密钥加密算法都采用f e i s t e l 网、s 盒及多次迭代等思想。 对称加密有速度上的优点，用软件实现， 对称密钥比非对称密钥快1 0 0 - 1 0 0 0 倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安 全传输密钥。 对称加密系统用键长来衡量加密强度， 4 0比特的键长被认为比较脆 弱，1 2 8 比特比较健壮。 东北大学硕士学位论文第二章 密 码学相关理论基拙 对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。 2 . 3公钥加密体制 公开密钥密码学的概念是由wh i t f i e l d d i f fi e和ma rt i n h e l l m a n 首先提出的。 1 9 7 6 年， d i f fi e 和h e l l m a n 在国际计算机会议上首次提出了这个概念。 从1 9 7 6 年 起， 学者们提出了许多种公钥加密方法， 它们的安全性都是基于复杂的数学难题。 根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的: ( 1 ) 基于大整数因子分解的:r s a和 r a b i n - wi l l i a m s ( 2 ) 基于离散对数问题的:d s a和e l g a m a l ( 3 ) 基于椭圆曲线离散对数问题的:椭圆曲线密码系统 公开密钥加密算法于对称密钥加密算法相比来说， 安全性能更好， 密钥管理、 分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对 称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。下面将介绍一下 著名的r s a , e l g a m a l 加密算法和d i f fi e - h e l l m a n 密钥交换算法，以及本文所要 着重阐述的椭圆曲线加密算法。 2 . 3 . 1 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算法可以用于密钥的分 配， 但该算法不能用于加密和解密消息。 下面将简单介绍d i f f i e - h e l l m a n 算法的 实现步骤，并简单讨论其安全性。 2 . 3 . 1 . 1 实现步骤 首先，假定在a l i c e 和b o b 间交换密钥，两人先约定一个大素数n 和一个数 g , b 为模n 的生成元， 这两个数均可以 公开。 ( 1 ) a l i c e 选择一个随 机大整数x ， 并向b o b 发 送x = g x m o d n ( 2 ) b o b 选择一个随 机大整数y ，并向a l i c e 发送y = 才m o d n ( 3 ) a l i c e 计算k = 1 m o d n ( 4 ) b o b 计 算k 气 x m o d n k 和k 都 等 于广m o d n 。 偷听 这 条 信 道 的 任 何 人都 不 能 计 算出 这 个 值， 他 们 即便是通过窃听也只能知道n , g , x和y 。 除非他们能够解决离散对数问 题，即 求出x 和y ， 否则无法求解出k . k 即为a l i c e 和b o b 各自 独立计算出的秘密密钥。 2 . 3 . 1 . 2 安全性讨论 d i f f i e - h e l l m a n 密钥交换协议有一个致命的弱点， 就是其对于中间人攻击是 东北大学硕士学位论文第二章 密 码学相关理论基拙 对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。 2 . 3公钥加密体制 公开密钥密码学的概念是由wh i t f i e l d d i f fi e和ma rt i n h e l l m a n 首先提出的。 1 9 7 6 年， d i f fi e 和h e l l m a n 在国际计算机会议上首次提出了这个概念。 从1 9 7 6 年 起， 学者们提出了许多种公钥加密方法， 它们的安全性都是基于复杂的数学难题。 根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的: ( 1 ) 基于大整数因子分解的:r s a和 r a b i n - wi l l i a m s ( 2 ) 基于离散对数问题的:d s a和e l g a m a l ( 3 ) 基于椭圆曲线离散对数问题的:椭圆曲线密码系统 公开密钥加密算法于对称密钥加密算法相比来说， 安全性能更好， 密钥管理、 分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对 称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。下面将介绍一下 著名的r s a , e l g a m a l 加密算法和d i f fi e - h e l l m a n 密钥交换算法，以及本文所要 着重阐述的椭圆曲线加密算法。 2 . 3 . 1 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算法可以用于密钥的分 配， 但该算法不能用于加密和解密消息。 下面将简单介绍d i f f i e - h e l l m a n 算法的 实现步骤，并简单讨论其安全性。 2 . 3 . 1 . 1 实现步骤 首先，假定在a l i c e 和b o b 间交换密钥，两人先约定一个大素数n 和一个数 g , b 为模n 的生成元， 这两个数均可以 公开。 ( 1 ) a l i c e 选择一个随 机大整数x ， 并向b o b 发 送x = g x m o d n ( 2 ) b o b 选择一个随 机大整数y ，并向a l i c e 发送y = 才m o d n ( 3 ) a l i c e 计算k = 1 m o d n ( 4 ) b o b 计 算k 气 x m o d n k 和k 都 等 于广m o d n 。 偷听 这 条 信 道 的 任 何 人都 不 能 计 算出 这 个 值， 他 们 即便是通过窃听也只能知道n , g , x和y 。 除非他们能够解决离散对数问 题，即 求出x 和y ， 否则无法求解出k . k 即为a l i c e 和b o b 各自 独立计算出的秘密密钥。 2 . 3 . 1 . 2 安全性讨论 d i f f i e - h e l l m a n 密钥交换协议有一个致命的弱点， 就是其对于中间人攻击是 东北大学硕士学位论文第二章 密 码学相关理论基拙 对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。 2 . 3公钥加密体制 公开密钥密码学的概念是由wh i t f i e l d d i f fi e和ma rt i n h e l l m a n 首先提出的。 1 9 7 6 年， d i f fi e 和h e l l m a n 在国际计算机会议上首次提出了这个概念。 从1 9 7 6 年 起， 学者们提出了许多种公钥加密方法， 它们的安全性都是基于复杂的数学难题。 根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的: ( 1 ) 基于大整数因子分解的:r s a和 r a b i n - wi l l i a m s ( 2 ) 基于离散对数问题的:d s a和e l g a m a l ( 3 ) 基于椭圆曲线离散对数问题的:椭圆曲线密码系统 公开密钥加密算法于对称密钥加密算法相比来说， 安全性能更好， 密钥管理、 分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对 称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。下面将介绍一下 著名的r s a , e l g a m a l 加密算法和d i f fi e - h e l l m a n 密钥交换算法，以及本文所要 着重阐述的椭圆曲线加密算法。 2 . 3 . 1 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算法可以用于密钥的分 配， 但该算法不能用于加密和解密消息。 下面将简单介绍d i f f i e - h e l l m a n 算法的 实现步骤，并简单讨论其安全性。 2 . 3 . 1 . 1 实现步骤 首先，假定在a l i c e 和b o b 间交换密钥，两人先约定一个大素数n 和一个数 g , b 为模n 的生成元， 这两个数均可以 公开。 ( 1 ) a l i c e 选择一个随 机大整数x ， 并向b o b 发 送x = g x m o d n ( 2 ) b o b 选择一个随 机大整数y ，并向a l i c e 发送y = 才m o d n ( 3 ) a l i c e 计算k = 1 m o d n ( 4 ) b o b 计 算k 气 x m o d n k 和k 都 等 于广m o d n 。 偷听 这 条 信 道 的 任 何 人都 不 能 计 算出 这 个 值， 他 们 即便是通过窃听也只能知道n , g , x和y 。 除非他们能够解决离散对数问 题，即 求出x 和y ， 否则无法求解出k . k 即为a l i c e 和b o b 各自 独立计算出的秘密密钥。 2 . 3 . 1 . 2 安全性讨论 d i f f i e - h e l l m a n 密钥交换协议有一个致命的弱点， 就是其对于中间人攻击是 东 北大学 硕士学 位论文第二章 密 码学相关理论基础 脆弱的。 假设c a r l 在a l i c e 和b o b 之间窃听， 并且在中间充当一个中间人， 使得 a l i c e 误以为 c a r l 是 b o b ， 使得 b o b 误以为 c a r l 是 a l i c e ， 从而导致 a l i c e与 b o b 之间的通信被 c a r l 所获取。 避免这一问题的一个方法是 a l i c e 和 b o b 分别对其自 身发送的消息进行签名。 另外， 9 和n 的选择会大大影响系统的安全性。 数( n - 1 ) / 2 也应该是一个素数。 最重要的是n 应该很大:系统的安全性基于对与n 长度相同的数进行因数分解的 困难性。 2 . 3 . 2 r s a 加密算法 当前应用最广泛的也是最著名的公开密钥加密算法即是r s a加密算法， 这是 第一个成熟的公开密