BHWallet
Newbie
Offline
Activity: 62
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 14, 2022, 01:11:36 PM |
|
Here is my modified version of "gen_data.py": #!/usr/bin/env python3
# Random demo data generator for Lattice ECDSA Attack # Copyright (C) 2021 Antoine Ferron - BitLogiK # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # You should have received a copy of the GNU General Public License # along with this program. If not, see <https://www.gnu.org/licenses/>. #
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[i]["hash"] lattice[num_sigs, i] = ( 2 * kbi * ( inv(kbi, n_order) * (sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order ) ) lattice[num_sigs + 1, i] = ( 2 * kbi * ( inv(kbi, n_order) * (sigs[i]["kp"] - hash_i * inv(sigs[i]["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[i]["hash"] lattice[num_sigs, i] = ( 2 * kbi * ((sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order) ) lattice[num_sigs + 1, i] = ( 2 * kbi * ( sigs[i]["kp"] * (curve_card // kbi) - hash_i * inv(sigs[i]["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=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492] 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)) ''' Of course, this code is messy, and it contains things like commented-out code, and some testing code from previous steps. And it is a raw dump of what I left a few months ago. And the most important thing is that it doesn't work, so it should be modified to be usable. But this is what I left before switching to other stuff, because my conclusion was that I need more mathematical knowledge to properly find out, why it fails. Thanks for sharing, but I this code is too much for me, can't get it to work. I hope someone will sort it out soon and explain the attack in a understandable way
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 14, 2022, 07:17:20 PM Last edit: September 14, 2022, 07:32:49 PM by COBRAS |
|
Here is my modified version of "gen_data.py": #!/usr/bin/env python3
# Random demo data generator for Lattice ECDSA Attack # Copyright (C) 2021 Antoine Ferron - BitLogiK # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # This program is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # You should have received a copy of the GNU General Public License # along with this program. If not, see <https://www.gnu.org/licenses/>. #
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[i]["hash"] lattice[num_sigs, i] = ( 2 * kbi * ( inv(kbi, n_order) * (sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order ) ) lattice[num_sigs + 1, i] = ( 2 * kbi * ( inv(kbi, n_order) * (sigs[i]["kp"] - hash_i * inv(sigs[i]["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[i]["hash"] lattice[num_sigs, i] = ( 2 * kbi * ((sigs[i]["r"] * inv(sigs[i]["s"], n_order)) % n_order) ) lattice[num_sigs + 1, i] = ( 2 * kbi * ( sigs[i]["kp"] * (curve_card // kbi) - hash_i * inv(sigs[i]["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=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492] 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)) ''' Of course, this code is messy, and it contains things like commented-out code, and some testing code from previous steps. And it is a raw dump of what I left a few months ago. And the most important thing is that it doesn't work, so it should be modified to be usable. But this is what I left before switching to other stuff, because my conclusion was that I need more mathematical knowledge to properly find out, why it fails. Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition https://github.com/bitlogik/lattice-attack/issuesps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him...
|
[
|
|
|
BHWallet
Newbie
Offline
Activity: 62
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 15, 2022, 04:54:35 PM |
|
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition https://github.com/bitlogik/lattice-attack/issuesps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him... That's actually a great idea, if you guys want we could offer the creator some $ to edit the code.
|
|
|
|
ecdsa123
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 207
Merit: 105
Dr WHO on disney+
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 15, 2022, 05:04:01 PM |
|
I can rewrite those code , for easy and understanding -> python with sage version
my propose $100 on my btc account, of course before start work
|
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 15, 2022, 07:50:56 PM |
|
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition https://github.com/bitlogik/lattice-attack/issuesps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him... That's actually a great idea, if you guys want we could offer the creator some $ to edit the code. For talk about $$ for coder of original scrypt for rsz generation, we need to know, what is difference of original and modified versions of scrypt, and what not work in the scrypt. May be this is imposible to solve ... unfortunately. I have a telegramm of original scrypt developer, and first of all we ned try ask him for free help and message post to devevrloper iesues in github on link what I provide previously in this thread. ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) br
|
[
|
|
|
COBRAS
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 895
Merit: 22
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 15, 2022, 07:52:55 PM |
|
I can rewrite those code , for easy and understanding -> python with sage version
my propose $100 on my btc account, of course before start work
and waht will be your new code doing ? generate sighnatures like original scrypt without rial world use posibble ? br
|
[
|
|
|
BHWallet
Newbie
Offline
Activity: 62
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
September 16, 2022, 09:35:01 AM |
|
Bro, can try talk with Antoine Ferron - BitLogiK at his github ? I think he can help modify code to working condition https://github.com/bitlogik/lattice-attack/issuesps a I was talk with him previously, he is ansver to queschion. Becausd I dont know what exact scrypt do, for me hard will talk with him... That's actually a great idea, if you guys want we could offer the creator some $ to edit the code. For talk about $$ for coder of original scrypt for rsz generation, we need to know, what is difference of original and modified versions of scrypt, and what not work in the scrypt. May be this is imposible to solve ... unfortunately. I have a telegramm of original scrypt developer, and first of all we ned try ask him for free help and message post to devevrloper iesues in github on link what I provide previously in this thread. ![Huh](https://bitcointalk.org/Smileys/default/huh.gif) br Just ask him can he edit the script in such a way that the user is able to paste a list of public keys or addresses and the script will go through that list and search for weaknesses. You can invite the creator to this thread.
|
|
|
|
PrivatePerson
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 174
Merit: 12
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
October 19, 2022, 08:20:49 PM |
|
If I understand correctly from the answers on github, the creator does not want to change his code.
|
|
|
|
krashfire
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 122
Merit: 14
Life aint interesting without any cuts and bruises
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 08, 2022, 04:33:06 PM |
|
First, we look at signatures: s=(z+rd)/k sk=z+rd sk-z=rd (sk-z)/r=d (s/r)k-(z/r)=d (z/r)+d=(s/r)k k=((z/r)+d)*(r/s) Then, things are quite simple: But we can do more than that: z/r=120_bit_number_v1 r/s=120_bit_number_v2 k=(120_bit_number_v1+d)*120_bit_number_v2 If "d" is our 120_bit_privkey, then first we add another 120_bit number to that (we can use 119-bit numbers to be 100% sure). Then, we have 121-bit number at most, it cannot be bigger. And if we multiply that by another 119-bit number (just to be sure), then we will have 121+119=240 bits in our result. It cannot be bigger than that, because if you multiply M-bit number by N-bit number, then the result has at most M+N bits. So, in this way I can be absolutely sure that if "d" is a 120-bit number, then "k" is a 240-bit number. In the same way, it is possible to generate many signatures with many different N-bit values. But it is still not enough to use that in a lattice attack, because it needs some randomness in the right places, so something else is also needed to make it. Edit: show your code def generates_signatures(curve): puzzle120=int("00000000000000000000000000000000007fffffffffffffffffffffffffffff",16) #119-bit to be 100% sure to not fall into 241-bit range known_bits=16 n_value=ecdsa_lib.curve_n(curve) Q_point=[93499419120076195219278579763555015417347613618260420189054155605804414805552,19494200143356336257404688340550956357466777176798681646526975620299854296492] 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) z_value_with_r=(hashedIndex%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) 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 I tested your code. I believe the output gave several R and S value. I wish you had continue finishing the script. Z value and Kp didn't come out. What do I need to add in the script so that the Z_hash value and kp can be output?
|
KRASH
|
|
|
krashfire
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 122
Merit: 14
Life aint interesting without any cuts and bruises
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 04, 2022, 12:50:08 PM |
|
Some problems with install fpylll
Developer using Ubuntu >= 20.04 So try on Ubuntu 20.04
pip install git+https://github.com/bitlogik/lattice-attack pip install git+https://github.com/fplll/fpylll.git
All command try installs not successful both on os windows and Linux
using conda not successful too conda install -c conda-forge fpylll
all methods include update apt too
sudo add-apt-repository universe sudo apt update sudo apt install python3-fpylll
pip install Cython
all fail
remove sagemath and it will work. somehow fpylll clash with sagemath and it does not run properly. removing sagemath will solve your issue. in debian, #apt remove sagemath #apt update then run your lattice_attack.py again.
|
KRASH
|
|
|
vhh
Newbie
Offline
Activity: 13
Merit: 2
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 31, 2023, 07:07:15 PM |
|
If I understand correctly from the answers on github, the creator does not want to change his code.
Well, the code is working as it should, so why should he change it? It finds the priv key from multiple signatures, when some LSB or MSB of each signature nonce is leaked.
|
|
|
|
Bglhn
Newbie
Offline
Activity: 30
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
March 18, 2024, 11:09:26 AM |
|
Hello friends. I've been trying to learn for a while. Where and how do you find the known bit value and Lbs/mbs? No matter what I did, I could not perform a successful lattice attack. I'm sorry for my English and my inexperience. I'm trying to learn.
|
|
|
|
jacky19790729
Jr. Member
Offline
Activity: 82
Merit: 8
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 15, 2024, 04:40:02 PM Last edit: June 16, 2024, 12:14:33 PM by jacky19790729 |
|
Hello friends. I've been trying to learn for a while. Where and how do you find the known bit value and Lbs/mbs? No matter what I did, I could not perform a successful lattice attack. I'm sorry for my English and my inexperience. I'm trying to learn.
https://github.com/bitlogik/lattice-attack lattice-attack lattice-attack only can recovery private key from 252 bit nonce (must know 4 bit from every 88 rsz or signatures ) # python3 gen_data.py -f data252_88.json -m "HelloYou" -c SECP256K1 -b 4 -t MSB -n 88
# python3 lattice_attack.py -f data252_88.json
...... BKZ reduction : block size = 25 ... ...
Key found \o/ 000000000000000000000000F320D5823C07E40B8EA073FF9AF7017C2A9294EB
time: 4.3 second
only 4.3 seconds , I can find my private key when I test 254, 255, 256 bit , even use 1000~2000 rsz , use lattice-attack unable to recovery private key
|
|
|
|
cassondracoffee
Newbie
Offline
Activity: 14
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 26, 2024, 08:55:22 AM Last edit: June 26, 2024, 02:09:36 PM by cassondracoffee |
|
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 E = EllipticCurve(GF(p), [0, 7]) G = E.point( (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)) # Base point import random def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m def sign(privkey,nonce,message): z=message nonceG=nonce*G rx,rye=nonceG.xy() rx=int(rx) s=(z+int(rx)*privkey)*modinv(nonce,n)%n return int(rx), int(s), int(z)
# private=0x12345678901234567890 #example public_key=private*G print('public_key:',public_key) for i in range(1,5):
nonce=random.randrange(2**256-1) message=random.randrange(2**256-1)
r,s,z = sign(private,nonce,message) print("k = ",(nonce)) print() print("r = ",(r)) print("s = ",(s)) print("z = ",(z)) print()
#output public_key: (105243071627259047368667483594044765021982824084363382876153694762750522988401 : 104125598182348586056118441571689985999353468102348956648162259104921527704151 : 1) k = 29083908611578474659724835409188629928450877954572645032653586874541462703237 r = 59696872847024287764883588359229125525293276767477693801880266944929876663510 s = 80010627594232692567321382817171148350979277410542815563295883382250157622365 z = 29046398954207568557559337812845639802158825374855453790727264507720942269061 k = 69337410267126143733445433769841521036184947061861184729931918182952636713603 r = 66204497299302794813448884860580533040028016382253230896212796932956850307851 s = 78197288316910247412893934169331566081232042979407260898010071194692833862752 z = 61490995350470215933587146879107314396788082593003439971438111557980048214364 k = 54369543228147138762559582927936238614035377338157105228406927029717132153226 r = 37044516715065049012561472807452925555312743982989311611730725335033602827346 s = 92461946708536229787310797942574898629331316369909556197824596742434968354935 z = 53622079066303081310409199779963535117997475674801702670649253314258639177195 k = 40168673992090659834561921614463767550862354984631432380883735769884152505584 r = 103919090362588117180151567326283890021253888086769542803093556743402383166255 s = 71275504518099351203494061824773539914502255758119765372192658739494934607323 z = 2815976014827110489026899227085751067228569669674380545422790815579479978003 #data.json { "curve": "SECP256K1", "public_key": [ 105243071627259047368667483594044765021982824084363382876153694762750522988401, 104125598182348586056118441571689985999353468102348956648162259104921527704151 ], "known_type": "MSB", "known_bits": ?, ? how to set correct value "signatures": [ { "r": 59696872847024287764883588359229125525293276767477693801880266944929876663510, "s": 80010627594232692567321382817171148350979277410542815563295883382250157622365, "kp": ? how to set correct value }, { "r": 66204497299302794813448884860580533040028016382253230896212796932956850307851, "s": 78197288316910247412893934169331566081232042979407260898010071194692833862752, "kp": ? how to set correct value }, { "r": 37044516715065049012561472807452925555312743982989311611730725335033602827346, "s": 92461946708536229787310797942574898629331316369909556197824596742434968354935, "kp": ? how to set correct value }, { "r": 103919090362588117180151567326283890021253888086769542803093556743402383166255, "s": 71275504518099351203494061824773539914502255758119765372192658739494934607323, "kp": ? how to set correct value } ], "message": [ 29046398954207568557559337812845639802158825374855453790727264507720942269061, 61490995350470215933587146879107314396788082593003439971438111557980048214364, 53622079066303081310409199779963535117997475674801702670649253314258639177195, 2815976014827110489026899227085751067228569669674380545422790815579479978003 ] } Using my sage code to how to write correct data.json format, please the anyone write correct json format, update my code please.. And the red is that I know a bit how to set Edit: python lattice_attack.py -f data.json ----- Lattice ECDSA Attack ----- Loading data from file data.json Traceback (most recent call last): File "/workspaces/cbmbhpeedwfpy/lattice-attack/lattice_attack.py", line 259, in <module> lattice_attack_cli(arg.f, arg.l) File "/workspaces/cbmbhpeedwfpy/lattice-attack/lattice_attack.py", line 222, in lattice_attack_cli hash_int = ecdsa_lib.sha2_int(bytes(message)) ValueError: bytes must be in range(0, 256) k = 29083908611578474659724835409188629928450877954572645032653586874541462703237 i know MSB red how to set kp: 29083908611578474659724835409188629 # this is correct or not and "known_bits": ? # how to correct know bit and "message": [ 29046398954207568557559337812845639802158825374855453790727264507720942269061, 61490995350470215933587146879107314396788082593003439971438111557980048214364, 53622079066303081310409199779963535117997475674801702670649253314258639177195, 2815976014827110489026899227085751067228569669674380545422790815579479978003 ] message is correct format or not ?? ![Huh](https://bitcointalk.org/Smileys/default/huh.gif)
|
|
|
|
|