Convert Hexadecimal String to Base64
Cryptopals Set 1 Challenge 1
code repo
working demo
Here’s a good blog post from Oracle to understand the maths behind the conversion:
First, we have to split the hex (Base16) string into groups of two characters each. We do some simple length and regexp validation and display error messages if the input string contains an odd number of characters or invalid characters.
The meat of the conversion happens in this function that calls helper functions (explained in depth below). Note that this is an extremely verbose way of performing conversion that shows all the steps. The process can be abbreviated with bitwise operators.
Also, where you see code like this: decBin.innerHTML=JSON.stringify(arr);
, that’s me breaking out variable contents in intermediate steps to display on the page. I added a simple event listener on the text box to update all these variables each time the text is modified, so that you can see the different steps of code running and their effects in realtime.
For a small project like this, manually updating the view is super straightforward and makes sense, but it’s the fundamental problem that a DOMdiffing view like React sets out to solve. Rather than manually figuring out what changed and updating it yourself, React will “do it for you” when state changes.
We verify the hexstring is valid, split it into twobyte groups, map the groups to base10, map the base 10 groups to base2, combine adjacent 8bit base2 groups to form 24bit base2 groups (handling padding when there are fewer than 24bits in the input stream or a # of bits not divisible by 24), split each of these 3x8bit base2 groups into 4x6bit base2 groups, zero pad each 6 bit group so they are now a 4x8bit group, convert each number in this new group back to decimal, and then we map this decimal 1>1 with the base64 character set. Finally, if padding was required, this is appended to the end of the string, and the converted base64 string is returned! Hooray!
Here are the individual steps broken down:
Step 1: Hexstring to Hex Bytes
Convert the string to an array of individual characters. Create a new array with twocharacter groups.
Step 2: Hex Bytes to Decimal
We map the twocharacter groups with .toUpperCase() so that we only have to have uppercase letters in our map.
The nMap array maps array index > hexadecimal value, 0 through 15.
We break the hexadecimal into two and convert into hexadecimal (first character decimal equivalent times 16^1 plus second character decimal equivalent times 16^0).
We return the decimal. There are two ways to do this. First, a concise way using ES6:
A more verbose way: something similar happens behind the scenes when using parseInt and toString functions:
Step 3: Decimal to Binary
Now that we have the decimal value of each hex byte we need to convert to binary, base2. We do this by iterating through powers of 2 for a byte and, if the value we want to represent is greater than or equal to the power of two at this position, we flip the bit to one, subtract this value from the value we wish to represent, and continue.
Clearly we can represent between 0 (00000000) and 255 (11111111) here.
Then we return the binary representation of the decimal as a string. Once again, it can be simple:
or verbose:
Steps 4, 5, and 6: Binary Octets to 24bit Groups, 24bit Groups to 6bit Groups, zeroPad 6bit groups
Now that we have an array of base2 binary octets, we need to convert its elements into 24bit groups by merging every three adjacent bytes.
Then we turn each 24bit group into 4 6bit groups (3 octets turn into 4 encoded characters in base64).
Each 6bit group is zeropadded at the front with “00”.
There’s a bit of a catch, because there are cases where the mapping from 3x24bit groups to 4x6bit groups does not map onetoone. There are two cases:
 input string contains fewer than 24 bits
 the input string contains > 24 bits and is not an even multiple of 24, so that bits are left over as part of an incomplete group.
In either case, we have to add padding. We treat this last group that may need padding separately, outside of the main loop. It’s called lastSixSlice
in the code below.
First, we loop over everything but the last group of three 8bytes. This loop will only happen if there are three or more bytes in the input stream. We split the 3x8byte group into 4x6byte groups and zero pad each 6byte group with two leading bits. We keep track of the last index if this loop runs in lastI, since we’ll need it to figure out where to start in the array find the “last” octets.
Now for the tricky part. numLastOctets
holds the number of leftover octets. If it’s zero, we’re good, and we don’t need any padding, so we throw all the padding logic in an if block to check this.
The first line of code in this block sets the number of remaining octets. If the remainder of the # of octets when divided by 3 isn’t zero, there will be leftovers to handle.
Then we follow the padding algorithm for leftovers which is:
 distribute the available bits from the final octets into the 4 6bit containers, lefttoright
 when you run out of bits, if a container is partially filled, pad it out to the right with zeroes until it is 6 bits long
 if a container is completely empty, use the “=” character for padding
The only question is, where to find the last octets. From cases 1 and 2 above, are they:

at the beginning of a short string (1. input string contains fewer than 24 bits)? lastI will have been set, so we offset the array index by this much.

at the end of a string of complete octets (2. the input string contains > 24 bits and is not an even multiple of 24)? lastI will NOT have been set, so we so we start at the beginning.
Step 7: Convert to Base64
Once we have the binary representation of the base64 characters, all we have to do is translate it back to base10, and then use the map defined up top to obtain the base64 representation of the hex string. We add on the string containing the last slice that we calculated separately (since we saw from Step 6 that it’s not a simple 1to1 map and requires special handling, depending on the number of input bits).
TODO:
[X] Add padding (currently assume that hex string can be broken into even number of bytes)
[ ] Add tests+validation with Mocha/Chai