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
7 votes
1 answer
442 views

Sextic twist over BN elliptic curves

I am struggling to understand how to perform a sextic twist over a BN elliptic curve. This is what I understood so far: Let's consider a BN elliptic curve: $$ E: y^2=x^3+b $$ And let's consider a ...
Baham91's user avatar
  • 71
7 votes
1 answer
173 views

How important is hardware based crypto in Quantum-safe TLS in mobile devices?

Microsoft Research published an approach to Quantum-safe TLS here, namely RLWE-ECDSA-AES128-GCM-SHA256. One highlight is that when it's used with ECC, there is only a slight performance hit. ...
makerofthings7's user avatar
7 votes
1 answer
715 views

Encoding scalar values to points on Ed25519

I'm interested exploring key derivation and threshold signature protocol that require point arithmetic (addition) on the private scalar values and $S$ values of the signatures in ed25519. ...
zmanian's user avatar
  • 171
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
7 votes
0 answers
521 views

Which is the smallest safe elliptic curve (bit-length)?

At https://safecurves.cr.yp.to/ some elliptic curves are listed which passed certain security tests. The smallest bit-length of a safe curve listed there is 221 bits. At wiki page discrete logarithm ...
J. Doe's user avatar
  • 453
6 votes
3 answers
1k views

Is EC integrated encryption scheme used in practice?

I know ECDSA and ECDH are used a lot but what about the ECIES? Is it used or specified as an option in any protocol?
SFlow's user avatar
  • 465
6 votes
2 answers
251 views

How sensitive to change are elliptic curve formulae In layman's terms?

Take for example a curve from a recent question such as #25519:- $$y^2 = x^3 + 486662x^2 + x$$ It's considered "safe". What are are the implications of amending it very slightly to:- $$y^2 = x^3 + ...
Paul Uszak's user avatar
  • 15.5k
6 votes
2 answers
3k views

Why are there only positive value points on an elliptic curve?

I read about elliptic curve cryptography $E$ over $Z_p$ where $p$ is prime number and $G$ is a base point on the curve. I noticed the points resulting from multiplication e.g. $2G$,$3G$,.....,$(N-1)G$ ...
Mhsz's user avatar
  • 451
6 votes
2 answers
5k views

Finite fields and ECC

I understand modular arithmetic(or at least I think I do!) and I've tried to read and learn about how the Math in RSA works(and I think it went pretty well). I've been reading up on ECC and it looks ...
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
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
6 votes
2 answers
3k views

EC Public key encryption scheme where Alice does not know Bob's public key

I've found ECDH and ECIES, but those both require Alice to know Bob's public key and Bob to know Alice's public key in order to derive a shared secret. Now assume Bob knows Alice's public key $A$, but ...
user avatar
6 votes
1 answer
840 views

What's wrong with this curve (generation algorithm)?

In this tweet, Paulo Barreto proposes the following elliptic curve over $\mathbb{F}_{2^{255}-19}$: $$ E_\mathrm{PB} : y^2 = x^3 - 3x + 13318 $$ with $G_\mathrm{PB} = (-7, 114)$. Now I would like to ...
dusk's user avatar
  • 1,175
6 votes
2 answers
543 views

"Cropping" the resulting shared secret from ECDH

I'm deriving a shared secret using ECDH with Ed25519 keys. According to the specification (page 5), the shared secret then can be any valid Curve25519 public key, i.e. any valid 32 bytes. My ...
user avatar
6 votes
2 answers
2k views

Why are elliptic curves over binary fields used less than those over prime fields?

In practical applications, elliptic curves over $F_p$ seem to be more popular than those over $F_{2^n}$. Is it because operations over prime fields are faster than those over $F_{2^n}$ for the same ...
Bob's user avatar
  • 509
6 votes
3 answers
716 views

Supersingular Isogeny Key Exchange broken?

Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves. https://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf with the quote "...
Zaphod1001's user avatar
6 votes
1 answer
14k views

Understanding example of ECDSA P256

I am new to cryptography, I found the below Example on a nice website, but I am not able to understand the most of the terms used (H:Hash, K:Random number,E=?, Kinv=?,Rx=?=RY?,R=Private key?,D?,S? ...
Yash Vardhan's user avatar
6 votes
1 answer
3k views

Generating a random point on an elliptic curve over a finite field

I have coded an implementation of elliptic curves in order to apply some of the ECC algorithms. However, in most of them, Alice needs to choose a point P on a given curve. What is the general ...
srb's user avatar
  • 95
6 votes
5 answers
2k views

Elliptic curves in Edwards form (or Edwards curve) and addition formulas

In recent studies on elliptic curve cryptography, Edwards curves are remarkable examples on this field. Studies show that this kind of elliptic curves provide faster computation compared to ...
sefiks's user avatar
  • 229
6 votes
2 answers
503 views

How to get an optimal strategy in computing isogenies for SIDH/SIKE

How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec? If possible, can anyone give me an example? And why do we need to compute all leaf point? I though we just need ...
Hzt's user avatar
  • 107
6 votes
1 answer
3k views

inverse problem about scalar multiplication on elliptic curve

Let $E$ be an elliptic curve over a finite field $F_p$. Given $n$ be a positive integer and $Q$ be a point on $E$, assume that $Q=nP$, how can we find this $P$? We can assume that $n|p-1$. If $n$ is "...
math curve's user avatar
6 votes
3 answers
772 views

The utility of elliptic curve cryptography

Suppose that the only public key cryptography schemes that we knew were Diffie Hellman, RSA and ElGamal. How much would this set civilization back? Are there important applications of elliptic curve ...
Jonah Sinick's user avatar
6 votes
1 answer
1k views

How many qubits can break NIST P-521 ECC?

NIST P-521 has the longest key size for standardised ECC, which has 521 bits instead of 512. If a quantum computer is available, how many qubits can break P-521?
Flan1335's user avatar
  • 361
6 votes
1 answer
6k views

Generating a NIST P-256 private key

From the Curve25519 spec I learned that it possible to take a random 32 bytes and with a few operations make it on the curve: To generate a 32-byte Curve25519 secret key, start by generating 32 ...
O. Nasirov's user avatar
6 votes
1 answer
405 views

Can two elliptic curve point multiplications have a same resulted point?

Is it possible for $aG \equiv bG$, with $a, b$ are scalars and $G$ is a point on the curve?
Danbo3004'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
1 answer
4k views

What EC curve is used by Apple iOS platform?

I can't find information about EC curve used by Apple's iOS platform. The algorithm name that I could see in their docs is: ...
Oleg Gryb's user avatar
  • 366
6 votes
2 answers
3k views

Elliptic curve and "vanity" public keys

I want to find an algorithm to get a private/public key pair where one coordinate of the public key has some specific prefix (for example: 20 leading zeroes). In the secp256k1 case (the Bitcoin curve),...
arulbero's user avatar
6 votes
2 answers
461 views

Why is elliptic curve parameter $a=-3$ somehow special

Considering the equation of the elliptic curves over $GF(p)$ $y^3 = x^2+ax+b$ , why is there some magic in using $a=-3$ ? In some well known curves (e.g. P-256) only $b$ is specified, while $a$ ist ...
MichaelW's user avatar
  • 1,497
6 votes
1 answer
3k views

In elliptic curve cryptography, how is "A dot A" computed?

I was just reading Ars Technica's primer on ECC. Somewhere near the middle of the second page, the author introduces the "dot" operation that takes an elliptic curve and two other known points, giving ...
andyn's user avatar
  • 163
6 votes
1 answer
2k views

Simple explanation of sliding-window and wNAF methods of elliptic curve point multiplication

I'm trying to understand the implementation of elliptic curve point multiplication. I can easily understand the naive double-and-add algorithm, but I'm struggling to find a good explanation / example ...
simbro's user avatar
  • 263
6 votes
1 answer
11k views

curve25519 by openSSL

How can i generate ec curve25519 keys using openSSL? When I run openssl ecparam -name curve25519 -genkey -noout -out private.ec.key I have this message ...
Vito Lipari's user avatar
6 votes
1 answer
3k views

What are the fastest attacks on ECDLP?

Consider the ECDSA protocol, which is applied in different environments e.g. the Bitcoin system (for user addresses, and transaction signing). What are the greatest threats in terms of algorithms ...
indiscreteLog's user avatar
6 votes
1 answer
1k views

Security level difference: supersingular vs non-singular elliptic curve

In some evaluation of elliptic curve cryptography, it says that for same security level In supersingular curve over $F_p$ with group of prime order $q$, p=512, q=160 bits In non-singular curve , p=...
myat's user avatar
  • 343
6 votes
2 answers
286 views

Is there a theorem to determine the elliptic curve parameters based on the group order?

By Hasse's theorem we know that range of the group order of the elliptic curve. And similarly, there exist a theorem on the admissible order of elliptic curves. Suppose by the theorem on the ...
user110219's user avatar
6 votes
1 answer
261 views

How does DJB's nistp224 manage to fit compressed points into 224 bits?

DJB's nistp224 program purports to be an implementation of elliptic curve Diffie-Hellman relative to the standard NIST P-224 elliptic curve. To the best of my ...
zwol's user avatar
  • 785
6 votes
1 answer
884 views

How to determine if a point is just a point or a valid public key?

In ECC, specifically over finite fields, in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used because the Generator Point (...
JamDiveBuddy's user avatar
6 votes
1 answer
610 views

What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI

What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI (Crypt32.dll) Could someone provide details?
kelalaka's user avatar
  • 49k
6 votes
2 answers
819 views

Why do elliptic curves require fewer bits for the same security level?

I'm studying the basics of cryptography and I didn't understand why elliptic curves use fewer bits. For example, finite-field Diffie-Hellman needs at least 1024 bit and it's a DLP, but elliptic ...
Ofey's user avatar
  • 81
6 votes
1 answer
291 views

Why can't you divide by 0 in an Edwards Curve?

The equation of an Edwards curve is $x^2 + y^2 = 1 + d x^2 y^2 \,$ The addition formula is $(x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - ...
Lomanter's user avatar
6 votes
1 answer
770 views

Advantages of RSA / EC against QC attacks

We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other? As an ...
Maarten Bodewes's user avatar
  • 93.2k
6 votes
1 answer
3k views

Non adjacent form of an integer is unique

I have tried to look up the proof for NAF (Non-adjacent form) being unique for every integer, but as far as I have seen, textbooks only mention it as a property of NAF, but no proof is given. Also I ...
Vi Jay's user avatar
  • 63
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
1 answer
626 views

Why is a simple hash into $G_2$ for (certain) pairing based crypto not possible?

In the paper Pairings for Cryptographers we read about what the authors call a type 2 pairing in which we have a "pairing friendly curve $E$ over $\mathbb{F}_q$ with embedding degree $k>1$ and ...
mikeazo's user avatar
  • 38.7k
6 votes
1 answer
3k 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 ...
Richard's user avatar
  • 63
6 votes
1 answer
208 views

Does any $x < p$ satisfy the curve equation of X25519?

I've been reading about the famous X25519, a montgomery curve from wikipedia and in that article they say that we do not have to check for point validity. Is it because that any $x < p$ satisfy ...
Aravind A's user avatar
  • 1,030
6 votes
1 answer
590 views

Can Pohlig-Hellman encryption be done over elliptic curves?

Following a bunch of questions on the topic of Pohlig-Hellman encryption. I was wondering if this could be trivially adapted to be done over elliptic curves just like we create EC-DH instead of DH. ...
Meir Maor's user avatar
  • 11.8k
6 votes
1 answer
12k views

Public-key format for ECDSA as in FIPS 186-4?

What is the public-key format for ECDSA as in FIPS 186-4, and where is it formally defined? In particular, are there variants beyond Cartesian coordinates? Is that a pair of bitstrings, or a ...
fgrieu's user avatar
  • 142k
6 votes
1 answer
807 views

How to properly add ECDSA private keys?

I'm currently working on an application that requires me to add two ECDSA private keys in order to make a new private key. The result has to have the property, that its corresponding public key is the ...
ThePiachu's user avatar
  • 1,679
6 votes
2 answers
552 views

Large prime numbers in ECC and discrete logarithm

In elliptic curve cryptography using Diffie-Hellman protocol, we need to use large prime numbers. So my question is what makes discrete logarithm hard to solve when we use large prime numbers. I guess ...
jean-michel-crapaud's user avatar

1
4 5
6
7 8
44