Jarvis OJ -- crypto题write up

-回复 -浏览
楼主 2019-11-12 13:53:09
举报 只看此人 收藏本贴 楼主


  • 那年春天我迷失在梦里

  • 那年夏天像她一样恬静

  • 那年秋天的风映入慌乱的耳际

  • 那年冬天身边缺了你




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头

有个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头,可以看到

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:
   58c:76:
 3:9d:5d:bf:9e:
   fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
   4c:AAOCAg8AMIICCgKCAgEAwJd4U0VkhH2MxLQg6TNY
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==
ps:因为字数原因,省略这儿的内容。具体可以自己根据思路来复现查看!建议访问
原文链接

-----END PUBLIC KEY-----


然后题目给了个private.corrupted



上面就是给所给文件大体内容,由于字数限制,无法将全部复制,可以阅读原文查看!

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
Q。。。。。因为字数原因这里省略这个key的内容
-----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=


简单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}


剩余题目链接:
Jarvis OJ -- crypto题(中):https://d001um3.github.io/2017/12/01/Jarvis_crypto_2/

Jarvis OJ -- crypto题(下):https://d001um3.github.io/2017/12/05/Jarvis_crypto_3/

差一题AK!



我要推荐
转发到