古典密码学+(1).ppt

2020/5/27,Page:1,古典密码学,杨秋伟湖南大学计算机与通信学院,2020/5/27,Page:2,古典密码学组成,古典替换密码体制古典单码加密法古典多码加密法古典换位密码体制古典置换加密法,2020/5/27,Page:3,古典单码加密法：概述,单码加密是一种替换加密法，其中的每个明文只能被唯一的一个密文字母所替换。例一：在给定的加密法中，明文的字母“a”在密文中可能总是显示为“n”；例二(恺撒加密法)：将字母在字母表中的位置后移3位，即“a”到“d”，“b”到“e”，“z”到“c”。,2020/5/27,Page:4,古典单码加密法：关键词加密,恺撒加密法的分析：简单移位加密法通过尝试所有25个密钥就可以很容易破解，所以替代加密法应具有更多的密钥。关键词加密的构造选择一个关键词，如果该关键词有重复的字母，去除除第一次出现之外的所有相同字母。例如，候选关键词为“success”，则使用“suce”；将该关键词写在字母表的下方，并用字母表的其它字母按标准的顺序填写余下的空间。,2020/5/27,Page:5,古典单码加密法：关键词加密,例一：关键词加密关键词为“magicnet”字母表的描述形式abcdefghijklmnopqrstuvwxyzmagicnetbdfhjklopqrsuvwxyz明文：help，密文：tcho改进方案：允许关键词从字母表的任意位置开始。,2020/5/27,Page:6,古典单码加密法：关键词加密的分析,攻击者的优势和目标优势：攻击者知道加密法是关键词加密目标：试图发现关键词和明文可用的信息明文是标准的英语；所用加密法为关键词加密法；每个明文字母已被唯一的密文替代。,2020/5/27,Page:7,古典单码加密法：关键词加密的分析,语言的每个字母都有自身的特性，虽然采用了字母替换，但是特性依旧保持。例如，每个明文“t”被替换为“m”，那么在密文中，“m”将具有“t”的特性。两个有用的特性出现频率：例如，在标准英语中，出现频率最高的是字母“e”，而“x”和“z”则很少出现；字母的实际出现频率取决于具体文字的类型，科技文献的字母出现频率与文学文献有很大的不同；首选关联集：在标准英语中，多个字母常一起出现或不出现，例如，元音字母“a”、“i”和“o”互不相联。,2020/5/27,Page:8,古典密码学组成,古典替换密码体制古典单码加密法古典多码加密法古典换位密码体制古典置换加密法,2020/5/27,Page:9,古典多码加密法：概述,多码加密法是为了用来对付频率分析工具。多码加密法也是一种替换加密法。多码加密法的目的是通过用多个密文字母来替换同一个明文字母，从而消除字母的特性。经典的古典多码加密：Playfair密码、Hill密码、Vigenere密码,2020/5/27,Page:10,古典多码加密法：Vigenere密码,Vigenere密码是基于关键词的加密系统。Vigenere密码不同于单码关键词加密，它将关键词写在明文的上面，并不断重复书写，这样每个明文字母都与一个关键词的字母关联。例一：关键词为“hold”，那么关键词-明文的关联如下,2020/5/27,Page:11,古典多码加密法：Vigenere密码,Vigenere表,明文,密文,2020/5/27,Page:12,古典多码加密法：Vigenere密码,加密过程：给定一个密钥字母k和一个明文字母p，密文字母就是位于k所在的行与p所在的列的交叉点上的那个字母。解密过程：由密钥字母决定行，在该行中找到密文字母，密文字母所在列的列首对应的明文字母就是相应的明文。例一：关键词为“hold”，那么关键词-明文-密文的关联如下,2020/5/27,Page:13,古典多码加密法：Vigenere密码的分析,攻击者的优势和目标优势：攻击者知道加密法是关键词加密目标：试图发现关键词和明文可用的信息多码加密的基础依旧是关键词加密关键词在明文上重复书写，导致有可能一个字母对应多个替换,2020/5/27,Page:14,古典多码加密法：Vigenere密码的分析,关键词在明文上重复书写密钥的重复部分与明文中的重复部分的关联，在密文中也产生一个重复部分推测关键词的长度：为了使关键词本身与重复的明文对齐，重复明文之间的间距是关键词长度的整数倍找到密文中重复的字符部分，并计算它们之间的“距离”(字符数)；计算所有“距离”的因子；最大公约数很可能就是关键词的长度。,2020/5/27,Page:15,古典多码加密法：Vigenere密码的分析,例一：假如确定关键词的长度，如何试图破解？如果Eve发现Alice和Bob的关键词长度为6，那么她就知道每相隔6个字母都是用相同关键词字母加密的；上表中：“aplpd”都是用字符“h”加密的只要密文足够多，可以生成合理的统计样本，破解Vigenere加密法的问题就变成了破解n个不同单码加密的问题。,2020/5/27,Page:16,古典替换密码体制：总结,替换密码体制：设P=C=K=Z26，这里P，C，K，Z26分别表示明文空间、密文空间、密钥空间和26个整数(对应26个英文字母)组成的空间。对任意的kK，替换密码系统的操作过程移位密码加密：ek(x)=x+k(mod26)=yC解密：x=dk(y)=y-k(mod26)仿射密码加密：ek(x)=k1x+k2(mod26)=yC解密：x=dk(y)=k1-1(yk2)(mod26),2020/5/27,Page:17,古典密码学组成,古典替换密码体制古典单码加密法古典多码加密法古典换位密码体制古典置换加密法,2020/5/27,Page:18,换位密码体制：概述,换位加密法不是用其它字母来替代已有字母，而是重新排列文本中的字母。设计目的在知道密钥的情况下，能很容易正确排序；而不知道密钥时，就不可能解决。典型加密法：古典置换加密法、列置换加密法、RailFence加密法,2020/5/27,Page:19,换位密码体制：古典置换加密法,古典置换加密法是一种简单的换位加密法，其加密过程类似于洗一副纸牌。它的密钥是(d，f)。将密文分成固定长度的块，如长度为d；置换函数f从1d中选取一个整数排列；将明文每个分块中的字母根据f重新排列。例一：令d=4，f=(2,4,1,3)第一个字符移位到位置二，第二个字符移到位置四，第三个字符移到位置一，第四个字符移到位置三；假设明文：“thisistheplaintext”-“thisistheplaintext*”密文：“itshthisleaptien*x*t”,2020/5/27,Page:20,换位密码体制：古典置换加密法的分析,已知明文攻击：明文中可能包含一个的一个单词找出包含有与已知单词相同字母的块；通过比较已知单词与密文块，确定置换方式；在密文的其它块上测试上面得到的置换方式。密文攻击法：通过密文求解明文查看密文块，查找可能生成可读单词的排列方式；一旦发现了某个块的置换方式，接可以应用到密文的所有块中。,2020/5/27,Page:21,古典密码编码学之外：隐写术,隐写术是信息隐藏的一种手段。它隐藏消息的存在，本质上不是一种编码加密技术，通常在一段普通的文字中嵌入排列一些词汇或字母，隐含地表达真正的意思。藏头诗剃发刻字传信密写术(电影国家宝藏中的独立宣言隐藏了地图)缺陷形式简单但构造费时，要大量信息来隐藏相对较少的信息；一旦构造方法被泄露，整个系统将失效；无稳健性，数据修改后隐藏信息不能被恢复。,2020/5/27,Page:22,古典密码编码学之外：小人密码,福尔摩斯全集中小人字母,2020/5/27,Page:23,古典密码编码学之外：一次一密乱码本,MajorJosephMauborgne和AT&T公司的GilbertVernam在1917年发明的一种理想的加密方案一次一密乱码本采用一个大的不重复的真随机密钥字母集，组成一个密码本；每一密钥字母准确地加密一个明文字符，每个密钥只用一次；加密是明文字符和一次一密乱码本密钥的模26加法。安全性分析每一密钥序列和明文序列都是等概率的出现，敌手没有任何信息用来哪一密钥序列和明文消息是正确的。,2020/5/27,Page:24,古典密码编码学之外：使用和安全性,一个被安全用于密码协议中的移位密码(零知识证明)假定一个Zn上的函数f(x)，具有以下两条性质单向性：对于任意的xZn，f(x)能有效计算，而对几乎所有的xZn，对于任意有效算法A，ProbxA(y)f(x)=y与y的大小相比是一个可忽略的量；同态性：对于所有的x1,x2Zn，f(x1+x2)=f(x1)*f(x2)。零知识证明示证者(Alice)向验证者(Bob)证明她知道f(x)的原像x(xn)；验证者(Bob)无法知道原像x。,2020/5/27,Page:25,古典密码编码学之外：使用和安全性,利用移位密码的零知识证明协议协议的输入共同输入：f()是Zn上的一个单向同态函数；Alice的输入：zZn，X=f(z)。z为原像协议的输出Bob相信“Alice知道zZn，满足X=f(z)”。,2020/5/27,Page:26,古典密码编码学之外：使用和安全性,利用移位密码的零知识证明协议重复下面的步骤m次Alice选取kUZn，计算Commitf(k)并发送给Bob；Bob选取ChallengeU0,1并发送给Alice；Alice计算Response：如果Challenge=0，Responsek；如果Challenge=1，Responsek+z(modn)；Bob验证f(Response)：如果Challenge=0，f(Response)?=Commit；如果Challenge=1，f(Response)?=Commit*X。如果任何严整步骤出错，则中断运行并拒绝；否则Bob接受。,2020/5/27,Page:27,古典密码编码学之外：使用和安全性,利用移位密码的零知识证明协议的分析移位加密Response=z+k(modn)；kUZn=K=M，置换将均匀分布映射到均匀分布，所以ResponseUZn，等价于任何密钥都等可能的用来生成Response，同样等价于任何明文都等可能被加密成Response；明文z与密文分布是独立的，或者说密文不泄露关于明文的任何信息该密码在信息理论安全的意义上是安全的(来源于香农理论)。,信息理论意义上的安全性是无条件的并且能够抵抗任何方法的密码分析！,2020/5/27,Page:28,古典密码编码学之外：使用和安全性,古典密码安全使用的条件#K#M；kUZn，且每次加密只使用一次对加密少量数据是实用的，例如依次随机数、会话密钥等。,2020/5/27,Page:29,古典密码编码学之外：最牛游戏玩家,密码学破译隐藏任务游戏大航海时代Online永远的矢车菊任务至今尚未被人破解两位堪称史上最牛的玩家冰魂心、水镜却利用密码学知识找到了一丝曙光！破译优势信息在城里领了26个物品后，提示卡纳冯伯爵在金字塔附近，但是，无论换什么衣服和他说话，都没有实质性反应。永远的矢车菊任务连锁到：寻找大盗墓集团，和海事公会会长对话三次，分别给出提示：“4445332443”、“434512454212”、“42452433”。,2020/5/27,Page:30,古典密码编码学之外：最牛游戏玩家,密码学破译隐藏任务暗示一数字替代法是密码学中常用的方法先分拆这个数列找到数字替代的字母暗