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
2
votes
1answer
81 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
1answer
78 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 ...
0
votes
0answers
24 views

Authentication between two servers using PKA

I've run into an small issue regarding authentication between 2 services (One way communication) using public and private key authentication (Elliptic Curve, secp256k1). The services will communicate ...
6
votes
1answer
73 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....
0
votes
3answers
115 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
2answers
50 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 ...
1
vote
0answers
38 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 ...
1
vote
0answers
34 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 ...
0
votes
1answer
154 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: ...
0
votes
1answer
30 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
2answers
92 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. ...
0
votes
1answer
47 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
1answer
106 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
1answer
115 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 ...
0
votes
0answers
37 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
1answer
2k 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
3answers
180 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 ...
1
vote
1answer
76 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
1answer
679 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
2answers
126 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
1answer
143 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
1answer
148 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
1answer
56 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
1answer
31 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 ...
1
vote
0answers
23 views

Composite order ECC and Ristretto

I've been looking at ristretto.group, and its really cool. I understand for some protocols we need curve points to behave as if they were from a prime order curve. I have a few questions on this, Do ...
2
votes
0answers
73 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 ...
0
votes
1answer
82 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
1answer
47 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?
0
votes
0answers
77 views

The security level on BN254 and BLS381

Does BLS12-381 still provide 128bits security level? How about BN12-254? 112bits? Is there any references about the security level on pairing?
2
votes
1answer
64 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
1answer
90 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 ...
4
votes
2answers
114 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 ...
2
votes
1answer
907 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 ...
0
votes
0answers
33 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
1answer
124 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 ...
2
votes
1answer
53 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
0answers
36 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
2answers
92 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 ...
3
votes
1answer
95 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 ...
1
vote
1answer
25 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 ...
7
votes
2answers
868 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 ...
2
votes
1answer
74 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
1answer
182 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 ...
1
vote
0answers
50 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 ...
6
votes
2answers
608 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 ...
1
vote
1answer
154 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
1answer
120 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": "...
4
votes
1answer
148 views

Can the security of ECDSA be compromised by the chosen parameters?

The recommended parameters for a secp256k1 ECDSA curve are: (All values are in hexadecimal) ...
1
vote
1answer
95 views

A few questions about the elliptic curves functionalities

I've been learning about the elliptic curves and how they work, and their usage in cryptography, and I'm trying to figure out how to use them using Go. Where is the 'a' parameter from my ECC equation ...
1
vote
1answer
28 views

How are the points computed in the ElGamal elliptic curve encryption algorithm?

I was looking at an example of the ElGamal encryption operation here (page 24), but I can't seem to understand why: $$\beta = 3(10, 3) = (10, 8)$$

1
2
3 4 5
36