一……二……开门！

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

CTFshow上的新题，搞了一天

题目

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
from door_sum import door_sum

# door_sum(l, d, n): calculate the sum of an arithmetic sequence
# with `l` being the first number, `d` being the common difference,
# and `n` being the number of terms

# Sanity check:
assert door_sum(1, 1, 100) == 5050

WELCOME = '''HELLO!
Open the door, and I'll show you my flag!
'''

if __name__ == '__main__':
	while True:
		try:
			print(WELCOME)
			n_1 = int(input('n_1 = '))
			n_2 = int(input('n_2 = '))
			if (n_1 > 2 ** 0x1337 and n_2 > 2 ** 0x1337 and door_sum(1, 1, n_1) == 0x1337 * door_sum(1, 2, n_2)):
				print('OKOK! YOU GOT THE FLAG:')
				with open('flag.txt') as f:
					print(f.read())
			else:
				print('Uh-Oh, the door is not opened...')
		except Exception:
			print('NONONO!')

分析

door_sum可以写成等差数列的和

注意door_sum里的n是项数！！！

题目的要求是两个数均大于2**4919并且第一个数的数列和是第二个数列和的4919倍 $$ x_n=x_1+d(n-1)

\ S_n=n=()n = \则S_{n1}= \S_{n2}= \已知S_{n1}=4919*S_{n2},且d_1=1,d_2=2,x_1=1 \则=4919n_2^2 \ =n2 $$

走到这里发现走不通了，毕竟是要爆破的，对于这个数量级依旧很难出解。因为要加快爆破速度，了解到佩尔方程：

佩尔方程

\[ 定义：形如x^2 − d y^2=1(d>1,且d不是完全平方数)\\ 要求第一类佩尔方程的解都是正整数解,也即( x , y ) , x > 0 , y > 0 \]

显然方程有无数组解，如何求最小解？ \[ 把方程化为x=\sqrt{1+dy^2}\\ 从y=1开始枚举，如果\sqrt{1+dy^2}是整数，那么此时(x,y)就是最小整数解(x_1,y_1) \] 如何得到所有的解？

迭代公式： \[ x_n=x_{n-1}x_1+dy_{n-1}y_1\\ y_n=x_{n-1}y_1+y_{n-1}x_1 \] 但如果用这个公式求解，时间复杂度依旧是O(n)，当n很大时还是跑不出来，所以使用矩阵快速幂，以O(logn)的时间复杂度求解： \[ \left[ \begin{matrix} x_n\\ y_n \end{matrix} \right] \tag{2}= \left[ \begin{matrix} x_1&d*y_1\\ y_1&x_1 \end{matrix} \right]^{n-1} \left[ \begin{matrix} x_1\\ y_1 \end{matrix} \right] \]

解

改变一下推法： \[ \frac{n_1^2+n_1}{2}=4919n_2^2 \\(n_1+\frac{1}{2})^2-\frac{1}{2}=9838n_2^2 \\(2n_1+1)^2-4*9838n_2^2=1 \] 得到了佩尔方程的表达式，之后使用连分数的性质计算得到了最小解： \[ (x_1,y_1)=\\(2662019309411216232806345449321879270495478346383, 26838472360889124413883226557207387537524821524) \] 可以看到还是很小的（比起2^0x1337)

完整代码如下：

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
def find_mini_solution(d):
    m=int(d**0.5)
    i=0
    a=[]
    a.append(m)
    i+=1
    b=m
    c=1
    sq=d**0.5
    while(a[i-1]!=2*a[0]):
        c=(d-b*b)/c
        tmp=(sq+b)/c
        a.append(int(tmp))
        i+=1
        b=a[i-1]*c-b
    del a[-1]

    p=[m]
    q=[1]
    for j in range(1,len(a)):
        if j==1:
            p.append(a[j]*p[0]+1)
            q.append(a[j]*q[0])
        else:
            p.append(a[j]*p[j-1]+p[j-2])
            q.append(a[j]*q[j-1]+q[j-2])

    if len(a)%2==0:
        return p[-1],q[-1]
    else:
         return 2*p[-1]**2,2*p[-1]*q[-1]

def mulMatrix(x,y):     #二阶矩阵乘法
    ans = [[0 for i in range(2)]for j in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ans[i][j] += x[i][k] * y[k][j]
    return ans

def quickMatrix(m,n):
    E = [[0 for i in range(2)]for j in range(2)]        #先定义一个单位矩阵
    for i in range(2):
        E[i][i] = 1

    while(n):
        if n % 2 != 0:
            E = mulMatrix(E,m)
        m = mulMatrix(m,m)
        n >>= 1
    return E

d=9838*4
x1,y1=find_mini_solution(d)
print((x1,y1))
basis_matrix=[[x1,d*y1],[y1,x1]]

cnt=2
while True:
    tmp=quickMatrix(basis_matrix,cnt)
    xn=tmp[0][0]*x1+tmp[0][1]*y1
    yn=tmp[1][0]*x1+tmp[1][1]*y1
    if xn >2 ** 0x1337 and yn > 2 ** 0x1337 and xn**2-d*yn**2==1:
        print(cnt)
        print((xn-1)//2)
        print(yn)
        break
    cnt+=1

感觉用sage会方便很多0.0

sage果然方便，连分数有内置的函数，补上：

1
2
3
4
5
6
7
8
9
def solve_pell(N, numTry = 100):
	cf= continued_fraction(sqrt(N))
	for i in range(numTry):
		denom = cf.denominator(i)
		numer = cf.numerator(i)
		if numer^2-N*denom^2 == 1:
			return numer,denom
print(solve_pell(9838)) 
#(2662019309411216232806345449321879270495478346383, 26838472360889124413883226557207387537524821524)