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
0answers
16 views

Pohlig Hellman and small subgroup attacks

While studying Curve25519 I read about the small subgroup attack in chapter 3. So far i know, that you need a point with a small subgroup to do such an attack. Curve25519 has a basepoint with prime ...
1
vote
1answer
82 views

Performing EdDSA/Ed448 employing Montgomery ladder

EdDSA can be efficiently performed employing the Montgomery ladder. In order to implement this method, the base point should be converted to Mont. space, then the Mont. ladder should be executed, and ...
2
votes
0answers
85 views

All Curve25519 Parameters with Explanation

I'm trying to sum up all Curve25519 parameter and specification reasons. Can you tell me if I missed some important reasons or parameters in the following list?: Curve: Montgomery Curve. $M_{A,B}: By^...
3
votes
1answer
129 views

Likelihood of signature collision with EdDSA

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid ...
159
votes
4answers
107k 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 ...
-3
votes
0answers
74 views

Deterministic DSA by Thomas Pornin (Java Illustration, its Errors) [closed]

(DISCLAIMER: I'm clearly seeking a point to be illustrated from a white paper as explained here, "How should questions be handled involving code?", and <...
2
votes
2answers
563 views

How do I multiply a Twisted Edwards point in Montgomery space?

EdDSA (and ed25519) signatures require a scalar multiplication. Currently, I do this directly in Twisted Edwards space. (The code can be found in my crypto library.) My research and my tests ...
3
votes
0answers
102 views

Check validity of generated parameters for SIDH

In section 4.1 of the paper Towards quantum-resistant Cryptosystems From Supersingular Elliptic Curve Isogenies by Feo, Jao and Plût it is described how you generate valid parameters for the SIDH ...
3
votes
1answer
49 views

Are skeleton keys possible for ECCDSA?

As alluded to here (split-key vanity addresses for bitcoin), ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public ...
0
votes
1answer
33 views

Curve25519 base point speed up

In the paper regarding Curve25519 DJB defines the base point to be $P_{base} = (9,y)$. The main reason for choosing it this way is, that $P_{base}$ has a big prime order which gives security ...
1
vote
1answer
41 views

Hash into elliptic curves for private set intersection

Would it be insecure to hash a message $m$ to an elliptic curve point by multiplying it to some generator $G$ for the purpose of a private set intersection ? $$ M = hash(m) * G $$ I keep seeing ...
1
vote
2answers
92 views

Curve25519 function, scalar multiplikation

This is the main paper for Curve25519. In section 2: Specification there is a important theorem. In this theorem Bernstein defines the function $X_0 : E(F_{p^2}) \rightarrow F_{p^2}$. First Question:...
3
votes
1answer
62 views

Curve25519 key structure

In the paper regarding Curve25519, the set of public keys $q$ is $\{q : q\in \{ 0,1,2,...,2^{256} - 1\}\}$ and the set of private keys $n$ is $\{n : n\in 2^{254} + 8 \cdot \{ 0,1,2,...,2^{251} - 1\}\}$...
3
votes
1answer
45 views

Curve25519 extension field

The paper regarding curve25519 presents a theorem in chapter 2 (specification). The extension field $F_{p^2}$ is used in this theorem. I don't understand why this extension field is needed for the ...
1
vote
1answer
1k views

Is ECDH(E) Key Exchange FIPS 140-2 compliant?

We have read dozens of documents now - some that contradict each other - and cannot find a solid source of truth. Does FIPS 140-2 compliance allow for the use of elliptic curve cryptography as a key ...
0
votes
0answers
23 views

How to estimate the computation overhead of ECDSA?

I am using ECDSA as a digital signature scheme. Using Charm, I got the timing for the multiplication, exponentiation, and pairing operations; they take 0.005, 9, and 4.4 ms respectively. I want to ...
4
votes
2answers
2k views

Recovering private key from Secp256k1 signatures

I've seen many answers here and many articles that says we can recover the private key from reused R signatures. But, what if the r,s signatures are different in transaction of bitcoin then is there a ...
0
votes
2answers
1k 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 ...
1
vote
1answer
101 views

Brute Force on Curve25519

I was thinking about a brute force attack on Curve25519. For this, we need to solve the discrete Logarithm problem $P = [n]Q \bmod 2^{255} - 19$. $P$ and $Q$ are known Points on the elliptic curve, so ...
2
votes
1answer
70 views

How convert Point on Curve into AES key?

I'm playing around with ECC, trying to encrypt traffic between my webapp and backend (its not a product, im trying to learn and understand more about ECC) I managed to generate keys, successful run ...
1
vote
1answer
32 views

What can be said about the order of short Weierstrass curves with $a=1$ and $b=0$?

I am looking at a elliptic curves of the form $E:y^2=x^3+x$, i.e. short Weierstrass curves wtih $a=1$ and $b=0$, defined over a field $\mathbb{F}_p$ with $p$ being a safe prime. Somewhat interestingly,...
14
votes
2answers
2k views

Can I still use insecure curves/ciphers for time relevant encryption?

Can Ciphers that are known to be insecure because their keysize is considered too small still be used in appliances that have a tight decryption timeframe? In particular I am looking at ECC2K-130. ecc-...
0
votes
0answers
5 views

Use of encrypting data in transit over a HTTPS connection [migrated]

I find certain APIs (that provide sensitive information) using algorithms like ECDHE with X25519, on top of the already ...
1
vote
0answers
46 views

Pohlig-Hellman on ECDLP over extension field $\mathbb{F_p}^6$

Suppose there is an elliptic curve $E$ in form $y^2=x^3+b$ defined over $\mathbb{F_p}$, where $p$ is large prime. #$E(\mathbb{F_p})$ is also a large prime but #$E(\mathbb{F_p})\ne p$. ECDLP on this ...
1
vote
1answer
72 views

Ensure Data Integrity In An ECDH Key Excange

Been playing around with the inner workings of onion routing and I have a problem. If I wanted to send the 2nd node of a relay network an ephemeral ECC public key, it has to go through node 1, so that ...
4
votes
1answer
46 views

Can libsodium's X25519 encryption construction be generalized?

It is my understanding that libsodium's sealed_box is based on X25519, a Diffie-Hellman function: By combining the X25519 key agreement with a symmetric cipher and having a recipient derive the ...
1
vote
0answers
28 views

How do Edward curves scale better in computation time compared to Weierstrass curves?

I see people talk about Edward curves (when I discuss Ed25519) as better curves than Weierstrass for computations. Now I get that Edward curves have the nice addition formula, but if we have a ...
0
votes
1answer
50 views

Characteristics of an isogeny between super-singular elliptic curves

I believe I've read this before, but I can't find it despite hours of searching on Google. I've know the common definition of isogeny in elliptic curves, as $\phi:E_1 \rightarrow E_2$ a nonconstant ...
0
votes
2answers
110 views

How to encrypt with elliptic curve cryptography (ECC)?

I need to ask this, as I am not allowed to comment and don't quite understand an existing answer because I don't have a cryptography background and never looked into how ECC works. Why can't you ...
0
votes
0answers
28 views

Can Pedersen commitment be used in pairing groups?

For bilinear groups: $(p,\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T,e,g_1,h_1,g_2,h_2)$, where $\mathbb{G}_1,\mathbb{G_2},\mathbb{G}_T$ are groups of prime oder $p$. $g_1,h_1$ are generators of $\mathbb{G}...
1
vote
1answer
129 views

Complexity of computing zk-SNARK Proofs

Disclaimer: I have no background in cryptography, and everything I'm asking about is what I've learnt from last couple of days of frantic reading on this topic. Any help is much appreciated. Q: What ...
3
votes
1answer
306 views

Sextic twist of BN pairing parameters vs security

I've previously asked questions on BN pairing parameters. Here's one more. In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some ...
1
vote
0answers
35 views

Non-interactively share secret with group without revealing to generator?

Imagine someone knows a set of $n$ ECC public keys $\mathcal R = \{K_1, K_2, ... K_n\}$ but they don't know the corresponding private keys $k_1$, $k_2$ ... $k_n$. They wish to create a public key $sG$ ...
0
votes
0answers
19 views

Can we use HMQV in an asynchronous setting?

Following the HMQV paper, to perform a key-exchange, Alice ($\hat{A}$) and Bob ($\hat{B}$) perform the following: $\hat{A}$ generates the long-term key pair ($sk_A= a$, $pk_A =g^a$) and the ephemeral ...
7
votes
1answer
173 views

Is this a safe way to prove the knowledge of an ECDSA Signature?

I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it. In short terms it consists in generating an ECDSA signature using the point $R$ as generator, ...
1
vote
1answer
52 views

MOV attack when $E(\mathbb{F}_q)$ is cyclic

Suppose $P\in E(\mathbb{F}_q)$ and $R=dP$. In the MOV attack, we compute $\alpha=e(P,T)$ and $\beta=e(R,T)$ and try to solve the discrete logarithm problem for $\alpha$ and $\beta$ in the finite ...
5
votes
1answer
155 views

Hash multiset to point on elliptic curve where $A = 0$

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that ...
1
vote
1answer
109 views

Which hash algorithms are suitable for use with Elliptic-curve cryptography

I try to use Elliptic-curve cryptography system first time really, so i confused about it. this is the scenario: First i want to hash a message then, sign it. i use javascript so i try to follow this ...
2
votes
2answers
146 views

Why the output of elliptic curve based cryptosystems is smaller than the ordinary public key cryptosystems?

I am trying to understand how much the output of elliptic curve based cryptosystems (for example elliptic curve ElGamal) is smaller than the ordinary public key cryptosystems. I know that the ...
1
vote
0answers
40 views

How many 2-torsion points in an elliptic curve?

N torsion points have the structure ker([n]) ≅ Zn×Zn , so ker([2]) ≅ Z2×Z2 , gives us 3 2-torsion points. but ker([4]) ≅ Z4×Z4 ,this means we have 5 subgroup of order 4 . In each subgroup , there is ...
1
vote
0answers
39 views

Which groups are secure for DL-Problem?

I was wondering why some groups provide more security to cryptosystems relying on DL-Problem. It is not clear to me whether it is just due to the known attacks or if there are some other reasons. So ...
3
votes
1answer
71 views

Are there any special points on an elliptic curve which would weaken security?

So, according to the elliptic curve discrete logarithm problem: $$A=[r]B$$ In which $A$ and $B$ are points on the curve, and r is the scalar. It is trivial to compute $A=[r]B$ if $r$ is known, but ...
0
votes
1answer
77 views

ECCS: Elliptic Curve Cryptography Cramer Shoup

Introduction I know how to do Cramer-Shoup with cyclic groups. But how do I do it in elliptic curve cryptography (ECC)? Cramer-Shoup with cyclic groups Following was taken from Wikipedia: https://...
1
vote
1answer
51 views

OID for Ed25519

I am working on a code generating Edwards curve (Ed25519) keys in a HSM using PKCS#11 API. In the public key template the CKA_EC_PARAMS uses an OID to specify the curve. The encoding for Ed25519 is ...
0
votes
1answer
59 views

A multi-target attack on 128-bit ECDSA private keys

I'm thinking about doing this as a project, but I'm not sure how I'm supposed to proceed. So I have an 128-bit ECDSA, which would provide about 128 bits of security (if we do not use special methods ...
-1
votes
2answers
74 views

Does the private key in ECDSA have to be an integer?

In ECDSA, the public key $P$ is computed via the private key $k$ and the generator point $G$: $P=[k]G$ The scalar $k$ (private key) has to be an integer. However, I am wondering - does the private ...
21
votes
3answers
17k views

Why is the P-521 elliptic curve not in Suite B if AES-256 is?

In the NSA's document, "The Case for Elliptic Curve Cryptography" (archived), we have ...
0
votes
1answer
51 views

Find Points of order 2 on elliptic curve [closed]

Suppose there is an elliptic curve $E:y^2=x^3+(p-1)\cdot x\bmod{p}$ with $p>3$. The question is: What are the points that have an order of 2?
18
votes
2answers
1k views

Can deterministic ECDSA be protected against fault attacks?

In a paper by Barenghi and Pelosi, it was described that fault attacks could be used to derive the secret key when using deterministic ECDSA as described in RFC6979 by @Thomas_Pornin Deterministic (...

1
2 3 4 5
30