Алгоритм шифрования Blowfish

 

 

Содержание   1 Введение 2 Описание алгоритма 2.1 Параметры 2.2 Функция F(x) 2.3 Алгоритм шифрования 64-битного блока с известным массивом P и F(x) 2.4 Алгоритм Blowfish 2.5 Выбор начального значения P-массива и таблицы замен 3 Криптостойкость 4 Пример работы алгоритма 5 Применения 6 Заключение 7 Список литературы 8 Приложение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

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

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

До появления Blowfish существовавшие алгоритмы были либо запатентованными, либо ненадёжными, а некоторые и  вовсе держались в секрете (например, Skipjack). Алгоритм был разработан в 1993 году Брюсом Шнайером в качестве быстрой и свободной альтернативы устаревшему DES и запатентованному IDEA. По заявлению автора, критерии проектирования Blowfish были:

• скорость (шифрование на 32-битных процессорах происходит за 26 тактов);
• простота (за счёт использования простых операций, уменьшающих вероятность ошибки реализации алгоритма);
• компактность;
• настраиваемая стойкость.

 

ОПИСАНИЕ АЛГОРИТМА

Параметры

• секретный ключ 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)

Функция F(x) в Blowfish

1. 32-битный блок делится на четыре 8-битных блока (X1, X2, X3, X4), каждый из которых является индексом массива таблицы замен S1-S4
2. значения S1[X1] и S2[X2] складываются по модулю 2³², после "XOR"ятся с S3[X3] и, наконец, складываются с S4[X4] по модулю 2³².
3. Результат этих операций — значение F(x).

 

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

 

Сеть Фейстеля при зашифровании

• разделение на 32-битные блоки :
•  и   «XOR»-ся c ключами  , 
• вычисления в i-том раунде:

• после 16 раунда   меняются местами:

 

Алгоритм Blowfish

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

1. Подготовительный — формирование ключей шифрования по секретному ключу.
• Инициализация массивов P и S при помощи секретного ключа K
1. Инициализация P1-P18 фиксированной строкой, состоящей из шестнадцатеричных цифр мантиссы числа пи.
2. Производится операция XOR над P1 с первыми 32 битами ключа K, над P2 со вторыми 32-битами и так далее. 
   Если ключ K короче, то он накладывается циклически.
• Шифрование ключей и таблиц замен
1. Алгоритм шифрования 64-битного блока, используя инициализированные ключи P1-P18 и таблицу замен S1-S4, шифрует 64 битную нулевую (0x0000000000000000) строку. Результат записывается в P1, P2.
2. P1 и P2 шифруются изменёнными значениями ключей и таблиц замен. Результат записывается в P3 и P4.
3. Шифрование продолжается до изменения всех ключей P1-P18 и таблиц замен S1-S4.
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) и слабым ключом. Для этого варианта требуется   выбранных открытых текстов (t — число раундов, а символы [] означают операцию получения целой части числа). Эта атака может быть использована только для алгоритма с  . Для t = 7 требуется 2²⁴ открытых текстов, причём для варианта с известным F(x) и случайным ключом требуется 2⁴⁸ открытых текстов. Но данная атака не эффективна для Blowfish с 16 раундами.

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

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

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

Модификация F(x): на вход подается 64-битный блок который делится на восемь 8-битных блоков (X1-X8). Результат  вычисляется по формуле 

 

, где 

 
На сегодняшний день (ноябрь 2008) не существует атак, выполняемых за разумное время. Успешные атаки возможны только из-за ошибок реализации.

ПРИМЕР  РАБОТЫ  АЛГОРИТМА

Пример работы свободно распространяемой версии алгоритма Blowfish. 
Параметры: Размер ключа: 448 бит Размер блока: 64 бит Число раундов: 16 режим: ECB

Исходное изображение

 

 

Зашифрованное изображение

ПРИМЕНЕНИЯ

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

• хэширование паролей
• защита электронной почты и файлов
• GnuPG (безопасное хранение и передача)
• в линиях связи: связка ElGamal (не запатентован) или RSA (действие патента закончилось в 2000 году) и Blowfish вместо IDEA
• в маршрутизаторе Intel Express 8100 с ключом длиной 144 бита
• обеспечение безопасности в протоколах сетевого и транспортного уровня
• PuTTY (сетевой уровень)
• SSH (транспортный уровень)
• OpenVPN (создание зашифрованных каналов)

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК  ЛИТЕРАТУРЫ

1. А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, «Основы криптографии», Гелиос АРВ, М., 2001.
2. Брюс Шнайер. Прикладная криптография. Изд-во «Триумф», М., 2004г.
3. Национальный стандарт РФ «Методы и средства обеспечения безопасности. Часть 1. Концепция и модели менеджмента безопасности информационных и телекоммуникационных технологий» (ГОСТ Р ИСО/МЭК 13335-1 — 2006).
4. Методы и средства защиты компьютерной информации Р.Р. Хамидуллин. Учеб. Пособие СПб.: Изд-во СЗТУ, 2006 г.
5. ГОСТ Р 34.11-94. Информационная технология. Криптографическая защита информации. Функция хеширования.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ПРИЛОЖЕНИЕ

Листинг

//USAGE:

//BlowFish b = new BlowFish("04B915BA43FEB5B6");

//string plainText = "The quick brown fox jumped over the lazy dog.";

//string cipherText = b.Encrypt_CBC(plainText);

//MessageBox.Show(cipherText);

//plainText = b.Decrypt_CBC(cipherText);

//MessageBox.Show(plainText);

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Security.Cryptography;

 

namespace BlowFishCS

{

    class BlowFish

    {

        RNGCryptoServiceProvider randomSource;

 

        //SBLOCKS

        private uint[] bf_s0;

        private uint[] bf_s1;

        private uint[] bf_s2;

        private uint[] bf_s3;

 

        private uint[] bf_P;

 

        //KEY

        private byte[] key;

 

        //HALF-BLOCKS

        private uint xl_par;

        private uint xr_par;

 

        private byte[] InitVector;

        private bool IVSet;

 

        //COMPATIBILITY WITH javascript CRYPTO LIBRARY

        private bool nonStandardMethod;

 

        /// <summary>

        /// Constructor for hex key

        /// </summary>

        /// <param name="hexKey">Cipher key as a hex string</param>

public BlowFish(string hexKey)

        {

            randomSource = new RNGCryptoServiceProvider();

            SetupKey(HexToByte(hexKey));

        }

 

        /// <summary>

        /// Constructor for byte key

        /// </summary>

        /// <param name="cipherKey">Cipher key as a byte array</param>

public BlowFish(byte[] cipherKey)

        {

            randomSource = new RNGCryptoServiceProvider();

            SetupKey(cipherKey);

        }

 

        /// <summary>

        /// Encrypts a string in CBC mode

        /// </summary>

        /// <param name="pt">Plaintext data to encrypt</param>

        /// <returns>Ciphertext with IV appended to front</returns>

public string Encrypt_CBC(string pt)

        {

            if (!IVSet)

                SetRandomIV();

            return ByteToHex(InitVector) + ByteToHex(Encrypt_CBC(

            Encoding.ASCII.GetBytes(pt)));

        }

 

        /// <summary>

        /// Decrypts a string in CBC mode

        /// </summary>

        /// <param name="ct">Ciphertext with IV appended to front</param>

        /// <returns>Plaintext</returns>

public string Decrypt_CBC(string ct)

        {

            IV = HexToByte(ct.Substring(0, 16));

            return Encoding.ASCII.GetString(Decrypt_CBC(HexToByte(

            ct.Substring(16)))).Replace("\0", "");

        }

 

        /// <summary>

        /// Decrypts a byte array in CBC mode.

        /// IV must be created and saved manually.

        /// </summary>

        /// <param name="ct">Ciphertext data to decrypt</param>

        /// <returns>Plaintext</returns>

public byte[] Decrypt_CBC(byte[] ct)

        {

            return Crypt_CBC(ct, true);

        }

 

        /// <summary>

        /// Encrypts a byte array in CBC mode.

        /// IV must be created and saved manually.

        /// </summary>

        /// <param name="pt">Plaintext data to encrypt</param>

        /// <returns>Ciphertext</returns>

public byte[] Encrypt_CBC(byte[] pt)

        {

            return Crypt_CBC(pt, false);

        }

       

        /// <summary>

        /// Encrypt a string in ECB mode

        /// </summary>

        /// <param name="pt">Plaintext to encrypt as ascii string</param>

        /// <returns>hex value of encrypted data</returns>

public string Encrypt_ECB(string pt)

        {

            return ByteToHex(Encrypt_ECB(Encoding.ASCII.GetBytes(pt)));

        }

 

        /// <summary>

        /// Decrypts a string (ECB)

        /// </summary>

        /// <param name="ct">hHex string of the ciphertext</param>

        /// <returns>Plaintext ascii string</returns>

public string Decrypt_ECB(string ct)

        {

            return Encoding.ASCII.GetString(Decrypt_ECB(