网络与信息安全
密码学基础
内容
? 对称加密算法
? 经典密码算法
? 现代密码算法
? AES
? 随机数发生器
对称加密算法的基本模型
? 加密, E,(X,K) ? Y,y = E(x,k)
X Y
K
E
Y X
K
D
? 解密, D,(Y,K) ? X,x = D(y,k)
对称加密算法研究
? 对称加密算法的特点
? 算法强度足够
? 安全性依赖于密钥，不是算法
? 速度快
? 两门学科
? 密码学
? 密码分析
用对称加密算法建立起来的安全通讯
密码学
? 三种考虑角度
? （ 1）从明文到密文的变换
? 替换 (substitution)
? 置换 (transposition)
? ……
? （ 2） 钥匙的数目
? 对称、单钥加密法
? 双钥、公钥加密
? （ 3）明文的处理方式
? 分组加密（块加密算法）
? 流方式加密
密码分析
? 发现 X和 K的过程被称为密码分析
? 分析的策略取决于加密的技术以及可利用的
信息，在加密算法设计和攻击时都需要用到
的技术
? 根据可利用信息的不同，可分为 5类,
? （ 1）只有密文
? （ 2）已知部分明文 -密文对
? （ 3）选择明文
? （ 4）选择密文
* （ 1）（ 2）（ 3）常见、（ 4）不常见
加密算法的有效性
? Unconditionally secure,绝对安全？
? 永不可破，是理想情况，理论上不可破，密
钥空间无限，在已知密文条件下，方程无解
。但是我们可以考虑,
? 破解的代价超过了加密信息本身的价值
? 破解的时间超过了加密信息本身的有效期
? Computationally secure,
? 满足上述两个条件
直觉：什么是一个好的加密算法
? 假设密码 (password)k是固定的
? 明文和密文是一个映射关系：单射，即
Ek(x1) != Ek(x2) if x1 != x2
? 通常情况是：明文非常有序
? 好的密码条件下，我们期望得到什么样的
密文
? 随机性
? 如何理解随机性
? 静态：特殊的点
? 动态：小的扰动带来的变化不可知
考虑设计一个加密算法
? 打破明文本身的规律性
? 随机性 (可望不可及 )
? 非线性 (一定要 )
? 统计意义上的规律
? 多次迭代
? 迭代是否会增加变换的复杂性
? 是否存在通用的框架，用于迭代
? 复杂性带来密码分析的困难和不可知性
? 实践的检验和考验
已有密码算法的讨论
? 经典密码算法
? 替换技术
? 置换技术
? 现代密码算法
? DES
? 其他密码算法
? AES密码算法
? Rijndael
经典密码算法
? 替换技术
? Caesar加密制
? 单表替换加密制
? Playfair加密制
? Hill加密制
? 多表加密制
? 置换技术
? 改变字母的排列顺序，比如
? 用对角线方式写明文，然后按行重新排序
? 写成一个矩阵，然后按照新的列序重新排列
? 转轮加密体制
? 多步结合
经典密码算法特点
? 要求的计算强度小
? DES之前
? 以字母表为主要加密对象
? 替换和置换技术
? 数据安全基于算法的保密
? 密码分析方法基于明文的可读性以及字母
和字母组合的频率特性
现代密码算法
? DES(Data Encryption Standard)
? IDEA
? Blowfish
? RC5
? CAST-128
? ……
分组密码算法设计指导原则
? Diffusion(发散 )
? 小扰动的影响波及到全局
? 密文没有统计特征，明文一位影响密文的多
位，增加密文与明文之间关系的复杂性
? Confusion(混淆 )
? 强调密钥的作用
? 增加密钥与密文之间关系的复杂性
? 结构简单、易于分析
Feistel分组加密算法结构之动机
? 分组加密算法，一一映射
? 当 n较小时，等价于替换变换
? 当 n较大时，比如 n=64,无法表达这样的
任意变换。
? Feistel结构很好地解决了二者之间的矛盾
Feistel分组加密算法结构之思想
? 基本思想：用简单算法的乘积来近似表达
大尺寸的替换变换
? 多个简单算法的结合得到的加密算法比任
何一个部分算法都要强
? 交替使用替换变换和排列 (permutation)
? 混淆 (confusion)和发散 (diffusion)概念的
应用
Feistel
结构图
Feistel结构定义
? 加密, Li = Ri-1; Ri = Li-1?F(Ri-1,Ki)
? 解密, Ri-1 = Li
Li-1 = Ri?F(Ri-1,Ki)
= Ri?F(Li,Ki)
Feistel分组加密算法特点
? 分组大小。越大安全性越高，但速度下降,64
比较合理
? 密钥位数。越大安全性越高，但速度下降,64
广泛使用，但现在已经不够用 — 〉 128
? 步数，典型 16步
? 子钥产生算法。算法越复杂，就增加密码分析
的难度
? 每一步的子函数。函数越复杂，就增加密码分
析的难度
? 快速软件实现，包括加密和解密算法
? 易于分析。便于掌握算法的保密强度以及扩展
办法。
Feistel分组
加密算法
之解密算法
Feistel分组加密算法之解密算法推导
DES算法
? 1977年由美国的标准化局 (NBS,现为
NIST)采纳
? 64位分组,56位密钥
? 历史,
? IBM在 60年代启动了 LUCIFER项目，当时的
算法采用 128位密钥
? 改进算法，降低为 56位密钥,IBM提交给
NBS(NIST),于是产生 DES
DES算法基本结构
DES,每一轮
Li = Ri-1 Ri = Li-1?F(Ri-1,Ki)
DES,Function F
Expansion,32 ? 48
S-box,6 ? 4
Permutation
DES,32位到 48位的扩展表
32 | 01 02 03 04 | 05
04 | 05 06 07 08 | 09
08 | 09 10 11 12 | 13
12 | 13 14 15 16 | 17
16 | 17 18 19 20 | 21
20 | 21 22 23 24 | 25
24 | 25 26 27 28 | 29
28 | 29 30 31 32 | 01
DES,S-box
S(1),
?14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07
?00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08
?04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00
?15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13
DES,Permutation
16 07 20 21 29 12 28 17
01 15 23 26 05 18 31 10
02 08 24 14 32 27 03 09
19 13 30 06 22 11 04 25
DES
之每步密钥产生过程
? PC-1
? 在第一步之前
? PC2
? 左移位数目表
? 1或者 2位
DES的强度
? 56位密钥的使用
? 理论上的强度,97年 $100000的机器可以在 6
小时内用穷举法攻破 DES
? 实际攻破的例子,97年 1月提出挑战，有人利
用 Internet的分布式计算能力，组织志愿军连
接了 70000多个系统在 96天后攻破
? DES算法的本质
? 关键在于 8个 S-BOX
? 针对 DES的密码分析
? 差分分析法
? 线性分析法
差分分析法
? 属于选择明文攻击
? 基本思想：通过分析特定明文差对结果密
文差的影响来获得可能性最大的密钥
? 差分在 DES的 16步加密过程中的传递，每
一个 S-BOX对于差分传递的概率特性
? 子密钥不影响每一步的输入差分，但是影
响输出的差分
? 针对每一个 DES步骤，用差分法可以推导
出该步的密钥
每一步的差分分析法
针对 DES的密码分析
? 差分分析法
? 247对选择明文，经过 247量级的计算可攻破
? 线性分析法
? 思想：用线性近似描述 DES变换
? 根据 247已知明文，可以找到 DES的密钥
二重 DES
C = EK2(EK1(P)) ? P = DK1(DK2(C))
针对两重分组加密算法的 中间相会攻击
三重 DES
C=EK3(DK2(EK1(P))) ? P=DK1(EK2( DK3(C)))
分组密码的用法
? 电子簿模式 (electronic codebook
mode)ECB
? 密码块链接 (cipher block chaining)CBC
? 密码反馈方式 (cipher feedback)CFB
? 输出反馈方式 (output feedback)OFB
电子簿模式 ECB
? 相同明文 ?相同密文
? 同样信息多次出现造
成泄漏
? 信息块可被替换
? 信息块可被重排
? 密文块损坏 ?仅 对应
明文块损坏
? 适合于传输短信息
密码块链接 CBC
? 需要共同的初始化
向量 IV
? 相同明文 ?不同密
文
? 初始化向量 IV可以
用来改变第一块
? 密文块损坏 ?两 明
文 块 损坏
? 安全性好于 ECB
密码反馈方式 CFB
? CFB:分组密码 ?流密码
? 需要共同的移位寄存器初始值 IV
? 对于不同的消息,IV必须唯一
? 一个单元损坏影响多个单元, (W+j-1)/j
W为分组加密块大小,j为流单元位数
输出反馈方式 OFB
? OFB:分组密码 ?流密码
? 需要共同的移位寄存器初始值 IV
? 一个单元损坏只影响对应单元
分组密码与序列 (流 )密码
? 定义,
? 分组密码 (block cipher)是对一个大的明文块
(block)进行固定变换的操作
? 序列密码 (stream cipher)也叫流密码，是对
单个明文位 (组 )的随时间变换的操作
? 相互转换
? 序列密码
? 异或 One-time pad
其他的密码算法
? IDEA
? Blowfish
? RC5
? CAST-128
? RC2
? RC4
IDEA算法
? 90年首次出现,91年修订,92公布细节
? 有望取代 DES
? 128位密钥,64位分组
? 设计目标可从两个方面考虑
? 加密强度
? 易实现性
IDEA设计思想
? 得到 confusion的途径
? 按位异或
? 以 216(65536)为模的加法
? 以 216+1 (65537)为模的乘法
? 互不满足分配律、结合律
? 得到 diffusion的途径
? 乘加 (MA)结构
? 实现上的考虑
? 软件和硬件实现上的考虑
IDEA
加密算法
IDEA
每一轮
BLOWFISH算法
? 作者为 Bruce Schneier[93]
? BLOWFISH算法特点
? 采用了 Feistel结构,16轮
? 快速,18时钟周期一个字节
? 紧凑：消耗不到 5k内存
? 简单：结构简单，易于实现和判定算法强度
? 安全性可变：通过选择不同的密钥长度选择
不同的安全级别。从 32位到 32*14=448位不
等
? 子密钥产生过程复杂，一次性
BLOWFISH算法讨论
? BLOWFISH算法可能是最难攻破的传统加
密算法，因为 S-BOX密钥相关
? 算法本身的特点
? 由于子密钥和 S-BOX产生需要执行 521
个 BLOWFISH加密算法，所以不适合于
密钥频繁变化的应用场合
? 子密钥和 S-BOX产生可以保存起来
? 与 Feistel分组密钥算法不同，每一步的两
个部分都参与运算，不是简单的传递
? 密钥变长带来灵活性
? 速度快，在同类算法中相比较是最快的
RC5加密算法
? 作者为 Ron Rivest
? 算法特点
? 三个参数
? 参数 w,表示字长,RC5加密两字长分组，可用
值为 16,32,64
? 参数 r,表示轮数，可用值 0,1,…,255
? 参数 b,表示密钥 K的字节数，可用值 0,1,…,255
? RC5版本,RC5-w/r/b
? 算法作者建议标定版本为 RC5-32/12/16
RC5加密算法
? 三个基本运算
? 字的加法，模 2w +
? 按位异或 ⊕
? 左循环移位 <<<
? 算法,
LE0 = A + S[0]
RE0 = B + S[1]
for i = 1 to r do
LEi = ((LEi-1⊕ REi-1) <<< REi-1 + S[2*i]
REi = ((REi-1⊕ LEi) <<< LEi + S[2*i+1]
RC5加、解密算法结构
CAST-128加密算法
? RFC 2144[97]定义
? 密钥 48-128位,8位增量
? 16轮 Feistel分组结构
? 64位分组
? 特殊处,
? 每一步两个子密钥
? 每一步的 F不同
CAST-128每步细节图
CAST-128算法之讨论
? S-Box是固定的，但设计时尽量保证了非
线性。设计者认为，选择一个好的非线性
S-BOX比随机的 S-BOX更可取
? 子密钥的产生过程采用了与其他算法不同
的产生法来加强其强度。目标是对抗已知
明文攻击。 Blowfish和 RC5算法使用了不
同的技术来保证这一点。
? F函数具有好的 confusion,diffusion等特
性。子密钥相关、轮数相关增加了强度。
RC2加密算法
? 设计者 Ron Rivest
? 分组长度 64位，密钥长度 8到 1024位
? 适合于在 16位微处理器上实现
? RC2在 S/MIME中用到的密钥为 40,64、
128位不等
RC4流加密算法
? 设计者 Ron Rivest
? 工作方式 OFB
? 算法特点,
? 简单、快速
? 随机序列的产生，用到 8*8的 S盒
AES介绍
? 1997年 NIST宣布征集 AES算法
? 要求, 与三重 DES比，要快且至少一样安全,
分组 128位,密钥 128/192/256位
? 1998年确定第一轮 15个候选者
? 1999年确定第二轮五个候选者, MARS,
RC6,Rijndael,Serpent,Twofish
? 2000年底 Rijndael胜出
Rijndael简介
? 不属于 Feistel结构
? 加密、解密相似但不对称
? 支持 128/192/256(/32=Nb)数据块大小
? 支持 128/192/256(/32=Nk)密钥长度
? 有较好的数学理论作为基础
? 结构简单、速度快
Rijndael简介 (续 )
? 数据 /密钥的矩阵表示
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
k00 k01 k02 k03
k10 k11 k12 k13
k20 k21 k22 k23
k30 k31 k32 k33
Nr Nb=4 Nb=6 Nb=8
Nk=4 10 12 14
Nk=6 12 12 14
Nk=8 14 14 14
? 轮数
Rijndael算法结构
? 假设,State表示数据，以及每一轮的中间结果
RoundKey表示每一轮对应的子密钥
? 算法如下,
? 第一轮之前执行 AddRoundKey(State,RoundKey)
? Round(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
? FinalRound(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
AddRoundKey(State,RoundKey);
}
Rijndael,AddRoundKey操作
? 按字节在 GF(28)上相加 (XOR)
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
k00 k01 k02 k03 k04 k05
k10 k11 k12 k13 k14 k15
k20 k21 k22 k23 k24 k25
k30 k31 k32 k33 k34 k35
?
=
b00 b01 b02 b03 b04 b05
b10 b11 b12 b13 b14 b15
b20 b21 b22 b23 b24 b25
b30 b31 b32 b33 b34 b35
Rijndael,ByteSub操作
? ByteSub(S-box)非线性、可逆
? 独立作用在每个字节上
? 先取 GF(28)上乘法的逆,再经过 GF(2)上一个仿射变换
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
b00 b01 b02 b03 b04 b05
b10 b11 b12 b13 b14 b15
b20 b21 b22 b23 b24 b25
b30 b31 b32 b33 b34 b35
S-box
aij bij
Rijndael,ShiftRow操作
? 第一行保持不变,其他行内的字节循环移位
Rijndael,MixColumn操作
? 列作为 GF(28)上多项式乘以多项式 c(x)
多项式 c(x) = ‘03’x3+ ‘01’x2+ ‘01’x+ ‘02’
c-1(x) = ‘ 0B’x3+ ‘0D’x2+ ‘09’x+ ‘0E’
? 模 M(x) = x4+1
每一轮操作
Round(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
Rijndael,Key schedule(1)
? 主密钥生成子密钥数组,(Nr+1)*Nb个字
? Nk<=6
KeyExpansion(byte Key[4*Nk],word W[Nb*(Nr+1)])
{
for(i=0;i<Nk;i++)
W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);
for(i=Nk;i<Nb*(Nr+1);i++) {
temp=W[i-1];
if(i%Nk == 0)
temp=ByteSub(temp<<<8)^Rcon[i/Nk];
W[i]=W[i-Nk]^temp;
};
};
? Rcon[i]=(xi-1,‘00’,‘00’,‘00’); xi-1为 GF(28)上的数,
Rijndael,Key schedule(2)
? Nk>6
KeyExpansion(byte Key[4*Nk],word W[Nb*(Nr+1)])
{
for(i=0;i<Nk;i++)
W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);
for(i=Nk;i<Nb*(Nr+1);i++)
{
temp=W[i-1];
if(i%Nk == 0)
temp=ByteSub(temp<<<8)^Rcon[i/Nk];
else if(i%Nk == 4)
temp=ByteSub(temp<<<8);
W[i]=W[i-Nk]^temp;
};
};
Rijndael,加密结构
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey);
AddRoundKey(State,ExpandedKey)
For(i=1;i<Nr;++i)
{
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,ExpandedKey+Nb*i);
}
ByteSub(State);
ShiftRow(State);
AddRoundKey(State,ExpandedKey+Nb*i);
}
Rijndael,解密结构
AddRoundKey()
For(i=1;i<Nr;++i)
{
ByteSub();
ShiftRow();
MixColumn();
AddRoundKey()
}
ByteSub();
ShiftRow();
AddRoundKey()
I_AddRoundKey()
I_ShiftRow();
I_ByteSub();
For(i=1;i<Nr;++i)
{
I_AddRoundKey()
I_MixColumn();
I_ShiftRow();
I_ByteSub();
}
I_AddRoundKey()
I_AddRoundKey()
For(i=1;i<Nr;++i)
{
I_ShiftRow();
I_ByteSub();
I_AddRoundKey()
I_MixColumn();
}
I_ShiftRow();
I_ByteSub();
I_AddRoundKey()
Rijndael算法的抵抗攻击能力
? 消除了 DES中出现的弱密钥的可能
? 也消除了 IDEA中发现的弱密钥
? 能有效抵抗目前已知的攻击算法
? 线性攻击
? 差分攻击
随机数产生
? 随机数用途，重要的角色，例如
? 认证过程中，避免重放攻击
? 会话密钥
? RSA公钥算法
? 随机数的基本特点
? 随机性
? 均匀分布，有大量的测试方案
? 独立性，难以测试，只能测试足够独立
? 不可预测性
? 随机选择 (Randomization)在算法设计中的意
义
伪随机数产生器
线性一致法 (linear congruential method)
基于密码学产生的随机数 (一 )
之循环加密法
基于密码学产生的随机数 (二 )
之 DES输出反馈模型
基于密码学产生的随机数 (三 )
之 ANSI X9.17
BBS伪随机数
产生器
? 通过了“下一位”测试 (next-bit test)
? 不存在多项式时间的算法使得在已知前 k位的
情况下预测出第 k+1位的概率大于 0.5
? BBS的安全性同样基于分解 n的难度
密码学基础
内容
? 对称加密算法
? 经典密码算法
? 现代密码算法
? AES
? 随机数发生器
对称加密算法的基本模型
? 加密, E,(X,K) ? Y,y = E(x,k)
X Y
K
E
Y X
K
D
? 解密, D,(Y,K) ? X,x = D(y,k)
对称加密算法研究
? 对称加密算法的特点
? 算法强度足够
? 安全性依赖于密钥，不是算法
? 速度快
? 两门学科
? 密码学
? 密码分析
用对称加密算法建立起来的安全通讯
密码学
? 三种考虑角度
? （ 1）从明文到密文的变换
? 替换 (substitution)
? 置换 (transposition)
? ……
? （ 2） 钥匙的数目
? 对称、单钥加密法
? 双钥、公钥加密
? （ 3）明文的处理方式
? 分组加密（块加密算法）
? 流方式加密
密码分析
? 发现 X和 K的过程被称为密码分析
? 分析的策略取决于加密的技术以及可利用的
信息，在加密算法设计和攻击时都需要用到
的技术
? 根据可利用信息的不同，可分为 5类,
? （ 1）只有密文
? （ 2）已知部分明文 -密文对
? （ 3）选择明文
? （ 4）选择密文
* （ 1）（ 2）（ 3）常见、（ 4）不常见
加密算法的有效性
? Unconditionally secure,绝对安全？
? 永不可破，是理想情况，理论上不可破，密
钥空间无限，在已知密文条件下，方程无解
。但是我们可以考虑,
? 破解的代价超过了加密信息本身的价值
? 破解的时间超过了加密信息本身的有效期
? Computationally secure,
? 满足上述两个条件
直觉：什么是一个好的加密算法
? 假设密码 (password)k是固定的
? 明文和密文是一个映射关系：单射，即
Ek(x1) != Ek(x2) if x1 != x2
? 通常情况是：明文非常有序
? 好的密码条件下，我们期望得到什么样的
密文
? 随机性
? 如何理解随机性
? 静态：特殊的点
? 动态：小的扰动带来的变化不可知
考虑设计一个加密算法
? 打破明文本身的规律性
? 随机性 (可望不可及 )
? 非线性 (一定要 )
? 统计意义上的规律
? 多次迭代
? 迭代是否会增加变换的复杂性
? 是否存在通用的框架，用于迭代
? 复杂性带来密码分析的困难和不可知性
? 实践的检验和考验
已有密码算法的讨论
? 经典密码算法
? 替换技术
? 置换技术
? 现代密码算法
? DES
? 其他密码算法
? AES密码算法
? Rijndael
经典密码算法
? 替换技术
? Caesar加密制
? 单表替换加密制
? Playfair加密制
? Hill加密制
? 多表加密制
? 置换技术
? 改变字母的排列顺序，比如
? 用对角线方式写明文，然后按行重新排序
? 写成一个矩阵，然后按照新的列序重新排列
? 转轮加密体制
? 多步结合
经典密码算法特点
? 要求的计算强度小
? DES之前
? 以字母表为主要加密对象
? 替换和置换技术
? 数据安全基于算法的保密
? 密码分析方法基于明文的可读性以及字母
和字母组合的频率特性
现代密码算法
? DES(Data Encryption Standard)
? IDEA
? Blowfish
? RC5
? CAST-128
? ……
分组密码算法设计指导原则
? Diffusion(发散 )
? 小扰动的影响波及到全局
? 密文没有统计特征，明文一位影响密文的多
位，增加密文与明文之间关系的复杂性
? Confusion(混淆 )
? 强调密钥的作用
? 增加密钥与密文之间关系的复杂性
? 结构简单、易于分析
Feistel分组加密算法结构之动机
? 分组加密算法，一一映射
? 当 n较小时，等价于替换变换
? 当 n较大时，比如 n=64,无法表达这样的
任意变换。
? Feistel结构很好地解决了二者之间的矛盾
Feistel分组加密算法结构之思想
? 基本思想：用简单算法的乘积来近似表达
大尺寸的替换变换
? 多个简单算法的结合得到的加密算法比任
何一个部分算法都要强
? 交替使用替换变换和排列 (permutation)
? 混淆 (confusion)和发散 (diffusion)概念的
应用
Feistel
结构图
Feistel结构定义
? 加密, Li = Ri-1; Ri = Li-1?F(Ri-1,Ki)
? 解密, Ri-1 = Li
Li-1 = Ri?F(Ri-1,Ki)
= Ri?F(Li,Ki)
Feistel分组加密算法特点
? 分组大小。越大安全性越高，但速度下降,64
比较合理
? 密钥位数。越大安全性越高，但速度下降,64
广泛使用，但现在已经不够用 — 〉 128
? 步数，典型 16步
? 子钥产生算法。算法越复杂，就增加密码分析
的难度
? 每一步的子函数。函数越复杂，就增加密码分
析的难度
? 快速软件实现，包括加密和解密算法
? 易于分析。便于掌握算法的保密强度以及扩展
办法。
Feistel分组
加密算法
之解密算法
Feistel分组加密算法之解密算法推导
DES算法
? 1977年由美国的标准化局 (NBS,现为
NIST)采纳
? 64位分组,56位密钥
? 历史,
? IBM在 60年代启动了 LUCIFER项目，当时的
算法采用 128位密钥
? 改进算法，降低为 56位密钥,IBM提交给
NBS(NIST),于是产生 DES
DES算法基本结构
DES,每一轮
Li = Ri-1 Ri = Li-1?F(Ri-1,Ki)
DES,Function F
Expansion,32 ? 48
S-box,6 ? 4
Permutation
DES,32位到 48位的扩展表
32 | 01 02 03 04 | 05
04 | 05 06 07 08 | 09
08 | 09 10 11 12 | 13
12 | 13 14 15 16 | 17
16 | 17 18 19 20 | 21
20 | 21 22 23 24 | 25
24 | 25 26 27 28 | 29
28 | 29 30 31 32 | 01
DES,S-box
S(1),
?14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07
?00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08
?04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00
?15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13
DES,Permutation
16 07 20 21 29 12 28 17
01 15 23 26 05 18 31 10
02 08 24 14 32 27 03 09
19 13 30 06 22 11 04 25
DES
之每步密钥产生过程
? PC-1
? 在第一步之前
? PC2
? 左移位数目表
? 1或者 2位
DES的强度
? 56位密钥的使用
? 理论上的强度,97年 $100000的机器可以在 6
小时内用穷举法攻破 DES
? 实际攻破的例子,97年 1月提出挑战，有人利
用 Internet的分布式计算能力，组织志愿军连
接了 70000多个系统在 96天后攻破
? DES算法的本质
? 关键在于 8个 S-BOX
? 针对 DES的密码分析
? 差分分析法
? 线性分析法
差分分析法
? 属于选择明文攻击
? 基本思想：通过分析特定明文差对结果密
文差的影响来获得可能性最大的密钥
? 差分在 DES的 16步加密过程中的传递，每
一个 S-BOX对于差分传递的概率特性
? 子密钥不影响每一步的输入差分，但是影
响输出的差分
? 针对每一个 DES步骤，用差分法可以推导
出该步的密钥
每一步的差分分析法
针对 DES的密码分析
? 差分分析法
? 247对选择明文，经过 247量级的计算可攻破
? 线性分析法
? 思想：用线性近似描述 DES变换
? 根据 247已知明文，可以找到 DES的密钥
二重 DES
C = EK2(EK1(P)) ? P = DK1(DK2(C))
针对两重分组加密算法的 中间相会攻击
三重 DES
C=EK3(DK2(EK1(P))) ? P=DK1(EK2( DK3(C)))
分组密码的用法
? 电子簿模式 (electronic codebook
mode)ECB
? 密码块链接 (cipher block chaining)CBC
? 密码反馈方式 (cipher feedback)CFB
? 输出反馈方式 (output feedback)OFB
电子簿模式 ECB
? 相同明文 ?相同密文
? 同样信息多次出现造
成泄漏
? 信息块可被替换
? 信息块可被重排
? 密文块损坏 ?仅 对应
明文块损坏
? 适合于传输短信息
密码块链接 CBC
? 需要共同的初始化
向量 IV
? 相同明文 ?不同密
文
? 初始化向量 IV可以
用来改变第一块
? 密文块损坏 ?两 明
文 块 损坏
? 安全性好于 ECB
密码反馈方式 CFB
? CFB:分组密码 ?流密码
? 需要共同的移位寄存器初始值 IV
? 对于不同的消息,IV必须唯一
? 一个单元损坏影响多个单元, (W+j-1)/j
W为分组加密块大小,j为流单元位数
输出反馈方式 OFB
? OFB:分组密码 ?流密码
? 需要共同的移位寄存器初始值 IV
? 一个单元损坏只影响对应单元
分组密码与序列 (流 )密码
? 定义,
? 分组密码 (block cipher)是对一个大的明文块
(block)进行固定变换的操作
? 序列密码 (stream cipher)也叫流密码，是对
单个明文位 (组 )的随时间变换的操作
? 相互转换
? 序列密码
? 异或 One-time pad
其他的密码算法
? IDEA
? Blowfish
? RC5
? CAST-128
? RC2
? RC4
IDEA算法
? 90年首次出现,91年修订,92公布细节
? 有望取代 DES
? 128位密钥,64位分组
? 设计目标可从两个方面考虑
? 加密强度
? 易实现性
IDEA设计思想
? 得到 confusion的途径
? 按位异或
? 以 216(65536)为模的加法
? 以 216+1 (65537)为模的乘法
? 互不满足分配律、结合律
? 得到 diffusion的途径
? 乘加 (MA)结构
? 实现上的考虑
? 软件和硬件实现上的考虑
IDEA
加密算法
IDEA
每一轮
BLOWFISH算法
? 作者为 Bruce Schneier[93]
? BLOWFISH算法特点
? 采用了 Feistel结构,16轮
? 快速,18时钟周期一个字节
? 紧凑：消耗不到 5k内存
? 简单：结构简单，易于实现和判定算法强度
? 安全性可变：通过选择不同的密钥长度选择
不同的安全级别。从 32位到 32*14=448位不
等
? 子密钥产生过程复杂，一次性
BLOWFISH算法讨论
? BLOWFISH算法可能是最难攻破的传统加
密算法，因为 S-BOX密钥相关
? 算法本身的特点
? 由于子密钥和 S-BOX产生需要执行 521
个 BLOWFISH加密算法，所以不适合于
密钥频繁变化的应用场合
? 子密钥和 S-BOX产生可以保存起来
? 与 Feistel分组密钥算法不同，每一步的两
个部分都参与运算，不是简单的传递
? 密钥变长带来灵活性
? 速度快，在同类算法中相比较是最快的
RC5加密算法
? 作者为 Ron Rivest
? 算法特点
? 三个参数
? 参数 w,表示字长,RC5加密两字长分组，可用
值为 16,32,64
? 参数 r,表示轮数，可用值 0,1,…,255
? 参数 b,表示密钥 K的字节数，可用值 0,1,…,255
? RC5版本,RC5-w/r/b
? 算法作者建议标定版本为 RC5-32/12/16
RC5加密算法
? 三个基本运算
? 字的加法，模 2w +
? 按位异或 ⊕
? 左循环移位 <<<
? 算法,
LE0 = A + S[0]
RE0 = B + S[1]
for i = 1 to r do
LEi = ((LEi-1⊕ REi-1) <<< REi-1 + S[2*i]
REi = ((REi-1⊕ LEi) <<< LEi + S[2*i+1]
RC5加、解密算法结构
CAST-128加密算法
? RFC 2144[97]定义
? 密钥 48-128位,8位增量
? 16轮 Feistel分组结构
? 64位分组
? 特殊处,
? 每一步两个子密钥
? 每一步的 F不同
CAST-128每步细节图
CAST-128算法之讨论
? S-Box是固定的，但设计时尽量保证了非
线性。设计者认为，选择一个好的非线性
S-BOX比随机的 S-BOX更可取
? 子密钥的产生过程采用了与其他算法不同
的产生法来加强其强度。目标是对抗已知
明文攻击。 Blowfish和 RC5算法使用了不
同的技术来保证这一点。
? F函数具有好的 confusion,diffusion等特
性。子密钥相关、轮数相关增加了强度。
RC2加密算法
? 设计者 Ron Rivest
? 分组长度 64位，密钥长度 8到 1024位
? 适合于在 16位微处理器上实现
? RC2在 S/MIME中用到的密钥为 40,64、
128位不等
RC4流加密算法
? 设计者 Ron Rivest
? 工作方式 OFB
? 算法特点,
? 简单、快速
? 随机序列的产生，用到 8*8的 S盒
AES介绍
? 1997年 NIST宣布征集 AES算法
? 要求, 与三重 DES比，要快且至少一样安全,
分组 128位,密钥 128/192/256位
? 1998年确定第一轮 15个候选者
? 1999年确定第二轮五个候选者, MARS,
RC6,Rijndael,Serpent,Twofish
? 2000年底 Rijndael胜出
Rijndael简介
? 不属于 Feistel结构
? 加密、解密相似但不对称
? 支持 128/192/256(/32=Nb)数据块大小
? 支持 128/192/256(/32=Nk)密钥长度
? 有较好的数学理论作为基础
? 结构简单、速度快
Rijndael简介 (续 )
? 数据 /密钥的矩阵表示
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
k00 k01 k02 k03
k10 k11 k12 k13
k20 k21 k22 k23
k30 k31 k32 k33
Nr Nb=4 Nb=6 Nb=8
Nk=4 10 12 14
Nk=6 12 12 14
Nk=8 14 14 14
? 轮数
Rijndael算法结构
? 假设,State表示数据，以及每一轮的中间结果
RoundKey表示每一轮对应的子密钥
? 算法如下,
? 第一轮之前执行 AddRoundKey(State,RoundKey)
? Round(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
? FinalRound(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
AddRoundKey(State,RoundKey);
}
Rijndael,AddRoundKey操作
? 按字节在 GF(28)上相加 (XOR)
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
k00 k01 k02 k03 k04 k05
k10 k11 k12 k13 k14 k15
k20 k21 k22 k23 k24 k25
k30 k31 k32 k33 k34 k35
?
=
b00 b01 b02 b03 b04 b05
b10 b11 b12 b13 b14 b15
b20 b21 b22 b23 b24 b25
b30 b31 b32 b33 b34 b35
Rijndael,ByteSub操作
? ByteSub(S-box)非线性、可逆
? 独立作用在每个字节上
? 先取 GF(28)上乘法的逆,再经过 GF(2)上一个仿射变换
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
b00 b01 b02 b03 b04 b05
b10 b11 b12 b13 b14 b15
b20 b21 b22 b23 b24 b25
b30 b31 b32 b33 b34 b35
S-box
aij bij
Rijndael,ShiftRow操作
? 第一行保持不变,其他行内的字节循环移位
Rijndael,MixColumn操作
? 列作为 GF(28)上多项式乘以多项式 c(x)
多项式 c(x) = ‘03’x3+ ‘01’x2+ ‘01’x+ ‘02’
c-1(x) = ‘ 0B’x3+ ‘0D’x2+ ‘09’x+ ‘0E’
? 模 M(x) = x4+1
每一轮操作
Round(State,RoundKey) {
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
a00 a01 a02 a03 a04 a05
a10 a11 a12 a13 a14 a15
a20 a21 a22 a23 a24 a25
a30 a31 a32 a33 a34 a35
Rijndael,Key schedule(1)
? 主密钥生成子密钥数组,(Nr+1)*Nb个字
? Nk<=6
KeyExpansion(byte Key[4*Nk],word W[Nb*(Nr+1)])
{
for(i=0;i<Nk;i++)
W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);
for(i=Nk;i<Nb*(Nr+1);i++) {
temp=W[i-1];
if(i%Nk == 0)
temp=ByteSub(temp<<<8)^Rcon[i/Nk];
W[i]=W[i-Nk]^temp;
};
};
? Rcon[i]=(xi-1,‘00’,‘00’,‘00’); xi-1为 GF(28)上的数,
Rijndael,Key schedule(2)
? Nk>6
KeyExpansion(byte Key[4*Nk],word W[Nb*(Nr+1)])
{
for(i=0;i<Nk;i++)
W[i]=(Key[4*i],Key[4*i|+1],Key[4*i+2],Key[4*i+3]);
for(i=Nk;i<Nb*(Nr+1);i++)
{
temp=W[i-1];
if(i%Nk == 0)
temp=ByteSub(temp<<<8)^Rcon[i/Nk];
else if(i%Nk == 4)
temp=ByteSub(temp<<<8);
W[i]=W[i-Nk]^temp;
};
};
Rijndael,加密结构
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey);
AddRoundKey(State,ExpandedKey)
For(i=1;i<Nr;++i)
{
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,ExpandedKey+Nb*i);
}
ByteSub(State);
ShiftRow(State);
AddRoundKey(State,ExpandedKey+Nb*i);
}
Rijndael,解密结构
AddRoundKey()
For(i=1;i<Nr;++i)
{
ByteSub();
ShiftRow();
MixColumn();
AddRoundKey()
}
ByteSub();
ShiftRow();
AddRoundKey()
I_AddRoundKey()
I_ShiftRow();
I_ByteSub();
For(i=1;i<Nr;++i)
{
I_AddRoundKey()
I_MixColumn();
I_ShiftRow();
I_ByteSub();
}
I_AddRoundKey()
I_AddRoundKey()
For(i=1;i<Nr;++i)
{
I_ShiftRow();
I_ByteSub();
I_AddRoundKey()
I_MixColumn();
}
I_ShiftRow();
I_ByteSub();
I_AddRoundKey()
Rijndael算法的抵抗攻击能力
? 消除了 DES中出现的弱密钥的可能
? 也消除了 IDEA中发现的弱密钥
? 能有效抵抗目前已知的攻击算法
? 线性攻击
? 差分攻击
随机数产生
? 随机数用途，重要的角色，例如
? 认证过程中，避免重放攻击
? 会话密钥
? RSA公钥算法
? 随机数的基本特点
? 随机性
? 均匀分布，有大量的测试方案
? 独立性，难以测试，只能测试足够独立
? 不可预测性
? 随机选择 (Randomization)在算法设计中的意
义
伪随机数产生器
线性一致法 (linear congruential method)
基于密码学产生的随机数 (一 )
之循环加密法
基于密码学产生的随机数 (二 )
之 DES输出反馈模型
基于密码学产生的随机数 (三 )
之 ANSI X9.17
BBS伪随机数
产生器
? 通过了“下一位”测试 (next-bit test)
? 不存在多项式时间的算法使得在已知前 k位的
情况下预测出第 k+1位的概率大于 0.5
? BBS的安全性同样基于分解 n的难度
