信息网络安全：原理、技术及应用 课件第2章 加密技术（上）

通信安全基础第二章加密技术（上）密码学基础古典密码对称密码公钥密码一二三四1、密码学内涵cryptology源于希腊语“kryptós”“gráphein”，直译“隐藏的”“书写”早期指一种掩盖文字真实内容的密写技术《简明牛津英语词典（第9版）》：密码学是编码或解码的艺术（编码：一种预先安排好专用于确保传输消息时的保密性的信号系统）仅关注秘密通信问题，且认为密码是一种艺术20世纪信息论和计算机科学的发展，使得密码学开始成为一种科学密码学的目的是隐藏信息的涵义，并不是隐藏信息的存在密码学从军事和智囊机构处理秘密通信的艺术变成保障全球信息网络和通信系统安全的科学。2、密码学分类密码编码学建立各种类型的密码系统密码分析学对密码系统进行攻击破译密码密钥学密钥的产生、分配、存储、保护、销毁密码学在编码与破译的斗争实践中逐步发展起来，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、生物学、量子力学、计算机科学等都有着广泛而密切的联系。3、密码学与通信安全密码学是通信安全的理论基石通信安全是密码学的实践应用领域密码学为通信安全提供了理论和方法支持，通过加密、解密、认证等技术，确保信息在传输过程中的机密性、完整性和可用性通信安全的目标是保护信息在传输过程中不被窃取、篡改或伪造，密码学的理论和技术直接服务于这一目标4、密码学简史古老“人类使用密码的历史几乎与使用文字的时间一样长”。 ——《破译者》，戴维·卡恩年轻20世纪70年代中期后，密码学才成为一门科学4、密码学简史（1）～1949：古典密码可以看作是密码科学的前夜时期密码常常带有神秘色彩被人们当成是一种巫术分为手工阶段和机械阶段4、密码学简史（1）～1949：古典密码手工阶段《山海经·大荒西经》：“西南海之外，赤水之南，流沙之西，有人珥两青蛇，乘两龙，名曰夏后开。公元前1900年，古埃及一位祭司在贵族的墓碑上书写铭文时，有意用变形的象形文字而不是普通的象形文字来写铭文，揭开了有文字记载的密码史4、密码学简史（1）～1949：古典密码手工阶段古巴比伦时代的Phaistos圆盘，表面有明显间距的符号，有研究学家认为它是古巴比伦人的加密工具公元前4世纪，古斯巴达的Scytale是人类历史上最早使用的密码器械4、密码学简史（1）～1949：古典密码手工阶段公元前1世纪，古罗马恺撒在高卢战争中使用了替代密码。公元2世纪，历史学家苏托尼厄斯写的《凯撒传》中进行了记载公元9世纪，阿拉伯阿尔·金迪提出频度分析方法，通过分析密文字符出现的频率破译密码，比西方同类文献早了300年公元16世纪晚期，英国的菲利普斯利用频度分析法成功破解苏格兰女王玛丽的密码信，信中策划暗杀英国女王伊丽莎白，这次解密将玛丽送上了断头台4、密码学简史（1）～1949：古典密码手工阶段小结针对的是字符采用纸、笔、简单加密设备基本操作：替代、置换简单的密码分析手段出现4、密码学简史（1）～1949：古典密码机械阶段1917年，英国40号办公室情报机关破译了德国外长齐默尔曼的电报，促成了美国对德宣战18世纪60年代，随着工业革命兴起，密码学进入了机器时代1895年，无线电报诞生，各国开始研究无线电密码编制和破译一战是世界密码史上的第一个转折点，密码科学迅速发展4、密码学简史（1）～1949：古典密码机械阶段二战爆发促进了密码科学的飞速发展1944年，美国海军22.3舰艇编队缴获了纳粹德国专门用于U型潜艇通讯联系的绝密的密码机和密码本。德国海军“狼群”作战彻底失败，改变了整个二战结局1942年，美国破译日本海军密报，获悉日军对中途岛地区的作战意图和兵力部署，以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局1943年，美国海军经过破译密码，掌握了日本海军大将山本五十六行踪，一举将其座机击落，山本死亡4、密码学简史（1）～1949：古典密码机械阶段二战期间，Enigma密码机令德军保密通讯技术处于世界领先地位盟军组织了一个上百名破译高手团队来破译Enigma密码。以图灵为首的专家们发明了具有实时破译等级的“炸弹”译码机4、密码学简史（1）～1949：古典密码机械阶段非机械方法：二战中，印第安纳瓦约土著语言被美军用作密码，当时纳瓦约族以外的美国人中，能听懂这种语言的也就一二十人，纳瓦约语密码在历史上从未被破译4、密码学简史（1）～1949：古典密码机械阶段小结从传统手工加密向现代电子加密过渡机械装置的使用使得加密算法更加复杂机械密码的复杂性催生了密码分析技术的进步密码攻防战成为战争的重要组成部分4、密码学简史（2）1949～1975：近代密码1949年，Shannon发表《保密系统的通信理论》，信息论为密码学奠定了理论基础，从此密码学成为一门科学1950年代，随着通用计算机的出现及发展，强大的计算能力使得复杂加密算法的实现成为可能，同时也加速了密码分析技术的进步密码学研究和应用主要集中在军事和外交领域，研究工作大多是秘密进行的。只有政府才有权利生成和破译密码。公开的密码文献极少，很多技术细节至今未公布4、密码学简史（2）1949～1975：近代密码小结从经验主义转向基于信息论和数学的科学体系计算机技术的引入使得密码算法的设计需要抵抗各类已知的攻击方法密码分析理论逐步形成密码学研究和应用主要集中在军事和外交领域4、密码学简史（3）1976～：现代密码学1977年，美国公布数据加密标准DES，开创了公开密码算法先例1976年，Diffie和Hellman在《密码学的新方向》中提出公钥密码体制，引起密码学史上一场里程牌式的革命1977年，MIT的Rivest、Shamir、Adleman共同提出一种实用的RSA公钥密码算法20世纪90年代，逐步出现椭圆曲线等其它公钥密码算法2000年，由VincentRijmen和JoanDaemen所设计的Rijndael算法取代DES成为新的高级加密标准AES4、密码学简史（3）1976～：现代密码学混沌密码学：混沌密码学利用混沌系统的非线性特性、对初始条件和参数的敏感性以及伪随机性来实现加密量子密码学：量子密码学基于量子力学的测不准原理和不可克隆性，利用量子态的特性实现信息的安全传输后量子密码学：后量子密码学专注于开发抗量子攻击的加密算法，这些算法旨在抵抗量子计算机的威胁DNA密码学：DNA密码学利用DNA分子的超高存储密度和大规模并行计算能力，将信息存储在DNA分子中，通过分子处理技术实现加密、隐写和签名认证属性基密码学、同态密码学、安全多方计算密码学、零知识证明密码学……4、密码学简史（3）1976～：现代密码学小结密码学从军事领域走向商业应用，成为信息安全的基石公钥密码学诞生，成为密码学的革命性突破密码算法的设计既要考虑理论，又要考虑实现和使用，成为一项工程密码学与数学、计算机科学、物理学、生物学等学科深度融合，催生了新的研究方向5、定义与基本概念（1）Shannon密钥密码系统模型5、定义与基本概念（1）Shannon密钥密码系统模型发送者：信息传送过程中主动提供信息的一方接收者：得到信息的一方明文：作为加密输入的原始消息密文：实施了加密的消息加密：由明文到密文的变换的过程解密：合法接收者从密文恢复出明文的过程破译：非法接收者试图从密文分析出明文的过程5、定义与基本概念（1）Shannon密钥密码系统模型加密算法：对明文进行加密时采用的一组规则解密算法：对密文解密时采用的一组规则加密算法和解密算法是在一组仅有合法用户知道的秘密信息，称为密钥（Key）的控制下进行的加密密钥：加密过程中使用的密钥解密密钥：解密过程中使用的密钥5、定义与基本概念（2）密码系统六元组(M,C,Ke,Kd,Eke,DKd)为密码系统/密码体制①M明文消息空间所有可能的明文集合②C密文消息空间所有可能的密文集合③Ke密钥空间K中的加密密钥密钥空间K是所有可能的密钥集合④Kd密钥空间K中的解密密钥⑤EKe加密密钥Ke控制的加密算法对于k=(Ke,Kd)∈K,存在EKe∈E,使Eke:M

C，E为加密变换集合⑥DKd解密密钥Kd控制的解密算法对于k=(Ke,Kd)∈K,存在DKd∈D,使DKd

:C

M，D为解密变换集合5、定义与基本概念（2）密码系统柯克霍夫原则（Kerckhoffs’sprinciple）:荷兰密码学家AuguesteKerckhoffs提出——Acryptosystemshouldbesecureevenifeverythingaboutthesystem,exceptthekey,

ispublicknowledge.知，只要密钥未泄漏，它也应是安全的。古典密码和现代密码的分界线密码强度的衡量标准密码算法的安全性完全寓于密钥5、定义与基本概念（2）密码系统已知明文m∈M，加密密钥Ke，计算密文c=EKe(m)容易已知密文c∈C，解密密钥Kd，计算明文m=DKd(c)容易已知明文m∈M，

但不知加密密钥Ke，就不能计算出密文c=EKe(m)已知密文c∈C，但不知解密密钥Kd，

就不能推出明文m=DKd(c)

密码算法的安全性完全寓于密钥5、定义与基本概念（3）密码分析法密码分析是一门无须取得密钥而能将密文信息恢复成明文的学问。

攻击者：恢复明文，窃取机密信息设计者：分析体制的弱点从密码的分析途径来看，密码分析的三种方法穷举法/暴力法统计分析法解密变换法5、定义与基本概念（3）密码分析法穷举法/暴力法：对截获的密文依次用各种可能的密钥破译，或对所有可能的明文加密直到与截获的密文一致为止时间和代价！！！密钥长度(比特)密钥空间大小每秒尝试100万个密钥（目前最快的PC）每秒尝试1千万亿个密钥（天河1号）32232=4.3

10935.8分钟2.15毫秒56256=7.2

10161142年10.01小时1282128=3.4

10385.4

1024

年5.4

1018

年1682168=3.7

10505.9

1036

年5.9

1030

年5、定义与基本概念（3）密码分析法统计分析法：通过分析密文和明文的统计规律来破译。经常针对对称密码系统实施。因为对称密码通常都有标准模块化结构，明文的结构在加密后仍然会留下蛛丝马迹解密变换法：针对密码变换的数学基础，通过数学求解的方法找到相应的解密变换。经常针对公钥密码系统实施。因为公钥密码大都基于数学难题设计的5、定义与基本概念（3）密码分析法根据密码分析者知道信息的多少，常见的几种攻击类型唯密文攻击（ciphertext-onlyattack）已知明文攻击（known-plaintextattack）选择明文攻击（chosen-plaintextattack）选择密文攻击（chosen-ciphertextattack）5、定义与基本概念（3）密码分析法唯密文攻击（ciphertext-onlyattack）待破译的密文这些密文是使用同一加密算法加密得到的恢复尽可能多的明文最好导出用于加密消息的密钥或者推出可以解密相同密钥加密的任何新消息的算法条件目的5、定义与基本概念（3）密码分析法已知明文攻击（known-plaintextattack）待破译的密文有一些消息的明-密文对这些密文是使用同一加密算法加密得到的恢复尽可能多的明文导出用于加密消息的密钥或者推出可以解密相同密钥加密的任何新消息的算法条件目的5、定义与基本概念（3）密码分析法选择明文攻击（chosen-plaintextattack）待破译的密文密码攻击者选择的明文并获得相应的密文这些密文是使用同一加密算法加密得到的恢复尽可能多的明文导出用于加密消息的密钥或者推出可以解密相同密钥加密的任何新消息的算法条件目的5、定义与基本概念（3）密码分析法选择密文攻击（chosen-ciphertextattack）待破译的密文密码攻击者选择的密文并获得相应的明文这些密文是使用同一加密算法加密得到的恢复尽可能多的明文导出用于加密消息的密钥条件目的5、定义与基本概念（3）密码分析法类型分析者己知的信息目的唯密文攻击密码算法待破译的密文尽可能多地恢复明文信息导出密钥推出一个解密用相同密钥加密的新消息的算法已知明文攻击密码算法待破译的密文一个或多个明-密文对选择明文攻击密码算法待破译的密文分析者选择的明文及相应的密文选择密文攻击密码算法待破译的密文分析者选择的一些密文及相应的已破译的明文常见的几种攻击类型5、定义与基本概念（4）密码系统安全性无条件安全（Unconditionallysecure）破译者计算资源没有限制，即使拥有无穷多计算资源和密文，也不能解出明文，即使解出明文，也无法验证结果的正确性。计算安全（Computationallysecure）破译密码成本超过信息价值，或破译时间超过信息生命周期。可证明安全（Provablesecure）破译难度归约为某个不可解的基础算法或数学难题。1、隐写术Steganography源于古希腊词汇stegons（隐藏、隐蔽）和graphia（书写、记录），意为“隐藏的书写”一种信息隐藏技术：将秘密消息隐藏在其它消息中，保密信息随着载体公开传递而传递历史上用过形形色色的隐写术头皮刺青蜡板隐写以矾书帛字验隐形墨水微缩胶片格孔密写卡藏头诗1、隐写术藏头诗1、隐写术隐蔽性强，不易发现适用于多种载体信息容量有限构造复杂且耗时一旦发现，毫无价值稳健性差优点缺点2、替代密码将明文字符替换成其它字母、数字或符号。对密文字符进行逆替换。加密解密（1）单表替代

（2）同音替代

（3）多元替代

（4）多表替代

2、替代密码（1）单表替代移位密码例：PHHWPHDIWHUWKHSDUWB

meetmeaftertheparty密文明文将字母表的每个字母用其后的第三个字母代替明文密文明文密文2、替代密码（1）单表替代移位密码明文空间、密文空间：{A,B,

...,Z}，密钥空间：或M=

C

=

{0,1,...,25}，K={1,...,25}对m∈M,c∈C,k∈K

Ek(m)

=(m+k)mod26=c

Dk(c)=(c-k)mod26=mA=0B=1C=2D=3E=4F=5G=6H=7I=8J=9K=10L=11M=12N=13O=14P=15Q=16R=17S=18T=19U=20V=21W=22X=23Y=24Z=25{1,...,25}2、替代密码（1）单表替代仿射密码基本思想：用仿射变换生成替代表（仿射变换是线性变换加平移）M=

C

=

{0,

1,

...,25}，K

=

{(a,

b)

|

gcd(a,

26)=1(互素)}a,

b∈{0,

1,

...,25}对m∈M,c∈C,k

=(a,

b)∈K

Ek(m)

=

am+b

(mod26)=c

Dk(c)

=

a-1(c-b)

(mod26)=ma-1称为a的逆，满足a-1a

mod26

=

1，a-1存在的充要条件是gcd(a,

26)=1。2、替代密码（1）单表替代仿射密码例：k=

(a,

b)

=

(9,2)，明文n，问：a-1=?密文？解：a-1=3，

Ek(m)

=9m+2(mod26)

Dk(c)

=3(c-2)

(mod26)加密，将字母

n转换成数字

13，

c=9×13+2=119mod26=15→密文P解密，将字母

P转换成数字

15，m=3×(15-2)=39mod26=13→明文n2、替代密码（1）单表替代仿射密码例：k=(a,

b)=(7,

3)，写出加密和解密公式，明文hot，密文?解：a-1=15Ek(m)

=

7m+3

(mod26)Dk(c)

=15(c-3)

(mod26)对明文字母

h,o,t

(7,14,19)分别加密

7×7+3=52mod26=0→A7×14+3=101mod26=23→X7×19+3=136mod26=6→G2、替代密码（1）单表替代仿射密码例：k=(a,

b)=(7,

3)，写出加密和解密公式，密文AXG，明文?解：a-1=15Ek(m)

=

7m+3

(mod26)Dk(c)

=15(c-3)

(mod26)对密文字母

A,X,G

(0,23,6)分别解密

15×(0–3)=-45mod26=7→h15×(23–3)=300mod26=14→o15×(6–3)=45mod26=19→t2、替代密码（1）单表替代26字母任意替代密码基本思想：替代表由26个字母按随机规律任意排列生成2、替代密码（1）单表替代安全性分析|K|=25Alright密钥空间大小抗密钥穷举攻击Can’t移位密码26字母任意替代密码|K|=26!-1≈4×1026加解密使用一个固定的替代表进行代换2、替代密码（1）单表替代安全性分析：单表替代密码由于在加解密时使用的是一个固定的替代表进行代换，因此，如果明文字母相同，通过单表替代后，它们会被加密成相同的密文由此产生一种利用语言统计规律，根据字母出现的频率对密文进行破译的频率分析攻击法加解密使用一个固定的替代表进行代换Step1.

统计密文中出现的单字母频率，与英语字母标准频率分布进行对比分析，作出假设，尝试做一些替代，寻找消息的轮廓；Step2.还可通过研究双字母、三字母或四字母的密文组合作出假设，如区分元音和辅音字母；Step3.

证实步骤1、2的假设，如果不正确，继续作其它假设、分析、测试，直至得到完整明文。%英语单字母标准频率分布频率分析攻击2、替代密码（2）同音替代基本思想：隐藏明文结构在密文中的信息。把明文字符替换成不同的密文字符，就像同音词一样，一个读音可以表示多个单词例如，同音词bye，by，buysee，seawrite，right2、替代密码（2）同音替代ABCDEFGHIJKLMNOPQRSTUVWXYZ8.21.52.84.312.72.22.06.17.00.20.84.02.46.77.51.90.16.06.39.12.81.02.40.22.00.1ABCDEFGHIJKLMNOPQRSTUVWXYZ06625340296677164913880373950783204756946130488255977691346041744308334215523299789671592100143951094519631179927087384498188069722735100224863175259089238193268564540165224604378468125817365028675705英文字母频率表同音替代表2、替代密码（2）同音替代例：明文CRYPTOGRAPHYISVERYINTERESTING，密文？解：密文1324673564444186061043673289 172031579911544775562301787974I32997896715921I7.0观察I的加密2、替代密码（2）同音替代安全性分析同音替代密码能较好地抵抗频率分析攻击问题：多字母语法模式仍然残留在密文中，降低了密码分析的难度，如双字母频率，Q后面基本只接U等Q0.1Q02U2.8U6812582、替代密码（3）多元替代基本思想：隐藏明文结构在密文中的信息。对明文中的多个字符成组加密，相同的明文字符能被加密成不同的密文字符，隐藏单字母的频率Hill密码1929年，数学家LesterHill发明将i个连续的明文字母通过线性变换转换为i个密文字母2、替代密码（3）多元替代Hill密码M=

C

=

({0,1,...25})i

，i为正整数K

=({0,1,...25}上的i阶可逆方阵)对m∈M,c∈C,

K∈K,

EK(m)

=mK

(mod26)=c

DK(c)

=cK-1(mod26)=mK-1

：K的逆矩阵，满足K·K-1

mod26=I，K-1

存在的条件

gcd(det(K),

26)=1。2、替代密码（3）多元替代Hill密码例：明文

july，加密密钥，密文？解：根据密钥矩阵阶数，明文分成2组ju、ly，转换成(9

20)、(11

24)，加密DELW

密文DELW2、替代密码（3）多元替代Hill密码例：明文hill，加密密钥解：根据密钥矩阵阶数，将明文分成1组hill，转换成(7

81111)，加密后(9

8824)，密文JIIY2、替代密码（3）多元替代安全性分析多元替代密码很好地隐藏了单字母的频率特性，3×3以上的Hill密码还能隐藏双字母的频率特性，能有效抗频率分析攻击对Hill密码的已知明文攻击对于n×n的Hill密码，如果获得n个明-密文对，每个长度都是n，可计算出

K2、替代密码（4）多表替代基本思想：隐藏明文结构在密文中的信息。对明文消息的每个字符采用不同的单表替代，相同的明文字符被加密成不同的密文字符维吉尼亚（Vigenère）密码16世纪，法国外交家BlaisedeVigenère发明使用词组或句子作密钥，密钥的每个字母确定一个单表替代，密钥循环使用2、替代密码（4）多表替代Vigenère密码例：密钥best，明文

datasecurity解：按密钥长度4将明文分组datasecurity，每一组都用best加密data“+”best(mod26)=EELTsecu“+”best(mod26)=TIUNrity“+”best(mod26)=SMLR密文

EELTTIUNSMLR2、替代密码（4）多表替代Vigenère密码例：密钥best，密文

EELTTIUNSMLR解：按密钥长度4将密文分组EELTTIUNSMLR，每一组用best解密EELT“-”best(mod26)=dataTIUN“-”best(mod26)=secuSMLR“-”best(mod26)=rity明文datasecurity2、替代密码（4）多表替代Vigenère密码M=

C

=

({0,1,...25})jK

=

({0,1,...25})d,j,d正整数（通常d<j）对m=(m1,m2,…,mj)∈M,c=(c1,c2,…,cj)∈C，k=(k1,k2,…,kd)∈KEk(m)=(m1+k1,…,md+kd,md+1+k1,md+2+k2,…

)(mod26)Dk(c)=(c1-k1,…,cd-kd,cd+1-k1,cd+2-k2,…)(mod26)密钥空间大小？|K|

=

26d-12、替代密码（4）多表替代安全性分析多表替代密码使用了明文字符到密文字符的多映射，每个映射都是单表替代，能有效抗频率分析攻击Vigenère密码替代表若没有很好地使用算法，Vigenère密码对字母频率信息的隐藏不够彻底2、替代密码原理直观易懂适合手工操作或简单的机械实现实现简单安全性较低稳健性差不适合大规模通信优点缺点3、置换密码按规则对密文字符恢复明文不改变明文字符，而是按照某一规则改变字符在明文中的位置和次序，实现明文信息的加密解密（1）倒置（2）换位加密3、置换密码（1）倒置完全倒置：将明文字母按顺序依次倒置形成密文。例：明文internetinformationisimportant密文tnatropmisinoitamrofnitenretni分组倒置：将明文按固定长度分组，每组字母倒置，形成密文。例：明文internetinformationisimportant6个分组internetinformationisimportant密文nretniofniteoitamrpmisintnatro3、置换密码（2）换位栅栏技术：按对角线顺序写明文，按行顺序读出作为密