lattice_oracle
问题：
data文件：
{"n": 6,"q": 97,"m": 30,"A": [[94,13,86,94,69,11],[54,4,3,11,27,29],[77,3,71,25,91,83],[69,53,28,57,75,35],[20,89,54,43,35,19],[43,13,11,48,12,45],[77,33,5,93,58,68],[48,10,70,37,80,79],[73,24,90,8,5,84],[37,10,29,12,48,35],[81,46,20,47,45,26],[34,89,87,82,9,77],[21,68,93,31,20,59],[34,81,88,71,28,87],[7,29,4,40,51,34],[27,72,91,40,27,83],[50,82,58,18,33,17],[95,71,68,33,95,74],[74,51,46,28,17,65],[11,96,6,14,19,80],[87,54,76,8,49,48],[59,67,32,70,1,87],[14,87,68,96,34,82],[14,37,55,20,58,0],[92,33,64,22,64,13],[38,81,64,77,25,19],[20,69,67,0,76,41],[2,14,46,39,30,7],[72,10,10,93,62,8],[16,16,84,60,70,21]],"b": [56,74,51,28,10,30,34,45,82,56,62,52,5,71,35,41,86,47,8,27,64,29,57,92,34,55,57,70,87,28],"iv": "bcdad772f7a0ec967887f7b8f36234c8","enc": "00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc" }
问题代码：
from Crypto.Cipher import AES import hashlib, os, json, randomflag = b"?"n = 6 q = 97 m = 30s = [random.randint(0, 3) for _ in range(n)]A = [] b = [] for _ in range(m):a_i = [random.randint(0, q - 1) for _ in range(n)]e_i = random.randint(-1, 1)b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % qA.append(a_i)b.append(b_i)key = hashlib.sha256(str(s).encode()).digest()[:16] iv = os.urandom(16) pad_len = 16 - len(flag) % 16 enc = AES.new(key, AES.MODE_CBC, iv).encrypt(flag + bytes([pad_len]) * pad_len)print(f"n = {n}") print(f"q = {q}") print(f"m = {m}") print(f"A = {A}") print(f"b = {b}") print(f"iv = '{iv.hex()}'") print(f"enc = '{enc.hex()}'")""" n = 6 q = 97 m = 30 A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]] b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28] iv = 'bcdad772f7a0ec967887f7b8f36234c8' enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc' """
解题代码：
题目给出了n=6, q=97, m=30, A和b，以及iv和enc。秘密向量s每个分量在0-3之间，共4^6=4096种可能。对于每个候选s，计算每个方程的误差e_i = b_i - dot(A_i, s) mod q，但需注意模q后，误差应在[-1,0,1]范围内（实际因为e_i随机取-1,0,1，且b_i = (dot + e_i) mod q，所以计算差值后应落在{0, q-1, q-2} 注意模运算：若dot + e_i在[0,q-1]内，则b_i = dot+e_i；若为负数，则加q。所以实际误差e_i = (b_i - dot) mod q，结果应为0, 1, 或q-1（对应-1）。因此检查条件：e_i == 0 or e_i == 1 or e_i == q-1。找到唯一s后，计算key值，然后用AES CBC解密得到flag.
from Crypto.Cipher import AES import hashlibn = 6 q = 97 m = 30 A = [[94,13,86,94,69,11],[54,4,3,11,27,29],[77,3,71,25,91,83],[69,53,28,57,75,35],[20,89,54,43,35,19],[43,13,11,48,12,45],[77,33,5,93,58,68],[48,10,70,37,80,79],[73,24,90,8,5,84],[37,10,29,12,48,35],[81,46,20,47,45,26],[34,89,87,82,9,77],[21,68,93,31,20,59],[34,81,88,71,28,87],[77,29,4,40,51,34],[27,72,91,40,27,83],[50,82,58,18,33,17],[95,71,68,33,95,74],[74,51,46,28,17,65],[11,96,6,14,19,80],[87,54,76,8,49,48],[59,67,32,70,1,87],[14,87,68,96,34,82],[14,37,55,20,58,0],[92,33,64,22,64,13],[38,81,64,77,25,19],[20,69,67,0,76,41],[2,14,46,39,30,7],[72,10,10,93,62,8],[16,16,84,60,70,21]] b = [56,74,51,28,10,30,34,45,82,56,62,52,5,71,35,41,86,47,8,27,64,29,57,92,34,55,57,70,87,28] iv = bytes.fromhex('bcdad772f7a0ec967887f7b8f36234c8') enc = bytes.fromhex('00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc')# 枚举所有可能的s (每个分量0-3) from itertools import product candidates = [] for s in product(range(4), repeat=n):valid = Truefor i in range(m):dot = sum(A[i][j] * s[j] for j in range(n)) % qe = (b[i] - dot) % qif e not in (0, 1, q-1):valid = Falsebreakif valid:candidates.append(s) print("Found candidates:", candidates)s = candidates[0] key = hashlib.sha256(str(list(s)).encode()).digest()[:16] cipher = AES.new(key, AES.MODE_CBC, iv) flag = cipher.decrypt(enc) pad_len = flag[-1] if pad_len <= 16:flag = flag[:-pad_len] print(flag.decode())
three_friends
问题：
from Crypto.Util.number import *flag = b"***********"L = len(flag) m1 = bytes_to_long(flag[:L//3]) m2 = bytes_to_long(flag[L//3:2*L//3]) m3 = bytes_to_long(flag[2*L//3:])p = getPrime(512) q = getPrime(512) r = getPrime(512)e = 65537n1 = p * q n2 = q * r n3 = p * rc1 = pow(m1, e, n1) c2 = pow(m2, e, n2) c3 = pow(m3, e, n3)print(f"n1 = {n1}") print(f"n2 = {n2}") print(f"n3 = {n3}") print(f"e = {e}") print(f"c1 = {c1}") print(f"c2 = {c2}") print(f"c3 = {c3}")""" n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e = 65537 c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002 """
解题代码：
RSA多素数问题：三个模数n1=p*q, n2=q*r, n3=p*r。已知n1, n2, n3, e, c1, c2, c3。我们需要恢复flag。flag被分成三部分m1, m2, m3，分别加密。由于我们知道n1, n2, n3，我们可以通过gcd(n1, n2)得到q，然后p = n1//q，r = n2//q。然后解每个密文得到m1, m2, m3。但注意m1, m2, m3是flag的一部分，可能长度不是正好整除，但这里使用了L//3分片，所以每个部分长度大致相等。我们需要将三个数字转换为字节并拼接得到flag。
from Crypto.Util.number import long_to_bytes from math import gcdn1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829 n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989 n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401 e = 65537 c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413 c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792 c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002# 1. 通过 gcd 恢复公共质因数 q = gcd(n1, n2) # n1 = p*q, n2 = q*r p = n1 // q r = n2 // q# 验证 n3 assert n3 == p * r, "n3 与 p*r 不匹配"# 2. 计算每个模数的欧拉函数值，并求私钥 d phi1 = (p-1)*(q-1) d1 = pow(e, -1, phi1) m1 = pow(c1, d1, n1)phi2 = (q-1)*(r-1) d2 = pow(e, -1, phi2) m2 = pow(c2, d2, n2)phi3 = (p-1)*(r-1) d3 = pow(e, -1, phi3) m3 = pow(c3, d3, n3)# 3. 将整数转为字节串并拼接 flag = long_to_bytes(m1) + long_to_bytes(m2) + long_to_bytes(m3) print(flag.decode())