0xGame2024:

week1:

Number-Theory-CRT

题面：

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
from Crypto.Util.number import bytes_to_long, getPrime
from hashlib import md5
from random import randint
from gmpy2 import invert,gcd

#Hash Function:
def MD5(m):return md5(str(m).encode()).hexdigest()

#RSA AlgorithmParameter Generation Function:
def KeyGen():
	Factor_BitLength = 30
	q = getPrime(Factor_BitLength)
	p = getPrime(Factor_BitLength)
	N = p * q
	#Euler's totient function:
	phi = (p-1) * (q-1)

	#Generate Keys:
	e = randint(1,phi)

	#Generate Result:
	Pub_Key = (N,e)
	return Pub_Key

Pub = KeyGen()

N = Pub[0]
e = Pub[1]

#RSA Encrypt:
m = randint(1,N)
c = pow(m,e,N)

print(f'Pub_Key = {Pub}')
print(f'Encrypt_msg = {c}')

'''
Pub_Key = (1022053332886345327, 294200073186305890)
Encrypt_msg = 107033510346108389
'''

flag = '0xGame{'+ MD5(m) +'}'

分析：

发现e,phi不互素，gcd(e,phi)=2
$$
gcd(e,\phi(n)) \neq 1\newline
m^e≡(m^{gcd(e,\phi(n))})^{\frac{e}{gcd(e,\phi(n))}}≡c\ (mod\ n)\newline
当gcd(e,\phi(n))较小时，可以直接对c开根，有两种情况：
$$

$$
\begin{cases}
m^e≡c<n,这种情况直接对c开e次方即可\
m^e≡c>n,这种情况需要在有限域下对c开方，一般先计算c_p = c\ mod\ p,c_q = c\ mod\ q，分别求出c_p,c_q在c下的e次方(可能有多个)，然后使用CRT遍历所有组合，分别check得出明文
\end{cases}
$$

解释一下吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
'''
这段代码是在Sage数学软件中运行的，用于求解一个在模质数p意义下的方程x^e=c的解。

代码定义了一个多项式环R，请注意 R.<x> = Zmod(p)[] 这一句。这里 R 表示多项式环的名称，<x> 表示所定义的环中的变量名是x，而 Zmod(p)[] 表示在模p的意义下定义了一个多项式。其中每个多项式的系数都是p的倍数，以确保在模p的意义下进行运算时不会出现浮点运算精度的问题。

接下来，代码定义了一个多项式 f = x^e - c。变量c和e在代码中的定义可能来自其他地方。通过将这个方程的领导系数归一化，再去除它，这个多项式被调整为monic的形式，并被保存在变量f中，以便计算方程的根。

接下来，代码再次调用了多项式 f 的roots() 方法，这一次将得到方程的一个根的列表。具体地，最终生成的变量res1是多项式f在模p意义下的根列表。注意，如果方程没有解，则res1变量将为空列表。
'''

题解：

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
from Crypto.Util.number import *
from gmpy2 import *
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()

N = 1022053332886345327
e = 294200073186305890
c = 107033510346108389

p = 970868179
q = 1052721013

phi = (p-1)*(q-1)
gcd = GCD(phi,e)
print(gcd)

d_ = invert(e//gcd,phi)
m_2 = pow(c,d_,N)

PR.<x> = Zmod(p)[]
f = x^gcd - c
res1 = f.roots()


PR.<x> = Zmod(q)[]
f = x^gcd - c
res2 = f.roots()

for r1 in res1:
    for r2 in res2:
        m = crt([r1,r2],[p,q])
        flag = '0xGame{'+ MD5(m) +'}'
        print(flag)

week2:

RSA-IV

题面：

task.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
from os import urandom
from hashlib import sha256
from random import choice, getrandbits
from string import ascii_letters, digits

from challenge import *
from secret import flag

def proof_of_work():
	proof = ''.join([choice(ascii_letters+digits) for _ in range(20)])
	_hexdigest = sha256(proof.encode()).hexdigest()
	print(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}")
	x = input('[+] Plz tell me XXXX: ')
	if len(x) != 4 or sha256( (x+proof[4:]).encode() ).hexdigest() != _hexdigest:
		return False
	return True

def choice_(num):
	if num not in [0,1,2,3]:return
	global scores
	m = getrandbits(96)

	match num:
		case 0:
			print( challenge0(m) )
		case 1:
			print( challenge1(m) )
		case 2:
			print( challenge2(m) )
		case 3:
			print( challenge3(m) )

	print('[+] input answer:')
	m_= int(input('>'))
	scores[num] = (m_==m)
	score_= sum(scores)
	print(f'[+] score:{score_}')

	if score_ == 4:
		print(f'[+] flag:{flag}')
		exit()

assert proof_of_work()
scores = [0, 0, 0, 0]
while True:
	print('[+] input choice:')
	choice_( int(input('>')) )

challenge.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
from Crypto.Util.number import getPrime, inverse, bytes_to_long

def challenge0(m):
	p = getPrime(150)
	q = getPrime(150)
	N = p * q
	e = 3
	c = pow(m, e, N)
	return (N, e, c)

def challenge1(m):
	p = getPrime(64)
	q = getPrime(64)
	N = p * q
	e = 0x10001
	dp = inverse(e, p-1)
	c = pow(m, e, N)
	return (N, e, c, dp)

def challenge2(m):
	p = getPrime(64)
	q = getPrime(64)
	N = p * q
	phi = (p-1) * (q-1)
	d = getPrime(21)
	e = inverse(d, phi)
	c = pow(m, e, N)
	return (N, e, c)

def challenge3(m):
	p = getPrime(64)
	q = getPrime(64)
	N = p * q
	e = getPrime(127)
	c = pow(m, e , N)
	e_= getPrime(127)
	c_= pow(m, e_, N)
	return (N, e, c, e_, c_)

分析：

很综合全面的一道题，考了sha256爆破，pwntools的使用和开方，dp泄露，wiener攻击和共模攻击

题解：

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
from Crypto.Util.number import *
from gmpy2 import *
import hashlib 
import string
from pwn import *
from RSAwienerHacker import *

r = remote('118.195.138.159',10003)

sa = lambda s,n : r.sendafter(s,n)
sla = lambda s,n : r.sendlineafter(s,n)
sl = lambda s : r.sendline(s)
sd = lambda s : r.send(s)
rc = lambda n : r.recv(n)
ru = lambda s : r.recvuntil(s)

def proof_of_work():
    dic = string.digits+string.ascii_lowercase+string.ascii_uppercase
    ru('XXXX+')
    part = ru(')')[:-1].decode()
    ru('== ')
    goal = ru('\n')[:-1].decode()
    print(goal)

    for i1 in dic:
        for i2 in dic:
            for i3 in dic:
                for i4 in dic:
                    tmp = i1+i2+i3+i4+part
                    sha = hashlib.sha256(tmp.encode('utf-8')).hexdigest()
                    if sha == goal:
                        sl(i1+i2+i3+i4)
                        print(i1+i2+i3+i4)
                        break 

def chose(num):
    ru('>')
    sl(str(num))

def challenge0():
    data = ru(')')
    N,e,c = data.decode()[1:-1].split(',')
    N,e,c = int(N),int(e),int(c)
    print(N)
    m = iroot(c,3)[0]
    sl(str(m))

def challenge1():
    data = ru('>')
    data = ru(')')
    N,e,c,dp = data.decode()[1:-1].split(',')
    N,e,c,dp = int(N),int(e),int(c),int(dp)
    for x in range(1,e):
        if e*dp%x == 1:
            p = (e*dp-1)//x+1
            if N%p != 0:
                continue
            q = N//p
            phi = (p-1)*(q-1)
            d = invert(e,phi)
            m = pow(c,d,N)
            sl(str(m))

def challenge2():
    data = ru('>')
    data = ru(')')
    N,e,c = data.decode()[1:-1].split(',')
    N,e,c = int(N),int(e),int(c)
    d = hack_RSA(e,N)
    m = pow(c,d,N)
    sl(str(m))

def challenge3():
    data = ru('>')
    data = ru(')')
    N,e,c,e_,c_ = data.decode()[1:-1].split(',')
    N,e,c,e_,c_ = int(N),int(e),int(c),int(e_),int(c_)
    
    gcd, s, r = gcdext(e, e_)
    if s < 0:
        s = -s
        c = invert(c, N)
    if r < 0:
        r = -r
        c_ = invert(c_, N)
    m = pow(c, s, N) * pow(c_, r, N) % N
    m = iroot(m,gcd)[0]
    sl(str(m))

proof_of_work()
chose(0)
challenge0()
chose(1)
challenge1()
chose(2)
challenge2()
chose(3)
challenge3()


r.interactive()