基于ARX结构的流密码算法Salsa20

0x0 ARX密码

ARX密码，是仅采用模加（Addition）、旋转移位（Rotation）和异或（Xor）三种运算构造的对称密码算法，具有良好的混淆扩散性质。其中模加运算提供了非线性复杂度，循环移位可以将高位活跃比特移动到低位，异或运算则提供了线性复杂度。使用ARX结构的分组密码算法有Speck、HIGHT、CHAM、LEA等，使用ARX结构的流密码算法有Salsa20、ChaCha、HC128、HC256等，使用ARX结构的密码杂凑算法有MD5、SHA2、SM3、Skein、BLAKE等。

0x1 Salsa20算法简介

Salsa20算法由DanielJ.Bernstein于2005年设计，是eSTREAM工程最终入选的4个面向软件实现的序列密码算法之一，该算法密钥长度为256比特或128比特，通过20轮的迭代运算，产生512比特密钥流输出。

Salsa20算法密钥长度为256比特或128比特，初始向量长度为64比特，计数器长度为64比特，该算法的核心是一个512比特输入、512比特输出的杂凑函数H，该杂凑函数将256比特密钥、64比特初始向量、64比特计数器及128比特固定常数共计512比特数据通过20轮的迭代运算，每拍产生512比特密钥流输出。算法分为初始化过程和密钥流产生过程，下面进行简要介绍。

0x2 初始化阶段

Salsa20的输入为：

其中，(k0，...，k7)为256比特的密钥，(v0，v1)为初始IV，(i0，i1)为分组标号，(σ0，σ1，σ2，σ3)为固定的常数。如果密钥长度是128比特，则(k4，k5，k6，k7)=(k0，k1，k2，k3)。其中(σ0，σ1，σ2，σ3)=(0x61707865，0x3320646e，0x79622d32，0x6b206574)或者(σ0，σ1，σ2，σ3)=(0x61707865，0x3120646e，0x79622d36，0x6b206574)。

0x3 密钥流产生过程

Salsa20为基于ARX(模加、循环移位、异或)混合运算设计的类分组结构流密码算法。

Salsa20的轮函数是一个16-word输入16-word输出的Hash函数。

Salsa20的最基本的部分是quarterround函数，该函数的输入为四个word，输出也为四个word。为了方便，在本文中我们将这个函数简记为QR。其定义如下：

Salsa20共有20轮变换。分别为10个列变换和10个行变换。我们将列变换简记为Col，将行变换简记为Row。列变换和行变换如下图所示。

一个Col和一个Row组成一个Doubleround函数，我们将Doubleround函数简记为Dou。容易看出，Salsa20包括10个Dou变换。我们定义第10个Dou变换后的输出为Dou(X)。Salsa20的Hash输出值为：

Salsa20(X0)=X0+Dou(X)。

Salsa20(X)是Salsa20算法的密钥流。我们把它记为S=Salsa20(X)=(s0，s1，...，s15)。设P是一个明文，C是相应的密文。加密函数为C=P⊕S，解密函数为P=C⊕S。Salsa20的加密过程参下图。

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)