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
6
votes
1answer
3k 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. ...
6
votes
2answers
1k views

Raw curve25519 public key points

I'm trying to understand curve25519, and ECC public points. I'm playing with Minisign, to better understand the fundamentals of ECC. Minisign uses curve25519 and outputs public keys as base64 ...
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
771 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
360 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
1answer
483 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 ...
4
votes
2answers
608 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
227 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,...
4
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 ...
4
votes
4answers
620 views

Is there any alternative for extended euclidean algorithm to perform modulo division?

I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division. It appears the that ...
4
votes
2answers
715 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-curve ...
4
votes
2answers
978 views

In Elliptic Curve, what does the point at infinity look like?

We know that for each point $P$ in curve $E$ there exists a minimum scalar $k$ such that $k*P$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only ...
3
votes
2answers
2k 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 ...
3
votes
1answer
392 views

Proving Non-Existence of ECC Backdoors

In light of the NIST Dual EC DRBG scandal, I was intrigued by a NIST slide (slide 9) that said the two points P and Q can be chosen so that the chooser can prove they don't have a backdoor. This ...
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 ...
2
votes
1answer
680 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$...
2
votes
2answers
4k 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 ...
2
votes
1answer
712 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 ...
0
votes
1answer
204 views

Is there any way to test how secure is a new cryptosystem? [closed]

I have investigated Elliptic Curves and after that I have designed a cryptosystem using this technique. How can I test the safety of my scheme compared to another cryptosystems that use factoring such ...
12
votes
1answer
2k 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-...
9
votes
1answer
1k views

Why are co-factors 4 and 8 so popular when co-factor is more than one?

For elliptic curve cryptography, I seem to keep coming across curves with either co-factors of 4 or 8 whenever it is a non-prime order group. Is this a co-incidence? Have we studied ECC for curves ...
8
votes
1answer
598 views

Point-at-infinity and error handling

I'm looking at a piece of (non-object oriented) code where functions return point-at-infinity for a specific prime curve if a calculation errors out. This is even the case when validating arguments to ...
8
votes
1answer
3k 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 ...
8
votes
1answer
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 ...
6
votes
1answer
273 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 ...
5
votes
1answer
277 views

Which attacks are possible against raw/textbook elliptic curve?

A quick question, we know that raw RSA is a no go. To solve this we have different PKCS standards forcing structure on the input messages. For EC the story is something else. For signatures we have ...
5
votes
0answers
404 views

Using a product of a series of curve25519 scalars as a private key [duplicate]

There are a few systems like the GNU Name System and the Sphinx mixnet packet format that employ a series of curve25519 scalars all multiplied together as a private key. Are there any caveats to ...
5
votes
1answer
592 views

Is there a flaw in this ECC blind signature scheme?

Recently I've found the following work on the internet: An ECC-Based Blind Signature Scheme The paper claims to be an ECDSA blind signature however it seems that their scheme has a flaw in it. The ...
5
votes
1answer
857 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 ...
5
votes
2answers
544 views

How to securely map messages to points on an elliptic curve

I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one ...
4
votes
2answers
1k views

Determine if a public key point y is negative or positive, odd or even?

Take an elliptic curve cryptography public key (x, y) and its additive inverse (x, -y). How do you identify which is the positive point and which is the negative point? Examples: Private key 1 -> (x,...
4
votes
3answers
573 views

Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption?

From DrLecter's comment, I know that DDH problem can be efficiently solved with this $$e(g^a,g^b)\stackrel{?}{=} e(g,g^z).$$ I have some trouble to understand this map $e:G \times G \to G_T$. Am I ...
4
votes
2answers
2k views

Is there any reason to use RSA or DSA when we have ECC?

I am having trouble coming up with a use case for RSA or DSA. It appears that ECC is better in every way. Is this true? I am looking for cases where RSA/DSA is superior to ECC, not where it is used ...
4
votes
1answer
4k 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 ...
4
votes
2answers
205 views

Difficulty of Reversing Elliptic Curve

In ECC, it is apparently easy to verify the final point given the starting point and the number of hops. But it is difficult to compute the number of hops given just the starting point and the final ...
4
votes
1answer
4k views

EC curve selection

Say for instance, this webservice offers the following curves. sect283k1 sect283r1 sect409k1 sect409r1 sect571k1 sect571r1 secp256k1 prime256v1 secp384r1 ...
3
votes
1answer
373 views

Counting points on elliptic curve over binary field

How to count number of rational points on elliptic curve over binary field?
3
votes
1answer
347 views

What can be learned from the ciphertext of LibSodium's crypto_box_detached()?

LibSodium, (https://github.com/jedisct1/libsodium), has a function crypto_box_detached() which does authenticated encryption using the public key of the recipient ...
3
votes
1answer
3k 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 ...
3
votes
1answer
468 views

Can keys from Bitcoin's Hierarchical Deterministic Wallets be correlated (reducing privacy)?

I'm trying to understand if the feature "Hierarchical Deterministic Wallets" in Bitcoin allows for complete privacy of all derived keys, and if any of those keys can be associated with each other ...
3
votes
0answers
198 views

Prime extension field encoding ASN.1

ASN.1 encoding for elliptic curve cryptography is recommended by Certicom, as explained at a related question, covering curves over prime fields and binary extension fields. I'm looking for known ...
3
votes
1answer
783 views

libsodium x25519 and Ed25519 small order check

Studying libsodium implementation of x25519 and Ed25519 I saw that it performs an small order check comparing given inputs with a hard coded blacklist of values. Is this list exhaustive or it is a ...
2
votes
2answers
1k views

Why does NaCL have different keys for signing and encryption?

I want to start using NaCL to sign messages that will go into a message queue, and I noticed that it generates different keys for each operation. Is there a reason for this? Can I not use the same PK ...
2
votes
2answers
660 views

What is the fastest elliptic curve operation f(P) in affine coordinates such that f^n(P)=P only if n is large?

I'm working with the affine representations of points of the Secp256k1 elliptic curve (from Bitcoin). I've read many papers that show that computing some functions, like $f(P)=3P$ can be computed ...
2
votes
1answer
367 views

Adding points on Elliptic Curves

How do we add the integer points $P=(-1, 4)$ and $Q=(2, 5)$ on the elliptic curve of the form $y^2=x^3+17$ ?
2
votes
1answer
917 views

Brute force attack expected running time

I am a bit confused about the expected running times of brute force attacks on different cryptosystems. So let's assume a key size of $2^n$ bits. Symmetric key cryptography: $E(brute)$ = $2^{n-1}\...
2
votes
2answers
1k views

Reuse of a DH / ECDH public key

I was wondering whether it is safe to use the same DH or ECDH key pair in more than one key agreement, particularly if these public keys are in a public registry. These public keys could be used by ...
1
vote
2answers
124 views

How does this formula work $(aG + bG) = (a + b) G$ in ECDSA?

Please explain how does this formula $(aG + bG) = (a + b) G$ work in ECDSA? According to the source: $a$ and $b$ are different private keys Suppose $a = 3$ $b = 4$ then the public key is $Q = aG$...
1
vote
0answers
364 views

ECC Curve25519: How to generate this kind of private key? / Strange key exchange mechanism

I'm currently reverse engineering a program that uses Curve25519 key exchange in network communication. I have only a basic understanding of ECC, so maybe this thing just seems strange to me. The ...
1
vote
1answer
433 views

does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448?

Quoting The Transport Layer Security (TLS) Protocol Version 1.3: ECDSA algorithms Indicates a signature algorithm using ECDSA [ECDSA], the corresponding curve as defined in ANSI X9.62 [...