首页
论坛
课程
招聘
[原创]2020KCTF重返地球writeup
2020-11-22 13:17 1372

[原创]2020KCTF重返地球writeup

2020-11-22 13:17
1372

分析

  • 丢到ida里面分析 发现会把输入的字符 放到一个链表里 然后会进入一个类似虚拟机的指令分发流程

  • 第一个是统计链表长度 如果链表长度为37则进入下面流程

  • 然后是一大堆数据的初始化 生成了37+1个链表 然后 进入指令分发流程 得出一个新的链表后 跟 最后一个链表对比

  • 跟踪流程 得出流程为

    (mat[1][1]*x[1] + mat[1][2]*x[2] + … + mat[1][n]*x[n]) % MOD =mat[1][n+1]

  • 乘法由加法完成 求模 为减法实现 所以在指令分发流程里面 没有发现 乘法跟除法 的指令码

  • 总结为37元一次模方程求解 百度了下 发现有在ACM中考察过 编号为 poj2947

  • 使用高斯消元法 进行求解 把系数扣下来以后 构建一个martix 因为链表为倒序 所以最后打印flag时候要倒序打印

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

    最后得出flag为KCTF{r4Ck3t_M4tr|X_W1tH_CP5_YqBHxjWX}

代码参考

 

https://blog.csdn.net/acm_code/article/details/43271603?utm_medium=distribute.wap_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.wap_blog_relevant_pic&depth_1-utm_source=distribute.wap_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.wap_blog_relevant_pic


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

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