玩着玩着CTF发现我基础太差了，很多基本原理算法都没有摸清，因为以前大多数用工具就可以解出来，所以没有太在意算法之类，但我最近遇到了一道题，它的Base64映射表换一下我就完全摸不着头脑。所以这篇笔记就来了。

1. Base64

将三个byte的数据，先后放入一个24bit的缓冲区中，先来的byte占高位。数据不足3byte的话，于缓冲器中剩下的bit用0补足。然后，每次取出6（因为$2^6=64$）个bit，按照其值选择索引表中的字符作为编码后的输出。不断进行，直到全部输入数据转换完成。需要注意的是，补4bit后面两个等号，补2bit后面一个等号。这样在解码时，如果有一个等号就往前删2bit无效位，两个等号往前删4bit无效位。

当原数据长度不是3的整数倍时，如果最后剩下一个输入数据，在编码结果后加2个“=”；如果最后剩下两个输入数据，编码结果后加1个“=”；如果没有剩下任何数据，就什么都不要加，这样才可以保证数据还原的正确性。

Base64的编码范围是A-Za-z0-9+/，Base64索引表：

例如“Man”：

例如“A”和“BC”：

Python版Base64加解密：

import base64
import string
# base 字符集
base64_charset = string.ascii_uppercase + string.ascii_lowercase + string.digits + '+/'
# base64_charset = "vwxrstuopq34567ABCDEFGHIJyz012PQRSTKLMNOZabcdUVWXYefghijklmn89+/"

def encode(origin_bytes):

     # 将每⼀位bytes转换为二进制字符串，用bin转换后是0b开头的，所以把0b替换了，首位补0补齐8位
    base64_bytes = ['{:0>8}'.format(str(bin(b)).replace('0b', '')) for b in origin_bytes]
     
    resp = ''
    nums = len(base64_bytes) // 3
    remain = len(base64_bytes) % 3     
    integral_part = base64_bytes[0:3 * nums]
    
    while integral_part:
         # 取三个字节，以每6⽐特，转换为4个整数
         tmp_unit = ''.join(integral_part[0:3])
         tmp_unit = [int(tmp_unit[x: x + 6], 2) for x in [0, 6, 12, 18]]
         # 取对应base64字符
         resp += ''.join([base64_charset[i] for i in tmp_unit])
         integral_part = integral_part[3:]
    
    if remain:
         # 补⻬三个字节，每个字节补充 0000 0000
         remain_part = ''.join(base64_bytes[3 * nums:]) + (3 - remain) * '0' * 8
         # 取三个字节，以每6⽐特，转换为4个整数
         # 剩余1字节可构造2个base64字符，补充==；剩余2字节可构造3个base64字符，补充=
         tmp_unit = [int(remain_part[x: x + 6], 2) for x in [0, 6, 12, 18]][:remain + 1]
         resp += ''.join([base64_charset[i] for i in tmp_unit]) + (3 - remain) * '='
    
    return resp

def decode(base64_str):
    if not valid_base64_str(base64_str):
        return bytearray()
    
    base64_bytes = ['{:0>6}'.format(str(bin(base64_charset.index(s))).replace('0b','')) for s in base64_str if s != '=']
    resp = bytearray()
    nums = len(base64_bytes) // 4
    remain = len(base64_bytes) % 4
    integral_part = base64_bytes[0:4 * nums]
    
    while integral_part:
         # 取4个6位base64字符，作为3个字节
         tmp_unit = ''.join(integral_part[0:4])
         tmp_unit = [int(tmp_unit[x: x + 8], 2) for x in [0, 8, 16]]
         for i in tmp_unit:
            resp.append(i)
         integral_part = integral_part[4:]
 
    if remain:
         remain_part = ''.join(base64_bytes[nums * 4:])
         tmp_unit = [int(remain_part[i * 8:(i + 1) * 8], 2) for i in range(remain - 1)]
         for i in tmp_unit:
         	resp.append(i)
    return resp

def valid_base64_str(b_str):
    if len(b_str) % 4:
     	return False
    for m in b_str:
     	if m != "=" and m not in base64_charset:
     		return False
    return True

if __name__ == '__main__':
     local_base64 = "MDUzOTdjNDJmOWI2ZGE1OTNhMzY0NDE2MmQzNmViMDE="
     print('使用本地base64解密：', decode(local_base64).decode())
'''
使用本地base64解密： 05397c42f9b6da593a3644162d36eb01
'''

使用Python中的Base64模块加解密：

import base64

s = "你好!v5le0n9"

bs = base64.b64encode(s.encode("utf-8")) # 将字符为unicode编码转换为utf-8编码
print(bs)

bbs = str(base64.b64decode(bs), "utf-8")
print(bbs) # 解码

bs = str(base64.b64encode(s.encode("utf-8")), "utf-8")
print(bs) # 去掉编码结果前的 b

bbs = str(base64.b64decode(bs), "utf-8")
print(bbs) # 解码
'''
b'5L2g5aW9IXY1bGUwbjk='
你好!v5le0n9
5L2g5aW9IXY1bGUwbjk=
你好!v5le0n9
'''

2. Base32

Base32编码使用32个ASCII字符对任何数据进行编码，Base32与Base64的实现原理类似，同样是将原数据二进制形式取指定位数转换为ASCII码。首先获取数据的二进制形式，将其串联起来，每5个比特为一组进行切分($2^5=32$)，每一组内的5个比特可转换到指定的32个ASCII字符中的一个，将转换后的ASCII字符连接起来，就是编码后的数据。

Base32的编码范围有两种，比较常用的是A-Z2-7，还有一种十六进制字符表0-9A-V。既然它是按5个比特切分，肯定需要填充字符，填充字符也是等号。等号可能有6个、4个、3个、1个。

使用Python中的Base64模块加解密：

import base64

s = "你好v5le0n9"

bs = base64.b32encode(s.encode("utf-8")) # 将字符为unicode编码转换为utf-8编码
print(bs)

bbs = str(base64.b32decode(bs), "utf-8")
print(bbs) # 解码

bs = str(base64.b32encode(s.encode("utf-8")), "utf-8")
print(bs) # 去掉编码结果前的 b

bbs = str(base64.b32decode(bs), "utf-8")
print(bbs) # 解码
'''
b'4S62BZNFXV3DK3DFGBXDS==='
你好v5le0n9
4S62BZNFXV3DK3DFGBXDS===
你好v5le0n9
'''

3. Base16

Base16编码使用16个ASCII字符对任何数据进行编码，Base16与Base64的实现原理类似，同样是将原数据二进制形式取指定位数转换为ASCII码。首先获取数据的二进制形式，将其串联起来，每4个比特为一组进行切分，所以不用填充符，每一组内的4个比特可转换到指定的16个ASCII字符中的一个，将转换后的ASCII字符连接起来，就是编码后的数据。

Base16依赖更小的字典，Base16编码时每4个字符为一个分组，字典的长度为$2^4=16$，字典值如下：

Value	Encoding	Value	Encoding	Value	Encoding	Value	Encoding
0	0	4	4	8	8	12	C
1	1	5	5	9	9	13	D
2	2	6	6	10	A	14	E
3	3	7	7	11	B	15	F

使用Python中的Base64模块加解密：

import base64

s = "你好!v5le0n9"

bs = base64.b16encode(s.encode("utf-8")) # 将字符为unicode编码转换为utf-8编码
print(bs)

bbs = str(base64.b16decode(bs), "utf-8")
print(bbs) # 解码

bs = str(base64.b16encode(s.encode("utf-8")), "utf-8")
print(bs) # 去掉编码结果前的 b

bbs = str(base64.b16decode(bs), "utf-8")
print(bbs) # 解码
'''
b'E4BDA0E5A5BD2176356C65306E39'
你好!v5le0n9
E4BDA0E5A5BD2176356C65306E39
你好!v5le0n9
'''

4. Base58

前三种Base都是用比特切分的方法来编码与解码，而下面几种都是用辗转相除法来编码和解码的。

与Base64一样，Base58编码的作用也是将非可视字符可视化（ASCII化）。但不同的是Base58编码去掉了几个看起来会产生歧义的字符，如 0 (零), O (大写字母O), I (大写的字母i) and l (小写的字母L) ，和几个影响双击选择的字符，如/, +。结果字符集正好58个字符(包括9个数字，24个大写字母，25个小写字母)。而且因为58不是2的整次幂，所以没有使用类似Base64编码中使用直接截取3个字符转4个字符（$38=46$ , 2的6次方刚好64）的方法进行转换，而是采用我们数学上经常使用的进制转换方法——辗转相除法（本质上，Base64编码是64进制，Base58是58进制）。看下Base58的编码表：

也就是字符1代表0，字符2代表1,字符3代表2…字符z代表57。然后回一下辗转相除法。

如要将1234转换为58进制；

第一步：1234除于58，商21，余数为16，查表得H

第二步：21除于58，商0，余数为21，查表得N

所以得到Base58编码为：NH

Python版Base58加解密：

def b58encode(tmp:str) -> str:
	tmp = list(map(ord,tmp))
	temp = tmp[0]
	base58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
	for i in range(len(tmp)-1):
		temp = temp * 256 + tmp[i+1]
	tmp = []
	while True:
		tmp.insert(0,temp % 58)
		temp = temp // 58
		if temp == 0:
			break
	temp = ""
	for i in tmp:
		temp += base58[i]
	return temp

def b58decode(tmp:str) -> str:
	import binascii
	base58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
	temp = []
	for i in tmp:
		temp.append(base58.index(i))
	tmp = temp[0]
	for i in range(len(temp)-1):
		tmp = tmp * 58 + temp[i+1]
	return binascii.unhexlify(hex(tmp)[2:].encode("utf-8")).decode("UTF-8")

print(b58encode("ABDCDEFGA"))
print(b58decode("qBLiPgShKjap"))
'''
qBLiPgShKjap
ABDCDEFGA
'''

5. Base36

Base36本质上就是36进制，编码范围0-9A-Z，只支持整数输入。

Python版Base36加解密：

def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    """Converts an integer to a base36 string."""
    if not isinstance(number, (int, int)):
        raise TypeError('number must be an integer')

    base36 = ''
    sign = ''

    if number < 0:
        sign = '-'
        number = -number

    # 如果输入的整数大于等于0小于36，直接返回索引表中的值
    if 0 <= number < len(alphabet):
        return sign + alphabet[number]
	
    # 商，余数 = divmod(被除数，除数)
    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def base36decode(number):
    return int(number, 36)

print (base36encode(35))
print (base36encode(6271023))
print (base36decode('3QER3'))
'''
Z
3QER3
6271023
'''

6. Base62

Base62的编码范围是0-9a-zA-Z，同样也是按进制来编码，也是只支持输入整数。

Python版Base62加解密：

BASE62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base62encode(num, alphabet=BASE62):
    """Encode a positive number into Base X and return the string.

    Arguments:
    - `num`: The number to encode
    - `alphabet`: The alphabet to use for encoding
    """
    if num == 0:
        return alphabet[0]
    arr = []
    arr_append = arr.append  # Extract bound-method for faster access.
    _divmod = divmod  # Access to locals is faster.
    base = len(alphabet)
    while num:
        num, rem = _divmod(num, base)
        arr_append(alphabet[rem])
    arr.reverse()
    return ''.join(arr)

def base62decode(string, alphabet=BASE62):
    """Decode a Base X encoded string into the number

    Arguments:
    - `string`: The encoded string
    - `alphabet`: The alphabet to use for decoding
    """
    base = len(alphabet)
    strlen = len(string)
    num = 0

    idx = 0
    for char in string:
        power = (strlen - (idx + 1))
        num += alphabet.index(char) * (base ** power)
        idx += 1

    return num

print (base62encode(6271023))
print (base62decode('qjnx'))
'''
qjnx
6271023
'''

7. Base91

下面这几种我都有点迷惑了，因为很少碰到，所以网上资料也没多少，故只是在此做个记录。

Base91就是91进制，也只能是支持整数输入。

8. Base92

Base92比Base91多了一个字符“~”。可支持中文、字母输入。

9. Base85

Base85 将4个字节转换为5个字节，数据的增加率为25%，而Base64的数据增加率为33%。用85进制的方式对照ASCII码表进行加密。

使用Python中的Base64模块进行加解密：

import base64

s = "你好!v5le0n9"

bs = base64.b85encode(s.encode("utf-8")) # 将字符为unicode编码转换为utf-8编码
print(bs)

bbs = str(base64.b85decode(bs), "utf-8")
print(bbs) # 解码

bs = str(base64.b85encode(s.encode("utf-8")), "utf-8")
print(bs) # 去掉编码结果前的 b

bbs = str(base64.b85decode(bs), "utf-8")
print(bbs) # 解码
'''
b'<h`KfrM)3`HEd-tZaD'
你好!v5le0n9
<h`KfrM)3`HEd-tZaD
你好!v5le0n9
'''

v5le0n9's garden

Base系列算法

1. Base64

2. Base32

3. Base16

4. Base58

5. Base36

6. Base62

7. Base91

8. Base92

9. Base85