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
votes
2answers
105 views

How to find at least one private key from a large list of compressed public keys secp256k1

Not long ago I saw a discussion on the Bitcoin Talk forum: https://bitcointalk.org/index.php?topic=5060735.msg50736695#msg50736695 Please give advice and working methods? Is it possible to find at ...
35
votes
3answers
13k 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 ...
38
votes
2answers
22k views

ECDSA vs ECIES vs ECDH

Recently I started studying Elliptic Curve Cryptography and I just loved it. I want to transfer some big data (like 3KB), What is the best method, ECDSA, ECIES, or ECDH (and why)? I am confused, how ...
20
votes
1answer
8k views

How does ECDH arrive on a shared secret?

I read a brilliant, three part article on Elliptic Curve cryptography (one, two, three). It was able to explain Elliptic Curves to me in a way that didn't require a math degree to understand. The ...
24
votes
1answer
17k views

How strong is the ECDSA algorithm?

Some cryptographic algorithms are as strong as the size of their key is, while other have some weaknesses that limit their strength (such as SHA-1). How strong is the ECDSA algorithm, and does that ...
12
votes
3answers
3k views

How does ECC go from decimals to integers?

I realise that elliptical curves are tricky, but there's one aspect that no one seems to explain. I've looked, and it's towards the beginning. This is the traverse over a red curve:- This is only ...
12
votes
2answers
2k views

How can I implement the elliptic curve MOV attack myself?

I understand and have implemented elliptic curve signatures in Python without the use of libraries like Sage, and would like to implement the MOV attack against certain weak types of elliptic curves. ...
6
votes
2answers
720 views

Is it possible to derive a public key from another public key without knowing a private key (Ed25519)?

I have a following use case: User has his master public (sk) - private (pk) key pair (Ed25519). In DB we store a public key. Is ...
17
votes
1answer
9k views

How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

So in the news this week, IBM have created a universal quantum computer with 5 fully functional qubits. Logic and Moore's law dictates they will be able to scale this up to a lot more qubits within a ...
12
votes
2answers
3k views

Why do public keys need to be validated?

For some curves it's necessary to validate the public-key of the other side before running an elliptic-curve Diffie-Hellman key-exchange. Apparently if you don't validate the public key, small ...
22
votes
1answer
7k views

Why do the elliptic curves recommended by NIST use 521 bits rather than 512?

Wikipedia says in reference to the elliptic curves officially recommended by NIST in FIPS 186-3: Five prime fields for certain primes p of sizes 192, 224, 256, 384, and 521 bits. For each of the ...
5
votes
3answers
902 views

How can there be insecure elliptic curves if the discrete logarithm problem is hard?

The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure ...
5
votes
1answer
420 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 ...
17
votes
2answers
3k views

Does the elliptic curve (EC) cryptosystem outperform RSA and DL cryptosystems?

Throughout the literature, it is stated that EC cryptosystems outperform RSA and Discrete logarithm cryptosystems, but I cannot understand how ECC would be more efficient than RSA and DL in terms of ...
14
votes
2answers
3k views

Can one reduce the size of ECDSA-like signatures?

Using $n$-bit ECDSA, a signature has a size of $2·n$. It is possible to recover the public key from this signature, which shows that there is a publicly visible redundancy in the signature. Is ...
12
votes
3answers
2k 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 ...
10
votes
3answers
17k 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 ...
9
votes
1answer
979 views

HD (Hierarchical Deterministic) Keys using Safe Curves?

Bitcoin's HD (Hierarchical Deterministic) Keys as described in BIP32 allow for a master key to be created (a private key and a chain code) such that a tree of both public and private keys can be ...
7
votes
2answers
15k views

With OpenSSL and ECDHE, how to show the actual curve being used?

Using openssl s_client -host myserver.net -port 443 I can see the cipher negotiated is indeed using ECDHE for session key ...
2
votes
1answer
270 views

Curves intended for both signing and key agreement

I need some guidance on elliptic curves that support signing and key agreement. I am trying to develop a protocol for sending encrypted, deniably authenticated messages. To do this I will sign the ...
17
votes
1answer
1k views

Compressing EC private keys

For reasonable security, EC private keys are typically 256-bits. Shorter EC private keys are not sufficiently secure. However, shorter symmetric keys (128-bits, for example) are comparably secure. I ...
14
votes
2answers
2k views

How do I get the equivalent strength of an ECC key?

I know how to calculate the comparable symmetric strength of an RSA modulus: calculate the running time for a field sieve. This is how NIST gives approximate symmetric sizes for asymmetric algos in ...
9
votes
1answer
4k views

ECDSA vs RSA: Performance on Android platform and surprising results

For our privacy-preserving protocol, an encrypted channel is established. In order to protect our system from man-in-the-middle attacks, signature-based approach is used. After we've implemented it ...
7
votes
1answer
1k views

Understanding Twist Security with respect to short Weierstrass curves

I'm trying to understand the "Invalid-curve attacks against ladders" section of SafeCurves Twist Security page and I have difficulties to apply it to short Weierstrass curves. That section claims ...
6
votes
1answer
2k views

Converting Ed25519 public key to a Curve25519 public key

I understand that: $$x_{montgomery} = \frac{1 + y_{edwards}}{1 - y_{edwards}}$$ Using the libsodium ed25519 implementation, I have tried to write the following: ...
5
votes
1answer
2k views

Do Weak Elliptic Curves Exist?

I'm running into very contradictory opinions when try to understand if weak elliptic curves exist. I'm not interested in the case when a curve's weakness is attributed to properties of an EC's prime, ...
4
votes
1answer
2k views

Elliptic Curve Encryption Ciphertext Size

I'd like to know how much bigger is the ciphertext when encrypting a message using ECC encrytpion? ECIES (or ElGamal)
4
votes
1answer
635 views

Elliptic curve parameter generation

I am curious of the details of how one would go about generating elliptic curve parameters. (I know standardized parameters exist, but I'm trying to understand both how they were generated and the ...
3
votes
2answers
241 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 ...
2
votes
1answer
371 views

Diffie-Hellman based password challenge response scheme

A very commonly used (examples: HTTP digest auth/CHAP/Kerberos) authentication scheme is something that looks like: Setup. Client and server both know a password $p$. Authentication. Server sends ...
12
votes
1answer
2k views

When do ECC patents end?

As the topic says, since when can ECC cryptography be freely used? Isn't it widely used because of patents? There is no alternative to it on embedded devices and smart cards. Just to mention: I am ...
11
votes
1answer
537 views

Why are elliptic curves over a field of characteristic 2 or 3 insecure?

The following is a quotation from my cryptography course: Recent results on the discrete logarithm raise big concerns on the security of elliptic curves over a binary field. What are these ...
10
votes
3answers
4k 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 ...
9
votes
1answer
1k views

Simple digital signature example that one could compute without a computer?

I am working on a document to explain Bitcoin to students. But I am having a hard time translating the principle described in §2 of the Bitcoin whitepaper in layman's terms. There is a great question ...
9
votes
1answer
1k views

What are the differences between the elliptic curve equations?

I think we're all aware of the "classical" Weierstrass (short?) elliptic curve equation: $y^2\equiv x^3 + ax +b \pmod p$. Well known examples of these curves include the NIST's and Brainpool ones. ...
8
votes
1answer
1k views

What is the curve type of SECP256K1?

This is possibly a dumb question. I'm trying to input SECP256K1 curve parameters to a system that expects any custom curve. The form is asking for "curve type". It offers three options: Short ...
7
votes
1answer
1k views

What is the difference between regular and “twisted” ECC curves?

When I do: openssl ecparam -list_curves I get, among other entries: ...
6
votes
1answer
735 views

How to derive the curve Ed25519 from Curve25519?

According to the paper "Faster addition and doubling on elliptic curves" by Bernstein and Lange, the Montgomery curve (Curve25519) $$v^{2}=u^{3}+486662\cdot u^{2}+u$$ is birationally equivalent to the ...
5
votes
1answer
2k 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. ...
5
votes
1answer
702 views

Elliptic Curve Verifiable Secret Sharing

I'm reading this paper, which on page 3(Section IV.C) presents a Jointly Random Verifiable Secret Sharing Scheme for Elliptic curves. The algorithm makes sense to me save for this part: "Each $P_{i\...
5
votes
1answer
2k 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 "...
5
votes
1answer
339 views

Implementing CD serial key system

I am trying to create a system where to unlock the application one needs to enter a serial code. I have read many articles on the theme but there are two problems bugging me. One is, If I have a ...
4
votes
2answers
471 views

Is it safe to generate two 256-bit ECC keys from 128 bits of entropy?

Apparently it is perfectly safe to use 128 bits of entropy to generate a single 256 bit ECC key. Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key? I assume this is because 256 bit ...
4
votes
1answer
348 views

Double-and-add/Montgomery VS blinding

I'm having a hard time understanding why people use constant-time techniques to counter time-attacks, when blinding seems as good and cheaper to implement. Why do people avoid blinding in ECC?
4
votes
1answer
205 views

representing binary finite fields in ASN.1

In SEC 2: Recommended Elliptic Curve Domain Parameters two types of finite fields are utilized - $\mathbb{F}_p$ and $\mathbb{F}_{2^m}$. In the case of sect193r1, $\mathbb{F}_{2^m}$ is the finite field,...
3
votes
3answers
1k 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 ...
3
votes
0answers
1k views

Can you help me understand this toy example of ECDSA signing and verification? [closed]

I'm a complete newbie to ECC. but I was trying to get my feet wet with (what I thought would be) a TRIVIAL/EXTREMELY SIMPLE example of ECDSA signing and verification (that I could check by hand). I'd ...
3
votes
1answer
387 views

What is a u-coordinate within Elliptic Curve Diffie-Hellman using the Montgomery ladder

I am trying to understand the below paragraph. Elliptic curve Diffie-Hellman is often calculated using the Montgomery ladder. This gives a simple and efficient calculation that is naturally ...
2
votes
1answer
641 views

Hide a weakness in ECC by choosing the prime or one of the curve coefficients

Suppose you are given a value $c$. Can you find a prime $p$ and an integer $b$ such that the elliptic curve $$E: y^2 \equiv x^3 -3x + b \pmod p$$ is cryptographically weak? You need to choose $p,b$...
1
vote
2answers
1k views

A private key with multiple public keys?

I'm trying to design a wallet, where any number of public keys can be handed out. Say Alice hands out the public keys to receive messages. She doesn't want others to be able to link all of the public ...