《密码学基础》全套教学课件

——密码的历史及古典密码传统加密技术4学时第1章

古典密码第2章分组密码与DES第3章AES第4章

序列密码第5章公钥密码与RSA第6章

数字签名第7章消息认证与Hash函数全套可编辑PPT课件密码的起源和发展密码学的基本概念古典密码初等密码分析主要内容全套可编辑PPT课件了解密码的产生和发展历史掌握密码学的基本概念理解古典密码的加密思想，掌握基本的加密方法：置换和代替掌握密码体制的分类方法理解初等密码分析的思想教学目的全套可编辑PPT课件古代——近代——现代

一、密码的起源和发展19491976全套可编辑PPT课件隐写术Staganography

由希腊词Steganos（覆盖）和Graphein（写）派生而来。密码术Cryptography

由希腊词Kryptos（隐藏）派生而来。密码的起源希波战争，漏格板希斯塔亚乌斯，在奴隶头皮上写字中国古代，蜡封小球公元一世纪，普林尼，隐形墨水一、密码的起源和发展密码技术的发展15世纪，意大利建筑师利昂．阿尔伯提设计的密码盘密码技术的发展潜伏相关影视作品例：

恺撒《高卢记》——将罗马字母用希腊字母替换苏托尼厄斯《恺撒传》——恺撒密码一、密码的起源和发展两种基本加密方法代替——对标准书写符号的修改Substitution机械密码大行其道Enigma，Hagelin密码机密码破译成果辉煌紫密，图灵炸弹，中途岛新技术的大量使用微粒照片，图灵机一、密码的起源和发展二战中的密码特点机械密码：用机器实现代替与置换三种有代表性的密码机：

Enigma（德、意、日军方）

Lorenz（德国高层）Hagelin（盟国：美、英、法等）

二战中的密码一、密码的起源和发展三、古典密码（Classical

Ciphers）Enigma三、古典密码（Classical

Ciphers）Hagelin1912年，美国人爱德华.休.赫本(EdwardHughHebern)发明了可以通过”移动字母板”加密的打字机，并申请专利。1918年，德国人阿瑟．谢尔比斯为Enigma申请专利。瑞典人鲍里斯.恺撒.威廉.哈格林（BorisCaesarWilhelmHagelin），靠密码机发财第一人

三、古典密码（Classical

Ciphers）机械密码转轮机(RotorMachine)

大量装备、参加实战、遭到破译、彻底曝光

1918年，德国发明家阿瑟．谢尔比斯为Enigma申请专利，并与理查德．里特建立了谢尔比斯＆里特公司，出售Enigma，售价为今天的3万$/台困境：卖不出去采取措施：拼命改进转机：1922年，丘吉尔出版《第一次世界大战回忆录》

Enigma纳粹德国的四大军事象征

普鲁士之鹰铁十字EnigmaEnigma英国组织破译（布莱切利庄园）图灵发明BombeEnigma破译Enigma的意义：波兰人，Bomba，机械化密码分析时代的到来英国Bombe，证明了机械化密码分析手段在破解机械化密码时的极端必要性波兰和英国专家能手工破译，说明了密码破译归根结底是人类智慧的胜利。Enigma密码学(Cryptology):

研究信息系统安全保密的科学，包括密码编码学和密码分析学。密码编码学(Cryptography):

主要研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):主要研究加密消息的破译或消息的伪造.二、密码学的基本概念密码体制：是一个五元组（P,C,K,E,D)，满足条件：（1）P是可能明文的有限集（明文空间）（2）C是可能密文的有限集（密文空间）（3）K是一切可能密钥构成的有限集（密钥空间）（4）任意k∈K,有一个加密算法ek∈E和相应的解密算法dk∈D，使得ek:P→C和dk:C→P分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。二、密码学的基本概念密码体制Example明文：Allofgaulisdividedintothreeparts.密文：DOORIJEXOLVGLYLGHGLQWRWKUHHSDUWV代替密码2.单表代替（MonoalphabeticSubstitution）所有的消息用同一个代替表加密，相同的明文替换为相同的密文。例：

乘法密码 仿射密码，多项式代替密码 密钥短语密码（将口令字中的字符无重复地写下，再将余下的字符按顺序写好，并将它们和明文字母建立一一对应的关系。）三、古典密码（Classical

Ciphers）代替密码多表代替：1412年，埃及数学家艾哈迈德.卡勒卡尚迪(Ahmadal-Qalqashandi)在百科全书中第一次提出。1508年，德国修道院院长约翰内斯.特米特里乌斯(HohannesTrithemius)首先构造出方表（tableau）——多个代替表1553年，意大利学者吉奥万.巴蒂斯塔.贝拉索（GiovanBattistaBellaso）设计出了密钥。贝拉索密码，使用时间较长，美国内战时北军使用。多表代替1586年，法国外交官布莱斯.德.维吉尼亚（BlaiseDeVigenere）对贝拉索密码进行改良。Vigenère密码：1854年，被英国人查理斯.巴贝奇（CharlesBabbage）所破译查理斯.巴贝奇（1792-1871）：设计了差分机（differenceengine）和分析机（analyticalengine），是现代计算机的雏形。多表代替二、置换技术（Permutation）1.栅栏技术——按列写入，按行读出。例：用深度为2的栅栏技术加密明文“meetmeaftertheparty”

可写为按行读出密文为“mematrhtgpryetefeteoaat”2.矩阵密码——把消息按行写入，再按列读出。mematrhtgpryetefeteoaat三、古典密码（Classical

Ciphers）置换密码加密部分可分为：多表代替模块：转轮组单表代替模块：连接板附加模块：反射板Enigma破译或攻击（Break/Attack）密码的方法包括穷举破译法（ExhaustiveAttack）和分析法两类。穷举法，又称为强力攻击（Brute-forceMethod），指对截收的密文依次用各种可能的密钥试译，直到得到有意义的明文；或者在不变密钥下，对所有可能的明文加密直到得到与截获密文一致，这又称为完全试凑法（CompleteTrial-and-errorMethod）四、初等密码分析唯密文攻击（CiphertectOnlyAttak）分析者从仅知道的密文进行分析，试图得出明文或密钥。已知明文攻击（KnowPlaintextAttak）分析者除了有截获密文外，还有一些已知的明文－密文对。选择明文攻击（ChosenPlaintextAttack）分析者可以选定任何明文－密文对进行攻击，以确定未知密钥。选择密文攻击（ChosenCiphertextAttack）分析者可以利用解密机由他所选的密文解密出相应明文，以确定未知密钥。四、初等密码分析密码分析分类分组密码与数据加密标准4学时分组密码的基本概念数据加密标准DESDES的产生及使用DES算法细节DES的安全性分析DES在设计上的优点分组密码的设计原理分组密码的工作方式主要内容现代密码对称密码非对称密码序列密码分组密码对称密码非对称密码现代密码的分类加密方式序列密码（Streamcipher）：也叫流密码，用随机的密钥序列依次对明文字符加密，一次加密一个字符。分组密码（Blockcipher）：将明文划分为长度固定的组，逐组进行加密，得到长度固定的一组密文。密文分组中的每一个字符与明文分组的每一个字符都有关。第一节分组密码的基本概念加密算法解密算法明文密钥密钥x=(x1,…,xm

)y=(y1,…,yn

)密文第一节分组密码的基本概念分组密码加密框图分组长度：64bit有效密钥长度：56bit密钥生成算法：产生16个48bit的子密钥解密过程与加密过程相同，所使用的密钥也相同，但各个子密钥的使用顺序不同。算法的全部的细节公开，安全性完全依赖于密钥。第二节数据加密标准DESDES基本特征初始置换IP16轮迭代逆初始置换IP-1子密钥产生算法。

第二节数据加密标准DESDES算法细节算法构成对64bit的明文重新排列，而后分成左右两段，每段32bit，以L0和R0表示。IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序排列，将阵中元素按行读出，构成置换的输出。第二节数据加密标准DES初始置换IP在16圈迭代之后，将左右两段合并为64bit，进行置换IP-1，得到输出的64bit密文。第二节数据加密标准DES逆初始置换IP和IP-1的输入与输出是已知的一一对应关系作用：打乱原来输入的ASCII码字划分，并将原来明文的校验位（如果有的话）变为IP输出的一个字节。第二节数据加密标准DES逆初始置换将经过IP置换后的数据分成32bit的左右两段，进行16圈迭代每次迭代只对右边的32bit进行一系列的加密变换一轮迭代即将结束时，将左边的32bit与右边进行变换后得到的32bit按位模2加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接作为下一轮迭代时左边的段。

第二节数据加密标准DES乘积变换——DES算法的核心64比特初始密钥经过置换选择PC-1循环移位置换选择PC-2产生16次迭代所用的子密钥ki

初始密钥的第8、16、24、32、40、48、56、64位为奇偶校验位，其余56位为有效位，PC-1的目的是从64位中选出56位有效位。第二节数据加密标准DES子密钥生成算法每次移位后，将C和D中的原存数送给置换选择PC-2，PC-2将C中第9、18、22、25位和D中第7、9、15、26位删去，将其余数字置换位置，输出48比特，作为子密钥。第二节数据加密标准DES子密钥生成IP：初始置换ki

：第i次迭代所用的子密钥Li、Ri：第i次迭代时左边和右边的32比特f：每次迭代时对右边所作的变换：逐位模2加。

第二节数据加密标准DESDES算法的数学表示符号说明加密过程：64Bit明文64Bit密文（1）（2）第二节数据加密标准DESDES算法的数学表示解密过程：（64比特明文）（64比特密文）第二节数据加密标准DESDES算法的数学表示互补对称性弱密钥和半弱密钥对DES的强力攻击差分分析和线性分析第二节数据加密标准DESDES的安全性DES设计上的优点主要体现在以下几个方面循环次数雪崩准则精巧的S盒和P盒第二节数据加密标准DESDES在设计上的优点电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)第四节分组密码的工作方式第四节分组密码的工作方式分组密码的加密方式和设计准则DES算法的基本结构，非线性运算DES的安全性及设计上的优点分组密码的设计原理及Feistel模型分组密码的四种工作方式第二节数据加密标准DES小结高级加密标准4学时AES概述Rijndael加密算法主要内容了解高级加密标准的设计思想掌握AES算法的运算过程教学目的1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准AES的活动，目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。第一节AES

概述第一节AES概述对AES的基本要求：比三重DES快至少与三重DES一样安全数据分组长度为128比特密钥长度为128/192/256比特。AESBackground第一节AES

概述1998年8月，首届AES会议，指定15个候选算法。1999年3月22日，第二次AES会议，候选名单减少为5个：RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者—Rijndael算法，2001年11月出版了最终标准FIPSPUB197。AESBackground第一节AES

概述Rijndael加解密过程第六节高级加密标准AES唯一的非线性运算，代替表（S盒）可逆，由两个变换构成：首先在GF(28)中模m(x)取乘法逆，m(x)=x8+x4+x3+x+1，0映射到自身；然后经过一个仿射变换字节代替（Bytesub）第二节Rijndael加密算法逆运算（InvByteSub）先经过仿射变换的逆变换作用之后，再在GF(28)中模m(x)取乘法逆。字节代替（Bytesub）第二节Rijndael加密算法行移位（ShiftRow）第二节Rijndael加密算法状态行移位不同的位移量第0行不移动第1行循环左移C1字节第2行循环左移C2字节第3行循环左移C3字节，逆运算（InvShiftRow）

后面3行分别循环左移：

Nb-C1字节

Nb-C2字节

Nb-C3字节行移位（ShiftRow）第二节Rijndael加密算法Rijndael加密程序S=B⊕K0；Fori=1toNr-1 S=ByteSub(S)；

S=ShiftRow(S)；

S=MixColumn(S)；

S=Ki⊕S；S=ByteSub(S)；S=ShiftRow(S)；S=KNrS；Rijndael算法第二节Rijndael加密算法注：最后一圈无列混合Rijndael解密程序S=KNr⊕C；S=InvShiftRow(S)；S=InvByteSub(S)；S=KNr⊕

S；Fori=Nr-1to1 S=KiS；

S=InvMixColumn(S)；

S=InvShiftRow(S)；

S=ByteSub(S)；

S=K0⊕S；Rijndael算法第二节Rijndael加密算法将16字节初始密钥扩展为156字节（44字）的扩展密钥；扩展密钥的前四个字直接由输入密钥中复制，即w[0]~w[3]；w[i]的值依赖于w[i-1]和w[i-4]密钥扩展算法第二节Rijndael加密算法（迭代圈数为10时）对于下标为4的倍数的密钥字，其产生方法更为复杂，表示为函数g包括的运算步骤有：字循环（RotWord）：使一个字中的4个字节循环左移一个字节字节代换（SubWord）：利用S盒对输入字中的每个字节进行代替字循环与字节代换的结果再与轮常量Rcon[j]相异或密钥扩展算法第二节Rijndael加密算法无弱密钥或补密钥能有效抵抗差分分析和线性分析迭代圈数大于6时可抗截断差分分析圈数大于7时可抗Square攻击密钥量大，穷举攻击较困难Rijndael的安全性第二节Rijndael加密算法第一节序列的随机性２学时第四章序列的随机性随机性的概念及参数随机性假设伪随机数发生器线性同余发生器用密码编码产生随机数BBS发生器主要内容掌握随机性的含义及衡量方法理解随机性假设的含义掌握线性同余发生器的原理及参数选择理解如何用密码产生随机数理解BBS发生器的原理教学目的随机序列：不能重复产生的序列几个相关概念真随机——不能重复产生密码学意义上的随机——不能预测伪随机——看起来是随机的，并能通过许多随机性测试第一节序列的随机性真随机数发生器（TRNG）：利用物理方法实现的随机数发生器，它是自然界随机的物理过程（所产生物理现象的不确定性）的反映，即使算法等重要信息被暴露，都无法猜测其结果如何产生真随机数1．若序列的周期为偶数，则在一个周期内，0、1的个数相等；若周期为奇数，则在一个周期内，0、1的个数相差1。2．在一个周期内，长度为l的游程数占游程总数的1/2l，且对于任意长度，0游程与1游程个数相等。3．所有异相自相关函数值相等。Golomb随机性假设第一节序列的随机性伪随机数发生器——将一个短的随机数“种子”扩展为较长的伪随机序列的确定算法。线性同余发生器（Linearcongruentialgenerator）用加密方式产生随机数BBS发生器伪随机数发生器第一节序列的随机性评价线性同余发生器有以下准则：（1）完整周期：即在一个周期中，０至m-1之间的数都出现。（2）满足随机性测试。（3）可以高效地实现。线性同余法的优点：方便，快速；缺点：除初值外，其它数字都用确定算法产生。第一节序列的随机性线性同余发生器线性同余发生器先后被JimReeds和JoanBoyar破译后者还破译了二次同余发生器Xn=(ax2n-1+bxn+c)modm和三次同余发生器Xn=ax3n-1+bx2n-1+cxn-1+d线性同余发生器NIST为银行电子支付系统建议的标准算法，被PGP采纳，在Internet中使用。方法：用三重DES的EDE模式产生，使用两个密钥K1，K2两个驱动随机数：初始化时，设DT0为初始时刻的日期和时间(64bit)，V0为种子密钥(64bit)输出：64bit的随机数Ri和更新后的Vi+1伪随机数发生器第一节序列的随机性（3）ANSIX9.17伪随机数产生器

每一时刻要进行三次加密，相当于9次DES加密，由两个伪随机数驱动。伪随机数发生器第一节序列的随机性用K1，K2对DT0加密，结果与V0相加，再对其加密，得到R0BlumBlumShub产生器（BBS发生器）:

利用数论方法产生伪随机数选择两个大素数p，q，满足p≡q≡3mod4；计算其乘积n=pq；选择随机数s，(s,n)=1；通过以下公式迭代计算序列{Bi}伪随机数发生器第一节序列的随机性BBS发生器在密码学意义上是相对安全的，但计算量比较大。伪随机数发生器第一节序列的随机性第二节序列密码的原理2学时序列密码的基本概念加密方式密钥序列生成器线性反馈移位寄存器与m序列线性反馈移位寄存器移位寄存器的周期及m序列序列的线性复杂度与B-M算法主要内容明文符号序列与密钥符号序列逐个加密密钥序列z=z1z2…的第i个符号加密明文序列m=m1m2…的第i个符号，即若密钥序列重复使用，则称为周期序列密码，否则，就是一次一密密码。序列密码的加密方式第二节序列密码的基本概念由密钥流生成器生成第i个密钥取决于第i时刻密钥生成器的内部状态和初始密钥。对序列密码的安全性有两个基本要求：根据密钥序列以前的状态，不能很容易地推导出后续状态，即密钥序列要有足够高的随机性；传输密钥的秘密信道必须足够安全。序列密码中的密钥密码的安全性主要取决于所用密钥的随机性，所以设计序列密码的核心问题是设计随机性较好的密钥流生成器设计密钥流生成器的关键：寻找状态转移函数和输出函数，使输出的密钥序列有良好的伪随机性。密钥流生成器第二节序列密码的基本概念Rueppel将密钥流生成器分为两部分：驱动部分和非线性组合部分。驱动部分控制生成器的状态，并为非线性组合部分提供周期长、统计性能良好的序列；非线性组合部分利用这些序列组合出满足要求的密钥序列。密钥流生成器第二节序列密码的基本概念根据密钥序列的产生方法，可将序列密码可分为两类：同步序列密码（SynchronousStreamCipher）：状态转移函数与明文字符无关自同步序列密码（Self-SynchronousStreamCipher）：状态转移函数与明文字符相关。在同步流密码中，只要发送端和接收端有相同的种子或实际密钥和内部状态，就能产生出相同的密钥流，此时，认为发送端和接收端的密钥生成器是同步的。序列密码的分类第二节序列密码的基本概念衡量密码体制安全性的方法计算安全性（computationalsecurity），又称实际安全性（practicalsecrecy）：利用已有的最好的方法破译该系统所需要的努力超过了敌手的破译能力。可证明安全性（provablesecurity）：能用严格的数学方法证明破译该体制等价于某个困难问题。无条件安全性（unconditionalsecurity）或完善保密性（perfectsecrecy）：在信息论意义上是安全的。理论保密的密码体制定理若某一密码系统的明文数、密文数和密钥数都相等，则该密码体制完全保密的充要条件是：将某一明文加密成某一密文的密钥只能有一个；所有密钥都是等概率的。理论保密的密码体制组成：一系列存储单元、若干个乘法器和加法器通过电路连接而成。假设共有n个存储单元（此时称该移位寄存器为n级），每个存储单元可存储一比特信息，在第i时刻各个存储单元中的比特序列(aiai+1…ai+n-1)称为移位寄存器的状态，为初始状态。线性反馈移位寄存器第三节线性反馈移位寄存器与m序列给定初态（101），按照反馈函数可求出各个时刻的状态及输出.状态在第5时刻开始重复，因此输出序列的周期是4，输出序列为1011101110111011……线性反馈移位寄存器（LFSR）第三节线性反馈移位寄存器与m序列定理5-1

n级LFSR的周期≤2n-1证明：n级LFSR最多有2n种不同状态，若初态为全零，则其后续状态恒为零，构成一个平凡序列，若初态不为零，则一个周期中最多出现2n-1种非零状态，故状态周期小于等于2n-1，同样，输出序列的周期也小于等于2n-1。定义5-1周期为2n-1的n级LFSR的输出序列称为m序列。移位寄存器的周期及m序列第三节线性反馈移位寄存器与m序列序列的随机性随机性的含义伪随机数发生器序列密码的基本概念LFSR及m序列小结公钥密码学与RSA6学时第五章对称密码的弱点及公钥密码的原理MH背包公钥密码Diffie-Hellman密钥交换RSA密码主要内容密钥量大密钥管理困难：传递、换发、保存无法实现网络中的签名、认证等应用对称密码的弱点第一节公钥密码的原理密钥量大对称密码的弱点设系统中共有n个用户，两两进行保密通信，总共需要多少个密钥？当n=5时，C（5，2）=10当n=1000时，C（1000，2）=499500密钥量大对称密码的弱点设系统中共有n个用户，两两进行保密通信，每个用户有多少个密钥？n-1个密钥管理困难对称密码的弱点对称密码的弱点无法适应网络应用数字签名身份认证消息认证公钥密码的原理基本原理使用两个不同的密钥，一个用于加密，一个用于解密用于加密的密钥Ek可以公开，用于解密的密钥Dk保密Ek与Dk之间有联系，但不能由Ek很容易地算出Dk公钥密码的原理加密与解密公钥密码的原理c=Ek(m)m=Dk(c)公钥密码的优点密钥数量大大减少密钥管理方便公钥密码的原理公钥密码的安全性公钥密码的原理计算复杂性理论公钥密码的原理如何构造陷门单向函数：利用困难问题背包问题离散对数问题整数分解问题椭圆曲线离散对数问题公钥密码的原理典型公钥密码背包密码RSA密码Rabin密码ElGamal密码椭圆曲线密码背包密码1978年，Merkle和Hellman提出了基于背包问题的公钥密码体制。如何解决背包问题：穷举法背包问题当物品个数为100时，有2100≈1.27×1030种可能性。把全世界所有的5亿台计算机全部联网来求解这个问题，需要1000万年！

背包密码的安全性破译方法： Shamir方法 L3格基归约方法：由AKLenstra,HWLenstra&LLovasz提出

Lagarias-Odlyzko-Brickell的方法Diffie-Hellman密钥交换功能：在没有秘密信道的情况下，让两个用户共享一个秘密密钥理论基础：离散对数问题方法：利用用户的公钥和私钥Diffie-Hellman密钥交换计算Diffie-Hellman问题（CDH问题）：已知ga和gb，计算gab如果CDH问题是容易的，则gab可以由p,g,ga,gb计算得到。背景数学基础加密解密过程安全性及应用第二节RSA密码复习：欧拉定理

如果a,n互素，则有a

Ф(n)≡1modn设n=pq,p,q均为素数，且a,n互素，则Ф(n)=(p-1)(q-1)aФ(n)=a

(p-1)(q-1)≡1modn

第二节RSA密码

选择p,qp,q均为素数且p≠q

计算n=pq

计算Ф(n)=(p-1)(q-1)

选择e1<e<Ф(n)且gcd(e,Ф(n))=1

计算dd≡e-1modФ(n)

公开n,e

保密d系统构造对明文m=374加密计算c≡memodn≡37431mod2173=446解密：计算cd≡446671mod2173=374RSA：Example选择p=53,q=41,n=pq=2173,Ф(n)=2080选择e=31,计算出d=671将n,e公开，d保密加密：模幂运算解密：模幂运算正确性：欧拉定理安全性：分解大整数参数选择RSA小结数字签名4学时第六章

数字签名的概念数字签名与手写签名的区别数字签名的特征

数字签名的原理数字签名分类

直接数字签名仲裁数字签名主要内容数字签名(DigitalSignature)：以电子化形式，使用密码方法，在数字消息中嵌入一个秘密信息，以验证这个秘密信息是否正确来达到识别的目的，其实质是一种密码变换。第一节数字签名概述手写签名的特点：

(1)签名不可伪造。签名中包含了签名者个人所特有的一些信息，如写字习惯、运笔方法等，是别人很难仿造的。

(2)签名不可重用。一个签名只能对一份文件起作用，不可能移到别的不同的文件上。第一节数字签名概述手写签名

(3)文件内容不可改变。在文件签名后，文件的内容就不能再变。

(4)签名不可抵赖。签名和文件都是物理的实体，签名者不能在签名后还声称他没签过名。手写签名应用：网络中的身份认证和消息认证。特征：

(1)不可否认性：签名者事后不能否认。

(2)可验证性：接收者能验证签名，而任何其他人都不能伪造签名。

(3)可仲裁性：当双方发生争执时，可以由一个公正的第三方出面解决争端。第一节数字签名概述数字签名的特征构成：签名者、验证者、密钥、算法、待签名消息签名系统的参数包括：

——消息空间M，所有可能的消息的集合

——签名空间S，所有可能的签名的集合

——密钥空间K，所有可能的密钥的集合

——签名者的密钥，包括公钥pK和私钥sK两部分

——算法：保密的签名算法S(.)和公开的验证算法V(..)第一节数字签名概述数字签名的原理(1)A→B：EKRa(M)提供鉴别与签名只有A具有KRa传输中没有被篡改任何第三方可以用KUa验证签名(1’)A→B：EKUb[EKRa(M)]

提供保密、鉴别与签名第一节数字签名概述直接数字签名（DSS）(2)A→B：M||EKRa[H(M)]

提供鉴别及数字签名H(M)受到密码算法的保护只有A能够生成EKRa[H(M)](2’)A→B：EKUb[M||EKRa(H(M))]

提供保密性、鉴别和签名第一节数字签名概述直接数字签名（DSS）验证模式依赖于发送方的保密密钥发送方要抵赖发送某一消息时，可能会声称其私有密钥丢失或被窃，从而他人伪造了他的签名对策：要求被签名的信息包含一个时间戳（日期与时间），并要求将已暴露的密钥报告给一个授权中心X的某些私有密钥确实在时间T被窃取，敌方可以伪造X的签名及早于或等于时间T的时间戳第一节数字签名概述直接数字签名的缺点引入仲裁者所有从发送方X到接收方Y的签名消息首先送到仲裁者A，A将消息及其签名进行一系列测试，以检查其来源和内容，然后将消息加上日期并与已被仲裁者验证通过的指示一起发给Y。第一节数字签名概述仲裁数字签名（ADS）当X否认时，通过以下方法解决纠纷：

Y：向A发送EKay[IDx||M||EKax[IDx||H(M)]]

A：用Kay恢复IDx，M，和签名（EKax[IDx||H(M)]），然后用Kax解密签名并验证散列码第一节数字签名概述仲裁数字签名（ADS）Y不能直接验证X的签名，Y认为消息正确，只因为它来自A。因此，双方都需要高度相信A:X必须信任A没有暴露Kax，并且没有生成错误的签名

Y必须信任A仅当散列值正确并且签名确实是X产生的情况下才发送消息（2）双方都必须信任A能公正地处理争议第一节数字签名概述仲裁数字签名（ADS）(b)单密钥加密方式，消息对仲裁者不可见

(1)XA：IDx||EKxy[M]||EKax[IDx||H(EKxy[M])] (2)AY：EKay[IDx||EKxy[M]||EKax[IDx||H(EKxy[M])]||T]X与Y之间共享密钥Kxy

第一节数字签名概述仲裁数字签名（ADS）(c)公钥加密方式，消息对仲裁者不可见

(1)XA：IDx||EKRx[IDx||EKUy(EKRx[M])] (2)AY：EKRa[IDx||EKUy[EKRx[M]]||T]X：对消息M双重加密：首先用X的私有密钥KRx，然后用Y的公开密钥KUy。双重加密的消息对A以及对除Y以外的其它人都是保密的。A：检查X的公开/私有密钥对是否仍然有效，是则确认消息。第一节数字签名概述仲裁数字签名（ADS）(c)与(a)(b)相比具有以下好处：

1、在通信之前各方之间无须共享任何信息，从而避免了联手作弊；

2、即使KRx暴露，只要KRa未暴露，就不会有时间戳不正确的消息被发送；

3、从X发送给Y的消息的内容对A和任何其他人是保密的。第一节数字签名概述仲裁数字签名（ADS）掌握数字签名的基本概念理解数字签名的特征理解数字签名的原理及分类方法小结数字签名算法第二节RSA签名算法ElGamal签名算法DSA概述DSA签名过程主要内容Alice的公开密钥：nA,eA；秘密密钥：dA；消息m签名算法：验证算法：Alice要对秘密信息签名时，先用私钥计算签名，再用公钥加密。第二节常见签名算法RSA签名签名：对信息m签名时，首先选取随机数k(1≤k≤p-2)，k与p-1互素，计算

r=gk

modps=k-1(m-xr)modp-1或m=xr+ksmodp-1验证：验证者A验证等式是否成立：gm=yrrs

modp

若正确，则(r，s)为m的合法签名，否则为非法签名。第二节常见签名算法ElGamal签名1991年美国国家标准局NIST将数字签名算法DSA作为其数字签名标准(DigitalSignatureStandard，DSS)，DSA是ElGamal数字签名算法的变形。使用了安全散列函数SHA-1，以长度小于264bits的明文作为输入，产生160bit的消息摘要作为DSA的输入。验证签名时必须使用相同的散列函数。数字签名算法DSA签名：对明文m

(1,q)，签名者选取随机整数k，1≤k≤p-2且k与p-1互素，计算r=(gk

modp)modqs=k-1(H(m)+xr)modq其中kk-1modq≡1(r，s)即为消息m的数字签名。数字签名算法DSA验证：计算w=s-1modq

u1=H(m)wmodqu2=rwmodqv=[(gu1yu2)modp]modq检验v=r是否成立。数字签名算法DSA签名者对消息m=1234签名：选择随机数k=50，得k-1(mod101)=99计算签名：r=(17050(mod7879)(mod101)=2518(mod101)=94s=(1234+75*94)99(mod101)=97签名为(1234,94,97)Example数字签名算法DSA掌握RSA签名算法掌握ElGamal签名算法理解随机数在签名中的作用理解DSA签名过程小结椭圆曲线签名第三节ECDSA算法ECDSA中的阈下信道ECDSA算法的变形主要内容ECDSA(EllipticCurveDigitalSignatureAlgorithm)——DSA算法在椭圆曲线上的模拟。1992年，作为NIST所征集的DSS候选算法之一，ScottVanstone提出了ECDSA算法。后来被各标准化组织广泛接受，1998年被ISO作为ISO14888-3标准，1999年被ANSI作为ANSIX9.62标准，2000年被IEEE作为IEEE1363-2000标准，同年被FIPS作为FIPS186-2标准。ECDSA简介1.方案建立设U为签名方，V为验证方：(1）U建立椭圆曲线域参数T=(p，a，b，G，n，h)；(2）U建立自己的密钥对（dU,QU），QU

=dUG；(3）U选择一个Hash函数；(4）U

通过可靠的方式将所选择的Hash函数和建立的椭圆曲线域参数T传递给V。算法描述2.签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)与域参数T相关(2）令r=xR

(modn)，如果r=0,返回1(3）计算待签消息的hash值H=Hash(M)，将H转换成整数e(4）计算s

k-1(e+rdU)(modn)，如果s=0,返回1(5）输出S=(r，s)为数字签名算法描述3.验证算法(1）如果r,s

[1,n-1],验证失败(2）计算待签消息的hash值H=Hash(M)，将H转换成整数e(3）计算u1

es-1(modn)，u2

rs-1(modn)(4）计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败(5）令v=

xR

(modn)，如果v=r，验证成功，否则验证失败算法描述对ECDLP的攻击ECDSA算法的安全性基于ECDLP问题的困难性。如果一种攻击能够从签名者U的公钥恢复出私钥，攻击者就可以伪造出U对任何消息的数字签名。目前，当基点的阶为大素数时，素数域上的ECDLP是不可解的。对密钥生成的攻击在密钥生成过程中用到了秘密随机或伪随机数，不安全的随机或伪随机数生成器将直接导致密码被攻破。攻击思路对哈希函数的攻击签名和验证阶段使用的哈希函数必须具备单向和抗冲突的特性。如果哈希函数不能抵抗冲突，攻击者可能会发现消息(M1;M2)的碰撞，在U对消息M1签名后可以伪造出对消息M2的签名。基于无效域参数和无效公钥的攻击ECDSA的安全性依赖于U使用的有效域参数，无效的域参数对Pohlig-Hellman攻击不免疫。U应该确保所采用的域参数是有效的。V在验证之前也应该检验这些参数的有效性。攻击思路阈下信道——在密码协议中，存在一些特殊的编码方法或数学结构，可以用于传输秘密消息。阈下信道主要存在于数字签名和认证协议中。签名者（发送方）可以将秘密信息隐藏在数字签名之中，验证者（接收方）通过事先约定的某种协议或参数恢复出阈下信息，这种秘密通信方式很难被第三方检测到。与一般的加密传输相比，阈下信道具有更高的安全性。ECDSA中的阈下信道如果签名中的附加数据量为αbit，其中βbit用来保证签名的安全性，则理论上最大可以传递α-β

bit的阈下信息。利用了全部或几乎全部α-βbit的附加数据的阈下信道为宽带阈下信道，只利用了一小部分的为窄带阈下信道。恢复阈下信息时需要签名者密钥的方式定义为方式I，不需要的定义为方式Ⅱ。在方式I中，签名者的密钥同时也是该阈下信道的恢复密钥。ECDSA中的阈下信道在ECDSA中，由于s

k-1

(e+rdU)(modn)，可得k

s-1

(e+rdU)(modn)，（r,s）和e为签名对于验证者V来说，只要事先知道签名者U的私钥dU就可以恢复出k来。于是以k作为阈下信息，可以实现方式I的阈下信道。ECDSA中的阈下信道在数字签名协议中补充以下步骤，就能设计出阈下通信协议：信道建立U为发送方，V为接收方:(1）U执行方案建立协议。建立参数T,(dU,QU),Hash。(2）U将私钥dU,秘密传输给V。ECDSA中的阈下信道阈下信息隐藏(1）U对秘密消息编码，得到一整数k。(2）U建立临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关。(3）U执行以上签名算法。ECDSA中的阈下信道阈下信息恢复(1）V执行验证协议。(2）V计算

k

s-1(e+rdU)(modn)，恢复阈下信息。(3)V对k解码恢复原始的秘密信息。ECDSA中的阈下信道ECDSA算法中的签名附加数据量为（logn+logp）bit，而阈下信息k为lognbit，该信道是一种宽带信道。按照目前对椭圆曲线参数的安全要求，通过这个信道可传输192bit以上的阈下信息。ECDSA中的阈下信道签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关。(2）令r=xR(modn)，如果r=0,返回1。 (3）计算待签名消息的hash值H=Hash(M)，将H转换成整数e。(4）计算s

dU-1(rk-e)(modn)，如果s=0,返回1。(5）输出S=(r，s)为数字签名。ECDSA算法的变形一验证算法(1）如果r,s

[1,n-1],验证失败。(2）计算待签消息的hash值H=Hash(M)，将H转换成整数e(3）计算u1

er-1(modn),u2

sr-1(modn)(4）计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败。(5）令v=

xR(modn)，如果v=r,验证成功，否则验证失败。这个改进方案中，可以预计算dU-1，将计算结果存储下来作为签名参数，在每次签名时模乘dU-1即可，于是模逆转化为模乘，运算量将减小。ECDSA算法的变形一签名算法(1）选择临时密钥对(k，R)，其中R=kG=(xR，yR)和域参数T相关；(2）令r=xR(modn)，如果r=0,返回1；(3）计算待签名消息的hash值H=Hash(M)，将H转换成整数e；(4）计算s

k(e+rdU)-1(modn)，如果s=0,返回1；(5）S=(r，s)作为数字签名。ECDSA算法的变形二验证算法(1)如果r,s

[1,n-1],验证失败；(2)计算待签名消息的hash值H=Hash(M)，将H转换成整数e；(3)计算u1

es(modn),u2

rs(modn)；(4)计算R=(xR，yR)=u1G+u2QU，如果R=O,验证失败。(5)令v=

xR(modn)，如果v=r,验证成功，否则验证失败。ECDSA算法的变形二掌握ECDSA签名过程理解阈下信道的含义理解如何在ECDSA中利用阈下信道进行信息隐藏了解ECDSA的两种变形小结第四节盲签名三、盲签名的原理及典型算法(重点)二、盲签名的产生背景----电子投票主要内容：一、盲签名的基本概念盲签名

盲签名:是一类特殊的数字签名,消息持有者希望签名者对他的消息作数字签名，但又不想让签名看到消息的真实内容。一、盲签名的基本概念1、远程匿名投票20世纪80年代，密码学家DavidChaum就建立过一个远程匿名投票模型设立一个选举委员会，其职责为：

规定选票格式。

确认选民身份。

统计选票。二、电子投票问题（盲签名产生的背景）条件：所有投票人散居各城市，无法集中，利用普通邮政系统投票。选民选委会资格审查票数统计

①②⑤③④

1、远程匿名投票

二、电子投票问题（盲签名产生的背景）用电子手段解决以下三个关键问题：（1）如何使选委会看不到选票内容？（2）选举委员会如何盖章？（3）选民如何确认收回的选票没有被做上记号？2、电子投票二、电子投票问题（盲签名产生的背景）1、盲签名的特性（1）签名人看不到所签的“文件内容”。（2）签名人无法建立文件与他的签名之间的联系。三、盲签名的原理及算法消息持有者签名者MS=S(M)M=B(M)S=B-1(S

)

2、盲签名的原理盲化盲签名解盲

消息持有者希望签名者对他的消息作数字签名，但又不想让签名者看到消息的真实内容。三、盲签名的原理及算法1.不可伪造性除了签名者本人外，任何人都不能以他的名义生成有效的盲签名。2.不可抵赖性签名者签署了某个消息后将无法否认自己对消息的签名。3.盲性签名者不可能得到消息的具体内容。4.不可跟踪性一旦消息的签名公开后，签名者不能确定自己何时签署的这条消息。一个好的盲签名算法应该具有以下的性质：

三、盲签名的原理及算法3、基于RSA密码的盲签名算法（1）参数选取（同RSA公钥密码）：选定p,q为大素数，计算n=pq。选取秘密密钥d，要求gcd(d,φ(n))=1。计算e,满足de=1modφ(n)。

e,n

公开，其它参数均保密。三、盲签名的原理及算法RSA数字签名过程AliceBobn,epublicdprivates≡md

modngcd(m,n)=1m≡se

modnsSetp1:选定M，随机数R。计算M

=ReM

modn签名者消息持有者Setp2:计算S

=M

d

modnStep3:S=R-1S

modn

=M

dmodnStep4:验证

Semodn？=M（2）签名算法三、盲签名的原理及算法（3）分析MM

(M,S)(M

，S

)

签名人对签的“文件内容”是看不见的。即使公布文件内容，签名人也不能把文件与他所作的签名联系起来。

三、盲签名的原理及算法（4）与普通RSA签名比较MS=M

dmodnRSA签名RSA盲签名M?=S

emodnS

=M

dmodnM?=S

emodnMM

S=R-1S

modn三、盲签名的原理及算法1.密钥的长度；2.盲签名的长度；3.盲签名的算法和验证算法。盲签名的可操作性和实现速度取决于：三、盲签名的原理及算法4、盲签名技术的应用现状（1）匿名电子投票系统（2）电子商务系统中的匿名支付

Microsoft公司的eWallet系统。三、盲签名的原理及算法主要内容：（1）盲签名的基本概念（2）盲签名的产生背景。（3）基于RSA密码的盲签名算法。

四、小结及相关问题第五节代理签名代理签名的含义及特点代理签名的分类M-U-O代理签名方案主要内容代理签名：签名者可以授权他人代理自己，由被指定的代理签名者代表原始签名者生成有效的签名。1996年，Mambo、Usuda和Okamoto首先提出了代理签名的概念。代理签名系统中的参与者：原始签名者获得授权执行签名的一个或多个代理签名者验证者第五节代理签名代理签名应满足三个基本条件验证者能够像验证原始签名者的签名那样来验证代理签名；能够容易区分代理签名和原始签名；原始签名者对代理签名者所作的代理签名不可否认。代理签名的特点第五节代理签名Mambo、Usuda和Okamoto把代理签名分为三类：完全代理签名、部分代理签名和具有证书的代理签名。完全代理签名(fulldelegation)：原始签名者通过可靠途径直接把自己的签名密钥分发给代理签名者，代理签名者产生的签名与原始签名者所产生的签名完全相同。代理签名的分类第五节代理签名部分代理签名(partialdelegation)，原始签名者用自己的签名密钥生成代理签名密钥s，然后将代理签名密钥通过可靠途径分发给代理签名者。要求：代理签名者不能由自己所获得的代理签名密钥推算出原始签名者的签名密钥。又可分为两种：代理非保护代理签名和代理保护代理签名。代理签名的分类第五节代理签名具有证书的代理签名(delegationbywarrant)，分两种类型：授权代理签名和持票代理签名。授权代理签名(delegateproxy)：原始签名者用他的签名密钥使用普通的签名方案签一个文件（证书），然后把产生的证书发给代理签名者。持票代理签名(bearerproxy)：证书由消息部分和原始签名者对新产生的公钥的签名组成。原始签名者把新产生的公钥所对应的私钥以安全的方式发给代理签名者。代理签名的分类第五节代理签名代理签名又可分为强代理签名和弱代理签名。强代理签名——代理签名不仅能够代表原始签名者的签名，也能代表代理签名者的签名；弱代理签名——代理签名只代表原始签名者的签名。代理签名的分类第五节代理签名2学时消息认证与Hash函数——公钥密码的应用第七章消息认证概述认证函数消息认证码Hash函数和MAC的安全性Hash算法主要内容机密性（Confidentiality）：确保信息不暴露给未经授权的人或应用进程。完整性（Integrity）：只有得到允许的人或应用进程才能修改数据，并且能够判别出数据是否已被更改。可用性（Availability）：只有得到授权的用户在需要时才可以访问数据，即使在网络被攻击时也不能阻碍授权用户对网络的使用。三种基本安全需求认证系统由认证编码器和认证译码器组成条件：指定的接收者能检验和证实消息的合法性、真实性和完整性发送者和接收者不能抵赖除了合法的发送者，其它人不能伪造消息认证系统第一节消息认证认证函数的特点：必须是单向函数对于一个特定消息，很难找到另外一个消息与其具有相同的认证码很难找到一对具有相同认证码的消息认证函数第一节消息认证认证函数可分为三类：消息加密：将整个消息的密文作为认证符；消息认证码（MAC）：是消息和密钥的公开函数，产生定长的认证符；Hash函数：将任意长的消息映射为定长的hash值的公开函数，该hash值则作为认证符。认证函数第一节消息认证消息认证码（MessageAuthenticationCode）：利用密钥生成固定长度的短数据块（MAC），将其附加在消息之后，也称为密码校验和（cryptographicchecksum）。MAC函数与加密的区别：不要求可逆性多对一不能用于数字签名第一节消息认证用消息认证码实现认证通过MAC，可以认证以下内容：

a.接收者可以确信所收到的消息M未被篡改；

b.接收者可以确信消息来自真实的发送者；

c.如果消息中包含顺序码(如X.25,TCP)，接收者可以确认消息的正常顺序。消息认证码第一节消息认证已知M和Ck(M)时，构造满足Ck(M’)=Ck(M)的消息M’在计算上不可行；Ck(M)应是均匀分布的，即对任何随机选择的消息M和M’，Ck(M’)=Ck(M)的概率是2-n，其中n是MAC的位数；设M’是M的某个已知的变换，即M’=f(M)，例如可令f

表示对M的一位或多位取反，那么

Pr[Ck(M’)=Ck(M)]=2-n

对MAC的要求第一节消息认证十进制移位加MAC算法

1980年，Sievi提出，称为十进制移位加算法(DecimalShiftandAddAlgorithm)简记为DSA，适用于金融支付中的数值消息交换业务，消息按十位十进制数字分段处理，不足十位时在右边以0补齐基于DES的MAC算法

两种：CBC模式和CFB模式。CBC模式是使用最广泛的一种，被美国作为数据认证算法(DataAuthenticationAlgorithm)，已被FIPS(FIPSPUB113)和ANSI(X9.17)作为标准。MAC算法第一节消息认证消息按64bit分组M1,M2,…,MN，不足时以0补齐，DES加密，设密钥为K，初始向量为0，计算如下：

O1=EK(M1)

O2=EK(M2XORO1)

O3=EK(M3XORO2) …

ON=EK(MNXORON-1)取加密结果最左边的r位作为认证码。r的大小由通信双方约定。第二节消息认证码MAC算法——CBC模式散列函数（HashFunction）：也称哈希函数，对任意长度的明文进行变换，得到相对应的函数值，称为散列值，或称散列值、消息摘要（MessageDigest）、指纹（Fingerprint），变换的过程称为散列变换。散列值的长度一般是固定的。用途：（1）消息鉴别码；（2）数字签名之前的预处理第二节散列函数第二节散列函数要求：对任意长度输入进行变换，得到固定长度输出求逆不可行对给定x，很难找到x’≠x，使得h(x’)=h(x)很难找到一对不同的x,x’，使得h(x’)=h(x)第二节散列函数对hash函数的要求满足条件（1）（2）的称之为单向散列函数(One-WayHashFunction)满足条件（1）~（3）的称之为弱散列函数（WeakHashFunction）或弱无碰撞的散列函数满足条件（1）~（4）的称之为强散列函数（StrongHashFunction）或强无碰撞的散列函数。对hash函数的要求第二节散列函数1978年，Rabin的方法利用DES的密码分组链接模式设计将明文M按M=m1m2…mn进行分组，mi为64bit，按DES的CBC模式依次对每个分组进行加密，令h0=初始向量，hi=Emi[hi-1]，加密过程不使用任何密钥，G=hn为最终得到的散列值。第二节Hash函数Hash函数举例散列函数用于签名时，假设签名消息为(x,y)，y=sigk(h(x))，则攻击者可用如下方式伪造攻击者计算Z=h(x)，找到x’≠x，但h(x’)=h(x)，则（x’,y）构成有效的签名；攻击者找到任意两个不同消息x’，x，满足h(x’)=h(x)，令签名者对h(x)签名，则（x’,h(x)）也是有效签名；攻击者伪造一个签名Z，若能计算h-1(Z)=x，则(x,h(x))为有效签名。对Hash函数的攻击第二节散列函数对hash函数的攻击可以看作是寻找碰撞的过程，攻击者的主要目标不是恢复原始的明文，而是用非法消息替代合法消息进行伪造和欺骗，。攻击方法：生日攻击、中间相遇攻击、穷举攻击第二节Hash函数对Hash函数的攻击攻击者通过一对已知的明文和散列值，就可以任意伪造其它明文的散列值，步骤如下：第一步，对已知明文M产生散列值G；第二步，将非法明文Q按Q=Q1Q2…Qn-2进行分组，每个分组长度为64bit；第三步，计算hi=EQi[hi-1]，1≤i≤n-2；第二节Hash函数中间相遇攻击第四步，产生232个不同的x，对每个x计算Ex[hn-2]，再任意产生232个不同的y，对每个y计算Dy[G]，D是对应于E的解密函数；第五步，找到一对对应的x和y，使得Ex[hn-2]=Dy[G]；第六步，生成新的明文Q′=Q1Q2…Qn-2xy。第二节Hash函数中间相遇攻击Merkle在1989年提出了散列函数的通用结构：

a.将原始消息M分成固定长度的分组(Block)Mi；

b.对最后一个分组MN填充，并附上原始消息M的长度，

使其长度等于固定长度；

c.设定链接变量(chainingvalue)的初始值CV0；

d.定义压缩函数f，CVi=f(CVi-1,Mi-1)；

e.循环操作N次，最后一个CVN为散列值。第二节Hash函数Hash函数的通用结构对hash函数的密码分析主要集中在f的内部结构进行分析，并试图找到能与f的执行产生碰撞的有效方法。第二节Hash函数密码分析2004年8月17日，美国加州圣巴巴拉，Crypto’2004。来自山东大学的王小云教授做了破译MD5、HAVAL-128、MD4和RIPEMD算法的报告。第二节Hash函数密码分析CollisionsforHashFunctionsMD4,MD5,HAVAL-128andRIPEMDMD5SHA-1RIPEMD-160HMAC第三节Hash算法Merkle于1989年提出hashfunction模型RonRivest于1990年提出MD41992年,RonRivest完成MD5(RFC1321)现行美国标准SHA-1以MD5的前身MD4为基础第三节Hash算法MD5输出：128bit分组长度：512bit算法细节：填充→轮函数MD5总体特征第三节Hash算法Step1:Padding，

M→M’ |M’|448mod512 |M’|>|M|→

如果|M|448mod512,则|M’