So my questions are:
1. Is it possible to know when the point addition process has gone outside of the field?
And
2. Is there a way (like a Python script or something) that I could use to add 2 points and it would tell me if the result went outside of the field?
I know that the result of the addition is still a valid point on the curve, but I would love to know if it passed out of bounds first.
This would be fantastic for my project to show others how this works.
I hope that made sense and thanks in advance for your help.
The point at infinity is not "outside the field", since by definition it is included. For secp256k1 adding two points results in the infinity point (zero), if and only if the x coordinates are equal, and y coordinates differ: x1 = x2, and y1 ≠ y2. In jacobian coordinates you'd need to check some intermediate calculations for equality: x1*z2^2 = x2*z1^2, and y1*z2^3 ≠ y2*z1^3. Usually the point at infinity is denoted as (0,0), or (0,0,1) in jacobian coordinates. Check if y is zero. |
|
|
|
I wonder how often you need to clean it if you use it 24/7. Too often  And my replacement fan doesn't do a very good job, I don't like baking my GPU at 80 degrees (when searching for vanity addresses). I wonder what will happen first: a phone with a fan, or standard laptops without them.Phones with a fan existed few years ago - I remember seeing a "gaming phone" with a fan... found it: "Red Magic 3" from 2019. There are fanless laptops, here is a list from 2018 (or 2019?). MacBook Air with M1 processor is fanless as well. It happened almost an year ago. Do you consider it "standard laptop"? |
|
|
|
I had read that while the key size of secp256k1 is 256 bits, the security level is 128 bits and I was trying to understand why, so please enlighten me.
Is it because there are two different private keys that return the same x coordinate?
No. The average number of group operations to find a private key from a public one using Pollard Rho is O(sqrt(N)), N being the group order. Since N≈2 256, sqrt(N)≈2 128, giving 128 bit security. |
|
|
|
If you search for 1HT7xU2Ngenf7D4yocz2SAcnNLW7rK8d4E you will realize that this address is a burner address, as the publickey is not on secp256k1.
There are however about 2 96 valid public keys with that address, unknown of course. There is ~37% chance (1/e), that no 160 bit private key has this address, leaving us with 63.2% chance (1-1/e) that one or more 160 bit private keys has the address. If we consider both compressed and uncompressed public keys, the lack of chance is 13.5%, while one or more is 86.5%. |
|
|
|
Is there any successful crackers craked an existing Bitcoin address. If this is possible, why is it no one dared to opened the Genesis address. I dared them to open it or else you are wasting time.
Genesis address is different from the rest of the bitcoin addresses, consensus rules prevent you from spending bitcoins from the Genesis address even if you have its private key. Only the first 50 coins are not in the UTXO set. There are more than 3000 UTXO, 18.5 BTC waiting to be spent. |
|
|
|
We take 8 in the finite field of 47. We'll multiply 8 by 13 times => 8*13 = 104, 104 mod 47 = 10. Now let's find the multiplication inverse of 10 in that field:
10 * x = 8
How exactly can I solve this besides trying a different value each time? In the article, it tries 1, 2, 3... until it finds 29 which is suitable.
Let's consider a * x ≡ b (mod p), which means x ≡ b/a (mod p) for a ≠ 0. There are two ways to find x. First through Fermat's little theorem: a p ≡ a (mod p) a p-2 ≡ a -1 ≡ 1/a (mod p) x ≡ b * a p-2 (mod p) Second through Extended Euclidean algorithm: x ≡ b * inverse(a, p) (mod p) |
|
|
|
How can you defeat the system if you're able of multiplying two points instead of a number and a point?
Multiplying two points allows us to square as well, and consequently rise to any power. Then we can work in the multiplicative group, which has order N-1, and excludes the point at infinity (0,0). The biggest factor of N-1 is only 108 bits. Using Pohlig-Hellman in conjunction with Pollard-Rho (or BSGS for smaller factors, and exhaustive search for the smallest) we find k with cost O(2 54) multiply operations. |
|
|
|
I am building a secp256k1 class in Node.js to use in my tools, and I know that numbers in a group already have a multiplicative inverse - and how to calculate it - I have point multiplication already implemented but I am not sure if there is such a factor k-1 such that
k-1P * kP = P
Modulo prime number for every number (except zero) there's unique inverse. That is, the sequence of all inverse is a permutation of all positive numbers. Is it simply the inverse of k mod curve order n? Since the curve order is n, then k -1 is mod n as well. This is supposed to be to implement the division operation P/k.
Also - I don't think multiplicative inverse of points (i.e. P-1, not group numbers) exists, does it?
I cannot guess what you mean. |
|
|
|
I know, but can you tell me the specific meaning of tapscript (Many previously disabled opcodes are redefined to be OP_SUCCESS opcodes that unconditionally render the entire script valid to simplify soft fork upgrades.)? I don’t understand what OP_SUCCESS specifically redefines? How is it used?
In tapscript when the interpreter encounters one of the OP_SUCCESSx opcodes, it instantly succeeds. In the future this might change, and some opcodes might enforce restrictions - soft fork. But the future is not here yet, so nobody knows what and how exactly would happen. So there was OP_CAT at the very beginning, then it was disabled, and now inside tapscript there's OP_SUCCESS126 instead, which might change (in future tapscript version) to something else (instead of instant success). Here is the list of the codes redefined as OP_SUCCESSx, the red ones were disabled in usual script:
OP_RESERVED = 0x50,
OP_VER = 0x62,
OP_CAT = 0x7e,
OP_SUBSTR = 0x7f,
OP_LEFT = 0x80,
OP_RIGHT = 0x81,
OP_SIZE = 0x82,
OP_INVERT = 0x83,
OP_AND = 0x84,
OP_OR = 0x85,
OP_XOR = 0x86,
OP_RESERVED1 = 0x89,
OP_RESERVED2 = 0x8a,
OP_2MUL = 0x8d,
OP_2DIV = 0x8e,
OP_MUL = 0x95,
OP_DIV = 0x96,
OP_MOD = 0x97,
OP_LSHIFT = 0x98,
OP_RSHIFT = 0x99,
and everything between OP_CHECKSIGADD = 0xba,
and OP_INVALIDOPCODE = 0xff,
|
|
|
|
I read the code, but I didn’t understand what is the purpose of this upgrade of OP_SUCCESS? Can you give me a detailed explanation? Thank you
This makes taproot upgradable. |
|
|
|
... quantum-resistant ...
What you think?
Creating quantum-resistant crypto algorithm is very easy: all algorithms are quantum-resistant. All of them. Quantum computing is, and will always be slower than classical one. All quantum computers are noise-generators, and can only be superior in generating garbage. Of course for some applications tons of noise is beneficial, but not for solving ECDLP or reversing SHA256. It is very easy to see it: somewhere halfway through solving the problem, the magical qubits have to represent a whooping 2 256 bits of information. Then a single neutrino passes through and all is gone, the information is disrupted. And neutrinos pass all the time in large quantity. And not only neutrinos. The word "quantum" in many cases is equivalent to "scam". So is any "scam computer" a threat to bitcoin? |
|
|
|
The extra 94 96 bits usually seen as minor security weakness since 1 private key is valid for 2^96 address (ignoring different public key representation, different address format, etc.).
You mean 1 address is valid for 2^96 private keys. |
|
|
|
It looks more like security through obscurity. As I wrote on my github: Note that the encrypted words/numbers are not cryptographically secure, as they can be bruteforced to get the original words, but they do give you some protection from the common thief and some extra time to react in case of theft, etc. Is the above true? Yes. Is it safer than writing it down in plain text? Yes. No. It was "safer" before you published it. Now it's no more. The obscurity is gone. Way "safer" would be to use the dates as an additional passphrase, maybe as text and together with other words. This way you wouldn't need additional software, it already works, not only with BIP39, but electrum seeds as well. |
|
|
|
It is less than $500.
For 12 word BIP39 on average every 16th try will have a valid checksum. If I got it correctly there are only 2 dates 1900-2021, so the complexity is around 365.24 2*121 2/16 = 2 26.9 PBKDF2. Single address derivation (the usual non-hardened) is about 10 times faster than PBKDF2. Generating all the master keys would take about 1-2 minutes on 4xV100 (amazon p3.8xlarge), but to develop and test it would cost much more time. Not worth it. Let's look at the "hardest" 12 word "encryption". If only valid dates are supplied (i.e. no 37th day of 185th month), then the complexity is 365.24 3*2048 3/16 = 2 54.5 PBKDF2. Going through all combinations would take ~461 years on 4xV100. Of course this scheme has an enormous weakness - since the dates are to be easy remembered, then the range would be significantly smaller. For example 3 dates in interval 1900-2021 give complexity 2 42.3, or about 35 days on 4xV100. Inserting a memorable date from the past doesn't help either. It looks more like security through obscurity. |
|
|
|
This is a C# thing, it adds a leading zero when MSB of the top byte is one, something to do with distinguishing between positive and negative numbers. You have to be careful when parsing hex numbers as well: BigInteger.Parse("ff") = -1.
Overall C# is a language with many such intricacies (or I would say stupid choices).
This is not a C# thing at all. This is a popular way in computers to indicate positive/negative numbers which the BigInteger class also uses. In fact we are using a similar logic in bitcoin signatures that are encoded using DER encoding (use most significant bit of the most significant byte to indicate sign). The most popular way to indicate a negative number is with "-". They are doing a memory dump. Is there a way to print and parse the number properly? In DER encoding it is justified, we get a single long hex digit sequence, but when printing a single number it just looks wrong, and consequently increases the cognitive load. One could write in the source code -0xff, and all is good, but AFAIK there's no (easy) way to parse "-0xff" as a BigInteger. |
|
|
|
Thank you! Your code works fine, there's just one thing which slips (?) the process. It adds an additional zero sometimes in front of the x & y and I don't know what's responsible for that. For example, if I run it with k=1, it returns it properly: x: 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
y: 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 Trying it with k=2, you'll get: x: 0C6047F9441ED7D6D3045406E95C07CD85C778E4B8CEF3CA7ABAC09B95C709EE5
y: 1AE168FEA63DC339A3C58419466CEAEEF7F632653266D0E1236431A950CFE52A
That extra zero ( 0C60...) shouldn't exist, because obviously, once is hashed with SHA256 it'll give a different result. This is a C# thing, it adds a leading zero when MSB of the top byte is one, something to do with distinguishing between positive and negative numbers. You have to be careful when parsing hex numbers as well: BigInteger.Parse("ff") = -1. Overall C# is a language with many such intricacies (or I would say stupid choices). |
|
|
|
... I could swear that ^n means raising to the power of n. But, it turns out that it doesn't. It actually means index from end operator. As for the missing parts, I didn't know them. I was only following the ruby scripts from learnmeabitcoin. Thanks for the time it took you to correct me. I would say it is Logical exclusive OR operator ^. I did make the changes, but still get false result. For k=100 I should be getting:
Test it step by step: Is ECdouble giving the correct result for G, 2G, O? Is ECaddition doing it as well: G+G, G+(-G), G+2G, 2G+3G, 3G+4G? Finally is ECMultiplication correct for small numbers (1-10), for big numbers (n-1), for numbers >=n ? Your inverse function is still wrong. You could give up and use the simpler (but slower) version: public static BigInteger inverse(BigInteger a, BigInteger m)
{
return BigInteger.ModPow(a, m - 2, m);
}
Looking at your struggle is just painful. Here is working code. using System;
using System.Numerics;
public class Program
{
static BigInteger p = BigInteger.Parse("115792089237316195423570985008687907853269984665640564039457584007908834671663");
static BigInteger n = BigInteger.Parse("115792089237316195423570985008687907852837564279074904382605163141518161494337");
static BigInteger[] zero = {0,0};
static BigInteger[] g = {
BigInteger.Parse("55066263022277343669578718895168534326250603453777594175500187360389116729240"),
BigInteger.Parse("32670510020758816978083085130507043184471273380659243275938904335757337482424")
};
public static void Main()
{
BigInteger[] g0 = {0,0}, g2 = ECdouble(g), g4 = ECdouble(g2);
BigInteger[] z = ECMultiplication(7, g);
//z = ECaddition(z, g);
//z = ECaddition(z, g2);
//z = ECaddition(z, g4);
Console.WriteLine(z[0].ToString());
Console.WriteLine(z[1].ToString());
Console.WriteLine(IsOnCurve(z));
Console.WriteLine(IsOnCurve(zero));
}
public static BigInteger inverse(BigInteger a, BigInteger m) { return BigInteger.ModPow(a, m-2, m); }
public static BigInteger[] ECdouble(BigInteger[] point)
{
if (point[1] == 0) return zero;
BigInteger slope = (3 * BigInteger.ModPow(point[0], 2, p) * inverse((2 * point[1]), p)) % p;
BigInteger x = (BigInteger.ModPow(slope, 2, p) - (2 * point[0])) % p;
BigInteger y = (slope * (point[0] - x) - point[1]) % p;
if (x < 0) x += p;
if (y < 0) y += p;
BigInteger[] coord = { x, y };
return coord;
}
public static BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
{
if (point1[1] == 0) return point2;
if (point2[1] == 0) return point1;
if (point1[0] == point2[0]) {
if (point1[1] == point2[1]) return ECdouble(point1);
return zero;
}
BigInteger slope = ((point2[1] - point1[1]) * inverse(point2[0] - point1[0], p)) % p;
BigInteger x = (BigInteger.ModPow(slope, 2, p) - point1[0] - point2[0]) % p;
BigInteger y = ((slope * (point1[0] - x)) - point1[1]) % p;
if (x < 0) x += p;
if (y < 0) y += p;
BigInteger[] coord = { x, y };
return coord;
}
public static BigInteger[] ECMultiplication(BigInteger k, BigInteger[] Gpoint)
{
BigInteger[] powerOfTwo = Gpoint;
BigInteger[] result = zero;
k %= n; if (k < 0) k += n;
while (k > 0) {
if ((k&1) == 1) result = ECaddition(result, powerOfTwo);
k >>= 1;
powerOfTwo = ECdouble(powerOfTwo);
}
return result;
}
public static bool IsOnCurve(BigInteger[] point)
{
BigInteger x = point[0] % p; if (x<0) x += p;
BigInteger y = point[1] % p; if (y<0) y += p;
return BigInteger.ModPow(y, 2, p) == (BigInteger.ModPow(x, 3, p) + 7) % p;
}
}
|
|
|
|
So it works in the full range of 2^256 so what would be the expected operations?
- 1 point addition to have Point (x1, y1)
- 1 subtraction to get y2
- 2 multiplications to get x2 and x3
- comparisions to get lowest x and lowest y
Then you will have all x and y coordinates for all 6 points with the effort of less than 2 point additions, what will increase the speed enormously. - 1 point addition to have Point (x1, y1)
- 2 subtractions to get y2 and the corresponding private key
- 4 multiplications to get x2 and x3, and their corresponding private keys
- 3 comparisions to get lowest x and lowest y
The speedup works only on Pollard Rho, at most sqrt(6) = 2.44 times. For Kangaroo only the negation (y) is applicable, with speedup at most 1.41 times (and bigger variance?) - AFAIK Jean-Luc uses it already. All this is well known: if we have a point (x,y) = k*G, the 6 points are (a ix, b jy) = c id j*(k*G) with a 3 = 1 mod p (matching the chosen value of c) b 2 = 1 mod p c 3 = 1 mod n (matching the chosen value of a) d 2 = 1 mod n i∈{0,1,2} j∈{0,1}. One can calculate the numbers by finding the primitive roots mod p and n I.E. r p = 77643668876891235360856744073230947502707792537156648322526682022085734511405 r n = 106331823171076060141872636901030920105366729272408102113527681246281393517969 a = (r p(p-1)/3) 2 = 55594575648329892869085402983802832744385952214688224221778511981742606582254 b = r p(p-1)/2 = 115792089237316195423570985008687907853269984665640564039457584007908834671662 = -1 c = r n(n-1)/3 = 37718080363155996902926221483475020450927657555482586988616620542887997980018 d = r n(n-1)/2 = 115792089237316195423570985008687907852837564279074904382605163141518161494336 = -1 |
|
|
|
Marked with red are some grievous mistakes. Blue are some missing parts. Since you managed to discard any feedback let me make it very clear: ^ 2 is not squaring a number: 2^2 = 0public BigInteger[] ECdouble(BigInteger[] point)
{
if (point[1] == 0) {
BigInteger[] coord = {0,0};
return coord;
}
BigInteger slope = ((3 * point[0] ^ 2) * inverse((2 * point[1]), p)) % p;
BigInteger x = (slope ^ 2 - (2 * point[0])) % p;
BigInteger y = (slope * (point[0] - x) - point[1]) % p;
BigInteger[] coord = { x, y };
return coord;
}
public BigInteger[] ECaddition(BigInteger[] point1, BigInteger[] point2)
{
if (point1[0] == point2[0] && point1[1] == point2[1])
{
return ECdouble(point1);
}
if (point1[0] == point2[0])
{
BigInteger[] coord = {0,0};
return coord;
}
BigInteger slope = ((point1[1] - point2[1]) * inverse(point1[0] - point2[0], p)) % p;
BigInteger x = (slope ^ 2 - point1[0] - point2[0]) % p;
BigInteger y = ((slope * (point1[0] - x)) - point1[1]) % p;
BigInteger[] coord = { x, y };
return coord;
}
|
|
|
|
|
Show Posts
