Salsa20

Словом далее будем называть элемент множества {0,1,…,2³²−1} и записывать в шестнадцатеричном виде с префиксом 0х.

Операцию сложения двух слов по модулю 2³² будем обозначать знаком «${\displaystyle +}$».

Исключающее или (побитовое суммирование) будем обозначать символом «${\displaystyle \oplus }$»

${\displaystyle c}$-битовый циклический левый сдвиг слова ${\displaystyle u}$ будем обозначать ${\displaystyle u\lll c}$. Если ${\displaystyle u}$ представить как ${\displaystyle u=\sum _{i=0}2^{i}u_{i}}$, тогда

${\displaystyle u\lll c=\sum _{i=0}2^{i+c\mod 32}u_{i}}$

Основным блоком системы является преобразование ${\displaystyle quarterround(y)}$ над четырьмя словами. Из него строятся далее описанные более общие преобразования.

Его суть заключается в том, что для каждого слова мы складываем два предыдущих, сдвигаем (циклично) сумму на определённое количество бит и побитово суммируем результат с выбранным словом. Последующие операции производятся с новыми значениями слов.

Допустим, что ${\displaystyle y}$ — последовательность 4 слов ${\displaystyle y=(y_{0},y_{1},y_{2},y_{3})}$ тогда функция ${\displaystyle quarterround(y)=(z_{0},z_{1},z_{2},z_{3})}$ где

${\displaystyle z_{1}=y_{1}\oplus ((y_{0}+y_{3})\lll 7),}$

${\displaystyle z_{2}=y_{2}\oplus ((z_{1}+y_{0})\lll 9),}$

${\displaystyle z_{3}=y_{3}\oplus ((z_{2}+z_{1})\lll 13),}$

${\displaystyle z_{0}=y_{0}\oplus ((z_{3}+z_{2})\lll 18).}$

Например:

quarterround(0x00000001; 0x00000000; 0x00000000; 0x00000000)

          = (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Можно рассматривать эту функцию как преобразования слов y₀, y₁, y₂ и y₃. Каждое из таких преобразований обратимо, как и функция в целом.

${\displaystyle y={\begin{pmatrix}y_{0}&y_{1}&y_{2}&y_{3}\\y_{4}&y_{5}&y_{6}&y_{7}\\y_{8}&y_{9}&y_{10}&y_{11}\\y_{12}&y_{13}&y_{14}&y_{15}\end{pmatrix}}}$

В этом преобразовании мы берем 16 слов. Представим их в виде матрицы 4х4. Берем каждый ряд этой матрицы и преобразуем слова этой матрицы функцией ${\displaystyle quarterround(y)}$. Слова из строки берутся по порядку, начиная с i-го для i-й строки, где i={0,1,2,3}.

Пусть ${\displaystyle y=(y_{0},y_{1},y_{2},...,y_{15})}$ — последовательность 16 слов, тогда ${\displaystyle rowround(y)=(z_{0},z_{1},z_{2},...,z_{15})}$ — также последовательность 16 слов где

${\displaystyle (z_{0},z_{1},z_{2},z_{3})=quarterround(y_{0},y_{1},y_{2},y_{3}),}$

${\displaystyle (z_{5},z_{6},z_{7},z_{4})=quarterround(y_{5},y_{6},y_{7},y_{4}),}$

${\displaystyle (z_{10},z_{11},z_{8},z_{9})=quarterround(y_{10},y_{11},y_{8},y_{9}),}$

${\displaystyle (z_{15},z_{12},z_{13},z_{14})=quarterround(y_{15},y_{12},y_{13},y_{14}).}$

Здесь мы берём столбцы такой же матрицы. Преобразуем их функцией ${\displaystyle quarterround(y)}$, по аналогии подставляя в неё значения, начиная с j-го для j-го столбца, где j={0,1,2,3}.

Функция columnround(y)=(z) тоже оперирует последовательностью 16 слов так, что

${\displaystyle (z_{0},z_{4},z_{8},z_{12})=quarterround(y_{0},y_{4},y_{8},y_{12}),}$

${\displaystyle (z_{5},z_{9},z_{13},z_{1})=quarterround(y_{5},y_{9},y_{13},y_{1}),}$

${\displaystyle (z_{10},z_{14},z_{2},z_{6})=quarterround(y_{10},y_{14},y_{2},y_{6}),}$

${\displaystyle (z_{15},z_{3},z_{7},z_{11})=quarterround(y_{15},y_{3},y_{7},y_{11}).}$

Функция doubleround(y) является последовательным применением функций columnround а затем rowround: doubleround(y) = rowround(columnround(y))

Данный алгоритм использует запись слова, начинающуюся с младшего байта. Для этого здесь введено преобразование ${\displaystyle littleendian(b)}$

Пусть ${\displaystyle b=(b_{0},b_{1},b_{2},b_{3})}$ — 4-байтовая последовательность, тогда ${\displaystyle littleendian(b)}$ — слово, такое, что

${\displaystyle littleendian(b)=b_{0}+2^{8}b_{1}+2^{16}b_{2}+2^{24}b_{3}}$

Итоговое преобразование — это побитовое суммирование исходной последовательности и результата 20 раундов чередующихся преобразований столбцов и строк.

${\displaystyle Salsa20(x)=x\oplus doubleround^{10}(x)}$

Где ${\displaystyle x=(x[0],x[1],...,x[63]),}$

${\displaystyle x_{0}=littleendian(x[0],x[1],x[2],x[3]),}$

${\displaystyle x_{1}=littleendian(x[4],x[5],x[6],x[7]),}$

…

${\displaystyle x_{15}=littleendian(x[60],x[61],x[62],x[63]).}$

x[i] — байты x, а x_j — слова, используемые в описанных выше функциях.

Если

${\displaystyle (z_{0},z_{1},...,z_{15})=doubleround^{10}(x_{0},x_{1},...,x_{15})}$,

тогда Salsa20(x) является последовательностью результатов

${\displaystyle littleendian^{-1}(z_{0}+x_{0}),...,littleendian^{-1}(z_{15}+x_{15})}$

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность ${\displaystyle Salsa20_{k}(n)}$.

Для расширения k используются константы
${\displaystyle \sigma _{0}=(101,120,112,97),~\sigma _{1}=(110,100,32,51),~\sigma _{2}=(50,45,98,121),~\sigma _{3}=(116,101,32,107)}$

для 32-байтного k и

${\displaystyle \tau _{0}=(101;120;112;97),~\tau _{1}=(110;100;32;49),~\tau _{2}=(54;45;98;121),~\tau _{3}=(116;101;32;107)}$

для 16-байтного k.

Это записи «expand 32-byte k» и «expand 16-byte k» в ASCII-коде.

Пусть у k₀,k₁,n — 16-байтовые последовательности, тогда
${\displaystyle Salsa20_{k_{0},k_{1}}(n)=Salsa20(\sigma _{0},k_{0},\sigma _{1},n,\sigma _{2},k_{1},\sigma _{3})}$.

Если у нас только одна 16-байтовая последовательность k то
${\displaystyle Salsa20_{k}(n)=Salsa20(\tau _{0},k,\tau _{1},n,\tau _{2},k,\tau _{3})}$

Шифром ${\displaystyle l}$-байтной последовательности ${\displaystyle m}$, для ${\displaystyle l\in \{0,1,...2^{70}\}}$ будет ${\displaystyle Salsa20_{k}(v)\oplus m}$

${\displaystyle v}$ — уникальный 8-байтовый номер (nonce).

Шифротекст будет размером в ${\displaystyle l}$ байт, так же, как и исходный текст.

Salsa20_k(v) — последовательность в 2⁷⁰ байт.

${\displaystyle Salsa20_{k}(v,{\underline {0}}),Salsa20_{k}(v,{\underline {1}}),Salsa20_{k}(v,{\underline {2}}),...,Salsa20_{k}(v,{\underline {2^{64}-1}})}$

Где ${\displaystyle {\underline {i}}}$ — уникальная последовательность в 8 байт ${\displaystyle (i_{0},i_{1},...,i_{7})}$ такая что ${\displaystyle i=i_{0}+2^{8}i_{1}+...+2^{56}i_{7}}$ Соответственно

${\displaystyle Salsa20_{k}(v)\oplus (m[0],m[1],..,m[l-1])=(c[0],c[1],...,c[l-1])}$

Где ${\displaystyle c[i]=m[i]\oplus Salsa20_{k}(v,{\mathcal {b}}{\underline {i/64}}{\mathcal {c}})[i\mod 64]}$