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

 目录：

 目录：

一、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进制的过程如下：

1. 将1234除以58，得到商21和余数16。根据Base58的编码表，余数16对应字符'H'。
2. 接着将商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'sint 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编码过程：

1. 计算输入数据的大小：输入数据（通常是一串字节）首先被评估以确定其长度和所需的编码空间大小。
2. 处理前导零：Base58编码保留了输入数据中的前导零字节（0x00），每个前导零字节在编码字符串中用字符'1'表示。
3. 转换为Base58：剩余的输入数据被转换为一个大整数，然后这个大整数被转换成Base58表示，即通过不断除以58并取余数的方式获得一系列的Base58字符。
4. 拼接结果：最终的编码字符串由步骤2中处理的前导零（每个零用'1'表示）和步骤3的转换结果组成。

2.1.2 Base58解码过程：

1. 校验并移除前导'1'：解码首先会检查编码字符串中前导的'1'字符，并记录其数量，因为每个'1'代表一个前导零字节。
2. Base58到大整数：然后将Base58编码字符串转换回一个大整数，即通过对每个Base58字符进行查表操作，获取对应的数值，并将这些数值以58为基数合并成一个大整数。
3. 转换为字节序列：这个大整数随后被转换回原始的字节序列。
4. 重建前导零：根据步骤1中记录的前导'1'的数量，在解码后的字节序列前加上相应数量的零字节。

2.1.3 Base58Check编码过程：

Base58Check是在Base58的基础上增加了错误检测的能力。它通常包括以下几个步骤：

1. 计算校验和：对输入数据计算校验和（如，通过SHA-256算法计算两次，取前四个字节作为校验和）。
2. 添加校验和：将这个校验和添加到原始数据的末尾。
3. Base58编码：将步骤2得到的字节序列进行Base58编码。

2.1.4 Base58Check解码过程：

1. Base58解码：首先对编码字符串进行Base58解码。
2. 验证校验和：从解码结果中提取末尾四个字节作为校验和，与剩余数据重新计算的校验和进行比较。
3. 提取数据：如果校验和匹配，说明数据未被篡改，去掉末尾四个字节的校验和，返回剩余的数据部分。

这些步骤中对前导零的特殊处理（编码中的'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表示的向量，初始全为0size_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'表示前导0for (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字符串。
  • 显示解码后的字符串，应与原始输入相同。