In a group of 16 people, everyone has an RSA key pair and all public keys are known. They agree that the code $m = 1234$ means "shall we go for a drink after class?". Rolf sends $m = 1234$ to Ruth with textbook RSA. If 15 people each sent Ruth this message, how many different ciphertexts would she get? Can the others read it? Does Ruth know the sender? How should Rolf fix this?
Ruth gets one ciphertext 15 times. The others can recognise it without decrypting, and Ruth cannot tell who sent it. Rolf must sign the message and use randomised padding.
a) How many ciphertexts? Just one. Everyone encrypts with Ruth's public key $(N_R, e_R)$, and textbook RSA is deterministic, so $1234^{e_R} \bmod N_R$ is the same for every sender.
b) Can the others read it? They cannot decrypt it, because they lack Ruth's private key. But they don't need to: anyone can compute $1234^{e_R} \bmod N_R$ with the public key and compare. Whenever that value shows up on the wire, they know exactly what was asked.
c) Does Ruth know the sender? No. Encryption with a public key proves nothing about the sender, since everyone holds that key.
d) The fix:
- Randomised padding (OAEP) before encrypting, so the same message gives a different ciphertext every time and the guess-and-compare trick fails.
- A digital signature with Rolf's private key, so Ruth can verify the message really comes from him.
Lesson: public-key encryption alone gives neither semantic secrecy for small, guessable message spaces nor sender authenticity.