第3讲-密码学基础课件

密码学基础

第3章

信息工程与技术系唐华议题密码学的发展密码学基本概念对称加密算法（DES）非对称加密算法（RSA）信息的鉴别和认证（MD5&SHA-1)密码学的发展密码学发展阶段1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学未来量子密码学第1阶段－古典密码

密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密第1阶段－古典密码Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。20世纪早期密码机20世纪早期密码机二战中美国陆军和海军使用的条形密码设备M-138-T4。根据1914年ParkerHitt的提议而设计。25个可选取的纸条按照预先编排的顺序编号和使用，主要用于低级的军事通信。20世纪早期密码机Kryha密码机大约在1926年由Alexandervo

Kryha发明。这是一个多表加密设备，密钥长度为442，周期固定。一个由数量不等的齿的轮子引导密文轮不规则运动。20世纪早期密码机哈格林（Hagelin）密码机C-36，由Aktiebolaget

CryptoeknidStockholm于1936年制造密钥周期长度为3,900,255。20世纪早期密码机M-209是哈格林对C-36改进后的产品，由Smith-Corna负责为美国陆军生产。它的密码周期达到了101,105,950。20世纪早期密码机转轮密码机ENIGMA，由ArthurScherbius于1919年发明，面板前有灯泡和插接板；4轮ENIGMA在1944年装备德国海军，英国从1942年2月到12月都没能解读德国潜艇的信号。恩尼格玛密码机（Enigma）

英军跳帮小组乘小艇接近德国海军U-505号潜艇俘获Enigma机

《猎杀U-571》剧照

“波兰三杰”：Rejewski、Różycki和Zygalski

BletchleyPark独特建筑在二战期间，Enigma是在美丽的BletchleyPark（布莱切利园，是一座位于英格兰米尔顿凯恩斯（MiltonKeynes）布莱切利镇内的宅第）破解的。密码专家在此BletchleyPark曾破解不少轴心国的密码与密码文件系统。正因如此，BletchleyPark附近一度成为解密中心。

20世纪早期密码机英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号。20世纪早期密码机在线密码电传机LorenzSZ42，大约在1943年由LorenzA.G制造。英国人称其为“tunny”，用于德国战略级陆军司令部。SZ40/SZ42加密因为德国人的加密错误而被英国人破解，此后英国人一直使用电子COLOSSUS机器解读德国信号。第1阶段－古典密码1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。examplePolybius’Checkerboard,205~123B.C.

123451ABCDE2FGHIJK3LMNOP4QRSTU5VWXYZ明文:POLYBIUS密文:3534315412244543图3-8Caser图像Caser密码机Caser密码Example-ii恺撒密码CaesarCipher,c.50B.C.

ABCDEFG……XYZDEFGHIJ……ABC

明文:Caesarcipherisashiftsubstitution

密文:FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ加密算法Ci=E(Pi)=Pi+3

计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“TheCommunicationTheoryofSecretSystems”

1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密

第2阶段1949~1975任务：尝试解密下面3个密码，你能解吗？

HASRVKDQJKDLOPXEIAHGNAHSSAGAEPHNHIXO替换加密法（Caser密码）置换加密法（倒序）

置换加密法（“栅栏密码”或“双轨”式密码）

1976年：Diffie&Hellman

的

“NewDirectionsinCryptography”

提出了不对称密钥1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能第3阶段1976~Rivest,Shamir&Adleman1977年DES正式成为标准80年代出现“过渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael（也就是AES）成为DES的替代者第3阶段1976~密码学基本概念基本概念密码学(Cryptology):

是研究信息系统安全保密的科学.密码编码学(Cryptography):

主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.基本术语明文(Plaintext)需要被隐蔽的信息。密文(Ciphertext)明文经变换形成的隐蔽形式。加密(Encrtption)把明文信息转化为秘文的形式。解密(Decryption)把秘文信息还原为明文的形式。

密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。加密通信的模型Alice加密机解密机Bob安全信道密钥源Oscarxyxk加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).明文明文密文加密算法解密算法密钥密钥密码体制密码体制：它是一个五元组（P,C,K,E,D)满足条件：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集；（密钥空间）*（4）任意k∈K,有一个加密算法和相应的解密算法，使得和分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。密码算法分类基于密钥的算法，按照密钥的特点分类：对称密码算法（symmetriccipher)：又称传统密码算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)

。公开密钥算法用一个密钥进行加密,而用另一个进行解密.其中的加密密钥可以公开,又称公开密钥（publickey)，简称公钥.解密密钥必须保密,又称私人密钥（privatekey)私钥.简称私钥。密码算法分类按照明文的处理方法：分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。序列密码是手工和机械密码时代的主流密码分析假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥。这个假设称为Kerckhoff原则。最常见的破解类型如下：1.唯密文攻击：Oscar具有密文串y.2.已知明文攻击:Oscar具有明文串x和相应的密文y.3.选择明文攻击：Oscar可获得对加密机的暂时访问，因此他能选择明文串x并构造出相应的密文串y。4.选择密文攻击:Oscar可暂时接近密码机,可选择密文串y，并构造出相应的明文x.

这一切的目的在于破译出密钥或密文密码破译密码破译的原则:遵循观察与经验方法:采用归纳与演绎步骤:分析、假设、推测和证实三大要素：语言的频率特征：e连接特征:q…u,Iex,重复特征:th,tion,tious密码算法的安全性无条件安全（Unconditionallysecure）无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期.对称加密算法对称加密算法对称加密算法性能速度块密钥管理共享密钥不适合大用户量的通信常用于快速的加密解密加密算法

DES、3-DES、AES、IDEA、RC2、RC4等

对称加密算法的弱点密钥无法管理安全共享密钥每对通信者需要一对密钥，N个通信者就需要N！对密钥不可能与你未曾谋面的人通信。数据加密标准

（DataEncryptionStandard,DES)DES产生的背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于1977年7月15日生效美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位1979年，美国银行协会批准使用DES1980年，DES成为美国标准化协会(ANSI)标准1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作DES产生的背景DES概述分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现DES加密算法的一般描述输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特DES加密过程DES加密过程令i表示迭代次数，表示逐位模2求和，f为加密函数DES解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数DES的应用1979年，美国银行协会批准使用1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSIX.392）

1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。

三重DES

F函数(S-Box)设计原理未知密钥长度的争论

DES的破译

弱密钥与半弱密钥DES的安全性关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有个

早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元DES密钥长度在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元DES密钥长度1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥DES密钥长度1990年，以色列密码学家EliBiham和Adi

Shamir提出了差分密码分析法，可对DES进行选择明文攻击线性密码分析比差分密码分析更有效破解DES非对称加密算法（公开密钥算法）

满足下列条件的函数f：

(1)给定x，计算y=f(x)是容易的

(2)给定y,计算x使y=f(x)是困难的

(3)存在z，已知z时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义单向陷门函数函数仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，z称为陷门信息当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为Pkf函数的设计者将z保密，用作解密密钥，此时z称为秘密钥匙，记为Sk。由于设计者拥有Sk，他自然可以解出x=f-1(y)单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的单向陷门函数说明非对称加密算法加密与解密由不同的密钥完成加密：解密：知道加密算法，从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的）公开密钥算法的基本要求公开密钥算法的实现过程非对称加密算法RSA算法RSA实现的步骤如下：Bob为实现者

(1)Bob寻找出两个大素数p和q(2)Bob计算出n=pq

和φ(n)=(p-1)(q-1)(3)Bob选择一个随机数e(0<e<φ(n))，满足(e,φ(n))=1(4)Bob使用辗转相除法计算d=e-1(modφ(n))(5)Bob在目录中公开n和e作为公钥密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的dRSA算法的实现参数T={N}；私钥SK=D；公钥PK=E；设：明文M，密文C，那么：用公钥作业：MEmodN=C

用私钥作业：MDmodN=MRSA算法编制设p=7,q=17,n=7*17=119;参数T={n=119};φ(n)=(7-1)(17-1)=96;选择e=5,gcd(5,96)=1;公钥pk=5;计算d,(d*e)mod96=1;d=77;私钥sk=77;设:明文m=19

加密：（19）5mod119=66

解密：（66）77mod119=19RSA算法举例简单小学计算题选择两个素数p，q（不要告诉别人），假设是p=2，q=5，算出n=p×q=

（1），将n公开。计算n的欧拉函数Φ(n)=(p-1)×(q-1)=

（2）。从1到Φ(n)之间选择一个和Φ(n)互素的数e公开，这里选择e=

（3）。计算解密密钥d，使得(d×e)modΦ(n)=1，这里可以得到d=

（4）。将n=

（1）和e=

（3）公开；将d=

（4）保密。这样就可以加密和解密了。例如，要发送的信息为s=2，那么可以通过如下计算得到密文：c=se

mod(n)=

（5）。密文8可以使用d=3恢复出明文：s=cdmod(n)=

（6）。只要知道素数和互素概念的小学生都能很快给出答案：（1）10；（2）4；（3）3；（4）3；（5）8；（6）2。如果给定两素数，不用通过人工计算或编程得到，我们用RSA-Tool工具就可以很容易得到公钥n和e，以及私钥d。

如假设两个素数p=101，q=113。下面通过一个小工具RSA-Tool演示上面所说的过程。

如下图所示，选择好密钥长度（Keysize）和进制（NumberBase），并确定P、Q和公钥E（PublicExponent）的值后，单击按钮，则可算出N和私钥D。从图可知，公开加密密钥（n，e）=（11413，3533）。解密密钥d=3579。这样就可以使用公钥对发送的信息进行加密，接收者如果拥有私钥，就可以对信息进行解密了。例如，要发送的信息为s=9726，那么可以通过如下计算得到密文：c=semod(n)=97263533mod(11413)=5761。将密文5761通过信道发送给接收端，接收者在接收到密文信息后，可以使用私钥d=3579恢复出明文：s=57613579

mod(n)=57613579mod(11413)=9726。密码分析者攻击RSA体制的关键点在于如何分解n若分解成功使n=pq，则可以算出φ(n)＝（p-1)(q-1)，然后由公开的e，解出秘密的d若使RSA安全，p与q必为足够大的素数，使分析者没有办法在多项式时间内将n分解出来RSA算法的安全性分析建议选择p和q大约是100位的十进制素数模n的长度要求至少是512比特EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，但必须是128的倍数国际数字签名标准ISO/IEC9796中规定n的长度位512比特位RSA算法的安全性分析为了提高加密速度，通常取e为特定的小整数如EDI国际标准中规定e＝216＋1ISO/IEC9796中甚至允许取e＝3这时加密速度一般比解密速度快10倍以上RSA算法的安全性分析DH/DSA对称加密与非对称加密算法类型说明对称加密使用一个密钥：对数据进行加密对数据进行解密快速且高效非对称加密使用两个在数学上相关的密钥：公钥用于对数据进行加密私钥用于对数据进行解密比对称加密安全速度比对称加密慢组合公钥加密和对称加密算法信息的鉴别和认证网络通信的几个安全要素网络通信的攻击威胁泄露：把消息内容发布给任何人或没有合法密钥的进程流量分析：发现通信双方之间信息流的结构模式，可以用来确定连接的频率、持续时间长度；还可以发现报文数量和长度等伪装：从一个假冒信息源向网络中插入消息内容篡改：消息内容被插入、删除、变换、修改顺序修改：插入、删除或重组消息序列时间修改：消息延迟或重放否认：接受者否认收到消息；发送者否认发送过消息鉴别和认证鉴别：authentication真伪性

(1)Aprocessusedtoverifytheintegrityoftransmitteddata,especiallyamessage

用来验证发送的数据,特别是一个信息的完整性的过程

(2)Theactofestablishingtheidentityofuserswhentheystarttousethesystem

在用户开始使用系统时对其身份进行的确认认证：Certification资格审查

Incomputersecurity,thetechnicalevaluationmadeaspartofandinsupportoftheaccreditationprocess,thatestablishedthe

extenttowhichaparticularcomputersystemornetworkdesignandimplementationmeetprespecifiedsecurity

requirements

计算安全学用语,指为了鉴定一个计算机系统或网络的设计和它提供的手段在多大程度上能满足预定的安全要求而进行的技术评估鉴别的目的信源识别：验证信息的发送者是真正的，而不是冒充的验证信息的完整性，在传送或存储过程中未被篡改，重放或延迟等鉴别模型鉴别系统的组成鉴别编码器和鉴别译码器可抽象为鉴别函数一个安全的鉴别系统，需满足（1）指定的接收者能够检验和证实消息的合法性、真实性和完整性（2）消息的发送者和接收者不能抵赖（3）除了合法的消息发送者，其它人不能伪造合法的消息鉴别函数分类消息加密：整个消息的密文作为认证标识消息鉴别码(MAC)：公开函数+密钥产生一个固定长度的值作为认证标识散列函数：一个公开函数将任意长度的消息映射到一个固定长度的哈希值，作为认证标识消息鉴别码使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称MAC，或密码校验和（cryptographicchecksum）

1、接收者可以确信消息M未被改变

2、接收者可以确信消息来自所声称的发送者

3、如果消息中包含顺序码（如HDLC,X.25,TCP），则接收者可以保证消息的正常顺序MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少消息鉴别VS

常规加密保密性与真实性是两个不同的概念根本上,信息加密提供的是保密性而非真实性加密代价大(公钥算法代价更大)鉴别函数与保密函数的分离能提供功能上的灵活性某些信息只需要真实性,不需要保密性

–广播的信息难以使用加密(信息量大)–网络管理信息等只需要真实性

–政府/权威部门的公告散列函数H(M):输入为任意长度的消息M;输出为一个固定长度的散列值，称为消息摘要(MessageDigest）H(M)是消息M的所有位的函数并提供错误检测能力：消息中的任何一位或多位的变化都将导致该散列值的变化H(M)又称为：哈希函数、数字指纹（Digitalfingerprint)、压缩（Compression)函数、数据鉴别码（Dataauthenticationcode）等HashvsMACMAC需要对全部数据进行加MAC速度慢Hash是一种直接产生鉴别码的方法散列函数的要求H能用于任意大小的分组H能产生定长的输出对任何给定的x，H(x)要相对易于计算，使得硬件和软件实现成为实际可能对任何给定的码h，寻找x使得H(x)=h在计算上是不可行的，即单向性对任何给定的分组x，寻找不等于x的y，使得H(x)=H(y)在计算上是不可行的，即弱抗冲突性寻找对任何的(x,y)对使得H(x)=H(y)在计算上是不可行的，即强抗冲突性用哈希值验证数据完整性用户

A用户

B数据数据哈希值哈希算法数据哈希值哈希值哈希算法如果哈希值匹配，则数据是有效的用户

A

将数据和哈希值发送给用户

BMD5描述Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest

完成MD5(RFC1321)在最近数年之前,MD5是最主要的hash算法现行美国标准SHA-1以MD5的前身MD4为基础MD5描述

输入：任意长度的报文输入分组长度：512bit

输出：128bit报文MD5的安全性Berson表明，对单循环MD5，使用不用的密码分析可能在合理的时间内找出能够产生相同摘要的两个报文，这个结果被证明对四个循环中的任意一个循环也成立，但作者没有能够提出如何攻击包含全部4个循环MD5的攻击Boer和Bosselaers显示了即使缓存ABCD不同，MD5对单个512bit分组的执行将得到相同的输出(伪冲突）Dobbertin的攻击技术：使MD5的压缩函数产生冲突，即寻找MD5被认为是易受攻击的，逐渐被SHA-1和RIPEMD-160替代其它常用哈希算法Hash小结Hash函数把变长信息映射到定长信息Hash函数不具备可逆性Hash函数速度较快Hash函数与对称密钥加密算法有某种相似性对Hash函数的密码分析比对称密钥密码更困难Hash函数可用于消息摘要Hash函数可用于数字签名报文鉴别的局限性用于保护通信双方免受第三方攻击无法防止通信双方的相互攻击信宿方伪造报文信源方否认已发送的报文引入数字签名，是笔迹签名的模拟数字签名数字签名问题Messageauthentication用以保护双方之间的数据交换不被第三方侵犯；但它并不保证双方自身的相互欺骗。假定A发送一个认证的信息给B，双方之间的争议可能有多种形式：B伪造一个不同的消息，但声称是从A收到的。A可以否认发过该消息，B无法证明A确实发了该消息。例如：

EFT(electronicfundstransfer,电子资金转账)中改大金额；股票交易指令亏损后抵赖。

思想

手写签名:Alice对一个文档利用手写签名后,人们就可以验证她的签名,并且其他人很难模仿她的签名.

数字签名(digitalsignature),也称电子签名,就是对电子文档利用电子手段进行签名,电子签名必须至少具备手写签名的两个性质,即可验证性与不可伪造性.

数字签名的性质传统签名的基本特点能与被签的文件在物理上不可分割签名者不能否认自己的签名签名不能被伪造容易被验证数字签名是传统签名的数字化数字签名数字签名用来保证信息传输过程中信息的完整性和提供信息发送者的身份的确认。数字签名的特点完整性：如果数