the cryptopals crypto challenges (Set 1)

folder_open笔记
comment没有评论

本站遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0),原创文章转载请注明出处。

前言

著名的 「密友」 密码学挑战,号称每一个程序员都应该掌握,并且据说是用来学习一门新编程语言的好例程。

所以我决定尽量分别用 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 – 维基百科,自由的百科全书

直观举例(引用自维基百科):

编码「Man」编码 「Man」

在此例中,Base64 算法将 3 个字节编码为 4 个字符。

如果要编码的字节数不能被 3 整除,最后会多出 1 个或 2 个字节,那么可以使用下面的方法进行处理:先使用 0 字节值在末尾补足,使其能够被 3 整除,然后再进行 Base64 的编码。在编码后的 Base64 文本后加上一个或两个=号,代表补足的字节数。也就是说,当最后剩余两个八位 (待补足) 字节(2 个 byte)时,最后一个 6 位的 Base64 字节块有四位是 0 值,最后附加上两个等号;如果最后剩余一个八位(待补足)字节(1 个 byte)时,最后一个 6 位的 base 字节块有两位是 0 值,最后附加一个等号。 参考下表:

待补足待补足

思路

算法不太复杂,因此思路也比较简单:

  1. 读取十六进制字符串,并以数值形式存储
  2. 每三个字节分割后,每六位查表转换为字符输出
  3. 最后注意下补等号的问题就行了

熟悉规则后,我们便可以开始编写代码了。

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 &currentByte = 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

待补充。

浏览量: 107
标签:

相关文章

HITCTF 2020 reverse1 HelloReverse Writeup

笔记

WPF 实现透明边框虚化窗口

笔记

为什么函数 f(x)=x² 不是满射

笔记

发表评论

您的电子邮箱地址不会被公开。

填写此字段
填写此字段
请输入有效的电子邮箱地址。
您需要同意条款才能继续

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

菜单