Tag Info

Hot answers tagged

12

Let's assume that everyone agreed on some elliptic curve and a public base point $g$ somewhere on the curve. When two parties Alice and Bob want to agree on a shared secret, they proceed as follows: Alice chooses some random number $a$ and applies the curve operation to $g$, the public base point, $a$ times. She obtains some result ...


8

The idea of "safe curve" is somewhat overrated. What you really want is a safe implementation which won't leak secret information when employed in some practical context. Leakage may occur in a variety of ways; some examples include timing attacks and implementation behaviour when encountering anomalous input. This is not an exhaustive list, and, depending ...


7

It happens that a line usually (not always) cuts three points in a elliptic curve by the Bezout theorem. This is the case for the points and the curve you are asking for. So the sum of two points are defined like the inverse of the third point intercepted by the line that cut $P$ and $Q$ (let's name it $R$). So we need to find $-R$ because $P+Q=-R$ by ...


7

The tangent line at point $P(x_1,y_1)$ is: $\frac{\partial f}{\partial x}(x-x_1)+\frac{\partial f}{\partial y}(y-y_1)$ Solving differentials, we obtain: $\frac{\partial f}{\partial x}=3x^2+2x$ $\frac{\partial f}{\partial y}=-2y-1$ For $x_1=0$ and $y_1=0$ we have: $\frac{\partial f}{\partial x}=3x^2+2x = 0$ $\frac{\partial f}{\partial y}=-2y-1 = -1$ ...


7

There are actually only 5 unique $x$-coordinates one needs to be concerned about: $(0, \ldots)$ $(1, \ldots)$ $(-1, \ldots)$ $(x_1, \ldots)$ $(x_2, \ldots)$, where $$\begin{eqnarray} x_1 =& 393823572354896145817230607815530211125 \\ & 29911719440698176882885853963445705823 \end{eqnarray} $$ and $$\begin{eqnarray} x_2 =& ...


7

Actually, it is not possible to uniquely recover the public key from an ECDSA signature $(r,s)$. This remains true even if we also assume you know the curve, the hash function used, and you also have the message that was signed. However, with the signature and the message that was signed, and the knowledge of the curve, it is possible to generate two ...


6

CodesInChaos has it correct, however since you're just learning, I think I'll lay it out rather explicitly. When we have an abstract group, there are two ways of expressing operations in the group. One way is writing the operation as if it were the multiplication operation, for example, if we apply the operation to elements $A$ and $B$ and the result is ...


6

BouncyCastle has a really bad ECC implementation. It uses affine coordinates which incur a huge performance hit (factor 20 or so) since it computes a field inversion after every single step. Good implementations use Jacobi coordinates (or a similar approach) where denominators are kept and there is only one field inversion at the end. It's also potentially ...


6

Over large characteristic fields, I am not aware of any "point generation method" that can be computed faster than a base field exponentiation, and I would be very surprised if such a thing existed even if you do not require constant running time. So your best bet in general is probably Icart's function (I'd pick that one over Elligator if I didn't need ...


6

I don't know about computing things in parallel, so I will ignore that part of the question. First, please note that the encryption algorithm is rarely the the weak point of the security. It is far more likely that you will have problems with the implementation, some spyware installed on your computer, a weak password (If you use qwerty as your password, ...


5

The implications are that someone screwed up some calculation. By Lagrange's theorem, the co-factor must be an integer.


5

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in ...


5

It mainly depends on how the algorithm was selected. If it was selected by a public competition like for AES, then it is likely to be secure. If it was forced in by the NSA such as Dual-EC random number generator, then you may have some doubts. Other questions you may want to ask yourself are: Is this an "original" algorithm or was the problem that it ...


5

Your second equation seems a bit off. In the curve of equation: $$ y^2 + cy = x^3 + ax + b $$ in a binary field $\mathbb{F}_{2^m}$, to add point $P_1 = (x_1,y_1)$ to point $P_2 = (x_2,y_2)$, resulting in point $P_3 = (x_3,y_3)$, then the two equations are: \begin{eqnarray*} x_3 &=& \lambda^2 + x_1 + x_2\\ y_3 &=& \lambda (x_1+x_3) + y_1 + c ...


5

The problem doesn't lie with curves in Weierstrass form necessarily, but with naive implementations of elliptic curve arithmetic on such curves. Basically, if you implement an ECC scheme (ECDH, ECDSA or whatever) on a smart card using a curve in Weierstrass form in the most straightforward way possible (by writing a simple double-and-add loop for ...


5

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations. The good news is that, sticking to affine coordinates, you can avoid most of the cost of the ...


5

SafeCurves lists some ways to compare the security of elliptic curves. Their security criteria are split to "ECDLP security" and "ECC security". Failing the former basically means "there is no way to use this curve securely in general" while the latter "it is difficult to implement this curve securely". None of the (few) BouncyCastle-supported curves that ...


5

Now to calculate Q this will take a lot of time since it means I will need to perform point addition an insane number of times unless I'm not understanding something about it. You're missing a point; elliptic curve point addition is associative; that is, for any three points $A, B, C$, we have: $$(A + B) + C = A + (B+C)$$ Now, why is this a big deal? ...


4

Given a EC public key, can a different, but plausible and functional private key be derived to match the public key? No, a public key will correspond to only one private key (with one minor exception, which I will explain below). With Elliptic Curve systems, the private key is an integer $d$ between 1 and $q$ (the order the generator point $G$), and ...


4

Trevor Perrin wrote a library doing exactly that. Explanation can be found on in the curves mailing list archives. To convert a Curve25519 public key $x_C$ into an Ed25519 public key $y_E$, with a Ed25519 sign bit of $0$: $$y_E = \frac{x_C - 1}{x_C + 1} \mod 2^{255}-19$$ The Ed25519 private key may need to be adjusted to match the sign bit of $0$: if ...


4

You are using the wrong value as the modulus; you ought to be using the value $r$ (which is also listed in the document). $p$ is the characteristic of the field that the elliptic curve you're using is defined on. In this case, we're not interested in that; instead what we're interested in is the order of the curve, that is, that value $r$ such that $rP = ...


4

The curve equation $Y^2=X^3+AX+B$ is traditional because it greatly simplifies a lot of theory. I like to use it for teaching. But all of these curve equations are in a sense equivalent, and for any smooth cubic curve, you can usually find an isomorphic curve of desired form. However, a long time ago, people realized that different curve equations have ...


4

The number of points on the curve $|E({\mathbb F}_p)|$ is defined as $|E({\mathbb F}_p)|=p+1-t$ where $t$ is the so called trace of Frobenius. Using Hasse's theorem one can bound $t$ as $|t| \leq 2\sqrt p$, which gives you an estimation for the number of points for $E({\mathbb F}_p)$. Now you could use a naive algorithm and simply run through all elements ...


4

Type-1 (symmetric pairings) are dead for curves over fields of small characteristic. Over prime fields of large prime characteristic they are not really dead, but as they only offer small embedding degrees ($k=2$), they are not really attractive from a performance point of view. You have to choose very large curves (which makes the curve arithmetic slow) ...


4

Designing such signature schemes from scratch without having strong experience is very likely to fail and very dangerous (see the tons of bad papers out there being accepted to "dubious" conferences and journals). Your proposed scheme Your verification relation is to check if: $sP - Q + R \stackrel{?}{=} zP + mP$ where $Q$ is the public key of the signer ...


4

Yes. There are several different kinds of twist attacks. Curve25519 is safe against all the ones SafeCurves looks at. Specifically, the cost of a combined attack is $2^{124.3}$, which is considered safe.


4

Actually, strictly speaking, the $x$ and $y$ values on an elliptic curve point aren't integers; instead, they are field elements. That is, the elliptic curve is defined in a field, which is a group of elements with addition and multiplication operations defined on them (along with a group of identities); the $x$ and $y$ values are members from these ...


4

A curve with cofactor 1, like all Brainpool curves, cannot possibly satisfy the SafeCurves criteria, so the answer to your question is no. Whether that means that they are actually "unsafe" for use in practice is debatable. I think it would be fair to say that implementing such curves in a secure way is perfectly doable in practice, but it's trickier to do ...


4

Both curves have similar form and primes close to powers of two ($2^{192}-2^{64}-1$ and $2^{224} - 2^{96} + 1$), so you wouldn't expect large differences in performance – all things equal, P-224 might be anywhere from 30% to 60% slower due to the computational scaling of curve operations. However, in practice different implementations will have different ...


4

What's difference between n & #E(FP)? The difference is that $n$ is the smallest positive integer where $nG = O$; while you correctly state that $\#E \cdot G = O$, that doesn't mean that $\#E$ is the smallest integer that makes this happen. There may be a smaller integer $n$; $n$ will always be a factor of $\#E$, however it can be smaller. As for ...



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