|
''' |
|
CRC is affine. |
|
CRC(x) = L(x) + C, where L is linear. |
|
We want CRC(x) = L(x) + C = x. |
|
Write as L(x)+x = C. |
|
Solve matrix equation. |
|
''' |
|
|
|
from sage.all import * |
|
|
|
res = [None] * 82 |
|
|
|
CONST = 1021102219365466010738322 |
|
res[0] = 4402329568053044357841518 |
|
res[1] = 652462650701865447562368 |
|
res[2] = 4369145759738886008595303 |
|
res[3] = 2480322725602030768875470 |
|
res[4] = 3504337364566901180287596 |
|
res[5] = 4492055947069970831288629 |
|
res[6] = 3089508555006000235210244 |
|
res[7] = 1531125389201339528551566 |
|
res[8] = 1176648019828191878602387 |
|
res[9] = 4533670916488644166065306 |
|
res[10] = 3183955374751928179076504 |
|
res[11] = 4303124591420953202645797 |
|
res[12] = 1219458672930521212879946 |
|
res[13] = 3521677260187149121494147 |
|
res[14] = 1021102219365466010738326 |
|
res[15] = 1021102219365466010737298 |
|
res[16] = 1021102219365466010476178 |
|
res[17] = 1021102219365466077847186 |
|
res[18] = 1021102219365483190607506 |
|
res[19] = 1021102219369864057249426 |
|
res[20] = 1021102218239566103895698 |
|
res[21] = 1021101931135089859026578 |
|
res[22] = 1021176006341760848944786 |
|
res[23] = 1039991685296944591593106 |
|
res[24] = 723612442736140615112435 |
|
res[25] = 1852317898417064568664547 |
|
res[26] = 969155808624207308437923 |
|
res[27] = 742482596032282848806519 |
|
res[28] = 2154197729079946044161410 |
|
res[29] = 648036100669268898076370 |
|
res[30] = 666934752783312987730279 |
|
res[31] = 966794639034359563652102 |
|
res[32] = 1346953540247252200842103 |
|
res[33] = 218302412844807103027364 |
|
res[34] = 1691684737928954304794860 |
|
res[35] = 1139012733091695709028251 |
|
res[36] = 4052941992792522312156248 |
|
res[37] = 2052942769961202012537404 |
|
res[38] = 2149530574831885440521453 |
|
res[39] = 4000931163639271155048817 |
|
res[40] = 2357535689749561895600857 |
|
res[41] = 104965772635601781260188 |
|
res[42] = 3514374087227427657767586 |
|
res[43] = 1606239676235867280703382 |
|
res[44] = 2291422308517462666340119 |
|
res[45] = 4019839449630599976032377 |
|
res[46] = 251363856455415866684414 |
|
res[47] = 4686815195412971855444906 |
|
res[48] = 1021102219365466010738320 |
|
res[49] = 1021102219365466010737810 |
|
res[50] = 1021102219365466010607250 |
|
res[51] = 1021102219365465977183890 |
|
res[52] = 1021102219365474600672914 |
|
res[53] = 1021102219367665033993874 |
|
res[54] = 1021102218802516057317010 |
|
res[55] = 1021102075250277934882450 |
|
res[56] = 1021065325877318591635090 |
|
res[57] = 1030546952331205301165714 |
|
res[58] = 3438953858594724360150674 |
|
res[59] = 2799047788572004106284314 |
|
res[60] = 3561743988569803951188282 |
|
res[61] = 3448407093760358505404112 |
|
res[62] = 378724150034108489592602 |
|
res[63] = 1136799457497020025428658 |
|
res[64] = 3410633455859351564430680 |
|
res[65] = 993948433704610785294296 |
|
res[66] = 2541716746266957902021712 |
|
res[67] = 770816895700360977415561 |
|
res[68] = 34130868528435514685869 |
|
res[69] = 3533483238466385943087654 |
|
res[70] = 1328022495564497406784503 |
|
res[71] = 516991334942417818521797 |
|
res[72] = 2980710693000113191747485 |
|
res[73] = 3868705842258174243202387 |
|
res[74] = 2933671034983430374102151 |
|
res[75] = 903043225902278644682261 |
|
res[76] = 2116768851942252770139274 |
|
res[77] = 142671634563984641084944 |
|
res[78] = 2900614627552098051212896 |
|
res[79] = 3915920186082480366598615 |
|
res[80] = 825126553326313425012772 |
|
res[81] = 1530552403008155235290126 |
|
|
|
def tobin(x, n): |
|
return map(int, bin(x).lstrip("0b").rjust(n, "0")) |
|
|
|
m = matrix(GF(2), 82, 82) |
|
for i, v in enumerate(res): |
|
m.set_column(i, tobin(v ^ CONST, 82)) |
|
m[i,i] -= 1 |
|
target = vector(GF(2), tobin(CONST, 82)) |
|
|
|
sol = m.solve_right(target) |
|
print "".join(map(str, sol)) |
|
|
|
''' |
|
$ nc -v selfhash.ctfcompetition.com 1337 |
|
selfhash.ctfcompetition.com [130.211.78.216] 1337 (?) open |
|
Give me some data: 1010010010111000110111101011101001101011011000010000100001011100101001001100000000 |
|
|
|
CTF{i-hope-you-like-linear-algebra} |
|
''' |