8abyRSA 题面 from Crypto.Util.number import getPrime, bytes_to_long from LCGRandom import lcg flag = b"DASCTF{xxxx}" m = bytes_to_long(flag) q = getPrime(512) p = getPrime(512) Q = pow(q, 2, p) # Q = q^2 mod p n = p*q e = getPrime(512) c = pow(m, e, n) print('c = ' + str(c)) mul = p n = e c = Q lcg1 = lcg(2023, mul, n, c) print(lcg1.generate(6)) # Data # c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924 # [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168, 464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755] c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924 lcg_gen_6 = [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168, 464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755] seed = 2023 Exploit SageMath’s Code / from sage.all import * import random from Crypto.Util.number import long_to_bytes lcg_gen_6 = [1829291767649461103161355195365566822501625317566021355553611375584303624765389047237072963403651896280059309840080549881138083110457632256619677785411889, 8614784647131959905489143385414473366220060118109917221659356152996027731619256154868253763867569947876938642677951734943013867186530789820165520197525548, 7845112879564311528346861967994968539141359532994486000551038947867807602664345244223622318955917969589790931596150225393028516278795565957075910272882168, 464696663556289552651401659156226806419638205935729756668755007052945250273596319671267391086858010496056118762904740103810918505838370732992982394379753, 6368769952056267497431070536699202267447921981615807369090285698513090854334005214066202915932322373348204466447234330868540529876844912401907159350901200, 4401214958628797991805307100256403706658940216552816808894942142670769563264366171079551655390635613048161714797548328158857275108940238519111063046341755] """ seed = 2023 x = [seed] x = x + lcg_gen_6 """ x = lcg_gen_6 x1 = x[0] x2 = x[1] x3 = x[2] t = [] for i in range(1, len(x)): t.append(x[i] - x[i-1]) # 恢复 Modulus m = 0 for i in range(1, len(t)-1): m = GCD(t[i+1]*t[i-1] - t[i]*t[i], m) print(f'[+] modulus: {m}') n = m # 恢复 Multiplier, Increment (a, b) R = Zmod(n) a = R(x[2] - x[1]) / (x[1] - x[0]) b = R(x[1] - a * x[0]) print(f'[+] a = {a}\n[+] b = {b}') # 也许参数位置不对 p = ZZ(a) e = ZZ(b) Q = ZZ(n) # Q \equiv q^2 \pmod{p} # 求二次剩余, 返回空, 大概率位置错了 # [] # check location print(f'[*] Parameters location check:\t{is_prime(p)} {is_prime(e)} {is_prime(Q)}') # 1 0 1 # p, q, e 均为 512-bits 素数, 而上面第二个返回值为 False, 则说明位置错了 Q, e = e, Q # 判二次剩余 if not legendre_symbol(Q, p) == 1: print('[-] No solution') else: print('[+] Found solution') # Solution quadratic residue # Modulus is prime, So # Cipolla Algorithm class CipollaAlgorithm: def __init__(self, p): self.p = p # 模数p def mul(self, a, b, w): # 复数乘法 x = (a[0] * b[0] + a[1] * b[1] * w) % self.p y = (a[0] * b[1] + a[1] * b[0]) % self.p return (x, y) def qpow_r(self, a, b): # 实数快速幂 res = 1 while b: if b & 1: res = res * a % self.p a = a * a % self.p b >>= 1 return res def qpow_i(self, a, b, w): # 复数快速幂 res = (1, 0) while b: if b & 1: res = self.mul(res, a, w) a = self.mul(a, a, w) b >>= 1 return res[0] def cipolla(self, n): n %= self.p if self.qpow_r(n, (self.p - 1) // 2) == self.p - 1: return -1 # 没有解 while True: a = random.randint(0, self.p-1) w = (a*a - n) % self.p if self.qpow_r(w, (self.p - 1) // 2) == self.p - 1: break x = (a, 1) return self.qpow_i(x, (self.p + 1) // 2, w) # Q = q^2 mod p p = p n = Q cipolla = CipollaAlgorithm(p) ans1 = cipolla.cipolla(n) ans2 = (-ans1) % p ans = [] if ans1 == -1: print("[-] No solution") else: if ans1 > ans2: ans1, ans2 = ans2, ans1 if ans1 == ans2: ans.append(ans1) else: ans.append(ans1) ans.append(ans2) # check prime for i in ans: if not is_prime(i): # print(f'[-] {i} is not prime') pass else: q = i print(f'[+] {i} is prime') print('[*] DONE Quadratic Residue') phi = (p - 1) * (q - 1) d = inverse_mod(e, phi) c = 14968774972802568447907734980942381885170753466134942777553237930032293557412276601708303806296932877792965437305452274767013479132983066980557420348521340748653518789837988349171582558831336243036976332252071289409948879158346086243451785505819420501498240344839999096449458990633841326838003742773196414924 m = pow(c, d, p * q) print(f'[*] 全因子解密: \n{long_to_bytes(m)}') # uuid 长 42 bytes # DASCTF{} 长 8 bytes # 50 * 8 = 400 bits < 512 bits # 单因子解密 phi = p - 1 d = inverse_mod(e, phi) m = power_mod(c, d, p) print(f'[*] 单因子解密: \n{long_to_bytes(m)}') """ inva = inverse(a, n) x1 = x[0] for i in range(300): x1 = (x1 - b) * inva % n try: flag = long_to_bytes(x1) if b'flag{' in flag: print(flag) except Exception as err: print(err) continue """

Hill Cipher(不知道题目叫什么名字) 下载题目附件后打开看到 / 拖到 010 Editor 提示报错，注意到文件末尾存在字符串，且为三的倍数 / 同时结合图片名为 hill.png 以及图片中数字的排列，推导可能是 Hill Cipher

Crypto easyLCG 题目代码 from Crypto.Util.number import * from random import randint FLAG = ? ROUND = randint(200, 300) class LCG: lcg_a = getPrime(498) lcg_b = getPrime(498) lcg_n = getPrime(512) def __init__(self, lcg_seed): self.state = lcg_seed def next(self): self.state = (self.state * self.lcg_a + self.lcg_b) % self.lcg_n return self.state seed = bytes_to_long(FLAG) print(seed.bit_length()) lcg = LCG(seed) for _ in range(ROUND-6): lcg.next() print([lcg.next() for _ in range(6)]) # 351 # [2485483242304449696161151168576736302336140244327446722677621064961717587947642623655706309294371876714311165214262071924932913930440142186509325733360885, 6174672247406972581092780254648964828729162316422924118545162215261641830776919624579500836375440017861960302702691972683448546062254126073514097080361044, 4584872703321313263026316988830140564935997972340636369234263637913498924218112980629201945528119162637762726584003527994733552009906632734086040880127542, 4829175497283310360340169484343201154685159906303099960915060755507745973302279262836696523131741537828200567942990339422885197644614494869008027862313162, 6669041483112643196441450289748743294802963984583343809912658359929976814854869038886397237458253328867571805574485994275429182399171275201561798677581761, 2732859498560958306654933055106793656103744294844703560692860713169132266734427400301681246251133210447387861776419850678194913478737337289544516324708390] 思路 比较基础的参数恢复后逆推 seed / flag 是初始 seed 的 bytes 形式, 且 seed 的 bit 长度为 $351$

初赛密码题只有一道，还沾了点猜谜… / 绝密文件-代号P 题目代码 import cv2 import numpy as np from Crypto.Util.number import * from secret import p, q, c def arnold(img, shuffle_times, a, b): r, c, d = img.shape # d: dimension p = np.zeros(img.shape, np.uint8) # new image for s in range(shuffle_times): # shuffle times for i in range(r): # height for j in range(c): # width x = (i + b * j) % r # new position y = ((a * i) + (a * b + 1) * j) % c # new position p[x, y, :] = img[i, j, :] img = np.copy(p) return p Img_path = "flag_test.png" Img = cv2.imread(Img_path) assert isPrime(p) and isPrime(q) and p**2 + \ q**2 == c and c == 179093209181929149953346613617854206675976823277412565868079070299728290913658 Img_arnold = arnold(Img, c, p, q) cv2.imwrite("flag_enc.png", Img_arnold) 思路 分析得知 arnold()管理图片像素置换，而参数 $a,b$ 未知

部分位已知 通过分析题目附件中的代码发现：素数总是隐藏了 50%bit，反过来就是 50%bit 已知 / DFS + 枚举状态 + 通过 $N$ 的低部分位来 Check 枚举的 $p,q$ 低位是否准确即可解出 $p,q$ / 随后即为常规 RSA

RSA是什么 特征：给出 p、q，考察 RSA 解密原理 SageMath’s Code / from Crypto.Util.number import long_to_bytes p = q = phi = (p - 1) * (q - 1) n = p * q e = d = inverse_mod(e, phi) m = power_mod(c, d, n) print(long_to_bytes(int(m))) # 强制类型转换 RSA $e=3$ 特征：$e$ (公钥指数) 很小 from gmpy2 import iroot import itertools n = e = 3 c = """ m = iroot(c, e) if m[1]: print(long_to_bytes(m[0])) """ for i in itertools.count(0): m = iroot(c + i * n, e) if m[1]: print(long_to_bytes(m[0])) break RSA 因数分解 特征：$N$ 的因子很小 这里为 ($80\text{bit} * 80\text{bit}$)

Bada Points: 90 / Solve: 51 / Difficulty: Medium 🤔 / 题面 Bada The Bada equation contains an undetermined function. By closely examining how this equation behaves, you may be able to discover the concealed flag. / nc 00.cr.yp.toc.tf 17113 Note: There is no file to download in this challenge! / 尝试交互 > nc 00.cr.yp.toc.tf 17113 ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓ ┃ Hey! It's time to solve the equation of a function f: N x N -> Z. ┃ ┃ Function f has given certain conditions. In each step, solve the ┃ ┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) = ┃ ┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'. ┃ ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛ ┃ We know: f(1, 1) = -444045537086 and f(x, y) = 202500187503 ┃ Please send x, y separated by comma: 概述 通过将 $f(x, y) - f(1, 1) = n$ 转换成一个因式分解的问题，然后用这种分解来求解 $x$ 和 $y$ 的值。可以有效利用 $n$ 的因子来找到可能的 $x$ 和 $y$

*S𝑪𝑷-0εε 4 solved / 题面 ANY NON-AUTHORIZED PERSONNEL ACCESSING THIS FILE WILL BE IMMEDIATELY TERMINATED THROUGH BERRYMAN-LANGFORD MEMETIC KILL AGENT. / Download Attachment / 关键词 猜谜 + 未知位数约到Coppersmith界内 / Idea 打开附件中的 PDF / 和题目关联度不是很大的信息：SCP-033 / 发现有四行代码

题面 from Crypto.Util.number import long_to_bytes, bytes_to_long from Crypto.Cipher import AES from Crypto.Util import Counter from hashlib import sha256 import os # from secret import flag flag = b'flag{test}' def padding(msg): return msg + os.urandom(16 - len(msg) % 16) # 随机值填充 msg = b"where is the flag? Key in my Heart/Counter!!!!" key = b"I w0nder how????" assert len(msg) == 46 assert len(key) == 16 enc_key = os.urandom(16) # 随机key initial_value = bytes_to_long(enc_key) # key转为整数 hash = sha256(str(initial_value).encode()).hexdigest() # 字符串(key) 的 sha256 aes = AES.new(enc_key,AES.MODE_ECB) enc_flag = aes.encrypt(padding(flag)) # 16 * 8 = 128, # {'counter_len': 16, 'prefix': b'', 'suffix': b'', 'initial_value': 1, 'little_endian': False} ctr = Counter.new(AES.block_size * 8, initial_value = initial_value) # print(ctr) aes = AES.new(key, counter = ctr, mode = AES.MODE_CTR) # key 已知, 推 counter, CTR mode 不需要 padding enc = aes.encrypt(msg) # msg 已知 # print("enc = {}".format(len(enc))) # 46 print("enc = {}".format(enc[-16:])) # 密文的最后16位, 但并不是最后一个 block print("enc_flag = {}".format(enc_flag)) print("hash = {}".format(hash)) Data enc_last16 = b'\xbe\x9bd\xc6\xd4=\x8c\xe4\x95bi\xbc\xe01\x0e\xb8' enc_flag = b'\xb2\x97\x83\x1dB\x13\x9b\xc2\x97\x9a\xa6+M\x19\xd74\xd2-\xc0\xb6\xba\xe8ZE\x0b:\x14\xed\xec!\xa1\x92\xdfZ\xb0\xbd\xb4M\xb1\x14\xea\xd8\xee\xbf\x83\x16g\xfa' hash = 'efb07225b3f1993113e104757210261083c79de50f577b3f0564368ee7b25eeb' Solution # Reference: # https://wumansgy.github.io/2018/11/03/AES%E7%9A%84CTR%E6%A8%A1%E5%BC%8F%E5%8A%A0%E5%AF%86%E8%A7%A3%E5%AF%86%E8%AF%A6%E8%A7%A3/ # https://blog.csdn.net/XiongSiqi_blog/article/details/131931066 from Crypto.Util.number import long_to_bytes, bytes_to_long from Crypto.Cipher import AES from Crypto.Util import Counter from hashlib import sha256 import os # from secret import flag flag = b'flag{test}' def padding(msg): return msg + os.urandom(16 - len(msg) % 16) # 随机值填充 msg = b"where is the flag? Key in my Heart/Counter!!!!" key = b"I w0nder how????" assert len(msg) == 46 assert len(key) == 16 enc_key = os.urandom(16) # 随机key initial_value = bytes_to_long(enc_key) # key转为整数 hash = sha256(str(initial_value).encode()).hexdigest() # 字符串(key) 的 sha256 aes = AES.new(enc_key,AES.MODE_ECB) enc_flag = aes.encrypt(padding(flag)) # 16 * 8 = 128, # {'counter_len': 16, 'prefix': b'', 'suffix': b'', 'initial_value': 1, 'little_endian': False} ctr = Counter.new(AES.block_size * 8, initial_value = initial_value) print(ctr) aes = AES.new(key, counter = ctr, mode = AES.MODE_CTR) # key 已知, 推 counter, CTR mode 不需要 padding enc = aes.encrypt(msg) # msg 已知 # print("enc = {}".format(len(enc))) # 46 print("enc = {}".format(enc[-16:])) # 密文的最后16位, 但并不是最后一个 block print("enc_flag = {}".format(enc_flag)) print("hash = {}".format(hash)) print('题目数据输出结束' + ' *' * 16) # Data enc_last16 = b'\xbe\x9bd\xc6\xd4=\x8c\xe4\x95bi\xbc\xe01\x0e\xb8' enc_flag = b'\xb2\x97\x83\x1dB\x13\x9b\xc2\x97\x9a\xa6+M\x19\xd74\xd2-\xc0\xb6\xba\xe8ZE\x0b:\x14\xed\xec!\xa1\x92\xdfZ\xb0\xbd\xb4M\xb1\x14\xea\xd8\xee\xbf\x83\x16g\xfa' hash = 'efb07225b3f1993113e104757210261083c79de50f577b3f0564368ee7b25eeb' # Solution # a = msg[32:] # 从明文index 32 开始 a = msg[16 * (len(msg) // 16):] # 取最后一个 block b = enc_last16[16 - (len(enc) % 16):] # 从密文index 2 开始 | 选最后一个 block # 加密最后步骤 明文 xor enc_{key}(counter) = 密文 # 解密最后步骤 enc_{key}(counter) xor 密文 = 明文 | enc_{key}(counter) = 密文 xor 明文 enc_Counter1 = bytes(a[i] ^ b[i] for i in range(14)) for i in range(0xff): for j in range(0xff): # ECB mode 要求数据长度与块长对齐, 而加密后的数据的最后 2 bytes 我们并不清楚, 所以我们需要尝试所有的可能 enc_Counter2 = enc_Counter1 + bytes([i]) + bytes([j]) aes = AES.new(key,AES.MODE_ECB) Counter = aes.decrypt(enc_Counter2) # E_{key}(Counter) = Counter_enc | Counter = D_{key}(Counter_enc) initial_value = bytes_to_long(Counter) - (len(msg) // 16) # 经历两个 block, 最后一个 block 的 Counter - block 数 = 初始值 if hash == sha256(str(initial_value).encode()).hexdigest(): # type: str print(f'found {initial_value = }') enc_key = long_to_bytes(initial_value) aes = AES.new(enc_key,AES.MODE_ECB) flag = aes.decrypt(enc_flag) print(flag) break # flag{9b1deb4d-3b7d-4bad-9bdd-2b0d7b3dcb6d}

[鹤城杯 2021]BabyRSA 题面 # [鹤城杯 2021]BabyRSA from Crypto.Util.number import getPrime, bytes_to_long # from secret import flag flag = b'flag{test}' p = getPrime(1024) q = getPrime(1024) n = p * q e = 65537 hint1 = p >> 724 # msb 1024 - 724 hint2 = q % (2 ** 265) # lsb 265 ct = pow(bytes_to_long(flag), e, n) print(hint1) print(hint2) print(n) print(ct) # Data hint1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479 hint2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623 n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969 ct = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188 Idea Reference: 鹤城杯2021 Crypto Writes up / 我的推导 [公式]