diff options
author | kaiwu <kaiwu2004@gmail.com> | 2023-01-22 20:35:49 +0800 |
---|---|---|
committer | kaiwu <kaiwu2004@gmail.com> | 2023-01-22 20:35:49 +0800 |
commit | c2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa (patch) | |
tree | 6013053b1b18d50b3fadb47eec859c8a1cf91baa /src | |
parent | c0de24475bcb8231d951ca894c3717ec4aa3080a (diff) | |
download | advent-of-code-c2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa.tar.gz advent-of-code-c2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa.zip |
2016 day14 part1
Diffstat (limited to 'src')
-rw-r--r-- | src/2016/day14/README.md | 27 | ||||
-rw-r--r-- | src/2016/day14/aoc.cpp | 19 | ||||
-rw-r--r-- | src/2016/day14/aoc.h | 2 |
3 files changed, 38 insertions, 10 deletions
diff --git a/src/2016/day14/README.md b/src/2016/day14/README.md index b9a680c..485be4a 100644 --- a/src/2016/day14/README.md +++ b/src/2016/day14/README.md @@ -23,3 +23,30 @@ So, using our example salt of abc, index 22728 produces the 64th key. Given the actual salt in your puzzle input, what index produces your 64th one-time pad key? Your puzzle input is jlmsuwbz. + +--- Part Two --- + +Of course, in order to make this process even more secure, you've also implemented key stretching. + +Key stretching forces attackers to spend more time generating hashes. Unfortunately, it forces everyone else to spend more time, too. + +To implement key stretching, whenever you generate a hash, before you use it, you first find the MD5 hash of that hash, then the MD5 hash of that hash, and so on, a total of 2016 additional hashings. Always use lowercase hexadecimal representations of hashes. + +For example, to find the stretched hash for index 0 and salt abc: + + Find the MD5 hash of abc0: 577571be4de9dcce85a041ba0410f29f. + Then, find the MD5 hash of that hash: eec80a0c92dc8a0777c619d9bb51e910. + Then, find the MD5 hash of that hash: 16062ce768787384c81fe17a7a60c7e3. + ...repeat many times... + Then, find the MD5 hash of that hash: a107ff634856bb300138cac6568c0f24. + +So, the stretched hash for index 0 in this situation is a107ff.... In the end, you find the original hash (one use of MD5), then find the hash-of-the-previous-hash 2016 times, for a total of 2017 uses of MD5. + +The rest of the process remains the same, but now the keys are entirely different. Again for salt abc: + + The first triple (222, at index 5) has no matching 22222 in the next thousand hashes. + The second triple (eee, at index 10) hash a matching eeeee at index 89, and so it is the first key. + Eventually, index 22551 produces the 64th key (triple fff with matching fffff at index 22859. + +Given the actual salt in your puzzle input and using 2016 extra MD5 calls of key stretching, what index now produces your 64th one-time pad key? + diff --git a/src/2016/day14/aoc.cpp b/src/2016/day14/aoc.cpp index 364bb5e..d70ff49 100644 --- a/src/2016/day14/aoc.cpp +++ b/src/2016/day14/aoc.cpp @@ -56,16 +56,17 @@ md5_property md5(const char* secret, size_t index) { auto s = md5s.size(); md5s.resize(index + 1); for (size_t i = s; i < md5s.size(); i++) { - sprintf(buf + l, "%zu", index); + sprintf(buf + l, "%zu", i); md5s[i].md5 = std::string(md5sum(buf), 32); auto pc3 = has(md5s[i].md5.c_str(), 3); if (pc3 != nullptr) { md5s[i].c = *pc3; auto pc5 = has(md5s[i].md5.c_str(), 5); if (pc5 != nullptr) { - auto p = has5s.insert({*pc3, {index}}); + // printf("%zu has 5 %c\n", i, *pc3); + auto p = has5s.insert({*pc3, {i}}); if (!p.second) { - p.first->second.push_back(index); + p.first->second.push_back(i); } } } @@ -83,15 +84,15 @@ size_t find_key(int* count, int max) { } i++; } - return i; + return i - 1; } -std::pair<int64_t, int64_t> day14(line_view) { - md5("abc", 30000); - // md5("jlmsuwbz", 30000); +std::pair<size_t, int64_t> day14(line_view) { + // md5("abc", 30000); + + md5("jlmsuwbz", 50000); int count{0}; auto i = find_key(&count, 64); - printf("%zu\n", i); - return {0, 0}; + return {i, 0}; } } // namespace aoc2016 diff --git a/src/2016/day14/aoc.h b/src/2016/day14/aoc.h index 5f77a81..1fec5aa 100644 --- a/src/2016/day14/aoc.h +++ b/src/2016/day14/aoc.h @@ -3,5 +3,5 @@ #include <vector> namespace aoc2016 { -std::pair<int64_t, int64_t> day14(line_view); +std::pair<size_t, int64_t> day14(line_view); } |