安卓逆向-ChaCha20算法

chacha20算法

1. 概述

• ChaCha20是一种高效、安全且快速的流加密算法，由 Daniel J. Bernstein 在 2008 年基于 Salsa20算法改进而成，主要用于加密数据流；
• ChaCha20 将密钥（256 位）、随机数（Nonce，96 位）和计数器（Counter，32 位）经过一系列混合运算生成密钥流（Key Stream），再与明文进行按位异或得到密文
• ChaCha20 的解密过程与加密完全相同，因为异或操作是可逆的，类似的算法还有RC4；
• 输入长度随意且没有填充，密文和明文长度一样；

2. 与RC4的区别

• Chacha20和RC4都是流密码算法，但它们的加密原理有以下几个区别：

  • 密钥长度：Chacha20的密钥长度为256位（32字节） ，而RC4的密钥长度为1到256字节不等；
  • S盒：Chacha20没有S盒，而RC4使用一个256字节的S盒来生成密钥流；Chacha20是基于置换的加密算法，它使用固定的置换来生成密钥流；
  • 加密过程：在Chacha20中，通过对输入的明文数据块进行置换和加密操作，生成密文输出；每次加密需要根据密钥和计数器生成一个新的置换和密钥流；而RC4是在密钥生成完毕后，直接用密钥流对输入的明文进行异或操作得到密文输出；
• 区别主要就是在于密钥流的生成方式；

3. 算法核心

3.1 初始化

• 构建一个固定的 4x4 矩阵（64字节）；

• 这个矩阵由四部分填充：

  • 固定的128位魔数（16字节），ASCII编码（小端序）：0x61707865, 0x3320646e, 0x79622d32, 0x6b206574；这个是特征点；
  • 256位密钥 key（32字节）；
  • 96位 Nonce（12字节）；
  • 32位计数器 counter（4字节）；
• 其中魔数常量是："expand 32-byte k"；它的初始排列可以看作下面的矩阵；

[ 常量 ][ 常量 ][ 常量 ][ 常量 ]
[ key0 ][ key1 ][ key2 ][ key3 ]
[ key4 ][ key5 ][ key6 ][ key7 ]
[counter][nonce0][nonce1][nonce2]

• 每一次加密生成 64 字节的密钥流块；

3.2 密钥流生成

• chacha20算法的重点其实就在于秘钥的扩展，通过ChaCha20的伪随机函数对初始状态进行20轮(或者说10轮)的混淆操作，生成512位(64字节)的密钥流；
• 秘钥扩展的算法如下：

# 进行 20 轮运算（10 次双轮，每次包括列轮和对角线轮）
for _ in range(10):
    # 列轮
    quarter_round(working_state, 0, 4, 8, 12)
    quarter_round(working_state, 1, 5, 9, 13)
    quarter_round(working_state, 2, 6, 10, 14)
    quarter_round(working_state, 3, 7, 11, 15)
    # 对角线轮
    quarter_round(working_state, 0, 5, 10, 15)
    quarter_round(working_state, 1, 6, 11, 12)
    quarter_round(working_state, 2, 7, 8, 13)
    quarter_round(working_state, 3, 4, 9, 14)

# 最终将原始状态与运算结果相加
for i in range(16):
    working_state[i] = (working_state[i] + state[i]) & 0xffffffff

• 对 16×32bit 状态做 20 轮运算，也可以说是10轮，20轮 = 10次 column+diagonal；
• 最终还需要将初始状态相加，也就是 out = in + 轮后状态；

3.3 加密

• 将16个32位字按小端序序列化为 64字节的密钥流块（key_stream_block），将当前64字节明文（plaintext_block）与密钥流块进行逐字节异或（XOR）；

def chacha20_encrypt(key, nonce, counter, plaintext):
    ciphertext = bytearray()
    # 每个块 64 字节，若明文长度不足 64 字节，则只使用部分 keystream
    block_count = (len(plaintext) + 63) // 64
    for i in range(block_count):
        keystream = chacha20_block(key, counter + i, nonce)
        block = plaintext[i * 64:(i + 1) * 64]
        # 异或运算
        for j in range(len(block)):
            ciphertext.append(block[j] ^ keystream[j])
    return bytes(ciphertext)

• 如果明文块大于64字节，则循环上面的秘钥扩展，然后继续加密；

  • 初始密钥扩展（仅一次）；
  • 对后续每个64字节块只需要修改计数器值，将状态矩阵中的 state[12]（块计数器）递增（例如从1→2→3...）；
  • 复用其余所有状态：矩阵中的常量、密钥、Nonce部分保持不变；
• 基于更新后的计数器值，重新执行 20轮ChaCha轮函数，生成新的密钥流块；

4. 源码实现

import struct


def rotl(v, n):
    """对32位无符号整数 v 进行循环左移 n 位。"""
    return ((v << n) & 0xffffffff) | (v >> (32 - n))


def quarter_round(x, a, b, c, d):
    """
    ChaCha20 的四分轮函数，对状态数组 x 的 a, b, c, d 四个位置进行操作。
    """
    x[a] = (x[a] + x[b]) & 0xffffffff
    x[d] = rotl(x[d] ^ x[a], 16)
    x[c] = (x[c] + x[d]) & 0xffffffff
    x[b] = rotl(x[b] ^ x[c], 12)
    x[a] = (x[a] + x[b]) & 0xffffffff
    x[d] = rotl(x[d] ^ x[a], 8)
    x[c] = (x[c] + x[d]) & 0xffffffff
    x[b] = rotl(x[b] ^ x[c], 7)


def chacha20_block(key, counter, nonce):
    # ChaCha20 常量 "expand 32-byte k"
    constants = [0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]
    key_words = list(struct.unpack("<8I", key))
    nonce_words = list(struct.unpack("<3I", nonce))

    # 构造初始状态，共16个32位整数
    state = [0] * 16
    state[0:4] = constants
    state[4:12] = key_words
    state[12] = counter & 0xffffffff
    state[13:16] = nonce_words

    working_state = state.copy()

    # 进行 20 轮运算（10 次双轮，每次包括列轮和对角线轮）
    for _ in range(10):
        # 列轮
        quarter_round(working_state, 0, 4, 8, 12)
        quarter_round(working_state, 1, 5, 9, 13)
        quarter_round(working_state, 2, 6, 10, 14)
        quarter_round(working_state, 3, 7, 11, 15)
        # 对角线轮
        quarter_round(working_state, 0, 5, 10, 15)
        quarter_round(working_state, 1, 6, 11, 12)
        quarter_round(working_state, 2, 7, 8, 13)
        quarter_round(working_state, 3, 4, 9, 14)

    # 最终将原始状态与运算结果相加
    for i in range(16):
        working_state[i] = (working_state[i] + state[i]) & 0xffffffff

    # 将 16 个 32 位整数以小端序打包成 64 字节
    return struct.pack("<16L", *working_state)


def chacha20_encrypt(key, nonce, counter, plaintext):
    ciphertext = bytearray()
    # 每个块 64 字节，若明文长度不足 64 字节，则只使用部分 keystream
    block_count = (len(plaintext) + 63) // 64
    for i in range(block_count):
        keystream = chacha20_block(key, counter + i, nonce)
        block = plaintext[i * 64:(i + 1) * 64]
        # 异或运算
        for j in range(len(block)):
            ciphertext.append(block[j] ^ keystream[j])
    return bytes(ciphertext)


# 示例：加密和解密测试
if __name__ == '__main__':
    # 示例密钥（32字节）和 nonce（12字节）
    key = bytes.fromhex('000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f')
    nonce = bytes.fromhex('202122232425262728292a2b')
    counter = 0  # 一直都是
    plaintext = bytes.fromhex('30313233343536373839')
    print("明文:", plaintext.hex())

    # 加密
    ciphertext = chacha20_encrypt(key, nonce, counter, plaintext)
    print("密文 (hex):", ciphertext.hex())

    # 解密：对密文再次使用同样的 keystream 异或即可还原明文
    decrypted = chacha20_encrypt(key, nonce, counter, ciphertext)  #
    print("解密后明文:", decrypted.hex())