# Matasano Cryptopals Challenge 1: convert hex to base64

Cryptopals challenge 1

Using binary strings to convert from hex to binary felt kinda hacky. I'd like to hear if there are better ways to do that.

I used memcpy() and pointer to the end of the string instead of strcat() to avoid the Shlemiel the Painter problem.

#include <stdio.h>
#include <assert.h>

char* hex_2_base64(char *_hex)
{
char *hex_2_bin[16] = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" };
char *dec_2_base64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

//allocating memory for binary string
int bin_size = strlen(_hex) * 4;
bin_size += 8;
char *bin = malloc(bin_size + 1);
memset(bin, 0, bin_size + 1);

//these are for strtol, its arguments need the zero terminator
char buf[2] = { 0 };
char b64buf[6 + 1] = { 0 };

//converting hex input to binary
char *bin_end = bin;
for (int i = 0; i < strlen(_hex); i++)
{
buf[0] = _hex[i];
memcpy(bin_end, hex_2_bin[strtol(buf, NULL, 16)], 4);
bin_end += 4;
}

while (strlen(bin) < bin_size)
strcat(bin, "00000000");

//allocating memory for b64 output
int b64size = (strlen(bin) / 6) + 1;
char *out = malloc(b64size);
memset(out, 0, b64size);

//walk through binary string, converting chunks of 6 bytes into base64 chars
char *bin_ptr = bin;
char *out_end = out;
int index_b64;
while (*bin_ptr)
{
strncpy(b64buf, bin_ptr, 6);
index_b64 = strtol(b64buf, NULL, 2);
if (index_b64 == 0)
buf[0] = '=';
else
buf[0] = dec_2_base64[index_b64];
memcpy(out_end, buf, 1);
out_end += 1;
bin_ptr += 6;
}

free(bin);
return out;
}

int main(void) {
char *out = NULL;

out = hex_2_base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d");
assert(strcmp(out, "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t") == 0);
free(out);

//Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.
out = hex_2_base64("4d616e2069732064697374696e677569736865642c206e6f74206f6e6c792062792068697320726561736f6e2c2062757420627920746869732073696e67756c61722070617373696f6e2066726f6d206f7468657220616e696d616c732c2077686963682069732061206c757374206f6620746865206d696e642c20746861742062792061207065727365766572616e6365206f662064656c6967687420696e2074686520636f6e74696e75656420616e6420696e6465666174696761626c652067656e65726174696f6e206f66206b6e6f776c656467652c2065786365656473207468652073686f727420766568656d656e6365206f6620616e79206361726e616c20706c6561737572652e");
assert(strcmp(out, "TWFuIGlzIGRpc3Rpbmd1aXNoZWQsIG5vdCBvbmx5IGJ5IGhpcyByZWFzb24sIGJ1dCBieSB0aGlzIHNpbmd1bGFyIHBhc3Npb24gZnJvbSBvdGhlciBhbmltYWxzLCB3aGljaCBpcyBhIGx1c3Qgb2YgdGhlIG1pbmQsIHRoYXQgYnkgYSBwZXJzZXZlcmFuY2Ugb2YgZGVsaWdodCBpbiB0aGUgY29udGludWVkIGFuZCBpbmRlZmF0aWdhYmxlIGdlbmVyYXRpb24gb2Yga25vd2xlZGdlLCBleGNlZWRzIHRoZSBzaG9ydCB2ZWhlbWVuY2Ugb2YgYW55IGNhcm5hbCBwbGVhc3VyZS4=") == 0);
free(out);

//f
out = hex_2_base64("66");
assert(strcmp(out, "Zg==") == 0);
free(out);

//fo
out = hex_2_base64("666f");
assert(strcmp(out, "Zm8=") == 0);
free(out);

//foo
out = hex_2_base64("666f6f");
assert(strcmp(out, "Zm9v") == 0);
free(out);

//foob
out = hex_2_base64("666f6f62");
assert(strcmp(out, "Zm9vYg==") == 0);
free(out);

//fooba
out = hex_2_base64("666f6f6261");
assert(strcmp(out, "Zm9vYmE=") == 0);
free(out);

//foobar
out = hex_2_base64("666f6f626172");
assert(strcmp(out, "Zm9vYmFy") == 0);
free(out);

printf("OK!");

return 0;
}


### Base 16 -> Base 2 -> Base 64: Cut out the middleman

You are currently converting each hex digit to 4 binary digits, then converting 6 binary digits into one Base64 digit. Instead of doing two conversions, how about if you took each three hex digits (= 12 binary digits) and converted that into two Base64 digits? You can do this up until the end of your hex string, where you might have 1 or 2 leftover hex digits. You can handle those leftover digits by padding with extra zero bits and outputting extra Base64 digits, including the special '=' digit.

### Bug

Your code doesn't convert zeros correctly. The problem is here:

if (index_b64 == 0)
buf[0] = '=';
else
buf[0] = dec_2_base64[index_b64];


As you can see, you output '=' for each Base64 zero digit. However, the correct digit to output is 'A'. The special '=' digit is only used to indicate zero bits for padding. Therefore, if I try to convert the hex string "0000", your program returns "====" when the correct answer is "AAA=".

• I've revised the code and made a new question. It is here if you're interested in taking a look. Oct 20 '16 at 18:53