密码学复习1

密码学(Cryptology)研究的是如何保证信息系统的安全。 加密密钥 解密密钥 明文 密文 消息源 加密变换 解密变换 文 明 窃听 干扰 密码分析

图1-1 保密通信系统模型 对消息进行变换，以使非法用户不能获取原始消息的过程称为加密(encryption)。消息经过加密变成了密文(ciphertext)，从密文恢复明文的过程称为解密(decryption)。

密码体制也叫密码系统，是指能完整地解决信息安全中的机密性、数据完整性、认证、身份识别、可控性及不可抵赖性等问题中的一个或几个的一个系统。

一个密码体制的安全性涉及到两方面的因素： (1) 所使用的密码算法的保密强度。

(2) 密码算法之外的不安全因素。(人员管理，非法授权)

1917年，Gilbert Vernam发明的一次一密密码是目前世界上唯一无条件安全的密码体制。对密码系统的常见攻击分为四种主要类型：

(1) 惟密文攻击。 在这种攻击中，密码分析者仅有一些密文。

(2) 已知明文攻击。在这种攻击中，分析者拥有一定数量的密文及其对应的明文。 (3) 选择明文攻击。分析者可以选择一些它认为对攻击有利的特定的明文，并获得相应的密文。

(4) 选择密文攻击。分析者可以选择一些它认为对攻击有利的特定的密文，并获得相应的明文。

四种攻击方式的攻击强度是递增的。

经典密码学主要包括两个既对立又统一的分支：密码编码学(Cryptography)和密码分析学(Cryptanalytics)。研究密码变化的规律并用之于编制密码以保护秘密信息的科学，称为密码编码学。研究密码变化的规律并用之于密码以获取信息情报的科学，称为密码分析学，也叫密码破译学。

根据加解密是否使用相同的密钥，可将密码体制分为对称和非对称密码体制。 按加密方式又可将密码体制分为流密码(或称序列密码)和分组密码。 按照在加密过程中是否使用除了密钥和明文外的随机数，可将密码体制区分为概率密码体制和确定性密码体制。

1949年，C. Shannon发表了“保密系统的通信理论”，为密码学的发展奠定了理论基础，使密码学成为一门真正的科学。

1976年，W. Diffie和M. Hellman发表了“密码学的新方向”一文，提出了一种新的密码设

计思想，从而开创了公钥密码学的新纪元。

第二章

按照一个明文字母是否总是被一个固定的字母代换进行划分，代换密码可分为两类：

单表代换密码：对明文消息中出现的同一个字母，在加密时都用同一个固定的字母来代换，不管它出现在什么地方。移位密码和仿射密码都属于单表代换密码

多表代换密码：明文消息中出现的同一个字母，在加密时不是完全被同一个固定的字母代换，而是根据其出现的位置次序，用不同的字母代换。如维吉利亚(Vigenere)

密码和Playfair密码

对明文字符按某种规律进行位置的置换，形成密文的过程称为置换加密。最常用的置换密码有两种：一种称为列置换密码，另一种称为周期置换密码。 列置换密码

列置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。 周期置换密码

周期置换密码是将明文字符按一定长度m分组，把每组中的字符按1，2，„，m的一个置换重排位置次序来得到密文的一种加密方法。

有一种理想的加密方案，叫做一次一密乱码本(one-time pad)，由Major Joseph Mauborgne和AT&T公司的Gilbert Vernam在1917年发明，被认为是无条件安全的密码体制，即是一种不可攻破的密码体制。

第三章

几种典型的分组加密算法：数据加密标准DES密码算法、国际数据加密算法IDEA、高级加密标准AES.

在密码学的体系结构中我们已经知道，以数学为基础的密码学发展到现在，其主要分类就是两类：一是分组密码，另一是流密码。分组密码又分为对称分组密码和非对称分组密码(公钥密码)。

分组密码相对于公钥密码来说，具有整体结构简单、运行速度快、实现平台(硬件、软件、芯片)容易、运行模式构造方便等特点.

一般分组密码的构造都应遵循下列几个原则：

1. 要有足够大分组长度 l ，保证足够大的明文空间，避免给攻击者提供太多的明文统计特征信息。

2. 密钥空间要尽可能大 以抵抗攻击者通过穷举密钥破译密文或者获得密钥信息。

3. 保证足够强的密码算法复杂度 以加强分组密码算法自身的安全性，使攻击者无法利用简单数学关系找到破译缺口。

具体来说，在分组密码算法的安全策略中，用的最多的就是采用代换－置换网络(Substitution-Permutation Network)，简称SP网络。它是由S变换(代换)和P变换(置换或换

位)交替进行多次迭代而形成的变换网络。 S变换：代换。作用是混乱 P变换：置换。作用是扩散。

混乱 是指明文与密钥、以及密文之间的统计关系尽可能复杂化，使破译者无法理出相互间的依赖关系，从而加强隐蔽性

扩散 是指让明文中的每一位(包括密钥的每一位)直接或间接影响输出密文中的许多位，或者让密文中的每一位受制于输入明文以及密钥中的若干位，以便达到隐蔽明文的统计特性。 Feistel密码结构。

衡量S盒的几个重要指标： 1、非线性度。 2、差分均匀性。 3、雪崩效应。

4、可逆完整性、没有门限。 DES加密算法

IDEA密码算法虽然没有采用直观的S-P网络结构，但却采用混合的乘加(MA－Multiplication Addition)特殊网路结构来实现混淆和扩散

：逐位mod 2 加；

：16位整数mod 2 16(即65536)加法运算，在图中用 表示，而在文中为简便起见，用+表示；

16⊙：16位整数mod( 2 ＋1)(即65537)乘法运算； AES加密算法。

分组密码的操作模式：

电子密码本模式(ECB-electroniccode book mode):相同明文分组对应相同的密文，容易暴露明文的数据格式以及它的某些统计特性。

密码分组链接模式(CBC-cipherblok chaining mode)：若发生传输错误，则会影响其他的明文块，但它的错误传播是有限的。

密码反馈模式(cipher feedback mode-CFB)：可掩盖明文的数据统计特征，但是存在错误传播。

输出反馈模式(out feedback mode-OFB)：可克服错误传播，但抵抗消息流篡改攻击的能力不如CFB。

公钥密码体制的优点是可以适用网络的开放性要求，与对称密钥体制相比，密钥管理要简单的多，尤其可以方便地实现数字签名和认证。公钥密码体制并没有完全取代对称密码体制，这是因为公开密钥的算法相对复杂，加解/密速度较低。在实际应用中，这两种体制常常结合使用，即加解/密使用对称密钥体制，密钥管理使用公钥密码体制。

公钥密码体制就是一种陷门单向函数。一个单向函数是满足下列条件的函数：它是定义域到值域的一个映射，同时还要满足下列条件：计算函数值是容易的，而从函数值计算原像是不可行的。而所谓陷门单向函数是这样的单向函数，存在一个附加信息，当不知道该附加信息时，从函数值求原像是困难的，但当知道该附加信息时，从函数值求原像就变得容易了。

第五章

RSA公钥密码体制的加密和解密

密钥生成

首先选取两个大素数p和q，计算 n  pq ，其欧拉函数值为 (n)(p1)(q1)1gcd(然后随机选取整数e，满足 e ,  ( n ))  1 ，e 与 ( n ) 互质，计算 demod(n)则公钥为 (e, n)，私钥是d。p, q是秘密参数，需要保密，如不需要保存，可销毁。 加密运算

将要加密的消息按 n 的比特长度分组，依次对每个分组m做一次加密，所有分组的密文构成的序列即是原始消息的加密结果。即明文m满足 0  m  n ，则加密算法为：

c E(m)memodnc为密文，且 0  c  n 。dmodn解密算法 mD(c)c

Eigamal加密算法

g*pp随机选择一个大素数p，且要求p-1有大素数因子。 ( 是一个有p个元素的有限域，  *是  p 中的非零元构成的乘法群)是一个本原元。然后再选一个随机数k p(1k(1) 加密过程

待加密的消息为m  。首先选择随机数 r  *， 然后计算 pp1c1grmodp，c2myrmodp

则密文为(c1,c2)。

(2) 解密过程

kmc/cmodp21,c 收到密文 ( c 1 2 ) 后，计算 则消息m被恢复。

解密算法的正确性：因为ygkmodp,所以

c2myrmgkrkrkrc1kggmodpm.

Diffie-Hellman 密钥协商方案

Diffie-Hellman 在1976年提出一种基于求解离散对数的困难性的密钥协商方案。方案如下：

系统中的用户共同选用一个大素数 p 和Zp的一个本原元 g 。设用户A要求与用户B进行保密通信，为此，他们必须共享一个密钥。用户A和B一起执行以下步骤：

1) 用户A产生随机数(2≤≤p-2), 计算yAgmodp，并发送yA给用户B。 2) 用户B产生随机数(2≤≤p-2), 计算yBgmodp，并发送yB给用户A。 3) 用户A计算kyBmodpg

用户B计算kyAmodp =gmodp。 modp，

这样用户A和B就拥有了一个共享密钥k，就能以k作为会话密钥进行保密通信了。

http://zh.wikipedia.org/zh-cn/Diffie-Hellman；

第八章

1数字签名及其特征

当给文件签名时，附加在文件上的位串称为数字签名。它具有以下特征：

(1) 收方能够确认或证实发方的签名，但不能伪造。

(2) 发方发出签名的消息给收方后，就不能再否认他所签发的消息。 (3) 收方对已收到的签名消息不能否认。

(4) 第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。 2根据攻击者所拥有的信息的不同，对数字签名方案的攻击主要有以下几种常见的类型：

惟密钥攻击(key-only attack) 攻击者只拥有签名人的公钥；

已知消息攻击(known message attack) 攻击者拥有签名人用同一密钥对若干不同消息的签名；

选择消息攻击(chosen message attack) 攻击者可自己选择若干消息，并获得签名人对这些消息的签名；

适应性选择消息攻击(adaptive chosen message attack) 攻击者可自己选择一个消

息，并获得签名人对该消息的签名，经过分析后，再选择一个对他有利的消息， 获得签名人的签名

攻击者攻击的目的可分为完全破译（获得密钥）和部分破译（选择性伪造：对他或别人选择的一些消息产生有效的签名；存在性伪造：攻击者至少可以为一则消息x产生一个有效的签名y，而消息签名对(x, y)是签名人以前从来没有产生过的。） 数字签名的分类： 1、 直接数字签名：直接数字签名是在签名者和签名接收者之间进行的。假设签名接

收者知道签名者的公钥。签名者用自己的私钥对整个消息或消息的散列码进行数字签名。缺点：可以以密钥丢失推卸责任。 2、仲裁数字签名：仲裁数字签名是在签名者、签名接收者和仲裁者之间进行的。仲裁者是签名者和签名接收者共同信任的。签名者首先对消息进行数字签名，然后送给仲裁者。仲裁者首先对签名者送来的消息和数字签名进行验证，并对验证过的消息和数字签名附加一个验证日期和一个仲裁说明，然后把验证过的数字签名和消息发给签名接收者。因为有仲裁者的验证，所以签名者无法否认他签过的数字签名，解决了直接数字签名中存在的弱点。

数字签名考点：

RSA数字签名方案； Schnorr数字签名方案； 数字签名标准（DSS）； EIGamal数字签名方案;

第九章

1 身份识别是对一个用户身份的实时验证，让验证者相信正在与之通信的另一方就是所声称的那个实体。身份识别协议就是对通信过程中的一方或双方的身份进行识别的一系列规则。身份识别协议涉及两个实体，声称者Ｐ，和验证者Ｖ。Ｐ要让Ｖ相信“他是Ｐ”。一个安全的身份识别协议至少应满足以下三个条件： ·Ｐ能向Ｖ证明他的确是Ｐ；

·Ｐ向Ｖ证明他的身份后，Ｖ没有获得任何有用的消息，也即Ｖ不能伪装成Ｐ，向第三方证明他就是Ｐ；

·除了Ｐ以外的第三者Ｔ以Ｐ的身份执行该协议，能够让Ｖ相信他是Ｐ的概率可以

忽略不计。

2身份识别分弱识别和强识别两种类型 ：

(1) 弱识别：基于非时变的静态口令识别或由口令驱动的动态口令识别； (2) 强识别：通过向验证者展示他知道某秘密信息进而证明他自己的身份，在识别协议过程中，即使交互的信息被暴露，对手也不会从中得到关于声称者的秘密信息。 在身份识别过程中，除了口令以外，往往采用询问－应答(challenge-response)的方式进行识别(identification)。

3身份识别协议:不需要事先分享秘密的交互式用户身份识别协议，必须满足如下三条性质。

(1) 完全性(Completeness)：若用户与验证者双方都是诚实地执行协议，则验证者能以非常大的概率确信用户的身份。

(2) 正确性(Soundness)：若用户根本不知道与他所声称的用户身份相关的密钥，且验证者是诚实的，则验证者将以非常大的概率拒绝接受用户的身份。

(3) 隐藏性(Witness hiding)：若用户是诚实的，则不论协议进行了多少次，任何人(包括验证者)都无法从协议中推出用户的密钥，并且无法冒充用户。

4 Okamoto身份识别协议(了解具体算法)

1993年，Okamoto对Schnorr识别协议做了改进，这种改进在假定在

Zp上计算一个

特定的离散对数是困难的情况下，是可证明安全的。但从实现效率来讲，Schnorr协议比它更实用。

密码学的目的； 保密模型； 常见攻击类型； 密码学的两个分支； 密码体制分为哪两种； 按加密方式分为哪两种； DES的过程； EIGamal加密算法；

安全模型，安全性，若不安全，写出攻击方案； RSA加密算法过程；

数字签名的安全模型； EIGamal签名方案：

给出签名算法，签名验证算法，验证签名算法的正确性； Schonorr签名方案； 数字签名标准；

签密算法signcrypt算法组成；

基于身份的签名 算法组成（给出签名算法，写出验证算法），基于身份的加密（算法组成，给出加密算法，推出解密算法）