1
$\begingroup$

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)

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of how to use common modulus attack? $\endgroup$ – fkraiem Sep 4 '18 at 10:46
  • 1
    $\begingroup$ 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... $\endgroup$ – Maarten Bodewes♦ Sep 4 '18 at 11:54
  • $\begingroup$ 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. $\endgroup$ – S. L. Sep 4 '18 at 12:07
  • $\begingroup$ @S.L. The message space is $\{0,\dots,n-1\}$, so if you know the message space, you know $n$. $\endgroup$ – fkraiem Sep 4 '18 at 12:14
  • $\begingroup$ Ahhhhhh! Thank you, that's the answer I was looking for, thank you! $\endgroup$ – S. L. Sep 4 '18 at 12:30
1
$\begingroup$

The RSA system in the question uses

  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

This leads to security issues:

  • 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).
  • The 1024-bit key size of 3, although seriously obsolete, would remain extremely hard to attack with 2 or 3 factors of about equal size. But with at least 7 factors, one must be 147-bit or less, and ECM can pull it out with little effort.
|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.