1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| # Define p and c_list (ensure full c list is used)
p = 94951668914836210059795315483536443488933021611300220555898947046010704751659
c_list = [
8035334017032303676884495695093849049591116586402215453176893169647528573473, 59633132506897001337475181076769716084659260056174745705282228861660454585844,
28162843329479433477265065446992147859471233196414186246357440403309160334499, 4299109678466131600343618060605648056113232607349218027650135505549407963910,
4087741063724374061725013462278085730705718667489149938923893312651486614669, 73854298568255274991238074779725329201544960932611944103367706659761710498656,
71229461213142919346904865844975917255119439992501630368712083457562572987703, 16114686718014289723082144014633157871938855520267677347584656837586670455351,
33815553137609375986764941536846486955311356747431282265813722199746367730735, 83230726604103337485693252608736987952116487439584868153421572585765208737752,
43354624060867962612688844511954799809306957508254538657246407957691125473891, 55101837278890697174045987723057079542992530782626626822696566148569826190699,
62604177849321207690994918211253550152229643480313270600641056287690505746500, 55392545954254989540181949652718594327551409387597584348155637070136573822824,
28077377409202524772685778716251907003804101264114658216348829339456013295161, 21334443181285981988980698630756886134980141537264094330711028083765063415519,
86527877688353267156038544409564951171579421083230184768315012173819906199896, 65794756895324638675873258762812358451842848189145910550661817702224116966369,
22957500705937080580790222196044227350593392941014901984708370379340604555411, 55977668885664502413144853336297159131177754737530642324233093247568745687864,
93062235767859648250412725812749448881541642649971084665181528969581777561465, 30474926227967272254439075001191161577976221357861668422513122909667896147233,
60775836432659248756300048642443361744048616393839129752849968709547592033670, 71214544835243381339076088571162567904668832029672120026798494828609569503119,
1174815806395901492096195189104319047839644470732310954592448712895225126130, 25608109273384978479485966037827618297462947734861101290796152980521502852654,
84310874165903335358606830377169502406570533488803476591113974411344926639939, 24825972828150211947708356276934254637682047694949045115854000286055596575358,
77671717686612226841883804936168777380412228821522967173353349296517170636360, 69846508771180325151756459684876846450893191201713121999727511653375604855218,
8987813778406417907094761426890842138014909328197870288562454428726660271907, 30440204987717603713083763738703598556857003088625013718943318268794375542978,
19521407840482588407487908680073693029442255108207197779397873576957114219574, 53017306130976718162852673259699032134557815647762813929925333742376644678749,
15774515989940084946089586257040469965291992992385643947928102390855958180000
]
# Ensure c is a SageMath vector
c = vector(Zmod(p), c_list)
n = len(c)
# Convert c components to SageMath integer type ZZ
c_int = [ZZ(x) for x in c]
# Construct the lattice basis matrix M
M = Matrix(ZZ, n + 1, n)
for i in range(n):
M[i, i] = p
for i in range(n):
M[n, i] = c_int[i]
print("Matrix M constructed. Running LLL...")
# Run LLL
B = M.LLL()
print("LLL computation finished.")
# print("Reduced Basis B (first few rows):") # Optional: print basis if needed
# print(B.nrows())
# for i in range(min(5, B.nrows())): # Print first 5 rows or fewer
# print(f"B[{i}]: {B[i]}")
# --- Try to find the correct vector ---
target_vec = None
if B[0].is_zero():
print("B[0] is the zero vector. Trying B[1]...")
if B.nrows() > 1 and not B[1].is_zero():
target_vec = B[1]
print("Using B[1] as the target vector.")
else:
print("B[1] is also zero or does not exist. Cannot proceed.")
else:
# Check if B[0] magnitude seems reasonable (heuristic)
# A very small norm might indicate the zero vector or an issue.
# Check nbits of the first component as a rough proxy for size.
if abs(B[0][0]).nbits() > 100: # Expect components ~135 bits
target_vec = B[0]
print("Using B[0] as the target vector.")
else:
print(f"B[0] seems potentially too small (first component has {abs(B[0][0]).nbits()} bits). Checking B[1]...")
if B.nrows() > 1 and not B[1].is_zero() and abs(B[1][0]).nbits() > 100:
target_vec = B[1]
print("Using B[1] as the target vector.")
else:
print("B[1] is also zero, too small, or doesn't exist. Defaulting back to B[0] or stopping.")
# Decide whether to proceed with B[0] or stop if both seem wrong
if not B[0].is_zero():
print("Proceeding with potentially small B[0].")
target_vec = B[0]
else:
print("Both B[0] and B[1] seem problematic. Stopping.")
target_vec = None # Ensure we don't proceed
if target_vec is None:
print("Could not identify a suitable short vector from LLL basis.")
else:
# print(f"Using vector: {target_vec}") # Optional: print the vector being used
flag = ""
print("Attempting to recover flag from the selected vector...")
found_flag = True
possible_chars = list(range(32, 127)) # ASCII printable range
for i, val in enumerate(target_vec): # Use enumerate to get index if needed
abs_val = abs(ZZ(val))
if abs_val == 0:
print(f"Error: Component {i} is zero.")
flag += "?"
found_char = False # Maintain consistency
found_flag = False # Mark overall flag recovery as failed
continue # Skip to the next component
found_char = False
for char_code in possible_chars:
if abs_val % char_code == 0:
potential_prime = abs_val // char_code
# Check if quotient is non-zero and prime
# Add bit size check for robustness
if potential_prime != 0 and potential_prime.is_prime() and 120 < potential_prime.nbits() < 140:
flag += chr(char_code)
found_char = True
break # Found the correct factor
if not found_char:
# If no factor is found, print more info
print(f"Error: Could not find valid character factor for value {abs_val} (nbits: {abs_val.nbits()}) at index {i}")
flag += "?"
found_flag = False
# Print final result
if found_flag:
print("\nSuccessfully recovered flag:")
print(flag)
else:
print("\nCould not recover the full flag. Partial result:")
print(flag)
|