计算机密码学课件

计算机密码学朱文余10/10/202311/32密码学发展历程

第一次世界大战前，密码学主要进展很少出目前公开文献中1923年，20世纪最有影响分析文章，重合指数及其在密码学中应用问世1949年，Shanon刊登了题为“保密系统通信理论”1949—1967密码学文献很少1976年，W.Diffie,M.Hellman提出了公开密钥密码1977年，美国联邦政府正式颁布DES1977年—至今，公开密码学研究爆炸性增加10/10/202322/32密码学基本概念密码学分类：密码编制学和密码分析学密码系统组成：（1）明文空间M；（2）密文空间C；（3）密钥空间K，对任意k∈K，k=（kd，ke）；（4)加密算法E，C=E（M，ke）；（5）解密算法D，M=D（C，kd）。10/10/202333/32密码体制分类根据密钥分类：[1]ke=kd或ke→kd称为单钥或对称或传统；[2]ke≠kd称为双钥或非对称，进而由ke不能推出kd称为公钥密码体制。根据对明文划分与密钥使用办法不一样可将密码体制分为分组密码和序列密码体制。10/10/202344/32密码分析者袭击密码办法主要有下列三种穷举袭击统计分析袭击数学分析袭击10/10/202355/32根据密码分析者可利用数据来分类，破译密码类型分为三种仅知密文袭击已知明文袭击：计算机程序易受这种袭击选择明文袭击：计算机文献系统和数据库易受这种袭击10/10/202366/32置换密码—把明文中字母重新排列，字母本身不变例：明文为thiscryptosystemisnotsecure。排成矩阵：thiscryptosystemisnotsecure密文为tysnuhptoritetesomscsierysc。10/10/202377/32单表替代密码首先构造一种密文字母表，然后用密文字母表中字母或字母组来替代明文字母表中字母或字母组，各字母或字母组相对位置不变，但其本身变化了。设A={a0，a1，…，an-1}为含n个字母明文字母表，B={b0，b1，…，bn-1}为含n个字母密文字母表，定义一种由A到B一一映射。f：A→B，f（ai）=bi设明文M=（m0，m1，…，mn-1），则对应密文C=（f（m0），f（m1），…，f（mn-1））10/10/202388/32几类单表替代密码加法密码：f（ai）=aj，j≡i+k（modn），0＜k＜n，取n=26。乘法密码：f（ai）=aj，j≡ik（modn），0＜k＜n，（k，n）=1。仿射密码：f（ai）=aj，j≡ik1+k0（modn），（k1，n）=1。密钥词组替代密码—用一词组或短语作密钥，去掉密钥中反复字母，把成果作为矩阵第一行，其次从明文字母表中补入其他字母，最后按某一次序从矩阵中取出字母组成密文字母表。例：密钥为redstar，明文为datasecurity。10/10/202399/32字母与数字对应表abcdefghi012345678jklmnopqr91011121314151617stuvwxyz181920212223242510/10/20231010/32单表替代密码统计分析极高频率字母组：ez次高频率字母组：taonirshjvbhdilc中等频率字母组：dlucmxseyr低频率字母组：pfywgbvtfkawnp甚低频率字母组：jkqxzmqgou双字母：thheineranreed…三字母：theingandherareent…10/10/20231111/32举例YKHLBAJCZSVIJJZBLZVHIJCZVHJDRIZXKHLBAVSSRDHEIDRYVJVLBXSKYLBAYLALJVSIFZZXCCVILEFHDNZYEVBTRDSYJCZFHLEVHTHZVIDBRDHJCLICVIWZZBJCZVYNZBJDRELXHDZSZXJHDBLXIJCZXDEFSZQLJTDRJCZRKBXJLDBIJCVJXVBBDPWZFZHRDHEZYWTJCZEVXCLBZCVIHLIZBYHVEVJLXVSSTVIVHZIKSJDRJCLIHZXZBJYZNZSDFEZBJLBJZXCBDSDATEVBTDRJCZXLFCZHITIJZEIJCVJPZHZDBXZCDBILYZHZYIZXKHZVHZBDPWHZVMVWSZ10/10/20231212/32Z：e，v→a，三字母单词JCZ→？？e：the2字母单词VI→a？：an，as，am，at，I→s三字母单词VHZ→a？e：are，ageH→r。三字母单词JZB→te？：B→n4字母单词JCLI→th？s：L→I4字母单词WZZB→？een：W→b2字母单词WT→B？：T→y6字母单词HZVIDB→reas？n：D→o2字母单词DR→o？：R→f3字母单词BDP→no？：P→w4字母单词DBXZ→on？e：X→c4字母单词EVBT→？any：E→m10/10/20231313/323字母单词BDP→no？：P→w4字母单词DBXZ→on？e：X→c4字母单词EVBT→？any：E→mIFZZXC→s？eech：F→pFZHRDHEZY→performe？：Y→dVSS→a？？：S→lJZXCBDSDAT→technono？yA→g3字母单词结尾LBA→i？g：B→nYKHLBA→d？ring：K→uLEFHDNZY→impro？ed：N→vWHZVMVWSZ→brea？ableM→k10/10/20231414/32多表替代密码构造d个密文字母表设A={a0，a1，…，an-1}为含n个字母明文字母表，Bj={bj0，bj1，…，bjn-1}，j=0，1，…，d-1为d个含n个字母密文字母表，定义d个映射。fj：A→Bj，fj（ai）=bji设明文M=（m0，m1，…，mn-1），则对应密文C=（f0（m0），f1（m1），…，fd-1（md-1），fd（md），…）10/10/20231515/32Vigenere密码若K=k1k2…km，M=m1m2…mn，C=c1c2…cn其中ci≡mi+ki（mod26）至于密钥k能够通过周期性地延长，周而复始，反复以至无穷。即ki+lm=ki例：密钥为cipher，明文为thiscrytosystem。10/10/20231616/32对Vigenere密码分析确定密钥字长度：[1]Kasiski测试，[2]使用重合指数。确定密钥。重合指数10/10/20231717/32例：UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIFASJWGGSJEPNSUETPTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLRLLGWOFKWLUWSHEVWSTTUARCWHWBVTGNITJRWWKCOTPGMILRQESKWGYHAENDIULKDHZIQASFMPRGWRVPBUIQQDSVMPFZMVEGEEPFODJQCHZIUZZM…10/10/20231818/32DWF：7，112105LLG：64，14985m？=5UUGIWYJ…确定密钥字母：考虑两行互重合指数是有用，求出δij=kj-ki10/10/20231919/32代数密码或Vernam密码若K=k1k2k3…，M=m1m2m3…，其中mi=0或1，

ki=0或1，

C=c1c2c3…其中ci=mi+ki例：明文为cat，密钥为key，于是M=000100000010011K=010100010011000C=01000001000101110/10/20232020/32Hill加密算法Hill加密算法基本思想是将l个明文字母通过线性变换将它们转换为l个密文字母。解密只要作一次逆变换就能够了，密钥就是变换矩阵本身。10/10/20232121/32DES数据加密标准初始置换IP将置换输出64位数据提成左右两半，左二分之一称为L0，右二分之一称为R0计算函数16次迭代。Li=Ri-1，Ri=Li-1⊕f（Ri-1，Ki）。i=1，…16最后一次迭代L16放在右边，R16放在左边。再经逆初始置换IP-1，产生64位密文。10/10/20232222/32密钥编排函数KS算法置换选择1：首先从64位密钥中去掉8个奇偶校验位，然后打乱重排，前28位作为C0，后28位作为D0。循环左移：Ci=LSi（Ci-1），Di=LSi（Di-1），i=1，…16。置换选择2：从Ci和Di（共56位）中选择出一种48位子密钥Ki。10/10/20232323/32加密函数f选择置换E（Ri-1）=48位E（Ri-1）⊕Ki选择函数组S，1）输出不是输入线性和仿射函数；2）变化其中任一位，输出最少有两位发生变化；3）保持1位不变，其他5位变化，输出中0和1个数接近相等。10/10/20232424/32IDEA密码系统64bit数据块提成4个子块为x1，x2，x3，x4，作为迭代第一轮输入，所有共8轮迭代，每轮迭代都是4个子块彼此间以及16bit子密钥进行异或，mod216加法运算，mod（216+1）乘法运算。在每一轮中，执行次序如下：10/10/20232525/32X1和第一种密钥子块相乘；X2和第二个密钥子块相加；X3和第三个密钥子块相加；X4和第四个密钥子块相乘；将第1）步和3）步成果相异或；将第2）步和4）步成果相异或；5）步成果与第五个密钥子块相乘；将第6）步和7）步成果相加；8）步成果与第六个密钥子块相乘；10/10/20232626/3210）将第7）步和9）步成果相加；11）将第1）步和9）步成果相异或；12）将第3）步和9）步成果相异或；13）将第2）步和10）步成果相异或；14）将第4）步和10）步成果相异或；第一轮输出是4个子块，即11）、12）、13）、14）步成果；将中间两个块交换（最后一轮除外）10/10/20232727/32为下一轮输入。在通过8轮运算之后，有一种最后输出变换（1）X1和第一种密钥子块相乘；（2）X2和第二个密钥子块相加；（3）X3和第三个密钥子块相加；（4）X4和第四个密钥子块相乘；最后，这4个子块连接到一起产生密文。。10/10/20232828/32分组密码工作方式电子密码本模式（ECB）：设明文M=m1m2…mn，C=c1c2…cn，其中ci=E（mi，K），i=1，…，n。电子密码本模式是分组密码基本工作方式。输出反馈模式（OFB）：在OFB模式中，先产生密钥流，然后将它与明文进行异或，定义Z0=IV，然后用Zi=E（Zi-1，K），i≥1计算Z1Z2…10/10/20232929/32通过ci=mi+Zi，i≥1，来加密明文序列m1m2…。3·密码分组链接模式（CBC）：定义C0=IV，Ci