This is the first challenge of Set 1 in The Cryptopals Crypto Challenges website. If you want to know more about these challenges, look at my previous post.
For this challenge, you need to be able to convert Hexadecimal strings to encoded Base64 strings:
The string:
49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d
Should produce:
SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t
Not only is this challenge just a warmup but it is also designed to make you feel comfortable in dealing with raw bytes as Base64 is used to encode binary information and Hexadecimal is used to view the raw bytes.
How to convert from Hexadecimal to Base64?
Well, it's simpler than you think! You will have to go through the following steps:
- Convert hexadecimal string to binary string
- Split the binary string into 4 pieces of 6 bits each
- Convert the binary string to decimal
- Compare each decimal against each character in a reference string of 64 characters
Convert hexadecimal string to binary string
Before converting to binary, you should compare each character against a hashmap table of hardcoded hexadecimal keys and binary values.
//Hashmap that contain hex key and binary values
map<char, string> CryptoLib::gen_hex_table()
{
map<char, string> map;
map['0'] = "0000";
map['1'] = "0001";
map['2'] = "0010";
map['3'] = "0011";
map['4'] = "0100";
map['5'] = "0101";
map['6'] = "0110";
map['7'] = "0111";
map['8'] = "1000";
map['9'] = "1001";
map['a'] = "1010";
map['b'] = "1011";
map['c'] = "1100";
map['d'] = "1101";
map['e'] = "1110";
map['f'] = "1111";
return map;
}
//Convert hex to string
string CryptoLib::con_hex_2_bin(string hexStr)
{
map<char,string> m = gen_hex_table();
string newStr = "";
for(int i=0; i <hexStr.size(); i++)
{
if(isdigit(hexStr[i]))
{
newStr += m.find(hexStr[i])->second;
}
else
{
newStr += m.find(hexStr[i])->second;
}
// newStr += m.find(hexStr[i])->second;
}
return newStr;
}
Split the binary string into 4 pieces of 6 bits each
Base64 represents data in the form of ASCII format that follows a Radix-64 representation. Each character is picked from a set of 64 characters, which means that I'll only need 6 bits represent each character because 26 = 64 characters.
//Add spaces between strings
string CryptoLib::add_spaces(string str, int spaces)
{
string newStr = "";
int count = 0;
for(int i=0; i<str.size(); i++)
{
// newStr += str[i];
if(count == spaces)
{
newStr += " ";
i--;
count = 0;
}
else
{
newStr += str[i];
count++;
}
}
return newStr;
}
Convert the binary string to decimal
Before converting, you should know that a decimal number is equal to the sum of binary digits (d~n~) times their power of 2 (2n).
Let's say you have a binary string of 111001, it's decimal would be 1x25 + 1x24 + 1x23 + 0x22 + 0x21 + 1x20 = 57
//Convert binary to decimal
vector<int> CryptoLib::con_bin_2_dec(string str, double power)
{
vector<int> v;
string newStr = "";
istringstream iss(str);
string x;
while(iss >> x)
{
double p = power;
double decimal = 0.0;
for(int i=0; i<x.size(); i++)
{
if(x[i] == '1')
{
decimal += pow(2.0, p);
}
p--;
}
v.push_back((int)decimal);
}
return v;
}
Compare each decimal against each character in a reference string of 64 characters
At this stage, all you have to do is find and concatenate each character (using the reference string) based on each decimal and return your encoded Base64 string as the final output.
//Convert HEX to Base 64
string CryptoLib::con_hex_2_b64(string str)
{
string b64 = "";
string ref = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
string newStr = add_spaces(con_hex_2_bin(str), 6);
vector<int> v = con_bin_2_dec(newStr, 5.0);
for(int i=0; i<v.size(); i++)
{
b64 += ref[v[i]];
}
return b64;
}
Here's the final section of the code:
//CryptoPals Set 1 Challenge 1
#include "crypto.h"
int main()
{
CryptoLib crypt;
//Test case provided from the site
string str = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
cout << crypt.con_hex_2_b64(str) << endl;
return 0;
}
Note: This solution and the library named crypto.h was built using the C++ programming language. The source code for this solution can be found on Github.
Stay tuned for the next challenge.
