8000 Merge pull request #147 from tomato42/speed-up · tlsfuzzer/python-ecdsa@d64e10c · GitHub
[go: up one dir, main page]
Skip to content

Commit d64e10c

Browse files
tomato42tomato42
authored
Merge pull request #147 from tomato42/speed-up
Minor speed-up
2 parents 4e82472 + f237037 commit d64e10c

File tree

4 files changed

+22
-28
lines changed

4 files changed

+22
-28
lines changed

‎README.md

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -49,13 +49,13 @@ On an Intel Core i7 4790K @ 4.0GHz I'm getting the following performance:
4949

5050
```
5151
siglen keygen keygen/s sign sign/s verify verify/s
52-
NIST192p: 48 0.03183s 31.42 0.01127s 88.70 0.02253s 44.39
53-
NIST224p: 56 0.04304s 23.24 0.01548s 64.59 0.03122s 32.03
54-
NIST256p: 64 0.05720s 17.48 0.02055s 48.67 0.04075s 24.54
55-
NIST384p: 96 0.13216s 7.57 0.04696s 21.29 0.09400s 10.64
56-
NIST521p: 132 0.25805s 3.88 0.09329s 10.72 0.18841s 5.31
57-
SECP256k1: 64 0.05677s 17.61 0.02073s 48.23 0.04067s 24.59
58-
```
52+
NIST192p: 48 0.01586s 63.05 0.00853s 117.26 0.01624s 61.58
53+
NIST224p: 56 0.02153s 46.46 0.01145s 87.36 0.02307s 43.35
54+
NIST256p: 64 0.02850s 35.09 0.01500s 66.65 0.02925s 34.19
55+
NIST384p: 96 0.06664s 15.01 0.03512s 28.48 0.06887s 14.52
56+
NIST521p: 132 0.13048s 7.66 0.07050s 14.18 0.13673s 7.31
57+
SECP256k1: 64 0.02809s 35.60 0.01531s 65.32 0.03113s 32.12
58+
```
5959

6060
For comparison, a highly optimised implementation (including curve-specific
6161
assemply) like OpenSSL provides following performance numbers on the same

‎src/ecdsa/keys.py

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -708,10 +708,10 @@ def from_secret_exponent(cls, secexp, curve=NIST192p, hashfunc=sha1):
708708
"Invalid value for secexp, expected integer between 1 and {0}"
709709
.format(n))
710710
pubkey_point = curve.generator * secexp
711-
pubkey = ecdsa.Public_key(curve.generator, pubkey_point)
712-
pubkey.order = n
713-
self.verifying_key = VerifyingKey.from_public_point(pubkey_point, curve,
711+
self.verifying_key = VerifyingKey.from_public_point(pubkey_point,
712+
curve,
714713
hashfunc)
714+
pubkey = self.verifying_key.pubkey
715715
self.privkey = ecdsa.Private_key(pubkey, secexp)
716716
self.privkey.order = n
717717
return self

‎src/ecdsa/numbertheory.py

Lines changed: 9 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -202,27 +202,18 @@ def square_root_mod_prime(a, p):
202202

203203

204204
def inverse_mod(a, m):
205-
"""Inverse of a mod m."""
205+
"""Inverse of a mod m."""
206206

207-
if a < 0 or m <= a:
208-
a = a % m
207+
if a == 0:
208+
return 0
209209

210-
# From Ferguson and Schneier, roughly:
210+
lm, hm = 1, 0
211+
low, high = a % m, m
212+
while low > 1:
213+
r = high // low
214+
lm, low, hm, high = hm - lm * r, high - low * r, lm, low
211215

212-
c, d = a, m
213-
uc, vc, ud, vd = 1, 0, 0, 1
214-
while c != 0:
215-
q, c, d = divmod(d, c) + (c,)
216-
uc, vc, ud, vd = ud - q * uc, vd - q * vc, uc, vc
217-
218-
# At this point, d is the GCD, and ud*a+vd*m = d.
219-
# If d == 1, this means that ud is a inverse.
220-
221-
assert d == 1
222-
if ud > 0:
223-
return ud
224-
else:
225-
return ud + m
216+
return lm % m
226217

227218

228219
try:

‎src/ecdsa/test_numbertheory.py

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -259,3 +259,6 @@ def test_inverse_mod(self, nums):
259259

260260
assert 0 < inv < mod
261261
assert num * inv % mod == 1
262+
263+
def test_inverse_mod_with_zero(self):
264+
assert 0 == inverse_mod(0, 11)

0 commit comments

Comments
 (0)
0