Topic: the dilemma of division in ECC-secp256k1 (Read 782 times)

pk_decimal= 109976111913671942994782547932288341104394192011282789345793555308339223784117
pub=03eeb9365c34d51c83060dd2fe898b8726143d86670c1f30e9cfc3d58f82973af9



pk is not for pub !

pub for pk is:

0495d913294063c97c009936a50efddbdabea78a91043c46fef15b5a93f2f9aa8b2e7234e4e7f81 467c5a06c85f2879c3e73f63f012185d313fb00a4d4041353f1

and

./km 0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 / 10000000000000000000000000000000000000000000000000000000000000000
Result: 03eeb9365c34d51c83060dd2fe898b8726143d86670c1f30e9cfc3d58f82973af9



0279b....  is a  pubkey of priv 1

this is precision, and mistake in this

1754225779965324 / 7476542256 =


234630.624679147670425471611218029341396662869339101612642580910198763945834375 0180765379733580415679255675432646147007879627504642568557964691318665637459349 09620070767643903


I not undertand what is your task. But if you get G as a 1/ 7476542256 you have no problem with find point

of
234630.624679147670425471611218029341396662869339101612642580910198763945834375 0180765379733580415679255675432646147007879627504642568557964691318665637459349 09620070767643903


Then you div point of  234630.624679147670425471611218029341396662869339101612642580910198763945834375 0180765379733580415679255675432646147007879627504642568557964691318665637459349 09620070767643903 to 1/ 7476542256 , you aways take int without float part.


ecctools of iceland is good for this calcs

It depends if something is long or short. For example, when I digged deeper into elliptic curves, I decided to not post all curves from the smallest to the 256-bit one, in some topic on bitcointalk. I decided to do that on GitHub, because it is too much content, and it is better to give someone a link, than to post all details on forum.

So, if you want to post something, that is too long to be posted here, then use other tools. Use pastebin, GitHub, or whatever, and just share a link. And if things are even more focused on your tools, then you can have some discussion in other places, for example on GitHub, inside some Pull Requests.

You know, bitcointalk is not your personal blog, and after reaching the point, where things are more related to your work, than to public discussions, it is usually a good idea to bring the whole discussion to your social media, and keep it there, leaving only links for someone, who may be interested, than posting everything here.

It is not a crime. If it would be, then all topics related to puzzles would be taken down, because they contain a lot of details about elliptic curves, and they are sometimes too long, but they stay on forum, and those topics are not taken down for some reason.

For example: this forum is not GitHub. If you have a long piece of code, then make your own repo, and give a link to that, instead of posting every file on bitcointalk. It is also more convenient to do "git clone" than to copy-paste each file manually.

Well, sometimes things are too stupid to continue the discussion. In that case, usually I leave it as it is, and switch to other things. And then, I come back, when I can analyze them peacefully, and reply to something that is worth it, and ignore the rest.

But yes, forum is for discussion, not for posting every code change you can think about. So yes, for example Core developers moved from forum to other places, not because they don't like the forum, but because other tools like GitHub are more convenient for their purposes.

Disclaimer, that noob Legends_Never_Die is my alt I wanted to use to ask things I didn't know, or forgot.

---

@mc, are you interested for more discoveries? You remember when we could divide by 47 and multiply by 34 to get results? Now try 474747 and 343434, interestingly you will get the same results, and can be used for large numbers. So you just need to find the right combination.

---

@mods, is it Ok to post in public about curve related stuff or do we need to do it privately? I believe in the spirit of transparency that's why I do everything here, if posting here is considered a crime or trolling, let me know so I stop.

Now I know why everyone left this forum.

decimal

python mod N


python div


1/10000000000000000000000000000000000000000000000000000000000000000 =
0.0000000000000000000000000000000000000000000000000000000000000001 =


pk_decimal= 109976111913671942994782547932288341104394192011282789345793555308339223784117
pub=03eeb9365c34d51c83060dd2fe898b8726143d86670c1f30e9cfc3d58f82973af9

You would only need a known decimal.

If you did this with divisions with decimals, for example, dividing by 2, at 0.5(N/2) you would know where to stop. Therefore you just have to find a large divisor that returns a known decimal.

But how in pubkeys you can separate float? how you know where is correct operation and where not? thats why i told that is usless with pubkeys

if you have for example:
target= 14688653357788537

and you want to divide by X:
X=3576434789998

target/X= 4107.0658967045645844960056238489

To reduce to decimals, you just have to subtract X and divide sequentially.

a=target-X   =14685076922998539

a.1= a/X      = 4106.0658967045645844960056238489

b=a-X          =14681500488208541

b.1= b/X      =4105.0658967045645844960056238489

If you continue sequentially you will arrive to

235675266751 / 3576434789998 =  0,0658967045645844960056238489

All results will get the same decimals, until negative (when target is less than X).

235675266751 -3576434789998 = -3340759523247

-3340759523247 / 3576434789998 = -0,93410329543541550399437615106299



Seeing the decimals is easy, but you must do it the way I explain, to reach the objective (in ecc with pubkeys).

But all this not suitable for pubkeys

I think he just got it out of his sleeves, after all cryptography is something which you could consider as magic if you know nothing about the math equations behind it, I thought there could be some actual magics involved at first, but now I just know it's not magic.
If you are interested to learn more about such divisions, first divide your target by any number, then divide 1 by the same number, and then keep multiplying the result of 1 being divided until you see a similar fraction as the fraction resulted from your first division.

Just a simple example,
97/5 = 19.4
1/5 = 0.2
0.2 * 2 = 0.4
0.4 - 19.4 = 19.

just mul rest to a divider

.8153570612637194174713249666 * 35789976533256789

I have came back to this thread and something confused me a little:

I have asked myself, how did @mcdouglasx came to this magic number, that when divided it results to the exact decimal value that the 3765.8153570612637194174713249666 had? I am not that newbie at math, but i really couldn't find it out, lol. Maybe I'm today not thinking good, i apologize.

Those keys are in decimal, you have to convert them to hex :
I wonder if you are really a puzzle hunter, what are you even doing btw, regarding solving a puzzle? I thought last year I told you to ask anything you want, but seems you rather stay idly by and let others claim the prize!

This is very nice example ! But i think there are some errors by your calculations. The "3765" Key doesnt represents the public key above, that you have mentioned. Or am i wrong?

Now here is the important part, how many keys will result in the fraction above when divided and by what? You could divide trillion trillion different numbers by trillion trillion other different numbers and get the same result. So that's not going to work, however there is something else to think about, have you started to divide by 2, 3, 4, 5 etc by iterating through different values? You can try dividing this  134778443257800664321  by e.g, 333, then add 1 to it and divide by 333, so if the last digit of your number is 1, try all from 0 to 9, then compare the hex representations mod n, after that change the second digit from right, do the same, you could also change all the digits one by one and then divide to see what big changes you can detect in the results.

For instance, when you divide by a 1 digit number, you will only notice the resulting hex changes it's starting character, which is obvious. Maybe the best thing to do is to divide n and focus on that, then subtract 1 at a time from n then keep dividing, you can only understand things when you see the results in hex, decimal won't be too much of help, unless your brain can handle it.

You can, but your results will be with exponential increase, if there is a trick it will probably be focused on decimals.
For example:




edit

Since you don't know the key you are dividing, you will only get public keys as results, so how can you guess if the result is correct or not? When you are using -1 divide by 2, there are 50-50 chances of each division to be correct because there are 5 odd and 5 even numbers.
For example, target = 99, now you sub 1 to get 98, then divide 98/2 = 49, 49-1 = 48/2 = 24, 24-1 = 23/2 = 11.5 game over.
Unless you do this 99/2 = 49.5, 98/2 = 49, now if you subtract 1 from 49.5 you won't get 48.5 in EC, you'd get half of n+48.  But your other division result which is 49, you can divide that as well as it's -1, which would be 49/2 = 24.5, 48/2 = 24, then you can continue with 24.5/2 = game over, 24-1 = 23/2 = 11.5 game over, 24/2 = 12. 12-1 = 11/2 = 5.5 game over, 12/2 = 6, 6-1 = 5/2 = 2.5 game over, 6/2 = 3, 3/2 = 1.5 game over, 3-1 = 2/2 = 0 you just won.

But can you detect which one of the results were game over or not when you are dividing a key in 2^130 key space without knowing the key? If you can do that, you win the game.😉

yes, for divide to 2 need sybsract 1,2 ana divide 2,2 one of pub will be without float

but this is real hard, most of time is waste of time, because needs divide 2**130  to 2**70 for get 2**60 pubkeya one of them will be 2**60 etc

How about we just try dividing the public key multiple times with multiple different numbers so in the end we can at least get a divided result of a new pubkey that is non float division?

34 give nothing

.72340 is a 34 /17

226918604442 - 226918604441 = 1  =( pbkey + any nummb ) - bupkey - n +1 = 1, so imposible to identity of axact divide without float part
=

The possibility of obtaining an integer from a division of two integers, in the best of cases is equal to the divisor, in your case 1/47 possibilities.

No, I mean that maybe with this:
PK = 3308345406780462726387424281965451008107326511642583950300466118623318555525
And with some type of formula we could somehow obtain the precise representation of the decimal
0.142857 .......
that reflects the same pub.


In this case it is not that they are really "unknown", the numbers are represented by the pubkeys, it is difficult to know how to identify them because it is as if we had a number system of (n ** 256-1)/2 digits with different symbols each number ( Difficult to memorize and smell with current technology), but that does not make them invisible.

On the contrary, if they were really "unknown", you would not know at the naked eye that number represents the following pub:

0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

Therefore you can use Math for known numbers.

You don't necessarily need to brute force all the possible values of n, you could figure things out another way, but the complexity could be much more, because when we are dealing with unknown numbers, we have to guess and try almost all the keys.

However sometimes there are some relations where we can use to our advantage, this is just an example:
I used 20 decimal precision for the following :

No fraction, if you want to know more about the possibilities, you have to do experiments with numbers. If you can do the same with other numbers, finding how many times you have to multiply n/x to reach the fraction for other numbers being divided, and if you can create a table of say 1 billion keys, then you could in theory divide many different keys by different numbers and start subtracting from them and you might find of the 1 billion keys while doing your subtraction like 4828055413.7234042553 if you have 0.7234042553 saved among the 1 billion keys, subtracting the bold part could solve a key when you land on 1/47 * 34, though this is just a demonstration.

I mean: your approach can be faster or slower. For example, it is widely known, that "one" is equal to "one half" plus "one quarter" plus "one eighth", and so on. Which means, you can use "one" directly, or you can use infinite point halving, and by using sum, you can "reach one".

Using inversion is a fast approach. You start for example from "7", and inversion can always transform any "x" into "1/x", so from "7", you can go directly into "1/7". But yes, technically, you can use decimal approach, and append 142857 each time. But in the same way, you can use "(1/2)+(1/4)+(1/8)+(1/16)+..." instead of simply using "one".

I wonder, what is your question. Maybe this one: "if it is so hard to get there, then how people can get there so fast?". If that is the thing you wanted to ask, then the answer is quite simple: they use inversion. Or some equivalent of inversion, without touching it directly. Which means, people don't try to append threes to reach "1/3". Instead, they simply divide "n" by "3", and they land in "almost there" area, and then tweak their results a little bit, to get where they want.
Guess what: people often use "-(1/3)" or "-(1/2)" instead of "(1/3)" and "(1/2)". Why? Because they simply do "n/number" instead of using inversion properly. And often they don't check what happens, if they multiply their result by "number". You can easily check that "my (1/3)" multiplied by 3, goes back to one. But "their -(1/3)" or "their -(1/2)" multiplied by 3 or 2 (respectively), goes back to "(-1)", instead of "one".

Do you mean that it is mandatory to use brute force when it is infinite in decimal? Even if we know the numbers?.

but what about:
1/3= 034c7ff4f2ba8603998339c8e42675ceac23ef2e9623fdb260b24b1c944a2ea1a9

Pk= 77194726158210796949047323339125271901891709519383269588403442094345440996225
pub= 034c7ff4f2ba8603998339c8e42675ceac23ef2e9623fdb260b24b1c944a2ea1a9

or

1/7=03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

pk=33083454067804627263877424288196545100810732651164258395030046611862331855525
pub=03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

You can use decimal. But the question is: are you ready for computing 2^256 public keys, or something around that? Because, as I said, this number has infinite expansion in decimal system. Which means, you will keep dividing by one million, and adding 142857. Until you reach that key. But it will take a lot of computations, probably more than breaking all keys used by all people since 2009. So, the question is: are you ready for a computation, which will take so much time and resources?

Also, again, you don't have to trust me. You can pick some ECC with lower n-value, and increase it gradually, to get a confirmation, that if some number has infinite expansion in a decimal system, then it will take a long time, to reach that public key, even if it is always finite in ECC. It is infinite in decimal, and that infinity is a huge problem, because it means, that you will need to check most of the keys to get there. So, are you ready to check all existing N public keys to get there?

but you are only dividing 1/1, 1/2...1/7.
You are not using decimal:

to get

03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

Of course, you gave me the script the first time, remember divide by range?
Here is what you want:

No one has been able to solve the mystery, maybe I haven't explained myself better.
do this in ecc, with pubkeys.



I suppose you already have the pubkey that corresponds "in theory" to this:

>>0.142857142857142857142857142857142857142857142857142857142857142857
>>03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

so now without using the pubkey obtained previously (therein lies the problem), try to find the same pubkey from these decimals
either multiplying, dividing or both operations.

There are some other possibilities as to why you get a different result, for example for educational purposes I use 77 decimal places whenever I am working with fractions, what does that mean?
E.g, if you divide a number and get 0.xxx, removing 0 and converting the fraction part to hex would give you 65 hex characters if you use 78 decimal precision, but using 77 decimal precision gives you a 256 bit number.

In your example:
Why would you try dividing? If it's a fraction, dividing won't work, you have to multiply, and if you multiply
Note the .5 in the result above converts to n/2 in EC. Any fraction number is like that, so .5 should go at the beginning, which means you have to subtract n/2 from the result to get your integer.

You are almost there. Note that if you have different fractions in different number systems, then in some of them, they may be infinite, but in others, they may be finite. In ECC, they are always finite. And that is probably the source of your confusion.

1/9 in decimal is just 0.(1). It is 0.11111...1. Ones are going to the infinity.
1/9 in hexadecimal is 0x0.(1c7). It is 0x0.1c71c71c7...1c7. This "1c7" part is always repeated.
1/9 in "nonal" (nine-based, just between "octal" and "decimal") is finite, and is simply 0.1. If you expand it in "nine-based" system, you will get "0.100000...0". Only zeroes are there, so you can use "0.1" instead, because trailing zeroes after comma can always be truncated.

So, what is preserved in all systems? The fractions, written in a "numerator/denominator" form. Which means, "1/9" in decimal is always the same as "0x1/0x9" in hexadecimal, and "1/10" in "nine-based" system.

Also, you may wonder, what does it mean that "In ECC, they are always finite". Well, you can also check it out.
So, what does it mean that "1/2" is always finite? Well, it simply means it is equal to 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1. Which means, some huge number is equal to "1/2". The same is true with things like square roots, cube roots, and so on. In ECC, "sqrt(2)" is also finite. Because, there is a number between 1 and N, which can be multiplied by itself, and when you can get "2" as a result of that operation.

Also, I can tell you exactly, what is the precision. Because it is not true that "they are not precise". I would rather say: "they always have some finite precision". And the precision is determined by, guess what: n-value. You can for example use some smaller ECC parameters, for example "p=79, n=67, base=(1,18)". And then, you can easily see that "1/2" is then equal to just "34". Then, by checking some properties on smaller numbers, it could help you to better understand, how much precision is there, if you start increasing those numbers, as I did there: https://bitcointalksearch.org/topic/smaller-elliptic-curves-y2-x37-based-on-secp256k1-5459153

I understand the whole part of using mod inverse ECC:
What worries me is that I am looking for a way to obtain the correct representation of floats in decimals.

if I divide
1/2=0.5
If I multiply by 10
I get pub 5
If I divide by 10
I go back to 0.5

but with big numbers
If I divide:
226918604445/7
in decimals
32416943492.14285714285714285714285714285714285714285714285714285714285714285
in ecc
0230719cfc1056f7b66637d5b0bf015e24d14c3f76a124aa8f1bb4a34f657cb80e

and I rest the entire part.
I get
in decimals
0.14285714285714285714285714285714285714285714285714285714285714285
at ECC
03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

but when I take those decimals without "0," (to take it as an integer
14285714285714285714285714285714285714285714285714285714285714285
generate the pub
02409309314806151f9a3ee457e83165639e45fe84b550fd003dd2fefca90263c8
and in ECC I divide by

10000000000000000000000000000000000000000000000000000000000000000

I don't get the same pub
03611a3775ff4f3e5acf0c371b5abe17d8d57b398710bd8b102597f5732b69d485

0.14285714285714285714285714285714285714285714285714285714285714285
get this
0356b4a41accf7d6631c2e2c50f5ded054df312f7dd7f6fad5b910227e038a0356

My conclusion is that these decimals are not precise.

0.14285714285714285714285714285714285714285714285714285714285714285

Just use inversion. I told that to many people, but some of them disagreed, and they are still using for example "n/2" instead of "(n+1)/2" as "1/2" or "0.5".

You don't have to trust me. You can multiply this number by 100000, and then you will see, that you will get 2356474256.

This is an exercise for you. Read the example above, and divide 864326889 by 1000000000. The whole algorithm is identical.

Edit: You are closer than you think. Because, guess what: 1/100 is just (1/10)*(1/10). Which means, you can easily get (1/10)^n, just by using multiplication, and then by applying one more multiplication, you can get 314*(1/100)=3.14. So, you are very close, the only missing puzzle is just going from "1/10" into "1/100", "1/1000", and so on.

I am looking for the representation of the floating numbers with respect to ecc, not how to extract the integer part.

example:

3/2= 1.5

where in ecc they are:
0.5=
57896044618658097711785492504343953926418782139537452191302581570759080747169
1.5= 57896044618658097711785492504343953926418782139537452191302581570759080747169 +1
2.5= 57896044618658097711785492504343953926418782139537452191302581570759080747169 +2

and so on.

I'm looking for how to calculate the equivalent of, for example, 23564.74256 in integer according to ECC.

because if I divide 1/10

is 0.1

028c6154856794fcd5ee79ba8c96b7dd980e289a6b93a52d50dbdb9388a4c75604

If I continue adding 0.1
0.2
03a3c9d9de2ba89d61c63af260be9759d752b8bfef56ee41b2dab2b99871af38a8
0.3
029b5d98e8ace287628d177ab6d47c6ae6e04a8858481582fd10a49baf4d066b4f
0.4
0337cd64f554a8a26e59fbffd50a0aa11a786012d3be0c3e085eb767afa2695716
0.5
020000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
0.6
0373414b5a15b55e859fc431a1a10dea18d829756d72cf2d70f5f26828e9965941
0.7
0373a5fb8e463a44348c3880a5e293646538e781cb201df39686ff33e073170363
0.8
033ff4953a91e46f3683c63d28c5100f3e8f78417ccc6567a217ef9ea6ca922729
0.9
0371cfb1ec28c77d72ba879acc074ffb775f7c6e54482975e1e8be62d54adbdaef
10
0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798

How will you see you can represent a number with floats in ecc.

but when there are many decimals it gets complicated.

0.864326889 ??

Besides the academic explanation by our friend, there are some tricks which you need to know about division.
E.g, if your key ends with an even number, you could get p+p/2 = p 1.5 by multiplying with this:


But how can you figure out  this? 0.6246791476704254716112
You need to know what produces the above fraction. However if you do this :
0.6246791476704254716112*10000000000000000000000
You'd end up with 6246791476704254716112, these are normal numbers but you can learn a lot from them ;
Lets see what that noob on second post did.
You will get an idea about what's happening once you do this and compare all the results.

When you are dividing, you'd want to use powers, to land on the closest number to your target.
Operating mod n, means your n is the limit of your world's mathematics, what that really means, n is not changing, it's a fixed value and you can find it's weak spots.

Since you're dividing two scalar numbers inside a Galois field, the division can be converted from x/y to x*y(^-1) [mod n, of course], following a basic law of division.

y^-1 inside a Galois field is equal to y^(n-2) [Not to the power of n-1 as you might think, because that evaluates to 1. Fermat's little theorem says y^n = y^1 = y.]

As you can see, the division has now been reduced to a modular exponentiation and a multiplication, which can be calculated by common tools.

There is no fractional part in finite field numbers, so we use this technique to do the division according to how it's supposed to be done in a field - as opposed to in the real number system.

given the private key

Pk= 1754225779965324
x= 7476542256
pk_pub= 035703f261cde18efa195bd626af22f35e47a091045370971d612589f642f250e5

we divide pk/X
we obtain...


02756d41db3f13a73d06684232efca6f99753827f6a3260dd50ca77f09b207036a

which in decimal numbers, should be:

234630.624679

either

234630.6246791476704254716112

we subtract the integer part "234630"

234630= 021b79ff0d52a6612cef311c61995259edc2a2a8771b5614d4b9e786f93afcb163


234630.624679 - 234630

we get the pub

02756d41db3f13a73d06684232efca6f99753827f6a3260dd50ca77f09b207036a

It should be the representation of:

0.624679

either

0.6246791476704254716112

but it is not, because if I divide

1/1000000= 0.000001

pub
026103a32c3d713955f09eb4aac723d7cec8492180c398e1398a50ff91937b8edd

and replace G by 0.000001

When generating pk= 624679, it does not match with:

02756d41db3f13a73d06684232efca6f99753827f6a3260dd50ca77f09b207036a

and if we divide


1/10000000000000000000000= 0.0000000000000000000001

pub

021f724a326b56244244206b0ad666dcadfa664e85ad037a9ba90816bbef0c2c43

and replace G by 0.0000000000000000000001

When generating the pk= 6246791476704254716112, it does not match either.

the question is why?

I know that ecc represents decimals and negatives as integers.
but in the same way it should be possible to represent the decimals after the "," or ".".

Could it be a precision problem?

0.6246791476704254716112xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

where the X are a series of unknown numbers?