# RSA with huge ciphertext

I am trying to find the flag from an RSA ciphertext, I am able to get the factors from factordb.com but the given e is not coprime with phi(n). One weird thing that I observed is that n and cipher_int has 10264 digits (looks like an integer). I am very new to crypto, Any ideas on how I can solve this?

New contributor
CipherNewbie is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• in python- len(bin(n)[2:]) == 34095 and len(bin(c)[2:]) ==34095 Aug 4 at 9:42
• If indeed $e$ is not coprime to $\varphi(n)$ then this is not really RSA. Since you "get the factors": are they distinct primes $p_i$ which product is $n$ ? Also, for confirmation; compute the $\gcd(e,p_i-1)$, is any of these not $1$? Does the problem statement make it clear that cipher_int was obtained as $c:=m^e\bmod n$ as in textbook RSA ? Is the order of magnitude of $e$ small enough that it could be that $m^e<n$, which would make recovery of $m$ from $c$ and $e$ trivial?
– fgrieu
Aug 4 at 9:52
• @fgrieu, thanks for the reply! Yes, the primes are distinct and their product is n, gcd(e, p-1) and gcd(e, q-1) both of them are not 1, e is quite small as compared to n. Aug 4 at 10:53
• So that's not RSA, but $n$ is a valid RSA modulus. What matters about the magnitude of $e$ is if the bit size of $n$ divided by the value (not bit size) of $e$ is large enough to form a meaningful message. E.g. if $e=17$ then we are talking $\lfloor34095/17\rfloor=2005$ bits (250 bytes in ASCII, more with some CTF encodings). Below that limit, $m^e<n$, thus $c=m^e$, thus $m$ is easy to find from $c$ and $e$. Note: If $e=2$, that could be Rabin encryption, or a variant if $e$ is even and larger.
– fgrieu
Aug 4 at 11:17
• Hmm turns out they gave the wrong e deliberately, actually e/4 was Fermat's number (65537) and they just wanted to see If I could "bend" my thought in that direction. BTW thank you so much for your quick response your comments gave me enough material to read for the coming weekend! @fgrieu Aug 4 at 11:42