本日重點：簽章的演算法和 message randomizer

FIPS 205 第 34 頁 [1] 是簽章的格式，今天的重點是產生它的主要流程

參考 Table 2，因為本系列要實作的演算法是 SLH-DSA-SHA2-128s，所以我們可以先這樣指定

n = 16
k = 14
a = 12
h = 63
d = 7 

len 的計算可以看第 17 頁，𝑙𝑒𝑛 = 2𝑛 + 3，也就是 35。所以 FORS signature 是 2,912 bytes (14 * 13 * 16)，HT signature 是 4,928 bytes ( (63 + 7 * 35) * 16 )。

FIPS 205 第 35 頁 [1] 是簽章的演算法

簡單來說，主要有 6 步

1. PRF_msg 產生亂數，此為 Randomness R
2. R 用來產生 digest，digest 用來產生 md
3. md 做為 fors_sign 的 input，並由 fors_sign 產生 FORS signature sig_fors
4. sig_fors 做為 fors_pk_from_sig 的 input，並由 fors_pk_from_sig 產生 pk_fors
5. pk_fors 做為 ht_sign 的 input，並由 ht_sign 產生 HT signature sig_ht
6. 最後 R, sig_fors, sig_ht 合併, 即為最後簽章的結果。

我們先把視角放在 PRF_msg 和 addrnd。PRF_msg 是一個 message randomizer，他有兩種變體，一為 hedged，一為 deterministic，取決於有沒有提供 addrnd。

如 FIPS 205 第 36 頁所言，如果有提供 addrnd，它就必須是一個 n bytes 的亂數。在理想的情況下，應該是由 approved random bit generator 所產生。也就是說，是由符合 800-90A/B/C 規範的 RBG 所產生。

While 𝑎𝑑𝑑𝑟𝑛𝑑 should ideally be generated by an approved random bit generator

hedged 變體藉由增加一個額外的亂數，對於防止 side-channel attacks 能發揮一定程度的防禦效果。

另一種變體是 deterministic，在這種變體，addrnd 不用提供，只要照 Algorithm 19 的第 2 行所述，直接把 PK.seed 的值給 opt_rand 就可以了。

substitute 𝑜𝑝𝑡_𝑟𝑎𝑛𝑑 ← PK.seed for the deterministic variant

今天我們把重點放在 addrnd 和 PRF_msg，明天將陸續探討 digest 的產生、fors_sign、fors_pk_from_sig 和 ht_sign。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard
2. SPHINCS+ – Submission to the 3rd round of the NIST post-quantum project. v3.1
3. The SPHINCS+ reference code, accompanying the submission to NIST's Post-Quantum Cryptography project