1
$\begingroup$

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.

$\endgroup$

migrated from security.stackexchange.com Mar 10 '16 at 9:23

This question came from our site for information security professionals.

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

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
    b510fc87ff47a07e7c748f67c768d7dd739adfdd7d082e933d6038ca554f3282
    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
    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
$\endgroup$

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.