Pollard's kangaroo ECDLP solver - page 28.

Etar

sr. member

Activity: 652

Merit: 316

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. Wink

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: wedom on October 04, 2021, 01:15:49 PM

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.

wedom

jr. member

Activity: 48

Merit: 11

Quote from: NotATether on October 04, 2021, 12:31:18 PM

...
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

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on October 03, 2021, 12:19:13 PM

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).

Quote from: PawGo on October 04, 2021, 10:44:42 AM

Quote from: NotATether on October 03, 2021, 01:36:01 AM

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

Quote from: a.a on October 04, 2021, 10:50:46 AM

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.

a.a

member

Activity: 126

Merit: 36

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.

PawGo

legendary

Activity: 952

Merit: 1386

Quote from: NotATether on October 03, 2021, 01:36:01 AM

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

member

Activity: 126

Merit: 36

Quote from: bigvito19 on October 03, 2021, 12:19:13 PM

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

Yeah sure. Makes totally sense. Roll Eyes

bigvito19

full member

Activity: 706

Merit: 111

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

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:  [(, <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.

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

elvis13

newbie

Activity: 26

Merit: 2

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

bigvito19

full member

Activity: 706

Merit: 111

Quote from: NotATether on October 02, 2021, 03:05:49 AM

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:  [(, <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

a.a

member

Activity: 126

Merit: 36

Can we have the sourcecode of your program Etar

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

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: [(, <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...

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: Etar on October 01, 2021, 02:25:16 PM

Try to create bsgs with GPU support(cuda).
Now for me result is to slow due to use binary search, not bloom filter or hashtable but...
For test use pubkey in JeanLucPons BSGS example: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
in JeanLucPons BSGS with Xeon X5647 2.93GHz with 12GB of RAM result is 17:46
I use 6x1660super each give around 48Mop/s x134217728, so i found key in 329s this is around 2^ 55.186846572340194 keys/s

Code:

GPU #1 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eba34000000000000 48MKey/s x134217728
GPU #0 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebca0000000000000 47MKey/s x134217728
GPU #2 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb7b0000000000000 48MKey/s x134217728
GPU #5 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ec08c000000000000 50MKey/s x134217728
GPU #3 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb82c000000000000 48MKey/s x134217728
GPU #4 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb878000000000000 48MKey/s x134217728
***********GPU#1************
Total solutions: 1
Winnonce: 6189319
ArrayID: 97454637
GPU #0 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebdc0000000000000 47MKey/s x134217728
SolutionID: 65509676
Yay!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
****************************
Found in 329 seconds

Hashrate low due to use 134217728 baby items, when use 4194304 items hash is around 260Mop/s x4194304 per card.
In this example GPU memory usage is around 2Gb

welcome back welcome back welcome back!!

I thought of BSGS with GPU. But it would have a CPU/central server that would do the baby steps and then the GPUs would do the giant steps.

Etar

sr. member

Activity: 652

Merit: 316

Try to create bsgs with GPU support(cuda).
Now for me result is to slow due to use binary search, not bloom filter or hashtable but...
For test use pubkey in JeanLucPons BSGS example: 0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED8 87AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
in JeanLucPons BSGS with Xeon X5647 2.93GHz with 12GB of RAM result is 17:46
I use 6x1660super each give around 48Mop/s x134217728, so i found key in 329s this is around 2^ 55.186846572340194 keys/s

Code:

GPU #1 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eba34000000000000 48MKey/s x134217728
GPU #0 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebca0000000000000 47MKey/s x134217728
GPU #2 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb7b0000000000000 48MKey/s x134217728
GPU #5 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ec08c000000000000 50MKey/s x134217728
GPU #3 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb82c000000000000 48MKey/s x134217728
GPU #4 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eb878000000000000 48MKey/s x134217728
***********GPU#1************
Total solutions: 1
Winnonce: 6189319
ArrayID: 97454637
GPU #0 Key:49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebdc0000000000000 47MKey/s x134217728
SolutionID: 65509676
Yay!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
****************************
Found in 329 seconds

Hashrate low due to use 134217728 baby items, when use 4194304 items hash is around 260Mop/s x4194304 per card.
In this example GPU memory usage is around 2Gb

_Counselor

member

Activity: 110

Merit: 61

Quote from: COBRAS on September 30, 2021, 08:46:17 PM

If you so cool WP, yor script can find a privkey for 02dd4127ed0232dcf6919e1cbf40562eeb6f050e0cc8663a576482100a51c116fa

Huh

Range only from 1:2^84

Huh

??

If someone find my privkey he get 500$ in btc

??

ASAP please.

There are many GPU renting services across the internet, you can rent power GPU for one hour and find this key spending just a few bucks.
If you're so sure you've found the correct key and the correct range this time, why would you ask anyone to find it?

wedom

jr. member

Activity: 48

Merit: 11

Quote from: COBRAS on September 30, 2021, 08:46:17 PM

Quote from: WanderingPhilospher on September 30, 2021, 06:53:55 PM

Quote

In fact the number 30240 has turned out to be very interesting to me. That one number opened up a horizon of different options for me. And how many Brainless knows these numbers. He knows the idea, he has an easier time with it. I am working on ways to use it. It is unlikely that I can come up with a Brainless solution, since there are millions of these ways and the idea of Brainless itself is unknown. I'm like a blind kitten. That's okay. I love math, I love to think and think and think. Maybe I will someday understand what Brainless meant and come up with a solution. Maybe I'll find another solution. I will think.

Keep on learning and/or trying to learn...

I can openly admit that probably 99% of the people on here are smarter than me when it comes to ec math (but def not Cobras, lol). I do not claim to be an expert at it or programming. But like you, I like to learn and "tinker". I can follow examples and learn from my mistakes. And I have zero issues saying "I was wrong" and if someone calls me out for being wrong, I'm ok with that too, it's how I learn.

If you so cool WP, yor script can find a privkey for 02dd4127ed0232dcf6919e1cbf40562eeb6f050e0cc8663a576482100a51c116fa

Huh

Range only from 1:2^84

Huh

??

If someone find my privkey he get 500$ in btc

??

ASAP please.

If the key is integer, range 84 will be found in kangaroo in a small amount of time. And I think you would have found it a long time ago yourself. Or by the same logic, reduce it by another 15 bits and the kangaroo will find it in 1 second.
I think it is fractional, just like last time. Which means it is in a different range. You have to reduce it so that the result of the reduction is a whole. You can not divide by a number if the original key does not divide by it, I wrote to you about this in personal correspondence.
Not knowing the algorithm how it was obtained means you have to look in a 256 bit range, which is impossible.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote

If you so cool WP, yor script can find a privkey for 02dd4127ed0232dcf6919e1cbf40562eeb6f050e0cc8663a576482100a51c116fa

After a quick review and search, that pubkey is outside of the astro curve, if it could be represented in ecc terms it would be sitting in the 2^296 range (which doesn't exist) but we can reduce it down via qdm space reducer and get it down to around 2^246 without losing its location. We could probably then run lxsx diaphram slex to squeeze it down maybe another 10 bits...12 bits at most. If we do not care about losing keyspace range, we can use orien's reverse beltology (mult with cross division and addpt) and easily get it down to a more comfortable 2^200 range. That is the best that I could do. Maybe someone can shrink it more? How did you come up with 02dd4127ed0232dcf6919e1cbf40562eeb6f050e0cc8663a576482100a51c116fa? I can send away for master and all his slaves to carry back and search for many privets, but master has pinkeye and no bueno. Update: when giant b steps closed in on targeted range and passed range, it triggered the German index calc and estimated the 2^296 but to be honest it could be higher because the gic always works congruently with the Chinese remainder theory and it kicked in and eventually its red solo cup overfilleth and stopped. maybe RAM shortage?! I still honestly believe if mem manufacturers would use streamlined, fractal-shaped perimeters (like flux compression) RAM could be used to full potential...but until that happens (probably never) I will continue researching a binary/hash table function that uses a new matrix: x:= (1:0:1:0) which speeds up search via matrix multiplication and stretches the bounds of unitary transformation, but ultimately will need bigger red solo cup (given an orthonormal basis), IMO. But no one understands or can yet program, in order to hyperbole the keyspace, in pure states, the extremal points of the keyspace range, when dealing with rsc. Any way, find keys and proceed to party...

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: WanderingPhilospher on September 30, 2021, 06:53:55 PM

Quote

In fact the number 30240 has turned out to be very interesting to me. That one number opened up a horizon of different options for me. And how many Brainless knows these numbers. He knows the idea, he has an easier time with it. I am working on ways to use it. It is unlikely that I can come up with a Brainless solution, since there are millions of these ways and the idea of Brainless itself is unknown. I'm like a blind kitten. That's okay. I love math, I love to think and think and think. Maybe I will someday understand what Brainless meant and come up with a solution. Maybe I'll find another solution. I will think.

Keep on learning and/or trying to learn...

I can openly admit that probably 99% of the people on here are smarter than me when it comes to ec math (but def not Cobras, lol). I do not claim to be an expert at it or programming. But like you, I like to learn and "tinker". I can follow examples and learn from my mistakes. And I have zero issues saying "I was wrong" and if someone calls me out for being wrong, I'm ok with that too, it's how I learn.

If you so cool WP, yor script can find a privkey for 02dd4127ed0232dcf6919e1cbf40562eeb6f050e0cc8663a576482100a51c116fa

Huh

Range only from 1:2^84

Huh

??

If someone find my privkey he get 500$ in btc

??

ASAP please.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote

In fact the number 30240 has turned out to be very interesting to me. That one number opened up a horizon of different options for me. And how many Brainless knows these numbers. He knows the idea, he has an easier time with it. I am working on ways to use it. It is unlikely that I can come up with a Brainless solution, since there are millions of these ways and the idea of Brainless itself is unknown. I'm like a blind kitten. That's okay. I love math, I love to think and think and think. Maybe I will someday understand what Brainless meant and come up with a solution. Maybe I'll find another solution. I will think.

Keep on learning and/or trying to learn...

I can openly admit that probably 99% of the people on here are smarter than me when it comes to ec math (but def not Cobras, lol). I do not claim to be an expert at it or programming. But like you, I like to learn and "tinker". I can follow examples and learn from my mistakes. And I have zero issues saying "I was wrong" and if someone calls me out for being wrong, I'm ok with that too, it's how I learn.

Topic: Pollard's kangaroo ECDLP solver - page 28. (Read 60037 times)