DSA签名计算

Question

阅读DSA签名规范，有一件事对我来说很突出。

$r = (g^k \bmod{p} ) \bmod{q}$

然后计算$s$。在上面的计算中，为什么需要模块化$p$，因为我们无论如何都在用模$q$来减少它？

要澄清的是，仅仅做一个模$q$就可以实现将数字降到q的范围内的结果。做一个模$p$似乎是一个额外的步骤，这表明简单地将数字降到Q的界并不是唯一的目标。从密码学上讲，为什么需要模块化$p$？

Answer 1

您应该认为它不是$(g^k \bmod p) \bmod q$，而是由阶的整数$k$计算的--组$G的$q$ element $g$ =(mathbb/p\mathbb Z)^\\乘以$--这恰好是单位模$p$的乘法组，并对应于减少整数$g^k$模$p$-然后随机地将其投影到$\mathbb Z/q\mathbb $。但是，为了安全起见，只需使用从$G$到$\mathbb Z/q\mathbb $组中的一些或多或少均匀分布的$g$指数函数(Recogna$g$ distributed $q$)，而$h \mapsto $似乎就像这样的函数一样工作得很好。

In更详细的内容： (EC)DSA的一般形式是以下结构：

• 参数：
  • 组$G$，其中离散日志是硬的。
  • 元素$g \in G$ of大素数阶$q$。
  • 随机函数$H\colon {0,1}^* \ \to \mathbb /q\mathbb$。
  • $F\colon G \to \mathbb /Q\mathbb$的分布比较均匀。

• 公钥:元素$y \in G$。
• 验证:消息$m$上的签名是一对指数$r，S \in mathbb/q_mathbb$满足方程$$r =F(g{H(M) \cdot s^{-1}}).$$
• 密钥生成:选择统一的随机$x \in \mathbb /q\mathbb$；公钥为$y = g^x$。
• 签名:随机选择$k \in \mathbb /q\mathbb$(拒绝0$，如果您是mud中的棒，则选择$1)；计算$r = F(g^k)$ (如果您是mud中的棒，则拒绝$0$ )和$s =k{-1} (H(m) +x)$。

$G =(mathbb/p_mathbb Z)^\\倍于$F\colon h \mapsto h \bmod q$ (以$h$为最小的非负剩余模$p$)。对于ECDSA，我们用曲线点$B$的标量乘法$B$代替整数$g$的指数$B$，因此我们有$G = E(k)$，域$k$上某些曲线$E$的$k$-rational点，以及$F\colon P \mapsto x(P) \bmod $。另外，在ECDSA的签名中，我们编码$x(P)$而不是$F(P) = x(P) \bmod q$，因为根据Hasse的定理，$#k \约q$ (只要协因数很小；对于ECDSA通常使用的曲线通常是1)，所以与有限域DSA不同，用于编码签名的附加缩减模$q$不会节省太多空间。

如果$F$的选择感觉很武断，那么你是对的。(EC)DSA是一种古怪的怪诞设计，其动机主要是为了避免在90年代初拥有专利的克劳斯施诺尔( Claus )，除了(EC)DSA现在已经被刻在美国官僚的联邦政府标准的石头上，西方世界没有人会因为遵循这些标准而被解雇。