1
$\begingroup$

Intro:

EC are often compared with RSA but how about a more safe version of the discrete logarithm?

All 3 can be reduced to the problem:

$$b = g^a \mod{P}$$

In RSA $P$ is a product of two primes. To solve the discrete logarithm 'just' a factorization of $P$ is required. Different to the two other cases $a,b$ is known and $g$ is searched.

But if $P$ is a prime the problem can get much harder. It depends at the factorization of $P-1$ because $P-1$ is also equal to the number of different elements.

As far as I know the best choice is a 'safe prime' with $P = 2 q +1$ with $q$ a prime as well. This discrete logarithm can be solved in $\mathcal{O}(\sqrt{q}) $ with $q$ the biggest prime factor (with Pollard's algorithm).

At EC $P$ is a prime as well but the number of elements can be different (but still $\approx P$). It can e.g. be determined with Schoof's algorithm. A number of safe elliptic curves can be found at safecurves.cr.yp.to . Tested safe curves had all $2^3 \cdot q$ elemnts (with $q$ a big prime). Afak solving those will also take $\mathcal{O}(\sqrt{q}) $ time.


Question:

Given the discrete logarithm solving problem for normal numbers and elliptic curves (mod a prime $P_i, P_e$). Given a valid generator $g_i, g_e$ and a possible result $b_i, b_e$.

$$\text{normal: } b_i = g_i^{a_i} \mod P_i $$ $$\text{elliptic curve: } b_e = g_e^{a_e} \mod P_e $$

Let the elliptic curve have $N_e = 2^3 \cdot q$ different elements with $q$ a big prime (other variables chosen in that way).

Let $$P_i = 2 \cdot q +1$$

Do both problems have the same solving time of $\mathcal{O}(\sqrt{q}) $ ?

(we ignore the linear factor of computation time for each single step due to different multiplication time)


Bonus questions:

Which other factor have impact into the solving speed?

BQ1.) The number of elements of some curves from safecurves.cr.yp.to had also the property: $N_e -1 = 3 \cdot r$ with $r$ a big prime. Does this have any impact?

BQ2.) Has the factorization of $P_e -1$ any impact at the security?

BQ3.) Has the factorization of $q-1$ any impact at the security? (for normal and EC)


Edit: Update

  • It looks like 'number filed sieve' can do better than Pollard's algorithm ($\mathcal{O}(\sqrt{q}) $). To use it on EC the embedding need to be small -> chose a big one
  • besides the safe prime property $P_i$ should als be not close to $p^n$ with $p$ a small prime like $2,3,..$

$\rightarrow$ assumption: so there is a difference?

$\endgroup$
5
  • 1
    $\begingroup$ keylength.com/en/compare $\endgroup$ – kelalaka Mar 4 at 19:01
  • $\begingroup$ @kelalaka ty4link. But unsure about the naming: I guess symmetric would be AES, But whats the difference between 'Factoring Modulus', 'Discrete Logarithm Key', 'Discrete Logarithm Group'. $\endgroup$ – J. Doe Mar 4 at 19:16
  • 2
    $\begingroup$ Symmetric is a general name for symmetric ciphers like AES, ChaCha. Factoring Modulus RSA like, the two other is realated to DSA $\endgroup$ – kelalaka Mar 4 at 19:20
  • $\begingroup$ Interesting link but as far as I understood DSA is not exactly the same as the described normal discrete log problem. However it also operation at a sub-group generator with an order of 'Discrete Logarithm Key'-bit. This also supports the assumption of same computation time. During checking this links out I also noticed there is a faster method 'number filed sieve' and besides the safe prime property it should als not be close to $p^n$ with $p$ a small prime like $2,3,..$ Will add this $\endgroup$ – J. Doe Mar 4 at 21:10
  • 1
    $\begingroup$ On the above comment: if one can solve the DLP in $\mathbb Z_p^*$, one can (trivially) solve DSA; for the converse, see this. $\endgroup$ – fgrieu Mar 5 at 19:09
1
$\begingroup$

As far as I know the best choice is a 'safe prime' with $P=2q+1$ with $q$ a prime as well.

This is the best choice for a given size of $P$, but not for a given size of $q$. See this.

This discrete logarithm can be solved in $\mathcal{O}(\sqrt{q})$ with q the biggest prime factor (with Pollard's (Rho) algorithm).

Essentially yes (minor caveat: $\mathcal{O}(\sqrt{q})$ is not effort, but the number of multiplications of integers of size $P$, with $P>q$, hence the effort grows faster by a factor at least $\ln P\,\ln\ln P$). That the DLP can be solved with such method and effort does not imply that such method or effort is needed. And if $P$ is a safe prime, there are methods (including the Number Field Sieve) requiring less effort. Again, see this.

Do (DLP in a subgroup of an appropriate Elliptic Curve on one hand, of $\mathbb Z_P^*$ on the other hand) have the same solving time of $\mathcal{O}(\sqrt{q})$ (group operations, where prime $q$ is the order of the subgroup)?

Yes, when using Pollard's Rho algorithm. That algorithm is believed optimum in the Elliptic Curve case, and for $P$ large enough in the $\mathbb Z_P^*$ case.

No, when $P$ is a safe prime (and large enough to make the DLP non-trivial), and using the Number Field Sieve to tackle the DLP in the subgroup of $\mathbb Z_P^*$.


Note: I don't know that the Number Field Sieve can be used to solve the DLP in an appropriate Elliptic Curve (sub)group; and it would come as a huge surprise if it was more efficient than Pollard's Rho algorithm.

$\endgroup$
2
  • 2
    $\begingroup$ as far as I understood EC can be embedded in a $\mathbb{F}_{p^k}$ DLP. If the embedding degree $k$ is small NFS can be used at this. Depending at $k$ it can be faster. see question1 and question2 $\endgroup$ – J. Doe Mar 5 at 23:10
  • $\begingroup$ ty for answering this as well. This was the first question and the linked was a 2nd trial but it generally also answering this question. I didn't knew how to proceed with this question. I think I know the difference now (except maybe the relation for some special primes which are somewhere in between those cases but not needed now). Thank you again. $\endgroup$ – J. Doe Mar 5 at 23:10

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.