Cryptopals 1/3 - Single-byte XOR cipher

W tym poście chciałbym opisać rozwiązania zadania 1/3 z Cryptopals. 

Dane podane w zadaniu zostały zakodowane z użyciem jednego bajtu. Należy znaleść wartością, jaką dane zostały zakodowane.

Szyfr jednobajtowy jest to prosty sposób szyfrowania danych. Jeden bajt danych jest modyfikowany przy użyciu jednego, i tego samego, bajtu klucza. Zwykle stosuje się operacje XOR, dodawanie lub odejmowanie wartości czy przesunięcia bitowe. W związku z tym, że jest to szyfr jednobajtowy to klucz może przyjąć maksymalnie wartość 255 (256 możliwości). Z tego powodu jego zadanie polega głównie na maskowaniu danych. 

W zadaniu chodzi o wykorzystanie tzw. Scoringu. Czyli sprawdzaniu który tekst po zdekodowaniu zdobędzie najwięcej punktów. Każda z liter ma przypisaną odpowiednią wagę. Zadanie jest w języku angielskim, więc potrzebne są wartości dla najczęściej stosowanych liter/znaków w tym języku.

Zacznę od prostego programu w języku Python zliczającego poszczególne punkty. Poniżej lista najczęściej występujących znaków razem z punktami przewidzianymi dla każdej z liter. 

1. letter_frequencies = {
2.     'E': 12.70, 'T': 9.06, 'A': 8.17, 'O': 7.51,
3.     'I': 6.97, 'N': 6.75, 'S': 6.33, 'H': 6.09,
4.     'R': 5.99, 'D': 4.25, 'L': 4.03, 'C': 2.78,
5.     'U': 2.76, 'M': 2.41, 'W': 2.36, 'F': 2.23,
6.     'G': 2.02, 'Y': 1.97, 'P': 1.93, 'B': 1.49,
7.     'V': 0.98, 'K': 0.77, 'J': 0.15, 'X': 0.15,
8.     'Q': 0.10, 'Z': 0.07, ' ': 13.00
9. }

Cały program wygląda następująco:

1. hex_data = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
2. data = bytes.fromhex(hex_data)
3.  
4. letter_frequencies = {
5.     'E': 12.70, 'T': 9.06, 'A': 8.17, 'O': 7.51,
6.     'I': 6.97, 'N': 6.75, 'S': 6.33, 'H': 6.09,
7.     'R': 5.99, 'D': 4.25, 'L': 4.03, 'C': 2.78,
8.     'U': 2.76, 'M': 2.41, 'W': 2.36, 'F': 2.23,
9.     'G': 2.02, 'Y': 1.97, 'P': 1.93, 'B': 1.49,
10.     'V': 0.98, 'K': 0.77, 'J': 0.15, 'X': 0.15,
11.     'Q': 0.10, 'Z': 0.07, ' ': 13.00
12. }
13.  
14. def score_english_advanced(text):
15.     score = 0
16.     for byte in text:
17.         try:
18.             char = chr(byte).upper()
19.             score += letter_frequencies.get(char, 0)
20.         except:
21.             pass
22.     return score
23.  
24. best_score = 0
25. best_key = None
26. best_result = b""
27.  
28. print(f"{'klucz':>5} | {'punkty':>7} ")
29. print("-" * 15)
30.  
31. for key in range(256):
32.     decoded = bytes([b ^ key for b in data])
33.     try:
34.         decoded.decode("ascii")
35.         score = score_english_advanced(decoded)
36.         print(f"  {key:02X}  | {score:7.2f}")
37.         if score > best_score:
38.             best_score = score
39.             best_key = key
40.             best_result = decoded
41.     except:
42.         continue
43.  
44. print("\nNajwiecej punktow z klucza:", hex(best_key))
45. print("Tekst z zastosowanym kluczem:", best_result.decode("ascii"))

Na samym początku definiujemy ciąg znaków jako string. Dalej konwertuje go na bajty. W kolejnym kroku sprawdzam czętotliwość występowania liter w języku angielskim. Wszystkie podstawowe znaki oraz spacja. Ta ostatnia jest najwyżej punktowana ponieważ występuje najczęściej w każdym tekście. Następnie sprawdzam XOR na każdym bajcie dla wprowadzonych znaków. Po tej operacji obliczana jest suma punktów dla każdej wartości. Odszyfrowany wynik będzie prawdopodobnie szukanym tekstem. 

Program wyświetla następujący wynik działania:

1. klucz |  punkty
2. ---------------
3.   0x00  |    0.90
4.   0x01  |   11.82
5.   0x02  |    0.42
6.   0x03  |    0.00
7.   0x04  |    0.00
8.   0x05  |    0.07
9.   0x06  |    1.97
10.   0x07  |    0.15
11.   0x08  |   26.94
12.   0x09  |    1.58
13.   0x0A  |   38.70
14.   0x0B  |   60.04
15.   0x0C  |   60.69
16.   0x0D  |   35.55
17.   0x0E  |    5.98
18.   0x0F  |   16.09
19.   0x10  |   44.05
20.   0x11  |   74.57
21.   0x12  |    3.31
22.   0x13  |   34.65
23.   0x14  |   37.95
24.   0x15  |   14.61
25.   0x16  |   86.47
26.   0x17  |  116.15
27.   0x18  |    2.02
28.   0x19  |   77.25
29.   0x1A  |   34.64
30.   0x1B  |   33.93
31.   0x1C  |   41.28
32.   0x1D  |   90.69
33.   0x1E  |   34.55
34.   0x1F  |   25.12
35.   0x20  |    0.90
36.   0x21  |   11.82
37.   0x22  |    0.42
38.   0x23  |    0.00
39.   0x24  |    0.00
40.   0x25  |    0.07
41.   0x26  |    1.97
42.   0x27  |    0.15
43.   0x28  |   13.94
44.   0x29  |    1.58
45.   0x2A  |   38.70
46.   0x2B  |   47.04
47.   0x2C  |   60.69
48.   0x2D  |   22.55
49.   0x2E  |    5.98
50.   0x2F  |   16.09
51.   0x30  |   44.05
52.   0x31  |   48.57
53.   0x32  |    3.31
54.   0x33  |    8.65
55.   0x34  |   24.95
56.   0x35  |   27.61
57.   0x36  |   47.47
58.   0x37  |   51.15
59.   0x38  |    2.02
60.   0x39  |   51.25
61.   0x3A  |   21.64
62.   0x3B  |   46.93
63.   0x3C  |   28.28
64.   0x3D  |   77.69
65.   0x3E  |   21.55
66.   0x3F  |   12.12
67.   0x40  |   52.70
68.   0x41  |   51.30
69.   0x42  |   77.87
70.   0x43  |   88.93
71.   0x44  |   82.59
72.   0x45  |   88.49
73.   0x46  |   40.97
74.   0x47  |   56.23
75.   0x48  |   59.76
76.   0x49  |   57.67
77.   0x4A  |   45.67
78.   0x4B  |   38.48
79.   0x4C  |   44.70
80.   0x4D  |   55.17
81.   0x4E  |   64.49
82.   0x4F  |   60.74
83.   0x50  |   92.89
84.   0x51  |   73.28
85.   0x52  |  153.68
86.   0x53  |  112.97
87.   0x54  |  106.03
88.   0x55  |   86.87
89.   0x56  |  114.82
90.   0x57  |   83.79
91.   0x58  |  216.11
92.   0x59  |  118.80
93.   0x5A  |  113.60
94.   0x5B  |   95.71
95.   0x5C  |   94.85
96.   0x5D  |   73.00
97.   0x5E  |  142.78
98.   0x5F  |  146.60
99.   0x60  |   52.70
100.   0x61  |   51.30
101.   0x62  |   77.87
102.   0x63  |   88.93
103.   0x64  |   82.59
104.   0x65  |   88.49
105.   0x66  |   40.97
106.   0x67  |   56.23
107.   0x68  |   59.76
108.   0x69  |   57.67
109.   0x6A  |   45.67
110.   0x6B  |   38.48
111.   0x6C  |   44.70
112.   0x6D  |   55.17
113.   0x6E  |   64.49
114.   0x6F  |   60.74
115.   0x70  |   92.89
116.   0x71  |   73.28
117.   0x72  |  153.68
118.   0x73  |  112.97
119.   0x74  |  106.03
120.   0x75  |   86.87
121.   0x76  |  114.82
122.   0x77  |   83.79
123.   0x78  |  138.11
124.   0x79  |  118.80
125.   0x7A  |  113.60
126.   0x7B  |   95.71
127.   0x7C  |   94.85
128.   0x7D  |   73.00
129.   0x7E  |  142.78
130.   0x7F  |  133.60
131.  
132. Najwiecej punktow z klucza: 0x58
133. Tekst z zastosowanym kluczem: Cooking MC's like a pound of bacon

W C można przygotować podobny program:

1. #include <stdio.h>
2. #include <string.h>
3. #include <ctype.h>
4. #include <stdlib.h>
5.  
6. #define HEX_DATA "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
7.  
8. double letter_frequencies[256] = {
9.     ['E'] = 12.70, ['T'] = 9.06, ['A'] = 8.17, ['O'] = 7.51, ['I'] = 6.97,
10.     ['N'] = 6.75, ['S'] = 6.33, ['H'] = 6.09, ['R'] = 5.99, ['D'] = 4.25,
11.     ['L'] = 4.03, ['C'] = 2.78, ['U'] = 2.76, ['M'] = 2.41, ['W'] = 2.36,
12.     ['F'] = 2.23, ['G'] = 2.02, ['Y'] = 1.97, ['P'] = 1.93, ['B'] = 1.49,
13.     ['V'] = 0.98, ['K'] = 0.77, ['J'] = 0.15, ['X'] = 0.15, ['Q'] = 0.10,
14.     ['Z'] = 0.07, [' '] = 13.00
15. };
16.  
17. int hex_to_bytes(const char *hex, unsigned char *out_bytes) {
18.     size_t len = strlen(hex);
19.     int count = 0;
20.  
21.     for (size_t i = 0; i < len; i += 2) {
22.         sscanf(hex + i, "%2hhx", &out_bytes[count]);
23.         count++;
24.     }
25.  
26.     return count;
27. }
28.  
29. double score_english(unsigned char *text, int length) {
30.     double score = 0.0;
31.  
32.     for (int i = 0; i < length; i++) {
33.         unsigned char c = toupper(text[i]);
34.         if (c < 256) {
35.             score += letter_frequencies[c];
36.         }
37.     }
38.  
39.     return score;
40. }
41.  
42. int main() {
43.     unsigned char data[128];
44.     int data_len = hex_to_bytes(HEX_DATA, data);
45.  
46.     double best_score = 0.0;
47.     unsigned char best_key = 0;
48.     unsigned char best_result[128] = {0};
49.  
50.     printf("%5s | %7s\n", "klucz", "punkty");
51.     printf("-----------\n");
52.  
53.     for (int key = 0; key < 256; key++) {
54.         unsigned char decoded[128] = {0};
55.  
56.         int valid_ascii = 1;
57.  
58.         for (int i = 0; i < data_len; i++) {
59.             decoded[i] = data[i] ^ key;
60.             if (decoded[i] < 32 || decoded[i] > 126) {
61.                 if (decoded[i] != ' ' && decoded[i] != '\n') {
62.                     valid_ascii = 0;
63.                     break;
64.                 }
65.             }
66.         }
67.  
68.         if (!valid_ascii) continue;
69.  
70.         double score = score_english(decoded, data_len);
71.         printf("  0x%02X | %7.2f\n", key, score);
72.  
73.         if (score > best_score) {
74.             best_score = score;
75.             best_key = key;
76.             memcpy(best_result, decoded, data_len);
77.             best_result[data_len] = '\0';
78.         }
79.     }
80.  
81.     printf("\nNajwiecej punktow z klucza: 0x%02X\n", best_key);
82.     printf("Tekst z zastosowanym kluczem: %s\n", best_result);
83.  
84.     return 0;
85. }

Wynik jego działania będzie identyczny jak w przypadku programu w Python.