0
$\begingroup$

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?

Improve this question
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.
$\endgroup$
5
  • $\begingroup$ in python- len(bin(n)[2:]) == 34095 and len(bin(c)[2:]) ==34095 $\endgroup$
    – CipherNewbie
    Aug 4 at 9:42
  • $\begingroup$ 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? $\endgroup$
    – fgrieu ♦
    Aug 4 at 9:52
  • $\begingroup$ @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. $\endgroup$
    – CipherNewbie
    Aug 4 at 10:53
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Aug 4 at 11:17
  • 1
    $\begingroup$ 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 $\endgroup$
    – CipherNewbie
    Aug 4 at 11:42

0

Reset to default

Your Answer

CipherNewbie is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.