Topic: lattice attack 2 (Read 345 times)

import sys

from random import choice


def modInv(n, p):
    return pow(n, p - 2, p)


def jordan_isinf(p):
    return p[0][0] == 0 and p[1][0] == 0


def mulcoords(c1, c2):
    return (c1[0] * c2[0] % P, c1[1] * c2[1] % P)


def mul_by_const(c, v):
    return (c[0] * v % P, c[1])


def addcoords(c1, c2):
    return ((c1[0] * c2[1] + c2[0] * c1[1]) % P, c1[1] * c2[1] % P)


def subcoords(c1, c2):
    return ((c1[0] * c2[1] - c2[0] * c1[1]) % P, c1[1] * c2[1] % P)


def invcoords(c):
    return (c[1], c[0])


def jordan_add(a, b):
    if jordan_isinf(a):
        return b
    if jordan_isinf(b):
        return a
    if (a[0][0] * b[0][1] - b[0][0] * a[0][1]) % P == 0:
        if (a[1][0] * b[1][1] - b[1][0] * a[1][1]) % P == 0:
            return jordan_double(a)
        else:
            return ((0, 1), (0, 1))

    xdiff = subcoords(b[0], a[0])
    ydiff = subcoords(b[1], a[1])
    m = mulcoords(ydiff, invcoords(xdiff))
    x = subcoords(subcoords(mulcoords(m, m), a[0]), b[0])
    y = subcoords(mulcoords(m, subcoords(a[0], x)), a[1])
    return (x, y)


def jordan_double(a):
    if jordan_isinf(a):
        return ((0, 1), (0, 1))
    num = addcoords(mul_by_const(mulcoords(a[0], a[0]), 3), [0, 1])
    den = mul_by_const(a[1], 2)
    m = mulcoords(num, invcoords(den))
    x = subcoords(mulcoords(m, m), mul_by_const(a[0], 2))
    y = subcoords(mulcoords(m, subcoords(a[0], x)), a[1])
    return (x, y)


def jordan_multiply(a, n):
    if jordan_isinf(a) or n == 0:
        return ((0, 0), (0, 0))
    if n == 1:
        return a
    if n < 0 or n >= N:
        return jordan_multiply(a, n % N)
    if n % 2 == 0:
        return jordan_double(jordan_multiply(a, n // 2))
    else:  # n % 2 == 1:
        return jordan_add(jordan_double(jordan_multiply(a, n // 2)), a)


def to_jordan(p):
    return ((p[0], 1), (p[1], 1))


def from_jordan(p):
    return (p[0][0] * modInv(p[0][1], P) % P, p[1][0] * modInv(p[1][1], P) % P)


def mul(a, n):
    """
    Multiply an ECPoint.
    @param {number} a - An ECPoint
    @param {number} n - A Big Number
    """
    return from_jordan(jordan_multiply(to_jordan(a), n))


def div(a, n):
    """
    Divide an ECPoint.
    @param {number} a - An ECPoint
    @param {number} n - A Big Number
    """
    return from_jordan(jordan_multiply(to_jordan(a), modInv(n, N) % N))


def add(a, b):
    """
    Add two ECPoints.
    @param {number} a - An ECPoint
    @param {number} b - An ECPoint
    """
    return from_jordan(jordan_add(to_jordan(a), to_jordan(b)))


def sub(a, b):
    """
    Subtract two ECPoints.
    @param {number} a - An ECPoint
    @param {number} b - An ECPoint
    """
    return from_jordan(jordan_add(to_jordan(a), to_jordan((b[0], P - (b[1] % P)))))


def negate(a):
    return (a[0], P - (a[1] % P))


def ecPoint(a):
    return mul((X, Y), a)


def get_data(sys_data):
    with open(sys_data['input_file']) as signature:
        # читaeм фaйл
        signature_file_data = [line.split(',') for line in signature.readlines()]
        # int( , 16) тaк кaк дaнныe в hex
        sys_data['signatures'] = [
            {'r': int(line[0], 16), 's': int(line[1], 16), 'kp': data['kp'], 'hash': int(line[2], 16)}
            for line in signature_file_data]
    return sys_data


# Extract Bitcoin Public Key using R, S and Z values.

# secp256k1 constants
# 2²⁵⁶ - 2³² - 2⁹ - 2⁸ - 2⁷ - 2⁶ - 2⁴ - 1
P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
X = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Pp1d4 = 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c

data = {arg.split('=')[0]: arg.split('=')[1] for arg in sys.argv if '=' in arg}

keys = ['public_key', 'input_file']

# ecли yкaзaны нe вce ключи cкpипт зaвepшaeт paбoтy
if not all([data.get(key) is not None for key in keys]):
    print('Incorrect input data')
    # пpимep, кaк зaпycтить кoд
    print("Example: python rsz.py public_key=12,aa input_file=json.txt")
    exit()

# int( , 16) тaк кaк дaнныe в hex
data['public_key'] = [int(item, 16) for item in data['public_key'].split(',')]

data = get_data(data)

new_signatures = []
for signature in data['signatures']:

    R = int(hex(signature['r']), 16)
    S = int(hex(signature['s']), 16)
    Z = int(hex(signature['hash']), 16)

    x = R
    ySquared = ((x ** 3) + 7) % P
    y = pow(ySquared, Pp1d4, P)
    ecPointK = (x, y)

    SdR = S * modInv(R, N) % N
    ZdR = Z * modInv(R, N) % N

    ecPointKmSdR = mul(ecPointK, SdR)
    ecPointZdR = mul([X, Y], ZdR)

    ecPointPubKey1 = sub(ecPointKmSdR, ecPointZdR)
    ecPointPubKey2 = sub(negate(ecPointKmSdR), ecPointZdR)

    keys = [ecPointPubKey1, ecPointPubKey2]

    if any([[x, y] == data['public_key'] for x, y in keys]):
        new_signatures += [f'{hex(signature["r"])},{hex(signature["s"])},{hex(signature["hash"])}']

print(new_signatures)
letters = 'qwertyuiopasdfghjklzxcvbnm1234567890'
with open(f'{"".join([choice(letters) for _ in range(5)])}.txt', 'w') as output_file:
    output_file.write('\n'.join(new_signatures))