Шифр Blowfish


Шифр Blowfish
Blowfish
Создатель:

Брюс Шнайер

Создан:

1993 г.

Опубликован:

1993 г.

Размер ключа:

до 448 бит

Размер блока:

64 бит

Число раундов:

16

Тип:

Сеть Фейстеля

Blowfish (произносится [бло́уфиш]) — криптографический алгоритм, реализующий симметричное шифрование.

Разработан Брюсом Шнайером в 1993 году. Представляет собой сеть Фейстеля. Выполнен на простых и быстрых операциях: XOR, подстановка, сложение. Является не запатентованным и свободно распространяемым.

Содержание

История

До появления Blowfish существовавшие алгоритмы были либо запатентованными, либо ненадёжными, а некоторые и вовсе держались в секрете (например, DES и запатентованному

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

Алгоритм шифрования 64-битного блока с известным массивом P и F(x)

Параметры

  • секретный ключ K (от 32 до 448 бит)
  • 32-битные ключи шифрования P1-P18
  • 32-битные таблицы замен S1-S4:
    S1[0] S1[1] .. S1[255]
    S2[0] S2[1] .. S2[255]
    S3[0] S3[1] .. S3[255]
    S4[0] S4[1] .. S4[255]

Функция F(x)

  1. 32-битный блок делится на четыре 8-битных блока (X1, X2, X3, X4), каждый из которых является индексом массива таблицы замен S1-S4
  2. значения S1[X1] и S2[X2] складываются по модулю 232, после «XOR»ятся с S3[X3] и, наконец, складываются с S4[X4] по модулю 232.
  3. Результат этих операций — значение F(x).
F(X1,X2,X3,X4)=(((S1[X1]\ +\ S2[X2]) \mod 2^{32}\ \oplus\ S3[X3])\ +\ S4[X4]) \mod 2^{32}

Алгоритм шифрования 64-битного блока с известным массивом P и F(x)

  • разделение на 32-битные блоки :L_{0}\ ,\ R_{0}
  • вычисления в i-том раунде:
    R_i\ =\ L_{i-1} \oplus P_i
    L_i\ =\ R_{i-1} \oplus F(R_i)
  • после 16 раунда L_{16}\ ,\ R_{16} меняются местами:
    R_{16}\ \leftleftarrows\ L_{16}\
    \ L_{16}\ \leftleftarrows\ R_{16}
  • и «XOR»-ся ключами P17,P18

Алгоритм Blowfish

Разделён на 2 этапа:

  1. Подготовительный — формирование ключей шифрования по секретному ключу.
    • Инициализация массивов P и S при помощи секретного ключа K
      1. Инициализация P1-P18 фиксированной строкой, состоящей из шестнадцатеричных цифр числа пи, следующих после 3, то есть после запятой.
      2. Производится операция XOR над P1 с первыми 32 битами ключа K, над P2 со вторыми 32-битами и так далее.
        Если ключ K короче, то он накладывается циклически.
    • Шифрование ключей и таблиц замен
      1. Алгоритм шифрования 64-битного блока, используя инициализированные ключи P1-P18 и таблицу замен S1-S4, шифрует 64 битную строку, состоящую из 0 (строго говоря, не обязательно из 0, важно чтобы она просто была фиксированной). Результат записывается в P1, P2.
      2. P1 и P2 шифруются изменёнными значениями ключей и таблиц замен. Результат записывается в P3 и P4.
      3. Шифрование продолжается до изменения всех ключей и таблицы замен.
  2. Шифрование текста полученными ключами и F(x), с предварительным разбиением на блоки по 64 бита. Если невозможно разбить начальный текст точно на блоки по 64 бита, используются различные режимы шифрования для построения сообщения, состоящего из целого числа блоков. Cуммарная требуемая память 4168 байт: P1-P18:18 переменных по 32 бита; S1-S4: 4x256 переменных по 32 бита.

Дешифрование происходит аналогично, только P1-P18 применяются в обратном порядке.

Выбор начального значения P-массива и таблицы замен

Нет ничего особенного в цифрах числа пи. Данный выбор заключается в инициализации последовательности, не связанной с алгоритмом, которая могла бы быть сохранена как часть алгоритма или получена при необходимости (Пи (число)). Как указывает Шнайер: "Подойдёт любая строка из случайных битов цифр числа e, RAND-таблицы, или случайные сгенерированные цифры."

Криптостойкость

  • слабый S-box (и порождающий его слабый ключ) означает, что существует такие i, j, N={1,2,3,4} : SN[i]==SN[j]

Криптостойкость главным образом зависит от F(x). На это указал Serge Vaudenay, говоря о наличии небольшого класса слабых ключей (генерирующих слабые S-box): вероятность появления слабого S-box равна 2 − 15. Он также рассмотрел упрощенный вариант Blowfish, с известной функцией F(x) и слабым ключом. Для этого варианта требуется 3*2^{2+7*[(t-2)/2]}\approx2^{3+7*[(t-2)/2]} выбранных открытых текстов (t - число раундов, а символы [] означают операцию получения целой части числа). Эта атака может быть использована только для алгоритма с t \le 7. Для t = 7 требуется 224 открытых текстов, причём для варианта с известным F(x) и случайным ключом требуется 248 открытых текстов. Но данная атака не эффективна для Blowfish с 16 раундами.

John Kelsey разработал атаку, которая позволяла взломать 3-итерационный Blowfish. Она опирается на факт, что операции сложения по модулю 232 и XOR не коммутативны.

Невозможно заранее определить является ли ключ слабым. Проводить проверку можно только после генерации ключа.

Криптостойкость можно настраивать за счёт изменения количества раундов шифрования (увеличивая длину массива P) и количества используемых S-box. При уменьшении используемых S-box возрастает вероятность появления слабых ключей, но уменьшается используемая память. Адаптируя Blowfish на 64-битной архитектуру, можно увеличить количество и размер S-box (а следовательно и память для массивов P и S), а также усложнить F(x), причём для алгоритма с такой функцией F(x) невозможны вышеуказанные атаки.

Модификация F(x): на вход подается 64-битный блок который делится на восемь 8-битных блоков (X1-X8). Результат вычисляется по формуле F(X1,..,X8)=(\ (\ (S1[X1]\ \boxplus\ S2[X2])\ \oplus\ (S3[X3]\ \boxplus\ S4[X4])\ )\ \boxplus\ (\ (S5[X5]\ \boxplus\ S6[X6])\ \oplus(S7[X7]\ \boxplus\ S8[X8])\ )\ ), где \boxplus\ \equiv mod 2^{32}
На сегодняшний день (ноябрь 2008) не существует атак, выполняемых за разумное время. Успешные атаки возможны только из-за ошибок реализации.

Применения

Blowfish зарекомендовал себя, как надёжный алгоритм, поэтому реализован во многих программах, где не требуется частая смена ключа и необходима высокая скорость шифрования/расшифрования.

Сравнение с симметричными криптосистемами

Скорость шифрования алгоритма во многом зависит от используемой техники и системы команд. На различных архитектурах один алгоритм может значительно опережать по скорости его конкурентов, а на другом ситуация может сравняться или даже измениться прямо в противоположную сторону. Более того, программная реализация значительно зависит от используемого компилятора. Использование ассемблерного кода может повысить скорость шифрования. На скорость шифрования влияет время выполнения операций mov, add, xor, причём время выполнения операций увеличивается при обращении к оперативной памяти (для процессоров серии DES, IDEA влияет операция умножения по модулю 232 + 1. Скорость

Хотя Blowfish по скорости опережает его аналоги, но при увеличении частоты смены ключа основное время его работы будет уходить на подготовительный этап, что в сотни раз уменьшает его эффективность.

См. также

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Шифр Blowfish" в других словарях:

  • Blowfish — Создатель: Брюс Шнайер Создан: 1993 г. Опубликован: 1993 г. Размер ключа: от 32 до 448 бит Размер блока: 64 бит Число раундов: 16 Тип …   Википедия

  • Шифр — У этого термина существуют и другие значения, см. Шифр (значения). Шифр (от араб. صِفْر ‎‎, ṣifr «ноль», откуда фр. chiffre «цифра»; родственно слову цифра)  какая либо система преобразования текста с секретом (ключом) для обеспечения… …   Википедия

  • Cobra (шифр) — Cobra Создатель: Кристиан Шнайдер, Создан …   Википедия

  • Блочный шифр — Общая схема работы блочного шифра Блочный шифр  разновидность симметричного шифра …   Википедия

  • Поточный шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к …   Википедия

  • Trivium (шифр) — Структура шифра Trivium Trivium  симметричный алгоритм синхронного потокового шифрования, ориентированный, в первую очередь, на аппаратную реализацию с гибким равновесием ме …   Википедия

  • A3 (шифр) — A3  алгоритм, используемый в процессе аутентификации в глобальном цифровом стандарте для мобильной сотовой связи GSM. A3 является, таким образом, элементом системы обеспечения конфиденциальности разговора в GSM наряду с алгоритмами A5 и A8.… …   Википедия

  • A8 (шифр) — A8  алгоритм формирования ключа шифрования, который впоследствии используется для обеспечения конфиденциальности передаваемой по радиоканалу информации в стандарте мобильной сотовой связи GSM. A8 является одним из алгоритмов обеспечения… …   Википедия

  • HPC (шифр) — У этого термина существуют и другие значения, см. HPC. Содержание 1 Общая структура 2 Структура раунда HPC Medium[1][2] …   Википедия

  • SC2000 (шифр) — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей …   Википедия