5
$\begingroup$

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.

$\endgroup$

migrated from math.stackexchange.com Mar 2 '16 at 20:04

This question came from our site for people studying math at any level and professionals in related fields.

  • $\begingroup$ It's very hard to answer such questions in the negative, as the best you can do usually is say "nothing comes to mind" $\endgroup$ – Stella Biderman Mar 2 '16 at 17:24
  • $\begingroup$ @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. $\endgroup$ – Niklas B. Mar 2 '16 at 17:29
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you link to the original "p - 1 factorization" method maybe so I can look that up? $\endgroup$ – Niklas B. Mar 2 '16 at 20:48
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm $\endgroup$ – poncho Mar 2 '16 at 20:53
  • $\begingroup$ 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 :) $\endgroup$ – Niklas B. Mar 3 '16 at 20:05

Your Answer

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

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