本文将介绍Salsa20密码算法的结构和原理,以及如何实现。 NeoAtlantis应用科学和神秘学实验室负责人是node-salsa20这个可用于NodeJS(但也可用于网页)的加密库的作者。

1 Salsa20介绍

Salsa20,又名Snuffle 2005,是一个2005年由Daniel J. Bernstein提出的流加密算法,已被一个欧洲的甄选流加密算法的计划eSTREAM选中。 其特点是结构简单、易于实现,很安全(支持128比特或256比特的密钥),速度很快,也适合在嵌入式系统上实现。

此外,Salsa20不受专利的约束。

2 结构

2.1 概括

简单来说,Salsa20的原理是产生一种伪随机的字节流。 这种字节流在很长(约2的70次方)范围内和真正的随机字节流(例如由硬件随机数发生器产生的真随机数)无法区分。 这样做到了和一次一密密码本(OTP,One Time Pad)加密等价的效果。

这种伪随机的字节流将会和真正的明文数据进行按字节异或。这样就是加密。 由于异或的特性,若A xor B=C,则有A xor C=BB xor C=A。 所以,解密时只要产生同样的伪随机字节流(通过提供同样的密钥和初始向量),对密文进行按字节异或,就能解密。

2.2 核心函数

核心函数,是Salsa20的关键部分。其原理是一个由如下C代码定义的变换,由64字节(512比特)的输入产生同样长度的输出。

#define R(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
void salsa20_word_specification(uint32 out[16],uint32 in[16])
{
    int i;
    uint32 x[16];
    for (i = 0;i < 16;++i) x[i] = in[i];
    for (i = 20;i > 0;i -= 2) {     // 迭代次数,注意每次 i -= 2 !
        x[ 4] ^= R(x[ 0]+x[12], 7);  x[ 8] ^= R(x[ 4]+x[ 0], 9);
        x[12] ^= R(x[ 8]+x[ 4],13);  x[ 0] ^= R(x[12]+x[ 8],18);
        x[ 9] ^= R(x[ 5]+x[ 1], 7);  x[13] ^= R(x[ 9]+x[ 5], 9);
        x[ 1] ^= R(x[13]+x[ 9],13);  x[ 5] ^= R(x[ 1]+x[13],18);
        x[14] ^= R(x[10]+x[ 6], 7);  x[ 2] ^= R(x[14]+x[10], 9);
        x[ 6] ^= R(x[ 2]+x[14],13);  x[10] ^= R(x[ 6]+x[ 2],18);
        x[ 3] ^= R(x[15]+x[11], 7);  x[ 7] ^= R(x[ 3]+x[15], 9);
        x[11] ^= R(x[ 7]+x[ 3],13);  x[15] ^= R(x[11]+x[ 7],18);
        x[ 1] ^= R(x[ 0]+x[ 3], 7);  x[ 2] ^= R(x[ 1]+x[ 0], 9);
        x[ 3] ^= R(x[ 2]+x[ 1],13);  x[ 0] ^= R(x[ 3]+x[ 2],18);
        x[ 6] ^= R(x[ 5]+x[ 4], 7);  x[ 7] ^= R(x[ 6]+x[ 5], 9);
        x[ 4] ^= R(x[ 7]+x[ 6],13);  x[ 5] ^= R(x[ 4]+x[ 7],18);
        x[11] ^= R(x[10]+x[ 9], 7);  x[ 8] ^= R(x[11]+x[10], 9);
        x[ 9] ^= R(x[ 8]+x[11],13);  x[10] ^= R(x[ 9]+x[ 8],18);
        x[12] ^= R(x[15]+x[14], 7);  x[13] ^= R(x[12]+x[15], 9);
        x[14] ^= R(x[13]+x[12],13);  x[15] ^= R(x[14]+x[13],18);
    }
    for (i = 0;i < 16;++i) out[i] = x[i] + in[i];
}

注意核心函数中标出来的迭代次数。 这个for循环的实际运行次数,就是实际应用中写成Salsa20/x中的x。

例如,如上代码迭代 10 次,因此是Salsa20/10

2.3 字节序

核心函数的输入和输出各是一个16元素的32位无符号整型数组。 根据Salsa20的定义,将字节变换为32位无符号整型时使用的是 小尾序(Little Endian) 的。

例如,我们要表示一个无符号32位整数0xDEADBEEF,则其在一个长度是4个字节的数组A中,应当有:

A[0] = 0xEF
A[1] = 0xBE
A[2] = 0xAD
A[3] = 0xDE

反之亦然。

在下文中,我们称这样一个小尾序的无符号32位整数为一个

2.4 使用核心函数产生伪随机数流

伪随机数流的产生其实就是将64字节(512比特)的输入送入核心函数,然后得到512比特的输出的过程。 每次输入的字节包含密钥、初始向量和计数器。 这样,要产生长度是N字节的伪随机数流,只需要调用核心函数若干次,直到获取了足够长度(不少于N)的输出即可。

Salsa20支持两种长度的密钥:128比特(16字节)或者256比特(32字节)。

为了构建送入核心函数的输入,规则如下:

常量1 || 密钥前半 || 常量2 || 初始向量 || 计数器 || 常量3 || 密钥后半 || 常量4
.0-3......4-19......20-23.....24-31......32-39....40-43.....44-59.....60-63.

其中:

  • 常量1常量2常量3常量4各是1个词;
  • 密钥前半密钥后半分别是4个词;
  • 初始向量计数器分别是2个词。

故一共是16个词,每个词4字节,共64字节=512比特。

在每多进行一次核心函数的计算时,计数器需要增加1位。 即每次在第32位上加1,如果进位则在33、34……39位上增加。

初始向量是对于一个流唯一的一个量。由2个词(8字节)构成。初始向量可以明文传送。

根据密钥长度不同,对密钥和常量的选取有差异,下面分开解释。

2.4.1 使用256比特密钥进行加密/解密

在使用256比特的密钥时,常量1-4是如下一组的4个词:

[0x61707865, 0x3320646e, 0x79622d32, 0x6b206574]

密钥前半由密钥的前128比特,即0-15字节构成。密钥后半,则是16-31字节。

这4个常量词的选取是由expand 32-byte k这段话得来。

2.4.2 使用128比特密钥进行加密/解密

在使用128比特的密钥时,常量1-4是如下一组的4个词:

[0x61707865, 0x3120646e, 0x79622d36, 0x6b206574]

密钥前半和密钥后半,都用整个密钥填充。

这4个常量词的选取是由expand 16-byte k这段话得来。

3 使用Salsa20时的注意事项

首先,关于选择哪种迭代次数的算法。本文作者推荐的是Salsa20/20,即20轮迭代。 14轮的迭代也是可以接受的。更低的迭代次数就有待商榷(例如10次)。

第二,初始向量一定要在每次运行Salsa20算法,进行一次加密的时候更换。

第三,Salsa20是流加密算法,并不抵抗密文的破坏。 如果密文出现比如一个比特的变化(0变成1或者1变成0),这个变化不会引起解密失败,而且会影响到明文。 为此,您可能有必要在明文开头附加一个MAC(Message Authentication Code,消息认证码),来检验密文的完整。

第四,绝对不要使用同样的密钥和初始向量加密不同的明文! 这样会导致您的密文很容易被破解。 因为这样产生的密文都是基于同样的伪随机字节流的,只要知道一份明文,就很容易求出字节流,进而解密其他的密文。