有幸参与了本次比赛crypto misc OSINT出题，难易程度循序渐进，下面记录一下本人题目题解((
比赛网址：https://yuanshen.life/
CRYPTO
SuperbRSA（85支队伍攻克）
题目
CRYPTO真的很难吗？Ö_O不会吧不会吧！，一定要相信自己咩~
出题人：Kicky_Mu
#user:mumu666
from Crypto.Util.number import *
p=getPrime(1024)
q=getPrime(1024)
n=p*q
e1=55
e2=200
m=bytes_to_long("flag")
assert(pow(m,5) < n)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print("n=",n)
print("c1=",c1)
print("c2=",c2)
n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021我的解答：
这题属实是第二天的签到题了。虽然有脚本可套，但尽量还是要懂原理。
我们不难发现e1和e2的GCD不为1，看这个代码：assert(pow(m,5) < n) 消息的五次方小于n，那么如果我们找到m的五次方然后取它的五次方根不就行了？
如何去求呢？这里需要一个转换：
我们令：
5ax + 5by = 5
然后我们将e1和e2同除以5，则得到a=11和b=40，这时他们彼此互为质数，这样一来，我们就可以利用数学证明得到m的五次方：
c1 = me1 mod n
c2 = me2 mod n
[(c1x) mod n] * [(c2y) mod n] = (me1*x+e2*y) mod n = m5ax+5by mod n = m5 mod n
因此，便得到m5 最后使用gmpy2的iroot函数来获得整数根。
exp：
#mumu666
import gmpy2
from Crypto.Util.number import long_to_bytes
def extended_euclid_gcd(a, b):
"""
Returns a list `result` of size 3 where:
Referring to the equation ax + by = gcd(a, b)
result[0] is gcd(a, b)
result[1] is x
result[2] is y
"""
s = 0; old_s = 1
t = 1; old_t = 0
r = b; old_r = a
while r != 0:
quotient = old_r//r # In Python, // operator performs integer or floored division
old_r, r = r, old_r - quotient*r
old_s, s = s, old_s - quotient*s
old_t, t = t, old_t - quotient*t
return [old_r, old_s, old_t]
n= 19006830358118902392432453595802675566730850352890246995920642811967821259388009049803513102750594524106471709641202019832682438027312468849299985832675191795417160553379580813410722359089872519372049229233732405993062464286888889084640878784209014165871696882564834896322508054231777967011195636564463806270998326936161449009988434249178477100127347406759932149010712091376183710135615375272671888541233275415737155953323133439644529709898791881795186775830217884663044495979067807418758455237701315019683802437323177125493076113419739827430282311018083976114158159925450746712064639569301925672742186294237113199023
c1= 276245243658976720066605903875366763552720328374098965164676247771817997950424168480909517684516498439306387133611184795758628248588201187138612090081389226321683486308199743311842513053259894661221013008371261704678716150646764446208833447643781574516045641493770778735363586857160147826684394417412837449465273160781074676966630398315417741542529612480836572205781076576325382832502694868883931680720558621770570349864399879523171995953720198118660355479626037129047327185224203109006251809257919143284157354935005710902589809259500117996982503679601132486140677013625335552533104471327456798955341220640782369529
c2= 11734019659226247713821792108026989060106712358397514827024912309860741729438494689480531875833287268454669859568719053896346471360750027952226633173559594064466850413737504267807599435679616522026241111887294138123201104718849744300769676961585732810579953221056338076885840743126397063074940281522137794340822594577352361616598702143477379145284687427705913831885493512616944504612474278405909277188118896882441812469679494459216431405139478548192152811441169176134750079073317011232934250365454908280676079801770043968006983848495835089055956722848080915898151352242215210071011331098761828031786300276771001839021
e1=55
e2=200
# ax + by = 1
gcd, x, y = extended_euclid_gcd(e1//5, e2//5)
m = (pow(c1, x, n) * pow(c2, y, n)) % n
m = gmpy2.iroot(m, 5)[0]
print(long_to_bytes(m))
#SICTF{S0_Great_RSA_Have_Y0u_Learned?}babyRSA（9支队伍攻克）
题目
树木想要一个baby题目，不说了。。那就来个吧！
出题人：Kicky_Mu
p = random_prime(1<<512)
with open("ffllaagg.txt", "rb") as f:
flag = int.from_bytes(f.read().strip(), "big")
assert flag < p
a = randint(2, p-1)
b = randint(2, p-1)
x = randint(2, p-1)
def h():
global a, b, x
x = (a*x + b) % p
return x
PR.<X> = PolynomialRing(GF(p))
f = h() + h()*X + h()*X**2 + h()*X**3 + h()*X**4 + h()*X**5
v_me_50 = [(i, f(i)) for i in range(1, 5)]
print(p)
print(v_me_50)
print(f(flag))
p = 8432316544210923620966806031040552674652729976238765323782536889706914762471638598119051165931563126522925761119650997703305509546949570434637437942542827
v_me_50 = [(1, 5237331460408741346823741966490617418367283531029963248255318507187035341590236835730694472064897540292182231844047116067936691956970631907605500080014355), (2, 5798977431976767515500795413771120575460553181185728489626756434911307088093739452469315524092208822863785429164219547384598943937099787390543171055679780), (3, 5030862375386942201139427367618716490378481408210696947331523552250206476805124204780313138835912303941204343248384742875319182761611109448446270069831113), (4, 4705360705603328842229554954026497175574981026785287316439514185860486128679614980330307863925942038530792583274904352630757089631411920876914529907563209)]
f_flag = 7251453750672416392395590357197330390627853878488142305852099080761477796591562813165554150640801022882531891827653530623183405183605476913024545431842867我的解答：
我们可知题目使用LCG生成了一个
的五次多项式f(x)，并且给出了四个点和f(flag)以及p的值
显然恢复五次多项式需要知道6个点才行，但是题目的系数都是LCG产生的，而且LCG的模也是p
因此多项式的系数可以完美的表示为a b x 的组合
四个点能列出四个式子，以此便于恢复整个多项式，然后使用sage的roots()把flag找出即可
解联立的部分可使用sage的groebner basis
exp:
from Crypto.Util.number import *
p = 8432316544210923620966806031040552674652729976238765323782536889706914762471638598119051165931563126522925761119650997703305509546949570434637437942542827
v_me_50 = [(1, 5237331460408741346823741966490617418367283531029963248255318507187035341590236835730694472064897540292182231844047116067936691956970631907605500080014355), (2, 5798977431976767515500795413771120575460553181185728489626756434911307088093739452469315524092208822863785429164219547384598943937099787390543171055679780), (3, 5030862375386942201139427367618716490378481408210696947331523552250206476805124204780313138835912303941204343248384742875319182761611109448446270069831113), (4, 4705360705603328842229554954026497175574981026785287316439514185860486128679614980330307863925942038530792583274904352630757089631411920876914529907563209)]
f_flag = 7251453750672416392395590357197330390627853878488142305852099080761477796591562813165554150640801022882531891827653530623183405183605476913024545431842867
shu = [v[1] for v in v_me_50]
P.<a, b, x> = GF(p)[]
def g():
global x
x = a * x + b
return x
mu = [g() for _ in range(6)]
print(mu)
M = matrix.vandermonde([1, 2, 3, 4, 5, 6])[:-2]
eqs = M * vector(mu) - vector(shu)
I = P.ideal(list(eqs))
assert I.dimension() == 0
V = I.variety()
sol = V[0]
a = sol["a"]
b = sol["b"]
x = sol["x"]
print(a, b, x)
P.<X> = PolynomialRing(GF(p))
f = g() + g() * X + g() * X ** 2 + g() * X ** 3 + g() * X ** 4 + g() * X ** 5
flag = (f - f_flag).roots()[0][0]
print(flag)
#10603559521836345227305379240054224406598915804878659960034174671004824270514372053024468093
print(long_to_bytes(flag))
#SICTF{Th3s_1s_a_high_l3vel_p0lyn0mial}[进阶]2024_New_Setback（10支队伍攻克）
题目
新的一年，我们总要有一个新的起点
标签：SICTF,v2,u1,misc,crypto,assert,v1,flag,print From： https://www.cnblogs.com/mumuhhh/p/18019200