PQC后量子密码

//ML-KEM.keygen
input：
  d0: 32 random byte d0,
  d1: 32 random byte d1,
  z:  32 random byte z
output: 
  ek: 384k+32 byte 
  dk: 1152k+96 byte dk=dk0_pke||dk1_pke||ek||H(ek)||z
算法流程
1. 检查d0, d1, z输入是否为NULL
2. K-PKE.Keygen
3. H(ek)
4. return dk
5. return ek

//K-PKE.Keygen
1.输入d0, d1
2.p,sigma = Gsec(d0||k，d1||0) //p和sigma带掩
3.输出dk.rho(z), ek.rho(p)//p 脱掩
4.s0,s1 = CBDsec()
5.s0,s1 = nttsec(s0， s1) //输入算术，输出算术
6.dk0 = encode12(s0)
7.dk1 = encode12(s1)
8.输出dk.dk0, 输出dk.dk1
9.循环L次s=s0+s1, shuffle
10.循环K-1次 begin
      循环L次A=SampleNTT(rho)（这里的rho = rho0 xor rho1）
      循环L次A*s, shuffle
   循环K-1次 end
11.循环K次e0, e1 = CBDsec()
12.循环K次nttsec(e0, e1)
13.循环K次t=As+e, shuffle
14.encode12(t)
15.输出dk.ek,输出ek.ek
16.H(ek)
17.输出H(ek)

//ML-KEM.Encaps
input：
  ek：384k+64 byte
output: 
  K：32 byte 
  c：32(du*k+dv) byte
算法流程
1.ek lenth check
2.generate m0,m1
3.check m0, m1
4.H(ek)
5.Gsec(m0||H(ek), m1||0)
6.K-PKE. Enc_sec & ek modulus check
7.return K, c

//K-PKE. Enc_sec
1.输入ek.ek，输入ek.rho
2.H(ek)
3.输入m0, m1
4.Gsec(m0||H(ek), m1||0)
5.输出K0，输出K1
6.y0, y1 = CBDsec()
7.y0, y1 = nttsec(y0, y1)
8.循环K-1次 begin
      循环L次A=SampleNTT(rho)
      循环L次A*y, 用shuffle
  循环K-1次 end
9.intt_sec(Ay)
10.循环K次e1_0,e1_1 = CBD_sec()
11.循环K次u=intt(Ay)+e1_0, shuffle
12.循环K次u=u+e1_1
13.c1 = compress(u)
14.输出c1
15.输入ek.ek
16.t=decode12(ek)
17.t*y，用shuffle
18.intt_sec(ty)
19.e2 = CBD()
20.v=intt(ty)+e2, shuffle
21.mu=decompress(m)
22.v=v+mu
23.compress(v)
24.输出c2

//ML-KEM.Decaps
input：
  dk：768k+96 byte
  c：32(du*k+dv) byte
output: 
  K：32 byte
算法流程
1.hash_check
2.J(z||c)
3.K-PKE. Dec_sec
4.Gsec(m0'||h, m1'||0)
5.K-PKE. Enc_sec
6.cmp(c, c')
7.check(c)
8.return K’

//K-PKE. Dec_sec
1.输入ek.ek 输入ek.rho 输入h
2.cmp(H(ek), h)
3.J(z||c)：输入c 输入z
4.u=decompress(c1)
5.v=decompress(c2)
6.ntt(u)
7.输入dk0
8.decode12(dk0)
9.s0*u
10.intt(s0u)
11.w0=v-s0u
12.输入dk1
13.decode12(dk1)
14.s1*u
15.intt(s1u)
16.w1 = -intt(s1u)
17.m0, m1 =compress_sec(w0, w1)
18.sha3_512:Gsec(m0'||h, m1'||0)
19.CBDsec(y0, y1)
20.nttsec(y0, y1)
21.循环L次A=SampleNTT(rho)
      循环L次A*y, 用shuffle
22.intt_sec(Ay)
23.循环K次e1_0, e1_1 = CBD_sec()
24.循环K次u0=intt(Ay)+e1_0, shuffle
25.循环K次u1[i]=e1_1
26.compress_sec(u0, u1)
27.输出c1_0', c1_1'
28.输入ek.ek
29.t=decode12(ek) (复用ek.ek)
30.t*y，用shuffle
31.intt_sec(ty)
32.CBD(e2)
33.v0=intt(ty)+e2, shuffle
34.mu0=decompress(m0')
35.v0=v0+mu0
36.v1=decompress(m1')
37.c2_0, c2_1 = compress_sec(v0, v1)
38.输入c2_0, c2_1
39.(c2 - c2_0') % 2^d
40.a = crc((c2 - c2_0') % 2^d)
41.b = crc(c2_1'% 2^d)
42.cmp(a, b)
43.randomdelay
44.cmp(a, b)
45.输入c1
46.输入c1_0', c1_1'
47.(c1 - c1_0') % 2^d
48.a = crc((c1- c1_0') % 2^d)
49.b = crc(c1_1'% 2^d)
50.cmp(a, b)
51.randomdelay
52.cmp(a, b)
53.输出K0, K1

困难问题：模块格上的短整数问题（Module - SIS）
安全参数：
    安全性基于格上最坏情况下的复杂性假设
    3个安全级别（NIST Level 1/3/5对应128/192/256比特经典安全）

Pure:      M' = 0x00 ‖ ctx_len ‖ ctx ‖ M            (原始消息M可任意长)
Pre-hash:  M' = 0x01 ‖ ctx_len ‖ ctx ‖ OID ‖ PH(M)  (PH(M)是固定长度的哈希值)，ctx长度在[0,255]字节
Raw:       M' = M                                   (直接透传，M' 作为变长输入)

Pure:      M' = 0x00 ‖ ctx_len ‖ ctx ‖ M            (原始消息M可任意长)
Pre-hash:  M' = 0x01 ‖ ctx_len ‖ ctx ‖ OID ‖ PH(M)  (PH(M)是固定长度的哈希值)，ctx长度在[0,255]字节
Raw:       M' = M                                   (直接透传，M' 作为变长输入)

 u = ceil(8*n/w) //ceil向上取整
 v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) //floor向下取整，lg底数为2
 ls = 16 - (v * w)
 p = u + v
//u：消息所需的w位字段数
//v：校验和字节字符串所需的w位字段数

//以LMOTS_SHA256_N32_W8举例
u = ceil(8*32/8) = 32 //消息被分成32个块，每个块8bit
v = ceil((floor(lg((2^w - 1) * u)) + 1) / w) //v可以理解为checksum数量
  = ceil((floor(lg((2^8 - 1) * 32)) + 1) / 8)
  = ceil((floor(X) + 1) / 8) //X=lg((2^8 - 1) * 32)=lg(255 * 32)=lg(8160) ,12<lg(8160)<13,底数是2，log2(8160) ≈ 12.994
  = ceil((12 + 1) / 8)
  = ceil(13/8)
  = 2
ls = 16 - 2*8 = 0
p = 32+2=34

//sign_len
|sig| = typecode||C||y[1]||...||y[32]
1124 = 4+n+p*n=4+32+p*32=36+34*32=36+1088=1124

//type取值：
enum lmots_algorithm_type {
 lmots_reserved       = 0,
 lmots_sha256_n32_w1  = 1,
 lmots_sha256_n32_w2  = 2,
 lmots_sha256_n32_w4  = 3,
 lmots_sha256_n32_w8  = 4
};

//l为16字节，SEED为m字节，m为H输出字节数，在开始时统一生成
x_q[i] = H(l || u32str(q) || u16str(i) || u8str(0xff) || SEED). //私钥长度固定，为

//byte(S,0)是S最左边字节，byte(S,1)是左边开始的第二个字节，byte(S,n-1)是S最右边字节
coef(S, i, w) = (2^w - 1) & (byte(S, floor(i * w / 8)) >> (8 - (w * (i % (8 / w)) + w)) )

sum = 0
for (i=0; i< n*8/w; i++) //n是哈希摘要输出字节数
{
    sum += sum + (2^w -1) - cofe(S, i, w)//S表示输入到该函数的n字节字符串
}
return (sum << 1s) //ls值见表1，sum值总和为16位无符号整数

通过依次执行以下操作生成消息的LM-OTS签名：将LMS密钥标识符I、LMS叶标识符q、值D_MESG（0x8181）和随机化器C前置到消息(==这里的消息是指原始待签名的消息，任意长度==)；计算散列；将哈希的校验和连接到哈希本身；将结果值视为w位值序列；以及使用每个w位值来确定将函数H应用于私钥的对应元素的次数。函数H的输出连接在一起并作为签名返回。此过程的伪代码如下所示。

//签名值表示
sig=type||C||y[0]||..||y[p-1]
//对消息hash预处理，得到Q
Q = H(I||q||8181||C||message)
for ( i = 0; i < p; i = i + 1 )
{
     a = coef(Q || Cksm(Q), i, w) 
     tmp = x[i] //这里x[i]参考私钥表示：x[i]=H(I||u32str(q)||u16str(i)||u8str(0xff)||SEED)
     for ( j = 0; j < a; j = j + 1 ) 
     {
         tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
     }
     y[i] = tmp
}

//私钥表示（标准没有规定格式）
priv=type||I||q||x[0]||...||x[p-1]
//附录A指定求私钥方式
x[i]=H(I||u32str(q)||u16str(i)||u8str(0xff)||SEED)

//公钥表示
pubkey=type||I||q||K
K=H(I||q||8080||y[0]||...||y[p-1])
for(i=0;i<p;i++)
{
    tmp = x[i]//这里x[i]参考私钥表示：x[i]=H(I||u32str(q)||u16str(i)||u8str(0xff)||SEED)
    for(j=0;j<2^w-1;j++)
    {
        tmp = H(I || u32str(q) || u16str(i) || u8str(j) || tmp)
    }
    y[i] = tmp  
}
K = H(l || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1])

Leighton-Michali签名（LMS）方法可以对大量但固定数量的消息进行签名。LMS系统使用两个加密组件：一次性签名方法和哈希函数。每个LMS公钥/私钥对与一个完美二叉树相关联，其中每个节点包含一个m字节值，其中m是哈希函数的输出长度。树的每个叶包含LM-OTS公钥/私钥对的公钥值。树的根包含的值是LMS公钥。通过将哈希函数应用于其子节点的值的串联来计算每个内部节点。

树的每个节点都与一个节点编号相关联，这是一个无符号整数，在下面的算法中表示为node_num，计算如下。根节点具有节点编号1；对于节点号N<2<sup>h（其中h是树的高度）</sup>的每个节点，其左子节点号为2*N，而其右子节点号为2*N+1。这样做的结果是树中的每个节点都有一个唯一的节点号，叶子的节点号为2<sup>h</sup>，（2<sup>h</sup>）+1，（2<sup>h</sup>）+2，…（2<sup>h</sup>）+（2<sup>h</sup>）-1。通常，第i级的第j个节点的节点号为2<sup>i</sup>+j。当LMS算法中需要节点数时，可以方便地计算节点数，如这些算法中所述。

由上可知，根节点的编号是1，节点号不包含叶子节点，假设一个满二叉树前序遍历为：ABDECFG
      A
      |
    |   |
    B   C
    |   |
   | | | |
   D E F G
A的编号为1，ABCDEFG的编号依次为1234567，G的编号为7，树高度h为2(从0开始编号)
节点号(不含叶子节点)N<2^2 => 3<4
叶子节点DEFG=4,5,6,7 => 2^2， 2^2+1，2^2+2，2^2+3
比方说第2级(从0级开始)第0个节点号为：2^2+0=4 (D)

LMS私钥的格式是实现的内部问题，本文档不尝试对其进行定义。一种可能性是，它可能由2<sup>h</sup> LM-OTS私钥的OTS_PRIV[]数组和尚未使用的下一个LM-OTS私钥的叶编号q组成。OTS_PRIV[]的第q个元素是使用带有标识符I，q的算法0生成的。创建LMS私钥时，叶编号q初始化为零（==即q取值范围[0,2<sup>h</sup>-1]==）。程序如下：

//标准文档没有对其进行定义
//自定义：整个LMS系统的私钥（一次性计算所有私钥）
typedef struct {
    uint32_t lms_type; //lms算法类型
    uint32_t ots_type; //ots算法类型
    //2^h为叶节点数，LM-OTS规定了私钥=ots_type||I||q||x[0]||...||x[p]，其中x[i]=H(I||q||u16(i)||ff||seed)
    uint8_t  lm_ots_key[2^h][32];//32为sha256输出字节长度，已经是计算完成好的私钥（q和seed不需要保存，q是从0到2^h-1的遍历） 
    uint32_t q; //尚未使用的叶编号（下一个签名要计算的密钥编号）
    uint8_t I[16]; //LMS私钥的16字节标识符
} lms_sk_t;

//自定义：考虑lm_ots_key存储太大，私钥可以实时计算，根据I, q和seed
//对于整个LMS系统，OTS私钥共2^h个
typedef struct {
    uint32_t lms_type; //lms算法类型
    uint32_t ots_type; //ots算法类型
    uint8_t  seed[16]; //随机化种子,用于实时生成私钥，LM-OTS规定了私钥=ots_type||I||q||x[0]||...||x[p]，其中x[i]=H(I||q||u16(i)||ff||seed)
    uint32_t q; //尚未使用的叶编号（下一个签名要计算的密钥编号）,q的取值范围[0,2^h-1]
    uint8_t I[16]; //LMS私钥的16字节标识符
} lms_sk_t;

typedef struct {
uint32_t lms_type;   //lms算法类型
uint32_t lm_ots_type;//lm_ots算法类型
uint8_t pk_root[32]; //sha256哈希值
uint8_t I[16];       //LMS公私钥16字节唯一标识符
} scl_lms_pk_t

//即OTS_PUB_hash[i]=K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) // D_PBLC=0x8080 
for(i=0;i<p;i++)//LMS叶编号
{
    //计算LM-OTS私钥
    tmp[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED)
    //计算LM-OTS公钥
    for(j=0;j<2^w-1;j++)
    {
        tmp[i] = H(l || u32str(q) || u16str(i) || u8str(j) || tmp[i])
    }
}
K = H(l || u32str(q) || u16str(D_PBLC) || tmp[0] || ... || tmp[p-1])//D_PBLC=0x8080


for(r=2^(h+1)-1;r>0;r--)//r代表所有节点包含叶子节点
{
    if (r >= 2^h)
        //散列LM-OTS公钥
        T[r] = H(I||u32str(r)||u16str(D_LEAF)||ost_pub_hash[r-2^h])//D_LEAF值0x8282
    else
        //合并散列左右节点, 处理的是一个内部节点——也就是说，一个节点有两个子节点，需要合并
        T[r] = H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])//D_INTR值0x8383
}

//公钥标准格式：u32str(lmstype) || u32str(otstype) || I || T[1]
pk_root = T[1]

top=0
uint8_t T_h_stack[25+1][32];
uint32_t T_idx_stack[25+1];

//计算LMS所有叶节点LM-OTS公钥，最原始计算，不考虑并行hash，不考虑资源优化
for(q=0;q<2^h;q++) //LMS叶编号
{
    H_init(ctx0)
    H_update(ctx0, I, 16)
    H_update(ctx0, q, 4)
    H_update(ctx0, D_PBLC, 2)//D_PBLC=0x8080

    for(i=0;i<p;i++)
    {
        //计算LM-OTS私钥
        H_init(ctx1)
        H_update(ctx1, I, 16)
        H_update(ctx1, q, 4)
        H_update(ctx1, i, 2)
        H_update(ctx1, 0xff, 1)
        H_update(ctx1, SEED, 32)
        tmp1 = H_final(ctx1)

        //计算LM-OTS公钥
        for(j=0;j<2^w-1;j++)
        {
            H_init()
            H_update(ctx1, I, 16)
            H_update(ctx1, q, 4)
            H_update(ctx1, i, 2)
            H_update(ctx1, j, 1)
            H_update(ctx1, tmp, 32)
            tmp1 = H_final(ctx1)
        }
        H_update(ctx0, tmp1, 32)
    }

    //LM-OTS公钥
    tmp0 = H_final(ctx0)
    //散列LM-OTS公钥
    r = i + (1<< h) //计算叶节点在Merkel树编号
    tmp0 = H(I||u32str(r)||u16str(D_LEAF)||tmp0)//D_LEAF值0x8282

    //计算LMS根公钥
    if (i != 0)
        top++;

    // 压栈
    T_h_stack[top] = tmp0
    T_idx_stack[top] = i + (1<< h)

    while (top >= 1) //至少存在两个节点，判断是否需要合并
    {
        // 判断top两个节点是否是相邻节点
        if (T_idx_stack[top] == (T_idx_stack[top - 1] + 1))
        {
            //更新父节点编号
            T_idx_stack[top-1] = T_idx_stack[top-1] / 2

            //合并计算hash更新到父节点: H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])
            r = T_idx_stack[top-1]
            r = ((r << 24) | ((r & 0x0000FF00) << 8) | ((r & 0x00FF0000) >> 8) | (r >> 24));
            H_Init(ctx)
            H_update(ctx, I_buf, 16)
            H_update(ctx, &r, 4)
            H_update(ctx, intr_buf, 2)
            H_update(ctx, T_h_stack[top-1], 32)
            H_update(ctx, T_h_stack[top], 32)
            H_final(ctx, T_h_stack[top - 1])

            //更新top
            top--;
        }
        else
        {
            break;
        }
    }
}

return T_h_stack[0]

//pqc ram一些存储
uint32_t  top=0xffffffff；
uint8_t h_stack[25][32]
uint8_t h_tmp0[32]
uint32_t tmp_r

//pqc ram一些存储
hash_ip_num = m+1         //假设可以同时使用m+1个hash IP,chain链并行m条
uint32_t tmp_m            //临时存储
uint8_t sk[m][16+4+2+1+32] //z[i]=I||u32str(q)||u16str(i)||u8str(j)||x

//预处理待hash的m条链数据，I和q,seed存储
for(k=0; k<m; k++)
{
    memcpy(sk, I, 16)
    memcpy(sk+16, q, 4)
    memcpy(sk+23, SEED, 32)
}

//计算LMS所有叶节点LM-OTS公钥
for(q=0;q<2^h;q++) //LMS叶编号
{
    H_init(hw_idx_0)
    H_update(hw_idx_0, I, 16)
    H_update(hw_idx_0, q, 4)
    H_update(hw_idx_0, D_PBLC, 2)//D_PBLC=0x8080

    for(i=0;i<p;;)
    {
        //获取本次并行的chain数量
        if ((p-i) >= m)
        {
            tmp_m = m
            i += m 
        }
        else
        {
            tmp_m = p-i
            i = p
        }

        //并行计算m个LM-OTS私钥
        for(k=0; k<tmp_m; k++)
        {
            sk[k].i = i //在sk中更新i值
            sk[k].j = 0xff //在sk中更新j值
            H_start(hw_idx_k+1, sk[k], 16+4+2+1+32) //启动hash计算
        }

        //等待m个LM-OTS私钥计算完成
        for(k=0; k<tmp_m; k++)
        {
            wait H(hw_idx_k+1)
            sk[k].x = H_get(hw_idx_k)
        }

        //并行计算m个LM-OTS公钥
        for(j=0;j<2^w-1;j++)
        {
            for(k=0; k<tmp_m; k++)
            {
                sk[k].j = j //在sk中更新j值
                H_start(hw_idx_k+1, sk[k], 16+4+2+1+32) //启动hash计算
            }

            //等待m个链hash计算完成
            for(k=0; k<tmp_m; k++)
            {
                wait H(hw_idx_k+1)
                sk[k].x = H_get(hw_idx_k)
            }
        }
        //将m个pk合并计算
        for(k=0; k<tmp_m; k++)
            H_update(hw_idx_0, sk[k].x, 32)

        if ((p-i) >= m)
            i += m 
        else
            i = p
    }

    //获取LM-OTS公钥
    h_tmp0 = H_final(hw_idx_0)
    //散列LM-OTS公钥
    r = i + (1<< h) //计算叶节点在Merkel树编号
    h_tmp0 = H(hw_idx_0, I||u32str(r)||u16str(D_LEAF)||h_tmp0)//D_LEAF值0x8282

    j = i;
    while ((j % 2) == 1) //至少存在两个节点 
    {
        r = (r - 1) / 2;
        j = (j - 1) / 2;
        tmp_r  = ((r << 24) | ((r & 0x0000FF00) << 8) | ((r & 0x00FF0000) >> 8) | (r >> 24));
        H_Init(hw_idx_0);
        H_update(hw_idx_0, I_buf, 16);
        H_update(hw_idx_0, &tmp_r, 4);
        H_update(hw_idx_0, 0x8383, 2);
        H_update(hw_idx_0, h_stack[top], 32);
        H_update(hw_idx_0, node, 32);
        h_tmp0 = H_final(hw_idx_0);
        top--;
    }
    top++;
    memcpy(h_stack[top], node, 32);
}

return h_stack[top]

enum lmots_algorithm_type {
 lmots_reserved       = 0,
 lmots_sha256_n32_w1  = 1,
 lmots_sha256_n32_w2  = 2,
 lmots_sha256_n32_w4  = 3,
 lmots_sha256_n32_w8  = 4
};
struct lms_key_n32 {
    lmots_algorithm_type ots_alg_type;
    opaque I[16];
    opaque K[32];
};

//自定义：这里我理解为私钥和公钥的密钥对结构体定义
struct lms_pubkey {
    uint32_t lms_type; //lms算法类型
    uint32_t ots_type; //ots算法类型
    uint8_t K[32]; //K=H(u32str(type)||u32str(otstype)||I||T[1])，这里的type指lms的type，标准里面指定的type暂时理解为不保存在结构体中，由外部保存
};

//lms公钥结构体
typedef struct {
uint32_t lms_type;   //lms算法类型
uint32_t lm_ots_type;//lm_ots算法类型
uint8_t pk_root[32]; //sha256哈希值
uint8_t I[16];       //LMS私钥的16字节标识符
} scl_lms_pk_t

//计算LMS所有叶节点LM-OTS公钥，最原始计算，不考虑并行hash，不考虑资源优化
for(q=0;q<2^h;q++) //LMS叶编号
{
    for(i=0;i<p;i++)
    {
        //计算LM-OTS私钥
        tmp[i] = H(I || u32str(q) || u16str(i) || u8str(0xff) || SEED)
        //计算LM-OTS公钥
        for(j=0;j<2^w-1;j++)
        {
            tmp[i] = H(I || u32str(q) || u16str(i) || u8str(j) || tmp[i])
        }
    }
    OTS_PUB_HASH[q] = H(l || u32str(q) || u16str(D_PBLC) || tmp[0] || ... || tmp[p-1])//D_PBLC=0x8080
}

//计算LMS根公钥，最原始计算，不考虑并行hash，不考虑资源优化
for(r=2^h-1;r>0;r--)
{
    if (r >= 2^h)
        //处理一个叶节点（因此仅散列一个LM-OTS公钥）,可以看出D_LEAF和D_INTR区别
        T[r] = H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h])//D_LEAF值0x8282
    else
        //处理的是一个内部节点——也就是说，一个节点有两个子节点，需要合并
        T[r] = H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])//D_INTR值0x8383
}

//公钥标准格式：u32str(lmstype) || u32str(otstype) || I || T[1]
pk_root = T[1]

typedef struct {
uint8_t sig[LMS_SIG_MAX_LEN]; //签名值
uint32_t siglen; //签名值长度，取决于参数集lms_ots的p和lms的h
} scl_lms_sig_t

//合并私钥结构体
//自定义：考虑lm_ots_key存储太大，私钥可以实时计算，根据I, q和seed
//对于整个LMS系统，OTS私钥共2^h个
struct lms_privkey {
    uint32_t lms_type; //lms算法类型
    uint32_t ots_type; //ots算法类型
    uint8_t  seed[16]; //随机化种子,用于实时生成私钥，LM-OTS规定了私钥=ots_type||I||q||x[0]||...||x[p]，其中x[i]=H(I||q||u16(i)||ff||seed)
    uint32_t q; //尚未使用的叶编号（下一个签名要计算的密钥编号）,q的取值范围[0,2^h-1]
    uint8_t  I[16]; //LMS私钥的16字节标识符
    uint8_t  *msg;
    uint8_t  *msg_len;
};

//在标准3.3章节中，正式将lmots_signature做了定义，占用的范围参考定义对应的lmots_signature_nXX_pXX
   enum lmots_algorithm_type {
     lmots_reserved       = 0,
     lmots_sha256_n32_w1  = 1,
     lmots_sha256_n32_w2  = 2,
     lmots_sha256_n32_w4  = 3,
     lmots_sha256_n32_w8  = 4
   };

   struct lmots_signature_n32_p265 {
     bytestring32 C;
     bytestring32 y[265]; //y的范围即p的值，p的值由lmots_algorithm_type决定参数值
   };

   struct lmots_signature_n32_p133 {
     bytestring32 C;
     bytestring32 y[133];
   };

   struct lmots_signature_n32_p133 {
     bytestring32 C;
     bytestring32 y[133];
   };

   struct lmots_signature_n32_p67 {
     bytestring32 C;
     bytestring32 y[67];
   };

   struct lmots_signature_n32_p67 {
     bytestring32 C;
     bytestring32 y[67];
   };

   struct lmots_signature_n32_p34 {
     bytestring32 C;
     bytestring32 y[34];
   };

   struct lmots_signature_n32_p34 {
     bytestring32 C;
     bytestring32 y[34];
   };

   union lmots_signature switch (lmots_algorithm_type type) {
    case lmots_sha256_n32_w1:
      lmots_signature_n32_p265 sig_n32_p265;
    case lmots_sha256_n32_w2:
      lmots_signature_n32_p133 sig_n32_p133;
    case lmots_sha256_n32_w4:
      lmots_signature_n32_p67  sig_n32_p67;
    case lmots_sha256_n32_w8:
      lmots_signature_n32_p34  sig_n32_p34;
    default:
      void;   /* error condition */
   };

                                Root
                                 |
                 ---------------------------------
                 |                               |
               T[2]*                          T[3]**
                 |                               |
          ------------------            -----------------
          |                |            |               |
       T[4]**           T[5]*         T[6]            T[7]
          |                |            |               |
      ---------       ----------     --------       ---------
      |       |       |        |     |      |       |       |
     leaf    leaf    OTS  leaf**   leaf   leaf    leaf    leaf

//获取OTS公钥，Kc是计算指定叶子节点的OTS公钥，占用32字节
Q = H(l || u32str(q) || u16str(D_MESG) || C || message)//D_MESG=0x8181
for ( i = 0; i < p; i = i + 1 ) 
{
    a = coef(Q || Cksm(Q), i, w) 
    tmp = y[i] 
    for ( j = a; j < ((1<<w) - 1); j = j + 1 ) 
    {
        tmp = H(l || u32str(q) || u16str(i) || u8str(j) || tmp) 
    } 
    z[i] = tmp 
} 
Kc = H(l || u32str(q) || u16str(D_PBLC) || z[0] || z[1] || ... || z[p-1])
//对指定叶子节点OTS公钥做hash 
node_num = (1<<h) + q //根据指定叶编号q获取整颗树节点编号（包含叶子节点和非叶子节点）
tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc) //D_LEAF为0x8282
i = 0 
while (node_num > 1) //一共执行h次
{ 
    if (0!= (node_num&1))
        //当前节点是右子节点
        tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp) //D_INTR为0x8383
    else
        // 当前节点是左子节点
        tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i]) 
    //获取上一层父节点
    node_num = node_num/2 
    i = i + 1 
} 
Tc = tmp

return 

typedef struct {
uint32_t cfg;         //keygen, sign, verify, []:init/update/final, []:决定是否吐出hash中间值
volatile uint32_t sw; //result
} scl_base_task_t

typedef struct {
uint32_t lms_type;   //lms算法类型
uint32_t lm_ots_type;//lm_ots算法类型
uint8_t pk_root[32]; //sha256哈希值，参与计算的I值存储在私钥，验签不需要计算该
uint8_t I[16];       //LMS私钥的16字节标识符
} scl_lms_pk_t

typedef struct {
uint32_t lms_type;    //lms算法类型
uint32_t lm_ots_type; //lm_ots算法类型
uint8_t  sk_seed[16]; //种子, 用于ots私钥生成
uint32_t q;          //尚未使用的叶编号（用于下一次签名）,lms_type决定q的取值范围[0,2^h-1]
uint8_t I[16];       //LMS私钥的16字节标识符
} scl_lms_sk_t

typedef struct {
//sig = u32str(q)||lmots_signature||u32str(type)||path[0]||path[1]||path[2]||...||path[h-1]
//lmots_signature = u32str(type)||C||y[0]||...||y[p-1]
uint32_t lms_type;    //lms算法类型
uint32_t lm_ots_type; //lm_ots算法类型
uint8_t sig[LMS_SIG_MAX_LEN]; //4+(32+32*p)+4+(32*h), p取最大值265，h取最大值25,取决于参数集选择p和h
uint32_t siglen; //签名长度取决于参数集lms_ots的p和lms的h
} scl_lms_sig_t


typedef struct {
scl_base_task_t base;
scl_lms_pk_t *lms_pk;
scl_lms_sk_t *lms_sk;
scl_lms_sig_t *lms_sig;
uint8_t *msg;
uint32_t msglen;
uint8_t *l_tmp;
uint32_t *l_tmplen;
} scl_lms_task_t

为了提高对攻击的安全性，这些攻击会分散他们对哈希函数多次调用的精力，Leighton和Micali引入了一个“安全字符串”，该字符串对于该函数的每次调用都是不同的。每当此进程计算散列时，被散列的字符串将以以下字段形成的字符串开始。这些字段将出现在我们计算散列值的固定位置，因此我们列出这些字段在散列中的位置。组成此字符串的字段如下所示：

//demo w8 h5
  keyname.prv（私钥文件）- 总长度56字节

  实际数据分析：
  00000000: 0000 0000 0000 0001 64ff ffff ffff ffff  ........d....... //counter||set_depress
  00000010: 0000 0000 0000 0000 0000 0000 0000 0000  ................ //seed
  00000020: 0000 0000 0000 0000 0000 0000 0000 0000  ................
  00000030: 1000 0000 0000 0000 0000 0000 0000 0000  ................ //I

  keyname.prv = str8(q)||str8(set)||str32(seed)||str16(I)

  1. 字节0-7 (PRIVATE_KEY_INDEX): 00 00 00 00 00 00 00 01    //q - 4byte
    - 当前签名计数器，值为1（大端字节序）
    - 表示已经使用了1次签名
  2. 字节8-15: 64 ff ff ff ff ff ff ff
    - 参数集压缩数据的一部分
    - 64 = 十进制100，可能是w参数或其他参数配置
  3. 字节16-47: 全0  //seed
  4. 字节48-63: 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 //I

//demo w8 h5
  keyname.pub（公钥文件）- 总长度60字节

  实际数据分析：
  ⎿  00000000: 0000 0001 0000 0005 0000 0004 1000 0000  ................
     00000010: 0000 0000 0000 0000 0000 0000 ee75 d868  .............u.h
     00000020: cced dfdd 57d1 0a9c 889a 6df4 1e03 efde  ....W.....m.....
     00000030: 2af2 c6e0 5831 d594 6e75 3b0b            *...X1..nu;.

  keyname.pub = str4(HSS high)||str4(lms_type)||str4(lm ots type)||str16(I)||str32(root)

  1. 前4字节 - HSS层级数
    - 格式：4字节大端字节序整数
    - 含义：HSS签名方案的层级数量
  2. 第4-7字节 - LM类型参数
    - 格式：4字节大端字节序整数
    - 含义：Merkle树的参数类型
  3. 第8-11字节 - LM-OTS类型参数
    - 格式：4字节大端字节序整数
    - 含义：一次性签名方案的参数类型
  4. 第12-27字节 - 标识符I
    - 长度：16字节 (I_LEN = 16)
    - 含义：密钥对的唯一标识符
  5. 第28-59字节 - 根哈希值
    - 长度：32字节 (MAX_HASH = 32，对于SHA-256)
    - 含义：Merkle树的根哈希值，用于验证签名

//demo w8 h5 16进制
//80字节
3132333435363738313233343536373831323334353637383132333435363738313233343536373831323334353637383132333435363738313233343536373831323334353637383132333435363738

//demo w8 h5

//HSS层级数减1（L-1）
00000000
// q (4 bytes)
00000002
// LMOTS_SHA256_N32_W8 (4 bytes)
00000004
// C (32 bytes)
df5f5fdeddd39038432ea36f9afd5510075fd03609106d81a457ef70003a019f
// y[0]||...||y[p-1] (34*32 = 1088 bytes)
c371ecb5b5d5bbda59bc1098ce8a1e7ae62676a30d14707e305c8b3b36213d3a
19ce9cd221a5586125f9865d9ad443d1743573607006d0b3fe40d4707aa35325
300c80d76ad23c6f0a8c116d4c3d47809994706058bd64b6d78e4ca57a77f9c9
b4fbc38a4d040e0eca7fd0060e5a616249076a99faf4b9ec2c440070c9de52f2
f43973c513b1b38419218debd34104991219dbbf3e6969e71cd5911a6d352657
6fcb890518d2a360fad59e3ecf43b349481ca7b2498f6f4c160aceeaa357e74e
64d152489d354ae1e34d01bcb0da7736d5e4abca3a6a4f5485b63af76aad651a
197a74fa1233002bc0cd87608d4bb4154a489e0f500a22d31b04c79c2303d621
8332f8cd1910586bdc621f5841fd3a624033ba9255b6a855e25efc0fbcec806d
9bd982146f6fcbc52d25df802809f4d194edcd41aad83a2554851a14440ede1d
607cad6eecae5e693fb37334d65675866b898b469ff11bb204f6f7ad86e9a163
005d8bf485488d6a8c6773006ebc571e87487e5892e73c2abb6dc00d7f5bbadd
c34347a46517e410f70625c084cd3d85c7c17dab9fd2b5ad47c2fa80dc745b8d
07b6c5a8145604bf1047ae539b32599549ee7dc1e1a20237c90ae437e0742845
174256d2ea15e9e8575594e1823af0c2fa43af99fb57065f1752c2d0751087a5
a9f3818bef618978d80b7d8fcf215fca116b49b859b94092ed232153caaed6d6
113c50b07c12e2173b29eb9ebf44c03111867c5c6e19eb0c1155ea231c76ebda
f4d17e2d12376f9f1722fc0a3789874d0b268d12db65c6510df41af8e7b91b0e
5211831f7954085fc2d29cc5664b3c7531e889d123638be117adfa1db6b4d12e
ec4195a79a1159e6dd0b9dd2e81fed24ce33527d2b6cc6e30c6f7743481e6621
bcf335ccb43dcc6cf2437d62b530dae37b07e0f04bfaf91c92f31d3ba00fdeef
4fc0c52bc2aa796a1b1765e66999fb9f93ae6c33689dc802e49fb316e95e8119
66065a3b3bcd2ad12ac01cafaec628f2a842d47b6d020c58f986d67177804658
85b7a29044a85b069ffcdb5ecddec5ba7122ba4f3888a32a47ebe4c44702e89f
ebab940f7c5fd9ba92aeef8363e7da92acb79681f50c58b85ff0ba3e2f5731e2
e509260844b808d0023a46b15c133243a1e4d753c939d99e9d0d5a7b5e74a475
2a8d654a69b99c41fc445ff843dba809b97682a0197066682973fc9e14c97378
a52dd3b575b55d8a7f75b7963f676836321c0e07d19367d8cb41b813fbbc9a00
cdc2a66116c889752fb88fcffa09b7153d7d67c167800271d47f6041c7577a19
8882e6d263a619f05e1a067bd4eadf90866f5a5282daf6d786cad134b25c118a
e1328c4db11934de8ad031f4da53051c2d3a3ec6f21af748e90cb7a1026b910e
c3092eb023f4cd74745e99c5e38f725a296b47d9d7ce1d9471bcdd7d75369e76
2ce89c663aefe2ac80355bb9ae4d7f6dad1f7a30eea7a4ed376088a8909c7468
11078e27e7a40ab32bd58a8082490b515f164f2f84559e49b1ab142c3f90d05c
// LMS_SHA256_M32_H5 (4 bytes)
00000005
// path[0]||...||path[h-1] (5*32 = 160 bytes)
abc80a13a7910f4af6efca10be4575edb5c336bc5c1a6d991d4edd898bbbb50a
ffd75ef07a4c1e2c1f51dc10a9acf54fbe8ab93b79fcd820ca6c8ec7f249609c
1efde58c816132cc74beed6b5790615faf2d499cf06eca583466a1fde205d2a3
d348a557e94b9981f7e0609aa3d82691aa45f87ab95b493a42fdd0188f337286
4c446423d7cc93b9ed731be8b1bf40c6a97f83f325be7c2c440ac2a5fe59d087

1. If need ti sign 0, publish x = x0
2. If need to sign 1,pushlish x=x1
3. Verify by H(x) = y0 or y1

Pk ：  y0     y1
     h()↑   h()↑
Sk:    x0     x1

Pk ：  y1,0     y1,1    y2,0    y2,1   y3,0   y3,1
       h()↑     h()↑     h()↑   h()↑   h()↑   h()↑
Sk:    x1,0     x1,1    x2,0    x2,1   x3,0   x3,1

Pk:    H3(x1)   H3(x2)   H3(x3)   H3(x4)  H3(x5)  H3(x6)
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑
Sk2:    H2(x1)   H2(x2)   H2(x3)   H2(x4)  H2(x5)  H2(x6)
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑
Sk1:    H(x1)    H(x2)    H(x3)    H(x4)   H(x5)   H(x6)
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑
Sk0:     x1       x2       x3       x4      x5      x6

Pk:    H3(x1)   H3(x2)   H3(x3)   H3(x4)  H3(x5)  H3(x6)  ... H3(xcs1)  H3(xcs2) 
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑   ...  h()↑       h()↑
Sk2:    H2(x1)   H2(x2)   H2(x3)   H2(x4)  H2(x5)  H2(x6) ... H2(xcs1)  H2(xcs2) 
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑   ...  h()↑       h()↑
Sk1:    H(x1)    H(x2)    H(x3)    H(x4)   H(x5)   H(x6)  ... H(xcs1)    H(xcs2) 
        h()↑     h()↑     h()↑     h()↑    h()↑    h()↑   ...  h()↑       h()↑
Sk0:     x1       x2       x3       x4      x5      x6    ...  xcs1        xcs2

取代hash碰撞攻击，F可以是一个PRF或抗二次原像攻击的hash函数
更小的签名具有相同的安全性

Pk:     C3k=Fk(C2k ⊕ r3)  C3k=Fk(C2k ⊕ r3)  ... C3k=Fk(C2k ⊕ r3)   C3k=Fk(C2k ⊕ r3) 
           r3()↑                r3()↑                  r3()↑             r3()↑ 
Sk2:    C2k=Fk(C1k ⊕ r2)  C2k=Fk(C1k ⊕ r2)  ... C2k=Fk(C1k ⊕ r2)   C2k=Fk(C1k ⊕ r2) 
           r2()↑                r2()↑                  r2()↑             r2()↑ 
Sk1:    C1k=Fk(C0k ⊕ r1)  C1k=Fk(C0k ⊕ r1)  ... C1k=Fk(C0k ⊕ r1)   C1k=Fk(C0k ⊕ r1) 
           r1()↑                r1()↑                  r1()↑             r1()↑ 
Sk0:      C0k=x1               C0k=x2         ...       C0k=xcs1          C0k=xcs2 

PK         H(H(PK1)||H(PK2)||H(PK3)||H(PK4))
                |                    |
        H(H(PK1)||H(PK2))      H(H(PK3)||H(PK4))
                |                    |
           |————————|           |——————————|
       H(PK1)      H(PK2)      H(PK3)     H(Pk4)
          |           |           |          | 
       OTS-PK1     OTS-PK2     OTS-PK3    OTS-PK4
SK     OTS-SK1     OTS-SK2     OTS-SK3    OTS-SK4