本日重點: fors_node

fors_node 的演算法在 FIPS 205 第 30 頁 [1]

Merkle tree 的結構是 node 和 leaf，每一個 node 都是一個 subtree 的 root，fors_node 是一個遞迴　function，他的 input 是一個 subtree，fors_node 則是計算 root of subtree。
如果 subtree 只有一個 leaf，就用 F 計算雜湊值

If the subtree consists of a single leaf node, then the function simply returns a hash of the node’s private n-byte string

𝑛𝑜𝑑𝑒 ← F(PK.seed, ADRS, 𝑠𝑘)

如果 subtree 底下還有 subtree，就對 left subtree 和 right subtree 各自繼續遞迴計算 root of subtree，並把他們合併後用 H 計算雜湊值。

𝑛𝑜𝑑𝑒 ← H(PK.seed, ADRS, 𝑙𝑛𝑜𝑑𝑒 ∥ 𝑟𝑛𝑜𝑑𝑒)

Day 3 我們探討過 F、H、Tℓ，只要寫了 Tℓ，然後將 ℓ 代入 1 和 2 就分別是 F 和 H。

Tℓ(PK.seed, ADRS, 𝑀ℓ) = Trunc𝑛(SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ))

F、H、Tℓ 的 source code 大概像這樣

void T(unsigned int len, const uint8_t pk_seed[SPX_N], ADRS adrs, const uint8_t *p_M, uint8_t out[SPX_N])
{
    unsigned int mlen = len * SPX_N;
    unsigned int size = 64 + 22 + mlen;  // compressed ADRS is a 22 bytes array
    uint8_t buf[size];

    // buf <- PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ
    memcpy(buf, pk_seed, SPX_N);
    // toByte(0, 64 − n)
    unsigned char S[48];   // n: 16, 64 - n = 48
    toByte(0, 48, S);
    memcpy(buf + SPX_N, S, 48);

    // ADRSc is a 22 bytes array
    uint8_t adrs_c[22];
    compress_adrs(adrs_c, adrs);
    // ADRS𝑐
    memcpy(buf + SPX_N + sizeof(S), adrs_c, sizeof(adrs_c));

    // ADRS𝑐 ∥ 𝑀ℓ
    memcpy(buf + SPX_N + sizeof(S) + sizeof(adrs_c), p_M, mlen);

    // SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ)
    uint8_t out32[32];
    sha256(buf, sizeof(buf), out32);

    // Trunc𝑛(SHA-256(PK.seed ∥ toByte(0, 64 − 𝑛) ∥ ADRS𝑐 ∥ 𝑀ℓ))
    memcpy(out, out32, 16);   // n is 16
}

// F: len = 1
void F(const uint8_t pk_seed[SPX_N], ADRS adrs, const uint8_t M[16], uint8_t out[SPX_N])
{
    T(1, pk_seed, adrs, (uint8_t *)M[0], out);
}

// H: len = 2
void H(const uint8_t pk_seed[SPX_N], ADRS adrs, const uint8_t M[32], uint8_t out[SPX_N])
{
    T(2, pk_seed, adrs, (uint8_t *)M[0], out);
}

這裡用到了 sha256，SHA-256 目前是用軟體計算，由於之後會改成讓硬體計算 (例如 CryptoCell-312)，所以 sha256 的 implementation 目前就直接讓 ChatGPT 產生，這純粹是暫時的，之後幾天 會改成由硬體產生。

Makefile 目前做了這個保留，之後若改成 CryptoCell-310 或是 CryptoCell-312，不用去對既有的程式做修改。

ifeq ($(TARGET),nrf52840)
  CCXX := cc310
else ifeq ($(TARGET),nrf5340)
  CCXX := cc312
endif

至此，fors_node 還差一個 function 就完成了，就是 fors_sk_gen，我們明天繼續。