[RCTF 2022] magicsign

I don't understand the exact sign & verify logic. However, self.U has only 9 different elements(4, 11, 18, 24, 26, 78, 81, 133, 135). So it requires the only $O(2^{27})$ bruteforce. To speed-up, rather than run 18770 iterations in mix, run 280 iterations and check the validity first.

#include <bits/stdc++.h>
using namespace std;

const int U_SIZE = 18770;

const int Square[8][8] = {{5, 3, 1, 6, 7, 2, 0, 4},
                      {3, 5, 0, 2, 4, 6, 1, 7},
                      {6, 2, 4, 5, 0, 3, 7, 1},
                      {4, 7, 6, 1, 3, 0, 2, 5},
                      {0, 1, 3, 7, 6, 4, 5, 2},
                      {7, 4, 2, 0, 5, 1, 6, 3},
                      {2, 6, 7, 3, 1, 5, 4, 0},
                      {1, 0, 5, 4, 2, 7, 3, 6}};

const int U[U_SIZE] = {...}; // omitted since too long

int U_index_change[U_SIZE];
// 4, 11, 24, 26, 81, 135, 18, 78, 133
// 0, 1,  2,  3,  4,  5    6   7   8
void preprocess(){
  for(int i = 0; i < U_SIZE; i++){
    if(U[i] == 4) U_index_change[i] = 0;
    if(U[i] == 11) U_index_change[i] = 1;
    if(U[i] == 24) U_index_change[i] = 2;
    if(U[i] == 26) U_index_change[i] = 3;
    if(U[i] == 81) U_index_change[i] = 4;
    if(U[i] == 135) U_index_change[i] = 5;
    if(U[i] == 18) U_index_change[i] = 6;
    if(U[i] == 78) U_index_change[i] = 7;
    if(U[i] == 133) U_index_change[i] = 8;    
  }
}

vector<int> mix_extract(vector<int>& T, vector<int>& K, int STEP){
  vector<int> R = T;
  // R = T + K 
  for(int i = 0; i < 9; i++){
    R[i] = Square[T[i]][K[i]];
  }

  for(int i = 1; i <= STEP; i++){
    R[U_index_change[i]] = Square[R[U_index_change[i]]][R[U_index_change[i-1]]];
  }


  for(int i = 0; i < 9; i++){
    R[i] = Square[R[i]][K[i]];
  }
  return R;
}




vector<int> str2vec(string& s){
  vector<int> v;
  for(int i = 0; i < 137; i++){
    v.push_back((int)(s[i] - '0'));
  }
  return v;
}

vector<int> extract_idx(vector<int>& seq){
  vector<int> v;
  v.push_back(seq[4]);
  v.push_back(seq[11]);
  v.push_back(seq[24]);
  v.push_back(seq[26]);
  v.push_back(seq[81]);
  v.push_back(seq[135]);
  v.push_back(seq[18]);
  v.push_back(seq[78]);
  v.push_back(seq[133]);
  return v;
}

string H1 = "00000000073472356175477321551613606604160747333127567726571101035745120413223147437457476323022700377634720722606501264707047017336370411";

string H2 = "00000000010711433446247704254623443435554621674653377332336216767200574302543717156504476701206620635345005461427376656032425232342514535";

string S = "02306223007703364406103766161140574436562753732537140704106536206016103512323630130667624207000200703404070320636506361303717760305304121";

bool total_valid_check(vector<int>& Q_cand){
  auto H1_vec = str2vec(H1);
  auto H1_vec_extract = extract_idx(H1_vec);
  auto S_vec = str2vec(S);
  auto S_vec_extract = extract_idx(S_vec);

  auto S_test = mix_extract(H1_vec_extract, Q_cand, 18769);


  return S_test == S_vec_extract;


}

void solve(){
  auto H1_vec = str2vec(H1);
  auto H1_vec_extract = extract_idx(H1_vec);
  auto S_vec = str2vec(S);
  auto S_vec_extract = extract_idx(S_vec);
  cout << "S_Vec_extract ";
  for(auto x : S_vec_extract) cout << x << ' ';
  cout << '\n';

  for(int i = 0; i < (1<<27); i++){
    int brute = i;
    vector<int> Q(9);
    for(int j = 0; j < 9; j++){
      Q[j] = brute & 7;
      brute >>= 3;
    }
    auto S_test = mix_extract(H1_vec_extract, Q, 280);
    if(i % 5000000 == 0){
      cout << i << '\n';          
    }

    bool match = true;
    for(int i = 0; i < 6; i++){
      if(S_test[i] != S_vec_extract[i]){
        match = false;
        break;
      }
    }
    if(match && total_valid_check(Q)){
      cout << "!! ";
      for(auto x : Q) cout << x << ' ';
      cout << '\n';
    }

    // cout << "!!! " << i << ' ';
    // for(auto x : S_test) cout << x;
    // cout << '\n';
  }
}

int main(void){
  preprocess();
  solve();
}