Jarvis OJ -- crypto题（上）

发表于 | 更新于 | 分类于
Jarvis OJ -- crypto题（上）

Medium RSA

你没看错，这还真是密码学系列了，相信你已经解出前两题了，那么继续看这题吧。

读取一下公钥

1
2
3
4
5
6
7
8
9
10
11
12
13
➜  mediumRSA openssl rsa -pubin -in pubkey.pem -text -modulus
Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
Modulus=C2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

或者通过python读取pem

1
2
3
4
5
6
7
8
9
from Crypto.PublicKey import RSA
with open('./pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    n = key.n
    e = key.e
print n
# 87924348264132406875276140514499937145050893665602592992418171647042491658461
print e
# 65537

factordb.com分解一下p和q，得到

p = 275127860351348928173285174381581152299

q = 319576316814478949870590164193048041239

然后求私钥d，解密文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
from Crypto.Util.number import long_to_bytes

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = 87924348264132406875276140514499937145050893665602592992418171647042491658461
e = 65537

d = libnum.invmod(e, (p - 1) * (q - 1))
with open('flag.enc', 'r') as f:
    c = f.read().encode('hex')
    c = int(c, 16)
m = pow(c, d, n)
print long_to_bytes(m)
# 前面有一部分不知道为什么乱码，但是不影响看出flag
# ���&[�PCTF{256b_i5_m3dium}

BrokenPic

这里有个图片，可是好像打不开？

Hint1: 图片大小是1366*768

按提示加上bmp头

bmp

有个key，bmp文件010 editor打开可以看到32位，32位的变换很规律，应该是aes加密

1
2
3
4
5
6
7
8
9
10
from Crypto.Cipher import AES
key = 'PHRACK-BROKENPIC'
aes = AES.new(key)

with open('brokenpic.bmp', 'r') as f:
    data = f.read()
    pic = aes.decrypt(data)

with open('2.bmp', 'w') as f:
    f.write(pic)

再加上bmp头，可以看到

bmp

PCTF{AES_i5_W3ak_foR_im4ge}

hard RSA

相信你已经做出了medium RSA，这题的pubkey在medium RSA的基础上我做了点手脚，继续挑战吧。

Hint1: 1.不需要爆破。2.用你的数学知识解决此题。3.难道大家都不会开根号吗？

如果按第一题那样做会发现求d的时候就会报错找不到e的模反数

ValueError: no invmod for given @a and @n

正如题目所说的动了下手脚……

因为题目里提到里开根号，所以做之前我要先说一点废话，关于开根号，网上大多wp里都用的gmpy2，那么我们先安装一下gmpy2，我是macos，按这篇文章里面linux的方法安装就行了，有几点要注意

  • macos需要先安装xcode的Command Line Tools
  • 文章里面安装MPFR的地址404了，需要去官网获取最新的

地址：www.cnblogs.com/pcat/p/5746821.html

然后可以通过gmpy2.iroot(n,e)求n开e次方，返回一个元组，包括一个结果值和一个是否刚好n能开e次方的bool值。gmpy2安装稍微复杂，相比之下libnum也有求根函数，为libnum.nroot(n,e)，但是只返回结果值。因为两个函数求根返回的结果值都是int型的，比如libnum.nroot(16,3)，返回int型的值2，但是3^2=9不等于16，但是gmpy2.iroot(16,3)，返回一个元组(mpz(2), False)，然后我们可以通过元组的第二个元素判断是否刚好n能开e次方。当然也可以采用d = libnum.nroot(n,e)求出d，然后判断n == pow(e,d)

关于libnum和gmpy2的开根号的区别就说到这里，很多密码学的题里都会用到这两个库，不过刚才安了gmpy2后发现，还是libnum好用，安装又简单

然后准备用小公钥指数攻击爆破，爆破了几十秒，发现哪里不对劲，重新看下提示，说不用爆破。于是注意到这题rsa的e = 2，搜一下就会发现有个听着很吊的名字

Rabin 算法

看了下数学推理过程，发现看不懂，算了，还是拿着脚本上吧

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
43
44
45
46
# coding=utf-8
import gmpy2
import string
from Crypto.PublicKey import RSA

with open('hardRSA/pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e
with open('hardRSA/flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = string.atoi(cipher, base=16)

# factordb.com分解得到p和q
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
# 还是偏向于使用libnum，用法如下
# import libnum
# inv_p = libnum.invmod(p, q)
# inv_q = libnum.invmod(q, p)

# 计算mp和mq
mp = pow(cipher, (p + 1) / 4, p)
mq = pow(cipher, (q + 1) / 4, q)

# 计算a,b,c,d
a = (inv_p * p * mq + inv_q * q * mp) % N
b = N - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % N
d = N - int(c)

for i in (a, b, c, d):
    s = '%x' % i
    if len(s) % 2 != 0:
        s = '0' + s
    print s.decode('hex')

# D�#���P�ޚe�cb�`ކ�P�/�V��
# }�Y¾�S��Zv#�
# C]�+��gq=
# �`��8
#      (�$X�@��i�{Y�=�`�w
#                        \��
# �2�̻`�?��PCTF{sp3ci4l_rsa}

very hard RSA

前几题因为N太小，都被你攻破了，出题人这次来了个RSA4096，是否接受挑战就看你了。

下载下来，发现这次多了一个python文件

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
#!/usr/bin/env python
import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
    return ('', '0')[len(x) % 2] + x

e1 = 17
e2 = 65537

fi = open('flag.txt', 'rb')
fo1 = open('flag.enc1', 'wb')
fo2 = open('flag.enc2', 'wb')

data = fi.read()
fi.close()

while (len(data) < 512 - 11):
    data = chr(random.randint(0, 255)) + data

data_num = int(data.encode('hex'), 16)

encrypt1 = pow(data_num, e1, N)
encrypt2 = pow(data_num, e2, N)

fo1.write(pad_even(format(encrypt1, 'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2, 'x')).decode('hex'))

fo1.close()
fo2.close()

可以看到，对一段密文分别用两个不同的公钥加密，但是两个公钥只有e不一样，模数n是一样的。于是很明显是共模攻击

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
import gmpy2
import string
from Crypto.Util.number import long_to_bytes

n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
e1 = 17
e2 = 65537

with open('veryhardRSA/flag.enc1', 'r') as f:
    cipher1 = f.read().encode('hex')
    cipher1 = string.atoi(cipher1, base=16)
with open('veryhardRSA/flag.enc2', 'r') as f:
    cipher2 = f.read().encode('hex')
    cipher2 = string.atoi(cipher2, base=16)

# s & t
gcd, s, t = gmpy2.gcdext(e1, e2)
if s < 0:
    s = -s
    cipher1 = gmpy2.invert(cipher1, n)
if t < 0:
    t = -t
    cipher2 = gmpy2.invert(cipher2, n)
plain = gmpy2.powmod(cipher1, s, n) * gmpy2.powmod(cipher2, t, n) % n
print long_to_bytes(plain)

# &�7�e��e�B
#           ��-�y�7�������ĩ�G��TNh0!�4\
# ��\��j���2$�+���'����3�i�[_�h��xL3;ѓ�΃C rD���b�"��Yp��"�.�SQjE�@��JͷH�S��#ܝ��Y����
# XO�eˍ1�����=g�<|�{0����WWQ�Au�ͅ'[����"L�Gw
# ��^"n�@ˏ|���ͬ]�u�3(�e��Y+Ɵ����X�����Z'qo;*v�Z���\�鱼r�Nɞ��.%��ۀV&#�"�*��6�]z�%_��v:�,V_�Sg�h
# ����Eu�
# �Ͷ#�\(⓭1��躧̐PCTF{M4st3r_oF_Number_Th3ory}

Extremely hard RSA

没想到RSA4096都被你给破了，一定是我的问题，给了你太多信息，这次我只给你一个flag的加密值和公钥，仍然是RSA4096，我就不信你还能解出来。

先看下公钥

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
43
44
45
46
47
48
49
50
51
52
53
54
55
➜  extremelyhardRSA openssl rsa -pubin -in pubkey.pem -text -modulus
Public-Key: (4096 bit)
Modulus:
    00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:
    18:fc:8c:7d:7d:03:b8:2e:40:99:51:c1:82:f3:98:
    de:e3:10:45:80:e7:ba:70:d3:83:ae:53:11:47:56:
    56:e8:a9:64:d3:80:cb:15:7f:48:c9:51:ad:fa:65:
    db:0b:12:2c:a4:0e:42:fa:70:91:89:b7:19:a4:f0:
    d7:46:e2:f6:06:9b:af:11:ce:bd:65:0f:14:b9:3c:
    97:73:52:fd:13:b1:ee:a6:d6:e1:da:77:55:02:ab:
    ff:89:d3:a8:b3:61:5f:d0:db:49:b8:8a:97:6b:c2:
    05:68:48:92:84:e1:81:f6:f1:1e:27:08:91:c8:ef:
    80:01:7b:ad:23:8e:36:30:39:a4:58:47:0f:17:49:
    10:1b:c2:99:49:d3:a4:f4:03:8d:46:39:38:85:15:
    79:c7:52:5a:69:98:4f:15:b5:66:7f:34:20:9b:70:
    eb:26:11:36:94:7f:a1:23:e5:49:df:ff:00:60:18:
    83:af:d9:36:fe:41:1e:00:6e:4e:93:d1:a0:0b:0f:
    ea:54:1b:bf:c8:c5:18:6c:b6:22:05:03:a9:4b:24:
    13:11:0d:64:0c:77:ea:54:ba:32:20:fc:8f:4c:c6:
    ce:77:15:1e:29:b3:e0:65:78:c4:78:bd:1b:eb:e0:
    45:89:ef:9a:19:7f:6f:80:6d:b8:b3:ec:d8:26:ca:
    d2:4f:53:24:cc:de:c6:e8:fe:ad:2c:21:50:06:86:
    02:c8:dc:dc:59:40:2c:ca:c9:42:4b:79:00:48:cc:
    dd:93:27:06:80:95:ef:a0:10:b7:f1:96:c7:4b:a8:
    c3:7b:12:8f:9e:14:11:75:16:33:f7:8b:7b:9e:56:
    f7:1f:77:a1:b4:da:ad:3f:c5:4b:5e:7e:f9:35:d9:
    a7:2f:b1:76:75:97:65:52:2b:4b:bc:02:e3:14:d5:
    c0:6b:64:d5:05:4b:7b:09:6c:60:12:36:e6:cc:f4:
    5b:5e:61:1c:80:5d:33:5d:ba:b0:c3:5d:22:6c:c2:
    08:d8:ce:47:36:ba:39:a0:35:44:26:fa:e0:06:c7:
    fe:52:d5:26:7d:cf:b9:c3:88:4f:51:fd:df:df:4a:
    97:94:bc:fe:0e:15:57:11:37:49:e6:c8:ef:42:1d:
    ba:26:3a:ff:68:73:9c:e0:0e:d8:0f:d0:02:2e:f9:
    2d:34:88:f7:6d:eb:62:bd:ef:7b:ea:60:26:f2:2a:
    1d:25:aa:2a:92:d1:24:41:4a:80:21:fe:0c:17:4b:
    98:03:e6:bb:5f:ad:75:e1:86:a9:46:a1:72:80:77:
    0f:12:43:f4:38:74:46:cc:ce:b2:22:2a:96:5c:c3:
    0b:39:29
Exponent: 3 (0x3)
Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
writing RSA key
-----BEGIN PUBLIC KEY-----
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY
/Ix9fQO4LkCZUcGC85je4xBFgOe6cNODrlMRR1ZW6Klk04DLFX9IyVGt+mXbCxIs
pA5C+nCRibcZpPDXRuL2BpuvEc69ZQ8UuTyXc1L9E7Huptbh2ndVAqv/idOos2Ff
0NtJuIqXa8IFaEiShOGB9vEeJwiRyO+AAXutI442MDmkWEcPF0kQG8KZSdOk9AON
Rjk4hRV5x1JaaZhPFbVmfzQgm3DrJhE2lH+hI+VJ3/8AYBiDr9k2/kEeAG5Ok9Gg
Cw/qVBu/yMUYbLYiBQOpSyQTEQ1kDHfqVLoyIPyPTMbOdxUeKbPgZXjEeL0b6+BF
ie+aGX9vgG24s+zYJsrST1MkzN7G6P6tLCFQBoYCyNzcWUAsyslCS3kASMzdkycG
gJXvoBC38ZbHS6jDexKPnhQRdRYz94t7nlb3H3ehtNqtP8VLXn75NdmnL7F2dZdl
UitLvALjFNXAa2TVBUt7CWxgEjbmzPRbXmEcgF0zXbqww10ibMII2M5HNro5oDVE
JvrgBsf+UtUmfc+5w4hPUf3f30qXlLz+DhVXETdJ5sjvQh26Jjr/aHOc4A7YD9AC
LvktNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcP
EkP0OHRGzM6yIiqWXMMLOSkCAQM=
-----END PUBLIC KEY-----

emmm，看到e=3，那么应该是刚才hard RSA里面开始做时用的小公钥指数攻击了，直接爆破

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# coding=utf-8
import gmpy2
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes

with open('extremelyhardRSA/pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e
with open('extremelyhardRSA/flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)

# 爆破出来值为118719488
for i in range(118000000, 120000000):
    if gmpy2.iroot(cipher + i * N, 3)[1]:
        print long_to_bytes(gmpy2.iroot(cipher + i * N, 3)[0])
# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}

God Like RSA

既然你逼我到绝境，那就休怪我不客气了，代表上帝挑战你~

先读公钥

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
43
44
45
46
47
48
49
50
51
52
53
54
55
➜  godlikeRSA openssl rsa -pubin -in pubkey.pem -text -modulus
Public-Key: (4096 bit)
Modulus:
    00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
    58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
    d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
    b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
    3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
    bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
    67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
    1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
    31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
    ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
    06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
    7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
    3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
    c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
    4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
    9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
    c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
    09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
    8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
    e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
    c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
    79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
    e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
    d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
    41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
    14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
    32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
    e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
    fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
    4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
    ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
    9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
    08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
    89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
    e8:6c:1d
Exponent: 65537 (0x10001)
Modulus=C09778534564847D8CC4B420E9335867EC783E6CF5F05CA03EEEDC2563D0EB2A9EBA8F1952A2670BE76EB234B86D5076E06AD103CF7733D8B1E9D73BE5EB1C650C2596FD9620B97ADE1DBFFDF2B6BF813E3E47444398BF652F677E2775F95647BAC4F04E672BDAE01A77144029C1A8675A8FF52EBE8E82313D4326D49786291514A969362C76EDB590EBEC6FCED5CA241CAAF663F806A262CB2674D35B824BB6D5E049327B62F805C4F70E86599BF3172502AA3C9778847B16FD1AF567CF031797D0C66985F08DFACEEE6824630624E1E44CF8E9AD25C7E0C015BBB4674890039B207F0C17EB9D1344ABAB08A5C3DCC19888C5CE4F5A879B0BBFBDD70EA9095981FA884F59606B8484ADD9C7258CE8C0E8F7269E37957CE148290F51E7BD982FF6CC80E7F0320B8951924EC26D50532B3B7772D1BD1A1F92D712796161C5A47EB385EBF07C6D4603C5E6D5812CBA7EEA8D517D6355342AB6D4DC315AF199E3DC8C830BA22AD53C414841541AA9E8B670BFD3FEED1917149413B317E38B8E6F53EDE244E84A32D65C0DA880F5FC02E94655D5A4D3E7C63077F973E94452D8139D5DBF9EFA3AB59679825BCD195C06A90096FD4CA473881AEC3C11DEB93DE050001EAC2197A1967D6B15F96CC9347F70D79D2DD1484A8171F812DD32BA64316008264B0922038390177FF3A77257BF896DE4D740248B7BBDDF33C0FF302EE86C1D
writing RSA key
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAwJd4U0VkhH2MxLQg6TNY
Z+x4Pmz18FygPu7cJWPQ6yqeuo8ZUqJnC+dusjS4bVB24GrRA893M9ix6dc75esc
ZQwllv2WILl63h2//fK2v4E+PkdEQ5i/ZS9nfid1+VZHusTwTmcr2uAadxRAKcGo
Z1qP9S6+joIxPUMm1JeGKRUUqWk2LHbttZDr7G/O1cokHKr2Y/gGomLLJnTTW4JL
ttXgSTJ7YvgFxPcOhlmb8xclAqo8l3iEexb9GvVnzwMXl9DGaYXwjfrO7mgkYwYk
4eRM+OmtJcfgwBW7tGdIkAObIH8MF+udE0Srqwilw9zBmIjFzk9ah5sLv73XDqkJ
WYH6iE9ZYGuEhK3ZxyWM6MDo9yaeN5V84UgpD1HnvZgv9syA5/AyC4lRkk7CbVBT
Kzt3ctG9Gh+S1xJ5YWHFpH6zhevwfG1GA8Xm1YEsun7qjVF9Y1U0KrbU3DFa8Znj
3IyDC6Iq1TxBSEFUGqnotnC/0/7tGRcUlBOzF+OLjm9T7eJE6Eoy1lwNqID1/ALp
RlXVpNPnxjB3+XPpRFLYE51dv576OrWWeYJbzRlcBqkAlv1MpHOIGuw8Ed65PeBQ
AB6sIZehln1rFflsyTR/cNedLdFISoFx+BLdMrpkMWAIJksJIgODkBd/86dyV7+J
beTXQCSLe73fM8D/MC7obB0CAwEAAQ==
-----END PUBLIC KEY-----

然后题目给了个private.corrupted

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
Private-Key: (4096 bit)
modulus:
    0 :c :9 :  :  : 5:6 :  :  :  :  :  :20:  :  :
     8:  :  :7 :  :  :  :  :5 :  :  :ee:  :  :6 :
    d :  : a:9e:  :  :  :  :a : 7:  :e7: e: 2:  :
      :  :50:  :  :6 : 1:  :c :7 :  :  :b :e :d7:
     b:e : b:  :6 :  : 5:9 :  :  : 0:b :  :  :1 :
      :f :f : 6:b :  : e:  :4 :  : 3: 8:  :6 :  :
      :7 :2 :  :  : 6:  :  :  : 0:  :  :2 :  : 0:
      :  :  :  :  :  :  :  : a:  :f :  :be:  : 2:
    3 :3 : 3:  :d4:  : 6:  :  : 4: 9:  : 6: c:  :
     d:  :  : b:ec: f:  :  :  :  :1 :  :  : 3: 8:
    0 :  :  :  :  :  : 3:  : 2: b:  : 5:  : 9:  :
    7 :  : 8: 5:c4:f :  :  : 9:  :f :  :  :  :  :
    3 :  :78:8 : b:  :fd:  :  :6 :  :  :  :9 :  :
    c6:6 :  :  :8d:  :  :e :6 :  :6 : 6: 4:  : 4:
      :  :  :a :  :  : 0:  : 5:  :b :  :4 :  :  :
     b:20:  :  :  : b: d:  :4 :  :  : 8:a :c :d :
    c1:  :  :  :ce:  :5a: 7:  :0 :  : d:  : e: 9:
    09:  : 1:  : 8:4 :  :  :  :  :8 :a : 9:  : 5:
      : 8:  : 8:  : 6: e:  :95:  : 1:  :  : f: 1:
      :b :  :  :  : c:  :  :  :  :0 :8 : 1:  :4e:
    c :  :  :  :  :  : 7:  :  :b :  :  :9 :  :  :
      :61: 1:  :  :  : 3:85:  :f :7c: d: 6:  :c :
      :d5:  :  :  : e:ea: d: 1:  :6 : 5:3 :  :b :
    d :  :  :  :  : 9:  :  :  :83:  : 2:  :  :  :
    4 :  :4 :  :  :  : 8:b : 0:  :  :f :  :  :  :
      :  :1 :  :  :  :  :8 :6 :  :  :  :  :  :  :
      : 6:5 :  :  :8 :f5: c:  :  :  : 5:  :  :  :
      :  :3 :7 : 9:7 :  :  :  :d8:  : d:5 : f:  :
    fa:  :  : 6:  :  :  :cd: 9:  : 6:a9:0 :  : d:
     c:a4:7 : 8:  :e : c:1 :  :b :  :  :  :  :  :
      :21:9 :a :96:  :  :  :  :6 :c :  :7 :  :d :
      :  :  : 8:4 :8 :71:  :1 : d:  :  :  :  : 0:
    08:  : b:  :  :03:83:  : 7:  :f :  : 2:  :  :
    8 :6 :e : 7:40:2 : b:  : d:  :3 : 0:f :  : e:
     8: c: d
publicExponent: 65537 (0x10001)
privateExponent:
      :  :  : f:8 :a5:d : 2: 0:b :7 :  : 1:  : 4:
     1:0d:  :3 :  :6 :  :  : b:  :  :  :e :  :  :
    0e: 0:db:  :1a:1c:c0:  : e:  :  :99:bc:8 :a5:
    7 :7 :7 : b:  :  : 8: 8:  :7 :55: 2:  :  :f :
    b2:  :  :b :f :4 :  : 8:  :b :  :  :  : 0:  :
    0 :  :6 :9 :  :  :  : b: 4:  : 0: a: 5:07:b :
     9: c:9a: 9:  : 7:9e:  : b:60:f :  :  :  :0 :
      : 3:0 :  :  :  : 1:b :  :  : b: 6:0 :f :  :
      : 2:18: 6: b:1 :  :  :  :  :d3:f3:  :a :  :
     3:  :  :  :  : 3: d: 1: 2:7 :  : d:  : 2: d:
      :  : d:4 :  :d :  :6d: c:a :b6:  :  :  : 1:
    69:  : 7:  :89:  :c :8 :61: d:25: 3:7 :1b: 4:
    b :  :8 :55:  :49: 1:2 :3 :  :1 :e9:a8: 3:  :
    9 :  : 1:f8:d3:  :e :  :d :  :9 :b6:  :  :71:
    1 :  :c1:  : b: 1:  : 6:e :  :64:  :  :1a:c :
      : b:  :bf:c :  : 0:  : 8:a :4 :  :26:a :5 :
    6 :  :  :  :eb:  :e5: a:  :3e:f9:10:0 :  :  :
     6:0 :  : 8:  : 1:72: c:0 : f:5 : f:9c: 0: e:
     7:b :  :  :  :  :d9: 4:  : e:c :68:  :  :  :
     c:  :3a:  :  :a0:ea: 3: 4:  :72:a :d : 8:  :
      :0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
      :  :17:6 :  : c: b:  : f:  :3 : 5:6 :3 :0e:
      : 7:c :3e: 2: 9: 7: 6: f: e: f: 9:  :f3: 9:
    a :c1:6 :  : 1:9 :  :43:  : f: 5:  :0 :27: 4:
    4 :a :  :e9:  : 8: 4:3 :8a: 6:16:d5:c : e: e:
      :d : c:b :a8:  : 7:  : 9:  :7 :7d:  :  :  :
      :  :  :4 :2 :  : 3: 3: 6:  :  :  :7b:0 :  :
     e:  :0 :  :a :  : 5:  :  :  : 5:1 :82:c :0d:
    4 :2 :fd:36: 5:50:0 :  :  :d : f: 6:  :  :e :
    0 :  :  :ce:  :9e:8 :  :0 :d :07:b3:  :  :  :
    0 :e4:  :  :68:b :c :  : c:5 :  :  :3 : 7: 2:
     c:e0:  :5 :  :  :b4:  :ef: 7:  :1 :e : 0:f :
      :6 :  :  :  :e0:c :3 :  :  : 3:  : d:  :  :
     3: 3: c: a:  :b : a:71: 3: 0:a :  :4 :5d:  :
    0 :4
prime1:
     0: e:  :  :  :c :c :  :  :  :b :  :  :  :  :
      :ab: e: 2: 8:c :  :  : 1:6 :6 : 6: f:d9: 0:
    8 :5c:7 :06:  :  :  :0 : 3:5 :4b:  :6 :  :  :
    2 :  :6 :  :  :  :2 :bc: c:  :85:1 : 1:d : 3:
     1:b4:  : b: 1: 3: d:a :  :  :6e: 0:b :2 :  :
      :b :  :9 :e :  :82:8d:  :  :13:  :  : a: a:
      :  :4 :  :c : f:  :  :7 :e :0a:  :  : b: 5:
      : e:91:3 :  :3c: 9:  : 6:  :  :b5:7d: 1:  :
      :  :  :b :a1:99:6 :4 :3 :c :1a:02:4 :  : 9:
    9 :f : d:bd:  :0 :  :  :  :b3:  : 4:  :e9: 9:
      : d:  :  :7 :  :93:  : e:dc:  : 0:  :e7:  :
    e :  :2 : b: 2:5 :  :  :  :  : c:5f:  :  :e2:
      :  : 9:  :2a:  : e:  :  :2 :  :9f: 7:3 :  :
    b : f:b :  : 8: 7:  :  :f :6 :e :c :  :3 :  :
    f7: 5: 8: 5:  :  :  :  :  : 8: e:  :03: c:  :
    33:76:e : 1:7 : c:  : 0:  :0b:  : a:  : 2: 9:
      :c8:bf:  :  :06: 7:d5:  :02: c:b :e2: 7:2 :
      :
prime2:
     0: f:  :d0: 1:55: 4:31:  : b:c4:8 :  : e: d:
    34: 3:f :  :  :  :  : 8:99:1 :  : a:0 :  :4 :
    0 :  :f :  :a4:41:2 :  :a :  : 1:  : a: c:  :
      :  : 9:  :  : 2:f4: f:  :  :  :  :1 : 4:9 :
    a :  :  :79:0 :  :  :  :  : 2: 8:b :  :4 : 8:
      :9b: 1:  :d :  :f :e4:  :4 :c :e :  :3 :  :
     7:2 :  :d :8 :2 :7 :  :d :67:fc:e : 0:f9: 7:
    8 :  :  :  :1 :2f:  :51:  :  :2e:0a: e:3d: 6:
    b :  :dd:  : 0:fb:  :f4:  :  :  :b4: 9:c :  :
     a:  :  :  :d :  :  :6b: 2:  :9b: a:60:  :d6:
     0:4f:16:d1:  :  :5 :fc:  :f :  :8 :  :  :  :
     1: 6:e1:9 : e:4 : 6: c: d:d :73: 3:  :  :7 :
      :8 : 9:  :3b:f : 2:  :  :f1: e:  :  :1e:  :
    8 :  :  : 6:0 : 4:99:e :  : 5:  :  : 4:  :  :
      : a:81:64:  :7 :f : 9: d:  :9 :  : 7:93:f :
    ac:8c:  : 8:  : 0: d: 8:  :7 :  :1d:  :f :  :
    1 :a :6 :8 :  :60:  :b3:  :  :  :89:  :  :14:
      :5
exponent1:
      : 3:2a:  : d:  :  :  :  :0 :1 : f:  :  : 6:
    1 :2 :1b:07: a:e :b :c5:58:7 :  :e8: 7: 1: c:
      : 1:b :a0: 4:0f:5 :67:  :3 :7 :6 :f9:  : c:
      :79: 0:1 :65:  :8 :  :99: d:d :  :2 :9 :0 :
     e:  :0 :  :  :  : d:  :d :7 :6 :a9: a:8b: b:
      :  : 7: a:37:  :  :7 :1 :6 :  :c2: 7:6 :b :
     e:  :  :  :  :  :  :b :3a:5 :  :  :  :  :  :
      :  :  :cd:8 :  : d:  :7 : 3:  : f:e : c:  :
      : a:  :c : f:c : 7:b :5 :  :  :2 :8 :8 :6 :
    0a: a:  :  :3 :db:  : 4:00:  : d:  :b : 5:  :
    20: 2: 5:  :82:  : 0: 6:  :8a:  :7 :  : 8:  :
     4: 1:  :  :  : 8:46:  :  :  :  :  : 0:f :c8:
    2 :  : c:7 :  : 1:  :  :2 : 0: 5:  :  : 1:9b:
     6:9 : 0:74:  :c :  :e :  :  :cb:b :3 :3 :  :
     2:  :  :47:  :2 : 0:5 :  :  : d: 6:83:  :  :
      :c7:  :  :0b:  :  : c:  :3 :8 :  :9 :4 : 7:
    5 :c0:fe:  :f9: 1:  :0 : e: 8:02:  : f:  :c :
    55:61
exponent2:
      :0b:7 :4 :0 : 0:6 : 7:7e:  : 5:  : 7:  : a:
    a :d : 0: 6: 4:86:  :  :8 :  :  :  :  :e :8f:
     9:  :  :  : 1:  :2 :  : 7: b:1 :5 : f:  :8 :
      :d :21:  :e : d:  :c9:e : b:  :  :1 :  :  :
      :d :a2:b7:  :  :  :f3:  :42:  :e : c:  :f :
      : 0:f :7 : 4: 5:34:  :4 : c:  :  :8 :d : 8:
    5 :af: 3:1d: 5:4 :  :2 :  :6 :c : 6:a :1 :5 :
     a:9 :  :d :  :  :0a:a1:  :f :7 :9 :b :  :  :
     f:2 :27: f:  :0 :f6:4d:  :  :  :  :  :5 :  :
     4:08:  : 5:  : 8: 5:  :  :  :18: 4: 8:57: 2:
     f: a:  :  :a8: f: c:f : e: 1:9 :c : 4:9 :  :
      :  :  :  :  : 1:  :2 :  :d1:  : 6:e : d:  :
      : f:04:2 :8d:  : 3:  :  :b : 8:  :d6:  : 2:
      :  :  :6 :  : f:  :  : 0:6 :  :51:  :48:19:
      :  :  :69:4 : c:  :c :  : f:  :f4:d :  : f:
     d:0 :0d:b :3 : 3:2 :  :  :6 : b:5 :2 :  : c:
     1:5a: f:f :  :  :7e:3e:  :d :f :0 : d: c: 6:
     1
coefficient:
      :  :4 :  :6 :  :35:  :e :  :  : e: c:  :  :
      :5 :5 :f8:1 : 9: a:3 :5 : b:  :f :  :  :  :
     a:  :2c:  :  :c :  :03:  :2 :  :  :68:c : 5:
    c9:8 :a :  : b:2 :  :  :3 :  : a: d:  :  :a :
      :  :  :8 :  :7b: e:  :e :  :  :a :  :d :  :
      :  :db:  :26: e:  :4 :  :  :  : 0:  :f :5 :
    2 : 7:  : d:  :  :8 : 5:  :75: 3:  :  :4 :4 :
    6 :c :  :  :  :b :  :f : c:  :a :d :b : a:  :
      :  : f:f3:  :  :  :  :  :13:04: f:3 :  :  :
    e :3 :  :d5:a4: 6:  :9 :  :  :  :b : d:  :  :
     9:  :  :  :  :  : a:7 :  :  :  :  :  :c : a:
    2 :  :  :  :  : 2:  :  :15:  :  :  :  :  :  :
    f : 6: 1: 0: 6:  :  :  :  :  :  :c :  : 7:  :
      : d:  :f :  :  :  : 8:b :  :4 :  :  : a:1 :
    a9:  : 9: 0:1e:  :  :4 :3 :  :  : f:  :d :2 :
      :  :a :8 :  :  :  : 7:  :3 :  :3 :9 :7 : c:
      :  :80:  :6d:  :  :  : 4:  :  : a:e4:8 :6 :

4096bits的N，e又不小，正常是解不了了，但是给了个破损的私钥文件，需要修复私钥，google到的修复办法为

  • given a candidate for (p mod 16**(t - 1)), generate all possible candidates for (p mod 16**t) (check against mask for prime1)
  • calculate q = n * invmod(p, 16**t) (and check against mask for prime2)
  • calculate d = invmod(e, 16**t) * (1 + k * (N - p - q + 1)) (and check against mask for private exponent)
  • calculate d_p = invmod(e, 16**t) * (1 + k_p * (p - 1)) (and check against mask for exponent1)
  • calculate d_q = invmod(e, 16**t) * (1 + k_q * (q - 1)) (and check against mask for exponent2)
  • if any of checks failed - check next candidate

修复脚本

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
import re
from itertools import product
from libnum import invmod


def solve_linear(a, b, mod):
    if a & 1 == 0 or b & 1 == 0:
        return None
    return (b * invmod(a, mod)) & (mod - 1)  # hack for mod = power of 2


def to_n(s):
    s = re.sub(r"[^0-9a-f]", "", s)
    return int(s, 16)


def msk(s):
    cleaned = "".join(map(lambda x: x[-2:], s.split(":")))
    return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)


def msk_ranges(s):
    return [range(16) if c == " " else [int(c, 16)] for c in s]


def msk_mask(s):
    return int("".join("0" if c == " " else "f" for c in s), 16)


def msk_val(s):
    return int("".join("0" if c == " " else c for c in s), 16)


E = 65537

N = to_n("""00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
    58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
    d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
    b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
    3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
    bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
    67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
    1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
    31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
    ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
    06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
    7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
    3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
    c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
    4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
    9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
    c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
    09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
    8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
    e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
    c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
    79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
    e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
    d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
    41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
    14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
    32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
    e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
    fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
    4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
    ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
    9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
    08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
    89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
    e8:6c:1d""")

p_ranges, pmask_msk, pmask_val = msk(""" 0: e:  :  :  :c :c :  :  :  :b :  :  :  :  :
      :ab: e: 2: 8:c :  :  : 1:6 :6 : 6: f:d9: 0:
    8 :5c:7 :06:  :  :  :0 : 3:5 :4b:  :6 :  :  :
    2 :  :6 :  :  :  :2 :bc: c:  :85:1 : 1:d : 3:
     1:b4:  : b: 1: 3: d:a :  :  :6e: 0:b :2 :  :
      :b :  :9 :e :  :82:8d:  :  :13:  :  : a: a:
      :  :4 :  :c : f:  :  :7 :e :0a:  :  : b: 5:
      : e:91:3 :  :3c: 9:  : 6:  :  :b5:7d: 1:  :
      :  :  :b :a1:99:6 :4 :3 :c :1a:02:4 :  : 9:
    9 :f : d:bd:  :0 :  :  :  :b3:  : 4:  :e9: 9:
      : d:  :  :7 :  :93:  : e:dc:  : 0:  :e7:  :
    e :  :2 : b: 2:5 :  :  :  :  : c:5f:  :  :e2:
      :  : 9:  :2a:  : e:  :  :2 :  :9f: 7:3 :  :
    b : f:b :  : 8: 7:  :  :f :6 :e :c :  :3 :  :
    f7: 5: 8: 5:  :  :  :  :  : 8: e:  :03: c:  :
    33:76:e : 1:7 : c:  : 0:  :0b:  : a:  : 2: 9:
      :c8:bf:  :  :06: 7:d5:  :02: c:b :e2: 7:2 :
      :  """)

q_ranges, qmask_msk, qmask_val = msk(""" 0: f:  :d0: 1:55: 4:31:  : b:c4:8 :  : e: d:
    34: 3:f :  :  :  :  : 8:99:1 :  : a:0 :  :4 :
    0 :  :f :  :a4:41:2 :  :a :  : 1:  : a: c:  :
      :  : 9:  :  : 2:f4: f:  :  :  :  :1 : 4:9 :
    a :  :  :79:0 :  :  :  :  : 2: 8:b :  :4 : 8:
      :9b: 1:  :d :  :f :e4:  :4 :c :e :  :3 :  :
     7:2 :  :d :8 :2 :7 :  :d :67:fc:e : 0:f9: 7:
    8 :  :  :  :1 :2f:  :51:  :  :2e:0a: e:3d: 6:
    b :  :dd:  : 0:fb:  :f4:  :  :  :b4: 9:c :  :
     a:  :  :  :d :  :  :6b: 2:  :9b: a:60:  :d6:
     0:4f:16:d1:  :  :5 :fc:  :f :  :8 :  :  :  :
     1: 6:e1:9 : e:4 : 6: c: d:d :73: 3:  :  :7 :
      :8 : 9:  :3b:f : 2:  :  :f1: e:  :  :1e:  :
    8 :  :  : 6:0 : 4:99:e :  : 5:  :  : 4:  :  :
      : a:81:64:  :7 :f : 9: d:  :9 :  : 7:93:f :
    ac:8c:  : 8:  : 0: d: 8:  :7 :  :1d:  :f :  :
    1 :a :6 :8 :  :60:  :b3:  :  :  :89:  :  :14:
      :5 """)

_, dmask_msk, dmask_val = msk("""  :  :  : f:8 :a5:d : 2: 0:b :7 :  : 1:  : 4:
     1:0d:  :3 :  :6 :  :  : b:  :  :  :e :  :  :
    0e: 0:db:  :1a:1c:c0:  : e:  :  :99:bc:8 :a5:
    7 :7 :7 : b:  :  : 8: 8:  :7 :55: 2:  :  :f :
    b2:  :  :b :f :4 :  : 8:  :b :  :  :  : 0:  :
    0 :  :6 :9 :  :  :  : b: 4:  : 0: a: 5:07:b :
     9: c:9a: 9:  : 7:9e:  : b:60:f :  :  :  :0 :
      : 3:0 :  :  :  : 1:b :  :  : b: 6:0 :f :  :
      : 2:18: 6: b:1 :  :  :  :  :d3:f3:  :a :  :
     3:  :  :  :  : 3: d: 1: 2:7 :  : d:  : 2: d:
      :  : d:4 :  :d :  :6d: c:a :b6:  :  :  : 1:
    69:  : 7:  :89:  :c :8 :61: d:25: 3:7 :1b: 4:
    b :  :8 :55:  :49: 1:2 :3 :  :1 :e9:a8: 3:  :
    9 :  : 1:f8:d3:  :e :  :d :  :9 :b6:  :  :71:
    1 :  :c1:  : b: 1:  : 6:e :  :64:  :  :1a:c :
      : b:  :bf:c :  : 0:  : 8:a :4 :  :26:a :5 :
    6 :  :  :  :eb:  :e5: a:  :3e:f9:10:0 :  :  :
     6:0 :  : 8:  : 1:72: c:0 : f:5 : f:9c: 0: e:
     7:b :  :  :  :  :d9: 4:  : e:c :68:  :  :  :
     c:  :3a:  :  :a0:ea: 3: 4:  :72:a :d : 8:  :
      :0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
      :  :17:6 :  : c: b:  : f:  :3 : 5:6 :3 :0e:
      : 7:c :3e: 2: 9: 7: 6: f: e: f: 9:  :f3: 9:
    a :c1:6 :  : 1:9 :  :43:  : f: 5:  :0 :27: 4:
    4 :a :  :e9:  : 8: 4:3 :8a: 6:16:d5:c : e: e:
      :d : c:b :a8:  : 7:  : 9:  :7 :7d:  :  :  :
      :  :  :4 :2 :  : 3: 3: 6:  :  :  :7b:0 :  :
     e:  :0 :  :a :  : 5:  :  :  : 5:1 :82:c :0d:
    4 :2 :fd:36: 5:50:0 :  :  :d : f: 6:  :  :e :
    0 :  :  :ce:  :9e:8 :  :0 :d :07:b3:  :  :  :
    0 :e4:  :  :68:b :c :  : c:5 :  :  :3 : 7: 2:
     c:e0:  :5 :  :  :b4:  :ef: 7:  :1 :e : 0:f :
      :6 :  :  :  :e0:c :3 :  :  : 3:  : d:  :  :
     3: 3: c: a:  :b : a:71: 3: 0:a :  :4 :5d:  :
    0 :4 """)

_, dpmask_msk, dpmask_val = msk("""  : 3:2a:  : d:  :  :  :  :0 :1 : f:  :  : 6:
    1 :2 :1b:07: a:e :b :c5:58:7 :  :e8: 7: 1: c:
      : 1:b :a0: 4:0f:5 :67:  :3 :7 :6 :f9:  : c:
      :79: 0:1 :65:  :8 :  :99: d:d :  :2 :9 :0 :
     e:  :0 :  :  :  : d:  :d :7 :6 :a9: a:8b: b:
      :  : 7: a:37:  :  :7 :1 :6 :  :c2: 7:6 :b :
     e:  :  :  :  :  :  :b :3a:5 :  :  :  :  :  :
      :  :  :cd:8 :  : d:  :7 : 3:  : f:e : c:  :
      : a:  :c : f:c : 7:b :5 :  :  :2 :8 :8 :6 :
    0a: a:  :  :3 :db:  : 4:00:  : d:  :b : 5:  :
    20: 2: 5:  :82:  : 0: 6:  :8a:  :7 :  : 8:  :
     4: 1:  :  :  : 8:46:  :  :  :  :  : 0:f :c8:
    2 :  : c:7 :  : 1:  :  :2 : 0: 5:  :  : 1:9b:
     6:9 : 0:74:  :c :  :e :  :  :cb:b :3 :3 :  :
     2:  :  :47:  :2 : 0:5 :  :  : d: 6:83:  :  :
      :c7:  :  :0b:  :  : c:  :3 :8 :  :9 :4 : 7:
    5 :c0:fe:  :f9: 1:  :0 : e: 8:02:  : f:  :c :
    55:61""")

_, dqmask_msk, dqmask_val = msk("""  :0b:7 :4 :0 : 0:6 : 7:7e:  : 5:  : 7:  : a:
    a :d : 0: 6: 4:86:  :  :8 :  :  :  :  :e :8f:
     9:  :  :  : 1:  :2 :  : 7: b:1 :5 : f:  :8 :
      :d :21:  :e : d:  :c9:e : b:  :  :1 :  :  :
      :d :a2:b7:  :  :  :f3:  :42:  :e : c:  :f :
      : 0:f :7 : 4: 5:34:  :4 : c:  :  :8 :d : 8:
    5 :af: 3:1d: 5:4 :  :2 :  :6 :c : 6:a :1 :5 :
     a:9 :  :d :  :  :0a:a1:  :f :7 :9 :b :  :  :
     f:2 :27: f:  :0 :f6:4d:  :  :  :  :  :5 :  :
     4:08:  : 5:  : 8: 5:  :  :  :18: 4: 8:57: 2:
     f: a:  :  :a8: f: c:f : e: 1:9 :c : 4:9 :  :
      :  :  :  :  : 1:  :2 :  :d1:  : 6:e : d:  :
      : f:04:2 :8d:  : 3:  :  :b : 8:  :d6:  : 2:
      :  :  :6 :  : f:  :  : 0:6 :  :51:  :48:19:
      :  :  :69:4 : c:  :c :  : f:  :f4:d :  : f:
     d:0 :0d:b :3 : 3:2 :  :  :6 : b:5 :2 :  : c:
     1:5a: f:f :  :  :7e:3e:  :d :f :0 : d: c: 6:
     1""")


def search(K, Kp, Kq, check_level, break_step):
    max_step = 0
    cands = [0]
    for step in range(1, break_step + 1):
        max_step = max(step, max_step)

        mod = 1 << (4 * step)
        mask = mod - 1

        cands_next = []
        for p, new_digit in product(cands, p_ranges[-step]):
            pval = (new_digit << ((step - 1) * 4)) | p

            if check_level >= 1:
                qval = solve_linear(pval, N & mask, mod)
                if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
                    continue

            if check_level >= 2:
                val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
                if val is None or not check_val(val, mask, dmask_msk, dmask_val):
                    continue

            if check_level >= 3:
                val = solve_linear(E, 1 + Kp * (pval - 1), mod)
                if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
                    continue

            if check_level >= 4:
                val = solve_linear(E, 1 + Kq * (qval - 1), mod)
                if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
                    continue

                if pval * qval == N:
                    print "Kq =", Kq
                    print "pwned"
                    print "p =", pval
                    print "q =", qval
                    p = pval
                    q = qval
                    d = invmod(E, (p - 1) * (q - 1))
                    coef = invmod(p, q)

                    from Crypto.PublicKey import RSA
                    print RSA.construct(map(long, (N, E, d, p, q, coef))).exportKey()
                    quit()

            cands_next.append(pval)

        if not cands_next:
            return False
        cands = cands_next
    return True


def check_val(val, mask, mask_msk, mask_val):
    test_mask = mask_msk & mask
    test_val = mask_val & mask
    return val & test_mask == test_val


for K in range(1, E):
    if K % 100 == 0:
        print "checking", K
    if search(K, 0, 0, check_level=2, break_step=20):
        print "K =", K
        break

for Kp in range(1, E):
    if Kp % 1000 == 0:
        print "checking", Kp
    if search(K, Kp, 0, check_level=3, break_step=30):
        print "Kp =", Kp
        break

for Kq in range(1, E):
    if Kq % 100 == 0:
        print "checking", Kq
    if search(K, Kp, Kq, check_level=4, break_step=9999):
        print "Kq =", Kq
        break

输出

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
43
44
45
46
47
48
49
50
51
52
53
p = 30061432003658510087798871614869318011389940352798147030129806359975911392091235344042288409629143229311060231549478211871643725394470760528211801310601767727834886942210718412087541234398453046895030858579989874035849439867334906873642352112428914855967993998732685221108379784833027771293275558876952608462050146340591449046825135890871650866799299533696175818103240024841274114925018619060818213433528894936128306780366785977567327073724428211445259983614467640785163297734447975723664659822673456683284394386723716344090232882990461174301609971805075768328757325956784604364401827152431260896927633163074694121679
q = 26136662545551829820746942051638228325025130519175536694008242208616774469870765684858288042819063837180243501117310278632509413217676559484513481677689042623348188876598901642459170232360966754692434316796014314498263800234390539118817050074978421973817764644287745302885861277447227180288605200894138168586207384484170481511828680117688324729381172912436910052489279406590356734739774635376711681212908417321705094537960645308009611045658947359297373154395500467689532455017647450616447445444254910371922944620114234547655209970657063715028350418518417105772707885648587233103869340985670430269862943630137067052883
-----BEGIN RSA PRIVATE KEY-----
MIIJKAIBAAKCAgEAwJd4U0VkhH2MxLQg6TNYZ+x4Pmz18FygPu7cJWPQ6yqeuo8Z
UqJnC+dusjS4bVB24GrRA893M9ix6dc75escZQwllv2WILl63h2//fK2v4E+PkdE
Q5i/ZS9nfid1+VZHusTwTmcr2uAadxRAKcGoZ1qP9S6+joIxPUMm1JeGKRUUqWk2
LHbttZDr7G/O1cokHKr2Y/gGomLLJnTTW4JLttXgSTJ7YvgFxPcOhlmb8xclAqo8
l3iEexb9GvVnzwMXl9DGaYXwjfrO7mgkYwYk4eRM+OmtJcfgwBW7tGdIkAObIH8M
F+udE0Srqwilw9zBmIjFzk9ah5sLv73XDqkJWYH6iE9ZYGuEhK3ZxyWM6MDo9yae
N5V84UgpD1HnvZgv9syA5/AyC4lRkk7CbVBTKzt3ctG9Gh+S1xJ5YWHFpH6zhevw
fG1GA8Xm1YEsun7qjVF9Y1U0KrbU3DFa8Znj3IyDC6Iq1TxBSEFUGqnotnC/0/7t
GRcUlBOzF+OLjm9T7eJE6Eoy1lwNqID1/ALpRlXVpNPnxjB3+XPpRFLYE51dv576
OrWWeYJbzRlcBqkAlv1MpHOIGuw8Ed65PeBQAB6sIZehln1rFflsyTR/cNedLdFI
SoFx+BLdMrpkMWAIJksJIgODkBd/86dyV7+JbeTXQCSLe73fM8D/MC7obB0CAwEA
AQKCAgAuZ5DPh6XboqC7eKeBaSTBDaI/cGOmAbt+znDu9WkOcNuEGhzA426u2Jm8
iKVzeXLbSgGIyIFxVaIwtPKyyH6z/kREaF+3DNoFEOgE2WmdJRgJS4SwQOrFB7IJ
HJr5dAeegftg+M0BVQQrcw6uwQHBvXl4W0YA8m/I0hhWGxhxZ6nt0/MArbtDB2NB
OgN9UdJ3sd3iYo2+rM1EO9v9bZyutkPvfyFpzFcfiWPPjWHdJdN+G+Szno9VVUmx
KDZWE+moY96a6HH409juattxnLZgU3EUfMGCm/GUdugeZNCAGs5S+ym/zb6wONig
QlomoldnWHVI66flir8++RALcUFWC46IH2FyrAJfWR+c8E5ns8Z+HlnZFFO+z2i/
xWWc9jqFMqDq0yQccqLUWFqPDVINClfIu7bUoM7QLuEKohdkyTwbcx9zOqVuNg7d
18g+Qrm3Ru+uD0ni85mnwWA3kZPdQ6pvJaEDJzRPp0rpZyjEP4p2FtXDbp7I1gy9
qH834mmrcH2R5RANmJZFIb0T49beAqF7B3wO0AfCpUj1D827JRKCww1OLv02FVAL
NPjcf7aIfecFAHTOc56NOwLdB7MvPw4O5LtUaLTHMUxZ1CIzB/Ks4P9Yn7O0du9n
FxPmYPWCYoXJX+DFOqc3U4atY6bTs2z6QLs6cdPQrltEXeYFRQKCAQEA7iHlusjD
SIy9vtxsYzr2qz6CqMUrd8FtaeYf2SCGXHEGfDlYCVNbS0dktyAkZ27mZxAovKzR
hRwB04PxtNNboTPdo5iDbqC8J8Kxvz6W6TeCjZLDEyoOunrYdE8SyK/1tX7oCrbe
+8Xk3pE5RzypwNZbp7V9gQsjJxe6oZlkRTXEGgJDJ5mV+v29ngoNki+zMhTk6emu
bf23cSmT+f7cw5Cs5+jgaCMrYliciLaejF869+JCcZm2Kj7eCP0lDJ9HMVa+v79n
KPeDyvdj680KMNv3RQhVjfavMsoIriIDfKczduzBdtylgBkLsqozoqmhyL/MuAY3
1VwCrLXipyWIzwKCAQEAzwrQ0VVkMYZ7xIxCnv004/DyDePSOJkU2ToMaE0Bcf+y
pEEu/KjW8aU6TKPNWHnAcCL0nzozoZcYNJyrI195DXiT8wXSaL2uR2gum+E71ov8
5MdIz+z9NTqXJsvRjy5w399n/O+g+XeIObAMGi+/UdLYLgquPVa7Pd37sPt69Cf1
H7TZx9y6+nXH1iCLa5LQm0pgedaQTxbR9EtY/Fj2vIc4I5JxduGb3kFm7D3Sc6Nq
P354hJnmO/diiCjxLhVqHiiPuIrmAOSZ4X4VRWOkPMylKoFkx3HxqW1Zkq/Hk/ms
jM8IUHBtSKd6Vh3//NYUq2SCt2Dys95f6YlonhQfUwKCAQEAwypk7cC8zCkNGe/t
pSYeJBsHWuq9xVhyI+jHEVzmwbygZA9bZ8k5eWj50lw1edAaZT2JJZk93qollQT+
hAT1hBjN/dZxYam6i5u1sdfKNzmXdhBicMJ3b75eyHRGINSVvDpWUvGtrwtxmDfN
ieTd+32zgK/uPGS0WsXH38mntFFsdySDhWEK2ro7PdtfZABUDSeytUMgAmV+gvBg
pvOKW32nOCpUQQUR+XhGUoXZS5KA8cguTIx+EAGWWCegxceEwZsmmmB0W87/5Mj8
y7UwNPsSnTFHbSJQVH/gvVaDJRajx0QjCxerTGE6hSOZTidYwP7w+aGfAO54ArTP
Hc5VYQKCAQBVC3RLCHBnh34/df3HoOqg1tAWtIYdiYPu1tFR5o+5a/bNUZkjX5cr
G1ufL4mh1iEd7r3cyeN7dL0Un2YM2aK3zde386RCMefsnPbIQPR7ZHU05EccYZSA
0NhVr1MdJU5oJzRnyWauElN6nr3Z49MKoTj7cJexynaPKye/wwz2TZN6uqbaWejU
CJ1Vb3jVbzERGLQYV/JfClijqG+c+E4hksmUkwrYckO8P9EvKRXROkbiXejTTwQr
jaqDk42+CD3WtYKTozpnE3/CCDBkmFFWSBlwJEZpRnylw60Pe/TW66/dBw27PPMm
7ORri1cjXCyRWm/3M3N+PtHW9AJtLIbRAoIBABgyTrVuAjXd7qO57px/XHtUXvgX
udo7XstJ9DYLE4roLEj8zUYDFS9KmGjANcmBpcgbKagWN9SqDQSfo8WkEoAue74n
7+8goDbeh0YQ2y0mDmpP34dBwF79USn3O+2lVI+1HXUTfTxOTmLPo5bSsv38HL2t
3Ll6cUCg//M7IAQbpRME3z8gIe0/HNWkZjyRadnBsk1QbEmZ8fBtiEp2LHFjnJLA
SiU+f38+cqqUFcrGBlNvc/7W0SB2a5rp81XRwBGXEGtt+fYlBCWIuHVEih9qFqnP
6VAeL6lKMzIpH1rbIrwFoIpMzyrnAjZGOJZ6bBcbgMFtNLBmJMSlmuSIao8=
-----END RSA PRIVATE KEY-----

然后写入private.pem解密就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

with open('pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e

with open('private.pem', 'r') as f:
    private = RSA.importKey(f)
    oaep = PKCS1_OAEP.new(private)

with open('flag.enc', 'r') as f:
    print oaep.decrypt(f.read())
# PCTF{0h_U_r_ju5t_lik3_g0d}

这里有个坑点是填充方式，不是PKCS1，而是PKCS1_OAEP，反正rsa填充方式就3种，一种一种试就行了，在线网站解方便一点

tool.chacuo.net/cryptrsaprikey

不过注意一下在线解密内容需要先base64，不然不可见字符你也输不进去。

1
2
➜  godlikeRSA cat flag.enc | base64
JP1VehHnCOCVdVq+nGBKaDGH//PFuuRJRIbykZ+JUhkgrZsMDyOxcTKfZ3DdAGrxZXGE2x66BgW153l5ASiMxqNnzwoDy+/5E1fXo/ZUjN10see070ljLHYviAinkrpTs44joMx6n6nqBvqObERsOl6fC18eWWQFG7XnNQEp74IHs0GNV9PTVXXuEeDopRhHfjxiPzZEDJT6JwhY+XWaa2otfArjE4bT1UMvw6Q66rJ2M/z7vTuxmqz/xKDU+ZIZoQ5u1ppIxaq+5LOZvQvva8/yrYHZgEnKSuQjG7QBzJN5lLdi3bFeEWTe0VgT5KX2ydSGH0dNqo66wx9c4m7gReV2zW/P/K90Xn47frpGX8HNfQU1+53Qe9DGkAptfLkXP3z34EWU7mRBGWgSdonkZERWmk6ZQXTtEQH9OZMZW8rulIsZ2iTlIAfB0ZbiynoarxAamBzOJO77NkQZnRM5Nqy43v+ffAXqGBcFeeZwJ8St7zOOb4XIe0vNYZK1WCaN/a5bK+obYTAsLEUYd7NspM/HFyP7oYMzk4lgsRXJTdk5C2xy8pj3Y4aDHtcwT+MXEiOlve83X3idKs8EqwznUM1ZnvBXUqhWDBt7/JVKBxdN4OIdjSJtUJa47PnYsLrJVTB4bu5V8NJMzl5EoN/kAFAS5B84j0IfO6TEywmkt/M=

rsa

简单ECC概念

已知椭圆曲线加密Ep(a,b)参数为

p = 15424654874903

a = 16546484

b = 4548674875

G(6478678675,5636379357093)

私钥为

k = 546768

求公钥K(x,y)

提示：K=kG

提交格式XUSTCTF{x+y}(注意，大括号里面是x和y加起来求和，不是用加号连接)

注：题目来源XUSTCTF2016

那就先来了解一下ECC

ECC全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短秘钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有

  • 以素数为模的整数域GF(p)，通常在通用处理器上更为有效。
  • 特征为2的伽罗华域GF（2^m），可以设计专门的硬件。

baidu + google + duckduckgo 了一圈回来发现没有wp，网上关于ecc的ctf题少的可怜，这个什么XUSTCTF2016更是找不到这题的wp

那么照着ecc的定义自己算吧，什么离散函数，有限域的，略蛋疼，还好这题简单

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
a = 16546484
M = 15424654874903
G = (6478678675, 5636379357093)
K = (0, 0)


def add(A, B):
    if A == (0, 0):
        return B
    if B == (0, 0):
        return A
    x1, y1 = A
    x2, y2 = B
    if A != B:
        p = (y2 - y1) * pow(x2 - x1, M - 2, M)
    else:
        p = (3 * x1 * x1 + a) * pow(2 * y1, M - 2, M)
    x3 = p * p - x1 - x2
    y3 = p * (x1 - x3) - y1
    return (x3 % M, y3 % M)


for i in range(546768):
    K = add(K, G)
print 'XUSTCTF{%d}' % (K[0] + K[1])
# XUSTCTF{19477226185390}

神秘的压缩包

就不告诉你密码，看你怎么办。

注：题目来源XUSTCTF2016

crc32爆破

crc32_util.py

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
# -*- coding: utf-8 -*-

import itertools
import binascii
import string


class crc32_reverse_class(object):
    def __init__(self, crc32, length, tbl=string.printable,
                 poly=0xEDB88320, accum=0):
        self.char_set = set(map(ord, tbl))
        self.crc32 = crc32
        self.length = length
        self.poly = poly
        self.accum = accum
        self.table = []
        self.table_reverse = []

    def init_tables(self, poly, reverse=True):
        # build CRC32 table
        for i in range(256):
            for j in range(8):
                if i & 1:
                    i >>= 1
                    i ^= poly
                else:
                    i >>= 1
            self.table.append(i)
        assert len(self.table) == 256, "table is wrong size"
        # build reverse table
        if reverse:
            found_none = set()
            found_multiple = set()
            for i in range(256):
                found = []
                for j in range(256):
                    if self.table[j] >> 24 == i:
                        found.append(j)
                self.table_reverse.append(tuple(found))
                if not found:
                    found_none.add(i)
                elif len(found) > 1:
                    found_multiple.add(i)
            assert len(self.table_reverse) == 256, "reverse table is wrong size"

    def rangess(self, i):
        return ', '.join(map(lambda x: '[{0},{1}]'.format(*x), self.ranges(i)))

    def ranges(self, i):
        for kg in itertools.groupby(enumerate(i), lambda x: x[1] - x[0]):
            g = list(kg[1])
            yield g[0][1], g[-1][1]

    def calc(self, data, accum=0):
        accum = ~accum
        for b in data:
            accum = self.table[(accum ^ b) & 0xFF] ^ (
                (accum >> 8) & 0x00FFFFFF)
        accum = ~accum
        return accum & 0xFFFFFFFF

    def findReverse(self, desired, accum):
        solutions = set()
        accum = ~accum
        stack = [(~desired,)]
        while stack:
            node = stack.pop()
            for j in self.table_reverse[(node[0] >> 24) & 0xFF]:
                if len(node) == 4:
                    a = accum
                    data = []
                    node = node[1:] + (j,)
                    for i in range(3, -1, -1):
                        data.append((a ^ node[i]) & 0xFF)
                        a >>= 8
                        a ^= self.table[node[i]]
                    solutions.add(tuple(data))
                else:
                    stack.append(((node[0] ^ self.table[j]) << 8,) + node[1:] + (j,))
        return solutions

    def dfs(self, length, outlist=['']):
        tmp_list = []
        if length == 0:
            return outlist
        for list_item in outlist:
            tmp_list.extend([list_item + chr(x) for x in self.char_set])
        return self.dfs(length - 1, tmp_list)

    def run_reverse(self):
        self.init_tables(self.poly)
        desired = self.crc32
        accum = self.accum
        if self.length >= 4:
            patches = self.findReverse(desired, accum)
            for patch in patches:
                checksum = self.calc(patch, accum)
                print 'verification checksum: 0x{0:08x} ({1})'.format(
                    checksum, 'OK' if checksum == desired else 'ERROR')
            for item in self.dfs(self.length - 4):
                patch = map(ord, item)
                patches = self.findReverse(desired, self.calc(patch, accum))
                for last_4_bytes in patches:
                    if all(p in self.char_set for p in last_4_bytes):
                        patch.extend(last_4_bytes)
                        print '[find]: {1} ({0})'.format(
                            'OK' if self.calc(patch, accum) == desired else 'ERROR', ''.join(map(chr, patch)))
        else:
            for item in self.dfs(self.length):
                if crc32(item) == desired:
                    print '[find]: {0} (OK)'.format(item)


def crc32_reverse(crc32, length, char_set=string.printable,
                  poly=0xEDB88320, accum=0):
    obj = crc32_reverse_class(crc32, length, char_set, poly, accum)
    obj.run_reverse()


def crc32(s):
    return binascii.crc32(s) & 0xffffffff

smdysb.py

1
2
3
4
5
6
7
8
9
10
11
from crc32_5byte import *

l = [0x20AE9F17,
     0xD2D0067E,
     0x6C53518D,
     0x80DF4DC3,
     0x3F637A50,
     0xBCD9703B]

for k in l:
    crc32_reverse(k, 5)

运行脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
➜  crypto python smdysb.py
verification checksum: 0x20ae9f17 (OK)
[find]: l./rc (OK)
[find]: passw (OK)
verification checksum: 0xd2d0067e (OK)
[find]: "_YWn (OK)
[find]: N,tS* (OK)
[find]: Rc(R> (OK)
[find]: ord:f (OK)
[find]: s=8;r (OK)
verification checksum: 0x6c53518d (OK)
[find]: /8LWp (OK)
[find]: CKaS4 (OK)
[find]: ~Z-;l (OK)
verification checksum: 0x80df4dc3 (OK)
[find]: apEwF (OK)
verification checksum: 0x3f637a50 (OK)
^Q6w (OK)
[find]: \<0Zk (OK)
[find]: a-|23 (OK)
[find]: }b 3' (OK)
verification checksum: 0xbcd9703b (OK)
[find]: hyAo5 (OK)

这么多重合的crc32，巨坑，手动一个一个试，最后得到

password:f~Z-;lapEwF\<0ZkhyAo5

解压rar得到flag

XUSTCTF{6ebd0342caa3cf39981b98ee24a1f0ac}