Topic: Even or Odd Point (Read 290 times)

with this script you can test some small range entirely and see how it goes.

46 is approximately. of course i cannot  know it exactly.
here is the code. you can test any secp256k1 range value.
the same will be with point operations.
p=120 # 2^120 here you set range
puzzle = 1231052970201832551532555186137109517 #value to test in p=range

pows = [2**0,2**1,2**2,2**3,2**4,2**5,2**6,2**7,2**8,2**9,
        2**10,2**11,2**12,2**13,2**14,2**15,2**16,2**17,2**18,2**19,
        2**20,2**21,2**22,2**23,2**24,2**25,2**26,2**27,2**28,2**29,
        2**30,2**31,2**32,2**33,2**34,2**35,2**36,2**37,2**38,2**39,
        2**40,2**41,2**42,2**43,2**44,2**45,2**46,2**47,2**48,2**49,
        2**50,2**51,2**52,2**53,2**54,2**55,2**56,2**57,2**58,2**59,
        2**60,2**61,2**62,2**63,2**64,2**65,2**66,2**67,2**68,2**69,
        2**70,2**71,2**72,2**73,2**74,2**75,2**76,2**77,2**78,2**79,
        2**80,2**81,2**82,2**83,2**84,2**85,2**86,2**87,2**88,2**89,
        2**90,2**91,2**92,2**93,2**94,2**95,2**96,2**97,2**98,2**99,
        2**100,2**101,2**102,2**103,2**104,2**105,2**106,2**107,2**108,2**109,
        2**110,2**111,2**112,2**113,2**114,2**115,2**116,2**117,2**118,2**119,
        2**120,2**121,2**122,2**123,2**124,2**125,2**126,2**127,2**128,2**129,
        2**130,2**131,2**132,2**133,2**134,2**135,2**136,2**137,2**138,2**139,
        2**140,2**141,2**142,2**143,2**144,2**145,2**146,2**147,2**148,2**149,
        2**150,2**151,2**152,2**153,2**154,2**155,2**156,2**157,2**158,2**159,
        2**160,2**161,2**162,2**163,2**164,2**165,2**166,2**167,2**168,2**169,
        2**170,2**171,2**172,2**173,2**174,2**175,2**176,2**177,2**178,2**179,
        2**180,2**181,2**182,2**183,2**184,2**185,2**186,2**187,2**188,2**189,
        2**190,2**191,2**192,2**193,2**194,2**195,2**196,2**197,2**198,2**199,
        2**200,2**201,2**202,2**203,2**204,2**205,2**206,2**207,2**208,2**209,
        2**210,2**211,2**212,2**213,2**214,2**215,2**216,2**217,2**218,2**219,
        2**220,2**221,2**222,2**223,2**224,2**225,2**226,2**227,2**228,2**229,
        2**230,2**231,2**232,2**233,2**234,2**235,2**236,2**237,2**238,2**239,
        2**240,2**241,2**242,2**243,2**244,2**245,2**246,2**247,2**248,2**249,
        2**250,2**251,2**252,2**253,2**254,2**255,2**256]

pattern = []
p = 120
puzzle = 1231052970201832551532555186137109517
print(f'Puzzle: {puzzle}')
p = p - 1
act1 = puzzle - pows[p]
print(f'{puzzle} - {pows[p]} = {act1}')
p = p - 1
counter = 0
while p > 0:
    if act1 < pows[p]:
        p = p - 1
        continue
    else:
        counter += 1
        save = act1
        act1 -= pows[p]
        print(f'{counter}: {save} - {pows[p]} = {act1} power=[{p}]')
        pattern.append(p)
        p = p - 1
s = ''
for p in pattern:
    s += 'p' + str(p) + ','
print(s)

guess anyone with coding skills can do it from this explanation alone.
it will require good knowledge of combinatorics in order to try it. There are other methods similar to this. Our imagination and knowledge is the limit.

That is quite correct. The only thing this method shows that you can determine whether point is even or odd without calculating its scalar.
There might well be some other ways to do it.
One interesting scheme is using powers of two.
For example:
1086 - 1024 = 62
62 - 32 =30
30 - 16 = 14
14 - 8 = 6
6 - 4 = 2

the lower range value we subtract first. then goes the sequence of powers of 2 that we subtract from results of previous calculations: 32,16,8,4
for every point there will be a sequence down like that. the problem is that powers of 2 do not come one by one. at least for the points of our interest.
but for every point in every range will be a unique sequence. we can catch lower ranges with bloomfilter.
knowing that sequence and the last result we can calculate the privkey easily.

2 + 4 = 6
6 + 8 = 14
14 + 16 = 30
30 + 32 = 62
62 + 1024 = 1086

here you only need to know the range where point is and find the right sequence of powers of 2 down.
This method also computationally quite hard. for example for puzzle #120 the sequence will  be around 46 values if you put lower 2^30 in bloomfilter.

Ok maybe I understand.
46 is the average length of the power of 2 sequence? that's right?

Alexander, can u explain how you arrive to a sequence of 46 values of power of 2 with a bloomfilter of size 2^30 for puzzle 120?
Thanks

Yeah, except the points are in random order so you have no way of knowing how far from the median the point is - which would imply that the computation would be faster.

This is still going to be prohibitively expensive for large N. It is O(n). Any method with a runtime greater than O(log N) is not going to be practical in cryptography.

How can knowledge of an even or odd point help in hacking secp256k1?

So, to test number N you need N+2 add/sub operations.
Isn't it easier to just iterate over all the points from 1 to N?

A-one.