密码学概述与古典密码

密码学教师：韩萌教师：韩萌EMAIL:compute2006_2022-7-11HANMENG20102教学要求教学要求1.成绩组成成绩组成密码学密码学成绩：成绩：100%。=作业作业10%+考勤考勤10%+实验实验10%+考试考试70%。密码学实践密码学实践成绩：成绩：100%。2.总学时总学时 教学教学48学时学时+实践实践20学时。学时。3.教学目的：教学目的：掌握常见的加密解密算法。掌握常见的加密解密算法。2022-7-11HANMENG20103教学要求教学要求4、前导课程、前导课程 编程语言编程语言C5、参考书目、参考书目密码学与网络安全密码学与网络安全应用密码学手册应用密码学手册密码学导引：原理与应用密码学导引：原理与应用现代密码学教程现代密码学教程2022-7-11HANMENG20104章节内容章节内容第第1章章 密码学概述与密码学概述与古典密码古典密码第第2章章 编程基础与数学基础编程基础与数学基础第第3章章 序列密码序列密码第第4章章 分组密码分组密码第第5章章 公钥密码公钥密码第第6章章 认证和哈希函数认证和哈希函数第第7章章 数字签名、密钥管理技术（选讲）数字签名、密钥管理技术（选讲）2022-7-11HANMENG20105引例引例1 早妆未罢暗凝眉，早妆未罢暗凝眉，迎户愁看紫燕飞，迎户愁看紫燕飞，无力回天春已老，无力回天春已老，双栖画栋不如归。双栖画栋不如归。2022-7-11HANMENG20106王先生：王先生：来信收悉，你的盛情真是难以报答。我已来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，方能上街，苦矣。大约本月中旬我才能返回，届时再见。届时再见。引例引例2-卡丹网格式密码卡丹网格式密码2022-7-11HANMENG20107密密码码学学古典密码学古典密码学现代密码学现代密码学置换密码置换密码代替密码代替密码序列密码序列密码分组密码分组密码公钥密码公钥密码哈希密码哈希密码对称密码对称密码非对称密码非对称密码图图1 1 密码学分类密码学分类第第1章章 密码学引论密码学引论与古典密码与古典密码本章重点：本章重点：掌握常用的古典密码的加密解密。掌握常用的古典密码的加密解密。学时：学时：6-8学时学时2022-7-11HANMENG20109主要内容主要内容1.1 信息安全与密码学信息安全与密码学1.2 信息安全的模型信息安全的模型1.3 密码学概述密码学概述1.4 几种古典密码几种古典密码(补充内容，重点补充内容，重点)2022-7-11HANMENG2010101.1 信息安全与密码学信息安全与密码学一一 网络信息安全面临的威胁网络信息安全面临的威胁p2020世纪世纪7070年代，面向单机的，主要内容是信息的年代，面向单机的，主要内容是信息的保密性。保密性。p2020世纪世纪8080年代，安全服务、安全机制等基本框架，年代，安全服务、安全机制等基本框架，成为信息安全的重要内容。成为信息安全的重要内容。p2020世纪世纪9090年代，因特网具有高度分布、边界模糊、年代，因特网具有高度分布、边界模糊、层次欠清、动态演化，而用户又在其中扮演主角层次欠清、动态演化，而用户又在其中扮演主角的特点，如何处理好这一复杂而又巨大的系统的的特点，如何处理好这一复杂而又巨大的系统的安全，成为信息安全的主要问题。安全，成为信息安全的主要问题。2022-7-11HANMENG2010111.1 信息安全与密码学信息安全与密码学1 1、信息安全所面临的威胁可以宏观地分为、信息安全所面临的威胁可以宏观地分为人人为攻击和自然威胁。为攻击和自然威胁。p人为攻击具有智能性、严重性、隐蔽性和人为攻击具有智能性、严重性、隐蔽性和多样性等特点。多样性等特点。p人为攻击分为被动攻击和主动攻击。人为攻击分为被动攻击和主动攻击。2022-7-11HANMENG201012信源信源接收者接收者 正常的信息流正常的信息流信源信源接收者接收者 窃听窃听信源信源接收者接收者 篡改篡改图图2 攻击的主要形式攻击的主要形式信源信源接收者接收者 重放重放信源信源接收者接收者 伪造伪造信源信源接收者接收者 中断中断2022-7-11HANMENG2010132 人为攻击人为攻击p被动攻击：被动攻击：即窃听，是对系统的保密性即窃听，是对系统的保密性进行攻击，如搭线窃听、对文件或程序进行攻击，如搭线窃听、对文件或程序的非法拷贝等以获取他人的信息，并不的非法拷贝等以获取他人的信息，并不修改信息。修改信息。p被动攻击又分为两类：被动攻击又分为两类：一是获取消息的内容；一是获取消息的内容；二是进行业务流分析。二是进行业务流分析。抗击重点在于预防而非检测。抗击重点在于预防而非检测。2022-7-11HANMENG2010142 人为攻击人为攻击p主动攻击：主动攻击：包括对数据流的某些篡改或产生某包括对数据流的某些篡改或产生某些假的数据流。些假的数据流。p分为以下四个子类：分为以下四个子类：中断：是对系统的可用性进行攻击，中断：是对系统的可用性进行攻击，如禁止设如禁止设备的正常使用或管理。备的正常使用或管理。篡改：是对系统的完整性进行攻击，篡改：是对系统的完整性进行攻击，如修改数如修改数据文件中的数据、替换某一程序使其执行不同据文件中的数据、替换某一程序使其执行不同的功能、修改网络中传送的消息内容等。的功能、修改网络中传送的消息内容等。2022-7-11HANMENG2010152 人为攻击人为攻击 伪造：是对系统的真实性进行攻击。伪造：是对系统的真实性进行攻击。如在网络中插入伪造的消息或在文件如在网络中插入伪造的消息或在文件中插入伪造的记录。中插入伪造的记录。重放：将数据截获后进行重传重放：将数据截获后进行重传，产生，产生未授权的消息。未授权的消息。抗击主动攻击的主要途径是检测，以及对抗击主动攻击的主要途径是检测，以及对此攻击造成的破坏进行恢复。此攻击造成的破坏进行恢复。2022-7-11HANMENG2010161.2 信息安全的模型信息安全的模型图图3 3 信息安全的基本模型信息安全的基本模型2022-7-11HANMENG2010171.2 信息安全的模型信息安全的模型安全传输技术有以下两个基本成分：安全传输技术有以下两个基本成分：p消息的安全传输，消息的安全传输，包括对消息的加密和包括对消息的加密和认证。通信双方共享的某些秘密信息，认证。通信双方共享的某些秘密信息，如加密密钥。如加密密钥。p为获得消息的安全传输，可能还需要一为获得消息的安全传输，可能还需要一个个可信的第三方可信的第三方，其作用可能是负责向，其作用可能是负责向通信双方发布秘密信息或者在通信双方通信双方发布秘密信息或者在通信双方有争议时进行仲裁。有争议时进行仲裁。2022-7-11HANMENG2010181.3 密码学概述密码学概述 密码学密码学(Cryptology)(Cryptology)：把来自信源的可理解：把来自信源的可理解的消息变成不可理解的消息，同时又可以恢复的消息变成不可理解的消息，同时又可以恢复到原消息的一门学科。到原消息的一门学科。它包含两个分支它包含两个分支:p密码编码学密码编码学(Cryptography)(Cryptography)，对信息进行编码，对信息进行编码实现隐蔽信息的一门学问。实现隐蔽信息的一门学问。p密码分析学密码分析学(Cryptanalytics(Cryptanalytics)，研究分析破译，研究分析破译密码的学问。密码的学问。2022-7-11HANMENG2010191 密码学基本概念密码学基本概念p明文明文m：初始的消息。：初始的消息。p密文密文c：明文经密码变换成的一种隐蔽形：明文经密码变换成的一种隐蔽形式。式。p明文空间明文空间M：全体明文的集合。：全体明文的集合。p密文空间密文空间C：全体密文的集合。：全体密文的集合。p加密算法加密算法E：对明文进行加密时所采用：对明文进行加密时所采用的一组规则。的一组规则。2022-7-11HANMENG201020p解密算法解密算法D：对密文进行解密时所采用：对密文进行解密时所采用的一组规则。是加密算法的逆过程。的一组规则。是加密算法的逆过程。p密钥空间密钥空间K：用于加密或者解密的秘密：用于加密或者解密的秘密消息，分别称作加密密钥空间消息，分别称作加密密钥空间Ke和解密和解密密钥空间密钥空间Kd。1 密码学基本概念密码学基本概念2022-7-11HANMENG201021图图4 4：加密解密模型：加密解密模型重点重点2022-7-11HANMENG201022示例示例eg：分析下列表达式的含义：分析下列表达式的含义pC=E(M,Ke)=Eke(M)加密算法加密算法E在加密密钥在加密密钥Ke的控制下将明的控制下将明文文M加密成密文加密成密文C。pM=D(C,Kd)=DKd(C)解密算法解密算法D在密钥在密钥Kd的控制下将密文的控制下将密文C解解出成明文出成明文M。重点重点2022-7-11HANMENG2010232 密码体制的分类密码体制的分类（1）按照加密解密方式，密码体制可分）按照加密解密方式，密码体制可分为为对称密码体制和非对称密码体制。对称密码体制和非对称密码体制。p对称密码体制：对称密码体制：加密解密的密钥是同一加密解密的密钥是同一个，个，即即Ke=Kd。p非对称密码体制：非对称密码体制：加密解密的密钥不同，加密解密的密钥不同，即即KeKd，且不能通过且不能通过Ke计算出计算出Kd。2022-7-11HANMENG2010242 密码体制的分类密码体制的分类（2）按照历史的发展，密码体制可分为）按照历史的发展，密码体制可分为:p古典密码：古典密码：以手工加密为主。以手工加密为主。p现代密码：现代密码：以机械加密为主。以机械加密为主。2022-7-11HANMENG2010251.4 几种古典密码几种古典密码p隐写术隐写术p置换密码（重点）置换密码（重点）p代替密码（重点）代替密码（重点）单表代替密码单表代替密码多表代替密码多表代替密码2022-7-11HANMENG201026一、一、隐写术隐写术隐写术：将秘密消息隐藏在公开消息中，并通隐写术：将秘密消息隐藏在公开消息中，并通过公开渠道来传送的方法。过公开渠道来传送的方法。两种隐藏明文两种隐藏明文信息的方法信息的方法隐写术隐写术密码编码学密码编码学2022-7-11HANMENG201027eg：诗情画意传：诗情画意传“密语密语”早妆未罢暗凝眉，早妆未罢暗凝眉，迎户愁看紫燕飞，迎户愁看紫燕飞，无力回天春已老，无力回天春已老，双栖画栋不如归。双栖画栋不如归。2022-7-11HANMENG201028王先生：王先生：来信收悉，你的盛情真是难以报答。我已来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，方能上街，苦矣。大约本月中旬我才能返回，届时再见。届时再见。eg：卡丹网格式密码：卡丹网格式密码2022-7-11HANMENG201029隐写术特点隐写术特点p简单，掌握密钥后，破译简单。简单，掌握密钥后，破译简单。p易被攻击。易被攻击。2022-7-11HANMENG201030二、二、置换密码置换密码p又称换位密码，指根据一定的规则重新排列明又称换位密码，指根据一定的规则重新排列明文。文。p特点：保持明文的所有字符不变，只是打乱了特点：保持明文的所有字符不变，只是打乱了位置和次序。位置和次序。p分类：分类：列置换密码列置换密码周期置换密码周期置换密码2022-7-11HANMENG2010311、列置换密码：将明文按照固定宽度、列置换密码：将明文按照固定宽度n按行写出，而按行写出，而后按照密钥的规则按列换位。后按照密钥的规则按列换位。eg1：已知明文是：已知明文是Beijing 2008 Olympic Games，密钥，密钥k=6，e=(14)(56)。加密过程是：加密过程是：step1:将明文将明文m按照宽度按照宽度k分行。分行。M=B e i j i n g 2 0 0 8 O l y m p i c G a m e sstep2:将明文将明文m按照按照e换行，得密文换行，得密文C=j e i B n i 0 2 0 g O 8 p y m l c i e a m G s2022-7-11HANMENG201032eg2：已知明文是：已知明文是this text，密钥，密钥k=4，e=(2 4 1 3)。加密过程：加密过程：将明文按照将明文按照4个字符一组分组，不足的部分填充个字符一组分组，不足的部分填充*得：得：this text 第第2个字符移位到位置个字符移位到位置4，第，第4个字符移到位置个字符移到位置1，第第1个字符移到位置个字符移到位置3，第，第3个字符移到位置个字符移到位置2；则密文：则密文：“sith txte”(2)周期置换密码：将明文周期置换密码：将明文m按照固定长度分组，对按照固定长度分组，对每组的字串按照某个置换重新排位从而得到密文。每组的字串按照某个置换重新排位从而得到密文。2022-7-11HANMENG201033练习练习ex：已知采用周期置换密码加密，密钥：已知采用周期置换密码加密，密钥k=6,e=(15623)。如果明文是。如果明文是statek，那么密文是什么？那么密文是什么？aKttSe如何解密？如何解密？2022-7-11HANMENG201034三、三、单表代换密码单表代换密码p就是明文中的字母由其他字母、数字或符就是明文中的字母由其他字母、数字或符号所取代的一种方法。号所取代的一种方法。p算法：建立一个代换表，加密时将明文字算法：建立一个代换表，加密时将明文字符通过代换表代换为相应的密钥文字。符通过代换表代换为相应的密钥文字。p具体的代替表称之为密钥。具体的代替表称之为密钥。2022-7-11HANMENG201035三、三、代换密码代换密码字母与十进制数字的对应关系：字母与十进制数字的对应关系：2022-7-11HANMENG201036其中：其中：pm是明文，是明文，c是密文。是密文。p3是加密所用的密钥，加密时，每个字母向后移是加密所用的密钥，加密时，每个字母向后移3位，解密时，每个字母向前移位，解密时，每个字母向前移3位（均为循环移位（均为循环移位）。位）。1、凯撒密码凯撒密码250),26(mod3)(250),26(mod3)(33cccDmmmmEc2022-7-11HANMENG201037eg：通过恺撒（：通过恺撒（Caesar）密码对明文加密：）密码对明文加密：please则密文为：则密文为：sohdvh2022-7-11HANMENG2010382、移位变换移位变换25,0),26(mod)(25,0),26(mod)(kckccDmkmkmmEckk特点：特点：o加密方法简单。加密方法简单。o 穷举即可破译。穷举即可破译。2022-7-11HANMENG2010393、基于密钥的单表代换密码基于密钥的单表代换密码o具体算法：具体算法：选取一个字符串作为密钥，除去密钥中重选取一个字符串作为密钥，除去密钥中重复的字母，剩余字母按照顺序写在此字母之复的字母，剩余字母按照顺序写在此字母之后生成字母表。后生成字母表。o特点：特点：o破译难度较高。破译难度较高。o 密钥更改灵活。密钥更改灵活。2022-7-11HANMENG201040eg：已知密钥为：已知密钥为magicnet，对明文，对明文help加密。加密。step1:生成字母表生成字母表abcd efgh ijkl mnop qrst uvwx yz magi cnet bdfh jklo pqrs uvwx yzstep2：按照字母表替换明文字符。：按照字母表替换明文字符。明文：明文：help 密文：密文：tcho如何解密？如何解密？2022-7-11HANMENG2010414、仿射加密仿射加密扩展的移位变换扩展的移位变换加密：解密：o密密钥为钥为025之间的数字对之间的数字对(a,b)。o 要求：要求：oa与与26的最大公约数必须为的最大公约数必须为1，即即gcd(a,26)=1。o a-1是是a的逆元的逆元，即，即a-1*a(mod26)=1。26mod)(bamc26mod)(1bcam25,0cm2022-7-11HANMENG201042eg：仿射加密。设：仿射加密。设(a,b)=(7,21)，对明文，对明文security加密。对加密。对vlxijh解密。解密。s=18,7*18+21(mod26)=17,sre=4,7*4+21(mod26)=23,exc=2,7*2+21(mod26)=9,cjy=24,7*24+21(mod26)=7,yhsecurity对应的密文：对应的密文：rxjfkzyh26mod)(bamc2022-7-11HANMENG201043eg：仿射加密。设：仿射加密。设(a,b)=(7,21)，对明文，对明文security加密。对加密。对vlxijh解密。解密。7-1mod26=?7*15mod26=17-1mod26=15v=21,15(21-21)mod26=0,val=11,15(11-21)mod26=6,lgh=7,15(7-21)mod26=24,hyvlxijh对应的明文：对应的明文：agency26mod)(1bcam2022-7-11HANMENG2010440-25内所有与内所有与26互素元素的乘法逆元互素元素的乘法逆元1-13-15-17-19-111-115-117-119-121-123-125-119211531972311517252022-7-11HANMENG201045练习练习ex:仿射加密。设仿射加密。设(a,b)=(3,21)，对明文，对明文book加密解密。加密解密。2022-7-11HANMENG201046p以一些表依次对明文消息的字母序列进行以一些表依次对明文消息的字母序列进行代换的加密方法。代换的加密方法。p明文中的同一个字母，由于出现的位置不明文中的同一个字母，由于出现的位置不同用不同的字母代替。同用不同的字母代替。四、多表代换密码四、多表代换密码2022-7-11HANMENG2010471、Playfair密码密码p算法设计：算法设计：将明文字母按照两个字母一组分组，然后将将明文字母按照两个字母一组分组，然后将这些组按照字母矩阵替换为密文字母组合。这些组按照字母矩阵替换为密文字母组合。p基于一个基于一个55字母矩阵字母矩阵p该矩阵使用密钥来构造。该矩阵使用密钥来构造。2022-7-11HANMENG2010481、Playfair密码密码p矩阵构造方法：矩阵构造方法：从左至右，从上至下依次填入关键词的字从左至右，从上至下依次填入关键词的字母，若字母重复则略过，然后再以字母表顺母，若字母重复则略过，然后再以字母表顺序依次填入其他的字母。序依次填入其他的字母。字母字母I和和J被算作一个字母被算作一个字母。表中的第表中的第1列看做是第列看做是第5列的右边列的右边1列，第列，第1行看做第行看做第5行的下行的下1行。行。2022-7-11HANMENG201049加密算法：加密算法：p P1、P2同行：同行：对应的对应的C1和和C2分别是紧靠分别是紧靠P1、P2右端的字母。其中第一右端的字母。其中第一列被看作是最后一列的右方。列被看作是最后一列的右方。p P1、P2同列：同列：对应的对应的C1和和C2分别是紧靠分别是紧靠P1、P2下方的字母。其中第一下方的字母。其中第一行看作是最后一行的下方。行看作是最后一行的下方。p P1、P2不同行、不同列：不同行、不同列：C1和和C2是由是由P1和和P2确定的矩形的其它两角的字母，并且确定的矩形的其它两角的字母，并且C1和和P1、C2和和P2同行。同行。p P1P2：则插入一个字母于重复字母之间，并用前述方法处理则插入一个字母于重复字母之间，并用前述方法处理.p 若明文字母数为奇数时：若明文字母数为奇数时：则在明文的末端添加某个事先约定的字母作为填充。则在明文的末端添加某个事先约定的字母作为填充。2022-7-11HANMENG201050eg1：已知密钥是：已知密钥是：PLAYFAIRISADIGRAMCIPHER。如果明文是。如果明文是playfair cipher，为其加密。，为其加密。明文两个一组：明文两个一组：pl ay fa ir ci ph er对应密文为对应密文为:LA YF PY RS MR AM CD2022-7-11HANMENG201051ex：用：用Playfair算法加密明文算法加密明文“playfair cipher”,密钥是密钥是fivestars。练习练习2022-7-11HANMENG2010522022-7-11HANMENG201053 明明文文playfaircipher密密文文qkbwitvaasokvb2022-7-11HANMENG201054Playfair密码的特点密码的特点p有有676种双字母组合，因此识别各种双字种双字母组合，因此识别各种双字母组合要困难得多。母组合要困难得多。p各个字母组的频率要比单字母呈现出大各个字母组的频率要比单字母呈现出大得多的范围，使得频率分析困难得多。得多的范围，使得频率分析困难得多。pPlayfair密码仍然使许多明文语言的结构密码仍然使许多明文语言的结构保存完好，使得密码分析者能够利用。保存完好，使得密码分析者能够利用。2022-7-11HANMENG2010552、维吉尼亚密码、维吉尼亚密码算法设计：算法设计：p设设N是某固定的正整数，已知密钥有是某固定的正整数，已知密钥有N个字个字符，符，K=(k1,k2,kN)。将明文。将明文M按照按照N个字个字符一组分段，分为符一组分段，分为L段，段，M=(m1,m2,mL)。p求密文求密文C，其中，其中Cij=kj+mij,i=L,j=N。2022-7-11HANMENG201056eg：已知密钥字是：已知密钥字是CIPHER，n6。假定明文串是：。假定明文串是：this system。3、相应的密文串将是、相应的密文串将是:vpxzwpubtt加密过程：加密过程：1、密钥字转换为数字密钥字转换为数字为：为：2 8 15 7 4 172、将明文串转化为数字串，按将明文串转化为数字串，按6个一组分段，然后加个一组分段，然后加上密钥字模上密钥字模26。19 7 8181824 2 8 15741721152325221518 19 4122 8 15720119192022-7-11HANMENG201057解密过程：解密过程：1、密钥字转换为数字。密钥字转换为数字。2、将密文串转化为数字串，按密钥字个数分将密文串转化为数字串，按密钥字个数分组，然后减去密钥字模组，然后减去密钥字模26。2022-7-11HANMENG2010583、Hill密码密码 p明文：明文：p密文：密文：p其中，其中，dMMMM21dCCCMEC21)(ddMkMkMkC12121111ddddddMkMkMkC22112022-7-11HANMENG201059矩阵形式：矩阵形式：dddddddkkkkkkmmmccc21112112121,121112112121,dddddddkkkkkkcccmmm加密：加密：解密：解密：2022-7-11HANMENG201060示例示例eg1eg1：逆矩阵：逆矩阵mod26mod26的含义。的含义。k=11 8 k=11 8 3 7 3 7 k k-1-1=7 18=7 18 23 11 23 11 kkkk-1-1=11=11*7+87+8*23 1123 11*18+818+8*11 11 3 3*7+77+7*23 323 3*18+718+7*1111 =261 286 =1 0 =261 286 =1 0 182 131 0 1 182 131 0 1mod 26mod 262022-7-11HANMENG201061eg2eg2：已知明文为：已知明文为hill ，密钥矩阵如下所，密钥矩阵如下所示：示：（23,8）明文明文M=hill,M=hill,对应数值：对应数值：7 7，8 8，1111，1111。k=11 8 k=11 8 3 7 3 7 C=(7,8)11 8 mod 26C=(7,8)11 8 mod 26 3 7 3 7（24,9）C=(11,11)11 8 mod 26 C=(11,11)11 8 mod 26 3 7 3 7 k k-1-1=7 18=7 18 23 11 23 11 密文为：密文为：xiyj2022-7-11HANMENG201062解密：解密：（7,8）m=(23,8)7 18 m=(23,8)7 18 23 11 23 11（11,11）C=(24,9)7 18 C=(24,9)7 18 23 11 23 11 k k-1-1=7 18=7 18 23 11 23 11 2022-7-11HANMENG201063Hill密码的特点：密码的特点：pHill密码完全隐藏了单字母的频率密码完全隐藏了单字母的频率p字母和数字的对应可以改成其它方案，使得更字母和数字的对应可以改成其它方案，使得更不容易攻击成功不容易攻击成功p能比较好地抵抗频率法的分析，对抗仅有密文能比较好地抵抗频率法的分析，对抗仅有密文的攻击强度较高的攻击强度较高2022-7-11HANMENG201064练习练习ex2：设明文是：设明文是cybert，使用的密钥如下，使用的密钥如下，为其加密解密。为其加密解密。ex1：已知密钥字是：已知密钥字是text，n4。对。对明文明文this system加密解密。加密解密。k k-1-1=7 18=7 18 23 11 23 11 k=11 8 k=11 8 3 7 3 7 2022-7-11HANMENG201065编程编程 已知是维吉尼亚加密，设密钥是：已知是维吉尼亚加密，设密钥是：but，明文是明文是sorcery，为其加密解密。，为其加密解密。