I recently decided to tackle the Cryptopals challenges and wrap my head around the basics of C++ in the process. Two bucketlist items in one go! (Except no Go).

Over the years, I’ve taught myself certain low level concepts, the same ones, many times over. However, I never stick with low level study or research long enough for the knowledge to consolidate. Let’s change that!

The task seems simple. Take input in strings of hex characters, select groups of six bits from the input, and map them to the alphabet. A quick read of the RFC quickly revealed my lack of comfort with RFC wording. Example:

A full encoding quantum is always completed at the end of a quantity. When fewer than 24 input bits are available in an input group, bits with value zero are added (on the right) to form an integral number of 6-bit groups. Padding at the end of the data is performed using the ‘=’ character.

Quantum leap in terminology (for me) aside. I couldn’t reconcile the padding with zeroes, with the padding using ‘=’ signs, based on this wording. It turns out that the ‘=’ signs are meant to signal to the decoder just how many bytes of the last quantum were real input. The zero bits are there so the final group is a whole 6 bits and maps to a character at all; the count of ‘=’ is what tells the decoder how much of that tail to throw away.

My first implementation looked like this.

My first implementation
#include <iostream>
#include <string>
#include <unordered_map>

std::string encode_block(std::string block) {
 std::unordered_map<int, char> Alphabet = {
     {0, 'A'},  {1, 'B'},  {2, 'C'},  {3, 'D'},  {4, 'E'},  {5, 'F'},
     {6, 'G'},  {7, 'H'},  {8, 'I'},  {9, 'J'},  {10, 'K'}, {11, 'L'},
     {12, 'M'}, {13, 'N'}, {14, 'O'}, {15, 'P'}, {16, 'Q'}, {17, 'R'},
     {18, 'S'}, {19, 'T'}, {20, 'U'}, {21, 'V'}, {22, 'W'}, {23, 'X'},
     {24, 'Y'}, {25, 'Z'}, {26, 'a'}, {27, 'b'}, {28, 'c'}, {29, 'd'},
     {30, 'e'}, {31, 'f'}, {32, 'g'}, {33, 'h'}, {34, 'i'}, {35, 'j'},
     {36, 'k'}, {37, 'l'}, {38, 'm'}, {39, 'n'}, {40, 'o'}, {41, 'p'},
     {42, 'q'}, {43, 'r'}, {44, 's'}, {45, 't'}, {46, 'u'}, {47, 'v'},
     {48, 'w'}, {49, 'x'}, {50, 'y'}, {51, 'z'}, {52, '0'}, {53, '1'},
     {54, '2'}, {55, '3'}, {56, '4'}, {57, '5'}, {58, '6'}, {59, '7'},
     {60, '8'}, {61, '9'}, {62, '+'}, {63, '/'},
 };
 std::string res{};
 unsigned long val = std::stoul(block, nullptr, 16);
 int b1 = (val >> 18) & 0x3F;
 int b2 = (val >> 12) & 0x3F;
 int b3 = (val >> 6) & 0x3F;
 int b4 = val & 0x3F;
 res += Alphabet[b1];
 res += Alphabet[b2];
 res += Alphabet[b3];
 res += Alphabet[b4];
 return res;
}

int main() {
 char x;
 int i{0};
 std::string aux{};
 std::string res{};
 while (std::cin >> x) {
   ++i;
   aux += x;
   if (i % 6 == 0) {
     i = 0;
     res += encode_block(aux);
     aux = "";
   }
 }
 if (aux != "") {
   if (aux.size() == 2) {
     aux += "0000";
     res += encode_block(aux).substr(0, 2);
     res += "==";
   } else if (aux.size() == 4) {
     aux += "00";
     res += encode_block(aux).substr(0, 3);
     res += "=";
   }
 }

 std::cout << res << '\n';
}

A tricky thing about working on non-coding challenges that require coding is that one can be allured into spending insane amounts of time looking up programming topics. In the context of something like Cryptopals, it could be argued this is a waste of time. Second looked much better!

The second implementation
#include <iostream>
#include <string>

constexpr char ALPHABET[]{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"};

void encode_block(const std::string& x, int start, std::string& res) {
 unsigned long val = 0;

 for (int j = 0; j < 6; ++j) {
   char c = x[start + j];
   int nibble = (c >= '0' && c <= '9')   ? c - '0'
                : (c >= 'a' && c <= 'f') ? c - 'a' + 10
                                         : c - 'A' + 10;
   val = (val << 4) | nibble;
 }

 int b1 = (val >> 18) & 0x3F;
 int b2 = (val >> 12) & 0x3F;
 int b3 = (val >> 6) & 0x3F;
 int b4 = val & 0x3F;
 res += ALPHABET[b1];
 res += ALPHABET[b2];
 res += ALPHABET[b3];
 res += ALPHABET[b4];
}

int main() {

 std::string x;
 std::string res{};
 std::string suffix{};
 std::cin >> x;

 long input_size = x.size();

 //hex representation string must encode byte-oriented data. thus
 //cannot be an odd length. plain reject.

 if (input_size % 2 != 0) {
   std::cerr << "error: odd-length hex string\n";
   return 1;
 }

 // Non Hex alphabet character -> reject.
 const char* hex_alphabet = "0123456789abcdefABCDEF";

 if (x.find_first_not_of(hex_alphabet, 0) != std::string::npos) {
   std::cerr << "error: invalid hex string\n";
   return 1;
 }

 // pad per section 4 of RFC4648
 if (input_size % 6 == 2) {
   x += "0000";
   suffix = "==";
   input_size += 4;
 } else if (input_size % 6 == 4) {
   x += "00";
   suffix += "=";
   input_size += 2;
 }

 int blocks = input_size / 6;
 res.reserve(blocks * 4);
 for (int i{}; i < blocks; ++i) {
   encode_block(x, i * 6, res);
 }

 if (suffix == "==") res.resize(res.size() - 2);
 else if (suffix == "=") res.resize(res.size() - 1);
 std::cout << res << suffix << '\n';
}

If you are the type to expend and review the code, you’ll notice that:

  • I used the properties of the C++ string, and the (guaranteed?) order of ASCII encoding to store the encoding alphabet more efficiently.
  • Instead of reading char by char and counting to group inputs into blocks of 6 characters, I consumed a whole string from std::in and then worked on it.
  • We are operating on segments of the input string directly, instead of copying each block into an auxiliary string first.

Some other efficiency gains include refusing to operate on malformed input immediately, only possible in implementation #2.

At any rate, the big learning from this exercise is that input comes into the program’s buffer as a sequence of integers (I believe the compiler treats chars as short integers by default, or uint8_t). Two nice features that come off this is that one can apply bit-wise operations on them, just assuming their decimal value will correspond to that of their new binary representation. Chars can also be compared to one another and operated on as integers, allowing for a quite elegant solution. This also brings me back to my uni days, where this came up and I was dramatically less appreciative of it.