[TWCTF 2019] M-Poly-Cipher

The cipher is below(All elements in matrixs are considered $Z_{0xFFFFFFFB}$):

pubkey : 8*8 matrix $A,B,C$

privkey : 8*8 matrix $X$

plaintext : 8*8 matrix $M$

ciphertext : 8*8 matrix $OTP_A, OTP_B, OTP_C$

 

$OTP, A, B$ : randomly chosen 8*8 matrix

 

encryption:

$C = -AX^2 - BX$

$OTP_A = OTP \times A$

$OTP_B = OTP \times B$

$OTP_C = OTP \times C + M$

 

decryption:

$M = OTP_A \times X^2+OTP_B \times X+OTP_C$

 

----------

 

To recover $M$, you must solve either the equation $AX^2+BX+C = O$ or find OTP.  Solve $AX^2+BX+C = O$ is hard. But OTP can be easily recovered by elementary calculation.

 

Although $det(A), det(B) = 0$, $det(B-A) \neq 0$. Therefore

 

$OTP = (OTP_B - OTP_A) \times (B-A)^(-1)$

 

Then $M = OTP_C - OTP \times C$ can be recovered.

 

from sage.all import IntegerModRing, MatrixSpace
 
 
mod = 0xFFFFFFFB
 
R = IntegerModRing(mod)
M = MatrixSpace(R,8,8)
 
A = M( [[3061373685, 2793288452, 3379156239, 3756818397, 2479317347, 1299748674, 1708276130, 3504934304], [2487607492, 3321012710, 2654148704, 2985766016, 2558681605, 2649106875, 3248937739, 1751021155], [1226390218, 1636981457, 2336138681, 290105240, 565093940, 3036661509, 2563017801, 765938396], [493145419, 2882315263, 1240490494, 2333415578, 2225016234, 2006449174, 992175038, 201898511], [1116432367, 1287892193, 3656860277, 1646974578, 3841098789, 2971336084, 2479678020, 2580776645], [666254982, 3308431100, 3902371851, 2546523429, 2843385157, 1152175852, 1499564239, 4953166], [2752591016, 3313518946, 4030532358, 1521414132, 3584340105, 1731855212, 3166298335, 2206789633], [2247255611, 1432179026, 3581134416, 1040862485, 1551141850, 3214177301, 356574821, 1033177343]] )
 
B = M( [[1874946135, 3036848081, 4266372659, 3822716103, 2539223274, 2776395270, 1592343752, 858338089], [1767984354, 3194259008, 2674992742, 3982998567, 3805616657, 3856451229, 1281407917, 3259144223], [3450960499, 863447826, 2309086456, 2820409953, 4053830779, 1759102368, 3062886588, 2181595411], [1327582621, 59100942, 1409226100, 4090914989, 3379410969, 3154860325, 893350723, 41493030], [3843281476, 1053244821, 3551596926, 194123543, 755886427, 1074215314,
1320563693, 2362286744], [1356997799, 2906444293, 4003922072, 985831683, 2793813019, 3187972735, 2148081768, 571388829], [2203698402, 1690965019, 3490610291, 667918844, 711986117, 2963774170, 3774574652, 2234342319], [3365331687, 1980367894, 572877263, 432826423, 3871679270,
3616509321, 1588316664, 2652575608]] )
 
C = M( [[2888029378, 3860587606, 3718019806, 3671255893, 1849823353, 988761075, 831124249, 974703135], [298497194, 2071209083, 750403830, 1011903655, 2247547112, 38172542, 1163592151, 653251305], [2315696570, 4244693686, 2299288579, 1488276978, 4219598065, 136874540, 1624320967,
290431480], [382670923, 2143511511, 3212855980, 3784624611, 1570298796, 2436266905, 2492979769, 2977969035], [2307083633, 358090101, 656915280, 745536474, 4153836969, 478257587, 207201412, 2760561093], [35912979, 637548255, 142521143, 2325311117, 3991628832, 2997898648, 3295038176, 3257685924], [22224251, 1068995474, 3524194890, 3793099571, 4143377314, 1091620964, 548795572, 2960226690], [3474719448, 355008537, 3711229694, 1300318520, 3327467511, 763514103, 3278512568, 2510697607]] )
 
OTP_A = M([[2716582022, 4084301418, 4151818525, 1422278892, 1369861164, 1613298264, 2900073187, 1964598128], [2753481205, 493595652, 565315225, 2950028936, 1494654641, 1565198195, 1821935145, 1185861501], [164370357, 436005162, 2815701498, 4174156708, 256795861, 3977759784, 1246234692, 97057022], [2325621496, 2620744676, 4018666671, 251117397, 3819917537, 1321497732, 896265439, 3639242790], [983542825, 4020044468, 1958580572, 595003756, 3013143078, 3706886809, 1979749517, 3687361750], [2611731788, 1782804165, 2927906200, 1928514011, 3906629325, 1280809420, 3698151597, 2378812419], [243836322, 3754526163, 3532682755, 2108443022, 354737559, 2625058601, 3107811435, 2905858194], [3218114692, 2694084275, 827772422, 1556237123, 291488027, 621169480, 653426521, 510118975]])
 
OTP_B = M([[4208214658, 1141042545, 2708383120, 457045796, 4130015787, 3290957094, 3126082618, 3320230692], [1466111706, 4056227737, 174742330, 4285221618, 3310324519, 4056215785, 1960438700, 186500500], [2912627126, 3834327149, 3052061589, 1860717089, 3153748975, 1111172768, 364253902, 1491593670], [1239932810, 3513118825, 199095984, 2263751480, 4285193614, 3475200926, 1067648159, 179009102], [4271340231, 707893284, 3791750854, 3191386411, 2742857472, 2330284944, 1043928958, 915069342], [1879765961, 2684813414, 3567283945, 3305112770, 2190703027, 885084630, 3675170595, 1959483168], [3717173206, 3762481794, 2558883988, 3474035828, 2909977898, 3864055306, 1690808134, 1256081129], [538320171, 680237347, 4064509998, 1303166605, 888522995, 2628811343, 578336895, 936456401]])
 
OTP_C = M([[4108227415, 3467527371, 1919686488, 1972690413, 964237228, 3083560747, 65249935, 1883917367], [175154727, 3605101142, 967469214, 2299437593, 3650035355, 400673433, 292025304, 2240974489], [1775180004, 890410229, 961213048, 207947447, 584409177, 2203526725, 1909624825, 2971025627], [216608792, 2015270265, 2884412645, 3751439311, 3471187975, 860487697, 437115178, 3310022716], [4124320737, 2321878557, 1196154615, 2599284463, 3800500668, 3273570568, 3737193570, 3410119944], [2359120676, 2764907194, 394673334, 2049351842, 1822158701, 1797094435, 1869242665, 2516861249], [3620926232, 1664408731, 1205895480, 2072096084, 869049620, 598309330, 3215990637, 4038757129], [3591275663, 1568901292, 3162576162, 2235551554, 1007647364, 2524055574, 3154568582, 2194599885]])
 
(B-A).det()
#A.echelon_form()
#A.kernel()
#C.minpoly()
 
OTP = (B-A)^(-1) * (OTP_B-OTP_A)
 
print(OTP*A == OTP_A)
print(OTP*B == OTP_B)
M = OTP_C - OTP*C
print(M)
ans = ''
for i in range(8):
   for j in range(8):
       ans += chr(M[i][j])
      
print(ans)