二进制上的明文算法

大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里很少记录程序员的自我修养，也很少记录热点新闻，主要记录工作中的架构与经验和其他好玩的知识技术，如算法，数学，物理，操作系统等等。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。

零、背景

上周起开始看书：经济学、文学、历史。是的，没有看技术书。
最近也在梳理自己的知识图谱，看到了以前记录的base64算法，这篇文章就来聊聊base64的本质吧。

一、二进制的缺点

所谓二进制可以理解为数据进行了加密或压缩后的一种表示。
加密和压缩的好处大家根据自己的理解，可以想到对应的优点与缺点。
这里要聊的自然是其中的一个缺点：文本中无法明文表示。

计算机中8位的ASCII只有部分字符可以明文显示，如常见的字母数字标点符号。
对于其他符号在文本中没办法显示，如果强行使用文本编辑器打开，会看到乱码。

二、二进制表示法

上面我们了解到了二进制在文本中的缺点，于是就需要想办法把这个二进制转换为可以明文储存的字符。

二进制在计算机中实际上就是01串， 所以我们自然可以想到使用01串来标示二进制。

比如对于”tiankonguse”的二进制就是下面的样子:

01110100
01101001
01100001
01101110
01101011
01101111
01101110
01100111
01110101
01110011
01100101

为什么表示成这样的01串呢?
每个字符在ASCII中都对应一个0~126中的一个数字, 而这个数字可以对应8位的01串.
于是对于一个二进制字符串就可以表示成文本的二进制串了.

但是这个算法也是有代价的。
还是上面的例子， 对于二进制我们只需要11字节的空间就可以储存下对应的内容了。
但是转化为二进制明文后， 需要88字节才能出储存下转换后的内容。

三、常用的十进制

对于十进制，我们在数字中经常使用。
比如对于我喜欢的数字1234567890，我们需要10个字节才能用十进制来表示。
但是在二进制里面，我们使用4个字节就可以表示了，而且可以使用这个空间表示更大的数字。

这里和上面的二进制表示法比较的话，可以发现虽然十进制也需要更多的字节来明文显示， 但是比二进制表示法需要的空间稍微少了一下。
不过这里具体的公式不好算，因为10进制和二进制不对等，所以一般我们都是使用二的整倍数来换算。

四、经典的十六进制

我们把二进制打入log中时,常用的就是十六进制表示法。
我们使用二进制编辑器打开二进制文件时,也是使用十六进制表示法。

比如上面的”tiankonguse”这个二进制字符串, 我们使用十六进制就是下面的样子:

0x74 0x69 0x61 0x6E 0x6B 0x6F 0x6E 0x67 0x75 0x73 0x65

看着是不是很眼熟。
我们一般不储存”0x”，这样我们表示这个字符串就需要22字节了，相比88字节我们节省了四分之一了。

五、本质

上面聊了三个明文算法：二进制表示法，十进制表示法，十六进制表示法。
而且发现进制越大我们相对需要的空间越小，但是比二进制对应的空间大。

为什么呢？
因为我们平常所说的二进制实际上标准名称应该称为256进制表示法。
这是因为计算机中最小的单元不是一位，而是8位，也就是一字节，对应的值就是256。

这个时候我们可以得出结论：明文表示法就是把256进制转化为另一个进制，这个进制中的字符都是明文可见的。
比如二进制表示法的可见明文是0和1。
十进制表示法中的可见明文是0到9。
十六进制表示法中可见明文是0到9以及a到f。
而且我们还可以确认明文表示法需要的空间肯定比256进制大， 因为可见明文的数量远远小于256。

这里我们就希望找到一种更多的可见字符来组成一个更大的进制，从而可以使用更小的空间来表示更多的二进制。

十进制中提到一般使用2的整倍数进行换算，于是我们可以想到几个更大的进制了。
比如我们可以创造出32进制表示法，64进制表示法，由于可见字符不足128个，所以没有128进制表示法。

六、64进制表示法

64进制表示法中有一个很常见的约定进制表示法：base64表示法.
所谓的base64就是使用”A-Za-z0-9”以及”+/”来表示可见的64个明文字符.

这个进制转换后空间扩大多少是可以算出来的。
一个长度为L字节的二进制传, 则需要(L * 8 + 6) / 6字节来标示，大概扩大了1.3倍，但已经是明文表示法中最优表示法了。

这个算法这里就不讲了，有兴趣的兄弟可以自己实现一下，注意最后的边界情况就OK了。
说到边界，base64还有一个约定后面不足的字符使用”=”代替。

下面还是贴一下二进制转64进制的代码吧, 反向的代码这里就不贴了。

static const std::string base64_chars = 
             "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
             "abcdefghijklmnopqrstuvwxyz"
             "0123456789+/";

void transThreeToFour(unsigned char c3[3], unsigned char c4[4]){
    c4[0] = ( c3[0] & 0xfc) >> 2;
    c4[1] = ((c3[0] & 0x03) << 4) + ((c3[1] & 0xf0) >> 4);
    c4[2] = ((c3[1] & 0x0f) << 2) + ((c3[2] & 0xc0) >> 6);
    c4[3] =   c3[2] & 0x3f;
}
             
std::string base64_encode(unsigned char const* bytes_to_encode, unsigned int in_len) {
    std::string ret;
    int i = 0;
    unsigned char char_array_3[3];
    unsigned char char_array_4[4];

    //64对应6位, 所以6位可以转化一个64进制 3字节有24位, 可以使用4个64进制表示
    while (in_len--) {
        char_array_3[i++] = *(bytes_to_encode++);
        if (i == 3) {
            transThreeToFour(char_array_3, char_array_4);
            for(int j = 0; j <4 ; j++){
                ret += base64_chars[char_array_4[j]];
            }
            i = 0;
        }
    }

    //i 为1或2是说明有边界问题,需要特殊梳理
    // i = 1, 剩余8位,需要2字节  i = 2, 剩余16位,需要3字节
    if (i){
        for(int j = i; j < 3; j++){
            char_array_3[j] = '\0';
        }
        transThreeToFour(char_array_3, char_array_4);
        for (int j = 0; j < i + 1; j++){
            ret += base64_chars[char_array_4[j]];
        }
        while(i++ < 3){
            ret += '=';
        }
    }

    return ret;
}

七、结语

好了，看到这里实际上就可以看到平常所说的二进制，10进制，十六进制，base64进制的本质是什么了。
对了, 这个转换实际上也是协议转换, 可以看这篇文章看什么是协议。
希望这些可以帮助到你们。

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。

长按图片关注公众号，接受最新文章消息。