0
$\begingroup$

So somehow I know that the key size in ECC is defined over the number of elements in a finite field or that it is almost equivalent to that (Correct me if I am wrong). However, other than on Wikipedia I cannot seem to find any source (Article, Book, Encyclopedia with a trusted author, etc.) that states this and I am not allowed to use Wikipedia as reference for my work. I have been scrolling back and forth in my book (Cryptography & Network Security, Sixth Edition) and on Google without finding anything that states exactly this except from Wikipedia. Also, I have looked through the references on Wikipedia and they don't really have anything even though they state it themselves. Therefore, I would just kindly ask if someone knows of a trusted source where the author is shown that states this, unless I am wrong of course...

$\endgroup$
0
$\begingroup$

The security level is usually taken to be an estimate of the $\log_2$ of the expected cost in bit operations of the best attack attaining probability near 1 of success. In the case of well-designed elliptic-curve cryptography for a curve $E/k$ over a field $k$, this is usually determined by the cost of the best algorithm for computing discrete logarithms in a subgroup of $E(k)$, the $k$-rational points of $E/k$, with large prime order $\ell$.

The expected attack cost for Pollard's $\rho$ is $O(\sqrt{\ell})$, so, e.g., we estimate a 128-bit security level for breaking X25519, which works in a group whose order $\ell$ is 252 bits; see the discussion at SafeCurves for more on Pollard's $\rho$ cost, and for references to other types of attacks on elliptic-curve cryptography. The order $\#E(k) = h \ell$ of the group $E(k)$ can't differ from $\#k$, the cardinality of the field $k$, by more than $2\sqrt{\#k}$, by Hasse's theorem; see an earlier answer I wrote for more on the relationship between field $k$, subgroup order $\ell$, and cofactor $h$.

The private key size is usually taken to be the number of bits it takes to encode a secret scalar in $\mathbb Z/\ell\mathbb Z$. (Again, by Hasse's theorem, $\ell = \#E(k)/h$ can't be much more than $\#k$, and won't be much less unless the group has an unreasonably large cofactor $h$.) This number of bits can't be less than twice the maximum security size because of the generic Pollard's $\rho$ attack cited above. In some cryptosystems, though, we don't exactly store an element of $\mathbb Z/\ell\mathbb Z$ but rather a seed that we hash into one as in standard EdDSA, and in others we store $\mathbb Z/\ell\mathbb Z$ alongside other data as in some nonstandard extensions to EdDSA.

The public key size is usually taken to be the number of bits it takes to encode a curve point in $E(k)$. There are different encoding schemes available. You could naively encode a pair of elements of $k$, but that's a waste of space with a lot of redundancy that attackers can exploit. You could encode one coordinate, and transmit the other as a single bit, which requires some work for the receiver to decompress. You could use fancier compression schemes like Elligator or Decaf, which have better security properties.

Since there are so many different types of cryptosystems and ways to use elliptic curves out there, nothing more specific can be said in general about ‘key size’ unless you have a more specific question.

$\endgroup$
  • $\begingroup$ Ok so, is it correct that the modulus size equals the size of the finite set? However, I don't really get what b in the elliptic curve equation is then... it somehow stretches the curve out when the value is changed, but is it always going to the limit of the finite field? Or, actually I was just wondering, why is it that these different curves have such large values for b? $\endgroup$ – user164324 Dec 18 '17 at 0:45
  • $\begingroup$ @user164324 There is no straightforward relationship between the $b$ parameter in the short Weierstrass formula $y^2 = x^3 - a x + b$ and the number of points on the curve—you just have to use Schoof's algorithm to count them. Some curves have parameters $a$ and $b$ that were allegedly chosen uniformly at random, rejecting composite numbers of points, like NIST P-256. Some have rigidly selected parameters that are the smallest values satisfying certain criteria, like secp256k1, whose equation is $y^2 = x^3 + 7$. Some were designed like that but for different shapes like Edwards curves. $\endgroup$ – Squeamish Ossifrage Dec 18 '17 at 0:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.