Блочный шифр ChaCha - это просто[RFC 8439]. На решение задачи, как векторизовать алгоритм ушло полдня. Обратил внимание, как выглядит алгоритм в [libGCrypt]. Уныло.
Алгоритм ChaCha20 строится на примитивах QUARTERROUND.
// The ChaCha Quarter Round: QUARTERROUND(a,b,c,d)
a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;
-- сложения, исключающее или и циклические сдвиги. Таких раундов по матрице uint32х4х4 получается 8 в кажом цикле и всего 10 циклов.
// Тело цикла ChaCha
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)
Вот так выглядит тело цикла, индексы в скобках - индексы массива состояния, всего 16 переменных. Не сложно заметить, каждая переменная участвует только в двух из восьми раундах. Присмотрелся -- первые четыре раунда могут выполняться параллельно и вторые четыре раунда могут выполнятся параллельно.
// Тело цикла ChaCha - векторизация по uint32х4 128 бит.
a += b; d ^= a; d = ROL(d,16);
c += d; b ^= c; b = ROL(b,12);
a += b; d ^= a; d = ROL(d, 8);
c += d; b ^= c; b = ROL(b, 7);
b = SHUFFLE(b, 1, 2, 3, 0);
c = SHUFFLE(c, 2, 3, 0, 1);
d = SHUFFLE(d, 3, 0, 1, 2);
a += b; d ^= a; d = ROL(d,16);
c += d; b ^= c; b = ROL(b,12);
a += b; d ^= a; d = ROL(d, 8);
c += d; b ^= c; b = ROL(b, 7);
b = SHUFFLE(b, 3, 0, 1, 2);
c = SHUFFLE(c, 2, 3, 0, 1);
d = SHUFFLE(d, 1, 2, 3, 0);
Вот так работает! Все операции - векторные, ROL - циклический сдвиг, SHUFFLE - перестановка слов.
Между строк написано, что ChaCha20 сделал по мотивам Salsa20. Структура та же - 8 раундов и 10 циклов.
// Тело цикла Salsa20 - векторизация по uint32х4 128 бит.
// замена столбцов x3<=>x1
x1 = SHUFFLE(x1, 1, 2, 3, 0);
x2 = SHUFFLE(x2, 2, 3, 0, 1);
x3 = SHUFFLE(x3, 3, 0, 1, 2);
x1 ^= ROL(x0 + x3, 7);
x2 ^= ROL(x1 + x0, 9);
x3 ^= ROL(x2 + x1,13);
x0 ^= ROL(x3 + x2,18);
// замена столбцов x3<=>x1
x3 = SHUFFLE(x3, 1, 2, 3, 0);
x2 = SHUFFLE(x2, 2, 3, 0, 1);
x1 = SHUFFLE(x1, 3, 0, 1, 2);
x3 ^= ROL(x0 + x1, 7);
x2 ^= ROL(x3 + x0, 9);
x1 ^= ROL(x2 + x3,13);
x0 ^= ROL(x1 + x2,18);
Также как и в предыдущем случае, в переменных состояния {x0,x1,x2,x3} живут столбцы матрицы uint32х4x4. Для подготовки данных к такому алгоритму матрицу состояния пришлось транспонировать.
Производительность
Получил результат по производительности. Применил хитрость при измерении скорости. Загрузил состояние в кеш, и загрузил код в кеш, методом запустить дважды. Получилась производительность по алгоритмам примерно равная на уровне 80 тактов на 512 байт, 10 циклов для каждого алгоритма. Измерял на Intel Core-i3 Gen10.
