Baby step giant step bitcoin

0xTowel / bsgs.py

#!/usr/bin/env python3

# -*- coding:utf-8 -*-

# Towel 2017

from math import ceil , sqrt

def bsgs ( g , h , p ):

»’

Solve for x in h = g^x mod p given a prime p.

If p is not prime, you shouldn’t use BSGS anyway.

»’

N = ceil ( sqrt ( p — 1 )) # phi(p) is p-1 if p is prime

# Store hashmap of g^ <1. m>(mod p). Baby step.

tbl =

# Precompute via Fermat’s Little Theorem

c = pow ( g , N * ( p — 2 ), p )

# Search for an equivalence in the table. Giant step.

for j in range ( N ):

y = ( h * pow ( c , j , p )) % p

if y in tbl :

return j * N + tbl [ y ]

# Solution not found

return None

print ( bsgs ( 7894352216 , 355407489 , 604604729 ))

This comment has been minimized.

Copy link Quote reply

PiepsC commented Jun 11, 2020 •

I’m a little lost on what you are computing for c.

Edit: nevermind. You’re using Fermat’s on the order of p. Ie inverse N.

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Источник

Solving Elliptic Curve Discrete Logarithm Problem

Elliptic curve cryptography is powerful. Calculating public key from known private key and base point can be handled easily. On the other hand, extracting private key from known public key and base point is not easy task. This is called as Elliptic Curve Discrete Logarithm Problem. Solving ECDLP requires O(k) operations in big O notation with brute force method. For instance, 256-bit private key should be selected for bitcoin.

I have the power

Basically, we would like to find k from the equation Q = k x P

Baby step giant step

This approach reduces complexity O(√n) where n states the order of group

Suppose that we are working on the bitcoin curve which satisfies y 2 = x 3 + 7 and the base point is (2, 24). Additionally, modulo would be 199 and order of group would be 211. Suppose that we have a point (14, 39) on that curve as public key.

Now, we would like to find k such that (14, 39) = k x (2, 24)

Remember that Q = k x P where P is the base point, Q is the public key value, and k is the private key. Herein, we can illustrate private key k as (jm + i).

Let’s put this linear formula instead of the private key.

Q = k x P = (jm + i) x P

Reflect base point multiplier into the parenthesis

Q = jm x P + i x P

Move (jm x P) term into the left side of the equation.

Q – jm x P = i x P

So, the following code will calculate jm x P.

Remember that elliptic curve is symmetric about x-axis. That’s why, if coordinates of point P is (xp, yp), then negative point -P would be (xp, -yp).

Q + jm x (-P) = i x P

Besides, we can calculate Q + jm x (-P) as coded below. I just set negative of y coordinate (-checkpoint[1]).

Now, all we need is to check this checkpoint is equal to i x P. We’ve already calculated i x P in previous steps.

Attacking

So, private key can be found in 27th operation in baby step giant step approach. On the other hand, it can be found in 177th operation if brute force is applied. This approach runs 6 times faster the brute force method even on very small numbers. It would reduce the complexity dramatically for very large private keys.

Solving Elliptic Curve Discrete Logarithm Problem

Even though, this approach reduces the complexity dramatically, elliptic curve cryptography is still too powerful and elliptic curve discrete logarithm problem is still hard. For instance, the following values are order of group and its square root of bitcoin protocol.

n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (256 bit)
√n = 340282366920938463463374607431768211455

So, Square root of order is greater than 10 38 . Suppose that you can check a possibility in microseconds (10 -6 ). Then, finding private key lasts more than years 10 24 based on the following calculation.

(10 38. 10 -6 )/(60 . 60 . 24 .365) > 10 24

Funnily, age of the universe is 10 9 years. You can imagine that why elliptic curve crypto systems are powerful. This is because of that there is no sub-exponential solution for ECDLP yet! Besides, ECDLP seems much more difficult than the traditional DLP which empowers RSA and Diffie Hellman. Select a 256-bit random private key and leave the rest to ECC!

Code of this tutorial is pushed into my GitHub profile. You can test it by yourself if you clone the repository. Also, I captured this post a video.

Источник

Baby-Step, Giant-Step: Solving Discrete Logarithms and Why It’s A Hard Problem To Solve

Within normal logarithms we define:

So if we want to find the value of x, we use:

So 10⁴ is 10,000, and the inverse log is log10(10,000) is 4.

Within discrete logarithms we introduce a finite field with a prime number. For this we have:

and where p is the prime number. It is thus a difficult task to find the value of x which has been used, even if we know h, g and p. We use discrete logarithms with the Diffie-Hellman key exchange method and in ElGamal encryption.

Let’s start with an example:

In this case we have g= 5, h= 20 and p= 53, and want to find x. We first determine the square root of p-1, and we will round it up to the nearest integer. In this case it will be:

N =Ceiling(√ (p-1)) = Ceiling(√ (52)) = 7

Next we will pre-compute from 1 to N with the baby table. These will store gⁱ (mod p) and then store them in the form of :

If i=0, we get 5⁰ mod 7 gives 1 <1:0>.

For i=1 we get 5¹ mod 7 gives 5

For i=2 we get 5² mod 7 gives 5

We now have a list of pairs from 0 to the square root of p-1.

We now compute g⁻ᴺ to give c:

We then search through values of:

until we find a match in the table. We then take this value and multiply it by N and add the value we have found:

The completed code is:

Now let’s try and example. If we try 22 = 5ˣ (mod 53) we get [Try]:

This gives a solution of x=9, and when we try it back in 5⁹ (mod 53), we get a result of 22.

Here are a few examples:

And there you go.

In real-life examples our prime numbers are likely to be extremely large, so we will need to store the square root of the number of values. For a 128-bit prime number we will need to store:

In ElGamal the recommended prime number size is 2,048 bits which would fill all the memory on the planet and much more. For just 512 bit prime numbers we get:

Which is a vast amount of memory.

Conclusions

We reduce the complexity of the problem by storing a square root of the prime number used. So for a prime number of 14,947, we now only need to 123 values. Unfortunately as our prime numbers get larger the amount of memory we need becomes vast.

And so discrete logarithms continue to be a hard task for a computer. If someone uses a 512-bit prime number, we will need to store 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 values in our baby table. This would be much more than all the memory on the planet. For 2,048 bit prime numbers we would need vastly more memory. Unfortunately quantum computers do not struggle as much with discrete logarithms, and will be able to crack them in a reasonable amount of time.

Источник

Baby step giant step bitcoin

UPDATE: I have removed all the BSGS files from version one, for the combined effort, on this page. The BSGS exe file located on main page is the same as Jean Luc’s; I just added the function where it will print and save a text document with the public and private keys. The combined effort seemed to cause confusion because of the pub key shift so now it’s back to just searching in the actual 120 bit range. Users can still share ranges searched. I will upload a simple python and batch file to randomly choose ranges to search and keep track of those ranges via a text file.

Baby Step Giant Step Combined Efforts to Find 1.2 Bitcoin

I have tweaked the code of Jean Luc Pons’ Baby Step Giant Step program ( https://github.com/JeanLucPons/BSGS ) to help find the #120 puzzle in the Bitcoin Challenge Transaction ( https://bitcointalk.org/index.php?topic=5218972.0 ).

Not everyone has a GPU or a high powered GPU to use programs such as Bitcrack or Kangaroo methods. But mostly everyone has a CPU, and that is what powers the Baby Step Giant Step (BSGS) program. the CPU located in your computer. Now, everyone has a chance to help crack the puzzle. One major advantage over Kangaroo methods, the BSGS is easy to give different ranges to workers without losing in complexity which is not possible with Kangaroo.

The tweaks I made to the original code include: a random range generator the program now automatically creates the input file: Baby Step Size Start Range End Range and applicable Public Keys (to search for)

All you have to do is download the tweaked program and the already made batch file. Once you download the files, place them in the same folder and double-click on the batch file. The program will automatically start searching for the public key. That’s it. It’s that easy.

What you will notice in the folder you placed your files in: an input file will automatically pre-fill and there will be a file called ranges_searched.txt

After we run the program for awhile, people can send me their ranges_searched.txt file and I can keep track of ranges searched and maybe this will help us narrow down to a smaller range in the future. Or, people can post how many ranges they’ve already searched and we can keep a running tally.

I took the #120 public key (120 bits) and compressed it down to 117 bits to make our search range 8 times smaller.

What happens when you find the public key? If your CPU finds a key, a text document called, FOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYS.txt will be created in the folder and it will contain the private key and the public key. Send that information to me, along with your bitcoin wallet address, and I will recreate the original #120 public key, and we will split the 1.2 bitcoin 50/50. It’s that easy.

How I am running the program on my computer: I have downloaded the 16 BSGS exe files and the 16 batch files. In each batch file, it calls to use one CPU thread (-t 1). So I run as many as the batch files/programs as my CPU can handle. On an i5-4690, with four instances running (4 threads total), each thread completes a range in about 9 seconds. So that’s 4 ranges checked every 9 seconds, which on the safe side, this one computer checks about 34,560 ranges a day. Let me know how fast your computer completes a range.

About

Baby Step Giant Step Combined Efforts to Find 1.2 Bitcoin

Источник

Baby step giant step bitcoin

UPDATE: I have removed all the BSGS files from version one, for the combined effort, on this page. The BSGS exe file located on main page is the same as Jean Luc’s; I just added the function where it will print and save a text document with the public and private keys. The combined effort seemed to cause confusion because of the pub key shift so now it’s back to just searching in the actual 120 bit range. Users can still share ranges searched. I will upload a simple python and batch file to randomly choose ranges to search and keep track of those ranges via a text file.

Baby Step Giant Step Combined Efforts to Find 1.2 Bitcoin

I have tweaked the code of Jean Luc Pons’ Baby Step Giant Step program ( https://github.com/JeanLucPons/BSGS ) to help find the #120 puzzle in the Bitcoin Challenge Transaction ( https://bitcointalk.org/index.php?topic=5218972.0 ).

Not everyone has a GPU or a high powered GPU to use programs such as Bitcrack or Kangaroo methods. But mostly everyone has a CPU, and that is what powers the Baby Step Giant Step (BSGS) program. the CPU located in your computer. Now, everyone has a chance to help crack the puzzle. One major advantage over Kangaroo methods, the BSGS is easy to give different ranges to workers without losing in complexity which is not possible with Kangaroo.

The tweaks I made to the original code include: a random range generator the program now automatically creates the input file: Baby Step Size Start Range End Range and applicable Public Keys (to search for)

All you have to do is download the tweaked program and the already made batch file. Once you download the files, place them in the same folder and double-click on the batch file. The program will automatically start searching for the public key. That’s it. It’s that easy.

What you will notice in the folder you placed your files in: an input file will automatically pre-fill and there will be a file called ranges_searched.txt

After we run the program for awhile, people can send me their ranges_searched.txt file and I can keep track of ranges searched and maybe this will help us narrow down to a smaller range in the future. Or, people can post how many ranges they’ve already searched and we can keep a running tally.

I took the #120 public key (120 bits) and compressed it down to 117 bits to make our search range 8 times smaller.

What happens when you find the public key? If your CPU finds a key, a text document called, FOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYSFOUNDKEYS.txt will be created in the folder and it will contain the private key and the public key. Send that information to me, along with your bitcoin wallet address, and I will recreate the original #120 public key, and we will split the 1.2 bitcoin 50/50. It’s that easy.

How I am running the program on my computer: I have downloaded the 16 BSGS exe files and the 16 batch files. In each batch file, it calls to use one CPU thread (-t 1). So I run as many as the batch files/programs as my CPU can handle. On an i5-4690, with four instances running (4 threads total), each thread completes a range in about 9 seconds. So that’s 4 ranges checked every 9 seconds, which on the safe side, this one computer checks about 34,560 ranges a day. Let me know how fast your computer completes a range.

About

Baby Step Giant Step Combined Efforts to Find 1.2 Bitcoin

Источник