Chain several RSA encryptions without increasing the message size I would like to be able to encrypt the output of RSA with RSA again without having the output grow in size over time.

In other words, I have some data $D_0$ which I want to encrypt with RSA: $D_1 = \mathrm{RSAencrypt}_{K_1}(D_0)$. Then, I would like to be able to encrypt $D_1$: $D_2 = \mathrm{RSAencrypt}_{K_2}(D_1)$, and so on, until $D_n = \mathrm{RSAencrypt}_{K_n}(D_{n-1})$. I want the successive messages not to grow in size: $|D_1| = |D_2| = \ldots = |D_n|$.

Since I obviously want the process to be secure, I suppose I should use some padding. It actually works with RSA_NO_PADDING but as soon as I add some padding, the output is the maximum size which is too large for adding padding for a next round of $\mathrm{RSAencrypt}$.

I was wondering if there was a way to make sure the output does not exceed the size required for another encrypt (e.g modulus - 11), through a specific padding for instance.



I am going to try to explain better what I am trying to accomplish. I've read a paper (http://research.microsoft.com/pubs/102086/key_regression.pdf) about key rotation which consists in taking a RSA key, $K$, and rotate a number $N$: $\mathrm{encrypt}_K(N_0) = N_1$, $\mathrm{encrypt}_K(N_1) = N_2$, etc. I'm basically trying to implement it.

At every step, one can deterministically determine an information based on the number $N_x$.

Now given the RSA key pair, we can imagine the owner keeping the private key which is used for rotating $N$ while the public key is disclosed to a set of users.

Any of those users could therefore derive the previous versions of $N$ by applying $\mathrm{decrypt}_K(N_x) = N_{x-1}$. One would however be unable to determine the future versions of $N_x$ since only the owner of the private key is capable of rotating $N$.

Hope it helps clarifying the use case :)
In this scenario, you don't need to do any padding (except for the first encryption).

If what you're encrypting with RSA is a random number between 0 and the modulus size, then you don't need any padding.  Padding is there to prevent the attacker from using the multiplicative properties of RSA to derive one plaintext from a bunch of others; this attack involves finding smooth plaintexts.  When a plaintext is a random number from the full range, this is unlikely to ever happen, and so we don't need to worry about it.

Note that, unless the original message (D0) is also a random number between 0 and N-1, you'll want to pad that.

In addition, in the decrypt direction, doing multiple decryptions can be done far more efficiently than applying each decryption in succession; you could actually apply (say) 1,000,000 successive decryptions almost as efficiently as you can do one.

On the other hand, it is not at all clear what you hope to gain from this procedure.  What is the problem you are solving?