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 SL (mod 20201227) (where S is the subject number and L is the loop size.) So, the total of what we know is this:

  • Pc ≡ 7Lc (mod 20201227)
  • Pd ≡ 7Ld (mod 20201227)
  • PcLdPdLc (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−1 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.1 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.2

The problem is of the form akb (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,3 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.4

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 inadequate5

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

Indonesian recipes

In late February and early March I attended the GNOME Recipes hackfest in Yogyakarta, Indonesia. It was my second time visiting Indonesia, and food was a bit of a theme. The hackfest was about GNOME Recipes, so food, but also I love Indonesian food and I was eager to taste some more so I can improve how I cook it at home.

I haven’t contributed to GNOME Recipes. (Shamefully, not even a recipe yet!) So why was I going to a GNOME Recipes hackfest? It’s because on Endless OS we have a Cooking app, which in many ways is not as good as GNOME Recipes. It’s certainly less lovingly curated, and less community-oriented, than GNOME Recipes, and it allows recipe submissions by users while the Endless app is read-only.

However, there are a few things Endless’s Cooking app does better than GNOME Recipes: it is visually more appealing, it’s available in several languages (Arabic, Bengali, English, Portuguese, Spanish, and also a Spanish version customized for Guatemala), and it uses a better database backend (which also makes it fully offline.) It does these things using Endless’s “modular framework,” which if you want to know more about, I gave a talk two years ago at GUADEC. This modular framework is the product that I primarily work on at Endless, so a few of my team joined in the GNOME Recipes hackfest to see whether the two apps could share some technology.

It turns out that Matthias was eager to have somebody come along and make a database backend for GNOME Recipes, so the answer was yes, we could very well share some technology.

As an experiment, we made a recipes “lookalike” app using the modular framework technologies of which you can see some nice screenshots in Martin’s blog post.

We worked out some goals that we wanted to achieve by GUADEC in order to present our work, which you can see in the hackfest notes.

Outreach

There were also some goings on besides the hackfest. On the day before the hackfest started we did an outreach event for the students of AMIKOM University Yogyakarta, where the hackfest was held. We gave some talks on our work, and GNOME contributor and Endless Ambassador Siska closed the morning out with a very successful talk on how to get involved in GNOME.

View this post on Instagram

Universitas AMIKOM Yogyakarta menjadi tuan rumah Recipes Hackfest 2018 (28 Februari – 2 Maret 2018). Recipes Hackfest sendiri merupakan agenda yang diadakan oleh GNOME Recipes team and Endless, yang mempertemukan developer, kontributor, maupun komunitas GNOME untuk membahas berbagai hal, terutama dalam mengembangkan open source, terutama mengenai GNOME dan Endless OS. . . Agenda ini merupakan kerjasama antara Program Studi D3-Teknik informatika dan Amikom Business Park dengan Gnome dan Endless OS dan diadakan selama 3 hari di ruang Inkubator Universitas Amikom Yogyakarta. Dalam agenda ini, Tim pengembang bertemu dengan developer, kontributor, komunitas, maupun pengguna Endless OS, untuk mencari dan mengeksplorasi berbagai resep/cara yang tepat dalam mengembangkan aplikasi yang sesuai dengan kebutuhan pengguna Endless OS dan komunitas GNOME. . . Agenda Recipes Hackfest 2018 ini sendiri dibuka dengan kegiatan outreaching/workshop tentang GNOME dan Endless OS di Ruang Cinema Amikom (27/2). agenda ini diikuti oleh sekitar 100 orang Mahasiswa Universitas AMIKOM Yogyakarta dan para pegiat GNOME community. Terdapat 4 Materi yang disampaikan dalah agenda Outreaching tersebut, yaitu : . . 1. Introduction to GNOME From technology to users by Jonathan Blandford (GNOME Contributor) 2. Introduction to Endless by Cosimo Cecchi (Endless, organizer) 3. Getting involved in GNOME/GSoc/Outreach by Umang Jain (Core apps contributor, GNOME Contributor) 4. Introduction to Flatpak by Philip Chimento (Endless, engineer)

A post shared by Universitas AMIKOM Yogyakarta (@amikomjogja) on

After that I gave a live demo of how to make a GNOME app, the result of which you can find on GitHub here!

GNOME hackers and students seated around a table, watching a programming demo on a projector

This is me doing the live-coding demo of a GNOME app. Some of the students said I looked like Tony Stark.

 

Translation

One of the most interesting discussions we had was about how to internationalize GNOME Recipes. In different countries people cook very differently, so translating a recipe from one language into another is not enough. You also have to adapt the recipe to the ingredients that you can get in the country, and sometimes it’s not possible to get the same taste. For example, if I wanted to adapt my beloved pesto recipe from Marcella Hazan’s Classic Italian Cookbook, to Indonesia, first of all I’d probably have to substitute Thai basil which would change the taste entirely. Or to adapt Indonesian recipes to Canada, you have to go to some lengths to find ingredients like terasi (shrimp paste) and kemiri (candlenuts), and we just can’t get some of the same vegetables.

It can also be that when one language is used in two countries, the same recipe still won’t work for both. For example, in the UK, baking measurements are given by weight, and in Canada and the US they are given by volume. The metric system (ºC, kg, ml) is used in the UK and the imperial system (ºF, pounds, quarts, ounces, bushels, specks, caltrops, and jeroboams) in the US. To make matters worse, Canada uses the metric system for weight and volume measurements (kg, ml) but oven temperatures are given in Fahrenheit as in the US. All three countries cook with teaspoons and tablespoons, but teaspoons and tablespoons are metric in Canada and the UK (5 ml and 15 ml) but imperial in the US (4.93 ml and 14.79 ml).

We also discussed that many translation tools assume that the source language is always English since that’s the lingua franca of programmers, but it’s definitely not the lingua franca of cooking!

I would go so far as to say that all the existing translation infrastructure that we have for internationalizing GNOME is not going to be good enough to translate the recipes in GNOME Recipes.

Progress since then

In the time since the hackfest, I was able to make a little bit of progress on our goals. I worked on splitting out the code that handles data modelling into DModel, a separate library, so that GNOME Recipes could use it.

Food

I did get a chance to learn the flavors of Indonesian food more. When I lived in the Netherlands I already became familiar with some Indonesian food, but the Indonesian food in Indonesia is really much more delicious. In Vancouver we have only one Indonesian restaurant, which is kind of far away. And I found only one Indonesian store where I can buy ingredients like shrimp paste and candlenuts, which is even farther away.

Siska brought in packets of rendang spice paste for everyone to take home, for which I was especially grateful. Here’s a picture of my rendang that I made when I got back to Vancouver:

Beef rendang, still cooking down, next to a pot of rice cooking

Rendang and rice

I also tried to make the spice paste myself (because soon I will be out of the spice paste packets) but I haven’t got it figured out yet.

Some of the other dishes that I’ve made at home:

Yellow coconut curry in a bowl with kale and rice

Gulai curry (substituting kale for the cassava greens)
(The recipe is from Daily Cooking Quest which is a cooking blog from an Indonesian blogger who emigrated to the United States, and I’ve had good luck with those recipes because she uses ingredients that are possible for me to get in Vancouver, and she also gives the Indonesian names of the ingredients)

Fried noodles on a plate, with a fried egg and chili paste

Mi goreng

I am going to try making gudeg this week, which is a jackfruit curry, a specialty of Yogyakarta.

Acknowledgements

Sponsored by GNOME FoundationI’d like to thank AMIKOM University Yogyakarta for hosting the hackfest and giving us the opportunity to get some students interested in open source development, and the GNOME Foundation for sponsoring my travel and accommodations during the hackfest. Thanks also to Cosimo, Ekta, Elvin, Emmanuele, Haris, Jonathan, Kukuh, Martin, Matthias, Rama, Siska, and Umang, and also Kiki from Mozilla who joined on the last day, and Angky from Endless who helped arrange the hosting and logistics, for making the event a success!