文章目录
- 前言
- easy_math
- Euler
- babyLCG
- baby_xor
前言
由于探姬小姐姐（bushi)跟我讲LitCTF是一个新生赛捏，所以我出的几个题题目都是比较简单，偏向于新手向。这里面可能有一点难度的题目就是baby_xor了，简单考一下copper定理，但是最终有45解挺出乎我的意料的。
easy_math
题目：
from Crypto.Util.number import *
from secret import flagm = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(128)
n = p*q
hint = p**3-q**5
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'hint = {hint}')
'''
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
'''
思路1：已知 n = p ∗ q n=p*q n=p∗q,以及 h i n t = p 3 − q 5 hint = p^3-q^5 hint=p3−q5，可直接构成方程组，然后直接解方程得到p q。
import gmpy2
from Crypto.Util.number import *
from sympy import *
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
e = 65537
p, q = symbols("p q")
eq = [p * q - n, p**3-q**5 - hint]
result = list(nonlinsolve(eq, [p, q]))
p, q = int(result[0][0]), int(result[0][1])
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
思路2：由于 p 3 p^3 p3远大于 q 5 q^5 q5，所以我们直接对hint开三次方，可到一个近似p的数，之后往后循环取下一个素数直至被n整除即可，此时该素数为p。
import gmpy2
from Crypto.Util.number import *
from sympy import *
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932
e = 65537
p_near = gmpy2.iroot(hint,3)[0]
while n%p_near !=0:p_near = gmpy2.next_prime(p_near)
p = p_near
q = n//p
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
Euler
题目：
from Crypto.Util.number import *
from secret import flagm = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m,n-p-q+3,n)
print(f'n = {n}')
print(f'c = {c}')
"""
n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441
"""
这题的考点是对欧拉定理的运用。
欧拉定理：对于任意两个正整数a,n，若gcd(a,n)=1，则：
a φ ( n ) ≡ 1 m o d n a^{\varphi(n)} \equiv 1 \space mod \space n aφ(n)≡1 mod n
已知
c ≡ m n − p − q + 3 m o d n c \equiv m^{n-p-q+3} \space mod \space n c≡mn−p−q+3 mod n
根据欧拉定理，化简，得到
c ≡ m φ ( n ) + 2 m o d n ≡ m 2 m o d n c \equiv m^{\varphi(n)+2} mod n \equiv m^2 \space mod \space n c≡mφ(n)+2modn≡m2 mod n
因此直接将c开平方即可到flag
import gmpy2
from Crypto.Util.number import *n = 115140122725890943990475192890188343698762004010330526468754961357872096040956340092062274481843042907652320664917728267982409212988849109825729150839069369465433531269728824368749655421846730162477193420534803525810831025762500375845466064264837531992986534097821734242082950392892529951104643690838773406549
c = 406480424882876909664869928877322864482740577681292497936198951316587691545267772748204383995815523935005725558478033908575228532559165174398668885819826720515607326399097899572022020453298441
m = gmpy2.iroot(c,2)[0]
flag = long_to_bytes(m)
print(flag)
babyLCG
题目：
from Crypto.Util.number import *
from secret import flagm = bytes_to_long(flag)
bit_len = m.bit_length()
a = getPrime(bit_len)
b = getPrime(bit_len)
p = getPrime(bit_len+1)seed = m
result = []
for i in range(10):seed = (a*seed+b)%presult.append(seed)
print(result)
"""
result = [699175025435513913222265085178805479192132631113784770123757454808149151697608216361550466652878, 193316257467202036043918706856603526262215679149886976392930192639917920593706895122296071643390, 1624937780477561769577140419364339298985292198464188802403816662221142156714021229977403603922943, 659236391930254891621938248429619132720452597526316230221895367798170380093631947248925278766506, 111407194162820942281872438978366964960570302720229611594374532025973998885554449685055172110829, 1415787594624585063605356859393351333923892058922987749824214311091742328340293435914830175796909, 655057648553921580727111809001898496375489870757705297406250204329094679858718932270475755075698, 1683427135823894785654993254138434580152093609545092045940376086714124324274044014654085676620851, 492953986125248558013838257810313149490245209968714980288031443714890115686764222999717055064509, 70048773361068060773257074705619791938224397526269544533030294499007242937089146507674570192265]
"""
本题主要是对4个LCG公式的综合利用，属于一道非常经典的LCG基础题目
1.已知 X n + 1 反推 X n X_{n+1}反推X_n Xn+1反推Xn
X n = a − 1 ( X n + 1 − b ) m o d m X_n = a^{-1}(X_{n+1}-b)\space mod \space m Xn=a−1(Xn+1−b) mod m
证明：
X n + 1 = a X n + b m o d m X_{n+1} = aX_n +b \space mod \space m Xn+1=aXn+b mod m
⇒ a X n = X n + 1 − b m o d m \Rightarrow aX_n = X_{n+1}-b \space mod \space m ⇒aXn=Xn+1−b mod m
⇒ X n = a − 1 ( X n + 1 − b ) m o d m \Rightarrow X_n = a^{-1}(X_{n+1}-b) \space mod \space m ⇒Xn=a−1(Xn+1−b) mod m
2.求a
a = ( X n + 2 − X n + 1 ) ( X n + 1 − X n ) − 1 m o d m a = (X_{n+2}-X_{n+1})(X_{n+1}-X_{n})^{-1} \space mod \space m a=(Xn+2−Xn+1)(Xn+1−Xn)−1 mod m
证明：
{ X n + 2 = a X n + 1 + b m o d m X n + 1 = a X n 1 + b m o d m \left\{\begin{matrix} X_{n+2} = aX_{n+1}+b \space mod \space m \space \\ X_{n+1} = aX_{n1}+b \space mod \space m \end{matrix}\right. {Xn+2=aXn+1+b mod m Xn+1=aXn1+b mod m
两式相减
X n + 2 − X n + 1 = a ( X n + 1 − X n ) m o d m X_{n+2}-X_{n+1} = a(X_{n+1}-X_n) \space mod \space m Xn+2−Xn+1=a(Xn+1−Xn) mod m
⇒ a = ( X n + 2 − X n + 1 ) ( X n + 1 − X n ) − 1 m o d m \Rightarrow a = (X_{n+2}-X_{n+1})(X_{n+1}-X_n)^{-1} \space mod \space m ⇒a=(Xn+2−Xn+1)(Xn+1−Xn)−1 mod m
3.求b
b = ( X n + 1 − a X n ) m o d m b = (X_{n+1}-aX_{n}) \space mod \space m b=(Xn+1−aXn) mod m
证明：
X n + 1 = a X n + b m o d m X_{n+1} = aX_n +b \space mod \space m Xn+1=aXn+b mod m
⇒ b = X n + 1 − a X n m o d m \Rightarrow b = X_{n+1}-aX_n \space mod \space m ⇒b=Xn+1−aXn mod m
4.求m
t n = X n + 1 − X n , m = g c d ( t n + 1 t n − 1 − t n t n , t n t n − 2 − t n − 1 t n − 1 ) t_n = X_{n+1}-X_{n},m = gcd(t_{n+1}t_{n-1}-t_{n}t_{n},t_{n}t_{n-2}-t_{n-1}t_{n-1}) tn=Xn+1−Xn,m=gcd(tn+1tn−1−tntn,tntn−2−tn−1tn−1)
证明：
设 t n = X n + 1 − X n t_n= X_{n+1}-X_n tn=Xn+1−Xn
⇒ t n = ( a X n + b ) − ( a X n − 1 + b ) = a t n − 1 m o d m \Rightarrow t_n = (aX_n+b)-(aX_{n-1}+b)=at_{n-1} \space mod \space m ⇒tn=(aXn+b)−(aXn−1+b)=atn−1 mod m
⇒ t n + 1 t n − 1 − t n t n = a t n t n − 1 − a t n − 1 a t n − 1 m o d m \Rightarrow t_{n+1}t_{n-1}-t_{n}t_{n} = at_{n}t_{n-1}-at_{n-1}at_{n-1} \space mod \space m ⇒tn+1tn−1−tntn=atntn−1−atn−1atn−1 mod m
⇒ t n + 1 t n − 1 − t n t n = a a t n − 1 t n − 1 − a t n − 1 a t n − 1 m o d m \Rightarrow t_{n+1}t_{n-1}-t_{n}t_{n} = aat_{n-1}t_{n-1}-at_{n-1}at_{n-1} \space mod \space m ⇒tn+1tn−1−tntn=aatn−1tn−1−atn−1atn−1 mod m
⇒ t n + 1 t n − 1 − t n t n = 0 m o d m \Rightarrow t_{n+1}t_{n-1}-t_{n}t_{n} = 0 \space mod \space m ⇒tn+1tn−1−tntn=0 mod m
可证， T n = t n + 1 t n − 1 − t n t n T_n = t_{n+1}t_{n-1}-t_{n}t_{n} Tn=tn+1tn−1−tntn为 m m m的倍数
那么， T n 和 T n − 1 之间的最大公约数数大概率 m T_n和T_{n-1}之间的最大公约数数大概率m Tn和Tn−1之间的最大公约数数大概率m
⇒ m = g c d ( T n , T n − 1 ) \Rightarrow m = gcd(T_n,T_{n-1}) ⇒m=gcd(Tn,Tn−1)
⇒ m = g c d ( ( t n + 1 t n − 1 − t n t n ) , ( t n t n − 2 − t n − 1 t n − 1 ) ) \Rightarrow m = gcd((t_{n+1}t_{n-1}-t_{n}t_{n}),(t_{n}t_{n-2}-t_{n-1}t_{n-1})) ⇒m=gcd((tn+1tn−1−tntn),(tntn−2−tn−1tn−1))
由于在求m的时候不知道gcd出来的是m还是m的倍数，所以我们把每组 g c d ( T n , T n − 1 ) gcd(T_n,T_{n-1}) gcd(Tn,Tn−1)都算出来，然后再计算出a和b，最后看一下哪一个是flag就ok了
解题脚本：
import gmpy2
from Crypto.Util.number import *
result = [699175025435513913222265085178805479192132631113784770123757454808149151697608216361550466652878, 193316257467202036043918706856603526262215679149886976392930192639917920593706895122296071643390, 1624937780477561769577140419364339298985292198464188802403816662221142156714021229977403603922943, 659236391930254891621938248429619132720452597526316230221895367798170380093631947248925278766506, 111407194162820942281872438978366964960570302720229611594374532025973998885554449685055172110829, 1415787594624585063605356859393351333923892058922987749824214311091742328340293435914830175796909, 655057648553921580727111809001898496375489870757705297406250204329094679858718932270475755075698, 1683427135823894785654993254138434580152093609545092045940376086714124324274044014654085676620851, 492953986125248558013838257810313149490245209968714980288031443714890115686764222999717055064509, 70048773361068060773257074705619791938224397526269544533030294499007242937089146507674570192265]
t = []
for i in range(len(result)-1):t.append(result[i]-result[i-1])
for i in range(len(result)-3):p = gmpy2.gcd((t[i + 1] * t[i - 1] - t[i] * t[i]), (t[i + 2] * t[i] - t[i + 1] * t[i + 1]))try:a = (gmpy2.invert(result[8] - result[7], p) * (result[9] - result[8])) % pb = (result[9] - a * result[8]) % pseed = (result[0] - b) * gmpy2.invert(a, p) % pprint(long_to_bytes(seed))except:continue
baby_xor
题目：
from Crypto.Util.number import *
from secret import flagm = bytes_to_long(flag)
assert len(flag)==32
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c1 = p^m
c2 = pow(m,e,n)
print(f'n = {n}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
"""
n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
c2 = 112016152270171196606652761990170033221036025260883289104273504703557624964071464062375228351458191745141525003775876044271210498526920529385038130932141551598616579917681815276713386113932345056134302042399379895915706991873687943357627747262597883603999621939794450743982662393955266685255577026078256473601
"""
这题主要考点是coppersmith,但是卡了上届。需要去调epsilon增大格子，从而增大根的上限。当epsilon调至最小，即0.01时；p为512bit，p的高位至少泄露264bit时候，环多项式方程在模n情况下有解，但是现在p = p>>256，也就是说只泄露了高256位，我们还需要爆破8bit才能copper出来，大概爆破时间5~6分钟左右。
from tqdm import *
from Crypto.Util.number import *n = 139167681803392690594490403105432649693546256181767408269202101512534988406137879788255103631885736461742577594980136624933914700779445704490217419248411578290305101891222576080645870988658334799437317221565839991979543660824098367011942169305111105129234902517835649895908656770416774539906212596072334423407
c1 = 11201139662236758800406931253538295757259990870588609533820056210585752522925690049252488581929717556881067021381940083808024384402885422258545946243513996
pbits = 512
p_high = c1>>256
for i in trange(2**8):p4 = p_high<<8p4 = p4 + ikbits = pbits - p4.nbits()p4 = p4 << kbitsPR.<x> = PolynomialRing(Zmod(n))f = x + p4roots = f.small_roots(X=2^kbits, beta=0.4, epsilon=0.01)if roots: p = p4+int(roots[0]) if n%p==0:print(i,p)breakm = c1.__xor__(int(p))
flag = long_to_bytes(int(m))
print(flag)
【善，论心不论迹，论迹贫家无孝子；恶，论迹不论心，论心世上无完人。】
