z2 n an 1an 2
做矩阵
而
an1
X S1 S2
an 2 a2 n cn cn 1 c1 X
Sn
c1 a1 a2 a2 a3 a a n n 1 an an 1 a2 n 1
基本概念
明文——要处理的数据 密文——处理后的数据 密钥——秘密参数 加密函数 解密函数

密码算法

密码算法如何构造？
需求1：可逆——算法的使用者可以求得逆函数 需求2：不可逆——敌手无法将密文恢复成明 文 秘密参数——密钥


密码算法实际上是一个带有秘密参数的函 数。
知道秘密参数，求逆非常容易 不知道秘密参数，求逆在计算上是不可行的




Vigenère密码
第二章 流密码
复习要点

流密码的基本思想 线性反馈移位寄存器序列的基本概念
特征多项式 序列的周期 m序列的定义 m序列的伪随机性 m序列的破译

流密码的基本概念

流密码是将明文划分成字符(如单个字母)，或其编码 的基本单元(如0, 1数字)，字符分别与密钥流作用进 行加密，解密时以同步产生的同样的密钥流实现。
输出反馈OFB模式
64 bit 寄存 器 64bit DES 64bit
选最左边 k位 k位
k
k
64 bit 寄存 器 64bit DES-1 64bit
选最左边
k bit xi
+
ki
yi
k bit
yi
+
k bit ki
xi
k bit
OFB模式
DES 算法

分组长度为64 bits (8 bytes) 密文分组长度也是64 bits。

分组密码概述
明文序列 x1, x2,…, xi,… 加密函数E: Vn×KVn 这种密码实质上是字长为m的数字序列的代换密码。
密钥k=(k0, k1,…, kt-1 ) 明文 x=(x0, x1,…, xm-1) 加密算法 密钥k=(k0, k1,…, kt-1 ) 明文 x=(x0, x1,…, xm-1)
密文 x=(y0, y1,…, ym-1)
解密算法
分组密码设计准则

混淆：人们所设计的密码应使用使得密钥和明文 以及密文之间的依赖关系相当复杂以至于这种依 赖性对密码分析者来说是无法利用的。 扩散：人们所设计的密码应使得密钥的每一位数 字影响密文的许多位数字以防止对密钥进行逐段 破译，而且明文的每一位数字也应影响密文的许 多位数字以便隐藏明文数字统计特性。
k
Xi 64bit DES-1 Yi 64bit
选最左边 k位
k bit xi
+
yi
yi
k bit
+
xi
CFB模式
k-比特密码反馈CFB模式

CFB的优点

它特别适于用户数据格式的需要。

能隐蔽明文数据图样，也能检测出对手对于密 文的篡改。
对信道错误较敏感，且会造成错误传播。 CFB也需要一个初始矢量，并要和密钥同时进 行更换。

分组密码的主要总体结构类型

分组密码算法一般采用迭代的方式来使用 乘积密码，其主要的总体结构类型有两种： Feistel密码和SP网络。
DES 是Feistel密码的代表。 AES是SP结构的代表。

Feistel密码结构
乘积密码指顺序地执行两个或多个基本 密码系统，使得最后结果的密码强度高于每 个基本密码系统产生的结果. Feistel还提出了实现代换和置换的方法。 其思想实际上是Shannon提出的利用乘积密 码实现混淆和扩散思想的具体应用。
标 准 数 据 加 密 算 法
DES的S1-盒的输入和输出关系

x5 x0 1 0
x5 x4 x3 x2 x1 x0 1 0 1 1 0 0
(y3 , y2, y1 , y0)=(0,0,1,0)
列号
行号 0 1 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
若敌手得到一段长为2n的密钥序列
z z1z2
z2n
由此可推出线性反馈移位寄存器连续的n+1个状态：
S1 z1 z2 S2 z2 z3
zn a1a2 zn 1 a2 a3
记为 记为
记为
an an 1 a2 n
Sn 1 zn 1 zn 2

电码本ECB模式

直接利用加密算法分别对分组数据组加密。 在给定的密钥下同一明文组总产生同样的 密文组。这会暴露明文数据的格式和统计 特征。
明文数据都有固定的格式，需要以协议的形式定 义，重要的数据常常在同一位置上出现，使密码 分析者可以对其进行统计分析、重传和代换攻击。
电码本ECB模式
LFSR的特征多项式
(*)
p(x)=1+c1x+…＋cn-1xn-1＋cnxn
1.
2.
n级LFSR输出序列的周期r不依赖于初始 条件，而依赖于特征多项式p(x)。
序列的周期达到最大2n-1，这种序列就是 m序列。 3. 显然对于特征多项式一样，而仅初始条 件不同的两个输出序列，一个记为{a(1)i}， 另一个记为{a(2)i}，其中一个必是另一个 的移位，即存在一个常数k，使得 a(1)i=a(2)k+i, i=1, 2,… 4、 n级LFSR输出序列为m序列，当且仅当 其反馈多项式是本原多项式
64 bit存储 k
64 bit存储 k yi DES-1
y i-1
xi
+
DES
yi
CBC模式
+
x’
CBC的优缺点

优点：能隐蔽明文的数据模式，在某种程度上 能防止数据纂改，诸如重放、嵌入和删除等。
缺点：会出现传播错误，对同步差错敏感（增 加或丢失一个或多个比特）。

CBC的错误传播
1. 明文有一组中有错，会使以后的密文组都受影响，

流密码强度完全依赖于密钥序列的随机性(Randomness) 和不可预测性(Unpredictability)。
核心问题是密钥流生成器的设计。 保持收发两端密钥流的精确同步是实现可靠解密的关 键技术。

流密码的框图
kI 安 全 信 道 kI
· · · KG
· · · KG
mi
ki
Eki(mi)
其中Ki是第i轮用的子密钥，由加密密钥K得到。一 般地，各轮子密钥彼此不同而且与K也不同。
图3.4 Feistel加解密过程
主要工作模式
即使有了安全的分组密码算法，也需要采 用适当的工作模式来隐蔽明文的统计特性、数 据的格式等，以提高整体的安全性，降低删除、 重放、插入和伪造成功的机会。 电子码本(ECB) 密码反馈链接(CBC) 密码反馈(CFB) 输出反馈(OFB) 。
密钥长度为64 bits，有8 bits奇偶校验，有效密钥长 度为56 bits。

算法主要包括：初始置换 IP、16轮迭代的乘积变换、 逆初始置换IP-1以及16个子密钥产生器。
DES算法框图
输入 64 bit明文数据
初始置换IP
乘积变换 （16轮迭代） 逆初始置换IP-1 64 bit密文数据 输出
加密 密钥 明文 加密 密文
解密 密钥 解密 原始明文
对称算法

早期的密钥算法是对称算法（Symmetric Algorithm），就 是加密密钥能够从解密密钥中推算出来，反之亦然。多数 对称算法中，加密和解密由同一个密钥来控制，也叫“单 钥算法”，如图所示。
非对称算法

用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密 密钥计算出来，就是非对称算法（Asymmetric Algorithm），也叫公 钥算法（Public-key Algorithm）或双钥算法，如图所示。

密码分组链接CBC模式

初始矢量IV(Initial Vector)：第一组明文
xi 加密时尚无反馈密文，为此需要在寄存 器中预先置入一个。收发双方必须选用同 一IV。 实际上，IV的完整性要比其保密性更为重 要。在CBC模式下，最好是每发一个消息， 都改变IV，比如将其值加一。

密码分组链接CBC模式
k
k
x
DES
y
y
DES-1
x
密码分组链接CBC模式
每个明文组xi加密之前，先与反馈至输入端的 前一组密文yi-1按位模2求和后，再送至加密算 法加密 各密文组yi不仅与当前明文组xi有关，而且通 过反馈作用还与以前的明文组x1, x2,…, xi-1， 有关 加密：yi=DESK(xi yi-1)，y0=IV 解密：xi=DESK-1(yi) yi-1
现代密码学（复习）
聂旭云 xynie@
目录





概述 流密码 分组密码 公钥密码 杂凑算法 数字签名 密码协议
第一章 引言
复习要点

密码学的基本概念 密码学的分类 密码体制攻击的四种类型 仿射密码体制的加密、解密原理，计算至 少一个实例

密码算法


CFB的缺点

输出反馈OFB模式

将分组密码算法作为一个密钥流产生器，其输出的kbit 密钥直接反馈至分组密码的输入端，同时这 k-bit 密钥和输入的k-bit明文段进行对应位模2相加。 克服了CBC和CFB的错误传播所带来的问题。
对于密文被篡改难以进行检测