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.

157 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
117 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 ...
6
votes
0answers
67 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
235 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(\...
4
votes
1answer
119 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 ...
4
votes
0answers
221 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
161 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 ...
4
votes
0answers
362 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
91 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
372 views

Using a product of a series of curve25519 scalars as a private key

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 ...
4
votes
0answers
200 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
146 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
445 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
66 views

ECDSA signature verification checks

From Wikipedia: Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are otherwise valid. Check that $Q_a$ lies on the curve. Check that $n*Q_a = O$ Verify that $r$ and $s$ ...
3
votes
0answers
76 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
31 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
153 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 ...
3
votes
0answers
74 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
32 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
49 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
156 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 ...
3
votes
0answers
385 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 ...
3
votes
0answers
106 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
139 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 ...
3
votes
0answers
90 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
185 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
78 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
301 views

Could a C25519/ED25519 cryptographic module be FIPS certified?

NIST algorithms include ECDH and ECDSA. NIST also specifies curves. Is the use of NIST curves required for FIPS certification or could other curves theoretically be certified if someone were willing ...
3
votes
0answers
185 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
232 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
205 views

What happens if no final subtraction is done in Montgomery multiplication?

I'm doing Montgomery arithmetic modulo $N = 2^{255}-19$ for the Curve25519, picking $R = 2^{256}$ for Montgomery. After multiplying two numbers $0 \leq A,B < N$ in the Montgomery representation ...
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
237 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
88 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 ...
2
votes
0answers
41 views

Security strength of JPBC Type A curve compared to SecP curve

I recently encountered some problems when learning about the JPBC library. Does the curve generated by (J)PBC using the method typeAcurvegenerator(160,512) and the ...
2
votes
0answers
71 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 ...
2
votes
0answers
57 views

ECC - complex multiplication and key agreement

I'd like to ask three questions - 2 of them regard CM method. The last is regarding the ECC domain parameters generation on the fly, see https://eprint.iacr.org/2015/647.pdf What role has ...
2
votes
0answers
140 views

Proving that a point on elliptic curve is smaller than half of group's order

Let's say I have an elliptic curve where generator $G_1$ has prime order $q$. Let's also say I have committed to a point $A_1 = a \cdot G_1$. Could I use the scheme below to prove that $a < \frac{q}...
2
votes
0answers
56 views

Proving key equivalence across different elliptic curves

We can use the technique described in this answer to prove key equivalence across two elliptic curves of different order. I'm wondering if modifying the technique as described below would compromise ...
2
votes
0answers
153 views

j-invariant of an elliptic curve

Given an elliptic curve $(E/\mathbb{K})$ where $char(\mathbb{K}) \ne 2,3$ defined by the Weierstrass equation $y^2=x^3+ax+b$. The $j$-invariant is $j=1728 \frac{4a^3}{4a^3+27b^2}$. I want to ...
2
votes
0answers
44 views

Is my way safe to remove SSL CA Cert by DHT and PoW NodeID for a decentralized system?

To implement a decentralized system, I wrote a TLS like P2P net stack. The main idea is removing CA Cert from the whole system by using a DHT for Naming and Key Exchange. I am not a crypto expert, so ...
2
votes
0answers
100 views

Creating ECC Signature - Is “R” necessary in calculating “S”

After going through the mathematical proof in confirming ECDSA, it doesn't seem apparent to me that "R" is necessary in calculating "S" for the signature. In other words, what's the problem with ...
2
votes
0answers
167 views

What standards of ECC point compression exist?

The method that I used before to decode EC point from public key led me in a dead end. So I just want to know what yet I could try. I've got a public key that I don't know how to decode and I am ...
2
votes
0answers
278 views

Ed25519 key generation

the following rfc describes the key-pair generation mechanism for Ed25519; the first two steps are as follows: Hash the 32-byte private key using SHA-512, storing the digest in a 64-octet ...
2
votes
0answers
311 views

ECDSA public key recovery is discovered by whom?

Im looking for the history of the method (ECDSA public key recovery from signature). Where is this implementation first appeared in (is it bitcoin?) and who discovered this method?
2
votes
0answers
149 views

Is EC El Gamal the only option?

This question is related to the question I asked here. I'm looking for encryption scheme with the following properties: Given $m$ is a 256-bit value, $pub_a$ and $pub_b$ are public keys, and $priv_a$ ...
2
votes
0answers
61 views

Asymmetric encryption property required in an authentication protocol

We want to choose an asymmetric encryption scheme for use as follows: A device holds its private key, with the corresponding public key known and trusted by all. The device also holds a small $b$-bit ...
2
votes
0answers
457 views

What ECDSA key is used to sign the ECDHE key exchange?

I have a server using TLS1.2 with an ECDSA certificate using secp256r1. The algorithms being used to connect to my browser are TLS_ECDHE_ECDSA_WITH_AES_256_GCM_SHA384 as I expect from my server ...
2
votes
0answers
104 views

Group signature Elliptic curve

I have been doing some research in group and ring signature literature. I am trying to find a ring/group signature which provide the following propriety: Anonymity for the signer Verifiable by a ...
2
votes
0answers
212 views

What pairings are used in PBC and charm-crypto with the proposed elliptic curves?

I'm implementing a pairing-based signature scheme using Charm Crypto and PBC, and I'm struggling to understand the relationship between the curves proposed for use with pairings and the pairings ...
2
votes
0answers
172 views

Frey-Rück Attack (FR-Reduction) - Tate Pairing

I am trying to understand the Frey-Rück attack and found different ways of a possible implementation. Since I am not yet very familiar with the Tate-Lichtenbaum pairing and the theory of divisors I ...