Skip to main content

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
1 vote
2 answers
3k views

What is the difference between "Elliptic Curve Function" and "Hash Functions" like SHA256?

I am reading about bitcoin and I am a little confused about "elliptic curve function" and "SHA256". Do they have the same properties? Can both be used to generate private and ...
Narayan Choudhary's user avatar
1 vote
1 answer
752 views

elliptic curve multiplication with negative factor

I'm learning the multiplication operation on EC. From most material I can found, the multiplication $nP$ is just: $$nP=P+P+\cdots +P+P$$ For negative factor, i.e. $(-n)P$, by above definition and the ...
qweruiop's user avatar
  • 326
0 votes
2 answers
7k views

Problem on Elliptic Curve Point Doubling

Given an elliptical curve e.g. from “Understanding Cryptography” by Parr & Pelzl §9.2 Example 9.5: $y^2 = x^3 + 2x + 2~~~~ mod~17$ And given a primitive $P = (5, 1)$, the book indicates: We ...
Brian M. Hunt's user avatar
32 votes
2 answers
6k views

What does "birational equivalence" mean in a cryptographic context?

In a recent question on using the same curve for signing and ECDH it was noted for the Ed25519 curve and Curve25519: Nitpick: the curves are birationally equivalent, not isomorphic. Now this term ...
SEJPM's user avatar
  • 46.1k
28 votes
3 answers
39k views

How can I use SSL/TLS with Perfect Forward Secrecy?

I'm new to the field of cryptography, but I want to make the web a better web by setting up the sites that I host with Perfect Forward Secrecy. I have a list of questions regarding the setup of ...
Clay Freeman's user avatar
24 votes
3 answers
16k views

How effective is quantum computing against elliptic curve cryptography?

I've been reading the Wikipedia page on Elliptic-Curve Cryptography and I came across the following. in August 2015, the NSA announced that it plans to replace Suite B with a new cipher suite due ...
Fathima Abdur Rahman's user avatar
17 votes
1 answer
4k views

Difference between “ECDH with cofactor key” and “ECDH without cofactor key”?

I need to use “ECDH with a cofactor key” for generating symmetric key. I have a fair idea on how ECDH works, but I don’t understand the cofactor part. What is the difference between ”ECDH with a co-...
Kiran's user avatar
  • 301
15 votes
1 answer
2k views

How to generate own secure elliptic curves?

I know that the algorithm used to generate the Brainpool curves and the NIST curves is published. The algorithm should be this one (RFC5639 Appendix A). From what it looks like it's rather slow to ...
SEJPM's user avatar
  • 46.1k
15 votes
2 answers
26k views

ECDSA Signature R|S to ASN1 DER Encoding question

I am trying to test my understanding on ECDSA Signature r|s to ASN.1 DER Encoding for NIST P-256. I have r|s and when I convert ...
vison's user avatar
  • 163
13 votes
2 answers
7k views

Does secp256k1 have any known weaknesses?

I am wondering whether there are any properties of the curve which would technically make it easier to attack than any other curves of 256 bits in size. I have heard that being a Koblitz curve, it ...
Matt's user avatar
  • 245
13 votes
1 answer
8k views

What is an elliptic curve cofactor?

As the title says, I have some doubts about the term "cofactor" used to describe elliptic curves. AFAIK, it's a factor of the curve order, but why is it explicitly specified in some parameter lists ...
Mark's user avatar
  • 835
12 votes
2 answers
4k views

Different ways/algorithms for implementing AES

I have seen a couple software implementations of the Advanced Encryption Standard. They are pretty much straight forward, i.e. they are implemented exactly the same way as the AES is described. This ...
jordi88's user avatar
  • 121
12 votes
1 answer
2k views

How many bits of entropy does an elliptic curve key of length n provide?

A FAQ for an open source project makes the claim: Indeed, an elliptic curve key of length n provides $n/2$ bits of security. I have two questions: What is the practical difference between "bits ...
Rich Apodaca's user avatar
12 votes
4 answers
3k views

Fast hashing into elliptic curve

Is there a fast algorithm for mapping $n$-bit numbers $s$ (for fixed $n$) into a cyclic subgroup of an elliptic curve (over a finite field) in which the Discrete Logarithm Problem is hard? By fast, I ...
jbms's user avatar
  • 360
11 votes
1 answer
2k 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 ...
Perseids's user avatar
  • 562
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 ...
sce's user avatar
  • 267
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 ...
irakliy's user avatar
  • 969
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 ...
sribin's user avatar
  • 248
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 ...
budderick's user avatar
  • 425
9 votes
1 answer
6k views

How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
Venkatesh's user avatar
  • 482
9 votes
1 answer
409 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 ...
forest's user avatar
  • 15.3k
9 votes
1 answer
1k views

Families of public/private keys in elliptic curve cryptography

I'm looking for a related key scheme for elliptic curve cryptography. The basic idea would be that there would be a master public key and a master private key. From the master public key, you could ...
David Schwartz's user avatar
9 votes
1 answer
2k views

Is it possible to decrypt an ECDSA private key if the same nonce is used across different private keys?

If the same nonce is used across different messages under the same private key, the private key can be easily revealed. However, let's consider another scenario. Two private keys, x1 and x2, are ...
Anonymous's user avatar
  • 153
9 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 ...
Venkatesh's user avatar
  • 482
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: ...
ConditionRacer's user avatar
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. ...
BlackAdder's user avatar
8 votes
1 answer
3k 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 ...
user12230's user avatar
  • 111
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 ...
Andy's user avatar
  • 181
8 votes
2 answers
9k 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 ...
Iñaki Viggers's user avatar
7 votes
1 answer
689 views

Proving that the least significant bit of an elliptic curve discrete logarithm is $0$

Suppose I have a secret value $a$ which maps to a public point on an elliptic curve $A = a \cdot G$, where $G$ is a generator of the elliptic curve of prime order $q$. Can I prove to someone that the ...
irakliy's user avatar
  • 969
7 votes
2 answers
902 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 + ...
HOANG GIANG's user avatar
7 votes
2 answers
5k views

Invalid curve attack: finding low order points

Background Here's a description of page 182 of "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone. Here's a quote from that page: The main observation in invalid-...
Max Mikhaylov's user avatar
7 votes
1 answer
2k views

Elliptic curve cryptography related key attacks [closed]

This question is an extension of Families of public/private keys in elliptic curve cryptography As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where ...
user2006's user avatar
6 votes
1 answer
450 views

What are the computational benefits of primes close to the power of 2?

Recently I was reading some article about the Bernstein's Curve25519. This is a particular Montgomery curve over $\mathbb{F}_q$ where $q = {2^{255}-19}$. What I missed or was unable to understand is ...
NumberFour's user avatar
6 votes
2 answers
3k views

Why is Diffie Hellman used alongside public keys?

I just read this post here: Why do we need asymmetric algorithms for key exchange? that asserts that in public key cryptography when asymmetric keys are used to secure communications, for parties to ...
Code Wiget's user avatar
6 votes
1 answer
3k views

Can a raw ECDH shared secret be used directly for encryption?

If two parties calculate an ECDH shared secret can they (with no security weakness) use this raw value directly as an encryption key, assuming the underlying key and ECDH sizes match? Also the ...
big_fish_small_pond's user avatar
6 votes
2 answers
10k views

How to solve this ECDLP?

The Problem is as follows: $E: y^2=x^3+17230x+22699 \pmod{23981} $ $p=23981$ is prime number point $G$ $G$'s order $109$ : prime number Alice creates a public key by selecting a private key $d$ ($d&...
user avatar
5 votes
1 answer
2k views

How is the order of a point calculated for elliptic curves over GF(p)

My question is about elliptic curves over $GF(p)$: How is the order of a generating element $G$ (which is to my knowledge also the order of the cyclic subgroup $G^n$) calculated? Taking P-256 as an ...
MichaelW's user avatar
  • 1,497
5 votes
2 answers
909 views

Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key?

Since ECC over P-256 provides only 128 bits of security, I'd like to cut corners and generate a private key using HKDF to generate 32 bytes of key material from an input secret that's only 16 bytes ...
Reid Rankin's user avatar
5 votes
1 answer
366 views

Why such a complicated way of cofactor clearing?

I thought I understood cofactor clearing before I read this write-up which generally seems quite popular (lot of other sites link to it) - Cofactor Explained: Clearing Elliptic Curves' dirty little ...
user93353's user avatar
  • 2,245
5 votes
1 answer
2k views

What differences between Menezes–Vanstone ECC and ElGamal ECC?

After researching ECC encryption, I found that we can use ElGamal cryptosystem with elliptic curve and can we use Menezes-Vanstone cryptosystem with elliptic curve. What is the essential difference ...
Mhsz's user avatar
  • 451
5 votes
1 answer
1k views

Looking at just EC Public Key parameters, how can you tell if it is invalid?

I am trying to handle when a parsers goes off the rails and reads an EC public keys wrong (just the X and Y components, I know the curve prior). Right now I check for the following (false means ...
Liam Kelly's user avatar
5 votes
1 answer
940 views

ElGamal with elliptic curves II

There is an encryption scheme using elliptic curves given by @tylo explained here: @tylo's answer on ElGamal with elliptic curves and here: ElGamal with elliptic curves I. The encryption idea is to ...
user45323's user avatar
  • 145
5 votes
2 answers
748 views

Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this; In fact, you can still play the billiards game on this curve and dot ...
kelalaka's user avatar
  • 49k
5 votes
3 answers
2k views

Should Diffie-Hellman on Curve25519 be validated?

I have some issues understanding the original protocol proposed by Daniel J. Bernstein for Diffie-Hellman on Curve25519. On his web page he states to not validate remote public key, but at the same ...
user3368561's user avatar
4 votes
2 answers
1k views

ECDSA: Why is SigningKey shorter than VerifyingKey

Total Crypto Noob here. I was wondering why in ECDSA the Signing Key is so much (half of) shorter than the Verifying key? Lets look at some python code: ...
SimonSchuler's user avatar
4 votes
1 answer
1k views

Is either brainpoolP320r1 or brainpoolP320t1 a SafeCurve?

Not all elliptic curves are safe to use for cryptography, especially from an ECC safety perspective. The site http://safecurves.cr.yp.to/index.html shows that two tested Brainpool curves, ...
user avatar
4 votes
1 answer
1k views

Is it safe to use same private key in two or more EC signature algorithms?

Given two (or more) algorithms: ed25519 private key is random blob of 32 bytes public key is encoded point on Edwards 25519 curve. ECDSA with secp256k1 private key is random blob of 32 bytes ...
warchantua's user avatar
4 votes
1 answer
2k views

Using Montgomery ladder to calculate the coordinates

In one of my assignments I need to solve the problem below: For a Montgomery curve $3y^2 = x^3+x^2+x$ over ${\mathbb{F}}_{11}$ and point $P = (9,8)$, compute the $x$ coordinate of $3P$ using the ...
TechJ's user avatar
  • 217
4 votes
2 answers
731 views

Is it ever unsafe to compress an EC point?

I am working with a library that outputs EC points in uncompressed form. To save space, I'm considering modifying said library to use compressed EC points. Assuming that I keep track of the sign bit ...
makerofthings7's user avatar

1 2
3
4 5
9