1
$\begingroup$

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.

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

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'$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes. That works for $e\in\{3,5,7\}$. $\endgroup$ – fgrieu♦ Apr 23 '20 at 8:44
  • $\begingroup$ 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 ;-) $\endgroup$ – Faulst Apr 23 '20 at 12:38
  • $\begingroup$ @Faulst Thanks! $\endgroup$ – user69015 Apr 23 '20 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.