# Cryptography
ChallengeLink
Baby RSA (100 pts)Here
Learning but Errors (410 pts)Here
## Baby RSA (100 pts) ### Solution Diberikan source code sebagai berikut ```python from Crypto.Util.number import * def gen_key(): while True: p = getPrime(1024) q = 2 * p + 1 if isPrime(q): break return p * q n = gen_key() e = 65537 flag = open("flag.txt", "rb").read() m = bytes_to_long(flag) c = pow(m, e, n) print("n = ", n) print("e = ", e) print("c = ", c) ``` Karena equationnya simple, kita bisa gunakan fungsi solve pada sage untuk mendapatkan nilai p ```python from Crypto.Util.number import * n = 29237198406447781840629726127809047660383994335982924017224165828947709888758817269330403616908753186654631934499630618269567226674757132570007351085595605345287089516753763258487567739997507428518364754926023428870567365087983926359766808760651362733024484642642130442198490208916336961141986329674270074758077168615387351540496624245321855451332339081859238865571419260611470144444333460718577949627290874422401816829724442862220140607155250782464921851735879929393939033223725572127225448491536267521471036484319582454901570581439471387728922421052405132489464009444709947629676451887119970077229329137396371678153 e = 65537 c = 5357624642921225510304458214528110256781731158227005082138032795561958182784301019426489867607735126321049257926005082018017602782337781933985047030746809420950408100455448858496355250905325511372799862570809648366646065545306516572963278402972088299653531841551844930909269487873647292645080007960390236241418753964802497472465043345321046531697603479418903526906298436978891764524534146121421596169306822115179183159612811336551281527383679899544897495492459540772355788065265764607837907724998656439578091932254136971737995959215027303360158145506983463331869617633351834924037983664699792872702481075229826916574 p = var('p') q = 2 * p + 1 eq = solve(p * q == n , p) sol = [i.rhs() for i in eq] p = int(sol[0]) q = n//p phi = (p-1)*(q-1) d = pow(e, -1, phi) print(long_to_bytes(pow(c, d, n))) ```
Flag: CBC2024{is\_the\_safe\_prime\_in\_the\_room\_with\_us?} ## Learning but Errors (410 pts) ### Solution Diberikan source code sebagai berikut ```python from Crypto.Util.number import * def gen_matrix(n): matrix = [] for i in range(n): matrix.append([getRandomInteger(16) for _ in range(n)]) return matrix def encrypt(m, A): c = [0] * len(m) for i in range(len(A)): e = getPrime(16) for j in range(len(A[i])): c[i] += A[i][j] * m[j] * e return c flag = open("flag.txt", "r").read() msg = [ord(c) for c in flag] A = gen_matrix(len(msg)) c = encrypt(msg, A) print("A = ", A) print("c = ", c) ``` Kode diatas jika hanya c\[i] += A\[i]\[j] \* m\[j] maka merupakan matrix multiplication. Namun karena terdapat noise yaitu \*e untuk setiap index i maka bukan hanya perkalian matrix namun terdapat perubahan di nilai akhirnya yaitu dikali dengan e. Atau bisa kita tuliskan ```python A = matrix axb m = matrix cxd c = mxA c[i] *= e[i] for i in range(len(c)) ``` Jadi kalau kita bisa mendapatkan nilai e untuk setiap index i maka kita bisa lakukan multiplication inverse seperti biasa. Disini kita tahu bahwa nilai e adalah prima dengan panjang bit 16, idenya adalah melakukan faktorisasi prima untuk semua nilai c dan memfilter hanya yang 16 bit saja untuk menjadi kemungkinan nilai e. Karena setelah dicoba pada c di soal jumlahnya sangat sedikit (mayoritas hanya ada 1 nilai prima 16 bit untuk setiap index di c) maka kita bisa lakukan semua kemungkinan yang ada untuk masing-masing kemungkinan e pada setiap index. Jadi flownya adalah melakukan brute untuk kemungkinan e dimana e\[i] sebagai pembagi untuk c\[i] lalu tinggal multiplication inverse pada matrix. Berikut solver yang saya gunakan ```python from itertools import * def get_factor(ct): tmp = factor(ct) factors = [p for p, _ in tmp] return factors A = [[5560, 30066, 61188, 8483, 22274, 17247, 57790, 5228, 43046, 3831, 7639, 4673, 42809, 10349, 44247, 28238, 37662, 48753, 35156, 32850, 61370, 60488, 27686, 2133, 6958, 35603, 9669, 39523, 51586, 53692, 19031, 25449, 20909, 56120, 64419, 44510, 15012, 7684, 21893, 48484], [57889, 59989, 60866, 20372, 56587, 17359, 32338, 59921, 27075, 15684, 29842, 8558, 52826, 2219, 20615, 14446, 52275, 48207, 23671, 15383, 612, 57639, 14314, 13488, 4991, 42906, 47660, 49839, 26408, 65464, 7437, 36537, 59896, 36792, 25795, 55605, 59324, 25276, 50100, 48300], [8845, 53109, 25030, 30915, 42290, 43975, 18780, 61882, 6753, 52139, 17748, 60270, 23768, 44865, 21323, 61556, 26128, 62288, 38709, 53715, 57476, 18694, 39853, 15764, 46434, 30662, 56759, 38715, 51027, 41475, 26761, 28998, 26225, 42268, 63463, 29913, 46866, 43023, 44324, 19527], [16359, 10422, 39208, 49508, 40665, 35491, 16967, 58444, 39356, 3138, 62498, 47986, 9947, 48633, 42134, 48581, 51386, 58793, 32809, 47843, 58170, 11015, 12222, 17874, 22435, 48254, 44131, 43409, 37389, 25516, 46300, 40697, 47380, 33225, 5433, 39386, 24070, 58860, 22974, 31337], [18057, 62885, 22217, 24634, 56244, 39182, 36646, 2530, 64838, 58426, 60723, 39534, 51512, 6721, 36430, 27349, 47770, 8904, 14309, 55006, 52343, 40722, 35679, 61242, 52632, 16335, 4183, 23653, 44739, 1904, 19621, 52799, 45356, 30546, 57106, 56330, 34251, 6297, 24006, 62803], [3030, 20036, 49848, 19719, 52530, 60665, 20833, 31614, 56437, 21244, 41909, 27494, 18060, 46438, 60971, 11606, 50841, 51618, 10985, 59567, 60081, 49944, 62951, 47653, 34374, 3220, 2548, 25934, 50088, 3464, 7848, 57564, 50310, 36929, 16742, 45326, 14583, 42786, 46399, 15564], [55537, 28122, 41059, 24394, 50282, 24494, 29219, 59282, 59561, 56409, 42717, 11347, 4789, 29607, 22197, 37904, 43743, 42217, 6237, 47494, 60747, 33549, 42799, 29738, 15921, 43166, 14392, 41447, 60866, 39697, 15319, 45044, 39216, 35298, 60948, 5083, 6611, 15835, 32720, 14907], [41219, 63186, 5581, 16758, 46124, 28604, 33874, 34111, 63510, 30069, 39622, 58959, 52845, 33350, 10632, 62010, 54511, 18327, 55832, 61433, 38871, 27167, 1784, 25284, 25146, 13909, 43299, 16274, 31191, 30337, 57091, 21672, 3433, 64759, 5125, 32335, 40818, 43587, 18034, 57531], [64530, 16972, 20038, 53258, 54673, 7302, 33357, 24509, 61580, 8069, 4207, 45873, 55065, 3831, 55269, 50656, 64204, 56583, 44660, 44049, 46921, 25208, 37861, 7399, 45230, 12086, 54568, 47917, 6899, 64452, 39161, 33737, 36666, 24349, 39566, 55626, 65247, 23226, 27996, 54071], [35858, 15199, 37822, 15536, 25618, 50155, 46598, 45614, 21343, 11286, 46271, 49700, 58910, 4253, 34791, 11866, 27456, 63347, 26397, 6125, 3083, 32552, 64772, 17140, 21960, 42552, 7222, 5748, 31634, 50731, 8928, 50790, 62454, 6699, 13205, 57270, 5204, 61510, 670, 30789], [36832, 43520, 28023, 53867, 15810, 20359, 29924, 21410, 53751, 21485, 7333, 30663, 23263, 17206, 38950, 61868, 5065, 41552, 28400, 21310, 63598, 28910, 29882, 21493, 38518, 1873, 45739, 28637, 59839, 23917, 24200, 32081, 65468, 25124, 23881, 46027, 53970, 49201, 2112, 11286], [22411, 41769, 16894, 30731, 51269, 57480, 22154, 14864, 50655, 12280, 39819, 7744, 41963, 17812, 51761, 38701, 34081, 62943, 55792, 11032, 1935, 35046, 44439, 48672, 12476, 44538, 50548, 52534, 1972, 63078, 37996, 42593, 37644, 28235, 38791, 57701, 27250, 6297, 34309, 14171], [54073, 21754, 33979, 65258, 2850, 39268, 35008, 11711, 8276, 26242, 29256, 45649, 47086, 30060, 17792, 9706, 48257, 37335, 5530, 59619, 44317, 35174, 58707, 12529, 45383, 58814, 51390, 60562, 52122, 4387, 48590, 45938, 12740, 5240, 17954, 22977, 47273, 27613, 12592, 57493], [18554, 37889, 19189, 2316, 56532, 51279, 28746, 50606, 51647, 30446, 7285, 41922, 57368, 64527, 44412, 39822, 57394, 39721, 52477, 32071, 9677, 25563, 49797, 26529, 24961, 16990, 30024, 62296, 49682, 46196, 17198, 2348, 39490, 51596, 46352, 49120, 25135, 32278, 48009, 28850], [20201, 58002, 11110, 12845, 43607, 18541, 57301, 45009, 64573, 33194, 6733, 53929, 1030, 14079, 24114, 33888, 34480, 10289, 32301, 40107, 14105, 4271, 26187, 23911, 11185, 36666, 46717, 27275, 21362, 40176, 15913, 1090, 25170, 13456, 18085, 54849, 8257, 38751, 14819, 3199], [2803, 6566, 49388, 12218, 54687, 18220, 11664, 37800, 8330, 54177, 58949, 30828, 6189, 60583, 57311, 41934, 50736, 27122, 65300, 55533, 1490, 23073, 37172, 33042, 38744, 21135, 8513, 15717, 45885, 6505, 57812, 49824, 61246, 8298, 58148, 60549, 34604, 23905, 24282, 22641], [1609, 11897, 36358, 35689, 32853, 14664, 17061, 33064, 10832, 13610, 26084, 62618, 5207, 63225, 5703, 42940, 11065, 41679, 18268, 27682, 51622, 61667, 46919, 23655, 34259, 1695, 28779, 33045, 19256, 60484, 28071, 33717, 20490, 52868, 24359, 52273, 29408, 59813, 43634, 26690], [28416, 24323, 24492, 29388, 6337, 13867, 31763, 60021, 16923, 3979, 58990, 36064, 63322, 8, 1816, 24959, 31023, 10182, 783, 40803, 36503, 1401, 52328, 38622, 43981, 31247, 57814, 1931, 36372, 40032, 8440, 16860, 31140, 65359, 54663, 48957, 11852, 45002, 42114, 48549], [35895, 16211, 58565, 31257, 13416, 11794, 37954, 50135, 13445, 31279, 48149, 63113, 17229, 46691, 8571, 43196, 34408, 38434, 8907, 46996, 7061, 50207, 59102, 40708, 49155, 2165, 51363, 27071, 41111, 30395, 59955, 57205, 56789, 17664, 51513, 22271, 41849, 29492, 37288, 63964], [42065, 27775, 41060, 12965, 64305, 44363, 65479, 14565, 31358, 6086, 64255, 27848, 12631, 64585, 28313, 32600, 16375, 15794, 15684, 20508, 19355, 31376, 25507, 23619, 51875, 19629, 10507, 52289, 24671, 45954, 13755, 10558, 30404, 20954, 59022, 24507, 22613, 53146, 61329, 19245], [8199, 12433, 47363, 12809, 64556, 51858, 32581, 23575, 38601, 50941, 348, 27389, 56576, 62121, 11597, 864, 9363, 21055, 27989, 10475, 16108, 61084, 61743, 49126, 17955, 53298, 31396, 16110, 6806, 24574, 6210, 27090, 25998, 45370, 23950, 61302, 63162, 46449, 15252, 15075], [934, 18456, 46285, 55972, 16019, 19309, 1482, 50588, 55211, 9558, 24467, 54645, 18053, 30588, 59554, 53162, 13525, 51639, 43211, 14403, 23237, 12343, 29133, 30479, 26337, 371, 37707, 30717, 64215, 61156, 39280, 63842, 2566, 28871, 52536, 35795, 61661, 61717, 18391, 63036], [22425, 8593, 17421, 179, 3093, 27900, 20885, 24363, 21315, 65080, 4288, 12222, 22605, 60713, 12599, 45810, 25892, 30650, 24047, 1778, 38452, 7541, 49920, 24220, 63857, 17224, 31971, 19492, 14614, 24583, 29312, 44498, 981, 14749, 58573, 60905, 47248, 18010, 54219, 53798], [40621, 11752, 51506, 35159, 53136, 6975, 43652, 59542, 50928, 5304, 26798, 5410, 34625, 19290, 14361, 53356, 47934, 45225, 30162, 47005, 36209, 44750, 56650, 4159, 37242, 21265, 7271, 48683, 41257, 50770, 33159, 40715, 39272, 63544, 62315, 7436, 28302, 49744, 57625, 41447], [61653, 63247, 12008, 14519, 16147, 34435, 19371, 22436, 32337, 46263, 39936, 57539, 20989, 39244, 16431, 54936, 54327, 39319, 12845, 21827, 52406, 44093, 33601, 27732, 17505, 28639, 39504, 10177, 16811, 60471, 58514, 55966, 31859, 31952, 54751, 20163, 6375, 24455, 27459, 61628], [28412, 9854, 53711, 47774, 58351, 53898, 32631, 4501, 47734, 30735, 60462, 8341, 57198, 20380, 25835, 6283, 14767, 10841, 29381, 31858, 15094, 4680, 35444, 1217, 9586, 27109, 27539, 63384, 12987, 22862, 1667, 19420, 6154, 44963, 43748, 51388, 5092, 53178, 23464, 47355], [24032, 3381, 47654, 63829, 61538, 63146, 39325, 24226, 21124, 39283, 5638, 34716, 47075, 31574, 48073, 49021, 3488, 4968, 11188, 56834, 63349, 57889, 50230, 21614, 20141, 8301, 18105, 43695, 49382, 62793, 19581, 30353, 49715, 44698, 31581, 35250, 41834, 24389, 56541, 25714], [58018, 40216, 22310, 40096, 51808, 7105, 41750, 7641, 49564, 22889, 35162, 44208, 1463, 48926, 657, 29705, 58583, 4636, 30621, 3484, 7057, 60404, 24293, 45910, 22322, 56185, 35600, 11506, 32363, 7288, 34131, 11248, 61136, 62340, 56349, 40789, 13023, 52047, 29274, 62343], [20869, 55395, 1541, 12882, 11221, 17853, 35151, 2257, 52277, 37853, 62383, 29423, 9265, 62667, 45558, 32238, 24551, 55504, 14481, 42135, 51158, 50708, 49316, 17680, 36546, 61662, 25918, 49046, 18310, 13542, 1945, 61017, 30480, 26186, 52636, 54593, 38188, 3570, 43836, 32107], [63843, 6434, 4037, 15193, 60934, 24422, 42189, 31987, 12437, 23003, 56444, 31682, 15066, 14537, 59894, 43571, 48007, 42847, 39283, 63606, 34220, 41378, 9445, 63466, 1636, 28790, 35496, 13482, 49428, 62724, 54855, 11568, 64503, 16895, 32692, 32526, 28137, 36233, 37545, 12469], [44502, 2835, 54948, 53323, 18089, 5229, 24613, 38465, 54994, 47716, 55166, 44321, 41309, 61521, 54483, 6713, 49931, 24956, 25530, 25243, 39466, 26383, 44689, 158, 39768, 17275, 46917, 1011, 31123, 18474, 60491, 36751, 29259, 41907, 25375, 24637, 15382, 54209, 50823, 17321], [56694, 47495, 64297, 17073, 1406, 63230, 35033, 57294, 34296, 17609, 58737, 37099, 6033, 64755, 24794, 8799, 11871, 54616, 11736, 45334, 11918, 52630, 44396, 54071, 35149, 50083, 10908, 33601, 62789, 20187, 44183, 25318, 1177, 39812, 23483, 48631, 36346, 32709, 54437, 44095], [8196, 41794, 20533, 5013, 55377, 57656, 30557, 55727, 41153, 14318, 13476, 31548, 41620, 12280, 14072, 58829, 61519, 9513, 35896, 2583, 16179, 199, 19105, 5069, 46479, 48515, 48460, 20269, 38232, 51036, 51692, 49406, 46324, 5894, 13050, 23912, 55156, 34789, 8846, 10685], [49445, 4674, 48630, 20999, 36493, 18966, 11249, 43114, 49821, 34788, 47478, 63478, 63015, 38727, 54958, 29911, 4527, 20720, 45180, 35447, 22868, 57792, 64861, 51141, 60917, 57623, 6201, 9317, 6961, 3080, 3653, 18009, 13941, 41089, 51788, 17607, 36784, 40449, 4710, 10795], [60114, 1852, 47688, 28791, 50903, 9822, 56247, 27781, 51220, 27824, 25176, 47213, 24855, 45816, 1215, 12040, 54860, 33709, 22394, 46845, 55874, 25690, 20172, 53797, 23276, 8058, 27216, 28571, 15902, 17385, 8606, 53027, 16491, 38752, 34764, 29865, 36197, 49110, 45048, 45942], [37881, 61185, 44451, 51783, 36787, 20538, 12711, 20931, 46422, 52502, 4438, 44487, 53632, 35629, 42270, 10683, 9712, 62906, 28273, 22391, 11548, 34471, 50286, 59338, 36591, 26218, 49381, 50700, 6411, 42320, 34396, 4266, 19071, 28507, 4303, 8780, 17635, 60217, 29855, 20411], [27429, 42330, 2259, 40206, 9934, 5615, 41138, 15492, 10295, 61404, 61868, 16156, 6738, 41371, 13642, 35813, 42109, 40556, 40246, 14596, 50210, 25757, 12659, 48443, 47627, 10865, 58956, 21987, 63755, 59159, 61000, 26254, 25236, 8882, 33230, 22730, 40638, 57458, 55788, 20706], [19832, 25686, 61763, 57928, 51619, 52422, 50406, 41825, 18333, 34833, 20274, 13835, 43034, 63504, 7418, 30515, 23381, 40258, 39461, 59459, 10315, 29833, 13429, 28559, 24413, 34854, 51706, 2012, 20621, 275, 4321, 35879, 10364, 22775, 37076, 50181, 45848, 40650, 8684, 61272], [39898, 63840, 42291, 10186, 6329, 1101, 31625, 45246, 60146, 38266, 4224, 31326, 23827, 63217, 63799, 1560, 5234, 14399, 19731, 60900, 29447, 38658, 49254, 32205, 8929, 54407, 51134, 27579, 34782, 61789, 49025, 25819, 8018, 47406, 40021, 7350, 42168, 65515, 56405, 21452], [56050, 29119, 65375, 42825, 53457, 23726, 16717, 8564, 24811, 48571, 3578, 40065, 33360, 48562, 31062, 48108, 64037, 37728, 34999, 63502, 58101, 54310, 54449, 25164, 12728, 22204, 494, 23169, 61743, 64470, 47087, 25736, 20144, 18211, 47460, 4697, 48286, 11652, 61434, 12494]] c = [6908678492501, 5091965688798, 5523154639899, 6989800096353, 7469910913239, 4689456349904, 6649292327035, 7593850248979, 7708469385263, 6481537437540, 5633488101529, 6008371130331, 5726235162773, 7423095938667, 5132009109933, 5305166980598, 4820438854154, 6603953599793, 5970382146350, 4660969434440, 6764566861758, 7233792783209, 5577234538394, 9553066379112, 5643262891867, 6018839242494, 4577751622266, 6360895069750, 7273239399196, 7390401512660, 8531165484400, 4977146774323, 7127110653640, 4931785083009, 6526369782638, 4884978186703, 5606023581590, 4821990459559, 5864911289042, 5332280516973] list_prime = [] for i in c: tmp = [] res = get_factor(i) for j in res: if j.bit_length() == 16: tmp.append(j) list_prime.append(tmp) W = Matrix(ZZ, A) for i in product(*list_prime): new_c = [] for j in range(len(c)): new_c.append(c[j] // i[j]) vec_c = vector(new_c) m = W.solve_right(vec_c) res = b"" for x in m: res += bytes([int(x) & 0xff]) if b"CBC" in res: print(res) break ```
Flag: CBC2024{whats\_the\_point\_of\_this\_err0rzz} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://kos0ng.gitbook.io/ctfs/write-up/2024/cyber-breaker-competition-quals/cryptography.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.