A bit off-topic but...
SAGE seems to have represented these finite fields and curves & operations really well. It would be nice if this functionality could be had in other languages as well - especially C-C++ where there are many applications for this kind of thing because of its raw speed, but are hard to implement because all the crypto libraries for these languages are half-arsed or incomplete (libsecp256k1 is the closest that replicates SAGE stuff but a general-purpose curve and field library would be a nice to-have).
I have used PARI/GP C library The following is with the provided gp shell (some empty lines omitted): gp > ellgroup(ellinit([0,7]), 2^256 - 2^32 - 977)
%1 = [115792089237316195423570985008687907852837564279074904382605163141518161494337]
gp > factor(%1[1] - 1)
%2 =
[ 2 6]
[ 3 1]
[ 149 1]
[ 631 1]
[ 107361793816595537 1]
[ 174723607534414371449 1]
[341948486974166000522343609283189 1]
The easiest for me was doing pari_init_opts, then (after recording avma) using gp_read_str with corresponding string (instead of interfacing each and every function), and then pari_sprintf("%Ps",...) to get the result as text (then recovering avma), and parse it to something meaningful. Couldn't find a function returning the multiplicative order of point though. |
|
|
|
hello there i have my own bitcoin address and public key and a WIF recognized as invalid this txt file was old and recovered from my old HDD i assume that the wif has more than 19 missing characters at known positions is there is any chances that i can recover it ?? any guiding help will be appreciated  The Missing Characters ( Replaced By * ) Are as Follows :
5HpHagT65TZzG1P*********************EB3kEsreAnchuDf
Assuming you manage to tweak Pollard Kangaroo (don't know if it's possible, looks kinda tricky), here are the expected run times and cost (on-demand, spot instance could be 1/3rd of the price) when using AWS GPU instance p3.8xlarge (4x V100): MC - missing characters, bits - equivalent missing bits | | | MC | | | bits | | | ETA | | | $ | | | | | | 14 | | | 82 | | | 00:11:17 | | | 2 | | | | | | 15 | | | 88 | | | 01:25:53 | | | 18 | | | | | | 16 | | | 94 | | | 10:54:07 | | | 133 | | | | | | 17 | | | 100 | | | 3d 11:01:37 | | | 1,016 | | | | | | 18 | | | 105 | | | 26d 08:18:52 | | | 7,740 | | | | | | 19 | | | 111 | | | 200 days | | | 58,942 | | | | | | 20 | | | 117 | | | 4 years 68 days | | | 448,893 | | | | | | 21 | | | 123 | | | 32 years | | | 3,418,664 | | | | | | 22 | | | 129 | | | 242 years | | | 26,035,770 | | | | | | 23 | | | 135 | | | 1849 years | | | 198,282,544 | | | | | | 24 | | | 141 | | | 14083 years | | | 1,510,074,752 | | |
This was using my software (not published), Jean_Luc should be faster (50%?), newer hardware should be faster as well. |
|
|
|
You got mistaken somewhere (or, as usual, in many places). Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic. Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one. You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other. |
|
|
|
No look, bitcoinsig.js that is used in the "brainwallet.github.io" sites has this in the verificaiton algo:
verify_message follows this algorithm ECDSA Public key recovery. The function calling verify_message sets the first byte of signature to 27..34. This corresponds to the eight cases, two for x (x or x+n, bit zero of recid), and two for y (y or p-y, bit 1, zero for even y, one for odd y), uncompressed or compressed (if first byte is >= 31). At the end it returns the address of decoded public key. You could see how Bitcoin Core does sign here |
|
|
|
To find square root mod p when p%4 = 3 (prime of secp256k1 curve is like that) you can compute x(p+1)/4 (mod p) instead.
I'm trying to grok my head around this. We have y^2 = x^3 + 7 so before I wrote this topic I had the idea that the next statement took the 4th root of Right Hand Side (power by p+1 is equivalent to just 1, and I had the belief that coord^((p+1)/2) was equivalent to taking the square root - since we clearly cannot raise by the fractional power 1/2, but (p+1)/2 is equivalent to that). In other words, (y^2)^((p+1)/4) would've been sqrt(y) not y. It's like in algebra how you apply the first sqrt and then you have (y)^((p+1)/2). But apparently the p+1 is to ensure that modulus is zero, i.e. (p+1) % 4 = 0, and then the division by 4 is done. So how is dividing this shifted prime by 4 equivalent to a square root? Is it because we are now taking the modular power by a whole number? Then why 4 specifically and not some other number? It all comes from Fermat's little theorem: y p = y (mod p) then y p+1 = y 2 (mod p) y (p+1)/4 = y 1/2 (mod p) You could do similar stuff for cube roots as well: x p+2 = x 3 (mod p) x (p+2)/9 = x 1/3 (mod p) |
|
|
|
This is the main disadvantage of HTLC: When used to secure multiple payments (e.g. a routed LN payment or an atomic swap), all payments use the same preimage and hash lock. This creates a link between those payments if they’re published onchain or if they’re routed offchain though surveillance nodes.
Also using the same hash gives surveillance information for a single payment as well, by revealing parts of the path. In contrast PTLC: Each point lock can use different keys and signatures, so there is nothing about the point lock that correlates different payments either onchain or when routed offchain through surveillance nodes.
|
|
|
|
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) |
|
|
|
Why this value can be rotated like in a clock?
...
Are there other such values? How to get them? Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves? Also, it is true for "n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?
There are many such values. Eventually what are you looking for is Primitive root modulo n. From it you can get every possible root of 1. Here is an algorithm for finding a primitive root modulo prime p (that is (p-1)-th root of 1): r = 1
factors = factor(p-1)
for [prime, power] in factors:
x = (p-1)/prime
y = (p-1)/(prime ** power)
for (a=2;;a++):
b = pow(a, x, p)
if (b != 1):
r = (r * pow(a, y, p)) % p
break
( prime ** power = prime power) Modulo p we get the following roots: 2 (square), 3 (cube), 7-th, 13341, 205115282021455665897114700593932402728804164701536103180137503955397371, and any multiple of these numbers, for a total of 2 5-1 = 31 possible roots (2nd, 3rd, 6th, 7th, 14th, 21st, 42th,...). Each k-th prime root has k-1 possible values besides 1. However if k is composite, some of the k-1 values are the corresponding smaller root, i.e. if a is 6-th root of 1, a 3 would be square root of 1, and not 6th. Modulo n we get the following factors (and roots): 2 6, 3, 149, 631, 107361793816595537, 174723607534414371449, 341948486974166000522343609283189. 7 * 2 6 - 1 = 447 possible roots. Your example is for 2 2*3=12-th root. Here are two primitive roots of 1 modulo the corresponding prime: n: rn = 106331823171076060141872636901030920105366729272408102113527681246281393517969
p: rp = 77643668876891235360856744073230947502707792537156648322526682022085734511405
So, let's say you want a 631th root of 1 modulo n: x = pow(rn, (n-1)/631, n). Since 631 is prime number, you could get all 631 possible 631-th roots of 1 (modulo n) by rising x to the power from 1 to 631. |
|
|
|
Cooling is solved. You place desalination facilities in the coast region, then you build pipelines into the deserts. Because not only do you need cooling, you also need water for all the inhabitants of those new mining oasis. And you need to clean the panels.
What about sandstorms? A single sandstorm could burry the whole mining facility. And they become more and more frequent. |
|
|
|
Quantum computers cannot reduce anything. Quantum computers are just a scam hidden behind weird probabilistic equations, which are very conveniently excluding almost all real life noise. Quantum computers are so weak, that cannot factor a 6-bit number using the almighty Shor's algorithm - which "breaks ECDLP" - the number 35 turned out just too big for reliable factorization
Quantum Computers do not equal Shor's algorithm. I'm pretty sure if they really wanted to they could factor something bigger than 35 though. We're way past that. Please show me anything quantum, that could factor big numbers (or even small); besides the obvious random search (adiabatic, annealing, etc), which doesn't scale, and is in fact faster on classical computers. Who is this "we"? All I see is random buzzwords and utter failure. They wanted to factor, and failed miserably. Now there are 127 qbit computers. And they cannot factor 6 bit numbers. Repeating buzzwords doesn't make it truth. |
|
|
|
160 bit hash in addresses provides enough security, and that's the important part.
Right now it does. But not eventually. Quantum computer can reduce that to 80 bits. Quantum computers cannot reduce anything. Quantum computers are just a scam hidden behind weird probabilistic equations, which are very conveniently excluding almost all real life noise. Quantum computers are so weak, that cannot factor a 6-bit number using the almighty Shor's algorithm - which "breaks ECDLP" - the number 35 turned out just too big for reliable factorization. |
|
|
|
There cannot be more than 128 bits entropy in BIP39 12-words. There are not enough bits to represent it.
If you have selected each word manually and randomly and you have 12 words then each word represents 11 bits which makes the total 12*11=132 bits. Yes, it is 132 bits, but only if there's no checksum or required version. It very much affects the entropy, since 255 (or 4095 in segwit case) possibilities are rejected (plus the valid BIP39 ones, about one in 16, another loss of additional 0.0931 bits of entropy). You end up with smaller pool of possible seeds, hence smaller entropy. It seems that entropy is a very tricky subject for many people. I'll give an example. Let's have a hypothetical seed generator, which starts randomly, and increments until it reaches only one specific seed. This is exactly 0 bits of entropy. If the generator stops when it reaches one of 2 seeds, we get 1 bit entropy. If an attacker has no information about these seeds, then he has to scan the whole 256 bit range (or whatever size it is in this case). So, valid electrum seeds do have less entropy - 123.9 bits for standard, and 119.9 bits for segwit. That doesn't mean it's much easier to crack versus BIP39. If my calculations are correct, it's about twice harder to find a valid Electrum segwit seed versus both Electrum standard and BIP39. (if we are given an address to compare to) In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Certainly only one in 2 4 seeds are valid for BIP39, in 2 8.09 for Electrum standard, and in 2 12.09 for Electrum segwit. Hence the entropy is lower. One might argue, that the attacker sees 132 bits of entropy, since nothing is certain for him. Then this is true for BIP39 as well, although it is generated using 128 bit entropy. Looking the other way if one insists BIP39 to have 128 bits entropy, then Electrum standard has 123.9, and segwit 119.9. |
|
|
|
Which means that one must "preselect" another 3 bits. It would look like selecting the last word, taking it's 3 bits and then replace the last word by the final one.
Unfortunately you cannot finish the manual process after 23 words.
Other option is to see which of 8 "correct" last words you like the best.
Exactly, another solution would be doing something similar to what Electrum does. You select 12 words and then increment the last word until you get a valid checksum. As long as the selection process is really random the entropy you get is more than 128 bits. Same for any other word count. There cannot be more than 128 bits entropy in BIP39 12-words. There are not enough bits to represent it. Electrum 12-word seeds have less than 128 bits entropy, IIRC it's slightly less than 132-8=124 for legacy addresses, and 132-12=120 for segwit addresses. More entropy could be inserted, if you instead of using the 12 words directly mutate them with additional entropy. For example: make some letters lower case, while other upper case, change some words to "leet speak", etc. And then feed this into PBKDF2. Of course, the easiest method of adding entropy is using password together with the seed. |
|
|
|
To be more precise, we may say that if unknown word is on the last position, could be treated as a checksum word (word which contains binary checksum), then the rest (23 words) produce 8 possibilities at the last position.
Assuming the first 23 words are known, there are 8 possibilities for the last word on average. It's not that there are always exactly 8 possibilities for the last word. There are always exactly 8 possibilities for the last word for BIP39 (in the 24-word case). Last word represents 11 bits, 8 of which are checksum. For every of the 3 bits we choose, there is always exactly one word with the needed checksum bits. |
|
|
|
Additionally the new difficulty is constrained to be between [1/4, 4] times the old one. And cannot be less than 1.
new_difficulty = max(1, old_difficulty * min(4, max(1/4, (20160 / time_elapsed_for_last_2015_blocks))))
In the source actually the new target is calculated, which might give slightly different result than above formula due to rounding.
And that's done with 256-bit integers, or with proper doubles? The rounding error shouldn't be that large if the difficulty is stored as an int with 256 bits, as the effect that the lowest bits of the difficulty have on the total hashrate at any given time is negligible. Looked again and remembered, that the target is always represented as a "compact" number (32 bits, similar to float), so double should have enough bits. Possibly double arithmetic should be done in specific rounding modes though. Then again - compact representation has only 23 significant bits, plus 8 bits exponent (and one sign bit). Instead of being power of 2, the exponent is power of 256. So things still might differ. Even more than I expected. |
|
|
|
The actual formula is new_difficulty = old_difficulty * (20160 / time_elapsed_for_last_2015_blocks). 2015 blocks is a bug that will probably never be fixed.
Additionally the new difficulty is constrained to be between [1/4, 4] times the old one. And cannot be less than 1. new_difficulty = max(1, old_difficulty * min(4, max(1/4, (20160 / time_elapsed_for_last_2015_blocks))))In the source actually the new target is calculated, which might give slightly different result than above formula due to rounding. |
|
|
|
i think you might be assuming sha256 is a one-way function. it might not be. and thus there could be an easy way to reverse it that no one ever though of yet.
It is and it will always be impossible to reverse hashes until the end of time, this is even true for non-cryptographic hash functions like MurmurHash. That's for a very simple reason: math. Well, 90 years ago Kurt Gödel proved such absolute statements are false. That said - and thanks to bitcoin - we would never know if one is capable to easy reverse hashes. If NSA and similar cannot do it yet, then they would never be able to. Anybody coming close to an answer would be very incentivized to keep it to himself, and never ever share. |
|
|
|
You only need to roll a dice 99 times to get a 256-bit number. Which gives you a bitcoin private key. Given that 4 out of the 6 results add 2 bits and 2 out of the 6 results add 1 bit, then each dice roll gives on average ~1.66 bits. That's 256/1.66 = ~154 times. But, there's no reason to do this for a bitcoin private key and not for a seed, which will then generate infinite keys. This looks very wrong. Rolling a dice gives certainly more than 2 bits uncertainty, since 2 bits is one of 4 choices, while the dice is one in 6. The correct way of calculating it is log26 = 2.5849...Indeed 256 bits of uncertainty is very slightly more than 99 dice rolls. You are loosing information when ignoring that there are 2 more choices in the first case, and 4 more in the second. It is easy to do a check: write down the number 555..5 (99 times) in base 6, and convert it to hexadecimal (base 16). The result is very close to 2 256F0BB8A1BBDE9163B9E053E8F918BF8E4D34034D7FFFFFFFFFFFFFFFFFFFFFFFF One more roll makes it overflow (100 rolls) 5A4653CA673768565B41F775D6947D55CF3813D0FFFFFFFFFFFFFFFFFFFFFFFFF Look at it this way: rolling 2 dices gives one in 36 choices, which is more than 5 bits (1 in 32). Using your scheme we get at most 4 bits, and sometimes even 2. |
|
|
|
You could use the method for comparing two jacobian points directly. (xa, ya, za=1) and (xj, yj, zj) xa / za^2 = xj / zj^2
ya / za^3 = yj / zj^3
xa * zj^2 = xj * za^2
ya * zj^3 = yj * za^2
which becomes
xa * zj^2 = xj
ya * zj^3 = yj
No inversion, so this is considerably faster. It depends on how many affine points you want to compare to. In the above case each check costs two multiplications (since we compute zj^2 and zj^3 once). It might be cheaper to convert the point to affine, and just compare. Additionally the known public keys might be organized in a radix tree for even faster comparison, which is not possible in jacobian coordinates. |
|
|
|
|
Show Posts
