Because 0x1110...f784 has many small factors: 2^2 * 17 * 4289 * 6196937 * 9672199247 * 441571470858719851994038335827739586159888848835828007
While 0x1b88...e5e9 has factor 3, and then some unholy big numbers.
Your funny random mapping then produces some random integer, which is very very unlikely to have one of the big factors in the second one.
That said, what is the purpose of this exercise?
Point coordinates are not integers, they are instead infinite sets of all kind of numbers, represented by integers.
Specially y^2 = x^3 + 7 does not have integer or rational number solutions. Plugging integers makes even less sense here.
Why not use an isomorphic curve of rank>0, i.e. y^2 = x^3 - 2. Then at least you'd know that there are rational solutions, and have a single nice generator (3,5).
|
|
|
There is an elliptic curve equation, which is taken modulo P. This produces a group with N points.
Now you'd like to change the modulo to N, and get a group with P points.
Congratulations! There are many many such curves.
But there's a caveat.
Taking something modulo P does not produce an integer. Instead the result is a "number modulo P". The "something" could be any of infinite numbers, both positive, negative, rational, irrational, etc.
So the real curve could be y^2 = x^3 + kPx + B, which reduces to y^2 = x^3 + B (mod P), and you could vary k in order to get the desired number of points modulo N. Or in a rare cases y^2 = x^3 + kPx + B + mP, if more flexibility is needed.
That means: the curves in different modulo are not related in any way.
Any curve in one modulo is equivalent to any curve in any other modulo.
Zero bits of information are gained here.
Edit: BTW, there is no curve possible with P=97 and N=67 or vice-versa. The number of points possible lays in the interval P+1±2√P, which gives [79, 117] mod 97, and [52, 84] mod 67.
|
|
|
Shor's algorithm with noiseless qubits and gates works in theory. Shor's algorithm with noisy qubits and gates does not work in theory. It needs exponentially small noise. Both in theory. That's it.
I thought that this is what error correction fixes-- with a huge but only polynomial blow up. If I understand it correctly, the error correction could reduce noise only in linear fashion - QC are analog machines - ten times more resources would reduce error only tenfold at most. For Shor's to work this is not enough at all - it needs exponentially smaller noise.
|
|
|
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically.
Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits. This is correct only with ideal noiseless qubits and gates. That's exactly what a "theoretical QC" is. Hence, your claim of "not vulnerable to QC even theoretically" being wrong. Shor's algorithm with noiseless qubits and gates works in theory. Shor's algorithm with noisy qubits and gates does not work in theory. It needs exponentially small noise. Both in theory. That's it.
|
|
|
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory.
Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits. This is correct only with ideal noiseless qubits and gates. Shor's algorithm fails when exponentially small noise is present. That is, it needs noise levels of the order 2 -n. The same is true for ECDLP. Good luck achieving noise level 2 -256. It is very easy to figure out why that happens. We start with qubits which are independent, each representing only 1 bit of information. But before reaching the final result it is not yet clear which of the 2 n possibilities are the correct ones. So midway of the quantum computation, qubits have to represent 2 2n states at the same time. This enormous amount of information vanishes with any noise present. Read the last sentence in this section https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation.
|
|
|
they might not factor 10^1000 size numbers but 2048 bit numbers are an entirely different animal and should be vulnerable to quantum computers at some point. very vulnerable. the only question is, when do companies like atom computing scale up past 1000 qbits to say 1 million qbits. i'd say in the next 10 years at worst. they went from 100 qbits to 1000 in like 2 years.
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory. Current QC hardware struggles with RSA-6 (six bits). Finally someone did put the noise into quantum equations and this is the result: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n - the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1−o(1) over random prime pairs (p,q), Shor's factoring algorithm does not factor numbers of the form pq, with the same level of random noise present.
|
|
|
Humanity developing a quantum computer strong enough to break ECDSA seems far more likely than someone finding an effective alternative to Shor's algorithm for classical computing tho.
It is exactly the opposite. Quantum computers are likely never going to do any useful cryptography related stuff. And Shor's algorithm is yet to be implemented, it exists just on paper, and very small and truncated versions happened. With current hardware, to even have a theoretical chance at ECDLP, one needs more than 28*10 15 qubits - this is 28 Peta qubits. Even with ideal, zero noise QC, one needs 126*10 9 Toffoli gates. And something more about the all-hyped Shor's algorithm: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n - the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1−o(1) over random prime pairs (p,q), Shor's factoring algorithm does not factor numbers of the form pq, with the same level of random noise present.
Well, looks like even quantum error correction wouldn't help with ECDLP. All quantum hope is gone.
|
|
|
How do you create a "coinbase tx"? Can it be built via createrawtransaction or can it only be created in code? Then I don't fully understand how to build this transaction.
Create it manually: createrawtransaction doesn't allow you to set the script of the input. version: 02000000 marker: 00 flag: 01 txIns: num: 01 in-1: txid: 0000000000000000000000000000000000000000000000000000000000000000 index: ffffffff script: length: 31 block-height-BIP34: 03 ed630c extra-nonce: 04a95e29652f466f756e6472792055534120506f6f6c202364726f70676f6c642f1a0727769676000000000000 sequence: ffffffff txOuts: num: 02 out-1: value: 46edf02500000000 script: length: 16 P2SH: 00 14 35f6de260c9f3bdee47524c473a6016c0c055cb9 out-2: value: 0000000000000000 script: length: 26 OP_RETURN: 6a OP_PUSH_36: 24 commitment-header: aa21a9ed commitment-hash: 95c53abf59b8c6df571b1ca9ff8ad0e6f77a82b2b59c229463cda7a0281a4caf witness: count: 01 witness-1: length: 20 data: 0000000000000000000000000000000000000000000000000000000000000000 locktime: 00000000
There are enough books explaining all this. I suggest to look inside "Programming Bitcoin" before asking here.
|
|
|
What happens if such solution is found?
Nothing. Anybody finding it would keep silent. The incentive to not spill out the secret is just too big. Is there any alternatives to replace ECC?
|-------------+-------+-------+-------+----------+-------+-------+-------+----------| | Name | PrivK | PubK | Sig | Security | PubK | Sig | block | average | | | bytes | bytes | bytes | bits | *secp | *secp | *secp | block MB | |-------------+-------+-------+-------+----------+-------+-------+-------+----------| | secp256k1 | 32 | 32 | 64 | 128 | 1.0 | 1.0 | 1.0 | 1.3 | |-------------+-------+-------+-------+----------+-------+-------+-------+----------| | RSA 2048 | 512 | 256 | 256 | 112 | 8.0 | 4.0 | 6.0 | 7.8 | | RSA 3072 | 768 | 384 | 384 | 128 | 12.0 | 6.0 | 9.0 | 11.7 | |-------------+-------+-------+-------+----------+-------+-------+-------+----------| | Dilithium2 | 2528 | 1312 | 2420 | 128 | 41.0 | 37.8 | 39.4 | 51.2 | | Dilithium3 | 4000 | 1952 | 3293 | 192 | 61.0 | 51.5 | 56.2 | 73.1 | | Dilithium5 | 4864 | 2592 | 4595 | 256 | 81.0 | 71.8 | 76.4 | 99.3 | |-------------+-------+-------+-------+----------+-------+-------+-------+----------| | Falcon-512 | 1281 | 897 | 666 | 128 | 28.0 | 10.4 | 19.2 | 25.0 | | Falcon-1024 | 2305 | 1793 | 1280 | 256 | 56.0 | 20.0 | 38.0 | 49.4 | |-------------+-------+-------+-------+----------+-------+-------+-------+----------| | Sphincs+ | 64 | 32 | 7856 | 128 | 1.0 | 122.8 | 61.9 | 80.5 | | Sphincs+ | 96 | 48 | 16224 | 192 | 1.5 | 253.5 | 127.5 | 165.8 | | Sphincs+ | 128 | 64 | 29792 | 256 | 2.0 | 465.5 | 233.8 | 303.9 | |-------------+-------+-------+-------+----------+-------+-------+-------+----------|
|
|
|
lambda and beta are non-trivial cube roots of 1 modulo n and p. λ 3 = 1 (mod n) β 3 = 1 (mod p) [λ](x,y) = (βx,y) Since there are 3 of each you'd have to match them (2 are non-trivial, so there is just one equality check). You could find how to get such root of 1 here. So, let your curve is modulo q, and has order m, both prime numbers. Compute a primitive root of 1 modulo q: a≠1 a q-1 = 1 (mod q) Then the cube root of 1 would be: k = a (q-1)/3 = 1 1/3 (mod q) Instead of finding a primitive root of 1, one could directly find a cube root of 1, this is faster: k = (-1-sqrt(-3))/2 (mod q) Do the same modulo the order of the curve m: b≠1 b m-1 = 1 (mod m) λ = b (m-1)/3 = 1 1/3 (mod m) Then check which one matches: [λ](x,y) = (kx,y) β = k or [λ](x,y) = (k 2x,y) β = k 2 (mod q)
|
|
|
This is a segwit transaction. Remove the marker, flag, and witness. https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#user-content-Transaction_ID nVersion: 01000000 marker: 00 flag: 01 txins: 010000000000000000000000000000000000000000000000000000000000000000ffffffff5e03e7610c0446f724652f4d41524120506f6f6c2ffabe6d6d621175c7c1371ebd43cefcefc3ab0453b7f952101cb5575976420d0104e9f0dd01000000000000006ffead5c76d2571ade6aa17dc7be6bde12b33031f30094000000ffffffffffffffff txouts: 02c2c0e825000000001976a9142fc701e2049ee4957b07134b6c1d771dd5a96b2188ac0000000000000000266a24aa21a9edaf182da3eb02887057bacf92ae319a024020f02c8d50537fe33f45f1c922e08d witness: 01200000000000000000000000000000000000000000000000000000000000000000 nLockTime: 453007e0
|
|
|
One we have quantum computers of 4000 Qubits, things will get tough for current security protocols.
You are off several order of magnitudes. If they somehow make quantum error correction work, then it's more like 15000*4000 = 60M qubits. For 256-bit ECDLP the lowest logical qubit count is around 2330, giving 35M physical qubits. There is a big problem - one also needs 126G Toffoli gates. Additionally, the algorithm has to perform 116G time steps. If the time step is 1ps, then there might be even a correct result! With 1ns we are looking at 116 seconds runtime, enough for decoherence. AFAIK right now the time step is several hundred nanoseconds. This is several hours runtime. No result possible. Wait a moment! Error correcting Toffoli gates needs additionally at least 15 logical qubits. This is 225K qubits per Toffoli gate. All together 28.35 * 10 15 qubits. Even if the above is off by orders of magnitude, for now, all quantum hope is lost.
|
|
|
"Super-singular elliptic-curve isogeny cryptosystems" has been broken classically, isn't it? There are no "Quantum Computing Threats". QC simply couldn't scale exponentially, and no workarounds would "enable" it. It all comes down to the noise, the random events altering the energy and space. There's no way to hide from it. Random gravitation pulse, a single neutrino passing, and it's all gone. Somebody making a step far away - all gone. If 256 bit private key is to be found - somebody laughs on the other side of the Earth - all gone. Most of the time such system have to represent at least 2 256 states simultaneously... well, even if it was 2 128 the noise eats it all. Some people put hope into "quantum error correction". Unfortunately the error correction system, while canceling some noise, produces more of it, since the process takes time and space. The more time passes - the more noise is accumulated. The bigger space a qubit "occupies", the more noise as well. It would be wonderful if I'm wrong, but for now the above looks correct.
|
|
|
So put simply, the only way to see if 2 identical addresses exist in any bit range with different private keys is to have all the 2^160 addresses in a file to compare for collisions when we brute force any range. There might be other ways but to be 100% sure that's the only way, even to find one collision?
Sorry if I ask stupid questions, my head is not clear past few days. As always thank you all so much for the time you spent to answer.
Let's first try to see if there is an "impossible" address, that is - no public key maps to that address. 1. When randomly mapping a n-bit number x to n-bit number y, the probability of having k distinct x-es mapping to y is e -1/k! 2. Starting with a private key (256 bit) we map it to public key, then sha256, and finally ripemd160. This is 256 bit to 160 bit random mapping. 3. Fixing the 96 MSB of the private key we get 160 bit to 160 bit mapping. The probability of not reaching y is e -1. 4. We repeat this for every possible 96 MSB. The probability of not reaching y every time is (e -1) 296 = e -296 < 2 -114302077158074026402637675936. Well, we could safely say there's no such address. Let's try to see if there is an address to which points only single public key. The probability of having zero mappings is the same as having one mapping: e -1(e -1) 296-1 = e -296We get the same number as above. There is no address with a single public key. We expect the number of public keys pointing to that address to be quite close to 2 96. --- Now let the private key lays in certain 160-bit interval (or is in a random set of 2 160 distinct private keys). The probability of not reaching an address y is e -1 ≈ 36.8% The probability of reaching an address only once is the same. The probability of collision is 1-e -1-e -1 ≈ 26.4% --- Hopefully this brings some clarity. For info on the math leading to these results one could look at the article "Random Mapping Statistics", or the book "Analytic Combinatorics".
|
|
|
... So for three years now with approximately 366 days then the block need for 3 years will be 52704 blocks. 808139+52704=860843.
Your math is off, 52704 blocks appear in one year (or so). You could check it yourself 808139-52704=755435, which happened on 24th September last year. If we set 210000 blocks per four years, then three years would be 157500 blocks. Indeed block 808139-157500=650639 was mined on 2020-09-30.
|
|
|
Because, it is not guaranteed that such information will be safe from future kind of attacks, for example, we all know that quantum computers will be able to defeat ECDSA and use the transactions of public keys to get the private key back without even using any WIF characters, so why make the OP take an unnecessary (even if its theoretically unpractical) risk?
How do you "know" about QC? Did you try understanding all the formulas? I did look into it, and now I really know that quantum computers are destined to utter failure. Quantum computing is a scam. It will never be able to do anything meaningful, besides generating noise.
|
|
|
But anyway what do you think about the goal of this anomaly?
There is no anomaly, since in secp256k1 all points (except the one at infinity) are equal. No point is more equal than others. It seems as an easy way to check if your implementation is mostly correct - you try multiplying by 1/2, and then receive small x coordinate. Many things have to be implemented accurately, and any deviation would show up.
|
|
|
UTXO are stored in chainstate subdirectory, which is a LevelDB database, currently ~4.8GB.
One could control how much of it is cached by the command line parameter "-dbcache". It might be useful to make it high enough during IBD (initial block download). Note that high dbcache leads to slow shutdown of Bitcoin Core. Other than during IBD, AFAIK, high dbcache is useless.
There are no private keys in UTXO. Or if there ever were, it's all gone.
|
|
|
Ok, lets to to write it by parts using openAI ... addq num2(,%rax,8), %rdx ...
As usual, the so called AI gave wrong result. The carry flag is completely ignored, so instead it adds two vectors, each having four 64bit numbers.
|
|
|
|