前言
著名的 「密友」 密码学挑战,号称每一个程序员都应该掌握,并且据说是用来学习一门新编程语言的好例程。
所以我决定尽量分别用 C++、C# 和 Python 各实现一遍,求异存同,也算是给自己增加一点编码和密码学方面的新姿♂势 XD
那么现在我们要处理的是第一部分(Set 1)。按原文描述,这套题是 qualifying set,所以应该是相对简单。尤其是对于现代高级语言来说有不少写好的库可以调用。但是,既然是密码学挑战,我们自然不能完全把算法丢给别人的库来处理,尽量还是要细致入微地手写过程。
话不多说,开淦。
Challenge 1
审题
题目:Convert hex to base64,将十六进制编码为 Base64。
知识点:Base64
首先我们来了解一下 Base64 编码,根据维基百科:
转换的时候,将 3 字节的数据,先后放入一个 24 位的缓冲区中,先来的字节占高位。数据不足 3 字节的话,于缓冲器中剩下的比特用 0 补足。每次取出 6 比特(因为 26 = 64),按照其值选择
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
中的字符作为编码后的输出,直到全部输入数据转换完成。若原数据长度不是 3 的倍数时且剩下 1 个输入数据,则在编码结果后加 2 个
=
;若剩下 2 个输入数据,则在编码结果后加 1 个=
。
直观举例(引用自维基百科):
在此例中,Base64 算法将 3 个字节编码为 4 个字符。
如果要编码的字节数不能被 3 整除,最后会多出 1 个或 2 个字节,那么可以使用下面的方法进行处理:先使用 0 字节值在末尾补足,使其能够被 3 整除,然后再进行 Base64 的编码。在编码后的 Base64 文本后加上一个或两个=
号,代表补足的字节数。也就是说,当最后剩余两个八位 (待补足) 字节(2 个 byte)时,最后一个 6 位的 Base64 字节块有四位是 0 值,最后附加上两个等号;如果最后剩余一个八位(待补足)字节(1 个 byte)时,最后一个 6 位的 base 字节块有两位是 0 值,最后附加一个等号。 参考下表:
思路
算法不太复杂,因此思路也比较简单:
- 读取十六进制字符串,并以数值形式存储
- 每三个字节分割后,每六位查表转换为字符输出
- 最后注意下补等号的问题就行了
熟悉规则后,我们便可以开始编写代码了。
C++ 代码
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
// 常量声明
const string BASE64_TABLE = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/;
const string FILL = =;
int main()
{
cout << Convert hex to base64: << endl;
string input;
getline(cin, input);
// 以 3 字节(6 字符)计算出长度以及最后剩余的字节数
int size = input.length() / 6, bytesLeft = input.length() / 2 % 3;
// 每 6 字符插入一个空格,便于稍后读取
for (size_t i = 6; i < input.length(); i += 6)
input.insert(i++, 1, ' ');
stringstream ss;
ss << input;
int tmp;
vector<int> bytes;
// 十六进制数读入,此处便实现了将字符转换为数值的操作
while (ss >> hex >> tmp)
bytes.push_back(tmp);
// 若字节数不能被 3 整除(有字节剩余),则将剩余的字节另外处理
int count = (bytesLeft) ? bytes.size() - 1 : bytes.size();
for (size_t i = 0; i < count; i++)
{
// 这里是声明了一个对当前所操作(3 个)字节的引用
auto ¤tByte = bytes[i];
char characters[5]{}; // 待输出的字符,加上空字符共 5 个字符
for (int j = 3, order; j >= 0; j--)
{
order = 0;
for (size_t k = 0; k < 6; k++, currentByte >>= 1)
order += (currentByte & 1) << k; // 依次取最低 6 位转换为十进制
characters[j] = BASE64_TABLE[order]; // 查表
}
cout << characters; // 输出
}
// 如果存在剩余的字节则进行额外处理
if (bytesLeft)
{
char characters[4]{};
for (int i = bytesLeft, order; i >= 0; i--)
{
order = 0;
for (size_t j = 0; j < 6; j++, bytes.back() >>= 1)
order += (bytes.back() & 1) << j;
characters[i] = BASE64_TABLE[order];
}
cout << characters << (bytesLeft == 1 ? FILL + FILL : FILL);
}
}
C# 和 Python 都有内置的 Base64 编解码方法,所以这里把使用内置方法的简短版本也贴一份出来,以供参考。
C# 代码
using System;
namespace Challenge_1
{
class Program
{
// 常量声明
private const string Base64Table = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/;
private const string Fill = =;
static void Main(string[] args)
{
Console.WriteLine(Convert hex to base64:);
string input = Console.ReadLine();
// 以 3 字节(6 字符)计算出最后剩余的字节数
int bytesLeft = input.Length / 2 % 3;
// 每 6 字符插入一个空格,便于稍后分割
for (int i = 6; i < input.Length; i += 6)
input = input.Insert(i++, );
// 以空格分割数据
string[] rawHexData = input.Split(' ');
int[] bytes = new int[rawHexData.Length];
// 直接将其以十六进制格式转换为整数
for (int i = 0; i < rawHexData.Length; i++)
bytes[i] = int.Parse(rawHexData[i], System.Globalization.NumberStyles.HexNumber);
// 若字节数不能被 3 整除(有字节剩余),则将剩余的字节另外处理
int count = bytesLeft > 0 ? bytes.Length - 1 : bytes.Length;
for (int i = 0; i < count; i++)
{
var characters = new char[4]; // 待输出的字符
for (int j = 3, order; j >= 0; j--)
{
order = 0;
for (int k = 0; k < 6; k++, bytes[i] >>= 1)
order += (bytes[i] & 1) << k; // 依次取最低 6 位转换为十进制
characters[j] = Base64Table[order]; // 查表
}
Console.Write(characters); // 输出
}
// 如果存在剩余的字节则进行额外处理
if (bytesLeft > 0)
{
var characters = new char[3];
for (int i = bytesLeft, order; i >= 0; i--)
{
order = 0;
for (int j = 0; j < 6; j++, bytes[bytes.Length - 1] >>= 1)
order += (bytes[bytes.Length - 1] & 1) << j;
characters[i] = Base64Table[order];
}
// 字符数组无法用 + 号和字符串拼接,所以这里分别输出
Console.Write(characters);
Console.Write(bytesLeft == 1 ? Fill + Fill : Fill);
}
}
}
}
简短版本:
using System;
namespace Challenge_1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Convert hex to base64:);
string input = Console.ReadLine();
byte[] bytes = Convert.FromHexString(input);
Console.WriteLine(Convert.ToBase64String(bytes));
}
}
}
Python 代码
# -*- coding: utf-8 -*-
# 常量声明
BASE64_TABLE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
FILL = '='
msg = input(Convert hex to base64:\n)
# 以 3 字节(6 字符)计算出最后剩余的字节数
bytes_left = len(msg) // 2 % 3
# 直接按长度分割字符串,Python 真方便
raw_hex_data = [msg[i: i + 6] for i in range(0, len(msg), 6)]
# 以十六进制格式转换为整数
data = [int(raw_hex_data[i], 16) for i in range(0, len(raw_hex_data))]
# 若字节数不能被 3 整除(有字节剩余),则将剩余的字节另外处理
cnt = len(data) - 1 if bytes_left > 0 else len(data)
for i in range(0, cnt):
characters = '' # 待输出的字符
for j in range(3, -1, -1):
order = 0
for k in range(0, 6):
# 依次取最低 6 位转换为十进制
order += (data[i] & 1) << k
data[i] >>= 1
# 查表。由于 Python 没有字符数组而字符串也无法修改,这里直接拼接在前面
characters = BASE64_TABLE[order] + characters
print(characters, end='') # 输出
# 如果存在剩余的字节则进行额外处理
if bytes_left > 0:
characters = ''
for i in range(bytes_left, -1, -1):
order = 0
for j in range(0, 6):
order += (data[len(data) - 1] & 1) << j
data[len(data) - 1] >>= 1
characters = BASE64_TABLE[order] + characters
print(characters + FILL * 2 if bytes_left == 1 else FILL, end='')
简短版本:
import base64
msg = input(Convert hex to base64:\n)
tmp = bytes.fromhex(msg)
ans = base64.b64encode(tmp)
print(ans.decode())
方便行事,这里的十六进制读取部分已经最简化,但编码一块仍然手动进行。
由于我首先写了 C++ ,C# 和 Python 的代码基本上就是直接翻译来的,这样比较方便(懒ˋ( ° ▽、° )),估计并不咋能体现出语言特性(毕竟我菜)。如果你有更好的解法当然是欢迎在下方留言辣。
Challenge 2
待补充。