what does kangaroo do with numbers?
we give him
1000
1004
he processes them step by step
1000
1001
1002
1003
1004
or
or glues into a string
10001001100210031004
can a kangaroo handle a string of numbers? if it can, can try such a search
Not sure if this was a real question or if you are just pondering how to change Kangaroo.
But Kangaroo, you give it a range, we will stay with your 1000-1004 example. And we are searching for key/pub 1000.
Tame
KEY/#/Point PUBKEY/#/Distance
1000 = 01000
1001 = A1001
1002 = 91002
1003 = 01003
1004 = 71004
Wild (offset of PubKey)
KEY/#/Point PUBKEY/#/Distance
1000 = 00000
1001 = A0001
1002 = 90002
1003 = 00003
1004 = 70004
Above is just example. But, if user told Kangaroo to search for leading DP = 0 bits, then all keys would eventually be entered into hashtable (because Kangaroo makes jumps, not sequential). If you told Kangaroo to search for leading DP = 4 bits, then only key 1000 and 1003 would be entered into hashtable. Then Kangaroo would do a collision check between Tame and Wild; checking if any of the KEY/#/Points match:
Tame
1000 pub = 01000
1000 pub = 00000
Key = Tame Distance - Wild Distance = Priv Key
Key = 01000 - 00000 = Priv Key 1000
Priv key could also be found with 1003.
yes real question.
from
https://github.com/Telariust/pollard-kangarooHow pollard-kangaroo works, the Tame and Wild kangaroos, is a simple explanation.
Suppose there is pubkeyX, unknow privkeyX, but privkeyX is in range w=[L..U]. The keys have a property - if we increase pubkey by S, then its privkey will also increase by S. We start step-by-step to increase pubkeyX by S(i), keeping sumX(S(i)). This is a Wild kangaroo. We select a random privkeyT from range [L..U], compute pubkeyT. We start step-by-step to increment pubkeyT by S(i) while maintaining sumT(S(i)). This is a Tame kangaroo. The size of the jump S(i) is determined by the x coordinate of the current point, so if a Wild or Tame kangaroo lands on one point, their paths will merge. (we are concerned with pseudo random walks whose next step is determined by the current position) Thanks to the Birthday Paradox (Kruskal's card trick), their paths will one day meet. Knowing each traveled path (sumX and sumT), privkeyX is calculated. The number of jumps is approximately 2w1/2 group operations, which is much less than a full search w.
Suppose there is pubkeyX, unknow privkeyX,
but privkeyX is in range w=[L..U].that is, we give him a range, he checks everything num from there?
if user told Kangaroo to search for leading DP = 0 bits, then all keys would eventually be entered into hashtable (because Kangaroo makes jumps, not sequential)
it means that he enters everything into the table, otherwise he can skip past...
if give the program instead
range w=[L..U] randomly generated (in seed(0...1...2...3...etc) order) numbers long of our range w=[L..U]. We just iterate over the seed(). pz 125, 48 dec lenght. It is necessary to empirically find out in which randomly selected number (the longest of our range, acceptable for the search time) the desired number, 48 characters long, may turn out to be. The length of the number we have is limited
range w=[L..U] left to jump on seed() relying on the probability of falling out of the desired.
If so, then you need to investigate the probability of the desired number falling out in the randomly generated range. And this is already the probability both from the length of the random number and from the seed () of the sample from which this number is selected.
of course, it will be quite difficult to find such a number so that the desired one could be in it 48 dec lenght, but in any case it is faster than just search by brute force shifting by a character in a large number...
exampl
123
4567890123
456
567
678
789
890
901
012
123
exampl
num 6 lenght
305683 similarly for 48 lengths pz 125 etc
in set "0","1","2","3","4","5","6","7","8","9" seed(
250), random take 1000 char lenght (
range w=[L..U])
6628108325646789492263743967369759335755330180876937749882483905138112428915013
9054848072269264202560819040354104866048607654607172251754376123013651469513049
5648200952501634505347303680081039514653337468980735311573971468007409323052011
0473225788077579473811677176050310606326591721387075750832843405067707502985666
6876617145832945544955613229276911559767104378637512948667047379064542492920975
2581324109003398367155062153265046958882531259230674050006267332751608318114807
7659936936197772897279551958970524784024371622381672464294673986840979653120419
1377973297040059463032741096578635370403280126662410147279435963632903139195988
5921142354005159220109798247570353825280747075846602460555303063249395364226634
2100020486708402826715206856173778319356312132804659059170036812
3056830692780420939899081369619843410377252264486201655086656380393186164736079012228
1549123570206781972709793858486954913794909950390553544102005076775328421225780
7616262718853368296898188896602573351571258671721308746732768
in set "0","1","2","3","4","5","6","7","8","9" seed(
618), random take 1000 char lenght (
range w=[L..U])
7271521025244124365207776189223775239575217553231514830801677530250829188476058
9584051073104191163434015636888665573089788551375513886590346145184878898638183
4230725850807208425593908647286354440391516972196316264217327283069791943047407
5435634408623970271715415048852321736405170224546087621981489103051717180611070
2022259705447180044620678358697904091834437506271957
3056839567470799313032694934668609814254346562430837032347542160481539801144283721315
6670881397651734966049767791051628938419947125563206965150322651169759574845400
8146472584315136519775634397917280791885905913181878738809851212016739847096395
9225726584627361788453049048321033166991196942042496479487251890643160344901152
5862764587101576517380872702619180367502816723326130852163890478289995273918557
1149637309515538725747409365493288233833950817026792553627640508339998102336790
8186198609312546415241068577642916179067686979509941374153769851338568026033509
7991411852864023386165725877650939884695604158402095378392973053699905562
here's another joke, when you change the set itself for randomness, the final number also changes... "0","1","2","3","4","5","6","7","8","9" > "9","1","2","3","4","5","6","7","8","0" etc can simply enumerate all the permutation options. all combinations of 10 characters (then can choose the length of the sample of the number, "1000 char lenght (
range w=[L..U]" , for the run of all variants of the permutation by adapting to the kangaroo run time). but they can be duplicated))) and the final numbers also change "0","0","0","1","2","3","4","5","6","7","8","9" etc.
***
Or maybe can do without a kangaroo.
pz 64 bit / 4 = 16
4 pieces of 16 bits
look at the dropouts of 16 bit pieces from the set "0","1" random take 16 by manual seed()
example (seed 1000000-10000000)
1111111111111111
1111111100000000
0000000011111111
0000000000000000
num random take seed
1111111111111111 1111111111111111 1114948
1111111111111111 1111111111111111 1160968
1111111111111111 1111111111111111 1195787
1111111111111111 1111111111111111 1234445
1111111111111111 1111111111111111 1236719
1111111111111111 1111111111111111 1416203
1111111111111111 1111111111111111 1446793
1111111111111111 1111111111111111 1456000
1111111111111111 1111111111111111 1473679
1111111111111111 1111111111111111 1528372
1111111111111111 1111111111111111 1700283
1111111111111111 1111111111111111 1863356
1111111111111111 1111111111111111 2067213
1111111111111111 1111111111111111 2130736
1111111111111111 1111111111111111 2135579
1111111111111111 1111111111111111 2165771
1111111111111111 1111111111111111 2238665
1111111111111111 1111111111111111 2239115
1111111111111111 1111111111111111 2272997
1111111111111111 1111111111111111 2275808
1111111111111111 1111111111111111 2449621
1111111111111111 1111111111111111 2473996
1111111111111111 1111111111111111 2551922
1111111111111111 1111111111111111 2588763
1111111111111111 1111111111111111 2652283
1111111111111111 1111111111111111 2663455
1111111111111111 1111111111111111 2803001
1111111111111111 1111111111111111 2829236
1111111111111111 1111111111111111 2840962
1111111111111111 1111111111111111 2850965
1111111111111111 1111111111111111 3078960
1111111111111111 1111111111111111 3085366
1111111111111111 1111111111111111 3235395
1111111111111111 1111111111111111 3301219
1111111111111111 1111111111111111 3353239
1111111111111111 1111111111111111 3367803
1111111111111111 1111111111111111 3434427
1111111111111111 1111111111111111 3464486
1111111111111111 1111111111111111 3567095
1111111111111111 1111111111111111 3617683
1111111111111111 1111111111111111 3776795
1111111111111111 1111111111111111 3834023
1111111111111111 1111111111111111 3902301
1111111111111111 1111111111111111 3906723
1111111111111111 1111111111111111 3998158
1111111111111111 1111111111111111 4395447
...
1111111100000000 1111111100000000 1054187
1111111100000000 1111111100000000 1056509
1111111100000000 1111111100000000 1117232
1111111100000000 1111111100000000 1176072
1111111100000000 1111111100000000 1188876
1111111100000000 1111111100000000 1243485
1111111100000000 1111111100000000 1331323
1111111100000000 1111111100000000 1332986
1111111100000000 1111111100000000 1337370
1111111100000000 1111111100000000 1363459
1111111100000000 1111111100000000 1381417
1111111100000000 1111111100000000 1611291
1111111100000000 1111111100000000 1645681
1111111100000000 1111111100000000 1650418
1111111100000000 1111111100000000 1670070
1111111100000000 1111111100000000 1706046
1111111100000000 1111111100000000 1815838
1111111100000000 1111111100000000 1834227
1111111100000000 1111111100000000 1886796
1111111100000000 1111111100000000 1922279
1111111100000000 1111111100000000 2010195
1111111100000000 1111111100000000 2128263
1111111100000000 1111111100000000 2290889
1111111100000000 1111111100000000 2302560
1111111100000000 1111111100000000 2399428
1111111100000000 1111111100000000 2404067
1111111100000000 1111111100000000 2508910
1111111100000000 1111111100000000 2566310
1111111100000000 1111111100000000 2644365
1111111100000000 1111111100000000 2660616
1111111100000000 1111111100000000 2682201
1111111100000000 1111111100000000 2720460
1111111100000000 1111111100000000 2788235
1111111100000000 1111111100000000 2803556
1111111100000000 1111111100000000 2995909
1111111100000000 1111111100000000 3016738
1111111100000000 1111111100000000 3053510
1111111100000000 1111111100000000 3110902
1111111100000000 1111111100000000 3131325
1111111100000000 1111111100000000 3204443
1111111100000000 1111111100000000 3215189
1111111100000000 1111111100000000 3263944
1111111100000000 1111111100000000 3353340
1111111100000000 1111111100000000 3378959
1111111100000000 1111111100000000 3446082
1111111100000000 1111111100000000 3452072
1111111100000000 1111111100000000 3715477
1111111100000000 1111111100000000 3721299
1111111100000000 1111111100000000 3734948
1111111100000000 1111111100000000 3774280
1111111100000000 1111111100000000 3802499
1111111100000000 1111111100000000 3924776
1111111100000000 1111111100000000 3956617
1111111100000000 1111111100000000 4028377
1111111100000000 1111111100000000 4030971
1111111100000000 1111111100000000 4034149
1111111100000000 1111111100000000 4050906
1111111100000000 1111111100000000 4170148
...
0000000011111111 0000000011111111 1014612
0000000011111111 0000000011111111 1092983
0000000011111111 0000000011111111 1181805
0000000011111111 0000000011111111 1262356
0000000011111111 0000000011111111 1362375
0000000011111111 0000000011111111 1363250
0000000011111111 0000000011111111 1364709
0000000011111111 0000000011111111 1385381
0000000011111111 0000000011111111 1473580
0000000011111111 0000000011111111 1478257
0000000011111111 0000000011111111 1537714
0000000011111111 0000000011111111 1565537
0000000011111111 0000000011111111 1599065
0000000011111111 0000000011111111 1647800
0000000011111111 0000000011111111 1660773
0000000011111111 0000000011111111 1770209
0000000011111111 0000000011111111 1815169
0000000011111111 0000000011111111 1833177
0000000011111111 0000000011111111 1870243
0000000011111111 0000000011111111 1990606
0000000011111111 0000000011111111 2027523
0000000011111111 0000000011111111 2240311
0000000011111111 0000000011111111 2265141
0000000011111111 0000000011111111 2278178
0000000011111111 0000000011111111 2278407
0000000011111111 0000000011111111 2428071
0000000011111111 0000000011111111 2555130
0000000011111111 0000000011111111 2646700
0000000011111111 0000000011111111 2648761
0000000011111111 0000000011111111 2654497
0000000011111111 0000000011111111 2661170
0000000011111111 0000000011111111 2754612
0000000011111111 0000000011111111 2797761
0000000011111111 0000000011111111 2857678
0000000011111111 0000000011111111 2882756
0000000011111111 0000000011111111 2901323
0000000011111111 0000000011111111 2903732
0000000011111111 0000000011111111 2967723
0000000011111111 0000000011111111 2998580
0000000011111111 0000000011111111 3010310
0000000011111111 0000000011111111 3111819
0000000011111111 0000000011111111 3173905
0000000011111111 0000000011111111 3326081
0000000011111111 0000000011111111 3382942
0000000011111111 0000000011111111 3419409
0000000011111111 0000000011111111 3517988
0000000011111111 0000000011111111 3583895
0000000011111111 0000000011111111 3584603
0000000011111111 0000000011111111 3719106
0000000011111111 0000000011111111 3734597
0000000011111111 0000000011111111 3798617
0000000011111111 0000000011111111 3800519
0000000011111111 0000000011111111 3863353
0000000011111111 0000000011111111 3905083
0000000011111111 0000000011111111 3971224
0000000011111111 0000000011111111 4198934
...
0000000000000000 0000000000000000 1102455
0000000000000000 0000000000000000 1198695
0000000000000000 0000000000000000 1344516
0000000000000000 0000000000000000 1467638
0000000000000000 0000000000000000 1475136
0000000000000000 0000000000000000 1556961
0000000000000000 0000000000000000 1612858
0000000000000000 0000000000000000 1657598
0000000000000000 0000000000000000 1701975
0000000000000000 0000000000000000 1751267
0000000000000000 0000000000000000 1866699
0000000000000000 0000000000000000 1916710
0000000000000000 0000000000000000 1988329
0000000000000000 0000000000000000 2020138
0000000000000000 0000000000000000 2128086
0000000000000000 0000000000000000 2356070
0000000000000000 0000000000000000 2428562
0000000000000000 0000000000000000 2533401
0000000000000000 0000000000000000 2598383
0000000000000000 0000000000000000 2657193
0000000000000000 0000000000000000 2816858
0000000000000000 0000000000000000 2879692
0000000000000000 0000000000000000 2920961
0000000000000000 0000000000000000 3020439
0000000000000000 0000000000000000 3027475
0000000000000000 0000000000000000 3028599
0000000000000000 0000000000000000 3084737
0000000000000000 0000000000000000 3101038
0000000000000000 0000000000000000 3106651
0000000000000000 0000000000000000 3239026
0000000000000000 0000000000000000 3245561
0000000000000000 0000000000000000 3263552
0000000000000000 0000000000000000 3266550
0000000000000000 0000000000000000 3404616
0000000000000000 0000000000000000 3446912
0000000000000000 0000000000000000 3468930
0000000000000000 0000000000000000 3534875
0000000000000000 0000000000000000 3584724
0000000000000000 0000000000000000 3723616
0000000000000000 0000000000000000 3764518
0000000000000000 0000000000000000 3800737
0000000000000000 0000000000000000 3923726
0000000000000000 0000000000000000 3976055
0000000000000000 0000000000000000 3978420
0000000000000000 0000000000000000 3988943
0000000000000000 0000000000000000 4190617
0000000000000000 0000000000000000 4231445
0000000000000000 0000000000000000 4233459
0000000000000000 0000000000000000 4287465
0000000000000000 0000000000000000 4321838
0000000000000000 0000000000000000 4328623
0000000000000000 0000000000000000 4364994
...
as can see, some seeds() match the first numbers
1111111111111111 1111111111111111
3776795
1111111100000000 1111111100000000
3715477
1111111100000000 1111111100000000
3721299
1111111100000000 1111111100000000
3734948
1111111100000000 1111111100000000
3774280
0000000011111111 0000000011111111
3719106
0000000011111111 0000000011111111
3734597
0000000011111111 0000000011111111
3798617
0000000000000000 0000000000000000
3723616
0000000000000000 0000000000000000
3764518
then there will be such with repeated first 3 or even 4 digits
and will have to iterate over just 0000-9999 or even 000-999
we can play with seed however we want
1111111111111111 1111111111111111 100000000000000000092928
1111111111111111 1111111111111111 100000000000000000454716
1111111111111111 1111111111111111 100000000000000000532054
1111111111111111 1111111111111111 100000000000000000861504
1111111111111111 1111111111111111 100000000000000001063166
1111111111111111 1111111111111111 100000000000000001079457
1111111111111111 1111111111111111 100000000000000001125196
1111111111111111 1111111111111111 100000000000000001137021
1111111111111111 1111111111111111 100000000000000001196552
1111111111111111 1111111111111111 100000000000000001258352
...
1111111111111111 1111111111111111 100100000000000000054516
1111111111111111 1111111111111111 100100000000000000069416
1111111111111111 1111111111111111 100100000000000000076498
1111111111111111 1111111111111111 100100000000000000178589
1111111111111111 1111111111111111 100100000000000000198487
1111111111111111 1111111111111111 100100000000000000338758
1111111111111111 1111111111111111 100100000000000000341690
1111111111111111 1111111111111111 100100000000000000385849
1111111111111111 1111111111111111 100100000000000000403566
1111111111111111 1111111111111111 100100000000000000459732
1111111111111111 1111111111111111 100100000000000000474863
...
1111111111111111 1111111111111111 100000000100000000078636
1111111111111111 1111111111111111 100000000100000000113259
1111111111111111 1111111111111111 100000000100000000116786
1111111111111111 1111111111111111 100000000100000000206369
1111111111111111 1111111111111111 100000000100000000272648
1111111111111111 1111111111111111 100000000100000000292722
1111111111111111 1111111111111111 100000000100000000405295
1111111111111111 1111111111111111 100000000100000000478474
...
1111111111111111 1111111111111111 107749499999999999922505
1111111111111111 1111111111111111 120909799999999999790902
1111111111111111 1111111111111111 123115299999999999768847
1111111111111111 1111111111111111 131149399999999999688506
1111111111111111 1111111111111111 132521899999999999674781
1111111111111111 1111111111111111 133511799999999999664882
1111111111111111 1111111111111111 134918899999999999650811
1111111111111111 1111111111111111 138612599999999999613874
1111111111111111 1111111111111111 139319399999999999606806
1111111111111111 1111111111111111 146412799999999999535872
...
...
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002123668
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002146904
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002159762
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002206181
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002264561
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002344811
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002455486
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002480462
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000002534433
1111111111111111 1111111111111111 10100000000000000000000000000000000000000000000000000
2729400
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003140504
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003212460
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003284649
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003301676
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003327779
1111111111111111 1111111111111111 101000000000000000000000000000000000000000000000000003409748
...
...
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000001944130
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000001964911
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002022639
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002245698
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002339489
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002435444
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002567005
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002693538
1111111100000000 1111111100000000 10100000000000000000000000000000000000000000000000000
2729828
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002737254
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002972374
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000002984002
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003082988
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003216730
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003221258
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003271554
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003360276
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003476620
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003626369
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003627591
1111111100000000 1111111100000000 101000000000000000000000000000000000000000000000000003679463
...
etc
take fixed first parts for 4 parts of 16 bits
seed
155(random 0000-9999)
155(random 0000-9999)
155(random 0000-9999)
155(random 0000-9999)
1155(random 0000-9999)
1155(random 0000-9999)
1155(random 0000-9999)
1155(random 0000-9999)
10155(random 0000-9999)
10155(random 0000-9999)
10155(random 0000-9999)
10155(random 0000-9999)
100000000000000155(random 0000-9999)
100000000000000155(random 0000-9999)
100000000000000155(random 0000-9999)
100000000000000155(random 0000-9999)
etc
seed(100000000000000155(random 0000-9999))+seed(100000000000000155(random 0000-9999))+seed(100000000000000155(random 0000-9999))+seed(100000000000000155(random 0000-9999))= 64 bit pz 64.
for the next few puzzles, can simply add in front or behind 1 by 2 by 3 all combinations of bits
+0
+1
+00
+10
+01
+11
etc