Hot answers tagged

68

Unfortunately, given the public's limited of understanding of cryptography this is apparently an easy fraud to pull off. The key trick is that non-technical people are prone to believe things that just sound jargony enough and that technical people tend to think they know a lot more than they actually do-- and so they're easily sent off into the weeds. In ...


33

There are two different encodings used. Everything in the Bitcoin protocol, including transaction signatures and alert signatures, uses DER encoding. This results in 71 bytes signatures (on average), as there are several header bytes, and the R and S valued are variable length. For message signatures, a custom encoding is used which is more compact (and ...


32

I'll try answering this again in a different way, using small numbers to keep it readable. convert the private key to binary representation, so decimal number 105, which is 0x69 in hex, becomes 01101001. calculate this list of points, by repeatedly doubling the Generator point G: 1*G 2*G = G+G 4*G = 2*G + 2*G 8*G = 4*G + 4*G 16*G = 8*G + 8*G 32*G = 16*G + ...


28

This has nothing to do with RFC6979, but with ECDSA signing and public key recovery. The (r, s) is the normal output of an ECDSA signature, where r is computed as the X coordinate of a point R, modulo the curve order n. In Bitcoin, for message signatures, we use a trick called public key recovery. The fact is that if you have the full R point (not just its ...


23

ECDSA signatures are pairs (r,s) where r=(kG).x mod n, and s = (m + rx)/k mod n, where x is the secret key, k is the random nonce, and m is the message. If you have two s values s1 and s2 for the same secret key and with the same nonce k (and thus the same value r), the following holds: s1 = (m1 + r*x)/k s2 = (m2 + r*x)/k From that we can derive: s1 * k =...


18

If you want, you can pay $100 for the standard, ANSI X9.62. Or, you can cheat and look at RFC3278, section 8.2. It is in DER format consisting of a SEQUENCE of two INTEGERs. The first INTEGER is r, the second s. If you look at this transaction you can see that one of the signatures is: 3045 0220 ...


16

Based on the time-frame and my impression of the capabilities of the various groups developing wallet software during that period my initial guess was that the Bitpay copay software might be the source of these signatures. Copay is a multi-signature wallet which was initially released around that time. As I'm not a javascript developer it took me a bit of ...


13

Install OpenSSL. When the executable in your path, enter this command to generate a private key: openssl ecparam -genkey -name secp256k1 -noout -out myprivatekey.pem To create the corresponding public key, do this: openssl ec -in myprivatekey.pem -pubout -out mypubkey.pem This will give you both keys in PEM format. I'm not sure what format the web page ...


13

Here is a fun thing about ECDSA signatures: you can always replace s with -s (mod N) and the signature is still valid. So when you are deducing the k value, it is possible that someone else flipped the sign of s and you will have to undo it. So, you have to make a list of candidates for k (kandidates?) and then select whichever one actually works. A good ...


11

My guess is that Satoshi did not know about the internals of ECDSA signatures, and simply used what OpenSSL gave him. If it didn't require a hard forking change (requiring every wallet and verifying node on the network to upgrade), we'd have changed it long ago.


11

I'm not sure why you think RSA is much safer than ECDSA. As you can read here: https://crypto.stackexchange.com/questions/3216/signatures-rsa-compared-to-ecdsa ECDSA offers same levels of security as RSA, but with a much smaller footprint. In fact, the more you increase the security, the larger the RSA keys become compared to ECDSA. This makes RSA less ...


11

The all-zero bitstring doesn't have a corresponding public key per the standard (according to "Are all possible EC private keys valid?" on Crypto.SE), so it's 000…001.


10

note: what Nils Schneider calls 'z', i call 'm'. this gist implements all this: https://gist.github.com/nlitsme/dda36eeef541de37d996 the calculation ecdsa signing is done as follows: given a message 'm', a sign-secret 'k', a private key 'x' R = G*k (elliptic curve scalar multiplication) r = xcoordinate(R) s = (m + x * r) / k (mod q) q = the ...


10

Let us take "pizza transaction" https://blockchain.info/tx/cca7507897abc89628f450e8b1e0c6fca4ec3f7b34cccf55f3f531c659ff4d79 ...


10

Yes it's a lot faster. For example from one of the core developers: reddit - Pieter Wuille / 2015-02-19 18:13 Just did a benchmark on libsecp256k1's current master, without GMP, without hand-written assembly, and it's around 3.6x faster than OpenSSL on my machine (64-bit code, i7 cpu). When the assembly is compiled in (which does not require any ...


9

The basic elliptic curve operation is addition of points. The operation of applying this addition repeatedly is called the scalar multiplication of a point by an integer. The private key is the 'scalar', the point being multiplied is the 'Generator' point, the result is the public key. Scalar multiplication is basically repeated addition. Multiplying the ...


9

Canonical DER signature implemented in BIP 66 fixes issue #1 of BIP 62 ( Non-DER encoded ECDSA signatures ) Amacilin's code exploits issue #5 in BIP 62 ( Inherent ECSDA signature malleability ), and is explained here : https://github.com/bitcoin/bitcoin/commit/a81cd96805ce6b65cca3a40ebbd3b2eb428abb7b This issue was fixed by requiring signatures to have ...


9

No, ECDSA and EC-Schnorr, as well as related schemes like EdDSA, all belong to the class of elliptic curve cryptography. Their security is based on the assumption that the EC discrete logarithm is unfeasibly hard to compute. This assumption is not true if a sufficiently strong general purpose quantum computer would exist. Quantum resistant signature ...


8

A private key is just a number modulo the order of the curve. A public key is the (X,Y) coordinate pair corresponding to that number (the private key) multiplied by the base point (which is a property of the curve used). If you're talking about public keys: you're almost right. The Y coordinate can indeed be computed from the X coordinate, if you know the ...


8

Not any serious efficiency concerns. Signing is done fairly infrequently for any particular client (only a few signatures per transaction usually). While possible that the signing might take slightly longer to generate the k value, it would not be noticeable, especially considering how infrequently it is used by any one particular client. It's the ...


8

Simple, the sender shows the pubkey when spending from whatever address the bitcoins are in. As part of the verification, the receiver (actually, every node in the network), can verify that the pubkey hashes to the address given and then and only then verifies the signature.


8

Schnorr will replace ECDSA, the signing algorithm, but both still use the same elliptic curve and thus the same public and private keys, etc. Regardless, compatibility with ECDSA must be kept too even if Schnorr is used, because otherwise all old nodes would see the schnorr signatures as invalid signatures, and all old transactions would be seen as invalid ...


8

One is the minimum number. [This space intentionally left unblank.]


7

k is just a scalar, modulo the order of the elliptic curve group. Q = k*P thus: (1/k)*Q = (1/k)*k*P thus: (1/k)*Q = P You find P by multiplying Q with the multiplication inverse of k modulo the curve order.


7

First, you need to understand what the two formats actually are. The first is the compressed SEC format and the second is the uncompressed SEC format. The difference between the two is that the compressed format only includes the X value and the parity of the Y value while the uncompressed format includes both the X and Y values. The 02 at the beginning of ...


7

A signature in Bitcoin (as used to sign transactions inside scriptSigs and scriptWitnesses), consists of a DER encoding of an ECDSA signature, plus a sighash type byte. Overall, this means they consist of: DER encoded signature data, consisting of: 1-byte type 0x30 "Compound object" (the tuple of (R,S) values) 1-byte length of the compound object The ...


7

Secp256k1 was designed to be a 256-bit size elliptic curve without cofactor and admitting an efficient endomorphism for optimization purposes. The choices of the relevant parameters are derived from these criteria. P is selected allow a more efficient implementation on general purpose computers. See Solinas' paper on Generalized Mersenne Numbers. We don't ...


6

In short, yes, Bitcoin would be vulnerable to some variation of Shor's algorithm and quantum computing, as would basically every kind of crypto we use today. While ECDSA uses the elliptic curve discrete logarithm problem for its security, rather than the prime number factorization problem, you are correct in stating that a variant of Shor's can be used to ...


6

Bitcoin uses SHA256 followed by RIPEMD-160, which I'll collectively call HASH160. Good hashes have 4 properties: it is easy to compute the hash value for any given message it is infeasible to generate a message that has a given hash it is infeasible to modify a message without changing the hash it is infeasible to find two different messages with the ...


6

Verification w/ Public key recovery is never going to be faster than normal verification however it is only marginally slower. I benchmarked it a while back and PubKey recovery added about 5% overhead. Changing the txn format would require a hard fork so it is unlikely that is going to happen but the advantage of pubkey recovery is that it trades storage ...


Only top voted, non community-wiki answers of a minimum length are eligible