[CTF write up] WACon CTF 2022 Final - islands : Easy matrix multiplication rev

ida

리버싱 공부하려고 처음으로 제대로 푼 리버싱 문제다. ida로 까보면 함수가 매우 여러게 있고 함수당 어셈블리가 들어있다. 별로 길지 않아서 하나씩 확인해서 로직을 분석하면 된다.

 

array1 = [246, 0, 58, 0, 217, 0, 173, 0, 210, 0, 224, 0, 7, 0, 116, 0, 199, 0, 18, 0, 117, 0, 160, 0, 27, 0, 191, 0, 158, 0, 238, 0, 243, 0, 211, 0, 116, 0, 147, 0, 195, 0, 39, 0, 185, 0, 154, 0, 181, 0, 215, 0, 33, 0, 184, 0, 231, 0, 42, 0, 78, 0, 65, 0, 137, 0, 188, 0, 52, 0, 136, 0, 154, 0, 233, 0, 124, 0, 245, 0, 43, 0, 140, 0, 62, 0, 103, 0, 129, 0, 182, 0, 122, 0, 108, 0, 35, 0, 60, 0, 17, 0, 113, 0, 215, 0, 68, 0, 193, 0, 173, 0, 35, 0, 58, 0, 147, 0, 116, 0, 170, 0, 166, 0, 109, 0, 27, 0, 126, 0, 2, 0, 243, 0, 222, 0, 221, 0, 25, 0, 124, 0, 196, 0, 50, 0, 212, 0, 97, 0, 222, 0, 131, 0, 57, 0, 59, 0, 23, 0, 136, 0, 198, 0, 63, 0, 125, 0, 29, 0, 9, 0, 35, 0, 128, 0, 244, 0, 168, 0, 2, 0, 208, 0, 111, 0, 164, 0, 58, 0, 190, 0, 147, 0, 164, 0, 198, 0, 67, 0, 233, 0, 141, 0, 72, 0, 15, 0, 9, 0, 148, 0, 139, 0, 125, 0, 174, 0, 238, 0, 56, 0, 1, 0, 14, 0, 189, 0, 231, 0, 84, 0, 147, 0, 66, 0, 124, 0, 238, 0, 16, 0, 63, 0, 146, 0, 191, 0, 189, 0, 115, 0, 87, 0, 222, 0, 128, 0, 155, 0, 167, 0, 199, 0, 37, 0, 14, 0, 147, 0, 22, 0, 209, 0, 201, 0, 27, 0, 82, 0, 186, 0, 121, 0, 209, 0, 236, 0, 62, 0, 94, 0, 120, 0, 55, 0, 163, 0, 249, 0, 106, 0, 122, 0, 159, 0, 94, 0, 126, 0, 110, 0, 60, 0, 103, 0, 39, 0, 216, 0, 69, 0, 31, 0, 216, 0, 210, 0, 36, 0, 242, 0, 66, 0, 200, 0, 174, 0, 79, 0, 247, 0, 37, 0, 97, 0, 250, 0, 82, 0, 81, 0, 188, 0, 115, 0, 128, 0, 97, 0, 204, 0, 6, 0, 70, 0, 79, 0, 36, 0, 175, 0, 14, 0, 140, 0, 108, 0, 200, 0, 89, 0, 118, 0, 109, 0, 152, 0, 9, 0, 238, 0, 10, 0, 246, 0, 112, 0, 210, 0, 154, 0, 154, 0, 199, 0, 51, 0, 8, 0, 9, 0, 247, 0, 241, 0, 127, 0, 139, 0, 236, 0, 158, 0, 214, 0, 195, 0, 245, 0, 205, 0, 226, 0, 195, 0, 167, 0, 241, 0, 81, 0, 191, 0, 206, 0, 50, 0, 21, 0, 164, 0, 92, 0, 239, 0, 208, 0, 117, 0, 103, 0, 89, 0, 81, 0, 85, 0, 140, 0, 12, 0, 197, 0, 114, 0, 152, 0, 1, 0, 172, 0, 171, 0, 110, 0, 82, 0, 66, 0, 48, 0, 20, 0, 5, 0, 19, 0, 136, 0, 5, 0, 142, 0, 77, 0, 124, 0, 69, 0, 196, 0, 147, 0, 60, 0, 228, 0, 130, 0, 168, 0, 202, 0, 130, 0, 178, 0, 188, 0, 234, 0, 115, 0, 15, 0, 214, 0, 107, 0, 28, 0, 178, 0, 144, 0, 47, 0, 249, 0, 10, 0, 39, 0, 23, 0, 112, 0, 232, 0, 93, 0, 60, 0, 175, 0, 50, 0, 215, 0, 61, 0, 122, 0, 200, 0, 82, 0, 147, 0, 40, 0, 173, 0, 187, 0, 135, 0, 218, 0, 116, 0, 65, 0, 146, 0, 52, 0, 1, 0, 153, 0, 147, 0, 37, 0, 191, 0, 123, 0, 52, 0, 75, 0, 73, 0, 155, 0, 98, 0, 132, 0, 215, 0, 110, 0, 5, 0, 50, 0, 183, 0, 161, 0, 68, 0, 236, 0, 106, 0, 19, 0, 106, 0, 249, 0, 156, 0, 69, 0, 222, 0, 180, 0, 97, 0, 39, 0, 143, 0, 32, 0, 24, 0, 81, 0, 129, 0, 234, 0, 177, 0, 245, 0, 45, 0, 199, 0, 129, 0, 81, 0, 61, 0, 237, 0, 109, 0, 113, 0, 130, 0, 121, 0, 60, 0, 42, 0, 17, 0, 123, 0, 44, 0, 221, 0, 152, 0, 137, 0, 92, 0, 100, 0, 65, 0, 42, 0, 140, 0, 60, 0, 182, 0, 121, 0, 65, 0, 64, 0, 3, 0, 108, 0, 14, 0, 169, 0, 22, 0, 137, 0, 99, 0, 245, 0, 12, 0, 89, 0, 97, 0, 205, 0, 170, 0, 21, 0, 13, 0, 2, 0, 194, 0, 171, 0, 109, 0, 79, 0, 231, 0, 115, 0, 203, 0, 47, 0, 11, 0, 22, 0, 35, 0, 212, 0, 176, 0, 25, 0, 245, 0, 44, 0, 172, 0, 0, 0, 170, 0, 72, 0, 141, 0, 104, 0, 158, 0, 72, 0, 175, 0, 199, 0, 123, 0, 9, 0, 113, 0, 213, 0, 92, 0, 140, 0, 34, 0, 108, 0, 238, 0, 128, 0, 50, 0, 9, 0, 36, 0, 167, 0, 171, 0, 162, 0, 31, 0, 73, 0, 0, 0, 197, 0, 156, 0, 208, 0, 49, 0, 207, 0, 248, 0, 142, 0, 107, 0, 223, 0, 29, 0, 33, 0, 134, 0, 226, 0, 217, 0, 23, 0, 161, 0, 153, 0, 134, 0, 52, 0, 74, 0, 209, 0, 40, 0, 85, 0, 67, 0, 132, 0, 38, 0, 141, 0, 125, 0, 44, 0, 147, 0, 104, 0, 136, 0, 185, 0, 119, 0, 91, 0, 229, 0, 43, 0, 14, 0, 22, 0, 73, 0, 39, 0, 162, 0, 103, 0, 114, 0, 60, 0, 220, 0, 57, 0, 72, 0, 206, 0, 213, 0, 100, 0, 219, 0, 50, 0, 223, 0, 82, 0, 127, 0, 236, 0, 20, 0, 178, 0, 241, 0, 94, 0, 30, 0, 93, 0, 234, 0, 162, 0, 200, 0, 68, 0, 81, 0, 175, 0, 219, 0, 167, 0, 182, 0, 72, 0, 16, 0, 44, 0, 59, 0, 164, 0, 225, 0, 71, 0, 54, 0, 31, 0, 120, 0, 110, 0, 96, 0, 231, 0, 210, 0, 229, 0, 18, 0, 137, 0, 48, 0, 234, 0, 238, 0, 233, 0, 148, 0, 200, 0, 202, 0, 151, 0, 142, 0, 149, 0, 8, 0, 151, 0, 39, 0, 226, 0, 168, 0, 193, 0, 211, 0, 11, 0, 141, 0, 34, 0, 172, 0, 205, 0, 21, 0, 146, 0, 142, 0, 188, 0, 144, 0, 50, 0, 236, 0, 7, 0, 8, 0, 0, 0, 239, 0, 179, 0, 194, 0, 231, 0, 164, 0, 145, 0, 228, 0, 15, 0, 155, 0, 80, 0, 202, 0, 4, 0, 242, 0, 216, 0, 19, 0, 98, 0, 177, 0, 22, 0, 77, 0, 138, 0, 205, 0, 34, 0, 107, 0, 134, 0, 194, 0, 78, 0, 62, 0, 181, 0, 153, 0, 151, 0, 244, 0, 112, 0, 139, 0, 49, 0, 51, 0, 186, 0, 180, 0, 117, 0, 166, 0, 128, 0, 174, 0, 136, 0, 77, 0, 157, 0, 104, 0, 233, 0, 47, 0, 17, 0, 33, 0, 248, 0, 120, 0, 17, 0, 56, 0, 62, 0, 170, 0, 82, 0, 127, 0, 123, 0, 143, 0, 137, 0, 52, 0, 2, 0, 107, 0, 55, 0, 74, 0, 210, 0, 28, 0, 180, 0, 68, 0, 82, 0, 90, 0, 29, 0, 89, 0, 88, 0, 16, 0, 182, 0, 59, 0, 38, 0, 43, 0, 65, 0, 18, 0, 104, 0, 2, 0, 169, 0, 81, 0, 106, 0, 226, 0, 219, 0, 99, 0, 154, 0, 107, 0, 188, 0, 54, 0, 222, 0, 236, 0, 23, 0, 209, 0, 127, 0, 94, 0, 148, 0, 95, 0, 117, 0, 217, 0, 66, 0, 178, 0, 141, 0, 19, 0, 205, 0, 149, 0, 204, 0, 71, 0, 34, 0, 204, 0, 130, 0, 165, 0, 209, 0, 214, 0, 84, 0, 129, 0, 183, 0, 97, 0, 101, 0, 12, 0, 244, 0, 229, 0, 165, 0, 37, 0, 166, 0, 168, 0, 87, 0, 171, 0, 56, 0, 226, 0, 139, 0, 176, 0, 82, 0, 194, 0, 0, 0, 16, 0, 1, 0, 140, 0, 232, 0, 154, 0, 129, 0, 95, 0, 123, 0, 215, 0, 84, 0, 48, 0, 154, 0, 130, 0, 107, 0, 147, 0, 152, 0, 102, 0, 19, 0, 55, 0, 98, 0, 208, 0, 70, 0, 106, 0, 250, 0, 66, 0, 238, 0, 111, 0, 155, 0, 5, 0, 56, 0, 71, 0, 230, 0, 193, 0, 33, 0, 199, 0, 60, 0, 63, 0, 194, 0, 204, 0, 172, 0, 40, 0, 75, 0, 197, 0, 41, 0, 198, 0, 167, 0, 142, 0, 161, 0, 31, 0, 1, 0, 175, 0, 246, 0, 162, 0, 233, 0, 119, 0, 145, 0, 11, 0, 226, 0, 11, 0, 97, 0, 229, 0, 241, 0, 82, 0, 175, 0, 248, 0, 152, 0, 146, 0, 163, 0, 6, 0, 59, 0, 224, 0, 216, 0, 41, 0, 142, 0, 97, 0, 10, 0, 243, 0, 53, 0, 157, 0, 210, 0, 197, 0, 65, 0, 52, 0, 143, 0, 155, 0, 103, 0, 184, 0, 171, 0, 231, 0, 238, 0, 95, 0, 146, 0, 243, 0, 117, 0, 190, 0, 165, 0, 203, 0, 63, 0, 147, 0, 55, 0, 190, 0, 132, 0, 162, 0, 210, 0, 108, 0, 186, 0, 213, 0, 91, 0, 237, 0, 58, 0, 244, 0, 218, 0, 119, 0, 213, 0, 33, 0, 118, 0, 133, 0, 111, 0, 20, 0, 27, 0, 171, 0, 53, 0, 195, 0, 133, 0, 5, 0, 202, 0, 8, 0, 79, 0, 50, 0, 118, 0, 200, 0, 61, 0, 152, 0, 132, 0, 111, 0, 73, 0, 92, 0, 76, 0, 245, 0, 55, 0, 196, 0, 114, 0, 22, 0, 232, 0, 40, 0, 205, 0, 156, 0, 83, 0, 230, 0, 213, 0, 170, 0, 84, 0, 82, 0, 212, 0, 157, 0, 142, 0, 99, 0, 62, 0, 3, 0, 86, 0, 49, 0, 186, 0, 250, 0, 106, 0, 25, 0, 19, 0, 121, 0, 209, 0, 31, 0, 151, 0, 61, 0, 187, 0, 230, 0, 132, 0, 198, 0, 217, 0, 76, 0, 226, 0, 230, 0, 249, 0, 164, 0, 36, 0, 157, 0, 108, 0, 178, 0, 149, 0, 10, 0, 246, 0, 228, 0, 82, 0, 226, 0, 94, 0, 198, 0, 243, 0, 94, 0, 151, 0, 54, 0, 81, 0, 137, 0, 93, 0, 245, 0, 243, 0, 62, 0, 132, 0, 245, 0, 45, 0, 120, 0, 212, 0, 212, 0, 85, 0, 218, 0, 169, 0, 189, 0, 73, 0, 38, 0, 75, 0, 41, 0, 0, 0, 71, 0, 204, 0, 237, 0, 205, 0, 58, 0, 96, 0, 104, 0, 23, 0, 34, 0, 45, 0, 64, 0, 200, 0, 130, 0, 11, 0, 46, 0, 132, 0, 184, 0, 57, 0, 25, 0, 96, 0, 122, 0, 93, 0, 27, 0, 244, 0, 210, 0, 142, 0, 16, 0, 124, 0, 26, 0, 118, 0, 148, 0, 198, 0, 173, 0, 196, 0, 96, 0, 248, 0, 127, 0, 240, 0, 225, 0, 4, 0, 142, 0, 167, 0, 224, 0, 108, 0, 12, 0, 52, 0, 23, 0, 225, 0, 183, 0, 197, 0, 250, 0, 169, 0, 35, 0, 41, 0, 81, 0, 191, 0, 199, 0, 63, 0, 240, 0, 104, 0, 126, 0, 84, 0, 238, 0, 197, 0, 208, 0, 165, 0, 236, 0, 153, 0, 52, 0, 135, 0, 111, 0, 22, 0, 169, 0, 54, 0, 27, 0, 180, 0, 129, 0, 232, 0, 213, 0, 149, 0, 116, 0, 98, 0, 85, 0, 5, 0, 30, 0, 82, 0, 120, 0, 107, 0, 101, 0, 39, 0, 200, 0, 193, 0, 65, 0, 82, 0, 169, 0, 64, 0, 210, 0, 137, 0, 8, 0, 198, 0, 74, 0, 152, 0, 190, 0, 172, 0, 112, 0, 56, 0, 140, 0, 38, 0, 168, 0, 85, 0, 142, 0, 33, 0, 8, 0, 171, 0, 148, 0, 163, 0, 20, 0, 231, 0, 192, 0, 166, 0, 181, 0]
array2 = [82, 0, 210, 0, 119, 0, 206, 0, 210, 0, 218, 0, 154, 0, 166, 0, 79, 0, 74, 0, 232, 0, 209, 0, 94, 0, 69, 0, 117, 0, 152, 0, 151, 0, 20, 0, 182, 0, 196, 0, 238, 0, 156, 0, 234, 0, 131, 0, 170, 0, 34, 0, 234, 0, 166, 0, 72, 0, 160, 0, 158, 0, 242, 0]
array1 = [array1[i] for i in range(0,len(array1)) if i%2==0]
array2 = [array2[i] for i in range(0,len(array2)) if i%2==0]

string = "a"*0x20
#string = "a"*0x20
v40 = [ord(w) for w in string]
v0 = [0]*0x20

for rbx in range(0,0x20):
    for rsi in range(0,0x20):
        edx = ( v0[rbx] + (v40[rsi] * array1[(rbx * 32) + ((rbx+rsi) & 0x1f)])) % 251
        v0[rbx] = edx

print(v0)

괴상한 비트 연산은 값을 하나씩 넣어서 확인해보면 % 251 연산이라는 걸 알 수 있다. 최종적으로 v0 = array2가 되게하는 string 값을 찾으면 된다. 로직을 살펴보면, 행렬곱과 유사하게 생겼다는 것을 알 수 있다.

 

 

 

b = [[246, 58, 217, 173, 210, 224, 7, 116, 199, 18, 117, 160, 27, 191, 158, 238, 243, 211, 116, 147, 195, 39, 185, 154, 181, 215, 33, 184, 231, 42, 78, 65], [137, 188, 52, 136, 154, 233, 124, 245, 43, 140, 62, 103, 129, 182, 122, 108, 35, 60, 17, 113, 215, 68, 193, 173, 35, 58, 147, 116, 170, 166, 109, 27], [126, 2, 243, 222, 221, 25, 124, 196, 50, 212, 97, 222, 131, 57, 59, 23, 136, 198, 63, 125, 29, 9, 35, 128, 244, 168, 2, 208, 111, 164, 58, 190], [147, 164, 198, 67, 233, 141, 72, 15, 9, 148, 139, 125, 174, 238, 56, 1, 14, 189, 231, 84, 147, 66, 124, 238, 16, 63, 146, 191, 189, 115, 87, 222], [128, 155, 167, 199, 37, 14, 147, 22, 209, 201, 27, 82, 186, 121, 209, 236, 62, 94, 120, 55, 163, 249, 106, 122, 159, 94, 126, 110, 60, 103, 39, 216], [69, 31, 216, 210, 36, 242, 66, 200, 174, 79, 247, 37, 97, 250, 82, 81, 188, 115, 128, 97, 204, 6, 70, 79, 36, 175, 14, 140, 108, 200, 89, 118], [109, 152, 9, 238, 10, 246, 112, 210, 154, 154, 199, 51, 8, 9, 247, 241, 127, 139, 236, 158, 214, 195, 245, 205, 226, 195, 167, 241, 81, 191, 206, 50], [21, 164, 92, 239, 208, 117, 103, 89, 81, 85, 140, 12, 197, 114, 152, 1, 172, 171, 110, 82, 66, 48, 20, 5, 19, 136, 5, 142, 77, 124, 69, 196], [147, 60, 228, 130, 168, 202, 130, 178, 188, 234, 115, 15, 214, 107, 28, 178, 144, 47, 249, 10, 39, 23, 112, 232, 93, 60, 175, 50, 215, 61, 122, 200], [82, 147, 40, 173, 187, 135, 218, 116, 65, 146, 52, 1, 153, 147, 37, 191, 123, 52, 75, 73, 155, 98, 132, 215, 110, 5, 50, 183, 161, 68, 236, 106], [19, 106, 249, 156, 69, 222, 180, 97, 39, 143, 32, 24, 81, 129, 234, 177, 245, 45, 199, 129, 81, 61, 237, 109, 113, 130, 121, 60, 42, 17, 123, 44], [221, 152, 137, 92, 100, 65, 42, 140, 60, 182, 121, 65, 64, 3, 108, 14, 169, 22, 137, 99, 245, 12, 89, 97, 205, 170, 21, 13, 2, 194, 171, 109], [79, 231, 115, 203, 47, 11, 22, 35, 212, 176, 25, 245, 44, 172, 0, 170, 72, 141, 104, 158, 72, 175, 199, 123, 9, 113, 213, 92, 140, 34, 108, 238], [128, 50, 9, 36, 167, 171, 162, 31, 73, 0, 197, 156, 208, 49, 207, 248, 142, 107, 223, 29, 33, 134, 226, 217, 23, 161, 153, 134, 52, 74, 209, 40], [85, 67, 132, 38, 141, 125, 44, 147, 104, 136, 185, 119, 91, 229, 43, 14, 22, 73, 39, 162, 103, 114, 60, 220, 57, 72, 206, 213, 100, 219, 50, 223], [82, 127, 236, 20, 178, 241, 94, 30, 93, 234, 162, 200, 68, 81, 175, 219, 167, 182, 72, 16, 44, 59, 164, 225, 71, 54, 31, 120, 110, 96, 231, 210], [229, 18, 137, 48, 234, 238, 233, 148, 200, 202, 151, 142, 149, 8, 151, 39, 226, 168, 193, 211, 11, 141, 34, 172, 205, 21, 146, 142, 188, 144, 50, 236], [7, 8, 0, 239, 179, 194, 231, 164, 145, 228, 15, 155, 80, 202, 4, 242, 216, 19, 98, 177, 22, 77, 138, 205, 34, 107, 134, 194, 78, 62, 181, 153], [151, 244, 112, 139, 49, 51, 186, 180, 117, 166, 128, 174, 136, 77, 157, 104, 233, 47, 17, 33, 248, 120, 17, 56, 62, 170, 82, 127, 123, 143, 137, 52], [2, 107, 55, 74, 210, 28, 180, 68, 82, 90, 29, 89, 88, 16, 182, 59, 38, 43, 65, 18, 104, 2, 169, 81, 106, 226, 219, 99, 154, 107, 188, 54], [222, 236, 23, 209, 127, 94, 148, 95, 117, 217, 66, 178, 141, 19, 205, 149, 204, 71, 34, 204, 130, 165, 209, 214, 84, 129, 183, 97, 101, 12, 244, 229], [165, 37, 166, 168, 87, 171, 56, 226, 139, 176, 82, 194, 0, 16, 1, 140, 232, 154, 129, 95, 123, 215, 84, 48, 154, 130, 107, 147, 152, 102, 19, 55], [98, 208, 70, 106, 250, 66, 238, 111, 155, 5, 56, 71, 230, 193, 33, 199, 60, 63, 194, 204, 172, 40, 75, 197, 41, 198, 167, 142, 161, 31, 1, 175], [246, 162, 233, 119, 145, 11, 226, 11, 97, 229, 241, 82, 175, 248, 152, 146, 163, 6, 59, 224, 216, 41, 142, 97, 10, 243, 53, 157, 210, 197, 65, 52], [143, 155, 103, 184, 171, 231, 238, 95, 146, 243, 117, 190, 165, 203, 63, 147, 55, 190, 132, 162, 210, 108, 186, 213, 91, 237, 58, 244, 218, 119, 213, 33], [118, 133, 111, 20, 27, 171, 53, 195, 133, 5, 202, 8, 79, 50, 118, 200, 61, 152, 132, 111, 73, 92, 76, 245, 55, 196, 114, 22, 232, 40, 205, 156], [83, 230, 213, 170, 84, 82, 212, 157, 142, 99, 62, 3, 86, 49, 186, 250, 106, 25, 19, 121, 209, 31, 151, 61, 187, 230, 132, 198, 217, 76, 226, 230], [249, 164, 36, 157, 108, 178, 149, 10, 246, 228, 82, 226, 94, 198, 243, 94, 151, 54, 81, 137, 93, 245, 243, 62, 132, 245, 45, 120, 212, 212, 85, 218], [169, 189, 73, 38, 75, 41, 0, 71, 204, 237, 205, 58, 96, 104, 23, 34, 45, 64, 200, 130, 11, 46, 132, 184, 57, 25, 96, 122, 93, 27, 244, 210], [142, 16, 124, 26, 118, 148, 198, 173, 196, 96, 248, 127, 240, 225, 4, 142, 167, 224, 108, 12, 52, 23, 225, 183, 197, 250, 169, 35, 41, 81, 191, 199], [63, 240, 104, 126, 84, 238, 197, 208, 165, 236, 153, 52, 135, 111, 22, 169, 54, 27, 180, 129, 232, 213, 149, 116, 98, 85, 5, 30, 82, 120, 107, 101], [39, 200, 193, 65, 82, 169, 64, 210, 137, 8, 198, 74, 152, 190, 172, 112, 56, 140, 38, 168, 85, 142, 33, 8, 171, 148, 163, 20, 231, 192, 166, 181]]
r = [82, 210, 119, 206, 210, 218, 154, 166, 79, 74, 232, 209, 94, 69, 117, 152, 151, 20, 182, 196, 238, 156, 234, 131, 170, 34, 234, 166, 72, 160, 158, 242]

string = "a"*0x20
a = [ord(w) for w in string]
c = [0]*0x20

d = [0]*0x20

for n1 in range(0,0x20):
    for n2 in range(0,0x20):
        c[n1] = (c[n1] + a[n2] * b[n1][n1+n2 & 31])
    c[n1] = c[n1] % 251

print(c)

좀 더 보기 쉽게 바꾸면 위와 같다. b[n1][n1+n2 & 31]을 b[n2][n1]으로 바꿔주면 행렬곱이 되므로 아래의 코드로 재배열 된 배열 b를 출력하면 된다.

 

 

b = [[246, 58, 217, 173, 210, 224, 7, 116, 199, 18, 117, 160, 27, 191, 158, 238, 243, 211, 116, 147, 195, 39, 185, 154, 181, 215, 33, 184, 231, 42, 78, 65], [137, 188, 52, 136, 154, 233, 124, 245, 43, 140, 62, 103, 129, 182, 122, 108, 35, 60, 17, 113, 215, 68, 193, 173, 35, 58, 147, 116, 170, 166, 109, 27], [126, 2, 243, 222, 221, 25, 124, 196, 50, 212, 97, 222, 131, 57, 59, 23, 136, 198, 63, 125, 29, 9, 35, 128, 244, 168, 2, 208, 111, 164, 58, 190], [147, 164, 198, 67, 233, 141, 72, 15, 9, 148, 139, 125, 174, 238, 56, 1, 14, 189, 231, 84, 147, 66, 124, 238, 16, 63, 146, 191, 189, 115, 87, 222], [128, 155, 167, 199, 37, 14, 147, 22, 209, 201, 27, 82, 186, 121, 209, 236, 62, 94, 120, 55, 163, 249, 106, 122, 159, 94, 126, 110, 60, 103, 39, 216], [69, 31, 216, 210, 36, 242, 66, 200, 174, 79, 247, 37, 97, 250, 82, 81, 188, 115, 128, 97, 204, 6, 70, 79, 36, 175, 14, 140, 108, 200, 89, 118], [109, 152, 9, 238, 10, 246, 112, 210, 154, 154, 199, 51, 8, 9, 247, 241, 127, 139, 236, 158, 214, 195, 245, 205, 226, 195, 167, 241, 81, 191, 206, 50], [21, 164, 92, 239, 208, 117, 103, 89, 81, 85, 140, 12, 197, 114, 152, 1, 172, 171, 110, 82, 66, 48, 20, 5, 19, 136, 5, 142, 77, 124, 69, 196], [147, 60, 228, 130, 168, 202, 130, 178, 188, 234, 115, 15, 214, 107, 28, 178, 144, 47, 249, 10, 39, 23, 112, 232, 93, 60, 175, 50, 215, 61, 122, 200], [82, 147, 40, 173, 187, 135, 218, 116, 65, 146, 52, 1, 153, 147, 37, 191, 123, 52, 75, 73, 155, 98, 132, 215, 110, 5, 50, 183, 161, 68, 236, 106], [19, 106, 249, 156, 69, 222, 180, 97, 39, 143, 32, 24, 81, 129, 234, 177, 245, 45, 199, 129, 81, 61, 237, 109, 113, 130, 121, 60, 42, 17, 123, 44], [221, 152, 137, 92, 100, 65, 42, 140, 60, 182, 121, 65, 64, 3, 108, 14, 169, 22, 137, 99, 245, 12, 89, 97, 205, 170, 21, 13, 2, 194, 171, 109], [79, 231, 115, 203, 47, 11, 22, 35, 212, 176, 25, 245, 44, 172, 0, 170, 72, 141, 104, 158, 72, 175, 199, 123, 9, 113, 213, 92, 140, 34, 108, 238], [128, 50, 9, 36, 167, 171, 162, 31, 73, 0, 197, 156, 208, 49, 207, 248, 142, 107, 223, 29, 33, 134, 226, 217, 23, 161, 153, 134, 52, 74, 209, 40], [85, 67, 132, 38, 141, 125, 44, 147, 104, 136, 185, 119, 91, 229, 43, 14, 22, 73, 39, 162, 103, 114, 60, 220, 57, 72, 206, 213, 100, 219, 50, 223], [82, 127, 236, 20, 178, 241, 94, 30, 93, 234, 162, 200, 68, 81, 175, 219, 167, 182, 72, 16, 44, 59, 164, 225, 71, 54, 31, 120, 110, 96, 231, 210], [229, 18, 137, 48, 234, 238, 233, 148, 200, 202, 151, 142, 149, 8, 151, 39, 226, 168, 193, 211, 11, 141, 34, 172, 205, 21, 146, 142, 188, 144, 50, 236], [7, 8, 0, 239, 179, 194, 231, 164, 145, 228, 15, 155, 80, 202, 4, 242, 216, 19, 98, 177, 22, 77, 138, 205, 34, 107, 134, 194, 78, 62, 181, 153], [151, 244, 112, 139, 49, 51, 186, 180, 117, 166, 128, 174, 136, 77, 157, 104, 233, 47, 17, 33, 248, 120, 17, 56, 62, 170, 82, 127, 123, 143, 137, 52], [2, 107, 55, 74, 210, 28, 180, 68, 82, 90, 29, 89, 88, 16, 182, 59, 38, 43, 65, 18, 104, 2, 169, 81, 106, 226, 219, 99, 154, 107, 188, 54], [222, 236, 23, 209, 127, 94, 148, 95, 117, 217, 66, 178, 141, 19, 205, 149, 204, 71, 34, 204, 130, 165, 209, 214, 84, 129, 183, 97, 101, 12, 244, 229], [165, 37, 166, 168, 87, 171, 56, 226, 139, 176, 82, 194, 0, 16, 1, 140, 232, 154, 129, 95, 123, 215, 84, 48, 154, 130, 107, 147, 152, 102, 19, 55], [98, 208, 70, 106, 250, 66, 238, 111, 155, 5, 56, 71, 230, 193, 33, 199, 60, 63, 194, 204, 172, 40, 75, 197, 41, 198, 167, 142, 161, 31, 1, 175], [246, 162, 233, 119, 145, 11, 226, 11, 97, 229, 241, 82, 175, 248, 152, 146, 163, 6, 59, 224, 216, 41, 142, 97, 10, 243, 53, 157, 210, 197, 65, 52], [143, 155, 103, 184, 171, 231, 238, 95, 146, 243, 117, 190, 165, 203, 63, 147, 55, 190, 132, 162, 210, 108, 186, 213, 91, 237, 58, 244, 218, 119, 213, 33], [118, 133, 111, 20, 27, 171, 53, 195, 133, 5, 202, 8, 79, 50, 118, 200, 61, 152, 132, 111, 73, 92, 76, 245, 55, 196, 114, 22, 232, 40, 205, 156], [83, 230, 213, 170, 84, 82, 212, 157, 142, 99, 62, 3, 86, 49, 186, 250, 106, 25, 19, 121, 209, 31, 151, 61, 187, 230, 132, 198, 217, 76, 226, 230], [249, 164, 36, 157, 108, 178, 149, 10, 246, 228, 82, 226, 94, 198, 243, 94, 151, 54, 81, 137, 93, 245, 243, 62, 132, 245, 45, 120, 212, 212, 85, 218], [169, 189, 73, 38, 75, 41, 0, 71, 204, 237, 205, 58, 96, 104, 23, 34, 45, 64, 200, 130, 11, 46, 132, 184, 57, 25, 96, 122, 93, 27, 244, 210], [142, 16, 124, 26, 118, 148, 198, 173, 196, 96, 248, 127, 240, 225, 4, 142, 167, 224, 108, 12, 52, 23, 225, 183, 197, 250, 169, 35, 41, 81, 191, 199], [63, 240, 104, 126, 84, 238, 197, 208, 165, 236, 153, 52, 135, 111, 22, 169, 54, 27, 180, 129, 232, 213, 149, 116, 98, 85, 5, 30, 82, 120, 107, 101], [39, 200, 193, 65, 82, 169, 64, 210, 137, 8, 198, 74, 152, 190, 172, 112, 56, 140, 38, 168, 85, 142, 33, 8, 171, 148, 163, 20, 231, 192, 166, 181]]

b2 = []
for n1 in range(0,0x20):
    b2_ = []
    for n2 in range(0,0x20):
        b2_.append(b[n1][n1+n2 & 31])
    b2.append(b2_)
b = b2

rs = []
for n1 in range(0,0x20):
    rs_ = []
    for n2 in range(0,0x20):
        rs_.append(b[n2][n1])
    rs.append(rs_)

print(rs)

위 코드로 재배열된 b를 얻을 수 있다.

 

 

 

b2 = [[246, 188, 243, 67, 37, 242, 112, 89, 188, 146, 32, 65, 44, 49, 43, 219, 226, 19, 17, 18, 130, 215, 75, 97, 91, 196, 132, 120, 93, 81, 107, 181], [58, 52, 222, 233, 14, 66, 210, 81, 234, 52, 24, 64, 172, 207, 14, 167, 168, 98, 33, 104, 165, 84, 197, 10, 237, 114, 198, 212, 27, 191, 101, 39], [217, 136, 221, 141, 147, 200, 154, 85, 115, 1, 81, 3, 0, 248, 22, 182, 193, 177, 248, 2, 209, 48, 41, 243, 58, 22, 217, 212, 244, 199, 63, 200], [173, 154, 25, 72, 22, 174, 154, 140, 15, 153, 129, 108, 170, 142, 73, 72, 211, 22, 120, 169, 214, 154, 198, 53, 244, 232, 76, 85, 210, 142, 240, 193], [210, 233, 124, 15, 209, 79, 199, 12, 214, 147, 234, 14, 72, 107, 39, 16, 11, 77, 17, 81, 84, 130, 167, 157, 218, 40, 226, 218, 169, 16, 104, 65], [224, 124, 196, 9, 201, 247, 51, 197, 107, 37, 177, 169, 141, 223, 162, 44, 141, 138, 56, 106, 129, 107, 142, 210, 119, 205, 230, 249, 189, 124, 126, 82], [7, 245, 50, 148, 27, 37, 8, 114, 28, 191, 245, 22, 104, 29, 103, 59, 34, 205, 62, 226, 183, 147, 161, 197, 213, 156, 83, 164, 73, 26, 84, 169], [116, 43, 212, 139, 82, 97, 9, 152, 178, 123, 45, 137, 158, 33, 114, 164, 172, 34, 170, 219, 97, 152, 31, 65, 33, 118, 230, 36, 38, 118, 238, 64], [199, 140, 97, 125, 186, 250, 247, 1, 144, 52, 199, 99, 72, 134, 60, 225, 205, 107, 82, 99, 101, 102, 1, 52, 143, 133, 213, 157, 75, 148, 197, 210], [18, 62, 222, 174, 121, 82, 241, 172, 47, 75, 129, 245, 175, 226, 220, 71, 21, 134, 127, 154, 12, 19, 175, 246, 155, 111, 170, 108, 41, 198, 208, 137], [117, 103, 131, 238, 209, 81, 127, 171, 249, 73, 81, 12, 199, 217, 57, 54, 146, 194, 123, 107, 244, 55, 98, 162, 103, 20, 84, 178, 0, 173, 165, 8], [160, 129, 57, 56, 236, 188, 139, 110, 10, 155, 61, 89, 123, 23, 72, 31, 142, 78, 143, 188, 229, 165, 208, 233, 184, 27, 82, 149, 71, 196, 236, 198], [27, 182, 59, 1, 62, 115, 236, 82, 39, 98, 237, 97, 9, 161, 206, 120, 188, 62, 137, 54, 222, 37, 70, 119, 171, 171, 212, 10, 204, 96, 153, 74], [191, 122, 23, 14, 94, 128, 158, 66, 23, 132, 109, 205, 113, 153, 213, 110, 144, 181, 52, 2, 236, 166, 106, 145, 231, 53, 157, 246, 237, 248, 52, 152], [158, 108, 136, 189, 120, 97, 214, 48, 112, 215, 113, 170, 213, 134, 100, 96, 50, 153, 151, 107, 23, 168, 250, 11, 238, 195, 142, 228, 205, 127, 135, 190], [238, 35, 198, 231, 55, 204, 195, 20, 232, 110, 130, 21, 92, 52, 219, 231, 236, 7, 244, 55, 209, 87, 66, 226, 95, 133, 99, 82, 58, 240, 111, 172], [243, 60, 63, 84, 163, 6, 245, 5, 93, 5, 121, 13, 140, 74, 50, 210, 229, 8, 112, 74, 127, 171, 238, 11, 146, 5, 62, 226, 96, 225, 22, 112], [211, 17, 125, 147, 249, 70, 205, 19, 60, 50, 60, 2, 34, 209, 223, 82, 18, 0, 139, 210, 94, 56, 111, 97, 243, 202, 3, 94, 104, 4, 169, 56], [116, 113, 29, 66, 106, 79, 226, 136, 175, 183, 42, 194, 108, 40, 85, 127, 137, 239, 49, 28, 148, 226, 155, 229, 117, 8, 86, 198, 23, 142, 54, 140], [147, 215, 9, 124, 122, 36, 195, 5, 50, 161, 17, 171, 238, 128, 67, 236, 48, 179, 51, 180, 95, 139, 5, 241, 190, 79, 49, 243, 34, 167, 27, 38], [195, 68, 35, 238, 159, 175, 167, 142, 215, 68, 123, 109, 79, 50, 132, 20, 234, 194, 186, 68, 117, 176, 56, 82, 165, 50, 186, 94, 45, 224, 180, 168], [39, 193, 128, 16, 94, 14, 241, 77, 61, 236, 44, 221, 231, 9, 38, 178, 238, 231, 180, 82, 217, 82, 71, 175, 203, 118, 250, 151, 64, 108, 129, 85], [185, 173, 244, 63, 126, 140, 81, 124, 122, 106, 19, 152, 115, 36, 141, 241, 233, 164, 117, 90, 66, 194, 230, 248, 63, 200, 106, 54, 200, 12, 232, 142], [154, 35, 168, 146, 110, 108, 191, 69, 200, 82, 106, 137, 203, 167, 125, 94, 148, 145, 166, 29, 178, 0, 193, 152, 147, 61, 25, 81, 130, 52, 213, 33], [181, 58, 2, 191, 60, 200, 206, 196, 147, 147, 249, 92, 47, 171, 44, 30, 200, 228, 128, 89, 141, 16, 33, 146, 55, 152, 19, 137, 11, 23, 149, 8], [215, 147, 208, 189, 103, 89, 50, 21, 60, 40, 156, 100, 11, 162, 147, 93, 202, 15, 174, 88, 19, 1, 199, 163, 190, 132, 121, 93, 46, 225, 116, 171], [33, 116, 111, 115, 39, 118, 109, 164, 228, 173, 69, 65, 22, 31, 104, 234, 151, 155, 136, 16, 205, 140, 60, 6, 132, 111, 209, 245, 132, 183, 98, 148], [184, 170, 164, 87, 216, 69, 152, 92, 130, 187, 222, 42, 35, 73, 136, 162, 142, 80, 77, 182, 149, 232, 63, 59, 162, 73, 31, 243, 184, 197, 85, 163], [231, 166, 58, 222, 128, 31, 9, 239, 168, 135, 180, 140, 212, 0, 185, 200, 149, 202, 157, 59, 204, 154, 194, 224, 210, 92, 151, 62, 57, 250, 5, 20], [42, 109, 190, 147, 155, 216, 238, 208, 202, 218, 97, 60, 176, 197, 119, 68, 8, 4, 104, 38, 71, 129, 204, 216, 108, 76, 61, 132, 25, 169, 30, 231], [78, 27, 126, 164, 167, 210, 10, 117, 130, 116, 39, 182, 25, 156, 91, 81, 151, 242, 233, 43, 34, 95, 172, 41, 186, 245, 187, 245, 96, 35, 82, 192], [65, 137, 2, 198, 199, 36, 246, 103, 178, 65, 143, 121, 245, 208, 229, 175, 39, 216, 47, 65, 204, 123, 40, 142, 213, 55, 230, 45, 122, 41, 120, 166]]
r = [82, 210, 119, 206, 210, 218, 154, 166, 79, 74, 232, 209, 94, 69, 117, 152, 151, 20, 182, 196, 238, 156, 234, 131, 170, 34, 234, 166, 72, 160, 158, 242]

string = "a"*0x20
a = [ord(w) for w in string]

c = [0]*0x20
for n1 in range(0,0x20):
    for n2 in range(0,0x20):
        c[n1] = (c[n1] + a[n2] * b2[n2][n1])
    c[n1] = c[n1] % 251

print(c)

최종적으로 모듈로 연산이 포함된 행렬곱 형태가 완성된다. 모듈로 연산이 포함되어있기 때문에 역연산을 하지 못한다. z3솔버를 돌려도 시간내에 답이 나오지 않기 때문에 sagemath를 이용해야한다.

 

 

 

b = [[246, 188, 243, 67, 37, 242, 112, 89, 188, 146, 32, 65, 44, 49, 43, 219, 226, 19, 17, 18, 130, 215, 75, 97, 91, 196, 132, 120, 93, 81, 107, 181], [58, 52, 222, 233, 14, 66, 210, 81, 234, 52, 24, 64, 172, 207, 14, 167, 168, 98, 33, 104, 165, 84, 197, 10, 237, 114, 198, 212, 27, 191, 101, 39], [217, 136, 221, 141, 147, 200, 154, 85, 115, 1, 81, 3, 0, 248, 22, 182, 193, 177, 248, 2, 209, 48, 41, 243, 58, 22, 217, 212, 244, 199, 63, 200], [173, 154, 25, 72, 22, 174, 154, 140, 15, 153, 129, 108, 170, 142, 73, 72, 211, 22, 120, 169, 214, 154, 198, 53, 244, 232, 76, 85, 210, 142, 240, 193], [210, 233, 124, 15, 209, 79, 199, 12, 214, 147, 234, 14, 72, 107, 39, 16, 11, 77, 17, 81, 84, 130, 167, 157, 218, 40, 226, 218, 169, 16, 104, 65], [224, 124, 196, 9, 201, 247, 51, 197, 107, 37, 177, 169, 141, 223, 162, 44, 141, 138, 56, 106, 129, 107, 142, 210, 119, 205, 230, 249, 189, 124, 126, 82], [7, 245, 50, 148, 27, 37, 8, 114, 28, 191, 245, 22, 104, 29, 103, 59, 34, 205, 62, 226, 183, 147, 161, 197, 213, 156, 83, 164, 73, 26, 84, 169], [116, 43, 212, 139, 82, 97, 9, 152, 178, 123, 45, 137, 158, 33, 114, 164, 172, 34, 170, 219, 97, 152, 31, 65, 33, 118, 230, 36, 38, 118, 238, 64], [199, 140, 97, 125, 186, 250, 247, 1, 144, 52, 199, 99, 72, 134, 60, 225, 205, 107, 82, 99, 101, 102, 1, 52, 143, 133, 213, 157, 75, 148, 197, 210], [18, 62, 222, 174, 121, 82, 241, 172, 47, 75, 129, 245, 175, 226, 220, 71, 21, 134, 127, 154, 12, 19, 175, 246, 155, 111, 170, 108, 41, 198, 208, 137], [117, 103, 131, 238, 209, 81, 127, 171, 249, 73, 81, 12, 199, 217, 57, 54, 146, 194, 123, 107, 244, 55, 98, 162, 103, 20, 84, 178, 0, 173, 165, 8], [160, 129, 57, 56, 236, 188, 139, 110, 10, 155, 61, 89, 123, 23, 72, 31, 142, 78, 143, 188, 229, 165, 208, 233, 184, 27, 82, 149, 71, 196, 236, 198], [27, 182, 59, 1, 62, 115, 236, 82, 39, 98, 237, 97, 9, 161, 206, 120, 188, 62, 137, 54, 222, 37, 70, 119, 171, 171, 212, 10, 204, 96, 153, 74], [191, 122, 23, 14, 94, 128, 158, 66, 23, 132, 109, 205, 113, 153, 213, 110, 144, 181, 52, 2, 236, 166, 106, 145, 231, 53, 157, 246, 237, 248, 52, 152], [158, 108, 136, 189, 120, 97, 214, 48, 112, 215, 113, 170, 213, 134, 100, 96, 50, 153, 151, 107, 23, 168, 250, 11, 238, 195, 142, 228, 205, 127, 135, 190], [238, 35, 198, 231, 55, 204, 195, 20, 232, 110, 130, 21, 92, 52, 219, 231, 236, 7, 244, 55, 209, 87, 66, 226, 95, 133, 99, 82, 58, 240, 111, 172], [243, 60, 63, 84, 163, 6, 245, 5, 93, 5, 121, 13, 140, 74, 50, 210, 229, 8, 112, 74, 127, 171, 238, 11, 146, 5, 62, 226, 96, 225, 22, 112], [211, 17, 125, 147, 249, 70, 205, 19, 60, 50, 60, 2, 34, 209, 223, 82, 18, 0, 139, 210, 94, 56, 111, 97, 243, 202, 3, 94, 104, 4, 169, 56], [116, 113, 29, 66, 106, 79, 226, 136, 175, 183, 42, 194, 108, 40, 85, 127, 137, 239, 49, 28, 148, 226, 155, 229, 117, 8, 86, 198, 23, 142, 54, 140], [147, 215, 9, 124, 122, 36, 195, 5, 50, 161, 17, 171, 238, 128, 67, 236, 48, 179, 51, 180, 95, 139, 5, 241, 190, 79, 49, 243, 34, 167, 27, 38], [195, 68, 35, 238, 159, 175, 167, 142, 215, 68, 123, 109, 79, 50, 132, 20, 234, 194, 186, 68, 117, 176, 56, 82, 165, 50, 186, 94, 45, 224, 180, 168], [39, 193, 128, 16, 94, 14, 241, 77, 61, 236, 44, 221, 231, 9, 38, 178, 238, 231, 180, 82, 217, 82, 71, 175, 203, 118, 250, 151, 64, 108, 129, 85], [185, 173, 244, 63, 126, 140, 81, 124, 122, 106, 19, 152, 115, 36, 141, 241, 233, 164, 117, 90, 66, 194, 230, 248, 63, 200, 106, 54, 200, 12, 232, 142], [154, 35, 168, 146, 110, 108, 191, 69, 200, 82, 106, 137, 203, 167, 125, 94, 148, 145, 166, 29, 178, 0, 193, 152, 147, 61, 25, 81, 130, 52, 213, 33], [181, 58, 2, 191, 60, 200, 206, 196, 147, 147, 249, 92, 47, 171, 44, 30, 200, 228, 128, 89, 141, 16, 33, 146, 55, 152, 19, 137, 11, 23, 149, 8], [215, 147, 208, 189, 103, 89, 50, 21, 60, 40, 156, 100, 11, 162, 147, 93, 202, 15, 174, 88, 19, 1, 199, 163, 190, 132, 121, 93, 46, 225, 116, 171], [33, 116, 111, 115, 39, 118, 109, 164, 228, 173, 69, 65, 22, 31, 104, 234, 151, 155, 136, 16, 205, 140, 60, 6, 132, 111, 209, 245, 132, 183, 98, 148], [184, 170, 164, 87, 216, 69, 152, 92, 130, 187, 222, 42, 35, 73, 136, 162, 142, 80, 77, 182, 149, 232, 63, 59, 162, 73, 31, 243, 184, 197, 85, 163], [231, 166, 58, 222, 128, 31, 9, 239, 168, 135, 180, 140, 212, 0, 185, 200, 149, 202, 157, 59, 204, 154, 194, 224, 210, 92, 151, 62, 57, 250, 5, 20], [42, 109, 190, 147, 155, 216, 238, 208, 202, 218, 97, 60, 176, 197, 119, 68, 8, 4, 104, 38, 71, 129, 204, 216, 108, 76, 61, 132, 25, 169, 30, 231], [78, 27, 126, 164, 167, 210, 10, 117, 130, 116, 39, 182, 25, 156, 91, 81, 151, 242, 233, 43, 34, 95, 172, 41, 186, 245, 187, 245, 96, 35, 82, 192], [65, 137, 2, 198, 199, 36, 246, 103, 178, 65, 143, 121, 245, 208, 229, 175, 39, 216, 47, 65, 204, 123, 40, 142, 213, 55, 230, 45, 122, 41, 120, 166]]
r = [82, 210, 119, 206, 210, 218, 154, 166, 79, 74, 232, 209, 94, 69, 117, 152, 151, 20, 182, 196, 238, 156, 234, 131, 170, 34, 234, 166, 72, 160, 158, 242]

R = IntegerModRing(251)
m1 = matrix(R,b)
m2 = matrix(R,r)

rs = m2*(~m1)

flag = ''
for x in rs[0]:
    flag += chr(int(x))

print(flag)

sagemath를 이용하면 모듈로 행렬의 역행렬을 구할 수 있다. 일반적인 실수에서 아래의 식이 성립하듯이 행렬에서도 동일한 식이 성립한다.

• A * B = C 
• B의 역수 * C = A
• 행렬 m1 * 행렬 m2 = 행렬 m3
• m2의 역행렬 * 행렬 m3 = 행렬 m1

 

따라서 행렬 a * 행렬 b = 행렬 r 을 만족하는 행렬 a, 즉 flag를 구할 수 있다.

 

flag