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
-3 votes
1 answer
76 views

Show me all the steps and methods used to get from a system of 4 linear equations to solve for X1 and X2

I am looking at an answer to a previous question and I would like more detail about how the answer was arrived at but I am not allowed to comment as I am a new user with low points. I am therefore ...
1 vote
2 answers
1k views

What is a good and bulletproof private key for ECC curves?

I am quite new to cryptography low-level mathematic details, though had worked in the crypto area for 2.5 years before. So if I am wrong about any of below part, please correct me without a facepalm ...
0 votes
1 answer
97 views

Elliptic Curve Key Compression

I have an elliptic curve y2 = x3 -x + 3 over a finite field of 127. I am trying to compress a point using the X9.62 standard. I know for the key compression you are supposed to check if the y value is ...
1 vote
0 answers
47 views

How to derive Edwards Point Addition formula

Deriving the addition equation for a Weierstrass curve is simple and straightforward (I started with this video that covers the simple case. If you know the basic derivative rules you can find the ...
9 votes
1 answer
1k views

How are curve names constructed?

I started with the question: Brainpool curves exist in a variant ending in ..r1 and ..t1. What does it mean? But there are also "secp.." and "sect.." just like NIST's "..r1&...
2 votes
1 answer
105 views

Why the trace of the Elliptic curve should be positive?

In https://eprint.iacr.org/2014/130.pdf , has been suggested to select the positive trace. What is the reason for this? What happened if we select the negative trace? Is there any security problem for ...
1 vote
1 answer
101 views

How do we compute the CM discriminants without factoring?

In ECC, there is a parameter known as CM discriminants. Suppose that the trace of the curve is $t$ in $Z_p$. The amount of $s^2$ is the largest square dividing $t^2-4p$ then $\frac{t^2-4p}{s^2}$ is a ...
7 votes
1 answer
122 views

CSIDH - l ideal generators

I am trying to study the CSIDH algorithm. I have some beginner background in elliptic curves and I have been following Andrew Sutherland's lectures (https://math.mit.edu/classes/18.783/2019/lectures....
  • 143
0 votes
3 answers
139 views

Asymmetric cryptosystems based on curves besides elliptic curves

Elliptic curve cryptography (ECC) has been gaining a lot of popularity recently because of its security. I tend to find the process of encoding plaintext using ECC particularly interesting so I was ...
0 votes
2 answers
67 views

Making commitment scheme on elliptic curves perfectly binding

So, the question is, a commitment scheme on elliptic curve is given. Initialisation phase: There is an elliptic curve EC, generator point $G$ over $GF(p)$, which creates a group, and random prime ...
2 votes
1 answer
162 views

Is it safe to implement elliptic curve Diffie Hellman with secp256k1

I need to implement X3DH Key Agreement Protocol according to Signal specification, in the document they suggest using either X25519 or X448 curves. I assume those curves have been chosen for this ...
  • 121
1 vote
0 answers
81 views

What's the difference between Optimal ate pairing and R-ate pairing?

I compare the algorithm description of Optimal ate pairing and R-ate pairing, it turns out to me that the formulas are the same. So I'm a little confused, what's the difference between them? or is it ...
1 vote
1 answer
588 views

How to calculate the order of secp256k1?

The elliptic curve secp256k1 is defined as $y^2 = x^3 + 7$. The prime for the field is set to: ...
  • 113
0 votes
1 answer
32 views

(Non)security of algebraically derived EC keys

I recently had a situation where I needed to derive a secondary Curve25519 private key from an existing one programmatically. The obvious solution was to use a KDF, but I wondered at the time about ...
1 vote
2 answers
128 views

Verifying result of (EC-)Diffie-Hellman

I received a public key by JSON. For the example, I have 4 keys: 2 public keys and 2 private keys. ...
  • 119
0 votes
1 answer
62 views

what does "product of two cyclic groups" mean

I am reading "Elliptic curve cryptosystems" and the link is here(https://www.ams.org/journals/mcom/1987-48-177/S0025-5718-1987-0866109-5/S0025-5718-1987-0866109-5.pdf). I don't understand ...
3 votes
1 answer
139 views

Asymmetric encryption scheme with the shortest output for encrypting 1 byte of information

Imagine that one needs to periodically encrypt very short messages (i.e., a boolean Yes/No, a single byte, or 3-4 bytes in the worst case). We assume that there is no session, and we just need to ...
2 votes
1 answer
140 views

ECC Point Addition on Jacob coordinate -- Not Commutative?

I have a python script that does the ECC point addition (code paste below), it simply performs the P =Q1+Q2 on Jacob coordination. However, when doing some regression tests, I found that if I exchange ...
  • 111
0 votes
0 answers
82 views

Why is the cofactor of the twisted Edwards curve equal to 8?

While The cofactor of the Edwards curve is chosen $4$ in standards, the cofactor of the twisted Edwards curve is chosen $8$. I can't understand the reason for this. Can we choose cofactor $4$ for the ...
7 votes
1 answer
3k views

Why are NIST curves still used?

I'm relatively new to the world of crypto (But as far as the math goes, I am familiar with the inner workings. I used to rarely use it for privacy, but now I use it for many things). Anyway, I was ...
3 votes
3 answers
280 views

How to calculate the n in n-bit security of a crypto algorithm?

I think I'm likely missing the term because searching for this is coming up with not so precise results. I'm looking to calculate the n-bit security of say Paillier vs ElGamal vs EC ElGamal, when I ...
  • 155
1 vote
1 answer
87 views

How to determine whether a point is greater than n/2?

How can we determine if a private key associated with a point, on an EC, is less than or greater than 1/2 $n$, where $n$ is the order?
6 votes
1 answer
709 views

How to determine if a point is just a point or a valid public key?

In ECC, specifically over finite fields, in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used because the Generator Point (...
3 votes
2 answers
136 views

What properties do elliptic curves possess that make them useful?

I tried to learn the algorithmic process behind ECDSA and it's pretty challenging. I'm wondering what motivation or thought process might have led to the discovery in the first place. What properties ...
4 votes
1 answer
252 views

Elliptic curve bilinear pairing parameters for 80-bit security level

I am reading a paper based on elliptic curve bilinear pairing groups. The author has defined the size of private key, public key etc in terms of $|\mathbb{G}_1|, |\mathbb{G}_2|$ and $|\mathbb{G}_T|$. ...
3 votes
1 answer
318 views

Digital Signatures with Curve25519 key-pair

I have a public/private key pair of Curve25519 keys used by Wireguard. How can I use this keypair to generate/verify digital signatures? Preferrably, I would like to use EdDSA/Ed25519 but I struggle ...
2 votes
1 answer
78 views

Can we reverse elliptic curve function mul?

I have an elliptic curve system with only one point P. Let's say the client A and server B generate a secret R1 and R2. A is sending X1 = mul(R1, P) to B and B is sending X2 = mul(R2, P) to A then ...
0 votes
1 answer
46 views

Can the result of a multiplication between an elliptic curve and a scalar not be on the curve?

As the title says, we have an elliptic curve, doesn't matter which one, say p256. We choose any scalar. Can the multiplication of a point on curve with the scalar result in a point that is not on ...
2 votes
1 answer
102 views

Composite order ECC and Ristretto

I've been looking at the Ristretto group, and its really cool. I understand that, for some protocols, we need curve points to behave as if they were from a prime order curve. I have a few questions on ...
  • 1,284
2 votes
0 answers
81 views

Cryptographic invariant maps

In [BGK+18] in section 4, Boneh et al. write that: For any choice of ideal classes $\mathfrak{a}_1,\dots,\mathfrak{a}_n,\mathfrak{a}_1',\dots,\mathfrak{a}_n'$ in ${Cl}(\mathcal{O})$, the abelian ...
  • 173
1 vote
1 answer
130 views

Zero Knowledge Discrete Logarithm on Elliptic Curves

Can the Discrete Logarithm ZK be implemented on elliptic curves? It seems that such an implementation should look like the following: $Y = \alpha G$ Random pick $v$ $t = vG$ $c = H(G, y, t)$ $r = v - ...
0 votes
1 answer
52 views

Why is the cofactor of twisted Edwards curve chosen 8?

While The cofactor of Edwards curve is chosen 4, the cofactor of twisted Edwards curve is chosen 8. I cant understand this reason. Can we choose cofactor 4 for twisted Edwards curve?
2 votes
1 answer
87 views

What happens if the Edwards curve isn't quadratic twist secure?

On this webpage, Daniel Bernstein offers that the curve must be quadratic twisted secure. This means that if the curve has $\#E$ points on $Z_p$ where $\#E=p+1-t$, then the quadratic twist curve has $\...
-1 votes
1 answer
154 views

How to encrypt using private key for ECC

As we know, ECC using $C_2 = r \cdot G, C_1 = M + r \cdot G$; and decrypt with $M=C_1 - K \cdot C_2$. And sign using point $X$: $X = k \cdot G(x_0,y_0)$. $r = x_0 \cdot K; s = 1 / k \cdot (M + r \cdot ...
  • 1
4 votes
2 answers
218 views

Large prime numbers in ECC and discrete logarithm

In elliptic curve cryptography using Diffie-Hellman protocol, we need to use large prime numbers. So my question is what makes discrete logarithm hard to solve when we use large prime numbers. I guess ...
3 votes
1 answer
1k views

Cracking Elliptic Curve Cryptography

I am quite new to the study of elliptic curve cryptography and as such I might be asking something with a mundane solution, but I can't easily find such a solution online. My understanding of ECC is ...
  • 191
0 votes
0 answers
41 views

Finding of trace of Edward curve and proper $d$

The obvious way for computing the trace of curve is counting the number of curve point and then compute the trace of the curve by $t=p+1-\#E$. Are there any faster way for computing the trace of the ...
0 votes
1 answer
436 views

Public key size for different elliptic curves

Let's say I want a certain level of security (eg 128 bits) when using ECIES but I also want to minimise communication, does the elliptic curve used matter on the size of the public key? If it does ...
  • 67
2 votes
1 answer
64 views

Why is ECDHE safe when paired within signing?

I wanted several videos by Computerphile on Elliptic Curve Diffie-Hellman, digital signatures and TLS. For the most part I understand everything but something is bothering me. Computerphile made a ...
0 votes
0 answers
42 views

Finding of proper $d$ for Edward curve

I wanna create the safe Twisted Edward curve. As far as I know, The number of curve points must be $\#E=8r$ that $r$ is big prime number. Also the number of points of quadratic twist of this curve ...
1 vote
2 answers
102 views

Different modulus in the exponent

Given two values $g^{a_1}, g^{a_2}$ where $a_1, a_2 \in \mathbb{Z}_q$ and $g$ is a generator of group $\mathbb{G}$ of order $q$. Discrete logarithm is assumed to be hard in $\mathbb{G}$. Is there a ...
  • 139
3 votes
1 answer
115 views

Multi-target attacks of ECC public keys

Imagine a situation where there are many high-value public keys around, using the same Elliptic Curve group, say $k$ in the millions public keys¹. Can an adversary reasonably find one of the matching ...
  • 126k
1 vote
1 answer
43 views

Where are the seeds for the initial key exchange phase taken from?

I know that the standard DH and ECDH key exchange algorithms require the client and server to agree on a large prime number and a generator (in the DH algorithm) or a curve and a point (in the ECDH ...
8 votes
2 answers
902 views

Why Elliptic Curve Cryptography protocols depend on fixed curves?

I'm learning about Ed25519. It depends on a bunch of magic values: The finite field of order $2^{255}-19$, the specific elliptic curve over that field, a specific ...
  • 181
2 votes
1 answer
183 views

How do I validate Curve448 public keys?

Performing an ECDH calculation with an invalid public key can leak information about your own private key. With Weierstrass curves, it's important to verify that the peer's public key is actually a ...
3 votes
1 answer
437 views

Problem with point addition about [n-1]+[2]G and [n-1]+G on on Secp256k1

I apologize in advance for my question. I am trying to make my own simple Secp256k1 calculator, just addition and subtraction, and one thing keeps confusing me. When I add 2 points, and I know what ...
  • 31
1 vote
0 answers
91 views

Is there any relation between Decisional Composite Residuosity Assumption and Square roots in elliptic curve groups assumption?

We have DCRA and ECSQRT assumptions. ECSQRT: Square roots in elliptic curve groups over Z/nZ Definition: Let E(Z/nZ) be the elliptic curve group over Z/nZ. Given a point Q ∈ E(Z/nZ). Compute all ...
  • 11
6 votes
2 answers
983 views

Why are elliptic curves over binary fields used less than those over prime fields?

In practical applications, elliptic curves over $F_p$ seem to be more popular than those over $F_{2^n}$. Is it because operations over prime fields are faster than those over $F_{2^n}$ for the same ...
  • 419
1 vote
1 answer
177 views

Finite field Elliptic Curve line intersection

I want to find the curve points that intersects an arbirtary line, not just tangent line or a line through curve points. An example: ...
1 vote
1 answer
296 views

Verify that x, y coordinates given as hex string are valid points on an Elliptic Curve [duplicate]

Given the following information: "curve": "P-256", "qx": "729C51D177EBE2079A0FB7B0B3C2145159CF81EC61960E642A1744719AA9F913", "qy": "...
  • 11

1
3 4
5
6 7
38