文章目录
  1. 题目信息
  2. 分析
  3. 解题

题目信息

有人正在他老房子的地下室里开发自己的RSA系统。 证明他这个RSA系统只在他的地下室有效！

分析

很明显素数的生成有问题，生成的素数p，其p-1有很多小因子，使用RsaCtfTool即可破解出私钥！

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
$ python3 RsaCtfTool.py -n 21702007965967851183912845012669844623756908507890324243024055496763943595946688940552416734878197459043831494232875785620294668737665396025897150541283087580428261036967329585399916163401369611036124501098728512558174430431806459204349427025717455575024289926516646738721697827263582054632714414433009171634156535642801472435174298248730890036345522414464312932752899972440365978028349224554681969090140541620264972373596402565696085035645624229615500129915303416150964709569033763686335344334340374467597281565279826664494938820964323794098815428802817709142950181265208976166531957235913949338642042322944000000001 -e 65537 --private

[*] Testing key /tmp/tmpeooqiijv.
[*] Performing boneh_durfee attack on /tmp/tmpeooqiijv.
[*] Performing comfact_cn attack on /tmp/tmpeooqiijv.
[*] Performing cube_root attack on /tmp/tmpeooqiijv.
[*] Performing ecm attack on /tmp/tmpeooqiijv.
[*] ECM Method can run forever and may never succeed, timeout set to 30sec. Hit Ctrl-C to bail out.
^C[*] Performing ecm2 attack on /tmp/tmpeooqiijv.
[*] ECM2 Method can run forever and may never succeed, timeout set to 30sec. Hit Ctrl-C to bail out.
^C[*] Performing factordb attack on /tmp/tmpeooqiijv.

Results for /tmp/tmpeooqiijv:

Private key :
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAq+m7iHurBa9G8ujEiTpZ71aHOVNhQXpd6jCQNhwMN3hD6JHk
v0HSxmJwfGe0EnXDtjRraWmS6OYzT4+LSrXsz9IkWGzRlJ4lC7WHS8D3NWIWYHCP
4TRt2N0TlWXWm9nFCrEXqQ3IWgYQpQvKzsdsetnIZJL1tf1wQzGE6rbkbvURlUBb
zBSuidkmi0kY5Qxp2Jfb6OUI647zx2dPxJpDffSCNffVIDUYOvrgYxIhs5HmCF3X
ECC3VfaKtRceL5JM8R0qz5nVU2Ns8hPvSVP+7/i7G447cjW151si0joB7RpBplu4
4Vk8TXXDAk0JZdW6KwJn7ITaX04AAAAAAAAAAQIDAQABAoIBAQCEWcr2FXeiRcIS
it+cYp8QowYyPR4YAfRBsyejcM56+g0WBRQdprh14R2GuXQp7h5BrXOwUQY4ZdnE
+9caKptpl/hBV222xFXzAMtrp+DqaVye3Kn4kJutJO7JywCBNhP72kFD9odzv02b
M0vtDB1ZK0ebHoUqmjaOlJYm+a0+OgzRG/VY6PfVs0GWdsSPtbIcautHI/+5V8US
yG2wRH78JmTobVCLxEmdpjnUNKTM1Vsg/VCatzbkpohrE1cEZHhk+ke9uhyPvIvt
afOC442Y09eI0vaC24IfgyAVuhOfuU3uik+JT6Vz1x9/53vorAD//wAA//8AAP//
AAD//wABAoGBAMaX7gnjTwV6mm9o004b07Hk5Ab3PR4oEzniNgtrpP8/3Ed1wpHg
M54idlm6rYlcLh+XWU4Z7/4v5HaNjbPaRye2tGVfGi+gY+HcrRLbEHUJlhPKUozd
N6nayALynp7Lso19xaOz6kV86oUw+TFSi1PRnHcV01mJTgAAAAAAAAABAoGBAN2b
baKYDQzqBypnO+t/6JQPIvHzY8gC34qdUv7ShqvKgX70QRcFY4BY2C+ZTln0y1jv
tX3tCwq59dzh1CRpgAfwk5nR2IjA+JLU35vAGB1IVqWmVC/VZ46zOSwy07xCJEy4
HQ0d+PqANk8Wv2pMFmZZZfDWsYDWAAAAAAAAAAABAoGAK2b69BhEperko6KiQ7jb
LE7c8xTHu7aAdS8WJqrQ9aQMTWXULzNztITNntCoqpOF1QurzeDnTYNECBDpvjvf
PzOz+0+slmoUSkGDZdKQpzOAJDUck4KpbqrM+a/ysLvN+xRYxG1Grwcc7h0E6R2k
K55s9q3DchcK//8AAP//AAECgYAUPbgb28uFXHLfGqLMddhmfaNxegupHyoP3SLR
h6UpV8vQLrsrQSC/fl3wqw4PBV71dp+bKuWRSz77t9zKnqBFGWJB8HrYsteBgdQS
w87wDcVsR+70l4dn71LPiKzySxBJuZ9drVkqeD99pdRB/0UkgBHhl5qK7AD//wAA
//8AAQKBgQCYIKsSiGhJxY9AGaWofVsVe2sgGPHpwj3l2Yv8/PoG5Fpxozy+mzqv
lDHIzJjsDIhtDeZr2cTkT6ODNM8bswDC62QnG+VUAzltXeN7P/aQzrbEUcGg7zgd
ZzvOJdNjXP9dU/vKGBT9cjjJhvwowfqnDlUVrl12W3AE/jn6U/Xpfg==
-----END RSA PRIVATE KEY-----

破解出私钥之后，循环解密多次直到找出flag。如下Python脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from base64 import b64decode
from Crypto.Util.number import *

def solve():
    N=21702007965967851183912845012669844623756908507890324243024055496763943595946688940552416734878197459043831494232875785620294668737665396025897150541283087580428261036967329585399916163401369611036124501098728512558174430431806459204349427025717455575024289926516646738721697827263582054632714414433009171634156535642801472435174298248730890036345522414464312932752899972440365978028349224554681969090140541620264972373596402565696085035645624229615500129915303416150964709569033763686335344334340374467597281565279826664494938820964323794098815428802817709142950181265208976166531957235913949338642042322944000000001
    d=16707734744082089987096183760536140050531071284398222525928539910115274945961673413424053379896538639181783084998088831705326266248972451538621553176990679827738650084993005694971585059194288779236578752505246610328862945930341561242587398577636666631640913502943335996493633579116896296237142465786006038646664937384294577512911411958573147328359278328601128101352047028079357406162063405979398633542591758429760763171350524080583743130797539259640940004907846945847664144924968938380506532950172261068535550048712875992662239788993590417593968724043704420879416184807161738395187599580068732017638891008132810473473
    C=b64decode(b'eER0JNIcZYx/t+7lnRvv8s8zyMw8dYspZlne0MQUatQNcnDL/wnHtkAoNdCalQkpcbnZeAz4qeMX5GBmsO+BXyAKDueMA4uy3fw2k/dqFSsZFiB7I9M0oEkqUja52IMpkGDJ2eXGj9WHe4mqkniIayS42o4p9b0Qlz754qqRgkuaKzPWkZPKynULAtFXF39zm6dPI/jUA2BEo5WBoPzsCzwRmdr6QmJXTsau5BAQC5qdIkmCNq7+NLY1fjOmSEF/W+mdQvcwYPbe2zezroCiLiPNZnoABfmPbWAcASVU6M0YxvnXsh2YjkyLFf4cJSgroM3Aw4fVz3PPSsAQyCFKBA==')
    f=open('mes','wb')
    for _ in range(80):
        C=long_to_bytes(pow(bytes_to_long(C),d,N))
        f.write(C+b'\n\n')
    return

if __name__=='__main__':
    solve()

在mes中第64行：

1
the flag is: ASIS{n0t_5O_e4sy___RSA___in_ASIS!!!}