fixed-point-fndsa/fxp-falcon-py

# Falcon 的定点 Python 原型 来自论文的定点算术栈参考实现 *Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme* （De Almeida Braga, Fouque, Lachguel, Prest）。本代码库包含： - 所提出的 fxp pipeline 的高级 Python 模型（`fxp/`）， - Prest 的 `falcon.py` 参考实现（`falcon_ref/`）， - 52 个单元测试 + 约 60 个数值测试向量（`tests/`）， - 验证与精度基准测试脚本（`experiments/`）， - 生成 FFT twiddle 表的辅助脚本（`scripts/`）。 `falcon_ref/` 是 Thomas Prest 在 上的参考 Falcon Python 实现的一个（稍作修改的）克隆。 `fxp/` 包仅替换了浮点算术； 其他所有内容（NTRUGen、hash-to-point、base-sampler 表等）均 复用自该参考实现。`falcon_ref/falcon.py` 同时暴露了 现代的 `Falcon` 管理类（上游 API）以及一个 `SecretKey` 适配器，它 提供了 fxp 模块所依赖的基于属性的有状态 API。 对该参考实现的唯一实质性更改是 [`falcon_ref/ntrugen_filters.py`](falcon_ref/ntrugen_filters.py)：它添加了 论文中的四个 NTRUGen 拒绝谓词 —— 对 `‖FFT(f,g)‖_∞` 的严格边界， `α_hybrid`、`‖FFT(F,G)‖_∞` 以及 `‖L_10_root‖_∞` —— 被分支整合到密钥生成中， 以便每个密钥都能保持在定点 `m`-预算所依赖的范围内。 如果没有它们，极端的密钥可能会导致 `|x| < 2^p` 定点格式溢出。 ## 首先查看的内容 | 你想要…… | 阅读 | |---|---| | 了解 fxp pipeline | [`fxp/README.md`](fxp/README.md) | | 查看 NTRUGen 密钥过滤器（论文中的检查） | [`falcon_ref/ntrugen_filters.py`](falcon_ref/ntrugen_filters.py) | | 重新生成 FFT twiddle 表 | [`scripts/`](scripts/) | ## 环境要求 **Python ≥ 3.10**（`fxp` 包在模块作用域内使用了 PEP 604 `X | None` 类型别名；3.9 无法导入它）。 使用 [uv](https://docs.astral.sh/uv/)（推荐 —— 无需激活）： ``` uv sync --extra experiments # creates .venv with core + benchmark deps ``` 然后通过 `uv run python …` / `uv run pytest …` 运行任何内容，或者直接使用 下面的 `make` 目标 —— 它们会自动检测 `uv` 并且无需激活。 如果没有 uv，请手动将 [`pyproject.toml`](pyproject.toml) 中的依赖安装到 venv 中： ``` python3 -m venv .venv && . .venv/bin/activate pip install beartype pycryptodome pytest mpmath matplotlib ``` 核心依赖（`beartype`、`pycryptodome`、`pytest`）涵盖了包和测试； `experiments/` 基准测试增加了 `mpmath` + `matplotlib`（即 `pyproject.toml` 中的 `experiments` 额外依赖）。 ## 快速开始 所有命令均从代码库根目录运行。运行 `make`（不带参数）以 列出每个目标。`make` 目标不需要激活 venv（它们使用 `uv run`）。每个脚本都会自动将 `fxp/` 和 `falcon_ref/` 添加到 `sys.path` 中 —— 这样 `from falcon import SecretKey` 就会解析到 Prest 的 `falcon.py`。 ### 测试（正确性） ``` make test # fxp unit tests + numerical KAT (core deps) python -m pytest tests/test_fxtypes.py # 52 unit tests, FxR/FxC arithmetic (~0.6 s) python tests/check_test_vectors.py # ~60 numerical KAT: FFT/ffLDL/division (~0.6 s) python tests/smoke_test_e2e.py --fast # KAT-only integration runner (~1 s) ``` `check_test_vectors.py` 的预言机是在 **float64** 中根据 `falcon_ref/` 计算出来的，因此 KAT 检查的是 fxp pipeline *是否与 float64 参考实现一致*（一项一致性/非回归测试） —— 而不是检查它是否更精确。fxp 是否优于 float64 取决于精度 `p`（在 `p=63` 时为 63 位尾数，而 float64 为 53 位，在 `p=127` 时甚至更多）以及具体的操作；精度基准测试（`experiments/bench_*_precision.py`）通过与 mpmath 256 位参考实现进行对比运行，才是量化该差异的手段。 `make test-ref` 额外运行了 Prest 的 `falcon.py` 附带的 自测（FFT/NTT/NTRUGen/ffNP/compress/sign + samplerz KATs）。 ### 实验（论文证据） 验证脚本（在前面加上 `uv run`，或激活 venv）： ``` uv run python experiments/sign_fxp_end_to_end.py # fxp == reference Falcon (A==B==C==D, 50 trials) uv run python experiments/sign_tweak_kat_fxp.py # Section-5.1 tweak: 0/1000 divergence in fxp ``` 四个精度基准测试图都有对应的 `make` 目标（自动检测 venv， 无需激活）。每个目标都会生成 `experiments/figures/.{png,pdf}` 和 `experiments/tables/.csv`： ``` make figures # all four (float64 vs FxP-63 vs FxP-127 vs mpmath-256) make fig-fft # or one at a time: fig-fft / fig-div / fig-ffldl / fig-ffsampling ``` 有关完整目录，请参阅 [`experiments/README.md`](experiments/README.md)。 需要 `mpmath` + `matplotlib`。 ### 常量表 / 性能分析 ``` sage scripts/generate_constants_fxp.sage # regenerate twiddle tables + 1/√q → fxp_constants_p*.py make profile # cProfile falcon_ref/profile_action.py → pyprof2calltree make clean # drop *.pyc / __pycache__ / *.cprof ``` ## 目录结构 ``` . ├── fxp/ core fxp package (Python) ├── falcon_ref/ Prest's falcon.py (MIT) + its self-test ├── experiments/ validation suite + precision benchmarks ├── scripts/ constant-table generators ├── tests/ unit tests + test vectors ├── pyproject.toml dependencies (uv / pip) ├── LICENSE └── README.md (this file) ``` ## 许可证 MIT —— 详见 [`LICENSE`](LICENSE)。`fxp/` 的贡献和 `falcon_ref/` 参考实现（Prest 的 `falcon.py`）版权归 Thomas Prest 所有， 基于 MIT 许可证发布。

标签：CVE, Falcon, Python, 后量子密码学, 安全规则引擎, 定点运算, 密码学, 手动系统调用, 数字签名, 无后门, 逆向工具