对称密码-- --古典密码

第1页共20页第二讲对称密码----古典密码一、内容提要1.为什么需要密码2.基本的概念和术语3.密码学的历史4.传统加密的古典技术---代替密码---置换密码为什么需要密码1.信息的存储：在公开的地方2.信息的交换：使用非隐秘介质3.信息的传输：通过不安全信道基本概念1.密码学(Cryptology)：是研究信息系统安全保密的科学。2.密码编码学(Cryptography)：主要研究对信息进行编码（压缩、保密和纠错），实现对信息的隐蔽。3.密码分析学(Cryptanalytics)：主要研究加密消息的破译或消息的伪造。基本术语1.消息被称为明文(Plaintext)。用某种方法伪装消息以隐藏它的内容的过程称为加密(Encryption)，被加密的消息称为密文(Ciphertext)，而把密文转变为明文的过程称为解密(Decryption)。2.对明文进行加密操作的人员称作加密员或密码员(Cryptographer)。3.密码算法(CryptographyAlgorithm)：是用于加密和解密的数学函数。4.密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)。5.所传送消息的预定对象称为接收者(Receiver)。第2页共20页6.接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm).二、传统密码体制1、凯撒密表•2）加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey)。3）加密通信的模型Y加密机Alice解密机Bob密钥源Oscar安全信道XXK第3页共20页密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。4.密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法eK∈E和相应的解密算法dK∈D，使得eK：PC和dK：CP分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。5.密码算法分类-i按照保密的内容分：1）受限制的（restricted)算法：算法的保密性基于保持算法的秘密。2）基于密钥（key-based)的算法：算法的保密性基于对密钥的保密。6.密码算法分类-ii基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher)：加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)。公开密钥算法用一个密钥进行加密，而用另一个进行解密。其中的加密密钥可以公开，又称公开密钥（publickey)，简称公钥。解密密钥必须保密，又称私人密钥（privatekey)私钥，简称私钥。7、密码算法分类-iii1）按照明文的处理方法：分组密码（blockcipher)：将明文分成固定长度的组，每个分组都用相同的密钥进行加密产生相同、输出也是固定长度的密文。第4页共20页流密码（streamcipher)：又称序列密码。序列密码每次加密一位或一字节的明文，然后用相关但不同密钥加密产生相应的密文，相同的明文分组由于在明文序列中的位置不同对应的密文不同，也可以称为流密码。序列密码是手工和机械密码时代的主流。密码学的历史密码学的起源和发展(1)三个阶段：1）1949年之前，密码学是一门艺术；2）1949～1975年，密码学成为科学；3）1976年以后，密码学的新方向——公钥密码学。密码学的起源和发展(2)1949年之前：古典密码（classicalcryptography)密码学还不是科学，而是艺术。出现一些密码算法和加密设备。密码算法的基本手段(substitution&permutation)出现，针对的是字符。简单的密码分析手段出现。密码学的起源隐写术(steganography)：通过隐藏消息的存在来保护消息。1）隐形墨水；2）字符格式的变化；3）图像Example-1•(象形文字的修改)ModifiedHieroglyphics,c.1900B.C.密码学的第一个例子是对标准书写符号的修改第5页共20页例如：古埃及法老坟墓上的文字思想：代替(substitution)Example-2•CaesarCipher,c.50B.C.ABCDEFG……XYZDEFGHIJ……ABC明文:Caesarcipherisashiftsubstitution密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQExample-3用布或羊皮纸缠在竿上写字、奴隶的头剃光，将消息刺在头上，等头发长好后上路等等。密码学的起源和发展(3)•1976年以后：第6页共20页1976年Diffie&Hellman提出了不对称密钥密码1977年Rivest，Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法，公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！密码分析假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：1）唯密文攻击：Oscar具有密文串y。2）已知明文攻击：Oscar具有明文串X和相应的密文Y。3）选择明文攻击：Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。4）选择密文攻击：Oscar可暂时接近密码机，可选择密文串y，并构造出相应的明文x。这一切的目的在于破译出密钥或密文。密码破译•密码破译的原则：遵循观察与经验；•方法：采用归纳与演绎；•步骤：分析、假设、推测和证实；•三大要素：密文加密机Alice解密机Bob加密密钥Oscar明文X解密密钥第7页共20页–语言的频率特征：e–连接特征：q…u,Iex,–重复特征：th,tion,tious密码算法的安全性1）无条件安全（Unconditionallysecure）无论破译者有多少密文，他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。2）计算上安全（Computationallysecure）破译的代价超出信息本身的价值；破译的时间超出了信息的有效期；对称密码分析的两个基本方法1）穷举法(ExhaustiveAttackmethod)，又称为强力法(Brute-forcemethod).。完全试凑法(completetrial-and–errormethod)；–这是对截获的密文依次用各种可能的密钥破译。–对所有可能的明文加密直到与截获的密文一致为止。2）分析法–系统分析法（统计分析法）：利用明文的统计规律–确定性分析法对称密码的两个基本运算1）代替(Substitution)古埃及的原始密码（左方是密文，右方是相应的明文）2）置换(Permutation)古典密码第8页共20页基于字符的密码1）代替密码（substitutioncipher)：就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。（代替规则、密文所用字符、明文中被代替的基本单位）2）置换密码(permutationcipher)，又称换位密码（transpositioncipher)：明文的字母保持相同，但顺序被打乱了。代替密码•简单代替密码（simplesubstitutioncipher)，又称单字母密码（monoalphabeticcipher)：明文的一个字符用相应的一个密文字符代替，而且密文所用的字符与一般的明文所用字符属同一语言系统。•多字母密码（ployalphabeticcipher)：明文中的字符映射到密文空间的字符还依赖于它在上下文中的位置。多字母代换密码可以用矩阵变换方便地描述多字母代换密码，有时又称起为矩阵变换密码。单字母密码单表代换密码–移位（shift）密码–密钥短语（KeyWord)密码–任意的单表代替密码1、移位密码算法设P=C=K=Z/(26)，对k∈K，定义ek(x)=x+k(mod26)=y∈C同时dk(y)=y-k(mod26)实际算法为：∀x∈P有e3（x）=x+3(mod26)=y第9页共20页同时有，d3(y)=y-3(mod26)移位密码分析给定加密的消息：PHHWPHDIWHUWKHWRJDSDUWB1）加解密算法已知2）可能尝试的密钥只有25个(不包括0)通过强力攻击得到明文：meetmeafterthetogaparty.移位密码很容易受到唯密文攻击。2、任意的单表代替密码算法例：置换π的对应关系为：ABCDEFGHIJKLMNOPQRSTUVWXYZIDMEFZOAPHXBSCQRLTUYJVNWGK试用单表代换密码以π为密钥对明文消息UNIVERSITY加密，然后对密文解密。加密：π（u）π（n）π（i）π（v）π（e）π（r）π（s）π（i）π（t）π（y）=JCPVFTUPYGπ-1的对应关系：ABCDEFGHIJKLMNOPQRSTUVWXYZHLNBDEYJAUZQCWGIOPMRSVXKTF构造方法：以西文单词为密钥的换字表–例如：取atmosphere为密钥，首先找出其中发生重复的字母，去掉重复字母第10页共20页e，成为atmospher.–其次，字母一共10个，从第11个字母开始，用atmosphere按顺序进行代替配置。–然后把其余17个字母按自然顺序接在后面。以atmosphere为密钥的换字表密码破译密码设计是利用数学来构造密码；密码分析除了依靠数学、工程背景、语言学知识外，还要靠经验、统计、测试、眼力、直觉判断力…有时还要靠点运气；密码破译的原则：遵循观察与经验；方法:采用归纳与演绎；步骤:分析、假设、推测和证实；1、单表替换密码的破译语言的统计特性：–语言的频率特征–连接特征–重复特征1）频率特征•在各种语言中，各个字母的使用次数是不一样的，有的偏高，有的偏低，这种现象叫偏用现象。•对英文的任何一篇文章，一个字母在该文章中出现的次数称作这个字母（在这篇文章中）的频数。•一个字母的频数除以文章的字母总数，就得到字母的使用频率。英文字母的普遍使用频率第11页共20页美国密码学家W.F.Friedman在调查了大量英文资料后，得出英文字母的普遍使用规律。英文单字母的相对频率表字母频率字母频率字母频率R0.0677I0.0627Z0.0008Q0.0012H0.0528Y0.0199P0.0199G0.0199X0.0017O0.0797F0.0289W0.0149N0.0707E0.1304V0.0092M0.0249D0.0378U0.0249L0.0339C0.0279T0.1045K0.0042B0.0139S0.0607J0.0013A0.0856第12页共20页特殊的特征开头结尾特征：有些文章的开头和结尾受到固定格式的限制；有时文章中间的某些特定部位，某些字母也会出现较高的使用频率。频度最高的前30个双字母•THHEINERANREEDONESST•ENATTONTHANDOUEANGAS•ORTIISETITARTESEHIOF频度最高的前20个三字母•THEINGANDHEREREENTTHANTHWASETHFORDTHHATSHEIONINTHISSTHERSVER其它频率特征①the的使用频率最高，是ING的三倍，若把the去掉，t在第II类中排在最后，h会降为第III类，th和he也不是常出现的字母组了；②一半的单词以esdt结尾；③一半的