# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.571881,"math_prob":0.99999917,"size":684,"snap":"2021-04-2021-17","text_gpt3_token_len":280,"char_repetition_ratio":0.15588236,"word_repetition_ratio":0.045801528,"special_character_ratio":0.46345028,"punctuation_ratio":0.08,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000056,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-13T15:32:36Z\",\"WARC-Record-ID\":\"<urn:uuid:26131191-5197-4504-a8f6-e993b69df70d>\",\"Content-Length\":\"171586\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:76ed4888-5b90-4891-a3c2-fc2b10317bf5>\",\"WARC-Concurrent-To\":\"<urn:uuid:58a58aed-0f59-41c4-a667-9d9cd1fe742d>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://crypto.stackexchange.com/questions/80204/how-can-i-decrypt-8-times-repeated-128-bit-aes-key-encrypted-by-1024-bit-rsa\",\"WARC-Payload-Digest\":\"sha1:T77OTTZK275QC65ERSVWXD2476QPORWZ\",\"WARC-Block-Digest\":\"sha1:C5QKNMJVLZWG67PPNAHZYEIWY2Z62JLS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038073437.35_warc_CC-MAIN-20210413152520-20210413182520-00455.warc.gz\"}"}