likes
comments
collection
share

从Base32编解码算法理解位移运算

作者站长头像
站长
· 阅读数 50

Base32编码并不是一种常见的编码方式。一般我们会熟悉hex、Base64等这些常用标准的基础编码方式，其他的编码方式一般情况下基于特殊的业务需求。如Base58，是比特币使用的编码方式。

其实所有这些各种BaseX的编码方式，它们的基础概念是一样的。这里的X本质上就是一个进制， HEX是16进制，58就是58进制，而所有信息的通用表示形式-字节数组，其实是256进制，只不过字节数组使用数字(Uint8)来表示，而BaseX可以简化使用对应进制的字符集合来表示，更容易使用而已。所以这里BaseX的编码，看起来是一个字符串，其实是一个数组，数组的每个元素，都是其对应进制的数字。

对于BaseX数据的处理方法，我们先讨论一下普遍的情况和一般过程，然后再详细探讨Base32编码的具体实现方式。

BaseX编解码的一般过程

首先明确一下基本概念和规则，所谓编码，就是将一段文字(UTF8字符集)，转换成为BaseX字符串；解码是编码的逆运算，输入为BaseX字符串，转换还原为原始文本。当然，这是一个狭义的定义，真正的转换有一个中间过程，就是先将文本转换为字节数组，然后再进行编码，因为字节数组才是信息在软件中的基础形式。

假设，我们有一个字符串： "China中国Hello"，要将其编码为BaseX编码，应该这么做：

1 基于编码规则，定义一个有序的字符集

BaseX编码，使用字符集合来表达信息，所以首先是需要确定这个字符集合。X就表示打算使用多少个字符来进行表达。如Base32的"标准"字符集为:

ABCDEFGHIJKLMNOPQRSTUVWXYZ234567

同理，HEX的编码字符集是0123456789abcdef，而Base64是: AB...XYZabc...xyz0123456789+/；它的本质是使用一个字符来代替一个数字(字符在字符串中的顺序)。要注意这个字符集合的定义“有序”的，因为实际上需要使用某个字符在集合中的位置，来表示进制数字的值。

2 生成字节数组

然后，就可以开始编码了。第一步应当是将其编码为标准的字节数组，即比较基础和通用的信息形式，在nodejs和浏览器中，可以使用Buffer或者TextEncoder都可以：

const s = "China中国@1234!";

// browser
let d1 = new TextEncoder().encode(s);

// nodejs 
let d2 = Buffer.from(s);

// 命令行
> new TextEncoder().encode("China中国@1234!")
Uint8Array(17) [
   67, 104, 105, 110,  97, 228,
  184, 173, 229, 155, 189,  64,
   49,  50,  51,  52,  33
]
> Buffer.from("China中国@1234!")
<Buffer 43 68 69 6e 61 e4 b8 ad e5 9b bd 40 31 32 33 34 21>

这样，我们就会得到一个21个字节的字节数组，这里buffer和uint8array本质上都是字节数组，就是一个smallint类型(8位二进制)数据组成的数组。Buffer使用16进制表示，所以0x43其实就是67(4x16+3)，是一样的。

3 循环整除求余

如果是通用的算法，即basex，理论上应该将这个字节数组转换成一个大整数，然后从低位开始，对X进行循环整除求余，就获得一个余数的序列，然后查找这些余数在字符串中对应位置的字符，构成的字符串就是原始信息BaseX的编码。

这个算法的核心是大整数操作。在这个意义上，任何信息都可以用一个大整数来表示。而字节数组无非是大整数的256进制表示的形式。

但通用的大整数操作的算法实现并不容易，在很多时候也没有必要。这时候，通常可以用工程的方式来简化问题。

4 特例处理

我们先来看两个熟悉的BaseX的特例。 hex和Base64。

Hex本质上就是Base16，它使用16个字符表示一个数组，每个字节数组的元素，都可以表达为两个hex字符表示的字符串。由于256可以被16整除，所以在字节数组中，每个元素都和其他的元素是无关的，可以单独处理。

Base64的情况稍微复杂一点点。 但考虑到 64是2的6次方，256是2的8次方。三个字节(3x8)，“刚好”可以用四个Base64字符(4x6)来表达。 所以，对于base64，我们可以把问题简化，将字节数组分为三个三个一组，对于这个组，可以在组内进行转换，为4个Base64字符，然后将所有小组连接起来，就是最后的Base64编码了。

5 Base32

所以，Base32其实也是一个特例。32是只是2的整数倍而已。当然你也可以认为8个Base32字符，可以用于表达5个字节，显然并不如64那么方便。但可以提供给我们一种处理的思路，进一步使用二进制的方式来进行操作。这一部分的实现我们会在后面详细的分析和讨论。

6 解码

检查编码的算法实现是否正确，其实也很简单，就是基本按照逆运算的方式，提供一个解码程序，能够将编码的结果，解码成为原始的信息就可以了。

上面就是BaseX编解码的一般过程。下面我们详细的分析一下Base32的编解码实现，为了方便讨论，我们使用Javascript语言和标准程序方法。

Base32编码实现

我们在前面已经知道，除了上面的大整数处理方式之外，Base32是可以作为一个特例来处理的。这里我们可以提供两种处理的思路。

  • 二进制字符串方式

从上面的过程可以看到，这种处理方式属于“简单粗暴”的方式，本质上并不是在处理数字，而是利用其字符串形式在处理字符。算是一种工程化的处理。但优点是容易理解和实现。

为了方便讨论，我们只看前五个字节(十进制表示)：

[67, 104, 105, 110, 97 ]

转为二进制字符串的数组，注意需要补全8位：

['01000011', '01101000', '01101001', '01101110', '01100001' ]

合并后的结果如下，并将其每五个字符分为一组，共8个二进制字符串：

01000,011 01,10100,0 0110,1001 0,11011,10 011,00001

将这个八个二进制数，转为整数为：

8,13,20,6,18,27,19,1

然后使用标准字符串，以其作为索引，查找对应的字符为：

B,N,U,G,S,3,T,1, 所以　BNUGS3T1就是这５个字节的编码。

以此类推，我们可以计算剩余的字节，得到完整信息的编码，如果不足5个字节，可以使用0字节补位的方式补足0位进行计算。

解码基本上就是编码过程的逆操作。将编码字符分隔一一计算其字符对应的索引索引数值；将此数值转换为二进制字符串（5位）；连接字符串后按8位进行分组；然后将此8位的二进制字符串转换为整数；得到的字节数组就是解码的结果。然后可以使用TextEncoder就可以还原为原始信息了。

  • 位移处理方式

前面讨论的字符串方式，可以说是一种比较“取巧”而且不是那么正规的方式，虽然也可以解决问题，但并不是建议的方式，当然也不是本文讨论的重点。我们当然希望使用“数学”和更本质的计算方式来进行处理。其实前面的方法是可以给我们一些思路的。就是可以将复杂的问题合理的进行分拆分步处理，我们下面就来尝试一下。

1 还是先转为一个二进制数构成的数组，注意这里已经不是字符串了：

[0b01000011, 0b01101000, 0b01101001, 0b01101110, 0b01100001 ]

2 先取出最高的5位

现在的构想是，希望从高到低取前5位作为新的编码数值。比如要从 0b01000011，取出前5位，可以使用位移计算方式，方式是向右移动3(8-5)位：

0b01000 = 0b01000011 >> 3， 得到第一位为： 8

3 宽度不够，加入下一个字节

下一步，就有两个问题，高位阶段后应该得到一个剩余的 0b011，要继续截位，这个位数已经不够了，需要将下一个字节0b01101000加进来才能继续，这时需要做几个操作。

首先要截断前面的高位，得到剩下的低位，可以使用掩码操作（要留几位掩几位）：

0b011 = 0b01000011 & 0b111

然后加入下一个字节，方法是将当前位进8位（一个字节的宽度），然后和下一位相加, ：

0b01101101000 = (0b011 << 8) + 0b01101000

得到一个数值，可以继续进行截位操作，这时这个数值的名义宽度是11位(3+8)

4 继续取出最高的5位

当前值的名义宽度11已经超过5位，就可以继续使用截断方法了, 继续右移6(11-5)位：

0b01101 = 0b01101101000 >> 6， 得到第二位为: 13

截断高位，保留低6位： 0b101000 = 0b01101101000 & 0b111111

5 当前位数宽度足够，可以直接继续取出高5位

0b10100 = 0b101000 >> 1, 得到第三位为: 20

到了这里，相信大家应该已经可以看出来规律了。就是如果当前的值够大，就可以直接取高5位，不够的话加入下一个字节来取高5位，直到所有的字节都编码完成。

6 补位 这个算法的要点和容易出问题的地方，就是在最后一个字节的补位操作。在编码的时候这个问题不大，直接把最后计算剩余的余数转换为字符添加即可。主要问题是解码的时候，需要将最后一个字节还原。大体上有两种情况，一种是信息的二进制长度刚好是40的整数倍，还有一种普通情况，都需要不同的处理，详见代码。

这个方法的优势在于，不管原始信息有多大，都可以直接开始编码计算，而且参与计算的信息总是有限的，不会造成太大或者不可控制的资源占用，保证了算法的稳定和高效。

这部分的内容比较重要，所以笔者给出了相关可执行的参考代码，方便大家在调试中理解：

从Base32编解码算法理解位移运算

相关要点和说明如下：

  • 使用循环来消耗数组中的数值，并使用一个数组来记录所有阶段的编码
  • 需要独立处理最后一个字节，退出条件为数组遍历完成并且剩余值小于32，作为最后的余数加入结果数组
  • 取高位可以使用 >> 位移操作(直观的意思是截断右边n位数据)，但需要移多少，取决于当前数值的名义宽度
  • 使用w来记录当前数值的名义宽度，初始为8，第一个字节的宽度
  • 每次截断的数据长度为5(二进制)
  • 可以使用((1 << w) -1) 构造掩码来取当前截断后的余数
  • 宽度不够可以从下一个字节进位，通过向左位移8位并且相加来实现，并使用i来记录当前字节位置
  • 最后使用数组中的数值作为索引，在字符集合中查找对应字符来构造数组字符串

笔者觉得这是一个很好的案例，让我们了解和熟悉位移计算在一个实际场景中的各种操作方式，比如取高位、保留低位、进位、构造掩码等等，觉得获益颇多，希望也对读者有所启示和帮助。

笔者的Base32使用场景

好了，最后我们来聊聊具体在什么地方会用到Base32编码。笔者是在Google Authticator(下简称为GA)的算法实现中遇到这个编码的。在一个具体业务应用中，要用GA来进行信息的动态签名，以提高系统安全性，就需要在服务器端实现这个算法来生成相同的认证代码。在这个过程中，就接触到了Base32编码的相关处理算法和实现。也解惑了很长一段时间内使用GA的一些困惑。

我们了解，GA是一种基于时间的OTP算法，原理和目的很容易理解，就是在一个时间区域内，将时间作为一个变量，使用一个密钥信息，通过计算生成得到一个6位的数字而已，显然这个数字会随时间区域进行变化，而且只能由相同的密钥才能生成对应的数字代码。

基于以上理解，我们也可以非常简单方便的写一个自己的OTP算法，比如：


require("crypto")
.createHash("SHA1")
.update("password" +(0 | Date.now() / 30000))
.digest()
.reduce((c,v,i)=>(c[i%4] ^= v,c), Array(4).fill(0))
.reduce((c,v,i)=> c + v*256**(3-i), 0)
.toString()
.slice(-6)
.padStart(6,"0");

但一个设计良好的OPT算法要能够实现良好的离散性，所以其具体实现也是具备一定的理论依据，精选设计和实现，并且经过相关的检验和测试的。GA的验证码的实现肯定也是这样的。

上面是算法的问题，另一个问题是所使用的密钥。笔者使用时，简单的理解就是OPT密钥可以随便设置，就和普通密码规则一样，只要保证长度和复杂性就可以了。但其实不然，经过资料查证，发现GA密钥的选择是有相关规范的，简单而言就是：

“16个Base32字符”。

所以如果不注意就不能正确设置（如图）。

从Base32编解码算法理解位移运算

怎么就有非法字符了呢？请大家思考一下。因此，GA的密钥设置，不是简单的口令设置，而是真正的密钥设置。这个概念上的差别，也可以很好的帮大家理解： 口令和密码主要是给人使用的，目的是容易记忆；而密钥是给程序使用的，它本质上是基础的二进制编码，而且不用考虑可记忆性。

这里为什么不能展示截图？因为有一个简单的安全机制，就是在GA的程序界面，是不能使用程序截图的。本来这个也不是一个太大的问题，基于Base32编码规则，我们可以将任何信息都编码成Base32,但这里要考虑和GA程序的兼容，就需要使用和它一样的算法，才能得到匹配的结果。

Google Authcode 兼容编码实现

内容既然都已经写到了这里，笔者觉得索性送佛到西，进一步讨论和分析一下Google Authticator编码算法的实现。

其实其算法核心就只有以下几行(其他的可执行的代码，详见前面的示例程序)：

    // convert to hex of period value add offset
    let time = Math.floor(epoch / options.period) + options.ofset;

    // convert time to 8 byte buffer 
    let i = 8, timeBuf = Buffer.alloc(i);
    while (i-- && time) {
        timeBuf[i] = time & 0xFF;
        time >>= 8;
    };

    // hmac of time use key and counter (use buf)
    let hmac = createHmac(options.algorithm,key).update(timeBuf).digest();

    // offset of hmac 
    const offset = hmac[hmac.length - 1] & 0xf;

    let icode = 
       ((hmac[offset    ] & 0x7f) << 24)|
       ((hmac[offset + 1] & 0xff) << 16)|
       ((hmac[offset + 2] & 0xff) << 8 )|
        (hmac[offset + 3] & 0xff);

    // return padding string
    return (icode % (10 ** options.digits)).toString().padStart(options.digits,"0");

这个实现和算法的相关要点和说明如下：

  • GA的密钥，必须是一个标准Base32字符串，长度不小于16位
  • 实际计算的时候，程序会将密钥转换为字节数组使用，因为其最终调用的程序是createHmac函数
  • 看默认设置常数，我们知道GA使用SHA1摘要函数，配合HMAC，时间步进是30秒，输出为6位数字
  • 时间变量是一个整数，需要从低位向高位，转换为一个长度为8的字节数组（其实通常前面是填不满的）
  • 对时间字节数组进行摘要，密钥就是输入的Base32密钥，但同样转为字节数组
  • 得到一个长度为20的字节数组(SHA1算法确定)
  • 数组的最后一位的低位(<16)作为一个偏移值
  • 使用这个偏移值在数组中依次取出四个字节进行计算
  • 将这四个字节按照算法转换为一个整数
  • 取此整数的后六位，不足的补零
  • 得到结果编码，是长度为六的数字组成的字符串

看见了吧，这个算法里面也大量的使用了位移计算，也算是贴近本文的主题了。

关于位移计算(shift)

最后，我们来总结一下位移计算相关的内容。

位移计算(shift)是位计算(bitwise)中的一种操作(图)。由于直接操作二进制数据，所以它是一种非常基础和底层的操作。其他的位操作一般都比较好理解，因为有很多实际的应用场景和作用，而初学者甚至一些有经验的开发者对位移计算都比较陌生，因为很难在日常业务中遇到合适的使用场合。用的不多，对其理解和认知也就不那么深入了。

从Base32编解码算法理解位移运算

其实在熟悉了之后，位移计算也是可以非常直观，容易理解的。我们就通过本文中的几个场景来说明一下：

  • 取高位

对于一个字节数字 10001010， 想要取高5位，直观的操作就是向右移动三位(右边的三位自动截断)就可以了

0b10001010 >> 3 = 0b10001

  • 取低位和构造掩码

这个操作，其实间接的用到了位移。因为它的原理是先构造一个n位的掩码，然后使用掩码和原值进行与操作，就可以得到低位。而在构造掩码的过程中，可以使用位移操作。

0b10001010 & (((1 << 3) -1)) = 0b10001010 & 0b111 = 0b010

这里，要构造一个n位都是1的数，可以将1向左位移n位，再减去1就可以了。

  • 取某一个位的值

在使用位数值来表达某种状态的时候，取某一个特定位的值或者状态的需求也是比较常见的。如要取第5位的值：

(0b10110001 >> 4) & 1 = 1

  • 左移的数学意义

在数学上，向左位移的意义是乘以2，移动n位就是乘以2的n次方，以此可以进行相关的数学计算

  • 右移的数学意义

同样，在数学上，向右移位的数学意义是被2整除，这里是整数除法，会舍弃小数部分。右移n位就是连续被2整除。

  • 字节数组转整数

利用右移是乘2的特性，将字节数组转换为整数的计算就可以使用下面的方法：

[1,2,3,4].reduce((c,v,i)=>(c | (v << ((3-i) * 8))),0)

等同于: 1 * 256 * 256 * 256 + 2* 256 * 256 + 3 * 256 + 4

所以我们在字节数组的各种操作中，经常看到 << 24, << 16 等操作，其实就是在整数中按照字节定位的方式(一个字节是8位)。

  • 整数转字节数组(循环求余)

let i = 0 | Date.now()/ 1000, l = []; while(i) { l.unshift(i & 0xFF); i>>=8 };

转载自:https://juejin.cn/post/7279041076273725452
评论
请登录