secp256k1 endomorphism multiplication

endomorphism_multiplication.py

# Параметры кривой secp256k1
import copy
import math
import random


P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0000000000000000000000000000000000000000000000000000000000000000
b = 0x0000000000000000000000000000000000000000000000000000000000000007
PLUS_G = (
    55066263022277343669578718895168534326250603453777594175500187360389116729240,
    32670510020758816978083085130507043184471273380659243275938904335757337482424,
)
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141


# эндоморфизм

POW_2_128 = 2**128
BETA = 0x7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
A1 = 0x3086D221A7D46BCDE86C90E49284EB15
B1 = -0xE4437ED6010E88286F547FA90ABFE4C3
A2 = 0x114CA50F7A8E2F3F657C1108D9D44CFD8
B2 = 0x3086D221A7D46BCDE86C90E49284EB15


# Определение функции умножения скаляра на точку
def scalar_mult(scalar, point):
    # Алгоритм двоичного разложения
    current_point = copy.copy(point)
    bits = bin(scalar)[2:]
    for bit in bits[1:]:
        current_point = double_point(current_point)
        if bit == "1":
            current_point = add_points(current_point, point)
    return current_point


# Определение функции удвоения точки
def double_point(point):
    x, y = point
    s = ((3 * x * x + a) * pow(2 * y, P - 2, P)) % P
    x3 = (s * s - 2 * x) % P
    y3 = (s * (x - x3) - y) % P
    return (x3, y3)


# Определение функции сложения точек
def add_points(point1, point2):
    if point1 == point2:
        return double_point(point1)
    x1, y1 = point1
    x2, y2 = point2
    s = ((y2 - y1) * pow(x2 - x1, P - 2, P)) % P
    x3 = (s * s - x1 - x2) % P
    y3 = (s * (x1 - x3) - y1) % P
    return (x3, y3)


def split_scalar(k):
    # Если убрать N // 2 из c1, то k1 часто получается размером 128 с копейками, чего не происходит при добавлении N // 2
    c1 = (B2 * k + N // 2) // N
    c2 = (-B1 * k + N // 2) // N
    k1 = (k - c1 * A1 - c2 * A2) % N
    k2 = (-c1 * B1 - c2 * B2) % N
    k1neg = k1 > POW_2_128
    k2neg = k2 > POW_2_128
    k1 = N - k1 if k1neg else k1
    k2 = N - k2 if k2neg else k2
    # print(k1, k2)
    # print(math.log2(k1), math.log2(k2))
    return k1, k2, k1neg, k2neg


def endomorphism_mult(k, point):
    k1, k2, k1neg, k2neg = split_scalar(k)
    p1 = scalar_mult(k1, point)
    p1 = (p1[0], P - p1[1]) if k1neg else p1
    p2 = scalar_mult(k2, point)
    p2 = (p2[0], P - p2[1]) if k2neg else p2
    p2 = ((p2[0] * BETA) % P, p2[1])
    return add_points(p1, p2)


def test():
    counter = 0
    while True:
        private_key = int.from_bytes(random.randbytes(32), "big")
        public_key_1 = scalar_mult(private_key, PLUS_G)
        public_key_2 = endomorphism_mult(private_key, PLUS_G)
        assert public_key_1 == public_key_2, f"{counter}) {public_key_1} != {public_key_2}"
        counter += 1
        if counter % 100 == 0:
            print(counter)


if __name__ == "__main__":
    test()