Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
26 votes
Accepted

Difference between X25519 vs. Ed25519

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 ...
SAI Peregrinus's user avatar
26 votes

Summarize the mathematical problem at the heart of breaking a Curve25519 public key

Six-word summary: the elliptic-curve discrete log problem. $\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}$Summary with math: Given $x(A)$ and $x(P)$ for two points $A$ and $P$ on the elliptic ...
Squeamish Ossifrage's user avatar
23 votes
Accepted

Distinguishing x25519 public keys from random?

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 + ...
Samuel Neves's user avatar
  • 12.6k
12 votes
Accepted

Curve 25519 (X25519, Ed25519) Convert coordinates between Montgomery curve and twisted Edwards curve

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 ...
Ruggero's user avatar
  • 7,104
10 votes
Accepted

"Cropping" the resulting shared secret from ECDH

You should apply the hash. If one follows the specification there are only roughly $2^{251}$ possible shared secret values and there is a simple test to see if a putative 32 bytes represents a ...
Daniel S's user avatar
  • 23.9k
8 votes
Accepted

How does the process of creating a new secure Elliptic Curve look like?

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 ...
Youssef El Housni's user avatar
7 votes
Accepted

Why does OpenSSL show 253 bits?

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 ...
fgrieu's user avatar
  • 142k
7 votes

Summarize the mathematical problem at the heart of breaking a Curve25519 public key

It's not $b^k = g$ because $b$ and $g$ are not integers but elliptic curve points. So keeping your notation what you are doing is $[k]B = G$ where you take point addition on Curve25519 and then add $...
Elias's user avatar
  • 4,923
7 votes
Accepted

Representations of secret keys on Curve25519

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 ...
Ilmari Karonen's user avatar
7 votes
Accepted

What is the order of the generator point G=9 in curve25519?

According to this source, the points of this curve are a group of cardinality $8\cdot p'$ with $p':=2^{252}+27742317777372353535851937790883648493$. This number can be computed by using the Schoof ...
Ievgeni's user avatar
  • 2,605
7 votes
Accepted

Is the combination of X25519 ECDH and NTRU in OpenSSH 9.X secure against quantum attacks?

Can the combination of X25519 ECDH and NTRU in OpenSSH 9.X defend me against quantum attacks? Actually, that version of OpenSSH uses NTRU Prime, rather than NTRU. However, that does not change the ...
poncho's user avatar
  • 148k
6 votes
Accepted

Difference on montgomery curve equation between EFD and RFC7748

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 ...
Squeamish Ossifrage's user avatar
6 votes
Accepted

Distinguishing EC Public Key from random

Argument towards $x^3+ax^2+x$ being a square modulo $q$ for around 50% of $x$ when $a,q$ are the parameters in Curve25519: we know $y^2\equiv x^3+ax^2+x\pmod q$ defines a proper elliptic curve group. ...
fgrieu's user avatar
  • 142k
5 votes
Accepted

Composition of X25519+XSalsa20+Poly1305

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 ...
Future Security's user avatar
5 votes

Difference on montgomery curve equation between EFD and RFC7748

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 ...
Samuel Neves's user avatar
  • 12.6k
5 votes

How many valid X25519 private keys are there?

The Curve25519 curve has $\ell = 2^{252}+27742317777372353535851937790883648493$ possible points in the prime-order group, corresponding to $\ell$ private keys. However, X25519 refers to a particular ...
knaccc's user avatar
  • 4,732
5 votes
Accepted

How many valid X25519 private keys are there?

This is a tricky topic as it depends on the definition of "valid" in the public key context. Your enumeration of the private keys for X25519 is obviously correct as it follows the definition ...
Ruggero's user avatar
  • 7,104
4 votes
Accepted

Is using different public keys for different peers safer than reusing the public key, beyond forward secrecy?

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 ...
Lery's user avatar
  • 7,699
4 votes

Is using different public keys for different peers safer than reusing the public key, beyond forward secrecy?

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 ...
Maarten Bodewes's user avatar
4 votes
Accepted

Proof of possession. x25519 + ed25519

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 ...
poncho's user avatar
  • 148k
4 votes

Why is there a slight mismatch most of the time in X25519 private keys depending on functions used, but public keys always match (same seed for both)?

'curve25519' (as Bernstein originally called it, now renamed X25519 or XDH25519 for clarity because the same curve in different form is used for Ed25519[ph]) requires the privatekey (multiplier) to be ...
dave_thompson_085's user avatar
3 votes

Compact ROM with space only for EdDSA. How to fit a key exchange algorithm inside?

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 ...
xorhash's user avatar
  • 233
3 votes
Accepted

Why is there a slight mismatch most of the time in X25519 private keys depending on functions used, but public keys always match (same seed for both)?

Mathematically, a Curve25519 private key is an element of $\mathbb{F}_{2^{255}-19}$, i.e. an integer modulo $2^{255}-19$. This can naturally be represented as an integer between $0$ and $2^{255}-19-1$,...
Gilles 'SO- stop being evil''s user avatar
3 votes
Accepted

Using same private key for both X25519 and ECDSA (using curve25519)

Why doesn't the X25519 private key need to fit in the range $[1,N]$? By unsetting the most significant bit and the three least significant bits, you limit the key to effectively only 252 bits. When ...
meshcollider's user avatar
  • 1,573
3 votes
Accepted

Ed25519 to X25519 transportation

Curve25519 and Ed25519 A Montgomery curve defined over a field $K$ is defined as; $$M_{A,B}: Bv^2 = u^3 + Au^2 + u$$ for certain $A,B \in K$ and with $B(A^2-4) \neq 0$. Curve25519 uses prime $q = 2^{...
kelalaka's user avatar
  • 48.8k
3 votes

Can X25519 (mult with basepoint) be reversed?

Can the ephemeral_secret be found by whomever obtains the ephemeral_share, given that they know the curve that was used (and therefore the curve's basepoint)? If the design goals of the X25519 ...
fgrieu's user avatar
  • 142k
3 votes
Accepted

Isomorphism of Curve25519 and Ed25519?

The word "isomorphism" is always relative to a particular structure your mathematical objects carry. Sometimes this is obvious from context, but in many cases clarification is needed. Here's ...
yyyyyyy's user avatar
  • 12.1k
3 votes

"Cropping" the resulting shared secret from ECDH

You should hash your secret. (In fact, you should not just hash it, but process it with a key derivation function such as HKDF that has been specifically designed for this purpose.) Doing so ...
Ilmari Karonen's user avatar

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