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?

Improve this question
$\endgroup$
14
  • 4
    $\begingroup$ The conjecture mentioned in the post is true, see the proof under the link given in the post. $\endgroup$
    – GH from MO
    Commented Oct 18, 2017 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
    Commented Oct 18, 2017 at 20:10
  • 3
    $\begingroup$ @FelipeVoloch This is not threat to sound RSA implementation, but there is interest in mathematics and cryptography about factors which can be found efficiently. $\endgroup$
    – joro
    Commented Oct 19, 2017 at 5:26
  • 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
    Commented Oct 19, 2017 at 7:20
  • 3
    $\begingroup$ @joro Yes, it is interesting but doesn't deserve the "unsafe RSA" clickbait title. $\endgroup$
    – Felipe Voloch
    Commented Oct 19, 2017 at 7:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .