古典密码学(1).ppt

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