Date: Mon, 17 Aug 1992 13:15-EDT
From:
Marc(_dot_)Ringuette(_at_)DAISY(_dot_)LEARNING(_dot_)CS(_dot_)CMU(_dot_)EDU
Sender: pem-dev-relay(_at_)TIS(_dot_)COM
I recently came across the following in some notes from a cryptography
lecture. I wonder if it has been properly dealt with in the PEM procedures?
A somewhat more serious potential hazard for RSA can occur when
the same message is sent more than e times using different N's,
where e is the public exponent used for the encryptions. Say we
send message M three times using exponent e=3, sending M^3 mod N1,
M^3 mod N2, and M^3 mod N3. In general we expect these values to
be relatively prime. But then the Chinese Remaindering Theorem
tells us that we can find M^3 mod N1 * N2 * N3, which is just M^3.
So taking an integer square root of this quantity gives the message!
Hopefully the danger is obvious: when sending a message to multiple
recipients, the natural thing to do is to encrypt the session key several
times, once for each recipient. But if three recipients all are using public
exponent 3, or in general e recipients use exponent e, then the message is
compromised.
There are some obvious fixes. One is to prohibit the use of small e's, and
another is to prohibit sending a message to more than one recipient. The
third, and my preference, is to require as part of the protocol that the
sender append some random bits to the session key before each encryption,
with different random bits for each recipient.
The later (appending different random bits to the session key) is what is
done in the implementation I work with...
-Jeff