Salsa20

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Salsa20 — система потокового шифрування, розроблена Деніелом Бернштейном. Алгоритм був представлений на конкурсі «eSTREAM», метою якого було створення європейських стандартів для шифрування даних, переданих поштовими системами. Алгоритм став переможцем конкурсу в першому профілі (потокові шифри для програмного застосування з великою пропускною здатністю).

Шифр Salsa20 використовує наступні операції:

Алгоритм використовує геш-функцію з 20 циклами. Основні її перетворення нагадують алгоритм AES.

Опис алгоритму[ред. | ред. код]

Поняття[ред. | ред. код]

Словом далі будемо називати елемент множини {0,1,...,232-1} і записувати його в шістнадцятковому вигляді з префіксом 0х.

Операцію додавання двох слів по модулю 232 будемо позначати символом «».

Виключне або (побітове додавання) будемо позначати символом «»

-бітовий циклічний зсув вліво слова , який будемо позначати . Якщо представити як , тоді

Функції, які використовуються в алгоритмі[ред. | ред. код]

quarterround(y)[ред. | ред. код]

Основним блоком системи є перетворення над чотирма словами. З нього будуються далі описані більш загальні перетворення. Його суть полягає в тому, що для кожного слова ми складаємо два попередніх, зсуваємо (циклічно) суму на певну кількість біт і побітово підсумовуємо результат з вибраним словом. Подальші операції проводяться з новими значеннями слів.

Припустимо, що — послідовність слів 4 . Тоді функція де

Наприклад:

quarterround(0x00000001; 0x00000000; 0x00000000; 0x00000000) = (0x08008145; 0x00000080; 0x00010200; 0x20500000)

Можна розглядати цю функцію перетворення слів y0, y1, y2 y3. Кожне з таких перетворень оборотне, як і функція в цілому.

rowround(y)[ред. | ред. код]

В цьому перетворенні ми беремо 16 слів. Представимо їх у вигляді матриці 4х4. Беремо кожен рядок цієї матриці і перетворимо слова цієї матриці функцією . Слова з рядка беруться за порядком, починаючи з i-го для i-го рядка, де i={0,1,2,3}.

Нехай — послідовність 16 слів, тоді — також послідовність 16 слів де

columnround(y)[ред. | ред. код]

Тут ми беремо стовпці такої ж матриці. Перетворимо їх функцією за аналогією підставляючи в неї значення, починаючи з j-го для j-го стовпця, де j={0,1,2,3}.

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

doubleround(y)[ред. | ред. код]

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

Salsa20()[ред. | ред. код]

Даний алгоритм використовує запис слова, що починається з молодшого байта. Для цього тут введено перетворення

Нехай — 4-байтова послідовність, тоді — слово, таке, що

Підсумкове перетворення — це побітове додавання вихідної послідовності і результату 20 раундів почергових перетворень стовпців і рядків.

де

x[i] — байти x, а xj — слова, які використовуються в описаних вище функціях.

Якщо ,

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


Розширення ключа для Salsa20[ред. | ред. код]

Розширення перетворює 32-байтний або 16-байтний ключ k і 16-байтний номер n  в 64-байтну послідовність . Для розширення k використовуються константи


для 32-бітного k і


для 16-бітного k. Це записи «expand 32-byte k» і «expand 16-byte k» ASCII-коді.

Нехай k0,k1,n — 16-байтові послідовності, тоді .

Якщо у нас тільки одна 16-байтові послідовність k то


Функція шифрування Salsa20[ред. | ред. код]

Шифром -байтної послідовності для буде

— унікальний 8-байтовий номер (nonce).

Шифротекст буде розміром в байт, так само, як вихідний текст.

Salsa20k(v) — послідовність у 270 байт.

Де — унікальна послідовність у 8 байт така що Відповідно

Де

Продуктивність[ред. | ред. код]

Завдяки тому, що перетворення кожного стовпця і кожного рядка не залежать один від одного, обчислення, необхідні для шифрування, легко розпаралелюються. Це дає суттєвий виграш у швидкості для більшості сучасних платформ.

Алгоритм практично не має накладних обчислень, необхідних для запуску циклу шифрування. Це так само відноситься до зміни ключа. Велика кількість шифросистем розраховує на попередні обчислення, результати яких повинні зберігатися в кеші першого рівня (L1) процесора. Так як вони залежать від ключа, обчислення доведеться проводити заново. У Salsa20 ж достатньо просто завантажити ключ в пам'ять.

Варіанти Salsa20/8 і Salsa20/12[ред. | ред. код]

Salsa20/8 і Salsa20/12 - це шифросистеми, що використовують той же механізм, що і Salsa20, але з 8 і 12 раундами шифрування, відповідно, замість 20 оригінальних. Salsa20 був зроблений з великим запасом стійкості. Тоді як Salsa20/8 показує хороші результати у швидкодії, обганяючи в більшості випадків багато інших шифросистем, в тому числі AES і RC4[1]

Варіант XSalsa20[ред. | ред. код]

Існує варіант алгоритму Salsa20, також запропонований Даніелем Бернштейном, в якому довжина nonce збільшена з 64 до 192 біт. Цей варіант називається XSalsa20. Збільшений розмір nonce дозволяє використовувати для його генерації криптографічно стійкий генератор псевдовипадкових чисел, в той час як для безпечного шифрування з 64-бітним nonce необхідне використання лічильника через високу ймовірність колізій.[2].

Криптоаналіз[ред. | ред. код]

У 2005 році Paul Crowley оголосив про атаки на Salsa20/5 з розрахунковою складністю по часу 2165. Ця і наступні атаки засновані на урізаному диференціальному криптоаналізі (truncated differential криптоаналіз). За цей криптоаналіз він отримав нагороду в 1000$ від автора Salsa20.

B 2006, Fischer, Meier, Berbain, Biasse, і Robshaw повідомили про атаку на Salsa/6 зі складністю 2117, і про атаку з пов'язаними ключами на Salsa20/7 зі складністю 2217

B 2008 році Aumasson, Fischer, Khazaei, Meier і Rechberger повідомили про атаку на Salsa20/7 зі складністю 2153 і про першу атаку на Salsa20/8 зі складністю 2251.

Поки що не було публічних повідомлень про атаки на Salsa20/12 і повну Salsa20/20.

ChaCha[ред. | ред. код]

Варіант ChaCha функції quarterround(a, b, c, d)

У 2008 році Даніель Берштейн опублікував споріднене сімейство потокових шифрів під назвою ChaCha, метою якого було поліпшення перемішування даних за один раунд і, імовірно, поліпшення криптостійкості при тій же, або навіть трохи більшій швидкості[3].

ChaCha20 описаний в RFC 7539 (травень 2015).

Основний блок системи тут працює інакше. Тепер кожна операція змінює одне з слів. Зміни відбуваються циклічно «у зворотний бік», починаючи з 0-го слова. Чергуються операції додавання побітової суми разом із зсувом, кожне слово складається з попереднім.

Функція quarterround(a, b, c, d), де a, b, c, d-слова, в ChaCha виглядає наступним чином

Тут використовуються ті ж самі арифметичні операції, але кожне слово змінюється два рази за перетворення замість одного.

Примітки[ред. | ред. код]

Посилання[ред. | ред. код]