# 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 :)

-
If you want any kind of suggestion about what would be secure to do, you have to explain exactly why you want to RSA encrypt some RSA cipher text. If I may guess you are either trying to invent some kind of counter signature scheme, or are using RSA in a block chaining mode, in both cases for which there are other recommended practices. – Henrick Hellström Apr 20 '13 at 11:09
I do not think I am trying to use RSA in a block chaining mode, at least the purpose is not to increase the security of the scheme. What I want to do is simply to be able to encrypt(encrypt(encrypt(x))) = y so that I can later do decrypt(decrypt(decrypt(y))) = x without y growing. Sorry I'm not an expert hence do not know about counter signature schemes. – user2301771 Apr 20 '13 at 12:47
Is the RSA key in each iterated encrypt operation the same, or are they different? – poncho Apr 20 '13 at 13:16
The same key is used for every iteration, say K: K.encrypt(K.encrypt(x)) = y, then, with the private key (or the other way around), K.decrypt(K.decrypt(y)) = x. – user2301771 Apr 20 '13 at 13:17
@user2301771: Sorry, but you still haven't explained why you are asking (which IMO is important in order to give an adequate reply). Is it out of purely theoretical-mathematical interest, or is this something you actually want to do in practice? In the latter case, why? – Henrick Hellström Apr 20 '13 at 13:29

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?

-
I have edited the question above. – user2301771 Apr 20 '13 at 15:09
As I explained in the question, rotating keys in one of the use cases (see the URL to the paper for instance). – user2301771 Apr 20 '13 at 16:32
Indeed it is not required to rotate with the same RSA key as long as the derivation complies. However, in practice, it is often the case as one wants to rotate N with its own RSA key. Is it problematic to rotate with the same key without padding? – user2301771 Apr 21 '13 at 12:42
@poncho: You mentioned the fact that the decryption process could be performed far more efficiently than a succession of RSA-decrypt(). Could you tell us more about that? – user2301771 Apr 23 '13 at 14:50
@user2301771: well, yes I could, however I don't know if it'd fit within a comment. However, the summary is that if RSA decryption is $C^d \bmod N$, then RSA decryption k times is $C^{d^k} \bmod N$, and if you know the factorization of $N$, you can actually do $C^{d^k \bmod lcm(p-1, q-1)} \bmod N$, which is the same, and is a lot cheaper to compute. If you want details, open a new question. – poncho Apr 23 '13 at 15:28

I take the question as: how to make a chain of RSA encryptions with distinct public keys $(N_j,e_j)$, that is $D_{j+1}=\operatorname{RSA-encrypt}((N_j,e_j),D_j)$, without having the ciphertext size growing at each encryption?

I'll use two facts:

1. When plaintext $x$ behaves to an adversary about as a uniform non-negative random number less than some bound $B$ with $N/2<B\le N$, textbook RSA encryption $x\mapsto x^e\bmod N$ is safe; no padding is required. Assumptions include that $x$ can not be chosen or influenced by an adversary, and that the adversary has no access to a decryption oracle leaking if a chosen ciphertext deciphers to something less than $B$ (note: the $N/2$ bound for $B$ is very conservative: I do not know an attack for $B=N^{0.35}$, and would be willing to assume $B=N^{0.7}$ is safe).
2. When RSA encryption (textbook or otherwise) is used safely, the ciphertext $x^e\bmod N$ is indistinguishable from a uniform non-negative random number less than $N$ to the adversary.

This suggests to have $N_{j+1}/2<N_j\le N_{j+1}$, so that we can safely chain encryptions using textbook RSA, for all but the first encryption: $D_{j+1}={D_j}^{e_j}\bmod N_j$, for $j>0$.

The first encryption requires special care: if the plaintext $D_0$ has bit size $|D_0|$ suitably smaller than $|N_j|$, the simplest is to use one of the RSAES random padding schemes of PKCS#1. If not, we can use an hybrid encryption scheme, which result will consist in $D_1$ which is an RSA-encrypted random key (possibly embedding part of $D_0$, though this is uncommon); and $D'_1$ which is a conventionally-encrypted ciphertext (we'll leave $D'_1$ unchanged in later encryptions, and chain encryptions on $D_1)$.

It is easy to generate public keys matching $N_{j+1}/2<N_j\le N_{j+1}$: simply choose the bit size $n$ of the $N_j$, say $n=4096$, and generates the $N_j$ in suitable ranges: narrow, non-overlapping, and increasing with $j$, such as: $\big[2^n-\lfloor2^{126}/\pi-j\rfloor\cdot2^{n-128}\dots2^n-\lfloor2^{126}/\pi-1-j\rfloor\cdot2^{n-128}\big]$; towards this, choose one prime $P_j$ as usual in RSA key generation (e.g. in range $\big[2^{(n-1)/2}\dots2^{n/2}\big]$), then the other prime $Q_j$ with an additional restriction to range $\big[(2^n-\lfloor2^{126}/\pi-j\rfloor\cdot2^{n-128})/P_j\dots(2^n-\lfloor2^{126}/\pi-1-j\rfloor\cdot2^{n-128})/P_j\big]$. We can simply use the same $e_j$ for all keys (e.g. $2^{16}+1$ or $3$).

If for some reason the order of the successive encryptions is not known in advance, we can still use this system: we can blindly assume that every cryptogram will be less than the next $N_j$ used; this has less chance to be wrong by accident than by effect of a computation error (probability less than $2^{129-n+\log_2(j_{\operatorname{max}})}$; further we can get rid of the $\log_2(j_{\operatorname{max}})$ term by choosing each $N_j$ in the range for $N_0$).

Note: if necessary, $\operatorname{RSA-encrypt}((N,e),D)$ can include a test on $N$ to decide if it should pad (for $N$ is the range of $N_0$) or use textbook RSA.

Note: $\lfloor2^{126}/\pi\rfloor$ is a 125-bit nothing-up-my-sleeve number.

Note: I have not examined if this is sound in the context of the quoted paper.

In summary: use RSA with padding or an hybrid RSA encryption scheme for the first step; then RSA without padding (applied to the RSA part of the cryptogram in the case of hybrid encryption). This will work assuming a proper choice of public modulus $N_j$, as discussed. This also works with identical modulus $N_j$, but I do not see a practical use.

-