jeanlucpons / bsgs

Baby Step Giant Step for SECPK1

Baby Step Giant Step for SECPK1

A simple Baby Step Giant Step program for SecpK1.

Structure of the input file:

• All values are in hex format
• Public keys can be given either in compressed or uncompressed format

Babystep size
Start range
End range
Key #1
Key #2
...

ex

40000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
0335BB25364370D4DD14A9FC2B406D398C4B53C85BE58FCC7297BD34004602EBEC

How it works

It uses a hash table (25bit hash) to store the baby steps. 2^30 baby steps is about 9GB (we do not store full point, only a part of it, false collisions are handled later). Here is a brief description of the algoritm:

We have to solve P = k.G, we know that k lies in the range ]k1,k2], G is the SecpK1 generator point.

 # Baby Step number
 # With enough memory, the best choice is m = floor(sqrt(k2-k1)) for a single key
 m = Baby Step number
 Compute a table of [G,2.G,3.G,..,b.G,...,m.G]
 S = P - k1.G
 found = false
 step = 0
 while not found and step<(k2-k1) {
   if S is in the table {
     b = Index of S in the table
     found = true
   }
   if not found {
     # Giant step
     S = S - m.G
     step = step + m
   }
 }
 k = k1 + step + b

Example of usage

On a Xeon X5647 2.93GHz with 12GB of RAM (Ubuntu 18.04)

Input file: in.txt

40000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5effffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
04A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD3E48440249D6BC78BC928AA52B1921E9690EBA823CBC7F3AF54B3707E6A73F34
0404A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3BD05357CAF8340CB041B1D46C5BB6B88CD9859A083B0804EF63D498B29D31DD1
040B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D1D18283AF49556CF33E1EA71A16B2D0E31EE7179D88BE7F6AA0A7C5498E5D97F
04837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493E46726DE04352832790FD1C99D9DDC2EE8A96E50CAD4DCC3AF1BFB82D51F2494
040ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBAD71A2A535FCB54D56913E7F37D8103BA33ED6441D019D0922AC363FCC792C29A
0422DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF038F139D652842243FC841E7C5B3E477D901F88C5AB0B88EE13D80080E413F2ED
04DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E536695DF83B68FD0F396BB9BFCF6D4FE312F32A43CF3FA1FE0F81DF70C877593B64E0
043BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687528B6D2BC0AA7A5855D168B26C6BAF9DDCD04B585D42C7B9913F60421716D37A
04332A02CA42C481EAADB7ADB97DF89033B23EA291FDA809BEA3CE5C3B73B20C49C410D1AD42A9247EB8FF217935C9E28411A08B325FBF28CC2AF8182CE2B5CE38
04513981849DE1A1327DEF34B51F5011C5070603CA22E6D868263CB7C908525F0C19EBA6BD2A8DCF651E4342512EDEACB6EA22DA323A194E25C6A1614ABD259BC0
04D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6805511F46262E10A25F252FD525AF1CBCC46016B6CD0A7705037364309198DA1
0456B468963752924DBF56112633DC57F07C512E3671A16CD7375C58469164599D1E04011D3E9004466C814B144A9BCB7E47D5BACA1B90DA0C4752603781BF5873
04D5BE7C653773CEE06A238020E953CFCD0F22BE2D045C6E5B4388A3F11B4586CBB4B177DFFD111F6A15A453009B568E95798B0227B60D8BEAC98AF671F31B0E2B
04B1985389D8AB680DEDD67BBA7CA781D1A9E6E5974AAD2E70518125BAD5783EB5355F46E927A030DB14CF8D3940C1BED7FB80624B32B349AB5A05226AF15A2228
0455B95BEF84A6045A505D015EF15E136E0A31CC2AA00FA4BCA62E5DF215EE981B3B4D6BCE33718DC6CF59F28B550648D7E8B2796AC36F25FF0C01F8BC42A16FD9

Result:

pons@linpons:~/BSGS$ ./bsgs in.txt 
BSGS v1.0
BabyStep:0x40000000 (2^30.00)
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 8
BabyStep Thread 0: 0x1 -> 0x8000000
BabyStep Thread 3: 0x18000001 -> 0x20000000
BabyStep Thread 1: 0x8000001 -> 0x10000000
BabyStep Thread 2: 0x10000001 -> 0x18000000
BabyStep Thread 4: 0x20000001 -> 0x28000000
BabyStep Thread 5: 0x28000001 -> 0x30000000
BabyStep Thread 6: 0x30000001 -> 0x38000000
BabyStep Thread 7: 0x38000001 -> 0x40000000
[2.05 MKey/s][Cnt 2^30.00][08:38][8959.9MB]  
Sort Thread 0: 00000000 -> 00400000
Sort Thread 1: 00400000 -> 00800000
Sort Thread 2: 00800000 -> 00C00000
Sort Thread 3: 00C00000 -> 01000000
Sort Thread 7: 01C00000 -> 02000000
Sort Thread 6: 01800000 -> 01C00000
Sort Thread 4: 01000000 -> 01400000
Sort Thread 5: 01400000 -> 01800000
[2.51 MSort/s][Cnt 2^25.00][13s][8959.9MB]  
GiantStep Thread 1: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E2000000000000000
GiantStep Thread 0: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
GiantStep Thread 2: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E4000000000000000
GiantStep Thread 3: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E6000000000000000
GiantStep Thread 4: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E8000000000000000
GiantStep Thread 5: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EA000000000000000
GiantStep Thread 6: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EC000000000000000
GiantStep Thread 7: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE000000000000000
[13.67 MKey/s][Cnt 2^33.76][17:46][8959.9MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 
[13.68 MKey/s][Cnt 2^33.43][14:07][8959.9MB]  
Key# 1 Pub:  0x02A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EB5ABC43BEBAD3207 
[13.68 MKey/s][Cnt 2^33.49][14:44][8959.9MB]  
Key# 2 Pub:  0x0304A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E5698AAAB6CAC52B3 
[13.68 MKey/s][Cnt 2^33.68][16:49][8959.9MB]  
Key# 3 Pub:  0x030B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E59C839258C2AD7A0 
[13.64 MKey/s][Cnt 2^33.48][14:36][8959.9MB]  
Key# 4 Pub:  0x02837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E765FB411E63B92B9 
[13.66 MKey/s][Cnt 2^33.86][19:00][8959.9MB]  
Key# 5 Pub:  0x020ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBA 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7D0E6081C7E0E865 
[13.65 MKey/s][Cnt 2^31.84][04:41][8959.9MB]  
Key# 6 Pub:  0x0322DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF0 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EC737344CA673CE28 
[13.68 MKey/s][Cnt 2^33.59][15:41][8959.9MB]  
Key# 7 Pub:  0x02DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E53669 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E38160DA9EBEAECD7 
[13.65 MKey/s][Cnt 2^33.69][16:53][8959.9MB]  
Key# 8 Pub:  0x023BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E79D808CAB1DECF8D 
[13.65 MKey/s][Cnt 2^33.37][13:35][8959.9MB]  
Key# 9 Pub:  0x02332A02CA42C481EAADB7ADB97DF89033B23EA291FDA809BEA3CE5C3B73B20C49 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E54CAD3CFBC2A9C2B 
[13.68 MKey/s][Cnt 2^32.74][08:42][8959.9MB]  
Key#10 Pub:  0x02513981849DE1A1327DEF34B51F5011C5070603CA22E6D868263CB7C908525F0C 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0D5ECCC38D0230E6 
[13.68 MKey/s][Cnt 2^30.73][02:10][8959.9MB]  
Key#11 Pub:  0x03D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE3579364DE939B0C 
[13.67 MKey/s][Cnt 2^33.82][18:27][8959.9MB]  
Key#12 Pub:  0x0356B468963752924DBF56112633DC57F07C512E3671A16CD7375C58469164599D 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7C43B8E079AE7278 
[13.66 MKey/s][Cnt 2^32.76][08:51][8959.9MB]  
Key#13 Pub:  0x03D5BE7C653773CEE06A238020E953CFCD0F22BE2D045C6E5B4388A3F11B4586CB 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E8D63EF128EF66B42 
[13.66 MKey/s][Cnt 2^31.11][02:49][8959.9MB]  
Key#14 Pub:  0x02B1985389D8AB680DEDD67BBA7CA781D1A9E6E5974AAD2E70518125BAD5783EB5 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E2452DD26BC983CD5 
[13.67 MKey/s][Cnt 2^33.76][17:42][8959.9MB]  
Key#15 Pub:  0x0355B95BEF84A6045A505D015EF15E136E0A31CC2AA00FA4BCA62E5DF215EE981B 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7AD38337C7F173C7 

Done: Total time 03:35:53 

bsgs's Issues

Sawe work

Dear Jean Luc, please make a path save file.

Point::equals is not always true if you using Point::Set

I been testing this funtion in my keyhunt tool, and some times i get a wrong result, this is because sometimes you are working adding points in a blind way, and you need test if some point is equals to other to performe a DoubleDirect instead of AddDirect

set work in this way, set x and y but not z

void Point::Set(Point &p) {
  x.Set(&p.x);
  y.Set(&p.y);
}

and equals evaluate the 3 elements, x,y and z

bool Point::equals(Point &p) {
  return x.IsEqual(&p.x) && y.IsEqual(&p.y) && z.IsEqual(&p.z);
}

To solve this when you are working you have 2 ways to to that, perform Double direct outside of the cycle or change the Point::set funtion to set also the z Integer in the next way:

void Point::Set(Point &p) {
  x.Set(&p.x);
  y.Set(&p.y);
  z.Set(&p.z);
}

Best regards!

Substart startRange bug.

JLP use a Substart startRange to the point to solve.

  Int km(&ph->startKey);
  km.Neg();
  km.Add(&secp->order);
  km.Sub((uint64_t)(CPU_GRP_SIZE/2)*bsSize);
  startP = secp->ComputePublicKey(&km);
  startP = secp->AddDirect(keyToSearch,startP);

This is the bug. startP is a neg point.
the sub result maybe 0.
however 0 key is secp256k1 is infinity(unaviable).
I have a test input file:

400
0
FFFFFFF
02A804C641D28CC0B53A4E3E1A2F56C86F6E0D880A454203B98CD3DB5A7940D33A #0x80000

According to the code.

Int km(&ph->startKey); #0
km.Neg(); #0
km.Add(&secp->order); #0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
km.Sub((uint64_t)(CPU_GRP_SIZE/2)*bsSize); #0x80000
startP = secp->ComputePublicKey(&km); # (A804C641D28CC0B53A4E3E1A2F56C86F6E0D880A454203B98CD3DB5A7940D33A,6A417CDAD4D0592FC213D7BD3E9FB817E50E73576308C956BC316A0492B965B5)
startP = secp->AddDirect(keyToSearch,startP); #JLP show the result is 0xAFF6737C5AE67E958B6383CBA1526F2123E4EFEB757BF88CE65849490D7E51EA(wrong)

Bsgs GPU support?

Tnx

How to capture all generated private key ,?

BSGS/BSGS.cpp

Line 432 in 5bf3bb3

if(p.equals(keyToSearch)) {

This line only catch if found point in table,
for(uint64_t i = 0; i<CPU_GRP_SIZE; i++) {

auto killed

chawla@i3-6100:/jlp/BSGS$ ./bsgs in.txt
BSGS v1.0
BabyStep:0x40000000 (2^30.00)
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 4
BabyStep Thread 0: 0x1 -> 0x10000000
BabyStep Thread 1: 0x10000001 -> 0x20000000
BabyStep Thread 2: 0x20000001 -> 0x30000000
BabyStep Thread 3: 0x30000001 -> 0x40000000
[3.02 MKey/s][Cnt 2^28.48][01:55][3632.1MB] Killed
chawla@i3-6100:/jlp/BSGS$ ./bsgs in.txt
BSGS v1.0
BabyStep:0x40000000 (2^30.00)
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 4
BabyStep Thread 0: 0x1 -> 0x10000000
BabyStep Thread 1: 0x10000001 -> 0x20000000
BabyStep Thread 2: 0x20000001 -> 0x30000000
BabyStep Thread 3: 0x30000001 -> 0x40000000
[3.01 MKey/s][Cnt 2^28.52][01:57][3697.5MB] Killed

How can I use __builtin_bswap64 in NVCC of CUDA?

There are built-in functions in GCC to flip byte contents, e.g. __builtin_bswap64. Is there a similar function under NVCC for CUDA? If not, how do I implement this function on the device?

Improvements

Can you add ETA to the program?
can you add table of Best step for Ram?
40000000 For 9GB
80000000 for 18GB?

Missing hit (Edge case)

input file:

400
800000000000000000000000000000
8000000000000000000000001FFFFF
03af08c568fbbc8c878252b72ff8cc03101b8f5ef61611dfdc3289719c6dec7dc2
032a08f56606f16c2bc60e77e5fe333c4d0e2114dd7eb8cf77b542bbc9c15868d9

Only one of those keys were found, both are in the middle of the given range

Private Key: 8000000000000000000000000FFFFF
Public key: 03af08c568fbbc8c878252b72ff8cc03101b8f5ef61611dfdc3289719c6dec7dc2

Private Key: 800000000000000000000000100000
Public key: 032a08f56606f16c2bc60e77e5fe333c4d0e2114dd7eb8cf77b542bbc9c15868d9

I chose the baby step size of 0x400 (1024) just to debug less key operations, both keys are Edge cases but only one of them were found.

I wonder if someone miss one hit by this bug.

Double speed for BSGS

Hi every one, hi JLP i hope you read this.

Current approach for BSGS is more o less the, example:

Target Key 99
known range 75-100 (Like puzzles etc...)
Baby step 5  = { 0,1,2,3,4}
Giant step 5 = {0,5,10,15,20}

First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24

New Target Key 24

Giant step 0
24 - 0 = 24 is on Baby Table? NO

Giant step 1
24 - 5 = 19 is on Baby Table? NO

Giant step 2
24 - 10 = 14 is on Baby Table? NO

Giant step 3
24 - 15 = 9 is on Baby Table? NO

Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)

Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99

Here we covered from 0 to 25

But since negative Numbers have the same X value of positive numbers that mean that our current baby table is also valid for:
Baby step 5 = {-4,-3,-2,-1,0,1,2,3,4}

We can move exclude the 0 for this example and keep some table like:
Baby step 5 = {-5,-4,-3,-2,-1,1,2,3,4,5}

We can handle the Zero element in some especial case, or include it and use an odd baby table,

So to work with this new Baby table we need to rearange the Giant steps just a litle.

Giant step 5 = {5,15,25,35,45}

| GS | RANGE BS |
|  5 | 0  - 10  |
| 15 | 10 - 20  |
| 25 | 20 - 30  |
| 35 | 30 - 40  |
| 45 | 40 - 50  |

So we covered a Double Range from 0 to 50 with the same number of Operations, this is double speed.

I already implement this on my tool keyhunt.

output writen to file

result should be writen to output file, have u assign switch ?

Compilation on OSX

Is it possible to compile on OSX? I am stuck on 2 errors in BSGS.h - unknown type p_thread and _mutex.

list of pubkeys

Q here, all pubkeys list checked at first which one found, or one by one check and found ?

How much ram use 2^36 ? 1 tb ram be along ? ( how calculate )

How much ram use 2^36 ? 1 tb ram be elong ? ( how calculate )

BSGS or Kangaroo?

Is it a comparison or evaluation between Kangaroo and BSGS which one is faster on a similar range, similar PubKey key on the same hardware?

thanks

Error message

I am getting error message. Please help me

"Warning, range is not a multiple of nbThread"

This may be nothing, but I wanted to check. Using some rather outlandish start/stop numbers, I saw these warnings pop up, but the program continues to run. Is it just info or do I need to slack off my span to prevent possible miscalculation?

in.txt
20000000
000000000000000000000000000000000000000002CE00BB2136A445C71E85BF
000000000000000000000000000000000000016F14FC2054CD87EE6396B33DF3
list of keys goes here

BSGS v1.1
BabyStep:0x0000000020000000 (2^29.00)
Start:2CE00BB2136A445C71E85BF
Stop :16F14FC2054CD87EE6396B33DF3
Keys :35
Number of CPU thread: 4
BabyStep Thread 0: 0x0000000000000001 -> 0x0000000008000000
BabyStep Thread 2: 0x0000000010000001 -> 0x0000000018000000
BabyStep Thread 3: 0x0000000018000001 -> 0x0000000020000000
BabyStep Thread 1: 0x0000000008000001 -> 0x0000000010000000
[2.04 MKey/s][Cnt 2^29.00][03:15][4864.0MB]
Sort Thread 0: 00000000 -> 00800000
Sort Thread 1: 00800000 -> 01000000
Sort Thread 2: 01000000 -> 01800000
Sort Thread 3: 01800000 -> 02000000
[4.70 MSort/s][Cnt 2^25.00][07s][4864.0MB]
Warning, range is not a multiple of nbThread
Warning, range is not a multiple of nbThread*1024
GiantStep Thread 1: 5BC75988A18C4AF6CD3B03B3CC
GiantStep Thread 3: 1135070986E62739BDC22CE0FE6
GiantStep Thread 2: B78BE51087F75F4954AEE8E1D9
GiantStep Thread 0: 2CE00BB2136A445C71E85BF
[6.20 MKey/s][Cnt 2^30.18][03:18][4864.0MB]