What's the meaning of "160-bit curve" in an elliptic curve? Or 192, 224, 256, etc. And what is the standard for selecting this number of bits?
Why they don't say "100-bit curve"?
$\begingroup$
$\endgroup$
-
$\begingroup$ Please do not merge a new question in your old question that already received answers. Just open a new one. $\endgroup$ – DrLecter Oct 17 '14 at 6:04
-
$\begingroup$ @DrLecter I thought maybe I can give my answer in this way . Because I can explain my problem better. I asked them in another post too but nobody can understand me.should I delete my new question in this post now? $\endgroup$ – zahra Oct 17 '14 at 6:15
-
$\begingroup$ I'd suggest to remove this edit from this question and put it into a new one. Otherwise the answers to your initial question would make the impression that they are incomplete (bad), but they are actually perfectly valid answers to your original question. $\endgroup$ – DrLecter Oct 17 '14 at 6:18
$\begingroup$
$\endgroup$
What's the meaning of 160 bit Curve in Elliptic curve?
It's the size of the field, as the other answers explain. It affects the size of keys and signatures (which can be equal to the number or e.g. double it), as well as security and performance.
Why they don't say 100 bit curve?
100-bit curves are too small.
It's also a convention. Other cryptographic primitives, like hash functions or symmetric ciphers, can have any bit length we want and powers of two are chosen for performance. So we want elliptic curves that match (or are close) to pair with them in a protocol, so we don't waste performance on security beyond the weakest link.
There's also the performance of the elliptic curve algorithm itself. It is useful to have the bit length be a multiple of a large enough power of two, like 64 bits, because computers deal with numbers of 32-bits or 64-bits. This isn't always the case though (e.g. P-521) if there happens to be a very juicy prime ($2^{521}-1$) that is easy to work with.
(As an aside, we do sometimes approximate something as e.g. 100-bit security if we don't care about the exact number but only a minimum. For example, a 256-bit elliptic curve that has a prime smaller than $2^{256}$ – e.g. P-256 – has only approximately 128-bit security so might as well call it 100-bit. Especially after you add a signature algorithm that also relies on a hash function, perhaps losing another bit of security to collisions.)
$\begingroup$
$\endgroup$
It refers to the bit length of the order of the elliptic curve group (number of points on the curve).
The security of a curve is equal to the square root of its order. So we pick values that are twice as long as the security level we want (160-bit for 80-bit security, 256-bit for 128-bit security, etc)
We don't use 100-bit curves because we prefer security levels that are greater than or equal to (preferably close to) symmetric key lengths.
-
$\begingroup$ It's that I get from your comment : when we say 192 bit curve it means there are 2^192 valid points on the curve .am I right? $\endgroup$ – zahra Oct 15 '14 at 14:29
-
$\begingroup$ @zahra Close to that number anyway (the order is an integer, which is slightly smaller than 2^192). But beware that e.g. the key size of RSA does not implicate the same thing; there will be significantly less key pairs for RSA. $\endgroup$ – Maarten Bodewes♦ Oct 15 '14 at 15:52
-
1$\begingroup$ @Zahra There are approximately 2^192 points on the 192-bit curve (It's a 192-bit number). $\endgroup$ – user13741 Oct 15 '14 at 15:53
-
$\begingroup$
$\endgroup$
An elliptic curve to be used in cryptography is defined over a finite field $\mathbb{F}_p$ (but also can be a binary polynomial finite field $\mathbb{F}_{2^m}$). The bit length of this $p$, or the $m$ in the case of the binary polinomials, is what is used later to describe the elliptic curve in terms of size.
-
$\begingroup$ thank you @srgbinch . OK it's mean that 192 is the bit length of p .yes? we can assume several prime number with length of 192 bit . how can I found the exact prime number? $\endgroup$ – zahra Oct 15 '14 at 13:54
-
$\begingroup$ @zahra Normally we use pre-generated "named" curves provided by brainpool, NIST or a set of other "safe curves". More info at SafeCurves. Only secret $s$ will be randomly chosen and public point $w$ can then be calculated by the user. $\endgroup$ – Maarten Bodewes♦ Oct 15 '14 at 15:46
-
$\begingroup$ @owlstead your comments are very helpful for me . I Checked the SafeCurves. But when I want to simulate algorithms I can't get the right output , I thought maybe can use small numbers to check the computations with my hand and compare them with the outputs . can I ? $\endgroup$ – zahra Oct 17 '14 at 6:08
-
$\begingroup$ I don't think you can validate outputs efficiently by hand. If you have a well described question for a specific implementation you could post on StackOverflow. $\endgroup$ – Maarten Bodewes♦ Oct 17 '14 at 10:02
$\begingroup$
$\endgroup$
The best known discrete logarithm algorithm on elliptic curves is the parallelized Pollard rho algorithm , which has running time $O(√r)$ where $r$ is the size of largest prime-order subgroup of $E(F_q)$. On the other hand, the best algorithm for discrete logarithm computation in finite fields is the index calculus attack which has running time subexponential in the field size. Thus to achieve the same level of security in both groups, the size $q^k$ of the extension field must be significantly larger than $r$.
