# How can I decrypt 8 times repeated 128-bit AES key encrypted by 1024-bit RSA?

There is a 128-bit AES key $$m$$, and it's encrypted by 1024-bit RSA modulus $$n$$ as $$c = (m\mathbin\| m\mathbin\|\ldots\mathbin\|m)^e \bmod n.$$

There are eight $$m$$ in $$m\mathbin\| m\mathbin\|\ldots\mathbin\|m$$.

Is there any way to find a message $$m$$?

The key is repeated 8 times, but I can't utilize this information to decrypt.

• Is this a homework question? What is the source of this question? – kelalaka Apr 23 '20 at 7:58
• If $e$ is small (such as $3$), then it is to possible to recover $m$ easily, but this information is missing. – user69015 Apr 23 '20 at 8:05

## 1 Answer

There is no proper padding and the message $$m$$ can be recovered easily if $$e$$ is small.

First, we can rewrite $$(m\mathbin\| m\mathbin\|\ldots\mathbin\|m)$$ as $$(m + m2^{128} + \cdots + m2^{128\times 7}) = m(1 + 2^{128} + \cdots + 2^{128\times 7}),$$ and when we put it back in the equation, we have $$c = m^e(1 + 2^{128} + \cdots + 2^{128\times 7})^e \mod n.$$ We can compute $$c' = c\times (1 + 2^{128} + \cdots + 2^{128\times 7})^{-e} \mod n,$$ so we have the relation $$c' \equiv m^e \bmod n$$. In the case that $$m^e < n$$ (which happens for $$e=3$$, $$5$$ or $$7$$), then this is in fact an equality: $$c' = m^e.$$ The value $$m$$ can be recovered by taking the $$e$$-nth root of $$c'$$.

• Yes. That works for $e\in\{3,5,7\}$. – fgrieu Apr 23 '20 at 8:44
• When you compute $c'$, it should be $c'=c\times(1+...)^{-e}$ to get $c' \equiv m^e \bmod n$, not $c'=c\times(1+...)^{-1}$. I can't edit a single character, and don't want to modify the rest of your answer ;-) – Faulst Apr 23 '20 at 12:38
• @Faulst Thanks! – user69015 Apr 23 '20 at 12:52