# Is there a security problem with this prime generation algorithm?

I am facing the following algorithm to generate an RSA public key:

e = 0x10001

def generate_p():
r := random odd 128-bit number
p := (3*r^4 + 1)/4
if is_prime(p) and gcd(p-1, e) = 1:
return p
else:
return generate_p()

def generate_q():
r := random odd 128-bit number
q := (11*r^4 + 1)/4
if is_prime(q) and gcd(q-1, e) = 1:
return q
else:
return generate_q()

p = generate_p()
q = generate_q()
N = p*q
d = modinv(e, (p-1)*(q-1))


So essentially $s$ and $t$ are random 128-bit integers, $4p = 3s^4 + 1$ and $4q = 11t^4 + 1$ with $p$ and $q$ prime. Does the way $p$ and $q$ are generated give us information that helps factor $N$ (which is 1024 bits in size)?

I considered Coppersmith's attack to compute $s$ and $t$ as small roots mod p/q, but they are not small enough for the algorithm to be applicable.

• It's very hard to answer such questions in the negative, as the best you can do usually is say "nothing comes to mind" – Stella Biderman Mar 2 '16 at 17:24
• @StellaBiderman OK let's put it differently. This problem is from a security competition, so it's very likely that it can be exploited. But there can be other bugs in the code which I didn't show that lead to it being exploitable. I don't know how to put the question differently. – Niklas B. Mar 2 '16 at 17:29

This is the approach that finally let us factor $N$ for the competition. I believe it completely breaks the given scheme. Let's write down the formula for $N$:

$N = pq = \frac{3s^4+1}{4}\cdot\frac{11t^4+1}{4}$ for some $s, t \in [2^{128}, 2^{129})$

After some rearranging:

$\frac{16}{33}N = (st)^4 + \frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33}$

In our case, we had $\frac{1}{11}s^4 + \frac{1}{3}t^4 +\frac{1}{33} < (st)^2$ and thus after we substitute $x := (st)^2$:

$x^2 \le \frac{16}{33}N < x^2 + x = x(x+1) < (x+1)^2$

So we could compute $x = \lfloor\sqrt{\frac{16}{33}N}\rfloor$ and then factor $\sqrt x$ (which has only 256 bits) to get $s$ and $t$.

I feel like the above inequality holds generally if $s$ and $t$ have somewhat similar value, but I haven't tried to prove this.

It would appear that the $p-1$ factorization method can be adapted to factor numbers of this form with nontrivial probability.

We have $4n = (3*r_p^4 + 1)q = (11*r_q^4 + 1)p$ (where $r_p$ is the value of $r$ selected when generating $p$, and $r_q$ is the value of $r$ selected when generating $q$.

Hence, if either $r_p$ or $r_q$ have no factors larger than, say, $2^{40}$ (which will happen with nontrivial probability), then this method would factor:

• Select an arbitrary odd $g$, and compute $z := g^{3\cdot 11} \bmod 4n$
• For each odd prime $s$ between 3 and $2^{40}$ (repeating small primes multiple times), update $z := z^{s^4} \bmod 4n$
• Compute $gcd(n, z-1)$

This probably can be simplified to work modulo $n$ rather than $4n$...

Update: on second thought, this approach is less likely to work than I originally thought; for this to be effective, the relevant values that need to be smooth is $p-1 = 3(p_r^2 + 1)(p_r+1)(p_r-1)/4$, or alternatively $q-1$. While it is possible that none of $p_r^2 + 1$, $p_r+1$, $p_r-1$ will have a large factor, it's not nearly as likely as it would be if $p_r$ alone was required to be smooth.

It would appear that all three values will have no prime factors $> 2^{64}$ with probability around 0.2%; hence the $p-1$ method would give a factorization method with circa $O(2^{64})$ work that would succeed for one out of about 500 modulii generated by this method.

• Can you link to the original "p - 1 factorization" method maybe so I can look that up? – Niklas B. Mar 2 '16 at 20:48
• en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm – poncho Mar 2 '16 at 20:53
• Your algorithm looks good. In my particular case it didn't yield a solution unfortunately, but given your probability bounds that seemed unlikely in the first place. I'm now wondering whether we can generalize a more powerful factorization algorithm such as the quadratic sieve to our scenario. I'm still leaving this question open for now in case somebody else comes along with a different approach. If not, I will accept this answer eventually of course :) – Niklas B. Mar 3 '16 at 20:05