签名算法之DSA,ECDSA和EdDSA

(Updated: )

好记性不如烂笔头，写一篇文章详细记录一下DSA，ECDSA和EdDSA。

DSA

数字签名算法（DSA）是用于数字签名的联邦信息处理标准之一，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。1

概述

DSA算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字签名，并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定（接收者可以验证消息的来源），完整性（接收方可以验证消息自签名以来未被修改）和不可否认性（发送方不能错误地声称它们没有签署消息）

算法

DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证

密钥生成

  1. 选择经核可的 密码散列函数 $H$，在原版的 DSS（Digital Signature Standard）中，$H$ 总是使用 SHA-1，而目前的 DSS 已核可更为安全的 SHA-2 作为散列函数。 假如长度 ${\displaystyle |H|}$ 大于模数长度$N$，则散列函数的输出只有最左边的 $N$ 比特会被使用。
  2. 选择密钥长度 $L$，原版的 DSS 限制 $L$ 必须为 512 到 1024 之间 64 的倍数，NIST 800-57 建议使用长度为 2048 的密钥。
  3. 选择模数长度 $N$ 使得 ${\displaystyle N<L}$ 且 ${\displaystyle N\leq |H|}$，FIPS 186-4 规定 ${\displaystyle (L,N)}$ 必须为 (1024, 160)、(2048, 224)、(2048, 256) 或 (3072, 256) 其中一种。
  4. 选择长度为 $N$ 比特的质数 $q$。
  5. 选择长度为 $L$ 比特的质数 $p$ 使得 $
    {\displaystyle p-1}$ 为 $q$ 的倍数。
  6. 从 ${\displaystyle \{2\ldots p-2\}}$ 随机选择 $h$。计算 ${\displaystyle g:=h^{(p-1)/q}\mod p}$，当 $g=1$ 时需要重新产生不同的 $h$，通常会使用 ${\displaystyle h=2}$，即使数值很大时仍然可以非常有效率的计算这个模幂。

算法参数为 $(p,q,g)$，可被不同的用户共享。

用户密钥

给定一套算法参数后，第二阶段会为每位用户计算独立密钥组合：

  1. 从 ${\displaystyle \{1\ldots q-1\}}$ 选择随机整数 $x$
  2. 计算 ${\displaystyle y:=g^{x}\mod p}$

其中
$x$ 是私钥、
$y$ 是公钥。

密钥分发

签名者需要透过可信任的管道发布公钥
$y$，并且安全地保护
$x$ 不被其他人知道。

签名

消息 $m$ 签名流程如下：

  1. 从 ${\displaystyle \{1\ldots q-1\}}$ 选择随机整数 $k$
  2. 计算 ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$，当出现 $r=0$ 状况时重新选择随机数 $k$
  3. 计算 ${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$，当出现$s=0$ 状况时重新选择随机数 $k$.

签名为 ${\displaystyle (r,s)}$ 组合

验证签名

以下步骤可以验证 $
{\displaystyle \left(r,s\right)}$ 是消息
$m$ 的有效签名：

  1. 验证$0 < r < q, 0 < s < q$
  2. 计算$w:=s^{-1} \mod q$
  3. 计算$u_1:=H(m)\cdot w \mod q$
  4. 计算$u_2:=r\cdot w \mod q$
  5. 计算$v:=(g^{u_1}y^{u_2}\mod p)\mod q$

只有$v = r$时，签名有效

Correctness

因为所以

所以有

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
from Crypto.Util.number import getPrime, getRandomRange, getRandomNBitInteger, isPrime
import hashlib
def generate_param(L,N):
    q = getPrime(N)
    while True:
        t = getRandomNBitInteger(L-N)
        p = t*q + 1
        if p.bit_length() == L and isPrime(p):
            break
    h = 2
    while True:
        g = pow(h,(p-1)//q,p)
        if g > 1:
            break
        h += 1
    return p,q,g

def generate_key(p,q,g):
    ''' 
    x is private key, y is public key
    '''
    x = getRandomRange(1,q-1)
    y = pow(g,x,p)
    return x,y

def sign(m,p,q,g,x):
    ''' 
    r,s is signature
    '''
    k = getRandomRange(1,q-1)
    r = pow(g,k,p) % q
    s = (pow(k,-1,q) * (int(hashlib.sha256(m).hexdigest(),16) + x*r)) % q
    return r,s

def verify(m,r,s,p,q,g,y):
    w = pow(s,-1,q)
    u1 = (int(hashlib.sha256(m).hexdigest(),16) * w) % q
    u2 = (r * w) % q
    v = ((pow(g,u1,p) * pow(y,u2,p)) % p) % q
    return v == r

if __name__ == '__main__':
    p,q,g = generate_param(1024,160)
    x,y = generate_key(p,q,g)
    r,s = sign(b'Hello world',p,q,g,x)
    print(verify(b'Hello world',r,s,p,q,g,y))
    print(verify(b'Hello world!',r,s,p,q,g,y))

Attack

Attack on DSA with signatures made with k, k+1

随便找了一个attack练练手，后面遇到了新的再补充

根据

我们可以得到

消去$k_1$

我们可以得到

从而

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def attack_1():
    p,q,g = generate_param(1024,160)
    x,y = generate_key(p,q,g)
    def sign_fault(m1,m2,p,q,g,x):
        k = getRandomRange(1,q-1)
        r1 = pow(g,k,p) % q
        s1 = (pow(k,-1,q) * (int(hashlib.sha256(m1).hexdigest(),16) + x*r1)) % q
        r2 = pow(g,k+1,p) % q
        s2 = (pow(k+1,-1,q) * (int(hashlib.sha256(m2).hexdigest(),16) + x*r2)) % q
        return r1,s1,r2,s2
    m1 = b'Hello world'
    m2 = b'Hello world!'
    r1,s1,r2,s2 = sign_fault(m1,m2,p,q,g,x)
    '''
    x = \frac{s_1s_2 +s_2H(m_1)-s_1H(m_2)}{s_1r_2-s_2r_1} \mod q
    '''
    x_ = ((s1*s2 + s2*int(hashlib.sha256(m1).hexdigest(),16) - s1*int(hashlib.sha256(m2).hexdigest(),16)) * pow(s1*r2-s2*r1,-1,q)) % q
    print(x == x_)

ECDSA

其实 ECDSA和DSA差不多，无非就是从素域转移到椭圆曲线上，废话不多说，开干

概述

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线密码（ECC）对数字签名算法（DSA）的模拟。ECDSA于1999年成为ANSI标准，并于2000年成为IEEE和NIST标准。它在1998年既已为ISO所接受，并且包含它的其他一些标准亦在ISO的考虑之中。与普通的离散对数问题（discrete logarithm problem DLP）和大数分解问题（integer factorization problem IFP）不同，椭圆曲线离散对数问题（elliptic curve discrete logarithm problem ECDLP）没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。

算法

和DSA一样，ECDSA算法包含了四种操作：密钥生成、密钥分发、签名、验证

写着写着，突然发现自己好像对于椭圆曲线没有做过系统的了解，先挖个坑，回头写一篇博客介绍一下。

密钥生成

只要Alice和Bob选定一个合适的曲线Curve和基点$G$，不过有一点要求，$G$的阶$n$必须是一个素数

Indeed, we assume that every nonzero element of the ring
$\mathbb {Z} /n\mathbb {Z}$ is invertible, so that $\mathbb {Z} /n\mathbb {Z}$ must be a field. It implies that $n$ must be prime

Alice 从 ${\displaystyle \{1\ldots n-1\}}$ 选择随机整数 $d_A$, 作为私钥；计算$Q_A = d_A \times G$作为公钥。

密钥分发

签名者需要透过可信任的管道发布公钥
$Q_A$，并且安全地保护
$d_A$ 不被其他人知道。

签名

  1. 计算 $e = \text{HASH}(m)$，$\text{HASH}$ 是一个密码哈希函数。
  2. 取 $z$ 为 e 最左边$|n|$比特，$|n|$ 为 $n$ 的比特长度。注意 $z$ 可以比 $n$ 大，但是不能比 $n$ 长。
  3. 从 ${\displaystyle \{1\ldots n-1\}}$ 选择随机整数 $k$
  4. 计算椭圆曲线上点 $(x_1,y_1)= k\times G$
  5. 计算 $r = x_1 \mod n$，如果 $r=0$，回到step 3
  6. 计算 $s = k^{-1}(z + rd_A )$，如果 $s=0$，回到step 3

签名为 ${\displaystyle (r,s)}$ 组合，注意${\displaystyle (r,-s)}$也是有效的签名。

验证签名

  1. 首先检验公钥$Q_A$的有效性：a. 是否为$O$点; b. 是否位于曲线上; c. $n\times Q_A$是否为$O$点。
  2. 验证$r,s\in [1,n-1]$
  3. 计算 $e = \text{HASH}(m)$，$\text{HASH}$ 是一个密码哈希函数。
  4. 取 $z$ 为 e 最左边$|n|$比特，$|n|$ 为 $n$ 的比特长度。
  5. 计算$u_1 = zs^{-1}\mod n, \,u_2=rs^{-1}\mod n$
  6. 计算椭圆曲线上点 $(x_1,y_1)=u_1\times G+u_2\times Q_A \mod n$，如果 $(x_1,y_1)=O$,签名无效。
  7. 如果$r\equiv x_1 \mod n$，签名有效。

Correctness

公钥恢复

  1. 计算$R=(x_1,y_1)$，$x_1$ 是 $r,r+n,r+2n\dots$中的其中一个。
  2. 计算$u_1 = -zr^{-1}\mod n, \,u_2=sr^{-1}\mod n$
  3. 计算$Q_A = (x_A,y_A) = u_1G+u_2R $.

$Q_A$即为公钥

Correctness

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
from Crypto.Util.number import *
import random
import hashlib

class point(object):
    def __init__(self,x,y,z = 1,curve = None):
        if x != None:
            assert (x**3 + curve.a * x * z**4 + curve.b * z**6 - y**2 ) % curve.p == 0
        self.x = x
        self.y = y
        self.z = z
        self.curve = curve
        self.invert_2 = inverse(2,self.curve.p)
    
    def to_affine(self):
        if self.z == 0:
            return point(None,None,0,self.curve)
        else:
            return point(self.x * inverse(self.z**2,self.curve.p) % self.curve.p,self.y * inverse(self.z**3,self.curve.p) % self.curve.p,1,self.curve)

    def __add__(self,other):
        if self.curve != other.curve:
            raise Exception('Curve not match')
        if self.z == 0:
            return other
        elif other.z == 0:
            return self
        else:
            l1 = (self.x * other.z * other.z) % self.curve.p
            l2 = (other.x * self.z * self.z) % self.curve.p
            l3 = (l1 -l2) % self.curve.p
            l4 = (self.y * other.z**3) % self.curve.p
            l5 = (other.y * self.z**3) % self.curve.p
            l6 = (l4 - l5) % self.curve.p
            if l3 == 0:
                if l6 == 0:
                    return self.double()
                else:
                    return point(None,None,0,self.curve)
            l7 = (l1 + l2) % self.curve.p
            l8 = (l4 + l5) % self.curve.p
            x3 = (l6**2 - l7*l3**2) % self.curve.p
            l9 = (l7 * l3**2 - 2 * x3) % self.curve.p
            y3 = ((l9 * l6 -l8 * l3**3) * self.invert_2) % self.curve.p
            z3 = self.z * other.z * l3 % self.curve.p
            return point(x3,y3,z3,self.curve)

    def __mul__(self,k):
        if self.x == None and self.y == None:
            return point(None,None,0,self.curve)
        q = point(None,None,0,self.curve)
        r = self
        while k > 0:
            if k & 1:
                q = q + r
            r = r.double()
            k >>= 1
        return q
        
    def __rmul__(self,k):
        return self.__mul__(k)
    
    def __eq__(self,other):
        return self.x == other.x and self.y == other.y and self.curve == other.curve
    
    def __ne__(self,other):
        return not self.__eq__(other)
    
    def __repr__(self):
        return 'Point : (%d,%d) ' % (self.x,self.y)

    def double(self):
        l1 = (3 * self.x * self.x + self.curve.a * self.z**4) % self.curve.p
        l2 = (4 * self.x * self.y * self.y) % self.curve.p
        l3 = (8 * self.y**4) % self.curve.p
        x3 = (l1**2 - 2 * l2) % self.curve.p
        y3 = (l1 * (l2 - x3) - l3) % self.curve.p
        z3 = (2 * self.y * self.z) % self.curve.p
        return point(x3,y3,z3,self.curve)
    

class curve(object):
    def __init__(self,a,b,p):
        self.a = a
        self.b = b
        self.p = p

    def is_on_curve(self,x,y ) -> bool :
        return (y**2 - x**3 - self.a*x - self.b) % self.p == 0

    def y(self,x):
        a = (x**3 + self.a*x + self.b) % self.p
        y = mod_root(a,self.p)
        if y is not None:
            return y
        else:
            return None

    def __repr__(self):
        return 'Curve : y^2 = x^3 + %dx + %d (mod %d)' % (self.a,self.b,self.p)
 
    def __eq__(self,other):
        return self.a == other.a and self.b == other.b and self.p == other.p
    
    def __ne__(self,other):
        return not self.__eq__(other)

def lucas_seq(X,Y,k):
    ''' lucas sequence
    :returns: lucas sequence
    '''
    U0 = 0
    U1 = 1
    V0 = 2
    V1 = X
    for i in range(k-1):
        U2 = X*U1 + Y*U0
        V2 = X*V1 + Y*V0
        U0 = U1
        U1 = U2
        V0 = V1
        V1 = V2
    return U2,V2


def mod_root(g,p):
    ''' modular square root
    :x: number
    :p: prime
    :returns: modular square root
    '''
    if p % 4 == 3:
        y = pow(g,(p+1)//4,p)
        if pow(y,2,p) == g:
            return y
        else:
            return None
    elif p % 8 == 5:
        u = p // 8
        z = pow(g,2*u+1,p)
        if z == 1:
            return pow(g,u+1,p)
        elif z == p-1:
            return 2*g*pow(4*g,u,p) % p
        else:
            return None
    else:
        u = p // 8
        Y = g
        while True:
            X = random.randint(1, p-1)
            U,V = lucas_seq(X, Y, 4*u+1)
            if pow(V,2,p) == 4*Y % p:
                return (V//2) % p
            elif (U % p == 1) or (U % p == p-1):
                return None

test_p = {'curve_p':curve(0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498,0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A,0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3),
'G':point(0x421DEBD61B62EAB6746434EBC3CC315E32220B3BADD50BDC4C4E6C147FEDD43D,0x0680512BCBB42C07D47349D2153B70C4E5D7FDFCBFA36EA1A85841B9E46E09A2,1,curve(0x787968B4FA32C3FD2417842E73BBFEFF2F3C848B6831D7E0EC65228B3937E498,0x63E4C6D3B23B0C849CF84241484BFE48F61D59A5B16BA06E6E12D1DA27C5249A,0x8542D69E4C044F18E8B92435BF6FF7DE457283915C45517D722EDB8B08F1DFC3)),
'n':0x8542D69E4C044F18E8B92435BF6FF7DD297720630485628D5AE74EE7C32E79B7,
'h':1}

class ecdsa(object):
    def __init__(self,table = test_p):
        self.curve = table['curve_p']
        self.G = table['G']
        self.n = table['n']
        self.h = table['h']

    def ecdsa_KeyGen(self):
        ''' SM2 key generation
        :returns: public key, private key
        '''
        while True:
            dA = random.randint(1,self.n - 1)
            # dA = 0x1649AB77A00637BD5E2EFE283FBF353534AA7F7CB89463F208DDBC2920BB0DA0
            PA = dA * self.G
            if self.ecdsa_keycheck(PA) == True:
                break
        return PA,dA

    def ecdsa_keycheck(self,PA):
        ''' ecdsa key check
        :PA: public key
        :returns: True or False
        '''
        if PA.x == None and PA.y == None:
            return False
        if PA.x < 0 or PA.x > self.curve.p or PA.y < 0 or PA.y > self.curve.p:
            return False
        if self.curve != PA.curve:
            return False
        if (self.n * PA.to_affine()).x != None:
            print(self.n * PA)
            return False
        return True

    def ecdsa_sign(self,m,dA):
        ''' ecdsa sign
        :PA: public key
        :dA: private key
        :m: message
        :returns: signature
        '''
        e = int(hashlib.sha256(m).hexdigest(),16)
        if e.bit_length() > self.n.bit_length():
            z = e >> (e.bit_length() - self.n.bit_length())
        else:
            z = e
        while True:
            k = random.randint(1,self.n - 1)
            C = (k * self.G).to_affine()
            r = (C.x % self.n)
            if r == 0:
                continue
            s = (inverse(k,self.n) * (z + r * dA)) % self.n
            if s != 0:
                break
        return r,s
    
    def ecdsa_verify(self,m,r,s,PA):
        e = int(hashlib.sha256(m).hexdigest(),16)
        if e.bit_length() > self.n.bit_length():
            z = e >> (e.bit_length() - self.n.bit_length())
        else:
            z = e
        u1 = z * inverse(s,self.n) % self.n
        u2 = r * inverse(s,self.n) % self.n
        C = (u1 * self.G + u2 * PA).to_affine()
        return (C.x % self.n) == r

if __name__ == '__main__':
    exp = ecdsa()
    print('---------------------------------')
    print('prameters: of Curve')
    print('[+]ECC: ',exp.curve)
    print('[+]G: ',exp.G)
    print('[+]n: ',exp.n)
    print('[+]h: ',exp.h)
    print('---------------------------------')
    print('Key Generation:')
    PA,dA = exp.ecdsa_KeyGen()
    print('[+]Public Key: ',PA)
    print('[+]Private Key: ',dA)
    print('---------------------------------')
    m = b'Hello world'
    print('Message: ',m)
    print('---------------------------------')
    print('Signature:')
    r,s = exp.ecdsa_sign(m,dA)
    print('[+]r: ',r)
    print('[+]s: ',s)
    print('---------------------------------')
    print('Verification:')
    print('[+]Result: ',exp.ecdsa_verify(m,r,s,PA))

Attack

Attack on ECDSA with signatures made with same k

根据

我们可以得到

从而有

从而可以得到

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def attack_1():
    exp = ecdsa()
    print('---------------------------------')
    print('prameters: of Curve')
    print('[+]ECC: ',exp.curve)
    print('[+]G: ',exp.G)
    print('[+]n: ',exp.n)
    print('[+]h: ',exp.h)
    print('---------------------------------')
    print('Key Generation:')
    PA,dA = exp.ecdsa_KeyGen()
    print('[+]Public Key: ',PA)
    print('[+]Private Key: ',dA)
    print('---------------------------------')
    m1 = b'Hello world'
    m2 = b'Hello world!'
    print('Message: ',m1)
    print('Message: ',m2)
    print('---------------------------------')
    print('Signature:')
    e = int(hashlib.sha256(m1).hexdigest(),16)
    if e.bit_length() > exp.n.bit_length():
        z1 = e >> (e.bit_length() - exp.n.bit_length())
    else:
        z1 = e
    while True:
        k = random.randint(1,exp.n - 1)
        C = (k * exp.G).to_affine()
        r1 = (C.x % exp.n)
        if r1 == 0:
            continue
        s1 = (inverse(k,exp.n) * (z1 + r1 * dA)) % exp.n
        if s1 != 0:
            break

    e = int(hashlib.sha256(m2).hexdigest(),16)
    if e.bit_length() > exp.n.bit_length():
        z2 = e >> (e.bit_length() - exp.n.bit_length())
    else:
        z2 = e
    while True:
        C = (k * exp.G).to_affine()
        r2 = (C.x % exp.n)
        if r2 == 0:
            continue
        s2 = (inverse(k,exp.n) * (z2 + r2 * dA)) % exp.n
        if s2 != 0:
            break
    
    print('[+]r1: ',r1)
    print('[+]s1: ',s1)
    print('[+]r2: ',r2)
    print('[+]s2: ',s2)
    print('---------------------------------')
    k = (z1 - z2) * inverse(s1 - s2,exp.n) % exp.n
    dA_ = ((s1 * k - z1) * inverse(r1,exp.n)) % exp.n
    print('Private Key: ',dA_)
    print('---------------------------------')
    print(dA==dA_)

EdDSA

EdDSA给我一种很奇怪的感觉，先留一个坑，等我摸索摸索再填

参考