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 |