chap2-古典密码

1、Chap2 古典密码古典密码密码学的发展历史n三个阶段：古代加密方法、古典密码和近代密码。n1.古代加密方法（手工阶段）古代加密方法（手工阶段）n从某种意义上说，战争是科学技术进步的催化剂。人类自从有了战争，就面临着通信安全的需求，密码技术源远流长。古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。n公元前400年，斯巴达人就发明了“塞塔式密码”，即把长条纸螺旋形地斜绕在一个多棱棒上，将文字沿棒的水平方向从左

2、到右书写，写一个字旋转一下，写完一行再另起一行从左到右写，直到写完。解下来后，纸条上的文字消息杂乱无章、无法理解，这就是密文,但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。这是最早的密码技术。nSpartanScytale,c.500B.C.塞塔式密码斯巴达人用于加解密的一种军事设备，发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想：置换（permutation)n我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。比如：我画蓝江水悠悠，爱晚亭枫叶愁

3、。秋月溶溶照佛寺，香烟袅袅绕轻楼n2.古典密码（机械阶段）古典密码（机械阶段）n古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。n3.近代密码（计算机阶段）近代密码（计算机阶段）密码形成一门新的学科是在20世纪70年代，快速电子计算机和现代数学方法一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利

4、用电子计算机可以设计出更为复杂的密码系统。目目 录录1.密码学的起源、发展和现状密码学的起源、发展和现状2.密码学基本概念密码学基本概念3.典型几种古典密码技术典型几种古典密码技术密码学发展阶段密码学发展阶段19491949年之前年之前 密码学是一门艺术密码学是一门艺术1949194919751975年年 密码学成为科学密码学成为科学19761976年以后年以后 密码学的新方向密码学的新方向公钥密码学公钥密码学第第1阶段古典密码阶段古典密码 密码学还不是科学密码学还不是科学, ,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段出现出现

5、，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现 主要特点：数据的安全基于算法的保密主要特点：数据的安全基于算法的保密第第1阶段古典密码阶段古典密码Phaistos圆盘，一种直径约为圆盘，一种直径约为160mm的的Cretan-Mnoan粘土圆盘，始于公元前粘土圆盘，始于公元前17世纪。表面有明世纪。表面有明显字间空格的字母，至今还没有破解。显字间空格的字母，至今还没有破解。20世纪早期密码机世纪早期密码机第第1阶段古典密码阶段古典密码1883年年Kerchoffs第一次明确提出了编码的原则：加第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安

6、密算法应建立在算法的公开不影响明文和密钥的安全。全。这一原则已得到普遍承认，成为判定密码强度的衡这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为量标准，实际上也成为古典密码古典密码和近代密码的分界和近代密码的分界线。线。 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 相关技术的发展相关技术的发展19491949年年ShannonShannon的的“The Communication Theory of Secret The Communication Theory of Secret SystemsSystems” 19671967年年David K

7、ahnDavid Kahn的的The CodebreakersThe Codebreakers1971-731971-73年年IBM WatsonIBM Watson实验室实验室的的Horst FeistelHorst Feistel等几篇技术报告等几篇技术报告主要特点：主要特点：数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密 第第2阶段阶段 1949197519761976年：年：Diffie & Hellman Diffie & Hellman 的的 “New Directions in New Directions in CryptographyCryptograp

8、hy” 提出了不对称密钥密提出了不对称密钥密19771977年年Rivest,Shamir & AdlemanRivest,Shamir & Adleman提出了提出了RSARSA公钥算法公钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法主要特点：主要特点：公钥密码使得发送端和接收端无密钥传输的保密公钥密码使得发送端和接收端无密钥传输的保密通信成为可能通信成为可能第第3阶段阶段 197619771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“Post DESPost DES”算法算法, ,如如IDEA,RCx,CA

9、STIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Rijndael,RC6, MARS, Twofish, SerpentTwofish, Serpent等出现等出现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者第第3阶段阶段 1976目目 录录1.密码学的起源、发展和现状密码学的起源、发展和现状2.密码学基本概念密码学基本概念3.典型几种古典密码技术典型几种古典密码技术基本概念基本概念密码学密码学(Cryptology): 是研究信息系统安全是研究信息系统安全保密的

10、科学保密的科学.密码编码学密码编码学(Cryptography): 主要研究对信主要研究对信息进行编码息进行编码,实现对信息的隐蔽实现对信息的隐蔽.密码分析学密码分析学(Cryptanalytics):主要研究加密主要研究加密消息的破译或消息的伪造消息的破译或消息的伪造.明文明文（Plaintext）：消息的初始形式；）：消息的初始形式；密文密文（CypherText）：加密后的形式）：加密后的形式记：记：明文记为明文记为P且且P为字符序列，为字符序列， P=P1,P2,Pn密文记为密文记为C, C=C1,C2,Cn明文和密文之间的变换记为明文和密文之间的变换记为 C=E(P)及及P=D(C)

11、其中其中 C表示密文，表示密文，E为加密算法；为加密算法；P为明文，为明文，D为解密算法为解密算法我们要求密码系统满足：我们要求密码系统满足：P=D(E(P)基本概念基本概念n加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥 需要密钥的加密算法，记为：需要密钥的加密算法，记为：C=E(K,P),即密文消息同时即密文消息同时依赖于初始明文和密钥的值。实际上，依赖于初始明文和密钥的值。实际上，E是一组加密算法，是一组加密算法，而密钥则用于选择其中特定的一个算法。而密钥则

12、用于选择其中特定的一个算法。 加密与解密的密钥相同，即：加密与解密的密钥相同，即：P=D(K,E(K,P) 加密与解密的密钥不同，则：加密与解密的密钥不同，则：P=D(KD,E(KE,P)基本概念基本概念常规加密简化模型常规加密简化模型 加密算法足够强大：仅知密文很难破译出明文加密算法足够强大：仅知密文很难破译出明文 基于密钥的安全性，而不是基于算法的安全性：基于密基于密钥的安全性，而不是基于算法的安全性：基于密文和加文和加/解密算法很难破译出明文解密算法很难破译出明文 算法开放性：开放算法，便于实现算法开放性：开放算法，便于实现常规加密的安全性常规加密的安全性常规加密系统的模型常规加密系统的

13、模型密码体系是一个五元组密码体系是一个五元组（P,C,K,E,D)满足条件：满足条件： （1）P是可能明文的有限集；（明文空间）是可能明文的有限集；（明文空间） （2）C是可能密文的有限集；（密文空间）是可能密文的有限集；（密文空间） （3）K是一切可能密钥构成的有限集；（密钥空间）是一切可能密钥构成的有限集；（密钥空间） （4）任意）任意k K，有一个加密算法，有一个加密算法 和相应的解密和相应的解密算法算法 ，使得，使得 和和 分别为加分别为加密解密函数，密解密函数， 满足满足dk(ek(x)=x ，这里，这里 x P。密码体系形式化描述密码体系形式化描述EekDdkCPek:PCdk:

14、保密内容保密内容 密钥数量密钥数量 明文处理的方式明文处理的方式密码编码系统分类密码编码系统分类 受限制的（受限制的（restricted)算法算法 算法的保密性基于保持算法的秘密（算法的保密性基于保持算法的秘密（古典古典） 基于密钥（基于密钥（key-based)的算法的算法 算法的保密性基于对密钥的保密（算法的保密性基于对密钥的保密（近代：对称近代：对称+非对称非对称）保密内容保密内容 对称密码算法（对称密码算法（symmetric cipher) 加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个 又称秘密密钥算法或单

15、密钥算法又称秘密密钥算法或单密钥算法 非对称密钥算法（非对称密钥算法（asymmetric cipher) 加密密钥和解密密钥不相同，从一个很难推出另一个加密密钥和解密密钥不相同，从一个很难推出另一个 又称公开密钥算法（又称公开密钥算法（public-key cipher) 公开密钥算法用一个密钥进行加密公开密钥算法用一个密钥进行加密, 而用另一个进行解密而用另一个进行解密 其中的加密密钥可以公开其中的加密密钥可以公开,又称公开密钥（又称公开密钥（public key)，简称公钥。解密密，简称公钥。解密密钥必须保密钥必须保密,又称私人密钥（又称私人密钥（private key)私钥，简称私钥私

16、钥，简称私钥密钥数量密钥数量 分组密码（分组密码（block cipher) 将明文分成固定长度的组，用同一密钥和算法对每一将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。块加密，输出也是固定长度的密文。 流密码（流密码（stream cipher) 又称序列密码。序列密码每次加密一位或一字节的又称序列密码。序列密码每次加密一位或一字节的明文。明文。明文处理方式明文处理方式密码分析密码分析试图破译单条消息试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译试图识别加密的消息格式，以便借助直接的解密算法破译后续的消息后续的消息试图找到加密算法中的普遍缺

17、陷（无须截取任何消息）试图找到加密算法中的普遍缺陷（无须截取任何消息）密码分析的条件与工具密码分析的条件与工具 已知加密算法已知加密算法 截取到明文、密文中已知或推测的数据项截取到明文、密文中已知或推测的数据项 数学或统计工具和技术数学或统计工具和技术 语言特性语言特性 计算机计算机 技巧与运气技巧与运气密码分析类型密码分析类型加密方案的安全性加密方案的安全性无条件安全：无论提供的密文有多少，如果由一个加密方无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的

18、算法除了一次一密的方案外，没有无条件安全的算法安全性体现在任意一条：安全性体现在任意一条：破译的成本超过加密信息的价值破译的成本超过加密信息的价值破译的时间超过该信息有用的生命周期破译的时间超过该信息有用的生命周期密钥搜索所需平均时间密钥搜索所需平均时间目目 录录1.密码学的起源、发展和现状密码学的起源、发展和现状2.密码学基本概念密码学基本概念3.典型几种古典密码技术典型几种古典密码技术 替代替代 置换置换 转子机转子机经典加密技术经典加密技术 明文的字母由其它字母或数字或符号代替明文的字母由其它字母或数字或符号代替 若该明文被视为一个比特序列，则替代涉及到用若该明文被视为一个比特序列，则替

19、代涉及到用密文比特模式代替明文比特模式密文比特模式代替明文比特模式替代（代替）替代（代替）代替密码n简单代替密码（简单代替密码（simple substitution cipher),又称又称单字母密码单字母密码（monoalphabetic cipher):明文的一个字符用相应的一个密明文的一个字符用相应的一个密文字符代替。文字符代替。恺撒密码恺撒密码破译以下密文：破译以下密文：wuhdwb lpsrvvleohTREATY IMPOSSIBLECi=E(Pi)=Pi+3加密算法：加密算法：字母表：字母表：(密码本）密码本） ABCDEFGHIJKLMNOPQRSTUVWXYZ defghi

20、jklmnopqrstuvwxyzabc恺撒密码恺撒密码(caesar cipher)破译以下密文：破译以下密文：wuhdwb lpsrvvleohTREATY IMPOSSIBLECi=E(Pi)=Pi+3加密算法：加密算法：字母表：字母表：(密码本）密码本）ABCDEFGHIJKLMNOPQRSTUVWXYZ（对应数字（对应数字0:a，1. 25:z)defghijklmnopqrstuvwxyzabc恺撒密码的改进恺撒密码的改进n已知加密与解密算法已知加密与解密算法nC=E(p)=(p+k)mod(26)np=D(C)=(C-k)mod(26)n25个可能的密钥个可能的密钥k，适用适用B

21、rute-ForceCryptanalysisn明文的语言是已知的且易于识别明文的语言是已知的且易于识别恺撒密码的特点恺撒密码的特点n单字母密码（简单替换技术）单字母密码（简单替换技术）n简单，便于记忆简单，便于记忆n缺点：结构过于简单，密码分析员只使用很缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构少的信息就可预言加密的整个结构其它单字母替换其它单字母替换n使用密钥使用密钥nkeyABCDEFGHIJKLMNOPQRSTUVWXYZkeyabcdfghijlmnopqrstuvwxznspectacularABCDEFGHIJKLMNOPQRSTUVWXYZspecta

22、ulrbdfghijkmnoqvwxyzn泄露给破译者的信息更少泄露给破译者的信息更少其它单字母替换其它单字母替换n对字母进行无规则的重新排列对字母进行无规则的重新排列E(i)=3*i mod 26ABCDEFGHIJKLMNOPQRSTUVWXYZadgjmpsvybehknqtwzcfilorux例：例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ0 02 24 46 68 81010121214

23、14A A B B C C D D E E F F G G H H I I J J K K L L M M N N O O P P Q Q R R S S T T U U V V W W X X Y Y Z Z频率频率密文字母频率密文字母频率对抗频率分析的办法n多字母密码（多字母密码（ployalphabetic cipher)：明文中多：明文中多个字母一起加密个字母一起加密n多表以一系列（两个以上）代换表依此对明文消多表以一系列（两个以上）代换表依此对明文消息的字母进行代换的方法。息的字母进行代换的方法。多字母密码多字母密码-PlayfairnPlayfair:将明文中的双字母组合作为一个单

24、元对待，并将这些单元转换为密文的双字母组合。n55变换矩阵: I与J视为同一字符C I P H ER A B D FG K L M N(cipher)O Q S T UV W X Y Zn加密规则:按成对字母加密1) 相同对中的字母加分隔符(如x)2) balloon ba lx lo on3) 同行取右边: he EC4) 同列取下边: dm MT5) 其他取交叉: kt MQ OD TRPlayfair举例n以前面的55变换矩阵(cipher)为例 C I P H ER A B D FG K L M N(cipher)O Q S T UV W X Y Z(1)balloon ba lx l

25、o on db sp gs ug(2)book bo ok rs qg(3)fill fi lx lx ae sp spPlayfair密码分析n字符出现几率一定程度上被均匀化n基于字母频率的攻击比较困难n依然保留了相当的结构信息多字母密码多字母密码：Hill密码（1929）n取m个连续的明文字母，并且用m个密文字母替代，如何替代由m个线性方程决定，每个字母对应一个数值(a=0, b=1, z=25)。Y=KX，K=YX-1nK是一个m*m矩阵,在Z/(26)上可逆,即存在K-1使得:KK-1 = I (在Z/(26)。模为26例子：当m=2时，明文元素x=(x1,x2),密文元素y=(y1,

26、y2)：(y1,y2)=(x1,x2)K若K=,可得K-1=若对明文july加密，它分成2个元素（j,u),(l,y),分别对应于（9,20）（9960,72140）（3,4）且（11,24）(12172,88168)（11,22）于是对july加密的结果为DELW。7381111231877381173811为了解密，Bob计算且因此，得到了正确的明文“july”)20,9(1123187)4,3()24,11(1123187)22,11(Hill密码特点n完全隐藏了字符(对)的频率信息n线性变换的安全性很脆弱，易被已知明文攻击击破。n对于一个mxm的hill密码，假定有m个明文-密文对，明

27、文和密文的长度都是m.可以把明文和密文对记为：模q算术-in同余：给定任意整数a和q，以q除a，余数是r，则可以表示为a=sq+r,0rq，其中s=a/q,表示小于a/q的最大整数。定义r为amodq的剩余，记为ramodq.若整数a和b有(amodq)=(bmodq)，则称a与b在modq下同余。对于满足r=a|a=sq+r,sZ的整数集称为同余类。模运算有下述性质：（1）若q|(a-b)，则abmodq（2）(amodq)=(bmodq)意味abmodq（3）abmodq等价于bamodq（4）若abmodq且bcmodq，则acmodq模q算术-iin模算术（ModularArithma

28、tic)在modq的q个剩余类集0，1，2，,q-1上可以定义加法和乘法运算如下:加法:(amodq)+(bmodq)=(a+b)modq乘法:(amodq)(bmodq)=(ab)modq多表加密-Vigenre ciphern是一种多表移位代替密码设d为一固定的正整数，d个移位代换表=（1，2,d)由密钥序列K（k1,k2,kd)给定，第i+td个明文字母由表i决定，即密钥ki决定ek(xi+td)=(xi+td+ki,)modq=ydk(yi+td)=(xi+td-ki)modq=x例子：q=26,x=polyalphabeticcipher,K=RADIO明文x=POLYALPHABE

29、TICCIPHER密钥k=RADIORADIORADIORADIO密文y=GOOGOCPKTPNTLKQZPKMFVigenre cipher-破译n依然保留了字符频率某些统计信息n重码分析法：间距是密钥长度整数倍的相同子串有相同密文，反过来，密文中两个相同的子串对应的密文相同的可能性很大。 a b c d e f g h i j k l m 000102 030405 060708 091011 12 n o p q r s t u v w x y z 131415 161718 192021 222324 25密钥: cryptographycryptographycr明文: yourpa

30、ckagereadyroomathree密文: AFSGIOI PG PGVernam密码n1918年，Gillbert Vernam建议密钥与明文一样长并且没有统计关系的密钥内容，他采用的是二进制数据: 加密：Ci = Pi Ki 解密 Pi = Ci Ki 核心：构造和消息一样长的随机密钥 总结总结n替换是密码学中有效的加密方法。本世纪上半叶用于外交替换是密码学中有效的加密方法。本世纪上半叶用于外交通信通信n破译威胁来自破译威胁来自n频率分布频率分布n重合指数重合指数n考虑最可能的字母及可能出现的单词考虑最可能的字母及可能出现的单词n重复结构分析及克思斯基方法重复结构分析及克思斯基方法n持

31、久性、组织性、创造性和运气持久性、组织性、创造性和运气 通过执行对明文字母的置换，取得一种类型完全通过执行对明文字母的置换，取得一种类型完全不同的映射，即置换密码。不同的映射，即置换密码。 若该明文被视为一个比特序列，则置换涉及到用若该明文被视为一个比特序列，则置换涉及到用密文比特模式代替明文比特模式密文比特模式代替明文比特模式置换置换n换位密码把明文按列写入,按行读出n密钥包含3方面信息: 行宽,列高,读出顺序key:4312567(先读第一列)plaintext:attackpostponeduntiltwoamxyzciphertext:TTNAAPTMTSUOAODWCOIXPETZn

32、完全保留字符的统计信息n使用多轮加密可提高安全性K K是一个是一个m m* *m m矩阵矩阵, ,在在Z/(26)上可逆上可逆, ,即存在即存在K K-1-1使得使得: :KKKK-1-1 = I ( = I (在在Z/(26) )对每一个对每一个k K, 定义定义ek(x)=xK (mod 26) 和和 dk(y)=yK-1 (mod 26)注：注：明文与密文都是明文与密文都是 m元的向量元的向量（x1, x2 , xm );(y1, y2,ym)，Z/(26)为同余类环为同余类环在这个环上的可逆矩阵在这个环上的可逆矩阵Amxm,是指行列式是指行列式detAmxm的值的值 Z*/(26),它为它为Z/(26)中中全体可逆元的集合。全体可逆元的集合。Z*/(26)= a Z/(26)|(a,26)=1，Z*/(26)=1,3,5,7,9,11,15,17,19,21,23,25这里的加密与解密仅仅用了置换，无代数运算这里的加密与解密仅仅用了置换，无代数运算例子：设例子：设m=6，取加密密钥，取加密密钥 1 2 3 4 5 63 5 1 6 4 2