Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 33. (Read 59389 times)

jr. member
Activity: 81
Merit: 2
September 28, 2021, 05:28:31 AM
Can somebody please explain what the "brainless"-method is?

What is he adding and subtracting? WTF.

chit chat he is adding and subtracting ~ dont worry he got no working method and by knowing private key and than start doing addition or subtraction is bad idea as you will know each stage where keys are going and you can modify the values to get the desire output to say wooowww to your self "i did it" is some high level shit  Roll Eyes

as i told you working blindly on public key is real skill but you will never know where you will land even if you know where you landed still range number will stab you in back so chill and drink soda while BSGS are running hahahaha  Kiss
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 05:22:36 AM
Can somebody please explain what the "brainless"-method is?

What is he adding and subtracting? WTF. Can somebody provide an example?

jr. member
Activity: 81
Merit: 2
September 28, 2021, 05:03:14 AM
ssxb

Your post makes not so much sense to me?!

How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?

ok which part doesn't make sense , if you asking about 1/720 keys part ~ that what brainless said in his previous posts. check his last posts and you will find these comments.

and if you ask me this is possible  or not? , yes this is possible but not the way he explained.

but there is one problem with my yes. it is very difficult to guess specific range where you can start searching your calculated keys. perhaps you will guess 10 keys are in 110 range but they are not there. Kiss

is that right ssxb?

this is possible but not the way he explained.

which way you got?

it is very difficult to guess specific range where you can start searching your calculated keys. perhaps you will guess 10 keys are in 110 range but they are not there


correct
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 04:43:45 AM
Code:
from fastecdsa import curve
from fastecdsa.point import Point
import bit

G = curve.secp256k1.G
N = curve.secp256k1.q

def pub2point(pub_hex):
    x = int(pub_hex[2:66], 16)
    if len(pub_hex) < 70:
        y = bit.format.x_to_y(x, int(pub_hex[:2], 16) % 2)
    else:
        y = int(pub_hex[66:], 16)
    return Point(x, y, curve=curve.secp256k1)

# This function makes all the downscaled pubkeys obtained from subtracting
# numbers between 0 and divisor, before dividing the pubkeys by divisor.
def shiftdown(pubkey, divisor, file, convert=True):
    Q = pub2point(pubkey) if convert else pubkey
    # k = 1/divisor
    k = pow(divisor, N - 2, N)
    for i in range(divisor):
        P = Q - (i * G)
        P = k * P
        if (P.y % 2 == 0):
            prefix = "02"
        else:
            prefix = "03"
        hx = hex(P.x)[2:].zfill(64)
        hy = hex(P.y)[2:].zfill(64)
        file.write(prefix+ " " + hx+"\n") # Writes compressed key to file
    file.write("\n") # Writes compressed key to file

with open("input.txt", "r") as f, open("output.txt", "w") as outf:
    line = f.readline().strip()
    while line != '':
        outf.write("original: " +line + "\n")
        shiftdown(line, pow(2,1), outf)
        line = f.readline().strip()

input:
Code:
02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4

..d13 is 4 and ...fe4 is 5

output:
Quote
original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413

original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4
03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5


02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 is 2

Because i know 4 is even, i know it has to be the first pubkey. Because i know 5 is odd, I know it has to be the second key.

The problem is, that in bigger numbers, you can not determine if it is odd or even.

See,if I add the pubkey of 3
Quote
original: 02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 -> pubkey of 3
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> not the halve
02 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 -> pubkey of 1

original: 02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13 -> pubkey of 4
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 -> odd pubkey of 5
02 c62c910e502cb615a27c58512b6cc2c94f5742f76cb3d12ec993400a3695d413 -> even pubkey of 3

original: 022f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4 -> pubkey of 5
03 5699b93fc6e1bd29e09a328d657a607b4155b61a6b5fcbedd7c12df7c67df8f5 -> not the halve
02 c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5-> pubkey of 2

You see... You can not determine from the halve if it is the correct one.
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 04:32:18 AM
Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
How does this affect? Please explain in more detail..

You can always shift down a public key, aka halving a public key. You get two new public keys. But one is really halving and the other one is moving to the key middle range.

E.g.

You have the public key of 4 (binary represantation is 100). You halve it, and get the public key of 2 (10) and the public key of midrange - 2.
You have the public key of 5 (binary representation is 101). You halve it, and get the public key of public key of midrange - 2 or 3 and 2 (binary 10).

As you dont know the lowest bit, you can not determine which one of the pubkeys is the one you need. So you you have to take both and check them for the correct result.
jr. member
Activity: 40
Merit: 7
September 28, 2021, 04:19:05 AM
Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
How does this affect? Please explain in more detail..

maybe SSXB can explain this
jr. member
Activity: 33
Merit: 7
September 28, 2021, 04:15:12 AM
Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
How does this affect? Please explain in more detail..
jr. member
Activity: 40
Merit: 7
September 28, 2021, 04:09:34 AM
ssxb

Your post makes not so much sense to me?!

How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?

ok which part doesn't make sense , if you asking about 1/720 keys part ~ that what brainless said in his previous posts. check his last posts and you will find these comments.

and if you ask me this is possible  or not? , yes this is possible but not the way he explained.

but there is one problem with my yes. it is very difficult to guess specific range where you can start searching your calculated keys. perhaps you will guess 10 keys are in 110 range but they are not there. Kiss

is that right ssxb?
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 03:47:03 AM
ssxb

Your post makes not so much sense to me?!

How does brainless approach reduce the amount of public keys? Did you understand what he meant? Can you elaborate it further?
jr. member
Activity: 81
Merit: 2
September 28, 2021, 02:46:13 AM
guys big lol here plus some explanation from my side.

the script shared by NotATether is just doing opposite of divisor it is increasing 5 bit and giving you last key 5 bit uper range. only difference is while doing divisor you will get 1 key from down 5 bit and other all from defined uper bits range on exact same distance from reference value of this formula

Code:
N=115792089237316195423570985008687907852837564279074904382605163141518161494337
for i in range(32):
    print(i, hex((((N-1)//32)*i+1)%N))

lets say we have key 10  and we do divisor of 10 so what we get is like this (just example)

upper reference range
210 ,  200   , 190 , 180 .................. until 10
assume after divisor each key will have 5 bit down from reference ranges based of exact same distance
205  ,  195 ,  185 , 175 .................  until 5

here is problem , position in 32 keys list is not always same so you cant guess which key is in which range at which position. but if you guess one key correctly which range that key is then you can find easily which is correct 5 bit down key at what position as all other keys ranges are always in sequence. if you do increment of one key all the keys will get increment as well and perhaps they will switch position also in divisor output.


now talk about NotATether script,

the script he posted is doing mod inverses and it is just multiplying value until reach 5 uper bit. (no one can get 120 how can they will get 125 lolololo)

exapmle

key is in 120 range and you used his script output will be

120, 121 , 122, 123, 124, 125 thats it . all 32 keys will be from 120 to 125 range and some range will have 2 or more keys. but guaranteed all keys will be between 120 ~ 125 range at known position as 125 bit will be at 32 position and divisor will have only one key from lower 5 bit guaranteed (not known position) and all other keys from exact same distance with upper reference range. hope you get the point.


now talk about brainless theory -


NotATether and brainless are misunderstanding each other brainless maybe joked that he reduced keys 720 by doing multiplication , addition and subtraction bla bla bla until 90 or 100 bit but NotATether  is insisting what he explained inside his posts is not a way & there is also no way to achieve that and perhaps he never achieved that one and just keep lying.

now what i think is brainless have to explain this to community

Code:
" I got it down to 104 bits today, but with 32,000 pubkeys; better than the normal 2^16 normally required, but I can't figure out a way to shrink it down to one key... "
for 10 bit down = 1024 pubkeys
for 20 bit down = 1024*1024 = 1048576 pubkeys
for 30 bit down = 1024*1024*1024 = 1073741824 pubkeys
1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys
now you can start to find with above tip

as how he claimed this one and plus dont forget he claimed before that he found the 120 key but no plan to cash it but same time he asked .75 bitcoin to provide 115 range one key to buy 3090 (WTF)

well i think i got headache now time to drink coffee  Roll Eyes
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 02:38:26 AM
Also dont forget:
The Problem we have is, that we don't know if the last bit is even or odd. If you know if the last bit is even or odd, you can crack any public key in no time.
a.a
member
Activity: 126
Merit: 36
September 28, 2021, 01:48:18 AM
@WanderingPhilosopher
If you store it in a file, you can lookup the position. But is there a formula for shifting it up by knowing the position of the pubkey?

@fxsniper

Do you read? It is a memory tradeoff! If you bitshift a 256 bit key 128 bit you will have 2^128 keys to check in a range of 1-2^128. 2^128 is how many petabytes???

Please inform yourself about ECDLP. I invested last few weeks in my freetime to understand how it works and what to do.
member
Activity: 406
Merit: 47
September 28, 2021, 01:29:47 AM
this is just idea think out of box from "subtracted" methods 

I don't know much about in deep of ECDLP
I know only basic, simple and overview about ECDLP

Did have some video or document description for learning ECDLP  from scratch? (include how to multiply private key to ECDLP step by step, I know how to using function but can not calculate by manual?

Can ECDLP can be scale?
y2=x3+0x+7(mod p)
Y^2 = X^3 + ax + b
(what correct formula of algorithm)

Now ECDLP is 256 bit right?
Can ECDLP scale down to 128 bit?
Can ECDLP scale up to 512 bit?

if can not, please ignore.
Just silly question?

if ECDLP can scale
Can possible to test ECDLP 128 bit for fast found then up scan it
or
Can possible to test ECDLP 512 bit for possible hit one and down scale it

I forget knowledge a lot it like brainwasher myself all about crypto (now like a newbies)
member
Activity: 406
Merit: 47
September 28, 2021, 12:50:51 AM
How can test and proof "subtracted" methods  it is work?
I would like to try and testing.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
September 27, 2021, 08:40:15 PM
Quote
So if you would have 65 bits, you would bitshift it by the amount of pubkeys you can effectively  store in your bloom filter. Lets say you can store 2 ^ 31 pubkeys in your bloom filter. Now you have only to generate the pubkeys and store them and crack them. Get the privatekey, shiftup and remove the first bits from the 65 bits of the pubkey and get a new shorter pubkey. Crack again like you did with the first bits. Shift up and remove the next bits. small amount of bits left, crack them. Now add privatekeys from the three rounds and voila you have the privatekey of the 65 bit in about an no time.
You just plug it back into your script that help you bitshift and you have the private key to the original 65 bit pub key. All that shifting back up, shorter pub key, etc. is over kill.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
September 27, 2021, 08:38:18 PM
exactly yes.

 you can use after shifting :
https://github.com/iceland2k14/bsgs -> version multiplies pubkeys
Sloooooooooooooooooooooooooow....lol

You can use just about any GPU cracking program to speed up the process versus slowed down multi pub python script.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
September 27, 2021, 08:37:16 PM
You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.
Why would you need a decision tree? Once you find the pubkey/private key in the 24 bit range, you have solved the private key for the original 40 bit public key.
a.a
member
Activity: 126
Merit: 36
September 27, 2021, 03:12:19 PM

for 40 bit it is 5 minutes.

With 300 MKey/s it will be for me 1 hour.

2^40 = 1,099511628×10¹²

1,099511628×10¹² keys / 300000000 keys/s = 3665,038759253 s = 61 minutes

I suppose that if you don't know range of public key, you can't nothing.

Well. we are cracking this puzzle currently, right Smiley. So as I wrote earlier, this bitshifting is a memory/processing performance tradeoff. The more you bitshift the more keys you have to check, till it is not practical anymore. So e.g. you could store 2^30 pubkeys into a bloom filter and need about 4 GB memory or 2 ^31 pubkeys and about 8 GB RAM or 2 ^32 pubkeys and about ....

So if you would have 65 bits, you would bitshift it by the amount of pubkeys you can effectively  store in your bloom filter. Lets say you can store 2 ^ 31 pubkeys in your bloom filter. Now you have only to generate the pubkeys and store them and crack them. Get the privatekey, shiftup and remove the first bits from the 65 bits of the pubkey and get a new shorter pubkey. Crack again like you did with the first bits. Shift up and remove the next bits. small amount of bits left, crack them. Now add privatekeys from the three rounds and voila you have the privatekey of the 65 bit in about an no time.

Maybe not as fast as BSGS or Kangaroo, but still faster then BruteForce. Also BSGS is possible to crack multiple keys, Kangaroo currently can only crack one pubkey at a time, so totally useless for this bitshifting operation.

because if it works, you are millionaire, and the question what are you doing on forum:D

lets say you want to crack 256 bit publickey. You could bitshift by lets say 30 bits. You would still need to bruteforce 226 bits. 
jr. member
Activity: 48
Merit: 11
September 27, 2021, 02:42:02 PM

You will have 32 pubkeys, but from those 32 pubkeys only one will be in the desired range. The other 31 pubkeys will be all over the place, and thus being uninteresting.
Thank you.
I translated it incorrectly at first, then I understood what was talking about and deleted my message.
jr. member
Activity: 48
Merit: 11
September 27, 2021, 02:40:02 PM
...
OpenSSL private keys aka. 256-bit random numbers by themselves will not help with reducing the number of keys, however it is estimating the bias (as in - empirically, some bits will appear in a certain state more often than others - when several thousand random numbers are generated) in OpenSSL random numbers this estimation method draws its power from.

Also this doesn't work if your sample only one private key, that's why I mentioned that thousands of random numbers need to be sampled. My calculations get away with just 1000, though.

...

I recently did a little research on private key generation via /dev/urandom. More than 100 million keys were used for the test. The bit allocation was about the same = 0.5
Maybe the old versions of OpenSSL, which were probably used in the puzzle creation, had some vulnerabilities and gave some deviation?
Pages:
Jump to: