Classical Public-Key, Advanced · 2 of 6
From Raw RSA to OAEP and PSS
Bare RSA arithmetic is correct but unsafe. Here is what goes wrong, how OAEP and PSS padding fix it, and the implementation details that still decide whether they hold.
RSA's arithmetic is beautifully simple: raise a number to one power to lock it and to another to unlock it. That simplicity is exactly why nobody should use it directly. Feed the bare arithmetic a message and it will lock it the same way every time, let a stranger rearrange the locked value into a related one, and sometimes barely hide the message at all. For three decades, real systems have wrapped RSA in padding, a carefully designed way of turning a message into a number before the arithmetic runs. The first padding scheme turned out to leak secrets through its error messages; its successors, the Optimal Asymmetric Encryption Padding (OAEP) for encryption and the Probabilistic Signature Scheme (PSS) for signatures, were designed with security arguments behind them. This article starts from the raw arithmetic, shows its failures with numbers you can check, walks through how each padding scheme works and why, and ends with the decisions that matter in practice, including for artificial intelligence (AI) agents that sign tokens, verify tool manifests and unwrap keys.
Textbook RSA works, and that is the problem
RSA, named after Ron Rivest, Adi Shamir and Leonard Adleman, uses clock arithmetic, also called modular arithmetic, where every result wraps around a fixed number called the modulus and only the remainder is kept. Take a toy key with modulus 55, public exponent 3 and private exponent 27. Encrypting a message number means raising it to the 3rd power on the 55-position clock; decrypting means raising the result to the 27th power. The message 7 becomes 13, and 13 becomes 7 again. Using this arithmetic directly, with no preparation of the message, is called textbook RSA.
Textbook RSA has three properties that would each be fatal in a real system. First, it is deterministic: the message 5 encrypts to 15 today, tomorrow and on every machine. Anyone who suspects the message is one of a few values, such as yes or no, or a price from a short list, can encrypt each guess with the public key and compare. Second, it is malleable: multiplying two ciphertexts multiplies the messages inside them. The encryption of 2 is 8 and the encryption of 7 is 13; multiply 8 by 13 and wrap at 55 to get 49, and 49 decrypts to 14, which is 2 times 7. An attacker can transform a locked message into a related locked message without ever unlocking it.
Third, small messages may not be hidden at all. The message 3 cubed is 27, which never reaches 55, so the clock never wraps, and anyone can take an ordinary cube root of 27 to get 3 back. At real sizes the same thing happens whenever a short message, such as a 16-byte key, is cubed without padding: the result stays far below a 2,048-bit modulus, and the cube root is easy. None of these failures breaks the hard problem RSA is built on. They are failures of use, and padding exists to close them.
What a secure encryption scheme must promise
Cryptographers state the goal precisely. An encryption scheme should be semantically secure: a ciphertext should reveal nothing useful about the message, even to an attacker who chose the candidate messages. That immediately rules out determinism, because comparing encryptions of guesses would reveal which guess was used. So every encryption must include fresh randomness, and the same message must produce a different ciphertext each time.
The stronger and more realistic goal is security against chosen-ciphertext attacks, usually written IND-CCA2, for indistinguishability under adaptive chosen-ciphertext attack. It assumes the attacker can submit modified ciphertexts to the system and observe what happens, which is exactly what a server does when it tries to decrypt whatever arrives on the network. Malleability defeats this goal, because an attacker can submit a transformed version of a target ciphertext and learn from the reply. A padding scheme therefore has to do two jobs at once: inject randomness, and add enough structure that any tampered ciphertext is rejected instead of decrypting to something meaningful.
Padding is not a cosmetic layer around the mathematics. It is the part that turns a trapdoor function, an operation that is easy forward and hard backward without a secret, into an encryption scheme with a security argument.
PKCS #1 v1.5: the first padding and its talkative errors
The first widely deployed padding came from the Public-Key Cryptography Standards number 1 (PKCS #1), version 1.5, published by RSA Laboratories in the early 1990s. Its encryption format is simple to describe. The padded block starts with a zero byte and a byte with value 2, followed by at least eight random nonzero bytes, then a zero byte as a separator, then the message. The random bytes give each encryption fresh randomness, which fixes determinism and the small-message problem.
The weakness is in what happens on decryption. A receiver that unlocks a ciphertext must check that the result starts with 0 and 2 and contains a separator. If the receiver tells the sender, in any way, whether that check passed, through a different error message, a different response time or a different follow-up behaviour, it is answering a yes-or-no question about the hidden number. In 1998 Daniel Bleichenbacher showed that an attacker who can ask that question many times, each time submitting a cleverly modified version of a captured ciphertext, can gradually narrow the possible message down to a single value. The original attack needed on the order of a million queries, which is why it is often called the million-message attack.
The lesson was not that the padding format is broken in isolation, but that its decryption check is extremely hard to implement without leaking. Two decades later, in 2018, researchers presenting the Return Of Bleichenbacher's Oracle Threat (ROBOT) found that a number of widely used servers still leaked the check in subtle ways. That is why newer protocols stopped relying on this format for encryption.
OAEP: two masks and a check
Optimal Asymmetric Encryption Padding (OAEP) was proposed by Mihir Bellare and Phillip Rogaway in 1994 and later standardised in PKCS #1 version 2. It uses a cryptographic hash function, a function that turns any input into a short fixed-size fingerprint, and a mask generation function, which stretches a short input into a long pseudo-random stream. The standard mask generation function, MGF1, is built by hashing its input together with a counter.
Encoding works in a few steps. First the sender builds a data block: the hash of an optional label, a run of zero bytes, a single byte with value 1 as a marker, and then the message. Next the sender picks a fresh random seed the length of one hash output. The seed is stretched by MGF1 into a mask that scrambles the whole data block, and the scrambled data block is then stretched into a second mask that scrambles the seed. The final encoded message is a zero byte, the masked seed and the masked data block, and only then is the RSA power applied.
The structure gives OAEP its properties. Because the seed is random, every encryption looks different. Because every bit of the output depends on every bit of the seed and the message through the two masks, flipping any bit of a ciphertext scrambles the whole decoded block, so a tampered ciphertext almost never decodes to a block with the right label hash, zero run and marker byte. The receiver reverses the masks and rejects anything whose structure is wrong. Under the idealised assumption that the hash behaves like a random function, known as the random oracle model, RSA-OAEP has been proved secure against chosen-ciphertext attacks.
The structure also costs space. With a 2,048-bit key, which is 256 bytes, and the SHA-256 hash, whose output is 32 bytes, the longest message OAEP can carry is 256 minus twice 32 minus 2, which is 190 bytes. That is plenty for what RSA encryption should carry in practice: a randomly generated symmetric key that then encrypts the real data.
Implementing OAEP decryption safely
OAEP's security argument assumes the receiver gives an attacker no information beyond accept or reject, and ideally not even a distinction between different kinds of reject. That assumption can still be broken in code. In 2001 James Manger showed that if an OAEP implementation reveals whether the first byte of the unlocked number is zero before it checks anything else, for example by returning a different error or taking a different amount of time, an attacker can again recover a message with a modest number of queries.
So the rule for decryption is the same one that PKCS #1 version 1.5 taught, applied with more discipline. Perform every check, then report a single generic failure regardless of which check failed, and take the same amount of time either way. The standard itself warns implementers to make the different error conditions indistinguishable. Mature libraries do this; hand-written decoders frequently do not.
OAEP is also meant to be used inside a hybrid design. RSA encryption is slow and carries at most a couple of hundred bytes, so the usual pattern is to generate a fresh symmetric key, encrypt the data with an authenticated symmetric cipher such as the Advanced Encryption Standard in Galois/Counter Mode (AES-GCM), and use RSA-OAEP only to wrap the symmetric key. Many cloud key management services expose exactly this operation, often called key wrapping.
Signatures: from hash-and-sign to PSS
Signing with RSA runs the arithmetic the other way: the signer applies the private exponent to an encoding of the message's hash, and anyone verifies by applying the public exponent and checking that the encoding is right. The encoding matters just as much as for encryption, because raw RSA signatures are malleable too. Multiplying two raw signatures produces a valid signature on the product of the two messages, so an attacker who collects a few signatures can manufacture new ones.
The PKCS #1 version 1.5 signature format pads the hash deterministically: a zero byte and a byte with value 1, a long run of bytes with value 255, a zero byte, and then a short header naming the hash algorithm followed by the hash itself. No practical attack is known against this format when it is verified correctly. In 2006, however, Bleichenbacher showed that verifiers which parsed the format loosely, without checking that the hash sits exactly at the end with nothing left over, could be fooled into accepting forged signatures when the public exponent was 3. The safe way to verify is to rebuild the expected encoding from the message and compare it byte for byte, rather than parsing the signature's contents.
The Probabilistic Signature Scheme (PSS), also designed by Bellare and Rogaway, adds a random salt to each signature. The signer hashes the message, hashes that together with the salt, and uses the result to mask a block containing the salt, ending the encoding with a fixed trailer byte. Because the salt is fresh, signing the same message twice gives two different valid signatures, and the scheme comes with a tight security proof in the random oracle model. RFC 8017, the current PKCS #1 specification, calls for PSS in new applications and keeps the version 1.5 signature format for compatibility with existing systems.
Thirty years of lessons in one timeline
Laid out in order, RSA's padding history reads like a slow migration away from formats whose correctness depended on perfect implementations. Each attack on the list exploited a gap between what the specification said and what deployed code actually checked or revealed.
The timeline also shows why the migration took so long. Systems that must interoperate keep old formats alive for compatibility, and every compatibility path is a place where an old oracle can survive. Transport Layer Security (TLS) version 1.3, published in 2018, finally removed RSA key transport altogether, so a TLS 1.3 server never decrypts anything with RSA, and it requires PSS for RSA signatures in the handshake. Many other systems, from token formats to file encryption tools, still offer the older choices, so engineers have to choose deliberately.
Decisions for practitioners and AI agents
For new designs the choices are clear. Encrypt with RSA-OAEP, using SHA-256 for both the hash and the mask generation function, and only to wrap symmetric keys. Sign with RSA-PSS, with a salt as long as the hash. Keep PKCS #1 version 1.5 encryption out of anything that decrypts attacker-supplied data, and if a legacy system forces it, use a library that implements the decryption check without leaking. Where version 1.5 signatures must still be accepted, verify by re-encoding and comparing, never by loose parsing. In every case, use a mature library rather than assembling padding by hand.
AI agents meet these choices constantly, often without anyone noticing. JSON Web Tokens (JWT), the signed tokens that carry an agent's identity and permissions between services, name their algorithm in a header: RS256 means RSA with version 1.5 signatures, PS256 means RSA-PSS, and the JSON Web Algorithms specification marks the older encryption option RSA1_5 as not recommended in favour of RSA-OAEP. An agent platform that verifies tokens or signed tool manifests should pin the algorithms it accepts rather than trusting whatever the header claims, because algorithm confusion is a recurring source of forged tokens.
Code assistants deserve the same scrutiny. Asked for quick RSA encryption, an assistant may reach for a 'no padding' mode or for the version 1.5 default of an older library. The code will run and the round trip will work, which is exactly why the flaw survives review. Treat any RSA call without an explicit OAEP or PSS choice as a defect, and route key-wrapping and signing through a key management service or hardware security module, a device that performs private-key operations without exporting the key, so the agent never handles raw private keys at all.
- Encrypt with RSA-OAEP and SHA-256, and only to wrap symmetric keys.
- Sign with RSA-PSS; verify version 1.5 signatures by re-encoding.
- Return one generic error, in constant time, for every decryption failure.
- Pin accepted token algorithms; never trust the header alone.
- Reject any RSA code path without explicit padding.
Key takeaways
- Textbook RSA is deterministic, malleable and can leave short messages unhidden, even though it decrypts correctly.
- Secure encryption needs fresh randomness and structure that makes tampered ciphertexts fail, which is the job of padding.
- PKCS #1 version 1.5 encryption leaks through its decryption check, as Bleichenbacher showed in 1998 and ROBOT showed was still common in 2018.
- OAEP masks a random seed and a structured data block against each other, has a chosen-ciphertext security proof, and still needs uniform, constant-time error handling.
- PSS adds a random salt to signatures and is required for new applications by RFC 8017; version 1.5 signatures must be verified by re-encoding, not loose parsing.
- AI agent platforms should pin token and manifest algorithms, prefer PS256 and RSA-OAEP, and treat any unpadded RSA call as a defect.
Glossary
- Textbook RSA
- RSA arithmetic applied directly to a message with no padding, which is correct but insecure.
- Malleable
- Describes a scheme whose ciphertexts or signatures can be transformed into valid related ones without the key.
- Semantic security
- The property that a ciphertext reveals nothing useful about its message, which requires randomised encryption.
- Chosen-ciphertext attack
- An attack in which the adversary submits modified ciphertexts for decryption and learns from the responses.
- Padding oracle
- Any observable difference in how a system handles valid and invalid padding, which an attacker can query to recover secrets.
- OAEP
- Optimal Asymmetric Encryption Padding, which masks a random seed and a structured block before RSA encryption.
- PSS
- The Probabilistic Signature Scheme, which adds a random salt and masking to RSA signatures.
- Mask generation function
- A function that stretches a short input into a long pseudo-random stream, used by OAEP and PSS.
- Random oracle model
- An idealised assumption that a hash function behaves like a truly random function, used in many security proofs.