从零实现 SPN 密码体制并完成差分攻击：C++ 实验详解

相信大家在信息安全学习过程中，绕不开密码体制基础的学习。那作为初学者最先接触的加密体制应该就是 SPN 密码体制了，在本文中将围绕一个 4 轮、16 位分组的 SPN（Substitution-Permutation Network，替换-置换网络）密码体制展开，先实现基础加密算法，再构造 S 盒差分分布表（DDT），最后利用 3 轮差分特征对最后一轮子密钥进行统计恢复。

---

目录

• 1. SPN 密码体制简介

• 2. 实验参数与加密流程

• 3. SPN 加密代码实现

• 4. 差分攻击基本思想

• 5. S 盒差分分布表 DDT

• 6. 本实验的差分路径设计

• 7. 差分攻击代码实现

• 8. 运行结果如何理解

• 9. 当前 SPN 的安全性问题

• 10. 如何提升安全性

• 11. 总结

---

1. SPN 密码体制简介

SPN 的全称是 Substitution-Permutation Network，中文一般称为 替换-置换网络。

它是很多现代分组密码的重要设计思想，基本结构由三类操作反复组成：

操作	作用	本实验中的体现
轮密钥异或	引入密钥相关性	明文或中间状态与子密钥异或
S 盒替换	提供非线性混淆	4 bit 输入映射到 4 bit 输出
P 盒置换	提供扩散	将 16 位状态重新排列

通俗地说：

• S 盒让输入和输出之间的关系变得非线性；

• P 盒让某一小块上的差异扩散到更多位置；

• 轮密钥异或让攻击者不能只看公开算法，还必须恢复密钥。

---

2. 实验参数与加密流程

2.1 实验参数

参数	取值
分组长度	16 位
主密钥长度	80 位
轮数	4 轮
S 盒规模	4 × 4
每轮 S 盒数量	4 个
子密钥数量	5 个，记为 K1 ~ K5

2.2 加密流程

本实验中的 SPN 加密流程如下：

明文 x（16 bit）
    │
    ├── ⊕ K1
    │
    ├── 第 1 轮：S 盒替换 → P 盒置换
    │
    ├── ⊕ K2
    │
    ├── 第 2 轮：S 盒替换 → P 盒置换
    │
    ├── ⊕ K3
    │
    ├── 第 3 轮：S 盒替换 → P 盒置换
    │
    ├── ⊕ K4
    │
    ├── 第 4 轮：S 盒替换
    │
    ├── ⊕ K5
    │
密文 y（16 bit）

需要注意的是：最后一轮不再执行 P 盒置换。这也是差分攻击中常见的设计切入点，因为攻击者可以从密文端对最后一轮进行部分逆推。

2.3 S 盒

本实验采用的 4 bit S 盒如下：

输入	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
输出	E	4	D	1	2	F	B	8	3	A	6	C	5	9	0	7

S 盒负责提供非线性，是差分攻击分析的重点。

2.4 P 盒

P 盒定义为：

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

如果第 i 位为 1，则它会被移动到第 P[i] 位。

---

3. SPN 加密代码实现

下面是完整的 SPN 加密代码。

代码结构主要分为四部分：

1. 定义 S 盒和 P 盒；

2. 从主密钥中截取子密钥；

3. 实现 S 盒替换与 P 盒置换；

4. 按轮函数执行 SPN 加密。

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;
// S-box
const int S_BOX[16] = {
    0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
    0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7
};

// P-box
const int P_BOX[16] = {
    0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15
};

string clean(string s) {
    s.erase(remove(s.begin(), s.end(), ' '), s.end());
    return s;
}

// 获取子密钥Kr
uint16_t getSubKey(const string& fullKey, int r) {
    string sub = fullKey.substr(4 * r - 4, 16);
    return (uint16_t)bitset<16>(sub).to_ulong();
}

// S-box 替换
uint16_t applySBox(uint16_t u) {
    uint16_t v = 0;
    for (int i = 0; i < 4; ++i) {
        int temp = (u >> (4 * (3 - i))) & 0xF;
        v |= (S_BOX[temp] << (4 * (3 - i)));
    }
    return v;
}

// P-box 置换
uint16_t applyPBox(uint16_t v) {
    uint16_t w = 0;
    for (int i = 0; i < 16; ++i) {
        if ((v >> (15 - i)) & 1)
            w |= (1 << (15 - P_BOX[i]));
    }
    return w;
}

// SPN 加密主函数
uint16_t encryptSPN(string x_str, string K_str, int Nr) {
    uint16_t w = (uint16_t)bitset<16>(x_str).to_ulong();
    for (int r = 1; r <= Nr - 1; ++r) {
        uint16_t u = w ^ getSubKey(K_str, r);
        uint16_t v = applySBox(u);
        w = applyPBox(v);
    }

    uint16_t u_last = w ^ getSubKey(K_str, Nr);
    uint16_t v_last = applySBox(u_last);
    uint16_t y = v_last ^ getSubKey(K_str, Nr + 1);
    return y;
}

int main() {
    string raw_x, raw_K;
    if (!getline(cin, raw_x)) return 0;
    if (!getline(cin, raw_K)) return 0;
    string clean_x = clean(raw_x);
    string clean_K = clean(raw_K);
    uint16_t result = encryptSPN(clean_x, clean_K, 4);
    bitset<16> outBits(result);
    string outStr = outBits.to_string();
    for (int i = 0; i < 16; ++i) {
        cout << outStr[i];
        if ((i + 1) % 4 == 0) cout << " ";
    }
    cout << endl;
    return 0;
}

代码阅读重点

这段代码里最关键的是 encryptSPN() 函数：

for (int r = 1; r <= Nr - 1; ++r) {
    uint16_t u = w ^ getSubKey(K_str, r);
    uint16_t v = applySBox(u);
    w = applyPBox(v);
}

前三轮都执行：

异或子密钥 → S 盒替换 → P 盒置换

最后一轮则执行：

异或 K4 → S 盒替换 → 异或 K5

这使得攻击者可以对密文异或候选 K5 后，再通过逆 S 盒回推最后一轮 S 盒输入差分。

---

4. 差分攻击基本思想

差分密码分析的核心是研究：

输入差分 Δx 会以什么概率传播成输出差分 Δy？

其中差分一般使用异或定义：

$$\Delta x=x\oplus x^{\prime }$$

$$\Delta y=y\oplus y^{\prime }$$

攻击者会选择大量明文对：

(x, x')

并让它们满足固定输入差分：

x ⊕ x' = Δx

然后观察对应密文对：

(y, y')

如果某条差分路径概率明显高于随机情况，那么正确密钥候选在统计计数中会更容易出现高票。

---

5. S 盒差分分布表 DDT

5.1 DDT 的定义

对于一个 4 bit 输入、4 bit 输出的 S 盒，差分分布表定义为：

D D T [ Δ x ] [ Δ y ] = ∣ { x ∈ { 0 , 1 } 4 : S ( x ) ⊕ S ( x ⊕ Δ x ) = Δ y } ∣ DDT[\Delta x][\Delta y]=\left|\{x \in \{0,1\}^4 : S(x) \oplus S(x \oplus \Delta x) = \Delta y\}\right| DDT[Δx][Δy]= ​{x∈{0,1}4:S(x)⊕S(x⊕Δx)=Δy} ​

也就是说，DDT 统计的是：

当输入差分为 Δx 时，有多少个输入值会产生输出差分 Δy。

5.2 本实验 S 盒的关键差分

输入差分 Δx	输出差分 Δy	出现次数	概率
0x0	0x0	16	1
0xB	0x2	4	1/4
0xB	0x6	4	1/4
0x4	0x6	4	1/4

除去平凡差分 0x0 → 0x0 之外，本实验 S 盒最大差分概率为：

$$\frac{4}{16}=\frac{1}{4}$$

这个概率并不低，因此可以用来构造差分攻击路径。

---

6. 本实验的差分路径设计

6.1 攻击目标

本实验不直接恢复完整 80 位主密钥，而是恢复最后一轮子密钥 K5 中的部分 nibble。

在程序中，攻击目标是：

K5 的 nibble1 和 nibble3

也就是 16 位 K5 中两个 4 bit 分组。

6.2 选择输入差分

选择的明文输入差分为：

Δx = 0x0B00

它表示只有第 2 个 nibble 被激活，其他 nibble 差分为 0。

6.3 目标差分

经过前三轮差分传播后，期望到达第四轮输入位置的差分为：

Δu4 = 0x0606

也就是两个目标 nibble 的差分都为 0x6。

6.4 差分路径示意

输入差分：
Δx = 0x0B00
        │
        ▼
第 1 轮：
S 盒中使用高概率差分 0xB → 0x2
        │
        ▼
P 盒扩散：
差分被扩散到其他 nibble
        │
        ▼
第 2 轮：
多个活跃 S 盒继续传播差分
        │
        ▼
第 3 轮：
形成目标差分 Δu4 = 0x0606
        │
        ▼
最后一轮：
枚举 K5 的目标 nibble，逆 S 盒验证差分

6.5 差分特征概率估计

如果路径中一共使用了 5 次概率为 1/4 的 S 盒差分，则整体概率约为：

$$p={\left(\frac{1}{4}\right)}^5=\frac{1}{1024}=2^{-10}$$

这意味着平均每 1024 对明文中，大约会有 1 对符合该差分特征。

为了让统计结果更稳定，通常需要更多明文对：

$$N\approx \frac{c}{p}$$

其中 c 是统计显著性常数，取 4 到 8 时，大约需要：

4000 ~ 8000 对明文

实验代码中使用了 10000 对明文对。

---

7. 差分攻击代码实现

下面是完整差分攻击程序。

程序主要做了 5 件事：

1. 构建 S 盒差分分布表 DDT；

2. 随机生成满足 x2 = x1 ⊕ 0x0B00 的明文对；

3. 调用 SPN 加密得到密文对；

4. 枚举 K5 的两个目标 nibble；

5. 对最后一轮做部分逆推，统计符合 Δu4 = 0x0606 的候选密钥。

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;

// SPN 密码体制参数
// S-BOX
const int SBOX[16] = {
    0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8,
    0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7
};

// SBOX 的逆
const int SBOX_INV[16] = { 
    0xE, 0x3, 0x4, 0x8, 0x1, 0xC, 0xA, 0xF,
    0x7, 0xD, 0x9, 0x6, 0xB, 0x2, 0x0, 0x5
};

// P-BOX
const int PBOX[16] = {
    0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15
};

//找出来本轮要用的子密钥
uint16_t setsubkey(const string& fullKey, int r) {  
    string sub = fullKey.substr(4 * r - 4, 16);
    return (uint16_t)bitset<16>(sub).to_ulong();
}

//对16位输入的每4位应用SBOX，增加非线性的混淆
uint16_t applySBox(uint16_t u) {  
    uint16_t v = 0;
    for (int i = 0; i < 4; ++i) {
        int nibble = (u >> (4 * (3 - i))) & 0xF;
        v |= (SBOX[nibble] << (4 * (3 - i)));
    }
    return v;
}

//S盒的逆操作，用于解密或攻击
uint16_t applySBoxInv(uint16_t v) {  
    uint16_t u = 0;
    for (int i = 0; i < 4; ++i) {
        int nibble = (v >> (4 * (3 - i))) & 0xF;
        u |= (SBOX_INV[nibble] << (4 * (3 - i)));
    }
    return u;
}

//对16位输入的每1位应用PBOX，增加位置上的扩散
uint16_t applyPBox(uint16_t v) {   
    uint16_t w = 0;
    for (int i = 0; i < 16; ++i) {
        if ((v >> (15 - i)) & 1)
            w |= (1 << (15 - PBOX[i]));
    }
    return w;
}


uint16_t encryptSPN(uint16_t x, const string& K_str, int Nr) {
    uint16_t w = x;
    for (int r = 1; r <= Nr - 1; ++r) {
        uint16_t u = w ^ setsubkey(K_str, r);  //异或
        uint16_t v = applySBox(u);             //S盒代换
        w = applyPBox(v);                      //P盒置换
    }
    uint16_t u_last = w ^ setsubkey(K_str, Nr);//最后一轮没有P盒，直接异或子密钥后输出
    uint16_t v_last = applySBox(u_last);
    uint16_t y = v_last ^ setsubkey(K_str, Nr + 1);
    return y;
}

// 差分分布表DDT
void buildDDT(int ddt[16][16]) {
    memset(ddt, 0, sizeof(int) * 16 * 16);
    for (int x = 0; x < 16; ++x)
        for (int dx = 0; dx < 16; ++dx)
            ddt[dx][SBOX[x] ^ SBOX[x ^ dx]]++;
}

void printDDT(int ddt[16][16]) {
    printf("\nSBox 差分分布表 DDT \n");
    printf("Δx\\Δy |");
    for (int i = 0; i < 16; ++i) printf(" %2X", i);
    printf("\n------+");
    for (int i = 0; i < 16; ++i) printf("---");
    printf("\n");
    for (int dx = 0; dx < 16; ++dx) {
        printf("  %2X  |", dx);
        for (int dy = 0; dy < 16; ++dy)
            printf(" %2d", ddt[dx][dy]);
        printf("\n");  
    }
}

// 对密文做逆S盒，得到第4轮输入的对应nibble
int partialDecrypt(uint16_t y, uint16_t k5, int nibble_idx) {
    // nibble_idx: 0最高 3最低
    int shift = 4 * (3 - nibble_idx);
    int y_nibble = (y >> shift) & 0xF;
    int k_nibble = (k5 >> shift) & 0xF;
    return SBOX_INV[y_nibble ^ k_nibble];//用S逆查出来S盒的输入
}

// 差分攻击函数
void differentialAttack(const string& K_str, int Nr) {
    printf("\n=== SPN 差分攻击 ===\n");
    printf("目标：恢复最后一轮子密钥 K5\n\n");
    
    // 差分路径：Δx=0x0B00，3轮后目标差分 Δu4=0x0606
    // u4 中活跃的 nibble 是 nibble1(0x6) 和 nibble3(0x6)
    uint16_t delta_x    = 0x0B00;
    uint16_t target_diff = 0x0606;
    int count[256] = { 0 };    // count[k]: k的高4位=K5_nibble1候选，低4位=K5_nibble3候选
    int num_pairs = 10000;
    mt19937 rng(42);    //用梅森旋转算法找随机数
    uniform_int_distribution<int> dist_rng(0, 65535);

    printf("差分路径: Δx=0x%04X -> Δu4=0x%04X\n", delta_x, target_diff);
    printf("攻击活跃nibble: nibble1 和 nibble3\n");
    printf("生成 %d 对明文对...\n\n", num_pairs);

    for (int i = 0; i < num_pairs; ++i) {
        uint16_t x1 = (uint16_t)dist_rng(rng);
        uint16_t x2 = x1 ^ delta_x;
        uint16_t y1 = encryptSPN(x1, K_str, Nr);
        uint16_t y2 = encryptSPN(x2, K_str, Nr);
        
        for (int k = 0; k < 256; ++k) {
            int k5_n1 = (k >> 4) & 0xF;
            int k5_n3 = k & 0xF;
            // 对最后一轮的nibble1和nibble3做逆S盒
            int y1_n1 = (y1 >> 8) & 0xF;  // nibble1 = bits[11:8]
            int y2_n1 = (y2 >> 8) & 0xF;
            int y1_n3 = y1 & 0xF;        
            int y2_n3 = y2 & 0xF;

            int u4_1_n1 = SBOX_INV[y1_n1 ^ k5_n1];
            int u4_2_n1 = SBOX_INV[y2_n1 ^ k5_n1];
            int u4_1_n3 = SBOX_INV[y1_n3 ^ k5_n3];
            int u4_2_n3 = SBOX_INV[y2_n3 ^ k5_n3];
            
            // 检验活跃nibble的差分是否符合目标
            if ((u4_1_n1 ^ u4_2_n1) == 0x6 && (u4_1_n3 ^ u4_2_n3) == 0x6)
                count[k]++;
        }
    }
    
    // 排序
    vector<pair<int,int>> results;
    for (int k = 0; k < 256; ++k)
        results.push_back({ count[k], k });
    sort(results.rbegin(), results.rend());
    printf("候选 K5 统计（前10名nibble1和nibble3）：\n");
    printf("  %-12s  %-12s  %s\n", "K5_nibble1", "K5_nibble3", "计数");
    printf("  %-12s  %-12s  %s\n", "----------", "----------", "----");
    for (int i = 0; i < 10; ++i) {
        int k = results[i].second;
        printf("  0x%X           0x%X           %d\n",
               (k>>4)&0xF, k&0xF, results[i].first);
    }

    uint16_t realk5 = setsubkey(K_str, Nr + 1);
    int real_n1 = (realk5 >> 8) & 0xF;
    int real_n3 = realk5 & 0xF;
    int real_k  = (real_n1 << 4) | real_n3;
    printf("\n真实 K5: 0x%04X  (nibble1=0x%X, nibble3=0x%X, 计数=%d)\n",realk5, real_n1, real_n3, count[real_k]);
    printf("攻击恢复: nibble1=0x%X, nibble3=0x%X  (计数=%d)\n",(results[0].second>>4)&0xF,results[0].second&0xF,results[0].first);

    if (results[0].second == real_k)
        printf("\n[成功] 差分攻击成功恢复 K5 的活跃 nibble！\n");
    else {
        int rank = (int)(find_if(results.begin(),results.end(),[&](auto&r){return r.second==real_k;})-results.begin())+1;
        printf("\n[提示] 真实K5活跃nibble排名第%d，可增加明文对数量。\n", rank);
    }

}

int main() {
    int ddt[16][16];
    buildDDT(ddt);
    printDDT(ddt);

    // K = 0x3A94D2B7E1F05C68，截取80位
    const string K_str = "00111010100101001101001010110111111000011111000001011100011010001010010110110111";
    printf("使用密钥 K = %s\n", K_str.c_str());
    
    for (int i = 1; i <= 5; ++i) {
        printf("K%d=0x%04X%s", i, setsubkey(K_str, i), (i == 5 ? "\n" : ", "));
    }

    // 执行差分攻击
    differentialAttack(K_str, 4);
    return 0;
}

---

8. 运行结果如何理解

运行程序后，会先打印 S 盒的 DDT，然后输出候选 K5 的统计排名。

输出中比较关键的部分如下：

候选 K5 统计（前10名nibble1和nibble3）：
  K5_nibble1  K5_nibble3  计数
  ----------  ----------  ----
  ...

判断攻击是否成功时，主要看两点：

1. 真实 K5 的目标 nibble 排名是否靠前；

2. 排名第一的候选是否等于真实 K5 的目标 nibble。

如果程序输出：

[成功] 差分攻击成功恢复 K5 的活跃 nibble！

就说明在当前明文对数量下，差分统计已经把正确密钥候选筛选出来了。

为什么只恢复部分 K5？

因为差分路径只让某些 nibble 处于活跃状态。

没有被差分路径覆盖的 nibble，在这次攻击中不会产生有效统计偏差，因此无法通过这条路径直接恢复。

如果想恢复更多位密钥，可以继续设计其他差分路径，分别攻击其他 nibble。

---

9. 当前 SPN 的安全性问题

这个 16 位 SPN 是教学实验模型，不适合作为真实密码系统使用，主要问题如下。

9.1 S 盒最大差分概率偏高

本实验 S 盒的最大非平凡差分概率为：

1/4

对于差分攻击来说，这个概率比较高，容易构造出可用的多轮差分路径。

9.2 轮数较少

本实验只有 4 轮，其中前三轮可以构造差分路径，最后一轮用于猜测子密钥。

轮数越少，差分特征概率越高，攻击所需样本量越少。

9.3 分组长度太短

16 位分组空间只有：
$$2^{16}=65536$$

这意味着即使不用差分攻击，穷举和统计实验也非常容易完成。

9.4 子密钥生成方式简单

子密钥直接从主密钥中截取，缺少复杂的非线性密钥扩展。

这会导致不同轮子密钥之间结构关系较强，不利于抵抗相关密钥攻击等更复杂的分析方法。

---

10. 如何提升安全性

10.1 优化 S 盒设计

一个更安全的 S 盒应尽量满足：

• 最大差分概率更低；

• 非线性度更高；

• 代数次数更高；

• DDT 中非零项分布更均匀。

简单来说，就是不要让某个输入差分过于稳定地对应某个输出差分。

10.2 增加轮数

差分路径概率会随着轮数增加而快速下降。

轮数	差分特征概率估计	攻击难度
4	约 2^-10	很容易实验
6	约 2^-20	明文对需求明显增加
8	约 2^-30	实验成本大幅提高
10	约 2^-40	对玩具模型也开始不现实

10.3 增大分组长度

将 16 位分组扩展到 64 位或 128 位，可以显著提高攻击成本。

更大的分组意味着：

• 状态空间更大；

• 可利用的简单统计偏差更难收集；

• 穷举和全空间遍历不再现实。

10.4 使用非线性密钥扩展

不要简单地从主密钥中截取子密钥。

可以参考现代分组密码的设计，引入：

• S 盒；

• 轮常数；

• 字循环；

• 非线性变换；

• 扩散操作。

这样可以降低轮密钥之间的直接相关性。

---

11. 总结

本文通过一个 4 轮 16 位 SPN 玩具密码，完整演示了差分攻击的基本流程：

1. 实现 SPN 加密算法；

2. 计算 S 盒差分分布表 DDT；

3. 选择高概率差分路径；

4. 生成大量固定输入差分的明文对；

5. 枚举最后一轮子密钥候选；

6. 通过逆 S 盒和统计计数恢复部分 K5。

说明了一个重要结论：

分组密码的安全性不仅取决于密钥长度，还取决于 S 盒差分性质、P 盒扩散能力、轮数设计和密钥扩展方式。

对于学习密码学的同学来说，SPN 差分攻击是理解现代分组密码设计原则的经典入门实验。

---