We know a standard way (cf. RFC 6979) to derandomize ECDSA signatures, i.e., to generate ECDSA signature without an external source of randomness.

Is there any similar standard way, or academic-proof way, to derandomize RSA-OAEP encryption?


Derandomization for asymmetric encryption is a bad idea. Main reason for that is that if an asymmetric encryption mechanism is deterministic, then it allows a brute force attack on the plaintext: the attacker tries possible plaintext messages and encrypts them, and tries to see if it yields the same encrypted message as the one which was observed. Real-world plaintexts usually have much less entropy than cryptographic keys.

Some extra notes:

  • You could use asymmetric encryption only to convey a fully random symmetric key, in which case brute force on the key is not feasible. But then, this means that you have a random source at hand, so OAEP should not be an issue.

  • You could imagine a deterministic process that feeds on an extra secret value, thus not reproducible by attackers. But then, this would not really be "derandomization"; that process and the source secret value would better be described as a custom PRNG, i.e. you are just using normal RSA-OAEP.


Signature schemes don't need to be randomized to be secure. The standard notion for security of a signature scheme is existential unforgeability under adaptive chosen-message attack, EUF-CMA (see, e.g., Goldwasser & Bellare's Lecture Notes on Cryptography, §10.3, p. 170). The adversary is given an oracle that will sign any messages of their choice. The adversary succeeds if they can forge a signature on any message not signed by the oracle.

Security in this sense means there is no such adversary that succeeds with nonnegligible probability. Nothing in this notion precludes deterministic signature schemes: if the oracle returns the same signature for the same message every time, so be it; that doesn't help an adversary to forge a signature on any other message.

The reason to derandomize ECDSA in particular is that in ECDSA, the signer must choose a per-signature secret, which is traditionally chosen randomly at signing time. If the per-signature secret is predictable, the signature leaks the signing key. If the per-signature secret is merely repeated, two signatures also leak the signing key. This was a catastrophically stupid design decision in the original DSA, objections to which by academic cryptographers in the early '90s fell on deaf ears at NIST on NSA's leash, and it took a quarter of a century to persuade the world that using a PRF under the signer's secret key of the message as the per-signature secret was a better idea.

In contrast, public-key encryption is necessarily randomized to match the standard notion of security, which is indistinguishability under adaptive chosen-ciphertext attack, IND-CCA2 (ibid., §7.3, p. 125). This means:

  1. the adversary submits two plaintexts to a challenger who returns the encryption of one of them chosen by a fair coin toss;
  2. the adversary is given an oracle that will decrypt any ciphertext of their choice except the challenge ciphertext (the adversary can also encrypt any plaintext, since the public key is public); and
  3. the adversary succeeds if they can tell which plaintext the challenge ciphertext corresponds to.

Again, security in this sense means there is no such adversary that succeeds with nonnegligible probability. But the encryption must necessarily be randomized because otherwise the adversary could simply re-encrypt the two challenge plaintexts to distinguish which one the ciphertext corresponds to, and succeed with probability 1.

However, there is a much simpler way to do public-key encryption with RSA than RSAES-OAEP. It uses an intermediate public-key key encapsulation mechanism called RSA-KEM, and any symmetric-key authenticated encryption scheme $\operatorname{AE}_k$. Given a message $m$, a public modulus $n$, and a public exponent $e$ (typically $e = 3$, but PTSD from historically bungled application of RSA scares some people away from $e = 3$):

  1. Pick an integer $x$ with $1 < x < n$ uniformly at random.
  2. Compute the secret key $k = H(x)$.
  3. Compute the encapsulation $y = x^e \bmod n$ of the secret key.
  4. Compute the ciphertext $c = \operatorname{AE}_k(m)$.
  5. Transmit $(y, c)$.

Here $H\colon \mathbb Z/n\mathbb Z \to \{0,1\}^{256}$ is a uniform random function, typically instantiated with, e.g., SHA-256. The recipient recovers $x = y^d \bmod n$ with the private exponent $n$, recomputes $k = H(x)$, and recovers (or rejects, if modified) the message $m = \operatorname{AE}_k^{-1}(c)$. Public-key encryption via RSA-KEM is still randomized—as it must be—but it is substantially simpler and easier to understand than RSAES-OAEP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.