2. 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. 位和字节
形式上, 所有操作都是在位序列上定义的.序列是有序的; 第一位被称为最左侧的, 而最后一位是最右侧的.
在大多数软件系统上, 位被分组为字节 (八位序列).二进制数据, 例如哈希函数的输出, 可作为字节序列使用.在适用的情况下, 我们认为字节内的位从最高有效位到最低有效位排序: 字节内的第一位 (最左侧) 具有数值 128, 而最后一位 (最右侧) 具有数值 1.
2.3.2. 位串到整数
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. 整数到字节串
小于 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. 位串到字节串
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. 使用
值得注意的是, int2octets 不是 bits2int 的逆运算, 即使对于长度为 qlen 的输入序列也是如此: int2octets 将在左侧添加一些位, 而 bits2int 将在右侧丢弃一些位.只有当 qlen 是 8 的倍数且位序列已经具有长度 qlen 时, int2octets 才是 bits2int 的逆运算.
在标准 DSA 和 ECDSA 的签名生成和验证过程中使用 bits2int 将哈希值 (在输入消息上计算) 转换为模 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. 签名生成
签名生成使用密码学哈希函数 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).