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.

209 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
124 views

Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
7
votes
0answers
119 views

About a SETUP mechanism on ECDH

I'm following these three articles: Kleptography: Using Cryptography Against Cryptography, Kleptographic Attack on Elliptic Curve Based Cryptographic Protocols and Elliptic Curve Kleptography . In ...
6
votes
0answers
132 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 ...
6
votes
0answers
90 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
6
votes
0answers
204 views

Cryptographically Secure Elliptic Curve

What are the properties a cryptographically secure Elliptic Curve must have? I have started to create a list and wanted to know if I forgot some important points, and if it is correct so far: A curve ...
6
votes
0answers
256 views

Index calculus over elliptic curve over function field

According to my understanding there are some pretty solid seeming roadblocks to carrying out an index calculus on an elliptic curve over a finite field. The general strategy is to take points over $E(\...
5
votes
0answers
549 views

How does post quantum key exchange in OpenSSH 8 work?

OpenSSH 8 supports a post quantum KEX, namely sntrup4591761x25519-sha512@tinyssh.org It says in its description that it is basically NTRU + ECC X25519. However, I have tried but cannot understand how ...
5
votes
0answers
191 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 ...
5
votes
0answers
97 views

Can cryptographically useful pairings only be used with elliptic curves?

As far as I understand one big advantage of ECC is that we can use pairings on the group of torsion points of the curve. I was wondering if it is possible to construct pairings from general finite ...
4
votes
0answers
75 views

Inverse Public Key Proof

Alice has a private key, $x$, and a public key $P = [x] \cdot G$ in a group of order $n$. Alice would like to also publish her inverse public key (inverted modulo the group order) $P_{inv} = [x^{-1} \...
4
votes
0answers
97 views

Regarding the need to hash the shared secret in X25519 with the public keys

I was looking at the LibSodium documentation where it says [...] and to mitigate subtle attacks due to the fact many $(p, n)$ [public key - secret scalar] pairs produce the same result, using the ...
4
votes
0answers
233 views

What is Frobenius map of an elliptic curve?

I was reading about elliptic curves from this PDF. Page 44 defines Frobenius map. It defines the frobenius map as $f(x,y) = (x^p, y^p) \bmod p$. Isn't it just an identity map? What's the use of this ...
4
votes
0answers
683 views

Fastest known Elliptic Curve Cryptography “solution” (coordinate systems (multiple?), algorithms, precomputed values etc)?

I am writing an Elliptic Curve Cryptography SDK in pure Swift, and currently I am only using Affine Point and simple Double-and-add. I am soon about to work on a faster solution. I am asking for help ...
4
votes
0answers
292 views

Encrypt using ECDH with two different EC public keys, minimizing payload size

Let's say Alice has the private EC keys $a$ and $b$, with a base point of prime order $G$. Alice computes the corresponding public keys $A = aG$ and $B = bG$, and sends them to Bob. Bob now wants to ...
4
votes
0answers
480 views

Elliptic Curve Blind Signature Implementation

I have seen this prior post: Elliptic Curve based blind signature implementation Currently I'm sizing up how difficult it would be to attain Elliptic Curve Blind signatures for an application I'm ...
4
votes
0answers
212 views

As a cryptographer, what are the things I should care about in my implementation of pairing functions?

As a beginner in cryptography, I do not know anything about different pairing types more than their names. So far, I know these names: Ate pairing, tate pairing, eta pairing, and r-ate pairing. I am ...
4
votes
0answers
170 views

ECIES: Purpose of optional shared information?

According to Wikipedia the ECIES algorithm has two optional shared information $S_1$ and $S_2$. They are used as follows: Generate a random shared secret $Z$ according to ECIES, which will never be ...
4
votes
0answers
497 views

Using the same private key for two ECC key pairs

Let $(d_1,Q_1)$ and $(d_2,Q_2)$ be ECC key pairs over two different elliptic curves (say NIST P-224 and NIST P-256). According to the Elliptic Curve Discrete Logarithm Problem (ECDLP), if the private ...
3
votes
0answers
99 views

Attack on Weierstrass Elliptic Curve

I have a naive question(as non specialist in this field). While reading Weierstrass Curve description,I found that it turns into 2 periodic tori on 2D complex plane. Is is it possible to create ...
3
votes
0answers
145 views

Security of ECC over finite fields of characteristic $p\approx2^{50\pm10}$?

What's the security of Elliptic Curve Cryptography over finite fields of word-sized characteristic $p\approx2^{50\pm10}$? We are talking about $\Bbb F_q$ where $q=p^k$ for some suitable $k$. ...
3
votes
1answer
171 views

Is this distributed random oracle scheme safe?

This question comes from an issue raised in another question: Non interactive threshold signature without bilinear pairing (is it possible)? Is the proposed random oracle model safe when trying to ...
3
votes
0answers
58 views

ECC: Lightweight proof of correct exponentiation

In the context of ECC. There's an EC point $P$ which is supposed to be a known power of another known point $G$ (generator). That is: $P = [k]G$ (in additive notation) This should be verified on an ...
3
votes
0answers
75 views

Using (EC)DH to generate a signature

Say I have access to a system A that is limited to performing (EC)DH, followed by key derivation to produce a secret key. This secret key is later used to provide integrity protection. There is a ...
3
votes
0answers
83 views

What are some use cases for white-box digital signatures?

There were 2 papers published in the last year, that describe 2 different white-box identity-based digital signature schemes: White-Box Implementation of the Identity-Based Signature Scheme in the ...
3
votes
0answers
78 views

How to use Montgomery arithmetic for elliptic curves (FIAT cryptography)

Let us consider the source code for curve P-256 from BoringSSL. This source code can be found here. This source code uses the FIAT generated implementation for field arithmetic. This implementation ...
3
votes
0answers
109 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
0answers
47 views

If curve bn256/bls12 support the isomorphism from $G_2$ to $G_1$?

Is bn256 or bls12 a type-2 pairing-friendly curve? As Dan Boneh said here While in many pairing instantiations this ψ exists naturally, in some instantiations it does not. However I can not find ...
3
votes
0answers
83 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
3
votes
0answers
34 views

EC non-shared cryptosystems - different group for every party

Efficient Identity Based Parameter Selection for Elliptic Curve Cryptosystems by Arjen K. Lenstra contains a proposal for a non-shared elliptic curve cryptosystem. Every party chooses its own field ...
3
votes
0answers
172 views

Precomputation attacks against ECDH

Diffie-Hellman groups are vulnerable to sieving precomputation attacks. These attacks allow a one-time computation against a given DH modulus that makes it practical to attack all subsequent key ...
3
votes
0answers
58 views

EC-ELGAMAL message mapping

I have been able properly set up an EC-elgamal protocol by using algorithms available in an IP that I have developed. Everything works fine, except for the fact that I haven't been able to completely "...
3
votes
0answers
147 views

How to map the points of an elliptic curve cyclic group to $\mathbb{Z}_q$ using a hash function?

Let $E$ be an elliptic curve defined over $\mathrm{GF}(q)$, where $q=p^r$. Let $G$ be a cyclic group of points of $E$. Then how we can map points of $G$ into $\mathbb{Z}_q$ using a hash function.
3
votes
0answers
101 views

Pairings over elliptic curves on rings

Looking at this presentation, Boneh says that elliptic curves could be defined over $\mathbb{Z}/n\mathbb{Z}$ and not necessarily over a prime field $\mathbb{F}_p$ and hence we could define pairings ...
3
votes
0answers
222 views

How can I calculate the security level provided by a supersingular Elliptic Curve?

I want to know what security level is provided by an elliptic curve used in Supersingular isogeny Diffie–Hellman key exchange (SIDH). Is there any mathematical convention to follow or by looking at ...
3
votes
0answers
84 views

Which safe elliptic curves allow for the fastest scalar multiplication

I'm specifically looking for curves that are safe (ideally on this list: https://safecurves.cr.yp.to/) and which allow for the fastest scalar multiplication operations on arbitrary points. By '...
3
votes
0answers
199 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
0answers
266 views

TypeA pairing, elliptic curves in pairing based cryptography

I am beginner to pairing-based cryptography. After downloading jpbc library, curve parameters files are seen as properties file. For example, for type A curve, following parameters are given. type a ...
3
votes
0answers
2k views

What is the (uncompressed) x,y-representation of a curve point on the P-256 NIST elliptic curve?

I am trying to understand the FIDO U2F Raw Message Format, especially the format in which a user public key should be provided. The documentation says the following: A user public key [65 bytes]. ...
3
votes
0answers
276 views

Gallant-Lambert-Vanstone method

I am experimenting with the GLV method but cannot manage to get the right results according to the literature. I managed to find lambda, beta, split $K$ into $k_1$ and $k_2$ etc. for the curve I'm ...
2
votes
0answers
45 views

Is “double-and-add-always” a good mitigation against side channel attacks?

In Discrete Log based Cryptography, one of the core operations that one, has to perform is modulo exponentiation. There are many algorithms to choose from, especially, when considering my point of ...
2
votes
0answers
86 views

MOV-attack on ecc: Time complexity and example

There already is this pretty big post about the MOV-attack. It states, that the discrete logarithm problem on elliptic curves can be transformed to a discrete logarithm problem over a finite field. ...
2
votes
0answers
58 views

What is a formula of a twist?

With the curve secp256k1, the order of the twist is 3×197×1559×96769×146849×2587814237219×375925338294461779×101009178936527559588563023359 But I can't understand what is formula of this twist(twist ...
2
votes
0answers
83 views

Pollard Rho Optimization

One of the most important attacks on Elliptic Curve cryptography is Pollard's Rho method. The effect on security can be seen on SafeCurves. This attack is pretty old and there has been a bunch of ...
2
votes
0answers
100 views

Curve25519 Attacks and Security

Curve25519 is a pretty secure way to exchange a key. In the original Paper and on SafeCurves a lot of attacks and security aspects are mentioned: Attacks: Brute force: This one is theoretically ...
2
votes
0answers
106 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^...
2
votes
0answers
74 views

How hard is it to link a hardened BIP32 child public key to it's parent public key?

The BIP32 spec says this in the security section: ...
2
votes
0answers
68 views

Elliptic curve of order $p = 2q + 1$

Does anyone know an example of an Elliptic Curve of caracteristic $p$ ($E_p$) that has a point generator $G$ that generates a subgroup of order $q$, with $p$, $q$ being prime numbers and $p = 2q + 1$?
2
votes
0answers
29 views

About the scalar multiplication on Koblitz curve in FIPS PUB 186-4 (2013)

In FIPS PUB 186-4, the computation of scalar multiplication on Koblitz curves is given in p.106~109. In p.109, step 11.3, $(r_0,r_1)$ is updated with $(r_1+\mu\,r_0/2,-r_0/2)$. But under ...
2
votes
0answers
76 views

Shamir three-pass protocol Elliptic Curve

I want to know how I can implement this protocol. I know how Shamir three pass protocol operates without elliptic curve, but I don't know how I can perform it with elliptic curve. I read about this ...
2
votes
0answers
112 views

Security of an Elliptic Curve Public Key with a “Small” x-coordinate

Consider an elliptic curve over a finite field $F_p$ with $p$ prime and order $n$. Let $Q$ be a generator for the field. Given a public key point $P = aQ$, suppose we have an algorithm that finds an ...

1
2 3 4 5