# Same message space for different public exponents

What is the weakness, if there is any, of using the same message space for different public exponents (assuming e changes everytime)?

Imagine I have a message space [0,n] where n is a 1024 bit number and several public exponents of 1024 bit each as well, does that somehow have an impact on my RSA system?

Edit: assume I don't have access to n in this scenario (unless "message space" refers to n. However, in this case we assume that the given message space is a composite number with > 6 prime factors)

• Possible duplicate of how to use common modulus attack? Commented Sep 4, 2018 at 10:46
• What do you mean: assume I don't have access to $n$ in this scenario? $n$ is part of each and every public key, so in the end everybody with a public exponent should also have $n$. Without clarification on this I would still consider the question a dupe... Commented Sep 4, 2018 at 11:54
• This is also what confuses me: all I have is the message space and the public exponents, I don't have the modulus. This leads me to think that I'm missing something. Commented Sep 4, 2018 at 12:07
• @S.L. The message space is $\{0,\dots,n-1\}$, so if you know the message space, you know $n$. Commented Sep 4, 2018 at 12:14
• Ahhhhhh! Thank you, that's the answer I was looking for, thank you! Commented Sep 4, 2018 at 12:30

1. a common modulus $n$ shared by multiple public exponents $e$
2. message space $[0,n)$
3. a 1024-bit mosulus $n$ with > 6 prime factors
• Given a private exponent $d$, matching $e$, and $n$, it is possible to factor $n$ (see answers to this). Then, because of 1, it is trivial to find the private exponents for all other $e$, and decipher all cryptograms. This is a disaster if any of the various $d$ falls in the hand of an adversary (including if the various $d$ are held by persons with diverging interests).
• Message space $[0,n)$ of 2 strongly suggests textbook RSA, where encryption of $m$ in the message space is as $c\gets m^e\bmod n$. This is unsafe, in particular because a guess of $m$ can be trivially verified from $c$, $n$, and $e$, which all are assumed available to attackers. That's a disasters for a coin throw, the name of person on the class roll, a credit card number... Proper RSA encryption use random encryption padding, e.g. as in RSAES-OAEP of PKCS#1v2.2, with typically a reduced message space.
• If 1 is combined with textbook RSA, and the same message is sent encrypted under multiple $e$, it can be deciphered without knowing any $d$ or the factorization of $n$ (see this).