# Questions tagged as ['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.
Score: 1
computation time of pairing operations and their securities

Suppose G1 is an elliptic group and G2 be a multiplicative group and they are of same prime order p and e is a bilinear pairing, e: G1 X G1 -> G2. The operations e(p,q)r and e(pr,q) gives equal result where p, q $$\in$$ G1 and r $$\in$$ Z*p.

The computation time of different cryptographic operations are given below source:

...
Operation Computation time (in ms)
Scalar multiplication in G1 0.24
Score: 2
Short Nonces in ECDSA signature generation

Recently I noticed that my device generates short-sized Nonces.

Approximately $$2 ^ {243} - 2^{244}$$.

Could it turn out that there will be a small leak of information about the first 3 bits of Nonces?

Accordingly, if Nonces is short, then it must contain null at the beginning. That is, the first 3 bits of Nonces contain null at the beginning.

Hence, for the sake of safety:

When creating an ECDSA signatur ...

Score: 1
Convert secp256k1 private key to sr25519 private key

Is it possible to convert secp256k1 private key to valid sr25519 key?

Score: 0
Two Elliptic Curve Points having the Same X coordinate

Suppose in a elliptic curve (say the curve equation is: $$y^2 = x^3 -17$$) with prime order $$q$$, we have $$(x,y_1) = nP$$, where $$P$$ is a generator and $$n<\lceil{q/2}\rceil$$. Can we claim that there does not exist $$n' < \lceil{q/2}\rceil$$, such that $$(x,y_2)=n'P$$ is a valid curve point where $$y_2 \neq y_1$$?

Score: 1
Birational transformation from Edwards curve with not square d to Edwards curve with square d

How can I transform a complete twisted Edwards curve $$ax^2+y^2 = 1+dx^2y^2$$ with not square $$d$$ and square $$a$$ into an isomorphic Edwards curve $$X^2+Y^2 = 1+DX^2Y^2$$ with a square $$-D$$ i.e. $$D = -r^2$$?

I tried to set $$X = \frac{x}{\sqrt{a}}; Y=y$$, but $$-\frac{d}{a}$$ is also a non square (at least for Edwards25519). This answer is not working as well (i.e. $$-1/d$$ is not a square), because $$-1$$ is squ ...

Score: 0
Is it possible (and if so how) to make one proof for multiple private keys in ECDSA

Lets say I have a message that needs to be signed by two keys that were generated using ECDSA

Is it possible to make a signature that accounts for both keys, meaning I can verify with both and see they are valid?

An example, if we need a cryptocurrency example:

Both inputs are in the transaction, and now need to be signed. Is it possible to make it so only one ...

Score: 2
ElGamal with elliptic curves and semantic security

To encrypt a group element $$P$$ with public key $$K$$ and randomness $$r$$ using ElGamal on elliptic curves with base point $$G$$ we do the following $$(c_1, c_2) = (r\cdot G; P+r\cdot K)$$.

When we want to encrypt a free-form message $$m$$, we have to convert it to a group element $$P$$ first. For that, we can either use scalar multiplication $$P=m\cdot G$$ (additively homomorphic) or map the message $$P = map(m) ...$$

Score: 1
Are there any public keys for which the private key can be easily derived (ECDSA)?

I know that generally it's infeasible to find the private for any given public key. But I also came across the question "Find ECDSA PrivKey to PubKey = 0", in which it was explained that the private key for a public key 0x0000...0000 can be easily derived.

From the answer to that question it appears that public key 0x0000...0000 is the only public key for which this is the case, but haven't understoo ...

Score: 0
Can I know from a Bitcoin public key if the private key is odd or even?

Can I know just from a Bitcoin public key if the private key is odd or even?

[moderator note] That is, can we find parity of the private key from a secp256k1 public key?
For the original dump of digits, see here.

Score: 1
running Project Wycheproof against crypto implementations in languages other than Java

So I guess https://github.com/google/wycheproof "tests crypto libraries against known attacks". It appears to mainly be intended for Java crypto providers but can it easily be adapted to be used for other languages?

For non timing attacks you could probably just loop through the *.json files in the testvectors directory but it's not clear to me what some of the data in there means.

Consider ecdh_sec ...

Score: 3
What is/was SEC#1 ECC public key leading octet 0x01 for?

In the SEC#1 elliptic curve cryptography standard, the encoding of the public key involve a leading octet:

• 00h: The public key is the point at infinity.
• 02h, 03h: The public key is the compressed point.
• 04h: The public key contain both x and y coordinates.

What is (or was) the value 01h for? Had there been other values defined for ECC?

Score: 0
Why does ECDSA produce a pair of values in its' signature (r,s)?

I was wondering why ecdsa generates a signature in form of a pair (r and s) and why it can't be only one value.

Score: 1
What is the difference between "Elliptic Curve Function" and "Hash Functions" like SHA256?

I am reading about bitcoin and I am a little confused about "elliptic curve function" and "SHA256". Do they have the same properties? Can both be used to generate private and public key pairs?

Score: 1
Multiuser encryption, singleuser decryption

I have an hybrid encryption (RSA, AES) for a file sharing project I am working on, where I use a single public key for encryption on the sender side and corresponding private key for decryption on the recipient side. I would like for a sender to be able to send files to multiple users each having only their own unique key pair (public keys would be distributed).

I know this is possible using GPG

Score: 1
ECDSA - generating a new private key each time we sign?

So, I kinda get the mathematics behind the ECDSA, but I can't seem to find precise information about private key generation. In other words, do we have to generate private key, each time we generate a signature? Coz, if a public key is known, then through using the discrete logarithm we can get the private key, and thus we have a problem.

Score: 2
Size of group elements in a bilinear context

In a asymetric pairing context, which size (in bits) should have the elements of $$\mathbb{G}_1,\mathbb{G}_2$$ and $$\mathbb{G}_T$$ if we consider the most efficient elliptic curves?

Score: 1
What is the meaning of $F_{p^k}$ and the elliptic curve over it, $E(F_{p^k})$?

In pairing based cryptography, there will be the finite field $$F_{p^k}$$ where $$p$$ is prime number and $$k$$ is an integer. The elliptic curve is constructed on that finite field as $$E(F_{p^k})$$.

For example, let $$E$$ be an elliptic curve $$Y^2 = X^3 + aX + b$$ over $$F_{q^k}$$. What is the meaning of $$F_{q^k}$$ here? I only understand prime fields ($$F_q$$ where q is a prime number).

Score: 1
Isomorphic mapping of BLS12-381 G2 points to G1

I'm attempting to reproduce ring signatures as described in Section 5 of https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf but applied to the BLS12-381 system.

One of the assumptions in their construction is that an isomorphism ψ: G2 → G1 exists, with ψ(g2) = g1

There's a hint that we may be able to use a trace map as this isomorphism:

Now I've found the definition of trace maps in Pairi ...

Score: 2
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 anyone help?

from ecpy.curves import Curve, Point
import hashlib
import gmpy

cv = Curve.get_curve('secp256k1')
G = Point(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
0x48 ...
Score: 0
Is it possible to give a definition for point multiplication on elliptic curve?

As we know that at least in cryptography, the group operation on elliptic curve is just the point addition(https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication), which is defined on $$E:y^{2}=x^{3}+a x+b$$ as: $$\left(x_{p}, y_{p}\right)+\left(x_{q}, y_{q}\right)=\left(x_{r}, y_{r}\right)$$, $$\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}}$$, $$x_{r}=\lambda^{2}-x_{p}-x_{q}$$, $$y_{r}=\lambda\left(x_{ ...$$

Score: 1
Why does point addition work on EC curves?

This may be more of a math question but I cannot find an intuitive answer.

On an EC curve why is 2P+2P equal to P+P+P+P?

The addition operation seems to a layman as some arbitrary sequence of steps. Draw a line here, flip the y coordinate, and so on. And yet point doubling twice brings up the same point. How is this so? (how is it that point addition is associative)

Score: 0
Notation question: Dividing 2 Elliptic Curve Points producing a third point

I'm working my way through some papers and ran across what seems to be division of two points that produce a third point. I'm new to ECC and am having a terrible time trying to figure out what this notation means, any thoughts?

This is from the BLS paper: https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf

Point division appears on pages

• 6 (A potential attack on aggregate signatures)
• 18 (Ring Si ...
Score: 5
How to decide if a point on a elliptic curve belongs to a group generated by a generator g?

In the elliptic curve encryption scheme, there is a cyclic group generated by a base point $$G$$ on the elliptic curve.

Given a random point on the elliptic curve, is there a way to decide if the random point is in the group or not?

Score: 0
How to decompose a public key into subgroups EC?

Is it possible to decompose the public key into its own subgroups? Suppose we know the order P with which the public key was generated (Qx, Qy)

How can the public key (Qx, Qy) be decomposed into subgroups of small orders?

I saw in SageMath it is possible to work with Elliptic Curves

M = EllipticCurve (GF (p), [0.7])


I am just getting familiar with SageMath and am having a hard time working on creating a  ...

Score: 2
What is the quadratic character of the field over which elliptic curve is defined?

I'm trying to understand the injective encoding of a message to an elliptic curve point (from this paper).

However, I'm not sure what do they mean by the quadratic character of the field. Do you know what does it mean and how to compute it? Is it somewhat similar to the Jacobi symbol?

Score: 0
How to get a common coordinate from two different coordinates on Elliptic Curves?

I am trying to write a SageMath script that multiplies two coordinates on Elliptic Curves into one common coordinate.

SageMath Elliptic curves over finite fields documentation

p = Number

M1 = EllipticCurve (GF (p), [0,7])

C1 = M1 ([x1, y1])
C2 = M1 ([x2, y2])
C3 = C1 * C2


Somewhere they wrote that using sets of the SageMath function it is possible to do this. How to do it?

Score: 2
How to find out what the order of the base point of the elliptic curve is?

I wanted to use https://github.com/AntonKueltz/fastecdsa library and the function parameters for creating curve are:

p,  # (long): The value of p in the curve equation.
a,  # (long): The value of a in the curve equation.
b,  # (long): The value of b in the curve equation.
q,  # (long): The order of the base point of the curve.
gx,  # (long): The x coordinate of the base point of the curve.
gy,  # (lon ...
Score: 2
How to have a hash function that maps from a group element to a binary string of a certain size in charm-crypto?

I am facing a problem in programming with the charm-crypto library. The hash functions for pairing group elements in charm-crypto can only map from a string to a specific field: $$\mathbb Z_r$$, $$G_1$$ or $$G_2$$.

Examples: \begin{align} H_1: \{0, 1\}^*\to\ &G_1\\ H_2: \{0, 1\}^*\to\ &Z_r\\ H_3: \{0, 1\}^*\to\ &G_2\\ \end{align}

I am implementing a certificateless public key encryption  ...

Score: 2
How can we link AES with Elliptic Curve Diffie-Hellman Key Exchange Method

Actually, I am working on a project to combine symmetric and asymmetric cryptographic algorithms.

The shared secret key for AES will be generated through the Elliptic Curve Diffie Hellman Key Exchange (ECDH) Method. I have one question that ECDH will generate a shared secret key of 256 bit or more length key. For AES-128 I need a secret key of 128 bit but ECDH is not generating the 128-bit key.

So h ...