计算 FORS 签名

本文章翻译自David Ireland首次发表于Computing the FORS signature的原创文章, 强烈推荐有一定英文基础的小伙伴阅读原文。让我们回顾一下 FORS 签名的相关知识。FORS 是一种*有限次签名 (Few Time Signature, FTS)*方案其中我们有大量可能的私钥使得我们可以使用一次性签名 (one-time-signature) 结构用同一密钥签名少量消息而不会过多地损害安全性。FORS_sign 算法输入: 消息 M, 私钥 SK (SK.seed, SK.prf, PK.seed, PK.root), (可选) 额外随机数 addrnd 如果 addrnd 存在则 opt_rand addrnd 否则 opt_rand PK.seed 结束本示例的输入值D5213BA4BB6470F1B9EDA88CBC94E627 # SK.seed 7A58A951EF7F2B81461DBAC41B5A6B83 # SK.prf FA495FB834DEFEA7CC96A81309479135 # PK.seed A67029E90668C5A58B96E60111491F3D # PK.root 输入消息 [3 字节] M 00003F addrnd NULL # 使用确定性 (deterministic) 变体步骤 1 - 计算随机数R RR计算n nn字节的随机数R RR。R PRF_msg(SK.prf, opt_rand, M)其中SK.prf是私钥的一部分M是要签名的消息opt_rand是一个n nn字节的字符串在 hedged 模式下为额外随机数在确定性 (deterministic) 模式下为PK.seed的值。使用 SHA-256PRF_msg被定义为使用 HMAC-SHA-256以SK.prf为密钥。PRF_msg(SK.prf, opt_rand, M) HMAC-SHA-256(SK.prf, opt_rand || M) # 截断至 16 字节在本例中我们有SK.prf 7A58A951EF7F2B81461DBAC41B5A6B83 opt_randPK.seedFA495FB834DEFEA7CC96A81309479135 M00003F 因此 R BD40E6D66893F38D5C5FAD99E4885329这是签名的第一个 16 字节行。因此设置SIG R。注意这个随机数值R RR完全由 SLH-DSA 私钥和消息本身决定可能还有一些可选的随机材料。Python 代码fromslh_sha256importHMAC_SHA256# 使用十六进制字符串生成 16 字节的随机数 Rsk_prf7A58A951EF7F2B81461DBAC41B5A6B83optrandFA495FB834DEFEA7CC96A81309479135# - PK.seed 用于确定性模式msg00003F# M 输入内容 0x3F 前置两个零字节RHMAC_SHA256(sk_prf,optrandmsg)RR[:32]# 截断至 16 字节print(R ,R)# R BD40E6D66893F38D5C5FAD99E4885329步骤 2 - 计算H_msg我们根据消息 M、公钥和随机数 R 计算H_msg。对于 SHA-256我们使用来自 PKCS#1 的 MGF1 作为 XOF可扩展输出函数eXtendable Output Function。H_msg(R, PK.seed, PK.root, M, m) MGF1-SHA-256(R||PKseed||SHA-256(R||PKseed||PKroot||M), m)在我们的例子中我们需要m 34 m34m34字节的输出见下文。计算H msg H_{\text{msg}}Hmsg​的 Python 代码fromslh_sha256importSHA256,MGF1_SHA256 Rbd40e6d66893f38d5c5fad99e4885329PKseedFA495FB834DEFEA7CC96A81309479135PKrootA67029E90668C5A58B96E60111491F3Dmsg\00003Fm34hSHA256(RPKseedPKrootmsg)h_msgMGF1_SHA256(RPKseedh,m)print(H_msg:,h_msg)# cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072fcdcef4b8fdb03b028注意使用 SHA-256 推导H_msg的函数自 SPHINCS 3.0 版本的原始计算以来已有所变更。将H_msg拆分为消息摘要、树地址和叶子索引我们需要将H_msg拆分为一个md_bytes的消息摘要md、一个tree_bits的树地址和一个leaf_bits的叶子索引。我们在字节边界上进行拆分。对于我们的示例参数如下h 66 h66h66,d 22 d22d22,k 33 k33k33,a 6 a6a6,t 2 a 64 t2^a64t2a64计算所需长度的公式为m d _ b y t e s ⌈ k ⋅ a 8 ⌉ 25 \mathtt{md\_bytes}\left\lceil \dfrac{k\cdot a}{8} \right\rceil 25md_bytes⌈8k⋅a​⌉25字节t r e e _ b i t s h − h / d 66 − 66 / 22 63 \mathtt{tree\_bits}h - h/d 66 - 66/22 63tree_bitsh−h/d66−66/2263位因此t r e e _ b y t e s ⌈ t r e e _ b i t s 8 ⌉ 8 \mathtt{tree\_bytes}\left\lceil \dfrac{\mathtt{tree\_bits} }{8} \right\rceil 8tree_bytes⌈8tree_bits​⌉8字节l e a f _ b i t s h / d 66 / 22 3 \mathtt{leaf\_bits}h/d 66/22 3leaf_bitsh/d66/223位因此l e a f _ b y t e s ⌈ l e a f _ b i t s 8 ⌉ 1 \mathtt{leaf\_bytes}\left\lceil \dfrac{\mathtt{leaf\_bits} }{8} \right\rceil 1leaf_bytes⌈8leaf_bits​⌉1字节因此在本例中我们需要 25 字节给消息摘要 (md)、足够给 63 位树地址的字节数8 字节和一个 3 位叶子索引1 字节共计m 34 m34m34。将H_msg拆分为 md25 字节、树地址8 字节和叶子索引1 字节。H_msg cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072 fcdcef4b8fdb03b0 28 md cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072然后将树地址和叶子索引的字节字符串解码为无符号整数并分别截断为 63 位和 3 位。treeaddr 0xfcdcef4b8fdb03b0 0x7fffffffffffffff # 63 位 0x7cdcef4b8fdb03b0 idx_leaf 28 0x7 # 3 位 0x0计算 SIG_FORS输入: md, SK.seed, PK.seed, ADRS将 25 字节的md解释为 33 个× \times×6 位 (k × a k\times ak×a位) 的无符号整数使用 base_2b ^bb算法。md cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072 索引 (十进制): 50 47 49 35 39 21 57 21 02 00 31 56 18 58 58 31 31 43 35 26 08 07 31 13 21 57 63 20 33 05 08 32 28这 33 个索引中的每一个都给出了k 33 k33k33个 FORS 树中每个树的一个私钥的索引0-63。第一个索引十进制值 50选择第 1 棵树中的第 50 个私钥第二个索引值 47选择第 2 棵树中的第 47 个密钥……最后第 33 个索引值 28选择第 33 棵树中的第 28 个密钥。这k 33 k33k33个私钥在签名中揭示出来连同它们的认证路径 (authentication paths)。计算索引的 Python 代码defbase_2_b(X,b,out_len):# 算法 4: base_2^b(X, b, out_len)# 计算 X 的 base 2^b 表示# 输入:# 字节串 X, 整数 b, 输出长度 out_len.two_to_b1b# 2^bbaseb[0]*out_len i0bits0total0foroutinrange(out_len):whilebitsb:total(total8)X[i]ii1bitsbits8bitsbits-b baseb[out](totalbits)(two_to_b-1)# mod 2^btotal(two_to_b-1)returnbaseb Xbytes.fromhex(cafc639d5e550807f84bae9f7eb8da2077cd579fd484522072)print(fX{X.hex()})indiciesbase_2_b(X,6,33)print(indicies:\n,[mforminindicies])# [50, 47, 49, 35, 39, 21, 57, 21, 2, 0, 31,# 56, 18, 58, 58, 31, 31, 43, 35, 26, 8, 7,# 31, 13, 21, 57, 63, 20, 33, 5, 8, 32, 28]计算第一个 FORS 私钥ADRS 的tree_index部分计算如下t r e e _ i n d e x i ⋅ t indices [ i ] \mathtt{tree\_index} i\cdot t \text{indices}[i]tree_indexi⋅tindices[i]其中i 0 , … , k − 1 i 0,\ldots, k-1i0,…,k−1k 33 k33k33且t 2 a 64 t2^a64t2a64。对于第一棵树i 0 i0i0我们有索引 50得到tree_index 0*64 50 50 0x32FORS 私钥通过以下方式计算sk PRF(PK.seed, SK.seed, ADRS)其中 ADRS 使用类型 6 (FORS_PRF) 构造。我们在层 0、树高 0叶子索引密钥对地址为 0tree_index 为 0x32。在 SHA-2 压缩形式ADRS_c中表示为layer treeaddr type idxleaf tree ht treeindex [1] [8] [1] [4] [4] [4] 00 7cdcef4b8fdb03b0 06 00000000 00000000 00000032 ^^注意我们的示例中idxleaf0但如果它不为零则会显示在上面标记为^^的字节中。私钥值使用PRF函数计算sk PRF(PK.seed, SK.seed, ADRS) SHA-256(PK.seed || toByte(0, 64 − n) || ADRS_c || SK.seed)[n] SHA256(FA495FB834DEFEA7CC96A81309479135 000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000 007cdcef4b8fdb03b006000000000000000000000032 D5213BA4BB6470F1B9EDA88CBC94E627)[:32] 925bb207d49e62bcb9b1c4685154a8b3因此签名中揭示的第一个 FORS 私钥值为925bb207d49e62bcb9b1c4685154a8b3 # fors_sig_sk[0]设置SIG SIG || fors_sig_sk[0]其后是从私钥到 FORS 树根经过a 6 a6a6层的6 n 6n6n字节 FORS 认证路径。见下文。第一个认证路径认证路径使用T r e e H a s h \mathsf{TreeHash}TreeHash算法计算详见Merkle 树的认证路径。使用相同的原理但我们使用特定的 SLH-DSA 哈希函数F ( ) F()F()和H ( ) H()H()这两个函数都接受一个 ADRS 参数且每次使用时该参数都不同在高度 0 的基底层使用p k F ( s k ) pk F(sk)pkF(sk)计算公钥p k pkpk其中 FORS 私钥s k sksk如上计算然后使用H ( l e f t ∣ ∣ r i g h t ) H(left||right)H(left∣∣right)计算父节点其中哈希函数H ( ) H()H()每次使用不同的 ADRS 参数。每个树的根也会被计算并存储在一个列表中供后续使用。在我们的示例中第一个公钥由上面计算出的私钥通过 F 哈希函数推导得出使用类型 3 地址 (FORS_TREE)ADRS 007cdcef4b8fdb03b003000000000000000000000032 ^^ sk PRF(PK.seed, SK.seed, ADRS) 925bb207d49e62bcb9b1c4685154a8b3 pk F(PK.seed, ADRS, sk) 81a7b89d408f2f91d81e9303d77b49c6TreeHash 算法所需的所有其他叶子节点p k pkpk值都以相同方式推导。本例中第一个私钥的认证路径结果为2e58b70c7aed0e28507f31b49ec7ed6e # fors_auth_path[0] d6dcb8db2da90fe938994d75c80e6712 f2421c22def8af88906b768333e7ebf6 ddf7b84dc01f06731dd640cf93f57927 bb56f9da9d4b2abe60c81d863a20f8e5 c5cce74326d6181d01b74e3cd7f794a9此 FORS 树的根值为root[0]fb0f55d9717066cf3c666854d1e2f928不是签名的一部分但存储下来供后续计算 FORS 公钥使用。设置SIG SIG || fors_auth_path[0]我们可以演示如何开始计算第一个 FORS 树的认证路径其中索引为 50。下图显示了树的相关部分为简洁起见16 字节的节点值缩写为 3 字节。私钥值从私钥及其类型 6 地址 (FORS_PRF) 确定性地计算得出sk PRF(PK.seed, SK.seed, ADRS)sk[48]06d6bddd89f5d5815063ca395e9b963d sk[49]ac6e9f1dc2226ed1cb2f86e3872f3fe0 sk[50]925bb207d49e62bcb9b1c4685154a8b3 #fors_sig_sk[0] sk[51]c7005085cda77e80444a44480c67d454对应的公钥高度 0 的节点使用 F 和类型 3 地址 (FORS_TREE) 计算pk F(PK.seed, ADRS, sk)adrs_c007cdcef4b8fdb03b003000000000000000000000030 # 480x40 pk[48]631195810d16cd1cf504d77e747317c7 adrs_c007cdcef4b8fdb03b003000000000000000000000031 # 490x31 pk[49]392e83145264282b3f728af62cd8fad8 adrs_c007cdcef4b8fdb03b003000000000000000000000032 # 500x32 pk[50]81a7b89d408f2f91d81e9303d77b49c6 adrs_c007cdcef4b8fdb03b003000000000000000000000033 # 510x33 pk[51]2e58b70c7aed0e28507f31b49ec7ed6e父节点使用H HH函数计算adrs_c 007cdcef4b8fdb03b003000000000000000100000018 # 24 node[24]H(PKseed, adrs_c, pk[48], pk[49]) d6dcb8db2da90fe938994d75c80e6712 adrs_c 007cdcef4b8fdb03b003000000000000000100000019 # 25 node[25]H(PKseed, adrs_c, pk[50], pk[51]) 2364eb5855b474c27760b3933e0f911f adrs_c 007cdcef4b8fdb03b00300000000000000020000000c # 12 node[12]H(PKseed, adrs_c, node[24], node[25]) 086fe170a5e4a56e952077e676cd4484此过程重复直至树的根记录所需的认证路径值并保存根值。Python 代码以下是一些使用硬编码 ADRS 值来重现上述值的 Python 代码。fromslh_sha256importPRF,SHA256,F,H SKseedD5213BA4BB6470F1B9EDA88CBC94E627PKseedFA495FB834DEFEA7CC96A81309479135# 计算 i 48 到 51 的 sk[i], pk[i]# 用于计算 sk 的 ADRS 类型为 6 (FORS_PRF)# 层 0, 树高 0, 叶子索引 0, tree index 48-51adrs_c007cdcef4b8fdb03b006000000000000000000000030# 480x30skPRF(PKseed,SKseed,adrs_c)print(fsk[48]{sk})# 06d6bddd89f5d5815063ca395e9b963d# 用于计算 pk 的 ADRS 类型为 3 (FORS_TREE)adrs_c007cdcef4b8fdb03b003000000000000000000000030pk_48F(PKseed,adrs_c,sk)print(fpk[48]{pk_48})# 631195810d16cd1cf504d77e747317c7adrs_c007cdcef4b8fdb03b006000000000000000000000031# 490x31skPRF(PKseed,SKseed,adrs_c)print(fsk[49]{sk})# ac6e9f1dc2226ed1cb2f86e3872f3fe0adrs_c007cdcef4b8fdb03b003000000000000000000000031pk_49F(PKseed,adrs_c,sk)print(fpk[49]{pk_49})# 392e83145264282b3f728af62cd8fad8adrs_c007cdcef4b8fdb03b006000000000000000000000032# 500x32skPRF(PKseed,SKseed,adrs_c)print(fsk[50]{sk})# 925bb207d49e62bcb9b1c4685154a8b3adrs_c007cdcef4b8fdb03b003000000000000000000000032pk_50F(PKseed,adrs_c,sk)print(fpk[50]{pk_50})# 81a7b89d408f2f91d81e9303d77b49c6adrs_c007cdcef4b8fdb03b006000000000000000000000033# 510x33skPRF(PKseed,SKseed,adrs_c)print(fsk[51]{sk})# c7005085cda77e80444a44480c67d454adrs_c007cdcef4b8fdb03b003000000000000000000000033pk_51F(PKseed,adrs_c,sk)print(fpk[51]{pk_51})# 2e58b70c7aed0e28507f31b49ec7ed6e# 计算认证路径所需的值# node H(left||right)# ADRS 类型 3 (FORS_TREE) 树高1, 树索引240x18adrs_c007cdcef4b8fdb03b003000000000000000100000018# 24node_24H(PKseed,adrs_c,pk_48,pk_49)print(fnode[24]{node_24})# d6dcb8db2da90fe938994d75c80e6712adrs_c007cdcef4b8fdb03b003000000000000000100000019# 25node_25H(PKseed,adrs_c,pk_50,pk_51)print(fnode[25]{node_25})# 2364eb5855b474c27760b3933e0f911f# 树高2 树索引12adrs_c007cdcef4b8fdb03b00300000000000000020000000c# 12node_12H(PKseed,adrs_c,node_24,node_25)print(fnode[12]{node_12})# 086fe170a5e4a56e952077e676cd4484计算其余的 FORS 签名 (i 1 , … , 32 i1,\ldots, 32i1,…,32)对于第 2 个密钥 (i 1 i1i1)我们有索引 47得到tree_index 1*64 47 111 0x6fADRS 更新为ADRS_c 00 7cdcef4b8fdb03b0 06 00000000 00000000 0000006f sk PRF(PK.seed, SK.seed, ADRS_c) 8b4ed7a791a1b77c561a6e7ae64e4e17因此8b4ed7a791a1b77c561a6e7ae64e4e17 # fors_sig_sk[1]认证路径单独计算为481de4ce7e26065d90ae21c965feba33 # fors_auth_path[1] 02102d7564e3b7414e1aa62271e9b4df b42c57c44726af6fe7f3bdd486d7d578 b4b4ba8ebc1f5d7243f94d2d2d4cb55b 7f95c3020e05a6ccbe12cbdffd6466b5 b34369fa56839a0e05af5c6613e4a229树根值为root[1]34c0d2ad1439f436a03efb94c1ce92dc将用于后续计算 FORS 公钥设置SIG SIG || fors_sig_sk[1] || fors_auth_path[1]此过程对所有k kk棵树重复得到 33 个 FORS 签名值和认证路径序列。第 33 个也是最后一个 FORS 签名 (i 32 i32i32) 计算如下我们有索引 28得到tree_index 32*64 28 2076 0x81cADRS_c 00 7cdcef4b8fdb03b0 06 00000000 00000000 0000081c sk PRF(PK.seed, SK.seed, ADRS_c) 2b38f096578c9a974ac0ce9a28d92351因此2b38f096578c9a974ac0ce9a28d92351 # fors_sig_sk[32]认证路径为5c1fd369cda5f3fa35e7358efdb91a07 # fors_auth_path[32] 71f3daa64e685f5e24bc819c93486b28 71fe59a0a2749a15bcfe36c4ab4ac2ed 4803015faf8bd4c309ee883d4f58131f 778fbb608f07c3fb62e588cc47902b6a 0c646676640ab0ee1b342537e9376ce5此树的根值为root[32]df3658bc1eaafcf157b2485e924b39ef。设置SIG SIG || fors_sig_sk[i] || fors_auth_path[i]对于i 2 , … , 33 i2,\ldots, 33i2,…,33我们现在有了FORS_SIG它由k kk个n nn字节的私钥和k kk个a ⋅ n a \cdot na⋅n字节的认证路径组成。此外我们还存储了k kk个n nn字节的根值到一个列表中。压缩树根值以形成 FORS 公钥我们为k 33 k33k33棵树中的每一棵存储了 33 个n nn字节的根值。它们是roots fb0f55d9717066cf3c666854d1e2f928 34c0d2ad1439f436a03efb94c1ce92dc 6df0754919401d2f9a6a9d0143483178 b72f2d742429d2b014e4d9b0f6908589 acbaddfc1bbea958690b47b54da5437f 3f5529c3812ce9fe4b3a8ef4cc7ebf1d 76b0e70df7d9ac867186906a6a623188 a20c75e80be927d2256cab3092782e1a 4846ed7e0710391d31081175ab37af8a 4a4be9954a695b4255d1d459dcc0f14a db43fe896787ea1dca4e91297f9ed053 ae0a12a089f7155af337e6ffaed8f234 22342fe15d5449b797268dfeeb0baa80 e9abce61c3b44b3914f1ec0d296dc520 b776498d75b925f09cc6d4c67c67eecf b124ead4ccf45a5f53a3335dd4399289 e755365d8d8b69bc57167580a527c2fa