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,127
questions
9
votes
1
answer
1k
views
Isn't the security of EC curve 25519 126 bits?
The security of the EC25519 is given as 128 bits, but since the order of the group is 252 bits shouldn't the security be 126 bits? Given as half the magnitude of the underlying field, since DLP ...
- 235
9
votes
1
answer
388
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 ...
- 15.1k
9
votes
1
answer
3k
views
Base point in Ed25519?
The paper "High-speed high-security signatures" by Bernstein et al. introduces the Edwards curve Ed25519.
Concerning the base point $B$, it says that
$B$ is the unique point $(x, 4/5)\in E$ for ...
- 989
9
votes
1
answer
8k
views
Elliptic Curve SSL performance: ECDHE and/or ECDSA?
I have a question about the performance benefits (in terms of server-side CPU load) of ECC (Elliptic Curve cryptography) cipher suites in SSL/TLS.
It is a known fact that ECC is very good for ...
- 91
9
votes
2
answers
6k
views
Complete Set of Test-Vectors for ECDSA secp256k1
Although there are several implementations of ECDSA secp256k1 public available over the internet (the most popular being OpenSSL), it seems that there are no complete set of test-vectors available.
...
- 203
9
votes
1
answer
2k
views
Simple digital signature example that one could compute without a computer?
I am working on a document to explain Bitcoin to students. But I am having a hard time translating the principle described in §2 of the Bitcoin whitepaper in layman's terms.
There is a great question ...
- 207
9
votes
1
answer
324
views
Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing
Are there any examples of practical attacks on cryptosystems set over elliptic curves which utilize the easiness of DDH for certain choices of curves $E(\textbf{F}_q)$, and as such their lack of ...
- 373
9
votes
2
answers
404
views
Why develop Edward curve formulas that deviate from unification?
Edward curves were considered initially because they provide a unified formula for both doubling and addition, thus having inherent side-channel resistance. But a lot of work has been done recently ...
- 121
9
votes
0
answers
192
views
Parity of the order of a element
Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $g$ has even or odd order. In other words $\textrm{ord}(g) \bmod 2$ can be computed easily.
In some cases where the ...
- 269
8
votes
3
answers
4k
views
Which Diffie-Hellman Groups does TLS 1.3 support? And should we use TLS 1.3 as a guide?
This is a two part question - and I'm asking as someone moving into a security role, who'll need to standardize practices going forward.
(1) I'm curious whether the following 10 different DH Groups ...
- 205
8
votes
1
answer
895
views
RFC6979: error in reference implementation?
If I correctly understand RFC 6979, there is an error in the ref implementation section 3.2.
In the step H2, RFC specification says
...
- 413
8
votes
2
answers
2k
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 (pk) - private (sk) key pair (Ed25519).
In DB we store a public key.
Is ...
- 263
8
votes
1
answer
4k
views
Curve25519 vs "Million Dollar Curve"
Quoting from the Million Dollar Curve website:
By using publicly verifiable randomness produced in February 2016 by many national lotteries from all around the world, we propose to generate a ...
- 2,814
8
votes
1
answer
463
views
What are the characteristics of a quantum secure protocol?
What are the characteristics of quantum secure protocol, and does it always need to be information theoretic to be called as quantum secure? Are the current techniques used in bitcoins quantum secure?
- 543
8
votes
2
answers
330
views
Is the elliptic-curve cryptography library libsecp256k1 not susceptible to the Hertzbleed attack?
I was reading up on the recently disclosed Hertzbleed side channel attack(s).
It was speculated on Twitter that the elliptic-curve cryptography library libsecp256k1 is not susceptible to these attacks....
- 197
8
votes
2
answers
985
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
8
votes
1
answer
2k
views
How can I generate a Koblitz curve?
Is there the way to generate new Koblitz curves, over $\mathbb F_{2^n}$ and $\mathbb F_p$?
The Certicom SEC 2 standard says:
The recommended parameters associated with a Koblitz curve were chosen ...
- 165
8
votes
2
answers
815
views
Rely on NSA Suite B Cryptography?
NSA's Suite B Cryptography suggests some cryptographic algorithms for encryption, digital signatures, message digests and key agreements. The selected algorithms and their key size are suggested by ...
8
votes
1
answer
2k
views
What does the $\|$ operation mean in cryptographic notation?
I am studying elliptic curves problems, which also includes study of related protocols such as ECIES. The problem is that I don't understand the notation $\|$. What does this operation mean?
Some ...
- 95
8
votes
1
answer
17k
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 ...
- 407
8
votes
1
answer
423
views
Elliptic Curve Cryptography - When to use p and when to use n
Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems.
So far I'...
- 786
8
votes
1
answer
1k
views
How to derive the curve Ed25519 from Curve25519?
According to the paper "Faster addition and doubling on elliptic curves" by Bernstein and Lange, the Montgomery curve (Curve25519) $$v^{2}=u^{3}+486662\cdot u^{2}+u$$ is birationally equivalent to the ...
- 989
8
votes
2
answers
9k
views
Explanation of each of the parameters used in ECC
I'm having a very difficult time finding a clear explanation of the parameters used elliptic curve cryptography. I know for certain that $p$ is the number or order or whatever of the given field that ...
- 3,635
8
votes
1
answer
4k
views
Montgomery Ladder vs Double-and-Add
I would like to know what (if any) are the advantages of using Montgomery Power ladder over the Double-and-Add-Always algorithm.
I think that firstly, Monty would be slightly faster than DoubleAndAdd. ...
- 408
8
votes
1
answer
979
views
Replacing Curve25519 with Ristretto255
Quoting Ristretto255 for the PHP Community,
Ristretto255 is Ristretto defined over Curve25519, which allows cryptographers to extend the Ed25519 signature scheme to support complex zero-knowledge ...
- 2,895
8
votes
1
answer
743
views
Point-at-infinity and error handling
I'm looking at a piece of (non-object oriented) code where functions return point-at-infinity for a specific prime curve if a calculation errors out. This is even the case when validating arguments to ...
- 91.8k
8
votes
2
answers
4k
views
Do Weak Elliptic Curves Exist?
I'm running into very contradictory opinions when try to understand if weak elliptic curves exist. I'm not interested in the case when a curve's weakness is attributed to properties of an EC's prime, ...
- 346
8
votes
1
answer
3k
views
Understanding Twist Security with respect to short Weierstrass curves
I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves.
That section claims ...
- 6,904
8
votes
1
answer
2k
views
Fast modular reduction
I am looking at ways to speed up modular reduction for the polynomial
$$2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$$
I have read the paper "Generalized Mersenne numbers" by J.A. Solinas, but it does not ...
- 111
8
votes
1
answer
273
views
Can somebody explain the major contributions of the tenants of the Gödel Prize 2013?
As you may know, the Gödel Prize 2013 will be awarded this year to cryptographers (see this ACM press release). The people awarded are Antoine Joux, the team of Dan Boneh and Matthew K. Franklin.
Can ...
- 605
8
votes
1
answer
3k
views
How to represent point-at-infinity in affine coordinate
In projective coordinates point-at-infinity can be identified with z=0. How to identify the point-at-infinity in affine coordinate.
Whether x=0 and y=0 can be considered as point-at-infinity in ...
- 181
8
votes
2
answers
6k
views
Are there any elliptic curve asymmetric encryption algorithms?
RSA offers the functionality of encrypting (short messages, or symmetric keys) with a public key, and decrypting with a private key. However, RSA key generation is extremely expensive, especially for ...
- 3,945
8
votes
1
answer
2k
views
NSA removed EC-256 and SHA-256 from CNSA recently--should we be alarmed by this?
Recently, the NSA (re-published?) their CNSA guidelines and some information on post-quantum computers (per the title of the document).
Here's the link for convenience (document is titled, 'Quantum ...
- 135
8
votes
1
answer
3k
views
Converting Ed25519 public key to a Curve25519 public key
I understand that:
$$x_{montgomery} = \frac{1 + y_{edwards}}{1 - y_{edwards}}$$
Using the libsodium ed25519 implementation, I have tried to write the following:
...
user7868
8
votes
1
answer
2k
views
Standardized parameters for elliptic curve cryptography
When an elliptic curve-based cryptosystem is deployed, a single set of public parameters (consisting of a particular elliptic curve over a finite field as well as a generator of a prime order subgroup ...
- 2,115
8
votes
1
answer
382
views
Are there security issues with discrete logarithm keys not being uniformly distributed?
Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both ...
- 1,704
8
votes
1
answer
4k
views
Pollard's kangaroo attack on Elliptic Curve Groups
Let's say I've intercepted some bits of a Diffie-Hellman private key: $x = n \mod r$. I can get the remaining bits by doing a kangaroo search. This algorithm works over $\mathbb{F}_p$. Can it be ...
user47922
8
votes
1
answer
464
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 (...
- 145k
8
votes
1
answer
322
views
Bob has an EC key pair. How can he receive a small integer in the least compute intensive way?
Alice wishes to send Bob a number $n$ between 0 and 255.
Bob has a private, public EC key pair $(b, B)$ where $B = bG$ and $G$ is an already agreed upon base point on the ed25519 curve.
Alice could ...
- 4,712
8
votes
1
answer
1k
views
How can ECDSA signatures be shortened (to be used as a product key)?
So I made my own serial key generation software, using ECDSA, for use in my own applications and it works great so far! To keep the serial key short enough I use a 128 bit EC curve. My final signature ...
- 261
8
votes
0
answers
151
views
Software timing attack using Kocher method
What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$?
I'm working from this paper: Volker ...
- 83
8
votes
0
answers
339
views
Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard? [duplicate]
I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but ...
7
votes
3
answers
2k
views
How can there be insecure elliptic curves if the discrete logarithm problem is hard?
The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure ...
- 15.2k
7
votes
2
answers
8k
views
In elliptic curve, what does the point at infinity look like?
We know that for each point $P$ on curve $E$ there exists a minimum scalar $k$ such that $kP$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only ...
- 218
7
votes
2
answers
798
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 + ...
- 73
7
votes
2
answers
2k
views
Is it possible to compute the y-coordinate of a point on SECP256K1, given only the x-coordinate
Given an x-coordiante of a point on the SECP256K1 curve, is it possible to calculate the corresponding y-coorindate? (Assuming the point is a verifying public key that complies with the Bitcoin ...
- 181
7
votes
1
answer
5k
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 ...
- 243
7
votes
3
answers
582
views
Do I understand (below) why Q = dP is easy while finding d is hard
As we all know for discussion of Dual_EC_DBRG, the point on an elliptic curve Q can be calculated from P and some (large) integer d
$Q = dP$
And we know that knowledge of Q and P is not sufficient ...
- 324
7
votes
2
answers
19k
views
With OpenSSL and ECDHE, how to show the actual curve being used?
Using
openssl s_client -host myserver.net -port 443
I can see the cipher negotiated is indeed using ECDHE for session key ...
- 447
7
votes
3
answers
3k
views
Timing Attacks on ECDSA, ECDHE, AES and SHA2
Are there any known timing attacks (both practical and theoretical) on any implementations of the following?
ECDSA (I'm aware of this one - are there any applicable to prime fields?),
ECDHE (again, ...
- 1,192