ECDSA算法

#

前言

#

我今天简单查了查ECDSA的流程，发现一大堆人瞎写，私钥写成公钥，随机数k写成d，真是令人尴尬。所以写个这个，额，差不多可以说是维基百科的翻译版。

ECDSA算法的讲解

#

场景假设还是经典的Alice，Bob场景，他们一开始只协商好了椭圆曲线ID，基点G，和基点G的阶n(multiplicative order)。

基本参数定义

#

场景假设还是经典的ALICE，BOB场景，他们一开始只协商好了椭圆曲线ID，基点G，和基点G的阶n(multiplicative order)。在TLS1.3中，选定了椭圆曲线就标识对应的基点和基点的阶了。我们下面定义具体的参数。

基点G的阶必须是素数，我们这里假设计算是基于整数域也就是Z/nZ的。此外，上面的d(A)是随机生成的私钥，注意d(A)并不是临时密钥(Ephemeral Key)。

ECDSA计算流程

#

现在假设Alice要开始对消息做签名了，除了第四步是加乘，其他都是正常的整数域乘法。流程如下：

1. 先对消息做$$hash$$，在TLS1.3中称之为transcrpthash(m)。具体体现为$$e = HASH(m)$$，将输出转换为整数
2. 假设$$L(n)$$是基点$$G$$的阶$$n$$的bit长度，取z为上一步计算结果e的最左端$$L(n)$$位，实际上就是个截断操作，毕竟这个要参与运算的
3. 从$$[1,n-1]$$中随机的选取一个随机数$$k$$，该随机数应当满足密码学安全性
4. 计算新的点$$(x(1),y(1))=k*G$$，这里的*依然是椭圆曲线上的加乘
5. 取上一步结果的横坐标$$x(1)$$，计算$$r = x(1) mod n$$,如果$$r==0$$，回退到第三步。
6. 计算$s=k`*(z+rd(A)) modn$，如果s==0，再次回退到第三步,这里的k`就是k的逆

ECDSA的验签

#

验签的流程并不难，对Bob而言，验签过程首先要验证的就是公钥是合法的。这点不多说了。具体流程如下：

1. 验证r和s在[1,n-1]之间，如果不在，则签名无效
2. 计算 $$e=hash(m)$$，保存e的最左端$$L(n)$$位为$$z$$
3. 计算$$u(1)=zs`mod n$$与$$u(2)=rs`mod n$$，s`指代s在n整数域上的逆
4. 计算点$$(x(1),y(1))=u(1)*G+u(2)*Q(A)$$，这里的两个乘都是椭圆曲线的加乘
5. 验证$$r==x(1)mod n$$，成立则说明签名有效，反之无效。

ECDSA验签的证明

#

证明就不多说了，本身将计算流程带入然后结合律搞一下就完了。ECDSA本身需要依靠椭圆曲线逆推难的结论，这点也没啥好说的。

结语

#

国内好多文章不知道为啥要自己改来改去，如何定义一个标准的正确的竟然成为了难题。奇葩

结尾的闲言碎语

#

写到这里差不多就可以结束了，就不多说了。TLS这块还有啥不明白的直接告诉我就成了