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.
2,125
questions
17
votes
3
answers
5k
views
What does the special form of the base point of secp256k1 allow?
The popular ECC parameters secp256k1 are documented in SEC2 as using curve $y^2\equiv x^3+a\cdot x+b\pmod p$ with $a=0$, $b=7$, $p=2^{256}-2^{32}-\mathtt{3d1_h}$, base point $G$ with the apparently ...
- 138k
0
votes
0
answers
40
views
Ed25519 and sealed boxes libsodium
Accidentally used ed25519 public key to create libsoidum_sealed_box. Is there any way to decrypt the data if the private key ed25519 is known?
3
votes
0
answers
90
views
EC public key with leading zeros
Let us take example of secp256k1 curve. The current known public key with most leading zero (in x cordinate) is:
...
- 138k
2
votes
1
answer
628
views
Ed25519 to X25519 transportation
Using
montgomeryX = (edwardsY + 1)*inverse(1 - edwardsY) mod p
it is possible to transport an Edwards curve point (Ed25519 ...
- 47.6k
1
vote
0
answers
61
views
Does ECC give the most secure assymetric cipher for a given public key size?
Cracking an ideal block cipher is basically a brute force key enumeration. The complexity of the attack is exponential, growing as $2^b$. Cracking ECC is also exponential, but the cost grows as $2^{\...
- 138k
0
votes
0
answers
18
views
Is ECC by far the most secure two-key cipher of equal key length? [duplicate]
As far as I know, to crack the block cipher is basically a violent enumeration, the complexity is exponential, but the ECC cracking is still only sub-exponential, so whether there is a better double-...
- 21
3
votes
1
answer
1k
views
Why do we need additional secret value (k) in ECDSA?
Formula for calculating an ECDSA signature (r, s) is:
s = k-1(z + qr)
k - private key for a random point R
z - hash of a message
q - original private key
r - x(R)
I am interested in why do we need ...
- 138k
2
votes
1
answer
207
views
Elliptic Curve digital signature algorithm without "hashing to point"?
Through " Why do we need to convert hashes to points on an elliptic curve? ", I found out why Hashing to Point is necessary.
However, using the algorithm below can sign and verify without ...
CommunityBot
- 1
1
vote
2
answers
225
views
Can I move elements from cyclic subgroup to its cyclic parent group?
The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.
I know that elements of a non-prime order cyclic group G can be moved to its subgroup H by a process called &...
CommunityBot
- 1
2
votes
1
answer
226
views
Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?
Specifically, I want an algebra group $G$ (or ring $R$) features:
Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy.
Given an element $g \in G$ (or $R$ ), finding the ...
- 138k
4
votes
1
answer
1k
views
Ed25519 key generation
the following rfc describes the key-pair generation mechanism for Ed25519; the first two steps are as follows:
Hash the 32-byte private key using SHA-512, storing the digest in
a 64-octet large ...
- 103
-2
votes
3
answers
94
views
Understanding Point Negation in secp256k1 Elliptic Curve
I'm exploring the secp256k1 elliptic curve in the context of cryptography and encountered the concept of Point negation. I would appreciate clarification on what point negation means in this context.
...
0
votes
2
answers
89
views
Determining the order of operations in elliptic curve cryptography: Point doubling vs point addition for obtaining x and y values of a public key
I have a question regarding the operations performed on an elliptic curve, specifically related to point doubling and point addition. I am trying to understand whether it is possible to determine the ...
- 9
1
vote
0
answers
66
views
Can the byte overhead of an ECDH based hybrid cryptosystem be reduced by encoding data in ephemeral key?
Motivation
I have a use case that involves sending small (25-50 byte) encrypted messages over a very constrained channel. Many senders send public key encrypted messages to other receivers. Anonymity (...
- 91.7k
0
votes
1
answer
153
views
Implementing Floor Division on secp256k1 Elliptic Curve in Python
I understand that the // operator is used for floor division in regular arithmetic
result = 7 // 3 # This will result in 2
but ...
- 47.6k
42
votes
2
answers
26k
views
How does recovering the public key from an ECDSA signature work?
It is possible to recover the public key from an ECDSA signature values $(r,s)$?
Please explain how this works.
- 101
0
votes
0
answers
48
views
Efficiently using BSGS or other algorithms if key range is known on Elliptic Curves
Let $X$ be a point on an elliptic curve such that $X = [x]G$, where $G$ is a generator. Let us assume that we know $x$ is something $x = 65t + 1$ where $t$ is an integer.
Now if I know that the key ...
- 47.6k
1
vote
1
answer
171
views
Key exchange for encrypted firmware update
I'm trying to implement encrypted firmware update functionality for an embedded device. The goal is to prevent reverse engineering of our firmware when the update files are shared with our customers.
...
- 23
2
votes
1
answer
96
views
Recover Y coordinate from xz elliptic curve multiplication
I have an elliptice curve in the form
y² = x³ + ax + b (mod p)
And I have a multiplication algortihm which uses only x and z coordinate
How can I recover the Y coordinate ?
I tried to use the curve ...
- 47.6k
2
votes
2
answers
180
views
How to recover y-coordinates when using XZ montgomery curve
I am using Montgomery ladder with Montgomery curve $by^2=x^3+ax^2+x$ using XZ coordinates and I recovered the $X$ value using $X3=X1/Z1$, but I don't know how to recover the $Y$ coordinates.
for ...
- 47.6k
0
votes
1
answer
111
views
Trouble detecting cyclic group order crossovers in SECP256K1
There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary
For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars),...
2
votes
2
answers
90
views
Is it possible to check pedersen commitment is of postive or negative number without knowing the original value
I generated a Pedersen commitment for a given account balance (say, 10) and stored it in the ledger. Now, when I debit 15 tokens from the same account, I first retrieve the Pedersen commitment of 10 ...
- 145k
1
vote
2
answers
107
views
Why is the Montgomery ladder algorithm safe against timing side-channel attacks?
I'm trying to understand the security of the Montgomery ladder algorithm in the context of timing side-channel attacks. I'm looking at the algorithm from wikipedia
While I know that the algorithm ...
- 1,108
0
votes
0
answers
29
views
Three ECDSA signatures sharing first component r, verifying against same message and public key?
For some common curve, can we exhibit three distinct ECDSA signatures $(r,s_1)$, $(r,s_2)$, $(r,s_3)$, a message $m$, and valid public key $Q$, such that the signatures verify?
Can we also generate ...
- 138k
2
votes
0
answers
40
views
SRP on elliptic curves: replacing + and - operations?
I was thinking about how SRP might be used with Curve25519 or Curve448. In this question, Can SRP be used with Elliptic Curves?, the answer is that you can't directly translate SRP to a group that ...
- 2,513
2
votes
1
answer
178
views
Point halving formula for Koblitz curve over prime field
Consider a Koblitz elliptic curve over a prime field $\mathbb F_p$, with equation $y^2=x^3+b$, prime order $n$ close to (but different from) $p$. This includes secp256k1, secp224k1, secp192k1, ...
- 47.6k
160
votes
4
answers
53k
views
Should we trust the NIST-recommended ECC parameters?
Recent articles in the media, based upon Snowden documents, have suggested that the NSA has actively tried to enable surveillance by embedding weaknesses in commercially-deployed technology -- ...
- 47.6k
1
vote
1
answer
125
views
Double- and -add algorithm
I am currently doing the elliptic curves and I'm stuck for 8 hours without finding solutions. I under stand the process of double and add but don't know how to obtain 5 * 8P = 4OP =11 P. 11 P was in ...
- 47.6k
1
vote
1
answer
94
views
Double and Add using NAF
I am new in Elliptic curve, so I started with implementing (single scalar multiplication) I have done it the simple way, and then I moved to Double & Add algorithm later with NAF form.
When I ...
CommunityBot
- 1
2
votes
1
answer
79
views
What would be the security consequences of replacing $H(R, A, M)$ with $H(R, M)$ in EdDSA?
The question is mainly stated in the title. We don't consider any other changes to the scheme except for the following:
We replace $S = H(R,A,M) \cdot a + r$ with $S = H(R,M) \cdot a + r$.
My thoughts ...
- 878
1
vote
1
answer
170
views
Finding scalar in scalar multiplication on secp256k1 elliptic curve
In elliptic curve cryptography using the secp256k1 curve, how can I determine the number of times the base point $G$ has been multiplied to derive a new point? The formula is as follow:
$k * G = Q$
...
- 138k
1
vote
1
answer
105
views
Is there a ZKP that proves knowledge of a particular elliptic curve point?
Let E be an elliptic curve of prime order n. If we assume that Alice and Bob both know a scalar value ...
CommunityBot
- 1
3
votes
0
answers
105
views
Elliptic Curve Scalar Multiplication - Boneh & Shoup
I'm currently reading the 'A Graduate Course in Applied Cryptography' paper written by Boneh and Shoup. More precisely, I'm reading the chapter about 'Elliptic Curve' and I'm stuck at the exercise ...
- 47.6k
7
votes
2
answers
2k
views
Difficulty of Reversing Elliptic Curve
In ECC, it is apparently easy to verify the final point given the starting point and the number of hops. But it is difficult to compute the number of hops given just the starting point and the final ...
- 138k
-1
votes
1
answer
156
views
Why don't secp256k1 use a prime order subgroup?
Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack. Meanwhile, secp256k1 doesn't use a ...
- 47.6k
0
votes
0
answers
33
views
can ownership proofs be added to circuits to make them zk-snark resistant to quantum proof forgery attacks?
According to my previous question the proofs cannot be broken by quantum computation, you cannot obtain the witness of the generated zk-snark proof.
link to my previous question.
Now if the concern is ...
- 3
4
votes
1
answer
675
views
Is it true that Public keys with even y coordinate correspond to private key that are less than n/2 and vice versa? (Secp256k1)
The question is somewhat complex and directed to clearing things out.
Suppose that $n$ is the order of the cyclic group. It $n - 1$ is the number of all private keys possible
...
- 47.6k
2
votes
1
answer
195
views
Which benefits do Twists of elliptic curves bring?
I understand that an elliptic curve $E$ over a field $K$ has an associated twist, that is another elliptic curve which is isomorphic to $E$ over an algebraic closure of $K$.
Which cryptographic ...
- 91.7k
0
votes
1
answer
80
views
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
can secrets be deciphered from the proofs generated with ZK-Snarks if a quantum attack were plausible?
I understand the concern that ZK-snarks and some of their cryptography may be broken by quantum ...
- 360
0
votes
0
answers
50
views
Framework for manipulating digital signatures
for a research project, i am currently looking for a way to manipulate the digital signature of a HTTPS TLS message flow. More specifically, i am trying to create a working example for a malicious ...
8
votes
1
answer
457
views
Who originally generated the elliptic curve now known as P256/secp256r1
Background: there is a theory going around that claims that P256 was backdoored by the NSA. The theory goes is that the NSA found a weakness that applies to a nontrivial fraction of elliptic curves (...
- 1,587
2
votes
1
answer
691
views
How can I split a packed Ed25519 public signing key into its X and Y coordinates?
I'm using the Curve25519 code (from http://www.dlbeer.co.nz/oss/c25519.html), and trying to convert from a public signing key (Edwards form) to a public key-exchange key (Montgomery form). There's ...
2
votes
2
answers
130
views
Elliptic curves over extension fields
I'm trying to understand which benefits can using of extension fields in elliptic curve cryptography bring over prime fields. Popular curves like secp256k1, curve25519, secp384r1 are defined over a ...
- 2,095
-1
votes
1
answer
156
views
Can the public key be derived from the private key? [closed]
The calculation/formula i use in deriving a public key from the private key without importing any module in python3 script involves the following steps:
Define the parameters of the secp256k1 ...
- 47.6k
3
votes
2
answers
229
views
Could a EC public key have zero coordinate?
Take secp256r1 as an example, the parameter of the curve is
...
- 133
-2
votes
1
answer
136
views
Validating slope (s) in secp256k1 elliptic curve
knowing the coordinates of $R$ on secp256k1 and an integer $s$, how do we validate that $s$ is the slope at the point $Q$ on secp256k1 such that $R=2Q$ ?
- 29
-1
votes
1
answer
272
views
How to convert (Rx1 and Ry1) to (Rx2 and Ry2)
I'm working with the secp256k1 elliptic curve and have point doubling and point addition formulas for this curve.
If a point is given $Q_x$ and $Q_y$
...
- 29
1
vote
2
answers
105
views
Deriving $y$-coordinate
Is there any formula for deriving the $y$-coordinate using the $x$-coordinate and the slope in the secp256k1 elliptic curve?
For example:
Calculate the slope:
...
- 91.7k
1
vote
2
answers
268
views
PAGE 2: Can I move elements from cyclic subgroup to its cyclic parent group?
We will continue our previous topic here⬇️ for clarity...
The following context is based on elliptic curves in short-weierstrass form y^2 = x^3 + b.
pls read carefully-
I am looking for a function/...
- 21
10
votes
1
answer
3k
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 ...
CommunityBot
- 1