12

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 ...


12

secp256k1 fails the following SafeCurves criteria, but it doesn't matter for Bitcoin's use of secp256k1: CM field discriminant. secp256k1 is a Koblitz curve that admits a fast endomorphism for speeding up scalar multiplications. There is no particular vulnerability here: the same speedup you get in computing with secp256k1, an adversary gets in trying to ...


11

What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure? The New Directions In Cryptography paper introduced the idea of public-key cryptography (though it had been proposed by Merkle before), and public-key cryptography was intended to solve two ...


11

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 ...


11

Having a cofactor $h > 1$ does not inherently provide an advantage; in addition, it has these small disadvantages: It reduces the expected effort of an attacker to solve the ECDLog problem by a factor of $\sqrt{h}$ (over a curve with approximately same size group order, and $h=1$) We then have to worry about "what if the adversary passes us a point that'...


10

There are two independent sources of equivalent public keys for the X25519 function. The first is rather simple: A public key is an integer u between $0$ and $2^{255}-1$ that represents an element of the finite field $\mathrm{GF}(2^{255}-19)$. Hence, for all $i\in\{0,\dots,18\}$, the integer $2^{255}-19+i$ represents the same field element as the integer $i$...


9

Sadly I'd like to know an answer for your first question as well. For your second question, you just need to see the difference between the description of a protocol and an actual instantiation of it (meaning, a cryptographic scheme). Diffie-Hellman is a cryptographic protocol, describing a way for two parties to exchange a common element in fixed ambient ...


9

(minisign author here) As noted by corpsfini, keys encode the Y coordinate. The X coordinate is recovered using the curve equation: X = sqrt((Y^2 - 1) / (d Y^2 + 1)). The square root has two solutions, so we need to encode the sign of x as well. Since coordinates only require 255 bits, we have a extra bit, used to encode the sign. X and Y ∈ [0; 2^255-19[, ...


8

As you said, you need to define the goals. You can take a look at SafeCurves, which is a joint work by Bernstein and Lange to help choose/construct elliptic curves w.r.t. ECDLP difficulty and ECC security. Note that if you need a pairing-friendly elliptic curve you need to look at other criteria related to the embedding degree. You can read this paper by ...


8

It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've recommended DH group 20-24 (we don't have DH group 24). Should we use these groups? NO, stick to groups 19-21 if possible! According to the linked resource, DH group 25 is a prime-based 192-bit elliptic curve and group 26 is a prime-based 224-bit ...


8

Yes! You can use the ephemeral key derivation mechanism that is for example used in Monero (they call it stealth keys there). Consider public key $A=aG$, with private key $a$. Then, a derived key can be generated, parametrised by the random scalar $r$: $$A'=H_s(rA)G+A$$ and the party that knows $a$ can use the public parameter $R=rG$ to compute their ...


8

Hash algorithms: Ed25519 uses SHA-512 (As referenced on wikipedia or on bearssl.org) Ed448 uses SHAKE-256$^1$ (As referenced on bearssl.org) $^1$ SHAKE-256 is a SHA-3 algorithm, a subgroup of the "Keccak" family.


8

If you follow the references in RFC 8446, you'll see that it cites RFC 8032 for the definition of the EdDSA-based algorithms. RFC 8032 in turn tells you all the details about the hash functions and other parametrization—field, curve equation, base point, encoding, signature equation, etc.—of EdDSA for Ed25519 and Ed448. There are several roles for a hash ...


8

The leading 04 byte is specified by the SEC standard (which is based on the ANSI X9.62 standard). It indicates that the public key point is not compressed. If the key is compressed, it uses 02 or 03 as leading byte depending on the lower bit of the y coordinate. EdDSA public keys do not use this byte for two reasons: It always uses compressed points; there ...


7

The best algorithm for computing discrete logs in a well-chosen finite field $\mathbb Z/p\mathbb Z$, where the safe prime $p$ has no structure that can be exploited by the special number field sieve, is the general number field sieve, or GNFS for short. The GNFS costs $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ bit operations, where $L = e^{n^{1/...


7

Yes, this is possible using Hierarchical Deterministic (HD) Keys. There are 2 variations for key generation, hardened and non-hardened. In hardened, generating child keys (both public and private) requires knowledge of parent private key but in non-hardened, child public key can be generated using parent public key. You need non-hardened key generation. The ...


7

You can think of the point at infinity as an extra point kludged into the set to make the curve work out as a group, but that's a little unsatisfying: in the geometric picture of a curve there's no place for the point at infinity, and in the algebraic construction the point at infinity is this weird magic object $\mathcal O$ with no coordinates. $$E := \{ (...


7

Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$. Fix an authenticated cipher $E_k$ of bit strings. In (EC)IES, roughly: A public key is a point $h \in G$. To encrypt a message $m$, the sender: picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random, computes an ephemeral public key $t = g^...


7

Suppose you publish a public key $P = [n]G$ for a secret scalar $n$, where $G$ is the standard base point. If you are willing to tell me $H([n]Q)$ given $Q = (x, y)$ for any coordinates $x$ and $y$ of my choice, then I can send you a point $Q$ of (say) order 2 on some other curve whose arithmetic law happens to coincide with the curve you meant to use, and ...


7

The secret $s$ in ECDSA is a value in the range 1 and the order of the group (exclusive). Some parameters are chosen in such a way that you can simply generate any value within the amount of bits as the chance that you're outside of the range or choose 0 is very small indeed. The public key is a point on the curve, calculated by performing $w = s \cdot G$ - ...


6

Yes, there is a point at infinity $O$ on Elliptic Curves (EC). Let the EC be given in Weierstrass equation; $$y^2 = x^3 +a x + b$$ $O$, the point at infinity can have different values according to the underlying coordinate system; Coordinate Systems For an elliptic curve over $\mathbb{F}_p$; In Homogeneous Coordinates (also known as Projective ...


6

The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves. The correct interpretation for this kind of curves is "adding their angles". It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful ...


6

Every elliptic curve over a finite field (and this includes Edwards curves; the use of projective coordinates $(X,Y,Z)$ has no relation to this) is a group isomorphic to $\mathbb{Z}_{n_1} \times \mathbb{Z}_{n_2}$ for two integers $n_1$ and $n_2$ such that $n_1$ divides $n_2$. In fact, if you have a curve over a finite field $K$ such that $r$ (prime) divides ...


6

RSA for key exchange is declining rapidly and is not recommended because it does not provide forward secrecy. Without forward secrecy, if someone breaks into the server and obtains the private key, they will be able to fully retroactively decrypt all recorded traffic encrypted under that key. ECDH does not have that problem because the private and public ...


6

This is not a bug: it arises from different choice of sign in the definition of a24 := (a ± 2)/4; the RFC uses - while the EFD uses +. RFC, following the Curve25519 paper: The constant a24 is (486662 - 2) / 4 = 121665 for curve25519/X25519 and (156326 - 2) / 4 = 39081 for curve448/X448. EFD, following Montgomery's paper (paywall-free): Assumptions: 4*...


6

Let $p = 2^n - c$. Then $2^n - c \equiv 0 \pmod p$, so $2^n \equiv c \pmod p$. Suppose you have an integer $$x = 2^n x_{\mathrm{hi}} + x_{\mathrm{lo}}.$$ Then $$x \equiv c\cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$ In other words, you can compute a reduction step by shift/multiply/add: shift right by $n$, multiply by $c$, and add to the low $n$ ...


6

There are concerns on curves defined over an extension field. In particular for those of a small extension degree. For a curve with a subgroup of prime order $r$, generally the best algorithm to solve the discrete logarithm problem has a complexity $O(r^{1/2})$. But there are attacks that use the structure of the extension field to get an algorithm with a ...


6

This is just a preventive measure. Without this separation, an attacker knowing ed25519ph(m) would also learn ed25519(h(m)). I'm not aware of any real-world protocol using both simultaneously and where that would be an issue, but it's not far-fetched to think that it could be the case. Domain separation is good hygiene and has become very common in new ...


5

Question1: Where is randomness coming from? The default secp256k1_nonce_function, when i pass in NULL is nonce_function_rfc6979. Obviously, there is no randomness involved when RFC 6979 is used. The title of that RFC is "Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)". In this case ...


5

In this case, the private key will be included in the site code and anyone can read it. No, the private key is not in the "site" code, it is not send. It is just used to authenticate the TLS session, by placing a signature that can be verified with the public key in the X.509 certificate. This certificate has been exchanged before in the handshake and it ...


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