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.
1,173 questions
3
votes
0answers
16 views
EC non-shared cryptosystems - different group for every party
Efficient Identity Based Parameter Selection for Elliptic Curve Cryptosystems by Arjen K. Lenstra contains a proposal for a non-shared elliptic curve cryptosystem. Every party chooses its own field ...
0
votes
1answer
23 views
Does Proxy re-encryption can re-encrypt large data?
Many resources talk about the benefit of Proxy Re-encryption (PRE) and I also implement my PRE using Elliptic Curve key pair. But after I set up Global parameters, I can encrypt very small data maybe ...
2
votes
1answer
62 views
Generating a key pair using a signature generated by an existing key
I’ve built an app in which each user has a private/public key pair and I want to generate a second one for them, however I cannot store the second private key anywhere.
What would be the drawbacks ...
1
vote
0answers
39 views
Reason for including the public key of the key agreement in the KDF
I found the following text when looking up KDFs:
In comparison, the so-called DHAES mode in IEEE 1363a mandates to use the binary representation of the sender’s public key as an input parameter.
...
2
votes
1answer
46 views
Generating a small EDDSA curve
I have an application that would benefit from very small (e.g. 16-20 byte) EDDSA keys and small signatures. It's an application where the goal is more to deter DOS attacks than "hard" security, so ...
-1
votes
1answer
52 views
Equivalence of cryptographic problems
Are integer factorization, discrete log and ECDH problems equivalent?
I know that factorization and discrete log are equivalent but are one of those two problem equivalent with ECDH? Cand someone ...
-1
votes
0answers
29 views
Is simple EC arithmetics enough to construct security proofs?
Using the simple rules of modular arithmetics for Elliptic Curves, including associative and commutative rules for $+$ and $*$, where uppercase letters are points and lowercase are scalars on the ...
0
votes
0answers
54 views
Is RSA in decline across the board?
From what I gather from the internet (source), the recommended practice for 2019 and beyond is to avoid RSA and use ECDH and ECDSA.
Is this the general case?
-1
votes
0answers
48 views
Finding $P$ when we know $2\times P$ in given Elliptic Curve [duplicate]
For a given elliptic curve $E$ like this $y^2 = x^3 + Ax + B \pmod p$, can we find the point $P$ if we know that the $Q = 2\times P = (a, b)$?
For example $E:\ y^2 = x^3 + x + 1 \pmod {10007}$, we ...
6
votes
0answers
58 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 ...
-2
votes
1answer
46 views
Elliptical Curve Actual Encryption
Im havirng a had time understanding ECC. For example, I have the equation below:
...
-1
votes
0answers
37 views
How to do the shortcut function in ECC when N (Private Key) is Known
When N or private key is known, we don't have to iterate through all the process just to get the final location given the two initial points. How is that shortcut function implemented given the ...
-1
votes
0answers
61 views
ECC: Counting points on $E:y^2+xy= x^3+5x+6$ over $GF(2^3)$
How to exactly count the number of rational points on the elliptic curve over the $GF(2^3)$ where the curve equation is
$$E:y^2+xy= x^3+5x+6$$
1
vote
1answer
54 views
How can you derive a P-256 public key from the X and Y points
Deriving a secp256k1 public key is also possible. For whatever reason, I'm only being provided X and Y, not the public portion.
I just need to get the binary representation of the public key given ...
4
votes
3answers
420 views
Pedersen commitment in elliptic curves
I try to understand Pedersen commitment in elliptic curves over finite fields. I could use some clarification.
Let's say we have two generators $G$ and $H$.
Is that required that $G$ and $H$ are ...
2
votes
0answers
29 views
Precomputation attacks against ECDH
Diffie-Hellman groups are vulnerable to sieving precomputation attacks. These attacks allow a one-time computation against a given DH modulus that makes it practical to attack all subsequent key ...
3
votes
1answer
127 views
+50
What is this EC key derivation method called?
I'm looking to identify the EC key derivation method used in Hyperledger Fabric. I can't find anything in the docs or the protocol specs, but the functions' code is here for the private key and the ...
12
votes
2answers
656 views
What motivated the creation of RSA and ECDH?
Recently I've been learning about cryptography and so far I am loving it. However, there are some things I do not comprehend.
As far as I know, RSA was published in 1979 while New Directions on ...
6
votes
2answers
633 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 ...
1
vote
0answers
54 views
Patterns in elliptic curve division polynomials
While looking at division polynomials of elliptic curves in relation to this and this questions, I noticed some patterns. I am wondering if anyone knows of general formulas the describe these patterns....
0
votes
0answers
26 views
Hash function a ring-signature-based range proof
For a ring-signature-based range proof (e.g. Ring Confidential Transactions , section 5.0.1) it is required to use some hash function from $\{0,1\}^* \to \text{scalar}$.
Is it safe to take for this ...
3
votes
0answers
26 views
EC-ELGAMAL message mapping
I have been able properly set up an EC-elgamal protocol by using algorithms available in an IP that I have developed. Everything works fine, except for the fact that I haven't been able to completely "...
1
vote
1answer
57 views
Can specific Weierstrass curves be some benefit from Montgomery/Edward form?
I have noticed that DBL/diffadd in Edward/Montgomery form almost double fast than Weierstrass form(EFD), and curve25519 is empressive high-performance.The transformation between these forms can be ...
2
votes
0answers
40 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
42 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
70 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
86 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
68 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
59 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
67 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
50 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
79 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
123 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
103 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
58 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
70 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
44 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
89 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
10 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
47 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
263 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
44 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
521 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
62 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 ...
2
votes
1answer
110 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
63 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
436 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
122 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
76 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{...
