Join Log in
Score:0
avatar Crypto

RSA: decrypting short message with a different public key

jp flag
Blooberty

I am having a hard time understanding what I have come across using RSA-textbook.

So I have:

  • e = 3 as an exponent
  • a VERY long public key N of 1991 bits (clearly useless trying to factor)
  • a very short cryptogram of 403 bits

By doing C^(1/3) (because we have a short message compared to the public key), I found the message of 135 bits.

However, when I generate a new public key, therefore calculating a new exponent d, and use it to decrypt the cryptogram, I find the message also!

I used the standard decryption method on a Python code I found for RSA-textbook here: https://www.packetmania.net/en/2022/01/22/Python-Textbook-RSA/

Using that code, I do what looks like: RSA(2048, 3).decrypt(C). I also noticed that the length for the public can be anywhere > 136 with my cryptogram.

How come generating a completely new N = pq and subsequently d then doing C^d mod N gives me my message?

64
0 + 0
rsa
kelalaka avatar
in flag
kelalaka
Welcome to [cryptography.se]. Your experiment is not repeatable, therefore cannot be resolved. High probably, you are still using the short message, so the cube-root attack still works. This is why RSA need a proper padding scheme!
1
Reply
fgrieu avatar
ng flag
fgrieu
Hint: detail what "we have a short message $M$ compared to the public key" exactly means; what it implies about textbook RSA encryption $M\mapsto M^e\bmod N$ w.r.t. raising to the $e$ non-modularly $M\mapsto M^e$; what $C\mapsto C^{1/e}$ is w.r.t. the later, and thus w.r.t. textbook RSA decryption $C\mapsto C^d\bmod N$. Then it will be clear why in the experiment of the last three paragraphs of the question, the same cause "short message" yields that same effect, coming down to the same equality but used in the reverse direction.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.