Pollard's kangaroo ECDLP solver

[a.a]

Can we have the sourcecode of your program Etar

[bigvito19]

Update: I now have a way to empirically guess some ofthe bits of private keys that are randomly generated:

https://gist.github.com/ZenulAbidin/ac00845048c36ceb81df6bc47cbcb4e5

Code:

# First, run this in shell:
# j=1000 # Sample size, feel free to change.
# for ((i=0; $i<$j; i++)); do openssl rand -hex 32 >> ~/Documents/randalysis.txt; echo -en "\n" >> ~/Documents/randalysis.txt; done
# sed -i '/^\s*$/d' ~/Documents/randalysis.txt
# pip install bitarray

import bitarray
import bitarray.util
from os.path import expanduser

sample=1000 # This is the number of example private keys you have generated above.
nkeys = 260 # This is the number of keys you want, change it accordingly.

home = expanduser("~")
with open(home+"/Documents/randalysis.txt", "r") as fp:
    s = fp.read()

l = s.split("\n")
l = l[:-1]   # Remove extraneous blank element
cl = [0]*256
delta = [0]*256

# Values closer to zero - more likely to be zero, values closer to one - more likely to be one
for i in l:                     
    ba = bitarray.util.hex2ba(i)
    ba.reverse()                
    for j in range(0, 256):     
        cl[j] += ba[j]              
        delta[j] = cl[j]/sample

# Values negative - more likely to be zero, values positive - more likely to be one
# Because values will be between -0.5 and 0.5, we must "explode" this
# (by two to get values from -1 to 1)
# to get percentages between 0% and 100% for likely zero and likely one.
deltat = [((delta[t] - 0.5)*2, t) for t in range(0,256)]
deltat = sorted(deltat, key=lambda x: abs(x[0]), reverse=True)
#deltat.sort(key=lambda x: x[0])
#deltatmin = [t for t in deltat if t[0] < 0.5]
#deltatmax = [t for t in deltat if t[0] > 0.5]
#deltatmax.sort(key=lambda x: x[0], reverse=True)
#deltateq = [t for t in deltat if t[0] == 0.5]
#delta = [d - 0.5 for d in delta]

import itertools
lz = []
# Adjust this value to return the combinations of probabilities for larger groups of bits.
# Warning: you should experiment with this setting, because setting this too high will
# make so many combinations, it will finish your RAM.
# Probability theory means that the probability of multiple bits having some specific values is
# __MUCH LESS__ than the probability of one bit having a aprticular value.
maxcomb = 2
for i in range(1,maxcomb+1):
    cdt = itertools.combinations(deltat, i)
    for c in cdt:
        total_prob = 1
        bit_configs = []
        for it in c:
            if it[0] < 0:
                # Zero
                bit_configs.append((it[1], 0))
            elif it[0] < 1:
                # One
                bit_configs.append((it[1], 1))
            else:
                # perfectly even, no bias here so skip to next one
                continue
            total_prob *= abs(it[0])
        lz.append((total_prob*100, bit_configs))

lz.sort(key = lambda x: x[0], reverse=True)

import pprint
print("========== TOP {} MOST LIKELY BIT CONFIGURATIONS (Highest probability first) ==========".format(nkeys))
print("Output format: <probability> [(<bit number between 0-255>, <0 or 1>), ...]")
pprint.pprint(lz[0:nkeys])

The probabilities are quite small though (as they should be), and the highest probabilities are still less than 10%. This could indicate some bias in OpenSSL RNG depending on what the user is doing on the mouse and keyboard...

Can you provide an example

[elvis13]

"Can you provide an example"
I join the request!

[NotATether]

Sure.

Load these 1000 example hex private keys (they are randomly generated which means don't waste your time trying to find money in these - I didn't load them).

https://pastebin.com/WNJLJd2r (too large to post here)

The script will analyze how frequently a 1 or 0 occurs in a certain bit position.

Then it uses the analysis results to estimate the probability of a 1 or 0 occurring in that position.

It also supports analyzing the probability of a sequence of bits occurring in multiple positions, but be warned that that increasing the number of positions to estimate together, uses a lot of memory (A LOT!).

This particular output makes the following result:

Code:

========== TOP 260 MOST LIKELY BIT CONFIGURATIONS (Highest probability first) ==========
Output format: <probability> [(<bit number between 0-255>, <0 or 1>), ...]
[(9.399999999999997, [(33, 0)]),
 (8.600000000000009, [(127, 1)]),
 (7.399999999999995, [(135, 0)]),
 (7.199999999999996, [(153, 0)]),
 (6.999999999999995, [(53, 0)]),
 (6.600000000000006, [(142, 1)]),
 (6.400000000000006, [(32, 1)]),
 (6.400000000000006, [(88, 1)]),
 (6.400000000000006, [(186, 1)]),
 (6.399999999999995, [(124, 0)]),
 (6.399999999999995, [(227, 0)]),
 (6.2000000000000055, [(43, 0)]),
 (5.800000000000005, [(0, 0)]),
 (5.800000000000005, [(2, 0)]),
 (5.800000000000005, [(9, 0)]),
 (5.600000000000005, [(76, 0)]),
 (5.600000000000005, [(94, 1)]),
 (5.600000000000005, [(111, 0)]),
 (5.600000000000005, [(137, 1)]),
 (5.600000000000005, [(196, 1)]),
 (5.600000000000005, [(208, 1)]),
 (5.400000000000005, [(16, 1)]),
 (5.400000000000005, [(247, 1)]),
 (5.200000000000005, [(15, 1)]),
 (5.200000000000005, [(89, 1)]),
 (5.200000000000005, [(147, 1)]),
 (5.200000000000005, [(170, 1)]),
 (5.200000000000005, [(190, 0)]),
 (5.200000000000005, [(212, 0)]),
 (5.200000000000005, [(219, 0)]),
 (5.000000000000004, [(3, 1)]),
 (5.000000000000004, [(36, 1)]),
 (5.000000000000004, [(41, 1)]),
 (4.800000000000004, [(165, 1)]),
 (4.800000000000004, [(169, 0)]),
 (4.600000000000004, [(19, 1)]),
 (4.600000000000004, [(31, 1)]),
 (4.600000000000004, [(112, 1)]),
 (4.600000000000004, [(140, 1)]),
 (4.600000000000004, [(191, 0)]),
 (4.400000000000004, [(22, 1)]),
 (4.400000000000004, [(93, 1)]),
 (4.200000000000004, [(18, 0)]),
 (4.200000000000004, [(64, 1)]),
 (4.200000000000004, [(68, 0)]),
 (4.200000000000004, [(84, 0)]),
 (4.200000000000004, [(174, 1)]),
 (4.200000000000004, [(181, 0)]),
 (4.0000000000000036, [(117, 0)]),
 (4.0000000000000036, [(144, 0)]),
 (4.0000000000000036, [(195, 0)]),
 (4.0000000000000036, [(199, 0)]),
 (4.0000000000000036, [(213, 0)]),
 (4.0000000000000036, [(228, 1)]),
 (3.8000000000000034, [(26, 0)]),
 (3.8000000000000034, [(47, 1)]),
 (3.8000000000000034, [(77, 0)]),
 (3.8000000000000034, [(109, 1)]),
 (3.8000000000000034, [(168, 0)]),
 (3.8000000000000034, [(222, 0)]),
 (3.600000000000003, [(35, 0)]),
 (3.600000000000003, [(61, 1)]),
 (3.600000000000003, [(92, 0)]),
 (3.600000000000003, [(224, 0)]),
 (3.600000000000003, [(225, 1)]),
 (3.600000000000003, [(232, 0)]),
 (3.400000000000003, [(1, 0)]),
 (3.400000000000003, [(40, 0)]),
 (3.400000000000003, [(102, 1)]),
 (3.400000000000003, [(116, 1)]),
 (3.400000000000003, [(188, 1)]),
 (3.400000000000003, [(244, 1)]),
 (3.200000000000003, [(103, 1)]),
 (3.200000000000003, [(108, 0)]),
 (3.200000000000003, [(129, 0)]),
 (3.200000000000003, [(132, 0)]),
 (3.200000000000003, [(139, 1)]),
 (3.200000000000003, [(159, 1)]),
 (3.200000000000003, [(238, 0)]),
 (3.0000000000000027, [(7, 0)]),
 (3.0000000000000027, [(10, 1)]),
 (3.0000000000000027, [(25, 1)]),
 (3.0000000000000027, [(45, 1)]),
 (3.0000000000000027, [(72, 1)]),
 (3.0000000000000027, [(85, 0)]),
 (3.0000000000000027, [(98, 1)]),
 (3.0000000000000027, [(99, 1)]),
 (3.0000000000000027, [(157, 0)]),
 (3.0000000000000027, [(180, 1)]),
 (3.0000000000000027, [(185, 0)]),
 (3.0000000000000027, [(206, 1)]),
 (3.0000000000000027, [(242, 0)]),
 (2.8000000000000025, [(23, 0)]),
 (2.8000000000000025, [(82, 1)]),
 (2.8000000000000025, [(160, 1)]),
 (2.8000000000000025, [(173, 0)]),
 (2.8000000000000025, [(175, 1)]),
 (2.8000000000000025, [(204, 1)]),
 (2.8000000000000025, [(210, 0)]),
 (2.8000000000000025, [(216, 0)]),
 (2.8000000000000025, [(250, 0)]),
 (2.6000000000000023, [(63, 1)]),
 (2.6000000000000023, [(83, 0)]),
 (2.6000000000000023, [(97, 0)]),
 (2.6000000000000023, [(107, 0)]),
 (2.6000000000000023, [(164, 0)]),
 (2.6000000000000023, [(233, 0)]),
 (2.6000000000000023, [(235, 0)]),
 (2.6000000000000023, [(237, 0)]),
 (2.400000000000002, [(105, 1)]),
 (2.400000000000002, [(128, 0)]),
 (2.400000000000002, [(149, 1)]),
 (2.400000000000002, [(158, 0)]),
 (2.400000000000002, [(162, 1)]),
 (2.400000000000002, [(177, 0)]),
 (2.400000000000002, [(179, 1)]),
 (2.400000000000002, [(245, 0)]),
 (2.200000000000002, [(14, 1)]),
 (2.200000000000002, [(27, 1)]),
 (2.200000000000002, [(34, 0)]),
 (2.200000000000002, [(46, 0)]),
 (2.200000000000002, [(95, 1)]),
 (2.200000000000002, [(115, 0)]),
 (2.200000000000002, [(134, 0)]),
 (2.200000000000002, [(146, 1)]),
 (2.200000000000002, [(183, 0)]),
 (2.200000000000002, [(189, 1)]),
 (2.200000000000002, [(200, 0)]),
 (2.200000000000002, [(205, 0)]),
 (2.200000000000002, [(241, 1)]),
 (2.200000000000002, [(243, 1)]),
 (2.0000000000000018, [(54, 0)]),
 (2.0000000000000018, [(58, 0)]),
 (2.0000000000000018, [(113, 0)]),
 (2.0000000000000018, [(119, 1)]),
 (2.0000000000000018, [(133, 0)]),
 (2.0000000000000018, [(155, 1)]),
 (2.0000000000000018, [(194, 0)]),
 (2.0000000000000018, [(240, 1)]),
 (1.8000000000000016, [(42, 0)]),
 (1.8000000000000016, [(62, 0)]),
 (1.8000000000000016, [(65, 1)]),
 (1.8000000000000016, [(67, 0)]),
 (1.8000000000000016, [(104, 0)]),
 (1.8000000000000016, [(131, 0)]),
 (1.8000000000000016, [(152, 1)]),
 (1.8000000000000016, [(176, 0)]),
 (1.8000000000000016, [(217, 0)]),
 (1.8000000000000016, [(226, 1)]),
 (1.6000000000000014, [(39, 0)]),
 (1.6000000000000014, [(57, 0)]),
 (1.6000000000000014, [(74, 1)]),
 (1.6000000000000014, [(80, 1)]),
 (1.6000000000000014, [(121, 1)]),
 (1.6000000000000014, [(182, 0)]),
 (1.6000000000000014, [(215, 1)]),
 (1.4000000000000012, [(6, 1)]),
 (1.4000000000000012, [(52, 0)]),
 (1.4000000000000012, [(75, 1)]),
 (1.4000000000000012, [(81, 1)]),
 (1.4000000000000012, [(87, 1)]),
 (1.4000000000000012, [(101, 1)]),
 (1.4000000000000012, [(123, 1)]),
 (1.4000000000000012, [(198, 1)]),
 (1.4000000000000012, [(214, 0)]),
 (1.4000000000000012, [(236, 1)]),
 (1.4000000000000012, [(249, 1)]),
 (1.4000000000000012, [(253, 0)]),
 (1.4000000000000012, [(255, 0)]),
 (1.200000000000001, [(66, 1)]),
 (1.200000000000001, [(78, 1)]),
 (1.200000000000001, [(86, 1)]),
 (1.200000000000001, [(118, 1)]),
 (1.200000000000001, [(120, 1)]),
 (1.200000000000001, [(130, 0)]),
 (1.200000000000001, [(136, 1)]),
 (1.200000000000001, [(143, 0)]),
 (1.200000000000001, [(145, 0)]),
 (1.200000000000001, [(148, 0)]),
 (1.200000000000001, [(156, 0)]),
 (1.200000000000001, [(218, 1)]),
 (1.200000000000001, [(220, 1)]),
 (1.0000000000000009, [(4, 1)]),
 (1.0000000000000009, [(12, 1)]),
 (1.0000000000000009, [(37, 0)]),
 (1.0000000000000009, [(71, 0)]),
 (1.0000000000000009, [(79, 0)]),
 (1.0000000000000009, [(96, 0)]),
 (1.0000000000000009, [(141, 1)]),
 (1.0000000000000009, [(172, 0)]),
 (1.0000000000000009, [(192, 0)]),
 (1.0000000000000009, [(202, 0)]),
 (1.0000000000000009, [(209, 1)]),
 (1.0000000000000009, [(211, 0)]),
 (1.0000000000000009, [(254, 1)]),
 (0.8084000000000005, [(33, 0), (127, 1)]),
 (0.8000000000000007, [(8, 1)]),
 (0.8000000000000007, [(21, 1)]),
 (0.8000000000000007, [(56, 0)]),
 (0.8000000000000007, [(69, 1)]),
 (0.8000000000000007, [(106, 1)]),
 (0.8000000000000007, [(122, 0)]),
 (0.8000000000000007, [(150, 0)]),
 (0.8000000000000007, [(163, 1)]),
 (0.8000000000000007, [(167, 0)]),
 (0.8000000000000007, [(193, 1)]),
 (0.8000000000000007, [(203, 1)]),
 (0.8000000000000007, [(207, 0)]),
 (0.8000000000000007, [(229, 1)]),
 (0.8000000000000007, [(230, 0)]),
 (0.8000000000000007, [(248, 0)]),
 (0.8000000000000007, [(252, 0)]),
 (0.6955999999999993, [(33, 0), (135, 0)]),
 (0.6767999999999994, [(33, 0), (153, 0)]),
 (0.6579999999999994, [(33, 0), (53, 0)]),
 (0.6364000000000002, [(127, 1), (135, 0)]),
 (0.6204000000000004, [(33, 0), (142, 1)]),
 (0.6192000000000001, [(127, 1), (153, 0)]),
 (0.6020000000000001, [(127, 1), (53, 0)]),
 (0.6016000000000004, [(33, 0), (32, 1)]),
 (0.6016000000000004, [(33, 0), (88, 1)]),
 (0.6016000000000004, [(33, 0), (186, 1)]),
 (0.6015999999999994, [(33, 0), (124, 0)]),
 (0.6015999999999994, [(33, 0), (227, 0)]),
 (0.6000000000000005, [(20, 0)]),
 (0.6000000000000005, [(29, 0)]),
 (0.6000000000000005, [(48, 1)]),
 (0.6000000000000005, [(49, 0)]),
 (0.6000000000000005, [(50, 1)]),
 (0.6000000000000005, [(90, 1)]),
 (0.6000000000000005, [(114, 0)]),
 (0.6000000000000005, [(151, 1)]),
 (0.6000000000000005, [(166, 1)]),
 (0.6000000000000005, [(171, 0)]),
 (0.6000000000000005, [(197, 0)]),
 (0.6000000000000005, [(221, 1)]),
 (0.6000000000000005, [(234, 1)]),
 (0.5828000000000003, [(33, 0), (43, 0)]),
 (0.567600000000001, [(127, 1), (142, 1)]),
 (0.550400000000001, [(127, 1), (32, 1)]),
 (0.550400000000001, [(127, 1), (88, 1)]),
 (0.550400000000001, [(127, 1), (186, 1)]),
 (0.5504, [(127, 1), (124, 0)]),
 (0.5504, [(127, 1), (227, 0)]),
 (0.5452000000000002, [(33, 0), (0, 0)]),
 (0.5452000000000002, [(33, 0), (2, 0)]),
 (0.5452000000000002, [(33, 0), (9, 0)]),
 (0.5332000000000009, [(127, 1), (43, 0)]),
 (0.5327999999999994, [(135, 0), (153, 0)]),
 (0.5264000000000003, [(33, 0), (76, 0)]),
 (0.5264000000000003, [(33, 0), (94, 1)]),
 (0.5264000000000003, [(33, 0), (111, 0)]),
 (0.5264000000000003, [(33, 0), (137, 1)]),
 (0.5264000000000003, [(33, 0), (196, 1)]),
 (0.5264000000000003, [(33, 0), (208, 1)]),
 (0.5179999999999993, [(135, 0), (53, 0)]),
 (0.5076000000000003, [(33, 0), (16, 1)]),
 (0.5076000000000003, [(33, 0), (247, 1)]),
 (0.5039999999999993, [(153, 0), (53, 0)]),
 (0.4988000000000009, [(127, 1), (0, 0)])]

The values on the left, are probabilities of the bit positions on the left (beginning with 0 and ending at 255)  being a 1 or 0 respectively (the second number in the tuple).

Normally when e.g. 40% of bits are 1, that means 60% of them are 0 (another version of this script using this algo can be found here https://gist.github.com/ZenulAbidin/63d13b05f5adda18f03ef2cab577fca3)

But I am calculating the probabilities above, a little differently here.

say 400 out of 1000 of keys have a specific bit at 1 like the example above, that would mean coefficient of 0.4 (where valid values are from 0 to 1 - likeliness of a bit being 1). 0.5 means that the bits are perfectly distributed evenly.

So I take this coefficient and subtract it by 0.5 - which gives a metric of how "chaotic" this bit is [n.b. this has nothing to do with quantum computers and all that].

Negative values here means the bit is more likely to be zero, Positive means more likely to be one. But the larger the absolute value of this result, the less "chaotic" (less likely to vary among larger sample size) this bit is.

This script multiplies these values by 2 to get a result between -1 and 1 (as opposed to -0.5 and 0.5), to allow interpretation as a percentage.

So 0% would be absolute chaos (equivalent to 50/50 probability of 0 or 1 for a given position). 100% would be no chaos at all (since the bit stays the same) and this is what the script is measuring.

<so this script in the form I showed you does not help you guess private key bits, it's just a scientific study of random numbers.>


The other script I linked in this post is using regular probabilities, not chaos percentages by the way.

[bigvito19]

Sure.

Load these 1000 example hex private keys (they are randomly generated which means don't waste your time trying to find money in these - I didn't load them).

https://pastebin.com/WNJLJd2r (too large to post here)

The script will analyze how frequently a 1 or 0 occurs in a certain bit position.

Then it uses the analysis results to estimate the probability of a 1 or 0 occurring in that position.

It also supports analyzing the probability of a sequence of bits occurring in multiple positions, but be warned that that increasing the number of positions to estimate together, uses a lot of memory (A LOT!).

This particular output makes the following result:

Code:

========== TOP 260 MOST LIKELY BIT CONFIGURATIONS (Highest probability first) ==========
Output format: <probability> [(<bit number between 0-255>, <0 or 1>), ...]
[(9.399999999999997, [(33, 0)]),
 (8.600000000000009, [(127, 1)]),
 (7.399999999999995, [(135, 0)]),
 (7.199999999999996, [(153, 0)]),
 (6.999999999999995, [(53, 0)]),
 (6.600000000000006, [(142, 1)]),
 (6.400000000000006, [(32, 1)]),
 (6.400000000000006, [(88, 1)]),
 (6.400000000000006, [(186, 1)]),
 (6.399999999999995, [(124, 0)]),
 (6.399999999999995, [(227, 0)]),
 (6.2000000000000055, [(43, 0)]),
 (5.800000000000005, [(0, 0)]),
 (5.800000000000005, [(2, 0)]),
 (5.800000000000005, [(9, 0)]),
 (5.600000000000005, [(76, 0)]),
 (5.600000000000005, [(94, 1)]),
 (5.600000000000005, [(111, 0)]),
 (5.600000000000005, [(137, 1)]),
 (5.600000000000005, [(196, 1)]),
 (5.600000000000005, [(208, 1)]),
 (5.400000000000005, [(16, 1)]),
 (5.400000000000005, [(247, 1)]),
 (5.200000000000005, [(15, 1)]),
 (5.200000000000005, [(89, 1)]),
 (5.200000000000005, [(147, 1)]),
 (5.200000000000005, [(170, 1)]),
 (5.200000000000005, [(190, 0)]),
 (5.200000000000005, [(212, 0)]),
 (5.200000000000005, [(219, 0)]),
 (5.000000000000004, [(3, 1)]),
 (5.000000000000004, [(36, 1)]),
 (5.000000000000004, [(41, 1)]),
 (4.800000000000004, [(165, 1)]),
 (4.800000000000004, [(169, 0)]),
 (4.600000000000004, [(19, 1)]),
 (4.600000000000004, [(31, 1)]),
 (4.600000000000004, [(112, 1)]),
 (4.600000000000004, [(140, 1)]),
 (4.600000000000004, [(191, 0)]),
 (4.400000000000004, [(22, 1)]),
 (4.400000000000004, [(93, 1)]),
 (4.200000000000004, [(18, 0)]),
 (4.200000000000004, [(64, 1)]),
 (4.200000000000004, [(68, 0)]),
 (4.200000000000004, [(84, 0)]),
 (4.200000000000004, [(174, 1)]),
 (4.200000000000004, [(181, 0)]),
 (4.0000000000000036, [(117, 0)]),
 (4.0000000000000036, [(144, 0)]),
 (4.0000000000000036, [(195, 0)]),
 (4.0000000000000036, [(199, 0)]),
 (4.0000000000000036, [(213, 0)]),
 (4.0000000000000036, [(228, 1)]),
 (3.8000000000000034, [(26, 0)]),
 (3.8000000000000034, [(47, 1)]),
 (3.8000000000000034, [(77, 0)]),
 (3.8000000000000034, [(109, 1)]),
 (3.8000000000000034, [(168, 0)]),
 (3.8000000000000034, [(222, 0)]),
 (3.600000000000003, [(35, 0)]),
 (3.600000000000003, [(61, 1)]),
 (3.600000000000003, [(92, 0)]),
 (3.600000000000003, [(224, 0)]),
 (3.600000000000003, [(225, 1)]),
 (3.600000000000003, [(232, 0)]),
 (3.400000000000003, [(1, 0)]),
 (3.400000000000003, [(40, 0)]),
 (3.400000000000003, [(102, 1)]),
 (3.400000000000003, [(116, 1)]),
 (3.400000000000003, [(188, 1)]),
 (3.400000000000003, [(244, 1)]),
 (3.200000000000003, [(103, 1)]),
 (3.200000000000003, [(108, 0)]),
 (3.200000000000003, [(129, 0)]),
 (3.200000000000003, [(132, 0)]),
 (3.200000000000003, [(139, 1)]),
 (3.200000000000003, [(159, 1)]),
 (3.200000000000003, [(238, 0)]),
 (3.0000000000000027, [(7, 0)]),
 (3.0000000000000027, [(10, 1)]),
 (3.0000000000000027, [(25, 1)]),
 (3.0000000000000027, [(45, 1)]),
 (3.0000000000000027, [(72, 1)]),
 (3.0000000000000027, [(85, 0)]),
 (3.0000000000000027, [(98, 1)]),
 (3.0000000000000027, [(99, 1)]),
 (3.0000000000000027, [(157, 0)]),
 (3.0000000000000027, [(180, 1)]),
 (3.0000000000000027, [(185, 0)]),
 (3.0000000000000027, [(206, 1)]),
 (3.0000000000000027, [(242, 0)]),
 (2.8000000000000025, [(23, 0)]),
 (2.8000000000000025, [(82, 1)]),
 (2.8000000000000025, [(160, 1)]),
 (2.8000000000000025, [(173, 0)]),
 (2.8000000000000025, [(175, 1)]),
 (2.8000000000000025, [(204, 1)]),
 (2.8000000000000025, [(210, 0)]),
 (2.8000000000000025, [(216, 0)]),
 (2.8000000000000025, [(250, 0)]),
 (2.6000000000000023, [(63, 1)]),
 (2.6000000000000023, [(83, 0)]),
 (2.6000000000000023, [(97, 0)]),
 (2.6000000000000023, [(107, 0)]),
 (2.6000000000000023, [(164, 0)]),
 (2.6000000000000023, [(233, 0)]),
 (2.6000000000000023, [(235, 0)]),
 (2.6000000000000023, [(237, 0)]),
 (2.400000000000002, [(105, 1)]),
 (2.400000000000002, [(128, 0)]),
 (2.400000000000002, [(149, 1)]),
 (2.400000000000002, [(158, 0)]),
 (2.400000000000002, [(162, 1)]),
 (2.400000000000002, [(177, 0)]),
 (2.400000000000002, [(179, 1)]),
 (2.400000000000002, [(245, 0)]),
 (2.200000000000002, [(14, 1)]),
 (2.200000000000002, [(27, 1)]),
 (2.200000000000002, [(34, 0)]),
 (2.200000000000002, [(46, 0)]),
 (2.200000000000002, [(95, 1)]),
 (2.200000000000002, [(115, 0)]),
 (2.200000000000002, [(134, 0)]),
 (2.200000000000002, [(146, 1)]),
 (2.200000000000002, [(183, 0)]),
 (2.200000000000002, [(189, 1)]),
 (2.200000000000002, [(200, 0)]),
 (2.200000000000002, [(205, 0)]),
 (2.200000000000002, [(241, 1)]),
 (2.200000000000002, [(243, 1)]),
 (2.0000000000000018, [(54, 0)]),
 (2.0000000000000018, [(58, 0)]),
 (2.0000000000000018, [(113, 0)]),
 (2.0000000000000018, [(119, 1)]),
 (2.0000000000000018, [(133, 0)]),
 (2.0000000000000018, [(155, 1)]),
 (2.0000000000000018, [(194, 0)]),
 (2.0000000000000018, [(240, 1)]),
 (1.8000000000000016, [(42, 0)]),
 (1.8000000000000016, [(62, 0)]),
 (1.8000000000000016, [(65, 1)]),
 (1.8000000000000016, [(67, 0)]),
 (1.8000000000000016, [(104, 0)]),
 (1.8000000000000016, [(131, 0)]),
 (1.8000000000000016, [(152, 1)]),
 (1.8000000000000016, [(176, 0)]),
 (1.8000000000000016, [(217, 0)]),
 (1.8000000000000016, [(226, 1)]),
 (1.6000000000000014, [(39, 0)]),
 (1.6000000000000014, [(57, 0)]),
 (1.6000000000000014, [(74, 1)]),
 (1.6000000000000014, [(80, 1)]),
 (1.6000000000000014, [(121, 1)]),
 (1.6000000000000014, [(182, 0)]),
 (1.6000000000000014, [(215, 1)]),
 (1.4000000000000012, [(6, 1)]),
 (1.4000000000000012, [(52, 0)]),
 (1.4000000000000012, [(75, 1)]),
 (1.4000000000000012, [(81, 1)]),
 (1.4000000000000012, [(87, 1)]),
 (1.4000000000000012, [(101, 1)]),
 (1.4000000000000012, [(123, 1)]),
 (1.4000000000000012, [(198, 1)]),
 (1.4000000000000012, [(214, 0)]),
 (1.4000000000000012, [(236, 1)]),
 (1.4000000000000012, [(249, 1)]),
 (1.4000000000000012, [(253, 0)]),
 (1.4000000000000012, [(255, 0)]),
 (1.200000000000001, [(66, 1)]),
 (1.200000000000001, [(78, 1)]),
 (1.200000000000001, [(86, 1)]),
 (1.200000000000001, [(118, 1)]),
 (1.200000000000001, [(120, 1)]),
 (1.200000000000001, [(130, 0)]),
 (1.200000000000001, [(136, 1)]),
 (1.200000000000001, [(143, 0)]),
 (1.200000000000001, [(145, 0)]),
 (1.200000000000001, [(148, 0)]),
 (1.200000000000001, [(156, 0)]),
 (1.200000000000001, [(218, 1)]),
 (1.200000000000001, [(220, 1)]),
 (1.0000000000000009, [(4, 1)]),
 (1.0000000000000009, [(12, 1)]),
 (1.0000000000000009, [(37, 0)]),
 (1.0000000000000009, [(71, 0)]),
 (1.0000000000000009, [(79, 0)]),
 (1.0000000000000009, [(96, 0)]),
 (1.0000000000000009, [(141, 1)]),
 (1.0000000000000009, [(172, 0)]),
 (1.0000000000000009, [(192, 0)]),
 (1.0000000000000009, [(202, 0)]),
 (1.0000000000000009, [(209, 1)]),
 (1.0000000000000009, [(211, 0)]),
 (1.0000000000000009, [(254, 1)]),
 (0.8084000000000005, [(33, 0), (127, 1)]),
 (0.8000000000000007, [(8, 1)]),
 (0.8000000000000007, [(21, 1)]),
 (0.8000000000000007, [(56, 0)]),
 (0.8000000000000007, [(69, 1)]),
 (0.8000000000000007, [(106, 1)]),
 (0.8000000000000007, [(122, 0)]),
 (0.8000000000000007, [(150, 0)]),
 (0.8000000000000007, [(163, 1)]),
 (0.8000000000000007, [(167, 0)]),
 (0.8000000000000007, [(193, 1)]),
 (0.8000000000000007, [(203, 1)]),
 (0.8000000000000007, [(207, 0)]),
 (0.8000000000000007, [(229, 1)]),
 (0.8000000000000007, [(230, 0)]),
 (0.8000000000000007, [(248, 0)]),
 (0.8000000000000007, [(252, 0)]),
 (0.6955999999999993, [(33, 0), (135, 0)]),
 (0.6767999999999994, [(33, 0), (153, 0)]),
 (0.6579999999999994, [(33, 0), (53, 0)]),
 (0.6364000000000002, [(127, 1), (135, 0)]),
 (0.6204000000000004, [(33, 0), (142, 1)]),
 (0.6192000000000001, [(127, 1), (153, 0)]),
 (0.6020000000000001, [(127, 1), (53, 0)]),
 (0.6016000000000004, [(33, 0), (32, 1)]),
 (0.6016000000000004, [(33, 0), (88, 1)]),
 (0.6016000000000004, [(33, 0), (186, 1)]),
 (0.6015999999999994, [(33, 0), (124, 0)]),
 (0.6015999999999994, [(33, 0), (227, 0)]),
 (0.6000000000000005, [(20, 0)]),
 (0.6000000000000005, [(29, 0)]),
 (0.6000000000000005, [(48, 1)]),
 (0.6000000000000005, [(49, 0)]),
 (0.6000000000000005, [(50, 1)]),
 (0.6000000000000005, [(90, 1)]),
 (0.6000000000000005, [(114, 0)]),
 (0.6000000000000005, [(151, 1)]),
 (0.6000000000000005, [(166, 1)]),
 (0.6000000000000005, [(171, 0)]),
 (0.6000000000000005, [(197, 0)]),
 (0.6000000000000005, [(221, 1)]),
 (0.6000000000000005, [(234, 1)]),
 (0.5828000000000003, [(33, 0), (43, 0)]),
 (0.567600000000001, [(127, 1), (142, 1)]),
 (0.550400000000001, [(127, 1), (32, 1)]),
 (0.550400000000001, [(127, 1), (88, 1)]),
 (0.550400000000001, [(127, 1), (186, 1)]),
 (0.5504, [(127, 1), (124, 0)]),
 (0.5504, [(127, 1), (227, 0)]),
 (0.5452000000000002, [(33, 0), (0, 0)]),
 (0.5452000000000002, [(33, 0), (2, 0)]),
 (0.5452000000000002, [(33, 0), (9, 0)]),
 (0.5332000000000009, [(127, 1), (43, 0)]),
 (0.5327999999999994, [(135, 0), (153, 0)]),
 (0.5264000000000003, [(33, 0), (76, 0)]),
 (0.5264000000000003, [(33, 0), (94, 1)]),
 (0.5264000000000003, [(33, 0), (111, 0)]),
 (0.5264000000000003, [(33, 0), (137, 1)]),
 (0.5264000000000003, [(33, 0), (196, 1)]),
 (0.5264000000000003, [(33, 0), (208, 1)]),
 (0.5179999999999993, [(135, 0), (53, 0)]),
 (0.5076000000000003, [(33, 0), (16, 1)]),
 (0.5076000000000003, [(33, 0), (247, 1)]),
 (0.5039999999999993, [(153, 0), (53, 0)]),
 (0.4988000000000009, [(127, 1), (0, 0)])]

The values on the left, are probabilities of the bit positions on the left (beginning with 0 and ending at 255)  being a 1 or 0 respectively (the second number in the tuple).

Normally when e.g. 40% of bits are 1, that means 60% of them are 0 (another version of this script using this algo can be found here https://gist.github.com/ZenulAbidin/63d13b05f5adda18f03ef2cab577fca3)

But I am calculating the probabilities above, a little differently here.

say 400 out of 1000 of keys have a specific bit at 1 like the example above, that would mean coefficient of 0.4 (where valid values are from 0 to 1 - likeliness of a bit being 1). 0.5 means that the bits are perfectly distributed evenly.

So I take this coefficient and subtract it by 0.5 - which gives a metric of how "chaotic" this bit is [n.b. this has nothing to do with quantum computers and all that].

Negative values here means the bit is more likely to be zero, Positive means more likely to be one. But the larger the absolute value of this result, the less "chaotic" (less likely to vary among larger sample size) this bit is.

This script multiplies these values by 2 to get a result between -1 and 1 (as opposed to -0.5 and 0.5), to allow interpretation as a percentage.

So 0% would be absolute chaos (equivalent to 50/50 probability of 0 or 1 for a given position). 100% would be no chaos at all (since the bit stays the same) and this is what the script is measuring.

<so this script in the form I showed you does not help you guess private key bits, it's just a scientific study of random numbers.>


The other script I linked in this post is using regular probabilities, not chaos percentages by the way.

I tested it and tried it, I kinda wish you could do that with the addresses.

[a.a]

I tested it and tried it, I kinda wish you could do that with the addresses.

Yeah sure. Makes totally sense.   

[PawGo]

It also supports analyzing the probability of a sequence of bits occurring in multiple positions, but be warned that that increasing the number of positions to estimate together, uses a lot of memory (A LOT!).

By the way, maybe that could be interesting for you: https://www.geeksforgeeks.org/longest-common-substring-binary-representation-two-numbers/

[a.a]

I have a conjecture:
The longest amount of consecutive 1 or 0 is sqrt(bits). So sqrt(120) = 10,95. So probably we can skip all numbes which have more than 11 consecutive 1 and 0.

[NotATether]

I tested it and tried it, I kinda wish you could do that with the addresses.

You could but it wouldn't really make sense. It only makes sense when you do this with private keys. But if I can find a way to "jump" between private keys that are more "natural looking" (see close to the end of this post for this expiration) e.g. if I could find terms to get from something like 1101001001 to e.g. 1101001100 instead of each time incrementing by 1, I could make a more efficient search algorithm than the one Bitcrack is currently doing (linear search).

It also supports analyzing the probability of a sequence of bits occurring in multiple positions, but be warned that that increasing the number of positions to estimate together, uses a lot of memory (A LOT!).

By the way, maybe that could be interesting for you: https://www.geeksforgeeks.org/longest-common-substring-binary-representation-two-numbers/

In fact, I have already implemented this in another (private) script of mine. The results were that groups of 1, 2 and 3 zero and one bits were the most common, followed by groups of 4-8 zeros and ones, then everything else longer than that.

If you generate a bunch of random PKs and count how many sequences of 1, 2, 3, etc zero & one bits they have, then compute their mean (call this sample_mean), you can actually use the result to calculate the average standard deviation between the mean and any private key you throw at it - could be a puzzle key, could be someone's random address private key, anything. Call the sequence counts of this testing privkey groups_testingPK_count. Then the avg. std. deviation is just sqrt(mean(variance[sample_mean, groups_testingPK_count])).

Lower (closer to zero in absolute value) is better, because it means keys start to look more like this:

10001101110010011100

Instead of this:

10101010101010101010

Or even this:

11111111111111111111

I have a conjecture:
The longest amount of consecutive 1 or 0 is sqrt(bits). So sqrt(120) = 10,95. So probably we can skip all numbes which have more than 11 consecutive 1 and 0.

In my testing, sequences of greater than 11 zeros or ones only occurred maximum once in an entire sample of 1000 256-bit random numbers.

[wedom]

...
In my testing, sequences of greater than 11 zeros or ones only occurred maximum once in an entire sample of 1000 256-bit random numbers.

I previously did tests of the probability of repeating bits 1111x and 0000x on a range of 256 bits. To do this I generated 100 million urandom(32) keys and looked for bits 0 and 1. Below is a table of the probabilities of repeating bits 1 or 0 on a 256-bit key.
For example, the probability of a key having 16 ones or 16 zeros is 0.367964%
I can look up the code if you need to

Code:

1	100,000000%
2	100,000000%
3	100,000000%
4	100,000000%
5	99,991147%
6	98,673109%
7	87,345356%
8	63,436401%
9	39,012922%
10	21,689362%
11	11,414800%
12	5,843793%
13	2,949750%
14	1,479510%
15	0,737481%
16	0,367964%
17	0,183264%
18	0,091321%
19	0,045563%
20	0,022649%
21	0,011249%
22	0,005631%
23	0,002762%
24	0,001374%
25	0,000654%
26	0,000339%
27	0,000176%
28	0,000086%
29	0,000042%
30	0,000025%
31	0,000016%
32	0,000005%

[NotATether]

I previously did tests of the probability of repeating bits 1111x and 0000x on a range of 256 bits. To do this I generated 100 million urandom(32) keys and looked for bits 0 and 1. Below is a table of the probabilities of repeating bits 1 or 0 on a 256-bit key.
For example, the probability of a key having 16 ones or 16 zeros is 0.367964%
I can look up the code if you need to

~

So this effectively means that bit lengths 15+ are unlikely to occur in a private key because they make up less than 1% of the sample population.

[Etar]

Have a some progress in BSGS for cuda.
Binary search replace with hashtable and after this results is:
With single 2080ti, 570Mgiantstep with 2^26 babysteps HT find key in 338 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)

Code:

GPU #0 Cnt:000000000000000000000000000000000000000000000000bac8c00000000001  570MKey/s x67108864 2^29.16 x2^26=2^55.16
***********GPU#0************
Total solutions: 2
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 338 seconds
GPU #0 finished
cuda finished ok

With 6x1660super, 270Mgiantstep per card with 2^26 babysteps HT find key in 117 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)

Code:

GPU #3 Cnt:000000000000000000000000000000000000000000000000b96a000000000001  272MKey/s x67108864 2^28.09 x2^26=2^54.09
GPU #0 Cnt:000000000000000000000000000000000000000000000000b340000000000001  259MKey/s x67108864 2^28.02 x2^26=2^54.02
GPU #1 Cnt:000000000000000000000000000000000000000000000000ba6e000000000001  274MKey/s x67108864 2^28.10 x2^26=2^54.10
GPU #2 Cnt:000000000000000000000000000000000000000000000000b398000000000001  270MKey/s x67108864 2^28.08 x2^26=2^54.08
***********GPU#3************
Total solutions: 2
GPU #4 Cnt:000000000000000000000000000000000000000000000000bcf0000000000001  269MKey/s x67108864 2^28.08 x2^26=2^54.08
GPU #5 Cnt:000000000000000000000000000000000000000000000000c3fa000000000001  284MKey/s x67108864 2^28.15 x2^26=2^54.15
GPU #0 Cnt:000000000000000000000000000000000000000000000000b658000000000001  261MKey/s x67108864 2^28.03 x2^26=2^54.03
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 117 seconds

Much better than before.

[ymgve2]

You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

Isn't this just a more complicated meet in the middle attack? Another alternative method that also works:

Generate public keys p - 0 .... p - 65535

One of those public keys is guaranteed to have a private key with the lower 16 bits all zeroed out, thus divisible by 65536

Then just calculate private keys with stride 65536: 1 * 65536, 2 * 65536 ..... up until 2^24 * 65536 and match against your generated keys


The issue here is: 1. you need a known public key (not just an address) and 2. as you move up in key size, you need insane storage requirements, like for a 120 bit key the most optimal solution is to generate 2^60 public keys and match those against 2^60 private keys

....which is comparable to what kangaroo already does, but kangaroo doesn't have that large memory requirement.

[dlystyr]

Have a some progress in BSGS for cuda.
Binary search replace with hashtable and after this results is:
With single 2080ti, 570Mgiantstep with 2^26 babysteps HT find key in 338 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)

Code:

GPU #0 Cnt:000000000000000000000000000000000000000000000000bac8c00000000001  570MKey/s x67108864 2^29.16 x2^26=2^55.16
***********GPU#0************
Total solutions: 2
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 338 seconds
GPU #0 finished
cuda finished ok

With 6x660super, 270Mgiantstep per card with 2^26 babysteps HT find key in 117 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)

Code:

GPU #3 Cnt:000000000000000000000000000000000000000000000000b96a000000000001  272MKey/s x67108864 2^28.09 x2^26=2^54.09
GPU #0 Cnt:000000000000000000000000000000000000000000000000b340000000000001  259MKey/s x67108864 2^28.02 x2^26=2^54.02
GPU #1 Cnt:000000000000000000000000000000000000000000000000ba6e000000000001  274MKey/s x67108864 2^28.10 x2^26=2^54.10
GPU #2 Cnt:000000000000000000000000000000000000000000000000b398000000000001  270MKey/s x67108864 2^28.08 x2^26=2^54.08
***********GPU#3************
Total solutions: 2
GPU #4 Cnt:000000000000000000000000000000000000000000000000bcf0000000000001  269MKey/s x67108864 2^28.08 x2^26=2^54.08
GPU #5 Cnt:000000000000000000000000000000000000000000000000c3fa000000000001  284MKey/s x67108864 2^28.15 x2^26=2^54.15
GPU #0 Cnt:000000000000000000000000000000000000000000000000b658000000000001  261MKey/s x67108864 2^28.03 x2^26=2^54.03
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 117 seconds

Much better than before.

If you need help testing I am sure there are 70+ people WANTING to test

additionally if you do want to test speeds I have an RTX 3070

[Etar]

--snip--
If you need help testing I am sure there are 70+ people WANTING to test

additionally if you do want to test speeds I have an RTX 3070

Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.

[NotATether]

~snip
By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

~

Isn't this just a more complicated meet in the middle attack? Another alternative method that also works:

Generate public keys p - 0 .... p - 65535

One of those public keys is guaranteed to have a private key with the lower 16 bits all zeroed out, thus divisible by 65536

Then just calculate private keys with stride 65536: 1 * 65536, 2 * 65536 ..... up until 2^24 * 65536 and match against your generated keys


The issue here is: 1. you need a known public key (not just an address) and 2. as you move up in key size, you need insane storage requirements, like for a 120 bit key the most optimal solution is to generate 2^60 public keys and match those against 2^60 private keys

....which is comparable to what kangaroo already does, but kangaroo doesn't have that large memory requirement.

Except you don't need to calculate all keys with stride 65536 - we know that RNG software will (practically) never generate predictable keys that look like 11111100000 and like that so we measure how "random" a public key looks, by calculating the mean number of sequences (2 1-bits, 3 0-bits, and others) and store them in a vector, then for any PK we want to check we place it as another vector next to that one like this:

[mean   sample]

And compute the avg. std. deviation of that by computing column-wise variance to get 1-column vector [ variance ], then take the mean of all values of that vector, then compute the square root.

The result is a coefficient that tells us how "random-looking" the PK is.

Now if we sort by coefficient, we can eliminate a bunch of stride amounts that give us absurd private keys like the one above. The question is now what is the function that will increment the stride to the next one based on random-looking coefficient?

I have a script for the coefficient calculation and it's working, but I'm on mobile right now so I have to wait to share it later.

[COBRAS]

--snip--
If you need help testing I am sure there are 70+ people WANTING to test

additionally if you do want to test speeds I have an RTX 3070

Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.

Why no linux version ?

Br.

[wedom]

--snip--
If you need help testing I am sure there are 70+ people WANTING to test

additionally if you do want to test speeds I have an RTX 3070

Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.

Hmm.
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126

[Etar]

-snip-
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126

Can`t say. I use PBv5.31 to compile app. It is licensed version(not cracked or so.) But I think if the other more well-known antiviruses did not find anything, then this is a false alarm. And so decide for yourself.

[dextronomous]

Trojan:Win32/Sabsik.FT.A!ml , this one is found by windows,

etayson love your software man, the previous server software great.
now this one greatest, thanks a lot, hope false positive obviously.