Questions tagged [elliptic-curves]

Elliptic curves are algebraic-geometric structures with applications in cryptography. Such a curve consists of the set of solutions to a cubic equation over a finite field equipped with a group operation. Questions relating to elliptic curves and derived algorithms should use this tag and might also consider more specific tags such as discrete-logarithm and ecdsa.

Filter by
Sorted by
Tagged with
7
votes
2answers
612 views

Endomorphism ring of a Elliptic Curve and $j$ invariant

I am reading Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i). I am trying to understand page 238 (second paragraph) of the proof: if the ...
7
votes
1answer
548 views

Goofs that could creep in ECDSA signature verification?

What are goofs that could creep in ECDSA signature verification, perhaps with focus on curves based on prime-order $\mathbb Z_p$, specifically P-256 aka secp256r1? Is it possible to construct test ...
7
votes
1answer
753 views

Isn't the security of EC curve 25519 126 bits?

The security of the EC25519 is given as 128 bits, but since the order of the group is 252 bits shouldn't the security be 126 bits? Given as half the magnitude of the underlying field, since DLP ...
7
votes
1answer
2k views

ECC considered secure in OpenSSL?

If I perform the following command: openssl ecparam -list_curves using my OpenSSL version (1.0.1f), it spits out the following supported curves: ...
7
votes
1answer
1k views

Elliptic curves for ECDSA

I'm trying to implement parameters generation for ECDSA according to SEC1 v2.0: ...
7
votes
1answer
320 views

Proving that the least significant bit of an elliptic curve discrete logarithm is $0$

Suppose I have a secret value $a$ which maps to a public point on an elliptic curve $A = a \cdot G$, where $G$ is a generator of the elliptic curve of prime order $q$. Can I prove to someone that the ...
7
votes
1answer
155 views

How important is hardware based crypto in Quantum-safe TLS in mobile devices?

Microsoft Research published an approach to Quantum-safe TLS here, namely RLWE-ECDSA-AES128-GCM-SHA256. One highlight is that when it's used with ECC, there is only a slight performance hit. ...
7
votes
1answer
356 views

Encoding scalar values to points on Ed25519

I'm interested exploring key derivation and threshold signature protocol that require point arithmetic (addition) on the private scalar values and $S$ values of the signatures in ed25519. ...
7
votes
1answer
95 views

Safe generation of $k$ points on a curve such that the mutual discrete logs are hard?

I have a multiplicative group $G$ of prime order $p$ implemented using a twisted Edwards curve (similar to Ed25519). I want to compute a set of $k$ distinct points $P_1,...,P_k$ that generate $G$, ...
7
votes
1answer
1k views

Elliptic curve cryptography related key attacks [closed]

This question is an extension of Families of public/private keys in elliptic curve cryptography As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where ...
6
votes
1answer
2k views

Can SRP be used with Elliptic Curves?

I'm sure it can, because SRP (secure remote protocol) can be implemented everywhere where Diffie-Hellman works, but I need a proof to put this aspect into Wikipedia. Edit: ok, can it be at least ...
6
votes
2answers
743 views

Is it possible to derive a public key from another public key without knowing a private key (Ed25519)?

I have a following use case: User has his master public (sk) - private (pk) key pair (Ed25519). In DB we store a public key. Is ...
6
votes
2answers
139 views

Why ECDSA has its form?

According to Wikipedia, if Alice wants to sign some message, she computes $s = k^{-1} (z + r d_A)$ then sends $(r, s)$ to Bob. I don't understand why they use this particular formula $s = k^{-1} (z + ...
6
votes
2answers
2k views

Why must an elliptic curve group for ECC have prime order?

What is the deeper reason, a group must have prime order for usage in cryptography?
6
votes
1answer
805 views

What's wrong with this curve (generation algorithm)?

In this tweet, Paulo Barreto proposes the following elliptic curve over $\mathbb{F}_{2^{255}-19}$: $$ E_\mathrm{PB} : y^2 = x^3 - 3x + 13318 $$ with $G_\mathrm{PB} = (-7, 114)$. Now I would like to ...
6
votes
2answers
1k views

Why are NaCl secret keys 64 bytes for signing, but 32 bytes for box?

Ed25519 secret and public keys can both be represented in 32 bytes. Why does NaCl use 64 byte signing keys?
6
votes
2answers
349 views

Difference on montgomery curve equation between EFD and RFC7748

There is a subtle difference between the 2 implementations for a Montgomery curve defined from the 2 following links https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html A = X2+Z2 AA = ...
6
votes
1answer
4k views

ECDH or RSA more secure for symmetric key wrapping?

Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key. In this case, the size of the message is ...
6
votes
3answers
449 views

Supersingular Isogeny Key Exchange broken?

Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves. http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf with the quote "...
6
votes
3answers
677 views

The utility of elliptic curve cryptography

Suppose that the only public key cryptography schemes that we knew were Diffie Hellman, RSA and ElGamal. How much would this set civilization back? Are there important applications of elliptic curve ...
6
votes
1answer
441 views

Can multiple public keys lead to the same shared secret in X25519?

I have no mathematical knowledge about this, but I just read in RFC 7748 the following: Designers using these curves should be aware that for each public key, there are several publicly ...
6
votes
1answer
505 views

Ed25519 PKCS8 private key example from IETF draft seems malformed

Malformed PKCS8 Key Algorithm Identifiers for Ed25519, Ed448, X25519 and X448 for use in the Internet X.509 Public Key Infrastructure § 10.3. Examples of Ed25519 Private Key states the following: <...
6
votes
2answers
2k views

Is Curve25519 vulnerable to private key exposure in the case of a bad RNG?

I'm really excited by what I've learned of advancements in elliptic-curve cryptography. Curve25519 seems to be a great choice at this point in time, but if I recall correctly, some elliptic curve ...
6
votes
1answer
2k views

Why Elliptic curve cryptography are not popular in practice

RSA and ElGamal can be implemented using the technique of Elliptic curves. I am confused on why the it seems that Elliptic curves are not so popular in cryptographic applications since they provide ...
6
votes
2answers
934 views

Elliptic curve and “vanity” public keys

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve),...
6
votes
1answer
860 views

What are the coordinates of a generator point?

I'm browsing through Curve25519 code, the generator point of it is $G=9$. I would like to know how can I get $x$ and $y$ coordinates of this generator point. Is there any standard way of ...
6
votes
1answer
259 views

Elliptic Curve Cryptography - When to use p and when to use n

Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems. So far I'...
6
votes
1answer
1k views

What does the $\|$ operation mean in cryptographic notation?

I am studying elliptic curves problems, which also includes study of related protocols such as ECIES. The problem is that I don't understand the notation $\|$. What does this operation mean? Some ...
6
votes
2answers
187 views

Is there a theorem to determine the elliptic curve parameters based on the group order?

By Hasse's theorem we know that range of the group order of the elliptic curve. And similarly, there exist a theorem on the admissible order of elliptic curves. Suppose by the theorem on the ...
6
votes
1answer
755 views

How to derive the curve Ed25519 from Curve25519?

According to the paper "Faster addition and doubling on elliptic curves" by Bernstein and Lange, the Montgomery curve (Curve25519) $$v^{2}=u^{3}+486662\cdot u^{2}+u$$ is birationally equivalent to the ...
6
votes
1answer
226 views

How does DJB's nistp224 manage to fit compressed points into 224 bits?

DJB's nistp224 program purports to be an implementation of elliptic curve Diffie-Hellman relative to the standard NIST P-224 elliptic curve. To the best of my ...
6
votes
1answer
264 views

Why can't you divide by 0 in an Edwards Curve?

The equation of an Edwards curve is $x^2 + y^2 = 1 + d x^2 y^2 \,$ The addition formula is $(x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - ...
6
votes
1answer
633 views

Advantages of RSA / EC against QC attacks

We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other? As an ...
6
votes
3answers
3k views

Can elliptic curve (25519) be used to encrypt file?

This is probably a simple question, but I haven't been able to see it stated anywhere. Is it possible to directly encrypt a file (of any length) with some form of EC using the 25519 curve. I know it'...
6
votes
1answer
2k views

Non adjacent form of an integer is unique

I have tried to look up the proof for NAF (Non-adjacent form) being unique for every integer, but as far as I have seen, textbooks only mention it as a property of NAF, but no proof is given. Also I ...
6
votes
1answer
267 views

What are the computational benefits of primes close to the power of 2?

Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$. What I missed or was unable to understand is ...
6
votes
1answer
2k views

Montgomery Ladder vs Double-and-Add

I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm. I think that firstly, Monty would be slightly faster than DoubleAndAdd. ...
6
votes
1answer
2k views

X9.62 Multiplying an elliptic curve point by a number

I'm currently trying to implement ecdsa and the first problem i met -- multiply an elliptic curve point by a number. As far as i understand X9.62 gives some recommendation for doing it but i haven'...
6
votes
1answer
450 views

Can Pohlig-Hellman encryption be done over elliptic curves?

Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH. ...
6
votes
1answer
126 views

Why do Edwards curves protect against side-channel attacks?

From Wikipedia: One of the attractive feature of the Edwards Addition law is that it is strongly unified i.e. it can also be used to double a point, simplifying protection against side-channel ...
6
votes
1answer
978 views

Why does anyone use elliptic curves for a CSPRNG?

I saw Martijn Grooten's talk on elliptic curves at BSides London this year, and it helped me understand how elliptic curve crypto works, especially in the case of Diffie-Hellman (ECDH). He also ...
6
votes
2answers
6k views

How to measure ECC key size?

I have implemented a ECC key generation scheme successfully. Now I need to find ECC key sizes of each generating key pairs. I assumed that ECC key size is the size of the ECC private Key. So I would ...
6
votes
2answers
4k views

Are there any elliptic curve asymmetric encryption algorithms?

RSA offers the functionality of encrypting (short messages, or symmetric keys) with a public key, and decrypting with a private key. However, RSA key generation is extremely expensive, especially for ...
6
votes
1answer
245 views

Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?

I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but ...
6
votes
2answers
2k views

ECC algorithm pollard's $\rho$ complexity

One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to ...
6
votes
1answer
531 views

Elliptic curves with pairings at 128-bit security in libpbc?

I am using Ben Lynn's libpbc to implement a BLS threshold signature scheme and I am aiming for 128-bit security (i.e., a forgery attack should take around $2^{128}$ ...
6
votes
2answers
3k views

Complete Set of Test-Vectors for ECDSA secp256k1

Although there are several implementations of ECDSA secp256k1 public available over the internet (the most popular being OpenSSL), it seems that there are no complete set of test-vectors available. ...
6
votes
1answer
2k views

Base point in Ed25519?

The paper "High-speed high-security signatures" by Bernstein et al. introduces the Edwards curve Ed25519. Concerning the base point $B$, it says that $B$ is the unique point $(x, 4/5)\in E$ for ...
6
votes
1answer
2k views

Converting Ed25519 public key to a Curve25519 public key

I understand that: $$x_{montgomery} = \frac{1 + y_{edwards}}{1 - y_{edwards}}$$ Using the libsodium ed25519 implementation, I have tried to write the following: ...
6
votes
1answer
192 views

Why would the use of Curve25519 in Dragonfly leak information?

An answer explaining Dragonfly, a form of key exchange used in WPA3, has an interesting footnote: One final note: reviewing the Firefly RFC, I see that it would (as written) leak some information ...