跳到主要内容

3. 确定性 DSA 和 ECDSA

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

我们使用第 2 节中描述的表示法.

3.1. 构建块​

3.1.1. HMAC​

HMAC [RFC2104] 是使用哈希函数和秘密密钥构造的消息认证码 (Message Authentication Code).在这里, 我们使用 HMAC 与相同的哈希函数 H, 该哈希函数用于在签名生成或验证之前处理输入消息.

我们用以下方式表示使用密钥 K 在数据 V 上应用 HMAC:

HMAC_K(V)

它返回长度为 hlen 的位序列 (底层哈希函数 H 的输出长度).

3.2. 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))

其中 '||' 表示连接.换句话说, 我们使用密钥 K 计算 HMAC, 对以下内容按顺序进行连接: V 的当前值,一个值为 0 的八位序列,(EC)DSA 私钥 x 的编码, 以及哈希消息 (可能由 bits2octets 转换截断和扩展).HMAC 结果是 K 的新值.请注意, 私钥 x 在 [1, q-1] 范围内, 因此是 int2octets 的适当输入, 产生 rlen 位的输出, 即整数个字节 (rlen 是 8 的倍数).

e. 设置:

V = HMAC_K(V)

f. 设置:

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

请注意, 这次 "内部字节" 是 0x01.

g. 设置:

V = HMAC_K(V)

h. 应用以下算法, 直到找到 k 的适当值:

  1. 将 T 设置为空序列.T 的长度 (以位为单位) 表示为 tlen; 因此, 此时 tlen = 0.

  2. 当 tlen < qlen 时, 执行以下操作:

    V = HMAC_K(V)
    T = T || V

  3. 计算:

    k = bits2int(T)

    如果 k 的值在 [1,q-1] 范围内, 并且适合 DSA 或 ECDSA (即, 它导致的 r 值不为 0; 参见第 3.4 节), 则 k 的生成完成.获得的 k 值用于 DSA 或 ECDSA.否则, 计算:

    K = HMAC_K(V || 0x00)
    V = HMAC_K(V)

    并循环 (尝试生成新的 T, 依此类推).

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

3.3. 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. 使用说明​

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

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

3.5. 原理​

前面几节中描述的过程模仿了 [X9.62] 附录 D 中描述的 k 的 "批准" 生成过程, 使用 "HMAC_DRBG" 伪随机数生成器.主要区别在于我们使用私钥 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. 变体​

确定性 (EC)DSA 规范的许多部分是相当任意的.可以定义不是 "确定性 (EC)DSA" 但在某些上下文中可能仍然有用的变体:

  • 可以直接使用 H(m), 而不是 bits2octets(H(m)), 作为 HMAC 输入的一部分.如第 3.5 节所述, 我们使用 bits2octets(H(m)) 是为了简化集成到已经使用 (EC)DSA 签名引擎的系统中, 通过向其发送已截断的哈希值.使用整个 H(m) 不会引入任何漏洞.

  • 可以将附加数据添加到 HMAC 的输入中, 连接在 bits2octets(H(m)) 之后:

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

    一个用例可能是在没有访问高质量随机源的系统上需要非确定性签名算法的协议.只要附加数据 k' 是非重复的 (例如, 签名计数器或单调时钟), 就足以确保 "看起来随机" 的签名在密码学方式上与普通 (EC)DSA 签名无法区分.在 [SP800-90A] 术语中, k' 是可以在生成伪随机位时设置为参数的 "附加输入".此变体可以被认为是对附加数据 k' 来源的随机性的 "增强".

  • 可以使用附加的秘密数据作为 HMAC 的输入, 而不是使用 x (私钥), 这些秘密数据与私钥一起存储并具有相同的安全措施.该附加数据的熵应至少为 n 位, 最好为 n+64 位或更多, 其中 n 是目标安全级别.拥有与私钥本身不同的附加秘密数据可以通过防止侧信道泄漏私钥的 "重放" 来帮助防御此类攻击.但是, 使用附加秘密数据会产生额外的存储要求, 并且必须保证该数据具有足够的熵.

  • 可以使用与用于处理消息的哈希函数 H 不同的哈希函数来参数化 HMAC.这在某些上下文中可能很有用, 例如, 当签名引擎必须支持多个哈希函数但只想实现一个 HMAC 实例时.但是, 这可能会降低安全性, 因为 HMAC 使用的哈希函数的强度应该至少与用于处理消息的哈希函数一样强.