Salsa20

Интернет магазин китайских планшетных компьютеров

Компьютеры - Salsa20

01 июля 2011

Оглавление:
1. Salsa20
2. Скоростные особенности
3. Криптоанализ

система поточного шифрования разработанная Daniel J. Bernstein. Алгоритм был представлен на конкурсе eSTREAM, целью которого было создание европейских стандартов для поточных систем шифрования. Алгоритм стал победителем конкурса в первом профиле.

Salsa20 основана на операциях 32-битного суммирования, побитового сложения и операции сдвига. Алгоритм использует хеш-функцию с 20-ю циклами. Основные ее преобразования напоминают алгоритм AES.

Описание алгоритма

Понятия

Словом далее будем называть элемент множества {0,1,…,2−1} и записывать в шестнадцатеричном виде с префиксом 0х.
Операцию сложения двух слов по модулю 2 будем обозначать знаком « $~+$ ».
Исключающее или будем обозначать символом « $\oplus$ »
$~c$ -битовый левый сдвиг слова $~u$ будем обозначать $u\lll c$ . если $~u$ представить как $~u=\sum_{i=1}2^iu_i$ , тогда $u\lll c=\sum_{i=1}2^{i+c \mod 32}u_i$

Функции, используемые в алгоритме

$~quarterround$

quarterround

Основным блоком системы является преобразование $~quarterround$ над 4-мя словами. Из него строятся далее описанные более общие преобразования. Его суть заключается в том, что для каждого слова мы складываем два предыдущих, сдвигаем сумму на определенное количество бит и побитово суммируем результат с выбранным словом. Последующие операции производятся с новыми значениями слов.

Допустим, что $~y$ — последовательность 4-х слов $~y =$ тогда функция $~quarterround =$ где

$z_1 = y_1 \oplus \lll 7),$

$z_2 = y_2 \oplus \lll 9),$

$z_3 = y_3 \oplus \lll 13),$

$z_0 = y_0 \oplus \lll 18).$

Например:

quarterround
          =

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

rowround

$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. Берем каждый ряд этой матрицы и преобразуем слова этой матрицы функцией quarterround. Слова из строки берутся по порядку, начиная с i-ого для i-ой строки, где i={0,1,2,3}.

Пусть $~y=$ — последовательность 16 слов, тогда $~rowround=$ — также последовательность 16 слов где

$~ = quarterround,$

$~ = quarterround.$

columnround

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

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

$~ = quarterround,$

$~ = quarterround.$

doubleround

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

Salsa20

Данный алгоритм использует запись слова начинающуюся с младшего байта. Для этого здесь введено преобразование $~littleendian$

Пусть $~b=$ — 4-байтовая последовательность, тогда $~littleendian$ — слово, такое что

$~littleendian = b_0 + 2^8 b_1 + 2^{16}b_2 + 2^{24} b_3$

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

$~Salsa20 = x \oplus doubleround^{10}$ Где $~x=,$

$~x_0 = littleendian,$

$~x_1 = littleendian,$

…

$~x_{15} = littleendian.$

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

Если
$~ = doubleround^{10}$ ,
тогда Salsa20 является последовательностью результатов
$~littleendian^{-1}, ..., littleendian^{-1}$

Расширение ключа для Salsa20

Расширение преобразует 32-байтный или 16-байтный ключ k и 16-байтный номер n в 64-байтную последовательность Salsa20_k.
Для расширения k используются константы
$\sigma_0 =,~ \sigma_1 =,~ \sigma_2 =,~ \sigma_3 =$
для 32-битного k и

$\tau_0 =,~ \tau_1 =,~ \tau_2 =,~ \tau_3 =$
для 16-битного k. Это записи «expand 32-byte k» и «expand 16-byte k» ASCII-коде.

Пусть у k₀,k₁,n — 16-байтовые последовательности, тогда
$Salsa20_{k_0,k_1}=Salsa20$ .

Если у нас только одна 16-байтовая последовательность k то
$~Salsa20_k=Salsa20$

Функция шифрования Salsa20

Шифром $~l$ -байтной последовательности $~m$ , для $l\in\{0,1,...2^{70}\}$ будет $Salsa20_k\oplus m$
$~v$ — уникальный 8-байтовый номер.
Шифротекст будет размером в $~l$ байт, так же как и исходный текст.