tprest/falcon.py
GitHub: tprest/falcon.py
一个用 Python 实现的 Falcon 格基签名方案库，专注教学与研究用途。
Stars: 193 | Forks: 60
# falcon.py
本仓库实现了 Falcon 签名方案（https://falcon-sign.info/）。
Falcon 代表 **FA**st Fourier **L**attice-based **CO**mpact signatures over **N**TRU
**更新 13/01/2026：**API 已全面修改，以匹配其他库的 API。验证密钥现在为字节串，签名密钥可以从字节串导入导出。
## 内容
本仓库包含以下文件（大致按依赖顺序排列）：
1. [`common.py`](common.py) 包含共享函数与常量
2. [`rng.py`](rng.py) 实现了基于 ChaCha20 的 PRNG，适用于 KAT（独立使用）
3. [`samplerz.py`](samplerz.py) 实现了整数上的高斯采样器（独立使用）
4. [`fft_constants.py`](fft_constants.py) 包含 FFT 所需的预计算常量
5. [`ntt_constants.py`](ntt_constants.py) 包含 NTT 所需的预计算常量
6. [`fft.py`](fft.py) 实现了 R[x] / (xn + 1) 上的 FFT
7. [`ntt.py`](ntt.py) 实现了 Zq[x] / (xn + 1) 上的 NTT
8. [`ntrugen.py`](ntrugen.py) 生成满足 f G - g F = q 的多项式 f,g,F,G（Z[x] / (xn + 1)）
9. [`ffsampling.py`](ffsampling.py) 实现了快速傅里叶采样算法
10. [`falcon.py`](falcon.py) 实现了 Falcon
11. [`test.py`](test.py) 实现了测试以验证所有功能是否正确
## 使用方法
1. 导入模块：`from falcon import Falcon`
2. 生成 Falcon 实例：`falcon = Falcon(n)`
3. 生成密钥对：`sk, vk = falcon.keygen()`
4. 现在可以对消息签名：`sig = falcon.sign(sk, m)`
5. 验证签名：`falcon.verify(vk, m, sig)`
我们还提供了导入导出字节串的函数：`falcon.pack_sk(sk)` 与 `falcon.unpack_sk(sk_bytes)`。
首次使用时，请运行 `make test` 以确保代码在你的机器上正常运行。对于 `n = 1024` 的测试套件可能需要几分钟：
```
python3 test.py
Test Sig KATs : OK
Test SamplerZ KATs : OK (46.887 msec / execution)
Test battery for n = 64
Test FFT : OK (0.907 msec / execution)
Test NTT : OK (0.957 msec / execution)
Test NTRUGen : OK (260.644 msec / execution)
Test ffNP : OK (5.024 msec / execution)
Test Compress : OK (0.184 msec / execution)
Test Signature : OK (6.266 msec / execution)
Test battery for n = 128
Test FFT : OK (1.907 msec / execution)
Test NTT : OK (2.137 msec / execution)
Test NTRUGen : OK (679.113 msec / execution)
Test ffNP : OK (11.589 msec / execution)
Test Compress : OK (0.36 msec / execution)
Test Signature : OK (11.882 msec / execution)
Test battery for n = 256
Test FFT : OK (4.298 msec / execution)
Test NTT : OK (5.014 msec / execution)
Test NTRUGen : OK (778.603 msec / execution)
Test ffNP : OK (26.182 msec / execution)
Test Compress : OK (0.758 msec / execution)
Test Signature : OK (23.865 msec / execution)
Test battery for n = 512
Test FFT : OK (9.455 msec / execution)
Test NTT : OK (9.997 msec / execution)
Test NTRUGen : OK (3578.415 msec / execution)
Test ffNP : OK (59.863 msec / execution)
Test Compress : OK (1.486 msec / execution)
Test Signature : OK (51.545 msec / execution)
Test battery for n = 1024
Test FFT : OK (20.706 msec / execution)
Test NTT : OK (22.937 msec / execution)
Test NTRUGen : OK (17707.189 msec / execution)
Test ffNP : OK (135.42 msec / execution)
Test Compress : OK (3.292 msec / execution)
Test Signature : OK (102.022 msec / execution)
```
## 性能分析
我添加了一个用于性能分析的 Makefile 目标。如果你在 Linux 机器上运行 `make profile`，应该会得到类似以下的结果：
请确保已安装 `pyprof2calltree` 和 `kcachegrind`，否则无法运行。
## 作者
* **Thomas Prest**（thomas . prest @ pqshield . com）
## 感谢
感谢以下人员发现代码中的各种错误：
- Dan Middleton
- Nadav Voloch
- Dekel Shiran
- Shlomi Dolev
## 免责声明
这不是参考代码。Falcon 的参考代码位于 https://falcon-sign.info/。此代码仍在开发中，不应被视为安全或适用于生产环境。同时，我无法保证其在 Python 2.x 上的可移植性。
不过，本 Python 代码相对简单，因此我希望它能对尝试实现 Falcon 的人有所帮助。
如果你发现错误或缺陷，请通过提供的地址向我报告，我将非常感激。
## 许可证
MIT
标签：API兼容, ChaCha20, CVE, Falcon, FFT, KAT测试, make test, NTRU, NTT, PRNG, Python实现, 后量子密码, 基于格的密码学, 多项式生成, 字节串序列化, 密钥导出导入, 密钥生成, 开源密码库, 快速傅里叶变换, 数字签名, 格基签名, 格密码, 签名方案, 签名验证, 紧凑签名, 逆向工具, 高斯采样