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

2024-07-18 21:01:56

目录：

一、base58(58进制)

1.1 什么是base58？

1.2 辗转相除法

1.3 base58输出字节数：

二、源码分析：

2.1源代码：

2.2 算法思路介绍：

2.2.1 Base58编码过程：

2.1.2 Base58解码过程：

2.1.3 Base58Check编码过程：

2.1.4 Base58Check解码过程：

三、Base58编解码：

3.1 Base58 编码函数 encodeBase58

3.2 Base58 解码函数 decodeBase58

3.3 主函数 main

一、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 <base58.h>
#include <hash.h>
#include <uint256.h>
#include <util/strencodings.h>
#include <util/string.h>
#include <assert.h>
#include <string.h>
#include <limits>

// 使用无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<unsigned char>& 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<unsigned char> 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<unsigned char>::reverse_iterator it = b256.rbegin(); (carry != 0 || i < length) && (it != b256.rend()); ++it, ++i) {
            carry += 58 * (*it);
            *it = carry % 256;
            carry /= 256;
        }
        assert(carry == 0);
        length = i;
        if (length + zeroes > max_ret_len) return false;
        psz++;
    }
    // 跳过后导空格
    while (IsSpace(*psz))
        psz++;
    if (*psz != 0)
        return false;
    // 跳过b256中的前导零
    std::vector<unsigned char>::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<const unsigned char> 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<unsigned char> b58(size);
    // 处理字节
    while (input.size() > 0) {
        int carry = input[0];
        int i = 0;
        // 应用 "b58 = b58 * 256 + ch" 
        for (std::vector<unsigned char>::reverse_iterator it = b58.rbegin(); (carry != 0 || i < length) && (it != b58.rend()); it++, i++) {
            carry += 256 * (*it);
            *it = carry % 58;
            carry /= 58;
        }
        assert(carry == 0);
        length = i;
        input = input.subspan(1);
    }
    // 在base58结果中跳过前导零
    std::vector<unsigned char>::iterator it = b58.begin() + (size - length);
    while (it != b58.end() && *it == 0)
        it++;
    // 将结果转化为字符串
    std::string str;
    str.reserve(zeroes + (b58.end() - it));
    str.assign(zeroes, '1');
    while (it != b58.end())
        str += pszBase58[*(it++)];
    return str;
}

// 定义一个函数DecodeBase58，用于解码输入的Base58字符串，返回转换后的字节序列
bool DecodeBase58(const std::string& str, std::vector<unsigned char>& vchRet, int max_ret_len)
{
    if (!ContainsNoNUL(str)) {
        return false;
    }
    return DecodeBase58(str.c_str(), vchRet, max_ret_len);
}

// 定义一个函数EncodeBase58Check，用于将输入的字节序列编码为添加了4字节hash校验的Base58字符串
std::string EncodeBase58Check(Span<const unsigned char> input)
{
    // 在结束处添加4字节的hash校验
    std::vector<unsigned char> vch(input.begin(), input.end());
    uint256 hash = Hash(vch);
    vch.insert(vch.end(), (unsigned char*)&hash, (unsigned char*)&hash + 4);
    return EncodeBase58(vch);
}

[[nodiscard]] static bool DecodeBase58Check(const char* psz, std::vector<unsigned char>& vchRet, int max_ret_len)
{
    if (!DecodeBase58(psz, vchRet, max_ret_len > std::numeric_limits<int>::max() - 4 ? std::numeric_limits<int>::max() : max_ret_len + 4) ||
        (vchRet.size() < 4)) {
        vchRet.clear();
        return false;
    }
    // 重新计算校验和，确保它匹配包含的4字节校验和
    uint256 hash = Hash(Span{vchRet}.first(vchRet.size() - 4));
    if (memcmp(&hash, &vchRet[vchRet.size() - 4], 4) != 0) {
        vchRet.clear();
        return false;
    }
    vchRet.resize(vchRet.size() - 4);
    return true;
}

bool DecodeBase58Check(const std::string& str, std::vector<unsigned char>& vchRet, int max_ret)
{
    if (!ContainsNoNUL(str)) {
        return false;
    }
    return DecodeBase58Check(str.c_str(), vchRet, max_ret);
}

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 <iostream>
#include <string>
#include <vector>
#include <algorithm>

// 定义Base58编码的字符集
static const std::string BASE58_ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

// Base58编码函数
std::string encodeBase58(const unsigned char* input, size_t len) {
    std::vector<unsigned int> digits(40, 0); // 用于存储Base58表示的向量，初始全为0
    size_t digits_len = 1; // 有效位数长度，初始为1

    // 对输入数据的每个字节进行处理
    for (size_t i = 0; i < len; i++) {
        unsigned int carry = input[i]; // 当前字节值
        for (size_t j = 0; j < digits_len; j++) {
            carry += digits[j] * 256; // 将当前值加到之前的结果
            digits[j] = carry % 58; // 计算Base58的当前位
            carry /= 58; // 更新进位
        }

        // 处理剩余的进位
        while (carry) {
            digits[digits_len++] = carry % 58;
            carry /= 58;
        }
    }

    std::string output;
    // 处理前导0的特殊情况，Base58用'1'表示前导0
    for (int i = 0; i < len && input[i] == 0; i++) {
        output += '1';
    }

    // 将计算得到的Base58位数转换为字符
    for (size_t i = 0; i < digits_len; i++) {
        output += BASE58_ALPHABET[digits[digits_len - 1 - i]];
    }

    return output; // 返回编码后的字符串
}

// Base58解码函数
std::vector<unsigned char> decodeBase58(const std::string& input) {
    std::vector<unsigned char> output; // 初始化输出向量

    // 对输入的每个字符进行处理
    for (size_t i = 0; i < input.length(); i++) {
        int value = BASE58_ALPHABET.find(input[i]); // 查找字符在Base58字符集中的位置
        if (value == std::string::npos) {
            // 如果字符不在Base58字符集中，返回空向量表示解码失败
            return {};
        }

        for (size_t j = 0; j < output.size(); j++) {
            value += output[j] * 58; // 更新当前位
            output[j] = value % 256; // 计算当前位的值
            value /= 256; // 更新进位
        }

        // 处理剩余的进位
        while (value) {
            output.push_back(value % 256);
            value /= 256;
        }
    }

    // 处理前导'1'的特殊情况，对应前导0字节
    for (size_t i = 0; i < input.length() && input[i] == '1'; i++) {
        output.push_back(0);
    }

    // 逆转输出向量以匹配原始输入的顺序
    std::reverse(output.begin(), output.end());

    return output; // 返回解码后的字节向量
}

int main() {
    const std::string input_data = "Hello, world!"; // 要编码的输入数据
    std::cout << "原始数据：" << input_data << "\n";

    // 调用编码函数
    std::string encoded = encodeBase58(reinterpret_cast<const unsigned char*>(input_data.data()), input_data.size());
    std::cout << "Encoded编码后: " << encoded << "\n";

    // 调用解码函数
    std::vector<unsigned char> decoded = decodeBase58(encoded);
    std::string decodedStr(decoded.begin(), decoded.end());
    std::cout << "Decoded解码后: " << decodedStr << "\n";

    return 0; // 返回0表示程序成功执行
}

3.1 Base58 编码函数 `encodeBase58`

这个函数用于将字节数组编码为Base58字符串。

输入: const unsigned char* input, size_t len，表示输入的字节数组及其长度。
处理:
- 使用一个vector<unsigned int>来临时存储计算的数字，这个向量的长度被初始化为40，足以处理常见的输入长度。
- 通过多重循环，将输入的字节转换为Base58编码。内部逻辑处理了进位，这对于任何基数的转换都是必需的。
- 处理前导0，因为Base58编码中前导0用'1'字符表示。

3.2 Base58 解码函数 `decodeBase58`

这个函数用于将Base58编码的字符串解码回原始的字节数据。

输入: const std::string& input，Base58编码的字符串。
处理:
- 初始化一个动态大小的vector<unsigned char>用于存储解码的结果。
- 遍历输入的每一个字符，找出其在Base58字符集中的索引，这个索引值代表了其对应的数值。
- 通过计算和处理进位，将Base58编码转换回字节。
- 处理Base58编码中的前导'1'，这些'1'在解码时应转换为前导0字节。
- 最后，由于解码过程中字节被逆向存储，需要将结果向量反转以恢复初始的字节顺序。

3.3 主函数 `main`

功能: 测试encodeBase58和decodeBase58函数，使用字符串"Hello, world!"作为输入。
输出:
- 显示原始数据。
- 显示编码后的Base58字符串。
- 显示解码后的字符串，应与原始输入相同。

码农公寓

目录：