aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorkaiwu <kaiwu2004@gmail.com>2023-01-22 20:35:49 +0800
committerkaiwu <kaiwu2004@gmail.com>2023-01-22 20:35:49 +0800
commitc2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa (patch)
tree6013053b1b18d50b3fadb47eec859c8a1cf91baa /src
parentc0de24475bcb8231d951ca894c3717ec4aa3080a (diff)
downloadadvent-of-code-c2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa.tar.gz
advent-of-code-c2dcf1ccfc1c8153e1b8ed0c48783c1edd4ef6aa.zip
2016 day14 part1
Diffstat (limited to 'src')
-rw-r--r--src/2016/day14/README.md27
-rw-r--r--src/2016/day14/aoc.cpp19
-rw-r--r--src/2016/day14/aoc.h2
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);
}