1
$\begingroup$

Consider a multi party system where public keys of all receivers are known. Server wants to send message to one of them using (textbook?) RSA. Adversary is given ciphertext and even Message to be send, and all $k$ public keys of participants. Can any attack tell who is the target receiver?

Or in nutshell: Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Editor's note: The textbook RSA part is per OP's comment. It was originally plaintext RSA. Alternatively, the question makes (more?) sense with some random encryption padding.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ The question is hard to understand. One reason is it is a single long sentence. I strongly recommend to break it down. Also, what's "plaintext RSA"? Is that textbook RSA, where encryption of message $M$ is directly as $C=M^e\bmod n$? In which case it's trivial to match a pair $(M,C)$ with a public key $(n,e)$. Things are more complex with RSA using proper encryption padding, e.g; RSAES-OAEP, especially if public moduli $n$ share their high-order bits. $\endgroup$
    – fgrieu ♦
    Commented May 4, 2021 at 3:11
  • $\begingroup$ @fgrieu yes it is textbook RSA and yes $C=M^e\bmod n$ but it is not trivial to match M , C with (n,e) because k may be exponential ....there are k public keys for k recipients here, hope i made myself clear $\endgroup$
    – Sam
    Commented May 4, 2021 at 4:07
  • $\begingroup$ "$k$ may be exponential" is strange. It's a given, thus it's constant, thus not exponential. And the work for the trivial attack (assuming textbook RSA and known $m$) is linear with $k$ (not even polynomial, much less exponential). Are you sure it's textbook RSA (with no random padding) and $M$ is known? That does not seem to make sense. $\endgroup$
    – fgrieu ♦
    Commented May 4, 2021 at 5:49
  • $\begingroup$ @fgrieu i am sure it is textbook RSA and M is given to adversary and you may be right in order k time he can find out as he just need to make table for all participants on input m and their public key but i still doubt on limit ok k. Can you propose another attack if k is exponential in security parameter to know e value of targeted receiver or can you refer me some text to refer. $\endgroup$
    – Sam
    Commented May 4, 2021 at 6:22
  • 2
    $\begingroup$ Does this answer your question? Is it possible to recover an RSA modulus from its signatures? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented May 5, 2021 at 22:26

1 Answer 1

Reset to default
1
$\begingroup$

Given $C$, $M$ and all $k$ public keys, can an attacker tell with significant probability which public key was used to encrypt $M$ giving $C$ ?

Well, he can eliminate some of the possibilities (which means with $k=2$, he has a decent chance at finding the correct one).

There are two observations he can use:

  • He can eliminate all public keys $K_i$ for which $C \ge K_i$. This is pretty obvious, but (if he is lucky) might eliminate some.

  • For each public key $K_i$, he can compute the Jacobi Symbols $\left( \frac{M}{K_i}{} \right)$ and $\left( \frac{C}{K_i}{} \right)$; if they differ, then he knows that $K_i$ is not the correct key.

This works because we're assuming textbook RSA, and textbook RSA always preserves the Jacobi symbol (which can be efficiently computed). For an incorrect key, this test will disqualify it with probability circa 0.5, and so about half the incorrect ones will be eliminated.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I wonder starting with what $e_i$ performing the Jacobi test has an advantage compared to the obvious: for all moduli $K_i$ with $K_i>C$, test if $M^{e_i}\bmod K_i=C$. $\endgroup$
    – fgrieu ♦
    Commented May 6, 2021 at 17:06
  • $\begingroup$ @fgrieu: doh! Sorry, I missed the completely obvious... $\endgroup$
    – poncho
    Commented May 6, 2021 at 17:33
  • $\begingroup$ Still, for some threshold of $e_i$, the Jacobi test might save time. $\endgroup$
    – fgrieu ♦
    Commented May 6, 2021 at 17:34
  • $\begingroup$ @fgrieu: don't think so; for practically sized $e$ (say, 65537), computing $M^e \bmod K_i$ would actually be faster than Jacobi... $\endgroup$
    – poncho
    Commented May 6, 2021 at 17:35
  • $\begingroup$ I checked, and in my test with Mathematica the threshold is like 200-bit $e$, give or take, for a possibly improved test that $\left( \frac{M\,C}{K_i}{} \right)=+1$. Still it's a nice idea. $\endgroup$
    – fgrieu ♦
    Commented May 6, 2021 at 18:12

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.