Hot answers tagged

20

A valid point of an elliptic curve in Weierstrass form satisfies the equation $$ y^2 = x^3 + ax + b\,. $$ We can rewrite this as $y = \pm \sqrt{x^3 + ax + b}$, which has either 2 solutions when $x^3 + ax + b$ is a square, 1 solution when $x^3 + ax + b = 0$, or 0 solutions when $x^3 + ax + b$ is not a square. In X25519, we only see the $x$ coordinate, but we ...


12

The formulas actually work. You just have to keep in mind to make computation in the field of intergers modulo $2^{255}-19$ and that there are actually two square roots, you need to use the right one if you want to have the expected result. You can test the following SAGE code gf=GF(2^255-19) X_P = gf(...


10

Is X25519 and Ed25519 the same curve? No. X25519 isn't a curve, it's an Elliptic-Curve Diffie-Hellman (ECDH) protocol using the x coordinate of the curve Curve25519. Ed25519 is an Edwards Digital Signature Algorithm using a curve which is birationally equivalent to Curve25519. Is X25519 used by ECDSA? No. It's not a curve, it's an ECDH protocol. What does ...


9

There are actually only 5 unique $x$-coordinates one needs to be concerned about: $(0, \ldots)$ $(1, \ldots)$ $(-1, \ldots)$ $(x_1, \ldots)$ $(x_2, \ldots)$, where $$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray} $$ and $$\begin{eqnarray} x_2 =& ...


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


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


5

The order of the base point of Curve25519 is the a 253-bit integer $2^{252}+ 27742317777372353535851937790883648493$. Choosing as private key a random positive integer less than said order is a common choice in cryptosystems based on the difficulty of the Discrete Logarithm in some group. That might be why private keys are said to be 253-bit. However, per ...


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


4

Well, as often when it comes to "practical security", the answer is: it depends. First things first, there is nothing special about the keys or the way the maths in X25519 works that would make the one or the other more secure: publishing many public keys will not significantly ease the process of recovering any single secret key, although each new key ...


4

Generally for forward secrecy you should not just limit the use of the private key (and thus public key) in time, but also per connection. For that reason, you can assume that in most implementations that require forward secrecy that there will be one ephemeral key pair per connection, not per time frame. Similarly, you're assuming that a new key pair is ...


3

A bit of nomenclature first: “Ed25519” is defined to refer to the EdDSA signature algorithm over the edwards25519 curve. What you appear to actually mean is whether you can reuse your edwards25519 code for Elliptic Curve Diffie–Hellman (ECDH). There is no inherent reason that you can't use edwards25519 for ECDH. We've been doing ECDH with all kinds of curves ...


3

Is this scheme correct ? What should I review/read to make it correct ? One obvious issue is that the client is willing to decrypt arbitrary ciphertexts with its private key. Hence, if it uses the private key for any other purpose, well, it's insecure. In the article from Digital Ocean you can find that client doesn't send raw data back to server ...


3

Poly1305 itself has the requirement that its keys can only ever be used to generate a tag for a single message. That means that when Poly1305-AES (or another Poly1305-based authenticated encryption algorithm) is used as intended, the Poly1305 authentication key will be different for each message even if a key is reused. However, the various Poly1305-based ...


2

You operations have to be modulo $p$ where $p=2^{255}-19$ because you are working in $\mathbb{F}_p$.


2

The clamping happens as part of the key agreement / signing procedure. The private key itself isn't clamped when stored. (How did you test the numbers you have provided? None of them seem to be multiple of 8. Also recall that curve25519 keys are in little endian.)


2

Note that $$\frac{7(p-5)}8+3=\frac{7p-11}8\equiv \frac{7p-11}8-p-1\equiv -\frac{(p+3)}8\pmod{p-1}.$$ Similarly $$\frac{p-5}8+1=\frac{p+3}8$$ And so $v^3(v^7)^{\frac{p-5}8}\equiv v^{-\frac{(p+3)}8}\pmod p$. Likewise $u(u)^{\frac{p-5}8}\equiv u^{\frac{p+3}8}$ as required. The reason is to save a modular division which is quite a pricey operation.


2

We want to answer "How many wolves are coming to attack?" by "twenty one" (big-endian), not "one twenty" (little-endian). That can be a matter of life and death, and perhaps natural selection of memes¹ made that the convention in many languages (German is an important exception). Big-endian is thus used in most human positional ...


2

So the answer thanks to @kelalaka's comments is that X25519 doesn't need an iv. I was not using just X25519, but instead x25519-xsalsa20-poly1305 via TweetNaCl.js. There isn't really a need to use x25519-xsalsa20-poly1305 to wrap the AES-256-GCM key, as the "xsalsa20 is a stream cipher and poly1305 is for mutual authentication". Regarding JWE, ...


2

For x25519, can multiple PK's resolve to a single SK, or is there ever only one unique PK-SK pair? If I wasn't mistaken, there can be atmost 2 PK corresponding to 1 SK in x25519, depending on whether the implicit y-coordinate is internally positive or negative. As for ECDH on the other hand, the mapping is 1:1. I'm wondering whether it's rational to ...


1

It turns out this is possible and has been implemented in the libolm library of Matrix. The solution adopted in this library is to generate a signing key for each user. This is an Ed25519 keypair, which is used to calculate a signature on an object including both the public Ed25519 signing key and the public Curve25519 identity key. It is then the public ...


1

One obvious note is that if someone (possibly someone posing as a server) overhears the client to server message (that is, the client's input to the crypto.verify.password_hash.argon2id function), then he knows enough to register as the client to a valid server. He might not know the password; however he wouldn't need to. If that is a problem, it would ...


1

Let $p = 2^{255} - 19$. Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$. (Here $k = 1$.) So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\...


1

Provided that you use the all 256 bits of SKEY as key then the bit security of this scheme is about $\sqrt2\cdot2^{125}$. The reason behind the $2^{125}$ as opposed to the security of $2^{128}$ is because, for curve25519, $2^{128}$ is just an approximation. If we use, as it is more commonly done, the number of "operation" for this calculation, then the ...


1

Note you're doing direct division instead of modular inverse. Since there is no division in elliptic curve arithmetic, you need to do mod inverse. pow function could be used as a helper here; it takes third argument as modulus: >>> P = 2 ** 255 - 19 >>> X = 15112221349535400772501151409588531511454012693041857206046113283949847762202 >&...


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