Choosing 512 bit prime biginteger as secret value as in RSA
Choosing TypeA curve (rbits=256,qbits=512) and setting secret value by randomly selecting from $Z_r$ value
I wanna know which one has more security strength even though I know 128 bit security can be obtained with 256 bit elliptic curve and 3072-bit RSA keys.I need some detailed explanation.
When we set rbits=256 bits, is it 256 bit elliptic curve? Or when we set qbits=256 bits, is it 256 bit elliptic curve?
-
1$\begingroup$ A "TypeA curve", do you mean a curve that is designed to do a so-called "Type A pairing"? Unless you actually need to do a pairing operation, selecting such a curve is silly, as it is a deliberately weak curve (compared to a random elliptic curve of the same size) $\endgroup$– ponchoOct 5, 2016 at 12:50
1 Answer
A Type A curve has embedding degree 2. That means via the pairing we get an homomorphism from an ECC curve of bit length k to a finite field with 2 k bits (i.e. qbits).
You have to compare the complexity of:
- calculating the discrete logarithm in the EC group with k bits and without using the paring homomorphism (i.e. by a generic algorithm)
- calculating the discrete logarithm in the finite field with 2k bits by the number field sieve.
and take the minimum of both.
The complexity of a generic ECC DL algorithm is $2^{k/2}$
The complexity of the number field sieve for a finite field with k bits is approximately
$$\lambda (k) := \exp(1.9 (k \log (2))^{1/3} \log(k \log (2))^{2/3})$$
Therefore we have to compare $2^{k/2}$ with $\lambda (2k)$.
For big values of k, surely the factorisation in the finite field is faster then the generic ECC algorithm. So let us calculate the break-even point:
$$min_k (\lambda (2 k) = 2^{k/2})$$
This gives $k \approx 65$.
From that value of k on we can calculate the running time complexity as $\lambda (2k)$
For instance, an elliptic Type A curve with 256 bits gives you a strength of 63 bits only .
Please take this result with a grain of salt, because I have omitted the $o(1)$ term.
For real cryptographic use its maybe a better idea to use the table from the NIST SP 800-57 document:
Strength RSA modulus size
80 1024
112 2048
128 3072
192 7680
256 15360
For instance, that would have the following security implication:
In order to get a strong security (i.e. strength >100) type A curve, you need a finite field size of 2048 bits. This means your type A curve must have rbits=1024 and qbits=2048.