VULNLAB: Flagsalad

from random import randint
from sage.all import Graph, matrix, ZZ, vector
from secret import flag

# evil me strips VL{} from flag :-)
flag = flag[3:-1]

def get_pubkey():
    return matrix(ZZ,len(flag),len(flag), [randint(1,2**32) for i in range(len(flag)**2)])

P = get_pubkey()
while P.is_singular() and P.rank() == len(flag):
    P = get_pubkey()

# flag to vector
v = vector(ZZ,[ord(c) for c in flag])

# make some noise
noise = vector(ZZ, [randint(1,2**24) for i in range(len(flag))])

# foggy flag
C = v * P + noise

print("matrix: ")
for row in P.rows():
    print(str(list(row))+",")
    
print("ciphertext:")
print(list(C))

'''
matrix: 
[1589528698, 3658290945, 465959865, 3006678515, 3385695160, 706648889, 2137329117, 3455194648, 1001573849, 4178032132, 2911836521, 4076674635, 266397451, 1754826113, 2329839172, 3106642459, 1404526993, 1865407304, 3229964068, 1321710159, 1878046068, 4270489870, 1125275417, 594556936, 858116689, 375298168, 4281577574, 3244249726, 3304746049, 3766800903, 3923196879, 3920011068],
[4033088221, 3159849645, 1450186906, 1141586021, 1525256441, 243572694, 3133811004, 1259565902, 631970108, 2106346043, 2482980099, 379713724, 640405265, 241638491, 1146638233, 1921079501, 409951054, 2068481479, 3380963560, 32625560, 272875964, 3572274753, 450664099, 2751110241, 1714549784, 2801657592, 3507977948, 1628635566, 210677247, 4165402567, 50093713, 3061833738],
[3174677095, 3194682820, 536018816, 1476077553, 2970646536, 1670879802, 3803954013, 2537147071, 2165375850, 909770977, 2199672768, 2325768285, 1256828143, 1049171791, 550517661, 869946084, 3043591266, 1649659762, 1248437861, 827832859, 494744281, 3324578594, 1927987730, 1464066752, 2456360492, 1618911554, 1941503172, 2874389968, 1302238637, 1922290321, 253177521, 809132345],
[3774276555, 1313859323, 1599291869, 1745112200, 25265435, 1561094881, 3148911652, 1087185973, 2315041500, 2521648833, 977652951, 3734404429, 1390427189, 4052495825, 707069808, 1875335385, 672935256, 4091420082, 2971097032, 1951162231, 2259994103, 3131063434, 1552949584, 2407858547, 1466201861, 3379398705, 3660127787, 377786731, 983496829, 3430473652, 493056284, 3439520692],
[547873757, 1221883608, 184389781, 3041489890, 4061565080, 325776049, 112503894, 3244035303, 1901028088, 175104020, 1313290038, 1325998796, 2469942811, 1251424792, 1925888722, 2325290739, 4036945605, 755476137, 3209259671, 1389309784, 3885193606, 2046028823, 2155707445, 277499234, 1392950835, 4234089800, 2930778404, 3139040784, 3254876722, 2101555901, 1247856845, 1109392365],
[3076672312, 3089580640, 1260421639, 778272330, 3256389529, 3144036984, 3922659780, 3520501943, 2611502806, 2206768610, 1649817128, 2476063082, 278749927, 2092211119, 1098092824, 1671888633, 502528050, 1107632383, 991606563, 1792075549, 248643293, 399392471, 1143937803, 2591807265, 482288261, 2339449553, 621032229, 2014122064, 3013624632, 1846741273, 2356494899, 947373565],
[746135893, 3526156752, 3813697623, 625817392, 1565483021, 3908000361, 3511610348, 534581172, 2758231579, 3008892982, 75547893, 1178372318, 1469766216, 1055493835, 684788261, 1205471731, 800749608, 3140168745, 749565346, 1871513494, 2584066379, 3486848257, 4217505221, 1473234430, 3649540195, 3517735067, 444892267, 173398414, 1071533312, 943853330, 1171501442, 1096006700],
[1681575225, 3231353794, 1802257751, 3760214610, 3369774043, 1788399051, 1548929661, 2555068330, 2451038530, 746827017, 2487453805, 2880870016, 4061321810, 4212726821, 1174262230, 4218364020, 1734981368, 3485250535, 3100489441, 1168539625, 3830486410, 2941366307, 3939509770, 4055768605, 1278411297, 1878715476, 487883763, 3345731187, 802055997, 310574935, 1420510666, 2717990696],
[3433748105, 3153771502, 803561156, 476915519, 1829218687, 3180008772, 3165476065, 3139787532, 1561127180, 2687107850, 4155982939, 2871079336, 412316763, 4266923533, 1368545666, 2922133400, 3043225326, 1598646432, 31115380, 2911202321, 1296121516, 3596786837, 4029248645, 2262682065, 3005337116, 661450721, 1553917949, 2388745435, 3852189766, 1885282566, 2534013574, 3434191893],
[1828168448, 130342453, 3705142126, 3044756417, 2006998415, 1399902609, 170706978, 384136233, 2714255173, 740576499, 3313989838, 3414755211, 3642793106, 1423464494, 145654750, 4054899430, 1411293507, 589650267, 3976823644, 868457187, 2543125738, 1347086080, 1138468177, 2013018654, 1846787828, 3286097495, 103242198, 165218499, 1178446700, 1072940305, 2213809685, 1509434185],
[2258168369, 2822618804, 1956805924, 3879056456, 3948126697, 1945899331, 746195743, 2140651835, 2210187509, 3785197421, 3426355334, 239407305, 1588544207, 1172457327, 3059334932, 3632495608, 3899577586, 2349695402, 3061856118, 3217222625, 2862747040, 1833134944, 3024355708, 1804822194, 14599889, 649673786, 1491378360, 3612330939, 2875087637, 2337944163, 1621098910, 583848883],
[1294413847, 3011115661, 1015754241, 2918015737, 4267846402, 845160460, 3800532555, 2613557445, 685048974, 458984480, 210415576, 1482748202, 2132555907, 304354955, 3298552298, 922957355, 793589679, 914364912, 3508750806, 1477543318, 2060640522, 3279359514, 652333262, 4209829639, 2693162180, 1160110925, 1554275532, 616573659, 2436564803, 987589393, 2903290842, 3076725903],
[2500038497, 2729000085, 1256882828, 3475656763, 2055247040, 288453436, 2199715555, 3170084195, 1252370145, 1776861634, 2999351543, 4166983190, 4155629870, 3409501518, 3088364110, 3344890124, 3377907792, 4089658173, 3264339117, 2647747365, 2569630199, 831373377, 2041650004, 573509270, 7415387, 1788009251, 1606903863, 3672933326, 537736711, 1876949993, 2640011421, 142051227],
[3311883441, 1619371861, 1168062299, 2819522895, 626038269, 326743505, 341893386, 2549532386, 68002269, 4102197582, 867092675, 1068776694, 976513827, 2482522255, 4108540460, 62650080, 672576830, 783930205, 3378363954, 1042516404, 4069755574, 1464816720, 341695142, 3955262101, 1930069553, 685867380, 4292878417, 2289676228, 186886889, 567885747, 3451654049, 3010649175],
[3635060652, 1868565469, 2070114752, 3750092086, 804040866, 787023595, 283618590, 3000960250, 3636424626, 3649563926, 1926869344, 1872388400, 2201354986, 3716396729, 2769726061, 1000593879, 2664412102, 630962462, 1356763451, 2376615740, 1232816423, 3680425188, 1690114111, 2417916005, 3495129336, 3777100613, 2717476243, 813317476, 3743544790, 3341089724, 1539310028, 2953487563],
[4288430759, 1056369653, 2373386885, 252944714, 145607291, 58286975, 793718009, 4108817082, 130607254, 2679478892, 2024930968, 2066716482, 1473310082, 2380474450, 3140059305, 619860965, 1168043277, 3346722238, 1831995558, 595653252, 755490883, 97066488, 3644695534, 20716503, 754923032, 2220798642, 4198672253, 2543457924, 1444226363, 1173113192, 3374439509, 3236604875],
[1607434579, 2111231345, 3904256974, 234384644, 2387923730, 430355417, 2737826367, 1219652744, 3732863860, 185872473, 2084865490, 1865466468, 2094063476, 3993236314, 3397155469, 2059998795, 3820181585, 2574850882, 3863053476, 105375109, 1888041989, 3688941987, 3798386842, 292523030, 2600512471, 586034742, 4289605742, 900257720, 123814017, 423897659, 3049348375, 1748728022],
[1478842772, 1758268516, 3435895124, 1557777433, 4002521745, 739932034, 651535197, 3310801512, 1019677113, 3573949429, 2720678412, 641856029, 580854537, 101921226, 614647186, 1586759623, 1625804316, 1723955985, 122735068, 1974935426, 2370846550, 3236069632, 2275450716, 1591401291, 3018812524, 3749825463, 634935267, 3340338788, 1762609909, 2627858324, 2312986129, 2285892961],
[1008457024, 743665062, 433837345, 2358457231, 104970833, 4279861335, 4121960428, 4263531440, 3360438183, 250730653, 3651772005, 1712525227, 391196218, 4290657648, 3815719257, 2925891249, 2080155291, 3362059666, 2272689880, 2656454067, 2955256037, 1762845980, 3640362178, 3617337072, 2576401492, 2685174914, 559910135, 1577445100, 3736095377, 1509311725, 2205187553, 1453704569],
[2003288301, 837058557, 2266878114, 811896944, 1639230424, 1456575489, 208659366, 2317417953, 455175932, 1744845314, 4191811896, 2986679203, 612005372, 3586879467, 2777444249, 3693238182, 666415394, 1106534917, 2670991902, 3862627184, 3726619821, 3717063026, 740748794, 67324599, 1723587790, 1235026649, 2894242579, 2176820604, 2700507568, 4290621046, 1924374991, 2845992281],
[2935913956, 1467971551, 1173436189, 2402710058, 1244417500, 2817578042, 2678887540, 3602390394, 4275537882, 3501990520, 3022086869, 1269420066, 2431891829, 415821586, 3996675716, 2462435147, 1837921498, 1002503763, 52199147, 453994266, 2956080817, 911009435, 530078803, 186381459, 2935249201, 3411268117, 3190839548, 817825880, 3221787966, 59952801, 2501155096, 4060762490],
[1996615221, 3072625080, 1377696204, 2197459250, 3443005945, 2257611244, 3191187010, 2278715584, 1594616571, 2420529048, 2515598680, 3609225252, 1897287023, 2387505393, 4144182567, 3587279770, 3592863217, 3178926286, 1541070302, 1579696562, 2264133335, 2881945430, 717278085, 3681027705, 3569037071, 4165188729, 4160282308, 3871218032, 1780261468, 3560779794, 478185093, 3437670645],
[3606254573, 4209521881, 2205331975, 2465028810, 15354462, 1611578496, 1269554179, 3152804899, 1278343411, 2401202089, 458372941, 1198981718, 1496221297, 2879068638, 262779017, 2259360495, 1380669604, 1904315649, 1163377246, 2502111190, 3567577902, 3576615416, 3306058369, 1252914254, 177307472, 3136425488, 3503342376, 4265844539, 1119038140, 1197830050, 2252118565, 838617954],
[1573820363, 1021805252, 2450872443, 3085512201, 1177629905, 1736883761, 3583241063, 2654527169, 752203610, 1819886725, 1307949621, 1407690375, 3728817955, 4274670270, 539210786, 3956547524, 1835141528, 1542233264, 1621089725, 1629511051, 671058573, 3641351145, 819237920, 631386227, 1020571637, 583466485, 1935051031, 1642171939, 3935340030, 565756269, 3959196831, 1584032553],
[3459059551, 4135590961, 677712563, 1625901030, 3399525818, 1611601636, 3601530446, 2637810405, 3068676025, 2934967255, 1957398327, 3795464573, 3180943446, 1183866312, 1388894902, 2373461854, 2675848996, 4097282682, 921060421, 3556908128, 2309479673, 1353740997, 385439181, 306757416, 386340062, 813487581, 1420557446, 341169551, 2022568209, 4292875274, 776277185, 2423113254],
[1901038881, 2292401674, 4004140465, 1835596069, 2820129829, 2789558216, 1748934417, 2504205042, 2405887473, 3762503427, 2131525915, 1206817982, 2217768824, 2158698018, 1273513762, 765128863, 2434644670, 1796411210, 2369212828, 2109294249, 2658542475, 3923288257, 669285174, 1674727208, 2179991406, 1361706807, 2046350949, 2409680759, 1916309392, 2027464119, 1152050861, 2613241455],
[964724342, 3139718682, 2174062982, 1772493433, 2696185206, 3071486511, 4035162606, 3025057100, 2633550077, 3737159528, 1950436296, 29333078, 2533657339, 4053796597, 3641283986, 2776290092, 1339396328, 2368259694, 1132843100, 3847274542, 1804682744, 3537272947, 3070817241, 188775200, 2812979683, 2402506186, 3863121197, 2151880129, 404381690, 3899869214, 3939211540, 3433718795],
[364257008, 3784126475, 3604495481, 427981420, 1393021520, 2995787264, 1038053636, 2053289907, 2446821491, 3256971591, 1193280685, 1720988755, 1629274215, 2516395773, 2436921716, 3857434172, 1661542449, 1529682877, 2331423083, 1687411588, 2974226960, 4191985916, 2545530396, 1398761216, 127223367, 1145121990, 554212492, 2076677108, 1163002396, 252457496, 3821015966, 1010213535],
[3325203717, 1347885601, 755985642, 2619383374, 3881595510, 1484049565, 114243579, 2294049868, 3475639880, 782160678, 1322183369, 2818886019, 2247364737, 2205048818, 2261381223, 1740199878, 477761712, 3402346354, 1560121313, 2295608717, 3949569574, 788696093, 2582803588, 685520144, 3458155792, 3971959142, 3317962004, 3811279451, 2189003448, 1915827816, 159357751, 3938493638],
[1815337677, 142049940, 3197340444, 3395397410, 2830213973, 3026903610, 4027855648, 1420709652, 446406542, 3802942727, 1605366716, 73274478, 4054870615, 3769234387, 1817202130, 1680796849, 438756811, 3270460802, 548153448, 267952172, 2956537426, 828323049, 3524699988, 2357462859, 2751147113, 2860943633, 1898867902, 3922526072, 3381816458, 3959183096, 2148806372, 665265200],
[1148688749, 3776019857, 1753013516, 1970652604, 3252648539, 541139464, 1137778828, 2766589910, 1280413748, 1045997502, 1150910571, 3773906079, 1898799674, 480344113, 445672542, 366912973, 957837557, 3266210628, 2493675955, 1342199261, 992028221, 3686243516, 3787306625, 2156130530, 4263746575, 120133949, 3977931659, 2871566669, 3137208510, 1947881946, 955135595, 3834606505],
[4187704344, 4121737699, 3050101417, 2244348445, 3054742376, 3139404284, 846879203, 1791134809, 455486407, 2013269268, 362730433, 2330297026, 249535202, 3013196254, 4195812949, 3147995133, 740810864, 51535105, 3509725251, 3176327641, 1842710438, 2402452039, 1573911325, 581360276, 2329118287, 3701489351, 2016809146, 2598329143, 3147936593, 2101667841, 714564140, 3221285197],
ciphertext:
[5792131326207, 5923973296972, 4552102343888, 5302047633048, 5679716596137, 4067415449124, 5229549930853, 6411800177527, 4657308665778, 5282686075744, 5027591438914, 5142370490717, 4702323086449, 5965958504632, 5138049658780, 5377748163882, 4555077068732, 5456094564563, 5309660645668, 4264168309426, 5554082917465, 6499059900024, 5517303197517, 4221278853245, 4965465903323, 5357530193909, 6042906158045, 5822884032028, 5144951629734, 5070954658953, 4809207020116, 5757756320758]
'''

import numpy as np

def read_input_file(filename):
    with open(filename, 'r') as f:
        lines = f.readlines()

    # Extract matrix part
    matrix_lines = []
    for line in lines:
        if line.startswith("matrix:"):
            continue
        if line.startswith("ciphertext:"):
            break
        matrix_lines.append(line.strip())

    # Extract ciphertext part
    ciphertext_line = lines[-1].strip()

    # Convert matrix to a 2D list of integers
    matrix = []
    for line in matrix_lines:
        # Remove brackets and split the line by commas
        row = line.strip("[], ").split(",")
        # Convert each element to an integer after stripping spaces
        matrix.append([int(x.strip()) for x in row])

    # Convert ciphertext to a list of integers
    ciphertext = [int(x.strip()) for x in ciphertext_line.strip("[], ").split(",")]

    return np.array(matrix), np.array(ciphertext)


def solve_system(matrix, ciphertext):
    try:
        # Compute the inverse of the matrix
        P_inv = np.linalg.inv(matrix)
        
        # Solve for the flag vector v by multiplying ciphertext by P_inv
        v = np.dot(ciphertext, P_inv)
        
        # Round to nearest integer and convert to characters
        flag = ''.join([chr(int(round(val))) for val in v])
        return flag
    except np.linalg.LinAlgError:
        return "Matrix is singular, cannot solve the system."

def main():
    # Read the matrix and ciphertext from input.txt
    matrix, ciphertext = read_input_file("input.txt")
    
    # Solve the system to find the flag
    flag = solve_system(matrix, ciphertext)
    
    # Output the flag
    print(f"Flag: {flag}")

if __name__ == "__main__":
    main()

$ python3 solve.py
Flag: cbc3e21fc60bc1beb4c298f23d75ccb5