Hot answers tagged

43

I'm considering switching to ECDSA, would this require less space with the same level of encryption? The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels. If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security ...


33

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it. It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that ...


33

Ed25519 is a specific instance of the EdDSA family of signature schemes. Ed25519 is specified in RFC 8032 and widely used. The only other instance of EdDSA that anyone cares about is Ed448, which is slower, not widely used, and also specified in RFC 8032. Keys and signatures in one instance of EdDSA are not meaningful in another instance of EdDSA: Ed25519 ...


32

Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$. This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed. However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two ...


32

What you seem to be looking for is deniable authentication. This is actually a somewhat stronger property than what you're asking for: it guarantees that the recipient (let's call him Bob) cannot cryptographically convince anyone else that the sender (let's call her Alice) signed the message, even if he discloses all his private keys, simply because the ...


31

The distinction is that ECDSA solves a problem that HMAC does not. If you need that problem solved, then you need to do ECDSA rather than HMAC; if you do not, then HMAC works just as well (and is a lot cheaper). With HMAC, here is what we have: we have an authenticator that has a secret key. It takes a message, and gives that (and the secret key) to the ...


27

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid ...


25

All points on an elliptic curve verify, by definition, the curve equation, usually written as $Y^2 = X^3 + aX + b$, with two given $a$ and $b$ parameters (these two parameters actually define the curve). So, if you know $X$, you can use the curve equation to recompute $Y^2$. A square root extraction will yield $Y$ or $-Y$. The compressed point format ...


20

It is possible to view DSA/ECDSA as an identification scheme (like Schnorr) but with a different variant of Fiat-Shamir. This gives the intuition that you are perhaps looking for. I will include an excerpt from Intro to Modern Cryptography 2nd edition (Section 12.5.2) which gives this explanation: Begin Excerpt -- Section 12.5.2 DSA and ECDSA The Digital ...


16

To add to poncho's answer (since they beat me to it!), there are several advantages to choosing HMAC over ECDSA (or RSA) if you can get away with it: Insanely better performance: signing and verifying is much faster Much simpler implementation: this is important for security (even if you're not the one doing the implementation), since more complexity leads ...


16

As already said by fgrieu in his answer, this is possible. There are multiple ways to protect deterministic ECDSA against fault attacks, but these ways will depend on your fault model. If you consider only a single fault model, then any construct requiring the attacker to perform two faults to achieve his goal will be an acceptable countermeasure... On the ...


15

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security: In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard Ed25519 is extremely similar to EC-Schnorr, and both ECIES and ...


15

The main reason is historical (and a bit sad). ECDSA can be seen as a repurposed authentication mechanism. The private key owner wants to prove knowledge of the private key $x$ that matches a given public key $Q = xG$, but without revealing that private key. Thus, this is organized as a three-step protocol: The prover makes a commitment on a newly ...


14

SafeCurves lists some ways to compare the security of elliptic curves. Their security criteria are split to "ECDLP security" and "ECC security". Failing the former basically means "there is no way to use this curve securely in general" while the latter "it is difficult to implement this curve securely". None of the (few) BouncyCastle-supported curves that ...


14

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing. Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name. Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the ...


14

Lets say Alice wants to send Bob a sensitive message, she wants to prove to Bob that it came from her, but she doesn't want Bob to be able to prove that to anyone else. A MAC is a good way of doing this. If Alice and Bob share a MAC key (and only they have it) then Bob will know any message authenticated with that MAC key came from Alice, since he knows he ...


13

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good ...


13

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key. Huh? I see two problems with the above statement; "Encryption"; using the word encryption implies that there's a way somehow to decrypt it. However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash....


13

Partially covered by does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448? but to add a little, rfc8032 describes EdDSA's advantages as: EdDSA provides high performance on a variety of platforms; The use of a unique random number for each signature is not required; It is more resilient to side-channel attacks; EdDSA uses ...


12

On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ...


12

An ECDSA signature consists of two integers that can range between 0 and $n$, where $n$ is the curve order. For secp521r1, the curve order is just a shade under $2^{521}-1$, hence it requires 521 bits to express one of those integers, or 1042 to express two. 130 bytes would not be sufficient, as that has only 1040 bits. 131 bytes would suffice; however ...


12

There are three use cases where RSA beats common ECC algorithms, such as ECDSA: Signature with verification frequent or/and by low-power devices. The verification cost of $n$-bit RSA with usual public exponents is $O(n^2)$, but the verification cost of ECC-based signatures is $O(n^3)$ (using usual algorithms). Together with simpler math, that's why RSA can ...


12

The ASN.1 DER format is deterministic; i.e. there is only a single sequence of bytes that validly encodes given $r$ and $s$ values. Mind the details, though: the encodings of $r$ and $s$ are minimal-sized signed big-endian. Since $r$ and $s$ are positive values, this means that the top bit of the first byte of each encoding must be zero. In your example, the ...


11

Well, lets go through the issues: It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone Nope, not quite. You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a ...


11

As @poncho says, both keys $Q_1=r^{-1}(sR-zG)$ and $Q_2=r^{-1}(sR'-zG)$ will validate the given signature, i.e., $(s^{-1}zG+s^{-1}rQ_i)_x=r\mod{n}$. For some curves, with small but non-zero probability, we have $n\leq(kG)_x<p$, and neither $Q_1$ nor $Q_2$ will validate other signatures made with the original private key $d$. However, by Hasse's theorem, ...


11

No, in general the hash isn't determined by the curve definition by NIST. Reasonable mappings of course exist (for a 224 bit curve you would probably use a hash with output size of 224 such as SHA-224). The hash used should however be specified by the protocol itself. The ECDSA key size as indicated by the -b of the openssh argument is linked to the hash ...


11

Deterministic signatures are safe in the random oracle model. Using HMAC_DRBG allowed me to rely on existing research on the safety of that construction and how close it comes to a "true" random oracle. If I had used any other "handmade" construction, then I would have had to provide extensive analysis on why it is secure. Being naturally lazy, I chose ...


11

The best option is to avoid doing so as much as possible. Ideally, your language of choice will offer a wrapper around a battle tested library such as libsodium (or maybe bearssl one day). Additionally, in a perfect world, the interface that the library/wrapper provides should be designed to make it difficult if not impossible for you as the developer to ...


11

From the source code: function createKeySigner(bits) { return function sign(thing, privateKey) { if (!bufferOrString(privateKey) && !(typeof privateKey === 'object')) throw typeError(MSG_INVALID_SIGNER_KEY); thing = normalizeInput(thing); // Even though we are specifying "RSA" here, this works with ECDSA // keys as well. ...


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