文章总结： 本文档详细介绍了Falcon-MRM消息恢复模式算法的代码实现，作者基于FALCON参考实现阐述了参数定义、签名与验证流程、哈希函数设计及消息编解码细节。文章填补了论文未提供代码的空白，指出了签名长度处理等具体问题的解决方案，并开源代码供学习参考，同时提醒未进行侧信道安全审计，仅供学习使用。 综合评分： 94 文章分类： 安全开发,实战经验,安全工具
【密码学】Falcon-MRM 代码实现
原创
Litt1eQ Litt1eQ
Coder小Q
2026年3月5日 08:31 山东
【密码学】Falcon-MRM 代码实现
这里，好久没有写代码了，上一篇文章刚讲解了 Falcon-MRM[1,2]，因为我并没有找到原始的实现，那么这里我就来自己实现一下吧，这里基于原始的 Falcon的参考实现[3]上来进行简单的修改，就可以得到这个的实现，但是这块在实现过程当中，实际上是存在一些小问题的，在论文当中并没有给出确切的说法，这里我是根据我自己的理解来实现的，如果有错误，也欢迎读者和我交流。
参数定义
这里，我们只来实现， logn = 9（FALCON-512）和 logn = 10（FALCON-1024）的相关参数。
FALCON_MRM_LAMBDA(logn) // λ：H1 输出长度，9→19，10→38
FALCON_MRM_GAMMA(logn) // γ：盐的长度，9→15，10→24
FALCON_MRM_M1_COEFFS(logn) // k = n - λ - γ，可恢复消息的系数数量
FALCON_MRM_ENCODED_BITS(logn) // B(k)：k 个 Zq 元素能编码的最大比特数
FALCON_MRM_SIG_MAXSIZE(logn) // 签名缓冲区的最大尺寸（分配缓冲区必须用这个）
FALCON_MRM_SIG_SIZE(logn) // 论文 Table 1 的理论参考值，不用于分配缓冲区
这里，需要注意一下，我们不能用理论值，也就是 FALCON_MRM_SIG_SIZE，我们要用 FALCON_MRM_SIG_MAXSIZE，对于具体原因，我们后续再来聊。
公开 API
这里，我们来定义一下公开的 API，分别是签名，验证并恢复 ，比特串和的转换这四个函数。
// 签名
int falcon_mrm_sign_dyn(shake256_context *rng,
void *sig, size_t *sig_len,
const void *privkey, size_t privkey_len,
const uint16_t *m1, size_t m1_len,
const void *m2, size_t m2_len,
void *tmp, size_t tmp_len);
// 验证并恢复 M1
int falcon_mrm_verify(const void *sig, size_t sig_len,
const void *pubkey, size_t pubkey_len,
const void *m2, size_t m2_len,
uint16_t *m1_out, size_t m1_out_len,
void *tmp, size_t tmp_len);
// 比特串 → Zq 向量
int falcon_mrm_encode_bits(uint16_t *m1, size_t m1_len,
const void *msg_bits, size_t msg_bit_len, unsigned logn);
// Zq 向量 → 比特串
int falcon_mrm_decode_bits(void *msg_bits, size_t msg_bit_len,
const uint16_t *m1, size_t m1_len, unsigned logn);
签名实现
这里，我们可以分为三个阶段，分别为
参数检查与私钥解码
首先从私钥头字节读取 logn，调用 mrm_get_params 获取 λ、γ、k，然后检查 m1 长度必须恰好等于 k，并逐元素验证 m1[i] < 12289。
私钥解码与原始 falcon_sign_dyn_finish 完全一致：用 Zf(trim_i8_decode) 依次解出 f、g、F，再用 Zf(complete_private) 算出 G。
这里，我们需要多一步——计算公钥多项式 h 并转为 NTT+Montgomery 形式：
Zf(compute_public)(h_ntt, f, g, logn, atmp);
Zf(to_ntt_monty)(h_ntt, logn);
原始签名不需要这一步，因为 s1 不输出。MRM 需要明文输出 s1，而 s1 = c - s2·h，所以必须先把 h 算好备用。
签名过程
for (;;) {
// 1. 采样随机盐 ρ ∈ Z_q^γ
mrm_sample_zq(rng, rho, gamma);
// 2. 计算目标点 c = (c1, c2)
mrm_hash_h1(c, lambda, logn, rho, gamma, m1, k, m2, m2_len);
mrm_hash_h2(c + lambda, n - lambda, logn, c, lambda);
for (u = 0; u < gamma; u++)
c[lambda + u] = mrm_add_modq(c[lambda + u], rho[u]);
for (u = 0; u < k; u++)
c[lambda + gamma + u] = mrm_add_modq(c[lambda + gamma + u], m1[u]);
// 3. 调用原始 FALCON 陷门采样，得到 s2
Zf(sign_dyn)(s2_buf, rng, f, g, F, G, c, logn, atmp);
// 4. 显式计算 s1 = c - s2·h
Zf(compute_s1)(s1_buf, c, s2_buf, h_ntt, logn, atmp);
// 5. 尝试编码：s1 用 compressed，s2 用 padded；s2 过长则重试
s1_len = Zf(comp_encode)(NULL, 0, s1_buf, logn); // 预测长度
if (s1_len == 0) continue;
Zf(comp_encode)(es + 3, s1_len, s1_buf, logn);
if (!mrm_encode_padded_comp(es + 3 + s1_len, part2_len, s2_buf, logn))
continue;
break;
}
注意，这里，Zf(sign_dyn) 是原始 FALCON 的陷门采样，它内部已经保证了 ‖(s1_内部, s2)‖ ≤ β，因此，我这可以直接用。s2 需要编码为 padded 固定大小格式，如果某次采样出的 s2 压缩后超出 padded 上限，就丢弃这次结果重新循环（概率很低），这块论文里面也是没有的，但是应该是有概率的。
序列化
签名的字节布局：
[1 字节] header = 0x70 + logn
[2 字节] s1 的 compressed 长度（大端）
[s1_len 字节] compressed s1
[part2_len 字节] padded s2，长度固定 = FALCON_SIG_PADDED_SIZE(logn) - 41
Header 高 4 位取 0x7，区别于原始 FALCON 的 0x3（compressed/padded）和 0x5（CT）。因为 s1 长度可变，用 2 字节长度前缀告知解析方 s1 结束的位置，s2 紧随其后且长度固定，不需要第二个长度字段。
FALCON_MRM_SIG_MAXSIZE 的计算正是基于这个格式：
#define FALCON_MRM_SIG_MAXSIZE(logn) \
(3u + (FALCON_SIG_COMPRESSED_MAXSIZE(logn) - 41u) \
+ (FALCON_SIG_PADDED_SIZE(logn) - 41u))
而 FALCON_MRM_SIG_SIZE 对应论文 Table 1 中两个 padded 多项式的理论值，这里，我们采用变长的方式来处理，这块和论文的固定值有一些差异，这块使用变长来说，所生成的长度更小。
验证过程
对于验证过程，其实就比较简单了，这里核心在于消息的恢复
解析签名
从 es[1]、es[2] 读取 s1_len，验证 sig_len == 3 + s1_len + part2_len。然后分别用 Zf(comp_decode) 解 s1，mrm_decode_padded_comp 解 s2——后者在解码完成后还会检查 padded 区域的剩余字节是否全为零，不满足则拒绝。
范数检查
if (!Zf(is_short)(s1, s2, logn)) return FALCON_ERR_BADSIG;
这块，和原始算法一致，没啥改动。
计算 c 并恢复消息
// c = s1 + s2·h，结果写回 h 数组
Zf(compute_c0)(h, s1, s2, h, logn, atmp);
// h2 = H2(c1)，复用 s2 的缓冲区节省内存
h2 = (uint16_t *)s2;
mrm_hash_h2(h2, n - lambda, logn, h, lambda);
// (ρ, M1) = c2 - H2(c1) mod q
for (u = 0; u < gamma; u++)
rho[u] = mrm_sub_modq(h[lambda + u], h2[u]);
for (u = 0; u < k; u++)
m1_out[u] = mrm_sub_modq(h[lambda + gamma + u], h2[gamma + u]);
一致性校验
mrm_hash_h1(c1_check, lambda, logn, rho, gamma, m1_out, k, m2, m2_len);
for (u = 0; u < lambda; u++)
if (c1_check[u] != h[u]) return FALCON_ERR_BADSIG;
重新用恢复出的 (ρ, M1, M2) 算一遍 H1，与 c 的前 λ 个系数比对。一致则验签通过，m1_out 即为恢复的消息向量。
哈希函数的实现
这里，我们需要用到和，直接沿用 Falcon 的方式，采用 SHAKE256 来实现，这里需要注意我们要区分这俩随机语言机，这俩按理说，不能出现碰撞，因此这里我们需要引入域分隔的方式。
域分隔
每个函数各有一个固定的 ASCII 标签和一个 logn 字节，吸收顺序如下：
| 函数 | 吸收内容（顺序） |
| — | — |
| H1 | "FALCON-MRM-H1" (13 B) + logn (1 B) + Enc14(ρ) + Enc14(M1) + M2 (原始字节) |
| H2 | "FALCON-MRM-H2" (13 B) + logn (1 B) + Enc14(c1) |
论文未规定域分隔标签的具体内容，但是这块是必须的，如果要使用，签名者和验证者需要保持一致。
Zq 元素的编码注入
这里，将 Zq 向量注入 SHAKE256 时，每个元素用 14 位大端整数表示，多元素的 14 位串拼接后按 8 位打包成字节（最后一字节低位补零）。若任何元素 ≥ 12289，函数返回 0 表示错误。
从 SHAKE256 输出采样 Zq
两个函数逻辑完全相同，区别仅在于输入来源：mrm_hash_to_zq 从已进入输出模式的 SHAKE256 上下文读取，mrm_sample_zq 从外部 RNG 读取。实现方式是拒绝采样：每次读 2 字节，若值 w < 61445（即 5 × 12289）则接受 w mod 12289，否则丢弃重取。阈值 61445 保证均匀分布。
消息解码的实现
编码
将长度恰好为 B(k) = 163×⌊k/12⌋ + 27×⌊(k mod 12)/2⌋ 位的比特串编码为 k 个 Zq 元素。分两段处理：
163 位块（每块生成 12 个 Zq 元素）：
mrm_read_bits_u192(x, src, i, 163); // 读 163 位为 192 位大端整数（3×uint64_t）
for (t = 0; t < 12; t++)
m1[j + t] = (uint16_t)mrm_u192_div_small(x, FALCON_Q); // 连除取余
mrm_u192_div_small 对 3 个 64 位肢进行大端除法，借助 __uint128_t 避免溢出。每次除法的余数就是一个 Zq 系数（低次在前），商继续参与下一次除法。
27 位块（每块生成 2 个 Zq 元素）：
x = (big-endian 27 位整数);
m1[j + 0] = x % FALCON_Q;
m1[j + 1] = x / FALCON_Q;
函数末尾检查 i == msg_bit_len && j == k，两者必须同时消耗完。
解码
逆过程。用 mrm_u192_muladd_small（即 x = x × q + z，Horner 展开）从高位到低位重建 192 位整数，再调用 mrm_write_bits_u192 写回比特串。
解码附带范围检查：
- 163 位块：若重建的整数
≥ 2^163（即x[2] >> 35 != 0），返回FALCON_ERR_FORMAT。 - 27 位块：若
m1[j] + q × m1[j+1] ≥ 2^27，返回FALCON_ERR_FORMAT。
这两项检查确保解码结果唯一。
辅助函数
这里，我们需要用到两个辅助函数来支持辅助实现 Falcon-MRM，具体如下。
// 签名方用：s1 = c0 - s2·h mod q，结果中心化到 [-q/2, q/2]
void Zf(compute_s1)(int16_t *s1, const uint16_t *c0,
const int16_t *s2, const uint16_t *h, unsigned logn, uint8_t *tmp);
// 验证方用：c0 = s1 + s2·h mod q
void Zf(compute_c0)(uint16_t *c0, const int16_t *s1,
const int16_t *s2, const uint16_t *h, unsigned logn, uint8_t *tmp);
两个函数都通过 NTT 多项式乘法实现，h 传入时为普通 Zq 表示（函数内部转 NTT）。compute_s1 的结果会中心化（将 Zq 上的值映射到有符号整数），以便后续的 is_short 范数检查。
验证函数中有一处内存复用优化：在 compute_c0 之后，s2 的缓冲区不再需要，直接被 H2 的输出覆盖，节省了一次额外分配：
Zf(compute_c0)(h, s1, s2, h, logn, atmp);
h2 = (uint16_t *)s2; // 复用 s2 缓冲区
mrm_hash_h2(h2, n - lambda, logn, h, lambda);
总结
这个实现的完整代码[4]，已经开源，大家可以自行看一下，这一块如果要用在生产，需要自己审计一下，仅保证实现正确性，未考虑侧信道攻击等其他攻击的方式，仅供学习参考使用。好了，快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见。
参考资料
[1] Litt1eQ. “【密码学】FALCON 消息恢复模式算法解读”. https://mp.weixin.qq.com/s/7jHIs7ibZljFQuvdPGQa4g
[2] Felix Günther, Vadim Lyubashevsky, and Rolfe Schmidt. “FALCON with message recovery, a specification”. IACR Cryptology ePrint Archive, Report 2026/420, 2026. https://eprint.iacr.org/2026/420
[3] T. Prest, et al. “FALCON: Fast-Fourier Lattice-based Compact Signatures over NTRU”. Technical report, 2017. https://falcon-sign.info/
[4] Litt1eQ. “Falcon-MRM Implementation”. GitHub repository. https://github.com/Litt1eQ/Falcon-MRM
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：Coder小Q Litt1eQ Litt1eQ《【密码学】Falcon-MRM 代码实现》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论