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()