现代密码学(第二版)重点概念整理

1、第一章1.被动攻击获取消息的真实内容进行业务流分析2.主动攻击中断、篡改、伪造3.安全业务 1、保密业务：保护数据以防被动攻击。 2、认证业务：用于保证通信的真实性。 3、完整性业务：防止对消息流的篡改和业务拒绝。 4、不可否认业务：用于防止通信双方中的某一方对所传输消息的否认。 5、访问控制：访问控制的目的是防止对网络资源的非授权访问，控制的实现方式是认证，即检查欲访问某一资源的用户是否具有访问权。4. 安全通信需考虑加密算法用于加密的秘密信息秘密信息的分布与共享安全服务所需的协议5. 信息安全可分为系统安全、数据安全、内容安全，密码技术是保障数据安全的关键技术。6. 密码体制从原理上分为单

2、钥体制和双钥体制，单钥体制包括对明文消息按字符逐位加密的流密码和将明文消息分组加密的分组密码。双钥特点是将加密和解密能力分开。7. 密码攻击类型唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击8. 加密算法是无条件安全的，仅当密钥至少和明文一样长时，才能达到无条件安全9. 多表代换密码的计算问题，课后习题3、4第二章1.流密码的概念：利用密钥k产生一个密钥流z=z0z1，并使用如下规则对明文串x=x0x1x2加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密钥流由密钥流发生器f产生： zi=f(k,i)， i:加密器中的记忆元件(存储器)在时刻i的状态， f:由密钥

3、k和i产生的函数。2.分组密码与流密码的区别: 有无记忆性3.密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析4.同步流密码的关键是密钥流产生器。5.如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。6.周期达到最大值2n-1，周期达到最大值的序列称为m序列。7.若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。8.只能要求截获比周期短的一段时不会泄露更多

4、信息，这样的序列称为伪随机序列。9.设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则： 长周期。 高线性复杂度。 统计性能良好。 足够的“混乱”。 足够的“扩散”。 抵抗不同形式的攻击。10. 课后习题1、3第三章1. 分组密码设计的算法应满足下述要求（1） 分组长度要足够大（2） 密钥量要足够大（3） 由密钥确定置换的算法要足够复杂（4） 加密和解密运算简单（5） 数据扩展尽可能地小（6） 差错传播尽可能地小2. 扩散和混淆是由香浓提出的设计密码系统的两个基本方法，成功地实现了分组密码的本质属性，因而成为设计现代分组密码的

5、基础。3. Feistel加密结构第i轮迭代的输入为前轮输出的函数（详见课本P33）Li=Ri-1Ri=Li-1F（Ri-1,Ki）4. DES：分组长度64比特，密钥长度56比特5. IDEA：分组长度64，密钥长度1286. AES:分组长度128，密钥长度128/192/2567. AES的设计策略是宽轨迹策略，轮函数包括：字节代换、行移位、列混合、密钥加8. 二重DES不能抵抗中途相遇攻击9. 课后作业习题：1、3、4、6第四章1.费尔玛定理定理4.2 (Fermat)若p是素数，a是正整数且gcd(a, p)=1，则ap-11 mod p。2. 欧拉函数设n是一正整数，小于n且与n互

6、素的正整数的个数称为n的欧拉函数，记为(n)。3. 欧拉定理定理4.4（Euler） 若a和n互素，则a(n)1 mod n。4.求最大公因子Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b, a mod b)。5. 中国剩余定理6. 定理4.6 设a的阶为m，则ak1 mod n的充要条件是k为m的倍数。7. 推论：a的阶m整除(n)。如果a的阶m等于(n)，则称a为n的本原根。如果a是n的本原根，则a,a2,a(n)在mod n下互不相同且都与n互素。特别地，如果a是素数p的本原根，则a, a2 , , ap-1在 mod p下都不相同

7、。8. 公钥密码体制提出者：W.Diffie和M.Hellman9. 勒让德符号定义4.1 设p是素数，a是一整数，符号 的定义如下：称符号 （a/p） 为Legendre符号。10.公钥密码算法应满足以下要求: 接收方B产生密钥对（公开钥PKB和秘密钥SKB）在计算上是容易的。 发方A用收方的公开钥对消息m加密以产生密文c，即c=EPKBm在计算上是容易的。 收方B用自己的秘密钥对c解密，即m=DSKBc在计算上是容易的。 敌手由B的公开钥PKB求秘密钥SKB在计算上是不可行的。 敌手由密文c和B的公开钥PKB恢复明文m在计算上是不可行的。 加、解密次序可换，即EPKBDSKB(m)=DSK

8、BEPKB(m)其中最后一条虽然非常有用，但不是对所有的算法都作要求。11.陷门单向函数是一族可逆函数fk，满足 Y=fk(X)易于计算（当k和X已知时）。 X=f-1k(Y)易于计算（当k和Y已知时）。 X=f-1k(Y)计算上是不可行的（当Y已知但k未知时）。12. RSA算法提出人;R.Rivest, A.Shamir和L.Adleman,安全性是基于分解大整数的困难性假定13. 计算题：课后3、4、5、6、7、8、10、14、15、17、18、19、20第五章1.假定两个用户A、B分别与密钥分配中心KDC (key distribution center)有一个共享的主密钥KA和KB，

9、A希望与B建立一个共享的一次性会话密钥，可通过以下几步来完成：2. 无中心的密钥分配时，两个用户A和B建立会话密钥需经过以下3步：3. 公钥管理机构与公用目录表类似，这里假定有一个公钥管理机构来为各用户建立、维护动态的公钥目录，但同时对系统提出以下要求，即： 每个用户都可靠地知道管理机构的公开钥，而只有管理机构自己知道相应的秘密钥。 公开钥的分配步骤如下：4.简单分配5. Diffie-Hellman密钥交换是W. Diffie和M. Hellman于1976年提出的第一个公钥密码算法算法的安全性基于求离散对数的困难性。缺点：易受中间人攻击（Oscar图例）6.秘密分割门限方案定义： 设秘密s

10、被分成n个部分信息，每一部分信息称为一个子密钥或影子，由一个参与者持有，使得：由k个或多于k个参与者所持有的部分信息可重构s。由少于k个参与者所持有的部分信息则无法重构s。 则称这种方案为(k,n)-秘密分割门限方案，k称为方案的门限值。如果一个参与者或一组未经授权的参与者在猜测秘密s时，并不比局外人猜秘密时有优势，即由少于k个参与者所持有的部分信息得不到秘密s的任何信息。则称这个方案是完善的，即(k,n)-秘密分割门限方案是完善的。7. 基于中国剩余定理的门限方案：课本P1388. 课后习题1、2、3、4、6第六章1.消息认证用以验证接收消息的如下属性：真实性（的确是由它所声称的实体发来的：

11、消息源认证）完整性（未被篡改、插入、删除）消息的顺序性和时间性2. 认证符的产生方法：消息认证函数MAC、杂凑函数3.杂凑函数应满足以下条件： 函数的输入可以是任意长 函数的输出是固定长 已知x，求H(x)较为容易，可用硬件或软件实现前3个是杂凑函数能用于消息认证的基本要求 已知h，求使得H(x)=h的x在计算上是不可行的，这一性质称为函数的单向性，称H(x)为单向散列函数单向性对使用秘密值的认证技术(见图3(e)极为重要。假如不具有单向性，则攻击者截获M和C=H(SM)后，求C的逆SM，就可求出秘密值S 已知x，找出y(yx)使得H(y)=H(x)在计算上是不可行的 找出任意两个不同的输入x

12、、y，使得H(y)=H(x)在计算上是不可行的4.第I类生日攻击已知一散列函数H有n个可能输出，H(x)是一特定输出，若对H随机取k个输入，则至少有一个输入y使得H(y)=H(x)的概率为0.5时，k有多大？称对散列函数H寻找上述 y 的攻击为第I类生日攻击5. 第类生日攻击：设散列函数H有2m个可能的输出（即输出长m比特），如果H的k个随机输入中至少有两个产生相同输出的概率大于0.5，则称寻找函数H的具有相同输出的两个任意输入的攻击方式为第类生日攻击6. 大多数杂凑函数如MD5、SHA，其结构都是迭代型的，算法的核心技术是设计无碰撞的压缩函数f7. MD5杂凑算法Ron Rivest提出，算

13、法的输入为小于264比特长的任意消息，分为512比特长的分组输出为160或128比特长的消息摘要。8. 2004年山东大学王小云教授破译了MD5，2005年，王小云等提出了对SHA-1碰撞搜索攻击9. 杂凑函数并不是为用于MAC而设计的，由于杂凑函数不使用密钥，因此不能直接用于MAC10. 基于密码杂凑函数构造的MAC的安全性取决于镶嵌的杂凑函数的安全性第七章1.数字签字应满足以下要求：（1）签字的产生必须使用发方独有的一些信息以防伪造和否认。（2）签字的产生应较为容易。（3）签字的识别和验证应较为容易。（4）对已知的数字签字构造一新的消息或对已知的消息构造一假冒的数字签字在计算上都是不可行的

14、。2.由签字算法产生数字签字算法的安全性在于从M和S难以推出密钥x或伪造一个消息M使M和S可被验证为真。4. 数字签字标准DSS； RSA算法既能用于加密和签字，又能用于密钥交换。 DSS使用的算法只能提供数字签字功能。5. DSA是在ElGamal和Schnorr两个签字方案的基础上设计的，其安全性基于求离散对数的困难性。6. Needham-Schroeder协议KDC的密钥分配过程，可用以下协议（称为Needham-Schroeder协议）来描述： AKDC：IDAIDBN1 KDCA： EKAKSIDBN1EKBKSIDA AB：EKBKSIDA -弱点 BA：EKSN2 AB：EKSf(N2)7. 交互证明系统交互证明系统由两方参与，分别称为证明者（prover，简记为P）和验证者（verifier，简记为V），其中P知道某一秘密（如公钥密码体制的秘密钥或一平方剩余x的平方根），P希望使V相信自己的确掌握这一秘密。8.交互证明和数学证明的区别是：数学证明的证明者可自己独立地完成证明，而交互证明是由P产生证明、V验证证明的有效性来实现，因此双方之间通过某种信道的通信是必需的。9.交互证明系统须满足以下要求： 完备性: 如果P知道某一秘密，V将接受P的证明。 正确性: 如果P能以一定的概率使V相信P的证明，则P知道相应的秘密。10.零知识证明零知识证明起源于最