lattice attack 2

[krashfire]

this code was shared by a user on this forum on how to generate our own 100 signatures via our public key,
instead of using random generator.

however he did not finish writing the code. when i ran it, it does not gave the correct output of RSZ and Kp. Can someone please help. im trying to generate 100 RSZ,Kp with my own public key.

#!/usr/bin/env python3

import argparse
import random
import json
import ecdsa_lib
from fpylll import LLL, BKZ, IntegerMatrix

def reduce_lattice(lattice, block_size=None):
    if block_size is None:
        return LLL.reduction(lattice)
    return BKZ.reduction(
        lattice,
        BKZ.Param(
            block_size=block_size,
            strategies=BKZ.DEFAULT_STRATEGY,
            auto_abort=True,
        ),
    )


def test_result(mat, target_pubkey, curve):
    mod_n = ecdsa_lib.curve_n(curve)
    for row in mat:
        candidate = row[-2] % mod_n
        if candidate > 0:
            cand1 = candidate
            cand2 = mod_n - candidate
            if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand1, curve):
                return cand1
            if target_pubkey == ecdsa_lib.privkey_to_pubkey(cand2, curve):
                return cand2
    return 0


def build_matrix(sigs, curve, num_bits, bits_type, hash_val):
    num_sigs = len(sigs)
    n_order = ecdsa_lib.curve_n(curve)
    curve_card = 2 ** ecdsa_lib.curve_size(curve)
    lattice = IntegerMatrix(num_sigs + 2, num_sigs + 2)
    kbi = 2 ** num_bits
    inv = ecdsa_lib.inverse_mod
    if hash_val is not None:
        hash_i = hash_val
    if bits_type == "LSB":
        for i in range(num_sigs):
            lattice[i, i] = 2 * kbi * n_order
            if hash_val is None:
                hash_i = sigs["hash"]
            lattice[num_sigs, i] = (
                2
                * kbi
                * (
                    inv(kbi, n_order)
                    * (sigs["r"] * inv(sigs["s"], n_order))
                    % n_order
                )
            )
            lattice[num_sigs + 1, i] = (
                2
                * kbi
                * (
                    inv(kbi, n_order)
                    * (sigs["kp"] - hash_i * inv(sigs["s"], n_order))
                    % n_order
                )
                + n_order
            )
    else:
        # MSB
        for i in range(num_sigs):
            lattice[i, i] = 2 * kbi * n_order
            if hash_val is None:
                hash_i = sigs["hash"]
            lattice[num_sigs, i] = (
                2 * kbi * ((sigs["r"] * inv(sigs["s"], n_order)) % n_order)
            )
            lattice[num_sigs + 1, i] = (
                2
                * kbi
                * (
                    sigs["kp"] * (curve_card // kbi)
                    - hash_i * inv(sigs["s"], n_order)
                )
                + n_order
            )
    lattice[num_sigs, num_sigs] = 1
    lattice[num_sigs + 1, num_sigs + 1] = n_order
    return lattice


MINIMUM_BITS = 4
RECOVERY_SEQUENCE = [None, 15, 25, 40, 50, 60]
SIGNATURES_NUMBER_MARGIN = 1.03


def minimum_sigs_required(num_bits, curve_name):
    curve_size = ecdsa_lib.curve_size(curve_name)
    return int(SIGNATURES_NUMBER_MARGIN * 4 / 3 * curve_size / num_bits)


def recover_private_key(
    signatures_data, h_int, pub_key, curve, bits_type, num_bits, loop
):

    # Is known bits > 4 ?
    # Change to 5 for 384 and 8 for 521 ?
    if num_bits < MINIMUM_BITS:
        print(
            "This script requires fixed known bits per signature, "
            f"and at least {MINIMUM_BITS}"
        )
        return False

    # Is there enough signatures ?
    n_sigs = minimum_sigs_required(num_bits, curve)
    if n_sigs > len(signatures_data):
        print("Not enough signatures")
        return False

    loop_var = True
    while loop_var:
        sigs_data = random.sample(signatures_data, n_sigs)

        lattice = build_matrix(sigs_data, curve, num_bits, bits_type, h_int)

        for effort in RECOVERY_SEQUENCE:
            lattice = reduce_lattice(lattice, effort)
            res = test_result(lattice, pub_key, curve)
            if res:
                return res
        loop_var = loop
        if loop:
            print("One more try")

    return 0


def lattice_attack_cli(file_name, loop):
    try:
        with open(file_name, "r") as fdata:
            data = json.load(fdata)
    except FileNotFoundError:
        print(f"Data file '{file_name}' was not found.")
        return
    except IOError:
        print(f"Data file {file_name} can't be accessed.")
        return
    except json.JSONDecodeError:
        print("Data file content is not JSON compatible.")
        return
    message = data.get("message")
    if message:
        hash_int = ecdsa_lib.sha2_int(bytes(message))
    else:
        hash_int = None  # Signal to use a hash per sig, sig data
    curve_string = data["curve"]
    data_type = data["known_type"]
    known_bits = data["known_bits"]
    signatures = data["signatures"]
    q_target = data["public_key"]
    if not ecdsa_lib.check_publickey(q_target, curve_string):
        print(
            f"Public key data invalid, not on the given {curve_string.upper()} curve."
        )
        return
    if loop:
        print("Will shuffle loop until the key found.")
    result = recover_private_key(
        signatures, hash_int, q_target, curve_string, data_type, known_bits, loop
    )
    if result:
        return result
    return 0


def get_p_value():
    return 115792089237316195423570985008687907853269984665640564039457584007908834671663


def add_point(px,py,qx,qy):
    if(px==qx):
        return double_point(px,py)
    p_value=get_p_value()
    almost_inverse=qx-px+p_value
    almost_second=qy-py+p_value
    almost_c=(almost_second*ecdsa_lib.inverse_mod(almost_inverse,p_value))
    c=almost_c%p_value
    rx=((c*c)+(2*p_value)-(px+qx))%p_value
    ry=(c*(px-rx+p_value)+p_value-py)%p_value
    return [rx,ry]


def double_point(px,py):
    p_value=get_p_value()
    triple_px_square=3*px*px
    double_py=2*py
    inverse_double_py=ecdsa_lib.inverse_mod(double_py,p_value)
    c=(triple_px_square*inverse_double_py)%p_value
    c_square=(c*c)%p_value
    minus_2_px=(2*(p_value-px))%p_value
    rx=(c_square+minus_2_px)%p_value
    ry=(c*(px-rx+p_value)+p_value-py)%p_value
    return [rx,ry]   


def multiply_point(px,py,number):
    has_final_point=False
    final_point=[0,0]
    added_point=[px,py]
    while(number!=0):
        if(number%2!=0):
            if not has_final_point:
                final_point=added_point
                has_final_point=True
            else: final_point=add_point(final_point[0],final_point[1],added_point[0],added_point[1])
        number=number//2
        added_point=double_point(added_point[0],added_point[1])
    return final_point


def generates_signatures(curve):
    puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16)
    known_bits=16
    n_value=ecdsa_lib.curve_n(curve)
    Q_point=[31504125288796341338541169388783846543997786027594142627385926708036691251730,29015715595623874326232564738946807912877814040423899127791236573353650594580]
    sigs = []
    for index in range(100):
        binaryIndex=(index*2).to_bytes(32,'big')
        binaryIndex2=(index*2+1).to_bytes(32,'big')
        hashedIndex=ecdsa_lib.sha2_int(binaryIndex)
        hashedIndex2=ecdsa_lib.sha2_int(binaryIndex2)
        #print(binaryIndex.hex(),hex(hashedIndex))
        #print(binaryIndex2.hex(),hex(hashedIndex2))
        z_value_with_r=(hashedIndex%puzzle120) #random.randrange(puzzle120)
        added_point=ecdsa_lib.privkey_to_pubkey(z_value_with_r,curve)
        final_point=add_point(Q_point[0],Q_point[1],added_point[0],added_point[1])
        r_value_with_s=(hashedIndex2%puzzle120) #random.randrange(puzzle120)
        print(hex(z_value_with_r),hex(r_value_with_s))
        R_point=multiply_point(final_point[0],final_point[1],r_value_with_s)
        r_value=R_point[0]
        s_value_with_r=ecdsa_lib.inverse_mod(r_value_with_s,n_value)
        s_value=(s_value_with_r*r_value)%n_value
        z_value=(z_value_with_r*r_value)%n_value
        sigs.append(
            {
                "r": r_value,
                "s": s_value,
                "kp": 0,
                "hash": z_value
            }
        )
    ret = {
        "curve": curve.upper(),
        "public_key": Q_point,
        "known_type": "MSB",
        "known_bits": known_bits,
        "signatures": sigs,
    }
    return ret


if __name__ == "__main__":
    curve="secp256k1"
    n_value=ecdsa_lib.curve_n(curve)
    sigs_data = generates_signatures(curve)
    with open("data.json", "w") as fout:
        json.dump(sigs_data, fout)   
    '''
    d_value=lattice_attack_cli("data.json", False)
    if(d_value==0):
        print("failed")
    else:
        r_value=sigs_data["signatures"][0]["r"]
        s_value=sigs_data["signatures"][0]["s"]
        z_value=sigs_data["signatures"][0]["hash"]
        rd_value=(r_value*d_value)%n_value
        rd_plus_z_value=(rd_value+z_value)%n_value
        inverted_s_value=ecdsa_lib.inverse_mod(s_value,n_value)
        k_value=(rd_plus_z_value*inverted_s_value)%n_value
        print("privkey:",hex(k_value))
    '''

[1715567304]

1715567304

[1715567304]

1715567304

[COBRAS]

Try thisrsz gen. nonce not more then 190 bit, fake sighnatures, not work on real data !!

Code:

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))

this gits has generators rsz too


https://github.com/bitlogik/lattice-attack

https://github.com/malb/bdd-predicate

[krashfire]

Hey cobra. I tried the bitlogik lattice attack. I'm still using it. The problem is it generates random RSZ, pubkey. I wanna input my own pubkey and let it generate 100 RSZ with leaked KP. U happen to know how? By the way script I put up earlier was modified from gen_data.py in bitlogik lattice attack

[krashfire]

Try thisrsz gen. nonce not more then 190 bit, fake sighnatures, not work on real data !!

Code:

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))

this gits has generators rsz too


https://github.com/bitlogik/lattice-attack

https://github.com/malb/bdd-predicate

i had tried your code but it seems to ask for some other files. is there an rsz.py? my output below.

Incorrect input data
Example: python rsz.py public_key=12,aa input_file=json.txt

[PrivatePerson]

I got the R,S,Z values from ~1000 transactions from one address.
How to find a nonce?
What information can be obtained from a large number of R,S,Z?