chacha20 算法流程

大家好，欢迎来到IT知识分享网。

chacha20算法请参看 RFC:7539。下面是我的理解，欢迎指正。

chacha20算法的基本思想：加密时，将明文数据与用户之间约定的某些数据进行异或操作，得到密文数据；由异或操作的特点可知，在解密时，只需要将密文数据与用户之间约定的那些数据再次进行异或操作，就得到了明文数据。

用相同值异或两次就能恢复出原来的值，所以加密和解密都严格采用同一个程序。

从原理上来说，chacha20的加解密过程还是非常简单的。这里面的难点在于理解 chacha20中那些用来与明文数据进行异或的数据是如何生成的，这就是 chacha20算法的核心所在。

大体的流程是这样的：首先，用户之间会约定一些初始的元数据，简单起见，称之为 KEY_INIT，则 KEY_INIT需要经过某种运算，得到另外一个 KEY_1，然后用 KEY_1与明文数据的第 1个分组进行异或，以得到密文数据的第 1个分组，接下来，KEY_INIT再经过某种运算，得到另外一个 KEY_2，然后用 KEY_2与明文数据的第 2个分组进行异或，以得到密文数据的第 2个分组，以此类推，直到处理完所有的明文分组。从这里可以看到，与每个明文分组进行异或的数据（KEY_n）是不相同的，且与分组所对应的顺序有关。

下面讲解一下如何由 KEY_INIT得到 KEY_1, KEY_2, ..., KEY_n。

首先需要明确的是，在 chacha20算法中，KEY_INIT和 KEY_n的长度是相同的，都是 64个字节。因此，明文分组的长度也是 64字节，即 16个 4字节整数。
其中，KEY_INIT由 4部分组成：
KEY_INIT[0]~ KEY_INIT[15]是 16字节的常量（constant）;
KEY_INIT[16]~ KEY_INIT[47]是 32字节的 key;
KEY_INIT[48]~ KEY_INIT[51]是 4字节的 block counter;
KEY_INIT[52]~ KEY_INIT[63]是 12字节的 nonce。

按顺序将上述 16个 4字节整数排列成 4x4的矩阵，记为矩阵 M，它的内容示意如下：

cccccccc cccccccc cccccccc cccccccc kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn 

其中，
c表示 constant的 4个 bit;
k表示 key的 4个 bit;
b表示 block counter的 4个 bit;
n表示 nonce的 4个 bit

上面之所以把 64字节的 KEY_INIT排列成矩阵的形式，是因为后续的计算都是在这个矩阵上展开的，写成矩阵形式后，能很清楚看到每次参与计算的元素的相对位置。基于上述的 4x4矩阵，chacha20里面的运算包含两种形式：列运算和对角线运算。这里暂时先不介绍列运算和对角线运算的具体含义，先讲讲由 KEY_INIT生成KEY_1的计算过程中涉及的 "轮"的概念。

简单来讲，"轮"是一系列运算步骤的组合，chacha20中的 20就是指由 KEY_INIT生成 KEY_1时需要进行 20轮运算。同时，在 chacha20中， 1个"轮"还可以进一步划分为 4个 "四分之一轮"，也就是说，在chacha20中由 KEY_INIT生成KEY_1的计算过程中包含 80个 四分之一轮的运算。

注意，由 KEY_INIT生成KEY_1，KEY_2，...，KEY_n的原理是一样，因此每次都需要进行 80个 四分之一轮的运算。

终于讲到四分之一轮的概念了，先给出四分之一轮的定义，如下所示：

a += b; d ^= a; d <<<= 16; c += d; b ^= c; b <<<= 12; a += b; d ^= a; d <<<= 8; c += d; b ^= c; b <<<= 7; 

从上述定义可以看到，四分之一轮的定义很简单，只有 4个变量参与运算，共计 12个基本操作，涉及 3种普通运算：加法、异或、循环移位。值得注意的是，这 4个变量都是 4字节整数，加法运算是模 2^32的。

现在可以猜到，在每个四分之一轮中，a, b, c, d这 4个 4字节整数均来自于矩阵 M，现在来讲讲列运算和对角线运算的含义。先用 4字节整数出现的顺序来重新表示矩阵 M，记为矩阵 T：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

有了上述索引表示，则所谓的列运算就是：在四分之一轮中，a, b, c, d这 4个 4字节整数在矩阵 M中的索引为矩阵 T的某个列向量。
具体来说就是，
对于第 1个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 0, 4, 8, 12，
对于第 2个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 1, 5, 9, 13，
对于第 3个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 2, 6, 10, 14,
对于第 4个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 3, 7, 11, 15。
由上述 指定顺序 的 4个 四分之一轮运算构成了一个 轮的运算，且是执行 列运算的 轮，在这一 轮运算中，会将矩阵 M中 16个4字节整数全部用到；

同理，所谓的对角线运算就是：在四分之一轮中，a, b, c, d这 4个 4字节整数在矩阵 M中的索引为矩阵 T的某条（或某两条）对角线上的元素。
具体来说就是，
对于第 1个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 0, 5, 10, 15，
对于第 2个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 1, 6, 11, 12，
对于第 3个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 2, 7, 8, 13,
对于第 4个四分之一轮而言，a, b, c, d在矩阵 M中的索引为 3, 4, 9, 14。
由上述 指定顺序 的 4个 四分之一轮运算构成了一个 轮的运算，且是执行 对角线运算的 轮，在这一 轮运算中，会将矩阵 M中 16个 4字节整数全部用到。

注意，在由 KEY_INIT生成 KEY_n时，每次都是先将矩阵 M的内容拷贝至一个新的矩阵 S中，然后在矩阵 S上进行80个 四分之一轮的运算，在计算的过程中原地更新矩阵 S中的内容，造成的影响在计算 该 KEY_n的过程中持续累积。

有了上述背景知识，现在就可以对 chacha20中的 20轮运算有一个整体性的认识：先将矩阵 M的内容拷贝至一个新的矩阵 S中，然后执行 4个 四分之一轮的列运算，再执行 4个四分之一轮的对角线运算，再将这两轮运算重复10遍，这样一共就是 20轮运算，在执行完这 20轮运算后，还需要将原矩阵 M与刚刚得到的矩阵 S中的对应位置元素相加，以便得到最终的矩阵，记为矩阵 W，最后以小端序将矩阵 W的 16个 4字节整数整理为一个 64字节的数据块（也即上述中的 KEY_n），并与 64字节的明文分组相异或，得到对应的密文分组。

综上所述，在 chacha20中，明文数据会被划分为若干个 64字节的分组，然后通过 chacha20算法计算出对应的 KEY_n（也即是上述中的矩阵 W），并让明文分组与 KEY_n相异或，得到对应的密文分组。其中最重要的一点是，在每处理完一个分组后，矩阵 M中的 block counter部分需要自增 1，其他三个部分（ constant, key，nonce）保持不变，这样就确保了对于不同的明文分组，对应的 KEY_n是不同的。若最后一个明文分组不足 64字节，则只异或 KEY_n中对应的字节。因此，即使明文分组不足 64字节，也不影响计算，但对应的 KEY_n的所有字节（矩阵 W的所有元素）需要被全部计算出来。

忘了说了，KEY_INIT中的前 16字节 constant是个字符串，它的内容是："expand 32-byte k"，数一下应该是 16字节。

下面给出 chacha20算法的 C语言实现，摘自 OpenSSL项目的 crypto/chacha/chacha_enc.c文件，可以在 github或 gitee上再看看这段代码：
https://github.com/openssl/openssl/blob/master/crypto/chacha/chacha_enc.c
https://gitee.com/mirrors/openssl/blob/master/crypto/chacha/chacha_enc.c

typedef unsigned int u32; typedef unsigned char u8; typedef union { 
    u32 u[16]; u8 c[64]; } chacha_buf; # define ROTATE(v, n) (((v) << (n)) | ((v) >> (32 - (n)))) # define U32TO8_LITTLE(p, v) do { 
      \ (p)[0] = (u8)(v >> 0); \ (p)[1] = (u8)(v >> 8); \ (p)[2] = (u8)(v >> 16); \ (p)[3] = (u8)(v >> 24); \ } while(0) /* QUARTERROUND updates a, b, c, d with a ChaCha "quarter" round. */ # define QUARTERROUND(a,b,c,d) ( \ x[a] += x[b], x[d] = ROTATE((x[d] ^ x[a]),16), \ x[c] += x[d], x[b] = ROTATE((x[b] ^ x[c]),12), \ x[a] += x[b], x[d] = ROTATE((x[d] ^ x[a]), 8), \ x[c] += x[d], x[b] = ROTATE((x[b] ^ x[c]), 7) ) /* chacha_core performs 20 rounds of ChaCha on the input words in * |input| and writes the 64 output bytes to |output|. */ static void chacha20_core(chacha_buf *output, const u32 input[16]) { 
    u32 x[16]; int i; DECLARE_IS_ENDIAN; memcpy(x, input, sizeof(x)); for (i = 20; i > 0; i -= 2) { 
    QUARTERROUND(0, 4, 8, 12); QUARTERROUND(1, 5, 9, 13); QUARTERROUND(2, 6, 10, 14); QUARTERROUND(3, 7, 11, 15); QUARTERROUND(0, 5, 10, 15); QUARTERROUND(1, 6, 11, 12); QUARTERROUND(2, 7, 8, 13); QUARTERROUND(3, 4, 9, 14); } if (IS_LITTLE_ENDIAN) { 
    for (i = 0; i < 16; ++i) output->u[i] = x[i] + input[i]; } else { 
    for (i = 0; i < 16; ++i) U32TO8_LITTLE(output->c + 4 * i, (x[i] + input[i])); } } void ChaCha20_ctr32(unsigned char *out, const unsigned char *inp, size_t len, const unsigned int key[8], const unsigned int counter[4]) { 
    u32 input[16]; chacha_buf buf; size_t todo, i; /* sigma constant "expand 32-byte k" in little-endian encoding */ input[0] = ((u32)ossl_toascii('e')) | ((u32)ossl_toascii('x') << 8) | ((u32)ossl_toascii('p') << 16) | ((u32)ossl_toascii('a') << 24); input[1] = ((u32)ossl_toascii('n')) | ((u32)ossl_toascii('d') << 8) | ((u32)ossl_toascii(' ') << 16) | ((u32)ossl_toascii('3') << 24); input[2] = ((u32)ossl_toascii('2')) | ((u32)ossl_toascii('-') << 8) | ((u32)ossl_toascii('b') << 16) | ((u32)ossl_toascii('y') << 24); input[3] = ((u32)ossl_toascii('t')) | ((u32)ossl_toascii('e') << 8) | ((u32)ossl_toascii(' ') << 16) | ((u32)ossl_toascii('k') << 24); input[4] = key[0]; input[5] = key[1]; input[6] = key[2]; input[7] = key[3]; input[8] = key[4]; input[9] = key[5]; input[10] = key[6]; input[11] = key[7]; input[12] = counter[0]; input[13] = counter[1]; input[14] = counter[2]; input[15] = counter[3]; while (len > 0) { 
    todo = sizeof(buf); if (len < todo) todo = len; chacha20_core(&buf, input); for (i = 0; i < todo; i++) out[i] = inp[i] ^ buf.c[i]; out += todo; inp += todo; len -= todo; /* * Advance 32-bit counter. Note that as subroutine is so to * say nonce-agnostic, this limited counter width doesn't * prevent caller from implementing wider counter. It would * simply take two calls split on counter overflow... */ input[12]++; } } 

参考资料：

chacha20算法的RFC: https://www.rfc-editor.org/rfc/rfc7539