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
|
"""Implementation of Edwards Digital Signature Algorithm."""
import hashlib
from ._sha3 import shake_256
from . import ellipticcurve
from ._compat import (
remove_whitespace,
bit_length,
bytes_to_int,
int_to_bytes,
compat26_str,
)
# edwards25519, defined in RFC7748
_p = 2**255 - 19
_a = -1
_d = int(
remove_whitespace(
"370957059346694393431380835087545651895421138798432190163887855330"
"85940283555"
)
)
_h = 8
_Gx = int(
remove_whitespace(
"151122213495354007725011514095885315114540126930418572060461132"
"83949847762202"
)
)
_Gy = int(
remove_whitespace(
"463168356949264781694283940034751631413079938662562256157830336"
"03165251855960"
)
)
_r = 2**252 + 0x14DEF9DEA2F79CD65812631A5CF5D3ED
def _sha512(data):
return hashlib.new("sha512", compat26_str(data)).digest()
curve_ed25519 = ellipticcurve.CurveEdTw(_p, _a, _d, _h, _sha512)
generator_ed25519 = ellipticcurve.PointEdwards(
curve_ed25519, _Gx, _Gy, 1, _Gx * _Gy % _p, _r, generator=True
)
# edwards448, defined in RFC7748
_p = 2**448 - 2**224 - 1
_a = 1
_d = -39081 % _p
_h = 4
_Gx = int(
remove_whitespace(
"224580040295924300187604334099896036246789641632564134246125461"
"686950415467406032909029192869357953282578032075146446173674602635"
"247710"
)
)
_Gy = int(
remove_whitespace(
"298819210078481492676017930443930673437544040154080242095928241"
"372331506189835876003536878655418784733982303233503462500531545062"
"832660"
)
)
_r = 2**446 - 0x8335DC163BB124B65129C96FDE933D8D723A70AADC873D6D54A7BB0D
def _shake256(data):
return shake_256(data, 114)
curve_ed448 = ellipticcurve.CurveEdTw(_p, _a, _d, _h, _shake256)
generator_ed448 = ellipticcurve.PointEdwards(
curve_ed448, _Gx, _Gy, 1, _Gx * _Gy % _p, _r, generator=True
)
class PublicKey(object):
"""Public key for the Edwards Digital Signature Algorithm."""
def __init__(self, generator, public_key, public_point=None):
self.generator = generator
self.curve = generator.curve()
self.__encoded = public_key
# plus one for the sign bit and round up
self.baselen = (bit_length(self.curve.p()) + 1 + 7) // 8
if len(public_key) != self.baselen:
raise ValueError(
"Incorrect size of the public key, expected: {0} bytes".format(
self.baselen
)
)
if public_point:
self.__point = public_point
else:
self.__point = ellipticcurve.PointEdwards.from_bytes(
self.curve, public_key
)
def __eq__(self, other):
if isinstance(other, PublicKey):
return (
self.curve == other.curve and self.__encoded == other.__encoded
)
return NotImplemented
def __ne__(self, other):
return not self == other
@property
def point(self):
return self.__point
@point.setter
def point(self, other):
if self.__point != other:
raise ValueError("Can't change the coordinates of the point")
self.__point = other
def public_point(self):
return self.__point
def public_key(self):
return self.__encoded
def verify(self, data, signature):
"""Verify a Pure EdDSA signature over data."""
data = compat26_str(data)
if len(signature) != 2 * self.baselen:
raise ValueError(
"Invalid signature length, expected: {0} bytes".format(
2 * self.baselen
)
)
R = ellipticcurve.PointEdwards.from_bytes(
self.curve, signature[: self.baselen]
)
S = bytes_to_int(signature[self.baselen :], "little")
if S >= self.generator.order():
raise ValueError("Invalid signature")
dom = bytearray()
if self.curve == curve_ed448:
dom = bytearray(b"SigEd448" + b"\x00\x00")
k = bytes_to_int(
self.curve.hash_func(dom + R.to_bytes() + self.__encoded + data),
"little",
)
if self.generator * S != self.__point * k + R:
raise ValueError("Invalid signature")
return True
class PrivateKey(object):
"""Private key for the Edwards Digital Signature Algorithm."""
def __init__(self, generator, private_key):
self.generator = generator
self.curve = generator.curve()
# plus one for the sign bit and round up
self.baselen = (bit_length(self.curve.p()) + 1 + 7) // 8
if len(private_key) != self.baselen:
raise ValueError(
"Incorrect size of private key, expected: {0} bytes".format(
self.baselen
)
)
self.__private_key = bytes(private_key)
self.__h = bytearray(self.curve.hash_func(private_key))
self.__public_key = None
a = self.__h[: self.baselen]
a = self._key_prune(a)
scalar = bytes_to_int(a, "little")
self.__s = scalar
@property
def private_key(self):
return self.__private_key
def __eq__(self, other):
if isinstance(other, PrivateKey):
return (
self.curve == other.curve
and self.__private_key == other.__private_key
)
return NotImplemented
def __ne__(self, other):
return not self == other
def _key_prune(self, key):
# make sure the key is not in a small subgroup
h = self.curve.cofactor()
if h == 4:
h_log = 2
elif h == 8:
h_log = 3
else:
raise ValueError("Only cofactor 4 and 8 curves supported")
key[0] &= ~((1 << h_log) - 1)
# ensure the highest bit is set but no higher
l = bit_length(self.curve.p())
if l % 8 == 0:
key[-1] = 0
key[-2] |= 0x80
else:
key[-1] = key[-1] & (1 << (l % 8)) - 1 | 1 << (l % 8) - 1
return key
def public_key(self):
"""Generate the public key based on the included private key"""
if self.__public_key:
return self.__public_key
public_point = self.generator * self.__s
self.__public_key = PublicKey(
self.generator, public_point.to_bytes(), public_point
)
return self.__public_key
def sign(self, data):
"""Perform a Pure EdDSA signature over data."""
data = compat26_str(data)
A = self.public_key().public_key()
prefix = self.__h[self.baselen :]
dom = bytearray()
if self.curve == curve_ed448:
dom = bytearray(b"SigEd448" + b"\x00\x00")
r = bytes_to_int(self.curve.hash_func(dom + prefix + data), "little")
R = (self.generator * r).to_bytes()
k = bytes_to_int(self.curve.hash_func(dom + R + A + data), "little")
k %= self.generator.order()
S = (r + k * self.__s) % self.generator.order()
return R + int_to_bytes(S, self.baselen, "little")
|