We need clear goals. The question asks for "plausible deniability" or "deniable encryption", and these terms needs a precise definition in a public-key context (implied by RSA). I assume that in addition to the IND-CPA and IND-CCA1 properties of a cipher, including hybrid (as implied by AES), it is desired that:
One without the private key can't distinguish ciphertext from random data of the same length (with the exception of data too small to be correct ciphertext considering the key size).
One trying to decipher ciphertext with the wrong private key get random-like output and no error message (with the exception of ciphertext too small to be correct ciphertext considering the key size).
Even one with the private key can not distinguish from random the ciphertext obtained by encryption with the corresponding public key of unknown random data.
I think these goals are orthogonal. (1) is most natural; (2) helps leaving interceptors clueless; (3) is useful in a context of layered encryption. The whole gives some useful level of deniability in societies where possessing random files and encryption programs designed for deniability is not objectionable.
I propose a simple scheme that I claim meet the above goals. It is close to the simplest possible form of hybrid RSA/AES encryption: use a random key to AES-encipher the bulk of the data, and use RSA to encipher that key. The only difficulty is making sure we do not leave a bias here or there. In particular, usual RSA primitives have their ciphertext with some bits biased, sometime constant, failing (1); and with the right private key, they often reveal more structure, failing (3).
The key setup is that of RSA. Users have private keys $(N,d)$, and all the corresponding public keys $(N,e)$ are made public. $n$ is the bit size of $N$, so that $2^{n-1}\le N<2^n$. I restrict to plaintext, ciphertext, and more generally data or files that are a contiguous collection of octets. Ciphertext always is exactly $\lceil(n-1)/8\rceil$ octets longer than the plaintext. Big-endian binary is used in all conversions between octets and integer.
Symmetric encryption is done using AES-128 for $128<n\le2049$, AES-192 for $2049<n\le4097$, AES-256 for $n>4097$.
The encryption procedure accepts a public key $(N,e)$ and plaintext:
- repeat the following steps..
- generate $M$ uniformly random in $\{0\dots N-1\}$;
- compute $C=M^e\mod N$, which is textbook RSA encryption;
- ..until $C<2^{n-1}$ [notes: here $C$ is uniformly random in $\{0\dots2^{n-1}\}$; in the context, the end condition means that $C$ fits in $n-1$ bits; it will take on average less than two iterations to get there];
- generate $a$ uniformly random in $\{0\dots2^{7-((n-2)\bmod8)}-1\}$ [note: in other words, generate $a$ of
7-((n-2)%8) random bits];
- let $A=a\cdot 2^{n-1}+C$ [note: that concatenates $a$ and $C$ for a total of $8\cdot\lceil(n-1)/8\rceil$ bits, when considering $a$ and $C$ as bitstrings of fixed sizes $7-((n-2)\bmod8)$ and $n-1$ bits];
- output $A$ as $\lceil(n-1)/8\rceil$ octets;
- let the low-order bits of $M$ be the AES key of the size determined by $n$;
- encipher the plaintext (if any) in AES-CTR mode with implicit zero IV, and output it.
The decryption procedure accepts a private key $(N,d)$ (possibly in another form) and data that is a putative ciphertext:
- read the first $\lceil(n-1)/8\rceil$ octets of data, forming an integer $A$ of (at most) $8\cdot\lceil(n-1)/8\rceil$ bits; if there is not enough data, terminate with error or hang;
- compute $C=A\bmod(2^{n-1})$ [note: that forms $C$ by ignoring the high-order $7-((n-2)\bmod8)$ bits of $A$, considered as a bitsring of $8\cdot\lceil(n-1)/8\rceil$ bits];
- compute $M=C^d\mod N$, which is textbook RSA decryption;
- let the low-order bits of $M$ be the AES key of the size determined by $n$;
- decipher the rest of the data (if any) using AES-CTR mode with implicit zero IV, and output it.
I do not support encryption to multiple users (a common feature of hybrid encryption), or checking that the plaintext or ciphertext is unaltered, which are antagonist with the combination of the goals.
I make no attempt to hide the length of the original data (adding some level of this is simple: for example, before encryption, append 0 to 255 random octets, and a final octet coding the random number of random octets added, which will allow removing the appropriate number of octets on decryption; goals need minor refinements).
UPDATE: I have made IND-CPA and IND-CCA1 explicit goals. IND-CCA2 is not met. Worst problem is that the cipher is extremely malleable, including to one not knowing which public key was used, and that's a weakness: an adversary guessing the plaintext (e.g. from context and ciphertext length) can replace it with another ciphertext that will decipher to any plaintext of her choice that is not longer than the original, without knowing which key is used (with knowledge of the public key, anything can be enciphered, of course). Another weakness is that the size overhead depends on the key size, and is higher than strictly necessary. It seems all this can be fixed, but with two passes for decryption and added complexity.
