密码学课件(古典密码)

第一章古典密码密码学的意义密码学的历史、现状和未来基本术语和定义古典密码和相关基础数学理论如何用精确的数学语言定义和分析古典密码密码学的重要性密码学是信息安全技术的核心和基石，在信息安全领域起着基本的、无可替代的作用。这方面的任何重大进展，都会有可能改变信息安全技术的走向密码技术和理论的发展始终深刻影响着信息安全技术的发展和突破密码学的地位信息安全大厦安全的密码算法安全协议网络安全系统安全应用安全密码学学习密码学的意义密码学相关理论和技术，是进一步学习和运用安全技术的基本功数据保密身份鉴别数字签名数字水印密码学的发展历史起源(4000年以前)有意识地隐藏信息古代密码(1900年以前)纯手工或采用简单机械古典密码(1900-1949)采用复杂机械或机电设备也有学者将1949年以前统称为古典密码传统密码(1950-1975)采用计算机技术安全基于密钥现代密码(1976以后)出现公钥密码密码学的起源密码学(Cryptology)一词来源于两个希腊语单词——隐藏(Kryptos)和书写(Graphen)隐写术(Steganography)：通过隐藏消息的存在来保护消息。常用的手段包括：隐形墨水、字符格式的变化、图形图像(水印)。AB

Apparentlyneutral'sprotestisthoroughlydiscountedandignored.Ismanhardhit.Blockadeissueaffectspretextforembargoonbyproducts,ejectingsuetsandvegetableoils.

:^;@b(]Y(m=4$1m=dQg&_;c?VdSt<C![VKYo]

藏头诗平湖一色万顷秋，湖光渺渺水长流。秋月圆圆世间少，月好四时最宜秋。芦花丛中一扁舟，俊杰俄从此地游，

义士若能知此理，反躬难逃可无忧乐谱古典密码的特点密码学还不是科学，而是艺术出现一些密码算法和加密设备密码算法的基本手段(代替&置换)出现，针对的是字符简单的密码分析手段出现基于字符的密码古典密码象形文字的修改(ModifiedHieroglyphics)：密码学的第一个例子是对标准书写符号的修改，例如古埃及法老坟墓上的文字（3200-1100B.C.），核心思想是代替(Substitution)古典密码400B.C.，希腊人艾奈阿斯《城市防卫论》艾奈阿斯绳结密码不同的绳结距离代表不同的字母妻子给丈夫的保密家书古典密码古典密码205-123B.C.，棋盘密码HELLO

2315313134古典密码50B.C.，恺撒密码明文：thequickbrownfoxjumpsoverthelazydog密文：WKHTXLFNEURZQIRAMXPSVRYHUWKHODCBGRJ曾公亮《武经总要》(北宋)将常用军事情报编为40种1请弓、2请箭、3请刀、4请甲、5请枪旗6请锅幕、7请马、8请衣赐、9请粮料、10请草料11请车牛、12请船、13请攻城守具、14请添兵、15请移营16请进军、17请退军、18请固守、19未见贼、20见贼讫21贼多、22贼少、23贼相敌、24贼添兵、25贼移营26贼进兵、27贼退兵、28贼固守、29围得贼城、30解围城31被贼围、32贼围解、33战不胜、34战大胜、35战大捷36将士投降、37将士叛、38士卒病、39都将病、40战小胜古典密码曾公密码选择一首五言律诗作为密码本国破山河在，城春草木深感时花溅泪，恨别鸟惊心烽火连三月，家书抵万金白头搔更短，浑欲不胜簪——杜甫《春望》加密过程：找到军情对应的字，做标记后放在普通公文中发送解密过程：字验古典密码古典密码500B.C.，斯巴达人在军事上用于加解密发送者把一条羊皮纸螺旋形地缠在一个圆柱形木棒上，核心思想是置换（Permutation）以一种形式写下消息，以另一种形式读取消息

IcameIsawIconquered几何图形密码王先生：来信收到，你的盛情真是难以报答。我已在昨天抵答广州。秋雨连绵，每天需备雨伞一把方能上街，苦矣！大约本月中旬我才能返回，届时再见。弟李明卡尔达诺漏格法16世纪，意大利数学家卡尔达诺发明情报加密古典密码卡尔达诺漏格法古典密码卡尔达诺漏格法古典密码王先生：来信收到，你的盛情真是难以报答。我已在昨天抵答广州。秋雨连绵，每天需备雨伞一把方能上街，苦矣！大约本月中旬我才能返回，届时再见。弟李明Enigma密码机宣告了手工编码技术的结束发明人，亚瑟.谢尔比乌斯(ArthurScherbius)(德国)初步破解人，马里安.雷杰夫斯基(MarianRejewski)(波兰)最终破解人，阿兰.图灵(AlanTuring)(英国)古典密码Enigma密码机基本原理利用不断变化的转子改变字母的代替规则古典密码Enigma密码机基本结构模拟程序古典密码传统密码1949～1975年传统密码计算机使得基于复杂计算的密码成为可能Shannon,TheCommTheoryofSecretSystems,1949DavidKahn,TheCodebreakers,1967J.L.Smith,ACryptographicDeviceforDataComm,1971H.Feistel,CryptographyandComputerPrivacy,1973数据的安全基于密钥而不是算法的保密传统密码加密通信模型HelloHelloHello传统密码加密通信模型HelloHello加密机解密机@#^$&@#^$&@#^$&密钥源安全信道现代密码1976年以后现代密码Diffie,Hellman.NewDirectionsinCryptography,19761977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他非对称算法基于身份标识的密码(IBE)非对称密码使得无密钥传输的保密通信成为可能！对称密钥密码算法进一步发展1977年DES加密算法正式成为标准90年代RC6,MARS,Twofish,Serpent等加密算法出现2001年Rijndael算法成为DES的替代者量子密码(QuantumCryptography)B的公开密钥现代密码非对称密码加密通信模型HelloHello加密机解密机@#^$&@#^$&@#^$&公开密钥库B的私人密钥基本术语和概念问题的描述发送者(Sender)把消息(Message)传递给接收者(Receiver)，他想确保除接收者以外的任何人都不能阅读发送的消息。消息的内容被称为明文(Plaintext)，用某种方法伪装消息以隐藏其内容的过程成为加密(Encrypt)或译成密码(Encipher)被加密的消息成为密文(Ciphertext)，而把密文还原为明文的过程称为解密(Decrypt)或解译密码(Decipher)。基本术语和概念密码学(Cryptology)是研究信息系统安全保密的科学。是数学的一个分支，包括密码编码学和密码分析学。密码编码学(Cryptography)主要研究对信息进行编码，实现对信息的隐蔽。密码分析学(Cryptanalytics)主要研究加密消息的破译或消息的伪造。基本术语和概念密码算法(CryptographyAlgorithm)是用于加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)。接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)。基本术语和概念密码算法的数学表达明文用M或P表示，密文用C表示，加密函数E作用于M得到C，数学公式表示为：

E(P)=C相反地，解密函数D作用于C产生M

D(C)=P如果使用了密钥k，则可表示为：

Ek(P)=C;Dk(C)=P基本术语和概念密码体制（密码系统）的数学描述它是一个五元组（P,C,K,E,D）满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）（4）E是加密算法的有限集，D是解密算法的有限集（5）对任意的k∈K，有一个加密规则(算法)ek∈E和相应的解密规则(算法)dk∈D，使得ek:P->C和dk:C->P分别为加密解密函数，满足dk(ek(x))=x，这里x∈P。*加密函数必须是单射函数密码算法的分类按照明文的处理方法可分为分组密码(blockcipher)和流密码(streamcipher)分组密码将明文分成固定长度的组块，用同一密钥和算法对每一块加密，每块输出也是固定长度的密文。流密码又称序列密码。序列密码每次加密一位或一字节的明文，是手工和机械密码时代的主流。密码算法的分类

按照保密的条件可分为受限制的（Restricted）算法和基于密钥（key-based）的算法如果加脱密的保密性是基于保持算法的秘密，这种算法称为受限制的算法。缺陷：无法用于大的或经常变换的用户组织。如果加脱密的保密性是基于保持密钥的秘密，而算法本身可以完全公开，则称为基于密钥的算法。基于密钥的算法通常有两类：对称算法和公开密钥算法。密码算法的分类对称算法(SymmetricAlgorithm)就是加密密钥和解密密钥相同或能相互推导的密码算法。秘密密钥算法或单密钥算法，要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性完全依赖于密钥，加密和解密表示为：

EK(M)=C DK(C)=M密码算法的分类公开密钥算法(PublicKeyAlgorithm)就是加密密钥和解密密钥无法相互推导（至少在假定的长时间内）的密码算法。加密密钥可以公开，任何人能用加密密钥加密信息，但只有相应的解密密钥才能解密信息。这里，加密密钥叫做公开密钥(PublicKey)，用PuK表示

EPuK(M)=C解密密钥不可公开，只为解密者(接收方)个人所持有，因此叫做私人密钥(PrivateKey)或秘密密钥，用PrK表示

DPrK(C)=M密码算法的分类有些算法用私人密钥加密而用公开密钥解密，这种算法通常叫数字签名算法，可以表示为：

EPrK(M)=C DPuK(C)=M移位密码基本思路将字母表中的每个字母向后移动若干位代替明文字母直观方便，操作简单移位密码移位密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=Z26对k,x,y∈Z26，定义ek(x)=(x+k)mod26dk(y)=(y-k)mod26mod称为“模运算”如果k=3，则此密码体制为凯撒密码模运算生活中的求模运算现在是3点钟，25小时以后是几点钟？52小时以后呢？(52+3)÷24余7，52小时后应该是7点钟今天是星期二，9天以后是星期几？90天以后呢？(90+2)÷7余1，90天以后应该是星期一模运算的作用为什么引入模运算模运算可将很大的数变成较小的数，同时保持数的某些周期性的性质不变比如1和32085在26下同余，都可以表示字母B从某种意义上看，1=32085可称32085被模26约化为1密码运算涉及指数、对数等大数的运算，模运算将运算的数值始终限定在一定范围内，利于计算机快速处理模运算和同余给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0≦r<q称q为模数，r为a模q的剩余，记为

r≡a

modq若整数a和b有(amodq)=(bmodq)，则称a与b在模q下同余。(即a和b的差是q的倍数)例如11和19在模4下同余(3)。模运算举例14＝3×4＋2,2是14模4的余，2≡14mod4（2也是14模3的余）通常对r<q的条件并不严格要求，如

19＝3×4＋7，7≡19mod4负数亦可参与求模（保证余数大于零即可)(-13)＝(-4)×4＋3，3≡(-13)mod4

7＝(-3)×4＋19，19≡7mod41＝(-1)×11＋12，12≡1mod11模运算的性质模运算的基本性质：①若q|(a-b)，则b≡amodq。如11－3能被4整除，则3是11模4的余；②(amodq)=(bmodq)意味着a≡bmodq。如3mod4=11mod4，则3是11模4的余；③a≡bmodq等价于b≡amodq。如3是11模4的余，同时4是11模3的余；④若a≡bmodq且b≡cmodq，则a≡cmodq。如3≡7mod4且7≡11mod4，则3≡11mod4模运算的性质模算术（不要求r<q）加法：((amodq)＋(bmodq))=(a＋b)modq例：(3mod4)＋(7mod4)=6=10mod4乘法：((amodq)×(bmodq))=(a×b)modq例：(3mod4)×(7mod4)=9=21mod4指数：anmodq=an-1modq×amodqam×nmodq=(ammodq)n模运算的性质模算数运算满足交换律、分配律、结合律模的加和乘存在单位元和逆元加法的单位元是0，乘法的单位元是1a关于模m的加法逆元是m-aa关于模m的乘法逆元是?能在有限的整数范围内构造群、环和域等重要的代数结构利用模运算实现移位密码字母编码表，将字母A－Z对应于数字0－25移位密码加密应用假设移位密码的密钥为K=11，明文为wewillmeetatmidnight首先根据编码表将明文转换成整数串

224228111112441901912831386719然后将每个数与11相加，结果模26，得到

71571922222315154114231914241917184最后根据编码表将数字串转换成字母串，得到

HPHTWWXPPELEXTOYTRSE移位密码的分析设有如下密文串

JBCRCLQRWCRVNBJENBWRWN取k=1,2,3...依次尝试，得到如下不同字母串 iabqbkpqvbpumaidmavqvm(k=1) hzapajopuaptlzhclzupul(k=2) gyzozinotzoskygbkytotk(k=3) fxynyhmnsynrjxfajxsnsj(k=4) ewxmxglmrxmqiweziwrmri(k=5) dvwlwfklqwlphvdyhvqlqh(k=6) cuvkvejkpvkogucxgupkpg(k=7) btujudijoujnftbwftojof(k=8)

astitchintimesavesnine(k=9)移位密码的安全性分析密钥空间过小最多尝试25次，最少尝试1次，平均尝试13次代换密码代换密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K是由26个数字0,1,2,...,25的所有可能的置换组成对任意的置换π∈K，定义 eπ(x)=π(x) dπ(y)=π-1(y)π-1表示置换π的逆置换代换密码加密任取一个置换π，可以得到一个加密函数，例如下表所示的置换规则：按照此表可知eπ(a)=X，eπ(b)=N，...abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDI代换密码解密解密函数是相应的逆置换，前例的逆置换可以表示为：可知dπ(A)=d，dπ(B)=l，...试解密MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHAABCDEFGHIJKLMdlryvohezxwptNOPQRSTUVWXYZbgfjqnmuskaci代换密码的安全性分析密钥是26个字母的置换，所有可能的置换有26!=403291461126605635584000000种采用穷举法，假设每秒可以尝试1000万次，需要1012年以上(已经超过宇宙的理论寿命)果真如此安全？仿射密码仿射密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K={(a,b)∈Z26×Z26:gcd(a,26)=1}对任意的k=(a,b)∈K,x,y∈Z26，定义 ek(x)=(ax+b)mod26 dk(y)=a-1(y-b)mod26gcd(a,26)=1意味着a和26互质a-1是a关于模26乘法的逆仿射密码a和26互质是保证加密函数为单射函数的充要条件，否则不同的明文可能被加密成相同的密文例如a=4，b=3则加密函数为(4x+3)mod26明文字母c对应的值为2，加密后为11，对应密文字母是L；明文字母p对应的值为15，加密后的密文也是L根据该条件，a可能的取值范围是12个数 1,3,5,7,9,11,15,17,19,21,23,25模乘法的逆模乘法的逆求a对于模b乘法的逆，即求x满足axmodb

＝1，可记做

x＝a-1modb

或x＝a-1

如：3×9＝1×26＋1，则称9和3对于模26互逆，记做9-1mod26=3或3-1mod26=9将模数的倍数加1后分解为两个数的乘法，即可得到两个关于模数互逆的数。仿射密码当a=1时，仿射密码即为移位密码仿射密码中不同a值对应的逆(模26)1-1=1 3-1=9 5-1=21 7-1=1511-1=19 17-1=23 25-1=25简单的验证(7×15)mod26=105mod26=17和15在模26下互逆仿射密码举例设仿射密码的密钥k=(7,3)，试给出明文hot的加解密过程加密函数为ek(x)=7x+3解密函数为dk(y)=7-1(y-3)=15(y-3)=15y-19验证dk(ek(x))=dk(7x+3)=15(7x+3)-19

=x+45-19=x仿射密码举例字母hot对应的明文数值为7,14,19，分别加密如下：(7×7+3)mod26=52mod26=0(7×14+3)mod26=101mod26=23(7×19+3)mod26=136mod26=6三个密文值分别为0,23,6，相应的密文为AXG解密过程略仿射密码安全性分析a可能的取值是12，b有效的取值是26，密钥空间大小为12×26=312如果将模数m推广到一般，则仿射密码的密钥空间为mΦ(m)，其中Φ(m)表示m以内与m互质的数的个数，称为欧拉函数例如：Φ(26)=12；Φ(60)=16取模数m=60，则仿射密码的密钥空间大小为16×60=960欧拉函数假定这里pi均为素数且互不相同，ei是大于0的整数，则例如60=22×3×5，则Φ(60)=(22-21)×(31-30)×(51-50)=2×2×4=16如果m=p×q(p和q均为素数)则Φ(m)=(p-1)×(q-1)课堂练习已知仿射密码的密钥为k=(3,10)试解密XICFP维吉尼亚密码16世纪晚期，法国外交官维吉尼亚(Vigenere)发明，引入了“密钥”的概念维吉尼亚密码维吉尼亚密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=(Z26)m，m是一个正整数对任意的k=(k1,k2,...,km)∈K,x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定义 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)以上运算均在Z26上运行(模26)维吉尼亚密码举例假设m=6，密钥字为CIPHER，加密明文

thiscryptosystemisnotsecure密钥字对应的数字串为k=(2,8,15,7,4,17)将明文转化为对应的数字，每6个为一组1978182172415191418241819412818131419184220174维吉尼亚密码举例使用密钥字进行模26下的加法运算1978182172415191418242815741728157417+(mod26)21152325680238212215181941281813141918422815741728157417+(mod26)20119191291522825819201742815+(mod26)222519得到相应的密文为VPXZGIAXIVWPUBTTMJPWIZITWZT维吉尼亚密码的安全性密钥空间大小为26m当m=5时，密钥空间大小超过1.1×107，已经不可能采用手工方法穷举搜索采用计算机穷举搜索可能不到1秒钟希尔(Hill)密码希尔密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=(Z26)m，m是一个不小于2的正整数K是定义在Z26上的m×m可逆矩阵的集合取密钥k∈K，k为一个m×m矩阵，记为(kij)，对x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定义 ek(x)=xk dk(y)=yk-1k-1表示k的逆矩阵以上运算均在Z26上运行(模26)希尔密码举例设m=2，取密钥k=每个明文单元使用x=(x1,x2)来表示，对应的密文单元用y=(y1,y2)表示，则有 y=xk，即(y1,y2)=(x1,x2)

即 y1=(11x1+3x2)mod26 y2=(8x1+7x2)mod26希尔密码加密假设需要加密明文july，则可将明文划分为如下两个加密单元(9,20)和(11,24)，分别进行加密变换如下(9,20)=(99+60,72+140)=(3,4)(11,24)=(121+72,88+168)=(11,22)因此密文为DELW希尔密码解密k的逆矩阵k-1=有x=yk-1，即(x1,x2)=(y1,y2)即x1=(7y1+23y2)mod26x2=(18y1+11y2)mod26希尔密码解密对密文DELW进行解密即做如下运算(3,4)=(21+92,54+44)=(9,20)(11,22)=(77+506,198+242)=(11,24)如何计算逆矩阵？矩阵运算矩阵的乘法设A=(ai,j)是一个l×m矩阵，B=(bj,k)是一个m×n矩阵，则定义矩阵的乘法AB=C=(ci,k)C是一个l×n矩阵矩阵乘法不满足交换律但满足结合律矩阵运算单位矩阵m×m的矩阵中，主对角线上的元素均为1，其余元素均为0的矩阵称为单位矩阵，记为Im对任意l×m矩阵A，有AIm=A；对任意m×n矩阵B，有ImB=B逆矩阵m×m矩阵A的逆矩阵记为A-1，满足AA-1=A-1A=Im逆矩阵具有唯一性(但不一定存在)矩阵运算m×m阶矩阵A=(ai,j)的行列式记为|A|或detA如果A为2×2阶矩阵，则 detA=a1,1a2,2-a1,2a2,1如果A为3×3阶矩阵，则 detA=a1,1a2,2a3,3+a1,2a2,3a3,1+a1,3a2,1a3,2 -(a1,1a2,3a3,2+a1,2a2,1a3,3+a1,3a2,2a3,1)矩阵运算推广到一般情况如果A为m×m阶矩阵，则其中i1i2...im是整数1到m的一个排列τ[i1i2...im]表示这个排列的逆序数递归法计算，定义Ai,j表示从A中删除第i行第j列所得的(m-1)×(m-1)阶矩阵，则矩阵求逆矩阵K的逆矩阵存在的充要条件是|K|非零；在模26下，逆矩阵存在的充要条件是|K|与26互素，即gcd(detK,26)=1矩阵求逆方法一：利用矩阵的初等行变换求逆矩阵如矩阵求逆矩阵求逆方法二：K-1=(detK)-1K*K*表示K的伴随矩阵K*的第i行第j列取值为(-1)i+jdetKji，Kji是删除K的第j行第i列后形成的矩阵对二阶矩阵有矩阵求逆举例设矩阵是定义在Z26上的矩阵，可计算detK=7，且(detK)-1=15K的伴随矩阵为因此K-1存在且为*利用matlab进行矩阵运算定义矩阵，命令行输入：A=[10,5,12;3,14,21;8,9,11]求矩阵的行列式值，命令行输入：det(A)求矩阵的逆(非模运算)，命令行输入：inv(A)求伴随矩阵，命令行输入：det(A)*inv(A)mod(det(A)*inv(A),26)课堂练习已知希尔密码的解密函数为试加密明文X=text置换密码置换密码体制密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=(Z26)m，m是一个正整数K是由所有定义在集合{1,2,...,m}上的置换组成对任意的密钥(即置换)π，定义其中π-1为置换π的逆置换置换密码置换和逆置换的定义置换是定义在有限集X上的双射函数π:X→X,对任意的x∈X，存在唯一的x’∈X，使得π(x’)=x置换π的逆置换定义为π-1:X→X π-1(x)=x’当且仅当π(x’)=x π-1也是X上的一个置换置换密码举例设m=6，密钥为如下的置换π将两行对调并重新排序可得逆置换π-1如下即x123456π(x)351642y123456π-1(y)361524置换密码举例使用该密码加密明文shesellsseashellsbytheseashore首先将明文字母每六个分为一组：shesel|lsseas|hellsb|ythese|ashore对每组字母使用加密变换可得EESLSH|SALSES|LSHBLE|HSYEET|HRAEOS即密文为EESLSHSALSESLSHBLEHSYEETHRAEOS置换密码的特性置换密码实际上是希尔密码的特殊形式给定集合{1,2,...,m}的一个置换π，定义置换π的关联置换矩阵Kπ=(Ki,j)m×m，其元素值为使用矩阵Kπ为密钥的希尔密码等价于使用置换π为密钥的置换密码，且置换密码的特性前面置换密码的例子中，等价的希尔密码加密密钥为加密函数为eπ(x)=xKπ =(x1,x2,x3,x4,x5,x6) =(x3,x5,x1,x6,x4,x2)置换密码的特性解密密钥为解密函数为dπ(y)=yKπ-1 =(y1,y2,y3,y4,y5,y6) =(y3,y6,y1,y5,y2,y4)流密码前面的密码体制中，连续的明文元素使用相同的密钥K来加密y=y1y2...=ek(x1)ek(x2)...这种类型的密码体制称为分组密码分组密码的不足需要设计复杂的加密函数以提高安全性经常需要对明文进行填充(padding)操作以确保分组长度完整如果k较短，则容易遭到穷举攻击流密码设计思路将明文看作字符串或比特串，并逐字符或者逐位进行加密为了防止密钥穷举，使用和明文信息一样长的密钥(无限)流z=z1,z2...进行加密这种密码体制称为流密码(或序列密码)可以使用非常简单的加密算法(如简单的异或运算)关键是如何生成密钥流流密码的代表弗纳姆(Vernam)密码1918年，GillbertVernam建议密钥与明文一样长并且没有统计关系的密钥内容，他采用的是二进制数据：加密：Ci=Pi⊕Ki

解密：Pi=Ci⊕Ki关键：构造和消息一样长的随机密钥异或运算位的异或运算0⊕0=0,0⊕1=1,1⊕0＝1,1⊕1=0异或运算等价模2加法运算特性：两次异或运算以后还原，可设计加密和脱密完全相同的函数。流密码特点运算简单实时性强安全性依赖与密钥流的产生方法流密码的分类按密钥的周期性分类周期流密码；存在某个固定的正整数r，使得密钥流每隔r个字符（或者比特）以后重复非周期流密码对任何正整数密钥流都不重复如一次一密乱码本流密码的分类按密钥的产生方式分类同步流密码密钥流的产生独立于消息流;例如分组密码的OFB(输出反馈)模式异步流密码每一个密钥字符是由前面n个明文或密文字符推导出来的，其中n为定值。例如分组密码的CFB(密码反馈)模式同步流密码使用某种算法，由一个初始密钥变换出和明文串相互独立的密钥流。定义如下：同步流密码是一个六元组(P,C,K,L,E,D)和一个函数g，且满足如下条件1P,C,K分别是明文、密文、密钥的有限集2L是密钥流字母表有限集3g是密钥流生成器，g使用密钥k∈K作为输入，产生无限长的密钥流Z=z1z2...，其中zi∈L4对任意的z∈L，都有一个加密规则(函数)ez:P→C∈E和相应的解密规则(函数)dz:C→P∈D，并且对每个明文x∈P满足 dz(ez(x))=x流密码和分组密码的关系分组密码可以看做流密码的特殊情况如维吉尼亚密码，可以看做是一种短周期的同步流密码 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)密钥流定义为即密钥流是周期为m的密钥序列k1k2...kmk1k2...kmk1k2...km...分组密码可以用于生成密钥序列密钥流的产生理想的密钥流是随机不重复的真随机抛硬币、掷骰子、噪声发生器收发双方难以同步无周期性密钥和密文等长一次一密乱码本难以在高带宽的信道上使用密钥流的产生真正的随机序列往往难以实用，实际多用线性递归关系产生伪随机序列例如设m=4，(a1,a2,a3,a4)为(0,0,0,1)密钥流按如下线性递归关系产生：ai+4=(ai+ai+3)mod2 (等价于ai+4=ai⊕ai+1)产生的密钥序列为a1a2a3a4a5....，即00011110101100100011110101...周期为24-1=15(a1,a2,a3,a4)通常被称为初始向量密钥流的产生这种方式可以使用硬件轻易实现，此硬件称为线性反馈移位寄存器(LFSR,LinearFeedbackShiftRegister)anan-1a2a1......⊕⊕⊕=1c0=1输出{ak}（a1，

a2，...

，an）输出序列为{ak}＝a1a2...

an...ai(t+1)=ai+1(t)an(t+1)=cna1(t)⊕cn-1a2(t)⊕...⊕c1an(t)ai(t+1)=ai+1(t)a4(t+1)=a1(t)⊕a4(t)ta4a3a2a1ta4a3a2a101000901101110010001121110111001311111201004011113001051011140001601011510007101016110081101...............a4a3a2a1⊕输出{ak}c4=1c1=1返回

LFSR示例说明周期为24－1＝15cn＝1的n级LFSR其输出序列为周期序列，且周期数r满足r≤2n－1若n级LFSR的输出序列的周期达到最大2n－1，则称之为m序列f(x)=c0+c1x+c2x2+...+cnxn描述LFSR的反馈连接状态，称为特征多项式可以证明，一个n级LFSR能产生m序列的充要条件是它的特征多项式为一个n次本原多项式本原多项式若一个n次多项式f(x)的阶为2n－1，即满足条件：f(x)为既约多项式f(x)可整除（x2n-1＋1)f(x)不能整除（xp＋1)，其中p<2n－1eg.n=4，周期为24－1＝15，其特征多项式是能整除(x15+1)的4次本原多项式x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)由于x4+x3+x2+x+1|x5＋1，所以本原多项式为，x4+x+1和x4+x3+1，选择f(x)＝x4+x+1，即c4＝c1＝c0＝1见前例本原多项式n2n-1λ(n)n2n-1λ(n)1111120471762311240951443721381916304152141638375653161532767180066361665535204871271817131071771082551618262143777695114819524287275941010236020104857524000

可以产生λ(n)×2n-1种密钥流m序列的特性Golomb提出0-1序列的随机性公设（1）若r是奇数，则0-1序列的一个周期内0的个数比1的个数多一个或少一个；若r是偶数，则其个数相等。（2）在长度为r的周期内，1游程的个数为游程总数的1/2，2游程的个数占总数的1/22，一次，c游程的个数占总数的1/2c。而且，对于任意长度，0的游程个数和1的游程个数相等。（3）自相关函数是一个常数。m序列的特性伪随机序列游程

eg.0-1序列00110111，00称为0的2游程；自相关函数

eg.假定s1s2s3...为0-1序列，r为其周期，即r为满足sm+r＝sm的最小正整数，若有两个子序列

s1，s2，s3，...，srs1＋τ，s2＋τ

，s3＋τ

，...，sr＋τ

定义R（τ）＝（nτ－dτ

）/r

其中：nτ为该两个子序列中相应位相同的数目，不同的位的数目即为dτ

＝r－nττ=0，有

R（τ）＝1m序列的特性平衡特性

m序列中1的个数比0的个数多1游程特性

1的最大游程为n游程，有且仅有1个，因为会出现1个全1状态111...1，那么会出现串01......10，则经历状态为

1...10

，1...1，01...1

不存在1的n-1游程，会出现1个0的n-1游程，则出现串10...01，经历状态0...01

和10...0

当n>2，设r为不超过n-2的任一正整数，则任何1的r游程表示存在串01...10（r+2位），其游程数目为2n-r-2，于是，在每一周期中出现1的游程个数为

1＋＝2n-2

同样，出现0的游程个数为2n-2

，游程总数为2n-1eg.n=4，000111101011001；m序列的特性位移相加特性

m序列和它的位移序列模2相加后所得序列仍是该m序列的某个位移序列。

设序列{ak}为m序列，且满足递推关系：

ah+n=cnah

⊕cn-1ah+1

⊕...⊕c1ah+n-1

位移τ位：ah+n+τ

=cnah+τ

⊕cn-1ah+1+τ

⊕...⊕c1ah+n-1+τ

，则ah+n

⊕ah+n+τ

＝cn（ah⊕

ah+τ

）⊕cn-1（ah+1⊕

ah+1+τ

）

⊕...⊕c1（ah+n-1⊕

ah+n-1+τ

）

自相关特性

设两子串为{at}和{at+τ}，则{at}⊕{at+τ}中为0的位的数目正好是两个子串中对应位相同的位数，则：

R（τ）＝（nτ－dτ

）/r＝－1/2n－1（τ≠0)

当τ＝0时，R（τ）＝1

利用LFSR设计加密算法同步序列密码实现⊕anan-1a2a1......⊕⊕=1c0=1输出{ak}密钥流⊕明文密文异步流密码同步流密码存在周期问题异步流密码思路密钥流z的产生不但与密钥K有关，而且还与明文元素(x1,x2,...,xi-1)或密文元素(y1,y2,...,yi-1)有关自动密钥密码通过K和明文产生密钥流自动密钥密码自动密钥密码体制的数学描述自动密钥密码是一个六元组(P,C,K,L,E,D)，满足以下条件P=C=K=L=Z26密钥流定义：z1=k∈K，zi=xi-1，i≥2对任意的z∈K，x,y∈Z26，定义 ez(x)=(x+z)mod26 dz(y)=(y-z)mod26自动密钥密码举例假设k=8，明文为rendezvous加密过程如下：首先将明文转换为整数序列:17413342521142018根据z1=k=8，zi=xi-1得到密钥流为：8174133425211420将对应的元素相加并模26得到：2521171673209812字母形式的密文为ZVRQHDUJIM解密过程略

利用LFSR设计加密算法序列密码密码反馈加密⊕anan-1a2a1......⊕⊕=1⊕明文m密文c加密过程：e1＝m1＋，e2＝m2＋＋c1e1

，......ek＝mk＋＋1≤k≤n

en+1＝mn+1＋，en+h＝mn+h＋

利用LFSR设计加密算法序列密码密码反馈解密⊕anan-1a2a1......⊕⊕=1⊕明文m密文c解密密钥和加密密钥相同，都是系数c1，c2，...，cn和初始状态(a1，a2，...an）密码分析前面从穷举密钥的角度简单分析了各类密码体制的安全性，其前提是分析者知道使用的密码体制(密码算法)。如果不知道密码体制，分析工作将困难得多将安全性建立在保持算法的秘密基础之上，这类算法称为受限制的算法缺陷：无法用于大的或经常变换用户的组织。如果加脱密的保密性是基于保持密钥的秘密，而算法本身可以完全公开，则称为基于密钥的算法密码分析目标密码分析学是在不知道密钥的情况下，恢复出明文的科学。分析者是在已知密码体制（密码算法及其实现的全部详细资料）的前提下来破译使用的密钥。从分析者掌握的条件区分，常用的密码分析攻击有四类密码分析方法四类常用的密码分析攻击方式唯密文攻击(Ciphertext-onlyAttack)分析者有一些消息的密文，这些密文都用同一加密算法加密，任务是尽可能恢复这些密文，或推算出加密的密钥。已知明文攻击(Known-plaintextAttack)分析者不但有一些消息的密文，还知道这些密文对应的明文，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法密码分析方法四类常用的密码分析攻击方式选择明文攻击(Chosen-plaintextAttack)分析者可获得对加密机的暂时访问，因此他能自由选择明文串并构造出相应的密文串，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法选择密文攻击(Chosen-ciphertextAttack)分析者可获得对解密机的暂时访问，因此他能自由选择密文串并构造出相应的明文串，任务是推算出加密的密钥，或推导出可以对新密文进行解密的算法课堂练习截获使用移位密码加密的密文如下 MQTSVXERXQIWWEKI试分析其对应的明文唯密文攻击分析古典密码最困难的分析条件在密文片段足够长的情况下，能分析大多数古典密码通常需要用到英文字母的频率分析和反复猜测能有效分析单表替代密码多表替代难度加大只能分析可阅读的文本数据借助计算机能大大提高分析效率英文字母频率分析利用26个字母在英文文字出现的不同频率猜测单表替代字母英文字母频率分析26个字母在英文语言中出现的频率排序E出现的频率远高于其他字母其次为T、A、O、I、N、S、H、R再次为D、L更次为C、U、M、W、F、G、Y、P、B最次为V、K、J、X、Q、Z许多双字母的固定序列经常出现TH、HE、IN、ER、AN、RE、ED、ON、ES、ST、EN、AT、TO、NT、HA、ND、OU、EA、NG、AS、OR、TI、IS、ET、IT、AR、TE、SE、HI、OF英文字母频率分析还有一些经常出现的3字母固定序列THE、ING、AND、HER、ERE、ENT、THA、NTH、WAS、ETH、FOR、DTH根据经验，有些字母不可能组合出现在一个单词中，如果出现可作为单词边界进行分析简单代替密码的分析原理根据密文字母出现频率的高低进行猜测和验证得到的密文越长，越符合统计规律仿射密码的密码分析仿射密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K={(a,b)∈Z26×Z26:gcd(a,26)=1}对任意的k=(a,b)∈K,x,y∈Z26，定义 ek(x)=(ax+b)mod26 dk(y)=a-1(y-b)mod26gcd(a,26)=1意味着a和26互质a-1是a关于模26乘法的逆分析目标：根据密文得到a和b的值分析方法：首先分析出现频率最高的字符，只需要猜中两个字母的代替，就能解出a和b仿射密码分析举例得到仿射密码的密文如下FMXVEDKAPHEFRBNDKRXRSREFMORUD SDKDVSHVUFEDKAPRKDLYEVLRHHRH分析密文中每个字母的出现频数记录如下字母频数字母频数字母频数字母频数字母频数A2B1C0D7E5F4G0H5I,J0K5L2M2N1O1P2Q0R8S3T0U2V4W0X2Y1Z0仿射密码分析举例以上密文中出现的最大频数的几个密文字母依次是R、D、E、H、K、S、F、V假设R是e的加密，D是t的加密即ek(4)=17,ek(19)=3，因为ek(x)=ax+b，得到方程组解方程组可知a=6,b=19，因为a不满足与26互质的条件，因此猜测错误仿射密码分析举例以上密文中出现的最大频数的几个密文字母依次是R、D、E、H、K、S、F、V再假设R是e的加密，E是t的加密，继续使用该方法得到a=13仍不满足与26互质的条件再假设H是t的加密，得到a=8仍无效再假设K是t的加密，得到a=3,b=5，使用此密钥尝试解密得到可阅读的明文为algorithmsarequitegeneraldefinitionsofarithmeticprocesses代换密码的密码分析代换密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=Z26K是由26个数字0,1,2,...,25的所有可能的置换组成对任意的置换π∈K，定义 eπ(x)=π(x) dπ(y)=π-1(y)π-1表示置换π的逆置换分析目标：根据密文得到置换π分析技巧：先分析频率高的密文，再根据英文单词中的字母组合规律进行分析代换密码分析举例得到代换密码的密文如下YIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代换密码分析举例分析密文中各字母出现的频数Z出现频率最高其次是C,D,F,J,M,R,Y字母频数字母频数字母频数字母频数字母频数A0B1C15D13E7F11G1H4I5J11K1L0M16N9O0P1Q4R10S3T2U,V5W8X6Y10Z20代换密码分析举例Z出现的频率远高于其他字母，推测dk(Z)=e以Z开头的双字母中，ZW出现的次数最多，推测dk(W)=d；以W结尾的双字母中，RW出现数次且R也多次出现，推测dk(R)=n；NZ出现多次而ZN未出现，推测dk(N)=h根据以上猜测得到一些残缺的明文如ne?ndhe(其密文为RZCRWNZ)，在英语字典中搜索不到匹配的单词，猜测?为a，即dk(C)=a代换密码分析举例nh(对应密文为RN)不可能出现在一个单词中，因此密文中的RNM解密为nh?，其中h是单词的开头且后面应该是一个元音字母M在密文中出现的频率很高，因此对应i或o；考虑到ai出现的频率高于ao，推测dk(M)=io是较常出现的字母，对应的密文应该是D,F,J,Y中的一个，因为密文中出现了CDM/CFM/CJM这样的组合，推测dk(Y)=o(单词中不会出现aoi)代换密码分析举例剩下的三个高频密文字母D,F,J，应该是明文r,s,t的某种映射密文组合NMD(hi?)多次出现，猜测dk(D)=s密文组合HCMF(hai?)出现，猜测dk(F)=r剩下dk(J)=t密文组合HNCMF(?hair)出现，猜测dk(H)=c代换密码分析举例目前猜测出的代替规则有Z-e，W-d，R-n，N-h，C-a，M-i，Y-o，D-s，F-r，J-t，H-c根据该规则部分解密密文如下o-r-riend-ro--arise-a-inedhise--t---ass-itYIFQFMZRWQFYVECFMDZPCVMRZWNMDZVEJBTXCDDUMJhs-r-riseasi-d-a-orationhadta-en--ace-hi-eNDIFEFMDZCDMQZKCEYFCJMYRNCWJCSZREXCHZUNMXZhe-asnt-oo-in-i-o-redso-e-ore-ineandhesettNZUCDRJXYYSMRTMEYIFZWDYVZVYFZUMRZCRWNZDZJJ-ed-ac-inhischair-aceti-ted--to-ardsthes-nXZWGCHSMRNMDHNCMFQCHZJMXJZWIEJYUCFWDJNZDIR代换密码分析举例最后从英文单词、语法等语言规律猜测其他代替规则，最终得到明文OurfriendfromParisexaminedhisemptyglasswithsurprise,asifevaporationhadtakenplacewhilehewasn’tlooking.Ipouredsomemorewineandhesettledbackinhischair,facetilteduptowardsthesun维吉尼亚密码的密码分析维吉尼亚密码体制的数学描述对于密码体制的五元组（P,C,K,E,D）有P=C=K=(Z26)m，m是一个正整数对任意的k=(k1,k2,...,km)∈K,x=(x1,x2,...,xm)∈P,y=(y1,y2,...,ym)∈C，定义 ek(x)=(x1+k1,x2+k2,...,xm+km) dk(y)=(y1-k1,y2-k2,...,ym-km)以上运算均在Z26上运行(模26)分析目标：根据密文得到k1,k2,...,km维吉尼亚密码的密码分析维吉尼亚密码的分析难点多表替代，使简单的频率分析方法失效如果知道密钥字长度m，可以分解为m个单表替代密码分析任务确认密钥字长度m是关键Kasiski法重合指数法维吉尼亚密码的密码分析Kasiski测试法确定密钥字长度m19世纪普鲁士少校Kasiski提出可粗略猜测m，密文越长越准确基本步骤1.在密文中标出重复的三个或多个字符结构；2.对每一个字符结构，记下结构的起始位置；3.计算相邻的起始点的距离；4.对每个距离求出所有因数；5.密钥的长度为步骤4中出现的某一因数维吉尼亚密码的密码分析Kasiski测试法举例明文：wearediscoveredsaveyourself密钥：deceptive密文：ZICVTWQNGRZGVTWAVZHCQYGLMGJ测试过程：1.在密文中标出重复的字符结构——VTW；2.两个字符结构的起始位置分别为4和13；3.两个起始点的距离是9；4.9的因数有3和9；5.根据步骤4出现的因数，确定密钥的可能长度是3位或9位。维吉尼亚密码的密码分析重合指数法确定密钥字长度m重合指数的定义一个字母串X中随机取出两个字母，这两个字母恰好相同的概率，记为Ic(X)对于完全随机的字母串，Ic(X)=26*(1/26)2=1/26≈0.038对于英文文本，其中pi是字母表中第i个字母在英文中出现的概率重合指数的特点单表代替密码中，密文的重合指数和明文相同维吉尼亚密码的密码分析重合指数法确定密钥字长度m密文重合指数的计算方法对于长度为n的密文串X，首先统计密文字母A,B,C,...,Z出现的频数(次数)，记为f0,f1,f2,...,f25计算维吉尼亚密码的密码分析重合指数法确定密钥字长度m分析原理假设密文串为Y=y1y2...yn，m是密钥字长度将Y分割成m个子串Y1=y1y1+my1+2m...Y2=y2y2+my2+2m......Ym=ymy2my3m...对于每个Yi，其密文采用的是单表代替方法(相同的密文对应相同的明文)，其重合指数Ic(Yi)应接近0.065通过尝试不同的m，找到重合指数最接近0.065的那个维吉尼亚密码分析举例得到维吉尼亚密码加密的密文如下CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE维吉尼亚密码分析举例Kasiski测试法分析密文串CHR出现在1,166,236,276,286这几个位置，到第一个位置的距离分别是165,235,275,285，他们只有一个公因子5，故猜测密钥字长度为5维吉尼亚密码分析举例重合指数法分析尝试不同的密钥字长度，计算密文的重合指数mIc(Y1)Ic(Y2)Ic(Y3)Ic(Y4)IcY510.04520.0460.04130.0430.0500.04740.0420.03900450.04050.0630.0680.0690.0610.072维吉尼亚密码分析举例分析密钥字确定密钥字长度后，可以使用频率分析方法分别解密Y1,Y2,...,YmY1=CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAX CWMNJJFAIACNRNCATBWKDMCDCQQXWKY2=HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHES BGSEGEMRDRSHEAIEORTHNHOANOEY3=RARANOBQRASAJNVRAPTCXUGRJRUQTHLVGRLJH NGYNQRRGINRYQPVEEBRVRHIRIEY4=EHAXXPQEVKXHMKGZKSEMMIMEEVLWYXJBLZEI WMLPRJVELMRQEEEKWMHTRCPIMIY5=EMTXBHMR