44
$\begingroup$

We got strong numerical evidence that primes of the form $p=27a^2+27a+7$ are unsafe for cryptographic purposes since they can be found in the factorization.

Consider the following generic factoring algorithm for factoring $n$ which is divisible by $p$. Suppose you known an elliptic curve in Weierstrass form with known multiple $m$ of the order of $E$ modulo $p$. Let $\psi_n$ denote the $n$-th division polynomial of $E$.

Choose random integer $X$. If $X$ is the $x$ coordinate on $E$ modulo $p$ then $\psi_m(X) \equiv 0 \pmod{p}$. If it is not, $\psi_m(X)$ need not vanish modulo $p$. By selecting few random $X$ we probabilistically find $p$ from $\gcd(n,\psi_m(X))$.

This question conjectures that if $p=27a^2+27a+7$ and $\textrm{kronecker}(2k^3,p)= -1$ then the order of $y^2=x^3+2k^3$ is $p$. In this case $n$ is multiple of the order, so we can use the above algorithm by trying in addition random $k$.

We found $200$ bit factor with pari/gp in just few seconds.

Are these conjecturally unsafe RSA primes known?

$\endgroup$
  • 4
    $\begingroup$ The conjecture mentioned in the post is true, see the proof under the link given in the post. $\endgroup$ – GH from MO Oct 18 '17 at 19:03
  • 6
    $\begingroup$ It would be a terrible idea and it would raise suspicions of a deliberate trapdoor if the primes for RSA were chosen from a quadratic progression rather than randomly. $\endgroup$ – Felipe Voloch Oct 18 '17 at 20:10
  • 9
    $\begingroup$ @DavyWybiral The density of primes of size about $x$ is approximately $1/\log x$, while the density of primes of size $x$ in such a quadratic progression is at most $1/({\sqrt x}{\log x})$. If primes are chosen at random this essentially will never happen. You can try for yourself to see if you find these primes in the wild. People have done large scale searches for vulnerable (against other attacks) keys in use online factorable.net $\endgroup$ – Felipe Voloch Oct 19 '17 at 7:20
  • 3
    $\begingroup$ @joro Yes, it is interesting but doesn't deserve the "unsafe RSA" clickbait title. $\endgroup$ – Felipe Voloch Oct 19 '17 at 7:40
  • 3
    $\begingroup$ @FelipeVoloch I believe the popularity of this question is not from the "clickbait" but because it is linked from some popular site(s). $\endgroup$ – joro Oct 19 '17 at 10:12
7
$\begingroup$

This appears special case of "A New Special-Purpose Factorization Algorithm":

https://pdfs.semanticscholar.org/1843/73605e846f90b0a9d7252931bab4c47a1ec7.pdf

From the abstract: a new factorization algorithm is presented, which finds a prime factor $p$ of an integer $n$ in time $(D \log{n})^{O(1)}$, if $4p - 1 = Db^2$

If $p=27a^2+27a+7$ we have $4p-1=3\square$ which is covered by the paper.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.