13

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


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


10

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

(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

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

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


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

Information on how the specific base point was chosen is scarce. If you look at SEC1 (section 3.1.3.2), you will find a pseudo-random method in which a given seed is hashed (along with some parameters, in particular a counter value) into a bit string, which is then interpreted as the $X$ coordinate of the candidate point (if there is no valid point with that ...


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

I'm pretty sure this is an endianness issue. Specifically, taking the S_a value from the Josefsson draft and reversing the order of the bytes (i.e. pairs of hex digits) in it gives: 70076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c6a which is almost the same as the value of a given in RFC 7748 § 6.1. In fact, XORing the values shows that ...


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


6

One possible reason (and probably the one that was behind that design choice) is to avoid multi-target attacks. Consider a setup where there are $k$ public/private key pairs, and the attacker's goal is to find one of these private keys. The attacker does not care which private key is obtained; getting any of them is a "win". For instance, the attacker wants ...


5

No, Shamir's trick doesn't break ECDSA. Verifying an ECDSA signature involves evaluating a sum of scalar multiplications $[h s^{-1}]G + [r s^{-1}]P$. You can compute the scalar multiplications $[h s^{-1}]G$ and $[r s^{-1}]P$ separately and then add the results, but Shamir's trick does it more efficiently as a combined computation. This trick for ...


5

This is not a typo; it is a difference in how the Montgomery doubling formula was derived between the original paper and the curve25519 paper. Both are correct. To double a point on a Montgomery curve $$ y^2 = x^3 + Ax^2 + x\,, $$ one has the identity relating the doubled point $(x_3, \cdot)$ and the source point $(x_1, \cdot)$: $$ x_3 4x_1(x_1^2 + Ax_1 + 1)...


5

Over the field $\mathbb Z/(2^{255} - 19)\mathbb Z$, Curve25519 is the Montgomery curve $$v^2 = u^3 + 486662 u^2 + u,$$ and edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2.$$ The curves correspond by the birational map \begin{gather} x = \sqrt{-486664} \frac{u}{v}, \quad y = \frac{u - 1}{u + 1}; \\ u = \frac{...


5

It appears that the public-key anonymous encryption scheme in question is ECIES. ECIES encryption requires generating a single-use key pair and doing a DH key agreement with it, while ECIES decryption only requires doing a DH key agreement and so should cost considerably less than encryption. Specifically, the sender knows the recipient's public key, $A$, ...


5

A good way to think of the point at infinity is that it is an artificial point of the curve, introduced to fill gaps in the table for addition of points on the curve, and act as the group's neutral element. That Makes point addition an internal law (addition of two points on the curve becomes a point on the curve, with no exception). Otherwise, there would ...


5

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


5

Some formulas like the usual short Weierstrass addition formula for curves over fields of characteristic ${>}3$, involve terms like $$\frac{y(P) - y(Q)}{x(P) - x(Q)}$$ which don't work when $P = Q$. So to reliably add two points, you have to write logic like: if P == Q: return doubling_formula(P) else: return addition_formula(P, Q) This ...


5

Well, if you have a pseudocurve [1] based on the formula: $$y^2 = x^3 + ax + b \pmod{ pq }$$ what you have is really two different curves stapled together; that is, the curves based on: $$y^2 = x^3 + ax + b \pmod{ p }$$ $$y^2 = x^3 + ax + b \pmod{ q }$$ You can look at a point in the $pq$ curve as really being a point in the $p$ curve and a point in the ...


5

Short answer: the definition you're using (and, in particular, the notation in it) is specific to multiplicative groups modulo $p$. It makes no sense for elliptic curves, or for most other kinds of groups over which the discrete logarithm problem can be defined. In particular, for elliptic curves, there is no prime modulus $p$. (Well, OK, for the elliptic ...


5

The public key representations are related but not the same. They cannot be used interchangeably without additional processing. The curves are birationally equivalent; a point on a curve has an equivalent on the other curve. So, given an EdDSA public and/or private key, you can compute an X25519 equivalent. Libraries such as libsodium provide functions to ...


5

For every $y \in \mathbf F_p$, there is a unique $x \in \mathbf F_p$ such that $(x,y)$ is on the curve, namely $x = \phi^{-1}(y^2)$, where $\phi : x \mapsto x^3+1$. Adding the point at infinity, that gives $p+1$ points.


5

If you have an elliptic curve given by the equation $y^2 = f(x) \bmod p$, then for each $x$, either $f(x)$ is a square modulo $p$, and there exists a square root $y$ such that $(x,y)$ and $(x,-y)$ satisfy the curve equation. If $f(x)$ is not a square modulo $p$, then this value $x$ does not correspond to a point on the curve, but to a point on the quadratic ...


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