· 4 years ago · Jan 19, 2021, 06:54 PM
1#include <algorithm>
2#include <array>
3#include <iostream>
4#include <string>
5#include <fstream>
6#include <vector>
7#include <numeric>
8#include <unordered_map>
9#include <ranges>
10
11// shifts all non-whitespace characters in str
12// negative amounts shift backwards
13auto shifter(std::string str, int amount) -> std::string
14{
15 if (amount < 0)
16 amount = 26+(amount %26);
17
18 for (char& c : str)
19 {
20 if (c != '\n' && c != ' ')
21 c = ((c-'A')+amount)%26+'A';
22 }
23 return str;
24}
25
26// substitutes all characters in the string according to the specified mapping.
27// the mapping is assumed to be injective from A to B
28template<typename A, typename B>
29auto encrypt_substitution(std::string str, const std::unordered_map<A,B>& mapping) -> std::string
30{
31 for (char& c : str)
32 {
33 c = mapping.at(c);
34 }
35 return str;
36}
37
38// substitutes all characters in the string according to an inverse of the mapping.
39// the mapping is assumed to be injective from A to B
40template<typename A, typename B>
41auto decrypt_substitution(std::string str, const std::unordered_map<A,B>& mapping) -> std::string
42{
43 const auto inverse_map = [&mapping] {
44 auto out = std::unordered_map<B,A>();
45 for (auto& [first,second] : mapping)
46 out.insert(std::pair(second,first));
47 return out;
48 }();
49
50 for (char& c : str)
51 {
52 c = inverse_map.at(c);
53 }
54 return str;
55}
56
57// returns a vector of strings, where each string represents
58// a line of a file, i.e. all characters up to a newline character
59auto parse_file(const std::string_view path) -> std::vector<std::string>
60{
61 auto file = std::ifstream(std::string(path));
62 auto vec = std::vector<std::string>();
63
64 std::string tmp;
65 while (std::getline(file, tmp))
66 {
67 vec.push_back(tmp);
68 }
69
70 if (vec.empty())
71 {
72 throw std::runtime_error{"File empty or non-existent"};
73 }
74 return vec;
75}
76
77auto stat1_aufgabe1() -> void
78{
79 const auto vec = parse_file("../data/text2.txt");
80 for (const auto& s : vec)
81 {
82 std::cout << shifter(s, -3) << '\n';
83 }
84}
85
86auto stat2_aufgabe1() -> void
87{
88 const auto vec = parse_file("../data/text3.txt");
89 for (const auto& s : vec)
90 {
91 std::cout << shifter(s, -13) << '\n';
92 }
93}
94
95auto stat3_aufgabe1() -> void
96{
97 const auto mapping = std::unordered_map<char,char>(
98 {
99 {'A','G'}, {'B','K'}, {'C','X'}, {'D','C'},
100 {'E','S'}, {'F','L'}, {'G','Z'}, {'H','U'},
101 {'I','A'}, {'J','H'}, {'K','W'}, {'L','D'},
102 {'M','B'}, {'N','M'}, {'O','T'}, {'P','Y'},
103 {'Q','E'}, {'R','N'}, {'S','J'}, {'T','V'},
104 {'U','P'}, {'V','O'}, {'W','I'}, {'X','R'},
105 {'Y','F'}, {'Z','Q'}
106 });
107
108 std::cout << encrypt_substitution("HALLOASTERIX", mapping) << '\n';
109 std::cout << decrypt_substitution("JGDOSXGSJGN", mapping) << '\n';
110}
111
112// returns an array containing the relative frequency of each
113// member of the alphabet. idx 0->A, idx1->B,..., idx 25->Z
114auto get_alphabet_distr(const std::string_view s)
115{
116 auto distribution = std::array<double, 26>();
117 for (auto c = 'A'; c <= 'Z'; ++c)
118 {
119 auto count = std::count(s.begin(), s.end(), c);
120 distribution[c-'A'] = static_cast<double>(count)/s.size();
121 }
122 return distribution;
123}
124
125auto stat4_aufgabe1() -> void
126{
127 auto text = parse_file("../data/station4-secrettext.txt")[0];
128
129 auto distribution = std::array<double, 26>();
130 for (auto c = 'A'; c <= 'Z'; ++c)
131 {
132 auto count = std::count(text.begin(), text.end(), c);
133 distribution[c-'A'] = static_cast<double>(count)/text.size();
134 }
135 for (unsigned i=0; i<distribution.size(); ++i)
136 {
137 std::cout << static_cast<char>(i+'A') << ": " << distribution[i]*100 << '%' << '\n';
138 }
139
140 const auto mapping = std::unordered_map<char,char>(
141 {
142 {'A','G'}, {'B','K'}, {'C','X'}, {'D','C'},
143 {'E','S'}, {'F','L'}, {'G','Z'}, {'H','U'},
144 {'I','A'}, {'J','H'}, {'K','W'}, {'L','D'},
145 {'M','B'}, {'N','M'}, {'O','T'}, {'P','Y'},
146 {'Q','E'}, {'R','N'}, {'S','J'}, {'T','V'},
147 {'U','P'}, {'V','O'}, {'W','I'}, {'X','R'},
148 {'Y','F'}, {'Z','Q'}
149 });
150 std::cout << decrypt_substitution(text, mapping) << '\n';
151}
152
153constexpr auto generate_vigenere_square() -> std::array<std::array<char, 26>, 26>
154{
155 auto out = std::array<std::array<char, 26>, 26>();
156 for (unsigned i=0; i<26; ++i)
157 {
158 for (unsigned j=0; j<26; ++j)
159 {
160 out[i][j] = j+'A';
161 }
162 std::rotate(out[i].begin(), out[i].begin()+i, out[i].end());
163 }
164 return out;
165}
166
167// assumes key is valid, i.e. more than 0 uppercase-only ASCII characters
168auto encrypt_vigenere(std::string s, const std::string_view key) -> std::string
169{
170 constexpr auto vigenere_square = generate_vigenere_square();
171
172 // pad key
173 std::string padded_key;
174 for (unsigned i=0; i<s.size(); ++i)
175 {
176 padded_key += key[i%key.size()] ;
177 }
178
179 for (unsigned i=0; i<s.size(); ++i)
180 {
181 s[i] = vigenere_square[s[i]-'A'][padded_key[i]-'A'];
182 }
183
184 return s;
185}
186
187// assumes key is valid, i.e. more than 0 uppercase-only ASCII characters
188auto decrypt_vigenere(std::string encrypted, const std::string_view key) -> std::string
189{
190 constexpr auto vigenere_square = generate_vigenere_square();
191
192 // pad key
193 std::string padded_key;
194 for (unsigned i=0; i<encrypted.size(); ++i)
195 {
196 padded_key += key[i%key.size()] ;
197 }
198 for (unsigned i=0; i<padded_key.size(); ++i)
199 {
200 for (unsigned x=0; x<26; ++x)
201 {
202 if (encrypted[i] == vigenere_square[padded_key[i]-'A'][x])
203 {
204 encrypted[i] = vigenere_square[0][x];
205 break;
206 }
207 }
208 }
209 return encrypted;
210}
211
212auto stat5_aufgabe1() -> void
213{
214 std::cout << encrypt_vigenere("HALLOWIEGEHTS", "ESEL") << '\n';
215 std::cout << decrypt_vigenere("LMSXEGXTXUS", "ZEBRA") << '\n';
216}
217
218auto kasiki_break_secretkey(const std::string_view encrypted, unsigned key_length)
219{
220 const auto columns = [&encrypted, key_length] {
221 auto out = std::vector<std::string>();
222 auto tmp = std::string();
223 for (auto i=0u; i<key_length; ++i)
224 {
225 unsigned j=i;
226 while (j<encrypted.size())
227 {
228 tmp += encrypted[j];
229 j+=key_length;
230 }
231 out.push_back(tmp);
232 tmp = {};
233 }
234 return out;
235 }();
236
237 // we can now map the letter with the highest relative frequency
238 // to E, as per the https://de.wikipedia.org/wiki/Buchstabenh%C3%A4ufigkeit
239 // and index the vigenere_square accordingly to reconstruct the secret key
240
241 auto vigenere_square = generate_vigenere_square();
242 auto secret_key = std::string();
243
244 for (const auto& c : columns)
245 {
246 auto distr = get_alphabet_distr(c);
247 char mapping = static_cast<char>(std::distance(distr.begin(), std::ranges::max_element(distr)) + 'A');
248
249 for (auto x=0u; x<26; ++x)
250 {
251 if (vigenere_square['E'-'A'][x] == mapping)
252 {
253 secret_key += vigenere_square[0][x];
254 break;
255 }
256 }
257 }
258
259 return secret_key;
260}
261
262auto stat6_aufgabe() -> void
263{
264 const auto encrypted = [] {
265 auto vec = parse_file("../data/station6-encryptedtext.txt");
266 return std::accumulate(vec.begin(), vec.end(), std::string());
267 }();
268
269 // repeated substrings imply that the key length
270 // is likely to be 5
271 constexpr unsigned key_length = 5;
272 auto secret_key = kasiki_break_secretkey(encrypted, key_length);
273
274 std::cout << "Reconstructed secret key: " << secret_key << '\n'
275 << "Applying secret key to encrypted sequence..\n" << '\n';
276
277 std::cout << decrypt_vigenere(encrypted, secret_key) << '\n';
278}
279
280auto main() -> int
281try
282{
283 //std::cout << "Station 1\n";
284 //stat1_aufgabe1();
285
286 //std::cout << "Station 2\n";
287 //stat2_aufgabe1();
288 //
289 //std::cout << "Station 3\n";
290 //stat3_aufgabe1();
291 //
292 //std::cout << "Station 4\n";
293 //stat4_aufgabe1();
294 //
295 //std::cout << "Station 5\n";
296 //stat5_aufgabe1();
297 //
298 std::cout << "Station 6\n";
299 stat6_aufgabe();
300}
301catch (std::runtime_error& ex)
302{
303 std::cout << "CAUGHT EXCEPTION: " << ex.what() << '\n';
304 return 1;
305}