Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 24. (Read 58537 times)

newbie
Activity: 25
Merit: 5
November 08, 2021, 07:23:49 PM
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]
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
November 05, 2021, 11:35:40 AM
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.
newbie
Activity: 25
Merit: 5
November 05, 2021, 10:33:27 AM
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;
}
member
Activity: 406
Merit: 47
October 30, 2021, 12:34:52 AM

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

a.a
member
Activity: 126
Merit: 36
October 26, 2021, 02:38:08 PM
They are not searched in parallel. So it first searches the first one, if not found searches the next one... Etc.
newbie
Activity: 18
Merit: 7
October 26, 2021, 02:33:50 PM
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
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 22, 2021, 01:08:50 AM

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).
member
Activity: 406
Merit: 47
October 21, 2021, 11:08:00 PM

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
?
full member
Activity: 706
Merit: 111
October 20, 2021, 09:40:23 AM
jr. member
Activity: 48
Merit: 11
October 20, 2021, 08:47:53 AM
Does anybody has this script, its gone.
...

I found the code of a script for browsing workfiles

kangaroo-tool.py

Code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys, os
if sys.version_info.major<3:
    print("Python3 required")
    sys.exit(0)

import argparse
from struct import unpack
from binascii import hexlify,unhexlify
from math import log2

HEADW = 0xFA6A8001  # Full work file
HEADK = 0xFA6A8002  # Kangaroo only file

HASH_SIZE = 2**18

TAME=False
WILD=True




def bytes_to_num(b):
    return int(hexlify(b), 16)

def GetTimeStr(dTime):
  tmp = ''
  nbDay = dTime / 86400.0
  if nbDay >= 1:
    nbYear = nbDay / 365.0
    if nbYear > 1:
      if nbYear < 5:
        tmp += "%.1fy" % (nbYear)
      else:
        tmp += "%gy" % (nbYear)
    else:
      tmp += "%.1fd" % (nbDay)

  else:

    iTime = dTime
    nbHour = ((iTime % 86400) / 3600)
    nbMin = (((iTime % 86400) % 3600) / 60)
    nbSec = (iTime % 60)

    if nbHour == 0:
      if nbMin == 0:
        tmp += "%02ds" % (nbSec)
      else:
        tmp += "%02d:%02d" % (nbMin, nbSec)
    else:
      tmp += "%02d:%02d:%02d" % (nbHour, nbMin, nbSec)

  return tmp


def checkhead(wf):
    head = unpack('I', wf.read(4))[0]
    if head==HEADW:
        return head
    else:
        print('HEADER ERROR %08x %08x' % (head, HEADW))
        return False

def workinfo(workfile):

  wf = open(workfile, 'rb')
  head = checkhead(wf)
  if not head:
    print('Invalid WorkFile Header')
    return
  version = unpack('I', wf.read(4))[0]
  dp1 = unpack('I', wf.read(4))[0]
  RangeStart = bytes(wf.read(32))[::-1]
  RangeEnd = bytes(wf.read(32))[::-1]
  x = bytes(wf.read(32))[::-1]
  y = bytes(wf.read(32))[::-1]
  count = unpack('Q', wf.read(8))[0]
  time = unpack('d', wf.read(8))[0]

  print('Header   : %08x' % head)
  print('Version  : %d' % version)
  print('DP Bits  : %08x' % dp1)
  print('Start    : %x' % bytes_to_num(RangeStart))
  print('Stop     : %x' % bytes_to_num(RangeEnd))
  print('PubKey X : %s' % hexlify(x).decode())
  print('PubKey Y : %s' % hexlify(y).decode())

  if count>0:
    print('Count    : %d 2^%.3f' % (count, log2(count)))
  else:
    print('Count    : %d' % (count))

  print('Time     : %s' % GetTimeStr(time))

  wf.close()


def workexport(workfile):

    wf = open(workfile, 'rb')
    head = checkhead(wf)
    if not head:
      print('Invalid WorkFile Header')
      return
    wf.seek(156,0) # Skip WorkFile header

    tameFile = open('tame.txt','a')
    wildFile = open('wild.txt','a')

    for h in range(HASH_SIZE):
      nbItem = unpack('I', wf.read(4))[0]
      maxItem = unpack('I', wf.read(4))[0]
      for i in range(nbItem):
        x = bytes(wf.read(16))[::-1]
        d = bytes(wf.read(16))[::-1]

        sign = (bytes_to_num(d) & 0x80000000000000000000000000000000)>0
        htype = (bytes_to_num(d) & 0x40000000000000000000000000000000)>0

        if htype==TAME:
          tameFile.write('%05x%032x ' % (h, bytes_to_num(x)))
          tameFile.write('%032x\n' % (bytes_to_num(d) & 0x3fffffffffffffffffffffffffffffff))
        else:
          wildFile.write('%05x%032x ' % (h, bytes_to_num(x)))
          if sign:
            wildFile.write('-')
          wildFile.write('%032x\n' % (bytes_to_num(d) & 0x3fffffffffffffffffffffffffffffff))

        if args.verbose:
          sys.stdout.write('%s' % ('Tame' if htype==TAME else 'Wild'))
          sys.stdout.write(' %05x%032x ' % (h, bytes_to_num(x)))
          if sign:
            sys.stdout.write('-')
          sys.stdout.write('%032x\n' % (bytes_to_num(d) & 0x3fffffffffffffffffffffffffffffff))


if __name__ == '__main__':
    parser = argparse.ArgumentParser()
    parser.add_argument('-f', dest='workfile', type=str, required=True, help='WorkFile path')
    parser.add_argument('--winfo', dest='winfo', action='store_true', help='Show workfile info')
    parser.add_argument('--wexport', dest='wexport', action='store_true', help='Export workfile into tame.txt and wild.txt')
    parser.add_argument('-v', dest='verbose', action='store_true', help='Verbose')
    args = parser.parse_args()

    if args.workfile:
        print("[+] Workfile %s" % args.workfile)

    if args.winfo:
        workinfo(args.workfile)

    if args.wexport:
        workexport(args.workfile)

https://gist.github.com/PatatasFritas/a0409df4306fb1bb81f9a53e70151ddc
jr. member
Activity: 48
Merit: 11
October 20, 2021, 07:25:05 AM
Does anybody has this script, its gone.
...
If you can compile your own version, you can add the export option that https://github.com/PatatasFritas/FriedKangaroo created.  If you search for PatatasFritas in this thread, they also have a python script that will do the same; export the wild and tame files.

...

it was a forked from JeanLucPons/Kangaroo
https://github.com/JeanLucPons/Kangaroo
I can't tell if there were any changes from the original. I still have the saved page, but there is no archive with the files


for the second question: the link is valid, everything is in place
https://gist.github.com/ZenulAbidin/286a652b160086b3b0f184a886ba68ca

full member
Activity: 706
Merit: 111
October 20, 2021, 06:54:52 AM
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 20, 2021, 03:58:06 AM
Shor's algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates.

Link to resource?
https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

look for Quantum computing attacks in the end

Read https://www.reddit.com/r/Bitcoin/comments/6is19z/new_estimate_quantum_computers_require_at_most/ , an x-post of your resource:

blk0  72 points 4 years ago
In all fairness, I have to state that the 2330 qubits refer to ideal, fault-tolerant, logical qubits, whereas the 17 qubits currently achieved by IBM's quantum processor are raw, imperfect qubits which could be used to encode 7 logical qubits. Yet, quantum error-correction of even a single fault-tolerant qubit has not been achieved in experiments today.

As Spock would say, your IBM's quantum computer is "illogical"  Smiley

World's most powerful quantum computer as of today can do 66 qubits.

And *it's* research paper says this:

In conclusion, we have reported the design, fabrication, measurement, and benchmarking of a state-of-the-art 66- qubit superconducting quantum processor that is fully programmable through electric control. ...... We note that the performance of the whole system behaves as predicted when system size grows from small to large, confirming our high fidelity quantum operations and low correlated errors on the Zuchongzhi processor. The quantum processor has a scalable architecture that is compatible with surface-code error correction, which can act as the test-bed for fault-tolerant quantum computing.

In other words, you still have a long shot to make even 66 *logical* (fault-free) Qbits.

So wake me up when you get anywhere near 2000 logical ones.
jr. member
Activity: 81
Merit: 2
October 19, 2021, 06:55:37 AM
 author=NotATether link=topic=5244940.msg58213662#msg58213662 date=1634617918]
Shor's algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates.



Link to resource?

https://en.wikipedia.org/wiki/Elliptic-curve_cryptography

look for Quantum computing attacks in the end
member
Activity: 406
Merit: 47
October 19, 2021, 02:01:23 AM

Wrong function.

The code for jumping is in SolveKeyGPU and SolveKeyCPU.

You can just make a for loop between 1 to 3 or 10 that computes 3 or 10 consecutive jumps but only store the last one in the hashtable. It won't improve speed but it will slow down your hashtable from ballooning to a large memory footprint.

Thank you

Quick test, result fail
compare test solve problem 65
original CPU finish in 3 minute
original GPU finish in 31 minute

problem 65
modify CPU (3 hour not found any thing)
modify GPU (3 hour not found any thing)
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 18, 2021, 11:31:58 PM
Shor's algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates.

Link to resource?

on Kangaroo.cpp
void Kangaroo::CreateJumpTable() {

Wrong function.

The code for jumping is in SolveKeyGPU and SolveKeyCPU.

You can just make a for loop between 1 to 3 or 10 that computes 3 or 10 consecutive jumps but only store the last one in the hashtable. It won't improve speed but it will slow down your hashtable from ballooning to a large memory footprint.
member
Activity: 406
Merit: 47
October 18, 2021, 07:56:16 PM

Can anyonel help to advice code on c++?

I know may be possible 99% not working and fail
I would like to test modify jump of Pollard's kangaroo
refer from kangaroo illustration JeanLucPons github
DP is foot of kangaroo right but jump is up to high right
I think 120 bit is to high  may be make jump to long will be help

yes, it possible to missing some point to found
Just would like to try

on Kangaroo.cpp
void Kangaroo::CreateJumpTable() {

this function right?

may be I change up 2 to  3-10
just testing a little
jr. member
Activity: 81
Merit: 2
October 18, 2021, 08:50:03 AM
Deny it again if you can.

Shor's algorithm can be used to break elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. The latest quantum resource estimates for breaking a curve with a 256-bit modulus (128-bit security level) are 2330 qubits and 126 billion Toffoli gates. In comparison, using Shor's algorithm to break the RSA algorithm requires 4098 qubits and 5.2 trillion Toffoli gates for a 2048-bit RSA key, suggesting that ECC is an easier target for quantum computers than RSA. All of these figures vastly exceed any quantum computer that has ever been built, and estimates place the creation of such computers at a decade or more away.

Supersingular Isogeny Diffie–Hellman Key Exchange provides a post-quantum secure form of elliptic curve cryptography by using isogenies to implement Diffie–Hellman key exchanges. This key exchange uses much of the same field arithmetic as existing elliptic curve cryptography and requires computational and transmission overhead similar to many currently used public key systems.

In August 2015, the NSA announced that it planned to transition "in the not distant future" to a new cipher suite that is resistant to quantum attacks. "Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy."


 Grin
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 18, 2021, 03:51:11 AM
i know python scripts, already have it too, but for asking about c script, it will faster then python

Most likely you will have to pay someone to make such a program for you as almost all of us are too busy with side projects and/or our personal lives and matters to work on something as complex as a C program (they'd also have to make the makefile too).
newbie
Activity: 9
Merit: 0
October 17, 2021, 04:42:10 AM
There is already a small python script for your needs here in this thread.
i know python scripts, already have it too, but for asking about c script, it will faster then python
Pages:
Jump to: