brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]

[MrFreeDragon]

-snip-
It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n)

Note that the precision afer 1.000.000 trials is about 1/sqrt(1.000.000)=0.001 so 3 digits are expected to be good.
2^0.825836 = 1.77256  , sqrt(PI) = 1.77245

Your empirical tests actually showed the results very closed to benchmark for Kangaroo known algorithm.
Yes, the 2*sqrt(n) was for simple Kangaroo method.

This is a very nice reading as well: https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf

For three-kangaroo it is 1.818*sqrt(n) - Excercise 14.5.11 in reading above
For four-kkangaroo it is 1.714*sqrt(n) - Excercise  14.5.12 in reading above

You are using herds of kangaroos, so it is not simple one.

Can you please also have a look at the 14.6 section of the reading above? There is a Distributed Kanagroo Algorithm: let Np is the number of processors; [0, w] is the range. They divide the interval into Np sub-intervals of size w/Np and then run the kangaroo algorithm in parallel on each sub-interval.
The solution is to use a herd of Np/2 tame kangaroos and a herd of Np/2 wild kangaroos. This gives an algorithm with running time O(sqrt(w/Np)).

How do you tink, will it be faster?

[Jean_Luc]

Your empirical tests actually showed the results very closed to benchmark for Kangaroo known algorithm.
Yes, the 2*sqrt(n) was for simple Kangaroo method.

The test i did was a simple calculation on a classical birthday paradox on 2 tables instead of one. I draw alternatively a random number in [0..N[ in each table and look for collision between the 2 tables. This converges to sqrt(PI.N). sqrt(PI/2.N) on a single table.

Now, I'm doing tests a in real situation, 1024 kangaroos, 10000 40 bit keys informally distributed, for the moment it seems to converge to 2.sqrt(N) + nbKangaroo.2^dp as expected, with dp=7 on 40bit search. In this situation (1024 << sqrt(N) - 2^dp), the approximation using the asymptote is good.

How do you tink, will it be faster?

Thanks for the reading.
No I don't think it will be faster

Example for Np=2, you have 2 ranges of w/2 so you perform a total of operation:

2.sqrt(w/2) + 2.sqrt(w/2) = 4/sqrt(2).sqrt(w) which is more than 2.sqrt(w)

[arulbero]

I published an exe file for Windows:
https://github.com/JeanLucPons/BSGS/releases/tag/1.0

Hi, I tested on my ubuntu 17.04 (and a mobile cpu: Intel(R) Xeon(R) CPU E3-1505M v6 @ 3.00GHz) your BSGS program with a 64 bit key:

Code:

input file
40000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8

Results:

Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 22:49


Then I replaced only this function void void Int::ModMulK1(Int *a, Int *b) with a my function and I get this result:

Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 20:00


Time ago I did a my version of the break-short program:

time ./break-short
Build Hash
Search Keys
Error!!! False collision!
Error!!! False collision!
Build Hash
Search Keys
Error!!! False collision!
Found private key  1: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4

real   11m58,270s

A note: your program uses 9 GB RAM and 8 cores (for the giant steps), my version of break-short uses 8 GB RAM and only 1 core.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

When I use 18 GB RAM:

Code:

input file
80000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8

your program:

Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 18:19

your program with my function:

Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 17:15


my version of break-short program (16 GB RAM):

time ./break-short
Build Hash
Search Keys
Error!!! False collision!
Found private key  1: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4

real   5m54,964s

If I could use parallel programming and exploit all my 8 cores, I think it would take probably less than 3 minutes to crack a 64 bit key only with a cpu.

[Jean_Luc]

Hi arulbero

The key you tested are
  ...7F2F1A1DDF3E9FF8 so near the worst case if you run with 8 thread.
or ...BB3EF3883C1866D4 idem

I didn't optimized this program up to the ninja level, I spend time on the Kangaroo one

[arulbero]

./kangaroo -d 8 input
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 8
Range width: 2^64
Number of random walk: 2^13.00 (Max DP=17)
DP size: 8 [0xff00000000000000]
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
[16.09 MKey/s][GPU 0.00 MKey/s][Count 2^33.42][Dead 3][13:26][3423.9MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 13:44

with my function in IntMod.cpp:

./kangaroo -d 8 input
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 8
Range width: 2^64
Number of random walk: 2^13.00 (Max DP=17)
DP size: 8 [0xff00000000000000]
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
[21.08 MKey/s][GPU 0.00 MKey/s][Count 2^32.47][Dead 0][05:16][1774.8MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 05:26

[Jean_Luc]

I presume the main differences between your ModMul function (if it is still the same you give me) and mine are in:
imm_umul() where I use intrinsic functions and where you have used inline assembly.
On windows it is not possible to do inline assembly, gcc support intrinsic functions so it should generate a good code.
I really don't want to fight with inline assembly on Linux and this horrible AT&T syntax, i did few ones where no intrinsic exists, this was a nightmare...

[arulbero]

I presume the main differences between your ModMul function (if it is still the same you give me) and mine are in:
imm_umul() where I use intrinsic functions and where you have used inline assembly.
On windows it is not possible to do inline assembly, gcc support intrinsic functions so it should generate a good code.
I really don't want to fight with inline assembly on Linux and this horrible AT&T syntax, i did few ones where no intrinsic exists, this was a nightmare...

Yes, you're right.
Besides when I compile I get this message:

warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp]
   #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance"

Maybe with a new version of gcc the performance of your function would be better on my system.



I replaced ModSquareK1(Int *a) too:

./kangaroo -d 8 input
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 8
Range width: 2^64
Number of random walk: 2^13.00 (Max DP=17)
DP size: 8 [0xff00000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
[24.33 MKey/s][GPU 0.00 MKey/s][Count 2^33.42][Dead 2][08:56][3440.8MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 09:15


from 16 to 24 MKeys/s, +50% ...




EDIT:

2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s  your program

2**(32.47) keys / (5*60+26)s = 18.248.465 = 18,2 MKeys/s  ModMul replaced

2**(33.42) keys / (9*60+15)s = 20707585 = 20,7 MKeys/s  ModMul+ModSqr replaced

2**(33.24) keys / (7*60+58)s = 21223116 = 21,2 MKeys/s  ModMul+ModSqr+ModSub replaced


from 14 to 21,2 MKeys/s: +50%

[COBRAS]

Hello Arulbero. Can you modyfi your break-short  code for import pubkeys from .txt files ?

This very hard recompile and edit code for run tests.

Big thank you.

Have a nice time in this thread.

[Jean_Luc]

warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp]
   #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance"

Yes, do you remenber this ?
We have fighting with a f.ck.ng bug when you have implemented the ModSqr function, i had to add a volatile to prevent gcc to perform optimization !
This volatile is not necessary for gcc > 7.3

[arulbero]

warning: #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance" [-Wcpp]
   #warning "GCC lass than 7.3 detected, upgrade gcc to get best perfromance"

Yes, do you remenber this ?
We have fighting with a f.ck.ng bug when you have implemented the ModSqr function, i had to add a volatile to prevent gcc to perform optimization !
This volatile is not necessary for gcc > 7.3

Ok, I tried with "unsigned char c" (I removed the check):

from
2**(33.42) keys / (13*60+44)s = 13.947.463 = 14 MKeys/s  your program with volatile

to
2**(32.18) keys / (4*60+12.0)s = 19.308.330 = 19,3 MKeys/s with unsigned char

and the bug is still there, with unsigned char I get this error:

./kangaroo -d 8 input
Kangaroo v1.3
ParsePublicKeyHex: Error invalid public key specified (Not lie on elliptic curve)
input, error line 2: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF

it's weird that the program doesn't stop, I think it should terminate in this case.

[COBRAS]

arulbero you giant-step code down then not enoth memory to ?

[nullius]

Etar, you are funny person.

Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length.

You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations.

So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total.

I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM.
It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation.
If I convert to the Etar's unit: It does 14.6 PKey/s.

Newsflash:  I, nullius, have written a very small shell script that can do over 100 trillion operations per second on a single core of an ancient 3.3 GHz CPU!  Here is the source code, including a benchmark, on a Linux system (FreeBSD will be a bit different):

Code:

$ echo '1048576^1024' | time -p bc -sql
12425423456181365279925387080786307311597595610838347638850287747623\
60861068891428772905674656322752135427515054673539621055134262585183\
19758974258574370940046385769635382008544820357548872424501984530330\
07298954744930507666995488232800628320702554659038871038462856168892\
86081195063491219050898500215483033932486747164814339647481138414482\
46888917028564677545436961362035603246262743087461966109644786182741\
43113267232859737251775529839066894535312855298925318702786023730327\
19869958099828161372489304583433717069182227464187121063444543113687\
08508016817415834539561007557262362984166823937246086587688258356477\
00836976266833112093887575424667085600301886904838933510219463816130\
80902598605780629569631487856056084824428655665090823522085781848136\
90257281434662352060481338229879814647807435854905171792202651978347\
81576216598469678835525935558383051575769346443249751553902761298124\
16603376553195639027589983660665862094399483358459126504039467900670\
57848445654106692228540961696646160891611201176550731263658980952921\
79661180975723679821903326940014763241580326424148011608373928415839\
89799573086647874776450926010315260838864367653687522517200666183052\
78046681072569421716140184999814186049906737726847623187904023921869\
96493297393422826404482175417711937716534206615666157396727516750219\
91851182241223465341934177526160075853973517749105067707179469601845\
88330671948952814804211541112010786462301589154313085414717834325712\
13484577645520690543228926603184248994369361889663953324943538057692\
09142925292218241559518002462550357529467477707118089331738992523144\
12851389177004142395041260697284263133880780366217511217984043484829\
53325405978696911189665650780516493277780136150107415182697715538908\
88939125791581583722002310729942726531722583550670593647217988951143\
92521808675257335863861193806735924700446683310178995467034389623843\
34637501209612847511049916048620985432493518099051493506017025211609\
28445644828520351429402092953664848212010413254950535181316532179730\
47923723479492788069287202544924191902788739261046871261774192771595\
98592964369820978291410445759190143932392603554581408191522473988300\
78968537639501149013877800816286561791691358636572217216223056875928\
17092366529353468311118760692178408198029055674402652184529251245244\
02444158263061794917079395096000934259933755433146079126284408690042\
38324933687603968469583639260051178509345170832212772332066117998429\
78113094510577400457305062492992418480494715522786170957895839161090\
90679234697955146377040610964269301216587823655778069747692220154167\
70472400404041730870427533141385209154167773633401949758275582595580\
27019512304014991243449078715269261165419536452307568016928400885256\
23776177665575668603825365845156272635985606083707288176434594230550\
63821924320631190657490067933585520675018760684824866176435920685678\
63296909178438390152244400222647826063647022042540400075485011545999\
00189922038235751253299117681279273929701919536924732136567627766777\
04272072134504254916928323201471851352779331900325117027741482200181\
92390633227909351864687090818155037147671652619953709590048531015638\
67766944930820904022173238020823903767522872288256850258417608533098\
55710889239543384650225162736547201843957566299847464495309572962950\
42100547721511026509080617441578235291230797585596956723791898048054\
94393551619189003705862052625203047394451564786087506671990059650588\
42311700375195922932824912529284060788340967215716848525338227678858\
31002874066317264714873448648393414928386389626018123213950936837951\
21684530567458009683534343813278777818354930730330893607406282866925\
70103938566958665744906496118155917745662805567050399327736908498724\
43501504905974334406632067569317805770368874333462501444598418238980\
06216784554109955223039089466808238818647459407144324415209786295284\
85351735941250780778945454134699359309040121089264637439201843749119\
15314754026062773120219884614094334344501797490773975165855473939626\
21196092140724536492766178184954443337984925556703373475742985168021\
17883078934435817288096762052976538997318141223726183848768580350589\
51200814398904661260693065337549329110975358618511651893597017063680\
49524900823342544481257688601563369725945461590068162007616574017948\
20914771999143977962015245639168441997258587765506763767166710832557\
71563537685088458448130330050803042730162103745712401339034512242847\
09907124547717119635576597246015627200917541559241502943454956637305\
93422940574002248679572906693549431041616952024928826004627897641216\
24770138766738991174439422719554351731082128344265526579459209824096\
26455027947494463143520489497270848150431960954940852601300917188450\
83650067617931857392960118807817462708184256574641193504040258930891\
99839012206942405624559164212070339133396667428983146045638492533064\
03158572693118328234068512101574762869748178279573282408346844832649\
81933372857871230260859650454635805876968974210471318739872847006616\
00804924005284963470674464976828185259204561264958120568094640836916\
06837889924231208724461928878298859310406116888954935403060987516114\
18405904888301595242442948380076830270819668592368944902754888707385\
35204279102855717837455807640171757260262847344547505722807775030875\
94359812363435941904987045950244172865748098743633724075503552976884\
62784080317728680909109997117711330509573013343458585365228551129794\
81049484143528284230564635011417106533259692707337253646177547883252\
44686207799941805384827372103287633228795533147652926838400042889746\
45173471725823456319919737251506683847696994908372466903589572209409\
39398547770207563852186420979082694689548292795391486301958732319406\
71045025668526409833244577121221967764239502649649279354614518521237\
21869340311444598473461599506348960422697831023422091976250909540756\
61895743811394436416668441435649266854835929322540019881764717021766\
29212632259442546037609341731335269657620305531233672864805604650871\
85427651321373449080020221012906959833983342655018947268462816668916\
24294703168898855422382676912113909067081031599264999514935027284486\
39503819472854481747533388916773509467027133785685914059820113289324\
61413428025585667367075371092228092827478558233432174901584085487469\
46201737657601518077611371103354312093969464251033488916198666142138\
7618179306677175709500343297535791418285490176
real 0.01
user 0.01
sys 0.00

Well, you see, I realized that an exponentiation is just a bunch of multiplications.  In this case, 1024 multiplications—and each of those multiplications is 1,047,576 additions.  Thus, I have done 1,073,741,824 additions in 0.01 seconds.  But wait!  If expressed in tally-style unary units, each operand of each of those additions is 1,048,576 additions of the number 1.  Thus, in my units, this counts as 1,125,899,906,842,624 operations in 0.01 seconds.  Ergo, >100 trillion operations per second on a CPU that is almost nine years old.

A genius, am I.

Sadly, I am still only in the “tera” range; but surely, if I were to play semantic games a bit more, I could boost myself into the “peta” range as OP did—or even beyond him, into the “exa” range.

This is well know since the beginning of elliptic curve usage in crypto.
But we count the number of group operation really performed (not the size of the range divided by time).

Soooo...  Let me get this straight:  OP, who has a past history of prolific posting in shitcoin threads before some long post history gaps, suddenly “woke up” and started posting in Development & Technology with wild claims backed only by semantic games and insulting the intelligence of people who know far more than he does.

I did not bother to read the whole thread, which is now nearly 10 pages.  Did I miss anything?

I will give a final explanation of how this works.
***************************************

Extraordinary claims backed by poorly-written explanations riddled with semantic games are the mark of either a crackpot or a scammer.  Take your pick.

I think yo do not understand what are you talking...

Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...

[Lauda]

Tagged this user named Etar for intellectual dishonesty/trying to fool newbies. Do not forget this:

Trust summary for Etar

This user recently woke up from a long period of inactivity.

I think yo do not understand what are you talking...

Clearly you're looking to fool people who don't, sadly for you I'm not one of them. Though the fact that you don't recognize that I do is odd...

[Etar]

@lauda, @ nullius
You are just bored and you decided to flood here?
If you have not read the whole topic, or at least a few pages, then you should not write here.
For people who have problems with trust in people and who see scam in any person, I will repeat
I created the topic because I didn’t know that algorithms such as bsgs or kangaroos had existed for a long time.
In fact, I just shared information and nothing more, and adequate people explained to me that this is not new, but long known.
I did not publish codes, I did not upload releases, so that I could be accused of something.
But it seems like some people just don’t have enough manners in communication.
One reason why i still look here is to find out how things are going Jean_luc with his kangaroo algorithm.

[Lauda]

In fact, I just shared information and nothing more, and adequate people explained to me that this is not new, but long known.

I will rather consult monkeys from the local zoo before I consult you. Please do not post any more of your "information".

[odolvlobo]

I did not bother to read the whole thread, which is now nearly 10 pages.  Did I miss anything?

Yes, you did. The thread is 10 pages because there is stuff going on here, despite the ridiculous title.

Tagged this user named Etar for intellectual dishonesty/trying to fool newbies. Do not forget this:

You are wrong. You didn't bother to read the thread and you just copy-pasted gmaxwell's undeserved negative trust.


Etar doesn't deserve the negative trust.

He claimed rates that are clearly impossible, but that is because his measurement methodology is flawed. He was not lying or trying to misrepresent anything. He was just wrong.

The fact that I challenged him to find 16 specific private keys in a 2⁶⁴ range and he succeeded clearly demonstrates that he has accomplished something. If you want to know the details, you'll have to read the thread.

[Lauda]

He claimed rates that are clearly impossible, but that is because his measurement methodology is flawed. He was not lying or trying to misrepresent anything. He was just wrong.

Insisting that you are right or that you are providing knowledge when you have been proven wrong is malicious, therefore the rating.

The fact that I challenged him to find 16 specific private keys in a 2⁶⁴ range and he succeeded clearly demonstrates that he has accomplished something.

Yes, and I am Santa Claus.
Don't try to teach me how to use the trust system, you have no idea what you are talking about in that aspect.

[nullius]

I did not bother to read the whole thread, which is now nearly 10 pages.  Did I miss anything?

Yes, you did. The thread is 10 pages because there is stuff going on here, despite the ridiculous title.

If you have not read the whole topic, or at least a few pages, then you should not write here.

University professors of the sciences regularly receive e-mails from cranks claiming to have invented perpetual motion machines, free energy devices, simple cures for cancer, etc., etc.  (I know this, because I used to have someone forwarding those to me for my amusement.)  Would you blame them for not wasting their time reading things that are facially incredible and, moreover, presented in the manner of arrogant ignorance?

The topic title, “brute-forcing public keys at amazing speed 2.2 PH/s on CPU”, is not only ridiculous because of the “2.2 PH/s” claim that I parodied:  Nobody who knows anything whatsoever about elliptic curve cryptography would ever talk about “brute-forcing public keys”.  It is stunningly ignorant.  I say that, having some history here of pointing out that Bitcoin’s secp256k1 has a 128-bit security level.  I made that thread because I was sick and tired of people yammering about how long it would take to bruteforce a 2²⁵⁶ keyspace.

If an attacker were to use a bruteforce attack, trying keys one by one, that would require on the order of 2²⁵⁶ work.  (I here ignore the restrictions on valid secp256k1 keys, which reduces that to about 2^255.5; the difference would be negligible in practical terms, and it’s anyway not here relevant.)

However, no serious attacker would ever try to bruteforce elliptic-curve crypto.  Rather, it is estimated that breaking Bitcoin’s 256-bit keys with the best known attacks should require around 2¹²⁸ work [...]

Although I didn’t read this whole thread, I skimmed Etar’s posts from his post history page.  It is easy, because he has been exclusively posting in this thread since 2020-04-07.  Before that, his last post was in a shitcoin thread on 2019-02-06.

I also noticed what others here seem not to, at least not in the first few pages which I did read:  Etar appears to have no history of posting in D&T, at least not that I could find on a cursory check.  He used to post prolifically in shitcoin threads.  In 2017–19, the account had several large posting gaps; then it was dormant for over a year.  It seems to have the same style as before; but that is easy, when the style is basically gibberish.  Anyway, the account suddenly woke up and immediately, exclusively started pushing this thread in a know-it-all belligerent manner.

Let me get this straight:  OP, who has a past history of prolific posting in shitcoin threads before some long post history gaps, suddenly “woke up” and started posting in Development & Technology with wild claims backed only by semantic games and insulting the intelligence of people who know far more than he does.

@lauda, @ nullius
You are just bored and you decided to flood here?

Back at you.

Post history is the kind of thing that Lauda would notice...

Don't try to teach me how to use the trust system, you have no idea what you are talking about in that aspect.

...indeed.

The fact that I challenged him to find 16 specific private keys in a 2⁶⁴ range and he succeeded clearly demonstrates that he has accomplished something. If you want to know the details, you'll have to read the thread.

Eh...

This is well know since the beginning of elliptic curve usage in crypto.
But we count the number of group operation really performed (not the size of the range divided by time).

For instance in my BTCollider which use the DP method (also in O(sqrt(n))), I get 27.9 Mips (GeForce GTX 1050 Ti) for 80bit collision search. That means that I really compute 27.9M group operation and hash per second. It solves 80bit collision in 14h30 (in average). Note that in that case, it have to compute an EC mult for each group operation.

https://github.com/JeanLucPons/BTCCollider

Most famous Square root methods:
- Baby-step Gian-step
- Pollard's Rho algorithm
- Pollard's kangaroo algorithm

Have a look this link as well: https://www.embeddedrelated.com/showarticle/1093.php

You guys are so smart here, I even feel awkward.

[...discussion continued right up to the top of this page.]

So... after others drew him an introductory map of methods better than brute-force, Etar managed to find your challenge keys in a 2⁶⁴ range?  It is manifestly unimpressive for someone with this attitude:

~

if you do not know how, this does not mean that it is impossible.
I'm not going to post programs, source codes or algorithms. It's just a fact.

~

I think yo do not understand what are you talking...
And if you do not understand the topic,

But it seems like some people just don’t have enough manners in communication.

You are not one to be lecturing others on “manners in communication”.  Your rudeness is as bad as your conceited ignorance.

[MrFreeDragon]

The topic started from one things, and continued with others. TC was wrong in some things, however he understood it. However he created a "marketing" name attracted JeanLuc developer and motivated him (i beleive) to continue his job with BSGS annd Kanagroo codes.

Here the message their Jean_Luc promissed to develop ECDLP solver: https://github.com/JeanLucPons/BTCCollider/issues/3

This topic helped to force that work, and JeanLuc finished his BSGS:
https://github.com/JeanLucPons/BSGS

and later Kangaroo on GPU:
https://github.com/JeanLucPons/Kangaroo

The last one (Kangaroo) is amazing. Many thanks to Jean_Luc!

Jean_Luc, i suggest you to create a separate topic about your Kangaroo program and continue discussions there. We can collect some main things (method, tests, benchmarks, etc) and post them in the 1st message of new topic. What do you think about this?

[Jean_Luc]

Yes I agree to open an other topic, I'm still fighting to get the average running time in function of dp and nbKangaroo, this is quite complex and I got unexpected results but interesting
I'll open the new thread when I ends my statistics.