Modified the gen_data.py script in
https://github.com/bitlogik/lattice-attack.
Now every set of R,S,Z(HASH) Signatures shows the K_Nonce value used. Does not show up in the json file like the other datas though. It's directly on Terminal. Modified full code below.
In gen_data.py, don't forget to input your own public keys XY coordinates.
#!/usr/bin/env python3
import argparse
import random
import json
import ecdsa_lib
def generates_signatures(number_sigs, message, kbits, data_type, curve):
print("Preparing Data")
d_key = random.randrange(ecdsa_lib.curve_n(curve))
print("Private key to be found (as demo) :")
print(hex(d_key))
sigs = []
sz_curve = ecdsa_lib.curve_size(curve)
kbi = int(2 ** kbits)
print(f"Generating {number_sigs} signatures with curve {curve.upper()}")
print(f" leaking {kbits} bits for k ({data_type}) ...")
if message is not None:
msg = message.encode("utf8")
# Always hash message provided with SHA2-256, whatever
hash_int = ecdsa_lib.sha2_int(msg)
for _ in range(number_sigs):
if message is None:
# Use a random different message for each signature
# Note : there is no associated message from the hash
# Do not ever that in practice, this is insecure, only here for demo
hash_int = random.randrange(ecdsa_lib.curve_n(curve))
# Compute signatures with k (nonce), r, s, hash
sig_info = ecdsa_lib.ecdsa_sign_kout(hash_int, d_key, curve)
# pack and save data as : r, s, hash, k%(2^bits) (partial k : "kp")
sigs.append(
{
"r": sig_info[0],
"s": sig_info[1],
"kp": sig_info[2] % kbi
if data_type == "MSB"
else sig_info[2] >> (sz_curve - kbits),
}
)
print(f"k_nonce:{sig_info[2]}")
if message is None:
sigs[-1]["hash"] = hash_int
ret = {
"curve": curve.upper(),
"public_key": (31504125288796341338541169388783846543997786027594142627385926708036691251730,
29015715595623874326232564738946807912877814040423899127791236573353650594580),
"known_type": data_type,
"known_bits": kbits,
"signatures": sigs,
}
if message is not None:
ret["message"] = list(msg)
return ret
if __name__ == "__main__":
parser = argparse.ArgumentParser(
description="Generate data for ECDSA attack."
)
parser.add_argument(
"-f",
default="data1.json",
help="File name output",
metavar="fileout",
)
parser.add_argument(
"-m",
help="Message string",
metavar="msg",
)
parser.add_argument(
"-c", default="secp256k1", help="Elliptic curve name", metavar="curve"
)
parser.add_argument(
"-b",
default=8,
type=int,
help="Number of known bits (at least 4)",
metavar="nbits",
)
parser.add_argument(
"-t", default="MSB", help="bits type : MSB or LSB", metavar="type"
)
parser.add_argument(
"-n",
default=100,
type=int,
help="Number of signatures to generate",
metavar="num",
)
arg = parser.parse_args()
sigs_data = generates_signatures(arg.n, arg.m, arg.b, arg.t, arg.c)
with open(arg.f, "w") as fout:
json.dump(sigs_data, fout)
print(f"File {arg.f} written with all data.")
Updated the ecdsa_lib.py to include print function for K_Nonce as well.
#!/usr/bin/env python3
# Lattice ECDSA Attack : ECDSA and cryptographic library
# Install cryptography
# pip3 install cryptography
# or
# apt install python3-cryptography
import hashlib
import secrets
from cryptography.hazmat import backends
from cryptography.hazmat.primitives.asymmetric import ec
CURVES_ORDER = {
"SECP224R1": int(
"2695994666715063979466701508701962594045780771442439172168272236" "8061"
),
"SECP256K1": int(
"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16
),
"SECP256R1": int(
"11579208921035624876269744694940757352999695522413576034242225906"
"1068512044369"
),
"SECP384R1": int(
"39402006196394479212279040100143613805079739270465446667946905279"
"627659399113263569398956308152294913554433653942643"
),
"SECP521R1": int(
"68647976601306097149819007990813932172694353001433054093944634591"
"85543183397655394245057746333217197532963996371363321113864768612"
"440380340372808892707005449"
),
}
def inverse_mod(a_num, m_mod):
# a_num^-1 mod m_mod, m_mod must be prime
# If not used on a prime modulo,
# can throw ZeroDivisionError.
if a_num < 0 or m_mod <= a_num:
a_num = a_num % m_mod
i, j = a_num, m_mod
x_a, x_b = 1, 0
while i != 1:
quot, rem = divmod(j, i)
x_rem = x_b - quot * x_a
j, i, x_b, x_a = i, rem, x_a, x_rem
return x_a % m_mod
def sha2(raw_message):
# SHA-2 256
return hashlib.sha256(raw_message).digest()
def bytes_to_int(bytes_data):
return int.from_bytes(bytes_data, "big")
def sha2_int(data):
return bytes_to_int(sha2(data))
def curve_size(curve_name):
# return the curve size (log2 N) from its name string
try:
curve_obj = getattr(ec, curve_name.upper())()
except Exception as exc:
raise Exception(
f"Unknown curves. Curves names available : {list(CURVES_ORDER.keys())}"
) from exc
return curve_obj.key_size
def curve_n(curve_name):
# return the curve order "N" from its name string
order = CURVES_ORDER.get(curve_name.upper())
if not order:
raise Exception(
f"Unknown curves. Curves names available : {list(CURVES_ORDER.keys())}"
)
return order
def check_publickey(pubkey, curve_str):
# Check pubkey (x,y) belongs on the curve
try:
curve_obj = getattr(ec, curve_str.upper())()
except Exception as exc:
raise Exception(
f"Unknown curves. Curves names available : {list(CURVES_ORDER.keys())}"
) from exc
if len(pubkey) != 2:
raise Exception(
'Public key data shall be provided as :\n "public_key" : [ x, y ]'
)
publickey_obj = ec.EllipticCurvePublicNumbers(pubkey[0], pubkey[1], curve_obj)
ret = False
try:
publickey_obj.public_key(backends.default_backend())
ret = True
except ValueError:
pass
return ret
def privkey_to_pubkey(pv_key_int, curve_name):
# Return public point coordinates (Scalar multiplication of pvkey with base point G)
ec_backend = getattr(ec, curve_name.upper())()
pubkey = (
ec.derive_private_key(pv_key_int, ec_backend, backends.default_backend())
.public_key()
.public_numbers()
)
return [pubkey.x, pubkey.y]
def ecdsa_sign_kout(z_hash, pvkey, curve_name):
# Perform ECDSA, but insecurely return the private k nonce
n_mod = curve_n(curve_name)
k_nonce = secrets.randbelow(n_mod)
r_sig = scalar_mult_x(k_nonce, curve_name)
s_sig = inverse_mod(k_nonce, n_mod) * (z_hash + r_sig * pvkey) % n_mod
print(f"k_nonce: {k_nonce}")
return r_sig, s_sig, k_nonce
def scalar_mult_x(d_scalar, curve):
# Scalar multiplication of d with base point G
# and return x, like ECDH with G.
return privkey_to_pubkey(d_scalar, curve)[0]
With R,S,Z(HASH) & now K nonce revealed, You can now proceed here and input your datas.
https://rawcdn.githack.com/nlitsme/bitcoinexplainer/aa50e86e8c72c04a7986f5f7c43bc2f98df94107/ecdsacrack.html to get to the Private key.
Wth this, its almost a done deal to get to the private key. Good luck.
