Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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.

Filter by
Sorted by
Tagged with
5 votes
3 answers
5k 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 ...
PouJa's user avatar
  • 314
162 votes
4 answers
54k 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 -- ...
D.W.'s user avatar
  • 36.4k
28 votes
1 answer
25k 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 ...
CriticalError's user avatar
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 ...
Marc's user avatar
  • 317
10 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 ...
Kevin Burke's user avatar
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 ...
SFlow's user avatar
  • 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, ...
CodesInChaos's user avatar
  • 24.9k
18 votes
1 answer
5k 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 ...
knaccc's user avatar
  • 4,732
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 ...
Derick Swodnick's user avatar
43 votes
3 answers
27k 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.
Jan Moritz's user avatar
23 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 ...
fgrieu's user avatar
  • 142k
7 votes
2 answers
4k 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 ...
Maarten Bodewes's user avatar
  • 92.9k
181 votes
4 answers
129k 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 ...
Vineet Menon's user avatar
  • 2,025
64 votes
3 answers
29k 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 ...
user avatar
30 votes
2 answers
14k 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 ...
user110219's user avatar
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 ...
cslashm's user avatar
  • 413
14 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 ...
OughtToPrevail's user avatar
13 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 ...
Eric's user avatar
  • 131
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 ...
inherithandle's user avatar
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 ...
D.W.'s user avatar
  • 36.4k
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 ...
Trina's user avatar
  • 694
28 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.
Ben's user avatar
  • 719
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 ...
kelalaka's user avatar
  • 48.7k
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?
knaccc's user avatar
  • 4,732
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 ...
Rick's user avatar
  • 103
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, ...
Niels Abildgaard's user avatar
35 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 ...
stackuser's user avatar
  • 583
20 votes
1 answer
5k 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 ...
user avatar
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 ...
Ali's user avatar
  • 481
17 votes
4 answers
33k 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 $...
Keith Lau Si Keit's user avatar
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$, ...
Ethan Heilman's user avatar
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 =...
Ruggero's user avatar
  • 7,104
36 votes
4 answers
13k 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 ...
ByteCoin's user avatar
  • 737
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 ...
poncho's user avatar
  • 148k
32 votes
2 answers
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 ...
Ian Purton's user avatar
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 ...
PulpSpy's user avatar
  • 8,627
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 ...
mikeazo's user avatar
  • 38.6k
12 votes
2 answers
6k 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. ...
user avatar
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 ...
Chris's user avatar
  • 989
5 votes
3 answers
4k 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 ...
Ravi's user avatar
  • 205
3 votes
1 answer
667 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 ...
irakliy's user avatar
  • 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 ...
Dan's user avatar
  • 123
39 votes
1 answer
17k 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, ...
Rafael Korbas's user avatar
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 ...
Vicfred's user avatar
  • 441
18 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, ...
SEJPM's user avatar
  • 46.1k
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 ...
Consy's user avatar
  • 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 ...
fgrieu's user avatar
  • 142k
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 ...
Thomas Von Panom's user avatar
15 votes
1 answer
685 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), ...
SEJPM's user avatar
  • 46.1k
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 ...
Set's user avatar
  • 303

1
2 3 4 5
9