9

The general rule for curves is given in; 2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone They defined a point is valid if $P \neq \mathcal{O}$ The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field. $P$ satisfies the curve equation - against the twist ...


6

Regarding the [B] and [C] parts of the question per the comments: I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most ...


5

Do your experiments count points at infinity? When $d$ is a quadratic nonresidue over $\mathbb{F}$, the curve $y^2 + x^2 = 1 + d x^2 y^2$ has no points at infinity over $\mathbb{F}$. But if $-1$ is also a quadratic nonresidue, then the curve $y^2 - x^2 = 1 - d x^2 y^2$ has two of them, roughly of the form $(\pm\sqrt{-1/d}, \infty)$.


5

We want $(r,s)$ same for two different set of $d,k,h$ In ECDSA $r = x_0([k]G) \bmod n$ where $k \in [1,n-1]$ and $x_o$ is the x-coordinate of the scalar multiplication $[k]G$ $s = k^{-1}\cdot (h+r\cdot d)$ where $h$ is the left most bits of $h$ to fit in the group order ( for simplicity we called it $h$ again). Now we want same $(r,s)$ for $d,k,h$ and $d',...


5

Is it possible for Carol to find Bobs key in $S_{pks}$ This is a decisional Diffie-Hellman problem. We can summary this problem as: "we're given the values $G, aG, abG$, and a series of values $c_1G, c_2G, ... c_nG$, can we recognize $c_iG = bG$" We can reword the problem as "assuming $H = aG$, we're given the values $H, (a^{-1})H, bH$, can ...


4

For a given private key $d$, random $k$ and message hash $h$: is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same ECDSA signature using the $\text{secp256k1}$ curve? Yes, and further it's easy to explicitly compute an alternate $(d',k',h')$ that matches all reasonable meanings of "different set of $d$, $k$ and $...


3

The affine addition formula for short Weierstrass curves is usually given by $$ \begin{align} \lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\ x_3 &= \lambda^2 - x_1 - x_2 \\ y_3 &= \lambda(x_1 - x_3) - y_1 \\ \end{align}. $$ This gives us 1 inversion, 2 multiplications, 1 squaring, and a few field additions. The trick here, when adding many points in ...


3

There is obviously missing information on both lecture projects. With a small try, I've found a curve with the required order. If you set the field as the prime field $F_P$ where $p=9254331510119$, the curve $$E(F_p) : y^2 = x^3 + 7x + 1$$ p = 9254331510119 E = EllipticCurve(GF(p), [7,1]) print(E.order().factor()) outputs $$9254332285624 = 2^3 \cdot 19 \...


3

I saw multiple software implementations with multiple results such that, $[0]G=0$ or $[0]G=G$. As stated in the comments, we define $[0]G = 0$, anything else is incorrect I thought I'd outline why we define things we did. What we want is to have $[a+b]G = [a]G + [b]G$ be true for all integers $a, b$, and all points $G$. If it is true for all integers $b$, ...


2

Although it is not forward secure against client-side compromise (i.e. disclosure of the user agent's long term private key), it is forward secure against server-side compromise (i.e. disclosure of all information available to the server). Thus, for example, if ownership of the application server is transferred from one company to another and the user's ...


2

Answering on the subquestion: Why $|E_d|+|E'_d|=2\cdot p+2$ ? It follows from the definition of quadratic twist. In fact, let's consider all possible $\tilde{x}$ coordinates for points, that is all the values in $\mathbb{F_p}$, and an elliptic curve $E$ with equation $y^2=x^3+ax+b$, then: Case $\tilde{x}^3+a\tilde{x}+b\neq0$: So either $\tilde{x}^3+a\tilde{...


2

It is totally possible and fairly easy to see without any advanced maths. The curve has order n (n Points in the curve) the private key d is [0... n-1] and the random number k [1... n-1] and there are 2^256 possible values for h. So there are n*(n-1)*2^256 possible inputs (d, k, h combinations). The output is r, s. Where r is there x part of a point so there ...


1

Let $E$ be an elliptic curve over a finite field $K$ with an order $n$ such that $n =p_1^{a_1}\dots p_k^{a_k}$. The order is the number of rational points of the curve. There are various point for a curve to be secure; Discrete logarithm The basic security of ECC is the Dlog that is given a base point $G$ and another point $P$ with $P= [x]G$ There are many ...


1

No, this is not equivalent. To see why, take the example with $ℓ_A = 2$ and $e_A = 2$, then the torsion group is isomorphic to the additive group $ℤ/4ℤ × ℤ/4ℤ$. Set $P=(1,3)$ and $Q=(1,1)$, then neither is a multiple of the other, however they do not generate the whole group because $2P = 2Q$, and indeed there is no way to write $(1,0)$ (and many other ...


1

As you mentioned, computing the discrete logarithm is an easy way to check for linear dependency. The usual way to compute discrete logs over elliptic curves relies on some pairing, but there are ways to do so without any pairing. See for instance "Isogeny-based key compression without pairings" at PKC'21 (https://eprint.iacr.org/2021/272.pdf), ...


1

If you read all of the RF 8032 you will see that there is a compression (endcodings) of the points. def point_compress(P): zinv = modp_inv(P[2]) x = P[0] * zinv % p y = P[1] * zinv % p return int.to_bytes(y | ((x & 1) << 255), 32, "little") Compression just stores the sign and restores it back with this information def ...


1

Similarly, just send the identity element $\mathcal{O}$ as the public key. Alice must be a fool to not validate the public key to fall into this trap. The first rule is to check that $P \neq \mathcal{O}$ Update per user's comment How can i find the identity element of curve 25519? The identity of some curves like Curve25519 is the point of infinity ( ...


Only top voted, non community-wiki answers of a minimum length are eligible