24Nov3

huangx607087 11月的切题3

0.Introduction

遇到了几个复杂的题目，对着题解看了2个小时也没有读懂，感觉再这么下去自己迟早得崩。

上一周几乎没看文献，前3天也就整理了一下之前上课学的内容，后面还有一堆pre得做>

本篇博客由于题目很难，因此多数还是参考了wp做的，如果各位师傅们发现里面引用了你的wp，但没有做标注的话，请邮件联系我，注明博文的title,date以及给出你的wp的地址，我会酌情加上引用（如果我当时确实没想出来的话，一些过于简单的知识不在此范围内），感谢。

（12.2考密码学，无线数字通信技术估计也是12月初考试了，12.15CISCN初赛，期末又有一堆东西要背，也不知道后面会怎么样）

1.[2024强网杯]electronic_game

1x01 题目大意

还是先看一下题目：

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
from sage.all import *
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
from Crypto.Util.number import * 
from base64 import b64encode
from random import * 
from secret import flag
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 66
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

def qary_trans_to_int(x, q):
    return sum([int(x[i]) * q**i for i in range(len(x))])

def encode(f, q):
    try:
        return b64encode(long_to_bytes(qary_trans_to_int(f.polynomial().coefficients(sparse = False), q)))
    except:
        return b64encode(long_to_bytes(qary_trans_to_int(f.coefficients(sparse = False), q)))

def generate_irreducible_polynomial(R, n):
    while True: 
        f = R.random_element(degree=n) 
        while f.degree() != n:
            f = R.random_element(degree=n) 
        if f.is_irreducible():
            return f

def generate_sparse_irreducible_polynomial(R, n): 
    x = R.gen()
    while True:
        g = sum(choice([-1, 0, 1]) * x**i for i in range(randint(1, n//2 + 1)))
        if (x**n + g + 1).is_irreducible():
            return x**n + g + 1

def random_polynomial(R, n, beta):  
    return sum(randrange(-beta, beta) * R.gen()**i for i in range(randint(0, n))) + R.gen()**n  

q = 333337
n = 128
beta = 333 
chance = 111
polyns = beta//chance
bound  = 106
R = PolynomialRing(GF(q),'x')

F = generate_irreducible_polynomial(R,n).monic()

k1 = GF(q**n, name = 'a', modulus = generate_sparse_irreducible_polynomial(R,n).monic())
k2 = GF(q**n, name = 'b', modulus = F)

phi = FiniteFieldHomomorphism_generic(Hom(k1, k2)) 

print("F:", encode(F,q).decode())

win_count = 0
for _ in range(chance):
    opt = randint(0, 1)
    if opt:
        As = [phi(random_polynomial(k1,n,beta)) for i in range(polyns)] 
    else:
        As = [k2.random_element() for i in range(polyns)]
    
    for i in range(polyns):
        print(f"As[{i}]: {encode(As[i],q).decode()}")

    opt_guess = input("Guess the option[0/1]: ")
    if int(opt_guess) != opt:
        print("Wrong guess!")
    else:
        win_count += 1
        print("Correct guess!")

if win_count >= bound:
    print("You are so smart! Here is your flag:")
    print(flag)
else:
    print("No flag for you!")

题目给出了两个有限域 $K_1$ 和 $K_2$，均为 $GF(333337^{128})$，只是选择的模多项式不同。其中 $K_1$ 的模多项式系数均为 $0,1,-1$，且除了 $x^{128}$ 项之外，所有的项次数不超过 $64$。而 $K_2$ 的模多项式为随机的。

此外，这里还生成了一个域同态 $\phi$ ，也就是 $K_1$ 到 $K_2$ 上的映射方式。很显然，因为这两个域的元素个数一样，群元素的阶一样，那么一定是存在同态的。然后要求你区分一个结果 $W(x)$ 是在 $K_1$ 上小系数多项式 $A(X)$ 同态到 $K_2$ 得到的 $\phi(A(x))$ ，还是仅仅在 $K_2$ 上随机取的一个多项式。

参考了一下糖醋小鸡块的blog，发现正解是和多项式元素的迹有关。速速地补基础知识。

1x02 基础知识

1x02o01 不同模多项式下的 $GF(q^n)$ 之间的同态是什么？

由于有限域的模多项式肯定是不可约多项式，类比素数 $p$ 有原根 $g$，不可约多项式 $p(x)$ 也有原根 $g(x)$，其原根 $g(x)$ 满足 $g^{p^n-1}(x)\equiv 1\pmod {p(x)}$，且对于任意 $k|p^{n}-1$，$g^{k}(x)\not \equiv 1 \pmod {p(x)}$，也就是指数必须到达 $p^n-1$ 才等于 $1$，达不到 $p^{n}-1$ 一定不等于 $1$。

举个简单的例子： $B_1=GF(2^{8},x^8+x^4+x^3+x^2+1)$ 和 $B_2=GF(2^8,x^8+x^4+x^3+x+1)$。对于 $B_1$ 中的模多项式 $x^8+x^4+x^3+x^2+1$，可以发现该多项式的一个原根为 $x$，因为 $2^{8}-1=255=3\times5\times17$。而 $x$ 不是 $x^8+x^4+x^3+x+1$ 的原根，因为 $x^{51}\equiv 1\pmod {x^8+x^4+x^3+x+1}$，指数还没达到 $255$ ，结果已经等于 $1$ 了。

但经过验证，$x+1$ 是 $x^8+x^4+x^3+x+1$ 的原根，因此，如果能把 $B_1$ 上的 $x$ 看作 $B_2$ 上的 $x+1$，呃，我们这里还是用 $u$ 和 $v$ 来区分 $B_1$ 和 $B_2$ 上的元素吧。也就是，如果把 $B_1$ 中的 $u$，看作 $B_2$ 上的 $v+1$，那么会产生什么效果？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sage: B1.<u>=GF(2**8,modulus=[1,0,1,1,1,0,0,0,1])
sage: B2.<v>=GF(2**8,modulus=[1,1,0,1,1,0,0,0,1])
sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
sage: phi=FiniteFieldHomomorphism_generic(Hom(B1,B2))
sage: phi
Ring morphism:
  From: Finite Field in u of size 2^8
  To:   Finite Field in v of size 2^8
  Defn: u |--> v + 1
sage: u**116
u^7 + u^6 + u^5 + u^4 + u^3
sage: (v+1)**116
v^7 + v^2 + v + 1
sage: R.<x>=PolynomialRing(GF(2)) #构造复合函数x^7+x^6+x^5+x^4+x^3
sage: ((x+1)**7+(x+1)**6+(x+1)**5+(x+1)**4+(x+1)**3)%(x^8+x^4+x^3+x+1)
x^7 + x^2 + x + 1

也就是说， $B_1$ 中的 $u$ 等价于 $B_2$ 中的 $v+1$。不仅仅是原根的关系，如果我们随机取 $u^{116}$，结果为 $u^7+u^6+u^5+u^4+u^3$，那么如果我们把 $u$ 全部替换成 $v+1$，那么在 $B_2$ 的意义下，结果为 $v^7+v^2+v+1$ （具体看上面代码），即 $B_1$ 中的 $u$ 和在 $B_2$ 中的 $v+1$ 是 等价的 。因此同态也就这么产生了（域的性质应该都懂吧）。

当然，也可以这么反过来同态，也就是 $B_2$ 中的 $v$ 等价于 $B_1$ 中的 $u+1$，可以看到这两个的阶都是 $51$，相当于 $B_2$ 的一个 $51$ 个元素的子域也可以同态到 $B_1$ 上的一个 $51$ 元素的子域。 

1
2
3
4
5
6
7
8
9
10
sage: phinv=FiniteFieldHomomorphism_generic(Hom(B2,B1))
sage: phinv
Ring morphism:
  From: Finite Field in v of size 2^8
  To:   Finite Field in u of size 2^8
  Defn: v |--> u + 1
sage: (u+1)**51
1
sage: v**51
1

当然，并不是原根都是 $x$，就可以从 $x$ 同态到 $x$ 的，比如下面这个例子 （你自己想想，下面这个 $C$ 中的 $u$ 能和 $D$ 中的 $v$ 等价吗，假如 $C([0,1])\equiv D([0,1])$，你构造个复合函数试试看，模多项式都不一样，直接放过去还能一样？）

注： $\mathbb F_7[x]$ 中，$x^3+x+1$ 和 $x^3+2x^2+4x+2$ 都是不可约多项式，且 $x$ 都是它们的原根。

为啥这个同态过去是 $5v^2+6v+6$ 呢？随机取 $u^{100}=4u^2+3u+3$，你构造 $f(x)=4x^2+3x+3$，然后计算 $f(5v^2+6v+6) \bmod (x^3+2x^2+4x+2)$，计算结果肯定和预想的一样，这样才是有意义的同态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
sage: C.<u>=GF(7**3,modulus=[1,1,0,1])
sage: D.<v>=GF(7**3,modulus=[2,4,2,1])
sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
sage: phi=FiniteFieldHomomorphism_generic(Hom(C,D))
sage: phi
Ring morphism:
  From: Finite Field in u of size 7^3
  To:   Finite Field in v of size 7^3
  Defn: u |--> 5*v^2 + 6*v + 6
sage: u**100
4*u^2 + 3*u + 3
sage: R.<x>=PolynomialRing(GF(7))
sage: f=4*x^2+3*x+3
sage: phi(u**100)
3*v^2 + 2*v + 1
sage: (5*v^2+6*v+6)**100
3*v^2 + 2*v + 1
sage: f(5*x^2+6*x+6)%(x^3+2*x^2+4*x+2)
3*x^2 + 2*x + 1

1x02o02 什么是域中元素的共轭，迹和极小多项式。

上次你听到共轭这个说法，还是在复数域中的共轭复数那一块。也就是 $a+b\mathrm i$ 的共轭复数是 $a-b\mathrm i$。而域 $\mathbb F_{p^n}$ 中某元素 $\alpha$ 的共轭一共有 $n-1$ 个，为 $\alpha^q,\alpha^{q^2},\alpha^{q^{3}},…,\alpha^{q^{n-1}}$，这又是为什么呢？

还是从复数域开始： 在 $\mathbb C_7$ 中 $3+2\mathrm i$ 的共轭复数是 $3+5\mathrm i$，这个能理解。并且你会发现，在 $\mathbb C$ 中，两个共轭复数相加之后，只剩下了实部，虚部清零

1
2
3
4
5
sage: C7.<img>=GF(49,modulus=[1,0,1])
sage: pow(3+2*img,7)
5*img + 3
sage: (3+2*img)+(3+5*img)
6

然后扩展到三阶，任意元素 $a$ 和其两个共轭 $a^{p},a^{p^2}$ 相加，也得到了一个数值，$u,u^2$ 清零。

1
2
3
4
5
6
7
8
9
10
sage: D13.<u>=GF(11**3)
sage: D13.modulus()
x^3 + 2*x + 9
sage: a=D13.random_element()
sage: a
10*u^2 + 3*u + 4
sage: a+(a**11)+(a**121)
5
sage: a.trace()
5

这也就是 $\alpha $ 的迹的定义。

当然，$\alpha$ 和它的 $n$ 个共轭可以成为一个一元 $n$ 次方程 $(x-\alpha)(x-\alpha^{p^2})\cdots(x-\alpha^{p^{n-1}})=0$ 的所有根。计等号左边为 $f$，通过根与系数的比较关系可以发现，$-f[n-1]$ 为 $n$ 个根之和，也就是 $x^{n-1}$ 次系数的相反数为 $\alpha$ 的迹。

1x02o03 同态前后迹不变的原因、$K_1$ 中小系数多项式迹很小的原因。

这边有两个域 $F,G$，换个大点的数字，看看实验结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from random import *
p=1435756429
R.<x>=PolynomialRing(GF(p))
fp2=[1281051561, 325824623, 587085269, 519016661, 607488613, 349057141, 1328077096, 1307270920, 561010408, 1114525395, 117794890, 713439535, 696507390, 529855506, 773150011, 251203247, 1]
fp1=[1, -1, 0, 1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
F.<u>=GF(p**16,modulus=fp1)
G.<v>=GF(p**16,modulus=fp2)
from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
phi = FiniteFieldHomomorphism_generic(Hom(F, G)) 
listAx=[randint(-607,607) for _ in range(16)]
print(listAx)
#[-133, 543, 547, -416, -20, -228, 340, 578, 460, -394, 147, 153, -237, -589, 521, 117]
Axf=F(listAx)
Axg=phi(F(listAx))
Bx=G.random_element()
print(Axf.trace(),Axg.trace(),Bx.trace())
#[-133, 543, 547, -416, -20, -228, 340, 578, 460, -394, 147, 153, -237, -589, 521, 117]
#8967 8967 965643423
print(Axf)
#117*u^15 + 521*u^14 + 1435755840*u^13 + 1435756192*u^12 + 153*u^11 + 147*u^10 + 1435756035*u^9 + 460*u^8 + 578*u^7 + 340*u^6 + 1435756201*u^5 + 1435756409*u^4 + 1435756013*u^3 + 547*u^2 + 543*u + 1435756296
print(Axg)
#426045453*v^15 + 1095853004*v^14 + 1027534429*v^13 + 199604488*v^12 + 1245066406*v^11 + 491522381*v^10 + 319187049*v^9 + 793800632*v^8 + 179486685*v^7 + 1344029075*v^6 + 926473343*v^5 + 484211635*v^4 + 1047468414*v^3 + 157075129*v^2 + 610169781*v + 917898386
print(Bx)
#779249508*v^15 + 297567236*v^14 + 378700571*v^13 + 1081381084*v^12 + 307273340*v^11 + 64314112*v^10 + 112350563*v^9 + 649766190*v^8 + 424903042*v^7 + 223527316*v^6 + 1393065653*v^5 + 1322430432*v^4 + 457302712*v^3 + 807713883*v^2 + 1191352294*v + 461422786

假设 $F$ 到 $G$ 的同态为 $\phi$。设 $A_F$ 的极小多项式为 $f(x)$，那么 $f(A_F)=0$，由同态可以得到 $\phi(f(A_F))=f(\phi(A_F))=f(A_G)$，因此同态前后，极小多项式不变，迹也不变。

1
2
3
4
5
6
print(Axf.minimal_polynomial())
#x^16 + 1435747462*x^15 + 33455366*x^14 + 1037842702*x^13 + 11109617*x^12 + 832067022*x^11 + 138214583*x^10 + 565542262*x^9 + 1176957343*x^8 + 1394076824*x^7 + 797026202*x^6 + 1386837332*x^5 + 948171790*x^4 + 593354364*x^3 + 495207351*x^2 + 1341667046*x + 1086432282
print(Axg.minimal_polynomial())
#x^16 + 1435747462*x^15 + 33455366*x^14 + 1037842702*x^13 + 11109617*x^12 + 832067022*x^11 + 138214583*x^10 + 565542262*x^9 + 1176957343*x^8 + 1394076824*x^7 + 797026202*x^6 + 1386837332*x^5 + 948171790*x^4 + 593354364*x^3 + 495207351*x^2 + 1341667046*x + 1086432282
Axg.minimal_polynomial()==Axf.minimal_polynomial()
#True

至于为何同态前的迹也很小，我大概的猜测如下：

1.原来生成的的多项式是小系数多项式

2.因为 $K_1$ 中的取模多项式只有低位有 $0$ 和 $\pm1$，那么 $x^{n}$ 会被分散到低一半的位中去，且变动只有可能是 $x^n$ 的系数。因此对于特定阶数的变换 $q,q^2,q^3,…,q^{n-1}$ 下，多次乘方后的效果会被抵消掉（对应元素的共轭），然后全部加起来，得到的迹也就很小了。

闲得无聊看了一下这个

1
print(list(Hom(F,G))) #length:16

然后又调了一下这个

1
phi(u**(p**3)) #1,2,3,4,5,...,15

发现这些刚好对应 (list(Hom(F,G))) 中出现的所有表达式，有点意思。

1x03 解题

既然在 $K_1$ 上取小多项式之后，得到的迹很小，那怎么样个迹才算小呢？随机取样之后，可以看到明显的差距：

1

2

1
2
T=[3765, 7362, 7440, 7259, 7343, 6932, 1174, 1072, 976, 821, 707, 668, 598, 540, 422, 409, 382, 367, 351, 306, 308, 290, 306, 316, 357, 365, 356, 369, 395, 495, 549, 583, 637, 738, 802, 981, 1060, 1364, 7058, 7249, 7249, 7421, 7434, 4424, 0]
S=[1189, 2334, 2362, 2395, 2329, 2269, 2359, 2378, 2341, 2276, 2333, 2387, 2300, 2265, 2347, 2307, 2236, 2272, 2282, 2339, 2285, 2331, 2353, 2308, 2295, 2342, 2308, 2254, 2323, 2275, 2249, 2283, 2306, 2357, 2371, 2375, 2339, 2344, 2411, 2375, 2323, 2327, 2363, 1203, 0]

然后你会发现，第一个取样耗时接近第二个的四倍（所以要是在对面服务器上打的话，是不是能直接根据时间去判断(bushi)

最后主要就是靠trace区分了，因为原题环境没了，所以进行了本地复现。一开始Bound调 $50000$ 和 $60000$ 都没成功，$70000$ 调了一次，成功了，但好像真的比较看脸。。。因为后续我又尝试了几次都没成功。。。

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 sage.all import *
from pwn import *
from Crypto.Util.number import *
sh=remote('127.0.0.1',60733)
from base64 import *
def b642poly(fb64):
	flist=[0]*129
	fi=bytes_to_long(b64decode(fb64))
	for i in range(129):
		flist[i]=fi%333337
		fi//=333337
	return flist
sh.recvuntil(b'F:')
Px=sh.recvline(keepends=False).strip().decode()
Px=(b642poly(Px))
K=GF(333337**128,modulus=Px,names=('t',))
BOUND=70000
score=0
for i in range(111):
	print(f'{score=},round={i}')
	sh.recvuntil(b']:')
	Fx=sh.recvline(keepends=False).strip()
	sh.recvuntil(b']:')
	Gx=sh.recvline(keepends=False).strip()
	sh.recvuntil(b']:')
	Hx=sh.recvline(keepends=False).strip()
	Fx,Gx,Hx=b642poly(Fx),b642poly(Gx),b642poly(Hx)
	Fx,Gx,Hx=K(Fx),K(Gx),K(Hx)
	a,b,c=(Fx.trace(),Gx.trace(),Hx.trace())
	judg=sum([a<BOUND,a>333337-BOUND,b<BOUND,b>333337-BOUND,c<BOUND,c>333337-BOUND])
	if(judg>2):
		sh.sendline(b'1')
	else:
		sh.sendline(b'0')
	jres=sh.recvline(keepends=False)
	if(b'Correct' in jres):
		score+=1
sh.interactive()

运行结果，卡线出了一次：

3

然后BOUND调成 $65000$，写了个自动化多次连接多次运行的脚本，反正能出，平均下来有十几分之一的概率。。。

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
from sage.all import *
from pwn import *
from Crypto.Util.number import *
from tqdm import *
from base64 import *
def b642poly(fb64):
	flist=[0]*129
	fi=bytes_to_long(b64decode(fb64))
	for i in range(129):
		flist[i]=fi%333337
		fi//=333337
	return flist
def Solveeee():
	sh=remote('127.0.0.1',60733)
	sh.recvuntil(b'F:')
	Px=sh.recvline(keepends=False).strip().decode()
	Px=(b642poly(Px))
	K=GF(333337**128,modulus=Px,names=('t',))
	BOUND=65000
	score=0
	for i in range(111):
		#print(f'{score=},round={i}')
		sh.recvuntil(b']:')
		Fx=sh.recvline(keepends=False).strip()
		sh.recvuntil(b']:')
		Gx=sh.recvline(keepends=False).strip()
		sh.recvuntil(b']:')
		Hx=sh.recvline(keepends=False).strip()
		Fx,Gx,Hx=b642poly(Fx),b642poly(Gx),b642poly(Hx)
		Fx,Gx,Hx=K(Fx),K(Gx),K(Hx)
		a,b,c=(Fx.trace(),Gx.trace(),Hx.trace())
		judg=sum([a<BOUND,a>333337-BOUND,b<BOUND,b>333337-BOUND,c<BOUND,c>333337-BOUND])
		if(judg>2):
			sh.sendline(b'1')
		else:
			sh.sendline(b'0')
		jres=sh.recvline(keepends=False)
		if(b'Correct' in jres):
			score+=1
	C=(sh.recvall())
	sh.close()
	return score,C
for i in (range(300)):
	print(i+1,Solveeee())
#sh.interactive()

运行结果：（服务器端删除了from secret import flag，改成了自定义flag格式，其他方法等效于原服务器）。

4

2.numbers2

2x01 题目大意

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
from Crypto.Util.number import *
import os
from hashlib import *
from random import *
p = getPrime(512)
q = getPrime(512)
n  = p*q
m = bytes_to_long(os.urandom(20))
x = pow(m,p,n)
y = pow(m,q,n)

with open('output.txt', 'w') as file:
    
    file.write('n = ' + str(n) + '\n')
    file.write('x = ' + str(x) + '\n')
    file.write('y = ' + str(y) + '\n')


iv = sha256(str(p).encode()).digest()[:16]


n = 17
q = getPrime(1024)
x = randint(q//2,q-1)
S = 2**544
K = 2**480

s = [randint(S//2,S-1) for i in range(n+1)]
t = [randint(S//2,S-1) for i in range(n+1)]


k = [randint(K//2,K-1) for i in range(n+1)]
b = [randint(K//2,K-1) for i in range(n+1)]

r = [(s[i]*k[i] - b[i]*t[i]) * inverse(x,q) % q for i in range(n+1)]


with open('output.txt', 'a') as file:
    file.write(f"s = {s}\n")
    file.write(f"t = {t}\n")
    file.write(f"r = {r}\n")
    file.write('q = ' + str(q) + '\n')
    
key = sha256(str(2024*b[0]+2023*k[0] + x).encode()).digest()[:16]

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from uuid import *
from flag import flag

aes = AES.new(key,AES.MODE_CBC,iv)
cipher = aes.encrypt(pad(flag.encode(),16))
with open('output.txt', 'a') as file:
    file.write(f"cipher = {cipher}")

题目的flag使用了AES-CBC加密。分为两部分，对iv的加密和对密钥的加密。下面分别阐述

2x02 Part 1

第一部分给出了一个RSA的加密过程加密 iv。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = getPrime(512)
q = getPrime(512)
n  = p*q
m = bytes_to_long(os.urandom(20))
x = pow(m,p,n)
y = pow(m,q,n)

with open('output.txt', 'w') as file:
    
    file.write('n = ' + str(n) + '\n')
    file.write('x = ' + str(x) + '\n')
    file.write('y = ' + str(y) + '\n')

iv = sha256(str(p).encode()).digest()[:16]

这一问和鹏城杯的那个题一样，CRT化简之后，还是 $g\equiv m\pmod p,h\equiv m \pmod q$ 的形式，完全一样的代码

1
2
3
4
5
6
7
8
n = 133693649727082259107041662011720823458571250895054242259170170354175642242128965748915759548206594541801234255878757661771526775311636655859201668702890990745739241126384729560433907755687614698569613585182786544165812027959219789602655976970715100245966545577285355634247363922810553139003838578363660449109
g=92401219014364912794053160070309527007771356043695463515571328726676546494869270394623052969651083009651771857467561945521106625547418406188430774969043958102947805651169010188202688119325462398122519423459244079993702953589811689050017122705616315531462047800685314554111273134721614734430443067361639605720
h=27444123601022148160097636168019280219400389861288181193988463940073215353205764735090720106313510456714820401995714013971697413924167047690200030265762984461900122475812718262941762361406314725034408660419186620573774598548615986428700226735633115570424145980543054306673862989672645266476994517440508647839

K=2**1600
M=Matrix(ZZ,[[1,0,0,g*h*K],[0,1,0,-(g+h)*K],[0,0,1,1*K],[0,0,0,K*n]])
print(M.LLL()[0])
#(-1, -220100243352092218129491119040565723833151607139, -48444117123650214661388931601686039991652705643026455075715408364262521400552593472298595765321, 0)

只是需要多做一步，计算 $g-m$ 和 $n$ 的最大公约数，因为 $g\equiv m\pmod p$，也就是 $g=kp+m$，因此 $g-m=kp$，这样就可以得到 $n$ 的分解了。

1
2
3
4
5
6
7
8
9
10
p=GCD(g-m,n)
q=n//p
assert p*q==n
from hashlib import sha256
iv1= sha256(str(p).encode()).digest()[:16]
iv2= sha256(str(q).encode()).digest()[:16]
print(iv1.hex())
print(iv2.hex())
#8076dd87467b159231123921f92dd39b
#313f3a43636d41db93278863b3d50e73

这样我们就得到了两个IV，先保存着，不确定哪个是对的。

2x03 Part 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 17
q = getPrime(1024)
x = randint(q//2,q-1)
S = 2**544
K = 2**480

s = [randint(S//2,S-1) for i in range(n+1)]
t = [randint(S//2,S-1) for i in range(n+1)]


k = [randint(K//2,K-1) for i in range(n+1)]
b = [randint(K//2,K-1) for i in range(n+1)]

r = [(s[i]*k[i] - b[i]*t[i]) * inverse(x,q) % q for i in range(n+1)]

这一部分给出了 $18$ 组数据、模数 $q$，数组 $s,t,r$。但未知量为 $x$ 和数组 $b$。其中 $q,x$ 均为 $1024$ 比特，$s,t$ 均为 $544$ 比特， $k,b$ 均为 $480$ 比特。很明显一个HNP问题，并且这个式子是一眼看出来的：
$$
s_ik_i-t_ib_i\equiv r_ix \pmod q
$$
很明显的线性关系，但这个矩阵属实不好构造。我一开始把所有的 $s_i$ 和 $b_i$ 都放在一起，消 $x$，构造了一个 $37\times37$ 的矩阵，但对角线上全是 $1$，加上 $k,b$ 同阶，不需要平衡因子，矩阵的行列式完全达不到要求。

最后参考了striving✌的构造方法：保留 $x$，化简式子：
$$
s’_ik_i-r_i’x\equiv b_i \pmod q
$$
也就是
$$
s’_ik_i-r_i’x-u_iq= b_i
$$

其中 $s_i’=\frac{s_i}{t_i},r_i’=\frac{r_i}{t_i}$。构造矩阵如下（以三个为例）：

6

根据striving的提醒：根据对角线算界：$\log_2 q^3=3072$，$\log_2\vec v_1=(k_1,k_2,k_3,b_1,b_2,b_3)=480+\log_2 6=482$，$6\log_2 \vec v_1=2892<3072$，因此算法是可行的。

打印一下每一行的nbits，可以看到第二行清一色的 $480$，说明这就是所求的值，对应下标为1

7

代码也放一下，方便复现

1
2
3
4
5
6
7
from Crypto.Util.number import *
sdivt=[s[i]*inverse(t[i],q)%q for i in range(len(s))]
rdivt=[r[i]*inverse(t[i],q)%q for i in range(len(r))]
M=block_matrix([[identity_matrix(len(s)),diagonal_matrix(ZZ,sdivt)],
                [zero_matrix(len(s)),q*identity_matrix(len(s))],
                [zero_matrix(1,18),Matrix(ZZ,rdivt)]])
MLLL=M.LLL()

有了 $k$ 和 $b$，就可以求出 AES 的密钥了。两个IV分别试一下，第一个是对的，因此原题得解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
v=MLLL[1]
v=v*sgn(v[0])
listv=list(v)
k=listv[:len(s)]
b=listv[len(s):]
x=(k[0]*s[0]-b[0]*t[0])*inverse(r[0],q)%q 
print(x,k[0],b[0])
from hashlib import sha256
key=sha256(str(2024*b[0]+2023*k[0]+x).encode()).digest()[:16]
key
#b'\xe0\x14\x00\x84\xb9\xcd\xa1\t\xec\xa9\x86\x91g\xcb\x8d\x16'
from Crypto.Cipher import AES
aes = AES.new(key,AES.MODE_CBC,iv=b'\x80v\xdd\x87F{\x15\x921\x129!\xf9-\xd3\x9b')
m=aes.decrypt(cipher)
print(m)
#DASCTF{b157059c-2871-421f-8cec-332b617de4d5}\x04\x04\x04\x04

2x04 Part 2 消 $x$ 做法

当然，我一开始的思路还是想消 $x$，在 striving✌的指点下，我尝试了一下这个矩阵：

由于
$$
s_{18}k_{18}-t_{18}b_{18}\equiv r_{18}x\pmod q
$$
和
$$
s_2k_2-t_2b_2\equiv r_2x\pmod q
$$
因此消 $x$，有
$$
r_2s_{18}k_{18}-r_{18}s_2k_2-r_2t_{18}b_{18}+r_{18}t_2b_{2}\equiv 0\pmod q
$$
那么可以有
$$
b_2=\frac{r_2s_{18}k_{18}-r_{18}s_2k_2-r_2t_{18}b_{18}}{r_{18}t_2}-u_2q
$$
固定第一组数据，将上面的 $x$ 换为 $b_{18}$，然后右边向量从 $b_2$ 开始也是可以的。算了一下界，也没有问题。但考虑到他第一组数据与密钥有关，因此这里固定最后一组数据。

设 $A_i=\dfrac{r_is_{18}} {r_{18}t_i},B_i=\dfrac{r_{18}s_i} {r_{18}t_i},C_i=\dfrac{r_it_{18}} {r_{18}t_i}$，最后构造的矩阵为（两组数据的情况）

9

这边的代码放一下，不知道为啥不需要加负号，很奇怪。。。

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
from Crypto.Util.number import *
A=[r[i]*s[-1]*inverse(r[-1]*t[i],q)%q for i in range(17)]
B=[r[-1]*s[i]*inverse(r[-1]*t[i],q)%q for i in range(17)]
C=[r[i]*t[-1]*inverse(r[-1]*t[i],q)%q for i in range(17)]
M=[[0 for _ in range(35)] for __ in range(36)]
for i in range(35):
    M[i][i]=1 if i<18 else q
for i in range(17):
    M[i][i+18]=B[i]
for i in range(17):
    M[17][18+i]=A[i]
for i in range(17):
    M[-1][18+i]=C[i]
M=Matrix(ZZ,M)
MLLL=M.LLL()
print('  ',end='')
for i in range(35):
    print(i%10,end=' ')
print()
for i in range(M.nrows()):
    print(f'{i%10} ',end='')
    for j in range(M.ncols()):
            print('X'if M[i][j] else '.',end=' ')
    print()
for i in range(MLLL.nrows()):
    for j in range(MLLL.ncols()):
        print(MLLL[i][j].nbits(),end=' ')
    print()
v=MLLL[3]
v=v*sgn(v[0])
listv=list(v)
k=listv[:18]
b=listv[18:]
x=(k[0]*s[0]-b[0]*t[0])*inverse(r[0],q)%q
print(x,k[0],b[0])

最后第 4 个向量（下标为3）为答案，很奇怪。striving师傅使用的第一组数据，解出来第一个向量就是答案。。

得到了striving✌的解答：构建对角+方阵这样会好一点，也就是我上面的那个最后一行被移到了第一行

1
2
3
4
5
6
7
8
9
M=[[0 for _ in range(36)] for __ in range(36)]
for i in range(36):
    M[i][i]=1 if i<=18 else q
for i in range(17):
    M[i+1][i+19]=B[i]
for i in range(17):
    M[18][19+i]=A[i]
for i in range(17):
    M[0][19+i]=C[i]

3.[N1CTF2021]n1token-1

3x01 题目大意

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
from Crypto.Util.number import *
import random
from secret import flag

def gettoken(c):
    X = 0
    while ((pow(X, (p-1)//2, p)!=1) or (pow(X, (q-1)//2, q)!=1)):
        X = 1
        while X.bit_length() < 920:
            X *= random.choice(primes)
    xp = pow(X, (p + 1)//4, p)
    xq = pow(X, (q + 1)//4, q)
    xp = random.choice([xp,-xp%p])
    xq = random.choice([xq,-xq%q])
    x = c * (xp*inverse(q,p)*q + xq*inverse(p,q)*p) % n
    return x

def getmyPrime(nbits):
    p = getPrime(nbits)
    while(p%4==1):
        p = getPrime(nbits)
    return p

primes = random.sample(sieve_base, 920)
p = getmyPrime(512)
q = getmyPrime(512)
e = 65537
n = p*q
c = pow(bytes_to_long(flag), e, n)

with open("output.txt", "w")as f:
    f.write("n = " + str(n) + "\n")
    for i in range(920):
        f.write("Token #"+str(i+1)+': '+str(gettoken(c))+'\n')
#最后给出了920组数据

3x02 Easy的Part 1

题目只给出了 $n,e$，$c$ 没有给出。但题目给出了 $t_i=cx_i$ 值，其中 $X=x^2\pmod n$，且 $X$ 为 $920$ 位光滑数字。因此可以得到
$$
t_i^2c^{-2}-k_in=X_i
$$
很明显的LLL，直接一把梭，求出了所有 $X$，并得到了 $c^2$。这个我很容易看出来了，那个看着复杂的式子，只不过是在知道 $n$ 分解时，通过CRT求 $\sqrt x\pmod n$，$p\equiv 3\pmod 4$ 的素数可以用公式开平方。

矩阵构造在这里，这个其实很简单，wp用了 $64$ 组，我用了 $50$ 组也能出。

10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from tqdm import *
tokens=open('output.txt','r').readlines()
tokens.pop(0)
n=68512262030092235082955402685415541014208343583540436164257874839232436153071370815269154345614809159891073442197732980480807167946204103083844856370368201582809851941837996671056932696292853288793127100756079130455873788646267803515293475609923615566516458978625901881951403282617405981962778117066458607117
tokens=[int(tokens[i].split(':')[1])for i in range(920)]
tokens2=[i*i%n for i in tokens]
M=block_matrix(ZZ,
[[Matrix(tokens2[:50])],
[identity_matrix(50)*n]])

MLLL=M.LLL()
lgMLLL=[[0 for _ in range(50)]for __ in range(51)]
Xarr=list(MLLL[1])
#print(Xarr)
C2=tokens2[0]*inverse(Xarr[0],n)%n
#print(C2)
for i in range(50,920):
    Xarr.append(tokens2[i]*inverse(C2,n)%n)

然后呢？我们要求的是 $c$ 啊。

考虑到 $X$ 的光滑，我们打算分解每一个 $X$，并将其保存起来。因为素数是 $920$ 个，$X$ 也是 $920$ 个，可以直接factor，获取因子。

1
2
3
4
5
6
7
8
9
10
11
FactXarr=[]
for i in (range(920)):
    FactXarr.append(list(factor(Xarr[i])))
primeset=[]
for i in range(920):
    for j,_ in FactXarr[i]:
        primeset.append(j)
primeset=sorted(list(set(primeset)))
indexdic={}
for i in range(920):
    indexdic[primeset[i]]=i

然后我就被卡住了。。

3x03 Tough的Part 2

瞄一下wp：

WP:

若 $x^2\equiv y^2 \pmod n$，则 $x=ky\pmod n$，其中 $k^2\equiv 1\pmod n$。

也就是 $(k+1)(k-1)\equiv 0\pmod n$，即 $(k+1)(k-1)=gn$。如果 $k$ 不为 $1$，那么就有可能通过公因数分解 $n$，这里 $\gcd(k+1,n)=p,\gcd(k-1,n)=q$。

因此，我们要求一个 $k$ 来分解 $n$。

如果我们从其中选取 $w$ 个表达式相乘，当$w$为偶数时，那么同余式左边由 $t_i^2$累乘得到的项可以看成$(t_0 * t_1 * … * t_w)^2$，同余式右边由$c^2$累乘得到的项可以看成$(c^w)^2$，当剩下的这$w$个$X_i$相乘得到的项也可以写为一个项的平方时，我们即构造出了一个上面所提到的分解$n$所需的表达式，由于这里$t_i$、$X_i$和$c^2$在模$n$下的值我们均已知，因此我们可以直接计算出$k$的值，继而按照上面的方法分解$n$，因此接下来我们只需从这920组数据当中找出符合条件的$w$组即可。

为了找到这样的$w$组数据，我们可以将每个$X_i$展开为若干素数$prime_i$乘积的形式，然后记录下每个$prime_i$的指数的奇偶性，这样一来可以将其看作一个GF(2)上的920维行向量，由于我们有920组数据，因此可以列出一个920 * 920的矩阵，这样一来寻找若干$X_i$相乘的结果其指数为偶数的问题就转化为了寻找若干$prime_i$其指数之和在GF(2)下为0的问题，因此我们直接对该矩阵求left kernel matrix即可，这样一来我们可以得到若干组$res$向量，其中每一个$res$向量中值为1的下标对应着我们的920组数据当中应当选取的$X_i$的下标，同时为了保证$w$为偶数，我们还需要选择$res$向量中1的个数为偶数的向量，在本题的数据中，我们一共得到了两组$res$向量，其中一组中1的个数为奇数、一组中1的个数为偶数，我们选择偶数这组即可，然后按照上述过程计算出$k$，既而即可分解$N$求出私钥$d$。

貌似有道理，但这是啥意思呢？

算了，先根据wp做一下。啊？被分解出来了吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
PM=[]
for i in tqdm(range(920)):
    cpm=[0]*920
    for j,k in FactXarr[i]:
        cpm[indexdic[j]]=k
    PM.append(cpm)
PM2=Matrix(GF(2),PM)
PM=Matrix(ZZ,PM)
print(PM2.rank())
#918
PM2K=PM2.left_kernel()
judgvec=list(PM2K[2])
cnt=judgvec.count(1)
Xpro,Tpro=1,1
for i in range(920):
    if(judgvec[i]):
        Xpro=Xpro*Xarr[i]
        Tpro=Tpro*tokens[i]
assert Xpro.is_square()
Xprosq=Xpro.nth_root(2)
k = (((Tpro * inverse_mod(Xprosq, n)) % n) * pow(C2, -(cnt // 2), n)) % n
print(GCD(int(k-1),n))
#7066689880579369785256516192953365235434055150846536631329529038878914448897380081597992569628631985623841078424106593028009177867365917709699457885163883

两个平方相等，哪两个相等啊？一个小时的乱搞后，我得到了答案：
$$
\prod_{\mathrm{judgvec}[i]=1} t_i^2\equiv \prod_{\mathrm{judgvec}[i]=1}X_ic^{2\sum\mathrm{judgvec}} \pmod n
$$

1
2
Tpro**2%n==(Xpro*pow(C2,cnt,n))%n #cnt=judgvec.count(1)
#True

再回顾过程：矩阵 PM 中存放的是每个 $X$ 对应的素数的指数，PM[i][j] 表示 $X_i$ 的分解中第 $j$ 个素数的指数，对 PM 矩阵全体模 $2$，就可以有每个指数是奇数还是偶数。在 PM2=GF(2)(PM) 下求left kernel，就是求满足条件的 $\vec v=(v_0,v_1,…,v_{919})$，使得 $\pi_{i=0}^{919} X_i^{v_i}$ 是一个平方数。然后就回到了 WP 中的这句话：

如果我们从其中选取 $w$ 个表达式相乘，当$w$为偶数时，那么同余式左边由 $t_i^2$累乘得到的项可以看成$(t_0 * t_1 * … * t_w)^2$，同余式右边由$c^2$累乘得到的项可以看成$(c^w)^2$，当剩下的这$w$个$X_i$相乘得到的项也可以写为一个项的平方时，我们即构造出了一个上面所提到的分解$n$所需的表达式，由于这里$t_i$、$X_i$和$c^2$在模$n$下的值我们均已知，因此我们可以直接计算出$k$的值，继而按照上面的方法分解$n$，因此接下来我们只需从这920组数据当中找出符合条件的$w$组即可。

验证一下：

1
2
Xpro.is_square()
#True

看来没问题了。设这个 $X_{pro}=a^2$，这边left kernel保证 $X$ 的分解的指数都是偶数（因为取模原因，$X$ 是模 $n$ 的二次剩余，但 $X$ 的分解指数不全为偶数，是因为部分奇数可以为二次剩余）。又因为 $t^2\equiv Xc^2\pmod n$，因此 $T_{pro}^2=X_{pro}c^{2w}$。因此我们可以两边开根：
$$
T_{pro}=ac^{w}
$$

1
2
Xprosq.is_square()
#False

OK，这下看看，我们找到了什么？
$$
T^2_{pro}=a^2c^{2w}
$$
两个平方相等！

开根测一下：两个平方模 $n$ 相等，但开方后不等。

1
2
3
4
Tpro**2%n==(Xpro*pow(C2,cnt,n))%n #cnt=judgvec.count(1)
#True
Tpro%n==Xprosq*pow(C2,cnt//2,n)%n
#False

因此，我们找到了所需要的 $k\equiv \dfrac{a}{c^{2(w/2)}}$。因为 $c^2$ 是一个整体，所以 $w$ 要保证是偶数才可行。这样思路终于和WP闭环了。。。

3x04 完结撒花

分解 $n$ 之后，先用CRT对 $c^2$ 开根，得到四个可能的结果。然后分别RSA解密，找到flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
p,q=GCD(int(k-1),n),GCD(int(k+1),n)
assert p not in [1,n] and q not in [1,n] and p!=q
carr=[]
cp=int(pow(C2,(p+1)//4,p))
cq=int(pow(C2,(q+1)//4,q))
for sp in [1,-1]:
    for sq in [1,-1]:
        carr.append(crt([cp*sp,cq*sq],[p,q]))
print(carr)
d=inverse(65537,(p-1)*(q-1))
for c in carr:
    print(long_to_bytes(pow(c,d,n)))
"""
Output:
[46630614291745334334152762312676921133624051168940817865903892997090214159501097997241603185344424810227360569767886901658508914717819387760635901824660947938796941642460399170111143796793156856634009422349818143947262685178807938549388138287681555995508698977295037594135656538624892517735216104401235804978, 19703989276128579847076476848899002659695039512136459426637790674933329268053509523645116022627877355721599775333883095285751759221736313984198660551863329947412556215691527518951119591197450423277438733191151653085195488305757310694499293449100108574981362635828059309918833297115589471736564051849673468541, 48808272753963655235878925836516538354513304071403976737620084164299106885017861291624038322986931804169473666863849885195055408724467789099646195818504871635397295726146469152105813105095402865515688367564927477370678300340510492820794182160823506991535096342797842572032569985501816510226214065216785138576, 21881647738346900748802640372738619880584292414599618298353981842142221993570272818027551160270384349663712872429846078822298253228384715323208954545707253644012910299377597500945788899499696432159117678406260986508611103467459864965905337322242059571007760001330864287815746743992513464227562012665222802139]
b'2v\xa7F0aU\xdaJK\x1e\xff\r!>\x84\xf3\xe3\xe5sC\xd6\xa2\x8a-vJ\xe15g\xf0\xcb-^g\xaeJ\x05o.N\xd2\xb1\x12\x06\xe0\x05\xf9\xcc\x0f\xcf\xac(\x1d\x9c\\\xfcz\xe9\xf4\x04\x99V[\x98\xc7\xeb(\xfe\xa1X\x1a\x89\xaa\x17,\xf7\xc9d\x069\xb3\x1d\x0chd\x9d6Z\xdaT\xf8\xba1\x16\xf8{Z\xb3D\xd9\x05\xf8\xb8E\xb8\xd75V\xcc-\x80al\xc3\xf2\xd6.\xcaNt\xfa\xed\x83\x14T\xb3\xe1'
b'n1ctf{b9e7d419-0df8-438a-9120-efdf3ddf155f}'
b"a\x90\x90(K\xa8\x92&\x82\x8f6\xdf\x86^\xa8p\x94\xf9^@wR\x08-g\xc19\x90\xae\x02\xfdQ\x1a\xb21U^(\xe0]9\n\xba\x86\xc1z!\xf1M\xc1\xa1\xcc\xb9~m:w\x0e\xf5\xe2s-\x83\xb0\xb0H^\xed\xe1H\xd5\x83yHp\xcf\x15\xed\xc6\xd8\xf1S\xf1B\xb2\xc1\xce!\xc0\x01\xbc\x82:0\xdd\xdfLy\xe3\xedJ\x9b\x0b\x14\xa0t\xef \x15\x02\xd8O\xfe\x8a'}3\x96\xc1\xbf\xef\x01\xcf\xf4\xb4\xa1\xc7\x90"
b'/\x19\xe8\xe2\x1bG<L8D\x17\xe0y=i\xeb\xa1\x15x\xcd3{e\xa3:J\xee\xafx\x9b\x0c\x85\xedS\xc9\xa7\x14#q.\xea8\tt\xba\x9a\x1b\xf7\x81\xb1\xd2 \x91`\xd0\xddz\x94\x0b\xeen\x94-U\x17\x80s\xc4\xe2\xa7}h\xef\x9eY\xa2\x1e$b\xd2\xb7\xa0\xd46J\xcbbN\xd9\x8d\xe2\xeb\xb9d\xfeK\x05Pi\xd5\xa1\xf9x\x94\x87\xf0K#\x1fc\xe4\x00\xcfM\x90\xef\xc3\xcc]\xa4\xdekH\xa2\xd5\x82z,'
"""

flag：n1ctf{b9e7d419-0df8-438a-9120-efdf3ddf155f}

4.[强网杯2024]traditional game

4x01 题目大意

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
from Crypto.Util.number import getPrime,bytes_to_long
from secret import secret,flag
import random
import time
import os
import signal

def _handle_timeout(signum, frame):
    raise TimeoutError('function timeout')

timeout = 300
signal.signal(signal.SIGALRM, _handle_timeout)
signal.alarm(timeout)

random.seed(secret + str(int(time.time())).encode())

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = getPrime(128)
        self.n = self.p * self.q
        self.phi = (self.p - 1) * (self.q - 1)
        self.d = pow(self.e, -1, self.phi)  

    def get_pub lic_key(self):
        return (self.n, self.e)
    
    def get_private_key(self, blind_bit=None, unknown_bit=None):
        if blind_bit is not None and unknown_bit is not None:
            blind = getPrime(blind_bit)
            d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
            return (d_, blind)
        else:
            return (self.d, 0)
    
    def encrypt(self, m):
        if type(m) == bytes:
            m = bytes_to_long(m)
        elif type(m) == str:
            m = bytes_to_long(m.encode())
        return pow(m, self.e, self.n)
    
    def game(self,m0,m1,b):   
        return self.encrypt([m0,m1][b]) 


rsa = RSA()
token = os.urandom(66) 

print( "[+] Welcome to the game!")
print(f"[+] rsa public key: {rsa.get_public_key()}")

coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

blind_bit = 40
unknown_bit = 365

d_,blind = rsa.get_private_key(blind_bit, unknown_bit)

print( "[+] Now, you have permission to access the privkey!")
print(f"[+] privkey is: ({d_},{blind}).")
print(f"[+] encrypt token is: {rsa.encrypt(bytes_to_long(token))}")

guess_token = bytes.fromhex(input("[-] guess token:"))
if guess_token == token:
    print("[+] correct token, here is your flag:",flag)
else:
    print("[-] wrong token")

题目还是分为两部分，后面一步一步地来看。

4x02 Part 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
coins = 100
price = 100
while coins > 0:
    print("=================================")
    b = random.randint(0,1)
    c = rsa.game(
        b'bit 0:' + os.urandom(114), 
        b'bit 1:' + os.urandom(114), 
        b)
    print("[+] c:",c)
    guessb = int(input("[-] b:"))
    coins -= 1
    if guessb == b:
        price -= 1
        print("[+] correct!") 
    else: 
        print("[+] wrong!") 

if price != 0: 
    print("[-] game over!")
    exit()

blind_bit = 40
unknown_bit = 365

这一部分是区分两个值的特定比特。不是，就前面两个一样，后面 $912$ 位都不一样，这还能区分？

然后当时在那边想了半天，比赛的时候实在没想出来怎么搞这个。赛后问了其他的师傅：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Dialog huangx607087-DeeBaTo

huangx607087 2024/11/7 17:29:09
师傅在吗？想问问你那边有无前几天强网杯的wp，之前看了rec师傅对那个traditional game的第一问也是开两个进程，同时连接容器，去获得同样的随机数种子做的，我很好奇那个题第一问的正确做法。

DeeBaTo 2024/11/7 17:29:22
就是这个

DeeBaTo 2024/11/7 17:29:34
网络协议里的反射攻击

Dialog huangx607087-rec

rec 2024/11/7 17:32:39
上个月blackhat我和他一起打的

rec 2024/11/7 17:32:43
有个题就是这样

？？？好家伙，奇怪的知识增加了。所以开两个进程，然后同时连接。真会玩啊。。

大概代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solve:
    self.sh=remote('127.0.0.1',60716) # for solve 2
    def __init__():
        pass
    
    def solve1():
        th=remote('127.0.0.1',60716) #only used in solve1
        A=[]
        #solve code,collect results
        return A
    def solve2(resultarr):
        pass
    def solveall():
        resultarr=solve1()
        solve2(resultarr)

参考网址：2024 强网杯 部分题解 - S1uM4i

4x03 Part 2

参考：糖醋小鸡块的blog

通过Part1之后，我们可以获得 $d_x$ 的值，其值为：

1
2
3
4
5
6
7
def get_private_key(self, blind_bit=None, unknown_bit=None):
    if blind_bit is not None and unknown_bit is not None:
        blind = getPrime(blind_bit)
        d_ = ((int(self.d >> unknown_bit) // blind * blind) << unknown_bit) + int(self.d % blind)
        return (d_, blind)
    else:
        return (self.d, 0)

这边 unknown_bit=365,blind_bit=40。

根据 $d_x$ 的表达式，如果化成十六进制，最低 40 位就是 $d \bmod b$ 的值，同时，题目中也告诉了我们 $b$ 的值。此时，我们知道了 $d$ 的高位和低位。

因此可以得到
$$
C=e(bd_h+bd_m+d_l)=1+k\varphi
$$
其中，$ed-1=k\varphi=k(n-(p+q)+1)\equiv k-k(p+q)\pmod n$。

但是这边 $k$ 不知道啊，看了参考的wp，然后自己动手实验了一下，因为 $d$ 高位知道了很多，$n$ 和 $\varphi$ 的高 $511$ 位是相同的，所以有
$$
\left \lfloor \frac{ebd_h}{n}\right \rfloor+1=k
$$
设
$$
C=e(bd_h+d_l-k(n+1)-1)
$$
到这一步，LLL就很简单了。我们期待求出 $(p+q,d_m)$，根据上面的式子，有
$$
ebd_m+k(p+q)\equiv n \pmod C
$$
其中：$d_m$ 预期为 $365$ 位，$(p+q)$ 预期为 $513$ 位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dh=(((dx>>365)//b)*2**365)
dl=(dx&0xffffffffff)
print(dh,dl)
k=1+(e*dh*b//n)
C=e*(b*dh+dl)-k*(n+1)-1
M=[[1,0,k],
    [0,1,e*b],
    [0,0,C]]
M=Matrix(ZZ,M)
M=M*diagonal_matrix(ZZ,[1,1<<148,C]) #148=513-365
M3L=M.LLL()
for v in M3L:
    print(v)
#(-165382578491530217740294945789051327054550730412409, 6069854417684843869781185345814449921057599813490779103392444182843066433073577984, 0)
#(24253655408554923753657477074063654465943861814895829354859517611675085695676047250571909835358720051039798073116052933831237123986406228006920402560817446, 660828381258241436840092787866586880655656505125224479398221243621629860031648793514091179644037262606768135285755491647488, 0)
#(13265834046843137898321312630162668582611515930035, -486881279321864056104093205528514024155683530545938397465394105939234142703058944, 412587550651454677464807044872817944212261052389482413806028317495998064325432106958378875349983999689868802166640436956611193538891106166781061387911779019238685876501201863206243588919056176)

然后解出来一看：第二个向量是 $513$ 位，貌似成功了吗？

拿进去试一下，发现不对。。并且第一个向量非常短，经过测试，里面的结果是 $(-k,2^{148}eb,0)$，是一个非常非常trivial的解。如果令 $p+q=x,d_m=y$，那么有 $kx+eby$，那么 $(x,y)=(-eb,k)$ 当然也是一组解咯。

设第二组数据为 $(x_2,y_2,0)$，由于 $x_2,y_2$ 大小符合预期，参考wp中的提示，可以认为 $p+q=x_2+teb$，也就是
$$
p+q\equiv x_2\pmod {eb}
$$

因为我是本地数据测试，所以可以有 $p,q$，测一下：

1
2
3
4
5
6
x2=abs(M3L[1][0])
paddqL=(x2%(e*b))
paddqH=(x2//(e*b))*(e*b)
print(paddqL,paddqH)
print((p+q)%(e*b)==paddqL)
#True

然后再测一下 $eb$ 进制下，$p+q$ 和 $x_2$ 的差别：

1
2
3
4
5
6
7
8
9
10
11
12
def getradixb(x,bb):
    arr=[0]*30
    for i in range(30):
        arr[i]=x%bb
        x//=bb
    return arr
A=print(getradixb((dh*b)+dl,e*b))
B=print(getradixb(d,e*b))
print(A)
print(B)
#[104668899241649537541186210781987061154261026601556, 92109567048793027288125736075569023185167845386074, 62813493539693390648778685609015503369769016471552, 80689223742648360656616346585665194908177979489243, 70805628792722422704735895621626856114034836989125, 41818883498127627092744577886150813128254101231100, 711081, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
#[157342616402321470506410965081459618389668038679383, 105869422956878578854817467532416606067687308116443, 62813493539693390648778685611216892179500683590388, 80689223742648360656616346585665194908177979489243, 70805628792722422704735895621626856114034836989125, 41818883498127627092744577886150813128254101231100, 711081, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

好像差的不多，不是吗（

然后就似乎已知 $d$ 部分位求解了，这一部分完全参考了鸡块佬的，下你求一个大概解，然后使用CRT求 $p$ 低位模 $eb$ 的值，可以发现这个题界卡得非常紧。。。

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
PR.<x> = PolynomialRing(RealField(2000))
f = x*(paddqH-x) - n 
ph = int(f.roots()[0][0]) // (e*b) * (e*b)
print(int(f.roots()[0][0]))
R.<x> = PolynomialRing(Zmod(e))
fe = x*(paddqL-x) - n
rese = fe.roots()
R.<x> = PolynomialRing(Zmod(b))
fb = x*(paddqL-x) - n
resb = fb.roots()
rese=[rese[i][0] for i in range(len(rese))]
resb=[resb[i][0] for i in range(len(resb))]
print(rese,resb)
for i in rese:
    for j in resb:
        pl=crt([int(i),int(j)],[e,b])
        PR.<x> = PolynomialRing(Zmod(n))
        f = ph + e*b*x + pl
        f = f.monic()
        res = f.small_roots(X=2**245,beta=0.496,epsilon=0.015)
        if(res!=[]):
            pg=ph+e*b*res[0]+pl
            assert (n%int(pg)==0)
            print(pg)
            qg=int(n)//int(pg)
            dg=inverse(int(e),int((pg-1)*(qg-1)))
            print(pg,qg)

some situation.

1
2
3
4
5
rec 2024/11/3 17:10:01
这个我和鸡块搞了一天。。

rec 2024/11/3 17:10:10
我一个朋友出的，毫不留情

麻了。

9.总结

好难啊，不过好在自己学到了很多，也算是挺有收获的了吧。

计划11月24日从贵阳回来之后，停一段时间CTF，预计12月5日恢复，12月15日打个国赛，后面考试和pre太多了，整个人要爆炸了:(

CTFSeason4
#ExpLog
24Nov3
http://example.com/2024/11/20/24Nov3/
作者
huangx607087
发布于
2024年11月20日
许可协议