# Tag Info

61

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, ...

39

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

35

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

21

This is mostly a supplement to @ThomasPornin's answer, not a complete answer on its own (but too long to fit in a comment). ECC uses a finite field, so even though elliptical curves themselves are relatively new, most of the math involved in taking a discrete logarithm over the field is much older. In fact, most of the algorithms used are relatively minor ...

21

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

20

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

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

17

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be ...

17

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

17

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

16

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics: Group elements must be representable with relatively little memory. The group size must be known and be a ...

16

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 \mapsto P_m$, which maps messages $m$ to points $P_m$ on $E$. It should be invertible, and one way is to use $m$ in ...

16

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

16

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

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

First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves. RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table: for Transport Layer Security (TLS) Symmetric | ECC ...

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

12

Here are five test vectors for secp256k1, which I just generated with my own code. My code is a generic implementation of elliptic curves; it has been tested for many curves for which test vectors were available (in particular the NIST curves) so I tend to believe that it is correct. Each test vector is a value $m$ (chosen randomly modulo the curve order ...

12

Most cryptosystems based on elliptic curves can be broken if you can solve the discrete logarithm problem, that is, given the point $P$ and $rP$, find the integer $r$. The MOV attack uses a bilinear pairing, which (roughly speaking) is a function $e$ that maps two points in an elliptic curve $E(\mathbb{F}_q)$ to a element in the finite field ...

12

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

11

Part of the reason is trust; RSA has been around longer than EC, and people feel they understand it, and they trust it more (and in security, this is important). It's also easier to implement. However, I believe that a bigger concern (at least for major companies) is the fear of being sued; there's a small company called Certicom that holds a number of ...

11

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

10

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

10

What you suggest is valid. Here is a way to show it: In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules: a key pair generator, which produces a pseudo-random key pair; a signature generator, which uses the private key to produce a signature over some piece of data; a signature verifier, which ...

10

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

10

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

10

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

10

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

9

Well, the advantages of static-ephemeral ECDH (and, they apply to DH as well): You get one-way authentication for free. That is, if Bob has Alice's public ECDH key, and uses it to talk to someone, Bob knows that that someone is Alice, without doing any further checks. Now, Alice has no idea who she's talking to; on the other hand, for some scenarios, ...

9

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 very much doubt that serious ...

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