ECDSA 签名

签名把临时秘密$k$、长期秘密$d$和消息整数$z$约束在$sk=z+rd$里。公钥允许验证者在点的世界计算$dG$，却不直接提供$d$。乘上$s^{-1}$后，验证者重建同一个临时点，比较它的横坐标指纹。

横坐标会丢失信息：$R$与$-R$共享横坐标。因此$(r,s)$通过时，$(r,q-s)$也通过，重建点恰好取负。这不会自动产生另一条消息的签名，却会产生同一消息的不同有效签名；“签名算法内部确定”与“每条消息只有唯一接受表示”是两个条件。

本算法实际调用椭圆曲线理路椭圆曲线Elliptic curve带指定有理点的光滑射影亏格一曲线；由短 Weierstrass 方程推导点加法，并完整计算一个九点有限群。的点加法、倍点和无穷远点规则。下载器采用仿射坐标、重复倍点与条件相加，目的是让每一步可复算；它有数据相关分支与大整数求逆，不提供恒定时间实现。

在17个坐标值上算一份签名 ​

取$p=17,a=b=2,G=(5,1),q=19$。全曲线恰有19个点；下载器可枚举核对。私钥$d=7$，所以$Q=7G=(0,6)$。让$z=4,k=3$，则$R=3G=(10,6)$、$r=10$，而$3^{-1}=13(\mathrm{mod}19)$，所以

验证时${12}^{-1}=8$，得到$u_1=13,u_2=4$，于是$13G+4Q=41G=3G$，通过。把$s$改成7仍通过，因为$7=19-12$；重建点变成$-3G=(10,11)$。这个极小群可穷举私钥，只适合教学。

同一个k泄漏了什么 ​

仍用$d=7,k=3$，第二条消息取$z_2=9$，签名为$(10,1)$。两条方程相减，消去长期秘密项：

这个计算要求真的用了同一个$k$，且$s_1\ne s_2(\mathrm{mod}q)$、$r\ne 0$。仅见相同$r$还不够：$k$与$q-k$也给出相同横坐标，其他坐标约简也可能产生重复$r$；应核对相应候选，而不能把任意相同$r$都代入同一假设。

$r=0$与$s=0$都是实际可触发的分支。在本小曲线上$7G=(0,6)$，故$k=7$必须重试；取$d=7,z=21,k=6$，$r=16$且$z+rd=133\equiv 0(\mathrm{mod}19)$，故$s=0$也必须重试。把零$s$发出去会令验证所需逆元不存在。

RFC6979确定性候选生成理路RFC6979 确定性签名临时量Deterministic signature nonce · RFC6979以私钥和摘要初始化HMAC状态，严格区分位截断与整数编码，按拒绝采样连续产生适合ECDSA的临时标量。用私钥与消息摘要生成候选序列，替换签名时的随机$k$来源。遇到$r=0$或$s=0$时应继续同一生成器，而不是重新初始化后永远得到同一个坏候选。确定性生成不弥补弱私钥、故障或侧信道，也不把ECDSA的$s\mapsto q-s$接受对称性消除。

设群阶位数为$b$，一次标量乘法用$O(b)$次点运算；验证包含公钥子群检查和两次标量乘法，仍是$O(b)$次点运算及常数次模$q$求逆。签名若尝试$a$个候选则是$O(ab)$次点运算。仿射点运算还含模$p$求逆，不能把它当作一个机器指令；消息哈希另计读取消息的成本。正常密钥参数下失败候选罕见，但这里的成本保留实际尝试数。

签名执行实验同时复算小曲线、RFC6979的P-256公开向量和篡改。迁移任务：把第二次临时量改为$q-k=16$，手算第二个$s$，分别尝试“同一$k$”和“相反$k$”两套方程，再用恢复的$dG$核对公钥；说明为什么相同$r$不能单独决定泄漏公式。另一项任务让两份摘要在截取后相同，解释为什么差分逆元条件失效。