# Crack RSA with $e$ and $d$?

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)


• Could you check if this Q/A has enough to resolve this for you? Is this part of a challenge / capture the flag? Mar 19 at 14:47
• @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. Mar 19 at 15:20
• 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.
– fgrieu
Mar 20 at 10:33
• @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! Mar 20 at 10:38
• 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.
– fgrieu
Mar 20 at 10:58

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.