Title: LLL_nonce_leakage.py -->> simple Sagemath code Post by: cassondracoffee on April 15, 2024, 10:42:55 AM import olll
import random import math import secp256k1 as ice G = ice.scalar_multiplication(1) N = ice.N # Secret key = x = (rns1 – r1sn)-1 (snm1 – s1mn – s1sn(k1 – kn)) # For most significant fix 128 bit leak at least 3 sig is required. fix_bits = 128 out_file_name = 'pseudo_sig_rsz.txt' kbits = 256 - fix_bits #============================================================================== def write_rsz_file(rr, ss, zz, pb): with open(out_file_name, 'w') as f: sz = len(rr) for i in range(sz): f.write('r = ' + hex(rr)[2:].zfill(64) + '\n') f.write('s = ' + hex(ss)[2:].zfill(64) + '\n') f.write('z = ' + hex(zz)[2:].zfill(64) + '\n') f.write('pubkey = ' + pb.hex()) def modinv(v): return pow(v, N-2, N) def getx(Q): return int(Q[1:33].hex(), 16) def minimum_sigs_required(num_bits): return math.ceil(1.03 * 4 / 3 * 256 / num_bits) def identity_plus2(u, elem=1): m=[[0 for x in range(u+2)] for y in range(u)] for i in range(0,u): m = elem return m #============================================================================== n = 1 + minimum_sigs_required(fix_bits) print(f'\n Fixed Nonce bits = {fix_bits} Minimum Signature Required = {n}') # example secret = 0x7cf5d79d200207963474c64e64bde80ff4cb3e225b6ac5b6e958522fdab60578 secret = random.randint(1,N) pub = ice.scalar_multiplication(secret) print('###############################################################################') print(f'secret: {hex(secret)}') print(f'Pubkey: {pub.hex()}') print('###############################################################################') fixed_k_prefix = random.randrange(2**kbits, N) #S = ((Z + (X * R)) / K) % N z = [random.randrange(1, N) for i in range(n)] nonces = [random.randrange(1, 2**kbits) + fixed_k_prefix for i in range(n)] sigs_r = [getx(ice.scalar_multiplication(nonces)) for i in range(n)] sigs_s = [( (z + secret * sigs_r) * modinv(nonces) )%N for i in range(n)] sinv = [modinv(sigs_s) for i in range(n)] write_rsz_file(sigs_r, sigs_s, z, pub) ############################################################################### matrix = identity_plus2(n-1, N) # Add last 2 rows row, row2 = [], [] [zn, rn, sn] = [z[-1], sigs_r[-1], sigs_s[-1]] rnsn_inv = rn * modinv(sn) znsn_inv = zn * modinv(sn) # 2nd to last row: [r1(s1^-1) - rn(sn^-1), ... , rn-1(sn-1^-1) - rn(sn^-1), 2^176/order, 0 ] # last row: [m1(s1^-1) - mn(sn^-1), ... , mn-1(sn-1^-1) - mn(sn^-1), 0, 2^176] for i in range(n-1): row.append((sigs_r * modinv(sigs_s)) - rnsn_inv) row2.append((z * modinv(sigs_s)) - znsn_inv) # add last elements of last two rows, B = 2**(256-80) for yubikey row.append((2**kbits) / N) row.append(0) row2.append(0) row2.append(2**kbits) matrix.append(row) matrix.append(row2) print(' Original Matrix') print(matrix) ############################################################################### new_matrix = olll.reduction(matrix, 0.75) print('\n\n Reduced Matrix') print(new_matrix) for row in new_matrix: potential_nonce_diff = row[0] # print('k=', hex(potential_nonce_diff)) # modinv(r3 * s1 - r1 *s3) * (s3 * m1 - s1 * m3 - s1 * s3 *(k1 - k3)) potential_priv_key = (sn * z[0]) - (sigs_s[0] * zn) - (sigs_s[0] * sn * potential_nonce_diff) potential_priv_key *= modinv((rn * sigs_s[0]) - (sigs_r[0] * sn)) potential_priv_key = potential_priv_key % N # print('PK=', hex(potential_priv_key)) # check if we found private key by comparing its public key with actual public key if ice.scalar_multiplication(potential_priv_key) == pub: print('-'*75) print(f' found private key = {hex(potential_priv_key)}') print('-'*75) I can't understand this Python code. Anyone write the Sagemath code? LLL_nonce_leakage.py -->> simple Sagemath code Title: Re: LLL_nonce_leakage.py -->> simple Sagemath code Post by: krashfire on April 17, 2024, 01:04:18 AM import olll download or clone the file from here to the same directory you have the LLL program. you need to use ice_secp256k1.dll or .so for linux to use this program..import random import math import secp256k1 as ice G = ice.scalar_multiplication(1) N = ice.N # Secret key = x = (rns1 – r1sn)-1 (snm1 – s1mn – s1sn(k1 – kn)) # For most significant fix 128 bit leak at least 3 sig is required. fix_bits = 128 out_file_name = 'pseudo_sig_rsz.txt' kbits = 256 - fix_bits #============================================================================== def write_rsz_file(rr, ss, zz, pb): with open(out_file_name, 'w') as f: sz = len(rr) for i in range(sz): f.write('r = ' + hex(rr)[2:].zfill(64) + '\n') f.write('s = ' + hex(ss)[2:].zfill(64) + '\n') f.write('z = ' + hex(zz)[2:].zfill(64) + '\n') f.write('pubkey = ' + pb.hex()) def modinv(v): return pow(v, N-2, N) def getx(Q): return int(Q[1:33].hex(), 16) def minimum_sigs_required(num_bits): return math.ceil(1.03 * 4 / 3 * 256 / num_bits) def identity_plus2(u, elem=1): m=[[0 for x in range(u+2)] for y in range(u)] for i in range(0,u): m = elem return m #============================================================================== n = 1 + minimum_sigs_required(fix_bits) print(f'\n Fixed Nonce bits = {fix_bits} Minimum Signature Required = {n}') # example secret = 0x7cf5d79d200207963474c64e64bde80ff4cb3e225b6ac5b6e958522fdab60578 secret = random.randint(1,N) pub = ice.scalar_multiplication(secret) print('###############################################################################') print(f'secret: {hex(secret)}') print(f'Pubkey: {pub.hex()}') print('###############################################################################') fixed_k_prefix = random.randrange(2**kbits, N) #S = ((Z + (X * R)) / K) % N z = [random.randrange(1, N) for i in range(n)] nonces = [random.randrange(1, 2**kbits) + fixed_k_prefix for i in range(n)] sigs_r = [getx(ice.scalar_multiplication(nonces)) for i in range(n)] sigs_s = [( (z + secret * sigs_r) * modinv(nonces) )%N for i in range(n)] sinv = [modinv(sigs_s) for i in range(n)] write_rsz_file(sigs_r, sigs_s, z, pub) ############################################################################### matrix = identity_plus2(n-1, N) # Add last 2 rows row, row2 = [], [] [zn, rn, sn] = [z[-1], sigs_r[-1], sigs_s[-1]] rnsn_inv = rn * modinv(sn) znsn_inv = zn * modinv(sn) # 2nd to last row: [r1(s1^-1) - rn(sn^-1), ... , rn-1(sn-1^-1) - rn(sn^-1), 2^176/order, 0 ] # last row: [m1(s1^-1) - mn(sn^-1), ... , mn-1(sn-1^-1) - mn(sn^-1), 0, 2^176] for i in range(n-1): row.append((sigs_r * modinv(sigs_s)) - rnsn_inv) row2.append((z * modinv(sigs_s)) - znsn_inv) # add last elements of last two rows, B = 2**(256-80) for yubikey row.append((2**kbits) / N) row.append(0) row2.append(0) row2.append(2**kbits) matrix.append(row) matrix.append(row2) print(' Original Matrix') print(matrix) ############################################################################### new_matrix = olll.reduction(matrix, 0.75) print('\n\n Reduced Matrix') print(new_matrix) for row in new_matrix: potential_nonce_diff = row[0] # print('k=', hex(potential_nonce_diff)) # modinv(r3 * s1 - r1 *s3) * (s3 * m1 - s1 * m3 - s1 * s3 *(k1 - k3)) potential_priv_key = (sn * z[0]) - (sigs_s[0] * zn) - (sigs_s[0] * sn * potential_nonce_diff) potential_priv_key *= modinv((rn * sigs_s[0]) - (sigs_r[0] * sn)) potential_priv_key = potential_priv_key % N # print('PK=', hex(potential_priv_key)) # check if we found private key by comparing its public key with actual public key if ice.scalar_multiplication(potential_priv_key) == pub: print('-'*75) print(f' found private key = {hex(potential_priv_key)}') print('-'*75) I can't understand this Python code. Anyone write the Sagemath code? LLL_nonce_leakage.py -->> simple Sagemath code https://github.com/iceland2k14/secp256k1 Title: Re: LLL_nonce_leakage.py -->> simple Sagemath code Post by: cassondracoffee on April 17, 2024, 03:43:15 AM # Secret key = x = (rns1 – r1sn)-1 (snm1 – s1mn – s1sn(k1 – kn)) # For most significant fix 128 bit leak at least 3 sig is required. fix_bits = 128 out_file_name = 'pseudo_sig_rsz.txt' kbits = 256 - fix_bits .... ................ for row in new_matrix: potential_nonce_diff = row[0] # print('k=', hex(potential_nonce_diff)) # modinv(r3 * s1 - r1 *s3) * (s3 * m1 - s1 * m3 - s1 * s3 *(k1 - k3)) potential_priv_key = (sn * z[0]) - (sigs_s[0] * zn) - (sigs_s[0] * sn * potential_nonce_diff) potential_priv_key *= modinv((rn * sigs_s[0]) - (sigs_r[0] * sn)) potential_priv_key = potential_priv_key % N # print('PK=', hex(potential_priv_key)) # check if we found private key by comparing its public key with actual public key if ice.scalar_multiplication(potential_priv_key) == pub: print('-'*75) print(f' found private key = {hex(potential_priv_key)}') print('-'*75) I can't understand this Python code. Anyone write the Sagemath code? LLL_nonce_leakage.py -->> simple Sagemath code https://github.com/iceland2k14/secp256k1 Please explain how LLL_nonce_leakage works, write simple math, or explain Title: Re: LLL_nonce_leakage.py -->> simple Sagemath code Post by: _Counselor on April 17, 2024, 06:33:50 AM Yes, I know, but I am asking for simple math for easy understanding. Please explain how LLL_nonce_leakage works, write simple math, or explain Lenstra–Lenstra–Lovász lattice basis reduction algorithm is not a something that can be understood using simple mathematics. Try to read this (https://www.researchgate.net/figure/Security-of-ECDSA-with-leak-weak-nonces-and-LLL-with-NIST-and-SECP-curves_fig6_370939924) for example. |