Press "Enter" to skip to content

[IceCTF2016]RSA2 – 90pt

Question:

N=0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f

e=0x10001

c=0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

Solution:

1.首先找出N 10進制的值

code:

print

int('180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd',16)

output:

30064958471180141352963255964320727764941087854957385562672821662319854021395100968823341108075020928542437446993994119863902565874355296188498304761389336438421889636409561936141985786801002923752627293790265351723795968412774268086467114263767947693310444934316205390814185802517514694528501333851255084653925181726978734804806707740444755908398751964899143494522781405457103697373868972836201511424363601490903086488506985489526910314474245106338585623571369549388434865567951986866445306840505397268281889886738015891982162371413136885989746931929787765617838750381226036784122498143172854419447324975505933540511

2.找出p , q

根據公式 ,

ϕ(N)=ϕ(p)ϕ(q)=(p1)(q1)

故使用此網站進行分解找出pq Factordb , 得出

p = 57970027

q=518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719

731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677

935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506

496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035

073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152

757864093

3.生成private key(d)

根據公式

ed1(modlcm(p1,q1))

我們可以使用rsatool透過 p 和 q找出 d

python rsatool.py -p 57970027 -q

518629368090170828331048663550229634444384299751272939077168648935075604180676006392464524953128293842996441022771890719731811852948684950388211907532651941639114462313594608747413310447500790775078081191686616804987790818396104388332734677935684723647108960882771460341293023764117182393730838418468480006985768382115446225422781116531906323045161803441960506496275763429558238732127362521949515590606221409745127192859630468854653290302491063292735496286233738504010613373838035073995140744724948933839238851600638652315655508861728439180988253324943039367876070687033249730660337593825389358874152757864093

-o priv.key

最後找出

n =

ee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397

d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b

1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f022836

6aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b

59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc

5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca

19bd54e39bbfa0d7a0e7c89d955b1c9f

e = 65537 (0x10001)

d =

9186c78d098af6815622ea9901cf84a89ead578a6dbdded7d7fc63531756239dc586501216fc2e4b

d1a8cee7e62284d16d91195f356d733a52dff011ebc3bf1e5d62af54d0455ea2f6ec948f45f34931

f5b0b4478b16c66951a95d2f069a6c8867a6bc673c8e40052a54dbc5c1aeacbbfae7cad150a4f41e

f4a02b1c97d70636ae187ed3c45f2551696a6a1172ae4089e033fb4853057c0f1e227d71ccf24fb2

7073ca4fe4ac3744dfed2cd7763c47ac4ae4d42820a19d68961bc103bb9016197463875169d062b4

5807e2e86aa17fa65e3088cc75ef35f984d0ca92d4c9270c2e694eb1f5df16b7ebe32b5c1d26086d

6aac5fe327288f2904cb54164db39151

p = 57970027 (0x3748d6b)

q =

44ed2b294274f82e2aca3f111bb159821c9c403162f25e35a4b1c04da8d6daa560351af288cc9c4c

85a02ec072ed7f9dbe63d09d6e98131b0bd76e3622c09bd83a9f98821b0806c986195a2ceae21d1b

f7afc717502376823731cfda3eb77ef2c91272ae5dc2b973ba4fefb706cc99e6e4e9dcbac8a6ae7d

de9919be822429a56b009897c3282876419d74f4622e09853deaad858f3cbf490c2367524913ebb7

f2a6b16712cb75a98b32d4dbb4469ccf8a46179e1c6db775dbc049b291da1a1e879d4cec1b515b26

da134f38220951d6d2fbbf44f62d4468e69ac8c97d9830771bea7bc7f866d3afc2f14c500be64128

3ef09b3d42a44a91ec1fc7a69d

4.直接解出c

有了n , d , c 我們可以直接解密了

import sys

import binascii

if __name__ == "__main__":

flag =

0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

n =

0xee290c7a603fc23300eb3f0e5868d056b7deb1af33b5112a6da1edc9612c5eeb4ab07d838a3b4397d8e6b6844065d98543a977ed40ccd8f57ac5bc2daee2dec301aac508f9befc27fae4a2665e82f13b1ddd17d3a0c85740bed8d53eeda665a5fc1bed35fbbcedd4279d04aa747ac1f996f724b14f0228366aeae34305152e1f430221f9594497686c9f49021d833144962c2a53dbb47bdbfd19785ad8da6e7b59be24d34ed201384d3b0f34267df4ba8b53f0f4481f9bd2e26c4a3e95cd1a47f806a1f16b86a9fc5e8a0756898f63f5c9144f51b401ba0dd5ad58fb0e97ebac9a41dc3fb4a378707f7210e64c131bca19bd54e39bbfa0d7a0e7c89d955b1c9f

d =

0x9186c78d098af6815622ea9901cf84a89ead578a6dbdded7d7fc63531756239dc586501216fc2e4bd1a8cee7e62284d16d91195f356d733a52dff011ebc3bf1e5d62af54d0455ea2f6ec948f45f34931f5b0b4478b16c66951a95d2f069a6c8867a6bc673c8e40052a54dbc5c1aeacbbfae7cad150a4f41ef4a02b1c97d70636ae187ed3c45f2551696a6a1172ae4089e033fb4853057c0f1e227d71ccf24fb27073ca4fe4ac3744dfed2cd7763c47ac4ae4d42820a19d68961bc103bb9016197463875169d062b45807e2e86aa17fa65e3088cc75ef35f984d0ca92d4c9270c2e694eb1f5df16b7ebe32b5c1d26086d6aac5fe327288f2904cb54164db39151

c =

0x3dbf00a02f924a70f44bdd69e73c46241e9f036bfa49a0c92659d8eb0fe47e42068eaf156a9b3ee81651bc0576a91ffed48610c158dc8d2fb1719c7242704f0d965f8798304925a322c121904b91e5fc5eb3dc960b03eb8635be53b995217d4c317126e0ec6e9a9acfd5d915265634a22a612de962cfaa2e0443b78bdf841ff901423ef765e3d98b38bcce114fede1f13e223b9bd8155e913c8670d8b85b1f3bcb99353053cdb4aef1bf16fa74fd81e42325209c0953a694636c0ce0a19949f343dc229b2b7d80c3c43ebe80e89cbe3a3f7c867fd7cee06943886b0718a4a3584c9d9f9a66c9de29fda7cfee30ad3db061981855555eeac01940b1924eb4c301

m =

hex(pow(c,d,n)).rstrip("L")

print m

print

binascii.unhexlify(m[2:])

{IceCTF2016}[Cryptography](Stage3)RSA2 - 90pt

IceCTF{next_time_check_your_keys_arent_factorable}

參考:

http://crypto.stackexchange.com/questions/1713/calculating-private-keys-in-the-rsa-cryptosystem

https://tenshine.gitbooks.io/topctf/content/chapter5/crypto/rsa.html

https://0x90r00t.com/2015/09/20/ekoparty-pre-ctf-2015-cry100-rsa-2070-write-up/

Comments