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.
398
questions
4
votes
3
answers
4k
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 ...
- 184
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 -- ...
- 36.2k
26
votes
1
answer
24k
views
ElGamal with elliptic curves
I've searched some information on ECC, but so far I have only found Diffie-Hellman key-exchange implementations using ECC, but I don't want to exchange keys, I want to encrypt & decrypt data like ...
- 363
10
votes
1
answer
1k
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 ...
- 297
9
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 ...
- 207
19
votes
1
answer
4k
views
What is the relationship between p (prime), n (order) and h (cofactor) of an elliptic curve?
I am reading up on ECC and having trouble understanding how these are related.
In a finite field, all point operations are taken modulo $p$.
$n$ is the order of the generator $G$ — which apparently ...
- 465
27
votes
2
answers
8k
views
Using same keypair for Diffie-Hellman and signing
Are there any security risks using a single key-pair for both key-exchange and signing?
I'm mainly interested in using Curve25519 for key-exchange and Ed25519 for signing. But similar combinations, ...
- 24.8k
18
votes
1
answer
4k
views
After ECDH with Curve25519, is it pointless to use anything stronger than AES-128?
Is the following reasoning correct:
After ECDH with Curve25519, the resulting shared secret will be an EC public key with a bit strength of 128 bits.
This public key would then be hashed (let's say ...
- 4,712
4
votes
1
answer
2k
views
How do I multiply two points on an elliptic curve?
Tell me if there is a way to multiply two points on an elliptic curve?
For example, as in secp256k1
...
22
votes
2
answers
7k
views
Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?
The NIST elliptic curves P-192, P-224, P-256, P-384, and P-521, prescribed in FIPS 186-4 appendix D.1.2, are generated according to a well defined process, but using an arbitrary random-looking seed ...
- 138k
7
votes
2
answers
3k
views
How to create an EC point from a plaintext message for encryption
It seems that ElGamal encryption is also possible for Elliptic Curve cryptography. However, that requires the user to convert the message to a point on the curve. What strategies are there to derive a ...
- 91.9k
178
votes
4
answers
127k
views
Why is elliptic curve cryptography not widely used, compared to RSA?
I recently ran across elliptic curve crypto-systems:
An Introduction to the Theory of Elliptic Curves (Brown University)
Elliptic Curve Cryptography (Wikipedia)
Performance analysis of identity ...
- 1,995
61
votes
3
answers
28k
views
Why Curve25519 for encryption but Ed25519 for signatures?
NaCl and libsodium libraries use Curve25519 for authenticated encryption (actually for sharing a key which is used for encryption) and Ed25519 for signatures. What is the purpose of using different ...
- 711
30
votes
2
answers
13k
views
How to determine the order of an elliptic curve group from its parameters?
Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...
- 665
23
votes
4
answers
6k
views
EC Schnorr signature: multiple standard?
I'm working on some EC-Schnorr signature code.
Reading various papers on that, it seems EC-Schnorr is not standardized as
well as ECDSA.
For example, I found two main differences in two main actors ...
- 413
13
votes
1
answer
6k
views
Curve25519 over Ed25519 for key exchange? Why?
I've been reading up on the Signal Protocol (in this PDF) and it seems to be using Curve25519 for ECDH and EdDSA (with Ed25519) for signatures.
My question is why not use only Ed25519?
This ...
- 324
12
votes
2
answers
8k
views
Can elliptic curve cryptography encrypt with public key and decrypt with private key like RSA?
I know that RSA can be used for both, encryption and signature.
What about EC? I know about ECDSA/EdDSA, but to my knowledge it can only be used to sign.
I also know about ECDH, but it is a key ...
- 121
3
votes
2
answers
2k
views
Can you tell me why doing scalar multiplication of a point on a Elliptic curve over a finite field gets to a point at infinity?
I am reading Programming Bitcoin. The author said:
Another property of scalar multiplication is that at a certain multiple, we get to the point at infinity (remember, the point at infinity is the ...
- 139
52
votes
6
answers
18k
views
Who uses Dual_EC_DRBG?
Recent news articles have suggested that the NSA may be involved in trying to influence the cryptography in public standards or commercially deployed software, to enable the NSA to decrypt the ...
- 36.2k
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.
- 624
31
votes
2
answers
4k
views
When using Curve25519, why does the private key always have a fixed bit at 2^254?
When using Curve25519, the private key always seems to have a fixed bit set at position $2^{254}$.
Why is that? Is there any good reason to use a fixed positioned most-significant-bit in the private ...
- 694
14
votes
1
answer
1k
views
What the X stands for in the front of Elliptic curve names like X25519
I have seen Curve25519 and X25519, Curve448 and X448. I've seen a small note in this answer
(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic ...
- 47.6k
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
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,712
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, ...
- 223
26
votes
2
answers
10k
views
How does the MOV attack work?
What exactly is the MOV attack, how does it actually work, and what is it used for?
It's explained briefly here and I'd like to know what it is more / what is it fully used for.
- 699
20
votes
1
answer
4k
views
Using a single Ed25519 key for encryption and signature
The libsodium documentation contains a function crypto_sign_ed25519_pk_to_curve25519 that converts an Ed25519 key into a Curve25519 one, so it can be used for both ...
user2552
18
votes
1
answer
17k
views
How does encryption work in elliptic curve cryptography?
So I think I understand a good amount of the theory behind elliptic curve cryptography, however I am slightly unclear on how exactly a message in encrypted and then how is it decrypted.
So my ...
- 461
17
votes
4
answers
31k
views
How does one calculate the scalar multiplication on elliptic curves?
I found this example online:
In the elliptic curve group defined by
$$y^2 = x^3 + 9x + 17 \quad \text{over } \mathbb{F}_{23},$$
what is the discrete logarithm $k$ of $Q = (4,5)$ to the base $...
14
votes
2
answers
6k
views
Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different?
We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=\frac{H(m)+xr}{k}$
Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, ...
- 2,266
5
votes
1
answer
2k
views
ECDH security when no KDF is used
Let's suppose our device performs ECDH with a fixed, unknown, private key $\text{prv}$.
It accepts as input any point $Q$ lying in the proper subgroup of the proper elliptic curve, then computes: $P =...
- 6,904
35
votes
4
answers
12k
views
Can ECDSA signatures be safely made "deterministic"?
Using the terminology of the ECDSA Wikipedia page, ECDSA (and DSA) signatures require a random k value for each signature which ensures that the signature is different each time even if the message ...
- 727
34
votes
4
answers
5k
views
What is so special about elliptic curves?
There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so ...
- 573
33
votes
3
answers
5k
views
Why would anyone use an elliptic curve with a cofactor > 1?
In cryptography, an elliptic curve is a group based on a finite field $GF(p^k)$; this group has $n$ elements on it, and we work on a prime-sized subgroup of size $q$. We denote the value $h = n/q$ as ...
- 145k
30
votes
1
answer
19k
views
ECDSA Compressed public key point back to uncompressed public key point
From the ECDH demo here, if I generate a private key for Alice I can get _
P = 1175846487558108474218546536054752289210804601041
Which gives the following public ...
- 493
22
votes
1
answer
3k
views
Mapping points between elliptic curves and the integers
My primary question is:
Is there an easy way to create a bijective mapping from points on an elliptic curve E (over a finite field) to the integers (desirably to $\mathbb{Z}^*_q$ where $q$ is the ...
- 8,587
19
votes
1
answer
2k
views
Why are elliptic curve variants of RSA "chiefly of academic interest"?
Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
- 38.5k
12
votes
2
answers
5k
views
Can curve25519 keys be used with ed25519 keys?
Can curve25519 keys be used with ed25519?
I'd prefer to use ed25519, but there isn't a fast java version. For my application, I'd like to use curve25519 until I can get a faster ed25519 for java.
...
user7024
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
5
votes
3
answers
3k
views
Graphically representing points on Elliptic Curve over finite field
I have taken elliptic curve $E\colon y^2=x^3-4x+20$, defined over $\mathbb{F}_{29}$.
The number of points on the curve, $\left|E(\mathbb{F}_{29})\right|=37$.
I took base point $P=(1,5)$, and got ...
- 205
3
votes
1
answer
646
views
Key equivalence across different elliptic curves
Is it possible to prove key-equivalence across elliptic curves of different order? Specifically:
Suppose I have a key $x$ valid for both curves listed below
On curve $g$ (for example, Curve25519) it ...
- 969
2
votes
2
answers
2k
views
Get the parameters of an elliptic curve's equation
I have a binary signed with ECDSA384 and I need to verify it using a particular cryptography library.
The first thing that needs to be done is to initialize the EC ...
- 123
38
votes
1
answer
16k
views
ECDSA, EdDSA and ed25519 relationship / compatibility
I'm trying to understand the relationship between those three signature schemes (ECDSA, EdDSA, and ed25519) and mainly to what degree they are mutually compatible in the sense of key-pair derivation, ...
- 483
22
votes
7
answers
10k
views
Current mathematics theory used in cryptography/coding theory
What are the mainstream techniques borrowed from algebraic geometry (or some other branch of mathematics) which are currently used in cryptography/coding theory? I've only heard about a small subset ...
- 441
18
votes
2
answers
4k
views
Schnorr signatures: multisignature support
Schnorr signature is mentioned as a promising upgrade to bitcoin to improve scalability. It support multisignature, several signatures can be aggregated into a single, new signature. But I fail to ...
- 367
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
17
votes
1
answer
3k
views
Edwards / Montgomery ECC with Weierstrass Implementation?
So let's assume I want to perform Ed448 or Ed25519 digital signatures or want to perform a DH key-exchange. Assume further that those curves (Curve448 or Curve25519) are required.
But the problem is, ...
- 45.7k
16
votes
3
answers
10k
views
Are all possible EC private keys valid?
I usually generate a key pair using OpenSSL or Bouncy Castle.
I'm using curve secp256k1.
The 256bit private keys look fairly random.
Do all values of "private ...
- 639
15
votes
1
answer
675
views
Logjam on Elliptic Curves?
I think we're all aware of the Logjam attack.
From now on we know that re-using primes for DH is a bad idea.
But we also say that elliptic curves are safe from the attack (relying on the NFS), ...
- 45.7k
14
votes
1
answer
3k
views
Trying to better understand the failure of the Index Calculus for ECDLP
So I'm going to give you guys my understanding and then if you would be so kind as to tell me where I'm off the mark (hopefully I'm not completely wrong).
So basically the index calculus for the ...
- 303