Search content
Sort by

Showing 7 of 7 results by Chail35
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 19/09/2024, 00:30:04 UTC
Here is a calculator to calculate the estimated time it would take to use the Kangaroo Algorithm on a given range and the Keys per second:

Code:
import math
import re

def normalize_key(key):
    # Remove '0x' prefix if present
    key = key.lower().replace('0x', '')
   
    # Pad with leading zeros if necessary
    key = key.zfill(64)
   
    # Ensure the key is 64 characters long
    if len(key) != 64:
        raise ValueError("Invalid key length. Must be 64 hexadecimal characters.")
   
    return key

def parse_keys_per_second(kps_input):
    # Remove commas and convert to float
    kps = float(kps_input.replace(',', ''))
    return kps

def pollards_kangaroo_time(start_key, stop_key, keys_per_second):
    # Convert hexadecimal keys to integers
    start = int(start_key, 16)
    stop = int(stop_key, 16)
   
    # Calculate the range size
    range_size = stop - start + 1
   
    # Pollard's Kangaroo expected number of steps
    # The square root of the range size multiplied by 2
    expected_steps = int(2 * math.sqrt(range_size))
   
    # Calculate time in seconds
    time_seconds = expected_steps / keys_per_second
   
    # Convert to more readable time units
    minutes, seconds = divmod(time_seconds, 60)
    hours, minutes = divmod(minutes, 60)
    days, hours = divmod(hours, 24)
    years, days = divmod(days, 365.25)  # Using 365.25 to account for leap years
   
    return years, days, hours, minutes, seconds, expected_steps, range_size

# Get input from user
start_key = input("Enter start key (64 hex chars, or shorter hex number): ")
stop_key = input("Enter stop key (64 hex chars, or shorter hex number): ")
keys_per_second = input("Enter keys per second (e.g., 29500000000 or 29,500,000,000): ")

# Normalize and validate inputs
try:
    start_key = normalize_key(start_key)
    stop_key = normalize_key(stop_key)
    keys_per_second = parse_keys_per_second(keys_per_second)
except ValueError as e:
    print(f"Error: {e}")
    exit(1)

# Calculate time and steps
years, days, hours, minutes, seconds, expected_steps, range_size = pollards_kangaroo_time(start_key, stop_key, keys_per_second)

# Print results
print(f"\nEstimated time to complete Pollard's Kangaroo algorithm:")
print(f"{years:.2f} years, {days:.2f} days, {hours:.2f} hours, {minutes:.2f} minutes, {seconds:.2f} seconds")

print(f"\nTotal operations (expected steps): {expected_steps:,}")
print(f"Total key range size: {range_size:,}")

# Calculate speedup compared to brute force
brute_force_time = range_size / keys_per_second
pollard_time = years * 365.25 * 86400 + days * 86400 + hours * 3600 + minutes * 60 + seconds
speedup = brute_force_time / pollard_time

print(f"\nSpeedup compared to brute force: {speedup:.2f}x")

I know it gives good estimates because I ran a test on puzzle 100 with my 4070 and the program said it would take about 14 days at about 1340 MK/s:

Code:
Kangaroo v2.2
Start:8000000000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 32
Range width: 2^99
Jump Avg distance: 2^48.95
Number of kangaroos: 2^20.55
Suggested DP: 26
Expected operations: 2^50.61
Expected RAM: 990.8MB
DP size: 26 [0xffffffc000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 29: 1024 kangaroos
SolveKeyCPU Thread 14: 1024 kangaroos
SolveKeyCPU Thread 17: 1024 kangaroos
SolveKeyCPU Thread 20: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 16: 1024 kangaroos
SolveKeyCPU Thread 9: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 24: 1024 kangaroos
SolveKeyCPU Thread 12: 1024 kangaroos
SolveKeyCPU Thread 18: 1024 kangaroos
SolveKeyCPU Thread 15: 1024 kangaroos
SolveKeyCPU Thread 25: 1024 kangaroos
SolveKeyCPU Thread 22: 1024 kangaroos
SolveKeyCPU Thread 31: 1024 kangaroos
SolveKeyCPU Thread 8: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 13: 1024 kangaroos
SolveKeyCPU Thread 27: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
SolveKeyCPU Thread 26: 1024 kangaroos
SolveKeyCPU Thread 11: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 23: 1024 kangaroos
SolveKeyCPU Thread 30: 1024 kangaroos
SolveKeyCPU Thread 19: 1024 kangaroos
SolveKeyCPU Thread 28: 1024 kangaroos
SolveKeyCPU Thread 10: 1024 kangaroos
SolveKeyCPU Thread 21: 1024 kangaroos
GPU: GPU #0 NVIDIA GeForce RTX 4070 (46x0 cores) Grid(92x128) (122.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.52 kangaroos [21.0s]
[1342.45 MK/s][GPU 1264.50 MK/s][Count 2^38.15][Dead 0][04:18 (Avg 14.8d)][2.1/4.7MB]

And this is what the calculator estimated:

Enter start key (64 hex chars, or shorter hex number): 8000000000000000000000000
Enter stop key (64 hex chars, or shorter hex number): FFFFFFFFFFFFFFFFFFFFFFFFF
Enter keys per second (e.g., 29500000000 or 29,500,000,000): 1,342,450,000

Estimated time to complete Pollard's Kangaroo algorithm:
0.00 years, 13.00 days, 17.00 hours, 28.00 minutes, 7.32 seconds

Total operations (expected steps): 1,592,262,918,131,443
Total key range size: 633,825,300,114,114,700,748,351,602,688

Speedup compared to brute force: 398065729532860.81x

Now, I know this is a stretch and isn't possible in its current state but you'll get the point. Hypothetically, if you were to use Elon Musk's new supercomputer with 100,000 H100s to run the Kangaroo Algorithm on puzzle 130 (doesn't have to be JLP), it would take about 18.5 hours:

Enter start key (64 hex chars, or shorter hex number): 200000000000000000000000000000000
Enter stop key (64 hex chars, or shorter hex number): 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Enter keys per second (e.g., 29500000000 or 29,500,000,000): 781250000000000

Estimated time to complete Pollard's Kangaroo algorithm:
0.00 years, 0.00 days, 18.00 hours, 33.00 minutes, 4.35 seconds

Total operations (expected steps): 52,175,271,301,331,132,416
Total key range size: 680,564,733,841,876,926,926,749,214,863,536,422,912

Speedup compared to brute force: 13043817825332781056.00x

Just thought I would share FYI
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 27/06/2024, 22:14:45 UTC
I have a question
It is for people who know the Kangaroo program well.

Kangaroo program has a multiple pubkey search feature, but it searches sequentially. that is, key1 key2 key3. It does not search for key2 before key1 is found. Likewise, it does not search for key3 unless key2 is found. I AM GIVING AN EXAMPLE. We have created 500 pubkeys. Is it possible to search all of them at the same time? Is there anyone working on this? can you share?

You would have to run on 500 different machines if you wanted to execute the search in parallel depending on the bit range, with the same amount of power. Think of it like this lets say you wanted to search 500 pubkeys in 125 bit range all at the same time, the computing power would be spread too thin it would be more efficient to just run a single pubkey search on 500 different machines concurrently, even though it sounds crazy. I think this is where FUTURE quantum computers would come in. now if you wanted to search for 500 pubkeys in say the 50 bit range, with modern a gpu you could do it relatively quick on 1 computer .
Post
Topic
Board Development & Technical Discussion
Re: divided Pubkey -> Privkey
by
Chail35
on 18/05/2024, 06:15:19 UTC
Hi sir it works perfectly but when range is 80 or more I cannot find because range is big to find the divided pubkey and do calculation. What can I do in that situation to solve that problem? Example I want to do calculation with 125 bit range pub key.

Unfortunately there's no workaround.

If you reduce too much you will be left with an absurd ammount of offsets which will be impossible to work with.

For a 125bit key:

10bit reduction = 1024 offsets to search in the 115bit range.

25bit reduction = 33.554.432 offsets to search in the 100bit range.

30bit reduction = 1.073.741.824 offsets to search in the 95bit range.

 Sad
  

I ran this equation using your example and the 40 bit pvk was found whether I ran the bsgs algo in the 50bit, 40bit or 30bit range. The same public key was found as long as I did not search in a range above 50bit. I don’t understand why it’s finding the same public and private key pair on line 120 in the output file. How is it finding a 40 bit private key in a 50 bit or 30 bit range? Do you know why?
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 10/04/2024, 18:47:04 UTC
There is a new NVIDIA GPU that was announced, the GB200 which is exponentially more powerful than the current gpus.

You need GB200 NVL72 rack to solve 130. Find out there how much it costs.  Grin

I meant when they become available through data centers and gpu servers.
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 27/03/2024, 19:31:11 UTC
Are you going to modify the code to be able to search the 130 bit? There is a new NVIDIA GPU that was announced, the GB200 which is exponentially more powerful than the current gpus.

I don't think so, unless someone proove me he has the needed power and is ready to beat the world record  Wink

Here's my current work file for 130, i got here in about 3 days
i need 25.55 DP
is what i have wrong? since you said the program can't solve it?
Kangaroo v2.2
Loading: save.work
Version   : 0
DP bits   : 40
Start     : 200000000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Count     : 0 2^-inf
Time      : 00s
DP Size   : 2.1/4.7MB
DP Count  : 4480 2^12.129
HT Max    : 2 [@ 001ECF]
HT Min    : 0 [@ 000000]
HT Avg    : 0.02
HT SDev   : 0.13
Kangaroos : 0 2^-inf
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 27/03/2024, 19:20:52 UTC
I checked on #125 with a RTX 4500 and a A100 (the H100 is not yet available).
The needed time evolve linearly with the number of board and you have to multiply by sqrt(32) for #130
So ~1 year to solve #130 with ~1000 RTX 4500 using this program with the required mods.

Kangaroo v2.2
Start:10000000000000000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^124
Jump Avg distance: 2^62.04
Number of kangaroos: 2^20.81
Suggested DP: 38
Expected operations: 2^63.10
Expected RAM: 1387.8MB
DP size: 38 [0xfffffffffc000000]
GPU: GPU #0 NVIDIA RTX A4500 (56x0 cores) Grid(112x128) (147.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos [9.9s]
[1514.20 MK/s][GPU 1514.20 MK/s][Count 2^34.77][Dead 0][22s (Avg 207.606y)][2.0/4.0MB]


Kangaroo v2.2
Start:10000000000000000000000000000000
Stop :1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^124
Jump Avg distance: 2^62.04
Number of kangaroos: 2^21.75
Suggested DP: 37
Expected operations: 2^63.10
Expected RAM: 2760.3MB
DP size: 37 [0xfffffffff8000000]
GPU: GPU #0 NVIDIA A100-PCIE-40GB (108x0 cores) Grid(216x128) (277.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.75 kangaroos [22.7s]
[3824.79 MK/s][GPU 3824.79 MK/s][Count 2^33.84][Dead 0][06s (Avg 82.0929y)][2.0/4.0MB]

---------

With a H100 (PCIe) (on #130)

Kangaroo v2.2
Start:200000000000000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^129
Jump Avg distance: 2^64.01
Number of kangaroos: 2^21.83
Suggested DP: 40
Expected operations: 2^65.62
Expected RAM: 1985.4MB
DP size: 40 [0xffffffffff000000]
GPU: GPU #0 NVIDIA H100 PCIe (114x0 cores) Grid(228x128) (292.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.83 kangaroos [23.3s]
[5113.99 MK/s][GPU 5113.99 MK/s][Count 2^34.26][Dead 0][06s (Avg 352.678y)][2.0/4.0MB]

You can find the cotation of the hypervisors we use for scientific calculation there (page 12 of my presentation):
https://indico.esrf.fr/event/93/contributions/559/



Are you going to modify the code to be able to search the 130 bit? There is a new NVIDIA GPU that was announced, the GB200 which is exponentially more powerful than the current gpus.
Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
Chail35
on 09/03/2024, 03:18:13 UTC
I do not want to be offtopic, but guys did you calculated what computing speed is required to scan the entire range of 130 puzzle?

For the range: 200000000000000000000000000000000:3ffffffffffffffffffffffffffffffff, which have: 680564733841876926926749214863536422912 total keys to scan, on a speed of 100 YottaK/s it would take almost 215657 years to finish  Grin

Not to mention that the highest reported speed on a single 4090 was only 7-8Gk/s .

So is there something that I miss, why you still bother to scan beyond 125?

I mean even if you change the bit range to scan to 160 bit range, is still impossible with the current gpu's, maybe with photonic gpu's we might have a chance.
Yeah...that's not how it works. What you are describing/showing the math for is a brute force approach.

With Kangaroo, and #130, you need to do 130/2 + 1.05 = 2^66.05 ops.

Now, recalculate.
Since JLPs Kangaroo says "This program is limited to a 125bit interval search" in the README. does that mean we should'nt use it to search for puzzle 130? Because when I run the program to search for 130, it gives me a dp of 40 and searches just fine, in that the program is running and i get no errors. it seems to search in the 129bit interval just ok.