写点什么

Base-x 编码的奥秘

  • 2021-02-26
  • 本文字数:3017 字

    阅读完需:约 10 分钟

Base-x 编码的奥秘

Base Encoding 是一组二进制转文本的编码模式(Encoding Scheme),常见的有 Base64、Base58、Base32、Base16。大家不仅疑惑为什么需要二进制转文本这种编码模式呢?常见误解之一就是既然所有的编码最终都会变成 0 和 1,那么分成 ASCII 和 Base64 编码是不是就没有必要呢?

Base 编码的历史

1970~1980 年代,DEC(和其他公司)生产的“微型计算机”使用的字符编码为 ASCII。每个字节使用 7 位,给出 128 个可用值。这足以满足大写和小写拉丁字母,数字,标点,一些常见的数学符号,货币符号和控制字符的需要。此后 ASCII 变得非常流行,并在很长一段时间内占主导地位。ASCII 规定了范围在 [0,127] 之间的字符编码,其中 [0, 31] 以及 127 (del) 这 33 个属于不可打印的控制字符(可以使用 man ascii 查证)。互联网的杀手级应用——电子邮件系统当初是为了传输 7 位 ASCII 文本而设计的,于是在传输信息时,有些邮件网关会把 [0,31] 这些控制字符给清除,而有些会替换 10 (newline 或 \n)和 13 (carrige 或 \r) 字符,有些更加粗暴地将二进制的最高位清空,还有的程序在收到 [128, 255 ] 之间的国际字符会发生错误。


如何在不同邮件网关之间安全地传输控制字符、国际字符和二进制文件呢?作为 MIME(RFC 2045 和 RFC 3548)多媒体电子邮件标准的一部分的 Base64 编码就被开发出来了。


Base64 编码的解题思路很简单。既然直接传输控制字符、国际字符和二进制文件容易造成原始信息在传递过程中的错误,那么就把原始信息都转成 ASCII 的可打印字符,这样就能让旧系统安分点,不再胡乱改变其内容。


Base64 是怎么做的呢?它的核心算法是将每 3 个字节(3 * 8 = 24 比特)依次转换成 4 个可打印字符(4 * log 64 = 24 比特)。具体操作如下:


  1. 将 3 字节的数据,先后放入一个 24 位的缓冲区中,先来的字节占高位。数据不足 3 字节的话,缓冲器中剩下的比特用 0 补足。

  2. 每次取出 6 比特,按照其值选择 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ 中的字符作为编码后的输出,直到全部输入数据转换完成。

  3. 若原数据长度不是 3 的倍数时且剩下 1 个输入数据,则在编码结果后加 2 个 =;若剩下 2 个输入数据,则在编码结果后加 1 个 =。用来代表补足的字节数。


我们以换行字符(ASCII 码 10)为例,原始的二进制表示如下


  1. 10 的二进制表示是 0000 1010,放到 24 位的缓冲区补零为 00001010 00000000 00000000

  2. 每次取 6 比特,则如右边划分所示:000010 100000 000000 000000。因为后两部分为补零,适用于规则 3。前两部分的十进制依次是 2, 32,所以通过索引表选择的值是 C, g

  3. 后两部分是补零,所以替换成=。

  4. 故结果为 Cg==

为什么需要 Base58?

首先,Base58 和 Base64 一样都是一组二进制转文本(binary-to-text)的编码模式。Base58 的主要职责是将大整数表现成文本,它是由中本聪在 Bitcoin 中首先引入进来的。为什么要这样使用呢?有如下几个原因:

https://en.bitcoin.it/wiki/Base58Check_encoding#Background

// Why base-58 instead of standard base-64 encoding?// - Don't want 0OIl characters that look the same in some fonts and//      could be used to create visually identical looking account numbers.// - A string with non-alphanumeric characters is not as easily accepted as an account number.// - E-mail usually won't line-break if there's no punctuation to break at.// - Doubleclicking selects the whole number as one word if it's all alphanumeric.
复制代码


  1. 去掉了 Base64 中的长相相近的字符,这样直观上就能分辨账户数字,如:0(零)和 O(大写 o),I(大写 i)和 l(小写 l),以及 + 和 / (non-alphanumeric 非字母和数字组成的),共 6 个字符。这也是 Base58 名称的由来,因为 64 - 6 = 58

  2. 非字母和数字的字符就不太容易混入账户地址里

  3. 在邮件里没有标点就不会断行(意在排除截断的可能性)

  4. 双击就能全部选中所有字符和数字的串


顺带一提,Base56 相较于 Base58,少了 1(一)和 o(小写 o)这两个字符,而 Base32 则只包含 A-Z 和 2-7 这 32 个字母和数字。

Base58 的特点

维基百科上说,Base58 不太适合编码二进制数据,而适合编码大整数?在探讨 Base58 的实现原理之前,我们先看看比较常见的几种 Base 编码。

Base16

有人可能会说 Base16 我没有用过,怎么能说常见呢?乍看这个名字还挺唬人的,但其实它就是 Hexidecimal 十六进制编码。对于 10101010,会被编码成 0xAA。拆解来看,1010 是十进制的 10,也就等于十六进制中的 A。原因是十六进制只能表示 0-9 以及 A-F 这 16 个数,16 换成二进制的范围就是 0000 - 1111。

Base32

那么 Base 32 这种编码呢?同理,它可以表达的二进制范围是 00000 - 11111 也即 2 的 5 次方,即 32 个数。但问题是二进制都是 8 位起,8 是没法整除 5 的。既然 8 除以 5 除不尽,那我们就找 8 和 5 的最小公倍数,即 40。换句话说,5 bytes = 8 chars。也就是说,我们需要将每 5 个字节转化成 8 个 Base32 中的字节。


由此,我们可以总结出一些规律。Base16 这种编码方式,8 和 4 的最小公倍数是 8,所以 1 bytes = 2 chars,每次都能将一个字节转化成 2 个字符,都能刚好对齐。而 Base32 这种编码方式,因为 8 和 5 的最小公倍数是 40,所以 5 bytes = 4 chars,存在对齐不了情况,那么非 5 字节倍数的字节序列就需要额外补齐,同理, Base58 和 Base64 也需要如此。

Base58

继续深入之前,我们先回忆一下中学学习的短除法求解二进制。以 10 为例,计算如下:



图 1 短除法计算十进制转二进制

短除法的实质是连除进制,降低位权,依次得到各位上的数值。我们不妨以十进制的 111 举例。



图 2 短除法计算十进制数各位上的数值

虽然上面的计算纯属画蛇添足,不过它对于理解二进制的短除法还是很有帮助的。我们第一次用 111/10,得到的余数为 1,便是个位上的数;再次用 11/10,得到的余数为 1,便是十位上的数;最后用 1/10 得到的余数为 1,就是百位上的数。类比可得,上例中计算 10 这个数字的二进制时,第一次用 10/2,得到的余数 0 便是最低位上的数,得到的商为 5,则是 10 这个数的二进制 1010 的高三位(101),依次类推即可得到不同数位上的二进制数了。所以这样就不难理解短除法有效性的来源。

我们再来看看 Base58 这种编码方式,它有 58 个字符,所以可以表示的二进制范围是 000000 - 111001。因此,Base58 编码算法需要除法运算实现,如果被编码的数据较长,则要用特殊的类来处理大数,在 Bitcoin 使用了 OpenSSL 中的 BIGNUM。

伪代码 - Base58 利用短除法编码的过程

code_string = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";x = convert_bytes_to_big_integer(hash_result);
output_string = "";
while(x > 0){ (x, remainder) = divide(x, 58);  output_string.append(code_string[remainder]);}
repeat(number_of_leading_zero_bytes_in_hash){  output_string.append(code_string[0]);}
output_string.reverse();
复制代码

小结

Base64 用于编码邮件内容、网页图片,意在减少传输过程中可能出现的错误;Base58 是比特币地址使用的编码方法,旨在提高地址的辨识度;Base32 用在一些对大小写不敏感的文件系统中。每种 Base-x 的编码都有适合它们的应用场景。自然,为应对需要我们也可以发明自己的 Base 编码。


本文转载自:ThoughtWorks 洞见(ID:TW-Insights)

原文链接:Base-x 编码的奥秘

2021-02-26 07:002202

评论

发布
暂无评论
发现更多内容

PHP自动加载原理

Sakura

4月日更

从中国企业进入IEC最高决策机构,看科技领先的产业价值与用户价值

脑极体

Modbus协议在串行链路上的实现

不脱发的程序猿

通信协议 物联网常用协议 4月日更 Modbus 串行通信

HDFS的垃圾桶机制

五分钟学大数据

hadoop 4月日更

想来百万流量技术公众号发布文章吗? InfoQ 开放内容平台了!

xiaotan

InfoQ 的朋友们 热门活动

想来百万流量技术公众号发布文章吗? InfoQ 开放内容平台了!

InfoQ写作社区官方

热门活动

聪明人的训练(十四)

Changing Lin

4月日更

Android面试送分题:大厂经典高频面试题体系化集合,实战篇

欢喜学安卓

android 程序员 面试 移动开发

android热修复基本原理,15分钟的字节跳动视频面试,满满干货指导

欢喜学安卓

android 程序员 面试 移动开发

APM-技术专题-监控系统选型

码界西柚

APM 监控

理论 + 标准 + 工程 —— 阿里云视频云编码优化的思考与发现

阿里云CloudImagine

阿里云 视频编码 视频算法 视频处理

1小时破千万点击量!阿里巴巴首发:Java核心框架指导手册

Java架构追梦

Java 阿里巴巴 架构 面试 核心框架

7年Java经验|面20+家公司|已拿16个offer|面经总结|

Java架构追梦

Java 架构 面试 20+大厂面经

入门物联网嵌入式才是关键!

cdhqyj

技术 编程语言 物联网 嵌入式 系统

HikariCP-技术专题-配置介绍和使用

码界西柚

spring中让你眼前一亮的代码技巧

AI乔治

Java spring 架构 微服务

Modus串行链路系统电气特性:2线-Modus、4线-Modus、RS232-Modus和RS485-Modus的特性

不脱发的程序猿

通信协议 4月日更 Modus 串行链路 RS232、RS485

Flume高阶自定义组件

大数据技术指南

大数据 flume 4月日更

硬核!阿里内部这份《Java面试核心知识手册》在Github上已获赞高达89.7K!

Java架构之路

Java 程序员 架构 面试 编程语言

一个CURD三年的Java程序员刷完这份《阿里面试指南(恒山版)》,居然斩获了十七个offer

Java架构之路

Java 程序员 架构 面试 编程语言

博云入选2021爱分析·产业数字化厂商全景报告

BoCloud博云

云计算 云原生 PaaS 博云

小厂逆袭美团|5年经验|一二三面经,已拿offer|

Java架构追梦

Java 架构 面试 美团Offer

2021金三银四:狂刷398道Java最新MySQL笔记;成功收获9个Offer

比伯

Java MySQL 编程 架构 计算机

入职字节跳动那一天,我哭了(蘑菇街被裁,奋战7个月拿下offer)

Java架构追梦

Java 架构 字节跳动 面试

最全 MongoDB 基础教程

若尘

数据库 mongodb mongo

LeetCode题解:剑指 Offer 49. 丑数,三指针,JavaScript,详细注释

Lee Chen

算法 大前端 LeetCode

阿里巴巴云原生 etcd 服务集群管控优化实践

阿里巴巴云原生

容器 运维 云原生 k8s 存储

非科班毕业生,五面阿里:四轮技术面+HR一面已拿offer

码农之家

Java 编程 程序员 互联网 面试

JVM-技术专题-方法区中常量池分析

码界西柚

JVM 常量池

iOS--面试题:多线程

ios 面试 多线程

卧槽,误删数据库了,会被开除吗?

AI乔治

Java 数据库 sql 架构 SQL语法

Base-x 编码的奥秘_架构_张凯峰_InfoQ精选文章