（通信与信息系统专业论文）frog数据加密算法的改进与应用研究.pdf

山东大学硕士学位论文 符号说明 d e s ( d a t a e n c r y p t i o ns t a n d a r d ) 数据加密标准 o s i ( o p e ns y s t e mi n t e r c o n n e c t i o n ) 开放系统互连 e c b ( e l e c t r o n i cc o d eb o o k ) 电子密码本 c b c ( c i p h e r b l o c k c h a i n i n g ) 密码分组链接 c f b ( c i p h e r f e e d b a c k ) 密码反馈 o f b ( o u t p u t f e e d b a c k ) 输出反馈 r s a ( r i v e s t ，s h a m i ra n da d l e m a n ) 一种公开密钥算法的名称 i t u ( i n t e r n a t i o n a lt e l e c o m m u n i c a t i o nu n i o n ) 国际标准化组织 n i s t ( n a t i o n a l i n s t i t u t eo f s t a n d a r d t e c h n o l o g y ) ( 美国) 国家标准技术研究会 i s o ( i n t e r n a t i o n a lo r g a n i z a t i o nf o rs t a n d a r d i z a t i o n ) 国际标准化组织 d v b ( d i g i t a l v i d e o b r o a d c a s t i n g ) 数字视频广播 d a b ( d i g i t a l a u d i o b r o a d c a s t i n g ) 数字音频广播 d v b c 有线电视传输标准 p s i ( p r o g r a ms p e c i f i ci n f o r m a t i o n ) 节目专用信息 v b i ( v e r t i c a l b l a n k i n g n t e r v a l ) 垂直回扫间隙 q p s k ( q u a d r i p h a s e s h i f tk e y i n g ) 四相移位健控 q a m ( q u a d r a t u r ea m p l i t u d em o d u l a t i o n ) 正交调幅 e c m ( e n t i t l e m e n tc o n t r o lm e s s a g e ) 授权控制信息 e m m ( e n t i t l e m e n tm a n a g e m e n tm e s s a g e ) 授权管理信息 p m t ( p r o g r a mm a pt a b l e ) 节目映射表 c a t ( c o n d i t i o n a la c c e s st a b l e ) 条件接收表 n i t ( n e t w o r ki n f o r m a t i o nt a b i e ) 网络信息表 p a t ( p r o g r a m a s s o c i a t i o nt a b l e ) 节目关联表 p i d ( p a c k e t i d e n t i t y ) 包识别符 b 用密钥七加密：臣。用密钥膏解密 n 初始化向量 山东大学硕士学位论文 引言 随着计算机和通信技术的发展，用户对信息的安全存储、安全处理和 安全传输的需要越来越迫切特别是随着i n t e r n e t 的广泛应用，以及个人 通信、多媒体通信、办公自动化、电子邮件、电子自动转账支付系统和自 动零售业务网的建立与实现，信息的安全保护问题就显得更加重要。数据 加密技术无疑是解决这一问题的最有效手段之一，它也是网络安全中核 心技术。通过数据加密，人们可以有效的保证线路上传输的信息不被窃取 和破坏，还可以检验传输的完整性 “密码学新方向”的发表和美国数据加密标准d e s i 引的颁布实篪，标 志着现代数据加密技术的诞生，从此揭开了商用数据加密技术研究的序 幕。此后使用数据加密体制的研究基本上沿着两个方向进行，即以r s a 为代表的非对称密钥密码体制和以d e s 为代表的对称密钥密码体制【3 。j ， 先后推出了i d e a l 5 - - 6 1 、g o s t l 7 4 1 ，t r i p l ed e s ! 町等m 。2 数据加密算法。 随着计算机网络不断渗透到各个领域，数据加密技术的应用随之扩大，数 字签名、身份鉴别等都是由数据加密技术派生出来的新技术和应用0 3 - j ! 。 1 9 9 7 年a e s 候选方案捌的征集又掀起了数据加密技术研究的新高潮， 可以说是近几年研究成果的一个汇总数据加密是对信息进行重新编码， 从而达到隐藏信息内容，使非法用户无法获得信息真实内容的一种技术手 段。加密技术中主要涉及的要素有：加密算法类型和模式1 2 。瑚、算法描 述和性能、密钥的长度和管理等翠不论是在理论上还是在工程实践中， 有关加密算法方面的研究一直是数据加密中的首要课题现在已有若干种 加密算法，但速度和可靠性之间的矛盾一直是数据加密中的主要问题，应 用时需要进行适当的选择，同时人们也在探索具有多种良好特性的数据加 密技术。 本文对加密技术中主要涉及的要素进行了论述和比较对对称式密码 体制和非对称式密码体销中的典型算法进行了插述，并分别对各种加密算 法的总体实现、速度、安全性能和改进措麓进行了分析比较，在此基础上 讨论了f r o g 算法的改进方案及其软件实现改进后的f r o g 算法在保 持其原有可靠性的基础上，提高了加解密数据的运行速度。 本文在对算法改进的基础上对其在数据广播中的应用进行了探讨。由 j j 山东大学硕士学位论文 于本文中所改进算法具有简单、灵活、密钥长度可变的特点，因此可将其 用于数据广播平台的安全控制中，从而有效的控制网络的访问。 1 密码技术与密码体制 密码学的主要目标是提供保密，数据完整，鉴别，抗抵赖功能。 保密，是指为用户保密信息内容的业务，从物理保护到数学算法都可 以提供保密性，通过对传输信息进行数据加密也可以保证信息的机密性。 数据完整，是指保证数据完整的业务，消息的接收者应该能够验证在 传送过程中消息没有被修改；入侵者也不可能用假消息代替合法消息。 鉴别，是指与认证相联系的业务，它可应用于实体和消息本身，基于 数据加密技术的数字签名技术可满足双方对用户进行认证的安全要求，信 道中传送的信息也要进行数据源，数据内容，发送时间的鉴别等等。 抗抵赖，是指阻止发送者否认事先行为的一种业务。 1 1 主要密码技术 随着计算机网络不断渗透到各个领域，数据加密技术的应用也随之扩 大，数字签名、身份鉴别等都是由数据加密技术派生出来的新技术和应用。 可提供信息安全性的密码技术主要有：数据加密，散列函数，数字签名等， 这些技术的相互联系，共同为网络安全服务。它们之间的关系如图1 1 所 示。 1 2 对称式密码体制与非对称式密码体制 密码体制是密码技术的核心，被定义为一对数据变换，即加密和解密。 对称式密码体制是指加密与解秘密钥相同或等价，而且通信双方必须都要 获得这把密钥，并保持其机密性。当发送方发送信息时，用自己的加密密 钥进行加密，而在接受方收到数据后，用对方所给的密钥进行解密。比较 典型的对称式加密算法有d e s 、a e s 、t d p l ed e s 、g d e s 、n e wd e s 、 l u c i f e r 、b l o w f i s h 、i d e a 、l o d k i9 1 、s k i p j a c k 、r c 4 、r c 5 等。对称 式密码体制具有加密速度快，保密度高等优点。但由于加解密双方要使用 2 山东大学硕士学位论文 图1 1 密码方案分类 鲁 i 相同的密钥，所以在发送接收数据之前，就必须完成密钥的分发。密钥的 卡 分发也成为该加密体系中最薄弱的环节。 非对称式密码体制，即公钥密码体制，要求密钥成对使用，加密和解 密分别用两个密钥来实现。每个用户都有一对选定的密钥，一个可以公开， 即公共密钥，用于加密；另一个由用户安全拥有，即秘密密钥，用于解密， 非法用户根据公开的加密密钥在计算上并不能算出解秘密钥。非对称式密 码体制中的典型算法，包括r s a 、r a b i n 、l u c 、e i g a m a l 、椭圆曲线密 码系统等。非对称密码体制的密钥管理和分配较为简单，尤其是可方便的 实现数字签名和验证，但算法复杂运算量十分浩大，加密和解密数据的 3 山东大学硕士学位论文 速率较低。因此。传送机密信息也可使用某个对称密钥密码体制来加密需 传递的机要信息，而同时使用非对称密钥密码体制来传送密钥，充分发挥 对称密码体制的高速简使性和非对称密码体制密钥管理的方便和安全性， 此方法即保证了数据安全又提高了加密和解密的速度。 1 3 数字签名技术 数字签名技术1 2 4 是封装的一种特殊情况，它是一段附加数据或者是数 据单元的密码变换结果。它主要用于证实消息的真实来源，也是解决个 消息( 例如检验或商业文件) 的发送者和接收者之间争端的基础。由于接 收者最有可能伪造消息，因此，接收者绝不能产生个与发送者产生的数 字签名不可区分的数字签名。 使用对称密码体制进行数字签名时，为了避免接收者伪造签名，必须 引入第三方即可信方。其主要方法是将数字签名过程与由可信方控制的硬 件器件相结合，接收者通过一个防窜扰器件能验证签名的正确性而不能用 同一密钥产生签名。密钥被存储在放窜扰器件内，接收者不能访问它，在 可信方的控制下验证密钥。 公钥密码体制可提供强大的数字签名方案，而无须接收者秘密保存验 证密钥。消息的发送者使用公钥密码体制中的认证模型加密消息，并将加 密结果和明文消息一起发送给接收者。接收者需要知道解密密钥即发送者 的公钥，对附件进行解密并将解密结果与明文消息进行比较，如果二者一 样，接收者确信发送者知道加密密钥，并认为消息未被篡改。为了提高数 字签名方案的有效性，可使用h a s h 函数先对要签名的消息进行压缩，然 后再对压缩后的消息即消息摘要进行签名获得附件，最后将消息和附件一 起发送给接收者。在消息的接收端，接收者重新计算消息摘要，并解密附 件获得发送者计算的消息摘要，然后比较二者，若二者一样，则接收者认 为数字签名是合法的。 1 4 密钥管理 前面所描述的所有密码技术都依赖于密钥的管理，它是保证安全性的 关键点。密钥管理包括密钥必须具备必要的特性，通信双方事先约定密钥 的方法以及密钥的保护等。密钥的管理方法实质上因所使用的密码体制不 - 4 山东大学硕士学位论文 同而有所区另0 。所有密钥都有生存周期，可分为以下几个阶段：密钥的产 生和登记、密钥分配、密钥启用，停用、密钥替换或更新、密钥撤消和密 钥销毁。在产生密要时必须考虑密码系统公认的体制。并确保使用一个合 适的随机过程，有时产生的密钥要与特定的使用捆绑在一起，即所谓的密 钥登记。一般密钥在从产生到终结的整个生存期中都需要保护，否则可能 被非法用户修改或替换，从而丢失数据的机密性。 1 5 硬件加密与软件加密 1 5 1 硬件加密 在硬件加密中，加解密盒子被嵌入到通信线路中，然后对所有通过的 数据进行加密解密。目前，硬件仍是商业和军事加密技术应用的主要选择， 主要原因是它的加密有以下特点： 速度快。由于加密算法含有很多对明文位的复杂运算，不能在一般的。 计算机上进行，因此特殊的硬件一直占据速度优势。 安全性高。硬件加密设备可以安全的封装起来，防窜改盒能防止别人 修改硬件加密设备，从而具有更好的安全性。 易安装。将专用加密硬件放在调制解调器中比增加一个徽处理器或软 件加密系统便宜的多。即使当加密数据来自计算机时，安装一个专用加密 设备也比修改计算机系统软件更容易。 目前，市场上有三类基本的加密硬件：自带加密模块( 可完成银行口 令确认和密钥管理等功能) ，用于通信链路的专用加密盒以及可插入个人 计算机的插卡。 1 5 2 软件加密 善 任何加密算法都可以用软件实现。软件的不利之处是速度慢、开销大、 易于改动，有利之处是灵活性和可移植性高，易使用，易升级，也能和大 型应用如通信或字处理程序相结合。软件加密程序较为大众化，可用于大 多数操作系统。 一5 山东大学硕士学位论文 2 典型加密算法的分析 数据加密技术是安全通信的基石，针对不同的业务要求人们设计了各 种不同的加密算法，它们的加密方式和模式、具体算法、密钥长度、加密 速度和安全性都有较大的差别，不同的用户只有根据自身情况和算法的具 体特性才能找到适合的加密方法。 2 1 数据加密方式分析 理论上，数据加密可以在o s i 通信模型的任何层进行，但事实上，加 密一般在最底层( 第一或第二层) 或较高层实现。从加密技术应用的逻辑 位置看，数据加密主要有：链到链加密( 又称在线加密) 、端到端加密和 节点加密等方式。 2 1 1 链到链加密 链到链的加密方式将网络看作由链路连接的节点集合，每一个链路被 独立的加密。它用于保护通信节点间传输的数据，包括数据、路由信息、 协议信息等。每一个连接相当于o s i 参考模型建立在物理层之上的链路 层。这种方式的加密对用户是透明的，通过链路发送的任何信息在发送前 都先被加密，每个链路只需要一对密钥，可提供信号流安全机制，但数据 在中间节点以明文形式出现，网络中每个链路都必须加密，维护节点安全 性的代价较高。 2 1 2 端到端加密 端到端加密方式建立在o s i 参考模型的网络层和传输层，这种方法要 求传送的数据从源端到目的端一直保持密文状态，任何通信链路的错误不 会影响整体数据的安全性。在端到端加密方式中，只加密数据本身信息， 不加密路径控制信息；在发送主机内和中间节点信息都是加密的，用户必 须找到加密算法，决定施加某种加密手段；加密可以用软件编程实现。但 此方式的密钥管理机制复杂，密码分析者可利用流量分析破译密码，且不 同的通信系统、计算机系统之间的接口定义不完善也增加了该加密方式的 难度。主要适合大型网络系统中在多个发方和收方之间传输的情况。 6 山东大学硕士学位论文 表2 1 对两种加密方式进行了比较。 表2 _ 1 链到链加密与端到端加密的比较 一塑燮童 墅堂垄堕 军鬲丙面丐夏舀j 西磊丽丽萄雨磊夏瑟王丽鬲息夏加密；主机内部 发送主机内部消息报露； 发送主机内部消息被加密； 发送主机使用 发送过程使用 对用户不可见 使用删嚣嚣骗 用户实现加密 用户必须选择算法 用户选择加密 可以硬件完成软件更易完成 将端到端与链到链加密相结合，尽管很昂贵，但是一种有效的网络安 全方法，加密每个物理链路使得对路由信息分析成为不可能，而端到端加 密减少了网络节点中对未加密数据处理带来的威胁。对两种方案的密钥管 理也可以完全分开：网络管理人员可以只关心物理层，而每个用户只负责 相应的端到端加密。 2 1 3 节点加密 。 节点加密虽然能给同络数据提供较高的安全性，但窗在操作方式上与 链到链加密是类似的。在通信链路上为传输的消息提供安全性，在中间节 点先对消息进行解密，然后进行加密。与链到链加密不同的是，它不允许 山东大学硕士学位论文 消息在网络节点以明文形式存在，先把收到的消息进行解密，然后采用另 一个不同的密钥进行加密。节点加密要求报头以明文形式传输，以便中间 节点能得到如何处理消息的信息。因此这种方法对于防止攻击者分析通信 业务是脆弱的。 2 2 算法类型和模式分析 对称密码算法有两种基本类型：分组密码和流密码。分组密码是在明 文数据分组和密文数据分组上进行运算通常分组长为6 4 位，有时更 长“l ；流密码作用在明文和密文数据流的1 位或1 个字节上，有时甚 至是一个3 2 位的字，利用流密码，每次对相同的明文位或字节加密都会 得到不同的密文位或字节。 分组密码对固定长度为 _ b i t ( n 通常为6 4 ) 的数据分组进行加密，对 于超过nb i t s 的报文，最简单的方法是将其分割成n b i t 数据块，依次加密， 即e c b 模式。但这种电子密码本模式在很多应用中存在很大缺陷，因此 更多的分组密码模式应运而生，最常见的模式有e c b ，c b c ，c f b ，o f b 这四种。 2 2 1e c b 模式 一 电子密码本( e l e c t r o n i cc o d eb o o k ，e c b ) 模式中，相同的明文分组 永远被加密成相同密文分组，每个明文分组可被独立的进行加密，不按次 序进行。主要算法是： 输入：k - b i t 密钥尬，z - b i t 明文分组墨，薯。 运算：生成密文分组。l - - ，：解密恢复明文。 加密：f o r 1 j f ，c j 卜e i ( ) 。 解密：f o r 1 - ，r ，0 卜巨一1 ( 勺) 。 2 。2 2 c b c 模式 密码分组链接( c i p h e rb l o c kc h a i n i n g ，c b c ) 模式中，明文在被加密 - 8 - 山东大学硕士学位论文 之前要与前面的密文进行异或运算。主要算法是 输入：k - b i t 密钥k ：，7 b i t i v ；”- b i t 明文分组。i ，一，x t 。 运算：生成密文分组q ，c ，；解密恢复明文。 加密：c o 卜i v f o r1 歹f ，c j 一e i ( c 一l o x j ) 。 解密：c 0 卜v f o r 1 ，x ，卜c 一1 e k 一1 ( c j ) 。 其中为初始化向量，是随机数据分组，它可以以明文形式与密文 一起传送。使用，y 后，完全相同的消息可以被加密成不同的密文信息。蠢 2 2 3c f b 模式 密码反馈( c i p h e r - f e e d b a c k ，c f b ) 模式中，数据可以在比分! l l d , n 多的单元里进行加密。主要算法是： 端) 。 输入：k - b i t 密钥k ：玎- b i t ，k r - b i t 明文分组x l j 一，x 。( 1 ，甩) 。 o 运算：生成，b i t 密文分组。l i ，c 。；解密恢复明文。 加密：i i 。，y ( ，为移位寄存器中的输入值) f o r 1 s j “，接收c j q 卜e k ( 1 j ) ( 计算分组密码输出) t ，卜g 最左端的字节 c i 七- x i o f | + l 七- 2 l j + c r o o d 2 ”( 将巳移进左移位寄存器的最右 9 山东大学硕士学位论文 解密：，卜，矿( ，为移位寄存器中的输入值) f o r l j “： x ，卜c ，o ，( t jo j ，l 的计算方法同加密是相同) 。 2 2 4 0 f b 模式 输出反馈( o u t p u t - f e e d b a c k ，o f b ) 模式是将分组密码作为同步序列 密码运行的一种方法。它与密码反馈模式相似，不同的是将前一个n - b i t 输出分组送入队列最右端的位置，解密是其逆过程。常见的o f b 有两种 版本，i s o 版本需要n - b i t 反馈，也更安全，早期的f i p s 版本使用r 卜z p 。1 ( r 厶) 一， 在d e s 的基础上，又出现了多种变形，如三重d e s ，g d e s 等。随 聋 着计算机的发展，1 9 9 7 年n i s t 又发起征集高级加密标准的活动，目的是 为了确定一个非密级的、全球免费使用的数据加密标准。它的基本要求是 比三重d e s 快而且至少与三重d e s 一样安全，分组长度为1 2 8 b i t s ，密钥 长度为1 2 8 1 9 2 2 5 6 b i t s 。2 0 0 0 年1 0 月2 日n i s t r i j n d a c l 算法作为候选 一l j 山东大学硕士学位论文 算法，它的设计策略是宽轨迹策略，是一个迭代分组密码，其分组长度和 密钥长度都是可变的，但为了满足a e s 的要求，限定了分组长度和密钥 长度，相应的轮数为1 0 1 2 1 4 。 2 3 1 2l d e a 1 9 9 0 年由瑞士联邦技术学院x j 1 a i 和m a s s e y 提出的建议标准算法， 称作p e s ( p r o p o s e de n c r y p t i o ns t a n d a r d ) ，后改称为i d e a 。它的输入和输 出字长为6 4 b i t s ，密钥长为1 2 8 b i t s ，8 轮迭代体制，基本算法为： 1 ) 逐位r o o d 2 和，以。表示； 2 ) r o o d 2 “( 即6 55 3 6 ) 整数加，以田表示； 3 ) m o d 2 ”+ l ( 即6 5 5 3 7 ) 整数乘，以。表示。 4 ) 三个运算中任意两个运算不满足分配律。例如： a 田( 6 0c ) ( 口田6 ) o ( 口田c ) 5 ) 三个运算中任意两个运算间不满足结合律。例如： a 田( 6 0 c ) ( d 田6 ) o c 以上的三种运算之间不具备兼容性，使输入之间实现了较复杂的组合 运算，8 次迭代后经过一个输出交换给出密文。 2 3 1 3g o s t g o s t 为前苏联国家标准局采用的一种标准分组密码算法，现在f i s 中依然使用该标准。算法中消息分组为6 4 b i t s ，密钥长为2 5 6 b i t s ，此外还 用一些附加密钥，采用3 2 轮迭代。明文组分为左半边厶和右半边r ，第 f 轮子密钥以t 表示。 加密函数为：l 1 = r 。 、 置= 厶一lo ，( r 。，七| ) o 表示逐位模之和，而后分成8 个4 1 ，i t s 的段，每段输入不同的s 盒， 各s 盒将输入数字( 以十六进制表示) 进行置换，8 个8 盒的输出重组成 一3 2 b i t s 字，而后循环左移1 1 次之后与上一轮左半边逐位异或作为此轮 输出的右3 2 b i t s ，而左3 2 b i t s 则为上一轮右3 2 b i t s 1 4 一 山东大学硕士学位论文 2 3 1 4b l o w f i s h 该算法是由b s e h n e i e r 设计在大型徽处理器上实现的分组密码算法， 数据分组长为6 4 b i t s ，密钥长度可变，最大为4 4 8 b i t s ，有1 8 个3 2 b i t s 子 密钥和8 个3 2 b i t s 的s 盒m 】。 加密算法：采用1 6 轮迭代，每一轮中含有密钥控制的置换及密钥和 数据控制的代换。运算包括3 2 b i t s 加法和3 2 b i t s 的逐位异或，以及4 个指 数阵列数据查表。输入数据划分成6 4 b i t s 的分组，而后分成o ，心左右两 半各3 2 b i t s 。 f o rf = lt o1 6d o r = l , - j o k l j = 厂( r ) o r j 一。= f ( oo k ) o 砟。 最后输出为，l = r 1 6 0 k l l ，r = r l o k t ，。l 与r 级连即为最后输出 的6 4 b i t s 密文，其中k 是密钥。将置划分成a , b ，c ，d4 个字节，分别送4 个s 盒，每个s 盒是8 b i t s 输入、3 2 b i t s 输出，其输出进行相应运算，组 合出3 2 b i t s 输出，即得加密函数： 八犬) = f + 黾m o d 2 ) ”o 瓯十墨j m o d 2 ” 解密：和加密一致，密钥k 。，k 2 , - - - , k 。以相反次序实旌，总共需要5 2 1 次迭代来生成所有需要的子密钥。 事 2 3 1 5r c 4 巧 r c - 4 是由r s a 安全公司的r i v e s t 在1 9 8 7 年提出的密钥长度可变的 ， 流密码。算法工作于o f b 模式，密钥流与明文独立，利用8 8 个s 盒： 岛，s ，s k 在变长密钥控制下对0 ，2 5 5 的数进行置换，有两个 。 计数器f 和_ ，初始值为0 。通过下述算法产生随机字节： - 1 5 山东大学硕士学位论文 i = ( j + 1 ) m o d 2 5 6 + j = ( _ ，+ s i ) m o d 2 5 6 i n t e r c h a n g e 墨和s j t = ( s | + s i ) r o o d 2 5 6 k = s j 字节k 与明文异或得到密文，或与密文异或得到明文。 r c 一5 是一种分组长( 为2 倍字长wb i t s ) 、密钥长和迭代轮数都可变， 面向字结构的分组迭代密码体制，引入数据相倚旋转( d a t a - d e p e n d e n t r o t a t i o n s ) ，即一个中间的字是另一个中间的低位比特所决定的循环移位 的结果1 2 9 1 。 令字长为w b i t s ，数据分组长则为2 w b i t s ，r 轮迭代，密钥长为 ( 2 r + 2 ) 3 2 b i t s 。按w b i t s 字长划分为明文组被划分成两个w b i t s 字，以 a 和b 表示，a 的第一字节进入寄存器a 中的低位，以此类推，第4 字 节进入最高位。 加密算法： a = 4 + 瓯 b = 曰+ s f o rj = 1 f d ，d o 彳= ( 似。功 功+ 是j b = “口。爿) 彳) + s 2 输出相应存在寄存器a 和b 中，其中为r o o d 2 。加法，o 表示逐位异 或，“工 爿) o a a = ( ( b 一) b ) o b b = b 一墨 a = a 一墨 1 6 其中，“x 砂”表示z 按y 所定次数进行循环右移运算。 2 3 1 6 c a s t - 1 2 8 c a s t 的算法接近于d e s ，数据分组为6 4 b i t s ，密钥长度可变，采用 1 6 轮迭代。明文分成左右两半的和r ，每一轮中完成下述运算： 厶= r p l 置= o 。o ，( r + k 。k 。) 其中，以为掩盖密钥，k ，为循环密钥，经过1 6 轮迭代后输出，将 左右两半交换级连构成输出的6 4 b i t s 密文。在c a s t - 1 2 8 中，轮函数有三 类，第1 ，4 ，7 ，1 0 ，1 3 和1 6 轮使用第一类厂函数：2 ，5 ，8 ，1 1 ，1 4 轮使用第二类，函数，3 ，6 ，9 ，1 2 ，1 5 轮使用第三类，函数。c a s t - 1 2 8 有8 个s 盒，前四个用于轮函数，后四个用作密钥表。 2 3 2 性能比较 各种加密算法的具体实现互不相同，因此其性能也有很大差别，上述 各种加密算法的总体实现、速度、安全性能和改进措施的比较如表2 4 所 示。 根据以上算法的比较，不难看出算法韵差异也会带来适用场合的不 同，如表2 3 所示 表2 3 算法适用场合 1 7 山东大学硕士学位论文 表2 4 性能比较 与密钥长度有关，按目前能实现的最大密钥长度进行评价。 2 4 典型的非对称式密钥加密算法分析 2 4 1 算法描述 2 4 1 1r s a r s a 体制是由r l r i v e s t ，a s h a m i r 和l a d l e m a n s h 设计的用数轮构 造双钥的体制，即可用于加密、也可用于数字签名，标准化组织i s o ，r r u 及s w i f t 等均已接受r s a 体制作为标准【3 1 4 ”。 - 1 8 山东大学硕士学位论文 独立的选取两个大素数，和g ，计算p x q ，其欧拉函数值为 ( n ) = ( p 一1 ) ( g 一1 ) ，随机选一整数p ，l p ( 挖) ，( ( 一) ，e ) = l 。因而在模 ( 胛) 下，p 有逆元d = p m o d e ( n ) ，取公钥为珂，e ，私钥为d 。 加密算法：将明文分组，各组在r a o d 一下可唯一的表示，密文为： y = x r o o d n 解密算法：x = y 。m o d 甩 警 2 4 1 2e l g a r e a l e l g a m a l 是基于离散对数问题的双钥密码体制，即可用于加密，又可 用于签名。若z p 是一个有p 个元素的有限域，p 是一个素数，令g 是z p + 中除去0 元素) 中的一个本原或其生成元，则明文集为勿，密文集为勿 z p * 【。 公钥为：声s 9 8m o d p选定p ( g p 的生成元) ： 私钥为： 口 p 。 加密算法：选择随机数k z p - l ，且( 七，p 1 ) = 1 ，计算得 y l = g m o d p ( 随机数七被加密) y 2 = 邶m o d p ( 明文被随机数k 和公钥卢加密) 式中，i f 是发送明文组，密文由y i 和y 2 级连构成。 解密算法：收到密文后，计算得： m ：y 2 ：攀：望m o d p y lg “g u , 1 。 2 4 1 3r a b i n 0 1 9 7 9 年r a b i n 利用合数模下求解平方根的困难性构造了该公钥体制。 若p 和留是两个素数，在模4 下均与3 同余，则以九= w 为公钥。 加密算法：设肘为待加密信息，则密文为： 一1 9 一 b 山东大学硕士学位论文 c = m 2m o d n0 m 履 解密： m i = c ( ”1 ) “m o d n m 2 = p 。c 2 ( p 。) 7 m o d n m 3 = c m i ) ，m o d n m 4 = q c t 一) “m o d n 其中，必有一个与膨相同。若吖是文字消息则易于识别；若m 是随 机数字流，则无法确定哪一个是正确的消息。 2 4 1 4l u c l u c 是新西兰学者e s m i t h 等提出的公钥密码体制。令n = p q 为两 个奇素数之积，选一个整数e ，使0 ，双) ) = 1 ，并由下式确定出另一整数 d ，e d = 您( ) + l ，七为整数，或等价于e d ；i r o o d s ( ) 。类似于r s a 体制，可以构造l u c 体制如下： 公钥：n ，e ； 私钥：d ( 陷门信息p ，g ) ； 明文：p 小于的某个整数； 密文：c = 屹( p ，i ) m o d n 解密：p = 屹( c 舯m o d n 2 4 1 5d s a d s a 是s c , h n o l - t 和e i g a m a l 签名算法的变种，被美国n i s t 作为 d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) t 3 7 - ”1 。 签名及验证协议如下： ( 1 ) p 产生随机数k , k g ( 2 ) p 计算，= 矿“m o d q ，s = 七h 。8 佃卜硼m o d g 签名结果是( m ， ( 3 ) 验证时计算 - 一 山东大学硕士学位论文 w = j m o d q ，u l = 日( 川) + w m o d q i ，2 = ，w m o d q ，v = ( 幢“+ y “) r o o d d m o d q 若v ：，则认为签名有效。其中，p 是l b i t s 长的素数( 三是6 4 的倍 数) ，范围是5 1 2 到1 0 2 4 ；q 为p 一1 的1 6 0 b i t s 的索因子：，h 满足 h p 一1 ，z 为私钥，工 g ；y = g x r o o d p ，( p ，q ，g ，y ) 为公钥；h ( x ) 为 o n e w a yh a s h 函数。d s s 中选用d s a 算法，p ，q ，g 可由一组用户共享， 但在实际应用中，使用公共模数可能会带来一定的威胁。 i 2 4 2 性能分析 上述各种加密算法的总体实现、速度、安全性能和改进措施的比较如 表2 5 所示。 表2 5 几种算法的性能比较 二2 l 一 山东大学硕士学位论文 3f r o g 算法的分析与改进 3 1f r o g 算法描述 f r o g 算法是由d i a n e l o sg e o r g o u d i s 等提出的一种新型对称式数据加 密算法【3 9 1 4 0 1 ，它的主要设计思想是用尽可能简单的算法，尽可能复杂的 数学模型实现加密，第一个性能提高了该算法的效率，增加了设计透明性， 第二个性能则增强了该算法的可靠性，因为在没有数学模型时攻击者只能 寻找统计意义上的弱点，而f r o g 正是实现了这点。 f r o g 复杂的密钥生成过程是抵御穷举式攻击的有效模型，并可通过 改变数值表中的数值进一步提高可靠性。f r o g 的密钥长度可达1 2 5 b y t e s ， 而2 5 6 b i t s 密钥就可有效抵御穷尽形密钥搜索。f r o g 中大多数内部置换， 包括置换表和引导扩散过程的数值表都依赖于算法内的密钥，而算法内的 密钥本身通过调用f r o g 算法以较为复杂的方式通过对用户密钥递归计 算得到。密钥的实现特性都是相同的，在密钥的选择时不存在任何限制。 f r o g 的结构简单，没有固定的密码表，因此排除了产生门陷的可能。它 的编码主要是实现下面的目标：根据设计需要或扩散处理速度的要求递归 生成密钥。在生成密钥时随机序列生成的是简单的密钥，而它可以根据用 户密钥的需要进行合并，这大大简化了密钥的生成途径。这样做更大的优 点是，简单密钥的初始化不会成为影响密钥可靠性的主要因素，从而可以 通过细微变化编制更多的f r o g 舨本。 f r o g 可对不同长度的分组进行加密，不需要添加数据，从而提高了 加密速度，也使它更容易在许多应用中使用。当它以c f b 模式加密数据 时可用作消息认证码，该算法可以加密6 4 1 0 2 4 b i t s 之间任意长度的明文 数据，f r o g 可很好的实现散列函数，还可作为伪随机序列发生器。f r o g 只需很小的程序即可实现，因此十分适用于8 位处理器( 像智能卡或其他 内嵌式应用) ，如果用软件生成密钥，则可用简单的a s i c 实现加密解密。 因此它是种值得研究和推广的算法。 对于a t m ，h d t v ，b i s d n 等快速通信技术，f r o g 的快速加密解 密有着很大的优势，使得对它的研究更具意义。但它的密钥生成速度过慢 影响了它在一些方面的应用，因此只要将密钥生成速度提高，则f r o g 算法可用于更多的场合，这也是本文所作的主要工作。 传统的对称式加密方法主要是通过混乱和扩散过程隐蔽明文信息， 2 2 山东大学硕士学位论文 f r o g 算法的基本设计思想则是将这一过程在创建内部密钥时实现混乱 用于掩盖明文和密文之问的关系，从而挫败通过研究密文以获取冗余度和 统计模式的企图。扩散通过将明文冗余度分散到密文中使之分敌开来，使 密码分析者更难发现这些冗余度。在实际的加密算法中它将密钥视作个 程序并执行，就象是一串指令，从而尽可能使攻击者无法知道实际操作过 程，达到抵御攻击的目的。 f r o g 算法使用了8 轮循环，每轮循环由1 6 次组成。第q 向= 0 ，7 ) 轮的第，( r = 0 ，1 5 ) 次循环通过下面的三次操作产生1 6 个字节的数据 x ，七_ s q ( 五o k ，) x r + l 一x ，+ l o x ， x 1 ( ，) 卜o 以 其中k 。为予密钥字节序列，s q 为字节大小的替换，x q ( r ) 则表示第 q f 0 ，7 ) 轮的第，( r = 0 ，1 5 ) 次循环，总共加起来，一次加密要进行 1 2 8 次循环，从而将k - b i t ( k = 1 2 9 ，1 9 2 , 2 5 6 ) 主密钥扩展成大量可供选择的 子密钥。一轮密码的加密过程如图3 1 所示， 在生成密码的每一轮中。首先轮输入被作用于一个由子密钥控制的可 一2 3 山东大学硕士学位论文 逆函数s ，然后再被作用于一个置换p 。s 一般被称为混乱层，主要起混 乱的作用。p 为扩散层，主要起扩散的作用。由于按比特置换在软件实现 中是难以实现的，因此，如果混乱层是由m 个s 一盒并置而成，则p 一般 设计成( 霹) “卜( 曰) ”的一个置换，其中( 日) 。= 露霹。 3 1f r o g 算法的改进方案 由上文的分析可见，f r o g 生成密钥的速度主要受到算法内加密速度 的影响，因为在生成密钥时要进行上百次的加密。本文将探讨一种对算法 实现过程本身作适当调整提高密钥生成速度的方法，从而缩短加密解密时 间。 f r o g 算法的密钥生成过程中，为了提高密钥扩展速度，通过本身的 加密技术对空序列，虬简单密钥的加密产生未格式化的用户密钥。对称 式加密算法中加密解密过程互为逆过程，该算法中的加密与解密都进行相 同的操作，不同的地方是加密过程先混乱再扩散，解密过程先扩散再混乱， 混乱层由若干个s 一盒并置而成，扩散层由一个置换来实现，而置换可提 供雪崩效应，因此先混乱后扩散的时间会长于先扩散后混乱的时问，即解 密速度大于加密速度，因此如用解密程序代替加密程序实现上述的加密过 程则会提高密钥的生成速度。本文将结合软件对改进的算法进行详细的说 明。 算法总体设计如图3 2 所示，它主要包括加密密钥生成模块和数据加 密解密 图3 2 算法总体设计 - 2 4 山东大学硕士学位论文 3 3 改进f r o g 算法的实现 3 3 1 加密解密模块 加密解密模块共进行八次迭代，每次迭代都存储一个内部密钥( 即 i m e ，n k e y ) ，这些存储单元都分成三个域：1 6 b y t e s 的序列( 即x o r b u ) ，用 于对数据分组初始的异或操作；2 5 6 b y t e s 的序列( s u b s t p e r m u ) ，作为字节 值的替换表；1 6 b y t e s 的序列( b o m b p e r m u ) ，这里的每个字节对应数据分 组中不同的字节位置。 每次迭代对1 6 个字节的数据分组依次进行四步运算，两次运算用来 实现混乱，两次用来实现扩散。 ( 1 ) 下一字节的数据分组与下一字节的x o r b u 域进行异或。 ( 2 ) 以它作为索引，用置换表( s u b s t p e r m u ) 中的字节替代上步运算中 得到的字节。 ( 3 ) 将下一字节与第二步计算所得字节异或，当到达数据尾部时，将开 头数据作为下一字节。 ( 4 ) 用b o m b p c r m u 序列的下一字节寻找相应位置的数据字节，将其与 第二步中计算所得字节异或。 图3 3 为其中一次运算的示意图。 d a t a b o “出l p 翻删 圣一s u 骘删i | r 紊毒 飞 k 图3 3 运算示意图 具体的加密操作用如下算法实现，其中b l o c k s i z e 表示要加密数据的 - 2 5 一 山东大学硕士学位论文 字节长度。 p r o c e d u r ee n c r y p t ( p l a i n t e x t ，c i p h e r t e x t , i n t e m k e y ) c o n v e r tp l a i n t e x ti n t oc i p h e r t e x t c o p yp l a i n t e x t i n t oc i p h e r t e x t f o re a c ho f t h ee i g h tr e c o r d si ni n t e r n k e yd o f f o re a c hb y t e i n e i p h e r t e x td o 【i 车0 t ob l o c k s i z e - l 】 e i p h e r t e x t i 】 c i p h e r t e x t 田x o rx o r b u i 】 c i p h e r t e x t i = s u b s t p e r m u 【e i p h e r t e x t i 】 i f i b l o e k s i z e l t h e nc i p h e r t e x t + 1 】 = c i p h e r t e x t 1 + 1 】x o rc i p h e r t e x t i e l s ec i p h e r t e x t 0 】 - c i p h e r t e x t 0 】x o r e i p h e r t e x t 田 k = b o m b p e r m u i 】 c i p b e r t e x t 阁 = c i p h e r t e x t i x 】x o rc i p h e r t e x t f i 】 ) e n dp r o c e d u r e 解密过程以与加密运算相反的顺序对内部密钥与密文分组进行运算， 从而恢复明文。除了所有的置换表( s u b s t p e r m u ) 被倒叙外，在解密过程 中使用的密钥与加密时是相同的，实现算法为： p r o c e d u r e d e , c r y p t ( d p h e r t e x t , p l a i n t e x li n t e m k e y ) c o n v e r te i p