error when calling crack_baby_giant(C, P, n, Q)

[rohosalndn]

Hello,

I enter this data and get the error below. It should work but I am not sure what I am doing wrong. I am trying to find the key by searching in a 2^54 points.

Please help. Thanks!

>>>C = CurveOverFp(0, 0, 7, 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1)
y^2 = x^3 + 7 over F_115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> P = Point(55066263022277343669578718895168534326250603453777594175500187360389116729240,
... 32670510020758816978083085130507043184471273380659243275938904335757337482424)
>>> n = 2^54
>>> Q = (69335761065767984070318781108127416310968753866933119760392423089576366173459, 113425617697416972613102767146321902225172329004525144463444008550345431352693)

>>>crack_baby_giant(C, P, n, Q)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "mini_ecdsa.py", line 470, in crack_baby_giant
    R = curve.add(Q, curve.invert(curve.mult(P, g*m)))
  File "mini_ecdsa.py", line 321, in add
    y_diff = (P_2.y - P_1.y) % self.char
AttributeError: 'tuple' object has no attribute 'y'

d should be returned as: 30045390491869460

[dem10]

Hi,you indicated (n) as a degree n = 2^54 specify as number n = 18014398509481984 In the example given the number n and not the degree. You also have a error in Q. You have a space between the points x and y(I pointed the arrow, this space should not be).Therefore, we see error ('tuple' object has no attribute 'y'), the tool does not see the point y. Point x,Point y (no spaces). you written (Q = )need(Q = Point) example Q = Point(4534,6584) Also, the value of P, everything must be specified without spaces. P = Point(550...29240,326...82424)

[rohosalndn]

Thank you, I got rid of the error. But it just stays stuck after the 'crack_baby_giant(C, P, n, Q)' command. It is like this for 12 hours, it should find the solution fast, correct?

Perhaps the tool is searching the whole space? Can I specify a range to search between two values like between 1801439000000000 and 18014398509481984? Or why is not finding the solution?

n is small enough for baby-step-giant-step. Your assistance is much appreciated.

[dem10]

The tool is most likely works, it will display the results as soon as it finds a collision. I don’t know about key space, the developer may clarify this issue. But he is not very sociable.

[rohosalndn]

I know it works, I just need it to work with the values I posted. It should, mathematically. But I'm not very good with coding.

This is for a Uni assignment and I am grateful if the developer can have a look and reply. I am posting here the final code I am using where it seems to get stuck.

>>> execfile('mini_ecdsa.py')
>>> C = CurveOverFp(0, 0, 7, 2**256-2**32-2**9-2**8-2**7-2**6-2**4-1)
y^2 = x^3 + 7 over F_115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> P = Point(55066263022277343669578718895168534326250603453777594175500187360389116729240,32670510020758816978083085130507043184471273380659243275938904335757337482424)
>>> Q = Point(69335761065767984070318781108127416310968753866933119760392423089576366173459,113425617697416972613102767146321902225172329004525144463444008550345431352693)
>>> n = 18014398509481984
>>> crack_baby_giant(C, P, n, Q)

Anyway, good luck and thanks again!

[dem10]

I'm not sure that it affects. You have entered data in this order( C, P, Q, n) and enter the query (C, P, n, Q) 1 C 2 P 3 n 4 Q

[qubd]

The initial problem was just that you defined Q as a tuple,Q = (1,2), when it should be a Point object, Q = Point(1,2) as dem10 correctly pointed out. The presence or absence of spaces shouldn't make any difference though (this is the case more generally in python, 3+5 and 3 + 5 should both be 8).

The code you posted in the last code box has a problem, it looks like you're using the curve (with base point) secp256k1, as I did in the readme, but the order of P is wrong. Did you intend to use a different base point P that generates a smaller subgroup (of order 18014398509481984) instead?

P.S. I am perfectly sociable. I'm sure you can understand that answering questions about code I wrote years ago as a pet project and had no intention of doing anything else with is a fairly low priority task.

[rohosalndn]

Hi and thanks for your time.

I am trying to use the default secp256k1 parameters, yes, but not the large search range. I want the tool to search within a 18014398509481984 or less range not the large EC field which is impossible due to DLP. But I want to keep P and Q and calculate d. Is that possible? Or it can only be done by using a smaller F_ and of course different P and Q?

[qubd]

Oh, I see. You're searching for a solution to Q = dP for d between 1 and 18014398509481984. It appears that n is only used to determine the size of the hash table in the baby step giant step method, so it seems you can vary the largest key searched in this way.

Here are some smaller examples of what you're doing. Everything seems to work fine.

>>> C = CurveOverFp.secp256k1()
y^2 = x^3 + 7 over F_115792089237316195423570985008687907853269984665640564039457584007908834671663
>>> P = Point.secp256k1()
>>> Q = C.mult(P,73)
>>> n = 100
>>> crack_baby_giant(C,P,n,Q)
Priv key: d = 73
Time: 0.009 secs
>>> Q = C.mult(P,734198)
>>> n = 1000000
>>> crack_baby_giant(C,P,n,Q)
Priv key: d = 734198
Time: 2.968 secs
>>> Q = C.mult(P,73419861)
>>> n = 100000000
>>> crack_baby_giant(C,P,n,Q)
Priv key: d = 73419861
Time: 48.299 secs
>>> Q = C.mult(P,734198613)
>>> n = 1000000000
>>> crack_baby_giant(C,P,n,Q)
Priv key: d = 734198613
Time: 229.004 secs

I think the crack_baby_giant function works fine as you've called it, it's simply very slow. Remember that this code is not designed to run fast. I've made no attempts to optimize it in any way. Python does all the big integer arithmetic (and hash table stuff) naively, so it's going to be vastly slower than production crypto code.

[rohosalndn]

Thanks a lot, this is good enough for me. By the way, there are many people I know looking for some DLP implementations. We can explain the math behind ECC but in practice putting it in code to demonstrate it's hard to find something like your tool. Cheers.

[qubd]

For posterity, note that in general I was assuming that the parameter n was the order of the base point when I wrote all this code. It just so happens that the baby step giant step method never uses this fact, and smaller values of n really do restrict the values of d in Q = dP being searched through. The rho method as I've implemented it, for example, won't work correctly unless n is the order of the base point (calculation of a multiplicative inverse won't work).