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

Does an binary elliptic curve like sect571r1 support a bijective asymmetric operation pair on bytes? If so, is there a self-contained example?

I'm wondering if a binary elliptic curve (such as sect571r1 aka B-571) supports pairs of asymmetric operations (for example, either sign/verify or encrypt/decrypt) on a fixed bit or byte input size in ...
3 votes
1 answer
572 views

EC has lower CPU consumption than RSA under what condition?

When I searched Google, the top result said On average, processing for ECC is about four times less CPU-intensive than for RSA. Yeah, but under what condition? The page says "A 256-bit EC ...
0 votes
0 answers
59 views

Is Index Calculus Attack on hyperelliptic curves feasible with a common laptop?

I am studying this paper about an index calculus attack in hyperelliptic curves for genus $3, 4, 5, \dots, 9$. Nicolas Thériault, Index calculus attack for hyperelliptic curves of small genus, 2003. ...
0 votes
1 answer
75 views

Does the ECDSA private or public keys contain data about the signature hash algorithm?

:-) Hello I was wondering if the signature hash algorithm was a part of the private key or just the signing process? Should a signature instance depend on the private key? (Of course, still talking ...
4 votes
1 answer
164 views

How are the unified addition formulae in extended twisted Edwards coordinates derived from the affine addition formulae?

I am trying to understand point addition in RFC8032 section 5.1.4, which references the paper "Twisted Edwards Curves Revisited" (https://eprint.iacr.org/2008/522.pdf) to describe the quick ...
2 votes
1 answer
234 views

Find Ed25519 Y Coordinate from X Coordinate

Are there any available formulas to determine a $Y$ coordinate given only an $X$ for the Ed25519 curve? The closest thing I've come to find is the recover_x(y, sign)...
4 votes
1 answer
165 views

Is it true that Public keys with even y coordinate correspond to private key that are less than n/2 and vice versa? (Secp256k1)

The question is somewhat complex and directed to clearing things out. Suppose that $n$ is the order of the cyclic group. It $n - 1$ is the number of all private keys possible ...
3 votes
2 answers
741 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
1 vote
0 answers
55 views

Power consumption of Post-Quantum Crypto vs. legacy crypto

Is there any educated views or references on how the PQC NIST finalists compare to legacy crypto with regards to power consumption? Many thanks
5 votes
3 answers
464 views

When working in a subgroup of EC in EdDSA (especially Ed255190), how is it OK to use operations different from that of the main group?

Ed25519 uses a composite order Elliptic Curve but works in the prime order subgroup of the main group. As per group theory, the subgroups use the group operation. However, as per this, Ed25519 ...
-2 votes
2 answers
89 views

How to modify elliptic curve point?

Good day. How I can modify elliptic curve point, like number modulo ? number example, with unknown privkey 5555555555 : 5555555555 % 2500 = 555 how to get pubkey with privkey 555, from pubkey with ...
0 votes
1 answer
64 views

Is product of two linear combinations over a finite field information hiding?

Suppose we have a 32-bit message $ M=(m_1,..m_{32}) \in \{0, 1\}^{32} $ and we have secrets $ F_{i, b} $ and $ G_{i, b} $ (2x32+2x32=128 secrets in total). $$ \forall 1 \leq i \leq 32, b \in \{0, 1\} :...
0 votes
0 answers
36 views

Fast methods for adding the basepoint to an elliptic curve point?

Are there any clever (fast) methods for adding the basepoint (generator) to an arbitrary point on elliptic curve, finally ending in affine coordinates? I.e. if G is ...
2 votes
2 answers
84 views

How is the edwards448 generator derived from the curve448 generator in RFC 7748?

In RFC 7748, it is explained how the Montgomery curve, curve448, is deterministically generated from the prime $p = 2^{448} - 2^{224} - 1$. It is also explained how the generator (given below) for ...
2 votes
2 answers
3k views

Security of elliptic curves

How can we say an elliptic curve is secure and can be used for cryptographic applications?
1 vote
1 answer
60 views

Non-determnistic ECDSA: is there any unique common factor of all signatures of the same message by the same private key?

For non-deterministic ECDSA: Given message $m$ and private key $p$, produce a series of signatures $s_i = signature(p,m)$, $i=[1,n]$. Does there exist some function $f$ such that $j_i=f(s_i)$ and $j_1=...
4 votes
1 answer
167 views

Why such a complicated way of cofactor clearing?

I thought I understood cofactor clearing before I read this write-up which generally seems quite popular (lot of other sites link to it) - Cofactor Explained: Clearing Elliptic Curves' dirty little ...
4 votes
2 answers
132 views

How to attest simultaneous knowledge of $2$ private keys?

I'm looking for a way for a single individual to sign or otherwise provide proof of ownership of two private keys from keypairs $A$ & $B$. Simultaneous ownership is important. Alice can't do part ...
0 votes
1 answer
119 views

Exponentiation Problem of G2 in MNT curve

I made a simple python program in the Charm framework (https://github.com/JHUISI/charm): ...
1 vote
1 answer
109 views

What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?

For $c\equiv a \pmod n$, in Barrett Reduction, $\mu = \lfloor{\frac{2^{2k}}{n} \rfloor}$ is precomputed, where $k = \lceil{\log_2{n}} \rceil$ and the bitlength of $a$ is assumed to be less than $2k$. ...
1 vote
1 answer
63 views

Can someone share pseudo code for a simplest ec accumulator?

I'm searching for ways of replacing a Merkle-tree with something more space-efficient. I don't need any kind of authentication embedded - the accumulator value can be signed via a separate procedure. ...
2 votes
1 answer
152 views

kleptography SETUP attack in ecdsa

I'm trying to implement kleptography SETUP attack of ecdsa with python. Just a simply script to verify the algorithm. However i can't get the right output as the paper said. Where is the problem? Can ...
3 votes
1 answer
210 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 ...
0 votes
1 answer
43 views

Equality Check with EC Point Division using Bilinear Pairing

I'm currently trying to implement a PEKS scheme for my master's thesis and got stuck on a check I have no clue how to implement. The equation looks like this: $$ \hat{e}\left(P_1, T_3\right)\stackrel{?...
22 votes
4 answers
5k views

EC Schnorr signature: multiple standard?

I'm working on some EC-Schnorr signature code. Reading various papers on that, it seems EC-Schnorr is not standardized as well as ECDSA. For example, I found two main differences in two main actors ...
0 votes
1 answer
34 views

Trying out the small subgroup attack on a group of non-prime order using a simple additive group instead of an Elliptic Curve Group?

This is the attack I am talking about - Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? An elliptic curve group of order $8p$ where $p$ is a prime. Let $G$ be the ...
2 votes
1 answer
314 views

Authentication protocol for communication with Arduino Uno

I am using an ECDH key exchange to establish a shared secret between an Arduino Uno and an Android device. For this purpose I am using this library and more specifically Curve25519. This is the ...
1 vote
1 answer
56 views

RSA-based Double Ratchet Algorithm

I'm reading the Signal specification and they suggest to use EC keys, in particular with X25519 or X448 curves, both for the initial X3DH agreement and the DH ratchet. I've noticed that languages and ...
3 votes
1 answer
225 views

Understanding the small cofactor attack with Elliptic Curves of non-prime order

I came across 2 older answers (2 different but similar questions on the small cofactor attack) which cover this attack. https://crypto.stackexchange.com/a/12614/3941 Here the attacker replaces the $...
0 votes
1 answer
198 views

Using Microsoft SIDH library for messages signing

SIDH library looks good but lacks documentation and samples. The only signature-related code was found at http://github.com/yhyoo93/isogenysignature/blob/master/tests/kex_tests.c appeared not able to ...
0 votes
0 answers
49 views

Why g is 2 and 3 to derive the lambda and beta values for endomorphism on the secp256k1 curve?

As you can seen here, in hex, N and P are: N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F The ...
5 votes
1 answer
161 views

Will a semi-hyperelliptic pairing be used in real-world cryptography if it is faster than state-of-the-art elliptic pairings?

Let $\mathbb{G}_1$, $\mathbb{G}_2$, $\mathbb{G}_T$ stand for three groups of the same large prime order $r$. I invented a pairing $e\!: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ (with ...
2 votes
2 answers
166 views

ECCDH: direct or with temporary ECC keypairs?

I am moving from RSA to ECC for my application. Looking at these posts 1 2 3, they all suggest that Alice generates a temporary (ephemeral) ECC keypair eKP to send a message to Bob. The sessionkey sK ...
0 votes
0 answers
47 views

Check if pubkey belongs to twisted Edwards25519

I want to check if some pubkey belongs to twisted edwards25519 (I guess this is used for ed25519 ?) The problem is that I have in theory some valid pubkeys like: ...
7 votes
1 answer
421 views

Replacing Curve25519 with Ristretto255

Quoting Ristretto255 for the PHP Community, Ristretto255 is Ristretto defined over Curve25519, which allows cryptographers to extend the Ed25519 signature scheme to support complex zero-knowledge ...
1 vote
1 answer
39 views

How do I calculate number of multiplication, exponential, and pairing operations in a cryptographic algorithm (signcryption/unsigncryption)?

I have been working on signcryption scheme and its security proof. I want to compute the efficiency in terms of number of scalar multiplication operation, number of exponential operations, and number ...
1 vote
1 answer
186 views

How to know that MAC isn't modified in ECIES

I am new to ECC but I was wondering, If there is a situation where instead of the ciphertext being falsified, the sent MAC was tampered. How does the receiver verify that the ciphertext is still ...
2 votes
2 answers
66 views

How does the ECIES-AES encryption work with a key size that is not supported by AES?

I am currently studying and implementing ECC algorithms but I encountered a problem. I want to use Secp521r1 for generating a shared key and encrypting with ECIES using AES256 but AES-256 requires a ...
1 vote
0 answers
132 views

Assuming secp256k1 curve and given fixed (but random) $h$ and $d$ values, is it possible to calculate a $k$ such that $h\equiv(k\,G)_X\,(k-d)\pmod n$?

For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that: $$h\equiv(k\,G)_X\,(k-d)\pmod n$$ where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) ...
3 votes
1 answer
255 views

Are the FIPS 186-5 and ANSI X9.142-2020 definitions of ECDSA consistent?

FIPS 186-4 Digital Signature Standard defers to ANSI X9.62-2005 for the specification of ECDSA, with additional requirements set out in Chapter 6 and Appendix D. However, X9.62-2005 has since been ...
1 vote
1 answer
100 views

ECC Range proof

In ECC, the proof showing that given $G$, $x$ and $y$ is in the range $[-z,z]$ is known as the range proof. Related to: Proving that two points on elliptic curve are within range So, if: $$H=xG−yG$$ ...
0 votes
1 answer
4k views

"Probability" of an ECDSA signature

The article Elliptic Curve Digital Signature Algorithm in Bitcoin's wiki talks about signatures having probabilities (as in ...
1 vote
1 answer
88 views

Zero secret key in EC ElGamal: standards vs theory

I'm a bit confused by the standards and some replies regarding zero (the point at infinity) in elliptic curves ElGamal. TL;DR: Why do some people recommend excluding zero? It has nothing to do with ...
5 votes
1 answer
277 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 ...
2 votes
0 answers
45 views

Generating pairs of elliptic $\mathbb{F}_q$-curves isogenous over $\mathbb{F}_q$ such that nobody knows an $\mathbb{F}_q$-isogeny between them

Let $\mathbb{F}_q$ be a large finite field. What if I invent how to efficiently construct pairs of elliptic "cryptographically strong" $\mathbb{F}_q$-curves $E_1$, $E_2$ isogenous over $\...
2 votes
1 answer
73 views

Follow-up II: Number of points on an elliptic curve

Context: paper on pairing based cryptography, question 1, question 2. Let $E: y^2 = x^3+x$ be an elliptic curve over $\mathbb{F}_{q}$ where $q=3^m$ for some $m\geq 1$. Then I know that $$ \# E(\mathbb{...
2 votes
1 answer
90 views

Follow-up: Number of points on an elliptic curve

Consider this question. Say I would want to do something similar for $E_2:y^2=x^3−x+1$ over $\mathbb{F}_{3^m}$. How would I proceed?
0 votes
1 answer
59 views

Proof that user compressed public key corresponds the curve equation (secp256k1)

I am trying to check if some compressed public key corresponds to an elliptic curve equation (secp256r1). As far as I know it should be valid once the following equation is fulfill y^2 = x^3 + ax + b ...
0 votes
0 answers
23 views

Optimal frequency of modulo operation in finite field arithmetic implementation

I'm trying to implement finite field arithmetic to use it in Elliptic Curve calculations. Since all that's ever used are arithmetic operations that commute with the modulo operator, I don't see a ...
2 votes
1 answer
102 views

Composite order ECC and Ristretto

I've been looking at the Ristretto group, and its really cool. I understand that, for some protocols, we need curve points to behave as if they were from a prime order curve. I have a few questions on ...

1
2 3 4 5
38