首页
论坛
课程
招聘
KCTF2020秋季赛 第三题 重返地球
2020-11-21 22:16 1104

KCTF2020秋季赛 第三题 重返地球

2020-11-21 22:16
1104

racket-lang写的程序


矩阵乘法 A * flag = b (mod N), 已知A, b, N, 求flag


flag = A_INV * b (mod N)

import numpy as np


def extract(s, start_pattern, end_pattern):
    start_index = s.find(start_pattern)
    if start_index == -1:
        return ''
    start_index += len(start_pattern)
    end_index = s.find(end_pattern, start_index)
    if end_index == -1:
        return ''
    return s[start_index:end_index]


def test1():
    f = open('test.txt')
    codes = f.readlines()
    f.close()
    arys = []
    ary = []
    for code in codes:
        v = extract(code, 'x_list_int_add(', ',')
        if v == '':
            if len(ary) != 0:
                arys.append(ary[::-1])
                ary = []
            continue
        ary.append(int(v))
    if len(ary) != 0:
        print('expected: %s,' % ary[::-1])
    arys = arys[::-1]
    for ary in arys:
        print('%s,' % ary)
    return


def gcd(a, b):
    if b > a:
        return gcd(b, a)
    elif b == 0:
        return 1, 0
    else:
        x, y = gcd(b, a % b)
        return y, x - (a / b) * y


def invert(a, p):
    a = a % p
    _, y = gcd(p, a % p)
    return y % p


def invert_matrix(matrix, q):
    n = len(matrix)
    A = np.matrix(matrix, dtype=long)
    E = np.eye(n, dtype=long)
    A_INV = np.matrix(E, dtype=long)
    for i in range(0, n):
        factor = invert(A[i, i], q)
        A[i] = A[i] * factor % q
        A_INV[i] = A_INV[i] * factor % q
        for j in range(0, n):
            if i != j:
                factor = A[j, i]
                A[j] = (A[j] - factor * A[i]) % q
                A_INV[j] = (A_INV[j] - factor * A_INV[i]) % q
    return A_INV


def test():
    mlen = 37
    modulus = 0x7357
    A = [
        [8868, 27507, 837, 6574, 19663, 5022, 4342, 5870, 18493, 24629, 25037, 23136, 9083, 25019, 6016, 14092, 6087, 16595, 5866, 25081, 1424, 4278, 8757, 1622, 5820, 23433, 11986, 5360, 14046, 16347, 9530, 2868, 27347, 26343, 16727, 12842, 17163],
        [11437, 94, 8725, 14809, 17929, 23145, 7365, 1163, 29286, 14049, 12996, 20829, 13553, 3373, 7693, 17268, 20027, 836, 2425, 15958, 6098, 3731, 24792, 6466, 15614, 12386, 13504, 23924, 8667, 926, 10956, 19610, 19814, 26440, 28065, 18667, 22617],
        [15073, 23809, 16571, 28128, 6133, 5376, 15249, 463, 1664, 20205, 25464, 5950, 28968, 1341, 6327, 16331, 22701, 9208, 10724, 15330, 24534, 3526, 16748, 27383, 9692, 7820, 28649, 20654, 19918, 7057, 8283, 1257, 2664, 29100, 28893, 21774, 4544],
        [17371, 26758, 15913, 4589, 4100, 310, 18513, 11498, 1668, 12494, 18836, 2273, 21025, 4723, 26495, 4651, 24539, 22056, 13212, 4023, 1758, 10610, 9121, 26008, 12888, 17468, 2708, 17173, 23937, 23768, 12254, 2367, 7611, 5833, 3817, 11208, 21069],
        [16424, 24068, 20277, 4486, 2297, 26015, 8313, 13498, 17392, 29305, 105, 6016, 3797, 29242, 19962, 8160, 2666, 6126, 388, 28148, 8708, 7468, 7114, 27296, 18846, 1420, 15833, 24002, 95, 18278, 27070, 11609, 25037, 1041, 2403, 9580, 8852],
        [11323, 27766, 17599, 6362, 19549, 23329, 6441, 23624, 18291, 20181, 942, 19658, 22600, 12659, 25722, 4426, 22652, 22078, 26404, 19514, 5776, 19109, 27948, 746, 13773, 16102, 27583, 11395, 19568, 29268, 27236, 16783, 3848, 12917, 18439, 24655, 2772],
        [24478, 25503, 8740, 13242, 16263, 5291, 25374, 20410, 11015, 15402, 781, 25479, 7602, 23451, 15529, 15566, 17583, 9277, 3753, 9597, 8317, 20942, 26066, 4826, 12266, 2276, 1095, 13707, 14167, 5042, 8676, 5656, 25161, 10613, 19965, 27621, 24030],
        [25425, 18397, 3826, 13390, 13668, 11398, 3535, 11646, 12545, 28009, 7805, 22382, 16004, 2775, 21988, 21160, 10217, 18843, 24010, 14898, 11971, 2620, 16653, 11917, 23625, 22695, 27790, 7196, 11494, 23605, 334, 4629, 23812, 24932, 1553, 24531, 7526],
        [3540, 18642, 22153, 29211, 20694, 5614, 28148, 12872, 2274, 10496, 21966, 5545, 19550, 22983, 25636, 29100, 12008, 26370, 3176, 26801, 26538, 4340, 25580, 22349, 3209, 9885, 10760, 26519, 2949, 26999, 21308, 13042, 29374, 24297, 8112, 21741, 5889],
        [264, 9848, 28659, 6198, 14873, 2284, 17484, 26724, 16386, 18119, 954, 5777, 16681, 6891, 29457, 28853, 10784, 22637, 20874, 18998, 28874, 13444, 2157, 8324, 27108, 491, 16684, 5912, 16419, 5434, 13849, 3837, 25021, 925, 5721, 22805, 9500],
        [28916, 20242, 10854, 8418, 1042, 3104, 19703, 16368, 13247, 11096, 25504, 11823, 27002, 9726, 20532, 20678, 1695, 8540, 1151, 3070, 27875, 17287, 23408, 16937, 24755, 22059, 4712, 11183, 11767, 27846, 5648, 4002, 23918, 26520, 3496, 24298, 3187],
        [8879, 10319, 27196, 10267, 19472, 5773, 3643, 29175, 29103, 12921, 6658, 23129, 737, 769, 1431, 15734, 19541, 24529, 16948, 9591, 20785, 17228, 25813, 21062, 1489, 6208, 25659, 17046, 4564, 26557, 12771, 2061, 16072, 1857, 16579, 15957, 1389],
        [25921, 21849, 3484, 7914, 14585, 22848, 8610, 10907, 24773, 11302, 22067, 1322, 8813, 3592, 23134, 9560, 11685, 13201, 13351, 10447, 4716, 4682, 28532, 6308, 27087, 13834, 17061, 18595, 17894, 9555, 9106, 12255, 3901, 13316, 26928, 9931, 12694],
        [15071, 12729, 23756, 20643, 1330, 4042, 10411, 19749, 19878, 28883, 16302, 20307, 27378, 24015, 19651, 24581, 674, 12338, 19451, 16863, 26549, 18340, 6738, 23138, 14813, 13931, 5652, 14552, 9730, 12526, 13631, 22439, 21033, 14527, 26973, 20021, 29122],
        [13463, 7176, 1943, 17045, 1621, 11445, 1592, 18862, 19234, 27587, 10893, 787, 12663, 5490, 27142, 27067, 8038, 5831, 26615, 3606, 5308, 24441, 20873, 2754, 18625, 1192, 9836, 5050, 9761, 24074, 25183, 29354, 26734, 25734, 6580, 25363, 2736],
        [11176, 21274, 27335, 15686, 16572, 25440, 22541, 17037, 27282, 10245, 2266, 11298, 10727, 13816, 16170, 11990, 8028, 10414, 274, 14058, 10127, 9662, 970, 16510, 23977, 9139, 22014, 5957, 9855, 14853, 15968, 13734, 2646, 4295, 25517, 9022, 3048],
        [25529, 24690, 1534, 4748, 14803, 14038, 3387, 8097, 2906, 9390, 23055, 6049, 340, 15396, 15211, 27823, 8962, 23710, 8383, 8582, 13650, 22620, 14402, 20852, 23550, 18280, 20531, 15123, 20869, 11057, 9746, 5610, 27435, 20684, 2687, 28671, 2967],
        [23549, 2425, 8031, 4335, 960, 22540, 12263, 11724, 27755, 11090, 21276, 13930, 8600, 24577, 9614, 19870, 3365, 10211, 20145, 5317, 22460, 23044, 1601, 1587, 22022, 17933, 20813, 24764, 25314, 14, 13735, 21291, 14162, 26475, 26208, 8523, 15664],
        [18779, 12848, 25825, 25463, 19184, 25559, 9236, 26532, 28809, 19474, 29106, 22181, 22612, 8808, 315, 12180, 710, 6073, 8264, 29447, 3074, 20697, 3798, 8215, 9912, 6080, 27935, 23977, 16531, 737, 23603, 20944, 21674, 13531, 203, 27841, 23855],
        [20869, 26314, 1779, 15165, 5062, 7363, 6640, 16267, 14171, 17002, 14235, 26885, 18002, 2919, 28362, 16299, 25323, 7350, 23060, 17481, 19855, 25200, 25144, 9114, 19111, 5300, 13815, 17645, 5303, 16559, 4144, 17395, 24830, 4693, 23547, 12375, 17661],
        [9844, 25872, 17230, 11957, 13535, 4970, 27231, 8736, 14811, 3626, 29073, 10032, 486, 19444, 2848, 25058, 25037, 3633, 20760, 17037, 4624, 16632, 1704, 29408, 23120, 27692, 6786, 22179, 19786, 23827, 29358, 21675, 9870, 4026, 27773, 8785, 7150],
        [24600, 25842, 14279, 9139, 28421, 20247, 21426, 26474, 9792, 11126, 18173, 26634, 11062, 6953, 26989, 29058, 21866, 20660, 406, 9228, 26495, 13202, 15179, 5571, 13378, 535, 1701, 26354, 20589, 6501, 3136, 20100, 28382, 26439, 524, 110, 20296],
        [9761, 16052, 23264, 11237, 14773, 27774, 3407, 13785, 7803, 2388, 7209, 20090, 16464, 24101, 17372, 27402, 4596, 18161, 18076, 27133, 5140, 28012, 10649, 16506, 7331, 8880, 27380, 9113, 25447, 12995, 9104, 12419, 16940, 25119, 177, 1113, 11391],
        [2559, 4332, 27002, 8621, 21106, 15087, 15597, 11709, 11104, 22580, 25544, 2517, 13456, 2015, 2237, 12824, 24548, 22388, 23662, 14145, 19977, 27026, 11159, 13032, 26368, 21310, 18209, 2196, 18876, 6117, 29173, 19838, 22129, 28523, 23442, 15630, 12176],
        [1190, 22556, 26994, 25490, 4325, 14667, 18046, 29309, 2124, 10207, 750, 15324, 7526, 26218, 3075, 4977, 26494, 26238, 26966, 17061, 29197, 14725, 6776, 21773, 17471, 29171, 16660, 10180, 7580, 13948, 24120, 29109, 7702, 23624, 28609, 9215, 15554],
        [12312, 14533, 10776, 25796, 24553, 26015, 4256, 28679, 26300, 22822, 1782, 11152, 11247, 10340, 26562, 9059, 2212, 26900, 27224, 16113, 1149, 13627, 12655, 9212, 15127, 17287, 18148, 12050, 16467, 27580, 797, 10119, 11141, 20970, 19572, 13555, 2219],
        [24784, 15869, 925, 7451, 21091, 14646, 24489, 24109, 11935, 16444, 378, 279, 11899, 23537, 8425, 16203, 3958, 17255, 16941, 13092, 24635, 12007, 13459, 13144, 7294, 28678, 5168, 24301, 27306, 21132, 22503, 5191, 10286, 9823, 24257, 21934, 1490],
        [13964, 26388, 476, 10540, 1029, 9982, 1507, 10198, 3893, 24072, 14024, 16849, 4717, 19945, 26350, 1316, 4292, 7128, 15206, 19239, 26686, 3803, 240, 9141, 1199, 10404, 5403, 17560, 25980, 21703, 18728, 10961, 21041, 10578, 11678, 17036, 20296],
        [21217, 20067, 10399, 9422, 20885, 12763, 29361, 627, 29189, 9963, 19208, 4543, 4088, 10787, 7240, 23044, 20895, 27831, 27775, 21618, 23686, 26514, 14275, 20332, 4023, 5353, 8078, 24700, 25117, 24065, 6952, 5943, 26211, 18117, 24249, 5156, 4042],
        [7691, 22352, 1348, 1134, 25374, 7581, 29187, 7558, 20519, 20392, 882, 6436, 21139, 27736, 4641, 22170, 11071, 11338, 14536, 3063, 4529, 2855, 2560, 22127, 13781, 4330, 685, 22839, 11100, 21948, 11762, 23219, 27937, 29183, 22644, 473, 19231],
        [28996, 20772, 1370, 19230, 23705, 7535, 11058, 22005, 3412, 4579, 1247, 21666, 12658, 14825, 15081, 5888, 28491, 16111, 24957, 11405, 19376, 11045, 16821, 1651, 1481, 6074, 23330, 1084, 23754, 5567, 7617, 28787, 2809, 21235, 23924, 2080, 26495],
        [1332, 20876, 4290, 26764, 25844, 6223, 561, 17156, 4854, 13834, 4515, 24452, 24642, 267, 20667, 846, 21250, 13739, 22405, 14629, 17058, 955, 9106, 24251, 4425, 25364, 20552, 21135, 24713, 564, 4761, 26657, 3022, 4408, 18475, 2718, 486],
        [100, 11877, 1591, 4100, 8367, 19185, 15264, 19803, 25409, 2678, 10265, 2060, 218, 13689, 7440, 2623, 24798, 4724, 9107, 22596, 6245, 23044, 12447, 28161, 28205, 28758, 7830, 26802, 18532, 16755, 11443, 6812, 11333, 15422, 16627, 21701, 11068],
        [16942, 7876, 1754, 28186, 20850, 11620, 22487, 5712, 9541, 11372, 11475, 17307, 8194, 95, 2947, 18842, 17269, 1980, 13150, 8961, 16668, 26426, 28563, 5459, 11816, 2608, 11031, 16390, 9203, 22074, 2321, 16904, 17301, 9398, 13591, 27762, 133],
        [20279, 21625, 1453, 23170, 10412, 15732, 24271, 20943, 7071, 22433, 22832, 13211, 10370, 17067, 11337, 21495, 16501, 27680, 23516, 29314, 14826, 7924, 17042, 2568, 18948, 25062, 27215, 26910, 9365, 18211, 2049, 5195, 9460, 11254, 24049, 21116, 25095],
        [8934, 28604, 16127, 4052, 16578, 19892, 5427, 4167, 17936, 2901, 18339, 23425, 4715, 20281, 3723, 14519, 7391, 26058, 11447, 5852, 19566, 7614, 1936, 20571, 27320, 7107, 4761, 1651, 5213, 3537, 372, 25250, 12835, 7210, 17221, 10387, 21175],
        [28305, 12613, 4099, 1182, 6987, 16008, 8587, 290, 16153, 14864, 19396, 28349, 24797, 13856, 9804, 12933, 19839, 5090, 10592, 26689, 1276, 11394, 6509, 19986, 6930, 5566, 3731, 19158, 27338, 13883, 734, 15500, 6283, 24155, 13626, 25043, 25998],
    ]
    A_INV = invert_matrix(A, modulus)
    b = [12586, 18694, 13603, 12668, 4893, 23914, 22145, 1555, 11941, 9908, 8859, 25566, 875, 22382, 24919, 5466, 22854, 28102, 21411, 2410, 6660, 6282, 10762, 7204, 16812, 13481, 662, 2176, 7691, 376, 22009, 11830, 4374, 2882, 28701, 8110, 7821]
    flag = ''
    for k in range(mlen):
        v = 0
        for i in range(mlen):
            v += (b[i] * A_INV[k, i])
        v %= modulus
        flag += chr(v)
    print flag
    return


test()



看雪侠者千人榜,看看你上榜了吗?

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回