《古典密码学优秀PPT.ppt》由会员分享，可在线阅读，更多相关《古典密码学优秀PPT.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、古典密码学杨秋伟湖南高校 计算机与通信学院10/31/20221古典密码学组成o古典替换密码体制n古典单码加密法n古典多码加密法o古典换位密码体制n古典置换加密法10/31/20222古典单码加密法：概述概述o单单码码加加密密是一种替换加密法，其中的每个明文只能被唯一的一个密文字母所替换。n例例一一：在给定的加密法中，明文的字母“a”在密文中可能总是显示为“n”；n例例二二(恺恺撒撒加加密密法法)：将字母在字母表中的位置后移3位，即“a”到“d”，“b”到“e”，“z”到“c”。10/31/20223古典单码加密法：关键词加密关键词加密o恺撒加密法的分析：简洁移位加密法通过尝试全部恺撒加密法的
2、分析：简洁移位加密法通过尝试全部25个密钥就可个密钥就可以很简洁破解，所以替代加密法应具有更多的密钥。以很简洁破解，所以替代加密法应具有更多的密钥。o关键词加密的构造关键词加密的构造o选择一个关键词，假如该关键词有重复的字母，去除除第一次出选择一个关键词，假如该关键词有重复的字母，去除除第一次出现之外的全部相同字母。例如，候选关键词为现之外的全部相同字母。例如，候选关键词为“success”，则运，则运用用“suce”；o将该关键词写在字母表的下方，并用字母表的其它字母按标准的将该关键词写在字母表的下方，并用字母表的其它字母按标准的依次填写余下的空间。依次填写余下的空间。10/31/20224
3、古典单码加密法：关键词加密关键词加密o例一：关键词加密例一：关键词加密o关键词为关键词为“magicnet”o字母表的描述形式字母表的描述形式oa b c d e f g h i j k l m n o p q r s t u v w x y z om a g i c n e t b d f h j k l o p q r s u v w x y zo明文：明文：help，密文：，密文：tchoo改进方案：允许关键词从字母表的随意位置起先。改进方案：允许关键词从字母表的随意位置起先。10/31/20225古典单码加密法：关键词加密的分析关键词加密的分析o攻击者的优势和目标攻击者的优势和目标o优
4、势：攻击者知道加密法是关键词加密优势：攻击者知道加密法是关键词加密o目标：试图发觉关键词和明文目标：试图发觉关键词和明文o可用的信息可用的信息o明文是标准的英语；明文是标准的英语；o所用加密法为关键词加密法；所用加密法为关键词加密法；o每个明文字母已被唯一的密文替代。每个明文字母已被唯一的密文替代。10/31/20226古典单码加密法：关键词加密的分析关键词加密的分析o语言的每个字母都有自身的特性，虽然接受了字母替换，但是特性照旧保持。例如，每个明文“t”被替换为“m”，那么在密文中，“m”将具有“t”的特性。o两个有用的特性o出现频率：例如，在标准英语中，出现频率最高的是字母“e”，而“x”
5、和“z”则很少出现；字母的实际出现频率取决于具体文字的类型，科技文献的字母出现频率与文学文献有很大的不同；o首选关联集：在标准英语中，多个字母常一起出现或不出现，例如，元音字母“a”、“i”和“o”互不相联。10/31/20227古典密码学组成o古典替换密码体制n古典单码加密法n古典多码加密法o古典换位密码体制n古典置换加密法10/31/20228古典多码加密法：概述概述o多码加密法是为了用来应付频率分析工具。o多码加密法也是一种替换加密法。o多码加密法的目的是通过用多个密文字母来替换同一个明文字母，从而消退字母的特性。o经典的古典多码加密：Playfair密码、Hill密码、Vigenere
6、密码10/31/20229古典多码加密法：Vigenere密码密码oVigenere密码是基于关键词的加密系统。oVigenere密码不同于单码关键词加密，它将关键词写在明文的上面，并不断重复书写，这样每个明文字母都与一个关键词的字母关联。n例一例一：关键词为“hold”，那么关键词-明文的关联如下holdholdholdholdhothisistheplaintext10/31/202210古典多码加密法：Vigenere密码密码oVigenere表明文密文10/31/202211古典多码加密法：Vigenere密码密码o加密过程：给定一个密钥字母加密过程：给定一个密钥字母k和一个明文字母和
7、一个明文字母p，密文字母就是位，密文字母就是位于于k所在的行与所在的行与p所在的列的交叉点上的那个字母。所在的列的交叉点上的那个字母。o解密过程：由密钥字母确定行，在该行中找到密文字母，密文字母解密过程：由密钥字母确定行，在该行中找到密文字母，密文字母所在列的列首对应的明文字母就是相应的明文。所在列的列首对应的明文字母就是相应的明文。o例一：关键词为例一：关键词为“hold”，那么关键词，那么关键词-明文明文-密文的关联如下密文的关联如下holdholdholdholdhothisistheplaintextavtvpgekldw dpbehdh10/31/202212古典多码加密法：Vige
8、nere密码的分析密码的分析o攻击者的优势和目标攻击者的优势和目标o优势：攻击者知道加密法是关键词加密优势：攻击者知道加密法是关键词加密o目标：试图发觉关键词和明文目标：试图发觉关键词和明文o可用的信息可用的信息o多码加密的基础照旧是关键词加密多码加密的基础照旧是关键词加密o关键词在明文上重复书写，导致有可能一个字母对应多个替换关键词在明文上重复书写，导致有可能一个字母对应多个替换10/31/202213古典多码加密法：Vigenere密码的分析密码的分析o关键词在明文上重复书写关键词在明文上重复书写o密钥的重复部分与明文中的重复部分的关联，在密文中也产生一密钥的重复部分与明文中的重复部分的关
9、联，在密文中也产生一个重复部分个重复部分o推想关键词的长度：为了使关键词本身与重复的明文对齐，重复推想关键词的长度：为了使关键词本身与重复的明文对齐，重复明文之间的间距是关键词长度的整数倍明文之间的间距是关键词长度的整数倍o找到密文中重复的字符部分，并计算它们之间的找到密文中重复的字符部分，并计算它们之间的“距离距离”(字符数字符数)；o计算全部计算全部“距离距离”的因子；的因子；o最大公约数很可能就是关键词的长度。最大公约数很可能就是关键词的长度。10/31/202214古典多码加密法：Vigenere密码的分析密码的分析o例一：假如确定关键词的长度，如何试图破解？例一：假如确定关键词的长度
10、，如何试图破解？o假如假如Eve发觉发觉Alice和和Bob的关键词长度为的关键词长度为 6，那么她就知道每相，那么她就知道每相隔隔6个字母都是用相同关键词字母加密的；个字母都是用相同关键词字母加密的；o上表中：上表中：“a p l p d”都是用字符都是用字符“h”加密的加密的o只要密文足够多，可以生成合理的统计样本，破解只要密文足够多，可以生成合理的统计样本，破解Vigenere加密加密法的问题就变成了破解法的问题就变成了破解n个不同单码加密的问题。个不同单码加密的问题。h o ld h o ld h o ld h o ld h oth isisth ep lain tex tav tv
11、p g ek ld w d p b eh d h10/31/202215古典替换密码体制：总结总结o替替换换密密码码体体制制：设设P=C=K=Z26，这这里里P，C，K，Z26分分别别表表示示明明文文空空间间、密密文文空空间间、密密钥钥空空间间和和26个个整整数数(对对应应26个个英英文文字字母母)组成的空间。对随意的组成的空间。对随意的kK，替换密码系统的操作过程，替换密码系统的操作过程o移位密码移位密码o加密：加密：ek(x)=x+k(mod26)=yCo解密：解密：x=dk(y)=y-k(mod26)o仿射密码仿射密码o加密：加密：ek(x)=k1x+k2(mod26)=yCo解密：解密
12、：x=dk(y)=k1-1(y k2)(mod26)10/31/202216古典密码学组成o古典替换密码体制n古典单码加密法n古典多码加密法o古典换位密码体制n古典置换加密法10/31/202217换位密码体制：概述概述o换位加密法不是用其它字母来替代已有字母，而是重新排列文本中的字母。o设计目的o在知道密钥的状况下，能很简洁正确排序；o而不知道密钥时，就不行能解决。o典型加密法：古典置换加密法、列置换加密法、Rail Fence加密法10/31/202218换位密码体制：古典置换加密法古典置换加密法o古典置换加密法是一种简洁的换位加密法，其加密过程类似于洗一副纸牌。它的密钥是(d，f)。o将
13、密文分成固定长度的块，如长度为d；o置换函数f从1d中选取一个整数排列；o将明文每个分块中的字母依据f重新排列。o例一：令d=4，f=(2,4,1,3)o第一个字符移位到位置二，其次个字符移到位置四，第三个字符移到位置一，第四个字符移到位置三；o假设明文：“thisistheplaintext”-“thisistheplaintext*”o密文：“itshthisleaptien*x*t”10/31/202219换位密码体制：古典置换加密法的分析古典置换加密法的分析o已知明文攻击：明文中可能包含一个的一个单词已知明文攻击：明文中可能包含一个的一个单词o找出包含有与已知单词相同字母的块；找出包含
14、有与已知单词相同字母的块；o通过比较已知单词与密文块，确定置换方式；通过比较已知单词与密文块，确定置换方式；o在密文的其它块上测试上面得到的置换方式。在密文的其它块上测试上面得到的置换方式。o密文攻击法：通过密文求解明文密文攻击法：通过密文求解明文o查看密文块，查找可能生成可读单词的排列方式；查看密文块，查找可能生成可读单词的排列方式；o一旦发觉了某个块的置换方式，接可以应用到密文的全部块中。一旦发觉了某个块的置换方式，接可以应用到密文的全部块中。10/31/202220古典密码编码学之外：隐写术隐写术o隐写术是信息隐藏的一种手段。它隐藏消息的存在，本质上不是一种编码加密技术，通常在一段一般的
15、文字中嵌入排列一些词汇或字母，隐含地表达真正的意思。o藏头诗o剃发刻字传信o密写术(电影国家宝藏中的独立宣言隐藏了地图)o缺陷o形式简洁但构造费时，要大量信息来隐藏相对较少的信息；o一旦构造方法被泄露，整个系统将失效；o无稳健性，数据修改后隐藏信息不能被复原。10/31/202221古典密码编码学之外：小人密码小人密码o福尔摩斯全集中o小人小人=字母字母10/31/202222古典密码编码学之外：一次一密乱码本一次一密乱码本oMajorJosephMauborgne和AT&T公司的GilbertVernam在1917年独创的一种志向的加密方案一次一密乱码本o接受一个大的不重复的真随机密钥字母集
16、，组成一个密码本；o每一密钥字母精确地加密一个明文字符，每个密钥只用一次；o加密是明文字符和一次一密乱码本密钥的模26加法。o平安性分析o每一密钥序列和明文序列都是等概率的出现，敌手没有任何信息用来哪一密钥序列和明文消息是正确的。10/31/202223古典密码编码学之外：运用和平安性o一个被平安用于密码协议中的移位密码一个被平安用于密码协议中的移位密码(零学问证明零学问证明)o假定一个假定一个Zn上的函数上的函数f(x)，具有以下两条性质，具有以下两条性质o单向性：对于随意的单向性：对于随意的x Zn，f(x)能有效计算，而对几乎全部的能有效计算，而对几乎全部的x Zn，对于随意有效算法，对
17、于随意有效算法A，ProbxA(y)f(x)=y与与y的大小相比是的大小相比是一个可忽视的量；一个可忽视的量；o同态性：对于全部的同态性：对于全部的x1,x2 Zn，f(x1+x2)=f(x1)*f(x2)。o零学问证明零学问证明o示证者示证者(Alice)向验证者向验证者(Bob)证明她知道证明她知道f(x)的原像的原像x(x n)；o验证者验证者(Bob)无法知道原像无法知道原像x。10/31/202224古典密码编码学之外：运用和平安性o利用移位密码的零学问证明协议利用移位密码的零学问证明协议o协议的输入协议的输入o共同输入：共同输入：f()是是Zn上的一个单向同态函数；上的一个单向同态
18、函数；oAlice的输入：的输入：z Zn，X=f(z)。z为原像为原像o协议的输出协议的输出oBob信任信任“Alice知道知道z Zn，满足，满足X=f(z)”。10/31/202225古典密码编码学之外：运用和平安性o利用移位密码的零学问证明协议利用移位密码的零学问证明协议o重复下面的步骤重复下面的步骤m次次oAlice选取选取k U Zn，计算，计算Commit f(k)并发送给并发送给Bob；oBob选取选取Challenge U0,1并发送给并发送给Alice；oAlice计计算算Response：假假如如Challenge=0，Response k；假如假如Challenge=1
19、，Response k+z(mod n)；oBob验验 证证 f(Response)：假假 如如 Challenge=0，f(Response)?=Commit；假假 如如 Challenge=1，f(Response)?=Commit*X。假假如如任任何何严严整整步步骤骤出出错错，则则中中断运行并拒绝；否则断运行并拒绝；否则Bob接受。接受。10/31/202226古典密码编码学之外：运用和平安性o利用移位密码的零学问证明协议的分析利用移位密码的零学问证明协议的分析o移位加密移位加密 Response=z+k(mod n)；ok U Zn=K=M，置置换换将将匀匀整整分分布布映映射射到到匀匀
20、整整分分布布，所所以以Response U Zn，等等价价于于任任何何密密钥钥都都等等可可能能的的用用来来生生成成Response，同同样样等等价价于于任任何何明明文文都都等等可可能能被被加加密密成成Response；o明明文文z与与密密文文分分布布是是独独立立的的，或或者者说说密密文文不不泄泄露露关关于于明明文文的的任任何何信信息息该该密密码码在在信信息息理理论论平平安安的的意意义义上上是是平平安安的的(来来源源于于香香农农理理论论)。信息理论意义上的平安性是无条件的并且能够反抗任何方法的密码分析！信息理论意义上的平安性是无条件的并且能够反抗任何方法的密码分析！10/31/202227古典密
21、码编码学之外：运用和平安性o古典密码平安运用的条件古典密码平安运用的条件o#K#M；okUZn，且且每每次次加加密密只只运运用用一一次次对对加加密密少少量量数数据据是是好好用用的的，例如依次随机数、会话密钥等。例如依次随机数、会话密钥等。10/31/202228古典密码编码学之外：最牛游戏玩家o密码学破译隐藏任务密码学破译隐藏任务o游戏大航海时代游戏大航海时代Onlineo恒久的矢车菊任务至今尚未被人破解恒久的矢车菊任务至今尚未被人破解o两两位位堪堪称称史史上上最最牛牛的的玩玩家家冰冰魂魂心心、水水镜镜却却利利用用密密码码学学学学问问找找到到了了一一丝曙光！丝曙光！o破译优势信息破译优势信息o
22、在在城城里里领领了了26个个物物品品后后，提提示示卡卡纳纳冯冯伯伯爵爵在在金金字字塔塔旁旁边边，但但是是，无无论换什么衣服和他说话，都没有实质性反应。论换什么衣服和他说话，都没有实质性反应。o恒恒久久的的矢矢车车菊菊任任务务连连锁锁到到：找找寻寻大大盗盗墓墓集集团团，和和海海事事公公会会会会长长对对话话三三次次，分分别别给给出出提提示示：“4445332443”、“434512454212”、“42452433”。10/31/202229古典密码编码学之外：最牛游戏玩家o密码学破译隐藏任务密码学破译隐藏任务o示意一示意一o数字替代法是密码学中常用的方法数字替代法是密码学中常用的方法o先分拆这个
23、数列先分拆这个数列o找到数字替代的字母找到数字替代的字母o示意二示意二o如何分拆数字如何分拆数字o第第一一行行10个个数数字字，其其次次行行12个个数数字字，第第三三行行8个个数数字字，3数数字字分分拆拆不不完整完整o接受接受2数字分拆数字分拆o44 45 33 24 4343 45 12 45 42 1242 45 24 33o示意三示意三o全部数字都是由全部数字都是由1-5以内的数字组成以内的数字组成暗合棋盘密暗合棋盘密10/31/202230古典密码编码学之外：最牛游戏玩家o密码学破译隐藏任务密码学破译隐藏任务o棋盘密棋盘密o公公元元前前2世世纪纪，宏宏大大的的希希腊腊历历史史学学家家、军军事事家家、数数学学家家波波利利比比奥奥斯斯独独创创了了波波利比奥斯方表利比奥斯方表Polybius Square棋盘密棋盘密123451abcde2fghik3lmnop4qrstu5vwxyz明文明文：tuni(j)stunis突尼斯suburb郊外rui(j)nruin废墟10/31/202231