ECDSA的直觉是什么？

#1 楼

可以将DSA / ECDSA视为一种识别方案（如Schnorr），但可以使用菲亚特-沙米尔的另一种变体。这给出了您可能正在寻找的直觉。我将摘录至《现代密码学概论》第二版（第12.5.2节），其中给出了以下解释：

摘录-第12.5.2节DSA和ECDSA

数字签名算法（DSA）
和椭圆曲线数字签名算法（ECDSA）基于不同类别组中的离散对数问题。
它们已经存在自1991年以来以某种形式出现，并且
都包含在NIST发布的当前数字签名标准（DSS）中。

这两种方案都遵循一个通用模板，可以看作是可以从基础标识方案中构造出来（见上一节）。
让$ \ mathbb {G} $是带有生成器$ g $的素数阶qq $的循环群。
考虑以下证明方案，其中证明者的
私钥为$ x $，公钥为$（\ mathbb {G}，q，g，y）$，其中$ y = g ^ x $：


证明者选择统一$ k \ in \ mathbb {Z} _ {q} ^ * $和sen ds
$ I：= g ^ k $。
验证者选择并发送统一的$ \ alpha，r \ in \ mathbb {Z} _ {q} $作为
挑战。< br证明者发送$ s：= [k ^ {-1} \ cdot（\ alpha + xr）\ bmod q] $作为
响应。
验证者接受$ s \ neq 0 $和$ g ^ {\ alpha s ^ {-1}} \！\ cdot
y ^ {rs ^ {-1}} = I $。

注意$ s \ neq 0 $除非$ \ alpha = -xr \ bmod q $，否则发生的概率可以忽略不计。假设$ s \ neq 0 $，则存在逆$ s ^ {-1} \ bmod q $，并且
$$
g ^ {\ alpha s ^ {-1}} \！ \ cdot y ^ {r s ^ {-1}}
= g ^ {\ alpha s ^ {-1}} \！ \ cdot g ^ {xrs ^ {-1}}
= g ^ {（\ alpha + xr）\ cdot s ^ {-1}}
= g ^ {（\ alpha + xr）\ cdot k \ cdot（\ alpha + xr）^ {-1}} =I。因此，我们看到正确性几乎可以忽略不计。

如果离散对数问题在组中很困难，则可以证明这种识别方案是安全的。我们仅假设
熟悉上一节的结果（即，Schnorr和识别方案）。
首先，可以模拟诚实处决的笔录：
要做因此，只需在\ mathbb {Z} _ {q} $
中选择统一的$ \ alpha，r \和\ mathbb {Z} _ {q} ^ * $中的$ s，然后设置$ I： = g ^ {\ alpha s ^ {-1}} \！\ cdot y ^ {rs ^ {-1}} $。
（这不再提供完美的模拟，但已经足够接近了。）
此外，如果攻击者输出了一条初始消息$ I $，并且可以针对该初始消息给出正确的响应$ s_1，s_2 \ mathbb {Z} _ {q} ^ * $，以针对不同的挑战$ { alpha，r_1），
（\ alpha，r_2）$然后
$$
g ^ {\ alpha s_1 ^ {-1}} \！\ cdot y ^ {r_1 s_1 ^ { -1}} = I = g ^ {\ alpha s_2 ^ {-1}} \！\ cdot y ^ {r_2 s_2 ^ {-1}}，
$$
等等$ g ^ {\ alpha（s_1 ^ {-1}-s_2 ^ {-1}）} = h ^ {r_1s_1 ^ {-1}-r_2s_2 ^ {-1}} $和
$ \ log_g h $可以是如上一节所述进行计算。如果攻击者对正确的挑战$（\ alpha_1，r），（\ alpha_2，r）$给出正确的响应，则同样适用。DSA/ ECDSA签名方案通过将上述标识方案``折叠''为签名者运行的非交互式算法来构造。与菲亚特-沙米尔（Fiat-Shamir）变换相反，这里的变换如下进行：



设置$ \ alpha：= H（m ）$，其中$ m $是要签名的消息，$ H $是一个加密哈希函数。
为一个（指定的）函数$ F：$ R：= F（I）$设置。 mathbb {G} \ rightarrow
\ mathbb {Z} _ {q} $。在这里，$ F $是一个``简单''函数，并非要像随机的oracle一样起作用。

函数$ F $取决于$ \ mathbb {G } $，具体取决于方案。
在DSA中，
$ \ mathbb {G} $被视为$ \ mathbb {Z} _ {p的order- $ q $子组} ^ * $，用于$ p $素数，并且
$ F（I）= [I \ bmod q] $。
在ECDSA中，$ \ mathbb {G} $是
椭圆曲线组$ E（{\ mathbb Z} _p）$的order- $ q $子组，素数为$ p $。 （ECDSA还允许其他字段上的椭圆曲线
。）
此类的任何元素都可以表示为一对
$（x，y）\ in {\ mathbb Z} _p \倍{\ mathbb Z} _p $。在这种情况下，函数$ F $
被定义为$ F（（x，y））= [x \ bmod q] $。

DSA和ECDSA-摘要：
让$ \ cal G $为组生成器算法。



$ \ sf gen $：在输入$ 1 ^ n $上运行$ {\ cal G} （1 ^ n）$获得$（\ mathbb {G}，
q，g）$。在\ mathbb {Z} _ {q} $中选择统一的$ x \，然后设置$ y：= g ^ x $。
公钥是$（\ mathbb {G}，q，g，y）$，私钥是
$ x $。

作为密钥生成的一部分，两个函数$ H：\ {0,1 \} ^ * \ rightarrow
\ mathbb {Z} _ {q} $和$ F：\ mathbb {G} \ rightarrow \ mathbb {Z} _ {q} $是
指定的，但我们将其保留为隐式。

$ \ sf符号$：在输入私钥$ x $和消息$ m \ in
\ {0 ，1 \} ^ * $，在\ mathbb {Z} _ {q} ^ * $中选择统一的$ k \，然后设置
$ r：= F（g ^ k）$。然后计算$ s：= [k ^ {-1} \ cdot（H（m）+ xr）\ bmod q] $。
（如果$ r = 0 $或$ s = 0 $，则再次以$ k $的新选择。）
输出签名\ mbox {$（r，s）$}。
$ \ sf vrfy $：输入公共密钥$（\ mathbb {G} ，q，g，y）$，消息
$ m \ in \ {0,1 \} ^ * $，以及带有$ r，s \ neq 0 \ bmod的签名$（r，s）$
q $，仅当$$ r = F \ left（g ^ {H（m）\ cdot s ^ {-1}}}时输出1，
y ^ {r \ cdot s ^ { -1}} \右）。 $$

假设离散对数问题的难度，
如果将$ H $和$ F $建模为随机预言子，则可以证明DSA和ECDSA是安全的。
但是，上面的讨论虽然
对于$ H $可能是合理的，但是
对于$ F $则不是合适的模型。对于标准中$ F $的特定选择，没有安全证据可知。尽管如此，DSA和ECDSA
已经使用和研究了数十年，没有发现任何攻击。

正确生成$ k $。
DSA / ECDSA方案规定，签名者在计算签名时应选择统一的$ k \ in \ mathbb {Z} _ {q} ^ * $
。如果未能正确选择$ k $（例如，由于生成差的随机数而导致的错误）可能会导致灾难性的结果。
对于初学者来说，如果攻击者可以预测用于计算a的$ k $的值
在消息$ m $上签名$（r，s）$，然后他们可以计算签名者的私钥。
这是正确的，因为
$ s = k ^ {-1} \ cdot（H（m）+ xr）\ bmod q $，如果已知$ k $，则唯一的未知数是
私钥$ x $。

即使$ k $是不可预测的，如果曾经使用过相同的$ k $来生成两个不同的签名，则攻击者可以计算签名者的私钥。
攻击者可以很容易地分辨出何时发生这种情况，因为$ r $也会重复。
说$（r，s_1）$和$（r，s_2）$是消息$上的签名。 m_1 $和$ m_2 $，
。然后
\ begin {eqnarray *}
s_1＆=＆k ^ {-1} \ cdot（H（m_1）+ xr）\ bmod q \\
s_2＆=＆k ^ {-1} \ cdot（H（m_2）+ xr）\ bmod q。
\ end {eqnarray *}
减法得出$ s_1-s_2 = k ^ {-1} \ left（H（ m_1）-H（m_2）\ right）\ bmod q $，由此可计算$ k $
；给定$ k $，攻击者就可以将上一段落的私钥$ x $确定为
。
黑客正是利用这种攻击从Sony PlayStation中提取主私钥
。 （PS3）在2010年。

#2 楼

EC-Schnorr或ECDSA没有重要区别。 $ k $（Schnorr）的加法或$ k ^ {-1} $ an的乘法可被视为消息和私钥的加密。这就是为什么它很安全。