【密码分析学 笔记】ch3 分组密码的差分分析和相关分析方法
ch3 分组密码的差分分析和相关分析方法
3.1 差分分析
- 评估分组密码安全性通用方法
- 可用于杂凑函数和流密码安全性
预备知识：
- 迭代性分组密码（分组密码一般结构）
- 简化版本 mini-AES CipherFour算法
3.1.1 差分分析原理
现象：密钥在异或运算过程中被抵消 → 直接从明文对异或值得到密文对异或值（绕过密钥）【不随机现象】
差分值: X和X’是两个长度为n的二进制比特串， Δ X = X ⊕ X ′ { ΔX=X \oplus X'} ΔX=X⊕X′ 称为X和X’的差分值
- 模加运算 模减差分
i轮差分、i轮差分对（differential）: P β 0 → i 轮 β i {P \beta_{0} \stackrel{i轮}\to \beta_{i} } Pβ0→i轮βi 差分经过i轮的传播特性
i轮差分概率： D P ( β 0 → i 轮 β i ) {DP(\beta_{0} \stackrel{i轮}\to \beta_{i}) } DP(β0→i轮βi)
理想分组密码： α {\alpha} α 是输入差分， β {\beta} β 是输出差分，n是分组长度，理想分组密码满足随机置换, ∀ β ∈ { 0 , 1 } n , D P ( α → i 轮 β ) = 1 / 2 n { \forall \beta \in \{0,1\} ^{n},DP(\alpha \stackrel{i轮}\to \beta)=1/2^{n} } ∀β∈{0,1}n,DP(α→i轮β)=1/2n,构造区分器关键：找到高概率的i轮差分 α → i 轮 β {\alpha \stackrel{i轮}\to \beta} α→i轮β，满足 D P ( α → i 轮 β ) > 1 / 2 n {DP(\alpha \stackrel{i轮}\to \beta)>1/2^{n}} DP(α→i轮β)>1/2n
差分分析原理：
- 发现长轮数、高概率的i轮差分（不随机现象）
- 建立与部分密钥有关的带概率的方程，利用正误密钥下，中间状态满足特定差分值的明密文对数服从不同分布，恢复密钥（分割密钥空间，建立方程组/约束条件，进行密钥恢复攻击）
差分分析攻击模型
假设 D P ( α , β ) = p > 1 / 2 n ， ∣ K ~ ∣ = k {DP(\alpha , \beta)=p >1/2^{n}，|\widetilde{K}|=k} DP(α,β)=p>1/2n，∣K ∣=k,设置 2 k { 2^{k} } 2k 个计数器，初始化为0
- 采样：选取满足条件的差分明文对
- 去噪：根据β值过滤对应的密文
- 恢复密钥：对方程组每个解都设置1个计数器，处理完所有明文对后从大到小排序，前 2 k − a {2^{k-a}} 2k−a个作为正确密钥候选值,结合穷举攻击等确定正确密钥
3.1.2 CipherFour 算法差分分析
3.1.2.1 各运算部件差分传播特性
CipherFour算法：
- 16bit分组长度
- r轮迭代
- 密钥长度为16(r+1)bits
- 假设轮密钥相互独立
算法每一轮（除最后一轮）包含：
- 16比特的轮密钥异或
- 4个4比特的S盒
- 16比特的比特置换
最后一轮包含：
- 16比特的轮密钥异或
- 4个4比特的S盒
- 16比特的白化密钥异或
1.S盒
非线性变换S盒差分传播概率：
- 输入差分α过S盒后变为输出差分β，记为** α → S β {\alpha \stackrel{S}\to \beta} α→Sβ**
- 满足 α → S β {\alpha \stackrel{S}\to \beta} α→Sβ 的明文对的个数为** N S ( α , β ) {N_{S}(\alpha,\beta)} NS(α,β)**
- 相应的 α → S β {\alpha \stackrel{S}\to \beta} α→Sβ 的差分传播概率为** D P ( α → S β ) = P r ( α → S β ) = N S ( α , β ) 2 m {DP(\alpha \stackrel{S}\to \beta)=Pr(\alpha \stackrel{S}\to \beta)=\frac{N_{S}(\alpha,\beta)}{2^{m}} } DP(α→Sβ)=Pr(α→Sβ)=2mNS(α,β)**
S盒差分分布表（DDT）
- 构造：α为行标，β为列标，行列交错处的项为 N S ( α , β ) {N_{S}(\alpha,\beta)} NS(α,β)，构造的 2 m × 2 n {2^{m}×2^{n}} 2m×2n的表
- CipherFour的DDT特性
- D P ( 0 x 0 → S 0 x 0 ) = 1 {DP(0x0 \stackrel{S}\to 0x0)=1} DP(0x0→S0x0)=1
- D P ( 0 x 0 → S 0 x i ) = 1 , i ≠ 0 {DP(0x0 \stackrel{S}\to 0xi)=1,i\neq0} DP(0x0→S0xi)=1,i=0
- 若
N
S
(
α
,
β
)
=
0
{N_{S}(\alpha,\beta)=0}
NS(α,β)=0，记作
α
↛
β
{\alpha \nrightarrow \beta}
α↛β
- 如 D P ( 0 x f → S 0 x 1 ) = 0 {DP(0xf \stackrel{S}\to 0x1)=0} DP(0xf→S0x1)=0
- 对随机置换RP(Random Permutation)
- P r ( α → R P β ) = 1 2 4 {Pr(\alpha \stackrel{RP}\to \beta)=\frac{1}{2^{4}}} Pr(α→RPβ)=241
- DDT中的数都是偶数
2.P置换
拉线操作，只改变bit位置，不改变取值
输出差分等于输入差分经过P置换后的结果
P ( X ) ⊕ P ( X ′ ) = P ( X ⊕ X ′ ) {P(X)\oplus P(X')=P(X \oplus X')} P(X)⊕P(X′)=P(X⊕X′)
3.异或密钥AK
（ X ⊕ K ) ⊕ ( X ′ ⊕ K ) = X ⊕ X ′ {（X\oplus K)\oplus (X'\oplus K)=X \oplus X'} （X⊕K)⊕(X′⊕K)=X⊕X′
输出差分等于输入差分
总结可得，差分在各部件的传播特性为：
- 过线性变换差分值确定
- 异或密钥差分值不变
- 过非线性变换差分值不确定，传播概率由S盒DDT决定
原文地址：https://blog.csdn.net/qq_26245471/article/details/143086107
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！