Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

8
votes
0answers
109 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
190 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(\...
7
votes
0answers
82 views

Safe generation of $k$ points on a curve such that the mutual discrete logs are hard?

I have a multiplicative group $G$ of prime order $p$ implemented using a twisted Edwards curve (similar to Ed25519). I want to compute a set of $k$ distinct points $P_1,...,P_k$ that generate $G$, ...
5
votes
0answers
55 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 ...
5
votes
0answers
507 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 ...
4
votes
0answers
167 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
148 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
279 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
88 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
328 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
192 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
395 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
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
29 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
227 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
84 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
116 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
78 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
153 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
69 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
196 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
175 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
55 views

Efficiently formatting data so that each byte is critical

I'm experimenting with implementing a Fair Exchange Protocol that assumes there is a trusted third party to provide a hash-checksum of the two files for each missing byte, (so that the exchange can ...
3
votes
0answers
200 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
182 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
130 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 ...
3
votes
0answers
218 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
41 views

ECDSA signing process

I am trying to learn how ECDSA works. I do not have a background in maths, but have been following a guide which has built me up from finite fields, elliptic curves. I am unable to figure out how a ...
2
votes
0answers
37 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
45 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
80 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
47 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
84 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
41 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
59 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
123 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
174 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
252 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
123 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
53 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
334 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
85 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
77 views

How to find q in a corrupted ECDSA signauture

I'm doing exam papers for a crypto exam and I've been given a corrupted ECDSA signature. I'm asked to check if the signature is valid (which I know how to do), however, the q value is corrupted and so ...
2
votes
0answers
271 views

Why does Smart's attack only work on anomalous curves?

Nigel Smart's attack solves the discrete logarithm problem in linear time. It requires the curve, however, to be anomalous, i.e. to have a trace of Frobenius equal to one or, equivalently, to be of ...
2
votes
0answers
194 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
134 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 ...
2
votes
0answers
209 views

How are Zhang-Safavi-Susilo signatures short?

ZSS signatures have been introduced by Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo: An Efficient Signature Scheme from Bilinear Pairings and Its Applications, in proceedings of PKC 2004. ...
2
votes
0answers
159 views

Finding the largest gap between the x coordinates of all points on an elliptic curve

Till now all we know is Hasse's theorem, which states that $|\#E(p)-(p+1)| \leq 2\sqrt{p}$, where $\#E(p)$ is the total number of points in $E_p(a,b)$. Is there any other theorem which defines ...
2
votes
0answers
399 views

Feasible attacks on ECRSA cryptosystem

In ECRSA cryptosystem, I want to know the feasible attacks. For illustrations we have two prime $p$ and $q$ such that $p \equiv 2 \pmod 3$, $q \equiv 2 \pmod 3$ and generate key pair as follows: $$n = ...