Return to Question

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.

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?

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?

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.

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}) $)
• besides the safe prime property $P_i$ should als be not close to $p^n$ with $p$ a small prime like $2,3,..$

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.

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?

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.

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)

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.

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}) $)
• besides the safe prime property $P_i$ should als be not close to $p^n$ with $p$ a small prime like $2,3,..$