0x1 前言

这里是对差分密码攻击与线性密码攻击学习的笔记梳理，在撰写此文章时，对与两种攻击掌握还不够全面，所以如有错误，还请大家多多包涵。由于是笔记梳理，所以我会使用很多手写笔记，字很丑多多见谅。由于我的数学功底不是很好，所以本文章可能会存在一些数学公式与逻辑我暂时无法解释的情况，之后若有机会我一定补上。

0x2 差分密码攻击

它是针对分组密码攻击最有效的方法之一。差分攻击通过分析特定明文差分对相对应密文差分的影响来提取密钥。但是差分攻击的性能不一定会比暴力枚举好，差分攻击是典型的拿空间复杂度换时间复杂度的一种攻击方法。整体下来攻击的感觉有点类似对于两重DES的中途相遇攻击，通过对两头的计算与打表可以使密钥空间减半，从而可以使整体的时间复杂度减少。

基本原理

我们先来看一下差分攻击的基本原理，首先我们要明确一件事情，就是线性元件与非线性元件，之所以分组密码具有安全性，是因为存在非线性元件。比如：DES的s盒就是典型的非线性元件。

这里举一个简单的例子，假设我们有一个简单的没有非线性元件的密码算法：

此时当我们拥有一组明密文对的时候，我们就可以轻易的解出对应的k（这里不使用一次一密的方式）。

而当我们的密码算法存在非线性元件的时候：

此时加入了一个非线性元件，我们就不可以简单的使用异或解出密钥k的值。因为我们已经没有了上一个例子的等式了。

所以我们的研究重点应该是非线性元件而不是线性元件，因为线性元件处理是可以写成等式的，而非线性元件不行。下面的所有例子我们只讨论非线性元件对整个密码体系的影响。

基本原理我们以DES为例，我们有：

差分举例说明流程

不存在非线性元件时

通过这种⽅式，我们可以从⼀对密⽂中直接得到⼀对明⽂的异或，经过⼀次异或运算消除了密钥。这体 现了差分攻击的思想，我们可以不从单个明⽂和密⽂中考虑信息的获取，⽽是从⼀对密⽂和⼀对明⽂的 差分⼊⼿，进⾏破解。

一轮S盒

假设我们有如下的加密手段，其中S盒是公开非线性元件，K0与K1是密钥。

在加密过程中，不妨假设我们得到了两对明密文对。分别为M0，C0与M1与C1。

则我们则有以下状态：

由于s盒是公开的，所以我们可以直接计算出s盒的逆盒。

为此我们可以举一个简单的例子

假设我们有两组明密文对{（a-->9），（5-->6）}，{（9-->7），（8--0）}一共4组明密文对。我们有如下手法：

两轮s盒

这里如果我们继续套用单s盒的步骤就会出现一个问题，那就是：

这样我们就无法套用刚才的方法了，但是由于差分密码攻击是选择明文攻击，所以我们可以得到无数组明密文对，所以我们可以构造一些具有一定特征的明密文对。所以我们可以对S盒进行统计分析，我们可以分析当我们如何选取明密文对时，S等式成立的概率最大。

我们这里借助python进行一下分析。

我们打出来s盒左右所有数据后，我们发现当两数据异或后为0xf的时候，16种输出有十种都为13，所以我们可以做出如下假设：

一个例子，我们假设我们的密钥为0x4,0x6,0x7，此时对密码系统进行分析。根据我们刚才的差分分析，我们可以知道当我们构造明文异或为0xf的数据时，S盒有很高的概率存在特征。所以我们选择特定明文密文对：

m1 is 0   m2 is 15  c1 is 5   c2 is 10  
m1 is 1   m2 is 14  c1 is 3   c2 is 0
m1 is 2   m2 is 13  c1 is 7   c2 is 8
m1 is 3   m2 is 12  c1 is 6   c2 is 9
m1 is 4   m2 is 11  c1 is 1   c2 is 13
m1 is 5   m2 is 10  c1 is 11  c2 is 12
m1 is 6   m2 is 9   c1 is 4   c2 is 15
m1 is 7   m2 is 8   c1 is 2   c2 is 14
m1 is 8   m2 is 7   c1 is 14  c2 is 2
m1 is 9   m2 is 6   c1 is 15  c2 is 4
m1 is 10  m2 is 5   c1 is 12  c2 is 11
m1 is 11  m2 is 4   c1 is 13  c2 is 1
m1 is 12  m2 is 3   c1 is 9   c2 is 6
m1 is 13  m2 is 2   c1 is 8   c2 is 7
m1 is 14  m2 is 1   c1 is 0   c2 is 3
m1 is 15  m2 is 0   c1 is 10  c2 is 5

此时我们就要利用上述差分分析的结论来求解K1。结论如图：·吧

这时我们对所有的明文异或为0xf的明文进行上一个例子（单s盒）的操作，我们就可以还原k_3（即第三个密钥）的值。

{'0': 2, '1': 0, '2': 0, '3': 0, '4': 6, '5': 6, '6': 4, '7': 10, '8': 8, '9': 4, '10': 
6, '11': 6, '12': 0, '13': 0, '14': 0, '15': 0}

我们可以看见，key3主要命中了0x7最多，一共10次。由于数据量比较的小，所以统计规律并不明显，假如密钥涉及bit数增多，统计特征会更加明显。此时，我们就成功地将一个双轮s盒简化为了一个单轮s盒，后续只需要继续分析就可以解出其余key。假若统计规律不明显，我们也可以还原出几对大概率是密钥的key值，获得部分密钥值。

实验python代码：

import os
import time
import datetime
S_box  = [0x6,0x4,0xc,0x5,0x0,0x7,0x2,0xe,0x1,0xf,0x3,0xd,0x8,0xa,0x9,0xb]
RS_box = [0x4,0x8,0x6,0xa,0x1,0x3,0x0,0x5,0xc,0xe,0xd,0xf,0x2,0xb,0x7,0x9]
C = []
k_0 = 0x4
k_1 = 0x6
k_2 = 0x7 

def str_to_bin(m):
    '''
    字符串转bit,m为一个字符串
    '''
    return bin(ord(m))[2:]



def bin_to_string(m):
    '''
    bit转字符串
    '''
    return chr(int(m,2))

def Encrypt(m,k_0,k_1,k_2):
    '''
    两个s盒的加密过程,m为明文
    K_0,K_1,K_2为密钥
    '''
    u = m ^ k_0
    v = S_box[u]
    w = v ^ k_1
    x = S_box[w]
    c = x ^ k_2
    return c

def Decrypt(c,k_0,K_1,K_2):
    '''
    两个s盒的解密过程,c为密文
    K_0,K_1,K_2为密钥
    '''
    x = c ^ K_2
    w = RS_box[x]
    v = w ^ K_1
    u = RS_box[v]
    m = u ^ k_0
    return m

def print_data(i,j,s_i,s_j,s_ij):
    '''
    打印s盒差分分析表
    '''
    print(str(i).ljust(4," ") + str(j).ljust(4," ")+ str(s_i).ljust(4," ")+ str(s_j).ljust(4," ")+ str(s_ij).ljust(4," "))

def Analyze():
    '''
    构建差分表
    '''
    for i in range(16):#i为s盒输入输出的差值
        print("This round is : " + str(i))
        sum = [0 for i in range(16)]
        for j in range(0,16):
            m = j ^ i #j为一号输入，m为二号
            sum[S_box[j]^S_box[m]] =  sum[S_box[j]^S_box[m]] + 1
            print_data(j,m,S_box[j],S_box[m],S_box[j]^S_box[m])
        print("Maximum number of hits in this round: " + str(max(sum)))
        print("------------------------")

def make(k):
    '''
    构造明密文对的函数,k为两明文之间的异或值
    '''
    for i in range(16):
        m = i ^ k
        c_1 = Encrypt(i,k_0,k_1,k_2)
        c_2 = Encrypt(m,k_0,k_1,k_2)
        c1 = [i,m,c_1,c_2]
        C.append(c1)
        #print("m1 is " + str(i).ljust(4," ") + "m2 is " + str(m).ljust(4," ") + "c1 is " + str(c_1).ljust(4," ") + "c2 is " + str(c_2).ljust(4," "))

def solve():
    '''
    差分解决方案，求解k_1
    '''
    #print(C)
    D = {'0':0,'1':0,'2':0,'3':0,'4':0,'5':0,'6':0,'7':0,'8':0,'9':0,'10':0,'11':0,'12':0,'13':0,'14':0,'15':0}
    for i in C:
        T = [0 for i in range(16)] #制作临时T盒
        for j in range(16):
            V_0 = j^i[2]
            V_1 = j^i[3]
            V_3 = RS_box[V_0] ^ RS_box[V_1]
            #print(V_3)
            T[j] = V_3
        #T = S_box[M_1]^RS_box[M_2]
        #print(T)
        for k in range(16):#统计产生d的密钥
            if T[k] == 0xd:
                D[str(k)] = D[str(k)] + 1
        #D[str(S_box[M_1]^RS_box[M_2])] = D[str(S_box[M_1]^RS_box[M_2])] + 1
    print(D)

if __name__ == "__main__":
    #print("hello")
    '''
    A = str_to_bin("a")
    print(bin_to_string(A))
    c = Encrypt(0x5,0x4,0x6,0x7)
    m = Decrypt(c,0x4,0x6,0x7)
    print("Encrypt:",c)
    print("Decrypt:",m)
    '''
    #Analyze()
    make(0xf)
    solve()

多轮s盒

更高轮的s盒，思想基本上与上述相同，统计规律，将多重s盒化简为单一s盒以求解部分密钥。

这里只讨论差分密码分析的基本原理，如何找到一条高概率的差分特征，这里并没有讨论，给自己挖一个坑。

0x3 线性密码分析

基本原理

线性密码分析是选择明攻击。

⽬的：期待找到⼀个线性区分器来恢复最后⼀轮或部分密钥信息．

原理：假设我们有明⽂p和对应的密⽂c,根据c=e (k , p),我们可以建⽴n个涉及 密钥⽐特的⽅程

简单来说，和我们差分密码分析一样，就是要解决s盒不是线性元件的问题。假如s盒被我们替换为了等价的线性元件，那么我们只需要几组明密文对就可以将整个密码体系的密钥进行还原。

堆积引理

线性密码分析举例说明

0x4 参考资料

差分密码分析

线性密码分析

差分密码分析与线性密码分析ppt

0x5 笔记附件

笔记草稿.pdf