1.RSA

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
*from* secret *import* flag
*from* sympy *import* nextprime
*from* Crypto.Util.number *import* bytes_to_long, getPrime

*assert* len(flag) == 25
m = bytes_to_long(flag)
m_2 = m ** 2
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = getPrime(20)
e2 = nextprime(e1)
c1 = pow(m_2, e1, n)
c2 = pow(m_2, e2, n)
print(f"{n = }")
print(f"{c1 = }")
print(f"{c2 = }")
print(f"e1 * e2 = {e1 * e2}")

'''
n = 17458177708167972601006075928178603632458484653513698130811502379770886617488812250316771652389146930021368938829589382031491274654982277645713675081195878898434071987145159852740952887162069527332009321885641432738456019768929625025444474879088866227228974366107849505211731585584752493146699373193756225672994124110085929377650609630272818492357122587196177689507054437331253195681746308352119595007148278183095076648805894206703648206381027192667880258896329951674442822704455278173602418807174426453634024025913505696472554118040475552518018625223843227646352106741432348697256853398782934399404986190331498953571
c1 = 7471405734106650056049382625843915708002841439347470462100165307668378280688214492090879574410776087897693658180337804688681259258079063769978772369287634692802731848132964169521837008221893198791358132574064940033094513694509672732823363449617705449601330506117650789580295963901159638760150556881499465029802550290528277407659502530147645263353666691420412262482992667754647572508273607571234305379010869239650868102523097524355830266191353349415404387796673741672081106445872867008110953693484203085226665527380822681730290331599307280373461218359608097945882612943207895400351985861182291598698288279532314377061
c2 = 14971370164721598646339851808358316022323624829437473649759053785186506514926712225559027071464973678018911192179071523605875315910623519510708127749406716130522472223534689655159194584895819954600509548055500627183354272273017371547639975655679688709707797070296129362809716322052290443105584850047053319755165888339232529476382060096519641658643857009400813096563781522905152344905129084460152014927314488827779354059863578389916477281176873082711697526212385791989006214313663949310593595211585946062498190101384989574634018224757465892823262797526705095193092331032673106596819250387046409121623857577568095856194
e1 * e2 = 358134024233
'''

（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
25
26
27
28
29
30
31
32
33
*from* Crypto.Util.number *import* bytes_to_long, getPrime
*import* gmpy2
*import* libnum

n = 17458177708167972601006075928178603632458484653513698130811502379770886617488812250316771652389146930021368938829589382031491274654982277645713675081195878898434071987145159852740952887162069527332009321885641432738456019768929625025444474879088866227228974366107849505211731585584752493146699373193756225672994124110085929377650609630272818492357122587196177689507054437331253195681746308352119595007148278183095076648805894206703648206381027192667880258896329951674442822704455278173602418807174426453634024025913505696472554118040475552518018625223843227646352106741432348697256853398782934399404986190331498953571
c1 = 7471405734106650056049382625843915708002841439347470462100165307668378280688214492090879574410776087897693658180337804688681259258079063769978772369287634692802731848132964169521837008221893198791358132574064940033094513694509672732823363449617705449601330506117650789580295963901159638760150556881499465029802550290528277407659502530147645263353666691420412262482992667754647572508273607571234305379010869239650868102523097524355830266191353349415404387796673741672081106445872867008110953693484203085226665527380822681730290331599307280373461218359608097945882612943207895400351985861182291598698288279532314377061
c2 = 14971370164721598646339851808358316022323624829437473649759053785186506514926712225559027071464973678018911192179071523605875315910623519510708127749406716130522472223534689655159194584895819954600509548055500627183354272273017371547639975655679688709707797070296129362809716322052290443105584850047053319755165888339232529476382060096519641658643857009400813096563781522905152344905129084460152014927314488827779354059863578389916477281176873082711697526212385791989006214313663949310593595211585946062498190101384989574634018224757465892823262797526705095193092331032673106596819250387046409121623857577568095856194
e1_e2 = 358134024233

*for* x *in* range(2**19,2**20):
    *if* e1_e2 % x == 0:
        e1=x
        e2=e1_e2//x
        print(e1,e2)

e1=598439
e2=598447

print(gmpy2.gcdext(e1,e2))

*#s=-74806*
t=74805
s=74806

c11=gmpy2.invert(c1,n)
print(c11)
A=pow(c11,s,n)
B=pow(c2,t,n)
m_2=pow(A*B,1,n)
m=int(gmpy2.iroot(m_2,2)[0])
print(libnum.n2s(m))

b'HnuCTF{W3lc0m3_T0_HnuCTF}'

（2）思路

$注意到，e_1和e_2都是20位数，且十分接近$

$那么已知e_1*e_2,则可以对e_1 \in (2^{19},2^{20})进行爆破$

$对于c_1 \equiv m^{e_1} \pmod n,c_2 \equiv m^{e_2} \pmod n,要求m$

$只需要用扩展欧几里得算法求得s、t满足se_1+te_2=1,其中一正一负，负的求c的逆元$

$则m\equiv c_1^s*c_2^t \pmod n$

2.Feimat

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* getPrime, bytes_to_long
*from* gmpy2 *import* gcd
*from* sympy *import* nextprime
*from* secret *import* flag, gen_mask

length = len(flag)
flag1 = flag[:length//2]
flag2 = flag[length//2:]
e = 65537

p1 = getPrime(1024)
q1 = nextprime(p1 + 2025)
*assert* gcd(e, (p1 - 1) * (q1 - 1)) == 1

n1 = p1 * q1
m1 = bytes_to_long(flag1)
mask = gen_mask(p1)
*assert* pow(202508, mask, p1) == 1
m1 = m1 ^ mask
c1 = pow(m1, e, n1)

p2 = getPrime(1024)
q2 = getPrime(1024)
n2 = p2 * q2
*assert* gcd(e, (p2 - 1) * (q2 - 1)) == 1
m2 = bytes_to_long(flag2)
c2 = pow(m2, e, n2)
hint = pow(805202 * p2 + 202508, q2, n2)

print(f"{n1 = }")
print(f"{c1 = }")
print(f'{n2 = }')
print(f'{c2 = }')
print(f'{hint = }')
'''
e=65537
n = 14610352399364581839773976105204260593742046173052215214293943619469687337552967511331744723868290459678719422805891651539597387430792362975150868136289273427691956897063875842999754148595972814688609035621065751060344999621634824460040776132447541189689653530926724546617178089216683112500750254925004561120442753737573579598402763007336135149888207655172131572410524529690466176293372760406006171069177282309609657024579767931660698839484717081173557357061844859022385459800384975348869868572643438383565270202207252068128005985572830717428809980325653021434420867476415366324324398065561600756700706843939843993163
c1 = 8465143742411821972950758746203548444649023707421431748058495413934664036140667519617557238622361952859450890921545663718558786519885627652287097250703530233057884999638180923934755092357948744968197730885724096146857615240908863737270879392301821602156658197221638228744727376648394094369817788314361905334656329358416793122360293311202863997598781268538697207675750745952261600068630193325762063241586664394315861662180370534382751496815733586130314526809356463549239905217777358537920364369522116112794049785115278223362691339204549622513864593253237512869370340576110834782508437996506389087050666044493292114942
n2 = 13799551095924286287155670525606290398362293970248794967450656028744385674062870325176015144327517456001055548828314494733902790027638169420402778982150175571852352545718995648991642014269959693060543440177246532172763748944340005291575714876079747290552125103832518001381626482303181023456172190837214457853127901010360881093272256236011120900409081212770946002286032343703041252480041833312252348795751267374735758186459354840574257888414172429504451213226350666986679759202221350429485507831511877065990610897025704817269670354911244295396294825315362708993051758888160381056404954736274025806821557321546389354631
c2 = 12098125638686600330681532303224452864076895892556196147971087856314288894816800362210145688710550014510670238814216832687116266939813520624126503741579573457763782978471387317612171192816327881430086801710244592008999981459342409266982820931446051506150376371301166794333293090574724436002525739321752116316240840573890183010958414463338348067820858550869967297011949577406214018282174796029358450146670160103794549021355750850001327532373959264500898213923493271408581277110842352950264929761701848736199113597159135120850152491093843812003313054143148459215100246677620939357208054868981387182891400397463723402245
hint = 13293915139077999305765300679678380163641196499807308734790290377718685703314690704182121097376950055172805778617253134536669278189733159942605193584824914796548357471361616758125280726775648258575917816419417123290159655475726988087725829357960805894503729949105870559975409837759685353980504894999621554037804293306015934065619455269733989815385667995811394179676934748040883934051987380467895106749838475782837485547835821462554468791570964807694216164584217820193920874690185042487319230404280920303279953128112483731560717326543788837329898007046787782629991997548867878517619046602463443922207569283517682571320
'''

（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
25
26
27
28
29
30
31
32
33
34
35
36
37
*from* Crypto.Util.number *import* *
*import* gmpy2
*import* libnum
*import* math

e=65537
n1 = 14610352399364581839773976105204260593742046173052215214293943619469687337552967511331744723868290459678719422805891651539597387430792362975150868136289273427691956897063875842999754148595972814688609035621065751060344999621634824460040776132447541189689653530926724546617178089216683112500750254925004561120442753737573579598402763007336135149888207655172131572410524529690466176293372760406006171069177282309609657024579767931660698839484717081173557357061844859022385459800384975348869868572643438383565270202207252068128005985572830717428809980325653021434420867476415366324324398065561600756700706843939843993163
c1 = 8465143742411821972950758746203548444649023707421431748058495413934664036140667519617557238622361952859450890921545663718558786519885627652287097250703530233057884999638180923934755092357948744968197730885724096146857615240908863737270879392301821602156658197221638228744727376648394094369817788314361905334656329358416793122360293311202863997598781268538697207675750745952261600068630193325762063241586664394315861662180370534382751496815733586130314526809356463549239905217777358537920364369522116112794049785115278223362691339204549622513864593253237512869370340576110834782508437996506389087050666044493292114942
n2 = 13799551095924286287155670525606290398362293970248794967450656028744385674062870325176015144327517456001055548828314494733902790027638169420402778982150175571852352545718995648991642014269959693060543440177246532172763748944340005291575714876079747290552125103832518001381626482303181023456172190837214457853127901010360881093272256236011120900409081212770946002286032343703041252480041833312252348795751267374735758186459354840574257888414172429504451213226350666986679759202221350429485507831511877065990610897025704817269670354911244295396294825315362708993051758888160381056404954736274025806821557321546389354631
c2 = 12098125638686600330681532303224452864076895892556196147971087856314288894816800362210145688710550014510670238814216832687116266939813520624126503741579573457763782978471387317612171192816327881430086801710244592008999981459342409266982820931446051506150376371301166794333293090574724436002525739321752116316240840573890183010958414463338348067820858550869967297011949577406214018282174796029358450146670160103794549021355750850001327532373959264500898213923493271408581277110842352950264929761701848736199113597159135120850152491093843812003313054143148459215100246677620939357208054868981387182891400397463723402245
hint = 13293915139077999305765300679678380163641196499807308734790290377718685703314690704182121097376950055172805778617253134536669278189733159942605193584824914796548357471361616758125280726775648258575917816419417123290159655475726988087725829357960805894503729949105870559975409837759685353980504894999621554037804293306015934065619455269733989815385667995811394179676934748040883934051987380467895106749838475782837485547835821462554468791570964807694216164584217820193920874690185042487319230404280920303279953128112483731560717326543788837329898007046787782629991997548867878517619046602463443922207569283517682571320

*#flag2*
A=pow(202508,n2,n2)
p2=gmpy2.gcd(hint-A,n2)
q2=n2//p2
phi2=(p2-1)*(q2-1)
d2=gmpy2.invert(e,phi2)
m2=pow(c2,d2,n2)
flag2=libnum.n2s(int(m2))
print(flag2)
*#falg2=y_kn0w_wh4t_Fermat_1111s}*

*#flag1*
sqrt=math.isqrt(n1)
*for* x *in* range(sqrt-9999,sqrt):
    *if* n1%x==0:
        p1=x
        q1=n1//x
        phi1=(p1-1)*(q1-1)
        d1=gmpy2.invert(e,phi1)
        m11=pow(c1,d1,n1)
        m1=m11^(p1-1)
        flag1=libnum.n2s(int(m1))
        flag=flag1+flag2
        print(flag)
HnuSec{I_th1nk_y0u_a1re4dy_kn0w_wh4t_Fermat_1111s}

（2）思路

flag1: 由题易知，p、q十分接近，已知n=p*q

$对p \in (\sqrt {n}-9999,\sqrt {n})进行爆破，得到p和q$

$又由费马小定理 a^{p-1} \equiv 1\pmod p,故猜测mask=\lambda *(p-1)$

$flag2:hint \equiv 202508^q \pmod p
令A=202508^n=202508^{pq} \equiv 202508^q \pmod p$

则p=gcd(hint-A,n)

3.LCG

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* getPrime, bytes_to_long
*from* random *import* randint
*from* secret *import* flag

class lcglcg:
    def __init__(self, seed1, seed2, a, b, c, n):
        self.state = [seed1, seed2]
        self.a = a
        self.b = b
        self.c = c
        self.n = n

    def next(self):
        new_state = (self.a * self.state[-2] + self.b * self.state[-1] + self.c) % self.n
        self.state.append(new_state)
        *return* new_state

flag1 = bytes_to_long(flag[:len(flag)//2])
flag2 = bytes_to_long(flag[len(flag)//2:])
n = getPrime(256)
a, b, c = [randint(1, n - 1) *for* _ *in* range(3)]
rand = lcglcg(flag1, flag2, a, b, c, n)
print(f"{n = }")
*for* i *in* range(5):
    print(f"state{i + 1} = {rand.next()}")

'''
n = 112985467699129082308933220510315694444233243027410919702612791784307914370263
state1 = 75194174695846143145856449178766074372329052728921502383948707888068285781201
state2 = 47959544953411013977666445717133476989728951243668241427192593231844551524515
state3 = 100266370555255818575708946681302227601890864427275753365657775643727045505990
state4 = 28274444764580605311958137104574248285504475353240922231969532435126796836661
state5 = 80533359831980560745151095597638020782602977679126998472484675233070226468529
'''

（1）解答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
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
*from* Crypto.Util.number *import* *

N = 112985467699129082308933220510315694444233243027410919702612791784307914370263
s3 = 75194174695846143145856449178766074372329052728921502383948707888068285781201
s4 = 47959544953411013977666445717133476989728951243668241427192593231844551524515
s5 = 100266370555255818575708946681302227601890864427275753365657775643727045505990
s6 = 28274444764580605311958137104574248285504475353240922231969532435126796836661
s7 = 80533359831980560745151095597638020782602977679126998472484675233070226468529

A=[[s3,s4,s5],
[s4,s5,s6],
[1,1,1]]

B=[[s4,s5,s6],
[s5,s6,s7],
[1,1,1]]

def matrix_mul_mod(A, B, mod):
    n, m = len(A), len(A[0])
    p = len(B[0])
    result = [[0] * p *for* _ *in* range(n)]
    *for* i *in* range(n):
        *for* j *in* range(p):
            total = 0
            *for* k *in* range(m):
                total = (total + A[i][k] * B[k][j]) % mod
            result[i][j] = total
    *return* result

def matrix_inv_mod(M, mod):
    a, b, c = M[0]
    d, e, f = M[1]
    g, h, i = M[2]
    *# 计算行列式*
    det = (a*(e*i - f*h) - b*(d*i - f*g) + c*(d*h - e*g)) % mod
    det_inv = pow(det, -1, mod)
    *# 伴随矩阵*
    adj = [
        [(e*i - f*h) % mod, (c*h - b*i) % mod, (b*f - c*e) % mod],
        [(f*g - d*i) % mod, (a*i - c*g) % mod, (c*d - a*f) % mod],
        [(d*h - e*g) % mod, (b*g - a*h) % mod, (a*e - b*d) % mod]
    ]
    *# 逆矩阵 = 伴随矩阵 * det_inv mod mod*
    inv = [[(adj[i][j] * det_inv) % mod *for* j *in* range(3)] *for* i *in* range(3)]
    *return* inv

C=matrix_inv_mod(A,N)
M=matrix_mul_mod(B,C,N)
a=M[1][0]
b=M[1][1]
c=M[1][2]
*#a = 80844630658753533388902967411208024843462595081905849501628736161427470447484*
*#b = 85648111093734473316254948769654085010734404462968481001425102935310161667653*
*#c = 21766242407954822086489769450621446883455856458325117328999781876077927439874*

as2=(s4-c-b*s3)%N
s2=(as2*pow(a,-1,N))%N
as1=(s3-c-b*s2)%N
s1=(as1*pow(a,-1,N))%N
flag1=long_to_bytes(s1)
flag2=long_to_bytes(s2)
flag=flag1+flag2
print(flag)

HnuSec{*0h*!!!*!*E4sy_D0ubl3_Lcg_R1ght*?*}

（2）思路1

$由题意得：s_{i+2}=as_i+bs_{i+1}+c \pmod N$

$已知s_3,s_4,s_5,s_6,s_7，N,求s_1,s_2$

$又s_{i+2}=as_i+bs_{i+1}+c*1=
\begin{pmatrix}
a,b,c
\end{pmatrix}
\begin{pmatrix}
s_i\
s_{i+1}\
1
\end{pmatrix}$

但这样无法递推，故有如下构造：

$\mathbf v_{i+1}=\begin{pmatrix}
s_{i+1}\
s_{i+2}\
1
\end{pmatrix}=\begin{pmatrix}
0&1&0\
a&b&c\
0&0&1
\end{pmatrix}
\begin{pmatrix}
s_i\
s_{i+1}\
1
\end{pmatrix}=\mathbf M \mathbf v_i$

那么:

$B=(v_4,v_5,v_6)=\mathbf M(v_3,v_4,v_5)=\mathbf MA$

$那么M=B*A^{-1},可求到a,b,c，从而逆推出s_2,s_1$

涉及到模N下的矩阵的乘法、矩阵的逆，故学习了矩阵

（3）解答2（解方程）

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

N = 112985467699129082308933220510315694444233243027410919702612791784307914370263
s3 = 75194174695846143145856449178766074372329052728921502383948707888068285781201
s4 = 47959544953411013977666445717133476989728951243668241427192593231844551524515
s5 = 100266370555255818575708946681302227601890864427275753365657775643727045505990
s6 = 28274444764580605311958137104574248285504475353240922231969532435126796836661
s7 = 80533359831980560745151095597638020782602977679126998472484675233070226468529
*#系数矩阵*
A=(s3-s4)%N
B=(s4-s5)%N
C=(s4-s5)%N
D=(s5-s6)%N
E=(s5-s6)%N
F=(s6-s7)%N

det=(A*D-B*C)%N
det_inv=pow(det, -1, N)

a=((E*D-B*F)%N)*det_inv%N
b=((A*F-C*E)% N)*det_inv% N
c=(s5-a*s3-b*s4)%N

as2=(s4-c-b*s3)%N
s2=(as2*pow(a,-1,N))%N
as1=(s3-c-b*s2)%N
s1=(as1*pow(a,-1,N))%N
flag1=long_to_bytes(s1)
flag2=long_to_bytes(s2)
flag=flag1+flag2
print(flag)

（4）思路2

由方程组：

$\begin{cases}
s_5=as_3+bs_4+c \pmod N \
s_6=as_4+bs_5+c \pmod N \
s_7=as_5+bs_6+c \pmod N
\end{cases}$

有：

$\begin{cases}
s_5-s_6=a(s_3-s_4)+b(s_4-s_5)\
s_6-s_7=a(s_4-s_5)+b(s_5-s_6)
\end{cases}记为
\begin{cases}
Aa+Bb=E \pmod N\
Ca+Db=F \pmod N
\end{cases}$

用克莱姆法则解方程即可

4.Lattice

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

flag = b'Hnusec{********}'

flag = flag + (64-len(flag))*b'a'
m = bytes_to_long(flag)
p = getPrime(512)

def enc(m,p):
    a = getPrime(255)
    print(a)
    x = m * invert(a,p) % p
    *return* x

X = []
*for* i *in* range(2):
    x = enc(m,p)
    X.append(int(x))

print(p)
print(X)

"""
p = 7864799480688061948280848010210585621657530357391571767595799481935148382260099317510405311732231071753131983039106747172697524512589589500334039842824979
X = [2839741580901873025101061768235549006691944412940209354868530840120836706233986744173985640701528741233844969252931957248720621487349612599643500679481486, 7769693514828080880704360118562124554448742751151819813472853796019979805990315761344951121398138958323999088865292899525710199631942132193123207074401938]
"""

（1）解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
*from* Crypto.Util.number *import* *
*from* gmpy2 *import* *

p = 7864799480688061948280848010210585621657530357391571767595799481935148382260099317510405311732231071753131983039106747172697524512589589500334039842824979
X = [2839741580901873025101061768235549006691944412940209354868530840120836706233986744173985640701528741233844969252931957248720621487349612599643500679481486, 7769693514828080880704360118562124554448742751151819813472853796019979805990315761344951121398138958323999088865292899525710199631942132193123207074401938]
x1,x2=X
B=(pow(x1,-1,p)*x2)%p
M=matrix(ZZ,[[0,p],[1,B]])
a2,a1=M.LLL()[0]
a1,a2=abs(a1),abs(a2)
m=(x1*a1)%p
flag=long_to_bytes(int(m))
print(flag)
Hnusec{*0hh_y0u_r3a11y_kn0w_7h3_Lattice*}aaaaaaaaaaaaaaaaaaaaaaaaa

（2）思路

$已知m \equiv a_1x_1 \equiv a_2x_2 \pmod p,则a_1 \equiv x_1^{-1}x_2a_2 \pmod p$

$则a_1-a_2x_2x_1^{-1}=kp,即
\begin{pmatrix}
k&a_2 \end{pmatrix}
\begin{pmatrix}
0&p\
1&x_2x_1^{-1}
\end{pmatrix}=
\begin{pmatrix}
a_2&a_1
\end{pmatrix}$