1
$\begingroup$

Here is a CTF chanllege about RSA(The competition has ended for serval hours),and here is the critical encryption code:

.........
def encrypt(msg):
    p, q, r, t = getPrime(256), getPrime(256), getPrime(256), getPrime(256)
    n = p ** 2 * q * r * t
    phi = (p - 1) * (q - 1) * (r - 1) * (t - 1)
    privkey = inverse(n, phi)
    c = long_to_bytes(pow(bytes_to_long(msg), n, n))
    return [c, n, privkey]
........

What i knew is the list:[c, n, privkey].

I need to recover p and q so that i can complete this Challenge. Here are some methods i've tried:

Try to brute k in : $$privatekey\cdot n=k\cdot phi+1$$but it not working;

And using yafu to factor n also failed.

I thought this code maybe about to Schmidt-Samoa_cryptosystem:https://en.wikipedia.org/wiki/Schmidt-Samoa_cryptosystem,but the way to generate private key are not the same.

And we can see the phi function seems not as normal as calculate $\phi(n)$ when $n=p\cdot q$ or $n=p_{1}^{k_1}\cdot p_{2}^{k_2}.....p_{n}^{k_n}$.

I thought the most hardest part of this problem is how to factor modules with know (c,n,d).But i tried what i knew,all not working.

I want to know if there are some ways i can use to factor modules like this situation,i will be more than delighted if someone can help me with it.

$\endgroup$
3
  • 1
    $\begingroup$ @kelalaka: actually $c^{privkey} \bmod n$ is (in general) not the original message; that's because $n$ isn't square-free, and the $phi$ computation assumes it is. In terms of using $privkey$ to factor $n$, that's only a minor complication; the standard technique can be tweaked so that it still works... $\endgroup$
    – poncho
    Sep 15, 2023 at 18:49
  • 1
    $\begingroup$ @kelalaka: we have $e$, it's $n$ (as in Clifford Cocks's A Note on 'Non-secret Encryption') $\endgroup$
    – fgrieu
    Sep 15, 2023 at 19:03
  • $\begingroup$ @fgrieu how badly I've read this code! Okey, that is solvable than What a nice typewrite usage there. $\endgroup$
    – kelalaka
    Sep 15, 2023 at 19:11

1 Answer 1

2
$\begingroup$

I need to recover p and q so that i can complete this Challenge.

There is a slight complication; we can recover $p$ and know that $q$ is one of three values, but we don't know which one it is.

In any case, we know a value $privatekey \cdot n - 1 = k \cdot (p-1) \cdot (q-1) \cdot (r-1) \cdot (t-1)$.

What this means is that (for $g \text{ r.p. with } p, q, r, t$):

$$g^{privatekey \cdot n - 1} - 1 \equiv 0 \pmod p$$ $$g^{privatekey \cdot n - 1} - 1 \equiv 0 \pmod q$$ $$g^{privatekey \cdot n - 1} - 1 \equiv 0 \pmod r$$ $$g^{privatekey \cdot n - 1} - 1 \equiv 0 \pmod t$$

but (most likely)

$$g^{privatekey \cdot n - 1} - 1 \not\equiv 0 \pmod {p^2}$$

What this means is that if we compute $\gcd(g^{privatekey \cdot n - 1} - 1, n)$, that's (unless we are quite unlucky or were silly enough to pick $g=1$) the value $p * q * r * t$. Divide that number into $n$, and that gives us $p$.

Now that we have that, now comes the task of recovering $q, r, t$. We can compute $n' = n / p^2$ (just to make our lives a bit easier). And, we can compute $z = (privatekey\cdot n - 1) / 2^\lambda$ odd (that is, $\lambda$ is the integer that makes $z$ an odd integer), and then we can pick random $g$ values, and compute:

$$f(g, \alpha) = g^{z \cdot 2^\alpha} \bmod n'$$

for various $\alpha$ between 0 and $\lambda$. If $f(g, x) \ne 1, n'-1$ but $f(g, x+1) = 1$, then $\gcd(f(g, x)-1, n')$ is a nontrivial factor of $n'$, that is, either $r, s, t, rs, rt$ or $st$. Do this a couple of times with various $g$ values and this will quickly recover all the $r, s, t$ values (but won't tell you which is which).

If you know your number theory, it should be straight-forward to see how this works.

$\endgroup$
3
  • $\begingroup$ Did you mean $\gcd(f(g, x-1)-1, n')$ insted of $\gcd(f(g, x)-1, n')$ $\endgroup$
    – kelalaka
    Sep 15, 2023 at 20:45
  • 1
    $\begingroup$ @kelalaka: no, I got it right this time. Remember, $f(g, x+1) = 1$, and we want the one before that, and that's $f(g, x)$. What we have in that case is that $f(g, x) \equiv 1$ for some of $\bmod q, r, t$ but not all (if it were all, then $f(g, x)=1$, if it were none, then $f(g, x) = n'-1)$; hence $\gcd( f(g, x) - 1, n')$ reveals factors... $\endgroup$
    – poncho
    Sep 15, 2023 at 20:55
  • $\begingroup$ That is so true. The only missing part from the question and answer for people don't see it is where the first we know... That is from the calculation of the inverse of the $e$ with the ExtGCD. $\endgroup$
    – kelalaka
    Sep 15, 2023 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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