Why is textbook RSA - treating the message as an integer and raising it to the public exponent modulo n with no padding - insecure even when nobody can factor the modulus? Name the property that randomized padding restores.

## The asymmetry in the threat model With symmetric encryption an attacker who wants to test a guess must persuade the system to encrypt for them. With public-key encryption they hold the encryption key already. Every property that depends on the attacker not being able to encrypt is therefore void by construction. This is why padding is mandatory rather than a hardening extra. ## Attack one: guess and compare Deterministic encryption preserves equality. If the plaintext space is small or predictable - an approve/reject decision, a numeric identifier, a national ID, a one-time code, a card number with a known prefix and check digit - the attacker enumerates candidates, encrypts each with the public key, and matches. Even over large spaces, equality leakage alone is damaging: identical ciphertexts prove identical plaintexts, so patterns across records are visible without any decryption. The same equality leak makes deterministic tokenisation and naive block-by-block encryption unsafe; what is peculiar to the asymmetric setting is that the attacker needs nothing from you to exploit it. ## Attack two: algebraic structure Raw RSA is homomorphic under multiplication: multiplying two ciphertexts yields the encryption of the product of the plaintexts. An attacker can therefore transform a ciphertext into a related one with a predictable effect, which is malleability - an integrity failure, not just a confidentiality failure. Small-exponent cases are worse still: if the message raised to a small public exponent is smaller than the modulus, there is no modular reduction and an ordinary integer root recovers the plaintext. ## The property, stated precisely Semantic security, formalised as indistinguishability under chosen-plaintext attack, says an adversary who picks two plaintexts cannot tell which one a ciphertext corresponds to, even holding the public key. No deterministic scheme can satisfy it, because the adversary simply encrypts both candidates. So the scheme must inject fresh randomness per operation, from a cryptographically secure source. A modern padding scheme mixes the message with random bytes through hash-based masking so the encoded value is spread across the whole modulus width, killing both the equality leak and the small-message shortcut. The stronger target is indistinguishability under chosen-ciphertext attack, which additionally requires that access to a decryption service teaches the attacker nothing. ## The decryption side is half the problem A padded scheme is only as strong as the way failure is reported. If a service distinguishes 'padding malformed' from 'padding fine but content rejected' - by error code, log line, response time or response length - an attacker who can submit chosen ciphertexts learns one bit per query and can iteratively recover a plaintext without ever obtaining the private key. That is the classic padding-oracle shape against older padding formats. The defences are structural: use a padding construction designed to resist chosen-ciphertext attack, return a single indistinguishable failure for every reason, branch and compare in constant time, and rate-limit and monitor the decryption endpoint. Constant-time comparison matters because an early-exit byte comparison leaks how many leading bytes were correct, converting a search over the whole space into a search one byte at a time. ## The transferable rule Encryption alone is not a safe interface. Any decryption service is an oracle whose observable behaviour - including its errors and its timing - is part of the cryptosystem. Design the failure path with the same care as the algorithm choice.