44

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?

Timothy Chow
  • 78,129
joro
  • 24,174
  • 4
    The conjecture mentioned in the post is true, see the proof under the link given in the post. – GH from MO Oct 18 '17 at 19:03
  • 6
    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. – Felipe Voloch Oct 18 '17 at 20:10
  • 1
    @FelipeVoloch even if they are totally random I think the point is that some random primes might be less safe than others. But I wonder how many this would even represent. – Davy Wybiral Oct 19 '17 at 00:57
  • 3
    @FelipeVoloch This is not threat to sound RSA implementation, but there is interest in mathematics and cryptography about factors which can be found efficiently. – joro Oct 19 '17 at 05:26
  • 9
    @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 https://factorable.net/ – Felipe Voloch Oct 19 '17 at 07:20
  • 3
    @joro Yes, it is interesting but doesn't deserve the "unsafe RSA" clickbait title. – Felipe Voloch Oct 19 '17 at 07:40
  • @FelipeVoloch What title do you suggest? I thought this is standard term, even for sparse sequences as you note. – joro Oct 19 '17 at 07:42
  • @joro "Multiples of primes of the form blah are easily factorable" would have been an alternative. – Felipe Voloch Oct 19 '17 at 07:57
  • @FelipeVoloch feel free to edit. The title gives the quadratic form, so it is clear from the title the sequence is sparse. – joro Oct 19 '17 at 08:24
  • 3
    @FelipeVoloch I believe the popularity of this question is not from the "clickbait" but because it is linked from some popular site(s). – joro Oct 19 '17 at 10:12
  • 1
    @FelipeVoloch thanks for clearing up the probabilities. That's what I was looking for. – Davy Wybiral Oct 19 '17 at 12:59
  • Can I suggest rewording "are unsafe for cryptographic reasons" to "are unsafe for cryptographic purposes"? I would be happy to make the edit myself but I'm not certain that you meant the latter so wanted to check. – Tom Ellis Oct 19 '17 at 13:46
  • @TomEllis Actually they are unsafe only for hardness of factorization not about discrete logs over finite fields. Will edit. Thanks. – joro Oct 19 '17 at 13:58
  • 3
    @FelipeVoloch : One version of the Qi Cheng paper that joro found is titled, "A new class of unsafe primes." So I don't think joro can be accused of "clickbait." https://eprint.iacr.org/2002/109.pdf – Timothy Chow Oct 25 '17 at 03:20

1 Answers1

7

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.

joro
  • 24,174