密码学基础古典密码学.ppt
Page 2密码学的起源和发展密码学的起源和发展密码学有着悠久而神秘的历史，人们很难对密码学的起始时间给出准确的密码学有着悠久而神秘的历史，人们很难对密码学的起始时间给出准确的定义。定义。三个阶段：三个阶段：-1949年之前密码学是一门艺术年之前密码学是一门艺术-19491975年密码学成为科学年密码学成为科学-1976年以后密码学的新方向年以后密码学的新方向公钥密码学公钥密码学 3第第1 1阶段阶段从古代到从古代到19491949年年这一时期可以看作是科学密码学的前夜时期，这阶段的密码技术可以说是这一时期可以看作是科学密码学的前夜时期，这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明。设计和分析，而不是推理和证明。主要特点：数据的安全基于算法的保密。主要特点：数据的安全基于算法的保密。4第第1阶段阶段从古代到从古代到19491949年年-隐写术（公元前440年出现在古希腊战争中）。-当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。5第第1 1阶段阶段从古代到从古代到19491949年年密码学用于通信的另一个记录是斯巴达人于公元前密码学用于通信的另一个记录是斯巴达人于公元前400年应用年应用Scytale加密加密工具在军官间传递秘密信息。工具在军官间传递秘密信息。-Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮纸，将要保密的信息写在羊皮纸上。解下羊皮纸，上面的消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。6第第1 1阶段阶段从古代到从古代到19491949年年-我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面意境，而不会去注意或很难发现隐藏其中的“话外之音”。7第第1 1阶段阶段从古代到从古代到19491949年年-到了20世纪20年代，随着机械和机电技术的成熟，以及电报和无线电需求的出现，引起了密码设备方面的一场革命发明了转轮密码机（简称转轮机，Rotor），转轮机的出现是密码学发展的重要标志之一。82020世纪早期密码机世纪早期密码机9关于二战的密码小插曲关于二战的密码小插曲美国在美国在1942年制造出了世界上第一台计算机年制造出了世界上第一台计算机.二战期间二战期间,日本采用的最高级别的加密手段是采用日本采用的最高级别的加密手段是采用M-209转轮机械加密改进型转轮机械加密改进型紫密紫密,在手工计算的在手工计算的情况下不可能在有限的时间破解情况下不可能在有限的时间破解,美国利用计算机美国利用计算机轻松地破译了日本的紫密密码轻松地破译了日本的紫密密码,使日本在中途岛海使日本在中途岛海战中一败涂地战中一败涂地,日日本海军的主力损失殆尽本海军的主力损失殆尽.（现代计（现代计算机每秒可执行万亿次）算机每秒可执行万亿次）1943年年,在获悉山本五十六将于在获悉山本五十六将于4月月18日乘中型轰日乘中型轰炸机，由炸机，由6架战斗机护航，到中途岛视察时架战斗机护航，到中途岛视察时,罗斯罗斯福总统亲自做出决定截击山本福总统亲自做出决定截击山本,山本乘坐的飞机在山本乘坐的飞机在去往中途岛的路上被美军击毁去往中途岛的路上被美军击毁,山本坠机身亡山本坠机身亡,日本日本海军从此一蹶不振海军从此一蹶不振.密码学的发展直接影响了二战密码学的发展直接影响了二战的战局的战局!10第第2 2阶段阶段从从19491949年到年到19751975年年19491949年年ShannonShannon发表了题为发表了题为保密通信的信息理论保密通信的信息理论的著的著名论文，把密码学置于坚实的名论文，把密码学置于坚实的数学基础之上，标志着密码学数学基础之上，标志着密码学作为一门学科的形成，这是密作为一门学科的形成，这是密码学的码学的第一次飞跃第一次飞跃。主要特点：数据安全基于密钥主要特点：数据安全基于密钥而不是算法的保密。而不是算法的保密。11第第3 3阶段阶段从从19761976年至今年至今19761976年，年，W WDiffieDiffie和和M MHellmanHellman在发在发表的文章表的文章“密码学的新动向密码学的新动向”中提出了公中提出了公开密钥的思想，从而开创了公钥密码学开密钥的思想，从而开创了公钥密码学的新纪元，导致了密码学上的一场革命，的新纪元，导致了密码学上的一场革命，这是密码学的这是密码学的第二次飞跃第二次飞跃。主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能。12第第3 3阶段阶段从从19761976年至今年至今受受DiffieDiffie和和HellmanHellman的思想启迪，各的思想启迪，各种公钥密码体制被提出，特别是种公钥密码体制被提出，特别是1978年年RSA公钥密码体制的出现，成为公公钥密码体制的出现，成为公钥密码的杰出代表，并成为事实标准，钥密码的杰出代表，并成为事实标准，在密码学史上是一个在密码学史上是一个里程碑里程碑。13 古典密码密码学基本概念几种典型的古典密码体制古典密码的统计分析141.1 1.1 密码学的基本概念密码学的基本概念密码学（密码学（cryptology）作为数学的一个分支，是密码编码学和密码分析作为数学的一个分支，是密码编码学和密码分析学的统称学的统称。-使消息保密的技术和科学叫做密码编码学密码编码学（cryptography)-破译密文的科学和技术就是密码分析学密码分析学（cryptanalysis）151.1 密码学的基本概念密码学的基本概念密码学的基本目的是面对攻击者密码学的基本目的是面对攻击者Oscar，在被称为，在被称为Alice和和Bob的通信双方之间应用不安全的信道进的通信双方之间应用不安全的信道进行通信时，保证通信安全。行通信时，保证通信安全。明文明文密文密文明文明文AliceAliceBobBobOscar161.1 密码学的基本概念密码学的基本概念密码体制的定义密码体制的定义定义定义1.1.1 1.1.1 密码体制：密码体制：密码体制的构成包括以下要素：密码体制的构成包括以下要素：（1 1）M M：明文消息空间：明文消息空间，表示所有可能的明文组成的有限集。，表示所有可能的明文组成的有限集。（2 2）C C：密文消息空间：密文消息空间，表示所有可能的密文组成的有限集。，表示所有可能的密文组成的有限集。（3 3）K K：密钥空间：密钥空间，表示所有可能的密钥组成的有限集。，表示所有可能的密钥组成的有限集。（4 4）E E：加密算法集合：加密算法集合。（5 5）D D：解密算法集合：解密算法集合。171.1 密码学的基本概念密码学的基本概念明文明文密文密文明文明文AliceAliceBobBob加密密匙加密密匙解密密匙解密密匙保密通信的一般机制181.1 密码学的基本概念密码学的基本概念密码体制的分类密码体制的分类 对称密匙密码系统Symmetric Key Cryptosystem 加密密钥=解密密钥 非对称密匙密码系统Asymmetric Key Cryptosystem 加密密钥解密密钥 钥匙是保密的 加密密钥为公钥（Public Key）解密密钥为私钥（Private Key）191.1 密码学的基本概念密码学的基本概念201.1 密码学的基本概念密码学的基本概念211.2 古典密码体制古典密码体制1、棋盘密码2、移位密码3、代换密码4、维吉尼亚密码5、仿射密码6、置换密码221 棋棋盘盘密密码码棋盘密码是公元前2世纪前后由希腊作家Polybius提出来的，在当时得到了广泛的应用。棋盘密码的密钥如下表所示：123451ABCDE2FGHI/JK3LMNOP4QRSTU5VWXYZ23123451qwert2yui/jop3asdfg4hklzx5cvbn m242 移位密移位密码码移位密码的加密对象为英文字母，移位密码采用对明文消息的每一个英文字母向前推移固定位的方式实现加密。换句话说，移位密码实现了26个英文字母的循环移位。移位密码中，当取密钥k=3时，得到的移位密码称为凯撒密码，因为该密码体制首先被Julius Caesar所使用。25ABCDEFGHIJKLM00 01 02 03 04 05 06 07 08 09 10 1112NOPQRSTUV W XYZ13 14 15 16 17 18 19 20 21 22 23 24 25263 代代换换密密码码定定义义1.2.3 代代换换密密码码体制：体制：令是上所有可能置换构成的集合。对任意的置换这里和互为逆置换。，定义：27ABCDEFGHIJKLMqwertyuiopasdNOPQRSTUVWXYZfghjklzxcvbnm28294 维维吉尼吉尼亚亚密密码码单表代换密码-移位密码、仿射密码等等多表代换密码-维吉尼亚密码（Vigenre cipher），它是由法国人Blaise de Vigenre在16世纪提出的。定定义义1.2.4 维维吉尼吉尼亚亚密密码码体制：体制：令是一个正整数，。对任意的密钥 定义:如果已经在26个英文字母和之间建立了一一对应的关系，则每一个密钥都相当于一个长度为m的字母串，被称为密钥字。305 仿仿射密射密码码仿射密码是移位密码的一个推广，其加密过程中不仅包含移位操作，而且使用了乘法运算。令密钥空间为定义：对任意密钥定定义义1.2.5 仿射密仿射密码码的密的密码码体制体制31Mod 2632明文字符明文字符对应对应的整数的整数为为仿射密仿射密码码的密的密钥为钥为 密文密文为为：336 置置换换密密码码通过重新排列消息中元素的位置而不改变元素本身的方式，对一个消息进行变换。这种加密机制称为置换密码(也称为换位密码)。定定义义1.2.6 置置换换密密码码体体制制令是一个正整数，K是 上所有可能置换构成的集合。对任意的，定义：其中和 互为上的逆置换，为分组长度。对于长度大于分组长度的明文消息，可对明文消息先按照长度进行分组，然后对每一个分组消息重复进行同样的置乱加密过程，最终实现对明文消息的加密。3435假设明文为：bcMod 26=密文为：密钥为：1*=7 -8 -3 11 7 -8 -3 111 2Mod 26=17 2217 22=1 2明文为：361.3 1.3 古典密码统计分析古典密码统计分析根据密根据密码码分析的分析的Kerckhoffs原原则则：攻：攻击击者知道所用的加密算者知道所用的加密算法的内部机理，不知道的法的内部机理，不知道的仅仅仅仅是加密算法所采用的加密密是加密算法所采用的加密密钥钥常用的密常用的密码码分析攻分析攻击击分分为为以下四以下四类类：1.惟密文攻惟密文攻击击(Ciphertext only attack)2.已知明文攻已知明文攻击击(Know plaintext attack)3.选择选择明文攻明文攻击击(Chosen plaintext attack)4.选择选择密文攻密文攻击击（Chosen ciphertext attack）：）：37几种古典密几种古典密码码体制体制4种攻种攻击击手段手段基本概念基本概念
