Advent of Rust 25: Baby Steps

It’s the final post in the series chronicling my attempt to teach myself the Rust programming language by solving programming puzzles from Advent of Code 2020.

Day 25, Part 1

Today’s puzzle is about cracking an encryption key, in order to get at a piece of secret information (called loop size in the puzzle) by taking a piece of known public information (public key) and reversing the algorithm used to generate it. Of course, the algorithm (called transform subject number) is not easy to reverse, and that’s what the puzzle is about.

The puzzle description suggests guessing the loop size by trial and error which I am skeptical about, but this is the code that would do that by brute force:

fn transform_subject_number(subject_number: u64, loop_size: usize) -> u64 {
    let mut value = 1;
    for _ in 0..loop_size {
        value *= subject_number;
        value %= 20201227;
    }
    value
}

fn guess_loop_size(public_key: u64) -> usize {
    for loop_size in 1.. {
        if transform_subject_number(7, loop_size) == public_key {
            return loop_size;
        }
    }
    panic!("Not reachable");
}

#[derive(Debug)]
struct Party {
    loop_size: usize,
}

impl Party {
    fn public_key(&self) -> u64 {
        transform_subject_number(7, self.loop_size)
    }

    fn encryption_key(&self, other_public_key: u64) -> u64 {
        transform_subject_number(other_public_key, self.loop_size)
    }
}

fn main() {
    let card_public_key = 2084668;
    let door_public_key = 3704642;
    let card = Party {
        loop_size: guess_loop_size(card_public_key),
    };
    let door = Party {
        loop_size: guess_loop_size(door_public_key),
    };
    println!("{}", card.encryption_key(door.public_key()));
}

This is taking a long time. I’m guessing that this is not the way to do it.

I notice that, were it not for integer overflow, we’d be able to write the transform subject number result as S^L (mod 20201227) (where S is the subject number and L is the loop size.) So, the total of what we know is this:

• P_c ≡ 7^L_c (mod 20201227)
• P_d ≡ 7^L_d (mod 20201227)
• P_c^L_d ≡ P_d^L_c (mod 20201227)

where P is the public key, and the subscript c or d indicates card or door. The symbol “≡” means “congruent with” although I had to look it up on Wikipedia. Since I’m not even using all of this information in the trial and error implementation, I’m not surprised that it isn’t working.

I’m sure this is a solved problem, just like the hexagons yesterday, so I start searching (although I’m not sure what to search for, I try things like “modulo inverse”) and eventually land on the Wikipedia article for Modular exponentiation, which explains “the task of finding the exponent […] when given [the base, modular exponentiation, and modulus] is believed to be difficult.” Thanks, I guess…

These pages contain a little too much math all at once for my holiday-addled brain, especially because they confusingly use the notation a⁻¹ to mean… something that’s not 1/a… so I decide to read a bit more on the topic hoping that something will sink in.

Eventually I read the “Modular arithmetic” section on the Wikipedia article for Discrete logarithm and a light begins to dawn. They give an example of how to calculate the possible solutions using Fermat’s Little Theorem.¹ However, this approach turns out not to be useful for me because it already requires knowing one possible solution, and that’s exactly what I don’t have.

I do some more searching and find the Baby-step giant-step algorithm. I would probably have skipped over this if I had just stumbled upon the Wikipedia article without any context (because I don’t know what a finite abelian group is) but I reached it via another site with a bit more explanation of the missing link connecting the problem at hand to the Wikipedia article.²

The problem is of the form a^k ≡ b (mod n), where we have to find k. For the example in the puzzle description, we can fill in: a = 7, b = 17807724, n = 20201227.

The first thing I do is replace transform_subject_number() with a more general pow_m() function using the algorithm that I already have, called the “memory-efficient algorithm” in the Wikipedia article, and check that the tests still pass:

fn pow_m(base: u64, exponent: usize, modulus: u64) -> u64 {
    if modulus == 1 {
        return 0;
    }
    let mut value = 1;
    for _ in 0..exponent {
        value *= base;
        value %= modulus;
    }
    value
}

fn transform_subject_number(subject_number: u64, loop_size: usize) -> u64 {
    pow_m(subject_number, loop_size, 20201227)
}

Then I rewrite pow_m() to use the faster “right-to-left binary” algorithm from the Wikipedia article, and again check that the tests still pass:

fn pow_m(base: u64, exponent: usize, modulus: u64) -> u64 {
    if modulus == 1 {
        return 0;
    }
    let mut value = 1;
    let mut mod_base = base % modulus;
    let mut mod_exponent = exponent;
    while mod_exponent > 0 {
        if mod_exponent % 2 == 1 {
            value *= mod_base;
            value %= modulus;
        }
        mod_exponent >>= 1;
        mod_base *= mod_base;
        mod_base %= modulus;
    }
    value
}

Next I rewrite guess_loop_size() to use the baby-steps giant-steps algorithm, as described by Wikipedia:

fn bsgs(base: u64, modulus: u64, result: u64) -> Option<usize> {
    let m = (modulus as f64).sqrt().ceil() as u64;
    let mut table = HashMap::new();
    let mut e = 1;
    for j in 0..m {
        table.insert(e, j);
        e *= base;
        e %= modulus;
    }
    let factor = pow_m(base, (modulus - m - 1) as usize, modulus);
    let mut gamma = result;
    for i in 0..m {
        if let Some(j) = table.get(&gamma) {
            return Some((i * m + j) as usize);
        }
        gamma *= factor;
        gamma %= modulus;
    }
    None
}

fn guess_loop_size(public_key: u64) -> usize {
    bsgs(7, 20201227, public_key).unwrap()
}

The tests still pass, so that means it correctly handles the example code. I run this, it finishes almost immediately, and I get the right answer.

Day 25, Part 2

I’m not going to spoil the very last puzzle! I solve it without writing any code though.

Afterword

I found this puzzle one of the most difficult ones, as I’m not really into cryptography, and it required quickly getting acquainted with an area of mathematics that I had never encountered before. I don’t even think it would have been possible for me to do it, if I hadn’t had enough experience in other areas of mathematics that I at least knew some search terms that brought me in the right direction.

It was difficult in a different way than the image-assembly puzzle on Day 20, though; that one was more like, you could easily see what needed to be done, but it was so tedious to get right. The hard part today was to find out what needed to be done, and once I had landed on the right Wikipedia page with an explanation of the algorithm, it was simple enough to implement. In a way it was similar to yesterday’s hexagons, but the topic of modular discrete logarithms was so much more difficult to absorb quickly than the topic of hexagons was.

Reflections on the Whole Thing

How do I feel about doing 50 puzzles in the past 28 days?
First of all, if I do this again, I’m not going to keep up this pace and I’m not going to blog about it. It was fun while it lasted, but it’s really quite time-consuming, and it’s not even over yet — Rust is open source, so I have practically obligated myself in January to do the right thing and follow through with submitting all the suggestions for improvement of the Rust tools that I can glean from the earlier posts in the series.

I enjoyed the VM-like puzzles the most, after that the parser ones,³ and after that the ones that could be solved with interesting uses of iterators and Itertools. The cryptography puzzles like today’s, I didn’t enjoy that much. I appreciated that there were so many Game of Life variations as an homage to Conway who passed away this year, but as puzzles they were not so interesting; after I wrote the code to solve one, I basically just copied it for the subsequent puzzles. Conway’s Game of Life is so mesmerizing when you can watch it evolving, but since it wasn’t necessary for solving the puzzle I didn’t really feel like spending time building visualizations.

I didn’t find the Reddit board very helpful unless I was actively looking for a hint from the hint threads, or looking for other people’s visualizations of the Game of Life puzzles. Reading all the posts from people who knew exactly the right algorithm to use, or solved the puzzle in mere minutes, or made fantastic visualizations, made me feel inadequate. Even though there were a few of these puzzles that I thought I did very well at, there were always people on the Reddit board who did better.⁴

Can I program in Rust now?
I’m not sure. Probably not. I know just enough that I should now go and read the Rust book, and I will get much more out of it than I would have if I had started out by reading the book.

Would I recommend learning Rust?
Certainly I found it very rewarding. It’s refreshing to see how they designed it to avoid or mitigate common classes of mistakes. Its tools and its standard library were a pleasure to use. That said, I would mainly recommend learning it if you are already experienced in another programming language. Put another way, I found learning Rust while knowing C++ as a reference point to be comparable to (what I imagine is the experience of) learning C++ while knowing JavaScript as a reference point. The things that you already know from the other language do serve you well, and give you a better footing in the new language, but there are also many new concepts that have no equivalent in the other language and you just don’t think about them explicitly. For C++, an example would be pointers, and for Rust an example would be borrows. Speaking for myself at least, I wouldn’t want to be learning borrowing at the same time as I was learning for-loops. Not to mention I’ve finished this whole series while still only having a vague idea of what a lifetime is!

Is the hype justified?
Although based on limited experience, at this point I believe the advice of using Rust for new projects where you would otherwise be using C or C++ is sound! I’m excited to use Rust for a project in the future. On the other hand, I don’t think Rust quite lives up to the hype of being absolutely safe because I was able to easily write code in almost all of these puzzles that would abort when given any sort of unexpected input, but it is at least true that those cases might instead be buffer overflows in C.

Would I recommend learning programming by doing these puzzles?
I’ve seen people recommend this while reading about Advent of Code this month, but honestly? I wouldn’t. If you are learning programming, start with something that’s straightforward and not tricky at all. Programming is tricky enough already by itself.

To conclude this series, I will leave you with a fast-loading version of the Rust error types diagram that Federico sent me after reading my early posts, rendered from DOT and accessible without Google Drive. This diagram was really helpful for me along the way, big thanks to whoever first made it, so I’m glad I can re-share it in a hopefully improved format.

Happy New Year, let’s hope for some better times in 2021!

---

[1] Yes, that really is the name; is there also Fermat’s Big Theorem? ↩

[2] I hesitate to link there because they have big banners saying “Get FAANG Ready With [our site]” which promotes a software engineering industry culture that I don’t support ↩

[3] Hopefully that means I’m in the right job ↩

[4] Or claimed to, in order to make others feel inadequate⁵ ↩

[5] No, I don’t have a very high opinion of the quality of discourse on Reddit, why do you ask? ↩

Advertisement