本日重點: fors_node、fors_sk_gen

fors_node 現在只剩下 fors_sk_gen 要完成

這裡有一個地方要注意，如 FIPS 205 第 30 頁 [1] 所述，target node height z 跟 target node index i 必須要滿足兩個條件。

The target node height and index must satisfy 𝑧 ≤ 𝑎 and 𝑖 < 𝑘 ⋅ (2^(𝑎−𝑧)).

fors_sk_gen 的演算法在 FIPS 205 第 29 頁 [1]，只要複製 ADRS，然後 call 三個 ADRS 的 member function，最後 call PRF 計算 secret value，就結束了。

如 FIPS 205 第 11 頁 [1]所述，PRF 的定義是這樣的，他是用來計算 secret value，在 fors_sk_gen 算出來的就是 FORS private key

PRF 演算法在 FIPS 205 第 46 頁 [1]

PRF(PK.seed, SK.seed, ADRS) =
Trunc𝑛(SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ SK.seed))

PRF 的程式大概像這樣

int size = 64 + 22 + SPX_N;  // ADRS_c is an array which length is 22
unsigned char combined[size];
memcpy(combined, pk_seed, SPX_N);
memset(combined + SPX_N, 0, (64 - SPX_N));   // toByte(0, 64 − 𝑛) => (64 − 𝑛) 個 bytes 都是 0

uint8_t adrs_c[22];
compress_adrs(adrs_c, adrs);   // ADRS convert to compressed ADRS (ADRSc)

// PK.seed ∥ toByte(0, 64 − n) ∥ ADRS_c
memcpy(combined + 64, adrs_c, sizeof(adrs_c));

// PK.seed ∥ toByte(0, 64 − n) ∥ ADRS_c ∥ SK.seed
memcpy(combined + 64 + sizeof(adrs_c), sk_seed, SPX_N);

// SHA-256(PK.seed ∥ toByte(0, 64 − n) ∥ ADRS_c ∥ SK.seed)
uint8_t out32[32];
sha256(combined, sizeof(combined), out32);

// Trunc_n(SHA-256(PK.seed ∥ toByte(0, 64 − n) ∥ ADRS_c ∥ SK.seed))
memcpy(out, out32, SPX_N);

SPX_N 是 n，在本系列 n 都是 16，第 3 ~ 13 行就是單純的把 PK.seed ∥ toByte(0, 64 − n) ∥ ADRS_c ∥ SK.seed 陸續存進 combined 這個 array，最後兩行就是先 sha256，然後取最左邊的 16 個 bytes。

至此，fors_sk_gen 的程式大概像這樣

// skADRS ← ADRS ▷ copy address to create key generation address
ADRS skADRS;
memcpy(skADRS, adrs, 32);   // ADRS  = 32 bytes

// skADRS.setTypeAndClear(FORS_PRF)
set_type_and_clear(adrs, FORS_PRF);

// skADRS.setKeyPairAddress(ADRS.getKeyPairAddress())
set_key_pair_addr(skADRS, get_key_pair_addr(adrs));

// skADRS.setTreeIndex(idx)
set_tree_index(skADRS, idx);

// PRF(PK.seed, SK.seed, skADRS)
prf(pk_seed, sk_seed, skADRS, out);

fors_node 需要 call 三個 function fors_sk_gen、F 和 H，其中F、H 在 Day 7 已經完成，今天又完成了fors_sk_gen。

fors_node 的程式大概像這樣，其中 z 是 target node height，SPX_N 是 16

if (z == 0)
{
    // 2: 𝑠𝑘 ← fors_skGen(SK.seed, PK.seed, ADRS, 𝑖)
    uint8_t sk[SPX_N];
    fors_sk_gen(sk, sk_seed, pk_seed, adrs, i);

    // 3: ADRS.setTreeHeight(0)
    set_tree_height(adrs, 0);

    // 4: ADRS.setTreeIndex(𝑖)
    set_tree_index(adrs, i);

    // 5: 𝑛𝑜𝑑𝑒 ← F(PK.seed, ADRS, 𝑠𝑘)
    F(pk_seed, adrs, sk, out);
}
else
{
    uint8_t lnode[SPX_N];
    fors_node(lnode, sk_seed, 2*i, z - 1, pk_seed, adrs);

    uint8_t rnode[SPX_N];
    fors_node(rnode, sk_seed, 2*i + 1, z - 1, pk_seed, adrs);

    // 9:   ADRS.setTreeHeight(𝑧)
    set_tree_height(adrs, z);
    // 10:  ADRS.setTreeIndex(𝑖)
    set_tree_index(adrs, i);

    uint8_t l_add_r[2*SPX_N];
    // 11:  𝑛𝑜𝑑𝑒 ← H(PK.seed, ADRS, 𝑙𝑛𝑜𝑑𝑒 ∥ 𝑟𝑛𝑜𝑑𝑒)
    H(pk_seed, adrs, l_add_r, out);
}

至此，我們已提及 fors_node、fors_sk_gen，回憶一下演算法，看看還有什麼

從 algorithm 16 的 line 3、4 能看出 fors_skGen 被 call了 k 次，FORS signature 裡於是就有了 k 個 FORS private key。Figure 14 是 FORS signature 的 format，FORS private key 的 tree index 從 0 到 k - 1，有 k 個 FORS private key，這裡的 AUTH 就是 authentication paths，明天我們會探討 authentication paths。

message digest md 如 FIPS 205 第 3 頁 [1]所述，它就是對 message 計算出來的雜湊值

The result of applying a hash function to a message. Also known as a
hash value. [1]

fors_node 和 xmss_node 的演算法高度一致，所以 fors_node 一旦完成，稍加修改就能完成 xmss_node。

明天我們就會探討 Forest of Random Subsets (FORS)，然後把 fors_sign 完成。

References

1. FIPS 205 Stateless Hash-Based Digital Signature Standard