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,240
questions
11
votes
2
answers
2k
views
Summarize the mathematical problem at the heart of breaking a Curve25519 public key
It's pretty easy to generate a Curve25519 private key: generate 32 random bytes of data and then do:
e[0] &= 248
e[31] &= 127
e[31] |= 64
You can then ...
- 227
11
votes
4
answers
1k
views
RSA & DH at risk due to math advances, will this eventually affect elliptic curves too?
I was looking into the predictions by some researchers that RSA and Diffie-Hellman may not be secure in the next few years due to advances in math and being able to calculate the discrete logarithm ...
- 415
11
votes
3
answers
521
views
What's up with unnamed elliptic curves in e-passports?
At my work I deal with the cryptographic aspects of the international E-Passport specification (the crypto chips embedded in your passports, the kiosks at airports that talk to them, and the ...
- 3,647
11
votes
2
answers
5k
views
Why are NaCl secret keys 64 bytes for signing, but 32 bytes for box?
Ed25519 secret and public keys can both be represented in 32 bytes. Why does NaCl use 64 byte signing keys?
- 4,760
11
votes
1
answer
3k
views
Is every point on an elliptic curve of a prime order group a generator?
If the order of elliptic group is prime then every point is a generator of that group.
I tested the above statement on some elliptic curves and found it true.
Does that really work on all curves?
Is ...
- 121
11
votes
1
answer
2k
views
Key exchange using ECDH vs ECIES?
I'm a beginner to ECC crypto programming. Can anyone explain to me the difference between using ECDH for shared key exchange and the use of ECIES by encrypting a shared key with the public key of the ...
- 275
11
votes
2
answers
7k
views
How to derive a symmetric key from ECDH shared secret?
I am trying to implement the internal primitives of ECDH. Currently I'm able to multiply the receiver's public EC point with the sender's private key to arrive at the shared EC point. Next step is to ...
- 267
11
votes
1
answer
2k
views
ECIES vs. RSA + AES
I am confused about the distinction between RSA and ECC (Elliptic curve) regarding encryption and would appreciate it if someone could confirm whether my understanding is correct.
To encrypt a large ...
- 569
11
votes
1
answer
3k
views
curve25519 weak points for contributory behaviour
The Diffie-Hellman on curve25519 is usually calculated using the base point $(9,…)$ which induces a cyclic subgroup of $G:=\{\infty\}\cup(E(F_{p^2})\cap(F_p\times F_p))$ with index 8, i.e. there is a ...
- 562
11
votes
1
answer
5k
views
Mapping of message onto elliptic curve and reverse it?
I would like to perform a variant of Elliptic Curve ElGamal in java using the BouncyCastle libraries.
I currently face the difficulty of mapping a message $m$ onto the elliptic curve $E_p$. I have so ...
- 213
11
votes
1
answer
319
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. ...
- 213
11
votes
1
answer
5k
views
ECDSA vs RSA: Performance on Android platform and surprising results
For our privacy-preserving protocol, an encrypted channel is established. In order to protect our system from man-in-the-middle attacks, a signature-based approach is used. After we've implemented it ...
- 453
11
votes
1
answer
1k
views
HD (Hierarchical Deterministic) Keys using Safe Curves?
Bitcoin's HD (Hierarchical Deterministic) Keys as described in BIP32 allow for a master key to be created (a private key and a chain code) such that a tree of both public and private keys can be ...
11
votes
1
answer
1k
views
Why are elliptic curves over a field of characteristic 2 or 3 insecure?
The following is a quotation from my cryptography course:
Recent results on the discrete logarithm raise big concerns on the security of elliptic curves over a binary field.
What are these ...
- 1,243
10
votes
2
answers
5k
views
Ed25519 is a signature or just elliptic curve
Ed25519 is a signature or just elliptic curve?
EDDSA is signature, what using curve ed25519?
- 133
10
votes
2
answers
1k
views
What is a "constant time" work around when dealing with the point at infinity for prime curves?
I've been working for some time, on designing a constant time solution for dealing with the "point at infinity" for prime curves. So, far I'm using the Standard Projective Coordinates for ...
- 1,060
10
votes
1
answer
3k
views
Is the term "Elliptic Curve Discrete Logarithm Problem" a misnomer?
I have just started studying Elliptic Curve Cryptography, and I have this doubt. In ECC the group operation is addition (and not multiplication). So, why is ECDLP stated as a variation of the discrete ...
- 103
10
votes
2
answers
2k
views
How do malware rely safely on ECDH algorithm to maintain secrecy of keys?
In traditional malware (especially ransomware) using RSA approach, the public key may be hard-coded in the malware binary and is used to encrypt a symmetric key generated on the system. The symmetric ...
- 687
10
votes
1
answer
1k
views
How are curve names constructed?
I started with the question: Brainpool curves exist in a variant ending in ..r1 and ..t1. What does it mean?
But there are also "secp.." and "sect.." just like NIST's "..r1&...
- 261
10
votes
2
answers
3k
views
Why are elliptic curves constructed using prime fields and not composite fields?
I come across this:
Numbers mod composite number does not form a field rather it forms a ring
and
every number has a multiplicative inverse under integer mod prime
Maybe these are the reasons ...
- 492
10
votes
1
answer
5k
views
Why can ECC key sizes be smaller than RSA keys for similar security?
I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted ...
- 103
10
votes
3
answers
2k
views
Curve 25519 (X25519, Ed25519) Convert coordinates between Montgomery curve and twisted Edwards curve
I have some misunderstanding about EdDSA conversion coordinates between Montgomery curve and twisted Edwards curve. In https://www.rfc-editor.org/rfc/rfc7748 I see that a base point for Curve25519 is
...
- 248
10
votes
1
answer
912
views
Visualization of Elliptic Point Addition [closed]
In an introductory text, I found that point addition for elliptic curves can be made plausible as follows:
Given two Points, P, Q, the sum is defined as the point on the curve I get by connecting P ...
- 1,507
10
votes
1
answer
9k
views
ECDH or RSA more secure for symmetric key wrapping?
Suppose a message is encrypted with a symmetric block cipher with a random key. RSA is often used to wrap the symmetric key using the recipient's public key.
In this case, the size of the message is ...
- 417
10
votes
2
answers
4k
views
How did someone discover N, order of G for SECP256k1?
Could someone please explain, in simple and easy terms, how the creators did (or should have) derived the N, order of G for ...
- 219
10
votes
1
answer
8k
views
EC curve selection
Say for instance, this webservice offers the following curves.
sect283k1 sect283r1 sect409k1 sect409r1 sect571k1 sect571r1 secp256k1 prime256v1 secp384r1 ...
- 103
10
votes
1
answer
2k
views
Curve25519 Key Validation
According to the original paper of Bernstein, there is no key validation needed when using Curve25519 for Diffie-Hellman Key Exchange. However, where does this property come from?
Is there any proof ...
- 317
10
votes
1
answer
350
views
Is the Representation Problem hard on elliptic curves?
The RP in ECC would be to find $a_1,\ldots,a_n$ (integers) given $P$ and $Q_1,\ldots,Q_n$ (points in the EC) such that $P = a_1 \cdot Q_1 + \ldots + a_n \cdot Q_n$.
Is it hard when DH-like ...
- 1,907
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 ...
- 979
10
votes
1
answer
3k
views
Performance of ECDSA, ECKCDSA and ECGDSA
It is proven that ECDSA algorithms are faster in key and signature generation compared to RSA. In addition, the signatures are much shorter.
However, I would like to know the performance difference ...
- 425
10
votes
1
answer
1k
views
When using Ristretto or Decaf with Ed25519 and Ed448, do scalars still need pruning/trimming/clamping?
Decaf is a point compression method that builds a prime-order group for (twisted) Edwards curves and Montgomery curves with cofactor $h = 4$ based on the Jacobi quartic [H2015]. The promise is to ...
- 233
10
votes
1
answer
1k
views
Is this a safe way to prove the knowledge of an ECDSA Signature?
I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it.
In short terms it consists in generating an ECDSA signature using the point $R$ as generator, ...
- 674
9
votes
1
answer
7k
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 ...
- 263
9
votes
2
answers
4k
views
Raw curve25519 public key points
I'm trying to understand curve25519, and ECC public points.
I'm playing with Minisign, to better understand the fundamentals of ECC.
Minisign uses curve25519 and outputs public keys as base64 ...
- 1,444
9
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 ...
- 283
9
votes
1
answer
4k
views
What is the projective space?
In Elliptic Curve Cryptography, using the projective space is often mentioned to accelerate the computations and to represent the point at infinity.
But What is the Projective space exactly ? How can ...
- 10k
9
votes
1
answer
5k
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,874
9
votes
3
answers
2k
views
How to decide if a point on a elliptic curve belongs to a group generated by a generator $g$?
In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $G$ on the elliptic curve.
Given a random point on the elliptic curve, is there a way to decide if the random ...
- 113
9
votes
3
answers
3k
views
Elliptic Curves of different forms
Looking at http://safecurves.cr.yp.to/ to find a safe curve, I find that most curves described here are of a different form from that generally used.
In Bouncy Castle, for example, ...
- 233
9
votes
2
answers
1k
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,430
9
votes
1
answer
7k
views
Subtracting a point in elliptic curve cryptography?
I've had lots of practice adding points for my crypto class. However I've run into a situation where I need to subtract two points for decryption:
...
- 423
9
votes
1
answer
454
views
Why are there so many different elliptic curves?
There are Chinese, French and NIST curves. There's a Million Dollar one. The BADA55 Research Team studied 1 million variants. Some are based on widely different formulae. Indeed there are entire ...
- 15.7k
9
votes
4
answers
6k
views
Is Elliptic Curve Diffie-Hellman (ECDH) still secure if I use the public key more than one time?
Elliptic Curve Diffie-Hellman (ECDH) with
Public parameters: Ep (a,b) and G = (x, y)
Private Keys: ...
9
votes
1
answer
3k
views
What is the difference between regular and "twisted" ECC curves?
When I do:
openssl ecparam -list_curves
I get, among other entries:
...
- 821
9
votes
2
answers
11k
views
How to measure ECC key size?
I have implemented a ECC key generation scheme successfully. Now I need to find ECC key sizes of each generating key pairs. I assumed that ECC key size is the size of the ECC private Key.
So I would ...
- 161
9
votes
1
answer
3k
views
Find Elliptic Curve Parameters, a and b, Given Two Points on the Curve
I am new to Elliptic Curve Cryptography and am working on a CTF challenge that uses Elliptic Curves. Currently, I am trying to find the generator, $G$, and am given the public and private keys, $P$ ...
- 193
9
votes
1
answer
21k
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 ...
- 417
9
votes
2
answers
10k
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,695
9
votes
2
answers
2k
views
How many valid X25519 private keys are there?
According to the Curve25519 website:
Computing secret keys. Inside your program, to generate a 32-byte Curve25519 secret key, start by generating 32 secret random bytes from a cryptographically safe ...
- 257
9
votes
1
answer
1k
views
Why are co-factors 4 and 8 so popular when co-factor is more than one?
For elliptic curve cryptography, I seem to keep coming across curves with either co-factors of 4 or 8 whenever it is a non-prime order group.
Is this a co-incidence? Have we studied ECC for curves ...
- 1,363