rfc6979: ECDSA和DSA的确定性用法

Posted on Edited on

本文档定义了确定性数字签名生成程序。
此类签名与标准数字签名算法 (DSA) 和椭圆曲线数字签名算法 (ECDSA) 数字签名兼容，并且可以使用未经修改的验证器进行处理，无需了解其中描述的过程。
确定性签名保留了与数字签名相关的加密安全功能，但可以更轻松地在各种环境中实现，因为它们不需要访问高质量的随机源。

DSA [FIPS-186-4] 和 ECDSA [X9.62] 是两种标准的数字签名方案。 它们在各种协议中提供数据完整性和可验证的真实性。

DSA 和 ECDSA 的一个特点是它们需要为每个签名生成生成一个新的随机值（以下称为 k）。 为了有效的安全性，必须使用加密安全过程从一组模整数中随机且一致地选择 k。 在这个过程中即使是轻微的偏斜也可能变成对签名方案的攻击。

对加密安全随机源的需求已被公认是在某些架构中部署 DSA 和 ECDSA 签名方案的障碍，其中安全随机数生成具有挑战性，特别是嵌入式系统，如智能卡。 在这些系统中，RSA 签名算法，如公钥密码标准 (PKCS) #1 [RFC3447]（使用“类型 1”填充，而不是概率签名方案 (PSS)）和 ISO 9796-2 [ISO-9796-2]，通常是首选，即使它在计算上更昂贵，因为 RSA（具有此类填充方案）是确定性的，因此不需要随机源。

DSA 和 ECDSA 的随机特性也使得实现更难测试。自动化测试无法可靠地检测实现是否使用了足够高质量的随机源。 这使得实施过程更容易受到灾难性故障的影响，通常在系统部署并成功攻击后发现。

通过使用确定性过程生成“随机”值 k，可以将 DSA 和 ECDSA 转化为确定性方案。 该过程必须满足一些密码学特征，以保持签名方案所期望的可验证性和不可伪造性； 即，对于不知道签名私钥的人，从输入消息到相应 k 值的映射必须在计算上与随机且统一选择的函数（从消息集到可能的 k 值集）将返回的内容没有区别。

本文档描述了这样一个过程。 它具有以下特点：

  • 生成的签名与普通 DSA 和 ECDSA 保持完全兼容。 验证签名的实体不需要更改，甚至不需要知道用于生成 k 的过程。
  • 密钥对生成没有改变。 现有的私钥可以与确定性 DSA 和 ECDSA 一起使用。
  • 使用确定性 DSA 和 ECDSA 意味着没有任何秘密或公共价值的额外存储要求。
  • 确定性 DSA 和 ECDSA 可以应用于与普通 DSA 和 ECDSA 相同的输入，即对要签名的消息计算的哈希值，具有加密安全的哈希函数。

在本文档中指定的确定性 (EC)DSA 的定义中采取了一些相对随意的选择。
这样做是为了使其尽可能普遍适用，从而最大限度地提高包含的测试向量的有用性。 有关一些可能的变体的讨论，请参见第 3.6 节。

需要注意的是，密钥对的生成仍然需要一个随机源。
在随机性存在问题的嵌入式系统中，通常可以安排在更可控的条件下生成密钥对（例如，在特殊的智能卡初始化过程中或在宣誓代理的物理控制下）；
或者甚至可以在其他地方生成密钥并导入到设备中。
确定性 DSA 和 ECDSA 仅处理签名生成时对随机性的需求。

1.1. 需求语言

本文档中的关键词“必须”、“不得”、“需要”、“应该”、“不应”、“应该”、“不应该”、“推荐”、“可以”和“可选”是 按照 RFC 2119 [RFC2119] 中的描述进行解释。

  1. DSA 和 ECDSA 符号

在本节中，我们将简要描述 DSA 和 ECDSA 并定义我们的符号。 DSA 和 ECDSA 的完整规范可以分别在 [FIPS-186-4] 和 [X9.62] 中找到。

2.1. 关键参数

DSA 和 ECDSA 工作在一个大的素数范围上，其中群运算很容易计算，但是离散对数在现有和可预见的技术下在计算上是不可行的。 组的定义称为“关键参数”。 密钥参数可以在不同的密钥对之间共享，不会对安全产生不良影响； 这尤其是 ECDSA 的常见情况。

DSA 使用以下关键参数：

  • p：一个大素数（至少 1024 位）
  • q：一个足够大的质数（至少 160 位），它也是 p-1 的除数
  • g： 整数模 p 的 q 阶乘法子群的生成器

计算 DSA 的组由值 ‘g^j mod p’ 组成，其中 ‘^’ 表示求幂，j 的范围从 0 到 q-1（含）。组的大小是 q。

ECDSA 使用以下关键参数：

  • E 椭圆曲线，定义在给定的有限域上
  • q 一个足够大的素数（至少 160 位），它是曲线阶数的除数
  • G：点 E的 q 阶乘

将计算 ECDSA 的组由曲线点 jG（点 G 乘以整数 j）组成，其中 j 的范围从 0 到 q-1。 G 使得 qG = 0（曲线 E 上的“无穷远点”）。
组的大小是 q。请注意，这些符号与 [X9.62] 中描述的符号略有不同；
我们使用它们是为了匹配用于 DSA 的那些。

2.2. 密钥对

DSA 或 ECDSA 私钥是一个整数 x 取模 q。 相关标准规定x不得为0； 因此，x 是 [1, q-1] 范围内的整数。

DSA 或 ECDSA 公钥由私钥 x 和密钥参数计算得出：

  • 对于 DSA，公钥是整数：y = g^x mod p
  • 对于 ECDSA，公钥是曲线点：U = xG

2.3. 整数转换

设 qlen 为 q 的二进制长度。 qlen 是使 q 小于 2^qlen 的最小整数。 这是没有符号位的 q 的二进制表示的大小（请注意，q 是一个大素数，是奇数，因此避免了关于任何等于 2 的幂的整数的长度的任何歧义）。 我们定义了五个转换函数，它们处理位串、八位组和整数模 q。 qlen 是这些转换的主要参数。

在以下小节中，我们使用另外两个长度，称为 blen 和 rlen。 rlen 等于 qlen，四舍五入到下一个 8 的倍数（如果 qlen 已经是 8 的倍数，则 rlen 等于 qlen；否则，rlen 稍大，最多为 qlen+7）。 请注意，rlen 与值 r（生成的签名的前半部分）无关。 blen 是输入位序列的长度（以位为单位），可能因调用而异。 blen 可能小于、等于或大于 qlen。

2.3.1. 二进制位和八进制位

形式上，所有操作都定义在位序列上。 一个序列是有序的； 第一位是最左边的，而最后一位是最右边的。

在大多数软件系统上，（每8个）位被编排分组为八进制位（八位序列）。
二进制数据，例如散列函数的输出，可用作八位字节序列。 在适用的情况下，我们认为八位字节中的位按从最重要到最不重要的顺序排列：八位字节中的第一个（最左侧）位的数值为 128，而最后一个（最右侧）的数值为 1。