---密码学基础(古典密码-素材)

网络与信息安全1古典密码算法2015-6-9网络与信息安全2提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全3当今的信息网络蕴含了表现为信息形式的多种巨大利益政治的、军事的、经济的、商业的……通过网络非法获取和利用信息可能随时发生互联网的开放性是根源网络安全已成为网络设计、建设和维护的重要内容密码学/密码算法成为保护网络信息的利器以数学为工具，将信息明文变换为密文成为保护信息的核心屏障网络与密码算法网络与信息安全4密码学的目的合法通信双方Alice和Bob在不安全的信道上进行安全通信，而破译者Oscar不能理解他们通信的内容“安全”指机密性、完整性、鉴别、不可抵赖简单加密系统模型简单加密系统模型密码系统网络与信息安全5密码系统包含带参数K的变换EK()、带参数K的逆变换DK()、信息传送信道、密钥传送信道变换EK得将明文消息P变换为密文C，这个过程称为加密E为加密算法，K为密钥。E不同或K不同，密文C就不同典型的密码系统密码系统小游戏角色1——如何给你的朋友发一封由你自己加密的电子邮件？角色2——如何解密你朋友给你发来的加密邮件？网络与信息安全6对密码算法的基本要求加密能力强当密文或明文－密文对被截获时，破解密钥或明文在计算上是不可行的安全性不依赖于密码算法本身的保密，而依赖于密钥易于实现，使用方便对密码算法的基本要求网络与信息安全7古典密码（ClassicalCryptography）密码算法针对的基本操作对象是字符/字母方法——字符代换（Substitution）或字符置换（Permutation）1949年之前此类密码学还不是科学，而是艺术产生了一些密码算法和加密设备也出现简单的密码分析手段古典密码网络与信息安全8古典密码分类代换Substitution置换Transposition单表代换Monoalphabetic~多表代换Polyalphabetic~单字符单表代换多字符单表代换移位密码单表密码短语单表密码Playfair密码Beaufort密码Vigenère密码行变换密码栅格密码Hill密码仿射密码Autokey密码转子机凯撒密码一次性密码网络与信息安全9代换与置换代换密码算法（SubstitutionCipher）将明文中的每一个字符均被替换成另一个字符（密文字符）。接收者对密文做反向替换就可以恢复出明文置换密码算法（PermutationCipher）又称换位密码算法（TranspositionCipher）：改变明文中各个字母的位置次序，但明文字母（的出现及出现次数）保持不变网络与信息安全10代替密码单表密码算法（MonoalphabeticCipher)密码表仅1个——固定任何明文加密、密文解密均使用同一个密码表加密明文中相同的字母必然被加密成相同的密文字母网络与信息安全11代替密码多表密码算法（PolyalphabeticCipher)密码表多个——不固定一条明文加密和解密同时使用多个密码表明文中两个相同的字母可能被加密成不同的密文字母网络与信息安全12提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全13凯撒密码恺撒密码（CaesarCipher）JuliusCaesar发明，是已知最早的代换密码明文字母用其后的第三个字母代替，作为其密文字母，即，将明文字母表循环左移三位作为密码表网络与信息安全14两个字母表明文字母表P＝{p0,p1,…,p25}密文字母表C＝{C0,C1,…,C25}基本型凯撒密码等于如下变换明文字母表密文字母表明文表和密文表共同构成密钥加密解密凯撒密码网络与信息安全15让每个字母对应一个数值则基本型凯撒密码可以表示为加密：Ci=E(pi)=(pi+3)mod26解密：pi=D(Ci)=(Ci3)mod26密钥数量：1凯撒密码网络与信息安全16凯撒密码凯撒密码实例明文：meetmeaftertheparty密文：PHHWPHDIWHUWKHSDUWB网络与信息安全17凯撒密码特点极为简单密钥数为1，极其脆弱网络与信息安全18提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全19移位密码（ShiftCipher）明文字母用其后的第k个字母代替，作为其密文字母，即，将明文字母表循环左移k位作为密码表明文字母用任一个密文字母代替，即，明文字母表的任一个排列均构成一个对应的密码表加密：Ci=E(pi)=(pi+k)mod26解密：pi=D(Ci)=(Cik)mod26移位密码网络与信息安全20移位密码移位密码网络与信息安全21例如，k=5明文字母表：密文字母表：密钥数量：25明文密文移位密码网络与信息安全22特点非常简单密钥数为25，仍非常脆弱移位密码网络与信息安全23提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全24单表密码（MonoalphabeticCipher）明文字母用任一个密文字母代替，即，明文字母表的任一个全排列均构成一个对应的密码表加密：Ci=E(pi)=(pi+ki)mod26解密：pi=D(Ci)=(Ciki)mod26当pipj有CiCj,ki,kj=0,1,2,…25例：明文字母表：密文字母表：ki:13172124……单表密码abcdefghijklmnopqrstuvwxyzNSXCHMRWBGLQVAFKPUZEJOTYDI网络与信息安全25密钥数量：26!=403,291,461,126,605,635,584,000,000≈4×1026=400亿亿亿特点密钥数极大，安全性好密钥无规律，使用不便单表密码网络与信息安全26提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全27短语密码短语密码（KeywordCipher）是单表密码的一种实用形式引入一个关键词（短语）来构造明文字母表的一个排列，从而构成对应的密码表密码表构造方法1指定一个关键词（词组、句子…）去除关键词中的重复字母和空格，前置于密码表将剩余的字母依次按序后置于密码表密钥数量：26!（≈4×1026=400亿亿亿）网络与信息安全28实例关键词：GUANGZHOUBAIYUNSHAN去重前置：GUANZHOBIYS剩余后置：TVWXCDEFJKLMPQR明文字母表：密文字母表：abcdefghijklmnopqrstuvwxyzGUANZHOBIYSTVWXCDEFJKLMPQR短语密码网络与信息安全29短语密码密码表构造方法2指定一个关键词，去重复、空格，按行排阵将剩余的字母依次继续按行排阵阵的各列构成密码表例：关键词=COLLEGE阵：明文字母表密文字母表短语密码网络与信息安全30提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全31仿射密码仿射密码（AffineCipher）用仿射变换构造密码表（密码表便于记忆）密码表两个字母表明文字母表P＝{p0,p1,…,pn-1}密文字母表C＝{C0,C1,…,Cn-1}引入两个参数、，使明文字母P用字母aP+b代替，作为其密文字母加密：Ci=E(pi)=(pi+)modn解密：pi=D(Ci)=1(Ci)modn网络与信息安全32仿射密码实例取参数=5,=8明文=AFFINECIPHER密文=IHHWVCSWFRCP明文AFFINECIPHERpi055813428157417(5pi+8)83333487328184883432893(5pi+8)mod26877222121822517215CiIHHWVCSWFRCP网络与信息安全33仿射密码提示仿射加密函数要求和n互素，即gcd(,n)=1，否则，(pi+)modn就不是一个单射函数当=1、=3时，仿射密码就是著名的凯撒密码在解密时，需求解在有限域Zn上的乘法逆元1Zn，这可由扩展欧几里得算法求解Z26上所有与26互素的元素的乘法逆元：网络与信息安全34提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全35对单表代换密码的攻击两种典型的攻击直接攻击文本•方法——频度分析直接攻击密钥•方法——暴力破解（穷举破解）两种攻击联合使用或单独使用可一举破解单表代换密码网络与信息安全36直接攻击文本——频度分析9世纪阿尔-金迪:《关于破译加密信息的手稿》西文语言的独到特征文章中字母的出现频度有统计规律：元音字母频度高对单表代换密码的攻击网络与信息安全37频度分析的步骤1.统计密码字母的频度2.排序3.按照已知频度分布替换密文字母对单表代换密码的攻击网络与信息安全38密文频度分析h:可能是e,a,i,o…尝试he,da,li,ro,……结果密文:明文:频度分析攻击：实例网络与信息安全39直接攻击密钥——暴力破解前提——已知采用的是代换密码暴力破解的要点尝试所有可能的密码表（移位密码：最多仅需尝试25次）暴力破解的步骤1.选择一个密码表2.作逆代换3.检查逆代换后的文本是否有意义，有则结束，否则换另一个密码表，进入步骤2对单表代换密码的攻击网络与信息安全40实例密文明文对单表代换密码的攻击网络与信息安全41本质选取字母表的一个全排列作为对称密钥密钥数量26!（41026）单表代换密码：小结网络与信息安全42提纲概述单表代换算法单符号代换算法•凯撒密码•移位密码•单表密码•短语密码•仿射密码攻击方法小结网络与信息安全43特征代换固定——明文字符的代换字符固定位置相同——密文字符与明文字符的位置相同优点简单——得到密文所需的计算量小缺点继承——密文继承了明文的统计特性（频率…）跟随——明文字符的跟随关系反映在密文中单字符代换算法：小结网络与信息安全44存在多种不同的破解途径攻击密文——频度分析攻击密钥——穷举密钥……改进思路：多角度同时抵御针对频度分析——使频度呈现“均匀分布”针对穷举密钥——增大密钥空间……如何做到？代换密码算法：如何改进？网络与信息安全451.如何解密用短语代换密码的密文？2.如何代换密码加密中文？3.对于本次给出的四种代换密码，指出它们是沿着什么思路改进的？进阶问题网络与信息安全461.生成26个字母表的一个全排列，画出计算机程序的流程图。2.生成短语代换密码的一个密码表，画出计算机程序的流程图。3.画出用短语代换密码加密明文和解密密文的计算机程序流程图。4.选取一个代换密码，利用邮件、微博或微信与你的朋友进行一次秘密通信。请一位第三方同学尝试破解密文，根据破解结果评价你选取的代换密码。调换角色，重做。课后作业网络与信息安全47单字母密码单表代换密码移位（shift）密码、乘数（multiplicative)密码仿射（affine)密码、多项式（Polynomial)密码密钥短语（KeyWord)密码多表代换密码维吉尼亚（Vigenere)密码博福特（Beaufort）密码滚动密钥(running-key)密码弗纳姆(Vernam)密码转子机(rotormachine)