（系统工程专业论文）刘氏加密算法的改进与密码协议分析.pdf

江苏大学硕士研究生学位论文 摘要 信息安全技术是现代通信技术进一步发展的基础。随着信息交换的日益增 多，信息受到非法侵害的可能性大大增加，所以信息安全就显得愈加重要。 随着计算机通信技术与i n t e m e t 的飞速发展，用户对信息的安全存储、安全 处理和安全传输的需求越来越迫切。密码学作为信息安全的关键技术，是目前研 究领域的一个热点，也是计算机网络安全的基础。论文就密码系统的发展，传统 密码技术及公开密钥密码技术进行了说明，并对未来密码系统的发展进行了展 望；分析了私钥密码系统以及公钥系统等近代加密算法的原理及优缺点；然后介 绍了刘氏加密算法。 论文针对刘氏加密算法的不足，重点提出了一种改进方法，并用v i s u a lb a s i c 语言进行了编程，用软件实现了这一改进后的加密算法，给出了文本加密实例。 论文最后着重于分析密码系统的安全性，在此基础上介绍了安全协议的特征 和协议的形式化分析工具，重点介绍了基于并发、异步的协议分析工具p e t r i 网，运用p e t r i 网对n s 协议建立了时延p e t r i 网模型，并对其进行了分析研究； 同时在n - s 协议时延p e t r i 网模型的基础上构造了带a r p n 模型并进行了分析， 获得了执行序列和攻击剧情，并分析了a t p n 软件的复杂度及其时间延迟。通过 上述分析揭示了形式化工具对验证协议正确性以及发现协议缺陷所起的重要作 用，随着安全协议及其分析技术的不断发展，提出了安全协议自动生成的构想。 关键词：信息安全，密码学，安全协议，身份认证，加密机制 江苏大学硕士研究生学位论文 i n f o r m a t i o ns e c u r i t yi st h eb a s eo ft h ed e v e l o p m e n to fm o d e mc o m m u n i c a t i o nt e c h n o l o g y , a sl h ei n c r e a s eo f t h ei n f o r m a t i o ne x c h a n g e , t h ep o s s i b i f f t yo f i n f o r m a t i o nd a m a g ei si n c r e a s i n g t h ed e m a n do f t h es a f e t yo f i n f o r m a t i o ni su r g e n td a yb yd a y w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o nt e c h n o l o g ya n di n t e m e lt h en e e d sf o rt h e i n f o r m a t i o ns t o r a g ea n dc o m m u n i c a t i o ni ns e c u r i t yw a ya r eb e c o m i n gm o r eu r g e n t a st h em a i n t e c h n i q u eo fi n f o r m a t i o ns e c u r i t y ，c r y p t o g r a p h yh a sb e e na c t i v er e c e n t l ya n di ti st h eb a s eo f c o m p u t e rs e c u r i t y t h i sp a p e rd i s c u s s e st h ed e v e l o p m e n to ft h ec t y p t o g r a p h y ，t r a d i t i o n a lk e y t e c h n o l o g ya n dp u b l i ck e yt e c h n o l o g y , i ti sa n a l y s e dt h a tt h ep r i r a t ek e yc r y p t o g r a p h ya n d c o m m o nk e ys y s t e m ，e t c e n c r y p tt h ep r i n c i p l ea n dp l u s e sa n dm i n u s e so f t h ea l g o r i t h mi nm o d e m t i m e s t h e nd i s c u s st h el i u se n c r y p t i o na l g o r i t h m t h i sp a p e rp u tf o r w a r dak i n do f i m p r o v e m e n ts c h e m eo nt h ed e f i c i e n c yo f t h ea l g o r i t h ma n d r e a l i z et h i sm a i nt h o u g h to fm o d e lc a r r i e do np r o g r a m m i n gi nv i s u a lb a s i cl a n g u a g ea n dp r o v i d e t h ee n c r y p t i o ni n s t a n c e t h i sp a p e rf o c u s e do na n a l y s i n gt h es e c u r i t ya n dm a n a g e m e n to ft h ec r y p t o g r a p h yf i n a l l y , i n t r o d n c es o m ec h a r a c t e r i s t i c so f s e c u r i t yp r o t o c o ls y s t e m a t i c a l l yo nt h i sb a s i s ，a b o u tt h ep r o t o c o l o fa n a l y s i n gt o o l si n t r o d u c e dt h et o o lo fp a t t in e t w o r ko nt h eb a s eo fa s y n c h r o n o u sa n d s i m u l t a n e o u ss i t u a t i o n ，b ya p p l y i n gp e r un e tt oa n a l y z i n gt h es e c u r i t yp r o t o c o lw cc a nf i n dt h e i m p o r t a n c eo ff o r m a lm e t h o d si nv c r i l y i n gt h ec o r r e c t n e s sa n dd e t e c t i n gw e a k n e s so fs e c u r i t y p o o c t o l s o nt h ef o u n d a t i o no f t p n m o d e lo f n - sp r o t o c o lc a r r i e do u tt h em o d e lo f a t p na n dt h e a r r a ya n da t t a c k e ds t o r ya tt h es a m et i m e ，i nt h ee n da n a l y z i n gt h ec o m p l e x i t yo f a t p ns o f t w a r e a n de s t i m a t e de x e c u t i o nt i m e w i t ht h ed e v e l o p m e n to fs e c u r i t yp r o t o c o l sa n dt h e i ra n a l y s i s t e c h n o l o g y , at h o u g h to f a u t o m a t e dg e n e r a t o ro f s e c u r i t yp r o t o c o l si sp r o v i d e d k e y w o r d s ：i n f o r m a t i o ns e c u r i t y , c r y p t o g r a p h y , s e c u r i t yp r o t o c o l ，i d e n t i t ya u t h e n t i c a t i o n 。 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囵。 学位论文作者签名 劳嘶 导师签名垫z 崤 签字f i 期：叩降月孑j 日签字日期：加嘭年多月2 ，日 f 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年 月日 江苏大学硕士研究生学位论文 第一章绪论 1 1 信息系统的安全需求 在现代信息社会中，信息是人类最宝贵的资源。对一个企业来讲，信息是 企业的生命，关系到企业的发展，甚至关系到企业的生死存亡。由于信息在社 会、经济活动中起着越来越重要的作用，信息安全甚至成为活动成败的关键要 素，日益引起人们的重视。 随着信息系统的广泛建立和规模化，计算机的应用形式上升为网络形态， 这种网络化的信息系统在系统内纵向贯通，在系统间横向渗透，构成了集通信、 计算机和信息处理于一体的庞大而复杂的系统，成为现代社会运转所不可缺少 的基础。人们意识到，系统的安全问题不能从单个功能、单个网络考虑，而必 须从体系结构上全面而系统地考虑。 所谓信息系统的安全，是指为信息处理系统建立所采取的技术和管理的安 全保护措施，以保护计算机系统中的硬件、软件及数据，防止其因偶然或恶意 的原因而使系统或信息遭到破坏、更改或泄露。信息系统安全的内容包括了计 算机安全技术、安全管理、安全评价概括起来，信息系统的安全性问题被区 分为三大类，即技术安全类、管理安全类和政策法律类，其安全应用模型如图 1 1 所示 的安全机制 图i i 信息系统安全应用的模型 f i 9 1 1m o d e lo f t h e i n f o r m a t i o ns y s t e ms e c u r i t y a p p l i c a t i o n 当前，国际互连网作为许多国家的基础信息设施，其建设己受到了高度重 江苏大学硕士研究生学位论文 视，并得到了迅速发展。迅猛崛起的互连网技术正把世界联成一个攘体，使得 信息的传输与加工可以在瞬间跨越地理位置的障碍遍布世界各地。信息处理几 乎己深入到各行各业并已经进入家庭。这一切使得人类开始进入信息化社会。 显然，信息的重要性和战略地位，使得信息安全与数据保密变得至关重要，受 到了国际社会的普遍关注。因为，没有信息安全，就没有完全意义上的国家安 全。而现代的信息安全除了涉及到国家安全外；更涉及到个人权益、企业生存 和金融风险防范等可以说，信息安全与国家、单位和个人都是息息相关。 1 2 信息系统安全研究现状 随着信息技术的发展与应用，信息安全的内涵在不断地延伸，从最初的信 息保密性发展到信息的完整性，可用性，可控性和不可否认性，进而又发展为 “攻击，防范，检测，控制，管理，评估”等多方面的基础理论和实施技术【l , 2 1 。 1 2 1 相关算法的研究 目前国际上流行的基于密钥的加密算法通常有两大类，即对称算法和公开 密钥算法。 对称算法( s y m m e t r i ca l g o r i t h m ) 又叫传统密码算法，就是加密密钥能够从解 密密钥中推算出来，反过来也成立。在大多数对称算法中，加解密密钥是相同 的，这些算法也叫秘密密钥算法或单钥算法。对称算法中最通用的是d e s 加密 算法。而公开密钥算法( p u b l i c k e ya l g o r i t h m 也叫非对称算法) 用作加密的密钥 不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来( 至少在合 理假定的长时间内) ，之所以叫做公开密钥算法，是因为加密密钥能够公开，即 陌生人能用加密密钥加密信息，但只有用相应的解密密钥才能解密信息。在这 些系统中，加密密钥叫做公开密钥( p u b l i c - - k e y ，简称公钥) ，解密密钥叫做私 人密钥( p r i v a t e - - k e y ，简称私钥) ，公开密钥算法中最流行的是r s a 算法。 在对称密钥体系算法方面，继最常用d e s 算法之后，针对d e s 密钥长度 过短的弱点，有所谓3 d e s 算法或d e s x 算法，分别将密钥长度加长到1 6 8 位 和1 8 4 位，在1 9 9 7 年，美国国家标准局( n i s t ) 征集d e s 之后的下一代密码 标准，即a e s ( a d v a n c ee n c r y p t i o ns t a n d a r d ) ，它有一点与d e s 不同，即密钥 长度是可变的到1 9 9 9 年，共有5 个算法入选，分别是m a r s ( i b m 公司) ， r c 6 ( r s a 公司) ，m j n d a c l ( 比利时) ，s e r p e n t ( 英国，以色列，挪威) ，t w o f i s h ( 美 2 江苏大学硕士研究生学位论文 国) ，美国在2 0 0 0 年选出r i j i i l d a c l 作为d e s 的下一代算法。 在非对称密钥体系算法方面，目前呈百花齐放的局面，公开密钥都是基于 某些数学上的难解问题，比较著名的算法有r s a 算法和e l g a m a l 算法，目 前最新的进展是椭圆曲线密码算法，其中r s a 算法主要是利用有两个大质数之 积的模运算来实现，其基础是欧拉定理，其加密强度依赖于对大数因式分解的 难度，而e l g a m a l 则是利用解离散对数的问题，目前所有非对称密钥算法的普 遍缺点就是其加密解密速度远较对称密钥算法为慢，所以目前一般不用它单独 对大批量数据进行加密解密，而是与对称密钥加密方法配合使用。 除了核心的加密解密算法之外，在一个网络信息加密系统中，还需要对数 据进行数字签名以保证身份的认证，而在此之前，需要使用单向散列函数生成 对应与原始数据的唯一散列值。同时在对数据使用s s l 安全通道进行传输时， 需要对此次对话生成唯一的一个m a c ( 信息鉴别码) ，其关系是：对称密钥和 非对称密钥算法共同构成数据加密部分；单向散列函数和数字签名共同构成数 字签名算法部分；而信息鉴别码是使用对称密钥密码体制对单向散列函数输出 值进行加密的结果，用于建立s s l 安全协议的连接。 1 2 2 相关的硬件产品 实现一种加密方案可通过软件或硬件两种途径，软件产品具有价格便宜，不 占用物理空间，易于安装和使用等特点，现今广泛使用的加密算法标准d e s 算 法，是单钥密码体制中一种最有代表性的分组加密体制，例如曾在m o t o r o l a 的m c 6 8 h c 0 5 8 1 6 上实现了d e s 算法，程序和相关表项共需约2 1 0 3 运行速度 可达到1 0 k b i t s ，硬件产品相对具有快速，安全性高，不易损坏，并会随着v l s i 技术的发展而更加小型化的特点，当今主要硬件产品有m o t o r o l a 公司的 m c 6 8 5 9 ，采用6 8 0 0 接口，时钟频率2 m h z ，速度可达4 0 0 k b i t s ：a m d 公司的 f a m z s 0 8 6 ，采用n 沟道硅门技术，速度可达1 7 m b i t s ：美国的w d 2 0 0 1 e f ， w d 2 0 0 2 a b 。w d 2 0 0 3 ，都以n 沟道硅门实现，加密速度为1 6 7 k b i t s 。d e s 芯 片设计的主要问题是极小化基本面积，极大化数据速度，降低成本，其一个令人 担忧的问题是：传输密钥时易于被截获，从而对安全性构成威胁。 r s a 因为本身算法的复杂性原因。最主要的缺点是加解密速度慢，现在也 存在实现r s a 算法的专用硬件产品，如m i t 研制的一种n m o s 芯片适应与 江苏大学硕士研究生学位论文 5 1 2 b i t 模数，加密速度高于1 2 0 0 b i t s ，美国s y l i n k 公司的商用芯片c y l 0 2 4 适用于1 0 2 8 b i t 模数，加密速度高于2 k b i t s ，n e c 设计的一种r s a 芯片，采用 5 1 2 b i t 模数，加密速度可达5 0 k b i t s ，西德的h o l g c rs e d l a c k 设计的r s a 专用芯 片，采用6 6 0 b i t 模数，加解密速度可达6 4 k b i t s 。 1 2 3 相关协议的研究 一个协议指的是两个或者两个以上的参与者为了完成某项特定的任务而采 取的一系列步骤，协议的参与者可能是诚实的主体，也可能是攻击者，参与协 议的各方可能为了互相确认身份，协商会话密钥，或者同时签署合同，在协议 中使用密码的目的是防止或发现偷听者或欺骗。在网络通信中密码协议按功能 可以分为三类： ( 1 ) 密钥交换协议：在参与协议的实体之间建立共享的秘密，通常是建立 在一次通信中所使用的会话密钥，协议可以采用对称密钥密码体制，也可以采用 公开密钥密码体制。 ( 2 ) 认证协议：在安全的分布式系统中，用户需要向通信的对方证实自己 的身份，同时也需要建立秘密的会话秘钥，认证协议是使用户达到认证及交换会 话秘钥的密码方案，目前如m i t 的k e r b e r o s 协议和p g p 协议，但是认证协议的 设计是容易出现错误而又难以发现的。因此，研究如何发现认证协议的漏洞及如 何设计安全的认证协议是密码学中非常重要的研究领域。到目前为止，已有许多 方法用于验证认证协议的安全性，其中，最著名的形式方法是由b u r o w s ，a b a d i ， n e e d h a m 提出的b a n 一逻辑。但这种逻辑具有许多局限性，其主要原因是没有 精确的语义定义和形式的协议理想化方法。 ( 3 ) 认证和密钥交换协议：这类协议将认证和密钥交换协议结合在一起， 是网络通信中最普通应用的安全协议，常见的有n e e d h a m - s c h r o e d e r 协议， k e r b e r o s 认证协议，s s l 协议等。s s l 作为种基本的安全协议，主要用于保障 收、发两端的信息不被窃听，同时又对客户端和服务器端进行认证的功能，主要 用于网络个人敏感信息的传输，在实际应用中，由于s s l 易于实现，扩展性好， 所以为广大用户所接受。 1 3 本文的主要研究内容 本文在已有的技术背景，算法描述及数学理论基础上，介绍了保证信息安全 4 江苏大学硕士研究生学位论文 的加解密算法，并基于刘氏加密算法提出了一种改进方案，分析了密码系统的安 全性及其在信息传输过程中的认证技术，安全协议等问题，最后利用形式化工具 对密码协议进行了分析。 第一章为绪论，介绍了信息系统的安全需求以及当前国内外研究现状，包括 相关的算法，协议和硬件产品的研究 第二章介绍了密码学基础以及相关的算法，主要讨论了两种典型的加密技术 d e s 和r s a 算法，分析了它们各自的特点及实用条件。 第三章首先介绍了文氏加密算法，并针对该算法存在的缺陷，提出了种改 进的方案，在了解其算法设计和实现安全文件系统的各功能模块的基础上，利用 软件实现了其加密解密过程。 第四章主要讨论了密码系统的安全性，包括密码算法以及密码协议的安全 性，分析了密码算法的潜在攻击者的条件攻击和技术攻击，以及对密码协议自身 的攻击的策略，在此基础上介绍了密钥交换协议及其以n e e d h a m - s c h r o e d e r 为代 表的认证协议。 第五章系统介绍了安全协议的一些重要特征并通过p e t r i 网这种并发、异步 系统建模和分析的重要工具，分析了协议的安全性，揭示了形式化工具对验证协 议正确性以及发现协议缺陷所起的重要作用。 文章最后对本文的内容做一总结，分析本文工作中的不足，并指出下一步工 作的努力方向。 5 江苏大学硕士研究生学位论文 第二章基本理论及相关算法分析 2 1 密码学的基本概念 密码学( ( c r y p t o l o g y ) 是研究密码系统或通信安全的- - ( - 科学。它主要包括两 个分支：即密码编码学( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y t i c s ) 。密码编码学 的主要目的寻求保证消息保密性或认证性的方法；密码分析学的主要目的是研究 加密消息的破译或消息的伪造。密码编码学主要致力于信息、加密、信息认证、 数字签名和密钥管理方面的研究。信息加密的且的在于将可读信息转变为无法识 别的内容，使得截获这些信息的人无法阅读；信息的接收方能够验证接收到的信 息是否被敌方篡改或替换过，数字签名的作用就是使信息的接收人能够确定接收 到的信息是否确实是由所希望的发信方发出的密钥管理是信息加密中最难的部 分，因为信息加密的安全性在于密钥。密码分析学则致力于研究分析破译密码的 方法，两者相互对立，而又相互促进。事实证明，密码技术是一种保护信息安全 的有效而且可行的方法，它能以较小的打搅提供比较高的安全保护。密码处理过 程是有形形色色的密码算法来具体实现的，据不完全统计，到目前为止，已经公 开发表的各种密码算法多达数百种。 采用密码技术可以隐蔽和保护需要保密的消息，使未授权者不能提取信息 被隐蔽的消息称作明文( p l a i n t e x t ) ，隐蔽后的消息称作密文( c i p h e r t e x t ) 或密报 ( c r y p t o g r a m ) 。明文变换成密文的过程称作加密( e n c t y p t i o n ) ，其逆过程，即由密 文恢复出原明文的过程称作解密( d e c r y p t i o n ) ，非法接收者试图从密文分析出明文 的过程称作破译。对明文进行加密操作的人员称作加密员或密码员 ( c r y p t o g r a p h e r ) 密码算法( c i p h e ra l g o r i t h m ) 是用于加密和解密的数学函数( 通常情况下， 有两个相关的函数：个用作加密，另一个用作解密) 。加密明文消息时，对明 文应用加密算法形成密文，解密密文消息时，对密文应用解密算法恢复出明文。 为了保证信息的安全，信息的加密、解密算法应经常更换，但实际上，真正能够 抵抗攻击的过硬的算法是难以在短期内设计出来的，因此无法满足经常更换算法 的需要，现代密码学用密码解决了这个问题。常规密码信息系统如图2 1 所示。 密钥( k e y ) 用于控制加密和解密过程，它由数字、字符或特殊控制字符组 成，密钥取值范围称为密钥空间。 6 江苏大学硕士研究生学位论文 明文消息空间m ；密文消息空间c ； 密钥空间k l 和k 2 ：加密变换e k i ：m 斗c ； 解密变换d i n ：c m 称总体( 肘，c ，k ，k ：，e 。，e 。：) 为密码系统，对于明文消息m ，密钥k l ，加密变 换将明文m 变换成密文c ：c - - f ( m , k l ，产e x 。( 加) ，合法接收者利用其知道的解密 密钥k 2 对收到的密文进行解密变换，恢复出明文消息m = d f 2 ，攻击者则利 用他选定的变换函数h ，对截获的密文c 迸行交换，得到的明文是明文空间的某 个元素m = h ( c ) ，如果m k 锄，则攻击者破译成功。 捂线信道描线信道 图2 1 常规密码信息系统 f 培2 1i n f o r m a t i o ns y s m no f r o u t l n ek 锣 2 2 传统加密法 1 置换加密：作为一种最基本的数学变换，置换只不过是一个简单的换位， 每个置换都可以用一个整数序列来表示，如p = ( 2 ，1 ，4 ，3 ) 就表示这样一个 置换：将位置1 与位置2 对调，同时将位置3 与位置4 对调，其逆置换为q ( 2 ， l ，4 ，3 ) 用于解密。 2 代换加密：在代换加密中，密文和明文不再是直接的置换关系， 如明文abcdefgh 密文zxywvuts 这种代换加密中，明文的所有字母都用同一固定的明文字母表看到密文字母表的 映射，即令明文m = m o m i - ，则相应的密文为c = e o c l = f ( m o ) f ( m 0 q 7 2 3 公钥r s a 算法及其理论基础 2 3 1 数论基础 求模的运算在信息加密中有非常广泛的应用，如每一本书都有一个代码i s b n ( 世界标准书号代码) 是一个十位数，可以用来清楚地标识每一本新近出版的书， 例i s b n 号码为34 9 80 3 4 9 52 由四组数组成： 第一组表示该书出版的国家 第二组表示出版社的代号 第三组表示出版社内部统计数 第职组表示检验数字 如果i s b n 代码正确，则第一个数乘以1 0 ，第二个数乘以9 ，第三个数乘以 8 ，第九个数乘以2 ，第十个数乘以l ，全部加起来，最终的结果必须被1 1 整除，如果不是这种情况，肯定发生错误。 用余数的相加和相乘代替这些数字的相加和相乘优点在于，能使我们进行计 算时所用的数字不至于太大，简化结果。 定理2 1 若( a ，n ) = l m o d n ，则存在唯一整数b ，0 ； ( 6 ) 将发送的明文信息m 数字化，分块( 其值的范围在0 至r 1 之间) 自 乘e 次幂后按r 取模进行加密运算，从而产生密文( 其值的范围也是0 至r - l 之 间) 即加密过程是： c 铷c ( m o d ( i ) ) ( 7 ) 将密文( 其值的范围也是0 至r - 1 之间) 自乘d 次幂后按r 取模进行解 密运算，从而将密文恢复为原来的明文( 其值的范围也是0 至r - l 之间) ，即解 密过程是： m = c d ( m o d ( r ) ) 其中e 满足e 与4 ( 0 互索，d 满足_ e , d - - - - 1 ( m o d q b ( r ) ) 的条件，一m ( m o d ( r ) ) ， 即明文n l 自乘e * d 次对r 取模，仍是明文本身。r s a 算法加密的信息分成一连 串的数据块，每个数据块的值不超出f - l ，否则就不可能得到唯一的明文表达式。 2 4 希尔( h i l l ) 加密算法 希尔加密算法的基本思想是：将l 个明文字母通过线性变换将它们转化为l 个密文字母，解密时只要做一次逆交换就可以了，密钥就是变换矩阵本身，即加 9 江苏大学硕士研究生擘位论文 c i2 k i l ? t l i + 局2 m 2 + + k 1 l m l c 2 = k 2 1 m l + k 2 2 m 2 + + k 2 l m l c l2 k l i m l + k l 2 m 2 + + k l l m l c = c l g ： c l ，m = 埘l m 2 ： r d l 解密时：d i k ( c 户k c m o d n = k k m m o d n = m ，其中k k r o o d n = ，为单 位矩阵。 2 5d e s ( 数据加密标准算法) 它是近2 0 年来全世界通用的标准算法，该体制是在m m 公司的建议下，先 后由h f e i s t e l ，w t u c h m a n 等博士领导并组织研究确定的【o j 。 该算法对于推动密码理论的发展和应用起了重大作用，对于掌握分组密码的 基本理论、设计思想和实际应用有着重要的参考价值，d e s 体制运算是在6 4 比 特的数据与5 6 比特的密钥向量上运算，即明文分组长“比特，密钥长为5 6 比 特。首先是初始置换i p ，用于重排明文分组“比特数据，然后是具有相同功能 的1 6 轮变换，每轮中都有置换和代换运算，第1 6 轮的变换输出分为左右两半， 并被交换次序，最后再经过一个逆初始变换i p 1 ，从而产生6 4 比特的密文。其 加密算法的数据流程如图2 2 所示，该算法输入的是6 4 比特的明文。 图2 2d e s 加密算法的教据漉程 f i 9 2 2 柏p l e d m o f d e sa l g e d f l u n 1 0 江苏大学硕士研究生学位论文 d e s 的加密过程可分为加密处理，子密钥生成，加密变换和解密几个过程。 加密变换如图2 3 所示，要进行加密一组数据，先要经过初始置换i p 的处理， 并且要通过一系列的运算，然后经过初始置换口的逆置换i p o 给出加密结果。 基本设计思想：通过循环和迭代，将简单的基本运算( 例如左移，右移， 模2 加法等) 和交换( 选择函数，置换函数) 构造成数据流的非线性变换( 加 密变换或解密变换) 。d e s 算法的数据流程的基本框架是固定的，通过密钥分解 将一个实际上是5 6 位( 二进制) ( 共6 4 位密钥去掉奇偶校验位，刚好是5 6 位) 的密钥分解成1 6 个4 8 位的子密钥，每个子密钥控制一次循环和迭代。加密和 解密的密钥和流程是完全相同的，区别仅仅是加密和解密使用子密钥序列的施 加顺序刚好相反，图2 3 为其具体的加密变换图。 图2 3 d e s 加密变换圈 f i 9 2 3 c l y p “r a r i n go f d e s 每一轮的运算为以下步骤： 1 6 江苏大学硕士研究生学位论文 ( 1 ) 加边运算( 3 2 比特的数据扩充，也就是把3 2 比特的数据向量变为一个 4 8 比特的数据向量) ： ( 2 ) s 盒运算s 【o 】，s 【l 】，s 2 】，s 7 b ( 3 ) p 盒运算( 3 2 比特的换位运算) ； ( 4 ) 左右3 2 比特交换位置。 d e s 综合应用了置换、代替、代数多种密码技术，是一种乘积密码，在算 法结构上采用迭代结构，从而使结构紧凑，条理清楚，而且算法为对称运算，便 于实现。d e s 使用了初始置换m 和逆初始置换i p d 各一次，置换1 6 次，安排使 用这三个置换的目的是把数据彻底打乱重排。它们在密码意义上作用不大，因为 它们与密钥无关，置换关系固定，一旦公开后便无多大密码意义，选择置换一方 面把数据打乱重排，另一方面把3 2 位输入扩展为4 8 位。算法中除了选择函数组 s 是非线性变换外，其余变换均为线性变换，所以保密性的关键是选择函数组s 。 这个非线性变换的本质是数据压缩，它把6 位输入压缩成4 位输出，选择函数的 输入中任意改变数位，其输出至少变化2 位，因为算法中使用了1 6 次迭代，从 而使得即使是改变明文或密钥中的l 位，密文都会发生约3 2 位的变化，大大提 高了保密性。d e s 的子密钥产生与使用上也很有特色，它确保了原密钥中各位 的使用次数基本上相等。实验表明，5 6 位密钥每位的使用次数在1 2 1 5 次之间。 这也使保密性得到了进一步提高，d e s 的设计中，将6 4 位密钥中的5 6 位用于 加密过程，其余8 位用于奇偶校验位，确切地说，密钥分成八个8 位的字节，在 每一个字节中的7 位用于加密算法，第8 位用于奇偶校验。事实上，d e s 加密 体制共有2 ”个密钥可供用户选择，相当于7 6 l o ”，若采用穷举法进行攻击， 即使l 微秒可以穷举一个密钥，也需要2 2 8 3 年的时间。 尽管在上面对d e s 加密过程的叙述略去了许多细节，但仍可体会到它的复 杂程度，d e s 体制足以使破译者在现有的实际情况下不可能用解析法对之求解， 迄今为止，仍具有良好的抗计算机破译能力。但由于d e s 使用的5 6 的密钥长度 较短，乘积变换的迭代次数太少，若用目前的巨型计算机，可在几小时之内搜出 其密钥来。另外它的s 盒可能隐含有陷门( h i d d e nt r a p d o o r s ) 。而且随着计算机 技术的迅速发展，攻击者破译密码的能力也日趋增强，d e s 的加密强度面临着 江苏大学硕士研究生学位论文 攻击者的严重威胁和挑战。这主要表现在以下几个方面1 1 m 3 ； a 关于d e s 算法的函数构造与作用域 从根本上说，d e s 算法的加密强度取决于函数f ( 它是选择函数s 和置换运 算p 的结合) 的复杂度和执行函数f 的次数，是基于迭代或循环的运算模式。 d e s 算法采用6 4 位的固定分组，这种短粗模式不利于有一定长度的明文 块加密，由于可能造成密文信息的重复组块，从而有利于攻击者采用统计方法来 破译。 - d e s 是对采用a s c i i 码的明文或密文进行变换，实际上相应的每一个明 文或密文字符的变化区闻为0 1 2 7 ( 1 0 进制) ，这是一个相当有限的函数作用域。 在d e s 算法设计中由于使用了模2 加法，从而有可能造成丢失进位，损 害信息变换的精度和计算特性，从而造成中间过程的结果不唯一或多种运算模式 取代，例如下面模2 加法运算结果是等价的： 1 0 0 1 0 1 1 0 o 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 l 0 0 0 1 0 1 i o o 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 l 0 1 0 0 0 1 0 1 竺q q q q q q 鳗 0 1 0 0 0 10 1 b 关于d e s 算法中迭代的理论问题 d e s 算法是基于迭代或循环的加密体制，规定加密运算和解密运算都是历 次迭代，因而加密算法或解密算法的系统开销大，这种算法根本上的缺陷，使其 在高速信息变换的应用领域必然受到限制。d e s 由于是基于迭代或循环的变换， 它对变换的初值：输入信息( 明文) 和密钥是有一定要求的，即对应二进制编码 江苏大学硕士研究生学位论文 而言，初值不宜取0 0 0 0 o 0 0 0 ，1 1 1 l 1 1 1 l ，o o o o l l i l 0 0 0 0 1 1 1 1 ，0 1 0 1 0 1 0 1 等具有一定规律的形式，以便防止攻击者采用统计方法来破译密文和对用户使用 的密钥进行搜索。这对使用者是不方便的，在某些数据处理方面，往往会有较多 重复性的数据( 诸如工资数额、产品价格等等) ，加密算法本身不应对数据选择 有所限制和要求。 从理论上分析，任何迭代算法或循环变换都是受初值影响的。 另外，d e s 用密钥控制的迭代是一个简单迭代。而这有可能产生的仍然是 一个简单替代密码。迭代或循环在有限的作用域中存在一个封闭性，即连续多次 进行的迭代变换有可能被一个简单变换所替代。故对于d e s 算法提高迭代变换 次数，不一定能提高加密强度。 c 关于d e s 算法s 盒中的重复因子及密钥的多值问题 至今为止，d e s 算法中的s 盒8 个选择函数矩阵的设计原理不予公布，d e s 算法的密钥的功能实际过于简单，子密钥只起运算参数的作用，其参与的唯一 运算是一次模2 加法，由于s 盒重复因子的作用，大大降低了密钥参与运算结 果的控制性和有效性；在d e s 算法的s 盒设计中利用重复因子，造成s 盒多个 不同的输入而具有相同的输出结果，致使加密或解密变换的密钥具有多值性。 虽然这种设计方法有利于s 盒设计者及其所属部门控制或破译加密信息，但却 造成使用d e s 算法用户的安全性，并显著降低了d e s 的加密强度。 对d e s 算法加密强度的评估，用户实际使用的密钥长度为5 6 位，理论上的 加密强度为2 5 6 ，由于s 盒重复因子的作用，在每次迭代或循环运算过程中， 4 8 位的子密钥只影响3 2 位的输出结果，即每次迭代的加密强度为2 ”，共1 6 次 迭代或循环运算，所以d e s 算法真正有效的加密强度为2 ”。 t 4 江苏大学硕士研究生学位论文 第三章刘氏加密算法的改进与软件实现 3 1 刘氏加密算法描述 刘氏加密算法采用整型数变换与运算机制，用整型数取代字符演算，对字符 采用算术运算取代逻辑运算可以实现无误差的明文至密文或密文至明文的精确 变换。基于整型多项式和代数方程运算的基本性质，当变元和系数唯一确定后， 其解是唯一可确定的，不同的密钥将导致不同的加密和解密变换结果。在确保每 一个可选择的密钥唯一控制加密解密变换的结果和用户可随机选择密钥的基础 上，奠定了刘氏加密算法体制的完全可信度和高度安全性【14 1 。 计算机处理或通信传输的明文和密文序列，都可以看作是一个线性序列，为 了构造这些离散元素之间的相关性，将线性的信息序列按着密钥控制的长度的大 小，分割成若干个块，即把线性序列的信息随机分割成若干块。通过分割，将一 个明文或密文的线性序列分成若干个块( 特殊情况下也可将整个明文或密文线性 序列当成一个块来处理) ，算法的数学描述可具体概括为求逆矩阵与非逆矩阵两 种实现方案。 3 1 1 求逆矩阵的加密方案 ( 1 ) 选择块的大小n 每个明文块都对应一个n 维的明文向量，每个向量都可加密成n 维的密文 向量。因此， 明文x = 石= 而1 rl ? 密文y ：z ： j 初始的明文通常是字符流的形式，可通过预先定义的字符代码表把字符表 达方式转换为数字表达方式。所有x 。和y ，都是以数字表达方式编码的。 ( 2 ) 般来说，x 。，x 2 ，h 没有必要与明文字符流中元素的相同序列对 应，可打乱形成映射前的初始块元素捧列顺序，确定传输数据的排列顺序。对于 长度为m 字节的数据，不同的排列顺序共有m ! 种，若m 很大就会占用很大的存 储空间，这时可以考虑只对整个序列中部分的数据进行排列，比如m - - 2 0 时只对 第0 ，4 ，8 ，1 2 ，1 6 等字节进行排列，这时只有51 = 1 2 0 种，当然重排的序号 、，j m k 吼 江苏大学硕士研究生学位论文 数量可以随安全性能要求的变化而变化。 ( 3 ) 由用户选定的一组映射参数：彳，互，生成第t 块的映射 距a x l + z i 其中t 代表第t 个块或向量，a 一般说来是一个可逆的n n 映 射矩阵： q , a 1 2 q r a = 【绚】= i 啦i 吃2 口2 ， a n i g n 2 ”a w i j = 1 ，2 ，n z ，= ( z 。) ，= 【z i ，z 2 ，z 。n _ b ，r nc 。) z ，是第2 个向量分量，它可根据具体情况呈现不同的形式，它是随块的不同而 变化的一个随机变量。r ( t ，c 。) 是t 的伪随机向量，b ，是一个常数向量，即 b = 【b 。，如，】，c ，是r 的初始值。 ( 4 ) 用户之间秘密的共用一个密钥，把加密信息从一个用户传送到另一个用 户，例如； k = f 央大小；映射参数；随机函数的详细描述；初始块排列； - 【n ，彳，互】 密钥通常分别控制加密和解密，密钥k 可推导出一组加密或解密参数，密钥空 问k 包括了所有可能的密钥，这些密钥是由每个密钥参数在其范围内所有可能 的取值生成的。如 l ) = o ，l ，2 ，l 1 ) a “ l 那么，给定n ，一个秘钥空间中存在的可能密钥由下式给出： k 兰 由方程y 。= a x ，+ z ，生成第t 块的逆映射 酬1 “ 逆映射参数a 1 ，z 是从密钥k 导出的，特别是逆映射矩阵是由对映射矩阵 1 6 江苏大学硕士研究生学位论文 a 求逆得到的，映射或逆映射是用整型变量来实现的。因此所有的映射参数和明 文都是用整型的形式表示并且计算是精确的。密文解密成明文后，用解密时使用 过的同一字符代码把数字表示的明文解码回原来用字符表示的明文。 在所选择的具体情况下，第二向量分量z t 不为零。加入该分量构成每个密 文向量以便迸一步增加安全性，特别是在已知个别明文或在块较小时采用统计方 法易被破译的情况下尤为重要。 对于第t 块，由方程y ，= a x + z ，通过下式给出每个密文向量元素： y i = a i i x i + q 2 x 2 + + a i x + b i r ( t ，q ) y 2 = a 2 l x i + $ 1 2 2 x 2 + + a 2 , v x + 6 2 r q ，c 2 ) y n 2 a n i x l + a n 2 x 2 + + o k nx n + b n r q 。c n 、 密钥参数：k f 【n ，a ，6 f ；q 】 解密公式：五= 爿。( r - z , ) 3 1 2 非逆矩阵加密方案 在非逆矩阵加密方案中，采用一种快速计算方法把密文向量转换成明文，而 无需对映射矩阵求逆。在这种情况下，第二分向量( z 。) 。最好是非线性函数或伪随 机函数。在菲逆矩阵加密中，需要从每个明文向量