RSA Laboratories

RSAES-OAEP Dictionary

Basic Terminology

cryptographic hash function A deterministic function H mapping bit strings of arbitrary length to bit strings of a fixed length such that H is collision-resistant and one-way.

decryption The process of recovering a plaintext from a ciphertext using a private key.

decryption primitive The inverse of the encryption primitive. One example is RSADP.

deterministic A function or algorithm is deterministic if the output is uniquely determined by the input. Compare to randomized.

encoding method A normally randomized operation applied to a message before the encryption primitive is applied. Originally, the most widely employed encoding methods were quite simple padding operations (one example is the method in PKCS #1 v1.5). Nowadays, encoding methods (for example, OAEP) tend to be more sophisticated and are designed with a specific security goal in mind.

encryption The process of transforming a plaintext into a ciphertext using a public key. The encryption process is required to be one-way in the strong sense, and it can be either deterministic or randomized.

encryption primitive Basic mathematical operation on which the encryption procedure is built, normally a one-way function. One example is RSAEP.

hash function See cryptographic hash function.

key pair Consists of a public key and a private key.

mask generation function (MGF) A pseudo-random function taking a bit string of any length (and the desired length of the output) as input and returning a new bit string of desired bit length. In theoretical models, MGFs are treated as random oracles. In practice, mask generation functions are often based on a secure cryptographic hash function such as SHA-1.

private key Private part of the key pair. Only the owner of the key pair is allowed to see the private key. The private key is used to decrypt ciphertexts obtained via encryption of plaintexts with the public key.

public key Public part of the key pair. Anyone is allowed to see the public key. The public key is used to encrypt plaintexts.

public-key encryption scheme Encryption scheme consisting of a public key and a private key.

randomized A function or algorithm is randomized if the output depends not only on the input but also on some random element. For example, the output from OAEP is a function of the input and a random seed. Compare to deterministic.

seed Random input to randomized public-key schemes such as RSAES-OAEP. The ciphertext is uniquely determined by the plaintext and the seed.

RSA Terminology

CRT Stands for Chinese Remainder Theorem. A method for performing the RSADP computation more efficiently. Requires a different representation of the RSA private key than the one described here.

modulus A large integer, normally the product of two large secret primes, denoted n. Part of the RSA public key and the RSA private key.

OAEP Stands for Optimal Asymmetric Encryption Padding. Encoding method taking a message M and returning an encoded message

EM = [ H([P||M] + G(S)) + S ] || [ [P||M] + G(S) ],

where S is a randomly generated seed, P is some padding, and G, H are mask generation functions. M is easily derived from EM, but it is difficult to predict anything nontrivial about EM from M without knowing S. (+ denotes bitwise addition and || denotes concatenation of strings; the length of the output from G is equal to the length of [P||M], while the length of the output from H is equal to the length of S.)

private exponent A large integer denoted d, part of the RSA private key. Satisfies

m = med (mod n),

where e is the public exponent.

public exponent A small integer denoted e, part of the RSA public key. Often a prime close to a power of 2, for example, 3, 5, 7, 17, 257, or 65537.

RSA key pair Consists of an RSA public key and an RSA private key.

RSA private key Private part of the RSA key pair. Consists of the modulus n and the private exponent d. Only the owner of the key pair is allowed to see the private exponent (the modulus is public).

RSA public key Public part of the RSA key pair. Consists of the modulus n and the public exponent e. Anyone is allowed to see the RSA public key.

RSADP The RSA decryption primitive. Takes a ciphertext representative c and outputs a plaintext representative m, where

m = cd (mod n);

n is the modulus and d is the private exponent.

RSAEP The RSA encryption primitive. Takes a plaintext representative m and outputs a ciphertext representative c, where

c = me (mod n);

n is the modulus and e is the public exponent.

RSAES-OAEP Public-key encryption scheme combining the encoding method OAEP with the encryption primitive RSAEP. RSAES-OAEP takes a plaintext as input, transforms it into an encoded message via OAEP and apply RSAEP to the result (interpreted as an integer) using an RSA public key.

Security Concepts

Note that the explanations given in this section are very brief and incomplete. Unless otherwise stated, we consider a public-key encryption scheme consisting of a first step where the message to be encrypted is encoded (e.g., via OAEP) and a second step where an encryption primitive (e.g., RSAEP) is applied to the result. The encoding method consists of one or a few applications of a mask generation function, which we idealize as a random oracle. All security considerations are in a complexity-theoretic sense rather than in an information-theoretic sense.

adaptive chosen ciphertext attack A chosen ciphertext attack where the adversary is allowed to send queries to a decryption oracle before as well as after she is given the challenge ciphertext (except that she is not allowed to ask for the decryption of the challenge ciphertext after she is given it).

adversary Deterministic or randomized algorithm aiming to break a cryptographic scheme or parts of it. (Referred to as feminine on these pages due to the popular interpretation of the adversary as 'Eve' or 'Carol'; for similar reasons, the sender ('Alice') is feminine, while the receiver and holder of the private key ('Bob') is masculine.)

chosen ciphertext attack An attack where the adversary is given access to a decryption oracle. There are two major kinds of chosen ciphertext attacks, adaptive attacks and indifferent attacks. Normally the goal in both these attacks is to find the decryption of a challenge ciphertext, but see also non-malleability.

chosen plaintext attack The most primitive kind of attack where the adversary only knows the public key. Using the public key, the adversary is able to construct as many plaintext-ciphertext pairs as she wants, but she is not allowed to ask for the decryption of ciphertexts. Normally the goal of the attack is to determine the decryption of challenge ciphertext, but see also non-malleability.

collision-resistance A function H is collision-resistant if the task of finding two distinct inputs x and y such that H(x) = H(y) is infeasible.

computationally indistinguishable Two algorithms are computationally indistinguishable if there is no efficient adversary who is able to distinguish between outputs from the two algorithms with better chance than 1/2.

decryption oracle An oracle decrypting ciphertexts for an adversary. It is not always required that the decryption oracle output the correct plaintext, but its outputs must be computationally indistinguishable from the correct outputs. (In particular, if the scheme is deterministic, then the decryption oracle must output the correct plaintext.)

encryption oracle An oracle encrypting plaintexts for an adversary. Such an oracle might appear as pointless, since any reasonable adversary is able to encrypt messages herself. However, in some theoretical models (e.g., consider plaintext awareness), the concept is useful as it allows us to model attack scenarios where an adversary is able to intercept ciphertexts via eavesdropping. In such instances, the adversary does not need any random oracle queries and random seed needed to get messages encrypted - a subtle distinction that may be of crucial importance for the model.

indifferent chosen ciphertext attack A chosen ciphertext attack where the adversary is not allowed to send queries to the decryption oracle after she has been given the challenge ciphertext. This type of attack is sometimes referred to as a "lunch-break" attack.

non-malleability In chosen plaintext and chosen ciphertext attacks, instead of asking for the encryption of a challenge ciphertext, one may ask for new ciphertexts "related" (in a way specified by the adversary) to the challenge ciphertext. For example, the adversary may try to output a new ciphertext such that the bitwise sum of the two underlying plaintexts is equal to a particular (nonzero) value. If any adversary is successful only with a negligible probability, then the encryption scheme is non-malleable ("tamper-resistant"). The concept is related to (but far from equivalent to) plaintext awareness. Trivially, non-malleability implies security against the corresponding ordinary attack (i.e., if an adversary is able to decrypt challenge ciphertexts, then the scheme is vulnerable to this malleability attack as well).

one-way A function or algorithm H, deterministic or randomized, is one-way if the task of inverting it is infeasible. Inverting means finding a solution to an equation of the form H(x) = y in x, where y is randomly chosen. RSAEP is widely believed to be one-way (given that the private key is kept secret), as are well-trusted cryptographic hash functions such as SHA-1. There are stronger notions of one-wayness, for example partial one-wayness.

one-way, partially A concept introduced in reference [3]. A function is partially one-way with respect to some parameter k if the first k bits of the input cannot be determined from the output. The terminology is somewhat confusing, because partial one-wayness is a stronger - not weaker - concept than ordinary one-wayness. A result that is crucial for the security of RSAES-OAEP is that the concepts are equivalent for reasonably large values on k for the encryption primitive RSAEP; see [3].

one-way, stronger notions of Ordinary one-wayness is not sufficient for a cryptographic scheme to be secure; a one-way function may give outputs that leak partial information about the corresponding inputs. For this reason, a stronger notion of one-wayness is often desirable. In such instances, one typically requires that the output do not leak any useful information about the input (other definitions appear in the literature). Encryption schemes and mask generation functions must be one-way in this strong sense, and any reasonably versatile cryptographic hash function should have this property as well. For encryption primitives, however, ordinary one-wayness is sufficient, given that the primitive is combined with an encoding method with certain properties.

oracle A "sub-component" S of an adversary A living its own life independent of the adversary; A interacts with the oracle but cannot control its behavior. Typically, S takes some parameters as input and outputs some other parameters (such as a bit string). For example, S can be a random oracle or a decryption oracle simulating the decryption primitive.

plaintext awareness, strong A concept introduced in [1]. Consider a scheme that is secure against chosen plaintext attacks. We are given an adversary who knows the public key and who is given access to a random oracle and an encryption oracle. All her queries to the random oracle are recorded, as are all outputs from both oracles. The goal for the adversary is to construct a valid ciphertext, but it must not be in the recorded list of outputs from the encryption oracle, and somebody who is given the recorded information along with the public key must not be able to decrypt the ciphertext. If the adversary fails with overwhelming probability, then the scheme is (strongly) plaintext-aware. Plaintext awareness implies security against adaptive chosen ciphertext attacks. Compare to weak plaintext awareness.

plaintext awareness, weak A concept introduced in [2]. Similar to strong plaintext awareness, except that the adversary is not given access to an encryption oracle. In particular, she will have to record more random oracle queries than an adversary in the stronger model in order to get the same amount of information. This difference is subtle but makes the adversary considerably weaker. Weak plaintext awareness implies security against indifferent chosen ciphertext attacks but not against adaptive attacks.

random oracle An oracle taking as input an element and returning a completely random and unpredictable element chosen from a certain set (for example, the set of all possible bit strings of a certain length). If the random oracle is supposed to simulate a deterministic function (such as a mask generation function), then it must output the same element every time it is given a certain input.

Top of Page