publicclassMain { int kmatrix[][]; int tmatrix[]; int rmatrix[]; publicvoiddiv(String temp, int size) { while (temp.length() > size) { String substr = temp.substring(0, size); temp = temp.substring(size, temp.length()); perf(substr); } if (temp.length() == size) perf(temp); elseif (temp.length() < size) { for (int i = temp.length(); i < size; i++) temp = temp + 'x'; perf(temp); } } publicvoidperf(String text) { textconv(text); multiply(text.length()); res(text.length()); } publicvoidkeyconv(String key, int len) { kmatrix = newint[len][len]; int c = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { kmatrix[i][j] = ((int) key.charAt(c)) - 97; c++; } } } publicvoidtextconv(String text) { tmatrix = newint[text.length()]; for (int i = 0; i < text.length(); i++) { tmatrix[i] = ((int) text.charAt(i)) - 97; } } publicvoidmultiply(int len) { rmatrix = newint[len]; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { rmatrix[i] += kmatrix[i][j] * tmatrix[j]; } rmatrix[i] %= 26; } } publicvoidres(int len) { String res = ""; for (int i = 0; i < len; i++) { res += (char) (rmatrix[i] + 97); } System.out.print(res); } publicstaticvoidmain(String[] args) { Main obj = new Main(); System.out.println("Enter the plain text: "); String text = "fakeflag"; System.out.println(text); System.out.println("Enter the key: "); String key = "gybnqkurp"; System.out.println(key); double root = Math.sqrt(key.length()); if (root != (long) root) System.out.println("Invalid key length."); else { int size = (int) root; System.out.println("Encrypted text = "); obj.keyconv(key, size); obj.div(text, size); } } }

To summarize, it takes the key gybnqkurp, converts it into a 3x3 matrix and encodes each block of three characters by taking the dot product of the block with each row of the key matrix modulo 26. To reverse this, the easiest idea I could come up with was to simply iterate through all possible blocks of size 3 (totalling 26^{3} = 17576) for each block of the ciphertext, encrypt it and see if it matches with the ciphertext block. While I didn't attempt to rigorously prove this, the idea was that the number of pre-images for each ciphertext block would be low, so I could manually pick out the correct plaintext blocks. Luckily (or not, I'm still not sure), each ciphertext block corresponded to exactly one plaintext block.

import string cipher = 'lrzlhhombgichae' key = 'gybnqkurp' defencrypt(text, key): keylist = [] for c in key: keylist.append(ord(c) - ord('a')) textlist = [] for i in range(3): for c in text: textlist.append(ord(c) - ord('a')) ret = '' for i in range(3): temp = 0 for j in range(3): ind = i*3 + j temp += keylist[ind]*textlist[ind] ret += chr(temp%26 + ord('a')) return ret cipher = [cipher[i:i+3] for i in range(0, len(cipher), 3)] for s in cipher: for a1 in string.ascii_lowercase: for a2 in string.ascii_lowercase: for a3 in string.ascii_lowercase: if encrypt(a1+a2+a3, key) == s: print(a1+a2+a3, end = '')

The output was hillshaveeyesxx, where x is for padding. Removing the padding and wrapping the rest in the flag format gave the final flag.