BSGS solver for cuda

[Etar]

Total: 4294967296 bytes
Save BIN file:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798_536870912_b.BI N

• chunk:2147483648b

Error when saving chunk: save:2147483648b, got:-2147483648b
Press Enter to exit


  new error

Download 1.3.2 version. decreased chunk size to 1Gb

[studyroom1]

Total: 4294967296 bytes
Save BIN file:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798_536870912_b.BI N

• chunk:2147483648b

Error when saving chunk: save:2147483648b, got:-2147483648b
Press Enter to exit


  new error

Download 1.3.2 version. decreased chunk size to 1Gb

let me try

[hamnaz]

Is there any script to uncompress multiple pubkeys in a file?
like this script: BTC Adresses > HASH160
https://github.com/sezginyildirim91/btc-address-to-hash160

here i see post related to compress to uncompress and uncompress to compress (codes)
https://bitcointalk.org/index.php?topic=5244940.msg57700007#msg57700007

[a.a]

Use bitcoin-tool.
https://github.com/matja/bitcoin-tool

[davidjjones]

Is there any script to uncompress multiple pubkeys in a file?
like this script: BTC Adresses > HASH160
https://github.com/sezginyildirim91/btc-address-to-hash160

here i see post related to compress to uncompress and uncompress to compress (codes)
https://bitcointalk.org/index.php?topic=5244940.msg57700007#msg57700007

Thank you

[studyroom1]

help me to understand which one is faster when you are searching multiple keys from file

BSGS or Kangaroo?

i heard that if you load list of PB keys in kangaroo it is not checking all simultaneously, is it true?

if over 80 bit kangaroo is more efficient and fast than bsgs please explain why?

[a.a]

Currently there is no known implementation of kangaroo algorithm which handles multiple pubkeys. JLPs implementation processes each pubkey consecutively.

BSGS is possible to handle each pubkey simultaneously.

Which one is faster? Depends.

[studyroom1]

Currently there is no known implementation of kangaroo algorithm which handles multiple pubkeys. JLPs implementation processes each pubkey consecutively.

BSGS is possible to handle each pubkey simultaneously.

Which one is faster? Depends.

so maybe your meaning is JLP first get one key from file and process only on that until he will find that in collision and than will process second one

and BSGS somewhat i know is checking all same time

[WanderingPhilospher]

Currently there is no known implementation of kangaroo algorithm which handles multiple pubkeys. JLPs implementation processes each pubkey consecutively.

BSGS is possible to handle each pubkey simultaneously.

Which one is faster? Depends.

so maybe your meaning is JLP first get one key from file and process only on that until he will find that in collision and than will process second one

and BSGS somewhat i know is checking all same time

Currently, JLP Kangaroo and BSGS Cuda, both process each pub key, one at a time. Neither are currently programmed to search for multiple pub keys at once.

In my limited tests, I can tell you BSGS Cuda is at least faster, when searching multiple pub keys (one at a time), in the 72 bit range. BSGS gives you 100% check a key is or is not in a range, Kangaroo does not, you have to at least set the -m option to -m 6 to get a 99% rate that the key is or is not in a range.

[sky59sky59]

Do you mean to say that bsgs algo gives you 100% information if key is or is not in s given range k1-k2?

Or you say bsgs would find private key even if k1 k2 interval is incorrect?

I had a closer look at JLP bsgs code (not cuda you speak about) and it seems there is no limit to 125 or 128 bit for search interval? Is bsgs by nature searching whole 256 bit range?

[a.a]

You should read the articles about Pollards Kangaroo Algorithm and BSGS.
If you find the key with BSGS in range, than you know 100% for sure, that the key is in range. And if a baby step is not found in the defined range for the pubkey than it will find no solution.

[sky59sky59]

You should read the articles about Pollards Kangaroo Algorithm and BSGS.
If you find the key with BSGS in range, than you know 100% for sure, that the key is in range. And if a baby step is not found in the defined range for the pubkey than it will find no solution.

I do not know if you are joking or serious.
Your answer is totally useless and does not even touch any of my questions.
Claiming that if you find key in range then you are sure 100% is there is childisch and raising my doubts for your mental health

[a.a]

Actually my original answer was kind of rough and was basically
Like: your questions are stupid, first inform yourself what the different cracking methods are doing on Wikipedia and then ask again before wasting our time. Then I thought, I should be friendly and removed the toxic part. Now to read your answer encourages me to give you a rough answer.

So yes your question about BSGS is total bullshit. BSGS looks for the right babysteps. If It finds the right babysteps, then it can determine by doing the giant steps the actual value of the private key. This is clearly described in wikipedia.

Do you mean to say that bsgs algo gives you 100% information if key is or is not in s given range k1-k2?

This question is stupid. Obviously if BSGS ran a range and did or did not find a solution it means that the key is or is not in range k1-k2.

Or you say bsgs would find private key even if k1 k2 interval is incorrect?

How is this even possible, when already babysteps don't find a value? This question is totally stupid.

Please first do some fundamental research. Maybe then you won't waste your and our time by asking totally stupid questions and blaming others for giving supposedly stupid answer despite the fact reading wikipedia and using your own brain would give you the logical answer.

[sky59sky59]

If you feel wasting your time you should not react at all

Anyway, your answer is like saying baby steps must find it (what) first. Total bullshit.

[a.a]

If you feel wasting your time you should not react at all

I was answering nice to even reach out to someone who asks such uninformed questions.

Anyway, your answer is like saying baby steps must find it (what) first. Total bullshit.

To understand babystep giantstep read the wiki article https://en.wikipedia.org/wiki/Baby-step_giant-step

If you search in a range, you just need to generate a small babystep lookup table, with potential steps in that range. But if you are looking for a value outside the provided range, the babystep lookup table wont contain the necessary value! So you are having no hit.

The english WP contains no example, but the german one contains an example:
https://de.wikipedia.org/wiki/Babystep-Giantstep-Algorithmus#Beispiel

[sky59sky59]

Thank you

[WanderingPhilospher]

Do you mean to say that bsgs algo gives you 100% information if key is or is not in s given range k1-k2?

Or you say bsgs would find private key even if k1 k2 interval is incorrect?

I had a closer look at JLP bsgs code (not cuda you speak about) and it seems there is no limit to 125 or 128 bit for search interval? Is bsgs by nature searching whole 256 bit range?

Apart from testing a program, meaning we know a key lies in a range we are using to test a program, to see if program works and can find the key that we know is in the range we are searching....

So if you are searching a range and do not know if the key you are searching for lies in the range, if you run the range with BSGS program, if the key is not found, then you know for 100% sure, that the key is not in that range. If you use JLP Kangaroo, you have to at least set the -m option to -m 6, if the program does not find the key, then you know with 99% sure, the key is not in the range.

BSGS will 100% tell you if the key is or is not in the range you are searching.

JLP BSGS is not limited to any bit range; meaning you can search in a 10 bit range or a 256 bit range.

Both programs search in the range you specify. If you specify a 64 bit range, that is what the program will search; if you specify a 256 bit range, that is what the program will search.

[Etar]

New release v1.4.0
supported compressed/uncompressed format public keys
removed binsort program (don`t need sorted array any more)
baby array need only first time to create HT (or rebuild HT when -htsz changed)
After HT created and saved, next time you will need less ram and only HT, giant array to launch.
with single 2080ti (parameters -w 29   -htsz 28) find 16 public keys from example JLP bsgs in 2m 30s

Code:

GPU#0 Cnt:0000000000000000000000000000000000000000000000006ce8000000000001 869MKey/s x536870912 2^29.76 x2^30=2^59.76
***********GPU#0************
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e7ad38337c7f173c7
Pub: 55b95bef84a6045a505d015ef15e136e0a31cc2aa00fa4bca62e5df215ee981b3b4d6bce33718dc6cf59f28b550648d7e8b2796ac36f25ff0c01f8bc42a16fd9
****************************
Found in 9 seconds
GPU#0 job finished
Working time 00:02:30s
Total time 00:03:16s

[sky59sky59]

BSGS will 100% tell you if the key is or is not in the range you are searching.

JLP BSGS is not limited to any bit range; meaning you can search in a 10 bit range or a 256 bit range.

Thank you for exhausting explanation!

I hope I understand correct both JLP and "cuda" BSGS work up to 256bit size search

Maybe you noticed I migrated JLP bsgs from curve k1 to r1. It was success. I started it for interval almost 256bit:
1000000000....0000000
EFFF.....................FFFFF

I know it will probably not succeed in this century but it is not impossible I want to try to find private key for gr**npass

I continue to work to migrate also  Kangaroo256 to r1 curve but I was told by the author to wait a bit until he updates hastables (?)
Anyway, I migrated cpu part already just to see how is the behaviour of the code. I already reported him my findings, it is here on the forum

[WanderingPhilospher]

I continue to work to migrate also  Kangaroo256 to r1 curve but I was told by the author to wait a bit until he updates hastables (?)

Not sure which author you are referring to, but if this is NotATether's version, I would not use it. Very buggy and last known speed is compromised and the program does not find keys.
The only thing needed, IMO, to upgrade JLPs original Kangaroo to be able to search a 256 bit range, was to update the limited 128 bit store function to a 256 bit store function (plus the + - and type bits) so the program could solve key. I have not looked at the code of the new 256bit version, but it seems it does not find keys.

Original JLP Kangaroo, you can search a 256 bit range for a key but since it only stores 128 bits for the distances, you will not solve key properly because it is missing 128 bits of the distance (private key), which is needed to reconstruct the private key of the pub key you are searching for.