本日重點: 總結 fors_sign

在 Day 8 我們完成了 fors_sk_gen 和 fors_node，今天我們把焦點放在 line 2 的 base_2b 和 line 5 ~ 8 的 authentication path

base_2b 的演算法在第 16 頁

b 在 FORS 就是 Table 2. SLH-DSA parameter sets 的 a，就是 6、8、9、12、14，本系列講的是 SLH-DSA-SHA2-128s，所以 a 我們用 12

如 algorithm 4 所示，base_2b 的輸出就是一個陣列，每一個元素都是整數，這個整數的範圍在 [0, 2^b-1]，2^12-1 = 4095，所以，當 parameter sets 是 SLH-DSA-SHA2-128s，base_2b 就輸出就是一個 整數的陣列，每一個整數的範圍是 0 ~ 4095。

照著 algorithm 4 base_2b 的演算法一行一行寫, 程式大概是這樣

for(int out = 0; out < out_len; out++)
{
    while(bits < b)
    {
        total = (total << 8) + pX[in];
        in++;
        bits += 8;
    }

    // bits = bits - b
    bits -= b;

    // baseb[out] = (total ≫ bits) mod 2^b
    baseb[out] = (total >> bits) & ((1u << b) - 1u);
}

在無號數的運算，x mod 2^y ≡ x & (2^y−1)，所以
(total ≫ bits) mod 2^b 可以寫成 (total >> bits) & ((1u << b) - 1u)

authentication path AUTH 是一個長度為 a 的陣列，整個陣列 的大小是 𝑎 ⋅ 𝑛 bytes，在 FORS signature 裡，這樣的 AUTH 有 k 個

在 algorithm 16 的演算法裡，從這 3 行能看出來 AUTH 有 k 個 (每一個 AUTH 都是 length a 的 array)

for i from 0 to k - 1 do
    ...
    for j from 0 to a - 1 do
        AUTH[j] <- fors_node(...)

fors_sign 就剩下 ⌊𝑖𝑛𝑑𝑖𝑐𝑒𝑠[𝑖]/2𝑗⌋ ⊕ 1 了，FIPS 205 第 5 頁 對此有說明

⊕ 是 bitwise exclusive-or
⌊ ⌋ 是 floor, 舉例來說 ⌊5.3⌋ = 5, ⌊-2.1⌋ = -3

我們總結一下 fors_sign 有幾個主要的步驟

1. base_2b 算出來一個 array 𝑖𝑛𝑑𝑖𝑐𝑒𝑠
2. 𝑖𝑛𝑑𝑖𝑐𝑒𝑠 的 element 具有 index 的意義，它能用來算出 tree index
3. tree index 和公私鑰的種子能算出 FORS private-key，它是 FORS signature 的一部份
4. tree index 和公私鑰的種子能計算 root of a Merkle subtree，它是 authentication path AUTH 的其中一個元素，每一個 AUTH 的長度是 a
5. 算出 authentication path AUTH 的每一個 element，此即為一個 AUTH
6. 這一個 AUTH 也是 FORS signature 的一部份，而 這樣的 AUTH 有 k 個
7. 於是 FORS private-key 有 k 個，AUTH 也有 k 個

明天我們會開始探討 WOTS+ signature 和 XMSS Signature。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard
2. https://sphincs.org/index.html
3. The SPHINCS+ reference code, accompanying the submission to NIST's Post-Quantum Cryptography project