The-Climb

点击此处获得更好的阅读体验


WriteUp来源

https://dunsp4rce.github.io/csictf-2020/crypto/2020/07/21/The-Climb.html

by raghul-rajasekar

题目描述

We are not lost, we're right here somewhere on this little blue line. Wait, why do I feel like I'm being watched?

Files:

题目考点

解题思路

Solution

theclimb.java contains the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class Main
{
int kmatrix[][];
int tmatrix[];
int rmatrix[];

public void div(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);
else if (temp.length() < size)
{
for (int i = temp.length(); i < size; i++)
temp = temp + 'x';
perf(temp);
}
}

public void perf(String text)
{
textconv(text);
multiply(text.length());
res(text.length());
}

public void keyconv(String key, int len)
{
kmatrix = new int[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++;
}
}
}

public void textconv(String text)
{
tmatrix = new int[text.length()];
for (int i = 0; i < text.length(); i++)
{
tmatrix[i] = ((int) text.charAt(i)) - 97;
}
}

public void multiply(int len)
{
rmatrix = new int[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;
}
}

public void res(int len)
{
String res = "";
for (int i = 0; i < len; i++)
{
res += (char) (rmatrix[i] + 97);
}
System.out.print(res);
}


public static void main(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 263 = 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import string
cipher = 'lrzlhhombgichae'
key = 'gybnqkurp'
def encrypt(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.

Flag

1
csictf{hillshaveeyes}