Wp for 华为XCTF2020鸿蒙计算专场’s crypto

RRSSAA

题目分三个level，加密了三次，我们反过来解密就好了

level3

观察e的生成代码，发现存在 $e=4\times (1+k\times (p-1))+3$ 这一关系，即 $e=7+k\times(p-1)$ ，所以由费马小定理有 $m^e=m^7\ (mod\ p)$ ，所以可知 $p\mid m^e-m^7$ ，那么可以算出 $p=gcd(m^e-m^7,n)$

level2

因为t = next_prime(o) u = next_prime(s)，所以p1q1、p1q2、p2q1、p2q2都比较相近，联想费马分解，因为 $n=x^2-y^2=(x+y)\times(x-y)=a\times b$ ，所以我们使用费马分解在 $\sqrt{n}$ 附近寻找x并计算y，而此时我们得到的 (x,y) 则是p1q1与p2q2、p1q2与p2p1、p1p2与q1q2中的其中一个，那当我们得到两组合法的(x,y)后，即可通过gcd来得到p1,p2,q1,q2了

level1

又是next_prime，观察到 $y$ 与 $21\cdot x$ 相近， $z$ 与 $3\cdot x\cdot y$ 相近，可知 $n = x\cdot y\cdot z\approx 1363\cdot x^4$ ，所以我们在 $\sqrt[4]\frac{n}{1363}$ 的周围即可找到 $x$

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

#level3
c4 = 2223858574968933504319836040365324804971094330459462393944127171432282147604729897704345429059208580970050059952008010773685842392707183675848552727061753816604521338667996166424030688312622416918364914092916834363424563757848785094598668876885795408211613686469658206698800530604510586036849762682266643367887969834461905627352683770069831534697242348271330554339411094917823350455146582135451453515538908713886757653213973927096082********************************************
m4 = 81225738828166640599054154023183465870678960906769673605358084529196871174429427936591822589995476552044227730868809310992934103731850597399114246762836121101348301079296663951503688072299542357013093324718850936925265954204973634470836187733828189312553819810470********************************************
c3 = 23850649176609488069574576816416148886692179606070063605432689009210174812454985632639914109186048913143848105334392538145230671686367689762200590281089005923231195246579033646977003291454535177690932650527152046258702322882034275451509830373108765348015483098908530262342484124214979398113857256424921042629540596777935387076042051793448841426568428955677950006478374618351793957423993726834602082713108846572798935325391218935581430299********************************************
n3 = 245027309396554072925434368973821962975166642272733206023979068786967233722428777765504465639508676248193528531220331147117321254335887247798699854774950988027443444489150326074699546422578258559318722819082323316238297250430318005357394321339486074483626412040345465814449044087548920371100312025734633992016258120056152646898775372319740238700067921969618291620584466621726342124271864707245999413528305460437729692977332395186047416381********************************************

p3 = gcd(c4 - pow(m4,7,n3),n3)
q3 = n3 // p3
assert p3 * q3 == n3
phi3 = (p3-1) * (q3-1)
while True:
    s = getPrime(10)
    if(gcd(s,p3-1) == 1):
        sinv = invert(s,p3-1)
        e = 4*s*sinv+3
        if(gcd(phi3,e) == 1):
            if(pow(m4,e,n3)==c4):
                break
e3 = e
d3 = invert(e3,phi3)
m3 = pow(c3,d3,n3)
print('Level3 passed!')

def fermat_factorization(n):
    factor_list = []
    get_context().precision = 2048
    x = int(sqrt(n))

    while True:
        x += 1
        y2 = x ** 2 - n
        if is_square(y2):
            #print('x = ',x)
            y2 = mpz(y2)
            get_context().precision = 2048
            y = int(sqrt(y2))
            factor_list.append([x+y, x-y])
        if len(factor_list) == 2:
            break
    return factor_list

#level2
c2 = m3
n2 = 87994385997075478104135902527696370476697303732829349373685150934389771812000800579489779988597377758155357032119662485786694473083701713238817766110307526481354801968791624978964643229368334587752275506234350005276147810555241459363533576625362804706641125169760333584993303919294358578117889235906667830900166286169********************************************
e2 = 65537
factor_list = fermat_factorization(n2)
[X1, Y1] = factor_list[0]
[X2, Y2] = factor_list[1]
assert X1 * Y1 == n2
assert X2 * Y2 == n2
p21 = gcd(X1, X2)
q21 = X1 // p21
p22 = gcd(Y1, Y2)
q22 = Y1 // p22
assert p21 *p22 * q21 * q22 == n2
phi2 = (p21 - 1) * (q21 - 1) * (p22 - 1) * (q22 - 1)
d2 = inverse(e2,phi2)
m2 = pow(c2,d2,n2)
print('Level2 passed!')

#level1
c1 = m2
n1 = 72968331464378596578736213097836639538889759902365332315018563128110329234698340288949958887638828272808811489147149910844881732898599415772529999325992095319128544723262119362648159655825918097703197797125275721741525608198285972415832787315444112461546745146260018587323632627512444194155444076538738583091********************************************
e1 = 65537

base = iroot(n1//21//63,4)[0]
for i in range(-10000,10000):
    x = base + i
    if(isPrime(x)):
        y = next_prime(21*x)
        z = next_prime(3*x*y)
        if(x*y*z==n1):
            break
print('Level1 passed!')

phi1 = (x-1) * (y-1) * (z-1)
d1 = inverse(e1,phi1)
m1 = pow(c1,d1,n1)
flag = long_to_bytes(m1)
print(flag)

27.png

combinelfsr

没看，想起来了就复现，爬了

backpack

没看，想起来了就复现，爬了