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
0answers
55 views

ECC - complex multiplication and key agreement

I'd like to ask three questions - 2 of them regard CM method. The last is regarding the ECC domain parameters generation on the fly, see https://eprint.iacr.org/2015/647.pdf What role has ...
0
votes
0answers
43 views

Differential representation of binary curve as a public key

Given elliptic curve $E$ over binary field $k$, a public key is the pair $(x,y)$ in $E$ and $x$ and $y$ in $k$. The differential representation of $(x,y)$ is $w = x + y$. What security implications ...
0
votes
1answer
78 views

Simplified ECC non-point public key example, how it works

I know that ECC public key is in fact point on curve calculated by $(x,y) = k \times G$ , while $k$ is random and $G$ is the base point, it performs "Point addition" which involves some math behind. ...
-1
votes
1answer
553 views

How to Find the Generators of an Elliptic Curve

Could someone explain how can I find the generator points of an elliptic curve? For example the generators of the EC: $y^2= x^3+x+6, Z_7$.
0
votes
0answers
104 views

Using division polynomials to prove that EC discrete log is even

This question is related to the other question I recently asked. I'm trying to figure out if it is possible to use division polynomials to prove that knowing $A = a \cdot G$ we can prove that $a$ is ...
1
vote
1answer
114 views

CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?

I am trying to understand the action of the CSIDH protocol. Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{...
2
votes
1answer
99 views

Elliptic curve as a product of 3 cyclic groups possible?

I'm looking for some kind of 3-dimensional Elliptic curve. As far as I know a normal Elliptic curve like $$y^2 = x^3 + ax + b$$ over $F_p$ consists of one or two cyclic groups $Z_m (\times Z_n)$. ...
3
votes
1answer
117 views

Elliptic curves on finite fields

I've been reading: https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf On page 22 it shows an eliptic curve over F17. I have added the orange lines ...
0
votes
0answers
80 views

Sharing secret content with multiple recipients

I have a sender and N recipients, and am thinking of using the following scheme to send secret content to those recipients. This is similar context to a group chat or email. I am no expert in crypto ...
1
vote
1answer
87 views

What is the difference between subtracting the modulus from a scalar field element and reducing it?

When implementing a Field element, we define the necessary operations on the data structure. One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that ...
3
votes
2answers
193 views

Prove I know a value $v$ in a Pedersen Commitment without revealing it

Given a Pedersen Commitment: $P = aG + vH$ Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to. Is there a way to prove I know $v$ ...
2
votes
2answers
118 views

How to model a miniature elliptic curve?

For educational purposes I would need to work on an elliptic curve that has a small field, but holds the safety futures of a real curve. Is that possible to have such a curve!? For example for the ...
0
votes
1answer
96 views

Why only non-prime order fields have small subgroup attacks?

Why don't prime-order curves have small subgroup attacks? It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in ...
3
votes
1answer
81 views

What type of curves have co-factors?

I read that non-primes only have co-factors, but Edwards have a co-factor and it is defined over Fp s.t. P = 2^255 -19 which is prime right? How is the co-factor created, some have co-factor 4 and ...
1
vote
1answer
105 views

For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$

What is the difference between the basefield modulus $Q$ and a subgroup of prime order $r$? They are all fields, but what is their relevance to the curve they are defined upon? How does this relate ...
-1
votes
1answer
233 views

How does Diffie Hellman protocol work in Bitcoin Blockchain Transactions?

Greetings to all! Please explain how the Diffie-Hellman protocol works in Bitcoin? That is, in Blockchain Transactions, there is also a total number of "K" recipient and sender? "K" the recipient and ...
0
votes
0answers
15 views

Are compressed pairings used for Barreto-Naehrig curves in practice?

In 2009 Galbraith and Lin wrote the article "Computing Pairings Using x-Coordinates Only" https://link.springer.com/article/10.1007/s10623-008-9233-3, where they proposed to compute pairings on ...
2
votes
1answer
66 views

In ECC scalar multiplication, how do `add(Q, Q)` exceptions occur?

Consider some scalar multiplication algorithm for a prime order (Weierstrass) curve $E$ with order $\ell$. Bernstein and Lange's SafeCurves: Completeness page mentions: The problem is that the ...
7
votes
1answer
300 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 ...
2
votes
1answer
53 views

Embedding POW in an EC public key

I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys. To do this, I require that the hash of the public key be less than a certain ...
8
votes
2answers
587 views

Geometric interpretation of an Edwards curve

Addition on an elliptic curve in Weierstrass form (over the rationals) is typically depicted with the following figure: (Image CC SA 3.0 https://en.wikipedia.org/wiki/File:ECClines.svg) To add two ...
2
votes
1answer
80 views

How to compare the order of elements in cyclic groups?

In a cyclic group with randomly looking behavior like the one used in secp256k1, is there any known efficient algorithm to compare the order of two randomly given elements $P_1$ and $P_2$ and find out ...
3
votes
1answer
415 views

What is the point at infinity on secp256k1 and how to calculate it?

I hear that there should be a point at infinity on secp256k1. I wounder how to calculate it and what does it even mean. I tried to calculate it as $P_{inf}=P+(-P)$ but this gives different results for ...
4
votes
1answer
124 views

Does Elliptic Curve Integrated Encryption Scheme (ECIES) provide IND-CCA2 security?

I am looking for a faster alternative to RSA with OAEP as a IND-CCA2 public key scheme. Elliptic Curve Integrated Encryption Scheme might be a candidate, but I am not sure if it provides IND-CCA2 ...
7
votes
2answers
920 views

Should we use IANA groups 14 (MODP), 25, and 26 (ECP)?

By looking at SonicWall Knowledge Base article Key exchange (DH) Groups Supported - Site to Site VPN: It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've ...
5
votes
1answer
165 views

Are EC public key values evenly distributed?

At my Day Job(tm) we've encountered a bug wherein if the leading digit of the X or Y value of a public key are zero, "shit happens" (this bug is in our code - I'm not suggesting there's some problem ...
1
vote
1answer
115 views

Could the reversibility of adding function be considered a weakness to secp256k1?

I have just started studying cryptography and secp256k1. I just wonder that adding two points can be easily reversible when the generator point is publicly known. I mean that if $Q=\operatorname{...
2
votes
1answer
146 views

Why SM2 ECC parameters does not specify cofactor h?

Recently I've been studying the ECC with the Chinese SM2 standard. One question is on standard part 5, parameters definition, it only defines $p, a, b, n, XG,$ and $YG$, but not cofactor $h$. I found ...
8
votes
1answer
441 views

Point halving on elliptic curves of even order

I am trying to understand how point halving on elliptic curves of even order works. Specifically: suppose $g$ is an elliptic curve, and $G$ is a generator point on this curve. The order of group ...
2
votes
0answers
127 views

Proving that a point on elliptic curve is smaller than half of group's order

Let's say I have an elliptic curve where generator $G_1$ has prime order $q$. Let's also say I have committed to a point $A_1 = a \cdot G_1$. Could I use the scheme below to prove that $a < \frac{q}...
1
vote
0answers
50 views

Is it necessary to transmit two or three points of an elliptic curve?

Are there cryptographic protocols, where a party should transmit by communication channel simultaneously two or three $\mathbb{F}_q$-points of an elliptic curve over a finite field $\mathbb{F}_q$? ...
2
votes
1answer
172 views

Proving that two points on elliptic curve are within range

Is it possible to prove that a point on an elliptic curve falls within a given range of another point, without revealing the distance between them. For example: Let's say $X$ and $Y$ are two points ...
0
votes
2answers
75 views

Does this pairing-based signature scheme work?

Suppose $g$ is a pairing-friendly elliptic curve with subgroup generators $G_1$ and $G_2$. Suppose also that $M$ is the message I want to sign. Setup Compute $A = a \cdot G_1$ and $P = p \cdot G_2$, ...
2
votes
0answers
55 views

Proving key equivalence across different elliptic curves

We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
2
votes
1answer
74 views

Does this simple signature scheme work?

Let's say my public key is defined as $P = p \cdot G$, where $p$ is my private key and $G$ is a generator point of an elliptic curve. If I wanted to sign a message $m$, could I do the following? Hash ...
1
vote
1answer
221 views

Can a TLS certificate using ECC secp384r1 as PK algorithm uses RSA for signature

If a TLS certificate public-key algorithm is ECC secp384r1 or ECC prime256v1, is it possible to have RSA as a signature ...
1
vote
1answer
785 views

What is the recommended minimum key length for ECDSA signature

I want to identify the proportion of certificates that use unrecommend ECDSA key length for TLS certificates based on some data I collected. By looking at a standard like NIST for example, I find ...
0
votes
2answers
312 views

How can I send a secure public message using ECC? [closed]

I want to know how to send a secure message protected with elliptic curve private and public keys.
2
votes
2answers
68 views

Rational exponents on group generators

In elementary concepts, mostly scalar exponents shows up in group operations: $g^x$ As one may encounter in more advanced papers, there are rational exponents over generators. Simply seems like: $g^...
2
votes
2answers
98 views

Is it secure to encrypt a 1 GB data file with AES-CTR by ECIES?

I have a file system with share resources over the network (like a shared FTP) Is it possible to use the client's ECC public key to encrypt the AES key, and then use the AES in CRT mode for the file ...
2
votes
1answer
88 views

Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?

In ZK Snarks bilinear pairings are used to do "encrypted computation". I was wondering if we can use Partial Homomorphic Encryption or Somewhat Homomorphic Encryption instead of bilinear pairings. Can ...
3
votes
1answer
164 views

Do I need to provide entropy to secp256k1_ecdsa_sign() ?

using secp256k1_ecdsa_sign() I noticed the same data signed multiple times, coming back with the same signature. I always thought that signatures are different because random data is somehow involved....
6
votes
2answers
129 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 + ...
0
votes
1answer
60 views

How to name a signature algorithm that has no hashed component

I have an API-based service that digitally signs messages with RSA or ECDSA (system decides during runtime). The input is base64 encoded SHA-256 hash and the output is: signature of this hash ...
3
votes
2answers
161 views

What risks are involved when choosing a curve for an implementation of ECC?

What risks are involved when specific curves are chosen for an ECC implementation? How should I audit a system that uses ECC with regards to a specific curve? Bonus: How can I (or a cryptographer) ...
6
votes
1answer
171 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 ...
0
votes
1answer
203 views

ECDSA Signing and verifying signatures between Python and JS [closed]

I create a signature on js, here jsrsasign Signatures are obtained in the format: ...
0
votes
1answer
351 views

Equivalent RSA modulus for NIST P-192 and P-521 elliptic curves [duplicate]

At www.keylength.com, I found the following table of ECC field size and the corresponding RSA modulus recommended by NIST. ECC Modulus RSA Prime Size 160 1024 224 2048 ...
11
votes
1answer
190 views

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

I'm especially curious about the technique djb would have used to come up with his Curve 25519. Say I have already written down my goals, such as - Twist Secure, Speed, Side Channel resistance, etc. ...
2
votes
3answers
157 views

For elliptic-curve cryptography, does a 256-bit key imply that $x$ and $y$ are each 256-bits or 128-bits?

In the wikipedia article, the claim is made that "256-bit elliptic curve public key should provide comparable security to a 3072-bit RSA public key". Since, in ECC, the public-key consists of a point $...