Public Key Division - Number Theore

[GR Sasa]

Hi,

We all (hopefully) have heard about the current ongoing-puzzle that was recently increased its prize by 10x and which is still not all solved for long time.

Since I'm very interesting in math and dealing with big numbers, I would love to get to learn about dividing public keys. I will mainly focus for the next possible puzzle (#125) which has its public key revealed.

Puzzle #125:

Code:

0233709eb11e0d4439a729f21c2c443dedb727528229713f0065721ba8fa46f00e

Since public key for puzzle #125 is revealed, we can do many things with it so we can try to slightly reduce the targeted range by XXX amount.

I already know Addition, Subtraction, and striding public keys, but weirdly i haven't managed to know how to divide public keys in the correct way.

Can you help me give me an detailed example of dividing public key into lower ranges, and if possible which tools is needed for the process?

What could be the advantages and disadvantages of dividing public keys? Is it a problem if the divided public key has a decimal in it? I think if i understood correctly, the newly divided keys could be invalid and could lead to infinity if its wrongly divided (Correct me, if I'm wrong).

Thanks to all, and Goodluck hunting!

[1714696563]

1714696563

[1714696563]

1714696563

[1714696563]

1714696563

[1714696563]

1714696563

[digaran]

Multiply your public key by this key
7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
Key above is N/2, or 0.5 and if you for example multiply 4 by 0.5 you'd get 2, this is a simple operation.
There is also a java calculator on github, https://github.com/MrMaxweII/Secp256k1-Calculator
You can put public key and select division then put 2 and divide or any other number you like.

About dividing you should know, every single even public key has an odd pair we call it inverse key, aka 02 and 03.

If the pub key starts with 02 and it's private key ends with 1, 3, 5, 7, 9 the inverse key must end with 2, 4, 6, 8, 0.

Now let us practice :

Our target pub key :
03f42cde25a364c9764a4c60f762337c0a1a9d27805c89b59bc845e18a93db4ac9

It's private key :
00000000000000000000000000000000000000002880422a1ab3e513482869b2
 Decimal ( 12534455350639729112533985714 ) ends with 4 so it is even.

Inverse pub key :
02f42cde25a364c9764a4c60f762337c0a1a9d27805c89b59bc845e18a93db4ac9

It's private key :
fffffffffffffffffffffffffffffffebaaedce686c85e11a51e7979880dd78f
Decimal (  115792089237316195423570985008687907852837564279062369927254523412405627508623  ) ends with 3 so it is odd.

Now it doesn't matter which one of the pub keys you are dividing, it will divide the even one because there is no fraction in ECC.

If we divide our target pub by 2 we will see :
0312d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Private key :
0000000000000000000000000000000000000000144021150d59f289a41434d9
Decimal (  6267227675319864556266992857  )
Inverse pub :
0212d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Private key :
fffffffffffffffffffffffffffffffebaaedce69b087f26b2786c032c220c68
Decimal (  115792089237316195423570985008687907852837564279068637154929843276961894501480  )

Then if you try to divide this
0312d8734901f0f88e3b396c4fa66454543cd8837bbb31ea177cc19b99a8a79ed1
Or the -n aka 02 version of it, doesn't matter which one since both will give you the same result which is :
0222db101c46b9d0f52e30f1be2565c67a9e75d3104fda0b75fcbec3fae320b88d
Private key :
7fffffffffffffffffffffffffffffff5d576e734d843f93593c360196110634
Decimal (  57896044618658097711785492504343953926418782139534318577464921638480947250740  )
Inverse key :
0322db101c46b9d0f52e30f1be2565c67a9e75d3104fda0b75fcbec3fae320b88d
Private key :
7fffffffffffffffffffffffffffffff5d576e7361c460a86696288b3a253b0d
Decimal (  57896044618658097711785492504343953926418782139540585805140241503037214243597  )

So, tell me, are we close to our target or did we just distanced ourselves from target by 2^255 difference? If you had more questions, happy to answer if I know the answer.😉

[GR Sasa]

Thanks for your answer,

Why do you divide by 2 though? Why not like 1000 or any larger number? (for more reducing). Seems dividing is just as complicated as bruteforcing a whole key. It can reduce range, but it can mess it up also. And what if a PubKey is a prime? Lol then, there is no way to divide it, correct?

[vjudeu]

Why do you divide by 2 though?

You can multiply or divide by any number, it doesn't matter.

Why not like 1000 or any larger number? (for more reducing).

You won't reduce anything by using division. You are in a finite field, so you can always divide your key by any number, and you will always reach a valid result. If you have 1234 as your key, and divide it by 1000, you will get "1.234" key, so you will end up in fractions, just they will be expressed as large, 256-bit numbers.

And what if a PubKey is a prime?

It doesn't matter. You can divide a key equal to 31337 by 127, and then you will just get a fraction 31337/127, expressed as some 256-bit number.

Lol then, there is no way to divide it, correct?

For each and every key, you can multiply or divide it by any other key, in the whole range from 1 to N-1, and you will always get some valid key as a result.

[GR Sasa]

Wouldn't it possible to reduce 120 bits to 100 bits?

For the targeted public key below: 0233709eb11e0d4439a729f21c2c443dedb727528229713f0065721ba8fa46f00e

[garlonicon]

Wouldn't it possible to reduce 120 bits to 100 bits?

You can generate 2^20 keys, based on some 120-bit key, and then one of them will have only 100 bits. But you won't know which one, and you will have to check all of them, so it won't solve anything.

[GR Sasa]

Thanks for answer everyone,

After doing researches, I found a decent ecctools that does public key math made and developed by Alberto

https://github.com/albertobsd/ecctools

However, it's made for ubuntu, and i have Windows operating system. Can anyone help me compile the tools for windows?

I'll be grateful

Thanks

[NotATether]

Thanks for answer everyone,

After doing researches, I found a decent ecctools that does public key math made and developed by Alberto

https://github.com/albertobsd/ecctools

However, it's made for ubuntu, and i have Windows operating system. Can anyone help me compile the tools for windows?

I'll be grateful

Thanks

Use MinGW software to create a Unix build environment in Windows, and run it from there. It doesn't have any external dependencies.

Thanks for your answer,

Why do you divide by 2 though? Why not like 1000 or any larger number? (for more reducing). Seems dividing is just as complicated as bruteforcing a whole key. It can reduce range, but it can mess it up also.

It's like having a spectrum of a numerical range that extremes from 0 to your maximum value 2^N.

0 |----------------| 2^N

Division cuts that spectrum into two lengths, so that there are 2^(N-M) keys remaining on the left, and then on the right there are 2^M possible remainders there may be that should be tried for each of the keys on the left.

               2^(M-N)
0 |-----------|----| 2^N

Since reminders have to be tried for all remaining keys, the total search space is these two values multiplied together: 2^M * 2^(N-M) = 2^(M+N-M) = 2^N. Exactly the same range as before.

So no, key division does not decrease search time.

[digaran]

So no, key division does not decrease search time.

Isn't kangaroo doing division to decrease the search time? As long as you are dividing +n key, you can even reach G itself.

Thanks for your answer,

Why do you divide by 2 though? Why not like 1000 or any larger number? (for more reducing). Seems dividing is just as complicated as bruteforcing a whole key. It can reduce range, but it can mess it up also. And what if a PubKey is a prime? Lol then, there is no way to divide it, correct?

Since you don't know anything about the private key, the easiest way is to guess the last digit and if it's even, at least you can divide by 2 for sure.
And if you are dealing with prime numbers, look at N of secp256k1, if you just subtract 1 from it you can divide it by dozens of already known divisor numbers.
Anyways for now the puzzle #125 has been solved, it's  time to focus on the next one #130, we'd either find it or die trying, right? 🤣

[GR Sasa]

So no, key division does not decrease search time.

And if you are dealing with prime numbers, look at N of secp256k1, if you just subtract 1 from it you can divide it by dozens of already known divisor numbers.

Hmm, i dont know if i agree with this statement. When you create 1 million key with the help of subtracting the public key, You have like created a million clones of the targeted public key, and with that, you increase the chance. When you find 1 of the 1 million pubkey, you get back to the original key. So the chances is higher. And so is very similar to dividing.

@digaran, you are fucking smart with coming up with this idea, but it still wont help us a lot finding the targeted priviate key.

Teach me more tips like that though!  

[digaran]

So no, key division does not decrease search time.

Hmm, i dont know if i agree with this statement. When you create 1 million key with the help of subtracting the public key, You have like created a million clones of the targeted public key, and with that, you increase the chance. When you find 1 of the 1 million pubkey, you get back to the original key. So the chances is higher. And so is very similar to dividing.

And if you are dealing with prime numbers, look at N of secp256k1, if you just subtract 1 from it you can divide it by dozens of already known divisor numbers.

@digaran, you are fucking smart with coming up with this idea, but it still wont help us a lot finding the targeted priviate key.

Teach me more tips like that though!  

Took me 4 mins to correct the quotes you misplaced lol.
I'm the last person you'd want to teach you something, I just share what I know, they might be incorrect sometimes.

What you need to know about public keys, ignore their size and char length, it's all smoke and mirrors, they are simply representations of private keys, and private keys are simply ordinary numbers but very big ones.

Hexadecimal keys can make our work easier, for instance, if you have a large number like 3637343230303931363537383831353435
By the time you can figure out how to extract a certain number out of that, you'd be spending a few minutes, but if you convert to hex  you will get this
b355b9d94ef43E58a7f80fe3b85b

And in seconds I can select my target and then by guess work I'd take b as my first char assuming we know the first char is b, so I'd go with b000000000000E00000000000000  then I subtract from target to get
355b9d94ef43058a7f80fe3b85b
Then I go with this
bffffffffffffeffffffffffffff  subtracting target from it to reach
caa4626b10bc0a75807f01c47a4  and then I add the last result to this  +  355b9d94ef43058a7f80fe3b85b to reach =
ffffffffffff0ffffffffffffff
And just like that I now know the E I guessed is really there otherwise I'd see something else instead of 0 in the middle of fs  =  ffffffffffff0ffffffffffffff . 😉

Fun fact, 99% of times when I share something I know with others, I learn something new then and later on, this is why we need to share our knowledge, we gain more than we already have by sharing.

[GR Sasa]

@digaran i didn't understand anything you wrote here, but could you please help me at least compile the ecctools that Alberto wrote? I will be greatful

I want to do some mathematics, maybe i can get near to #130

[digaran]

@digaran i didn't understand anything you wrote here, but could you please help me at least compile the ecctools that Alberto wrote? I will be greatful

I want to do some mathematics, maybe i can get near to #130

I guess I was speaking arabic right? 😅 that is math right there, follow up on it to get some where.

About compiling, I'm the worst person to ask, because I have the same problem as you, when I for example open visual studio  it's like an alien world to me. In case you didn't know, I used WP's ready to use for windows tools.

[GR Sasa]

I guess I was speaking arabic right? 😅 that is math right there, follow up on it to get some where.

About compiling, I'm the worst person to ask, because I have the same problem as you, when I for example open visual studio  it's like an alien world to me. In case you didn't know, I used WP's ready to use for windows tools.

Nono, you werent speaking arabic. You just explain a lot of good things but the way you explain them, nobody but einstein could understand it.
Your examples are good, but as i said the way you explain things are catastrophic.

Thank you for nothing. We probably need help of Wandering around the jungle, i think he is the only and other few who can compile codes. I asked him but unfortunately he ignored me

[ripemdhash]

I have thought about this topic.

We ( I hope) we no need check all subranges.

here my experiment. at the moment without explanation. ok?  will do later.

but for setup :
- target pubkey
- control pubkey

Code:

private1 10101010101010
private2 20101050101010
0 81054462466121336796499689506081535496986294995352433067823614199163723147046 81054462466121336796499689506081535496986294995352433067823614199263723547046
0 diferential 100000400000 100000400000

1 19883490071054296183845522678259539732305440330750236106103916903191007631361 17544255945047908397510755304346652704975388527132561270091691385281550227435
1 diferential -2339234126006387786334767373912887027330051803617674836012225517909457403926 113452855111309807637236217634775020825507512475457229546592937623608704090411

2 73256219721567388941442868066720921294652336584720857874709388926369663497448 92161050617455747377944253374261804209401326671100434100440844133250180067952
2 diferential 18904830895888358436501385307540882914748990086379576225731455206880516570504 18904830895888358436501385307540882914748990086379576225731455206880516570504

3 5968664393676092547606751804571541641898843519539943524876554801213317706935 15518527423557840623777554691886008268936993150803853164679042483091104634303
3 diferential 9549863029881748076170802887314466627038149631263909639802487681877786927368 9549863029881748076170802887314466627038149631263909639802487681877786927368

4 16886346347108611832604101980433653228538811457365090222463252958243284073143 94081072505319408781651425319558925130430520976748359810866695052692892152701
4 diferential 77194726158210796949047323339125271901891709519383269588403442094449608079558 77194726158210796949047323339125271901891709519383269588403442094449608079558

5 30471602430872683006202890791759975750746727441861816942790832405769000499573 97509127778792585619849250533631922402389527813957814216930663698332147048926
5 diferential 67037525347919902613646359741871946651642800372095997274139831292563146549353 67037525347919902613646359741871946651642800372095997274139831292563146549353

6 2463661473134387136671723085291232081975267325086700093246918364820609926486 14781968838806322820030338511747392491851603950520200559481510188492755191841
6 diferential 12318307365671935683358615426456160409876336625433500466234591823672145265355 12318307365671935683358615426456160409876336625433500466234591823672145265355

7 32371981937314205172181135593826726926599749153289758214491766039672830203804 67234116331344887665299281617947817462937940549140267060867514082387976030056
7 diferential 34862134394030682493118146024121090536338191395850508846375748042715145826252 34862134394030682493118146024121090536338191395850508846375748042715145826252

8 72999360606134123201816490548955420168093247045503744067294559371936460617093 7551657993738012745015499022305733120837232452983145937995988900752282815946
8 diferential -65447702612396110456800991526649687047256014592520598129298570471184177801147 50344386624920084966769993482038220805581549686554306253306592670333983693190

9 78891313546303341936938473302622530625010208629699385403533188074551945304944 10179524328555269927346899780983552338710994661896694890778475880793915846766
9 diferential -68711789217748072009591573521638978286299213967802690512754712193758029458178 47080300019568123413979411487048929566538350311272213869850450947760132036159

10 102926301544281062598729764452167029202522279359177692784537922792572821440533 77194726158210796949047323339125271901891709519383269588403442094568785997347
10 diferential -25731575386070265649682441113041757300630569839794423196134480698004035443186 90060513851245929773888543895646150552206994439280481186470682443514126051151

11 71556909079240345486476451409863313841641191408417075742059370480826965081905 71556909079240345486476451409863313841641191408417075742059370480939325081905
11 diferential 112360000000 112360000000

12 7894915175271558778879839886955993717238924837209652571541261123400113398489 92107343711501519086931465347819926701120789767445946667981379771890594939825
12 diferential 84212428536229960308051625460863932983881864930236294096440118648490481541336 84212428536229960308051625460863932983881864930236294096440118648490481541336

13 102482653692797092501321446501942171318028648844698478591501121401229878680057 3992830663355730876674861552023720960442674630312927737331212522352362466483
13 diferential -98489823029441361624646584949918450357585974214385550854169908878877516213574 17302266207874833798924400058769457495251590064689353528435254262640645280763

14 105020732098961200500448102682298335029317790857765610951665147965680437286736 86170857106839959384983058611116582588158187370474347447520121407875155648123
14 diferential -18849874992121241115465044071181752441159603487291263504145026557805281638613 96942214245194954308105940937506155411677960791783640878460136583712879855724

15 81735592402811432063697165888485582013767692432288167799485997511778714114838 102169490503514290079621457360606977517209615540360209749357496889811331319721
15 diferential 20433898100702858015924291472121395503441923108072041949871499378032617204883 20433898100702858015924291472121395503441923108072041949871499378032617204883

16 85465589675161953765016679411174408177094392682174334187160953747431274080356 107521225720365038607601628936638771577634881116283839783847651488791876745944
16 diferential 22055636045203084842584949525464363400540488434109505596686697741360602665588 22055636045203084842584949525464363400540488434109505596686697741360602665588

17 73939526862382630812641713318800712243378203696276746172024983692898356256637 22321366599964567792495611567939837658378325644159017712309429039570983542294
17 diferential -51618160262418063020146101750860874584999878052117728459715554653327372714343 64173928974898132403424883257827033267837686226957175922889608488190788779994

18 98846905446489435117682548178148214020714993896771259838809285608736247740300 59308143267893661070609528906888928412428996338062755903285571365412973571502
18 diferential -39538762178595774047073019271259285608285997558708503935523714243323274168798 76253327058720421376497965737428622244551566720366400447081448898194887325539

19 88630981885353137237795074944921608479949740559291902120018766849187987935184 8577191795356755216560813704347252433543523279931474398711493566286543445272
19 diferential -80053790089996382021234261240574356046406217279360427721307273282901444489912 35738299147319813402336723768113551806431346999714476661297889858616717004425

20 43422033463993573283839119378257965444814086604653089143476936178195573186639 43422033463993573283839119378257965444814086604653089143476936178320573686639
20 diferential 125000500000 125000500000

21 17588671782883472722567744558281707521950009763910112058117239970991379089026 95271972157285477247241949690692582410562552887846440314801716509098500597885
21 diferential 77683300374402004524674205132410874888612543123936328256684476538107121508859 77683300374402004524674205132410874888612543123936328256684476538107121508859

22 92039865804020565593094885519726285729178576734649282970788719420310602855768 89070837874858611864285373083606082963721203291596080294311663955271676150785
22 diferential -2969027929161953728809512436120202765457373443053202676477055465038926704983 112823061308154241694761472572567705087380190836021701706128107676479234789354

23 9022760200310352890148388442235421391130199813953888653190012712457272455416 22556900500775882225370971105588553477825499534884721632975031781076278863845
23 diferential 13534140300465529335222582663353132086695299720930832979785019068619006408429 13534140300465529335222582663353132086695299720930832979785019068619006408429

24 9141480729261804901860867237527992725224018232558545082837249721831710250882 63990365104832634313026070662695949076568127627909815579860748052156103063989
24 diferential 54848884375570829411165203425167956351344109395351270497023498330324392813107 54848884375570829411165203425167956351344109395351270497023498330324392813107

25 30877890463284318779618929335650108760756683807753307835361376837872856533170 69475253542389717254142591005212744711702538567444942629563097885178910897949
25 diferential 38597363079105398474523661669562635950945854759691634794201721047306054364779 38597363079105398474523661669562635950945854759691634794201721047306054364779

26 87626445909320364104323988655223281618363562157137765478728231566690784510593 62590318506657402931659991896588058298831115826526975341948736833524696079385
26 diferential -25036127402662961172663996758635223319532446330610790136779494733166088431208 90755961834653234250906988250052684533305117948464114245825668408352073063129

27 19034316039010881439491120823345957455260969470532860994400848735730396548398 109447317224312568277073944734239255367750574455563950717804880229929509496031
27 diferential 90413001185301686837582823910893297912489604985031089723404031494199112947633 90413001185301686837582823910893297912489604985031089723404031494199112947633

28 99709854621022279392519459313036809539943458129203389885021112705336486427082 9649340769776349618630915417390658987736463689922908698550430262072361375931
28 diferential -90060513851245929773888543895646150552206994439280481186470682443264125051151 25731575386070265649682441113041757300630569839794423196134480698254036443186

29 112530340244715739214456309374640361152757632890931949329574031785561326101553 75020226829810492809637539583093574101838421927287966219716021190562485617472
29 diferential -37510113414905246404818769791546787050919210963643983109858010594998840484081 78281975822410949018752215217141120801918353315430921272747152546519321010256

30 33083454067804627263877424288196545100810732651164258395030046612006631999825 82708635169511568159693560720491362752026831627910645987575116529942987497398
30 diferential 49625181101706940895816136432294817651216098976746387592545069917936355497573 49625181101706940895816136432294817651216098976746387592545069917936355497573

31 58735117729073432461231659062377924273178474634313357295524358115409226991345 10068877324984016993353998696407644161116309937310861250661318534336377087928
31 diferential -48666240404089415467877660365970280112062164697002496044863039581072849903417 67125848833226779955693324642717627740775399582072408337742123560445311590920

32 44273445884856192367835964856263023590790833400822757558054915318964311896379 98763840820063813743634075448586744933302628355681536091045580326884623776067
32 diferential 54490394935207621375798110592323721342511794954858778532990665007920311879688 54490394935207621375798110592323721342511794954858778532990665007920311879688

33 67401365376945248082377140527445200093442761296774944342113453172079243408659 24195361930185473670596922240621353879697401491149980020245854985094855388384
33 diferential -43206003446759774411780218286823846213745359805624964321867598186984388020275 72586085790556421011790766721864061639092204473449940060737564954533773474062

34 87721279725239541987553776521733263524876942635662806350458456925545592194210 84212428536229960308051625460863932983881864930236294096440118648681406088321
34 diferential -3508851189009581679502151060869330540995077705426512254018338276864186105889 112283238048306613744068833947818577311842486573648392128586824864653975388448

35 17814167574971722372857074616721216592744240658319216058862332791158194231452 106885005449830334237142447700327299556465443949915296353173996746326011380942
35 diferential 89070837874858611864285373083606082963721203291596080294311663955167817149490 89070837874858611864285373083606082963721203291596080294311663955167817149490

36 83225564139321015460691645474994433769226999325585087524997461008124006856883 83225564139321015460691645474994433769226999325585087524997461008280257481883
36 diferential 156250625000 156250625000

37 113954119566882605020022239214899210902792523576232445582881271663241698773808 27569545056503856053231186906830454250675610542636881995858372176871007500255
37 diferential -86384574510378748966791052308068756652116913033595563587022899486370691273553 29407514726937446456779932700619151200720651245479340795582263655147470220784

38 48557972905971307758271703390740090389899623729934637321737649059509245305706 100851174497017331497948922426921726194406910823710400591301271123581964045084
38 diferential 52293201591046023739677219036181635804507287093775763269563622064072718739378 52293201591046023739677219036181635804507287093775763269563622064072718739378

39 75929238844141767490866219677828136296942665101032724185314861076570942129090 87318624670763032614496152629502356741484064866187632813112090238195679980992
39 diferential 11389385826621265123629932951674220444541399765154908627797229161624737851902 11389385826621265123629932951674220444541399765154908627797229161624737851902

40 96493407697763496186309154173906589877364636899229086985504302618100151413631 57896044618658097711785492504343953926418782139537452191302581571094098248852
40 diferential -38597363079105398474523661669562635950945854759691634794201721047006053164779 77194726158210796949047323339125271901891709519383269588403442094512108329558

41 102054044751532918000435444414436800141483954957828729286363872599475345895026 78503111347333013846488803395720615493449196121406714835664517384420805252110
41 diferential -23550933404199904153946641018716184648034758836422014450699355215054540642916 92241155833116291269624343989971723204802805442652889931905807926463620851421

42 95827935920537541040196677248569303050624191127510265695949100531085737272917 63885290613691694026797784832379535367082794085006843797299400354287624446893
42 diferential -31942645306845847013398892416189767683541397042503421898649700176798112826024 83849443930470348410172092592498140169296167236571482483955462964720048668313

43 89383367130559870151528479655829262202190400496127996365519775056787721330734 85320486806443512417368094216927932102090836837213087439814330736208137418652
43 diferential -4062880324116357734160385438901330100099563658914908925705444320579583912082 111729208913199837689410599569786577752738000620159995456899718820938577582255

44 12406295275426735223954034108073704412804024744186596898136267479628749626197 45489749343231362487831458396270249513614757395350855293166314091669653624579
44 diferential 33083454067804627263877424288196545100810732651164258395030046612040903998382 33083454067804627263877424288196545100810732651164258395030046612040903998382

45 105265535670287450385064531826079916229852331162795367620550148310654710633052 31579660701086235115519359547823974868955699348838610286165044493506790409383
45 diferential -73685874969201215269545172278255941360896631813956757334385103817147920223669 42106214268114980154025812730431966491940932465118147048220059324370241270668

46 17154383590713510433121627408694504867087046559862948797422987132263820408439 12865787693035132824841220556520878650315284919897211598067240349429815167908
46 diferential -4288595897678377608280406852173626216771761639965737199355746782834005240531 111503493339637817815290578156514281636065802639109167183249416358684156253806

47 48064640815489741496576635286625169297404271964899016913534218662707557792008 48064640815489741496576635286625169297404271964899016913534218662896237792008
47 diferential 188680000000 188680000000

48 22267709468714652966071343270901520740930300822899020073577915988947742789315 75710212193629820084642567121065170519163022797856668250164914362148433479009
48 diferential 53442502724915167118571223850163649778232721974957648176586998373200690689694 53442502724915167118571223850163649778232721974957648176586998373200690689694

49 59031261179808256490447953141684031454387777867763676744073220425285749195172 54490394935207621375798110592323721342511794954858778532990665008167390705198
49 diferential -4540866244600635114649842549360310111875982912904898211082555417118358489974 111251222992715560308921142459327597740961581366170006171522607724399803004363

50 46316835694926478169428394003475163141135025711629961753042065256809284799755 46316835694926478169428394003475163141135025711629961753042065257009285599755
50 diferential 200000800000 200000800000

51 30720350205818582459314751124753934736467108890366811366813614711221165500559 68530011997595299332317521739835700565965089063125963818276525124982198641567
51 diferential 37809661791776716873002770615081765829497980172759152451462910413761033141008 37809661791776716873002770615081765829497980172759152451462910413761033141008

52 33772692694217223665208203960867306457077622914730180444926505916486568146286 72370055773322622139731865630429942408023477674421815239128226963867622811065
52 diferential 38597363079105398474523661669562635950945854759691634794201721047381054664779 38597363079105398474523661669562635950945854759691634794201721047381054664779

53 4927322946268774273343446170582464163950534650173400186493836729641219852972 29563937677612645640060677023494784983703207901040401118963020376985510383682
53 diferential 24636614731343871366717230852912320819752673250867000932469183647344290530710 24636614731343871366717230852912320819752673250867000932469183647344290530710

54 30206631974952050980061996089222932483348929811932583751983955602354759739849 15103315987476025490030998044611466241674464905966291875991977801504565631892
54 diferential -15103315987476025490030998044611466241674464905966291875991977800850194107957 100688773249840169933539986964076441611163099373108612506613185340667967386380

55 90060513851245929773888543895646150552206994439280481186470682443627481386729 38597363079105398474523661669562635950945854759691634794201721047619410500357
55 diferential -51463150772140531299364882226083514601261139679588846392268961396008070886372 64328938465175664124206102782604393251576424599486057990336201745510090607965

56 15789830350543117557759679773911987434477849674419305143082522246800226796978 68422598185686842750291945686951945549404015255816988953357596402263028385313
56 diferential 52632767835143725192532265913039958114926165581397683810275074155462801588335 52632767835143725192532265913039958114926165581397683810275074155462801588335

57 94249374960606205577325220355908762205798017436456317520725132789842713079135 56549624976363723346395132213545257323478810461873790512435079674232149801909
57 diferential -37699749984242482230930088142363504882319206974582527008290053115610563277226 78092339253073713192640896866324402970518357304492377374315110025907598217111

58 55139090113007712106462373813660908501351221085273763991716744353344386666375 99250362203413881791632272864589635302432197953492775185090139836065591997551
58 diferential 44111272090406169685169899050928726801080976868219011193373395482721205331176 44111272090406169685169899050928726801080976868219011193373395482721205331176

59 81901721655662674811794111347608520188592423514467615295013408075954333986263 2824197298471126717648072805089948972020428397050607423965979589307785648667
59 diferential -79077524357191548094146038542518571216571995117417007871047428486646548337596 36714564880124647329424946466169336636265569161657896511557734654871613156741

60 86844066927987146567678238756515930889628173209306178286953872356391146373278 86844066927987146567678238756515930889628173209306178286953872356641147373278
60 diferential 250001000000 250001000000

61 68287642370724935762618786030764663605519589190223661558972275699103044217199 62349586512401028304999761158524258074604842304117256206018164769025190807233
61 diferential -5938055858323907457619024872240405530914746886106405352954110930077853409966 109854033378992287965951960136447502321922817392968499029651052211440308084371

62 18282961458523609803721734475055985450448036465117090165674499443663420501764 12188640972349073202481156316703990300298690976744726777116332962794044633641
62 diferential -6094320486174536601240578158351995150149345488372363388558166480869375868123 109697768751141658822330406850335912702688218790702540994046996660648785626214

63 59460802581324532785076992301758655383889560035200626574851299991863407526849 9388547775998610439748998784488208744824667373979046301292310525531230664433
63 diferential -50072254805325922345327993517270446639064892661221580273558989466332176862416 65719834431990273078242991491417461213772671617853324109046173675185984631921

64 83627620004728363361467933617385711227049351979331875387437062269154811359827 19298681539552699237261830834781317975472927379845817397100860524144722751862
64 diferential -64328938465175664124206102782604393251576424599486057990336201745010088607965 51463150772140531299364882226083514601261139679588846392268961396508072886372

65 66166908135609254527754848576393090201621465302328516790060093224013263999650 49625181101706940895816136432294817651216098976746387592545069918367813500459
65 diferential -16541727033902313631938712144098272550405366325582129197515023305645450499191 99250362203413881791632272864589635302432197953492775185090139835872710995146

66 88546891769712384735671929712526047181581666801645515116109830637928623792758 81735592402811432063697165888485582013767692432288167799485997512251086057797
66 diferential -6811299366900952671974763824040465167813974369357347316623833125677537734961 108980789870415242751596221184647442685023589909717557065981330015840623759376

67 59650470213162888551536568034778619196916320992250708318311750709573022894083 52632767835143725192532265913039958114926165581397683810275074155844650682305
67 diferential -7017702378019163359004302121738661081990155410853024508036676553728372211778 108774386859297032064566682886949246770847408868221879874568486587789789282559

68 50659039041325835497812305941300959685616434372095270667389758874729852219429 50659039041325835497812305941300959685616434372095270667389758875042353469429
68 diferential 312501250000 312501250000

69 97115945811942615516543406781480180779799247459869274643475298119018490611412 85910259756718467572326859845155544535976257368345896799997379105645766595831
69 diferential -11205686055224147944216546936324636243822990091523377843477919013372724015581 104586403182092047479354438072363271609014574187551526539127244128145437478756

70 77194726158210796949047323339125271901891709519383269588403442094682141332925 670035003367
70 diferential -77194726158210796949047323339125271901891709519383269588403442094012106329558 38597363079105398474523661669562635950945854759691634794201721047506055164779

71 75863782603758886656822369488450698248410817975945627009293037920653313051497 11978491990067192630024584656071162881328023890938783211993637567057087399449
71 diferential -63885290613691694026797784832379535367082794085006843797299400353596225652048 51906798623624501396773200176308372485754770194068060585305762787921935842289

72 24812590550853470447908068216147408825608049488373193796272534959257499252394 90979498686462724975662916792540499027229514790701710586332628183339307249158
72 diferential 66166908135609254527754848576393090201621465302328516790060093224081807996764 66166908135609254527754848576393090201621465302328516790060093224081807996764

73 34308767181427020866243254817389009734174093119725897594845974264527640816878 25731575386070265649682441113041757300630569839794423196134480698859630335816
73 diferential -8577191795356755216560813704347252433543523279931474398711493565668010481062 107214897441959440207010171304340655419294040999143429983893669575850151013275

74 44535418937429305932142686541803041481860601645798040147155831977895485578630 35628335149943444745714149233442433185488481316638432117724665582778705463681
74 diferential -8907083787485861186428537308360608296372120329159608029431166395116780114949 106885005449830334237142447700327299556465443949915296353173996746401381379388

75 92633671389852956338856788006950326282270051423259923506084130513618569599510 92633671389852956338856788006950326282270051423259923506084130514018571199510
75 diferential 400001600000 400001600000

76 67545385388434447330416407921734612914155245829460360889853011832973136292572 28948022309329048855892746252171976963209391069768726095651290786217084127793
76 diferential -38597363079105398474523661669562635950945854759691634794201721046756052164779 77194726158210796949047323339125271901891709519383269588403442094762109329558

77 60413263949904101960123992178445864966697859623865167503967911204709519479698 30206631974952050980061996089222932483348929811932583751983955603009131263784
77 diferential -30206631974952050980061996089222932483348929811932583751983955601700388215914 85585457262364144443508988919464975369488634467142320630621207539817773278423

78 31579660701086235115519359547823974868955699348838610286165044493600453593956 21053107134057490077012906365215983245970466232559073524110029663007895276289
78 diferential -10526553567028745038506453182607991622985233116279536762055014830592558317667 105265535670287450385064531826079916229852331162795367620550148310925603176670

79 110278180226015424212924747627321817002702442170547527983433488706688773332750 82708635169511568159693560720491362752026831627910645987575116530613022500765
79 diferential -27569545056503856053231186906830454250675610542636881995858372176075750831985 88222544180812339370339798101857453602161953736438022386746790965442410662352

80 57896044618658097711785492504343953926418782139537452191302581571264131252219 57896044618658097711785492504343953926418782139537452191302581571764133252219
80 diferential 500002000000 500002000000

81 36565922917047219607443468950111970900896072930234180331348998887326841003528 24377281944698146404962312633407980600597381953489453554232665925588089267282
81 diferential -12188640972349073202481156316703990300298690976744726777116332961738751736246 103603448264967122221089828691983917552538873302330177605488830179779409758091

82 51463150772140531299364882226083514601261139679588846392268961396791461225317 38597363079105398474523661669562635950945854759691634794201721048289445503724
82 diferential -12865787693035132824841220556520878650315284919897211598067240348502015721593 102926301544281062598729764452167029202522279359177692784537922793016145772744

83 61301694302108574047772874416364186510325769324216125849614498134339086091179 47679095568306668703823346768283256174697820585501431216366831882984010621257
83 diferential -13622598733801905343949527648080930335627948738714694633247666251355075469922 102169490503514290079621457360606977517209615540360209749357496890163086024415

84 101318078082651670995624611882601919371232868744190541334779517749459704438858 101318078082651670995624611882601919371232868744190541334779517750084706938858
84 diferential 625002500000 625002500000

85 38597363079105398474523661669562635950945854759691634794201721047846121171513 1340070006734
85 diferential -38597363079105398474523661669562635950945854759691634794201721046506051164779 77194726158210796949047323339125271901891709519383269588403442095012110329558

86 49625181101706940895816136432294817651216098976746387592545069918514998504788 66166908135609254527754848576393090201621465302328516790060093225160453003979
86 diferential 16541727033902313631938712144098272550405366325582129197515023306645454499191 16541727033902313631938712144098272550405366325582129197515023306645454499191

87 89070837874858611864285373083606082963721203291596080294311663955790971157260 71256670299886889491428298466884866370976962633276864235449331165557410927362
87 diferential -17814167574971722372857074616721216592744240658319216058862332790233560229898 97977921662344473050713910391966691260093323620755688323742830351284601264439

88 19298681539552699237261830834781317975472927379845817397100860524428111090807 57896044618658097711785492504343953926418782139537452191302581572434168255586
88 diferential 38597363079105398474523661669562635950945854759691634794201721048006057164779 38597363079105398474523661669562635950945854759691634794201721048006057164779

89 63159321402172470231038719095647949737911398697677220572330088987200907187912 42106214268114980154025812730431966491940932465118147048220059326015790552578
89 diferential -21053107134057490077012906365215983245970466232559073524110029661185116635334 94738982103258705346558078643471924606867098046515830858495133480333044859003

90 1010101010101 2010105010101
90 diferential 1000004000000 1000004000000

91 102926301544281062598729764452167029202522279359177692784537922793582922450634 77194726158210796949047323339125271901891709519383269588403442096578891007448
91 diferential -25731575386070265649682441113041757300630569839794423196134480697004031443186 90060513851245929773888543895646150552206994439280481186470682444514130051151

92 86844066927987146567678238756515930889628173209306178286953872357401247383379 86844066927987146567678238756515930889628173209306178286953872358651252383379
92 diferential 1250005000000 1250005000000

93 99250362203413881791632272864589635302432197953492775185090139837029997009576 16541727033902313631938712144098272550405366325582129197515023308802744513621
93 diferential -82708635169511568159693560720491362752026831627910645987575116528227252495955 33083454067804627263877424288196545100810732651164258395030046613290908998382

94 38597363079105398474523661669562635950945854759691634794201721048856222181614 3350175016835
94 diferential -38597363079105398474523661669562635950945854759691634794201721045506047164779 77194726158210796949047323339125271901891709519383269588403442096012114329558

95 2020202020202 4020210020202
95 diferential 2000008000000 2000008000000

96 57896044618658097711785492504343953926418782139537452191302581573284333272421 57896044618658097711785492504343953926418782139537452191302581575784343272421
96 diferential 2500010000000 2500010000000

97 77194726158210796949047323339125271901891709519383269588403442097712444363228 6700350033670
97 diferential -77194726158210796949047323339125271901891709519383269588403442091012094329558 38597363079105398474523661669562635950945854759691634794201721050506067164779

98 5050505050505 10050525050505
98 diferential 5000020000000 5000020000000

99 10101010101010 20101050101010
99 diferential 10000040000000 10000040000000

[NotATether]

@digaran i didn't understand anything you wrote here, but could you please help me at least compile the ecctools that Alberto wrote? I will be greatful

I believe there is a makefile for the ecctools at the top level of the repository.

Then again, it's been some time since I last checked it so it's possible that you compile the programs by running GCC directly. Each (?) of the programs are self-contained in a single file.

[GR Sasa]

Does dividing a public key by a non division number really result in a random unknown point in the curve? Why is that though? For me, this makes no sense  :

[ertil]

Does dividing a public key by a non division number really result in a random unknown point in the curve?

Yes, of course. For that reason, ECDSA is secure, and simple tricks like "let's divide it" won't work.

Why is that though?

Because we are in finite field. And the beauty of finite fields is that they are, well, finite.

For me, this makes no sense

It makes perfect sense, if you know, how things are calculated.

In real numbers, you have things like sqrt(8). In finite fields, you have for example 18.

Code:

18*18=324
324=79*4+8
324 modulo 79=8

See? In finite fields, you can have "18" as a result of "sqrt(8)", and it is perfectly valid, because "18*18" gives you "8" in this field.

[digaran]

Does dividing a public key by a non division number really result in a random unknown point in the curve? Why is that though? For me, this makes no sense  :

The result is not random at all, did you even read my first post and other posts?

Let me give you a solution in order to successfully divide an odd key by 2, I have tried 4, 5, 6 etc, I couldn't get any meaningful result, I'm still learning.

Now the example, you could either add 1 or subtract 1 from your odd private (public key) key and then divide by 2 or you could simply divide the odd key by 2 add n/2 to the result, you will get the same result.

If your key is divisible  by 2, 4, 8 etc but the last digit is 1, you could reach key 0x3 by dividing by 2 adding n/2 and dividing the result again by 2 adding n/2 till you reach the lowest point.

Demonstration :

Private key :

Code:

0000000000000000000000000000000000000000000000000000000000008001

Public key :

Code:

03a3dd9bdf806a8c86fa43fd7c8af5fe3949b9244d46cfdf42aa716e3168f8e67b

Divided by 2, result:

Code:

024d2432b7f67a3b25fe7f6a52164f1bf0235d3f6ce00569f4fc954b823c7c7607

Adding n/2 to above
N/2 =

Code:

7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0

Result, private key :

Code:

0000000000000000000000000000000000000000000000000000000000004001

Result, public key :

Code:

03d7ec238cd058837f44315fb8db2134f01daea15c10320c9173e7d5f68ff2d9d0

And if you keep dividing you will eventually reach 0x3, dividing 3 by 2 will give you 0x2 then 1, and dividing 1 by 2 will give you half, aka n/2 and take a look at 0.5 = n/2, it is a number around 2^255.

Now to simplify it, imagine you have 23 as your odd key, dividing by 2 adding n/2 will give you 12, it's like adding 1 to 23 = 24/2 = 12. You have 2 options.

Furthermore, there are ways to accurately divide your key by 2 without any division, but that rock is really big and I'm afraid the glass will shatter, you should start with small rocks, learn from Musk throwing a big rock at E-truck's window claiming it won't shatter. Lol

[garlonicon]

The result is not random at all, did you even read my first post and other posts?

Random in, random out. Unknown in, unknown out. Infinity in, infinity out. It is that simple. If you divide some public key, where you don't know the private key, the result is totally random from your perspective. It may be non-random for the key owner, but not for the attacker.

I have tried 4, 5, 6 etc, I couldn't get any meaningful result, I'm still learning.

Just use inversion:

Code:

   n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
 n/2=7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1
-n/2=7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
 n/4=bfffffffffffffffffffffffffffffff0c0325ad0376782ccfddc6e99c28b0f1
 n/5=66666666666666666666666666666665e445f1f5dfb6a67e4cba8c385348e6e7
 n/6=d5555555555555555555555555555554463c62c03cbc85871fd9f975582d3661

By the way, last time you messed up 1/2 with -1/2. This is a common mistake, been there, done that. If you learn more about inversion, you will know why. And if you want a proof, then halve a point using your method, and then double it. If you reach points, where 02 and 03 prefixes are inverted, you will understand, why you need inversion, instead of relying just on standard division, provided by any BigInteger implementation.

Furthermore, there are ways to accurately divide your key by 2 without any division, but that rock is really big and I'm afraid the glass will shatter

This problem is called "discrete logarithm", that's why you have DL letters in ECDLP. You can always divide a number by two, and finally reach the base point. The problem is: if you try to halve some point in a loop, you will visit a significant portion of the elliptic curve, I guess something above 2^250, maybe n/6 or something like that. So, don't run brute force on that, because you will never reach that answer in any reasonable time.