2
$\begingroup$

Is it possible to decipher a ciphertext, in RSA with small primes (two 128-bit factors) when we only have ciphertext $c$, private exponent $d$ and public exponent $e=65537$ to crack it? I try hard on this question but I couldn't find $N$.

First try, I write the code to find factors of $ed-1$ and find it on factordb and try to find out $p$ and $q$ but it doesn't help at all

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def another_set(all, subset):
    for s in subset:
        all.remove(s)
    return tuple(all)

from functools import reduce

factors = [2,2,13,17,17,137,263,397, 11119,99181,12203,12330780871,94976914459050383474573,663887747473781762461237]
all = powerset(factors)

for subset in all:
    p = subset
    q = another_set(factors.copy(), p)
    p = reduce((lambda x, y: x * y), p, 1)
    q = reduce((lambda x, y: x * y), q, 1)
    if isPrime(p+1) and isPrime(q+1):
        print(p+1,q+1)
        
$\endgroup$
5
  • 1
    $\begingroup$ Could you check if this Q/A has enough to resolve this for you? Is this part of a challenge / capture the flag? $\endgroup$
    – Maarten Bodewes
    Mar 19, 2023 at 14:47
  • $\begingroup$ @MaartenBodewes that Q/A assume that we have N but in this question there is no d, yes this is a part of CTF already finished. Unfortunately there is no write up for this question. $\endgroup$
    – Siyanew
    Mar 19, 2023 at 15:20
  • $\begingroup$ Duplicate of this later question. There is now little doubt this is a thinly disguised CTF, homework or similar. No matter how interesting and fun, that's off-topic. [update] Ah it's admitted it's a CTF, and we are told it's finished. [update] Here comes another duplicate. Perhaps we should not take "finished" at face value. $\endgroup$
    – fgrieu
    Mar 20, 2023 at 10:33
  • $\begingroup$ @fgrieu it was a ctf but it was finished and i was curious to solve it, the later question you mention link refrence to my question again! $\endgroup$
    – Siyanew
    Mar 20, 2023 at 10:38
  • $\begingroup$ To the OP: I modified the question to clarify the givens. Could you please check the current version, and edit it to tell the bit size of the given $d$ as per d.bit_length() ? From your code I think it's 255-bit (343…229, equivalently 0x4b…c5), but can't be sure. $\endgroup$
    – fgrieu
    Mar 20, 2023 at 10:58

1 Answer 1

2
$\begingroup$

Since this is a CTF, I won't give quite a full solution, just try to unstuck the OP (who seemingly made significant progress).

We are given $e$ and $d$. They must match $e\,d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$, but because the bit size of $d$ is just one bit below the sum of the bit sizes of $p$ and $q$, and because that's a common way to compute $d$, and also we can test that $e\,d\equiv1\pmod 4$, it's a reasonable betthat $d=e^{-1}\bmod((p-1)(q-1))$, and I'll assume that unless it's proven otherwise.

It follows that $e\,d-1=k\,(p-1)(q-1)$ for some integer $k$. Since $p$ and $q$ are large primes, they are odd, and we get the integer equation $$\frac{ed-1}4=k\,u\,v\quad\mathsf{with}\quad u=\frac{p-1}2\quad \mathsf{and}\quad v=\frac{q-1}2$$ The question already lists the factors of $e\,d-1$, from which we extract the $12$ factors of $k\,u\,v$ :

13 17 17 137 263 397 11119 12203 99181 12330780871 94976914459050383474573 663887747473781762461237

We need to split these factors into the integers $k$, $u$ and $v$. Their respective base-2 logarithm, rounding to two decimals towards nearest, are the 12 values

3.70  4.09  4.09  7.10  8.04  8.63  13.44  13.57  16.60  33.52  76.33  79.14

So we have reduced the problem to picking among this list two groups that each sums to $126.5\pm0.5$; and further such that the products $u$ and $v$ of the corresponding integers in the first list are such that $p=2u+1$ and $q=2v+1$ are prime.

There are only $3^{12}$ ways to split $12$ integers into $3$ groups, and it's easy to prune this tree because we approximately know the sums ($126.5\pm0.5$ for the groups for $u$ and $v$, from which we deduce $15.246\pm1.001$ for the group for $k$). E.g. one of the two largest values must belong to $u$ and the other to $v$, and then the third largest must belong to one of these.

That hopefully yields $p$ and $q$, and then deciphering a message should be easy.

$\endgroup$

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.