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
6
votes
1answer
377 views

What does Shor's algorithm tell us about the complexity class of RSA and the DLP?

If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these ...
6
votes
1answer
294 views

Is there any reason not to use EdDSA with Weierstrass curves?

I'm volunterely working for a crypto library and we're planning on adding Curve25519 support (finally). At the same point I had the idea of adding support for EdDSA in the same run. Our library is ...
6
votes
1answer
620 views

How to exctract ECDH parameters from an OpenSSL-generated $G$?

I'm using ECDH for generating ECDH public parameters (p,a,b,G,n), I try to get this values using openssl ecparam -in cert.pem -text -noout For ...
6
votes
1answer
122 views

Would key stretching help mitigate concerns with “verifiably random”?

Daniel J. Bernstein (and others) have expressed concern over how "verifiably random" curve parameters are generated. He points out that hashing a public seed doesn't prevent, say, the US government (...
6
votes
1answer
1k views

Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing?

Note: A distributed signature scheme exists for RSA: Practical Threshold Signatures, Victor Shoup. Is it possible to adapt such scheme for ECC? A centralized signing machine is vulnerable to ...
6
votes
1answer
282 views

What exactly could be accomplished with a backdoor in Dual_EC_DRBG?

Assume that some entity really holds the private key corresponding to the recommended/dubious constants of Dual_EC_DRBG. According to this presentation, they would be able to reconstruct the internal ...
6
votes
1answer
168 views

Is it important to defend against key substitution attack in ECDSA?

When planning a file signature scheme (basically, just to sign all files content). Is it obligatory to defend against ECDSA key substitution attack? ISO/IEC 14888-3:2018 NOTE 5 states: The ...
6
votes
1answer
669 views

Normalization of points on an Elliptic Curve

The Bouncy Castle source code (Java edition) has a ECPoint.normalize() function. It seems to calculate the modular inverse of a coordinate of a point on the curve. ...
6
votes
1answer
344 views

Default algorithm for scalar multiplication of elliptic curve points by the MIRACL Library

What is the default algorithm used by the MIRACL-Library [1] for elliptic curve cryptography systems to perform scalar-point multiplication with curves of Weierstrass form satisfying the equation : $y^...
6
votes
3answers
750 views

Safe curves in Weierstrass form?

I would like to implement a protocol using elliptic curves. I'm thinking of using MIRACL so using curves in their Weierstrass form is preferable as it they are supported by this framework. I don't ...
6
votes
1answer
329 views

How can I use Weierstrass curve operations with a=-3 for implementing operations for a=0?

I am working with golang's elliptic library. It implements functions on Weierstrass elliptic curves with $a=-3$. I need to make my own library that allows me to handle curves with $a=0$. I understand ...
6
votes
1answer
256 views

Elligator-2 against curves over Fq, q mod 4 = 3

It appears that the conditions for applicability of Elligator-2 against many of the SaveCurves curves, where $q \mod 4 = 3$ will inevitably poke a hole in the bit-string set over $(0, 1, .. (q-1)/2)$. ...
6
votes
0answers
73 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
6
votes
0answers
245 views

Index calculus over elliptic curve over function field

According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\...
5
votes
3answers
967 views

How can there be insecure elliptic curves if the discrete logarithm problem is hard?

The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure ...
5
votes
2answers
1k views

Raw curve25519 public key points

I'm trying to understand curve25519, and ECC public points. I'm playing with Minisign, to better understand the fundamentals of ECC. Minisign uses curve25519 and outputs public keys as base64 ...
5
votes
2answers
141 views

How sensitive to change are elliptic curve formulae In layman's terms?

Take for example a curve from a recent question such as #25519:- $$y^2 = x^3 + 486662x^2 + x$$ It's considered "safe". What are are the implications of amending it very slightly to:- $$y^2 = x^3 + ...
5
votes
1answer
2k views

What is an elliptic curve cofactor?

As the title says, I have some doubts about the term "cofactor" used to describe elliptic curves. AFAIK, it's a factor of the curve order, but why is it explicitly specified in some parameter lists ...
5
votes
2answers
2k views

Why is Diffie Hellman used alongside public keys?

I just read this post here: Why do we need asymmetric algorithms for key exchange? that asserts that in public key cryptography when asymmetric keys are used to secure communications, for parties to ...
5
votes
3answers
741 views

Is EC integrated encryption scheme used in practice?

I know ECDSA and ECDH are used a lot but what about the ECIES? Is it used or specified as an option in any protocol?
5
votes
2answers
657 views

Can we use elliptic curve cryptography in wireless sensors?

Can we use elliptic curve cryptography in wireless sensors? If so, how do you map points to message characters?
5
votes
2answers
261 views

How to get an optimal strategy in computing isogenies for SIDH/SIKE

How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec? If possible, can anyone give me an example? And why do we need to compute all leaf point? I though we just need ...
5
votes
1answer
391 views

Can two elliptic curve point multiplications have a same resulted point?

Is it possible for $aG \equiv bG$, with $a, b$ are scalars and $G$ is a point on the curve?
5
votes
1answer
530 views

ECDSA key recovery - floating point values

I'm currently attempting to recover an ECDSA key. I have $m$, $m'$ and signatures $(r, s)$, $(r', s')$, and I know that $k$ is constant, the curve is NIST P-192 and the hash function of the. As such,...
5
votes
2answers
890 views

Why is 2048-bit RSA always paired with 320-bit ECC?

You may already have noticed that most smart cards ship with 2048-bit RSA support and 320-bit ECC over GF(p) support. You may have already asked yourself "why exactly 320-bit?". Now I remember having ...
5
votes
1answer
630 views

Why doesn't this replay attack work on ECDSA?

I've just started working with elliptic curves and ECSDA in particular, so my understanding of the underlying math isn't great. The thing I'm currently stuck on is trying to understand why replay ...
5
votes
5answers
1k views

Elliptic curves in Edwards form (or Edwards curve) and addition formulas

In recent studies on elliptic curve cryptography, Edwards curves are remarkable examples on this field. Studies show that this kind of elliptic curves provide faster computation compared to ...
5
votes
1answer
399 views

Elliptic Curve Cryptography

I have been trying this for a while. But I couldn't get it. How can I determine the point of intersection of the tangent line at (0, 0) on the curve $y^2 + y = x^3 + x^2$ ?
5
votes
1answer
1k views

In elliptic curve cryptography, how is “A dot A” computed?

I was just reading Ars Technica's primer on ECC. Somewhere near the middle of the second page, the author introduces the "dot" operation that takes an elliptic curve and two other known points, giving ...
5
votes
1answer
2k views

inverse problem about scalar multiplication on elliptic curve

Let $E$ be an elliptic curve over a finite field $F_p$. Given $n$ be a positive integer and $Q$ be a point on $E$, assume that $Q=nP$, how can we find this $P$? We can assume that $n|p-1$. If $n$ is "...
5
votes
2answers
3k views

How do I unpack the x and y values from the BITSTRING in a DER ECDSA public key?

In ASN.1, the X and Y values for a 256-bit elliptic curve key are stored as a single 66-byte ASN.1 BITSTRING. Are the values just the first and second half of this bitstring? The private key is an ...
5
votes
1answer
2k views

Understanding BLS12-381 Curve

I have some basic understanding of ECC - but pretty far from advanced concepts. I've been reading about BLS12-381 curve here and here, but I can't seem to fully understand it. The things that I think ...
5
votes
1answer
423 views

How can I generate a Koblitz curve?

Is there the way to generate new Koblitz curves, over $\mathbb F_{2^n}$ and $\mathbb F_p$? The Certicom SEC 2 standard says: The recommended parameters associated with a Koblitz curve were chosen ...
5
votes
1answer
669 views

Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why?

I was considering using Microsoft's SIDH implementation for post-quantum public-key encryption because of its relatively small key size. I realized however, thanks to Issue #4, that it might not be as ...
5
votes
1answer
137 views

What are the problems with Diffie-Hellman groups 3 and 4 (RFC 2409 + RFC 2412)?

In RFC 2409 and RFC 2412 Diffie-Hellman groups 3 and 4 were defined. These are groups over elliptic curves based on Galois Fields with and elements respectively. I know that these sizes are ...
5
votes
1answer
801 views

BN-Curves for 256-bit symmetric security

I'm just studying the purpose of BN-Curves and I am interested in a setting for a 256-Bit security. So could you tell or link me to any information about this? are BN-Curves efficient for this ...
5
votes
2answers
210 views

Why is elliptic curve parameter $a=-3$ somehow special

Considering the equation of the elliptic curves over $GF(p)$ $y^3 = x^2+ax+b$ , why is there some magic in using $a=-3$ ? In some well known curves (e.g. P-256) only $b$ is specified, while $a$ ist ...
5
votes
1answer
1k views

Key exchange using ECDH vs ECIES?

I'm a beginner to ECC crypto programming. Does any one explain to me the difference with using ECDH for shared key exchange and use of ECIES by encrypting shared key with the public key of the ...
5
votes
2answers
1k views

Safe elliptic curve point addition using projective coordinates: How do I tell if the points are the same?

I am trying to implement elliptic curve point addition in hardware for NIST p256 and p384 curves. I have noticed the following issue with the suggested NIST routines: Consider routine 2.2.7 of http://...
5
votes
1answer
434 views

Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible?

In the paper Pairings for Cryptographers we read about what the authors call a type 2 pairing in which we have a "pairing friendly curve $E$ over $\mathbb{F}_q$ with embedding degree $k>1$ and ...
5
votes
1answer
2k views

With TLS and ECDHE, how does curve selection work?

Given that a TLS client and server have already agreed upon ECDHE for session key establishment, how does the selection of the actual elliptic curve ("domain parameters") being used for deriving the ...
5
votes
1answer
2k views

Possible ECC backdoor and its impact on Internet traffic

In a recent article, Bruce Schneier suggested that he prefers classic discrete log crypto over ECC because "I no longer trust the constants. I believe the NSA has manipulated them through their ...
5
votes
1answer
387 views

Difference between Pure EdDSA (ed25519) and HashEdDSA (ed25519ph)

My question refers to EdDSA as specified in RFC 8032. I get from the RFC that ed25519 and ed25519ph are two different instances of EdDSA mainly differing in the fact that that in the case of ...
5
votes
1answer
226 views

Intersection of two elliptic curves

Is it possible to find points that are on two elliptic curves, and how? More precisely, I'm looking for coordinates $(x,y)$ that satisfy the defining equations of two elliptic curves on prime fields $...
5
votes
2answers
751 views

Is ECC over real numbers possible?

Many elliptic-curve cryptosystems today use GF(p) or GF(2^m). What if, say, we use big floating numbers with the classical point addition formulas - is a cryptosystem possible to build on that?
5
votes
1answer
572 views

ElGamal with elliptic curves II

There is an encryption scheme using elliptic curves given by @tylo explained here: @tylo's answer on ElGamal with elliptic curves and here: ElGamal with elliptic curves I. The encryption idea is to ...
5
votes
2answers
3k views

How to derive a symmetric key from ECDH shared secret?

I am trying to implement the internal primitives of ECDH. Currently I'm able to multiply the receiver's public EC point with the sender's private key to arrive at the shared EC point. Next step is to ...
5
votes
1answer
829 views

Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates

My implementation of the parallelized Pollard's Rho algorithm is using Jacobian coordinates to avoid the costly inversion operation when performing point addition. I am wondering if there are any ...
5
votes
1answer
331 views

Is ECDSA obsolete/deprecated?

I have been reading about recommendations on the correct use of crypto as a developer and I read at least two references to the obsolescence (so to say) of ECDSA. https://paragonie.com/blog/2015/08/...
5
votes
1answer
449 views

Does the backdoor in Dual_EC_DRBG work like that?

From what I read, the backdoor in Dual_EC_DRBG operates by using related $P$ and $Q$ points. Did I understand the idea correctly? Dual_EC_DRBG works by multiplying the $P$ point with the seed ...