1
$\begingroup$

For encryption a prime $P = 2 \cdot Q \cdot R \cdot S +1$ was used.
An adversary want to solve the discrete log problem $m \equiv g^i \bmod P$. For this he want to use the Pholig-Hellmann algorithm.
To use this he need the factorization of $P-1 = 2 \cdot Q \cdot R \cdot S$.
Factor $2$ is trivial so he only need to know the primes $Q, R, S$

(edit) He should also not be able to project a value $m$ into a subgroup, like:

$$m^{2\cdot R \cdot S} \equiv v \bmod P$$ $v$ is $1$ or has order $Q$ (edit end)

He does know prime $P$ and the internal structure of $P-1$ has $4$ factors and one of those is $2$. He also knows the other three factors are quite similar to eachother: $$\frac{P-1}{2} \approx Q^3 \approx R^3 \approx S^3$$ with $$ \max(Q,R,S) \le 1.25\cdot\min(Q,R,S)$$ or $$\forall a,b,c \in \{Q,R,S\}: 0.8\cdot a \le b \le 1.25 \cdot c$$

edit2: That means the potential factors are in limited range between $\sqrt[3]{(P/(1.25^2))}$ and $\sqrt[3]{P}$


For values consisting out of two factors the current record is afaik about 240 decimal digits or 795-bit (records-wiki)


Question: How large need to be a value out of three prime factors as described above to be as secure as the current record for two factors?

($Q,R,S,P$ can be set to special kind of primes, like safe primes, as long those conditions from above hold )

$\endgroup$
  • 2
    $\begingroup$ Security of discrete log is not related to factoring. You can directly assume that the adversary has the factorization. $\endgroup$ – kelalaka Jan 21 at 11:24
  • 1
    $\begingroup$ @kelalaka fastest way to solve such a discrete log is afaik Pholig-Hellmann algorithm which needs to know the factorization of $P-1$. If he dont know the factorization it will take way longer to solve it. Or did got something wrong? If a generator with e.g. order $Q$ is given. Would it be faster to find his order than factorizing $P-1$? $\endgroup$ – J. Doe Jan 21 at 11:38
  • $\begingroup$ Do you want to increase the prime sizes since you fear of factoring? Then not able to solve the dLog since that already infeasible! $\endgroup$ – kelalaka Jan 21 at 12:10
  • $\begingroup$ Note that the runtime of Pohlig-Hellman is roughly $O(\sqrt Q+\sqrt R+\sqrt S)$ in your case. As the product still needs to be at least 1000 bit long, each factor needs to be at least 333 bits long and so the runtime of Pohlig-Hellman would be roughly $2^{160}$ which is infeasible. $\endgroup$ – SEJPM Jan 21 at 12:26
  • $\begingroup$ @kelalaka you are correct. The main reason is not be able to project one value to another subgroup. (did some edit) $\endgroup$ – J. Doe Jan 21 at 12:45

Your Answer

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

Browse other questions tagged or ask your own question.