第二讲：密码学基础-2

公公司司徽徽标标9/1/20201第二讲：密码学基础主讲:张修军

Email:woodszhang@电话:88195226密码学基础教学目的通过本讲的学习，应能了解密码学的基本概念及简单加解密算法。教学重点1、密码系统模型，密码系统的基本特性2、对称/非对称密钥系统3、简单加解密算法及词频分析破解方法4、加密强度教学难点1、对称/非对称密钥系统2、简单加解密算法及词频分析破解方法3、加密强度一、密码学的基本概念9/1/20203密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问密码分析学(Cryptanalytics)，研究分析破译密码的学问。几个概念（一）明文(消息)(Plaintext)：被隐蔽消息。密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。9/1/20204几个概念（二）加密算法(Encryption

algorithm)：密码员对明文进行加密时所采用的一组规则。(替换法,变换法)接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。9/1/20205几个概念（三）密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passive

attack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Active

attack)：非法入侵者

(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。9/1/20206保密系统模型信源Mm加密器解密器接收者m非法接入者搭线信道（主动攻击）C

’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道9/1/20207保密系统应当满足的要求9/1/20208系统即使达不到理论上是不可破的，即

pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。认证与认证系统认证系统(Authentication

system)防止消息被窜改、删除、重放和伪造的一种有效方法,使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统保密性保密性是使截获者在不知密钥条件下不能解读密文的内容。认证性使任何不知密钥的人不能构造一个密报，使意定的接收者解密成一个可理解的消息(合法的消息)。9/1/20209安全认证系统应满足下述条件意定的接收者能够检验和证实消息的合法性和真实性。消息的发送者对所发送的消息不能抵赖。除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c和相应消息m下，要确定加密密钥或系统地伪造合法密文在计算

上是不可行的。必要时可由第三者作出仲裁。9/1/202010完整性(integrity)9/1/202011在有自然和人为干扰条件下，系统保持检测错误和恢复消息和原来发送消息一致性的能力。实际中常常借助于纠、检错技术和杂凑技术来保证消息的完整

性。二、密码体制分类9/1/202012·

密码体制有2大类：单钥体制(One-key

system)：加密密钥和解密密钥相同。双钥体制(Two

key

system)：加密密钥和解密密钥不同。密码体制分类单钥体制加密器EK解密器DK密文明文明文K密钥产生器K9/1/202013密码体制分类单钥体制9/1/202014单钥体制主要研究问题：密钥产生(Keygeneration)，密钥管理(Key

management)。分类：流密码(Streamcipher)分组密码(Block

cipher)单钥体制不仅可用于数据加密，也可用于消息的认证。密码体制分类双钥体制9/1/202015双钥体制或公钥体制(Public

key

system)(Diffie和Hellman,1976)每个用户都有一对选定的密钥(公钥k1；私钥

k2)，公开的密钥k1可以像电话号码一样进行注册公布。公钥体制的主要特点9/1/202016加密和解密能力分开可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）。无需事先分配密钥。三、密码分析截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。9/1/202017密码分析9/1/202018密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反。两者解决问题的途径有很大差别密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力……，有时还靠点运气。密码分析方法--穷举破译法对截收的密报依次用各种可解的密钥试译，直到得到有意义的明文；或在不变密钥下，对所有可能的明文加密直到得到与截获密报一致为止，此法又称为完全试凑法

(Complete

trial-and-error

Method)。只要有足够多的计算时间和存储容量，原则上穷举法总是可以成功的。但实际中，任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的。9/1/202019密码分析方法—分析法确定性分析法利用一个或几个已知量(比如，已知密文或明文-密文对)用数学关系式表示出所求未知量(如密钥等)。已知量和未知量的关系视加密和解密算法而定，寻求这种关系是确定性分析法的关键步骤。统计分析法利用明文的已知统计规律进行破译的方法。密码破译者对截收的密文进行统计分析，总结出其间的统计规律，并与明文的统计规律进行对照比较，从中提取出明文和密文之间的对应或变换信息。9/1/202020密码可能经受的攻击攻击类型攻击者拥有的资源惟密文攻击加密算法截获的部分密文已知明文攻击加密算法，截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文9/1/202021无条件安全和计算安全9/1/202022无条件安全如果算法产生的密文不能给出唯一决定相应明文的足够信息，无论截获多少密文，花费多少时间都不能解密密文。Shannon指出，仅当密钥至少和明文一样长时达到无条件安全（即一次一密）计算安全破译密文的代价超过被加密信息的价值破译密文所花时间超过信息的有效期将替换密码用于军事用途的第一个文件记载是恺撒著的《高卢记》。恺撒描述了他如何将密信送到正处在被围困、濒临投降的西塞罗。其中罗马字母被替换成希腊字母使得敌人根本无法看懂信息。苏托尼厄斯在公元二世纪写的《恺撒传》中对恺撒用过的其中一种替换密码作了详细的描写。恺撒只是简单地把信息中的每一个字母用字母表中的该字母后的第三个字母代

替。这种密码替换通常叫做恺撒移位密码，或简单的说，恺撒密码。尽管苏托尼厄斯仅提到三个位置的恺撒移位，但显然

从1到25个位置的移位我们都可以使用替换加密方法恺撒加密法朱利叶斯.恺撒发明的。每一个字母用字母表中的该字母后的第三个字母代替恺撒移位密码举例明文：I

LOVE

YOU密文：L

ORYH

BRX改进的恺撒加密法·可以后面1-25个字母进行替换，不一定是3个字母。破解只要尝试26次就能实现进一步改进恺撒加密法·单字母替换密码（单码加密法）例如明码表A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

RS

T

U

V

W

X

Y

Z密码表Q

W

E

R

T

Y

U

I

O

P

A

S

D

F

G

H

J

KL

Z

X

C

V

B

N

M明文F

O

R

E

S

T密文Y

G

K

T

L

Z单码加密的破解·从数学上来将

26*25*24*…*2*1种组合破解计算量非常大有没有其他办法？单码加密的破解·词频分析法9世纪的科学家阿尔·金迪在《关于破译加密信息的手稿》“如果我们知道一条加密信息所使用的语言，那么破

译这条加密信息的方法就是找出同样的语言写的一篇

其他文章，大约一页纸长，然后我们计算其中每个字

母的出现频率。我们将频率最高的字母标为1号，频率排第2的标为2号，第三标为3号，依次类推，直到数完样品文章中所有字母。然后我们观察需要破译的密文，同样分类出所有的字母，找出频率最高的字母，并全

部用样本文章中最高频率的字母替换。第二高频的字

母用样本中2号代替，第三则用3号替换，直到密文中所有字母均已被样本中的字母替换。”词频分析法设密者后来针对频率分析技术对以前的设密方法做了些改进，比如说引进空符号等，目的是为了打破正常的字母出现频率。但是小的改进已经无法掩盖单字母替换法的巨大缺陷了。到16世纪，最好的密码破译师已经能够破译当时大多数的加密信息。词频分析法的局限性短文可能严重偏离标准频率，加入文章少于100个字母，那么对它的解密就会比较困难。不是所有文章都适用标准频度1969年，法国作家乔治斯·佩雷克写了一部200页的小说《逃亡》，其中没有一个含有字母e的单词。更令人称奇的是英国小说家和拼论家吉尔伯特·阿代尔成功地将《逃亡》翻译成英文，而且其中也没有一个字母e。阿代尔将这部译著命名为《真空》。如果这本书用单密码表进行加密，那么频度分析破解它会受到很大的困难。多密码表加密法为了解决词频分析问题维热纳尔(Blaise

de

Vigenere)于16世纪末确立其密码不再用一个密码表来加密，而是使用了26个不同的密码表变换加密技术C

mh

m

tm

rooe

o

eo

or

w对明文进行某种置换栅栏加密技术明文“Comehometomorrow”密文”Cmhmtmrooeoeoorw”Cmhmtmrooeoeoorw简单分栏式变换加密技术·基本方法一行行写，一列列读明文“Comehometomorrow”密文”Cmroermtoeowhmoo”如果列读的顺序再变一下，352146得密文

“mtohmoerCmreowoo”很容易破解第一列第二列第三列第四列第五列第六列Comehometomorrow多轮简单分栏变换加密技术·简单分栏变换加密变换多次，从而增加复杂性明文“Comehometomorrow”52146得密文“mtomoerCmreowoo”3

h以“mtohmoerCmreowoo”为明文再做若干次。第一列第二列第三列第四列第五列第六列Comehometomorrow多轮简单分栏变换加密技术·第二轮明文“mtohmoerCmreowoo”352146得密文“oComrtrwmeohmooe”以“oComrtrwmeohmooe”为明文再做若干次。轮次越多，复杂度越高第一列第二列第三列第四列第五列第六列mtohmoerCmreowooVernam加密·

Vernam加密法也称一次性板(One-Time-Pad)，用随机的非重复的字符集合作为输出密文。1.明文:HOWAREYOU714220174241420+2.密钥NCBTZQARX1321192516017233.初始和2016231942202431434.大于25则减去26201623191620245175.密文UQXTQUYFR由于一次性板用完就要放弃,因此这个技术相当安全,适合少量明文消息,但是对大消是行不通的(一次性板称为密钥(Key),并且明文有多长,密钥就有多长,因此对于大消不通).Vernam加密法最初是AT&T公司借助所谓的Vernam机实现的.对称密钥发布问题加密和解密密钥是一样的如何将解密密钥安全发送给接收方？二战德国在使用ENIGMA密码机时也是对称密

钥。采用的办法就是每天更新密码，在发送新密电前，用老的密钥加密新的密钥。所以盟军总能收到短的密电，但初期还是没有办法破译对称密钥密码系统的密钥数要两个人——只要一个密钥三个人——要三个密钥四个人——要4*3/2个五个人——要5*4*3/2个N个人—— 个，即N*(N-1)/2!如果有1000人参加，那么就需要499500个密钥。这个数字就太大了。Diffie-Hellman密钥见换协议/算为了解决对称密钥交换问题Whitefield

Diffie与Martin

Hellman在1976提出了这套奇妙的密钥交换协议。可以让需要安全通信的双方确定对称密钥。这个方法只是为了解决密钥交换，不能做加/解密。Diffie-Hellman算法描述·

Alice和Bob两个人要确定密钥Alice发送两个大的素数n,g给Bob同时Alice另选择大随机数x，并计算

Alice将A发给BobBob选择大随机数y，并计算

Bob将B发给AliceAlice计算密钥

Bob计算密钥

可证明K1=K2Diffie-Hellman算法举例Alice选择n=11,g=7，并将这两个数告诉BobAlice选择x=3，则Bob选择y=6，则Alice得到B，并计算Bob得到A，并计算Diffie-Hellman算法理论基础·仔细想想，Alice和Bob交换了什么信息？n,g,A,B而n和g是公开的。只要知道x和y就能求出密钥。现在的问题是对方还知道A和B需要用A,B,n,g求出下列方程组中的x和y.当g,n非常大，要求x,y是非常复杂的。有多大呢？复杂度真的那么大吗?当g,n非常大，要求x,y是非常复杂的。有多大呢？举例·且g,n会非常大!Diffie-Hellman算法问题这个方法是否万无一失呢？不是！存在中间人攻击或桶队攻击·可分别计算各自的A，BAliceTomBobn=11,g=7n=11,g=7n=11,g=7x=3x=8,y=6y=9AliceTomB=4BobB=8A=2A=9Diffie-Hellman算法问题交换A，B分别计算各自的K产生的结果，Alice和Bob以为是直接和对方通信，结果被中间人Tom翻译了。AliceTomBobA=2

B=4A=2

B=4A=9

B=8A=9

B=8AliceTomBobA=9

K2=5B=4

K1=9A=2

K1=9B=8

K2=5非对称密钥的密钥数对称密钥的密钥数N*(N-1)/2!非对称密钥呢?非对称密钥就是加密和解密不是同一个密钥。加密密钥可以公开（公钥），实际也可做解密解密密钥不公开（私钥），当然也可以做加密既一个做加密，一个就做解密。通常公开的做加密，私有的来解密。这样其他人就不能解开信息。有N个人加入通信，非对称密钥对为N个。明显少得多。夹带加密法将要保密的信息放在另一个信息中隐形墨水在某个字符上加上小标记在书写字符之间稍做变化手写字符上使用铅笔标记等。图形夹带秘密信息将图形每个字节最右边两位换成密码消息位。图形变化不大。但夹带了秘密。图形夹带信息摘要，验证图象是否经人篡改。密钥范围与密钥长度密码分析员知道如下信息加/解密算法密文（信道监听得到）密钥的长度知识（即密钥的取值范围，比如0-1000亿）如何破解，只要用0-1000亿的值做密钥，通过解密算法计算明文，如果明文可读。（暴力破解）最好的情况，最差的情况，平均情况密钥范围与密钥长度如果密钥的范围为0-1000亿而攻击者只要五分钟就破解了密钥。但你又希望消息能在五年内保密。如何做？