# Matasano cryptopals challenge - part one - Converting to base64

*This post is the first one of a serie about the matasano cryptopals challenge. This serie is not intended to cover all excercises of this challenge. I’m just going to write about some of them I find interesting. Moreover, I don’t want to give all solutions of the challenge, it could be more rewarding to do it by yourself.*

**So, I’m going to talk about the very first exercice: base64 encoding. You have an ascii (or hex encoded, whatever…) input buffer, you must return a base64 encoded of the input. As you could guess by yourself, a good entry point is this page. In this exercice, it is not asked to handle the padding but anyways, I put the padding as part of the solution.**

So here is a quick example on how things work with base64 encoding:

We define the following index table: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=

- We have the sequence “Fo” as input.
- We convert the sequence using ascii decimal value for each character: 70 111 (and add 0 to have a ascii sequence multiple of 3).
- We convert every ascii decimal value in binary (8-bit sequence).
- Now we cut the all sequence of bits into 6-bits long values.
- Every 6-bits long value is converted into an integer. (17 38 60 0)
- For every integers
**i**,**i**is the index of the base64 symbol of our output in our index table, the last sequence will be the padding .

This algorithm is illustrated in the following table:

Source input | F | o | ||||||||||||||||||||||

ASCII Dec | 70 (0x46) | 111 (0x6F) | 0 | |||||||||||||||||||||

Bit pattern | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

Index | 17 | 38 | 60 | 0 | ||||||||||||||||||||

Base64 enc. | R | M | 8 | = |

In practise, the implementation of the below algorithm is slightly different because:

- Each input character is already in its integer representation when stored
- We get the result from the index table directly from the 6-bit integer representation (we shift the bits from the decimal input representation)
- By comparing where we are in the input, to the input size, we apply the right shifting and set the right padding if needed (if clauses)

This results in the following C implementation:

```
1 typedef unsigned char byte;
2 char index_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
3
4 byte *
5 ascii_to_64(byte * input) {
6
7 byte * str64;
8 unsigned int input_length = strlen(input);
9 unsigned int str64_length = input_length * 4 / 3;
10 unsigned int i, j = 0;
11
12 if((str64 = (byte *) malloc(str64_length * sizeof(byte))) == NULL)
13 return NULL;
14
15 for(i = 0; i < input_length; i+=3) {
16
17 str64[j++] = index_table[(input[i] >> 2)];
18
19 if(input_length >= i+2) {
20 str64[j++] = index_table[(((input[i] << 4) & 0x30) | ((input[i+1] >> 4) & 0x0F))];
21 } else {
22 str64[j++] = index_table[(((input[i] << 4) & 0x30) | (0x00))];
23 str64[j++] = index_table[64];
24 str64[j++] = index_table[64];
25 break;
26 }
27
28 if(input_length > i+2) {
29 str64[j++] = index_table[(((input[i+1] << 2) & 0x3C) | ((input[i+2] >> 6) & 0x03))];
30 } else {
31 str64[j++] = index_table[(((input[i+1] << 2) & 0x3C) | (0x00))];
32 }
33
34 if(input_length >= i+3) {
35 str64[j++] = index_table[((input[i+2]) & 0x3F)];
36 } else {
37 str64[j++] = index_table[64];
38 }
39 }
40
41 return str64;
42 }
```

That’s it for today. As usual, any feedbacks are always welcome using my email address (“about” page).

Happy crypto!