AdyaSarr/Stage-de-Fin-d-ann-e-M2-Side-Channel-Attack

# M2 阶段实习 — 针对 Classic McEliece 的侧信道攻击 [](https://www.python.org/) [](https://opensource.org/licenses/MIT) 本仓库包含针对后量子密码系统 **Classic McEliece** 的侧信道攻击 (*side-channel attack*) 的完整实现。该工作是在 **Hubert Curien 实验室**（圣艾蒂安）进行的 M2 毕业实习的一部分，由 **Pierre-Louis Cayrel（里昂大学 Jean Monnet 大学 - LabHC 的 HDR 讲师）、Brice Colombier（圣艾蒂安 IUT 的电子与编程研究员及教授）、Michaël Bulois（Camille Jordan 研究所实验室的数学讲师）、Vincent GROSSO（CNRS 研究员）和 Vlad-Florin Dragoi（罗马尼亚阿拉德 Aurel Vlaicu 大学副教授）** 共同指导完成。 ## 背景 Classic McEliece 是一种基于 **二元 Goppa 码** 的后量子密码系统，也是 NIST PQC 标准化的决赛选手。其安全性建立在随机码译码的困难性，以及通过秘密置换隐藏 Goppa 结构的基础之上。 本研究探讨了一种利用解封装过程中信息泄露的**侧信道攻击**。基于带噪声的汉明重量采集结果： $$y_{i,j} = \mathrm{wt}(\alpha_i^j \cdot G(\alpha_i)^{-2}) + \varepsilon_{i,j}, \qquad \varepsilon_{i,j} \sim \mathcal{N}(0, \sigma^2)$$ 攻击者可以完整重构出私钥 $(G, L)$：即 Goppa 多项式 $G$ 和支持集 $L = (\alpha_0, \ldots, \alpha_{n-1})$。 ## 攻击 Pipeline ┌─────────────────────────────────────────────────────────────────┐ ───────────────────┐\\ │1. 通过 FFT 进行 MLE 译码│ │带噪声的采集结果 (n×N) → 数据对 (α_i, β_i = G(α_i)^-2)│ │ 开销：O(P² log P) 其中 P = 2^m - 1│ ├───────────────────────────────────────────────────────────────── ─────────┤ │2. G 的代数重构│ │Bernstein 算法 (2024) — Reed-Solomon 插值│ │含纠错功能│ │开销：O(n² m²) 次二元运算│ ├───────────────────────────────────────────────────────────────── │3. 支持集 L 的重构│ │在公共校验矩阵上进行高斯消元（Pivot de Gauss）│ │开销：O((mt)³ + n(mt)²) 次二元运算│ └───────────────────────────────────────────────────────────────── ─────────┘ ## 实验结果 ### Classic McEliece 官方参数验证 | 参数 | m | t | n | mt | 测试的 σ | 攻击 | |------------------|----|-----|------|------|---------|---------| | mceliece348864 | 12 | 64 | 3488 | 768 | 0 – 2.3 | ✓ | | mceliece348864 | 12 | 64 | 3488 | 2.5+ | ✗ (达到阈值) | | mceliece460896 | 13 | 96 | 4608 | 1248 | 0 – 3.0+| ✓ | 只要 FFT 译码器的错误率对于 `mceliece348864` 保持在约 5% 以下，对于 `mceliece460896` 保持在 3% 以下，该攻击就能完全成功（同时重构 $G$ **和** $L$）。 ### mceliece460896 上的 σ 扫描测试 | σ | 成功率 | 错误数 | 恢复 G | 恢复 L | |------|----------|---------|--------|--------| | 0.5 | 1.0000 | 0 | ✓ | ✓ | | 1.0 | 1.0000 | 0 | ✓ | ✓ | | 1.5 | 1.0000 | 0 | ✓ | ✓ | | 2.0 | 1.0000 | 0 | ✓ | ✓ | | 2.5 | 0.9979 | 3 | ✓ | ✓ | | 3.0 | 0.9827 | 25 | ✓ | ✓ | ## 仓库结构 . ├──────src/ │ ├── Classe_Classic_McEliece.py # 密码系统的实现 │ ├── Classe_Decodeur_FFT.py # 基于 FFT 的 MLE 译码器 │ └── GoppaReconstructor.py # 代数重构 ├──────tests/ │ └── tests.py # 完整的测试 pipeline ├──────docs/ # 实习报告（即将推出） ├──────results/ # 实验结果 ├──────requirements.txt ├──────.gitignore └──────README.md ## 安装与使用 ### 前置条件 - Python ≥ 3.9 - 依赖库：`numpy`, `galois`, `joblib` ### 安装 ``` git clone https://github.com/AdyaSarr/Stage-de-Fin-d-annee-M2-Side-Channel-Attack.git cd Stage-de-Fin-d-annee-M2-Side-Channel-Attack pip install -r requirements.txt ``` ### 执行 运行完整的测试 pipeline： ``` python tests/tests.py mceliece348864 python tests/tests.py mceliece460896 ``` ### 编程方式使用示例 ``` import sys sys.path.insert(0, 'src') from Classe_Classic_McEliece import ClassicMcEliece from Classe_Decodeur_FFT import DecodorFFT from GoppaReconstructor import GoppaAttack import numpy as np # 密钥生成 mc = ClassicMcEliece('mceliece348864') mc.key_generation() # 含噪 acquisition decoder = DecodorFFT(mc) acq = decoder.noise_acquisitions(sigma=2.0) # FFT 解码 alphas, betas, scores = decoder.found_all_alpha_beta( acq, mode='alpha_any', Nb_couple=968 ) # 密钥 reconstruction attacker = GoppaAttack(mc) positions = np.arange(968, dtype=np.int64) G_hat, L_hat = attacker.full_attack( alphas, betas, positions, e_max=70, r_for_G=300 ) print(f"G_hat == G ? {G_hat == mc.G}") print(f"L_hat == L ? {np.array_equal(L_hat, [int(a) for a in mc.L])}") ``` ## 理论框架 本攻击依赖于以下工具： - **最大似然译码** (MLE)，利用循环抽取和离散对数变量替换实现 FFT 加速。 - Daniel J. Bernstein 提出的**带误差的 Reed-Solomon 插值算法**（*Understanding binary-Goppa decoding*, IACR ePrint 2024），通过求解线性方程组来计算近似值。 - **Goppa 支持集重构**，利用系统化形式的公共校验矩阵，并基于映射 $\Phi_G$ 的单射性。 报告中详细介绍了关于可容忍噪声阈值（$\sigma_c$）、所需最小数据对数量（$n_{\min}(p)$）的分析，以及对由 $X$（Artin 素数）生成的正规基的病态情况的探讨。 ## 参考文献 1. **Classic McEliece team.** *Classic McEliece: conservative code-based cryptography*. NIST PQC Round 4 submission (2022). [https://classic.mceliece.org/](https://classic.mceliece.org/) 2. **Daniel J. Bernstein.** *Understanding binary-Goppa decoding*. IACR Communications in Cryptology, 2024. [https://cic.iacr.org/p/1/1/14/](https://cic.iacr.org/p/1/1/14/) 3. **Nicolas Vallet, Brice Colombie, Vlad-Florin Drăgoi, Vincent Grosso, Pierre-Louis Cayrel**[https://cic.iacr.org/p/2/2/26/pdf](https://cic.iacr.org/p/2/2/26/pdf). 4. **Vlad Dragoi, Brice Colombier, Nicolas Vallet, Pierre-Louis Cayrel, Vincent Grosso.**[https://hal.science/hal-04835914/document](https://hal.science/hal-04835914/document) 5. **Michaël Bulois , Pierre-Louis Cayrel , Vlad-Florin Drăgoi , and Vincent Grosso**.**** 6. **Annelie Heuser⋆, Olivier Rioul, and Sylvain Guilley**.[https://eprint.iacr.org/2014/527.pdf](https://eprint.iacr.org/2014/527.pdf) ## 作者 **Adya SARR** M2 数学、计算机与密码学应用 (MIC) 巴黎西岱大学 (Université Paris Cité) Hubert Curien 实验室实习生 — 让·莫奈大学 (Université Jean-Monnet)，圣艾蒂安 ## 许可证 本代码在 MIT 许可证下分发。详情请参阅 [LICENSE](LICENSE) 文件。

标签：Classic McEliece, Python, 侧信道攻击, 后量子密码学, 密码学, 手动系统调用, 无后门, 逆向工具