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
21
votes
1answer
20k 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 ...
157
votes
4answers
49k 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 -- ...
4
votes
3answers
2k 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 ...
16
votes
1answer
3k 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 ...
18
votes
1answer
3k 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 ...
25
votes
2answers
6k 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, ...
8
votes
2answers
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 ...
8
votes
1answer
411 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 ...
20
votes
2answers
5k 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 ...
170
votes
4answers
114k 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 ...
50
votes
3answers
23k 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 ...
51
votes
6answers
17k 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 ...
9
votes
1answer
4k 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 ...
9
votes
3answers
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, ...
37
votes
2answers
19k 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.
21
votes
4answers
4k 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 ...
23
votes
2answers
10k 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 ...
16
votes
1answer
15k 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 ...
14
votes
2answers
3k 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$, ...
8
votes
2answers
3k 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?
29
votes
3answers
3k 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 ...
28
votes
1answer
16k 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 ...
26
votes
2answers
3k 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 ...
21
votes
2answers
7k 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.
15
votes
4answers
27k 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 $...
20
votes
1answer
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 ...
10
votes
1answer
3k 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 ...
19
votes
1answer
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 ...
4
votes
1answer
1k 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 =...
10
votes
2answers
6k 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 ...
9
votes
1answer
2k 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 ...
4
votes
2answers
1k 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 ...
3
votes
3answers
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 ...
3
votes
1answer
350 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 ...
22
votes
7answers
9k 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 ...
15
votes
2answers
3k 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 ...
9
votes
1answer
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 ...
17
votes
1answer
2k 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, ...
11
votes
3answers
23k views

Using ECDSA keys for encryption

I know that ECDSA is used for signature only, but I wonder if I can use the public/private Elliptic Curve keys for encryption too. I have ECDSA SSH public keys and I wonder if I can use them to ...
4
votes
1answer
3k views

Elliptic curve and embedding degree

I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?) ...
14
votes
1answer
583 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), ...
13
votes
1answer
2k 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 ...
1
vote
4answers
3k views

Optimized modular multiplicative inverse for Bitcoin (secp256k1)

I have written an application to brute-force attack Bitcoin addresses for OpenCL. It implements a simple exhaustive search starting from public key G (private key 1) and point increment (addition of G)...
28
votes
3answers
4k 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 ...
8
votes
1answer
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 ...
7
votes
2answers
856 views

Besides key and ciphertext sizes what are other advantages of elliptic curve versions of various protocols?

There are elliptic curve variants of Diffie-Hellman, ElGamal, DSA and possibly other protocols/algorithms. I know that these elliptic curve variants have smaller key and ciphertext sizes which will ...
5
votes
2answers
3k views

Why Smart's attack doesn't work on this ECDLP?

The Problem is as follows: ...
4
votes
1answer
2k views

Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack

The curve $E(\mathbb{F}_{47}):y^2=x^3+x+38$ has order $61$ and $61|47^3-1$ so the embedding degree of $E$ is $3$ and therefore the MOV attack, presumably using some sort of distortion map and a ...
4
votes
1answer
5k views

ECC vs RSA: how to compare key sizes?

I know and I have understood the details of RSA, elliptic curve cryptography, (EC)DH and (EC)DSA. I keep reading everywhere that (if we don't consider non-deterministic computers) "ECC can achieve ...
11
votes
1answer
2k 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 ...

1
2 3 4 5
7