钟林:椭圆曲线数字签名 ECDSA 与 CramerShoup 公钥加密算法简介

frdhy

最受区块链开发者欢迎的干货分享！👍👍


今晚帅锅钟林先生会为我们带来一个知识分享，我就不多介绍了。有请钟林先生！🎉🎉

钟林:
今天我给大家分享的是椭圆曲线数字签名ECDSA和Cramer-Shoup公钥加密方案。ECDSA是目前比特币以太坊等系统正在使用的经典签名方案，而Cramer-Shoup公钥加密方案也是一个经典的加密方案。Cramer和Shoup就是两个密码学家的名字。

ECDSA稍微详细点说明，而Cramer-Shoup公钥加密 稍微简略点。

我是从理论的角度 分析这两个算法:

符号说明：a^b是指a的b次方；a_1 下划线表示下标；a*b是指a乘以b。

讲ECDSA之前先要做个铺垫，介绍群的概念：群。
群定义：一个集合G，满足以下6个条件，则称为群。
1.非空集：集合中至少有一个元素。
2.二元运算：集合中的元素能够进行一种运算，例如加法运算、或乘法运算。
3.封闭性：集合中的元素进行运算后，得到的结果仍然是集合中的元素。
4.结合律：任意a,b,c属于G，则(a+b)+c=a+(b+c)。
5.单位元e：加法情况下a+e=e+a=a，乘法情况下：a*e=e*a=a。
6.每个元素都有逆元a^(-1)：加法情况下a+ a^(-1)= a^(-1)+a=e，乘法情况下：a*a^(-1)= a^(-1)*a=e。
因此集合G称为群。
对群的概念可以简单理解为：具有封闭运算的集合称为群。

这个概念有点复杂，有6个性质，主要用到二元运算、封闭性、单位元、逆元 这四个性质。

非空集、结合律 很容易满足。

概念1：如果一个群元素能够通过有限次运算，表达出群内其他所有元素，则称为群的生成元。例如：椭圆曲线的生成元G。
概念2：群内元素个数称为群的阶。

生成元：理解为用一个元素表达其他所有元素

举例：集合{0,1,2,3,4,5,6}模系数为7，就是一个群。
1.非空集：群内有7个元素。
2.二元运算是加法。
3.封闭性：群内任意两个元素相加后模7后仍然是群中的元素，例如(5+6)mod7=4；
4.结合律：((3+4)+5) mod7=(3+(4+5)) mod7=5，结果相同。
5.单位元为0：3+0=0+3=3。
6.逆元：1的逆元为6，因为(1+6)mod7=0，2的逆元为5，因为(2+5)mod7=0，同理3的逆元为4。0的逆元是0。
因此集合{0,1,2,3,4,5,6}模系数为7就是一个群。

7是素数，这个素数群的性质特别好。因为素数与群元素是互素的，所以每个非零元素都是群的生成元。例如：群元素2能够通过有限次运算，表达其他所有元素：
(2+2)mod7=4则表达群元素4，
(2+2+2)mod7=6则表达群元素6，
(2+2+2+2)mod7=1则表达群元素1，
(2+2+2+2+2)mod7=3则表达群元素3，
(2+2+2+2+2+2)mod7=5则表达群元素5，
(2+2+2+2+2+2+2)mod7=0则表达群元素0。
群元素1,2,3,4,5,6,均可以通过有限次运算表达其他群元素。素数群中的非零元素均为生成元。

上面介绍了群的概念，下面简单介绍环、域。
环：同时拥有加法和乘法运算，但是乘法运算没有逆元（不满足条件6），可以理解为大约是1.5个群。域：同时拥有加法和乘法运算，两种运算均满足条件3,4,5,6，可以理解为是2个群。

密码学里就是选择一个安全的大素数P（256位）实现签名算法或加密算法。有了一个安全的群，则密码算法大多都在群上实现。

那下面开始讲ECDSA:

在椭圆曲线上选择一个素数群，阶为n（就是群元素有n个，n是256位），群的生成元是G（即G通过有限次运算能够表达群内所有元素）。G也可以表达为(x_0, y_0)坐标形式。

@钟林 博士深入浅出，很精彩！👍👍

谢谢，我也只是从理论的角度讲，好久没看代码了。

ECDSA有3个阶段：1.密钥生成阶段，2.签名阶段，3.验证阶段。

1密钥生成阶段：
Alice选择一个安全的大的随机数d作为私钥（私钥要保密），则私钥乘以生成元G得到公钥Q，即Q=d*G属于群元素（根据封闭性）。Q也可以坐标表达为：Q=d*G=(d*x_0, d*y_0)。d取值范围是1到n-1，需要取大的随机数才会安全。

注释：秘钥生成阶段，理解为生成私钥和公钥。私钥是一个安全的随机数，公钥是由私钥sk和生成元G计算得到的群元素Q。

场景假设：Alice需要支付10个比特币给Bob。

2.签名阶段：
步骤1：Alice首先选择一个安全的大的随机数k，并计算k*G得到椭圆曲线上的一个新的点(x_1, y_1)，坐标表达为：(x_1, y_1)= k*(x_0, y_0)。注意：已知新点坐标(x_1, y_1)和基点坐标(x_0, y_0)是不能计算出随机数k的，因为是离散对数困难问题。
步骤2：令r=x_1 modn，如果r=0，则重新选择随机数k，否则继续下一步。
步骤3：计算s=k^(-1)*(m+rd) modn。如果s=0则重新选择随机数k，否则(m,r,s)就是消息签名对。

注释：
1.步骤3中，m代表10个比特币、Alice和Bob的公钥地址等信息的哈希值。
2.因为是大素数群，所以随机数k有逆元k^(-1)，且k* k^(-1)= k^(-1)*k=1单位元。
3.步骤3中的r是步骤2计算出来的r。d是Alice的私钥。
4.椭圆曲线上只使用了横坐标，纵坐标可以通过椭圆曲线表达式直接计算出来而没有其他作用。
5.每次签名都必须选择不同的随机数k，否则可以通过步骤3中的公式推倒出私钥d，而导致不安全。维基百科上有介绍如何推倒出私钥的计算过程。

3.验证阶段：
Bob首先做出基本判断
判断1：Alice的公钥Q不是零元、Q在椭圆曲线上、且n*Q=0（最后这个判断是说明群的阶为n）。
判断2：签名r和s取值范围是1到n-1。
如果判断满足，则计算：
步骤1：计算w=s^(-1)。即计算出s的逆元
步骤2：计算u_1=mw modn, u_2=rw modn。
步骤3：计算(x_1,y_1)=u_1*G + u_2*Q。
步骤4：判断：如果r=x_1 modn，则签密有效，否则签名无效。

注释：
步骤1和步骤2合并后表达为：u_1=m*s^(-1) modn, u_2=r*s^(-1) modn。
带入步骤3的公式：(x_1,y_1)=u_1*G + u_2*Q。
坐标表达为：(x_1, y_1)= m*s^(-1)*(x_0, y_0)+ r*s^(-1)* d*(x_0, y_0)。
把横坐标单独写出来：x_1= m*s^(-1)*x_0+ r*s^(-1)* d*x_0。
这条公式右边合并同类项：x_1= (m+ rd) *s^(-1)*x_0。
把x_1=k*x_0带入上述公式：k*x_0= (m+ rd) s^(-1)*x_0，可以约掉x_0。
进一步变化：s=k^(-1)*(m+rd) modn 就是签名算法过程中步骤3的公式。至于中间计算过程模n和最后再模n效果都是一样的。代码实现的时候最好中间过程就模n，能够降低计算量。

这里ECDSA验证的公式推导过程和维基百科上的推导过程思路不一样，但本质一样的。

Claire:
维基百科什么都可以学到？😄

钟林:
好多算法 都可以学到，讲的也挺专业的

Claire:
不用上大学了！👏👏

钟林:
扩展：
这个ECDSA还有一个特殊性质：能够从消息签名对(m,r,s)中提取出签名方的公钥，而不需要把公钥附加到消息签名对的后面。其他绝大多数签名算法都不能从消息签名对中提取出签名方的公钥。如何从消息签名对中提取出签名方的公钥，我在这里给出一个思路，感兴趣的朋友可以私底下与我讨论。

公钥提取思路：
签名算法步骤2中计算出一个横坐标r=x_1 modn，可以根据签名算法步骤3中的公式计算出两个椭圆曲线上的点，Q_1，Q_1。为什么是两个点，因为椭圆曲线是x轴对称的，能够计算对应的两个纵坐标。把计算出的两个值带入验证公式中，其中一个满足验证算法，另外一个不满足验证算法，因此确定签名方的公钥。

星星之🔥:
@钟林 赞 赞👍

钟林:
好，下面简要介绍Cramer-Shoup公钥加密。
公钥加密与数字签名是对应关系。
1.数字签名：用私钥对消息签名，用公钥对签名进行验证。
2.公钥加密：用公钥对消息加密，用私钥对密文进行解密。
呈现出一一对应的关系。

场景假设：Bob需要把消息m加密发送给Alice。

公钥加密分为3个阶段：1.秘钥生成阶段、2.加密阶段、3.解密阶段。

1.密钥生成阶段：
步骤1：私钥sk生成：
Alice选择5个安全的大的随机数作为自己的私钥sk, 表达为：sk={x_1, x_2, y_1, y_2, z}。
步骤2：计算出公钥pk：
Alice选择2个随机生成元g_1,g_2（生成元通过有限次计算能够表达群内所有其他元素），并计算c=[(g_1)^(x_1)] * [(g_2)^(x_2)], d=[(g_1)^(y_1)] * [(g_2)^(y_2)], h=(g_1)^z。（c,d,h则是由生成元g_1,g_2计算出来的三个群元素），Alice的公钥pk={c,d,h}。

2.加密阶段：
Bob用Alice的公钥pk={c,d,h}对消息m进行加密。
Bob选择一个安全的大的随机数r和需要加密的明文消息m，如下计算：
u_1=(g_1)^r,
u_2=(g_2)^r,
e=m*( h^r),
w=Hash(u_1, u_2, e),
v=(c^r) *[d^(rw)]
因此消息m被加密后的密文是(u_1, u_2, e, v)这四个群元素，而元素w是根据u_1, u_2, e的哈希值。

3.解密阶段：
Alice得到密文(u_1, u_2, e, v)，需要输入自己的私钥sk={x_1, x_2, y_1, y_2, z}，通过计算把消息m恢复出来。
步骤1： Alice首先计算Hash(u_1,u_2,e)得到w
步骤2：有效性判断：Alice输入得到的w、前4个私钥x_1, x_2, y_1, y_2、密文u_1,u_2,v。判断等式(u_1)^(x_1+w*y_1) * (u_2)^(x_2+w*y_2)=v是否成立。如果成立，则密文有效，否则拒绝。
步骤3：如果密文有效，则输入密文e, u_1,和最后一个私钥z，计算：e * ((u_1)^z)^(-1)。计算结果就是m。

注释1：
步骤2判断的左边：[(u_1)^(x_1+w*y_1)] * [(u_2)^(x_2+w*y_2)]=[(g_1) ^(rx_1+rw*y_1)] * [(g_2) ^(rx_2+rw*y_2)]
步骤2判断的右边：v=(c^r) * [d^(rw)]= [(g_1)^(rx_1)*(g_2)^(rx_2)] * [(g_1)^(rw*y_1)*(g_2)^(rw*y_2)]。因此左边等于右边。

注释2：
步骤3：e * ((u_1)^z)^(-1)=[m*(h^r)] * [(g_1]^(rz)]^(-1) =[m*(g_1)^(zr)] * [(g_1]^(rz)]^(-1) =m 刚好把公式e=m*( h^r)中的h^r约掉了，于是得到了消息m。本质上是计算h^r=(u_1)^z等式相等。

樊 深圳超节点区块链 sssnodes.com:
@钟林 💐💐💐

Claire:
干货满满👍👍👍

钟林:
可以把这个公钥加密方案放到椭圆曲线上去表达，能够非常安全的加密消息，而效率很高，在这里我仅仅是在一般的群上表达。

didier:
👍👍👍