1、第二章 数据加密及认证技术计算机科学学院计算机科学学院 网络工程教研室网络工程教研室 梁晓梁晓Email: Email: Tel: 1xxxxxxxxxxTel: 1xxxxxxxxxx主要内容主要内容v数据加密概述数据加密概述 密码学的发展密码学的发展 密码学基本概念与分类密码学基本概念与分类 密码分析学密码分析学v传统密码技术传统密码技术v对称密钥密码对称密钥密码v公钥密码体制公钥密码体制v数字签名与认证技术数字签名与认证技术v加密软件加密软件密码学的起源密码学的起源v 古代加密方法大约起源于公元前古代加密方法大约起源于公元前440年出现在古希腊战争年出现在古希腊战争中的隐写术。中的隐写术
2、。v 古希腊的斯巴达人曾将军事情报刻在普通的木板上，用石古希腊的斯巴达人曾将军事情报刻在普通的木板上，用石蜡填平，收信的一方只要用火烤热木板，融化石蜡后，就蜡填平，收信的一方只要用火烤热木板，融化石蜡后，就可以看到密信。可以看到密信。v 密码学用于通信的另一个记录是斯巴达人于公元前密码学用于通信的另一个记录是斯巴达人于公元前400年年应用锥形指挥棒在军官间传递秘密信息。应用锥形指挥棒在军官间传递秘密信息。我国古代的藏头诗、藏尾诗、漏格诗我国古代的藏头诗、藏尾诗、漏格诗v水浒传水浒传 “吴用智赚玉麒麟吴用智赚玉麒麟”一回中的诗一回中的诗 卢卢花滩上有扁舟，花滩上有扁舟，俊俊杰黄昏独自游。杰黄昏独
3、自游。 义义到尽头原是命，到尽头原是命，反反躬逃难必无忧。躬逃难必无忧。v明代怪杰徐文长：明代怪杰徐文长： 平平湖一色万顷秋，湖一色万顷秋， 湖湖光渺渺水长流。光渺渺水长流。 秋秋月圆圆世间少，月圆圆世间少， 月月好四时最宜秋。好四时最宜秋。 密码学在军事中的应用密码学在军事中的应用v 1894年甲午海战中北洋水师的覆灭，虽然其根本的原因年甲午海战中北洋水师的覆灭，虽然其根本的原因在于清朝廷的腐败在于清朝廷的腐败, 但是日本人破译了清军的密码也是一但是日本人破译了清军的密码也是一个重要的原因；个重要的原因；v 二战中二战中, 美国利用破译密码所获得的情报为其外交服务；美国利用破译密码所获得的情
4、报为其外交服务；v 在在1962年的古巴导弹危机中年的古巴导弹危机中,苏美剑拔弩张苏美剑拔弩张,形势严峻。形势严峻。据悉，美国人心生一计，故意用能被苏联截收、破译的密据悉，美国人心生一计，故意用能被苏联截收、破译的密码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁晓夫；晓夫；v 1994年年, 美国的情报机构通过截获国际电讯得知，法国美国的情报机构通过截获国际电讯得知，法国与沙特阿拉伯正在进行一笔数亿美元的军火交易，美国先与沙特阿拉伯正在进行一笔数亿美元的军火交易，美国先行一步从法国人手中抢下了这笔大生意。行一步从法国人手中抢下了这笔大生意。
5、密码学从军事走向生活密码学从军事走向生活v电子邮件电子邮件v自动提款机（自动提款机（ATM）v网上银行网上银行/网上证券网上证券v信用卡购物（信用卡购物（POS机）机）生活中的密码学生活中的密码学v案例一：案例一： 甲给乙写的私人信件，丙未经甲乙允许擅自阅读此信甲给乙写的私人信件，丙未经甲乙允许擅自阅读此信非授权访问非授权访问v案例二：案例二： 甲和乙正常通信，丙冒充甲并且：甲和乙正常通信，丙冒充甲并且： 制造欺诈信息给乙；制造欺诈信息给乙； 窜改甲给乙发的合法信息；窜改甲给乙发的合法信息；中间人攻击中间人攻击v案例三：案例三： 甲在某时某地给乙发了信，乙否认收到了该信甲在某时某地给乙发了信，
6、乙否认收到了该信抵抵赖赖密码学的发展史密码学的发展史 v 第一阶段：第一阶段：1949年以前年以前 古典密码阶段古典密码阶段 计算机技术出现以前计算机技术出现以前 密码学作为一种艺术密码学作为一种艺术，而不是一门科学而不是一门科学v 第二阶段：第二阶段：1949年年1975年年 现代密码学初期现代密码学初期 标志：标志：1949年年Shannon发表的发表的保密系统的信息理论保密系统的信息理论一文。一文。 密码学进入了科学的轨道，密码学成为科学密码学进入了科学的轨道，密码学成为科学 主要技术主要技术: 单密钥的对称密钥加密算法单密钥的对称密钥加密算法v 第三阶段：第三阶段：1976年年 现代密
7、码学阶段现代密码学阶段 标志：标志：1976年年Diffie和和Hellman发表了发表了密码学新方向密码学新方向一文。一文。 新的密码体制新的密码体制 : 公开密钥体制公开密钥体制第一阶段古典密码第一阶段古典密码v古典密码的加密方法一般是古典密码的加密方法一般是代换代换与与置换置换，使用手，使用手工或机械变换的方式实现；工或机械变换的方式实现；v代表密码体制主要有：代表密码体制主要有： 单表替代密码：单表替代密码：Caesar密码；密码； 多表替代密码：多表替代密码：Playfair密码、密码、Hill密码、密码、Vigenere密码密码； 转轮密码：著名的转轮密码：著名的Enigma密码，
8、第二次世界大战中使密码，第二次世界大战中使用过。用过。v主要特点：数据的安全基于算法的保密。：数据的安全基于算法的保密。第二阶段第二阶段 现代密码学初期现代密码学初期 19491975v 1949年，年，香农香农发表了发表了保密系统的信息理论保密系统的信息理论 证明了密码编码学是如何置于坚实的数学基础之上的，从此证明了密码编码学是如何置于坚实的数学基础之上的，从此密码学发展成为一个专门学科密码学发展成为一个专门学科标志性事件标志性事件 为对称密码体制的发展奠定了理论基础；为对称密码体制的发展奠定了理论基础；v 1967年，年，大韦大韦卡恩的专著卡恩的专著破译者详细描述了密码破译者详细描述了密码
9、学的历史学的历史；v 1971-73年，年，IBM Watson实验室的实验室的Horst Feistel等几篇等几篇技术报告，技术报告，DES算法的产生；算法的产生；v 主要特点主要特点：数据的安全基于密钥而不是算法的保密。数据的安全基于密钥而不是算法的保密。第三阶段：第三阶段：1976 公钥密码学公钥密码学v 公钥密码学成为主要研究方向；公钥密码学成为主要研究方向；v 主要特点主要特点:公钥密码使得发送端和接收端无密钥传输的保公钥密码使得发送端和接收端无密钥传输的保密通信成为可能密通信成为可能。v 代表性事件：代表性事件： 1976年年, Diffie和和Hellman发表的革命性论文发表
10、的革命性论文密码学新方向密码学新方向(New deryctions in cryptography), 突破了传统密码体制使用秘密密钥所带来的密钥管理难题突破了传统密码体制使用秘密密钥所带来的密钥管理难题, 使密码的使密码的发展进入了一个全新的发展时期。发展进入了一个全新的发展时期。 1977年，年，Rivest，Shamir和和Adleman提出了提出了RSA公钥算法公钥算法。 DES算法出现算法出现。 80年代，出现年代，出现IDEA和和CAST等算法。等算法。 90年代，对称密钥密码算法进一步成熟，年代，对称密钥密码算法进一步成熟，Rijndael，RC6等出现，等出现，逐步出现逐步出现
11、椭圆曲线等其他公钥算法椭圆曲线等其他公钥算法。 2001年，年，Rijndael成为成为DES算法的替代者。算法的替代者。密码学的新方向密码学的新方向v密码专用芯片集成密码专用芯片集成 密码技术是信息安全的核心技术，无处不在，目前已密码技术是信息安全的核心技术，无处不在，目前已经渗透到大部分安全产品之中，正向芯片化方向发展经渗透到大部分安全产品之中，正向芯片化方向发展。在芯片设计制造方面，目前微电子水平已经发展到。在芯片设计制造方面，目前微电子水平已经发展到0.1um工艺以下，芯片设计的水平很高。工艺以下，芯片设计的水平很高。 我国在密码专用芯片领域的研究起步落后于国外，近我国在密码专用芯片领
12、域的研究起步落后于国外，近年来我国集成电路产业技术的创新和自我开发能力得年来我国集成电路产业技术的创新和自我开发能力得到了提高，微电子工业得到了发展，从而推动了密码到了提高，微电子工业得到了发展，从而推动了密码专用芯片的发展。加快密码专用芯片的研制将会推动专用芯片的发展。加快密码专用芯片的研制将会推动我国信息安全系统的完善。我国信息安全系统的完善。量子密码技术量子密码技术v量子技术在密码学上的应用分为两类：量子技术在密码学上的应用分为两类： 一是利用量子计算机对传统密码体制的分析；一是利用量子计算机对传统密码体制的分析； 二是利用单光子的测不准原理在光纤级实现密钥管理二是利用单光子的测不准原理
13、在光纤级实现密钥管理和信息加密，即量子密码学。和信息加密，即量子密码学。v量子计算机是一种传统意义上的超大规模并行计量子计算机是一种传统意义上的超大规模并行计算系统，利用量子计算机可以在几秒钟内分解算系统，利用量子计算机可以在几秒钟内分解RSA129的公钥。的公钥。量子计算机处理器量子计算机处理器DNA密码技术密码技术v随着随着DNA计算的发展，有科学家开始把计算的发展，有科学家开始把DNA用于密用于密码学领域。码学领域。Reif等人提出用等人提出用DNA实现一次一密的密实现一次一密的密码系统，码系统，Celland等人提出用等人提出用DNA隐藏消息。隐藏消息。v Dan Boneh等人用等人
14、用DNA计算机破译了计算机破译了DES，并且声，并且声称任何小于称任何小于64位的密钥都可以用这种方法破译位的密钥都可以用这种方法破译vSalomaa也宣称现有的很多数学困难问题可以通过也宣称现有的很多数学困难问题可以通过DNA计算机进行穷举搜索得到结果，而其中很多困计算机进行穷举搜索得到结果，而其中很多困难问题都是现代密码系统的安全依据。难问题都是现代密码系统的安全依据。什么是密码学什么是密码学v密码学基本概念密码学基本概念v密码体制分类密码体制分类密码学基本概念密码学基本概念v密码学密码学(cryptology) ： 研究信息的保密和复原保密信息以获取其真实内容的研究信息的保密和复原保密信
15、息以获取其真实内容的学科称为密码学。学科称为密码学。v包括：包括： 密码编码学密码编码学(cryptography)：研究对信息进行编码，实：研究对信息进行编码，实现隐蔽信息的一门学科。现隐蔽信息的一门学科。 密码分析学密码分析学(cryptanalytics)：不知道任何加密细节的条：不知道任何加密细节的条件下解密消息的技术，即件下解密消息的技术，即“破译破译”。密码编码学密码编码学v （1）密码编码学是密码学的一个分支，研究与信息安全）密码编码学是密码学的一个分支，研究与信息安全（例如：机密性、完整性、可鉴别性）有关的数学技术。（例如：机密性、完整性、可鉴别性）有关的数学技术。v （2）密
16、码编码学是包含数据变换的原理、工具和方法的）密码编码学是包含数据变换的原理、工具和方法的一门学科，这种数据变换的目的是为了隐藏数据的信息内一门学科，这种数据变换的目的是为了隐藏数据的信息内容，阻止对数据的篡改以及防止未经认可使用数据。容，阻止对数据的篡改以及防止未经认可使用数据。v （3）密码编码学是论述使明文变得不可懂的密文，以及）密码编码学是论述使明文变得不可懂的密文，以及把已加密的消息变换成可懂形式的艺术和技巧。把已加密的消息变换成可懂形式的艺术和技巧。v 加密（加密（Encryption）：将明文变换为密文的过程。把可懂的语：将明文变换为密文的过程。把可懂的语言变换成不可懂的语言，这里
17、的语言指人类能懂的语言和机器能言变换成不可懂的语言，这里的语言指人类能懂的语言和机器能懂的语言。懂的语言。v 解密（解密（Decryption）：加密的逆过程，即由密文恢复出原明文：加密的逆过程，即由密文恢复出原明文的过程。把不可懂的语言变换成可懂的语言。的过程。把不可懂的语言变换成可懂的语言。加密算法加密算法密钥密钥密文密文明文明文解密算法解密算法密钥密钥密文密文明文明文加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别称为称为加密密钥加密密钥(Encryption Key) 和和解密密钥解密密钥(Decryption Key
18、)。加密：加密：Ek(M) = C 解密：解密：Dk (C) = M密码学基本概念密码学基本概念Kerckhoff原理原理Auguste Kerckhoff在在1883年发表了一篇论文，认为一个年发表了一篇论文，认为一个密码系统中唯一应该保密的只有密钥。他认为，密码算法密码系统中唯一应该保密的只有密钥。他认为，密码算法应该对外公开，如果一个密码系统需要保密的越多，可能应该对外公开，如果一个密码系统需要保密的越多，可能的弱点也越多。的弱点也越多。这种观点对于密码研究者和私营部门来说已经是一种常这种观点对于密码研究者和私营部门来说已经是一种常识，但是军事部门和政府则不这么认为。世界上大部分的识，但
19、是军事部门和政府则不这么认为。世界上大部分的政府都研制自己的算法并且不对外公开。政府都研制自己的算法并且不对外公开。Kerchhoff假设假设：密码分析者知道双方使用的密码系统，密码分析者知道双方使用的密码系统，包括明文的统计特性、加解密体制等，唯一不知道的是包括明文的统计特性、加解密体制等，唯一不知道的是密钥。密钥。在设计一个密码系统时，目标是在在设计一个密码系统时，目标是在Kerckhoffs 假设的前假设的前提下实现安全提下实现安全 。密码体制分类的三种方法密码体制分类的三种方法v替代密码替代密码 vs. 换位密码换位密码v对称密码算法对称密码算法 vs. 非对称密码算法非对称密码算法v
20、分组密码分组密码 vs. 流密码流密码密码体制分类密码体制分类v按转换明文为密文的运算类型分类：按转换明文为密文的运算类型分类：v替替代代密码密码（Substitution Cipher）：）： 就是明文中的每一个字符被替换成密文中的另一个字就是明文中的每一个字符被替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。符。接收者对密文做反向替换就可以恢复出明文。v置换密码置换密码（Permutation Cipher）：）： 又称又称换位密码换位密码(Transposition Cipher)：明文的字母保：明文的字母保持相同，但顺序被打乱了。持相同，但顺序被打乱了。密码体制分类密
21、码体制分类v 按所用的密钥数分类：按所用的密钥数分类：v 对称密码算法对称密码算法（Symmetric cipher）：加密密钥和解密密）：加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称钥相同，或实质上等同，即从一个易于推出另一个。又称传统密码算法（传统密码算法（Conventional cipher)、秘密密钥算法或、秘密密钥算法或单单密钥算法密钥算法。 DES、3DES、IDEA、AESv 非对称密码算法非对称密码算法（Asymmetric cipher） ：加密密钥和解：加密密钥和解密密钥不同，从一个很难推出另一个。又叫公钥密码算法密密钥不同，从一个很难推出另一个。又
22、叫公钥密码算法（Public-key cipher)。其中的加密密钥可以公开，称为公。其中的加密密钥可以公开，称为公开密钥（开密钥（public key)，简称，简称公钥公钥；解密密钥必须保密，称；解密密钥必须保密，称为私人密钥（为私人密钥（private key)，简称，简称私钥私钥。 RSA、ECC、ElGamal密码体制分类密码体制分类v按处理明文的方法分类：按处理明文的方法分类：v分组（块）密码分组（块）密码： 将明文分成固定长度的组，用同一密钥和算法对每一将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文；块加密，输出也是固定长度的密文； DES、IDEA、
23、RC2、RC4、RC5；v序列（流）密码序列（流）密码： 序列密码每次加密一位或一字节的明文；序列密码每次加密一位或一字节的明文； One-time padding、Vigenre、Vernam；流密码模型流密码模型24密钥流密钥流产生器产生器密钥密钥k明文明文m密文密文c流密码体制模型流密码体制模型异或运算v明文为明文为“university”，密钥流为，密钥流为key=(xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx xxxxxxx) 分组密码模型分组密码模型v分组密码分组密码是将明文消息编码表
24、示后的数字（简称是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为明文数字）序列，划分成长度为n的组（可看成的组（可看成长度为长度为n的矢量），每组分别在密钥的控制下变的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。换成等长的输出数字（简称密文数字）序列。密码分析学密码分析学v 攻击传统密码体制的一般方法：攻击传统密码体制的一般方法： 穷举攻击穷举攻击： 对一条密文对一条密文尝试所有可能的密钥尝试所有可能的密钥。平均而言，。平均而言，成功至少需要尝试所有可能密钥的一半。成功至少需要尝试所有可能密钥的一半。 密码分析密码分析：利用：利用算法算法的性质和的性质
25、和明文的特征明文的特征或某些或某些明密文明密文对对。v密码分析学密码分析学是在不知道密钥的情况下，恢复出明是在不知道密钥的情况下，恢复出明文的科学；文的科学；v成功的密码分析能恢复出消息的明文或密钥；成功的密码分析能恢复出消息的明文或密钥；密码分析学密码分析学v （1）密码分析学是密码学的一个分支，它与另一个分支）密码分析学是密码学的一个分支，它与另一个分支学科学科密码编码学是两个相互对立、相互依存、相辅相密码编码学是两个相互对立、相互依存、相辅相成、相互促进的学科。成、相互促进的学科。v （2）密码分析学是企图挫败编码技术以及更一般说来的）密码分析学是企图挫败编码技术以及更一般说来的信息安全
26、服务的数学技术学科。信息安全服务的数学技术学科。v （3）密码分析学是对密码体制、密码体制的输入输出关）密码分析学是对密码体制、密码体制的输入输出关系进行分析，以便推出机密变量、包括明文在内的敏感数系进行分析，以便推出机密变量、包括明文在内的敏感数据。有时又称作密码破译学（据。有时又称作密码破译学（code breaking）密码分析攻击的典型方式密码分析攻击的典型方式v 假设通信双方，假设通信双方，Alice和和Bob已经完成了秘钥交换，秘钥已经完成了秘钥交换，秘钥k是双方已知的，开始进行如下通信：是双方已知的，开始进行如下通信：AliceBob密码分析攻击的典型方式密码分析攻击的典型方式v
27、攻击者已知加密算法，已知待破解的密文：攻击者已知加密算法，已知待破解的密文： v唯密文攻击唯密文攻击： 密码分析者有一些消息的密文，这些消息都用同一加密码分析者有一些消息的密文，这些消息都用同一加密算法加密。密算法加密。 密码分析者的任务是恢复尽可能多的明文，或者最好密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。钥解出其他被加密的消息。 密码分析攻击的典型方式密码分析攻击的典型方式v攻击者已知加密算法，已知待破解的密文，已知攻击者已知加密算法，已知待破解的密文，已知一条或者多条明
28、文一条或者多条明文-密文对；密文对；v已知明文攻击已知明文攻击： 密码分析者不仅可得到一些消息的密文，而且也知道密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。这些消息的明文。 分析者的任务就是用加密信息推出用来加密的密钥或分析者的任务就是用加密信息推出用来加密的密钥或推导出一个算法，此算法可以对用同一密钥加密的任推导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。何新的消息进行解密。 密码分析攻击的典型方式密码分析攻击的典型方式v攻击者已知加密算法，已知待破解的密文，能够攻击者已知加密算法，已知待破解的密文，能够获得通过加密算法生成自选的明文获得通过加密算法生成自
29、选的明文-密文对；密文对；v选择明文攻击选择明文攻击： 分析者不仅可得到一些消息的密文和相应的明文，而分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密可以对用同一密钥加密的任何新的消息进行解密
30、.v通常，加密算法被设计成能够抵御已知明文攻击通常，加密算法被设计成能够抵御已知明文攻击攻击强度：唯密文攻击攻击强度：唯密文攻击 已知明文攻击已知明文攻击 选择明文攻击选择明文攻击密码分析攻击的典型方式密码分析攻击的典型方式v自适应选择明文攻击自适应选择明文攻击： 这是选择明文攻击的特殊情况。密码分析者不仅能选这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加密的明文，而在自适应选择密文攻击中择一大块被加
31、密的明文，而在自适应选择密文攻击中，可选取较小的明文块，然后再基于第一块的结果选，可选取较小的明文块，然后再基于第一块的结果选择另一明文块，依此类推。择另一明文块，依此类推。v选择密文攻击选择密文攻击： 密码分析者能选择不同的被加密的密文，并可得到对密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。自动解密盒，密码分析者的任务是推出密钥。两个概念两个概念v绝对安全，绝对安全，unconditional security 无论花多少时间，攻击者都无法将密文解密无论花多少
32、时间，攻击者都无法将密文解密 原因：攻击者所需要的信息不在密文里。原因：攻击者所需要的信息不在密文里。 除一次一密外，所有的加密算法都不是绝对安全的除一次一密外，所有的加密算法都不是绝对安全的v计算安全，计算安全，computational security 破译密码的代价超过密文信息的价值；破译密码的代价超过密文信息的价值； 破译密码的时间超出了密文信息的有效生命期。破译密码的时间超出了密文信息的有效生命期。穷举攻击穷举攻击32232 = 4.3 109231 s = 35.8 minutes2.15 milliseconds56256 = 7.2 1016255 s = 1142 year
33、s10.01 hours1282128 = 3.4 10382127 s = 5.4 1024 years5.4 1018 years1682168 = 3.7 10502167 s = 5.9 1036 years5.9 1030 years26 characters (permutation)26! = 4 10262 1026 s= 6.4 1012 years6.4 106 years主要内容主要内容v数据加密概述数据加密概述v传统密码技术传统密码技术 （一）替代技术（一）替代技术 （二）换位技术（二）换位技术v对称密钥密码技术对称密钥密码技术v公钥密码体制公钥密码体制v数字签名与认证
34、技术数字签名与认证技术v加密软件加密软件（一）替代技术（一）替代技术v替代法：替代法： 将明文字母替换成其他字母、数字或符号的方法；将明文字母替换成其他字母、数字或符号的方法； 如果把明文看成是如果把明文看成是0或或1的序列，那么密文就是的序列，那么密文就是0或或1比比特序列的另一种表达。特序列的另一种表达。v包括：包括： （1）凯撒密码）凯撒密码 （2）单表替代密码）单表替代密码 （3）多表替代密码）多表替代密码（1）凯撒密码（）凯撒密码（Caesar Cipher）v由古罗马人由古罗马人Julius Caesar发明的一种密码体制，发明的一种密码体制，它是使用最早的密码体制之一；首先用在军
35、事通它是使用最早的密码体制之一；首先用在军事通信中；信中；v替代原理：替代原理： 用字母后的第三个字母代替用字母后的第三个字母代替 字母表看作是循环的，即字母表看作是循环的，即z后面的字母是后面的字母是a明明 文文abcdefghijklm nopqrstuv w xyz密密 文文D E F G H I J K L M N O P Q R S T U V W X Y Z A B C凯撒密码凯撒密码v映射表中，明文字母中在字母表中的相应位置数映射表中，明文字母中在字母表中的相应位置数为为C，（如，（如A=1，B=2，）形式如下：）形式如下：设设k3；对于明文；对于明文Pcompute syste
36、ms则则f（C）=（3+3） mod 26=6=Ff（O）=（15+3）mod 26=18=Rf（M）=（13+3）mod 26=16=Pf（S）=（19+3） mod 26=22=V密文密文C= Ek（P）=FRPSXRWHUVBVWHPV。凯撒凯撒密码的一般形式密码的一般形式v将英文字母表左环移将英文字母表左环移k（0k26）位得到替）位得到替换表，则得一般的换表，则得一般的Caesar算法。算法。v共有共有26种可能的密码算法（种可能的密码算法（25种可用）种可用）v将每个字母分配一个数值，如将每个字母分配一个数值，如a0，b=1等，等，则算法可表示为：则算法可表示为： 加密算法：加密算
37、法：C = Ek(P) = (P + k) mod 26 解密算法：解密算法：P = Dk(C) = (C k) mod 26凯撒密码的安全性分析凯撒密码的安全性分析 v凯撒密码的三个特征：凯撒密码的三个特征： 加密和解密算法已知加密和解密算法已知 需尝试的密钥只有需尝试的密钥只有25个个 所破译的明文语言已知，其意义易于识别所破译的明文语言已知，其意义易于识别 大多数情况下，密码算法是已知的，这三个特征使大多数情况下，密码算法是已知的，这三个特征使穷穷举攻击举攻击很容易实现很容易实现v抗攻击分析：抗攻击分析： 使明文的语言未知：例如将明文压缩再进行加密使明文的语言未知：例如将明文压缩再进行加
38、密 加大密钥空间：如允许字母的任意替代加大密钥空间：如允许字母的任意替代（2）单表替代密码）单表替代密码v不是简单有序地字母移位不是简单有序地字母移位 v每个明文字母映射到一个不同的随机密文字母每个明文字母映射到一个不同的随机密文字母 v密钥数目：密钥数目： 26！ v包括：包括： 棋盘密码棋盘密码 仿射密码仿射密码 移位代换密码：凯撒密码移位代换密码：凯撒密码 多项式代换密码多项式代换密码 乘数乘数/采样密码采样密码 密钥短语密码密钥短语密码单表替代密码分析单表替代密码分析v密钥空间：密钥空间： 26! 4 x 1026 大于大于56位位DES(数据加密标准数据加密标准)的密钥空间的密钥空间
39、v貌似安全，实则不然貌似安全，实则不然 ： 基于语言统计规律仍可破译基于语言统计规律仍可破译单表替代密码分析单表替代密码分析v 举例：举例：v 字母相对频率分析：字母相对频率分析：英文字母英文字母相对频率相对频率单表替代密码分析单表替代密码分析v 初步分析：初步分析：v 解密结果：解密结果：v 解决方法：目标解决方法：目标-减少密文中的明文结构残留度减少密文中的明文结构残留度 字母组合加密：字母组合加密：playfair密码密码 多表替代密码：多表替代密码：Vigenre密码密码Playfair密码密码v单表替代缺陷是：密文带有原始字母使用频率的单表替代缺陷是：密文带有原始字母使用频率的一些统
40、计学特征。一些统计学特征。v对策：每个字母提供多种代换。对策：每个字母提供多种代换。v最著名的多表代换密码最著名的多表代换密码 Playfair密码密码: Charles Wheatstone 于于1854年发明年发明, 用其朋友用其朋友Baron Playfair 命名命名 把明文中的双字母音节作为一个单元并将其转换成密把明文中的双字母音节作为一个单元并将其转换成密文的文的“双字母音节双字母音节”Playfair密钥矩阵密钥矩阵v 加密结果基于一个加密结果基于一个 5 x 5 字母矩阵字母矩阵v从左到右，从上到下：从左到右，从上到下： 填写密钥单词填写密钥单词 用其他字母填写剩下的空缺用其他
41、字母填写剩下的空缺vI = JMONARCHYBDEFGI/JKLPQSTUVWXZmonarchy为密钥为密钥加加/解密步骤解密步骤v加密加密 明文分组（填充）：明文分组（填充）：2个字母组个字母组 同行字母对加密：循环向右，同行字母对加密：循环向右，eiFK 同列字母对加密：循环向下，同列字母对加密：循环向下，cuEM，xiAS 其它字母对加密：矩形对角线字母，且按行排序，其它字母对加密：矩形对角线字母，且按行排序，hsBP，esIL（或（或JL）v解密解密 加密的逆向操作加密的逆向操作安全性分析安全性分析v安全性优于简单的单表代换密码：安全性优于简单的单表代换密码： 共有共有26x26个
42、字母对，判断单个字母对困难；个字母对，判断单个字母对困难； 字母对的相对频率的统计规律低于单个字母的频率；字母对的相对频率的统计规律低于单个字母的频率； 利用频率分析字母对较困难；利用频率分析字母对较困难；v虽然明文中字母的统计规律在密文中得到了降低，虽然明文中字母的统计规律在密文中得到了降低，但密文中仍含有明文的部分结构信息；但密文中仍含有明文的部分结构信息；v给定几百个字母，即可被攻破；给定几百个字母，即可被攻破；字母出现的相对频率字母出现的相对频率（3）多表替代密码）多表替代密码v替代规则：替代规则： 使用一系列相关的单表替代规则使用一系列相关的单表替代规则 密钥决定给定变换的具体规则密
43、钥决定给定变换的具体规则v例如：例如： Vigenre密码密码（1858） Beaufort 密码密码 Vernam密码密码Vigenre方阵方阵使用一系列单表替代规则使用一系列单表替代规则密钥密钥决定给定变换的具体规则决定给定变换的具体规则Vigenre密码示例密码示例v加密过程：加密过程： P“encode and decode”，k“mykey”字母序号encodeanddecode明文编码P =4132143401333421434密钥编码k =122410424122410424122410424加密C =1637121827162423727162624728模运算111102密文
44、C =QLMSBQYXHBQAYHC明文中不同位置的相同字母，被映明文中不同位置的相同字母，被映射为不同的字母射为不同的字母Vigenre密码示例密码示例v解密过程：解密过程： C“QLMSBQYXHBQAYHC”，k“mykey”字母序号123456789101112131415密文编码C=161112181162423711602472密钥编码k=122410424122410424122410424加密C=4-13214-2340133-234-24143-22模运算133324密文解码C=encodeanddecodeVigenre密码密码加密过程加密过程：v数学公式计算数学公式计算
45、设明文设明文 P = p1p2pn，密钥，密钥 K = k1k2km，密文，密文C = c1c2cn 加密：加密： ci= ( pi+ki mod m) mod 26； 说明：若明文长度大于说明：若明文长度大于n，则，则k重复使用。重复使用。Vigenre密码密码解密过程解密过程：v数学公式计算数学公式计算 pi = (ciki mod m ) mod 26；安全性分析安全性分析v每个明文字母对应着多个密文字母，明、密文字每个明文字母对应着多个密文字母，明、密文字母不是一一对应关系母不是一一对应关系v一条消息中，同样的字母在不同的位置映射成不一条消息中，同样的字母在不同的位置映射成不同的密文；
46、同的密文；v字母的统计规律进一步降低；字母的统计规律进一步降低；vVigenre本人建议：密钥与明文一样长；本人建议：密钥与明文一样长；vVigenre代换表中的每一行就是一代换表中的每一行就是一Caesar密码；密码；安全性分析安全性分析v举例：举例：v 密文用数字描述后：密文用数字描述后：v 密码分析思路：密码分析思路： 集中精力找到密钥长度；集中精力找到密钥长度； 采用单表替代分析方法；采用单表替代分析方法；Germany: Enigma轮转机密码系统轮转机密码系统v Arthur Scherbius于于1919年发明，年发明，4轮轮Enigma在在1944年装备到德国海军，使得英年装备
47、到德国海军，使得英国从国从1944年年2月到月到12月没有检测到德国潜月没有检测到德国潜艇信号。艇信号。v 基于多表替代密码的原理；基于多表替代密码的原理；v 重要性质：重要性质：v 反射器使得恩格玛机的加密过程是自反反射器使得恩格玛机的加密过程是自反的；的；v 一个字母加密后的输出结果绝不会是它一个字母加密后的输出结果绝不会是它自身自身v 密码表数量：密码表数量：10万以上（二）换位密码（二）换位密码 Transposition Ciphersv换位换位： 对明文字母的某种置换，采用移位发进行加密；对明文字母的某种置换，采用移位发进行加密； 明文中的字母重新排列，位置发生变化；明文中的字母重
48、新排列，位置发生变化；v栅栏技术栅栏技术：按对角线的顺序写出明文，以行的顺：按对角线的顺序写出明文，以行的顺序读出作为密文序读出作为密文 易破译易破译v矩阵排列法：矩阵排列法： 纯置换密码易识别纯置换密码易识别v多次置换多次置换：多阶段加密，安全性更高：多阶段加密，安全性更高v明文：明文：meet me after the toga partyv写为写为:m e m a t r h t g p r y e t e f e t e o a a tv读出密文为：读出密文为：MEMATRHTGPRYETEFETEOAATv带有密钥带有密钥v再改进：重复加密，多步置换再改进：重复加密，多步置换61v
49、更加复杂的移位更加复杂的移位v 以指定的行将明文写作多行以指定的行将明文写作多行v 按照密钥指定的列读出按照密钥指定的列读出 Key: Plaintext: Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ a tta c k po s tp o n ed u n tiltw o a m x y z62矩阵排列法主要内容主要内容v数据加密概述数据加密概述v传统密码技术传统密码技术v对称密钥密码技术对称密钥密码技术 Feistel密码结构密码结构 数据加密标准数据加密标准DESv公钥密码体制公钥密码体制v数字签名数字签名与与认证技术认证技术v加密软件加密软件对称密
50、码算法对称密码算法v数据加密标准（数据加密标准（DES）v国际数据加密算法（国际数据加密算法（IDEA）v高级数据加密标准（高级数据加密标准（AES）对称加密的安全性取决于密钥的安全，而非算法的安全。对称加密的安全性取决于密钥的安全，而非算法的安全。Alice加密机加密机解密机解密机Bob安全信道安全信道密钥源密钥源Oscar明文明文x密文密文y密钥密钥k明文明文x密钥密钥k对称加密模型对称加密模型密码学的目的密码学的目的：Alice和和Bob两个人在不安全的信道上进两个人在不安全的信道上进行通信，而破译者行通信，而破译者Oscar不能理解他们通信的内容。不能理解他们通信的内容。回顾回顾v代替
