Wp for NCTF2020's Crypto
题目很难，嗯，就是很难
题目质量（我啥也不会也不敢评论）
我是废物！（大声）
RRSA
签到题，看完代码后发现是共膜，而且可以拿五次c，exgcd解决即可
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
| from string import digits, ascii_letters
from pwn import *
from hashlib import sha256
from Crypto.Util.number import *
from gmpy2 import *
table = '1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
r = remote("42.192.180.50", "30002")
def passpow():
rev = r.recvuntil("sha256(XXXX+")
suffix = r.recv(16).decode()
r.recvuntil(" == ")
res = r.recv(64).decode()
def f(x):
hashresult = hashlib.sha256((x+suffix).encode()).hexdigest()
if hashresult == res:
return 1
else:
return 0
prefix = util.iters.mbruteforce(f,table,4,'upto')
r.sendline(str(prefix))
r.recvuntil("Give me XXXX: ")
def read_data():
e = int(r.recvuntil(", ").strip().decode()[:-1])
n = int(r.recvuntil("\n").strip().decode())
return e,n
passpow()
print('Successfully pass!')
r.recvuntil("My public key: ")
e1,n1 = read_data()
r.recvuntil("Your choice: ")
r.sendline('4')
r.recvuntil("encflag: ")
c1 = int(r.recvline(False).strip().decode())
r.recvuntil("Your choice: ")
r.sendline('3')
r.recvuntil("My new public key: ")
e2,n2 = read_data()
r.recvuntil("Your choice: ")
r.sendline('4')
r.recvuntil("encflag: ")
c2 = int(r.recvline(False).strip().decode())
gcd, s, t = gcdext(e1, e2)
if(n1 == n2):
n = n1
if (s < 0):
s = -s
c1 = inverse(c1, n)
if (t < 0):
t = -t
c2 = inverse(c2, n)
plain = (pow(c1,s,n) % n) * (pow(c2,t,n) % n) % n
print(long_to_bytes(plain))
|
NCTF{W3_1augh3d_4nd_k3pt_say1ng_s33_u_s00n__but_ins1d3_w3_b0th_kn3w_we_d_n3ver_see_e4ch_0ther_4gain}
RSA_revenge
Waiting for update……
Oracle
此题是个有趣的题目，服务器会解密我们的数据，随后判断转换为bytes后首位（也就是二进制前8位）是否为0
分析：
- 服务器只会告诉我们前8位是不是0，而并不能保证其后面的部分
- 如果我们想要得到明文的性质，就要想办法找到一个确切的关系，那么我们的任务即是将服务器中的条件转化或扩展成更加确切的值
bytes最大1024位，而已知前8位，所以如果想要得到确切可控的数，最好的办法就是使得后面的全部为0，那么我们就可以利用服务器的条件，构造 $x$ 满足 $x\cdot m=2^{1016}$ ，从而求出明文
方法：
- 首先计算 $m\times 2^{cnt}$ 找到临界的 $x$ 使得其满足 $x\cdot m<2^{1016}<n$ （原因是为了避免出现 $x\cdot m=2^{1016}+k\cdot n$ 这种情况）
- 二分查找 $x$
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
| from string import digits, ascii_letters
from pwn import *
from hashlib import sha256
from Crypto.Util.number import *
r = remote("42.192.180.50", "30001")
def read_data():
e = int(r.recvline().strip().decode())
n = int(r.recvline().strip().decode())
c = int(r.recvline().strip().decode())
return e,n,c
def talk(x):
r.recvuntil("> ")
r.sendline(str(x))
res = r.recvline(False)
return (b'True' in res)
e,n,c=read_data()
print("Successfully get data!")
cnt = 0
while(1):
cnt += 1
res = c * pow(pow(2, cnt , n), e, n)
back = talk(res)
if(back == False):
break
print("Successfully get the range!")
upper = 2 ** cnt
lower = 2 ** (cnt-1)
while(lower+1 < upper):
mid = (upper + lower) // 2
res = c * pow(mid, e, n) % n
back = talk(res)
if(back):
lower = mid
else:
upper = mid
m = 2 ** (1024 - 8)
print(long_to_bytes(m//lower))
print(long_to_bytes(m//upper))
|
NCTF{M4rry_1n_hast3__4nd_r3pen7_4t_le1sure}
RDH
Waiting for update……
RRSA
Waiting for update……
wechat
