3. Deterministic DSA and ECDSA (确定性 DSA 和 ECDSA)

确定性 (EC)DSA 是通过使用标准 (EC)DSA 签名生成过程 (在上一节中讨论) 在输入消息 m 上生成 (EC)DSA 签名的过程, 除了值 k 不是随机生成的, 而是通过本节中描述的过程获得。

我们使用第 2 节中描述的符号表示。

3.2. Generation of k (k 的生成)

给定输入消息 m, 应用以下过程:

a. 通过哈希函数 H 处理 m, 产生:

h1 = H(m)

(h1 是 hlen 比特的序列)。

b. 设置:

V = 0x01 0x01 0x01 ... 0x01

使得 V 的长度 (以比特为单位) 等于 8*ceil(hlen/8)。例如, 在基于八位字节的系统上, 如果 H 是 SHA-256, 则 V 设置为 32 个值为 1 的八位字节序列。请注意, 在此步骤和所有后续步骤中, 我们使用与步骤 'a' 中用于处理输入消息的相同 H 函数; 这个选择将在第 3.6 节中更详细地讨论。

c. 设置:

K = 0x00 0x00 0x00 ... 0x00

使得 K 的长度 (以比特为单位) 等于 8*ceil(hlen/8)。

d. 设置:

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

其中 '||' 表示连接。换句话说, 我们计算 HMAC, 密钥为 K, 消息为 V 的值 (当前是一个全 1 的比特序列), 后面跟着值为 0 的八位字节, 然后是编码的私钥 x, 然后是 h1, 后者本身是哈希消息的结果。HMAC 仍然使用相同的哈希函数 H。得到的输出长度为 hlen, 成为 K 的新值。

e. 设置:

V = HMAC_K(V)

f. 设置:

K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))

请注意, 这与步骤 'd' 中的计算相同, 除了 0x00 已被替换为 0x01。

g. 设置:

V = HMAC_K(V)

h. 应用以下过程, 直到产生适当范围内的 k 值:

设置 T 为空序列。T 的长度 (以比特为单位) 在此步骤开始时为 0。
当 T 的长度 (以比特为单位) 小于 qlen 时, 执行以下操作:
```
V = HMAC_K(V)
T = T || V
```
使用 bits2int 转换将 T 转换为整数, 然后对 q 取模, 计算:
```
k = bits2int(T) mod q
```
如果该值对于 k 是合适的 (即, 它在 [1, q-1] 范围内且与为同一密钥生成的任何以前的签名产生的值不同), 则退出循环。
否则, 计算:
```
K = HMAC_K(V || 0x00)
V = HMAC_K(V)
```
并循环 (尝试生成新的 T, 以及新的 k 值)。

生成的值 k 应在签名生成过程的步骤 3 中使用 (参见第 2.4 节)。

请注意, 当从 T 生成 k 时, bits2int 的结果与 q 比较, 而不是对 q 取模约简。如果值不在 1 和 q-1 之间, 则过程循环。执行简单的模约简会引入偏差, 这将对签名安全性有害。

3.3. Alternate Description of the Generation of k (k 生成的替代描述)

上一节中描述的过程实际上源自 "HMAC_DRBG" 伪随机数生成器, 在 [SP800-90A] 和 [X9.62] 的附录 D 中描述。使用 [SP800-90A] 中的术语, k 的生成可以描述如下:

a. 使用 HMAC 实例化 HMAC_DRBG, 参数化为与用于处理待签名消息的相同哈希函数 H。实例化参数为:

requested_instantiation_security_strength
将此参数设置为 HMAC_DRBG 实现在使用 H 作为基础哈希函数时将接受的任何值。

prediction_resistance_flag
将此参数设置为 "false"。

personalization_string
将此参数设置为 "Null" (空比特序列)。

entropy_input
使用 int2octets(x) 作为熵串。

nonce
使用 bits2octets(H(m)) 作为 nonce。

请注意, 后两个参数本身不是 HMAC_DRBG 实例化函数的参数; 相反, 这些值在实例化期间从内部 Get_entropy_input 函数请求。对于确定性 (EC)DSA, 我们希望 HMAC_DRBG 使用我们指定的熵串和 nonce 运行, 而不访问实际的熵源。

b. 通过从 HMAC_DRBG 请求 qlen 比特并使用 bits2int 转换将结果比特转换为整数来生成 k 的候选值。重复此步骤, 直到获得非零、小于 q 且适合 (EC)DSA 的值 (参见第 3.4 节)。

请注意, 我们为每个签名生成过程实例化一个新的 HMAC_DRBG 实例。生成比特时没有 "个性化字符串" 和 "附加输入"。HMAC_DRBG 的重新种子函数从未被调用, 无论是外部还是作为内部 HMAC_DRBG 处理的结果。

如上所示, 我们使用私钥的编码作为 "熵串", 使用哈希消息 (通过 bits2octets 截断和扩展) 作为 "nonce"。在 HMAC_DRBG 中, 熵串和 nonce 简单地连接到初始种子中; 因此, "熵" 和 "nonce" 之间的分割是相当任意的。为每个使用 qlen 比特应该与大多数 HMAC_DRBG 实现输入要求兼容。

3.4. Usage Notes (使用注意事项)

对于 DSA 或 ECDSA, 值 k 用于计算签名的前半部分, 称为 r (参见第 2.4 节)。DSA 和 ECDSA 标准规定, 如果 r 为零, 则应选择新的 k。在这种情况下, 本文档指定值 k 是 "不合适的", 生成过程应继续循环。

这种情况极不可能发生。实际上, 它需要相当大的计算工作 (类似于破坏哈希函数的原像抵抗性) 来找到导致 r 为零值的私钥和消息; 因此纯粹偶然遇到这种情况被认为是不太可能的, 攻击者无法用精心制作的消息强制执行它。实际上, 这样的代码路径不会被触发, 因此可以在很少优化的情况下实现。

前几节中描述的过程模仿了 [X9.62] 附录 D 中描述的使用 "HMAC_DRBG" 伪随机数生成器的 "Approved" k 生成过程。主要区别在于我们使用私钥 x 和哈希消息 H(m) 的连接作为伪随机数生成器 (PRNG) 种子。如果使用 n 比特的 "安全级别", 则 HMAC_DRBG 应使用至少 n+64 比特的种子熵; 然而, 密钥 x 也应该用那么多熵生成, 并且 x 的长度是 qlen, 它至少等于 2*n, 因此大于 n+64 (根据标准规定的 DSA 和 ECDSA 要求 qlen >= 160)。因此可以认为确定性 ECDSA 满足 [X9.62] 附录 D 的熵要求。

我们使用 bits2octets(H(m)) 而不是 H(m), 以便于集成。实际上, 许多现有签名系统卸载消息哈希; 签名引擎 (可以访问私钥) 仅接收 H(m)。在某些应用中, 数据带宽受到限制, 仅将 H(m) 的前 qlen 比特传输到签名引擎, 基于 bits2int 转换将忽略后续比特。可能在某些系统中, 截断的 H(m) 可以在外部对 q 取模约简, 因为这是 (EC)DSA 对哈希消息执行的第一件事。通过 bits2octets 的定义, 确定性 (EC)DSA 可以应用于相同的输入。

3.6. Variants (变体)

确定性 (EC)DSA 规范的许多部分是相当任意的, 但出于互操作性原因做出了选择。本节讨论一些可能的变体。

使用的哈希函数 H 在签名生成过程中用于两个不同的目的: 首先处理输入消息, 然后作为 HMAC 的基础 (HMAC 本身也是哈希函数)。在本文档中, 我们规定对这两种用法使用相同的哈希函数。然而, 这不是强制性的; 将不同的函数用于这两个角色是可能的。主要缺点是测试向量不能涵盖所有组合; 使用单一哈希函数简化了互操作性测试。

int2octets 和 bits2octets 的定义导致 rlen 比特的输出 (即 qlen 向上舍入到下一个 8 的倍数), 并且它们在使用时实际上最多只产生 qlen 比特的熵。可以定义相同的函数, 使其输出恰好为 qlen 比特; 然而, 这会使实现稍微复杂一些, 因为许多编程语言和框架倾向于在八位字节的序列上工作, 而不是比特的序列。另一方面, 舍入 qlen 最多增加 7 比特, 这在 PRNG 种子的上下文中可以忽略不计。

在这个规范中, 我们规定了一个在特殊情况下循环的过程, 其中 k (从 T 通过 bits2int 获得) 不在适当的范围内, 或者将导致为 r 生成零值。然而, 这两种情况实际上从未发生。后一种情况 (计算的 r 为零) 可能仅由于软件错误而发生 (例如, 椭圆曲线参数在程序运行时被损坏)。因此, 实现可能会选择将此类情况简单地视为不可恢复的错误, 并简单地中止签名计算, 而不是循环。

3. Deterministic DSA and ECDSA (确定性 DSA 和 ECDSA)