# Decrypting arbitrary numbers with RSA

I want to construct a hash-chain where I want to share millions of small AES-128 keys with Bob over a period of time. Bob should not be able to predict the future keys if he knows the past keys. I also want to avoid having Bob storing all these keys, but rather be able to derive them so that if they know the key from time $$t$$, they should be able to derive the keys from time $$t-1, t-2$$, and so on. So, future-to-past derivation should be possible. Past-to-future derivation should be hard.

The hash-chain way of doing this is to start with a random string, hash it with sha256, say, 1 million times, and start the chain with the 1 millionth hash. This way, if Bob is at the 10th iteration of our protocol, and wants to go back to the 6th iteration, he hashes the 10th iteration key 4 times to get the 6th key.

I am wondering if we can do the same with some encryption scheme like RSA. I give Bob my RSA public key $$([e, n])$$. I start the chain with a large random number in the range $$(2, n-1)$$, and decrypt it. I am assuming that every number in this range has a valid decryption. This decryption chain can continue as many times. If Bob wants to reconstruct keys, he uses the encryption algorithm, for which he has the public key. I can use some KDF to derive the AES-128 key from this large RSA "number".

Is the RSA-chain scheme as safe as the SHA-chain scheme?

• Seems like "Related questions" from stackexchange works great. I got what I was looking for here: crypto.stackexchange.com/questions/1793/… – Tejaswi Nadahalli Aug 16 at 8:20
• This question also feels closely related. – Ilmari Karonen Aug 16 at 12:40
• Seekable sequential key generators (SSKG), used in reverse order (start from a very high counter value, give them one key at a time counting backwards in the SSKG output, and when given any one key they can recreate all past keys / later SSKG values). eprint.iacr.org/2013/397 – Natanael Aug 17 at 12:43

The proposed system seems to be as follows:

• At generation, Alice selects odd $$e>2$$ and random large primes $$p$$ and $$q$$ with $$\gcd(p-1,e)=1=\gcd(q-1,e)$$; computes $$n\gets p\,q$$; chooses random $$s_0$$ in $$[1,n)$$; and publishes $$(n,e,s_0)$$. She computes and keeps secret $$\lambda(n)\gets(p-1)(q-1)/\gcd(p-1,q-1)$$ and $$d\gets e^{-1}\bmod\lambda(n)$$.
• For successive times $$t\in\Bbb N^*$$, Alice computes $$s_t\gets{s_{t-1}}^d\bmod n$$ and publishes $$s_t$$ at time $$t$$.
• For $$t\in\Bbb N^*$$, anyone with knowledge of $$(n,e,s_{t-1})$$, e.g. Bob, can check an alleged $$s_t$$, by verifying that $$0 and $${s_t}^e\bmod n=s_{t-1}$$. Alternatively, $$s_t$$ can be verified from $$(n,e,s_0)$$ by verifying that $$0 and $${s_t}^{(e^t)}\bmod n=s_0$$.
• By convention, $$k_t=H(s_t)$$ where $$H$$ is some 128-bit PRF, e.g. the low-order 128 bits of SHA-256.

Anyone with knowledge and trust of $$(n,e,s_0)$$ and knowledge of $$s_{t'}$$, e.g. Bob, can compute and trust $$k_t$$ for $$0\le t\le t'$$. The intention is that it would be infeasible to derive $$k_t$$ for $$t>t'$$. That holds, with some degree of reduction to the RSA problem. Some arguments:

• Given how it is generated, it is overwhelmingly likely that $$s_0$$ is coprime to both $$p$$ and $$q$$. Assuming that, it follows that for fixed $$t$$, each $$s_t$$ is uniformly random in $$\Bbb Z_n^*$$.
• Knowledge of $$s_{t'}$$ subsumes knowledge of earlier $$s_i$$ with $$i.
• Finding $$s_t$$ from $$s_{t'}$$ for $$t>t'$$ is solving the RSA problem for public exponent $$e^{t-t'}$$, or equivalently public exponent $$e^{t-t'}\bmod\lambda(n)$$, which itself takes quite random-like values in $$\Bbb Z_{\lambda(n)}^*$$.
• Wait... I tried following your insecurity argument with $t=1 > t'=0$ (i.e. Alice only publishes $n$, $e$ and $s_0$, Bob wants to compute $s_1 = s_0^d \bmod n$), but it seems to me that Bob being able to compute $s_1$ in that case would be directly equivalent to breaking RSA. Now I'm confused. :/ – Ilmari Karonen Aug 16 at 17:36
• @Ilmari Karonen: You are of course totally right. Fixed now. Somewhat I wrote ${s_t}^{(t\,e)}\bmod n=s_0$ when really ${s_t}^{(e^t)}\bmod n=s_0$. Oups. – fgrieu Aug 17 at 10:23
• Ah, a typo. That happens. :) Anyway, thinking about this a bit more, it seems like a reduction should be possible. Basically, if Alice knew that Bob could break this scheme by predicting $s_{t+1}=s_t^d$ when given $(n,e,s_0,\dots,s_t)$, then she could use Bob as an oracle to break RSA encryption by taking a ciphertext $c$ encrypted with the public key $(n,e)$, generating $(s_t, s_{t-1}, s_{t-2}, \dots, s_0) = (c, c^e, c^{e^2}, \dots, c^{e^t})$ and sending those (along with $n$ and $e$) to Bob. – Ilmari Karonen Aug 17 at 10:54
• See my other comment, SSKG:s are relevant eprint.iacr.org/2013/397 – Natanael Aug 17 at 12:44
• @fgrieu I saw your earlier comment and was about to remark on the typo, but then your answer disappeared :-). Now, it's back again, and seems like everything is ok. – Tejaswi Nadahalli Aug 19 at 11:48