Tag Info

Hot answers tagged

14

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 ...


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

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

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 ...


7

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem): Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$. Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. ...


7

These are "red flags". No one knows of a specific exploit, only some possible reasons to be concerned that one might exist. Since no one knows of a specific attack, we can't possibly know how much speedup such a hypothetical attack might allow. Basically, you're asking for speculation where there is not enough information to allow meaningful speculation, ...


7

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...


6

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 ...


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, ...


6

In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ...


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

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 ...


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

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

The main difference is that secp256r1 is a prime field curve, while secp256k1 is a Koblitz curve. Koblitz curves are known to be a few bits weaker than prime field curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough. The other difference is how the parameters have been chosen. In secp256r1 ...


5

The real question isn't "Why doesn't Suite B use P-521?" It is, "Why doesn't Suite B use AES-192?" NSA were only interested in 192-bit security for Suite B, but they chose to use AES-256 because AES-192 wasn't widely supported. "In fact we had wanted to use AES -128 and AES-192, but a quick survey of AES implementations (hardware centric, I believe) ...


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? ...


5

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up ...


5

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous). Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in ...


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

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 ...


4

In the usual definition of security of Elliptic Curves, curve25519 security is in fact 126 bits. If look at safecurves's rho page you can see the rho complexity for curve25519 is $2^{125.8}$ in accordance to what you say. Curve25519 author basically doesn't accept that definition of security. In the Curve25519 paper he states in section 1: Every known ...


4

After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and ...


4

Such an operation is possible. The ways of calculating that appear to be different for each curve.


3

From a mathematical point of view this is not possible. I would say almost by definition because the point at infinity does not lie in the affine part. To be more precise: Let $\mathbb P^2$ is the two dimensional projective space with coordinates $(x:y:z)$ and $\mathbb A^2 \subset \mathbb P^2$ the affine part where $z \neq 0$ then one can see $X = x/z$ and ...



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