【常见开源库的二次开发】基于openssl的加密与解密——Base58比特币钱包地址——算法分析（三）

07-16 1483阅读

一、base58(58进制)

1.1 什么是base58？

Base58编码是在Base64字符集基础上，为了避免混淆而进行的优化。它去除了在Base64中可能引起混淆的字符，包括数字0、大写字母O、小写字母l、大写字母I，以及“+”和“/”两个符号。这样的设计使得Base58在视觉上更为清晰，减少错误。

Base58采用了一种相当别致的处理方法，它并未像Base16或Base64那样规律性的按位处理。相反，我们采用了一种称为"辗转相除法"的处理方式。这种方法虽然与传统方式不同，但却同样有效，进一步增强了编码的清晰度和可读性。

1.2 辗转相除法

欧几里得算法，也称为辗转相除法，是一种高效求解两个数最大公约数的方法。这种算法的核心思想在于：两个数的最大公约数等于其中较小的数与它们的差的最大公约数。这个算法不仅简洁，而且在数学和计算机科学中应用广泛。

Base58编码中，字符从'1'开始映射，其中'1'代表数字0，'2'代表数字1，一直到'z'代表数字57。这种映射策略有助于在编码时减少混淆，并保持数据的清晰易读。

对于将一个数字转换为Base58编码，我们用辗转相除法，这可以通过以下步骤来说明：

以数字1234为例，转换为58进制的过程如下：

将1234除以58，得到商21和余数16。根据Base58的编码表，余数16对应字符'H'。
接着将商21除以58，得到商0和余数21。根据Base58的编码表，余数21对应字符'N'。

因此，1234在Base58编码中表示为“NH”。

对于数字前有一个或多个0的情况，按Base58的编码规则，每一个0都直接转换为字符'1'。例如，如果数字是001234，那么在Base58编码中，它将表示为“11NH”。这里，前面的两个0分别转换为两个'1'，紧接着是由1234转换来的“NH”。

1.3 base58输出字节数：

在Base58编码中，每个字符来自58个可选字符，因此每个字符需要表示的位数是log2(58)，也即每个字符携带的信息量为log2(58)位。

对于输入的字节数据，其长度为(length * 8)位。所以，需要预留的字符数量就是(length * 8) / log2(58)。

换句话说，为了表示一个字节（8位）的信息，Base58编码需要的字符长度为1 / log2(58)，即大约1.38个字符。这意味着每个Base58字符能够表示的信息比二进制编码要多，从而提高了编码效率。

二、源码分析：

2.1源代码：

实现了Base58编码与解码的相关功能，包括对输入的字节序列进行Base58编码、对Base58编码的字符串进行解码，并且包含了对Base58Check编码的支持（这是一种在Base58编码的基础上添加了校验和的编码方式，用于提高数据的传输可靠性）。

//版权信息 (c) 2014-2022 比特币核心开发者
//在MIT软件许可下分发，参见附带的
//复制文件或http://www.opensource.org/licenses/mit-license.php.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
// 使用无NUL包含的工具
using util::ContainsNoNUL;
/** 所有的字母数字除了 "0", "I", "O", 和 "l" */
//定义一个Base58编码表
static const char* pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"; 
//定义一个映射表，将输入字符映射为对应的整数值
static const int8_t mapBase58[256] = { 
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1, 0, 1, 2, 3, 4, 5, 6,  7, 8,-1,-1,-1,-1,-1,-1,
    -1, 9,10,11,12,13,14,15, 16,-1,17,18,19,20,21,-1,
    22,23,24,25,26,27,28,29, 30,31,32,-1,-1,-1,-1,-1,
    -1,33,34,35,36,37,38,39, 40,41,42,43,-1,44,45,46,
    47,48,49,50,51,52,53,54, 55,56,57,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
    -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
};
// 定义一个函数DecodeBase58，用于解码输入的Base58字符串，返回转换后的字节序列
[[nodiscard]] static bool DecodeBase58(const char* psz, std::vector& vch, int max_ret_len)
{
    // 跳过前导空格
    while (*psz && IsSpace(*psz))
        psz++;
    // 跳过并计数前导的'1's
    int zeroes = 0;
    int length = 0;
    while (*psz == '1') {
        zeroes++;
        if (zeroes > max_ret_len) return false;
        psz++;
    }
    // 在大端base256表示中分配足够的空间
    int size = strlen(psz) * 733 /1000 + 1; // log(58) / log(256), 向上取整
    std::vector b256(size);
    // 处理字符
    static_assert(std::size(mapBase58) == 256, "mapBase58.size() should be 256"); // 保证不超出范围
    while (*psz && !IsSpace(*psz)) {
        // 解码base58字符
        int carry = mapBase58[(uint8_t)*psz];
        if (carry == -1)  // 无效的b58字符
            return false;
        int i = 0;
        for (std::vector::reverse_iterator it = b256.rbegin(); (carry != 0 || i  max_ret_len) return false;
        psz++;
    }
    // 跳过后导空格
    while (IsSpace(*psz))
        psz++;
    if (*psz != 0)
        return false;
    // 跳过b256中的前导零
    std::vector::iterator it = b256.begin() + (size - length);
    // 将结果复制到输出向量
    vch.reserve(zeroes + (b256.end() - it));
    vch.assign(zeroes, 0x00);
    while (it != b256.end())
        vch.push_back(*(it++));
    return true;
}
// 定义一个函数EncodeBase58，用于将输入的字节序列编码为Base58字符串
std::string EncodeBase58(Span input)
{
    // 跳过和计数前导零
    int zeroes = 0;
    int length = 0;
    while (input.size() > 0 && input[0] == 0) {
        input = input.subspan(1);
        zeroes++;
    }
    // 在大端base58表示中分配足够的空间
    int size = input.size() * 138 / 100 + 1; // log(256) / log(58), 向上取整
    std::vector b58(size);
    // 处理字节
    while (input.size() > 0) {
        int carry = input[0];
        int i = 0;
        // 应用 "b58 = b58 * 256 + ch" 
        for (std::vector::reverse_iterator it = b58.rbegin(); (carry != 0 || i  std::numeric_limits::max() - 4 ? std::numeric_limits::max() : max_ret_len + 4) ||
        (vchRet.size()  
2.2 算法思路介绍： 
Base58编码是一种常用于加密货币地址和某些区块链应用中的编码方式，它使用了58个字符（排除了容易混淆的字符，如0（零）、O（大写的o）、I（大写的i）和l（小写的L）），以提供一种相对于Base64更容易人工阅读和手写的编码系统。 
2.2.1 Base58编码过程： 
计算输入数据的大小：输入数据（通常是一串字节）首先被评估以确定其长度和所需的编码空间大小。
处理前导零：Base58编码保留了输入数据中的前导零字节（0x00），每个前导零字节在编码字符串中用字符'1'表示。
转换为Base58：剩余的输入数据被转换为一个大整数，然后这个大整数被转换成Base58表示，即通过不断除以58并取余数的方式获得一系列的Base58字符。
拼接结果：最终的编码字符串由步骤2中处理的前导零（每个零用'1'表示）和步骤3的转换结果组成。
2.1.2 Base58解码过程： 
校验并移除前导'1'：解码首先会检查编码字符串中前导的'1'字符，并记录其数量，因为每个'1'代表一个前导零字节。
Base58到大整数：然后将Base58编码字符串转换回一个大整数，即通过对每个Base58字符进行查表操作，获取对应的数值，并将这些数值以58为基数合并成一个大整数。
转换为字节序列：这个大整数随后被转换回原始的字节序列。
重建前导零：根据步骤1中记录的前导'1'的数量，在解码后的字节序列前加上相应数量的零字节。
2.1.3 Base58Check编码过程： 
Base58Check是在Base58的基础上增加了错误检测的能力。它通常包括以下几个步骤： 
计算校验和：对输入数据计算校验和（如，通过SHA-256算法计算两次，取前四个字节作为校验和）。
添加校验和：将这个校验和添加到原始数据的末尾。
Base58编码：将步骤2得到的字节序列进行Base58编码。
2.1.4 Base58Check解码过程： 
Base58解码：首先对编码字符串进行Base58解码。
验证校验和：从解码结果中提取末尾四个字节作为校验和，与剩余数据重新计算的校验和进行比较。
提取数据：如果校验和匹配，说明数据未被篡改，去掉末尾四个字节的校验和，返回剩余的数据部分。
这些步骤中对前导零的特殊处理（编码中的'1'字符和解码时的零字节）是Base58和Base58Check编码的一个重要特性，确保了编码结果的唯一性和解码的准确性。 
三、Base58编解码： 
Base58编码和解码的实现。Base58是一种用于比特币等加密货币中的编码方案，它避开了某些视觉上容易混淆的字符，比如0（数字零）、O（大写字母O）、I（大写字母I）和l（小写字母L）。 
#include 
#include 
#include 
#include 
// 定义Base58编码的字符集
static const std::string BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
// Base58编码函数
std::string encodeBase58(const unsigned char* input, size_t len) {
    std::vector digits(40, 0); // 用于存储Base58表示的向量，初始全为0
    size_t digits_len = 1; // 有效位数长度，初始为1
    // 对输入数据的每个字节进行处理
    for (size_t i = 0; i