基于线性移位寄存器的流密码算法与实现

基于线性移位寄存器的流密码算法与实现 ------------------------------------------------------------------------------------------------ 基于线性移位寄存器的流密码算法与实现 深 圳 大 学 本 科 毕 业 论 文() 题目: 基于线性移位寄存器 的流密码算法与实 现 姓名: 黄乔仕 专业: 通 信工程工程 学院: 信息工程学院 学号: 2009130398 指导教师: 田 传俊 职称: 教授 2013年 04 月 29 日 深圳大学本科毕业论文(设计)诚信声明 毕业论文(设计)作者签名: 日期: 年 月 日 目 录 摘要(关键 词)................................................................................................................ 1 1 引 言................................................................................................................. ........ 1 1.1 概 述............................................................................................................ 1 1.2 密码学发展 史............................................................................................. 2 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 1.3 保密通信系统模 型..................................................................................... 3 1.4 密码体制的分 类......................................................................................... 4 2 流密 码................................................................................................................. ... 6 2.1 2.2 2.3 流密码的基本概 念..................................................................................... 6 线性反馈移 位寄存器................................................................................. 7 几种常 见的非线性序列发生器................................................................. 9 3 流密码算法的设计与分 析................................................................................... 10 3.1 密钥流的设计原理与结 构............................................................................ 10 3.2 设计标 准................................................................................................. 11 3.3 LFSR的结 构 .......................................................................................... 12 3.4 小 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 结......................................................................................................... 12 4 MATLAB平台实现图像加 密 ............................................................................ 13 4.1 MATLAB基本应用及功 能 ................................................................... 13 4.2 加密流程 图............................................................................................. 14 4.3 加密步 骤................................................................................................. 14 5 结 束 语.................................................................................................................... 20 参考文 献...................................................................................................................... 21 致 谢.............................................................................................................................. 22 Abstract(Key words) .................................................................................................... 23 附录 1........................................................................................................................... 24 附录 2...................................................................................................................—————————————————————————————————————— ------------------------------------------------------------------------------------------------ ........ 32 信息工程学院通信工程 黄乔仕 学号:2009130398 【摘要】因特网的飞速发展和普及应用加速了信息社会的节奏和步伐，信息作为一种无形的资源，已经越来越受到人们的重视。为了保护信息的安全性，对所传的信息进行加密是常用的一种技术。本文设计了一种基于线性反馈移位寄存器的流密码算法，给出了一种密钥流序列新的生成，并且将它用于数字图像的加密之中，从而达到了保护信息安全的效果，并且通过Matlab平台实现该算法对数字图像的加密与解密。 【关键词】加密;解密;流密码;线性反馈移位寄存器;数字图像; 1 引言 1.1 概述 因特网的飞速发展和普及应用加速了信息社会的节奏和步伐，信息作为一种无形的资源，已经成为促进经济增长和社会进步的重要力量。 现在，信息系统已经被广泛的应用于政治、军事、经济和科研等诸多领域，并逐渐成为一种很重要的工具和手段。但事物都有两面性，当我们享受信息社会带来的诸多便利和高效的同时，也需防范它所带来的负面影响。 信息网络的社会性、开放性和共享性等特点使其蒙上了不安全因—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 素的阴影。由于信息的存储、传递、处理等过程往往是在开放的通信网络中进行的，使信息容易受到窃听、截取、篡改、伪造、假冒、重放等多种攻击手段的威胁。 如果信息安全问题不解决，信息社会就不能稳步有序地发展，电子商务、电子政务、网络银行等应用都讲无法开展起来。因此，信息安全已经成为信息社会亟需解决的最重要问题 [1]之一 。 为了保护信息的安全性，对所传的信息进行加密并且对加密的信息破解的这个过程，就是密法学的基本过程。用系统的语言概括:研究密码变化的内在客观规律，编制密码以保护信息安全秘密的的过程，称为密码编码技术;应用于破译密码以获取信息的过程，称为密码分析技术，两者总称为密码学。 密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议，以满足对消息进行加密或认证的要求。密码分析技术的主要任务是破译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。 这两个分支既相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身 [2]的发展 。 在密码学里面，信息交换的过程中，通信的双方中的发送方将要发送的信息就是明文， 共 32 页 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 而明文通过加密算法之后变成的看似无意义的随机信息则称为密文，而这种变换的过程就是加密;而收信方将密文用解密算法变换成明文的过程就是解密。加密算法和解密算法的操作 [3]通常都是在一组密钥控制下进行的，分别称为加密密钥和解密密钥。 1.2 密码学发展简史 密码学是保护明文的秘密以防止攻击者获知的科学，是密码编码学和密码分析学的统称。密码编码学是指使消息保密的技术和科学。密码分析学是在不知道密钥的情况下识别出明文的科学。明文是指需要采用密码技术进行保护的消息。密文是指用密码技术处理“明文”后的结果，通常称为加密消息。将明文变换成密文的过程称为加密(encryption)。其逆过程，即由密文恢复出原明文的过程称为解密(decryption)。加密过程所使用的一组操作运算规则称作加密算法。解密时使用的一组运算规则称作解密算法。加密和解密算法的操作通常都是在密钥控制之下进行的，分别称为加密密钥和解密密钥。 密码学的历史极为久远，它的起源可以追溯到4000多年前的古埃及、古巴比伦、古罗马和古希腊。尤其人类社会有了战争，接着有了保密通信的需求，继而有了密码的应用，因 [1] 而用于对信息进行保密的密码技术就产生了 。 例如我国古代的烽火就是一种传递军情的方法，或者一些口号密语都是密码学的一种表现形式。特别是战争的发展，更促进了密码学的发展，交战双方为了保护自己的通信安全和隐秘，又或者为了窃取—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 对方情报而研究各种保密和解密的方法，第二次世界大战期间著名的美国破译日本的情报事件更是体现了那时候密码学的逐渐为人们所完善和重视。 1949年以前的密码技术研究还称不上是一门学科，许多密码系统的设计仅仅凭借着一些直观的技巧和经验。保密通信和密码学的一些最本质的东西并没有被揭示，密码的研究与应用仅仅是一门文学变换技术，因而只能成为密码技术，简称密码术。 1949年香农C.E.Shannon发表了一篇题为《保密系统的通信理论》(Communication Theory Secrecy System)的经典论文，他将信息理论引入到密码学中，为密码学的发展奠定了坚实的理论基础，从而把已有数千年历史的密码技术推向了科学的轨道，形成了科学的密码学学科。因而从严格的意义上讲，此后的密码技术才真正称得上密码学。 但因受到历史的局限，七十年代中期前的密码学研究基本上是秘密进行的，而且主要应用于军事上和政府部门中。密码学真正蓬勃发展和广泛应用是从七十年代中期以后开始的，因为这个时候研究密码学的科学家们提出了公钥的概念。 自从1976年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码体制，如基于大整数因子分解问题的RSA 体制和Rabin体制、基于有限域上的离散对数问题的Diffie-Hellman 公钥体制和ElGamal体制、基于椭圆曲线上的离散对数问题的Diffie-Hellman公钥体制和ElGamal 体制、基于背包问题的Merkle-Hellman体制和Chor-Rivest体制、基于代数编码理论的MeEliece体制、基于有限自动—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 机理论的公钥体制 [2]等等。这时候的密码学犹如雨后春笋般的发展起来，而在20世纪80年代中期到20世纪90年代初，序列密码的研究非常之热门的时期。 在这个时期，序列密码主要用于国家的情报机关、国家政府机关、军方等国家要害部门，由于这些部门的特殊性，所以这些部门所用的秘密学的理论和技术都是保密性非常强的，不 共 32 页 可以公开的。 但是随着Internet网络技术的发展，序列密码还是逐步转变成为一种大众化的民用技术，经过一段时间的高速发展，现在其理论和技术相对而言比较成熟。随着近年来分组密码的流行，序列密码已经不是一个研究热点，不过还是有很多学者热衷于开发更加高效安全的序列密码的。 1.3 保密通信系统模型 保密通信系统可用下图示意图表示: 图1 保密通信系统模型 它是由以下几部分组成的: 明文消息空间M，密文消息空间C，密钥空间K1和K2。在单钥体制下K1?K2?K，此时密钥K需经安全的密钥信道由发送方传给接收方。 加密变换Ek1: M?C，其中k1?K1 ，由加密器完成;解密变换—————————————————————————————————————— ------------------------------------------------------------------------------------------------ Dk2:C?M，其中k2?K2，由解密器实现。称总体(M,C,K1,K2,EK1,DK2) 为保密通信系统。 对于给定明文消息m?M，密钥k1?K11，加密变换将明文m变换为密文c，即 c?f(m,k1)?Ek1(m),m?M,k1?K1。 共 32 页 接收方利用通过安全信道送来的密钥k(k?K，单钥体制下)或用本地密钥发生器产生的解密密钥k2(k2?K2，双钥体制下)控制解密操作D，对收到的密文进行变换得到恢复的明文消息，即: m?Dk2(c),m?M,k2?K2 而密码分析者，则用其选定的变换h，对截获的密文c进行变换，得到的明文是明文空间中的某个元素即m'?h(c)。一般m'?m。如果m'?m，则分析成功。 为了保护信息的保密性，抗击密码分析，保密系统应当满足下述要求: ?系统即使达不到理论上是不可破的，即pr?m'?m??0，也应当为实际上不可破的。就是说，从截获的密文或某些已知的明文密文对，要决定密钥或任意明文在计算上是不可行的。 ?系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。 ?加密和解密算法适用于所有密钥空间中的元素。 ?系统便于实现和使用。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ [8] 1.4 密码体制的分类 密码体制是指实现加密和解密功能的密码，从使用密钥策略上，可分为对称密码体制(Symmetric Key Cryptosystem)和非对称密码体制(Asymmetric Key Cryptosystem，也称公钥密码体制)两类。 1 对称密码体制 在对称密码体制中，使用的密钥必须完全保密，而且要求加密密钥和解密密钥相同，或者由其中的一个可以很容易的推出另一个，所以，对称密码体制又称为私密密钥密码体制(Secret Key Cryptosystem)、单钥密码体制(One Key Cryptosystem)或者传统密码体制(Traditional Cryptosystem，因为传统密码都属于对称密码体制)。 对称密码体制包括分组密码和序列密码，点行的对称算法体制有DES、3DES、AES、IDEA、RC4、A5和SEAL等。对称密码体制就如同显示生活中保密箱的机制，一般来说，保密箱上的锁有多把相同的钥匙。发送方把消息放入保险箱并用锁锁上，然后不仅把保险箱发送给接收方，而且还要把钥匙通过安全通道送给接收方，当接收方收到保密箱后，再用收到的钥匙打开保密箱，从而获得消息。 对称密码体制的优点是: (1)加密和解密的速度都比较快，具有很高的数据吞吐率，不仅软件能实现较高的吞吐率，而且还易于硬件实现，硬件加密/解密的处理速度更快。 共 32 页 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ (2)对称密码体制中使用的密钥相对较短。 (3)密文的长度往往与明文长度相同。 对称密码体制的缺点是: (1)密钥分发需要安全通道。发送方如何安全、高效的把密钥送到接收方是对称密码体制的软肋，对称密钥的分发过程往往很烦琐，需要发出的代价较高(需要“安全通道”)。 (2)密钥量大，难于管理。多人用对称密码算法进行保密通信时，其密钥组合会呈指数级增长，从而使密钥管理变得越来越复杂。 (3)难以解决不可否认问题。因为通信双方拥有同样的密钥，所以接收方可以否认接收到某消息，发送方也可以否认发送过某消息，即对称密码体制很难解决鉴别认证和不可否认性的问题。 2 非对称密码体制 非对称密码体制中使用的密钥有两个，一个是对外公开的公钥，可以像电话号码一样进行注册公布;另一个是必须保密的私钥，只有拥有者才知道。不能从公钥推出私钥，或者说从公钥推出私钥在计算机上困难或者不可能，非对称密码体制又称为双钥密码体制(Double Key Cryptosystem)或者公开密钥密码体制(Public Key Cryptosystem)。典型非对称密钥密码体制有RSA、ECC、Rabin、Elgamal和NTRU等。 非对称密码体制就又像现在大家都熟悉的电子邮件机制，每个人的E-mail是公开的，发信人根据公开的E-mail向指定人发送消息，而只有E-mail的合法用户(知道口令)才可以打开这个E-mail并获得消息。上述中E-mail地址可以看做是公钥，而E-mail的口令可看成私钥。—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 发件人把信件发送给指定的E-mail，只有知道这个E-mail口令的用户才能进入这个信箱。 非对称密码体制主要为了解决对称密码体制的缺陷而提出的:其一是为了解决对称密码体制中密钥分发和管理的问题;其二是为了解决不可否认的问题。基于以上两点可知，公钥密码体制在密钥分配和管理、鉴别认证、不可否认性等方面有重要的意义。 非对称密码体制的优点是: (1)密钥的分发相对容易。在非对称密码体制中，公钥是公开的，而用公钥加密的信息只有对应的私钥才能解开。 (2)密钥管理简单。 (3)可以有效的实现数字签名。 非对称密码体制的缺点是: (1)与对称密码体制相比，非对称密码体制加解密速度较慢。 (2)同等安全强度下非对称密码体制要求的密钥位数要多一些。 (3)密文的长度往往大于明文长度。 [9] 共 32 页 2 流密码 2.1 流密码的基本概念 流密码也称序列密码，其基本思路是利用密钥k产生的是一个密钥流 并且通过如下的规则对明文串z?z0z1z2z3?，x?x0x1x2x3?进行加—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 密，即: y?y0y1y2y3...?Ez0(x0)Ez1(x1)Ez2(x2)Ez3(x3)... z?f(k,?i)，这里是?i加密器中的记忆元件，在其中，密钥流由密钥流发生器f产生: i [3]?时刻i的状态，f是由密钥k和i产生的函数。 虽然目前已有大量的关于流密码的理论知识，也提出了多种流密码的设计原理及其分析，但在公开文献中关于流密码算法详细的设计的内容非常少。相反，种种实用的分组密码算法已经公布，且已经形成。这是因为流密码主要广泛应用于在军事、外交等领域而不便于公开。所以，流密码在实际的应用也颇为广泛。 流密码分为同步流密码和自同步流密码。如果加密器中记忆元件?i与输入的明文序列有关系的话，则称为自同步流密码，反之，记忆元件?i与输入的明文序列没有关系的时候，则称为同步流密码。 由于自同步流密码的密钥流动产生与明文有关，比较难从理论上进行分析，因为目前大多数流密码的研究都是同步流密码，本文所研究的流密码也是常见的同步流密码。如图为常用的加法流密码体制模型: 图2 加法流密码体制模型 共 32 页 其中K是密钥流生成器初始密钥(一般为了计算方便，都要求K较短)。在流密码系统中，加密算法和解密算法同样为ki。 在现实的生活中，密码设计者总是想设计出来一个安全隐秘的滚—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 动密钥流生成器，使得生成的密钥流有极大的周期、良好的统计特性、抗分析等等特性。因此在实际上，我们一般设计的二进制的密钥流一般应该满足如下几个基本条件: (1)必须拥有极大的周期，只有极大化的周期才能让密码分析者无法从中找到规律，从而破译出密钥的周期进而得到完整的密钥，这样系统才能可靠安全。 (2)良好的统计特性。即满足或部分满足Golomb的3个随机性公设: ?在周期T内，0-1序列中0与1的个数相差至多为1; ?在周期T内，0-1序列中长为1的游程数占总游程数的1/2，长为2的游程数占总游 2n程数的1/2，?，长为n的游程数占总游程数的1/2，?，且在等长的游程中0，1游程数 相等; ?异相自相关函数是一个常数。 (3)不能用级数较小的(可实现长度)线性移位寄存器(LFSR)近似代替，即有很高的 [4]线性复杂度; (4)密钥要足够安全则要保持密钥的复杂性，不能只是线性的密钥，密钥如果单单只是线性结构密钥，密码分析者就能够通过统计方法得出密钥的结构，所以必须设计出的密钥 [10]要能够不被统计的方法破译。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ [4] 2.2 线性反馈移位寄存器 同步流密码的关键问题是设计出一个可靠的密钥流产生器, 而目前社会上，应用最多并且最为可靠的密钥流产生器的结构如下图所示，其中的驱动子系统是一个或者多个线性反馈移位寄存器(LFSR)组成的。 图3 密钥流生成器结构图 线性反馈移位寄存器(英文简称表示为LFSR)是流密码产生序列密码密钥流的一个主要组成部分，线性反馈移位寄存器是反馈移位寄存器中最简单的一种，其中由线性反馈移位寄存器产生的序列称为线性反馈移位寄存器序列。反馈移位寄存器是一种硬件设备，由移位 共 32 页 寄存器和反馈函数组成。一个移位寄存器由若干寄存器串联，每个寄存器是一个具有记忆功能的单元，要么存放数字0，要么存放数字1，只有这两种状态。移位寄存器所含寄存器的个数称为它的级数。其原理图如下图所示。 cn … 图4 线性反馈移位寄存器原理图 当给最左边寄存器一个输入时，每个寄存器的值都向右移一位，这时最右边寄存器的值就是这个反馈移位寄存器的输出。记为AI为第I级存储器的内容，(A1,A2,?,AN)为某时刻的状态，反馈函数—————————————————————————————————————— ------------------------------------------------------------------------------------------------ F(A1,A2,?,AN)是一个布尔函数，它的输入是各寄存器的状态值，它的输出则反馈到最左边的寄存器、作为该寄存器下一拍的输入。在外来时钟的控制下，当给每个寄存器一个初始状态后，该反馈移位寄存器就会不断有输出，所输出的序列就称为反馈移位寄 [11]存器序列。 如果反馈移位寄存器的状态表示为维向量: si?(ai,ai?1,?,ai?n?1) 则 ai?n?f(ai,ai?1,?,ai?n?1) (1) ai?n又是移位寄存器下一时刻的输入， ai?n的驱动下，移位寄存器的各个数据向“前”一位，使状态变为: si?1?(ai?1,ai?2,?,ai?n) 同时，整个移位寄存器的输出为的输出为的输出为的输出为ai。由此得到一系列的数据 a1,a2,?an? (2) 它们满足(1)，称无穷序列(2)为一个反馈移位寄存器的输出序列。 定义:当一个N级LFSR序列{AT}的周期是2-1时，称{AT}是一个N级最大周期线性反 共 32 页 N 馈移位寄存器序列，简称M序列。 定理:当一个N级LFSR的特征多项式是一个本原多项式时，该—————————————————————————————————————— ------------------------------------------------------------------------------------------------ LFSR所产生的N级LFSR [6] 序列一定是一个M序列。 2.3 几种常见的非线性序列发生器 1 Pless生成器 为了克服J-K触发器的缺点，PLESS提出了由多个J-K触发器序列驱动的多路复合序列方案，即PLESS生成器。PLESS生成器是由8个LFSR、4个J—K触发器和1个循环计数器构成的。而常用的循环二进制计数器的作用是在某一时刻T输出中T(MOD4)的内容，这样，仅是从每个J-K触发器来的输出序列中的每第4位是有效的。通过只使用每个移位寄存器输出序列第4位的信息的方法，可以克服J-K触发器的弱点，从而提高安全性和隐秘性。 图5 PLESS生成器 2 GEFFE发生器 这个密钥序列发生器使用了三个LFSR，它们以非线性方式组合而成，如下图。 共 32 页 图6 GEFFE发生器 Geffe序列生成器序列生成器最基本得结构是由3个LFSR组成的，其中LFSR2作为控制生成器使用，当LFSR2输出为1的时候，LFSR2和LFSR1连接，当LFSR2输出为0的时候，LFSR2与LFSR3连接。 3 流密码算法的设计与分析 流密码是现代密码学的一大重要分支，它的加密算法就是由明文—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 序列与密钥序列进行异或运算从而得到密文序列，反过来再由密文序列与密钥序列作异或运算便重新得到明文序列。其算法简单，而且具有易实现、无延迟、通信效率高等优点。但是，流密码算法也存在其弊端，当攻击者获得部分明文和对应的密文时，很容易求得其对应的密钥序列，同样当攻击者得到密钥序列和对应的密文时，就可以恢复出相应的明文。正是根据这一特性，由部分明文和对应的密文得到部分密钥序列，再根据这部分密钥序列试图恢复整个密钥序列，从而 [5]达到破译密文的目的。 3.1 密钥流的设计原理与结构 在本文的设计中，将借鉴Geffe生成器的结构设计，采用五个线性移位寄存器和非线性结构的特点，令所设计出的结构足够安全。 下图为密钥流的结构图。其中，初始密钥K1K2K3K4K5由加密者决定，为了系统的安全性，初始密钥采用不同级数，且最好是互素的，这样能给密码分析者的破译带来极大的难度，极大的增加系统的安全性和隐秘性。 共 32 页 图7 密钥流的结构图 ? LFSR1、LFSR2、LFSR3、LFSR4、LFSR5工作，将输出的密钥序列放入x*y维矩阵中，得到c1(i,j),c2(i,j),c3(i,j),c4(i,j),c5(i,j)。 ? LFSR1、LFSR2、LFSR3将构成第一个Geffe序列，将初始密钥k1k2k3输入LFSR1、LFSR2、LFSR3中，通过Geffe生成器产生一个新的密钥序列temp1。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ?将temp1序列放入x*y维矩阵中，得到加密矩阵coord_0。 ? coord_0、LFSR4、LFSR5将构成第二个Geffe序列，将初始密钥k4k5输入LFSR4、LFSR5中，通过Geffe生成器产生一个新的密钥序列temp2。 ?将temp2序列放入x*y维矩阵中得到加密矩阵coord_1。 ?coord_1与c1、c2、c3、c4、c5进行异或得到最终密钥流k。 3.2 设计标准 通过研究密码学的基础知识和流密码的基础原理，为了设计一种实用的流密码，设计的密钥生成器，应该满足下列几个基本要求: ?满足图3的密钥流生成器的结构，即由LFSR和非线性序列构成的密钥生成器，这样才足够的安全和隐秘，不容易被破解; ?结构中所用的LFSR都应当满足本原多项式，即所用的LFSR产生的流密钥都是M序列，这样才能够把周期最大化，形成一种伪随机序列; ?采用的多个LFSR都应该使用不同的级数，这样也能加强密钥的安全和隐秘; ?为了加强密钥的可靠性，在加密过程中将加入明文序列，这样能够混淆密码分析者分 共 32 页 析密码的思维，使得密钥更加难以破解 [11]。 3.3 LFSR的结构 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ?LFSR1采用满足41级本原多项式的线性移位寄存器，其周期T1=2-1。AI为LFSR5的初始密钥，假设LFSR5 的初始密钥序列为41k1?(a1,a2,?,a40,a41)，且LFSR5 满足41级本 413R(x)?x?x?1，则输入初始序列之后LFSR1输出序列K1。 原多项式 ?LFSR2 采用满足18级本原多项式的线性移位寄存器，其周期T2=2-1。ai为LFSR2的初始密钥，假设LFSR2 的初始密钥序列为k2?(a1,a2,?,a17,a18)，且LFSR2 满足18级本原多项式R(x)?x18?x11?1，则输入初始序列之后LFSR2输出序列K2。 ?LFSR3 采用满足35级本原多项式的线性移位寄存器，其周期T3=2-1。ai为LFSR3的初始密钥，假设LFSR3 的初始密钥序列为k3?(a1,a2,?,a34,a35)，且LFSR3 满足35级本原多项式R(x)?x35?x2?1，则输入初始序列之后LFSR3输出序列K3。 ?LFSR4 采用满足17级本原多项式的线性移位寄存器，其周期T4=2-1。ai为LFSR4的初始密钥，假设LFSR4 的初始密钥序列为k4?(a1,a2,?,a16,a17)，且LFSR4 满足17级本原多项式 R(x)?x17173518?x14?1，则输入初始序列之后LFSR4输出序列K4。 7?LFSR5 采用满足7级本原多项式的线性移位寄存器，其周期T5=2-1。ai为LFSR5的 初始密钥，假设LFSR5 的初始密钥序列为k5?(a1,a2,?,a6,a7)，且LFSR5 满足7级本原多项式R(x)?x?x?1，则输入初始序列之后LFSR5输出序列K5。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 76 3.4 小结 本次设计使用了5个LFSR，所以周期为T=T1T2T3T4T5 =(2-1)*(2-1)*(2-1)*(2-1)7*(2-1)，所以周期十分之长，使得想要通过截获一部分密钥序列并且获得周期来破译密码成为一件不可能的事情。并且Geffe序列生成器的应用，通过线性序列以及非线性序列的结合，使得系统的破译变得更加复杂。 但是本设计也有缺点。就是周期的过长使得加密时间长，另外就是系统结构过于复杂，实现难度比较大。 41183517 共 32 页 4 MATLAB平台实现图像加密 4.1 MATLAB基本应用及功能 MATLAB是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言(如C、Fortran)的编辑模式，代表了当今国际科学计算软件的先进水平。 MATLAB和Mathematica、Maple、MathCAD并称为四大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连matlab开发工作界面接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。 MATLAB的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用MATLAB来解算问题要比用C，FORTRAN等语言完成相同的事情简捷得多，并且MATLAB [7]也吸收了像Maple等软件的优点，使MATLAB成为一个强大的数学软件。 共 32 页 4.2 加密流程图 图8 加密流程图 4.3 加密步骤 ?对所有下面加密图像中将要用到的矩阵进行定义，并给定5个LFSR的初始密钥流。 %LFSR1 级数41 共 32 页 array1= [51,49,196,63,12,34,153,158,20,105,89,89,12,47,15,35,15,156,123,123,7 8,96,125,78,123,15,13,23,34,133,26,48,42,16,13,28,38,69,66,123,215]; %LFSR2 级数18 array2 = —————————————————————————————————————— ------------------------------------------------------------------------------------------------ [105,89,89,12,47,15,35,15,156,123,123,78,96,123,121,154,21,19]; %LFS R3 级数35 array3= [142,152,18,125,22,85,71,11,73,12,63,12,86,152,31,82,56,96,13,68,12,5 8,62,23,48,32,156,45,15,156,52,72,8,6,132]; %LFSR4 级数17 array4 = [47,15,35,112,63,12,158,152,31,156,45,15,156,15,35,15,156]; %LFSR5 级数7 array5 = [34,153,158,20,35,15,26]; N = 256*256 lfsr1 = zeros(1,N); lfsr2 = zeros(1,N); lfsr3 = zeros(1,N); lfsr4 = zeros(1,N); lfsr5 = zeros(1,N); coord_0 = zeros(1,N); temp = zeros(1,N); ?读取所要加密的图像teddy的灰度矩阵并且显示出原始图像: %%读图%% z=imread('D:\MATLAB7\teddy.jpg'); —————————————————————————————————————— ------------------------------------------------------------------------------------------------ subplot(1,3,1),imshow(z); title('teddy原始图像'); 共 32 页 图9 teddy原始图像 ?由于LFSR1、LFSR2和LFSR3最先开始工作，故将这3个LFSR 的初始array矩阵分别进入各自的LFSR中，进行线性移位处理，下面 举其中的LFSR1为例: %LFSR1 级数41 array1 = [51,49,196,63,12,34,153,158,20,105,89,89,12,47,15,35,15,156,123,123,78,96,125,78,123,15,13,23,34,133,26,48,42,16,13,28,38,69,66,123,215]; %LFSR2 级数18 array2 = [105,89,89,12,47,15,35,15,156,123,123,78,96,123,121,154,21,19]; %LFSR3 级数35 array3 = [142,152,18,125,22,85,71,11,73,12,63,12,86,152,31,82,56,96,13,68,12,58,62,23,48,32,156,45,15,156,52,72,8,6,132]; %LFSR4 级数17 array4 = —————————————————————————————————————— ------------------------------------------------------------------------------------------------ [47,15,35,112,63,12,158,152,31,156,45,15,156,15,35,15,156]; %LFSR5 级数7 array5 = [34,153,158,20,35,15,26]; N = 256*256 共 32 页 lfsr1 = zeros(1,N); lfsr2 = zeros(1,N); lfsr3 = zeros(1,N); lfsr4 = zeros(1,N); lfsr5 = zeros(1,N); temp1 = zeros(1,N); temp2 = zeros(1,N); %%%%%%% LFSR1工作 %%%%%%% for i = 1 : N lfsr1(i) = array1(1); a = bitxor(array1(3),array1(41)); for m = 1 : 40 array1(m) = array1(m+1); end if a<=255 array1(41) = a; else —————————————————————————————————————— ------------------------------------------------------------------------------------------------ array1(41) = mod(a,255); end end %将LFSR1输出密钥序列放入x*y维矩阵中 c1 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 c1(i,j) = lfsr1((i-1)*256+j); end end ?由LFSR1、LFSR2和LFSR3组成geffe序列生成器，把结果放入coord_0(1，256*256) 共 32 页 矩阵的矩阵中，过程如下:(由coord_0、 LFSR4和LFSR5组成geffe序列生成器，把结果放入coord_1(1，256*256)矩阵的矩阵中，过程与第四步类似，故代码将在附录中展示。) %%%lfsr1，lfsr2，lfsr3组成的Geffe生成器的输出 for i = 1 : N temp1(i) = 0; if mod(lfsr2(i),2) == 0; d1= bitxor(array1(3),array1(41)); d2= bitxor(array2(11),array2(18)); —————————————————————————————————————— ------------------------------------------------------------------------------------------------ d=bitxor(d1,d2) else d2= bitxor(array2(11),array2(18)); d3= bitxor(array3(2),array3(35)); d = bitxor(d2,d3) end if d<=255 temp1(i) = d; temp1(i) = temp1(i) + 1; end end %%%%% 将geffe序列生成器得出的序列放进x*y维矩阵中 coord_0 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 coord_0(i,j) = temp1((i-1)*256+j) end end ? 将lfsr1，lfsr2，lfsr3，lfsr4，lfsr5以及coord_1异或得到最终密钥流，并对图像进行加密。其过程如下: %%%%% 最终密钥密钥key 共 32 页 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ key = zeros(256,256); for i = 1 :256 for j = 1 : 256 key(i,j) = bitxor(bitxor(bitxor(bitxor(bitxor(c1(i,j),c2(i,j)),c3(i,j)),c4(i,j)),c5(i,j)),coord _1(i,j)); end end %%%%%%%% 初始化加解密图像矩阵 encfig = z; %%%%%% 加密处理过程 %%%%%%% for i = 1 : 256 for j = 1 : 256 encfig(i,j) = bitxor(key(i,j),z(i,j)); end end subplot(1,3,2),imshow(encfig); title('teddy加密 '); 图10 teddy加密 共 32 页 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ?解密过程是加密的逆过程，因此可以通过key密钥逆运算从加密图像中恢复得到原始图像。如下: %%%%%%%% 初始化加解密图像矩阵 decfig = z; %%%%%% 解密处理过程 %%%%%%% for i = 1 : 256 for j = 1 : 256 decfig(i,j) = bitxor(encfig(i,j),key(i,j)); end end subplot(1,3,3),imshow(decfig); title('teddy解密 '); 图11 teddy解密图像 5. 结束语 本文介绍了密码学中的流密码的原理及结构，并且通过流密码的原理设计出了一个密钥流设计，并且借鉴了GEFFE生成器，通过LSFR与GEFFE序列结构设计出了一个密钥流，并且通过MATLAB使用这个密钥流实现了对数字图像的仿真加密。 共 32 页 【参考文献】 [1]杨义先等.现代密码学教程[M].北京:北京邮电大学出版社。—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 2009, [2]冯登国.国内外密码学研究现状及发展趋势[J].通信学报，2002,5:18-26, [3]杨波. 现代密码学(第2版)[M].北京:清华大学出版社, 2007, [4] 胡向东,魏琴芳. 应用密码学[M]. 北京:电子工业出版社,2006, [5]赵立杰.《基于线性反馈移位寄存器的流密码的研究及设计》[M].西南交通大学硕士研究生学位论文.2003, [8] 杨晓元 现代密码学[M]. 西安:西安电子科技大学出版社 2009, [9] (美)Richard Spillman 著.叶阮健,曹英,张长富 译. 经典密码学与现代密码学[M].北京:清华大学出版社,2005, [10] 郑阿奇,曹弋,赵阳. MATLAB实验教程[M]. 北京:电子工业出版社,2007, [11] (美)WILLIAM STALLINGS 著.杨明 译. 密码编码学与网络安全:原理与实践(第二版)[M].北京:电子工业出版社,2001, 共 32 页 致谢 本次的论文之所以能够顺利完成，离不开指导老师田传俊的悉心教导以及无微不至的关怀。田传俊老师严谨的科学态度以及严谨的治学精神还有精益求精的工作作风，都是我非常需要学习的。田传俊老师不仅在学习上给予我指导，还在生活上给予我关心，有了田传俊老—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 师的帮助我才能顺利完成本次论文的写作。感谢田传俊给我这个学习 的机会。谢谢～ 在此次论文完成之际，还要特别感谢大学期间的各科授课老师， 感谢他们在学业上对我的教导和各个方面的帮助，使我学到各种知识。 感谢各位帮助过我的同学们与女朋友，感谢他们给予我的支持和浓厚 的学习氛围。感谢深圳大学，特别感谢信息工程学院为我提供良好的 学习环境，谢谢～ 最后要感谢父母含辛茹苦的养育之恩，正是你们无私的关爱以及 支持，才能让我更有信心、更有动力、更有能力去完成学业。在以后 的人生道路上，我将脚踏实地，努力拼搏，回报父母。最后，谨借此 机会向所有关心。支持和帮助过我的老师和同学们致以最诚挚的谢意～ 共 32 页 A stream cipher based on linear feedback shift register and it's application on Matlab platform 【Abstract】With the development and widespread used of Internet, the information society is also developing rapidly. As a kind of resource witch can't be seen, people are paying more and more attention to information. In order to protect, encrypting information is a commonly used technology, this paper designed a stream cipher witch based on linear feedback shift register, then used for encryption digital images to achieve the protection of information security role. At last，I have carry it out to encrypt and decrypt digital image information through the Matlab —————————————————————————————————————— ------------------------------------------------------------------------------------------------ platform. 【Key words】encryption; decryption; stream cipher; linear feedback shift register; digital image; 指导老师:田传俊教授 共 32 页 附录1 MATLAB程序代码 %%读图%% z=imread('D:\MATLAB7\teddy.jpg'); subplot(1,3,1),imshow(z); title('teddy原始图像'); %LFSR1 级数41 array1 = [51,49,196,63,12,34,153,158,20,105,89,89,12,47,15,35,15,156,123,123,78,96,125,78,123,15,13,23,34,133,26,48,42,16,13,28,38,69,66,123,215]; %LFSR2 级数18 array2 = [105,89,89,12,47,15,35,15,156,123,123,78,96,123,121,154,21,19]; %LFSR3 级数35 array3 = [142,152,18,125,22,85,71,11,73,12,63,12,86,152,31,82,56,96,13,68,12,5—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 8,62,23,48,32,156,45,15,156,52,72,8,6,132]; %LFSR4 级数17 array4 = [47,15,35,112,63,12,158,152,31,156,45,15,156,15,35,15,156]; %LFSR5 级数7 array5 = [34,153,158,20,35,15,26]; N = 256*256 lfsr1 = zeros(1,N); lfsr2 = zeros(1,N); lfsr3 = zeros(1,N); lfsr4 = zeros(1,N); lfsr5 = zeros(1,N); temp1 = zeros(1,N); temp2 = zeros(1,N); 共 32 页 %%%%%%% LFSR1工作 %%%%%%% for i = 1 : N lfsr1(i) = array1(1); a = bitxor(array1(3),array1(41)); for m = 1 : 40 array1(m) = array1(m+1); end —————————————————————————————————————— ------------------------------------------------------------------------------------------------ if a<=255 array1(41) = a; else array1(41) = mod(a,255); end end %将LFSR1输出密钥序列放入x*y维矩阵中 c1 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 c1(i,j) = lfsr1((i-1)*256+j); end end %%%%%%% LFSR2工作 %%%%%%% for i = 1 : N lfsr2(i) = array2(1); a = bitxor(array2(11),array2(18)); for m = 1 : 17 array2(m) = array2(m+1); end if a<=255 共 32 页 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ array2(18) = a; else array2(18) = mod(a,255); end end %将LFSR2输出密钥序列放入x*y维矩阵中 c2 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 c2(i,j) = lfsr2((i-1)*256+j); end end %%%%%%% LFSR3工作 %%%%%%% for i = 1 : N lfsr3(i) = array3(1); a = bitxor(array3(2),array3(35)); for m = 1 : 34 array3(m) = array1(m+1); end if a<=255 array3(35) = a; else —————————————————————————————————————— ------------------------------------------------------------------------------------------------ array3(35) = mod(a,255); end end %将LFSR3输出密钥序列放入x*y维矩阵中 c3 = zeros(256,256); 共 32 页 for i = 1 : 256 for j = 1 : 256 c3(i,j) = lfsr3((i-1)*256+j); end end %%%%%%% LFSR4工作 %%%%%%% for i = 1 : N lfsr4(i) = array4(1); a = bitxor(array4(14),array4(17)); for m = 1 : 16 array4(m) = array4(m+1); end if a<=255 array4(17) = a; else array4(17) = mod(a,255); —————————————————————————————————————— ------------------------------------------------------------------------------------------------ end end %将LFSR4输出密钥序列放入x*y维矩阵中 c4 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 c4(i,j) = lfsr4((i-1)*256+j); end end %%%%%%% LFSR5工作 %%%%%%% for i = 1 : N 共 32 页 lfsr5(i) = array5(1); a = bitxor(array5(6),array5(7)); for m = 1 : 6 array5(m) = array5(m+1); end if a<=255 array5(7) = a; else array5(7) = mod(a,255); end —————————————————————————————————————— ------------------------------------------------------------------------------------------------ end %将LFSR5输出密钥序列放入x*y维矩阵中 c5 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 c5(i,j) = lfsr5((i-1)*256+j); end end %%%lfsr1，lfsr2，lfsr3组成的Geffe生成器的输出 for i = 1 : N temp1(i) = 0; if mod(lfsr2(i),2) == 0; d1= bitxor(array1(3),array1(41)); d2= bitxor(array2(11),array2(18)); d=bitxor(d1,d2) else d2= bitxor(array2(11),array2(18)); d3= bitxor(array3(2),array3(35)); 共 32 页 d = bitxor(d2,d3) end if d<=255 temp1(i) = d; —————————————————————————————————————— ------------------------------------------------------------------------------------------------ temp1(i) = temp1(i) + 1; end end %%%%% 将geffe序列生成器得出的序列放进x*y维矩阵中 coord_0 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 coord_0(i,j) = temp1((i-1)*256+j) end end %%%temp1(i)，lfsr4，lfsr5组成的Geffe生成器的输出 for i = 1 : N temp2(i) = 0; if mod(lfsr4(i),2) == 0; e1= e1= coord_0(i,j); e2= bitxor(array4(14),array4(17)); e=bitxor(e1,e2) else e2= bitxor(array4(14),array4(17)); e3= bitxor(array5(6),array5(7)); e = bitxor(e2,e3) end if e<=255 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ temp2(i) = e; 共 32 页 temp2(i) = temp2(i) + 1; end end %%%%% 将geffe序列生成器得出的序列放进x*y维矩阵中 coord_1 = zeros(256,256); for i = 1 : 256 for j = 1 : 256 coord_1(i,j) = temp2((i-1)*256+j) end end %%%%% 最终密钥密钥key key = zeros(256,256); for i = 1 :256 for j = 1 : 256 key(i,j) = bitxor(bitxor(bitxor(bitxor(bitxor(c1(i,j),c2(i,j)),c3(i,j)),c4(i,j)),c5(i,j)),coord _1(i,j)); end end —————————————————————————————————————— ------------------------------------------------------------------------------------------------ %%%%%%%% 初始化加解密图像矩阵 encfig = z; %%%%%% 加密处理过程 %%%%%%% for i = 1 : 256 for j = 1 : 256 encfig(i,j) = bitxor(key(i,j),z(i,j)); end 共 32 页 end subplot(1,3,2),imshow(encfig); title('teddy加密'); %%%%%%%% 初始化加解密图像矩阵 decfig = z; %%%%%% 解密处理过程 %%%%%%% for i = 1 : 256 for j = 1 : 256 decfig(i,j) = bitxor(encfig(i,j),key(i,j)); end end subplot(1,3,3),imshow(decfig); title('teddy解密'); 共 32 页 附录2 图像演示 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 共 32 页 ——————————————————————————————————————