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.

$\endgroup$
2
  • $\begingroup$ Is this a homework question? What is the source of this question? $\endgroup$
    – kelalaka
    Commented Apr 23, 2020 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
    Commented Apr 23, 2020 at 8:05

1 Answer 1

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

$\endgroup$
3
  • $\begingroup$ Yes. That works for $e\in\{3,5,7\}$. $\endgroup$
    – fgrieu
    Commented Apr 23, 2020 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
    Commented Apr 23, 2020 at 12:38
  • $\begingroup$ @Faulst Thanks! $\endgroup$
    – user69015
    Commented Apr 23, 2020 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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