Changeset View
Changeset View
Standalone View
Standalone View
test/functional/test_framework/key.py
| #!/usr/bin/env python3 | #!/usr/bin/env python3 | ||||
| # Copyright (c) 2019 Pieter Wuille | # Copyright (c) 2019 Pieter Wuille | ||||
| # Copyright (c) 2019-2020 The Bitcoin developers | # Copyright (c) 2019-2020 The Bitcoin developers | ||||
| """Test-only secp256k1 elliptic curve implementation | """Test-only secp256k1 elliptic curve implementation | ||||
| WARNING: This code is slow, uses bad randomness, does not properly protect | WARNING: This code is slow, uses bad randomness, does not properly protect | ||||
| keys, and is trivially vulnerable to side channel attacks. Do not use for | keys, and is trivially vulnerable to side channel attacks. Do not use for | ||||
| anything but tests. | anything but tests. | ||||
| """ | """ | ||||
| import hashlib | import hashlib | ||||
| import random | import random | ||||
| from .util import modinv | |||||
| def modinv(a, n): | |||||
| """Compute the modular inverse of a modulo n | |||||
| See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers | |||||
| """ | |||||
| t1, t2 = 0, 1 | |||||
| r1, r2 = n, a | |||||
| while r2 != 0: | |||||
| q = r1 // r2 | |||||
| t1, t2 = t2, t1 - q * t2 | |||||
| r1, r2 = r2, r1 - q * r2 | |||||
| if r1 > 1: | |||||
| return None | |||||
| if t1 < 0: | |||||
| t1 += n | |||||
| return t1 | |||||
| def jacobi_symbol(n, k): | def jacobi_symbol(n, k): | ||||
| """Compute the Jacobi symbol of n modulo k | """Compute the Jacobi symbol of n modulo k | ||||
| See http://en.wikipedia.org/wiki/Jacobi_symbol | See http://en.wikipedia.org/wiki/Jacobi_symbol | ||||
| """ | """ | ||||
| assert k > 0 and k & 1 | assert k > 0 and k & 1 | ||||
| ▲ Show 20 Lines • Show All 384 Lines • Show Last 20 Lines | |||||