As pointed in comment
- "encrypt" with sender's private key is improper terminology; the proper term is sign. I took the liberty to fix that common error in the question. If we used anything else than trapdoor-permutation-based public-key cryptography (RSA, Rabin for the most), "encrypt" with sender's private key would be plain unintelligible.
- It's assumed $n_r>n_s$ so that $c_1<n_r$, which is necessary to get $\widetilde{c_1}=c_1$. Thus the technique won't "work" with 100% reliability in both directions unless we take some precaution.
Also, the issue of padding is ignored. And more broadly the security goals are not stated.
Issue 2 can be solved in a number of ways:
- The best is to use separate keys for signature and encryption, with a maximum $n$ for the first applied (signature in the question) lower than the minimum for the second. That abides to the time-proven security design principle: one usage, one key. It also avoids the embarrassment of ending up with $c_2=m$ when the sender is the receiver, something an adversary might induce.
- Another option is to force all $n$ to share the same bit size and many high order bits (say 512, which become a fixed public arbitrary constant). That insures $c_1<n_r$ with overwhelming probability. It does not solve the send-to-self issue.
- Yet another is to require all $n$ to have the same bit size, restrict to (say) even $m$, and use $c_2\gets\min\bigl(c_1,n_s-c_1)^{e_r}\bmod n_r$. On decryption, we'll end up with either $m=\widetilde{c_2}$ or $m=n_s-\widetilde{c_2}$, and the parity of $m$ allows to determine which (wince $n_s$ is odd). That does not solve the send-to-self issue.
- A small variant of the above forces $m<n_s/2$ (typically by requiring $m$ to fit into two bits less than any $n$), which also allows recovery of $m$.
On the aforementioned padding issue: both RSA encryption and signing require redundancy for security; plus encryption requires random padding (or non-guessable plaintext) in what's processed with textbook RSA encryption. That can be solved by:
- pad $m$ with randomness and redundancy
- sign with textbook RSA using private key $(n_s,e_s)$ [in it's instance for signature, if distinct from encryption]
- encrypt with textbook RSA using public key $(n_r,e_r)$ [in it's instance for encryption].
Proper checking of the redundancy on decryption insures integrity and protects against decryption padding oracle attacks.
Encrypt-then-Sign works as well, and is used in the RSA-based authentication protocol¹ between (pan-)European Digital Tachograph and it's Smart Cards. It uses the $\min$ and even padded message trick.
¹ Designed circa the end of the 20th century, I wish I knew exactly by who. A modern variant would use RSAES-OAEP padding and the $m<n/2$ trick, or best separate encryption and signature keys. It would also use public moduli much larger than 1024-bit, but I was instrumental in not increasing that value (see this) late in the project and causing yet another launch delay. I don't regret that bet: roads would have been rather less than more safe from drivers lacking sleep or over-speeding if Europe had waited 2048-bit RSA gizmos to be available to enforce something better than the old recording disc. As predicted, fraud on the new system ended up focusing elsewhere: pulling the power fuse during part of a long drive (pretending the battery was disconnected to avoid vehicle theft or fire risk to explain the record of that incident), using a magnet on the motion sensor (as an alternate way to stop recording while driving), unscrewing the real motion sensor and stimulating it artificially (to lower the recorded speed), somewhat getting the calibration factors off (to the same effect), drivers getting hold of two cards (doubling their driving allowance), plain not introducing their card, or purposely using old trucks (without the new Digital Tachograph mandated).
