Puzzle Factorization

[iceland2k14]

For the BTC Puzzle https://bitcointalk.org/index.php?topic=5218972.0  to try the possibility of simplification using the probabilistic approach.

If we start analyzing all the Found Keys we see that most of them are NOT PRIME.


So instead of blind bruteforcing we could try to find the maximum likelihood range. This off course may not work for each of the remaining puzzle but if we see them together as a whole there seems to be a way of approach for many of them.
Privatekey being a composite number will have several factors. We are not interested in the Prime Factors but instead all the possible factors. Because once we have (somehow) a factor of the privatekey then the difficulty of that Key is reduced. Before thinking about how we can get a factor of the unknown Key, Lets analyze this concept in the already Found Keys first. There are some interesting observation. Some Keys are hopeless and have very less number of factors but some Keys are juicy and have a factor in almost all bit.
 

If we looks closely in every 10 Keys there is definitely 1 or more juicy Key present. Another observation is we are looking for Factors which are not very small and not very big. Small factor will leave rest of Key bruteforcing almost same level and Big Factor finding itself is a huge challenge. The Best is if the factor is somewhere in closer to the mid level of the Key. So again lets try for this search in existing Keys.



Here if we look for Factors closer to Q1 then we have much narrower range to search for. The same thing can be also observed in Q2 or Q3. Now if we use this range of -10 to 25% of distance for the closest factor and check the same in existing Keys, we can validate that we would have found these puzzles as shown in transparent lines. The beauty of big mid factor is that second factor will also be closer to similar strength and will help in search range limit.

 
Applying the same idea to the remaining Puzzles becomes interesting as the reduction in difficulty level would be significant.


Note:
1. This whole analysis is to focus on the most relevant range, if you do not want to search for everything (hardware or time shortage)
2. If we still have to scan through all the factors and for each Factor all the Keys, then there is no gain in the search
2. For the Pubkey Kangaroo search the overhead of switching factors range would soon overpower the advantage of stride search of Keys

[CY4NiDE]

So if I understood correctly since at least 1 key in a group of ~10 keys probably has factors in almost every lower bit range, we can attempt to reduce the size of the problem by carefully choosing the bit range of the stride values in relation to the keys we are targeting. We can limit the amount of possible values we need to brute force through (stride range is not too big) while still enabling the program to traverse a key space in minimal time (stride value is not too small) thus maximizing the amount of candidates being checked per time unit while drastically reducing the size of the set. We are now searching for a stride value in a much smaller bit range, albeit slower (and there could be more than one value that opens the doors for us, or none).

I like it. This is my current approach:

Code:

import argparse
import random

def generate_hex():
    stride_start = 0x100000000
    stride_end = 0xFFFFFFFFF
    hex_val = random.randint(stride_start, stride_end)
    return hex(hex_val)[2:].upper()

def generate_bat(n):
    with open('random_stride.bat', 'w') as f:
        f.write('@echo off \ncd %~dp0 \nCOLOR B \n')
        for i in range(n):
            hex_val = generate_hex()
            f.write(f':task_{i} \n')
            f.write(f'start /min BitCrack.exe -c --device 0 --out found_by_task_{i}.txt --stride {hex_val} --keyspace {hex_val}:fffffffffffffffffff 13zb1hQbWVsc2S7ZTZnP2G4undNNpdh5so 1BY8GQbnueYofwSuFAT3USAhGjPrkxDdW9 1MVDYgVaSN6iKKEsbzRUAYFrYJadLYZvvZ 19vkiEajfhuZ8bs8Zu2jgmC6oqZbWqhxhG 1PWo3JeB9jrGwfHDNpdGK54CRas7fsVzXU 1JTK7s9YVYywfm5XUH7RNhHJH1LshCaRFR 12VVRNPi4SJqUTsp6FmqDqY5sGosDtysn4 1FWGcVDK3JGzCC3WtkYetULPszMaK2Jksv 1DJh2eHFYQfACPmrvpyWc8MSTYKh7w9eRF \n')
            f.write('timeout /t 120 /nobreak \n')      
            f.write('taskkill /f /im BitCrack.exe \n')
            if i < n-1:
                f.write(f'goto :task_{i+1} \n')
        f.write(':stop \n')

if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('-n', type=int, help='Number of tasks to generate')
    args = parser.parse_args()
    generate_bat(args.n)

It's currently taking me 120 seconds to check two ~36 bit stride values against puzzles 66-76 using two GPUs. Does anyone know of another CUDA based program other than BitCrack that has the stride option?

[GR Sasa]

Hello,

i tried puzzle factoring and took for testing purposes puzzle 64.

Code:

64  | 000000000000000000000000000000000000000000000000F7051F27B09112D4 | 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN | 03100611c54dfef604163b8358f7b7fac13ce478e02cb224ae16d45526b25d9d4d 

Since the private key for #64 is known, i used some websites to get its factor and did a test for puzzle 64.

I used the following strides, and surprisingly i don't know the reason why it didn't catch the private key even though i subtract 1 because of the starting private key, still didn't hit. 

Possible_Strides_For_Puzzle_64:

Code:

124 544615 496846
249 089230 993692
394 391282 406679
788 782564 813358
1183 173847 220037
1577 565129 626716
2366 347694 440074
4732 695388 880148
78068 716480 606301
156137 432961 212602
234206 149441 818903
312274 865922 425204
468412 298883 637806
936824 597767 275612
1 483305 613131 519719
2 966611 226263 039438
4 449916 839394 559157
5 933222 452526 078876
8 899833 678789 118314

None of those strides worked, so i must have did a mistake? Would be nice having your opinions.

[madogss]

Hello,

i tried puzzle factoring and took for testing purposes puzzle 64.

Code:

64  | 000000000000000000000000000000000000000000000000F7051F27B09112D4 | 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN | 03100611c54dfef604163b8358f7b7fac13ce478e02cb224ae16d45526b25d9d4d 

Since the private key for #64 is known, i used some websites to get its factor and did a test for puzzle 64.

I used the following strides, and surprisingly i don't know the reason why it didn't catch the private key even though i subtract 1 because of the starting private key, still didn't hit.  

Possible_Strides_For_Puzzle_64:

Code:

124 544615 496846
249 089230 993692
394 391282 406679
788 782564 813358
1183 173847 220037
1577 565129 626716
2366 347694 440074
4732 695388 880148
78068 716480 606301
156137 432961 212602
234206 149441 818903
312274 865922 425204
468412 298883 637806
936824 597767 275612
1 483305 613131 519719
2 966611 226263 039438
4 449916 839394 559157
5 933222 452526 078876
8 899833 678789 118314

None of those strides worked, so i must have did a mistake? Would be nice having your opinions.

don't know if this would work but have you tried turning them into hex form by that i mean consider those strides as decimal and not hex

[NotATether]

It's kinda hard to identify the prime numbers, as in computing only the non-prime numbers at runtime though, because there is still a huge amount of numbers in Z(2^256) that are not prime.

So you could be multiplying by two, or by three, or by five, or seven, or a combination thereof, but you don't really have anything more efficient than that using this method. Plus if you are just searching these sequences in that order, or even some other order, then you are more likely to miss the actual key (in addition to the risk that the key is prime). Not to mention that multiplication by anything that isn't two is inefficient.

[GR Sasa]

don't know if this would work but have you tried turning them into hex form by that i mean consider those strides as decimal and not hex

Yes, i converted them to Hexadecimal, subtracted 1 because of starting private key, actually no chances i'm not sure what i am doing wrong, i gotta test it more deeply when i get enough time

[CrunchyF]

Privatekey being a composite number will have several factors. We are not interested in the Prime Factors but instead all the possible factors.

what do you mean by "all the possible factors"?
this is what i found by factorizing the priv keys

Code:

Puzzle 1: 0x1 : 1 : 1
Puzzle 2: 0x3 : 3 : 3
Puzzle 3: 0x7 : 7 : 7
Puzzle 4: 0x8 : 8 : 2^3
Puzzle 5: 0x15 : 21 : 3 * 7
Puzzle 6: 0x31 : 49 : 7^2
Puzzle 7: 0x4c : 76 : 2^2 * 19
Puzzle 8: 0xe0 : 224 : 2^5 * 7
Puzzle 9: 0x1d3 : 467 : 467
Puzzle 10: 0x202 : 514 : 2 * 257
Puzzle 11: 0x483 : 1155 : 3 * 5 * 7 * 11
Puzzle 12: 0xa7b : 2683 : 2683
Puzzle 13: 0x1460 : 5216 : 2^5 * 163
Puzzle 14: 0x2930 : 10544 : 2^4 * 659
Puzzle 15: 0x68f3 : 26867 : 67 * 401
Puzzle 16: 0xc936 : 51510 : 2 * 3 * 5 * 17 * 101
Puzzle 17: 0x1764f : 95823 : 3^4 * 7 * 13^2
Puzzle 18: 0x3080d : 198669 : 3 * 47 * 1409
Puzzle 19: 0x5749f : 357535 : 5 * 23 * 3109
Puzzle 20: 0xd2c55 : 863317 : 7 * 13 * 53 * 179
Puzzle 21: 0x1ba534 : 1811764 : 2^2 * 19 * 31 * 769
Puzzle 22: 0x2de40f : 3007503 : 3^3 * 23 * 29 * 167
Puzzle 23: 0x556e52 : 5598802 : 2 * 11 * 254491
Puzzle 24: 0xdc2a04 : 14428676 : 2^2 * 19 * 189851
Puzzle 25: 0x1fa5ee5 : 33185509 : 7 * 4740787
Puzzle 26: 0x340326e : 54538862 : 2 * 7^2 * 556519
Puzzle 27: 0x6ac3875 : 111949941 : 3 * 43 * 867829
Puzzle 28: 0xd916ce8 : 227634408 : 2^3 * 3^3 * 1053863
Puzzle 29: 0x17e2551e : 400708894 : 2 * 83 * 2413909
Puzzle 30: 0x3d94cd64 : 1033162084 : 2^2 * 47 * 5495543
Puzzle 31: 0x7d4fe747 : 2102388551 : 19^2 * 43 * 167 * 811
Puzzle 32: 0xb862a62e : 3093472814 : 2 * 23 * 3001 * 22409
Puzzle 33: 0x1a96ca8d8 : 7137437912 : 2^3 * 11 * 751 * 107999
Puzzle 34: 0x34a65911d : 14133072157 : 19 * 41 * 131 * 138493
Puzzle 35: 0x4aed21170 : 20112871792 : 2^4 * 13 * 96696499
Puzzle 36: 0x9de820a7c : 42387769980 : 2^2 * 3^2 * 5 * 235487611
Puzzle 37: 0x1757756a93 : 100251560595 : 3 * 5 * 6683437373
Puzzle 38: 0x22382facd0 : 146971536592 : 2^4 * 60037 * 153001
Puzzle 39: 0x4b5f8303e9 : 323724968937 : 3^2 * 138319 * 260047
Puzzle 40: 0xe9ae4933d6 : 1003651412950 : 2 * 5^2 * 20073028259
Puzzle 41: 0x153869acc5b : 1458252205147 : 23 * 63402269789
Puzzle 42: 0x2a221c58d8f : 2895374552463 : 3^2 * 59 * 5452682773
Puzzle 43: 0x6bd3b27c591 : 7409811047825 : 5^2 * 587 * 2903 * 173933
Puzzle 44: 0xe02b35a358f : 15404761757071 : 2783789 * 5533739
Puzzle 45: 0x122fca143c05 : 19996463086597 : 157 * 193 * 7477 * 88261
Puzzle 46: 0x2ec18388d544 : 51408670348612 : 2^2 * 5839 * 2201090527
Puzzle 47: 0x6cd610b53cba : 119666659114170 : 2 * 3^3 * 5 * 7 * 17 * 89 * 41847781
Puzzle 48: 0xade6d7ce3b9b : 191206974700443 : 3 * 13 * 4902742941037
Puzzle 49: 0x174176b015f4d : 409118905032525 : 3^2 * 5^2 * 23 * 197 * 1663 * 241313
Puzzle 50: 0x22bd43c2e9354 : 611140496167764 : 2^2 * 3^2 * 12211 * 1390232159
Puzzle 51: 0x75070a1a009d4 : 2058769515153876 : 2^2 * 3 * 7 * 43 * 53 * 197 * 2477 * 22039
Puzzle 52: 0xefae164cb9e3c : 4216495639600700 : 2^2 * 5^2 * 53 * 795565215019
Puzzle 53: 0x180788e47e326c : 6763683971478124 : 2^2 * 14359547 * 117755873
Puzzle 54: 0x236fb6d5ad1f43 : 9974455244496707 : 7019 * 76123 * 18668011
Puzzle 55: 0x6abe1f9b67e114 : 30045390491869460 : 2^2 * 5 * 19 * 79066817083867
Puzzle 56: 0x9d18b63ac4ffdf : 44218742292676575 : 3^2 * 5^2 * 13 * 15117518732539
Puzzle 57: 0x1eb25c90795d61c : 138245758910846492 : 2^2 * 23 * 1002377 * 1499107913
Puzzle 58: 0x2c675b852189a21 : 199976667976342049 : 13 * 167 * 2511323 * 36678953
Puzzle 59: 0x7496cbb87cab44f : 525070384258266191 : 307^2 * 5571097669559
Puzzle 60: 0xfc07a1825367bbe : 1135041350219496382 : 2 * 13 * 31 * 71 * 269 * 587 * 3637 * 34537
Puzzle 61: 0x13c96a3742f64906 : 1425787542618654982 : 2 * 13 * 54837982408409807
Puzzle 62: 0x363d541eb611abee : 3908372542507822062 : 2 * 3 * 43 * 62922991 * 240750329
Puzzle 63: 0x7cce5efdaccf6808 : 8993229949524469768 : 2^3 * 7 * 251 * 2383 * 268491108091
Puzzle 64: 0xf7051f27b09112d4 : 17799667357578236628 : 2^2 * 3 * 19 * 3761 * 408229 * 50847529
Puzzle 65: 0x1a838b13505b26867 : 30568377312064202855 : 5 * 67 * 5639 * 16181749866767

i don't understand how you found the "special" pattern you highlight on your graphics

[iceland2k14]

what do you mean by "all the possible factors"?

For Example for Puzzle 65

Code:

30568377312064202855 : {5, 67, 335, 5639, 28195, 377813, 1889065, 16181749866767, 80908749333835, 1084177241073389, 5420886205366945, 91248887498699113, 456244437493495565, 6113675462412840571, 30568377312064202855}

[CrunchyF]

Ok thanks.
I generated 400 randoms privkeys in the range of puzzle 64-65.
I obtain that with all factors of every key:



the specific pattern you noticed occurs around 1/10 times (as you found before)
so i don't think this a way to say that the priv key of the puzzle was not generated randomly and we can find a trick to speed up the search

 

[iceland2k14]

so i don't think this a way to say that the priv key of the puzzle was not generated randomly and we can find a trick to speed up the search

It is not about how the privatekey is generated. We know that process already. The creator himself told that.

It is about the way of searching most relevant range first thinking about the 84 remaining puzzles. As clearly mentioned in Note 1 and 2.

[COBRAS]

How this factors correlate with difference in quantity of 0 and  quantity of 1 in privkey in bin format?


Difference is has, most probably key and not, for ex with  quantity of  zero -
  quantity of ones = 6 more probably , or  =2 less probably , or  =0 les less probably, etc not need generate all privkeys.

[iceland2k14]

By the Way, Puzzle 66 was juicy too.