Pollard's kangaroo ECDLP solver

[NotATether]

Can I ask about Pollard's kangaroo python script ?

Did I understand wrong?
Pollard's kangaroo generate random number(in range) to private key for generate public point and compare collision right ?

if I understand correct
What variable is private key Pollard's kangaroo ?

from ask, I mean private key of each generate point for check. ( I not mean private key of result )

https://github.com/JeanLucPons/Kangaroo/blob/master/Kangaroo.cpp
http://fe57.org/forum/thread.php?board=4&thema=1#1
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

pollard_kangaroo.txt
t.append((3 << problem - 2) + random.randint(1, 1 << problem - 1))
w.append(random.randint(1, 1 << problem - 1))

pollard-kangaroo-multi.py
prvkey0 = random.randint(L,U)

Kangaroo.cpp
?

Most likely it is the last line (privkey0 = random.randint(L, U)).

L and U are the range of the kangaroos of course.

t and w are just the tame and wild points respectively (actually they are represented by numbers here).

[1714480900]

1714480900

[1714480900]

1714480900

[1714480900]

1714480900

[1714480900]

1714480900

[Andre_25]

Hello.
Friends, I have a question.
 I can put many public keys (to study, myself) in the kangaroo input file, for example about 1000.
Will this make the job more difficult? because, for example, if you find a possible collision of one of them, the others will no longer be searched and you are left with only one? (the possible found). Or it carries a set of possible collisions, independently for each of the public keys put in the input.

Thank you for the help that you may be able to provide

[a.a]

They are not searched in parallel. So it first searches the first one, if not found searches the next one... Etc.

[fxsniper]

How long JeanLucPons use time for solve puzzle #105 ,#110 and #115 each ?
info on GitHub tell only #120

็How to can calculate range for my GPU can search?
example
[139.25 MK/s][GPU 117.25 MK/s][Count 2^39.32][Dead 0][01:34:25 (Avg 17.4802y)][2.0/4.0MB]

24 hour = 24*60=1,440*60=86,400 sec

117.25 MK = 117000000
117000000*86400=77,760,000,000,000
log2(77760000,0000000)
49.466021547366765
49bit range

just try spilt search
D5F00C73EA6B3394A6BB77FFFFFFFF
D5FE01DEDF5D348E540611C71C71C7
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

[John_Ahmet]

Hello, thank you to everyone who contributed to this project.
I want to try something and I need ModPow function for Int type.

All Mod functions use P.

Can a faster version be made for b=2?

I want to calculate 2 ^ e % m

For int type like this:

Code:

int ModPow(int b, int e, int m)
{
	int result = 1;
	if (1 & e)
		result = b;
	while (1) {
		if (!e) break;
		e >>= 1;
		b = (b * b) % m;//ModMul
		if (e & 1)
			result = (result * b) % m;//ModMul
	}
	return result;
}

[NotATether]

Hello, thank you to everyone who contributed to this project.
I want to try something and I need ModPow function for Int type.

All Mod functions use P.

Can a faster version be made for b=2?

I want to calculate 2 ^ e % m

For int type like this:

Code:

int ModPow(int b, int e, int m)
{
	int result = 1;
	if (1 & e)
		result = b;
	while (1) {
		if (!e) break;
		e >>= 1;
		b = (b * b) % m;//ModMul
		if (e & 1)
			result = (result * b) % m;//ModMul
	}
	return result;
}

There is not one that I know of. You could've been able to replace the (b*b) with b << (b >> 1) which uses only bitwise operators, and other basic bitwise optimizations in other statements, if it wasn't for the presence of the possibly odd modulus n.

[John_Ahmet]

I've shared the basic pseudo code for RSA Bruteforce below. Can you please write a basic pseudo-code for this method?

Code:

GenerateRSAKeys()
   p => random big prime, below 64bits
   q => random big prime, below 64bits
   e => random small prime, below 16bits
   k => random small integer, below 16 bits
   N = p * q
   d = (k * ((p - 1) * (q - 1)) + 1) / e

   (e, N) => Public key
   (e, d, p, q) => Private key

RSAEncode(m, e, N) // m => message, e and N are public key
   h ≡ m ^ e mod N

RSADecode(h, d, N) // h => encrypted message, d is part of private key
   m ≡ h ^ d mod N

RSACrack_GetPrivateKeyFromPublicKey(e, N, minPrimeBitsLength)
   bitLength = GetBitsLength(N)
   k = 2
   // iterator uses sieve algorithm
   primes = all64BitsPrimes.Select(p => GetBitsLength(p) >= minPrimeBitsLength && GetBitsLength(p) <= (bitLength - minPrimeBitsLength)) 
   // Example Primes buffer uses 4GB memory, all below 64Bits primes use 1TB memory
   // use only odd numbers bit array
   // max 256 cycles
   index = -1
   for primesBuffer1 of primes
     index++
     for primesBuffer2 of primes.NextTo(index) // next buffers from index, including index. buffer. if you use ModMul, remove this line
       for p of primesBuffer1
         for q of primesBuffer2 // if you use ModMul, remove this line
           bitLengthA = GetBitsLength(p)
           bitLengthB = GetBitsLength(q)
           bitSum = bitLengthA + bitLengthB
           if (max(bitLengthA, bitLengthB) >= bitLength && bitSum <= bitLength)
             if (p * q == N) // or (N % p == 0) or ModMul(N+1, 10, p) == 10
               d = (k * ((p - 1) * (q - 1)) + 1) / e
               return (e, d, p, q)

For RSA this code results much faster.

I expect you to write basic pseudocode for Kangaroo. Thanks.

Code:

RSAHacking_GetPrivateKeyFromPublicKeyUsingModPowNoPrimeTable(e, N)
   k = 2
   SqrtN = Sqrt(N)
   if((SqrtN & 1) == 0) SqrtN++
   for(p = SqrtN; p > 2; p-=2)
     if (true/*You can use more filters for p*/ && ModPow(2, p-1, p) == 1 && ModMul(N+1, 10, p) == 10)
       q = N / p
       d = (k * ((p - 1) * (q - 1)) + 1) / e
       return (e, d, p, q)

[moderator's note: consecutive posts merged]

[NotATether]

I've shared the basic pseudo code for RSA Bruteforce below. Can you please write a basic pseudo-code for this method?

You cannot solve RSA problems with the Kangaroo method because the ECDLP problem is not applicable for RSA, as there are no logarithms to solve for.

[superkatchu]

I've shared the basic pseudo code for RSA Bruteforce below. Can you please write a basic pseudo-code for this method?

You cannot solve RSA problems with the Kangaroo method because the ECDLP problem is not applicable for RSA, as there are no logarithms to solve for.

Not ECDLP but DLP so Pollard Rho and Pollard Kangaroo should be applicable no?

[demoinvest1]

Can possible Pollard's kangaroo can search multiple pubkey in same time?
I mean check multiple pubkey at once

[wedom]

Can possible Pollard's kangaroo can search multiple pubkey in same time?
I mean check multiple pubkey at once

No, one at a time only

[NotATether]

I've shared the basic pseudo code for RSA Bruteforce below. Can you please write a basic pseudo-code for this method?

You cannot solve RSA problems with the Kangaroo method because the ECDLP problem is not applicable for RSA, as there are no logarithms to solve for.

Not ECDLP but DLP so Pollard Rho and Pollard Kangaroo should be applicable no?

Rho is specifically designed for Discrete Logarithm (factoring) problem.

Also I read the Wikipedia page for Kangaroo which said that it's applicable for any group. In fact the paper for Pollard's Kangaroo originally mentioned it's use for multiplicative [again, RSA/factoring] groups.

[bigvito19]

I've shared the basic pseudo code for RSA Bruteforce below. Can you please write a basic pseudo-code for this method?

You cannot solve RSA problems with the Kangaroo method because the ECDLP problem is not applicable for RSA, as there are no logarithms to solve for.

Not ECDLP but DLP so Pollard Rho and Pollard Kangaroo should be applicable no?

Rho is specifically designed for Discrete Logarithm (factoring) problem.

Also I read the Wikipedia page for Kangaroo which said that it's applicable for any group. In fact the paper for Pollard's Kangaroo originally mentioned it's use for multiplicative [again, RSA/factoring] groups.

Are there any Rho programs?

[fxsniper]

I not yet deep understand about ECDLP and Pollard's kangaroo Algorithm and about Collision
I just know overview that not enough for knowledge can solve puzzle

I am not sure I understand it correctly
This Collision method meaning it have Collision every where on range around 2*32 will be found Collision of every key right (but size large 2**256 it is large enough for can not find it)

[NotATether]

Are there any Rho programs?

Not that I know of.

I not yet deep understand about ECDLP and Pollard's kangaroo Algorithm and about Collision
I just know overview that not enough for knowledge can solve puzzle

I am not sure I understand it correctly
This Collision method meaning it have Collision every where on range around 2*32 will be found Collision of every key right (but size large 2**256 it is large enough for can not find it)

It is considering as a collision any key that has the same Most Significant Bytes as some other key in the hash table. How many MSBs that have to be identical depends on your DP setting. So if your DP size is 10, all keys with the same 10 beginning bits are considered a collision for hashtable purposes.

[mausuv]

guys please tell two point subtract example i need

tell easy understand because, i know tow point add and multipliction
but subtract not understand please write example easy math

for example :

c = K(qy-py)/(qx-px)
rx1 = K(c^2-px-qx)
ry2 = K(c*(px-rx))

your example write this method #sorrymyBADenglish

[jovica888]

@mausuv

I am searching for this too... It looks to me that if | public key = private key * G point | then some parts of the whole process is the same for all keys... It does not need to be calculated again... Also what I understood is I have 2 points P and Q and I am searching for  x and y of R... So what does generator points have to do with all process... And how do I get values of P and Q if I know the private key and that private key has a value "0x2"... Somebody could explain which variable means what?

[fxsniper]

I am not yet understand about subtract method I follow come later
May be subtract method it is not works. for now can not solve
What is thing make subtract method stuck, power of GPU not help right

[jovica888]

And also one more thing.


When I look at this picture I see that this one value for x and y of R
has millions and billions different pairs of x and y of Q and P
I mean just change the slope of the line

[mausuv]

And also one more thing.
https://i.imgur.com/RU7sYqO.png

When I look at this picture I see that this one value for x and y of R
has millions and billions different pairs of x and y of Q and P
I mean just change the slope of the line

this code write for c in keysubtracter i need python >>>>  https://github.com/albertobsd/keysubtracter

i know tow point add,multiple in python code, but subtracter not understand https://github.com/albertobsd/keysubtracter/blob/main/keysubtracter.c please

modifiy this code c to python convert
another c code https://github.com/albertobsd/ecctools  subtract
please only subtract code get write to python

atleast  this c code https://github.com/albertobsd/keysubtracter/blob/main/keysubtracter.c decode to mathematical explain
for example :

c = K(qy-py)/(qx-px)
rx1 = K(c^2-px-qx)
ry2 = K(c*(px-rx)) #sorrymyBADenglish

----------------------------------------------------------i use this tow point multiple in python
P = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
Gy = 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
Acurve = 0

Cx,Cy = multiple(Gx,Gy)
print (hex(Cx)[2:66],hex(Cy)[2:66])