JonJonBon
Newbie
Offline
Activity: 3
Merit: 0
|
|
July 11, 2024, 12:22:56 PM |
|
Hello everyone, can you tell me if there has been a message here for a long time? where it says "if it would be possible to divide a point on the curve by 2, then find the private key, etc.." I've seen this message here before and it was answered by someone. I can't seem to find this page.
Division by 2 just means to multiply by 1/2 mod N. 1/2 just means 2's inverse so that 2*x = 1 mod N. Inverse of x mod N just means x N-2 mod N (Fermat Little Theorem). Let's take F = { y(x) = 2 x mod 11, 0 < x < 11 } and some known y = 5: 2 x = 5 mod 11 "Divide" public key by 2: 2 x/2 = 5/2 mod 11 2 x-1 = 2 -1 * 5 mod 11 2 -1 = 2 11-2 mod 11 = 6 So: 2 x-1 = 5*6 mod 11 = 8 Great, now you have to find x - 1. Repeat? Sounds like nothing really changed. Let's take F = { (x, y) = [k]G, 0 < k < N } and some known (x, y) = Q: [k]G = Q "Divide" public key by 2: [k/2]G = [1/2]Q [k/2]G = [2 -1]Q 2 -1 = 2 N-2 mod N So: [k/2 mod N]G = [2 N-2 mod N]Q Great, now you have to find k / 2. Repeat? Sounds like nothing really changed. If you fall into the trap that k is somehow half the size now, remember this: 1. Division of a field element means multiplying the element with the divisor's field inverse. k is not an integer in an infinite field, but a finite field. You can't just half it's value, that only makes sense in an infinite field, and only if such an inverse really exists. 2. Groups do not have multiplication operation, only addition. There's no such thing as multiplying or division of elliptic points, they form a group, not a field. "Point multiplication by k" just means adding the point to itself k times. "Division by k" means adding the same point to itself kN-2 mod N times. You need to respect the definitions of what something can be called a "group" or "field", "finite" vs "infinite", not invent or borrow properties from different structures. It can't work. Yes, I read about it here on the forum! thanks for the answer! But there was a message on this branch with a division by 2. and there was an answer to it, but I don't remember which one and on which page these messages are also I don't remember. But the question is, if it were possible to divide public keys by 2? would it make it easier to find the private key? what I remember seems to be the answer to that message was "if we could divide the public key by 2, then finding the private key would be easy, and it seems to have given the formula", if I was wrong, please correct me!
|
|
|
|
GR Sasa
Member
Offline
Activity: 180
Merit: 14
|
|
July 11, 2024, 02:28:34 PM |
|
Yes, I read about it here on the forum! thanks for the answer! But there was a message on this branch with a division by 2. and there was an answer to it, but I don't remember which one and on which page these messages are also I don't remember. But the question is, if it were possible to divide public keys by 2? would it make it easier to find the private key? what I remember seems to be the answer to that message was "if we could divide the public key by 2, then finding the private key would be easy, and it seems to have given the formula", if I was wrong, please correct me!
I suspect and breath a bad digaran breath here... He told you and explained indirectly that it doesn't help find the original private key. You'll just be in a infinite loop with unknown keys that cannot be found. So you'll endup having trying to find some random private keys the same way as finding the orginal key if you decide to divide or even multiple. Yes you can divide any key by 2, 3 or even 9999999999999999999999 but it doesn't make any sense, because the key won't really be divideded according to our needs because of floats EDIT: I might have understood your point. YES you could divide the key by 2 since you have 50 % 50 % that its even or odd and if you're lucky enough if the original private key ends with 2, 4, 8 or 10 (even numbers) yes you could divide and cut a little bit of its length and size but then what? What's next? The new key is still big as hell to be found and searched. And if you try to keep dividing the divided keys by 2 you will definitely f*ck up with a key and divide a key that ends with a odd number ( 1 , 3 , 5 , 7 , 9 ) and then good morning u will end with a random key on the curve that is totally unknown. It doesn't help.
|
|
|
|
kTimesG
Member
Offline
Activity: 94
Merit: 21
|
|
July 11, 2024, 05:44:05 PM |
|
EDIT: I might have understood your point. YES you could divide the key by 2 since you have 50 % 50 % that its even or odd and if you're lucky enough if the original private key ends with 2, 4, 8 or 10 (even numbers) yes you could divide and cut a little bit of its length and size but then what? What's next? The new key is still big as hell to be found and searched. And if you try to keep dividing the divided keys by 2 you will definitely f*ck up with a key and divide a key that ends with a odd number ( 1 , 3 , 5 , 7 , 9 ) and then good morning u will end with a random key on the curve that is totally unknown.
It doesn't help.
When one goes down that road (is it even, is it odd?) then the decision tree has the same size as the problem to be solved. It's basically the same thing as writing: k = 2*(2*(2*(2*(?/2 + ?)/2 + ?)/2 + ?)...) which is the same thing as the representation of the problem. Same thing as hoping that 2 k mod N ends in a 0, and create a strategy off that. But that only always happens when 2 k is inside an infinite field, like [1, 2, ... infinity], not [0, 1, ... N-1]
|
|
|
|
Qstar
Newbie
Offline
Activity: 7
Merit: 1
|
|
July 12, 2024, 12:24:17 PM |
|
So 2 days ago I was convinced I had it, today i feel further away than ever. What I've been doing is converting some features to binary and carefully engineering matrices that convert them into quantum states. I've identified a pattern in the data that is very hard to express. At first I thought this pattern I have been trying to zero in on was the puzzle, but the more I work the more convinced I become that what I am looking at is not the pattern of the puzzle. In Bitcoin, the one-way nature of elliptic curve point multiplication on the secp256k1 curve ensures that while a private key can easily generate a public key and address, reversing the process to derive the private key from the public key or address is computationally infeasible due to the hardness of the Elliptic Curve Discrete Logarithm Problem. Except I think there is leakage, in the data. It's just hidden really, really well. Anyway the search continues. Have fun with your kangaroo!
|
|
|
|
kTimesG
Member
Offline
Activity: 94
Merit: 21
|
|
July 12, 2024, 08:30:25 PM |
|
So 2 days ago I was convinced I had it, today i feel further away than ever. What I've been doing is converting some features to binary and carefully engineering matrices that convert them into quantum states. I've identified a pattern in the data that is very hard to express. At first I thought this pattern I have been trying to zero in on was the puzzle, but the more I work the more convinced I become that what I am looking at is not the pattern of the puzzle. In Bitcoin, the one-way nature of elliptic curve point multiplication on the secp256k1 curve ensures that while a private key can easily generate a public key and address, reversing the process to derive the private key from the public key or address is computationally infeasible due to the hardness of the Elliptic Curve Discrete Logarithm Problem. Except I think there is leakage, in the data. It's just hidden really, really well. Anyway the search continues. Have fun with your kangaroo!
Tho let the wildest Kangaroos into the realm of quantum entanglement and free them of collision harmfulness. A wild mutation out of nowhere will emerge at once from the multiverse of Schrodinger cats, as the living proof of certainty of uncertainty. Make Heisenberg proud and escape us of the hardness of ECDLP's secret hidden patterns. Let's embrace that Public Key is just a mind construct, such like time, out of our control. Don't try to break it, let's dance gracefully around it and forget it even exists. And if ECDLP dares to fight, summon all qubits from all realities to join the GBB (Great Bits Battle). Take control over the full quantum state and derive all the keys at once in a single Matrix Transition, for your Desired Outcome. Show'em who the boss is. Make your own reality! Meow.
|
|
|
|
nomachine
Member
Offline
Activity: 330
Merit: 17
|
|
July 12, 2024, 09:58:32 PM Last edit: Today at 12:50:49 AM by nomachine |
|
Have fun with your kangaroo!
I am still on Earth. I don't even have a GPU card right now. Here is Kangaroo C++ in one single file: kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <map> #include <random> #include <set> #include <sstream> #include <vector>
using namespace std;
typedef pair<mpz_class, mpz_class> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P;
const mpz_class& Px = P.first; const mpz_class& Py = P.second; const mpz_class& Qx = Q.first; const mpz_class& Qy = Q.second;
if (Px == Qx && (Py != Qy || Py == 0)) return Z;
mpz_class m, inv; mpz_class num, denom;
if (Px == Qx) { num = (3 * Px * Px) % p; denom = (2 * Py) % p; } else { num = (Qy - Py) % p; denom = (Qx - Px) % p; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); m = (num * inv) % p;
mpz_class x = (m * m - Px - Qx) % p; mpz_class y = (m * (Px - x) - Py) % p;
x = (x + p) % p; y = (y + p) % p;
return {x, y}; }
Point mul2(const Point& P, const mpz_class& p = modulo) { if (P == Z) return Z;
const mpz_class& Px = P.first; const mpz_class& Py = P.second;
mpz_class num = (3 * Px * Px) % p; mpz_class denom = (2 * Py) % p; mpz_class inv; mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); mpz_class m = (num * inv) % p;
mpz_class x = (m * m - 2 * Px) % p; mpz_class y = (m * (Px - x) - Py) % p;
x = (x + p) % p; y = (y + p) % p;
return {x, y}; }
Point mulk(mpz_class k, const Point& P = PG, const mpz_class& p = modulo) { Point result = Z; Point addend = P; while (k > 0) { if (k % 2 == 1) { result = add(result, addend, p); } addend = mul2(addend, p); k /= 2; }
return result; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { if (P.first % DP_rarity == 0) { T.push_back(P); t.push_back(Pindex); std::set<mpz_class> T_set; for (const auto& tp : T) T_set.insert(tp.first); for (const auto& wp : W) { if (T_set.count(wp.first)) { mpz_class tT = t[std::distance(T.begin(), std::find_if(T.begin(), T.end(), [&](const Point& p) { return p.first == wp.first; }))]; mpz_class wW = w[std::distance(W.begin(), std::find_if(W.begin(), W.end(), [&](const Point& p) { return p.first == wp.first; }))]; mpz_class dec = abs(tT - wW); auto end = std::chrono::system_clock::now(); time_t end_time = std::chrono::system_clock::to_time_t(end); std::cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << std::ctime(&end_time) << "\r"; std::cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << std::endl; std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app); file << "\n" << std::string(140, '-') << std::endl; file << "SOLVED " << std::ctime(&end_time); file << "Private Key (decimal): " << dec << std::endl; file << "Private Key (hex): " << dec.get_str(16) << std::endl; file << std::string(140, '-') << std::endl; file.close(); return true; } } } return false; }
std::vector<mpz_class> generate_powers_of_two(int hop_modulo) { std::vector<mpz_class> powers; powers.reserve(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers.push_back(mpz_class(1) << pw); } return powers; }
std::string search(const std::vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const std::vector<mpz_class>& powers_of_two) { std::vector<Point> T(Nt, Z), W(Nw, Z); std::vector<mpz_class> t(Nt), w(Nw), dt(Nt, 0), dw(Nw, 0);
gmp_randclass rand(gmp_randinit_default);
for (int i = 0; i < Nt; ++i) { t[i] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[i] = mulk(t[i]); }
for (int i = 0; i < Nw; ++i) { w[i] = rand.get_z_range(upper_range_limit - lower_range_limit); W[i] = add(W0, mulk(w[i])); }
long long Hops = 0, Hops_old = 0; auto t0 = std::chrono::high_resolution_clock::now(); std::map<mpz_class, mpz_class> memo;
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < Nt; ++k) { ++Hops; mpz_class pw = T[k].first % hop_modulo; dt[k] = memo[pw]; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += dt[k]; T[k] = add(P[pw.get_ui()], T[k]); } if (solved) break;
for (int k = 0; k < Nw; ++k) { ++Hops; mpz_class pw = W[k].first % hop_modulo; dw[k] = memo[pw]; solved = comparator(W[k], w[k], DP_rarity, W, w, T, t); if (solved) break; w[k] += dw[k]; W[k] = add(P[pw.get_ui()], W[k]); } if (solved) break;
auto t1 = std::chrono::high_resolution_clock::now(); double elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 2.0) { std::cout << "\r[+] Hops: " << ((Hops - Hops_old) / elapsed_seconds) << " h/s" << std::flush << "\r"; std::cout << std::flush << "\r"; t0 = t1; Hops_old = Hops; } }
std::cout << "\r[+] Hops: " << Hops << std::endl; auto end = std::chrono::high_resolution_clock::now(); double elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double>>(end - t0).count(); return "\r[+] Solution time: " + std::to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 40; string compressed_public_key = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4"; int kangaroo_power = 5; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = std::time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << std::ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [X]: " << X << endl; cout << "[+] [Y]: " << Y << endl;
vector<Point> P = {PG}; P.reserve(puzzle + 1); for (int k = 0; k < puzzle; ++k) { P.push_back(mul2(P[k])); } cout << "[+] P-table prepared" << endl;
// Set the random seed unsigned long seed = static_cast<unsigned long>(std::time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime) .count() << " sec" << endl;
return 0; } Build command: g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -lgmp -lgmpxx - KANGAROO: Sat Jul 13 02:26:56 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [X]: 73698089885969865917178217585365130397293864653143545863290470632977971667156
- [Y]: 55920112788027504860697624221258924004816541552996850637631037640326076931751
- P-table prepared
- Hops: 423183 h/s
- PUZZLE SOLVED: Sat Jul 13 02:27:00 2024
- Private key (dec): 1003651412950
- Hops: 1366627
- Average time to solve: 3 sec
More than 420K hops per second on a single core. Kangaroo power value is crucial in determining the efficiency for solving puzzle. It affects the balance between the number of "tame" and "wild" kangaroos and the size of the steps they take. Finding the optimal value can require manually calibration based on the specific puzzle number. Thanks to 57fe for idea
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1106
Merit: 223
Shooters Shoot...
|
|
Today at 03:14:13 AM |
|
Have fun with your kangaroo!
- KANGAROO: Sat Jul 13 02:26:56 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [X]: 73698089885969865917178217585365130397293864653143545863290470632977971667156
- [Y]: 55920112788027504860697624221258924004816541552996850637631037640326076931751
- P-table prepared
- Hops: 423183 h/s
- PUZZLE SOLVED: Sat Jul 13 02:27:00 2024
- Private key (dec): 1003651412950
- Hops: 1366627
- Average time to solve: 3 sec
More than 420K hops per second on a single core. Kangaroo power value is crucial in determining the efficiency for solving puzzle. It affects the balance between the number of "tame" and "wild" kangaroos and the size of the steps they take. Finding the optimal value can require manually calibration based on the specific puzzle number. Thanks to 57fe for idea Single core, Python script: [ 0d 00:00:03s ; 386.9K j/s; 1.2Mj 78.6%; dp/kgr=5.0; 0d 00:00:00s ] [prvkey#40] 0x000000000000000000000000000000000000000000000000000000e9ae4933d6 [i] [2^39.0|-------------------------------------------------K----------|2^40.0] [i] 386.1K j/s; 1.5Mj of 1.5Mj 100.6%; DP T+W=6+5=11; dp/kgr=5.5 [runtime] 0d 00:00:03s
And it could be faster with some tweaks.
|
|
|
|
dextronomous
|
|
Today at 03:55:31 AM |
|
hi there wandering,
what kind of code you have to do this speed next to his code, tweaked it, got it for sharing ready, thanks for sharing, i got the 640000 whatever it said with the original., so would be nice to have a faster one..
|
|
|
|
nomachine
Member
Offline
Activity: 330
Merit: 17
|
|
Today at 05:29:20 AM Last edit: Today at 05:54:01 AM by nomachine |
|
hi there wandering,
what kind of code you have to do this speed next to his code, tweaked it, got it for sharing ready, thanks for sharing, i got the 640000 whatever it said with the original., so would be nice to have a faster one..
I have almost the same speed regardless of whether I use Python, Rust, or C++, as long as it's based on a script from here https://fe57.org/forum/thread.php?board=4&thema=1#1This is because I have exactly the same GMP library and the same formulas everywhere.
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1106
Merit: 223
Shooters Shoot...
|
|
Today at 06:00:14 AM |
|
hi there wandering,
what kind of code you have to do this speed next to his code, tweaked it, got it for sharing ready, thanks for sharing, i got the 640000 whatever it said with the original., so would be nice to have a faster one..
I have almost the same speed regardless of whether I use Python, Rust, or C++, as long as it's based on a script from here https://fe57.org/forum/thread.php?board=4&thema=1#1This is because I have exactly the same GMP library and the same formulas everywhere. Ole, FE57, oldie but goodie! I believe it's sprinkled in the python script as well. But this was one of the first Python scripts that I remember seeing put out for the public. Many worked on it. https://github.com/Telariust/pollard-kangarooI'm wondering if going from GMP to iceland's package, would offer some speed up.
|
|
|
|
Qstar
Newbie
Offline
Activity: 7
Merit: 1
|
|
Today at 06:05:40 AM |
|
So some how i got side tracked by this kangaroo thing cause i thought i saw a way to make it better. look. - KANGAROO: Fri Jul 12 23:59:50 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [X]: 73698089885969865917178217585365130397293864653143545863290470632977971667156
- [Y]: 55920112788027504860697624221258924004816541552996850637631037640326076931751
- P-table prepared
- Hops: 472063.55 h/s
- PUZZLE SOLVED: Fri Jul 12 23:59:56 2024
- Private key (dec): 1003651412950
- Hops: 2970544
- Average time to solve: 6.33 sec
|
|
|
|
Akito S. M. Hosana
Newbie
Offline
Activity: 16
Merit: 0
|
|
Today at 06:13:03 AM |
|
So some how i got side tracked by this kangaroo thing cause i thought i saw a way to make it better. look. - KANGAROO: Fri Jul 12 23:59:50 2024
- [Puzzle]: 40
- [Lower range limit]: 549755813888
- [Upper range limit]: 1099511627775
- [X]: 73698089885969865917178217585365130397293864653143545863290470632977971667156
- [Y]: 55920112788027504860697624221258924004816541552996850637631037640326076931751
- P-table prepared
- Hops: 472063.55 h/s
- PUZZLE SOLVED: Fri Jul 12 23:59:56 2024
- Private key (dec): 1003651412950
- Hops: 2970544
- Average time to solve: 6.33 sec
Same here... I love small simple scripts like these. I start to get lost when I see a script that has over 1000 lines of code.
|
|
|
|
nomachine
Member
Offline
Activity: 330
Merit: 17
|
|
Today at 06:38:02 AM |
|
I'm wondering if going from GMP to iceland's package, would offer some speed up.
https://github.com/iceland2k14/kangaroo.gitfrom here? # time python3 kangaroo.py -p 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 -keyspace 8000000000:ffffffffff - Starting CPU Kangaroo.... Please Wait Version [ 15112021 ]
- Search Mode: Range search Continuous in the given range
- Working on Pubkey: 04a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d47ba1a987013e7 8aef5295bf842749bdf97e25336a82458bbaba8c00d16a79ea7
- Using [Number of CPU Threads: 11] [DP size: 10] [MaxStep: 2]
- Scanning Range 0x8000000000 : 0x100007fffffffff
- [3074.58 TeraKeys/s][Kang 11264][Count 2^28.20/2^29.07][Elapsed 08s][Dead 2][RAM 29.6MB/45.1MB]
============== KEYFOUND ============== Kangaroo FOUND PrivateKey : 0x000000000000000000000000000000000000000000000000000000e9ae4933d6 ====================================== real 0m8.687s user 1m31.744s sys 0m0.095s It has not been updated for a long time.
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1106
Merit: 223
Shooters Shoot...
|
|
Today at 07:14:57 AM |
|
I'm wondering if going from GMP to iceland's package, would offer some speed up.
https://github.com/iceland2k14/kangaroo.gitfrom here? # time python3 kangaroo.py -p 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 -keyspace 8000000000:ffffffffff - Starting CPU Kangaroo.... Please Wait Version [ 15112021 ]
- Search Mode: Range search Continuous in the given range
- Working on Pubkey: 04a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d47ba1a987013e7 8aef5295bf842749bdf97e25336a82458bbaba8c00d16a79ea7
- Using [Number of CPU Threads: 11] [DP size: 10] [MaxStep: 2]
- Scanning Range 0x8000000000 : 0x100007fffffffff
- [3074.58 TeraKeys/s][Kang 11264][Count 2^28.20/2^29.07][Elapsed 08s][Dead 2][RAM 29.6MB/45.1MB]
============== KEYFOUND ============== Kangaroo FOUND PrivateKey : 0x000000000000000000000000000000000000000000000000000000e9ae4933d6 ====================================== real 0m8.687s user 1m31.744s sys 0m0.095s It has not been updated for a long time. No, I meant using his secp256k1 library, integrating it into another kangaroo python script. I haven't really looked at his kangaroo library.
|
|
|
|
nomachine
Member
Offline
Activity: 330
Merit: 17
|
|
Today at 07:42:04 AM |
|
I'm wondering if going from GMP to iceland's package, would offer some speed up.
https://github.com/iceland2k14/kangaroo.gitfrom here? # time python3 kangaroo.py -p 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 -keyspace 8000000000:ffffffffff - Starting CPU Kangaroo.... Please Wait Version [ 15112021 ]
- Search Mode: Range search Continuous in the given range
- Working on Pubkey: 04a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d47ba1a987013e7 8aef5295bf842749bdf97e25336a82458bbaba8c00d16a79ea7
- Using [Number of CPU Threads: 11] [DP size: 10] [MaxStep: 2]
- Scanning Range 0x8000000000 : 0x100007fffffffff
- [3074.58 TeraKeys/s][Kang 11264][Count 2^28.20/2^29.07][Elapsed 08s][Dead 2][RAM 29.6MB/45.1MB]
============== KEYFOUND ============== Kangaroo FOUND PrivateKey : 0x000000000000000000000000000000000000000000000000000000e9ae4933d6 ====================================== real 0m8.687s user 1m31.744s sys 0m0.095s It has not been updated for a long time. No, I meant using his secp256k1 library, integrating it into another kangaroo python script. I haven't really looked at his kangaroo library. I understand, it's not a bad idea to try. I tried to see what was in his kangaroo .so file from https://dogbolt.org/Best result is from Retargetable Decompiler(RetDec) the decompiled output contains low-level assembly instructions and it's challenging to fully reconstruct high-level source code from compiled binaries, but you can see roughly what the program accesses and how. I think he packaged the code with Cython a Python compiler.
|
|
|
|
kTimesG
Member
Offline
Activity: 94
Merit: 21
|
|
Today at 09:25:33 AM |
|
You can easily get 11M hops/s on single-core CPU
Do a single inverse (10-20x speedup). Use carry-free representation (1-2x speedup). Dump GMP, it does generic arithmetic, not specialized to our needs (> 75% speedup).
With GMP, using MPN (lowest level possible) calls, and naive point addition like the one above, I never topped 700 K/s. In plain C.
Likely it would be even faster than 11-12 M/s with careful choices so that all data resides in CPU cache and the core is strongly assigned (no context switch).
But IMO it's just an exercise. The cost per kangaroo jump, in watts, is not worth it even if the speed would be triple or whatever. You might also get a fried CPU. Serve with potatoes and ketchup.
|
|
|
|
nomachine
Member
Offline
Activity: 330
Merit: 17
|
|
Today at 09:45:02 AM |
|
You can easily get 11M hops/s on single-core CPU
Do a single inverse (10-20x speedup). Use carry-free representation (1-2x speedup). Dump GMP, it does generic arithmetic, not specialized to our needs (> 75% speedup).
I only know how to do this with OpenSSL's BIGNUM and functions like BN_add, BN_sub, BN_mul, BN_mod, etc., for arithmetic operations. But I don't believe that the speed will be that high. Maybe 5M hops/s on single-core CPU.
|
|
|
|
|