Topic: BSGS solver for cuda - page 7. (Read 3999 times)

Yep he was referring to mine.

You should not try to update it to 256-bit store - it's too complicated since you'll have to find a new home for the two flag bits at the end of each store (the ones which limit to the actual search range to 126 bits). This is how the hashtable got screwed.

It is more logical to update it to a 254-bit store instead so you don't have to move the flag bits anywhere.

Thanks for your good explanation, I got how it works.
So multiple xpoints checking (in parallel) is only possible with KeyHunt-CUDA.

Gotcha...no worries, I just did not want to mislead anyone or anyone mislead anyone lol.

But you are right, if it did search in parallel, performance would drop, but I believe it would be due to the giant steps (CPU performs the baby steps). If one had higher end card and wanted to search 2 pubkeys, then I think it would be worth it, to search 2 at same time. I have been running the program on slower card, my test card, for a few days now. The purpose is to see if there is a benefit or angle to attack the 120, 125, 130, etc keys where public key is exposed. More to come with this...

I think I made myself not clear. My native language is German. I apologize. I Looked at it with my programmers eyes.

As you already explained few days ago, cuda BSGS is searching the keys one after another, not in parallel. I know that, I read carefully . With my previous post I meant that even if it would run in parallel it would slow down as described. So read my post in conjunctive and if someone would modify it to process in parallel I expect that behaviours.

I am sure there will be a limit, but it is probably in the millions. For similar programs, it usually caps out at around 30 million addresses, pubkeys, xpoints...

a.a.
Have you ran this program yet? It's just that some of your answers make it seem like you have not ran it at all.

The program does not check keys in parallel, it runs range with one pubkey, once finished, it moves to the next, until the last pubkey has been checked for that specific range.

Interesting List you have. I would have given merits If I had some.

I don't think that they can be effectively searched in parallel. You have to divide each pubkey and check it with the babysteps. So not only do you need to make very expensive global memory lookup (GPU has slow global and super fast local memory) and load each key.

So if you would search multiple keys you would effectively reduce the performance by them. Like 10 keys in parallel means 10 times slower. 2800 keys means 2800 times slower.

Thanks for your great code.
Is there a limit to the number of pubkeys in the input txt file?

Here is the list of 2800 top richest pubkeys:
https://pastebin.com/YMr3BaiU

yes it is, he informed me already about some problems and I should wait until he corrects them

but as I have written already, I could not resist and I migrated it to R1 curve just to try what it does...

yes, you are right, as it is now it behaves a bit non repetitive way, for me it found the keys but solving the same problem more time the time to resolve was from zero (!) seconds to minutes, but I tried only fewer bits search as it was considerably slower than JLP 125b version searching more bits range

I also noticed he changed DP mask meaning (not from left to rigth as original but from right to left) and he "regrets" this as it made me confused

also I noticed there is a problem when having public key in configuration file to solve in 03 mode (only x coordinate)  something is wrong as it falsely reports "point not lie on curve", when in 04 mode it seems to be ok

but let us see and wait if NotATether manages to bring it to life

I was already thinking if there is any way as to test the program before starting it for months..., would it be a change to provide instead of random numbers where algo starts some precalculated values so program would find a test private key in hours? or is there already a way to test the code?

Sorry, I do not understand abbreviation "IMO"  what does it mean?

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.

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

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

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.

Thank you

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


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

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.

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.


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.

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.

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

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.

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?

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.