Hot answers tagged elliptic-curves
38
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, ...
15
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 ...
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 ...
11
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 ...
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
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 ...
9
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 ...
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
Prime theory is of great interest to me! It is currently used in many cryptosystems to protect data (in making public keys, for example). There are always a few obscure researchers studying how to make prime factorization easier (or stronger I suppose).
There are so many branches of math that we use in cryptography (matrices, primes, ellipses, modular ...
7
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 ...
7
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, ...
7
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 ...
7
ECDSA is actually a kind-of computational zero-knowledge protocol, played by the signer, with a "reduction function" as impartial verifier. For that matter, ECDSA is not very different from plain DSA.
Things basically go this way. There is a known public group $\mathbb{G}$ which I will denote additively, with $G$ as generator, and of size $q$ (a known prime ...
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 ...
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 ...
6
Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo n (the modulus, from the public key), and thus in the range 0 to n-1. This implies that values for the first byte will be quite biased (RSA ...
6
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 ...
6
Well, you understand that Elliptic Curves define an operation on points we denote as +; that is, if $A$ and $B$ are two (not necessarily distinct) points, then $A+B$ is a third point (which will be distinct unless either $A$ or $B$ are the 'point-at-infinity'). If $A$ and $B$ are the same, the operation is usually called doubling instead of addition.
Now, ...
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
Well, what SSL uses to negotiate the symmetric keys depends on the ciphersuite that both sides agree upon. By far, the most common method is that the client picks a random value (the premaster secret), and encrypts it with the server's RSA public key. However, it is not that unusual for the ciphersuite to specify that the client and the server agree upon a ...
5
To my knowledge the answer is no.
Informally, the only known method to construct pairing friendly curve is the CM method, which allows you to find an elliptic curve with strong constraints on its number of points if you put few constraints on the cardinal of the base field, or conversely a curve over a very constrained base field with only little ...
5
If RP is easy, then so is discrete logarithm.
Assume that you have a way to easily solve the RP for a given n. Now I give you G and P on the curve (of size q), and I want you to find x such that P = xG. What you do is the following: you generate random integers r1, r2,... rn modulo q, and compute Qi = riG for all i from 1 to n. Then you solve RP for P ...
5
I do not know of any general way to create the mapping you want (and if there was, it might turn into an efficient point-counting algorithm, which would be great), but you can do this on some curves.
Consider a prime $p$ equal to $2$ modulo $3$. In $\mathbb{Z}_p$, every value has a single cube root (because $3$ is then invertible modulo $p-1$). Then, look ...
5
Yes, one can use Elliptic Curve Cryptography in wireless sensors.
A typical use of ECC in this domain would be to authenticate the sensor and establish a symmetric session key using a combination of ECDSA and ECDH. That symmetric session key would then protect application data, insuring confidentiality and integrity using AES-GCM. This is hybrid ...
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
The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus ...
Only top voted, non community-wiki answers of a minimum length are eligible
