2. DSA and ECDSA Notations (DSA 和 ECDSA 符号表示)

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

2.1. Key Parameters (密钥参数)

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. Key Pairs (密钥对)

DSA 或 ECDSA 私钥是对 q 取模的整数 x。相关标准规定 x 不应为 0; 因此, x 是范围 [1, q-1] 中的整数。

DSA 或 ECDSA 公钥是从私钥 x 和密钥参数计算的:

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

2.3. Integer Conversions (整数转换)

设 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. Bits and Octets (比特和八位字节)

形式上, 所有操作都定义在比特序列上。序列是有序的; 第一个比特称为最左边的, 而最后一个比特是最右边的。

在大多数软件系统上, 比特被分组为八位字节 (八个比特的序列)。二进制数据, 例如哈希函数的输出, 可作为八位字节序列使用。在适用的情况下, 我们认为八位字节内的比特从最高有效位到最低有效位排序: 八位字节内的第一个 (最左边的) 比特具有数值 128, 而最后一个 (最右边的) 具有数值 1。

2.3.2. Bit String to Integer (比特串到整数)

bits2int 转换将 blen 比特的序列作为输入, 并输出小于 2^qlen 的非负整数。它由以下步骤组成:

序列首先被截断或扩展到长度 qlen:
- 如果 qlen < blen, 则保留 qlen 个最左边的比特, 并丢弃后续比特;
- 否则, qlen-blen 个比特 (值为零) 被添加到序列的左侧 (即, 在序列顺序中的输入比特之前)。
然后使用大端约定将结果序列转换为整数值: 如果输入比特称为 b_0 (最左边) 到 b_(qlen-1) (最右边), 则结果值为:
```
b_0*2^(qlen-1) + b_1*2^(qlen-2) + ... + b_(qlen-1)*2^0
```

bits2int 转换也可以用以下方式描述: 使用大端约定将输入比特序列 (长度为 blen) 转换为整数。然后, 如果 blen 大于 qlen, 则将结果整数除以 2 的 blen-qlen 次幂 (欧几里得除法: 余数被丢弃); 在大整数算术的许多软件实现中, 该除法等效于向右移位 blen-qlen 比特。

2.3.3. Integer to Octet String (整数到八位字节串)

小于 q 的整数值 x (特别是已对 q 取模的值) 可以转换为 rlen 比特的序列, 其中 rlen = 8*ceil(qlen/8)。这是通过大端编码获得的比特序列。换句话说, 序列比特 x_i (对于 i 从 0 到 rlen-1 的范围) 使得:

x = x_0*2^(rlen-1) + x_1*2^(rlen-2) + ... + x_(rlen-1)

我们将此转换称为 int2octets。由于 rlen 是 8 的倍数 (不小于 qlen 的 8 的最小倍数), 因此结果的比特序列也是八位字节的序列, 因此得名。

2.3.4. Bit String to Octet String (比特串到八位字节串)

bits2octets 转换将 blen 比特的序列作为输入并输出 rlen 比特的序列。它由以下步骤组成:

通过 bits2int 转换将输入序列 b 转换为整数值 z1:
```
z1 = bits2int(b)
```
z1 对 q 取模, 产生 z2 (0 和 q-1 之间的整数, 含):
```
z2 = z1 mod q
```
请注意, 由于 z1 小于 2^qlen, 因此该模约简可以通过简单的条件减法来实现: 如果该值为非负, 则 z2 = z1-q; 否则, z2 = z1。
通过应用 int2octets 将 z2 转换为八位字节序列 (rlen 比特的序列)。

2.3.5. Usage (用法)

值得注意的是, int2octets 不是 bits2int 的逆操作, 即使对于长度为 qlen 的输入序列也是如此: int2octets 会在左侧添加一些比特, 而 bits2int 会在右侧丢弃一些比特。int2octets 只有在 qlen 是 8 的倍数且比特序列已经具有长度 qlen 时才是 bits2int 的逆操作。

bits2int 在标准 DSA 和 ECDSA 的签名生成和验证期间使用, 以将哈希值 (在输入消息上计算) 转换为模 q 的整数。也就是说, 通过 bits2int 获得的整数进一步对 q 取模; 由于该整数小于 2^qlen, 因此该约简可以通过最多一次减法来执行。

int2octets 在 SEC 1 [SEC1] 的第 2.3.7 节中以名称 "Integer-to-OctetString" 定义。它用于在基于 ASN.1 的结构中指定 ECDSA 私钥 (x) 的编码。

bits2octets 不在标准 DSA 或 ECDSA 中使用。我们将在确定性 (EC)DSA 的规范中使用它。

2.4. Signature Generation (签名生成)

签名生成使用密码学哈希函数 H 和输入消息 m。消息首先由 H 处理, 产生值 H(m), 这是长度为 hlen 的比特序列。通常, 选择 H 使得其输出长度 hlen 大致等于 qlen, 因为签名方案的整体安全性将取决于 hlen 和 qlen 中的最小值; 然而, 相关标准支持 hlen 和 qlen 的所有组合。

然后应用以下步骤:

使用 bits2int 转换和额外的模约简将 H(m) 转换为模 q 的整数:
```
h = bits2int(H(m)) mod q
```
如在 bits2octets 的描述中所述, 额外的模约简不过是一个条件减法。
生成模 q 的随机值, 称为 k。该值不应为 0; 因此, 它位于 [1, q-1] 范围内。本文档的大部分剩余内容将围绕用于生成 k 的过程展开。在普通 DSA 或 ECDSA 中, k 应通过以均匀概率在 q-1 个可能值中选择一个值的随机选择来选择。
从 k 和密钥参数计算值 r (模 q):
- 对于 DSA:
```
r = g^k mod p mod q
```
  (幂运算模 p 执行, 产生 0 和 p-1 之间的数字, 然后进一步对 q 取模。)
- 对于 ECDSA: 计算点 kG; 其 X 坐标 (定义 E 的域的成员) 转换为整数, 该整数对 q 取模, 产生 r。
如果 r 结果为零, 则应选择新的 k 并再次计算 r (这是一个极不可能发生的情况)。
计算值 s (模 q):
```
s = (h+x*r)/k mod q
```
对 (r, s) 是签名。DSA 和 ECDSA 标准本身并未涵盖签名的编码方式; 一种常见的方式是使用 DER 编码的 ASN.1 结构 (两个 INTEGER 的 SEQUENCE, 按顺序为 r 和 s)。