Tag Info

Hot answers tagged

18

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...


16

Curve25519 was designed to take advantage of the Montgomery ladder, which combined with Montgomery curves forgoes the $Y$ coordinates, is side-channel resistant, and enables public keys to be any 255-bit string. The ladder looks something like this (pseudocode): Q[0] = P; Q[1] = 2*P; for(int i = log2(exponent) - 2; i >= 0; --i) { Q[ bit(exponent, i)] ...


13

I'd say that the whole argument hinges around a "secret attack" that possibly the NSA may know of, enabling them to break some instances of elliptic curves that the rest of the World considers as safe, because the secret attack is, well, secret. This yields to the only possible answer to your question: since secret attacks are secret, they are not known to ...


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

You are correct that a line through a single point can intersect the curve in many other points. But you don't choose just any line. You choose the tangent through $A$. And that line will intersect the curve in exactly one point (which usually isn't, but may actually be $A$). It is an interesting and useful exercise to actually do these computations with ...


7

ElGamal appears to be used instead of Diffie-Hellman (or IES) in OpenPGP mostly because when that format was put together, there were some unresolved intellectual property issues surrounding both RSA and Diffie-Hellman, while ElGamal was unproblematic. This trend for ElGamal seems to stick around, mostly by force of habit, e.g. when switching to ...


7

ECDSA is a digial signature algorithm ECIES is an Intergrated Encryption scheme ECDH is a key secure key exchange algorithm. First you should understand what are the purpose of these algorithms. Digital signature algorithms are used to authenticate a digital content.A valid digital signature gives a recipient reason to believe that the message was created ...


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


6

The inverse of a point $P = (x_P,y_P)$ is its reflexion across the $x$-axis : $P' = (x_P,-y_P)$. If you want to compute $Q-P$, just replace $y_P$ by $-y_P$ in the usual formula for point addition.


6

The attack which you link to, on ECDSA, is related to the following: the signer computes several values $kG$, for random $k$ values chosen uniformly modulo $n$ ($n$ is the size of the subgroup generated by $G$). One such value is generated for each signature. It is important that the selection is uniform: even small biases can be exploited in order to make a ...


6

It's probably best to understand Lenstra's Elliptic Curve factorization algorithm by way of contrast with its predecessors, the Pollard's p-1 method, the Williams' p+1 method and the Cyclotomic Polynomial method of Bach and Shallit. These are all Algebraic-group factorisation algorithms which require you to select a stage 1 bound $B_1$ and stage 2 bound ...


6

Did you take a look at DjB's paper? One of his design criterias in order to improve performance is "Use a fixed position for the leading 1 in the secret key". The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$.


6

An elliptic curve whose polynomial has repeated roots is not in fact an elliptic curve, but a singular cubic curve, as it has a singular point where the group law breaks down. Still, we can remove those broken points and treat the remaining ones as a group. There are 3 possible cases: $y^2 = x^3 \bmod p$. This curve has a triple root, and is isomorphic to ...


6

For what it's worth, the OpenSSL developers have committed changes that improve this. I assume they will be in OpenSSL 1.0.2, but I don't know for sure. In any case, if you clone the git repo and compile the OpenSSL_1_0_2-stable branch (or master, I suppose), s_client will display the curve name: $ OPENSSL_CONF=apps/openssl.cnf apps/openssl s_client -CApath ...


6

This has been basically asked already: Should we trust the NIST recommended ECC parameters? History Once it was found that NSA allegedly had inserted backdoor to a cryptographic standard, people started thinking what standard it was. The most common guess is that the Dual EC DRBG is the backdoored standard. However, some amount of (possibly justified) ...


6

It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get. The definition is rather mind-twisting: You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a ...


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

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

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

Elliptic curves have a number of nice features that make them good for cryptography. One could write a whole book on the topic (as some have), so I'll highlight a few points. The points on an elliptic curve over a finite field forms a group. The same is not true for the ideas you mentioned. Discrete log on many of these EC groups is hard. In fact, there ...


5

You can make OpenSSL print out the handshake messages with the -msg parameter: openssl s_client -msg -connect myserver.net:443 Then look for the ServerKeyExchange message. Here is an example: <<< TLS 1.2 Handshake [length 014d], ServerKeyExchange 0c 00 01 49 03 00 17 41 04 6b d8 6e 14 1c 9b 12 4d 58 29 20 e8 e2 1a 24 0d da 8f 38 1a 5d 85 ...


5

What the authors of the paper cited by you certainly mean by secure is "treat the hash function to $G_2$ as a random oracle". The problem is that hashing to $G_2$ can only be realized by taking some point in the group and multiplying it with a scalar (which is for instance the output of a full domain hash mapping to integers in $Z_{ord(G_2)}^*$). See for ...


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 implications are that someone screwed up some calculation. By Lagrange's theorem, the co-factor must be an integer.


5

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


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



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