20210925-长安杯-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 7.2k Reading time ≈ 7 mins.

  • series 0 solve

  • ticket_login 0 solve

  • easyRSA 11 solves

  • 4xwi11 0 solve

easyRSA

题目

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 Crypto.Util.number import *
# from secret import flag
flag = b'flag'

def add(a,b):
    if(a<b):
        a0 = str(b).encode()
        b0 = str(a).encode()
    else:
        a0 = str(a).encode()
        b0 = str(b).encode()
    ans = 0
    for i in range(len(a0)-len(b0)):
        ans = ans*10+a0[i]-48
    # print(ans)
    for i in range(len(b0)):
        ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10
    return ans

def mul(a,b):
    if(a<b):
        a0 = str(b).encode()
        b0 = str(a).encode()
    else:
        a0 = str(a).encode()
        b0 = str(b).encode()
    ans = 0
    for i in range(len(b0)):
        ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10
    return ans

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(512)
n = p*q
# c = pow(m,e,n)
print(add(p,q))
print(mul(p,q))
# print(n)
# print(c)
# 10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408
# 6004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861
# 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181
# 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937

关键是看懂下面两句话，即没有进位的十进制加法和乘法

1
ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10
1
ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10

结合RSA异或pq的解法，用这三个条件，甚至mul都不要，就可以筛选出p和q。

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
from Crypto.Util.number import long_to_bytes
from gmpy2 import invert

def add(a,b):
    if(a<b):
        a0 = str(b).encode()
        b0 = str(a).encode()
    else:
        a0 = str(a).encode()
        b0 = str(b).encode()
    ans = 0
    for i in range(len(a0)-len(b0)):
        ans = ans*10+a0[i]-48
    # print(ans)
    for i in range(len(b0)):
        ans = ans*10+(a0[i+len(a0)-len(b0)]+b0[i]+4)%10
    return ans

def mul(a,b):
    if(a<b):
        a0 = str(b).encode()
        b0 = str(a).encode()
    else:
        a0 = str(a).encode()
        b0 = str(b).encode()
    ans = 0
    for i in range(len(b0)):
        ans = ans*10+((a0[i+len(a0)-len(b0)]+2)*(b0[i]+2))%10
    return ans

n = 100457237809578238448997689590363740025639066957321554834356116114019566855447194466985968666777662995007348443263561295712530012665535942780881309520544097928921920784417859632308854225762469971326925931642031846400402355926637518199130760304347996335637140724757568332604740023000379088112644537238901495181
ADD = '10399034381787849923326924881454040531711492204619924608227265350044149907274051734345037676383421545973249148286183660679683016947030357640361405556516408'
MUL = '6004903250672248020273453078045186428048881010508070095760634049430058892705564009054400328070528434060550830050010084328522605000400260581038846465000861'
# print(len(ADD))
# print(len(MUL))
# 155
# 154
# p 154 q 155 or p 155 q 154
MUL = '0' + MUL

candidate = [(0, 0)]
for b10 in range(155):
    # print(len(candidate), candidate)
    crit = b10+1
    candidateForCandidate, candidate = candidate, []
    for p, q in candidateForCandidate:
        for i in range(10):
            for j in range(10):
                xx = p + i * 10 ** b10
                yy = q + j * 10 ** b10
                if ADD[-crit:] != str(add(xx, yy)).zfill(crit):
                    continue
                if MUL[-crit:] != str(mul(xx, yy)).zfill(crit):
                    continue
                if str(xx * yy)[-crit:] != str(n)[-crit:]:
                    continue
                if (yy, xx) not in candidate and (xx, yy) not in candidate:
                    candidate.append((xx, yy))

for p, q in candidate:
    if p * q == n:
        e = 0x10001
        c = 49042009464540753864186870038605696433949255281829439530955555557471951265762643642510403828448619593655860548966001304965902133517879714352191832895783859451396658166132732818620715968231113019681486494621363269268257297512939412717227009564539512793374347236183475339558666141579267673676878540943373877937
        d = invert(e, n - p - q + 1)
        m = pow(c, d, n)
        print(long_to_bytes(m))
        break
# b'flag{a4e3676e1e340581f7018972dd1905be}'

series

  • 考点：Fibonacci矩阵快速幂+降幂

看Tover. L师傅的博客复现 [2]

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce
from secret import *
import random

def F(x):
    if (x<4):
        return 1
    return F(x-1)+F(x-2)+F(x-3)

m = bytes_to_long(flag)
e = random.getrandbits(250)
p = getPrime(1001)
q = getPrime(1001)
k = e**e
s = reduce(lambda a, b: a*b, [F(k+i) % e for i in range(1,5)]) + F(2021**k)**4
p = next_prime(s)
c = pow(m,e,p)
print(e)
print(c)
#1292991588783542706506728336494377723983115217051171962646571511384590134899
#229797522574801936576076488492034448896863980731763047709941641260180597290800402814069755381965565755866855389082787759443816945304000719176334587540293777658369250939545994974691382505993209963323032684771922094686136104097942892330051349688373437571196103392801691879287264056022383484359551333197

问题并不复杂，模数为p是素数，求出p就能求解d，要求p只要求出s

而s的表达式如下
$$
s\equiv\prod\limits_{i=1}^4F(e^e+i)+F(2021^{e^{e}})^4\ (mod\ e)\notag
$$
但是显然$e^e$和$2021^{e^{e}}$太大了，在使用矩阵快速幂时阶数过大，即

$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}^{e^e-3}$和$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}^{2021^{e^e}-3}$

这是在模e下的，类似整数，指数可以模一个$\varphi(e)$降幂

有结论说矩阵$M\equiv\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}\ (mod\ p)$所在子群的阶为$p^2-1$，$p$为素数（不懂

在模e下，这里e=p*q，同样有结论

对于$n=p_1^{a_1}p_2^{a_2}\cdots$

  • $\varphi(n)=LCM(\varphi(p_1^{a_1})\varphi(p_2^{a_2})\cdots)$

  • $\varphi(p_1^{a_1})=p^{a-1}\varphi(p)$

注：这里的$\varphi$并不是欧拉函数，只是一个记号

所以

$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}^{(e^e-3)\ mod\ \varphi(e)}$和$\begin{bmatrix}
1 & 1 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}^{(2021^{e^e}-3)\ mod\ \varphi(e)}$

2021头上的$e^e$还是很大，用整数上的模欧拉函数模就好

exp如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
from gmpy2 import next_prime
from functools import reduce

e = 1292991588783542706506728336494377723983115217051171962646571511384590134899
c = 229797522574801936576076488492034448896863980731763047709941641260180597290800402814069755381965565755866855389082787759443816945304000719176334587540293777658369250939545994974691382505993209963323032684771922094686136104097942892330051349688373437571196103392801691879287264056022383484359551333197
M = matrix(IntegerModRing(e), [[1,1,1],[1,0,0],[0,1,0]])
v = vector(ZZ, [1,1,1])
def F(n):
    return int((M ^ int((n - 3)) * v)[0])

# https://www.alpertron.com.ar/ECM.HTM
p1 = 33285073849485750791903437807279991921
p2 = 38845988283830087557982578789883120419
assert p1 * p2 == e
phi = (p1^2 - 1) * (p2^2 - 1)
phi2 = euler_phi(p1+1)*euler_phi(p1-1)*euler_phi(p2+1)*euler_phi(p2-1)
k = pow(e, e, phi)
k2 = pow(e, e, phi2)

s = reduce(lambda a, b: a*b, [F(k + i) for i in range(1, 5)]) + (F(pow(2021, k2, phi))^4)
p = next_prime(s)
print(long_to_bytes(pow(c, inverse(e, p - 1), p)))	# b'flag{94e2b59bd8e8899be7bfa3ee9e540a2f}'

最后，题目存在不严谨的地方。第17行

1
s = reduce(lambda a, b: a*b, [F(k+i) % e for i in range(1,5)]) + F(2021**k)**4

出题人的意思应该是想让我们写出时间复杂度比一般递归求斐波那契数列低的算法，而在模运算下，这个算法如上文所示。累乘部分写了，但F(2021**k)**4部分并没有把模e写出来（可能是被IntegerModRing(e)之类的骗了

正确的应该是

1
s = reduce(lambda a, b: a*b, [F(k+i) % e for i in range(1,5)]) + (F(2021**k) % e)**4

Reference

  1. Integer factorization with additional knowledge of p⊕q
  2. Tover. L-模n的Fibonacci的快速计算——长安杯的series