# Tag Info

12

Simply put, elliptic curves allow you to use smaller fields. Consider Diffie-Hellman: given $p$, $g$ and $x$, you compute $g^x \mod p$. To ensure security, you must use values of $x$ and $p$ which are large enough to defeat known attacks. In practice, $x$ will need to be at least 160-bit long, while $p$ will be a 1024-bit prime. Now, the elliptic curve ...

8

The generic discrete logarithm problem is this: Given a group $(G, ·)$ with generator $g$ and $y \in G$, find $x \in \mathbb N$ such that $y = g^x$. The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e. $(\mathbb Z/p \mathbb Z)^*$: Given a ...

8

SRP needs more than a group, it requires a field. See the specification: second user sends $B = v + g^b$. This requires two operations, addition and multiplication. You cannot trivially slap that onto a group which provides only one operation, such as elliptic curves. Variants of SRP which use elliptic curves have been proposed, but do not seem to have ...

7

On a general basis, you want to keep encryption and signature keys disjoint, because they tend to have distinct life cycles. In broad terms, an encryption key should be escrowed, because loss of the private key implies loss of the data which is encrypted relatively to the public key. However, a signature key must not be escrowed, since the proof value of a ...

6

I very much suspect it's to related to the fact that $2^{521}-1$ is prime. The previous similar prime is $2^{127}-1$ and the next such is $2^{607}-1$ so they're quite rare. Elliptic curve operations on such a field can be implemented somewhat faster than over another prime field with similar size but without this special form. I doubt that very much serious ...

5

That's because you can do ECDH by exchanging only the X coordinates of your public value; as long as the shared secret depends only on the x coordinate, everything works out. Here's the fundamental property of elliptic curves that makes this work, the x coordinate of $nP$ is only a function of the x coordinate of $P$ (and $n$); it does not depend on the y ...

5

I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.) There are many ways to compute factorings and discrete logarithms where you ...

5

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other. This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same. This is arguably a pitfall in the notation: the assumption is ...

5

The first octet in a DER encoded BITSTRING is the number of unused bits (0 in this case). The remaining 65 octets are the elliptic curve point encoded as described in SEC 1 (http://www.secg.org/collateral/sec1_final.pdf) section 2.3.4. The first octet distinguishes the identity point and whether point compression is being used. Since you have 65=1+32+32 ...

4

It's the prime of the prime field. (Note that, if you're also using the curve for pairings, you'll need arithmetic over both $\mathbb{F}_p$ and $\mathbb{F}_{p^{12}}$. The first can be viewed as arithmetic modulo $p$, but the second is slightly more complex, and can be viewed as arithmetic of polynomials over $\mathbb{F}_p$, modulo a reduction polynomial.)

4

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash ...

4

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security: In the random oracle model ECIES-KEM and EC-Schnorr are jointly secure if the gap-DLP problem and gap-DH problem are both hard Ed25519 is extremely similar to EC-Schnorr, and both ECIES ...

4

Before we get to the questions, we need to understand what these attacks look like. An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$. (The equations I'm writing ...

4

Let me preface this by saying that I am not a lawyer and if you are planning on using ECC in a system you sell, you should hire a lawyer. There are a number of ECC related patents. However "in all of these cases, it is the implementation technique that is patented, not the prime or representation, and there are alternative, compatible implementation ...

3

I do not have any hard data to back this up, but an educated guess is that relaxing the cofactor to be "small" instead of 1 was done to allow Koblitz curves, which in early days looked like an attractive choice for implementation. Koblitz curves over binary fields are of the form $$y^2 + xy = x^3 + a x^2 + 1$$ The cofactor is at least $4$ when $a = 0$, ...

3

Well, the normal rules apply, i.e. $(aG + bG) = (a + b)G$, so as long as you add $a$ and $b$ correctly, everything should work fine. Note that you don't actually have to reduce the result of the addition for the point multiplication to give the same result, however your implementation may require the number to be smaller than the order. Also make sure that ...

3

I don't have David Bressoud's book, and so I can't say whether you made a mistake or he did. However, the algorithm you're using might come from the preliminary steps of Lenstra's method; however, it's missing the part that is designed to actually find the factors. In addition, as written, it can be shown (as written) to be lousy; not much better than ...

3

Depends what you mean by "validate". You should always validate any Public Key, as otherwise how do you know who owns it? If you are not sure of the owner, you are open to a man-in-the-middle attack. But I guess by validate you mean validate that the point is of the right order? You should certainly check that its on the curve (easy) and check that its not ...

3

$\def\dbl{\mathrm{dbl}}$Okay, let's give the missing step between mikeazo's and poncho's answers. I assume you've read mikeazo's answer to know how to add and double points. Now, how do we get a scalar multiple of a point? A simple algorithm is called "double-and-add", as it just does this. In a simple example, we have $5 = 4 + 1 = 2·2 + 1$, and thus ...

3

Most pairing-based cryptography (PBC) schemes are based in elliptic curve cryptography (ECC). The main function in PBC is the pairing, which is a function $e$ with two parameters, e.g. $r = e(P, Q)$. The relationship with ECC is that $P$ and $Q$ are points in elliptic curves over finite fields. The value $r$ is an element of a certain finite field (related ...

3

See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.

3

If you are restricted to Diffie-Helman, RSA, and ElGamal, I believe you cannot do pairing based cryptography which has applications to attributed based encryption and identity based encryption. These applications are not used heavily in practice, but could be in the next decade or two. For more information on speed benefits of ECC, see this question and ...

3

I haven't worked through all the (boring) details but it should be fairly easy. Just start with the normal affine addition and doubling formulae but when it comes to the stage where you do any division, don't bother and just keep track of the numerator/denominator separately. The whole point of Jacobian and other projective representations is that you don't ...

2

Elliptic Curve Cryptography (ECC) is not known to be specifically more resistant to side channel attacks (of course the next question is more resistant than what). This paper reviews power analysis side-channel attacks against ECC and countermeasures. Given that ECC uses multiplication and many common implementations of the MUL instruction run in time ...

2

It's not exactly clear what you're asking; whether how to do point addition (Mike covered that), how to do scalar point multiplication (e.g. how do you compute 9G=G+G+G+G+G+G+G+G+G) or how you can compute discrete logs (e.g. given points G and Q, find k such that kG = Q). My answer is applicable if you're asking the latter. One easy-to-understand method ...

2

Graphically, addition looks like this for two distinct points ($P+Q=R$): For doing $P+P=2P$, instead you draw a line tangent to $P$. Find where it intersects, and reflect about the $x$ axis. Like this: Mathematically this is done by finding the line tangent to $P$, finding where it intersects and reflecting about $x$. The trick is to remember to do ...

2

Montgomery and twisted Edwards curves have even order, but the group law can be implemented using fewer multiplications than Weierstrass models. So that is why these curves are popular and we have to live with cofactors > 1. There are other reasons to prefer to use prime-order elliptic curves (e.g., small subgroup attacks). So you are right that in an ...

2

About the best you can do is have a master public/private key pair where the public key is stored on your server and the private key is stored offline. When you generate a new private key, encrypt it with the master public key and store that in the database. That way, if a password is ever lost, you can recover the user's private key by using the master ...

2

It becomes clear once you understand what $p-1$ and ECM are doing. I'll start with $p-1$, since it is simpler. Suppose the number you want to factor, $n$, is the product of two primes: $p$ and $q$. If we knew $p-1$, we could get $p$ from $n$ by doing $$\gcd(a^{p-1} - 1 \bmod n, n) = p.$$ This works because by working modulo $n$, we're working "in ...

2

Let's take your latter example. We will use the Weil pairing here, since that was the original MOV approach. Let's pick some arbitrary points in your curve: $$\begin{eqnarray} P &=& (6116 : 2715) \\ Q &=& (3034 : 462) \end{eqnarray}$$ From now on, we'll actually work in an extension field of $\mathbb{F}_{8111}$, namely ...

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