Cryptography
Baby RSA (100 pts)
Solution
Diberikan source code sebagai berikut
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
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
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
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
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)
breakFlag: CBC2024{whats_the_point_of_this_err0rzz}
Last updated
