# Cube-Root attack - RSA with low exponent

I have this RSA public key

-----BEGIN PUBLIC KEY----- MIIBIDANBgkqhkiG9w0BAQEFAAOCAQ0AMIIBCAKCAQEAx9a8pYAiNaVt9PrwjQ+0 cB6elLiGpcPQxkQckuPToObXVJcg2BSWG1M4XcH70oI3sCipPBDQiy1HvzHIvW96 qAYsbXR5ouEnNNF9hRlV3hE4LPQhN/H8QIOd8lYrepHcO2dR9gYM6zCQg312C3SJ l6Q6AZGaDI8saxv7cmU95wqK4ZfrHGeAp1kUzaz5rKVq81BZtyhYTpuyhMR5Hoz+ 0XPsZB58xbJ4/2gAhrk0wKuy7B9DGx0hc+rJcBn/UQCwtRD8h/9HoH58dI9nx2jX 3XOa3919CC6TPWA4ylVPMoLXqpByAo9DU9vvUVuOtv9YZ8A54b0fgHoMvtRlWGIG DwIBAw== -----END PUBLIC KEY-----

From which I get the values of n and e

n = 25227313400403003289291316040964706793284526130307773148182567990181812103363366492141868094341253168514098087977707768352520652692143206065406906643084095767849329466558935239586943914389925429616795559049929569740742883151498832979927915567828657543757871650853272541594015354947860164753295474118247326770430739348498870310114642065925503324951264351013482315725877175994479883134119470270775988034913135302127722176827339225792610659723969082753807504414521250872063048608812550101510336558064093636352586121260624931803298322088622685800438189865267661921807764104595582348335380035988782396542471100276681082383


e = 3

I have given a chipher.bin file which i have to decrypt using these values. I had tried to find the prime factor of n but failed, then I come to know about cube-root RSA attack but didn't able to figure out how to proceed.

## migrated from security.stackexchange.comMar 10 '16 at 9:23

This question came from our site for information security professionals.

• Do you know the padding (scheme) used for the message? – SEJPM Mar 10 '16 at 9:56
• A 2048 bit RSA key. Do you have any information? Such as the cleartext length, the character set, OAEP or not, etc. – Leo.W Mar 10 '16 at 10:12
• Googled the base64 key and found this question is at least 4 month old. – Leo.W Mar 10 '16 at 10:26

As you know, RSA encryption works by raising a plaintext block $p$ to some power $e$ modulo some composite modulus $n$:

$$c = p^e \pmod n$$

Now suppose $p$ and $e$ are so small that $p^e < n$. This is a disaster for Alice, because Eve can retrieve the plaintext by simply calculating the $e$-th root of $c$:

$$p = \sqrt[e]{c} \quad (\text{if }p^e < n)$$

On the other hand, if $p^e \ge n$, then $c$ will not be an exact $e$-th power. In this case, you could try adding integer multiples of $n$ to $c$ until you end up with a number that does work; i.e.,

$$p = \sqrt[e]{c + kn} \quad (\text{for some }k \in \mathbb{Z})$$

Note that this works without knowing the factors of $n$. In practical situations, RSA uses a much larger value of $e$ (usually 65537) and a much larger value of $p$ (through the use of padding), making this sort of attack impossible.

### A couple of examples:

Using the same modulus and exponent:

e = 3
n = c7d6bca5802235a56df4faf08d0fb4701e9e94b886a5c3d0c6441c92e3d3a0e6
d7549720d814961b53385dc1fbd28237b028a93c10d08b2d47bf31c8bd6f7aa8
062c6d7479a2e12734d17d851955de11382cf42137f1fc40839df2562b7a91dc
3b6751f6060ceb3090837d760b748997a43a01919a0c8f2c6b1bfb72653de70a
8ae197eb1c6780a75914cdacf9aca56af35059b728584e9bb284c4791e8cfed1
73ec641e7cc5b278ff680086b934c0abb2ec1f431b1d2173eac97019ff5100b0
d7aa9072028f4353dbef515b8eb6ff5867c039e1bd1f807a0cbed4655862060f


see if you can decipher the following:

(a) A simple example where $p^e < n$ (making the value of $n$ irrelevant):

c = 000608a5a8b32e3b218b49f9f0c33d05f135eff53dabee5ac00ec13e72997ef7
c4b478d6b95cecc01ebcf7cecf24785ba28b4b88f605ee93d6502f24635624cc
f4772e0d7334d125e047853c4a42e21d4bc3412729b0d230c1f5d6a2f8272bb1
8927313328c6e431bf1e38d5200a5ac32293f4d58c467636a20bc7393d7133c3
898da302aa100efd95f43e7d6698a7eeea05dd97870583f149beda3aa6334ba4
9c54397de803b8e2347f7daf413695e1df816782758f26a2abfe947c82ce9e9d


(b) A slightly harder one where $p^e$ is larger than $n$. You'll have to test for multiple values of $k$ to crack this one:

c = 9478dff8ca00aa472291b24a2db6288c4a865cfb53bff7c6ecb304a2d506bbbd
16c4d26584657c17693becbdbba5a9bb18d462d72d52ae10bfe3edf906120bc2
b0bec55f529f8eb2a0ae6cd997db467c53c463d7ed44790c7917b76dc6992a4c
db7362e93eb3f4f2bb433d7256793a5992891a86ce87edc4234ec81e83c7ecc7
d7659fa3639a1e299745c8ef5bd632928cb4871f19a6bd63ec974e45ac132f04
f53f1e5c0e4a12d008783e31650816d2c78d9ec84ecd828a5ed7d915bf7a9a08