/src/openssl/crypto/slh_dsa/slh_fors.c

Source
/*
 * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include <string.h>
#include <openssl/crypto.h>
#include "slh_dsa_local.h"
#include "slh_dsa_key.h"

/* k = 14, 17, 22, 33, 35 (number of trees) */
#define SLH_MAX_K 35
/* a = 6, 8, 9, 12 or 14  - There are (2^a) merkle trees */
#define SLH_MAX_A 9

/* The FORS public key is computed from the roots of k Merkle trees */
#define SLH_MAX_ROOTS (SLH_MAX_K * SLH_MAX_N)

static void slh_base_2b(const uint8_t *in, uint32_t b, uint32_t *out, size_t out_len);

/**
 * @brief Generate FORS secret values
 * See FIPS 205 Section 8.1 Algorithm 14.
 *
 * @param ctx Contains SLH_DSA algorithm functions and constants.
 * @param sk_seed A private key seed of size |n|
 * @param pk_seed A public key seed of size |n|
 * @param adrs An ADRS object containing the layer address of zero, with the
 *             tree address and key pair address set to the index of the WOTS+
 *             key within the XMSS tree that signs the FORS key.
 * @param id The index of the FORS secret value within the sets of FORS trees.
 *               (which must be < 2^(hm - height)
 * @param pk_out The generated FORS secret value of size |n|
 * @param pk_out_len The maximum size of |pk_out|
 * @returns 1 on success, or 0 on error.
 */
static int slh_fors_sk_gen(SLH_DSA_HASH_CTX *ctx, const uint8_t *sk_seed,
    const uint8_t *pk_seed, uint8_t *adrs, uint32_t id,
    uint8_t *pk_out, size_t pk_out_len)
{
    const SLH_DSA_KEY *key = ctx->key;
    SLH_ADRS_DECLARE(sk_adrs);
    SLH_ADRS_FUNC_DECLARE(key, adrsf);

    adrsf->copy(sk_adrs, adrs);
    adrsf->set_type_and_clear(sk_adrs, SLH_ADRS_TYPE_FORS_PRF);
    adrsf->copy_keypair_address(sk_adrs, adrs);
    adrsf->set_tree_index(sk_adrs, id);
    return key->hash_func->PRF(ctx, pk_seed, sk_seed, sk_adrs, pk_out, pk_out_len);
}

/**
 * @brief Computes the nodes of a Merkle tree.
 * See FIPS 205 Section 8.2 Algorithm 18
 *
 * The leaf nodes are hashes of FORS secret values.
 * Each parent node is a hash of its 2 children.
 * Note this is a recursive function.
 *
 * @param ctx Contains SLH_DSA algorithm functions and constants.
 * @param sk_seed A SLH_DSA private key seed of size |n|
 * @param pk_seed A SLH_DSA public key seed of size |n|
 * @param adrs The ADRS object must have a layer address of zero, and the
 *             tree address set to the XMSS tree that signs the FORS key,
 *             the type set to FORS_TREE, and the keypair address set to the
 *             index of the WOTS+ key that signs the FORS key.
 * @param node_id The target node index
 * @param height The target node height
 * @param node The returned hash for a node of size|n|
 * @param node_len The maximum size of |node|
 * @returns 1 on success, or 0 on error.
 */
static int slh_fors_node(SLH_DSA_HASH_CTX *ctx, const uint8_t *sk_seed,
    const uint8_t *pk_seed, uint8_t *adrs, uint32_t node_id,
    uint32_t height, uint8_t *node, size_t node_len)
{
    int ret = 0;
    const SLH_DSA_KEY *key = ctx->key;
    uint8_t sk[SLH_MAX_N], lnode[SLH_MAX_N], rnode[SLH_MAX_N];
    uint32_t n = key->params->n;

    SLH_ADRS_FUNC_DECLARE(key, adrsf);

    if (height == 0) {
        /* Gets here for leaf nodes */
        if (slh_fors_sk_gen(ctx, sk_seed, pk_seed, adrs, node_id, sk, sizeof(sk))) {
            adrsf->set_tree_height(adrs, 0);
            adrsf->set_tree_index(adrs, node_id);
            ret = key->hash_func->F(ctx, pk_seed, adrs, sk, n, node, node_len);
        }
        OPENSSL_cleanse(sk, n);
    } else {
        if (slh_fors_node(ctx, sk_seed, pk_seed, adrs, 2 * node_id, height - 1,
                lnode, sizeof(lnode))
            && slh_fors_node(ctx, sk_seed, pk_seed, adrs, 2 * node_id + 1,
                height - 1, rnode, sizeof(rnode))) {
            adrsf->set_tree_height(adrs, height);
            adrsf->set_tree_index(adrs, node_id);
            ret = key->hash_func->H(ctx, pk_seed, adrs, lnode, rnode, node, node_len);
        }
        OPENSSL_cleanse(lnode, sizeof(lnode));
        OPENSSL_cleanse(rnode, sizeof(rnode));
    }
    return ret;
}

/**
 * @brief Generate an FORS signature
 * See FIPS 205 Section 8.3 Algorithm 16
 *
 * A FORS signature has a size of (k * (1 + a) * n) bytes
 * There are k trees, each of which have a private key value of size |n| followed
 * by an authentication path of size |a| (where each path is size |n|)
 *
 * @param ctx Contains SLH_DSA algorithm functions and constants.
 * @param md A message digest of size |(k * a + 7) / 8| bytes to sign
 * @param sk_seed A private key seed of size |n|
 * @param pk_seed A public key seed of size |n|
 * @param adrs The ADRS object must have a layer address of zero, and the
 *             tree address set to the XMSS tree that signs the FORS key,
 *             the type set to FORS_TREE, and the keypair address set to the
 *             index of the WOTS+ key that signs the FORS key.
 * @param sig_wpkt A WPACKET object to write the generated XMSS signature to
 * @param sig_len  The size of |sig| which is (2 * n + 3) * n + tree_height * n.
 * @returns 1 on success, or 0 on error.
 */
int ossl_slh_fors_sign(SLH_DSA_HASH_CTX *ctx, const uint8_t *md,
    const uint8_t *sk_seed, const uint8_t *pk_seed,
    uint8_t *adrs, WPACKET *sig_wpkt)
{
    int ret = 0;
    const SLH_DSA_KEY *key = ctx->key;
    uint32_t tree_id, layer, s, tree_offset;
    uint32_t ids[SLH_MAX_K];
    const SLH_DSA_PARAMS *params = key->params;
    uint32_t n = params->n;
    uint32_t k = params->k; /* number of trees */
    uint32_t a = params->a;
    uint32_t two_power_a = (1 << a); /* this is t in FIPS 205 */
    uint32_t tree_id_times_two_power_a = 0;
    uint8_t out[SLH_MAX_N];

    /*
     * Split md into k a-bit values e.g with k = 14, a = 12
     * ids[0..13] = 12 bits each of md
     */
    slh_base_2b(md, a, ids, k);

    for (tree_id = 0; tree_id < k; ++tree_id) {
        /* Get the tree[i] leaf id */
        uint32_t node_id = ids[tree_id]; /* |id| = |a| bits */

        /*
         * Give each of the k trees a unique range at each level.
         * e.g. If we have 4096 leaf nodes (2^a = 2^12) for each tree
         * i will use indexes from 4096 * i + (0..4095) for its bottom level.
         * For the next level up from the bottom there would be 2048 nodes
         * (so tree i uses indexes 2048 * i + (0...2047) for this level)
         */
        tree_offset = tree_id_times_two_power_a;

        if (!slh_fors_sk_gen(ctx, sk_seed, pk_seed, adrs,
                node_id + tree_id_times_two_power_a, out, sizeof(out))
            || !WPACKET_memcpy(sig_wpkt, out, n))
            goto err;

        /*
         * Traverse from the bottom of the tree (layer = 0)
         * up to the root (layer = a - 1).
         * NOTE: This is a really inefficient way of doing this, since at
         * layer a - 1 it calculates most of the hashes of the entire tree as
         * well as all the leaf nodes. So it is calculating nodes multiple times.
         */
        for (layer = 0; layer < a; ++layer) {
            s = node_id ^ 1; /* XOR gets the index of the other child in a binary tree */
            if (!slh_fors_node(ctx, sk_seed, pk_seed, adrs,
                    s + tree_offset, layer, out, sizeof(out)))
                goto err;
            node_id >>= 1; /* Get the parent node id */
            tree_offset >>= 1; /* Each layer up has half as many nodes */
            if (!WPACKET_memcpy(sig_wpkt, out, n))
                goto err;
        }
        tree_id_times_two_power_a += two_power_a;
    }
    ret = 1;
err:
    OPENSSL_cleanse(out, sizeof(out));
    return ret;
}

/**
 * @brief Compute a candidate FORS public key from a message and signature.
 * See FIPS 205 Section 8.4 Algorithm 17.
 *
 * A FORS signature has a size of (k * (a + 1) * n) bytes
 *
 * @param ctx Contains SLH_DSA algorithm functions and constants.
 * @param fors_sig_rpkt A PACKET object to read a FORS signature from
 * @param md A message digest of size (k * a / 8) bytes
 * @param pk_seed A public key seed of size |n|
 * @param adrs The ADRS object must have a layer address of zero, and the
 *             tree address set to the XMSS tree that signs the FORS key,
 *             the type set to FORS_TREE, and the keypair address set to the
 *             index of the WOTS+ key that signs the FORS key.
 * @param pk_out The returned candidate FORS public key of size |n|
 * @param pk_out_len The maximum size of |pk_out|
 * @returns 1 on success, or 0 on error.
 */
int ossl_slh_fors_pk_from_sig(SLH_DSA_HASH_CTX *ctx, PACKET *fors_sig_rpkt,
    const uint8_t *md, const uint8_t *pk_seed,
    uint8_t *adrs, uint8_t *pk_out, size_t pk_out_len)
{
    const SLH_DSA_KEY *key = ctx->key;
    int ret = 0;
    uint32_t i, j, aoff = 0;
    uint32_t ids[SLH_MAX_K];
    const SLH_DSA_PARAMS *params = key->params;
    uint32_t a = params->a;
    uint32_t k = params->k;
    uint32_t n = params->n;
    uint32_t two_power_a = (1 << a);
    const uint8_t *sk, *authj; /* Pointers to |sig| buffer inside fors_sig_rpkt */
    uint8_t roots[SLH_MAX_ROOTS];
    size_t roots_len = 0; /* The size of |roots| */
    uint8_t *node0, *node1; /* Pointers into roots[] */
    WPACKET root_pkt, *wroot_pkt = &root_pkt; /* Points to |roots| buffer */

    SLH_ADRS_DECLARE(pk_adrs);
    SLH_ADRS_FUNC_DECLARE(key, adrsf);
    SLH_ADRS_FN_DECLARE(adrsf, set_tree_index);
    SLH_ADRS_FN_DECLARE(adrsf, set_tree_height);
    SLH_HASH_FUNC_DECLARE(key, hashf);
    SLH_HASH_FN_DECLARE(hashf, F);
    SLH_HASH_FN_DECLARE(hashf, H);

    if (!WPACKET_init_static_len(wroot_pkt, roots, sizeof(roots), 0))
        return 0;

    /* Split md into k a-bit values e.g ids[0..k-1] = 12 bits each of md */
    slh_base_2b(md, a, ids, k);

    /* Compute the roots of k Merkle trees */
    for (i = 0; i < k; ++i) {
        uint32_t id = ids[i];
        uint32_t node_id = id + aoff;

        set_tree_height(adrs, 0);
        set_tree_index(adrs, node_id);

        /* Regenerate the public key of the leaf */
        if (!PACKET_get_bytes(fors_sig_rpkt, &sk, n)
            || !WPACKET_allocate_bytes(wroot_pkt, n, &node0)
            || !F(ctx, pk_seed, adrs, sk, n, node0, n))
            goto err;

        /* This omits the copying of the nodes that the FIPS 205 code does */
        node1 = node0;
        for (j = 0; j < a; ++j) {
            /* Get this layers other child public key */
            if (!PACKET_get_bytes(fors_sig_rpkt, &authj, n))
                goto err;
            /* Hash the children together to get the parent nodes public key */
            set_tree_height(adrs, j + 1);
            if ((id & 1) == 0) {
                node_id >>= 1;
                set_tree_index(adrs, node_id);
                if (!H(ctx, pk_seed, adrs, node0, authj, node1, n))
                    goto err;
            } else {
                node_id = (node_id - 1) >> 1;
                set_tree_index(adrs, node_id);
                if (!H(ctx, pk_seed, adrs, authj, node0, node1, n))
                    goto err;
            }
            id >>= 1;
        }
        aoff += two_power_a;
    }
    if (!WPACKET_get_total_written(wroot_pkt, &roots_len))
        goto err;

    /* The public key is the hash of all the roots of the k trees */
    adrsf->copy(pk_adrs, adrs);
    adrsf->set_type_and_clear(pk_adrs, SLH_ADRS_TYPE_FORS_ROOTS);
    adrsf->copy_keypair_address(pk_adrs, adrs);
    ret = hashf->T(ctx, pk_seed, pk_adrs, roots, roots_len, pk_out, pk_out_len);
err:
    if (!WPACKET_finish(wroot_pkt))
        ret = 0;
    /* At most one |n| byte root per tree was written */
    OPENSSL_cleanse(roots, k * n);
    return ret;
}

/**
 * @brief Convert a byte string into a base 2^b representation
 * See FIPS 205 Algorithm 4
 *
 * @param in An input byte stream with a size >= |outlen * b / 8|
 * @param b The bit size to divide |in| into
 *          This is one of 6, 8, 9, 12 or 14 for FORS.
 * @param out The array of returned base 2^b integers that represents the first
 *            |outlen|*|b| bits of |in|
 * @param out_len The size of |out|
 */
static void slh_base_2b(const uint8_t *in, uint32_t b,
    uint32_t *out, size_t out_len)
{
    size_t consumed = 0;
    uint32_t bits = 0;
    uint32_t total = 0;
    uint32_t mask = (1 << b) - 1;

    for (consumed = 0; consumed < out_len; consumed++) {
        while (bits < b) {
            total <<= 8;
            total += *in++;
            bits += 8;
        }
        bits -= b;
        *out++ = (total >> bits) & mask;
    }
}

Coverage Report

Created: 2026-08-12 06:14

Line	Count	Source
1		/*
2		* Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
3		*
4		* Licensed under the Apache License 2.0 (the "License"). You may not use
5		* this file except in compliance with the License. You can obtain a copy
6		* in the file LICENSE in the source distribution or at
7		* https://www.openssl.org/source/license.html
8		*/
9
10		#include <string.h>
11		#include <openssl/crypto.h>
12		#include "slh_dsa_local.h"
13		#include "slh_dsa_key.h"
14
15		/* k = 14, 17, 22, 33, 35 (number of trees) */
16		#define SLH_MAX_K 35
17		/* a = 6, 8, 9, 12 or 14 - There are (2^a) merkle trees */
18		#define SLH_MAX_A 9
19
20		/* The FORS public key is computed from the roots of k Merkle trees */
21		#define SLH_MAX_ROOTS (SLH_MAX_K * SLH_MAX_N)
22
23		static void slh_base_2b(const uint8_t in, uint32_t b, uint32_t out, size_t out_len);
24
25		/**
26		* @brief Generate FORS secret values
27		* See FIPS 205 Section 8.1 Algorithm 14.
28		*
29		* @param ctx Contains SLH_DSA algorithm functions and constants.
30		* @param sk_seed A private key seed of size \|n\|
31		* @param pk_seed A public key seed of size \|n\|
32		* @param adrs An ADRS object containing the layer address of zero, with the
33		* tree address and key pair address set to the index of the WOTS+
34		* key within the XMSS tree that signs the FORS key.
35		* @param id The index of the FORS secret value within the sets of FORS trees.
36		* (which must be < 2^(hm - height)
37		* @param pk_out The generated FORS secret value of size \|n\|
38		* @param pk_out_len The maximum size of \|pk_out\|
39		* @returns 1 on success, or 0 on error.
40		*/
41		static int slh_fors_sk_gen(SLH_DSA_HASH_CTX ctx, const uint8_t sk_seed,
42		const uint8_t pk_seed, uint8_t adrs, uint32_t id,
43		uint8_t *pk_out, size_t pk_out_len)
44	0	{
45	0	const SLH_DSA_KEY *key = ctx->key;
46	0	SLH_ADRS_DECLARE(sk_adrs);
47	0	SLH_ADRS_FUNC_DECLARE(key, adrsf);
48
49	0	adrsf->copy(sk_adrs, adrs);
50	0	adrsf->set_type_and_clear(sk_adrs, SLH_ADRS_TYPE_FORS_PRF);
51	0	adrsf->copy_keypair_address(sk_adrs, adrs);
52	0	adrsf->set_tree_index(sk_adrs, id);
53	0	return key->hash_func->PRF(ctx, pk_seed, sk_seed, sk_adrs, pk_out, pk_out_len);
54	0	}
55
56		/**
57		* @brief Computes the nodes of a Merkle tree.
58		* See FIPS 205 Section 8.2 Algorithm 18
59		*
60		* The leaf nodes are hashes of FORS secret values.
61		* Each parent node is a hash of its 2 children.
62		* Note this is a recursive function.
63		*
64		* @param ctx Contains SLH_DSA algorithm functions and constants.
65		* @param sk_seed A SLH_DSA private key seed of size \|n\|
66		* @param pk_seed A SLH_DSA public key seed of size \|n\|
67		* @param adrs The ADRS object must have a layer address of zero, and the
68		* tree address set to the XMSS tree that signs the FORS key,
69		* the type set to FORS_TREE, and the keypair address set to the
70		* index of the WOTS+ key that signs the FORS key.
71		* @param node_id The target node index
72		* @param height The target node height
73		* @param node The returned hash for a node of size\|n\|
74		* @param node_len The maximum size of \|node\|
75		* @returns 1 on success, or 0 on error.
76		*/
77		static int slh_fors_node(SLH_DSA_HASH_CTX ctx, const uint8_t sk_seed,
78		const uint8_t pk_seed, uint8_t adrs, uint32_t node_id,
79		uint32_t height, uint8_t *node, size_t node_len)
80	0	{
81	0	int ret = 0;
82	0	const SLH_DSA_KEY *key = ctx->key;
83	0	uint8_t sk[SLH_MAX_N], lnode[SLH_MAX_N], rnode[SLH_MAX_N];
84	0	uint32_t n = key->params->n;
85
86	0	SLH_ADRS_FUNC_DECLARE(key, adrsf);
87
88	0	if (height == 0) {
89		/* Gets here for leaf nodes */
90	0	if (slh_fors_sk_gen(ctx, sk_seed, pk_seed, adrs, node_id, sk, sizeof(sk))) {
91	0	adrsf->set_tree_height(adrs, 0);
92	0	adrsf->set_tree_index(adrs, node_id);
93	0	ret = key->hash_func->F(ctx, pk_seed, adrs, sk, n, node, node_len);
94	0	}
95	0	OPENSSL_cleanse(sk, n);
96	0	} else {
97	0	if (slh_fors_node(ctx, sk_seed, pk_seed, adrs, 2 * node_id, height - 1,
98	0	lnode, sizeof(lnode))
99	0	&& slh_fors_node(ctx, sk_seed, pk_seed, adrs, 2 * node_id + 1,
100	0	height - 1, rnode, sizeof(rnode))) {
101	0	adrsf->set_tree_height(adrs, height);
102	0	adrsf->set_tree_index(adrs, node_id);
103	0	ret = key->hash_func->H(ctx, pk_seed, adrs, lnode, rnode, node, node_len);
104	0	}
105	0	OPENSSL_cleanse(lnode, sizeof(lnode));
106	0	OPENSSL_cleanse(rnode, sizeof(rnode));
107	0	}
108	0	return ret;
109	0	}
110
111		/**
112		* @brief Generate an FORS signature
113		* See FIPS 205 Section 8.3 Algorithm 16
114		*
115		* A FORS signature has a size of (k * (1 + a) * n) bytes
116		* There are k trees, each of which have a private key value of size \|n\| followed
117		* by an authentication path of size \|a\| (where each path is size \|n\|)
118		*
119		* @param ctx Contains SLH_DSA algorithm functions and constants.
120		* @param md A message digest of size \|(k * a + 7) / 8\| bytes to sign
121		* @param sk_seed A private key seed of size \|n\|
122		* @param pk_seed A public key seed of size \|n\|
123		* @param adrs The ADRS object must have a layer address of zero, and the
124		* tree address set to the XMSS tree that signs the FORS key,
125		* the type set to FORS_TREE, and the keypair address set to the
126		* index of the WOTS+ key that signs the FORS key.
127		* @param sig_wpkt A WPACKET object to write the generated XMSS signature to
128		* @param sig_len The size of \|sig\| which is (2 * n + 3) * n + tree_height * n.
129		* @returns 1 on success, or 0 on error.
130		*/
131		int ossl_slh_fors_sign(SLH_DSA_HASH_CTX ctx, const uint8_t md,
132		const uint8_t sk_seed, const uint8_t pk_seed,
133		uint8_t adrs, WPACKET sig_wpkt)
134	0	{
135	0	int ret = 0;
136	0	const SLH_DSA_KEY *key = ctx->key;
137	0	uint32_t tree_id, layer, s, tree_offset;
138	0	uint32_t ids[SLH_MAX_K];
139	0	const SLH_DSA_PARAMS *params = key->params;
140	0	uint32_t n = params->n;
141	0	uint32_t k = params->k; /* number of trees */
142	0	uint32_t a = params->a;
143	0	uint32_t two_power_a = (1 << a); /* this is t in FIPS 205 */
144	0	uint32_t tree_id_times_two_power_a = 0;
145	0	uint8_t out[SLH_MAX_N];
146
147		/*
148		* Split md into k a-bit values e.g with k = 14, a = 12
149		* ids[0..13] = 12 bits each of md
150		*/
151	0	slh_base_2b(md, a, ids, k);
152
153	0	for (tree_id = 0; tree_id < k; ++tree_id) {
154		/* Get the tree[i] leaf id */
155	0	uint32_t node_id = ids[tree_id]; /* \|id\| = \|a\| bits */
156
157		/*
158		* Give each of the k trees a unique range at each level.
159		* e.g. If we have 4096 leaf nodes (2^a = 2^12) for each tree
160		* i will use indexes from 4096 * i + (0..4095) for its bottom level.
161		* For the next level up from the bottom there would be 2048 nodes
162		* (so tree i uses indexes 2048 * i + (0...2047) for this level)
163		*/
164	0	tree_offset = tree_id_times_two_power_a;
165
166	0	if (!slh_fors_sk_gen(ctx, sk_seed, pk_seed, adrs,
167	0	node_id + tree_id_times_two_power_a, out, sizeof(out))
168	0	\|\| !WPACKET_memcpy(sig_wpkt, out, n))
169	0	goto err;
170
171		/*
172		* Traverse from the bottom of the tree (layer = 0)
173		* up to the root (layer = a - 1).
174		* NOTE: This is a really inefficient way of doing this, since at
175		* layer a - 1 it calculates most of the hashes of the entire tree as
176		* well as all the leaf nodes. So it is calculating nodes multiple times.
177		*/
178	0	for (layer = 0; layer < a; ++layer) {
179	0	s = node_id ^ 1; /* XOR gets the index of the other child in a binary tree */
180	0	if (!slh_fors_node(ctx, sk_seed, pk_seed, adrs,
181	0	s + tree_offset, layer, out, sizeof(out)))
182	0	goto err;
183	0	node_id >>= 1; /* Get the parent node id */
184	0	tree_offset >>= 1; /* Each layer up has half as many nodes */
185	0	if (!WPACKET_memcpy(sig_wpkt, out, n))
186	0	goto err;
187	0	}
188	0	tree_id_times_two_power_a += two_power_a;
189	0	}
190	0	ret = 1;
191	0	err:
192	0	OPENSSL_cleanse(out, sizeof(out));
193	0	return ret;
194	0	}
195
196		/**
197		* @brief Compute a candidate FORS public key from a message and signature.
198		* See FIPS 205 Section 8.4 Algorithm 17.
199		*
200		* A FORS signature has a size of (k * (a + 1) * n) bytes
201		*
202		* @param ctx Contains SLH_DSA algorithm functions and constants.
203		* @param fors_sig_rpkt A PACKET object to read a FORS signature from
204		* @param md A message digest of size (k * a / 8) bytes
205		* @param pk_seed A public key seed of size \|n\|
206		* @param adrs The ADRS object must have a layer address of zero, and the
207		* tree address set to the XMSS tree that signs the FORS key,
208		* the type set to FORS_TREE, and the keypair address set to the
209		* index of the WOTS+ key that signs the FORS key.
210		* @param pk_out The returned candidate FORS public key of size \|n\|
211		* @param pk_out_len The maximum size of \|pk_out\|
212		* @returns 1 on success, or 0 on error.
213		*/
214		int ossl_slh_fors_pk_from_sig(SLH_DSA_HASH_CTX ctx, PACKET fors_sig_rpkt,
215		const uint8_t md, const uint8_t pk_seed,
216		uint8_t adrs, uint8_t pk_out, size_t pk_out_len)
217	0	{
218	0	const SLH_DSA_KEY *key = ctx->key;
219	0	int ret = 0;
220	0	uint32_t i, j, aoff = 0;
221	0	uint32_t ids[SLH_MAX_K];
222	0	const SLH_DSA_PARAMS *params = key->params;
223	0	uint32_t a = params->a;
224	0	uint32_t k = params->k;
225	0	uint32_t n = params->n;
226	0	uint32_t two_power_a = (1 << a);
227	0	const uint8_t sk, authj; /* Pointers to \|sig\| buffer inside fors_sig_rpkt */
228	0	uint8_t roots[SLH_MAX_ROOTS];
229	0	size_t roots_len = 0; /* The size of \|roots\| */
230	0	uint8_t node0, node1; /* Pointers into roots[] */
231	0	WPACKET root_pkt, wroot_pkt = &root_pkt; / Points to \|roots\| buffer */
232
233	0	SLH_ADRS_DECLARE(pk_adrs);
234	0	SLH_ADRS_FUNC_DECLARE(key, adrsf);
235	0	SLH_ADRS_FN_DECLARE(adrsf, set_tree_index);
236	0	SLH_ADRS_FN_DECLARE(adrsf, set_tree_height);
237	0	SLH_HASH_FUNC_DECLARE(key, hashf);
238	0	SLH_HASH_FN_DECLARE(hashf, F);
239	0	SLH_HASH_FN_DECLARE(hashf, H);
240
241	0	if (!WPACKET_init_static_len(wroot_pkt, roots, sizeof(roots), 0))
242	0	return 0;
243
244		/* Split md into k a-bit values e.g ids[0..k-1] = 12 bits each of md */
245	0	slh_base_2b(md, a, ids, k);
246
247		/* Compute the roots of k Merkle trees */
248	0	for (i = 0; i < k; ++i) {
249	0	uint32_t id = ids[i];
250	0	uint32_t node_id = id + aoff;
251
252	0	set_tree_height(adrs, 0);
253	0	set_tree_index(adrs, node_id);
254
255		/* Regenerate the public key of the leaf */
256	0	if (!PACKET_get_bytes(fors_sig_rpkt, &sk, n)
257	0	\|\| !WPACKET_allocate_bytes(wroot_pkt, n, &node0)
258	0	\|\| !F(ctx, pk_seed, adrs, sk, n, node0, n))
259	0	goto err;
260
261		/* This omits the copying of the nodes that the FIPS 205 code does */
262	0	node1 = node0;
263	0	for (j = 0; j < a; ++j) {
264		/* Get this layers other child public key */
265	0	if (!PACKET_get_bytes(fors_sig_rpkt, &authj, n))
266	0	goto err;
267		/* Hash the children together to get the parent nodes public key */
268	0	set_tree_height(adrs, j + 1);
269	0	if ((id & 1) == 0) {
270	0	node_id >>= 1;
271	0	set_tree_index(adrs, node_id);
272	0	if (!H(ctx, pk_seed, adrs, node0, authj, node1, n))
273	0	goto err;
274	0	} else {
275	0	node_id = (node_id - 1) >> 1;
276	0	set_tree_index(adrs, node_id);
277	0	if (!H(ctx, pk_seed, adrs, authj, node0, node1, n))
278	0	goto err;
279	0	}
280	0	id >>= 1;
281	0	}
282	0	aoff += two_power_a;
283	0	}
284	0	if (!WPACKET_get_total_written(wroot_pkt, &roots_len))
285	0	goto err;
286
287		/* The public key is the hash of all the roots of the k trees */
288	0	adrsf->copy(pk_adrs, adrs);
289	0	adrsf->set_type_and_clear(pk_adrs, SLH_ADRS_TYPE_FORS_ROOTS);
290	0	adrsf->copy_keypair_address(pk_adrs, adrs);
291	0	ret = hashf->T(ctx, pk_seed, pk_adrs, roots, roots_len, pk_out, pk_out_len);
292	0	err:
293	0	if (!WPACKET_finish(wroot_pkt))
294	0	ret = 0;
295		/* At most one \|n\| byte root per tree was written */
296	0	OPENSSL_cleanse(roots, k * n);
297	0	return ret;
298	0	}
299
300		/**
301		* @brief Convert a byte string into a base 2^b representation
302		* See FIPS 205 Algorithm 4
303		*
304		* @param in An input byte stream with a size >= \|outlen * b / 8\|
305		* @param b The bit size to divide \|in\| into
306		* This is one of 6, 8, 9, 12 or 14 for FORS.
307		* @param out The array of returned base 2^b integers that represents the first
308		* \|outlen\|*\|b\| bits of \|in\|
309		* @param out_len The size of \|out\|
310		*/
311		static void slh_base_2b(const uint8_t *in, uint32_t b,
312		uint32_t *out, size_t out_len)
313	0	{
314	0	size_t consumed = 0;
315	0	uint32_t bits = 0;
316	0	uint32_t total = 0;
317	0	uint32_t mask = (1 << b) - 1;
318
319	0	for (consumed = 0; consumed < out_len; consumed++) {
320	0	while (bits < b) {
321	0	total <<= 8;
322	0	total += *in++;
323	0	bits += 8;
324	0	}
325	0	bits -= b;
326	0	*out++ = (total >> bits) & mask;
327	0	}
328	0	}