# Tag Info

25

I wouldn't try to explain the mathematics of the backdoor. Just explain that the NSA hid a secret backdoor in there. Instead, I would suggest focusing on the history and the context. For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers. You could explain how random number generators are a ...

23

Edit: I have made some tests and I found something weird. See at the end. Initial answer: At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent: Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several ...

16

Here is a list of products and companies who have had their EC DRBG algorithm validated by NIST. http://csrc.nist.gov/groups/STM/cavp/documents/drbg/drbgval.html The validation lists all modes that have been validated, so you can see which ones have gone to the effort of having their implementation of Dual_EC_DRBG validated. Tim Dierks points out that, for ...

16

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

14

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

14

Frankly, I'd be surprised if anyone did use it. Even before the potential backdoor was discovered back in 2007, the Dual_EC_DRBG was known to be much slower and slightly more biased than all the other random number generators in NIST SP 800-90. To quote Bruce Schneier: "If this story leaves you confused, join the club. I don't understand why the NSA ...

13

(That Tor mailing list link appears to be broken at the moment) Your question is at least partially answered in FIPS 186-3 itself… Appendix A describes how to start with a seed and use an iterative process involving SHA-1 until a valid elliptic curve is found. Appendix D contains the NIST recommended curves and includes the seed used to generate each one ...

12

RSA BSAFE Libraries (Both for Java and C/C++) use it as their default PRNG. Java: http://developer-content.emc.com/docs/rsashare/share_for_java/1.1/dev_guide/group__LEARNJSSE__RANDOM__ALGORITHM.html C/C++: https://community.emc.com/servlet/JiveServlet/previewBody/4950-102-2-17171/Share-C_1.1_rel_notes.pdf This obviously impacts users of the library such ...

11

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using. This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, ...

9

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

8

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

8

As of 9 Sep. 2013, the NIST recommendation is that Dual_EC_DRBG SHOULD NOT be used. Quoting from the link: Recommending against the use of SP 800-90A Dual Elliptic Curve Deterministic Random Bit Generation: NIST strongly recommends that, pending the resolution of the security concerns and the re-issuance of SP 800-90A, the Dual_EC_DRBG, as specified in ...

7

Joux's work is really summarized by this answer already on Crypto.SE. He discovered a way to generalize Diffie-Hellman to multiple (more than 2) parties. In particular though, he presented a single round protocol for key establishment between 3 parties. Something that until then was thought to be impossible. Boneh and Franklin developed the first fully ...

7

It is true that elliptic curves allow the same security with smaller key sizes. However, the size is not the only important aspect. Familiarity of algorithm, ease of implementation, performance, how many independent implementations exist, etc. affect how widely algorithm is implemented. For Elliptic Curves, like many other technologies one factor slowing ...

7

Your answer is in the paper Elliptic curve cryptosystems from Neal Koblitz: Set up an elliptic curve $E$ over a field $\mathbb{F}_q$ and a point $P$ just the same as for EC-DDH as system parameters. You need a public known function $f(m) \rightarrow P_m$, which maps messages $m$ to points $P_m$ in $E$. It should be invertible, and one way is to use $m$ in ...

7

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

6

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

6

It has to be this way. First, if it was deterministic, you could trivially break the encryption. Say the encrypted message was a response to "which candidate for President do you vote for". An attacker would simply need to encrypt each candidate's name and see the response that matched the encrypted data. Second, if it was the same length as the encrypted ...

6

If the NSA knew a sufficiently large weak class of elliptic curves, it is possible for them to have chosen weak curves and have them standardized. As far as I can tell, there is no hint about any sufficiently large class of curves being weak. Regarding choosing the curves: It would have been better if NIST had used an "obvious" string as the seed, e.g. ...

6

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now. Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime ...

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

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

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\}\}$.

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

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 assumption: $E(F_q) \simeq Z_s \times Z_t$ is always true!! (see Handbook of Elliptic and HyperElliptic Curve Cryptography) It is never said that coordinates of points lie on $Z_s \times Z_t$ which has no sense except if $s=t$. But the isomorphism is not trivial to compute (it is in fact hard to compute, since it is related to the discrete ...

5

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

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

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

4

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

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