PowerGlove (OP)
|
|
July 27, 2022, 05:15:58 AM Last edit: July 28, 2022, 06:55:45 AM by PowerGlove Merited by vapourminer (1) |
|
My first post on this forum was about "split" keys. I ended that post by saying that you shouldn't mix up field operations with different moduli (I use that word all the time ). @garlonicon left a reply and a nice edit about how mixing them up can actually be useful, here's the relevant snip: It is better than that: you can join sub-fields if you know how it works. For example, you have two public keys with the same x-value, and you have three public keys with the same y-value. That means, for a given public key, you always have six "trivial" points, forming some area. And you can do crazy stuff if you start dealing with such rectangles.
This made very little sense to me at the time, and I've been trying to figure it out on my own, here's what I've got so far: I get that for a given point you can find a "second" Y co-ordinate by negating it (modulo P). As I understand it, this is because there are two solutions (given X) to this equation (modulo P): Equation A: Y = (X ** 3 + 7) ** 1/2 I also get that if you negate the private key (modulo N), it has the same effect (i.e. producing a public key with the "other" Y co-ordinate). Okay, so that takes care of the first two "trivial" points, what about the other four? At first, I couldn't see how it would be possible to have three points with the same Y co-ordinate. But, after learning a bit more about finding roots in finite fields I can now appreciate how there are three solutions (given Y) to this equation (modulo P): Equation B: X = (Y ** 2 - 7) ** 1/3 I'm still not sure what (if any) the corresponding operations are with private keys (i.e. what do you have to do to a private key to produce these "other" X co-ordinates?). Okay, so I can now see how to compute these 6 "trivial" points: X 1 = First solution to Equation B (given Y) X 2 = Second solution to Equation B (given Y) X 3 = Third solution to Equation B (given Y) Y 1 = First solution to Equation A (given X) Y 2 = Second solution to Equation A (given X) Point A: (X 1, Y 1) Point B: (X 2, Y 1) Point C: (X 3, Y 1) Point D: (X 1, Y 2) Point E: (X 2, Y 2) Point F: (X 3, Y 2) What are these useful for? What "crazy stuff" can be done with them? Thanks for your help Update: I think I've found something these might be used for! Would still appreciate any other insights though.
|
|
|
|
NotATether
Legendary
Offline
Activity: 1722
Merit: 7259
In memory of o_e_l_e_o
|
|
July 27, 2022, 05:39:42 AM |
|
As far as I know, nothing. It's like attempting to create the world's shortest program that does a specific function - they are mind games for computer scientists, but that's about it.
|
|
|
|
j2002ba2
|
But, after learning a bit more about finding roots in finite fields I can now appreciate how there are three solutions (given Y) to this equation (modulo P):
Equation B: X = (Y ** 2 - 7) ** 1/3
I'm still not sure what (if any) the corresponding operations are with private keys (i.e. what do you have to do to a private key to produce these "other" X co-ordinates?).
You could obtain the other private keys by multiplying by a non-trivial cubic root of 1 modulo n. Then y will be the same, and x will be multiplied by the corresponding non-trivial root of 1 modulo p. Here are the two cube roots of 1 (besides the trivial 1) modulo n: n2: 37718080363155996902926221483475020450927657555482586988616620542887997980018 n3: 78074008874160198520644763525212887401909906723592317393988542598630163514318 and their corresponding cube roots of 1 modulo p: p2: 55594575648329892869085402983802832744385952214688224221778511981742606582254 p3: 60197513588986302554485582024885075108884032450952339817679072026166228089408 (X2, Y1) = n2 * (X1, Y1) = (p2*X1, Y1) (X3, Y1) = n3 * (X1, Y1) = (p3*X1, Y1) (X1, Y2) = -1 * (X1, Y1) = (X1, -Y1) (X2, Y2) = -n2 * (X1, Y1) = (p2*X1, -Y1) (X3, Y2) = -n3 * (X1, Y1) = (p3*X1, -Y1)
|
|
|
|
PowerGlove (OP)
|
|
July 27, 2022, 04:31:26 PM |
|
You could obtain the other private keys by multiplying by a non-trivial cubic root of 1 modulo n. Then y will be the same, and x will be multiplied by the corresponding non-trivial root of 1 modulo p.
Here are the two cube roots of 1 (besides the trivial 1) modulo n: n2: 37718080363155996902926221483475020450927657555482586988616620542887997980018 n3: 78074008874160198520644763525212887401909906723592317393988542598630163514318 and their corresponding cube roots of 1 modulo p: p2: 55594575648329892869085402983802832744385952214688224221778511981742606582254 p3: 60197513588986302554485582024885075108884032450952339817679072026166228089408
(X2, Y1) = n2 * (X1, Y1) = (p2*X1, Y1) (X3, Y1) = n3 * (X1, Y1) = (p3*X1, Y1) (X1, Y2) = -1 * (X1, Y1) = (X1, -Y1) (X2, Y2) = -n2 * (X1, Y1) = (p2*X1, -Y1) (X3, Y2) = -n3 * (X1, Y1) = (p3*X1, -Y1)
@j2002ba2: Thank you, I was vaguely aware of these "roots of unity" but seeing your example made them click for me, much appreciated.
|
|
|
|
bjpark
Jr. Member
Offline
Activity: 35
Merit: 2
|
|
August 03, 2022, 02:15:05 AM Last edit: August 03, 2022, 02:59:01 AM by bjpark |
|
Private key(1) p1= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 p2= 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 p3= 0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 True True p4= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 p5= 0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcb, 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 p6= 0xc994b69768832bcbff5e9ab39ae8d1d3763bbf1e531bed98fe51de5ee84f50fb, 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 ======================================================================== Private key(2) p1= 0x769ad99b0ac59bb38e84d114104707f3d08d98e78ed88b6915ba9ad5cafd0898, 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a p2= 0xc360a6d0b34ce6df4135ee7d59f87b33d2fad8cce43837ef3e995b6ed89250e1, 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a p3= 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5, 0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a True True p4= 0x769ad99b0ac59bb38e84d114104707f3d08d98e78ed88b6915ba9ad5cafd0898, 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705 p5= 0xc360a6d0b34ce6df4135ee7d59f87b33d2fad8cce43837ef3e995b6ed89250e1, 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705 p6= 0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5, 0xe51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705 ======================================================================== Private key(3) p1= 0x276096fafa87a1a428fe22aadd39b3a6bfdc5797b5b3d832820d9c5dcbff5636, 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 p2= 0xdf6edf03731f9b4b8dcd8dcf2a28fa2f8af1e022c6dc8e1cf7f0728c77206b2f, 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 p3= 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9, 0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 True True p4= 0x276096fafa87a1a428fe22aadd39b3a6bfdc5797b5b3d832820d9c5dcbff5636, 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bd p5= 0xdf6edf03731f9b4b8dcd8dcf2a28fa2f8af1e022c6dc8e1cf7f0728c77206b2f, 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bd p6= 0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9, 0xc77084f09cd217ebf01cc819d5c80ca99aff5666cb3ddce4934602897b4715bd ======================================================================== Private key(4) p1= 0x1b77921f0d3829075c45faf8b90e324b714c30b5ab4871275bde5b333b306100, 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922 p2= 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13, 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922 p3= 0xfff491ef31ba56054b9bbc02b3e6b9afc247bbba45d719542f27101edc0aca4b, 0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922 True True p4= 0x1b77921f0d3829075c45faf8b90e324b714c30b5ab4871275bde5b333b306100, 0xae1266c15f2baa48a9bd1df6715aebb7269851cc404201bf30168422b88c630d p5= 0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13, 0xae1266c15f2baa48a9bd1df6715aebb7269851cc404201bf30168422b88c630d p6= 0xfff491ef31ba56054b9bbc02b3e6b9afc247bbba45d719542f27101edc0aca4b, 0xae1266c15f2baa48a9bd1df6715aebb7269851cc404201bf30168422b88c630d ======================================================================== Private key(5) p1= 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4, 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6 p2= 0x337b52e3acda49dff79f54fbccb94671a045693ee0d097cc138c694695a83668, 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6 p3= 0x9cf8cecf391e958cb2ac03df28ea6865772f120342cdcd7c20cac14eb816d5e3, 0xd8ac222636e5e3d6d4dba9dda6c9c426f788271bab0d6840dca87d3aa6ac62d6 True True p4= 0x2f8bde4d1a07209355b4a7250a5c5128e88b84bddc619ab7cba8d569b240efe4, 0x2753ddd9c91a1c292b24562259363bd90877d8e454f297bf235782c459539959 p5= 0x337b52e3acda49dff79f54fbccb94671a045693ee0d097cc138c694695a83668, 0x2753ddd9c91a1c292b24562259363bd90877d8e454f297bf235782c459539959 p6= 0x9cf8cecf391e958cb2ac03df28ea6865772f120342cdcd7c20cac14eb816d5e3, 0x2753ddd9c91a1c292b24562259363bd90877d8e454f297bf235782c459539959 ======================================================================== Private key(6) p1= 0x19cab650e04db19581801eb9e6c50b54f6a51b9223f6040c894f936926e302c3, 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297 p2= 0xe63bcdd9aa535fc65e3aa731e3e8bed786649d3e56a15a6847aaf28078f38045, 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297 p3= 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556, 0xae12777aacfbb620f3be96017f45c560de80f0f6518fe4a03c870c36b075f297 True True p4= 0x19cab650e04db19581801eb9e6c50b54f6a51b9223f6040c894f936926e302c3, 0x51ed8885530449df0c4169fe80ba3a9f217f0f09ae701b5fc378f3c84f8a0998 p5= 0xe63bcdd9aa535fc65e3aa731e3e8bed786649d3e56a15a6847aaf28078f38045, 0x51ed8885530449df0c4169fe80ba3a9f217f0f09ae701b5fc378f3c84f8a0998 p6= 0xfff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556, 0x51ed8885530449df0c4169fe80ba3a9f217f0f09ae701b5fc378f3c84f8a0998
1 = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8-1= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777I have a question. Like the example of private key number 1, The Y value is often larger, so is there a way to correct the error? 1 > -1 BUT 1 = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8-1= 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef27770x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 (1)< 0xb7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777 (-1)
|
|
|
|
PowerGlove (OP)
|
@bjpark: Sorry, I'm not sure what you're asking, I can take a guess though. Your X/Y co-ordinates for all 6 points generated from private key 1 are correct. So, assuming [1], I'm guessing your question is: "Why is the Y co-ordinate of PointB larger than the Y co-ordinate of PointA when SecretB is smaller than SecretA?" First of all, and this is mostly irrelevant to the answer, but SecretB isn't smaller than SecretA because you haven't taken the modulo operation into account (i.e. -1 < 1 but (-1 % N) > 1). But even if it were, it wouldn't matter, because multiplying a scalar by the generator point acts much like a hash function (the security of Bitcoin depends on it). For example, assuming a hash function 'H' that accepts and returns an integer, you wouldn't expect H(2) > H(1), would you? If that wasn't your question, then feel free to try again, but this time please don't misquote me [1] SecretA = 1, SecretB = (-1 % N), PointA = SecretA * G, PointB = SecretB * G, usual definitions for N and G.
|
|
|
|
bjpark
Jr. Member
Offline
Activity: 35
Merit: 2
|
|
August 03, 2022, 11:14:37 PM |
|
@bjpark: Sorry, I'm not sure what you're asking, I can take a guess though. Your X/Y co-ordinates for all 6 points generated from private key 1 are correct. So, assuming [1], I'm guessing your question is: "Why is the Y co-ordinate of PointB larger than the Y co-ordinate of PointA when SecretB is smaller than SecretA?" First of all, and this is mostly irrelevant to the answer, but SecretB isn't smaller than SecretA because you haven't taken the modulo operation into account (i.e. -1 < 1 but (-1 % N) > 1). But even if it were, it wouldn't matter, because multiplying a scalar by the generator point acts much like a hash function (the security of Bitcoin depends on it). For example, assuming a hash function 'H' that accepts and returns an integer, you wouldn't expect H(2) > H(1), would you? If that wasn't your question, then feel free to try again, but this time please don't misquote me [1] SecretA = 1, SecretB = (-1 % N), PointA = SecretA * G, PointB = SecretB * G, usual definitions for N and G. @PowerGlove Thank you for your good answer. It is easy to distinguish between p1 and p4 when you know the private key. P1 = (X1,Y1) P2 = (X2, Y1) = n2 * (X1, Y1) = (p2*X1, Y1) P3 = (X3, Y1) = n3 * (X1, Y1) = (p3*X1, Y1) P4 = (X1, Y2) = -1 * (X1, Y1) = (X1, -Y1) P5 = (X2, Y2) = -n2 * (X1, Y1) = (p2*X1, -Y1) P6 = (X3, Y2) = -n3 * (X1, Y1) = (p3*X1, -Y1) When you only know the public key, I don't know how to decide P1 and P4. 0xae40e58174d04b4490c4876028b648e569fa484b7e3d29aaf2dae49bd360d77, 0x171c179d32934ee25cefd742e65e75fd5a0e31a03063ce702f6dc53db46d4ecf ==>P1 or P4 ? 0xae40e58174d04b4490c4876028b648e569fa484b7e3d29aaf2dae49bd360d77, 0xe8e3e862cd6cb11da31028bd19a18a02a5f1ce5fcf9c318fd0923ac14b92ad60 ==>P1 or P4 ? He's the one I made. https://youtu.be/G3veKAXGyFoI can create a transaction without a private key I think it would be nice to collaborate together.
|
|
|
|
NotATether
Legendary
Offline
Activity: 1722
Merit: 7259
In memory of o_e_l_e_o
|
|
August 04, 2022, 03:53:05 AM Last edit: August 04, 2022, 04:10:38 AM by NotATether |
|
I have a question. Like the example of private key number 1, The Y value is often larger, so is there a way to correct the error?
Yeah, you're basically asking about even and odd y. Take y, and compute n-y, and take the smaller of the two. Because sometimes the even y is larger than it's odd part, and vice versa. @PowerGlove: Since the curve characteristic p = 1 mod 3, that means there's 3 cube roots for all numbers on the field (including x and 1), so to get the roots of 1 on any curve that satisfies that equation, you can just compute x^((p-1)/3). [The x^(p-1) part will evaluate to 1, but of course you can't split the operations].
|
|
|
|
fxsniper
Member
Offline
Activity: 406
Merit: 47
|
|
August 04, 2022, 10:06:20 AM |
|
from an image that means calculate point 1 and calculate to point 6 and use point 6 to be point 1 again right?
|
|
|
|
fxsniper
Member
Offline
Activity: 406
Merit: 47
|
|
August 05, 2022, 05:38:00 AM |
|
this method calculates Can possibly use it to calculate some points back to the G point? Inverse Modulo of private key can multiply with the public key and roll back to G point right
|
|
|
|
PowerGlove (OP)
|
|
August 06, 2022, 05:41:54 AM Last edit: August 06, 2022, 04:41:42 PM by PowerGlove |
|
@bjpark: Sorry, it looks to me like you're asking the same question, but using different words. Unless I'm misunderstanding you, I think my first answer already covered that. You're not supposed to be able to infer anything about the private key by looking at the public key. Even being able to correctly guess a single bit can break the security of Bitcoin [1]. @fxsniper: I'm not the right person to ask about that image. It strikes me as some kind of ECDLP acceleration scheme but I've never looked deeply into that and just bumped into it on this thread here [2] while trying to figure out what these so-called "trivial" points can be used for. [1] https://crypto.stackexchange.com/questions/96116/can-i-know-from-a-bitcoin-public-key-if-the-private-key-is-odd-or-even[2] https://bitcointalk.org/index.php?topic=5347863.0
|
|
|
|
fxsniper
Member
Offline
Activity: 406
Merit: 47
|
|
August 06, 2022, 09:58:59 AM |
|
Thank you PowerGlove for helping answer puzzle project help me to interesting in learning deep detail of cryptography now I interesting in blockchain programming technology bitcoin it is a very complex algorithm hard to crack (still try)
|
|
|
|
|