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.
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 &lt; 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 &lt; 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
    b510fc87ff47a07e7c748f67c768d7dd739adfdd7d082e933d6038ca554f3282
    d7aa9072028f4353dbef515b8eb6ff5867c039e1bd1f807a0cbed4655862060f


see if you can decipher the following:

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

c = 000608a5a8b32e3b218b49f9f0c33d05f135eff53dabee5ac00ec13e72997ef7
    c4b478d6b95cecc01ebcf7cecf24785ba28b4b88f605ee93d6502f24635624cc
    f4772e0d7334d125e047853c4a42e21d4bc3412729b0d230c1f5d6a2f8272bb1
    8927313328c6e431bf1e38d5200a5ac32293f4d58c467636a20bc7393d7133c3
    65880f07a2a29ad63fb21ebd2011b02dcd298fbd97c70d72fbc5c433a223987d
    898da302aa100efd95f43e7d6698a7eeea05dd97870583f149beda3aa6334ba4
    641c224e8c8f2cd61156abd42e4e3d03070c453656ec072526618e2ad74c87e8
    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
    c23ebb85e69c9c2a3bef0d4a77b28a62db65f437e019062a74891ad17c3a9c58
    ba73644a3097de31dbd5a13349f7a3f031d2352cbba680525e4249147aa58053