矩阵元 |【隐私计算笔谈】MPC系列专题（二十八）：ECDSA多方签名

本文转载自微信公众号：矩阵元

原创：胡震恺等

前言

隐私计算笔谈系列是矩阵元联合知名密码学学者共同推出的密码学科普系列文章，旨在普及密码学与隐私计算，让密码学触手可及。

ECDSA多方签名

本期我们将介绍一种多方的椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm，ECDSA），在介绍ECDSA之前，我们先简要介绍一下需要用到的背景知识：椭圆曲线密码体制（Elliptic Curve Cryptography, ECC），数字签名算法（Digital Signature Algorithm, DSA），以及将ECC和DSA结合起来的ECDSA。

| 椭圆曲线

首先简要介绍一下椭圆曲线，椭圆曲线一般是形如y²+axy+by=x³+cx²+dx+e𝑒的方程，定义中包含一个无穷远点，记为𝑂。一般普遍采用的是有限域𝐺𝐹(𝑝)上的椭圆曲线，较为常用的定义方程为y²=x³+ax+b，用E_p(𝑎, 𝑏)来代表这条曲线。因为有限域中点是离散的，因此有限域上的椭圆曲线的坐标分布也是离散的。定义椭圆曲线上任意一点𝑃，𝑃+𝑂=𝑂+𝑃=𝑃。假设曲线上有两个点P₁=(x₁,y₁),P₂=(_x2,y₂)，x₁,y₁和x₂,y₂分别表示点的坐标，椭圆曲线上的加法P₃=(x₃,y₃)=P₁+P₂定义为：,和,分别表示点的坐标，椭圆曲线上的加法P₃=(X₃,Y₃)=P₁+P₃定义为：

其中：

可以验证椭圆曲线上的每个点加法的结果都落在椭圆曲线上，定义椭圆曲线上的倍点运算，如2𝑃=𝑃+𝑃。

使用椭圆曲线构造的密码体制基于的是离散对数困难假设：对于曲线E_p(𝑎, 𝑏)上的一点𝑄=𝑘𝑃，知道𝑘的值和𝑃的坐标后计算𝑄的坐标很简单，但是由𝑃, 𝑄求𝑘是困难的。

| 数字签名算法

DSA签名算法是在ElGamal和Schnorr两个签名方案基础上设计的，其安全性也是基于求离散对数的困难性。首先DSA算法有三个全局公开的参数，分别是𝑝,𝑞,𝑔，𝑝是大素数，𝑞是𝑝−1的素因子，，其中ℎ是满足一定条件的任意整数。还是以Alice和Bob为例，Alice作为签名方，Bob作为验证方，假设Alice要签名的消息为M。

首先Alice秘密产生一个随机数𝑥∈[1,𝑞−1] ，并公开自己的公钥𝑦≡g^x𝑚𝑜𝑑 𝑝，𝑥是Alice的私钥。接着Alice为自己要签名的消息𝑀产生一个随机数𝑘∈[1,𝑞−1]，计算𝑟≡(g^k𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞，𝑠≡(k^-1(𝐻(𝑀)+𝑥𝑟))𝑚𝑜𝑑 𝑞，其中𝐻(∗)是一个哈希函数。Alice将(𝑟, 𝑠)作为自己对消息的签名，将(𝑀,(𝑟, 𝑠))发送给Bob。

假设Bob收到的为(𝑟′, 𝑠′)，Bob可以利用Alice的公钥和公开参数计算：𝑤≡(s’)^-1𝑚𝑜𝑑 𝑞，u¹≡(𝐻(𝑀′)𝑤) 𝑚𝑜𝑑 𝑞，u²≡𝑟′𝑤 𝑚𝑜𝑑 𝑞，𝑣≡((g^u1y^u2) 𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞。Bob验证若𝑣=𝑟′，则验证通过。

因为𝑣≡((g^u1y^u2)𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞≡(g^{(H(M’)+xr)s-1}𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞，又因为(𝐻(𝑀′)+𝑥𝑟)≡(𝐻(𝑀)^s-1+𝑥𝑟)⋅(k^-1(𝐻(𝑀)+𝑥𝑟)^)-1≡𝑘 𝑚𝑜𝑑 𝑝，当𝐻(𝑀)≡𝐻(𝑀′)时，𝑣≡(g^k𝑚𝑜𝑑 𝑝)𝑚𝑜𝑑 𝑞≡𝑟。若收到的(𝑀′,(𝑟′,𝑠′))和(𝑀, (𝑟, 𝑠))中有任意元素不相同，验证就会不通过。