Алгоритм шифрования данных DES

Содержание

Алгоритм шифрования данных DES

Меню

DES (Data Encryption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется, как для шифрования, так и для расшифрования данных. DES разработан фирмой IBM и утвержден правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

  • режим электронной кодовой книги (ECB — Electronic Code Book),
  • режим сцепления блоков (СВС — Cipher Block Chaining),
  • режим обратной связи по шифротексту (CFB — Cipher Feed Back),
  • режим обратной связи по выходу (OFB — Output Feed Back).

    Блочный шифр

    Преобразования Сетью Фейстеля

    Схема шифрования алгоритма DES

    Исходный текст — блок 64 бит.
    Шифрованный текст — блок 64 бит.

    Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
    Рассмотрим подробную схему алгоритма DES:
    LiRi=1,2\ldots.левая и правая половины 64-битового блока LiRi
    ki — 48 битовые ключи
    f — функция шифрования
    IP — начальная перестановка
    IP -1 — конечная перестановка. По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

    — 16 циклов преобразования Фейстеля:

    Разбить IP(T) на две части L,R, где L,R — соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= LR

    Пусть Ti -1 = Li -1Ri -1 результат (i-1) итерации, тогда результат i-ой интерации Ti = LiRi определяется:

    Li = Ri — 1 Левая половина Li равна правой половине предыдущего вектора Li — 1Ri — 1. А правая половина Ri — это битовое сложение Li — 1 и f(Ri — 1, k i) по модулю 2.

    В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

    Аргументы функции f являются 32 битовой вектор Ri — 1, 48 битовой ключ ki, которые являются результатом преобразования 56 битового исходного ключа шифра k.

    Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

    Функция Е расширяется 32 битовой вектор Ri — 1 до 48 битовой вектор E(Ri — 1) путем дублирования некоторых битов из Ri — 1 при этом порядок битов вектора E(Ri — 1) указан в таблице 2. Первые три бита вектора E(Ri — 1) являются битами 32, 1, 2 вектора Ri -1. По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri — 1) — это биты 31, 32, 1 вектора Ri — 1. Полученный после перестановки блок E(Ri -1) складывается по модулю 2 с ключами ki и затем представляются в виде восьми последовательных блоков B1,B2. B8.
    E(Ri — 1) = B1B2. B8
    Каждый Bj является 6-битовым блоком. Далее каждый из блоков Bj трансформируется в 4 битовой блок B’j с помощью преобразований Sj. Преобразования Sj определяется таблицей 3. Предположим что B3 = 101111 и мы хотим найти B’3. Первый и последний разряды B3 являются двоичной записью числа а, 0
    f(Ri — 1,ki) = P(B’1B’2. B’8)
    Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это бита 16, 7, 20, 21 вектора B’1B’2. B’8

    Генерирование ключей ki.
    Ключи ki получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

    Эта перестановка определяется двумя блоками C и D по 28 бит каждый. Первые 3 бита C есть биты 57, 49, 41 расширенного ключа. А первые три бита D есть биты 63, 55, 47 расширенного ключа. Ci,Di i=1,2,3…получаются из Ci — 1,Di — 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

    Ключ ki, i=1,…16 состоит из 48 бит, выбранных из битов вектора CiDi (56 бит) согласно таблице 7. Первый и второй биты ki есть биты 14, 17 вектора CiDi

    Конечная перестановка IP — 1 действует на T16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
    Режимы использования DES DES может используется в четырех режимах.

  • Режим электронной кодовой книги (ЕСВ — Electronic Code Book): обычное использование DES как блочного шифра (см. Рис.7).
  • Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок Ci i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста Mi + 1. Вектор C — начальный вектор, он меняется ежедневно и хранится в секрете.
  • Режим обратной связи по шифротексту (CFB — Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z,Z1. Zi = DESk(Ci — 1) . Начальный вектор C сохраняется в секрете.
  • Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z,Z1. , i>=1

  • Режим ECB прост в реализации, но возможно проведение критоанализа
  • В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста Ci приводит к искажению после расшифрования только соответствующего открытого блока Mi , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.
  • В режимах CBC и CFB искажение при передаче одного блока шифрованного текста Сi приводит к искажению на приёмнике не более двух блоков открытого текста Mi,Mi + 1. Изменение Mi приводит к изменению всех остальных блоковMi + 1,Mi + 2… Это свойство используется для выработки кода аутентификации сообщения.

    Стандарт шифрования данных

    Data Encryption Standard (DES) — это шифр на основе блоков симметричных ключей, разработанный национальным институтом стандартов и технологий ( NIST ).

    Алгоритм DES является реализацией шифра Фейстеля. Он использует 16-уровневую структуру Фейстеля. Размер блока — 64 бита. Хотя длина ключа составляет 64 бита, значимая длина ключа — 56 бит, так как 8 из 64 битов ключа не используются алгоритмом шифрования ( используются только для проверки битов ). Общая структура стандарта приведена на рисунке ниже:

    Поскольку DES основан на шифре Фейстеля, все, что требуется для его определения, это:

    • Функция уровня;
    • Список ключей;
    • Дополнительная обработка — начальная и завершающая перестановки.

    Начальная и завершающая перестановки

    Начальная и конечная перестановки представляют собой прямые блоки перестановки ( P-боксы ), которые являются обратными друг другу. Они не имеют криптографического значения в алгоритме шифрования DES . Начальные и конечные перестановки проиллюстрированы на рисунке ниже:

    Функция уровня

    Суть этого шифра заключается в функции DES , f . Функция использует 48-битный ключ к крайним правым 32 битам, чтобы сформировать 32-битовый результат:

    Блок перестановки с расширением, потому что вводимые данные имеют 32 бита, а ключ уровня является 48-битным. В первую очередь нам необходимо расширить вводимые данные до 48 бит. Логика перестановка графически представлена на рисунке ниже:

    Данная логика перестановки обычно описывается в виде таблицы из описания алгоритма DES , приведенного на рисунке ниже:

    XOR ( отбеливатель ) — после перестановки с расширением DES выполняет операцию XOR с расширенной правой секцией и ключом уровня. Ключ уровня используется только в этой операции.

    Блоки замены ( S-боксы ) — S-боксы осуществляют фактическое смешивание. Стандарт использует 8 S-боксов , каждый из которых с 6-битным входом данных и 4-битным выходом.

    Смотрите рисунок ниже:

    Правило S-боксов иллюстрирует приведенный ниже рисунок:

    В общей сложности есть восемь таблиц S-боксов . Выходные данные всех восьми S-боксов затем объединяются в 32-битную секцию.

    Прямая перестановка — 32-битные выходные данные S-боксов затем подвергают прямой перестановке с помощью правила, показанного на рисунке ниже:

    Генерация ключей

    Генератор ключей уровня создает шестнадцать 48-битных ключей из 56-битного ключа шифра. Процесс генерации ключей показан на рисунке ниже:

    Логика для введения равнозначных данных, сдвига и P-бокса сжатия, приводится в описании алгоритма DES схемы .

    Анализ DES

    Коммутатор DES удовлетворяет обоим требуемым свойствам блочного шифра. Эти два свойства делают шифр надежным.

    • Лавинообразный эффект — небольшое изменение открытого текста приводит к огромным изменениям в шифрованном тексте;
    • Полнота — каждый бит шифрованного текста зависит от многих битов открытого текста.

    В течение последних нескольких лет в результате криптоанализа были выявлены некоторые недостатки стандарта в случае, когда выбирались ненадежные ключи. Этого следует избегать.

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

    Данная публикация представляет собой перевод статьи « Data Encryption Standard » , подготовленной дружной командой проекта Интернет-технологии.ру

    Американский стандарт шифрования данных DES

    Стандарт шифрования данных DES (Data Encryption Standard) опубликован в 1977 г. Национальным бюро стандартов США. Стандарт DES предназначен для защиты от несанкционированного доступа к важной, но несекретной информации в государственных и коммерческих организациях США. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 г. был одобрен Национальным институтом стандартов и технологий США (НИСТ). С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования и расшифрования информации в сетях передачи данных.

    К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. Более того, реализация алгоритма DES в таких системах становится признаком хорошего тона.

    Основные достоинства алгоритма DES:

    · используется только один ключ длиной 56 бит;

    · зашифровав сообщение с помощью одного пакета программ, для расшифровки можно использовать любой другой пакет программ, соответствующий стандарту DES;

    · относительная простота алгоритма обеспечивает высокую скорость обработки;

    · достаточно высокая стойкость алгоритма.

    Алгоритм DES использует комбинацию подстановок и перестановок. DES осуществляет шифрование 64-битовых блоков данных с помощью 64-битового ключа, в котором значащими являются 56 бит (остальные 8 бит – проверочные биты для контроля на четность). Дешифрование в DES является операцией, обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности. Обобщенная схема процесса шифрования в алгоритме DES показана на 3.2. Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, в конечной перестановке битов.

    Рисунок 3.2 – Обобщенная схема шифрования в алгоритме DES

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

    Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. При описании алгоритма DES (рис. 3.3) применены следующие обозначения:

    L и R – последовательности битов (левая (left) и правая (right));

    Рисунок 3.3 – Структура алгоритма DES

    LR – конкатенация последовательностей L и R, т.е. такая последовательность битов, длина которой равна сумме длин L и R; в последовательности LR биты последовательности R следуют за битами последовательности L;

     – операция побитового сложения по модулю 2.

    Пусть из файла исходного текста считан очередной 64-битовый (8-байтовый) блок Т. Этот блок Т преобразуется с помощью матрицы начальной перестановки IP (табл. 3.1).

    Не нашли то, что искали? Воспользуйтесь поиском:

    Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10034 — | 7498 — или читать все.

    188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

    Отключите adBlock!
    и обновите страницу (F5)

    очень нужно

    Алгоритм DES (стр. 1 из 2)

    Основные достоинства алгоритма DES:

    · используется только один ключ длиной 56 битов;

    · зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;

    · относительная простота алгоритма обеспечивает высокую скорость обработки информации;

    · достаточно высокая стойкость алгоритма.

    DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам).

    Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).

    Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.

    Рис.2. Структура алгоритма шифрования DES

    Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 — битом 2 и т.д., что даст в результате: T(0) = IP(T).

    Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) — левые или старшие биты, R(0) — правые или младшие биты.

    Таблица 1: Матрица начальной перестановки IP

    58 50 42 34 26 18 10 02

    60 52 44 36 28 20 12 04

    62 54 46 38 30 22 14 06

    64 56 48 40 32 24 16 08

    57 49 41 33 25 17 09 01

    59 51 43 35 27 19 11 03

    61 53 45 37 29 21 13 05

    63 55 47 39 31 23 15 07

    Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:

    R(i) = L(i-1) xor f(R(i-1), K(i)) ,

    где xor — операция ИСКЛЮЧАЮЩЕЕ ИЛИ.

    Функция f называется функцией шифрования. Ее аргументы — это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

    На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл.2).

    Таблица 2: Матрица обратной перестановки IP -1

    40 08 48 16 56 24 64 32

    39 07 47 15 55 23 63 31

    38 06 46 14 54 22 62 30

    37 05 45 13 53 21 61 29

    36 04 44 12 52 20 60 28

    35 03 43 11 51 19 59 27

    34 02 42 10 50 18 58 26

    33 01 41 09 49 17 57 25

    Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

    Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP-1, а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

    Итеративный процесс расшифрования может быть описан следующими формулами:

    R(i-1) = L(i), i = 1, 2, . 16;

    L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, . 16 .

    На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки — исходная 64-битовая последовательность.

    Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.

    Рис.3. Вычисление функции f(R(i-1), K(i))

    Для вычисления значения функции f используются следующие функции-матрицы:

    Е — расширение 32-битовой последовательности до 48-битовой,

    S1, S2, . , S8 — преобразование 6-битового блока в 4-битовый,

    Р — перестановка бит в 32-битовой последовательности.

    Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) — это биты 32, 1 и 2, а последние — 31, 32 и 1.

    Таблица 3:Функция расширения E

    32 01 02 03 04 05

    04 05 06 07 08 09

    08 09 10 11 12 13

    12 13 14 15 16 17

    16 17 18 19 20 21

    20 21 22 23 24 25

    24 25 26 27 28 29

    28 29 30 31 32 01

    Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:

    E(R(i-1)) xor K(i) = B(1)B(2). B(8) .

    Функции S1, S2, . , S8 определяются табл.4.

    К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 — номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.

    Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.

    Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), . B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3)). S8(B(8)).

    Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 — битом 2 и т.д.

    Таблица 5:Функция перестановки P

    Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1. 16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.

    Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).

    Матрица G первоначальной подготовки ключа

    57 49 41 33 25 17 09

    01 58 50 42 34 26 18

    10 02 59 51 43 35 27

    19 11 03 60 52 44 36

    63 55 47 39 31 23 15

    07 62 54 46 38 30 22

    14 06 61 53 45 37 29

    21 13 05 28 20 12 04

    Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, . 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, . 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1. 16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.

    Таблица сдвигов для вычисления ключа

    Номер итерации Сдвиг (бит)
    01 1
    02 1
    03 2
    04 2
    05 2
    06 2
    07 2
    08 2
    09 1
    10 2
    11 2
    12 2
    13 2
    14 2
    15 2
    16 1

    Полученное значение вновь «перемешивается» в соответствии с матрицей H (табл.8).

    Таблица 8:Матрица H завершающей обработки ключа

    14 17 11 24 01 05

    03 28 15 06 21 10

    23 19 12 04 26 08

    16 07 27 20 13 02

    41 52 31 37 47 55

    30 40 51 45 33 48

    44 49 39 56 34 53

    46 42 50 36 29 32

    Ключ K(i) будет состоять из битов 14, 17, . 29, 32 последовательности C(i)D(i). Таким образом:

    Блок-схема алгоритма вычисления ключа приведена на рис.4.

    Рис.4. Блок-схема алгоритма вычисления ключа K(i)

    Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ

    K(15), затем — K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть!

    Режимы работы алгоритма DES

    Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:

    · электронный шифроблокнот (Electronic Codebook ) — ECB;

    · цепочкацифровыхблоков (Cipher Block Chaining) — CBC;

    · цифровая обратная связь (Cipher Feedback) — CFB;

    · внешняя обратная связь (Output Feedback) — OFB.

    В этом режиме исходный файл M разбивается на 64-битовые блоки (по 8 байтов): M = M(1)M(2). M(n). Каждый из этих блоков кодируется независимо с использованием одного и того же ключа шифрования (рис.5). Основное достоинство этого алгоритма — простота реализации. Недостаток — относительно слабая устойчивость против квалифицированных криптоаналитиков.

    Методы симметричного шифрования. Алгоритм шифрования DES.

    Симметричные алгоритмы шифрования преобразуют входные данные с использованием секретного ключа. В результате работы алгоритмов получаются зашифрованные тексты или криптограммы. Для расшифрования криптограмм, зашифрованных с помощью симметричного алгоритма, необходимо знать ключ использовавшийся в процессе зашифрования. На рисунке (NN) приведена классификация симметричных алгоритмов шифрования.

    Все множество алгоритмов делится на две большие группы: блочные и поточные. Разница между ними состоит в том, что алгоритмы первой группы принимают исходный текст блоками по несколько символов, а алгоритмы второй группы последовательно посимвольно или даже побитовое преобразуют поток исходного текста. Использование блочного шифра означает, что исходный текст делится на блоки определенной длины и все преобразования выполняются отдельно над каждый блоком. Иногда преобразования над одним блоком могут зависеть от результатов преобразования над предыдущими блоками.

    При поточном шифровании каждый символ исходного текста может представляться в битовой форме, то есть в двоичном виде. Далее каждый бит полученной последовательности можно преобразовать по определенному правилу. В качестве такого правила преобразования часто используют побитовое сложение исходного текста с некоторой секретной последовательностью битов. Секретная последовательность битов играет роль ключа зашифрования в симметричных потоковых шифрах. Сама по себе операция побитового сложения, называемая также операцией сложения по модулю двойки, операцией “исключающего ИЛИ” или просто XOR, является очень простой. При сложении каждый бит заменятся по правилу:

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

    Основу большинства потоковых шифров составляет некоторый генератор псевдослучайных последовательностей. Задача такого генератора состоит в побитовом производстве битовой последовательности, которую также иногда называют ключевой гаммой шифра. Такая гамма используется в операции побитового сложения с исходным текстом. Собственно, ключом шифрования в таком случае является начальное состояние (и, возможно, структура генератора). Очевидно, что тот, кто знает алгоритм генерации последовательностей и начальные входные данные для работы алгоритма, сможет произвести всю гамму. Основной характеристикой таких потоковых шифров является криптографическая стойкость генератора псевдослучайных последовательностей. Генератор должен обеспечивать следующие важные свойства:

    Илон Маск рекомендует:  Другие языки

    производить последовательности битов, по своим статистическим характеристикам близкие к случайным последовательностям;

    обеспечивать производство достаточно длинных неповторяющихся

    обладать достаточной скоростью для работы в реальном времени.

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

    Операция замены, которую еще иногда называют операцией подстановки, состоит в замене одних символов исходного текста на другие символы. Символы исходного текста и символы, на которые они заменяются, могут принадлежать одному и тому же алфавиту (например, русскому языку), а могут – разным.

    Операция перестановки состоит в перестановки символов исходного текста по определенному правилу.

    Рассеивание – нивелирование влияния статистических свойств открытого текста на криптограмму. Рассеивание распространяет влияние одного символа открытого текста на большое число символов криптограммы. Рассеивание обычно достигается использованием методов перестановки.

    Перемешивание – усложнение восстановления взаимосвязи статистических свойств открытого текста и криптограммы, а также между ключом и криптограммой.

    Перемешивание соответствует использованию методов замены.

    Data Encryption Standard

    DES — алгоритм для симметричного шифрования, разработанный фирмой IBM и утверждённый правительством США в 1977 году как официальный стандарт (FIPS 46-3). Размер блока для DES равен 64 бита. В основе алгоритма лежит сеть Фейстеля с 16-ю циклами (раундами) и ключом, имеющим длину 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

    В 1977 году Национальное бюро Стандартов США (NBS) опубликовало стандарт шифрования данных Data Encryption Standard (DES), предназначенный для использования в государственных и правительственных учреждениях США для защиты от несанкционированного доступа важной, но несекретной информации. Алгоритм, положенный в основу стандарта, распространялся достаточно быстро, и уже в 1980 году был одобрен ANSI. С этого момента DES превращается в стандарт не только по названию (Data Encryption Standard), но и фактически. Появляются программное обеспечение и специализированные микроЭВМ, предназначенные для шифрования/расшифрования информации в сетях передачи данных и на магнитных носителях. К настоящему времени DES является наиболее распространенным алгоритмом, используемым в системах защиты коммерческой информации. За примерами далеко ходить не надо. Программа DISKREET из пакета Norton Utilities, предназначенная для создания зашифрованных разделов на диске, использует именно алгоритм DES. «Собственный алгоритм шифрования» отличается от DES только числом итераций при шифровании. Почему же DES добился такой популярности?

    Основные достоинства алгоритма DES: • используется только один ключ длиной 56 битов;

    зашифровав сообщение с помощью одного пакета, для расшифровки вы можете использовать любой другой;

    относительная простота алгоритма обеспечивает высокую скорость обработки информации;

    достаточно высокая стойкость алгоритма.

    DES осуществляет шифрование 64-битовых блоков данных с помощью 56-битового ключа. Расшифрование в DES является операцией обратной шифрованию и выполняется путем повторения операций шифрования в обратной последовательности (несмотря на кажущуюся очевидность, так делается далеко не всегда. Позже мы рассмотрим шифры, в которых шифрование и расшифрование осуществляются по разным алгоритмам).

    Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).

    Рис.1. Обобщенная схема шифрования в алгоритме DES

    Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а, следовательно, должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.

    Рис.2. Структура алгоритма шифрования DES Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 — битом 2 и т.д., что даст в результате: T(0) = IP(T).

    Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) — левые или старшие биты, R(0) — правые или младшие биты.

    Таблица 1: Матрица начальной перестановки IP

    58 50 42 34 26 18 10 02

    60 52 44 36 28 20 12 04

    62 54 46 38 30 22 14 06

    64 56 48 40 32 24 16 08

    57 49 41 33 25 17 09 01

    59 51 43 35 27 19 11 03

    61 53 45 37 29 21 13 05

    63 55 47 39 31 23 15 07

    Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:

    R(i) = L(i-1) xor f(R(i-1), K(i)) ,

    где xor — операция ИСКЛЮЧАЮЩЕЕ ИЛИ.

    Функция f называется функцией шифрования. Ее аргументы — это 32-битовая последовательность R(i-1), полученная на (i-1)-ой итерации, и 48-битовый ключ K(i), который является результатом преобразования 64-битового ключа K. Подробно функция шифрования и алгоритм получения ключей К(i) описаны ниже.

    На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP -1 (табл.2).

    Таблица 2: Матрица обратной перестановки IP -1

    40 08 48 16 56 24 64 32

    39 07 47 15 55 23 63 31

    38 06 46 14 54 22 62 30

    37 05 45 13 53 21 61 29

    36 04 44 12 52 20 60 28

    35 03 43 11 51 19 59 27

    34 02 42 10 50 18 58 26

    33 01 41 09 49 17 57 25

    Матрицы IP -1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP -1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP -1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

    Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с матрицей IP -1 , а затем над последовательностью бит R(16)L(16) выполняются те же действия, что и в процессе шифрования, но в обратном порядке.

    Итеративный процесс расшифрования может быть описан следующими формулами:

    R(i-1) = L(i), i = 1, 2, . 16;

    L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, . 16 .

    На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).

    Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки — исходная 64-битовая последовательность.

    Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.

    Рис.3. Вычисление функции f(R(i-1), K(i))

    Для вычисления значения функции f используются следующие функции-матрицы:

    Е — расширение 32-битовой последовательности до 48-битовой,

    S1, S2, . , S8 — преобразование 6-битового блока в 4-битовый,

    Р — перестановка бит в 32-битовой последовательности.

    Функция расширения Е определяется табл.3. В соответствии с этой таблицей первые 3 бита Е(R(i-1)) — это биты 32, 1 и 2, а последние — 31, 32 и 1.

    Таблица 3: Функция расширения E

    32 01 02 03 04 05

    04 05 06 07 08 09

    08 09 10 11 12 13

    12 13 14 15 16 17

    16 17 18 19 20 21

    20 21 22 23 24 25

    24 25 26 27 28 29

    28 29 30 31 32 01

    Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:

    E(R(i-1)) xor K(i) = B(1)B(2). B(8) .

    Функции S1, S2, . , S8 определяются табл.4.

    Таблица 4 Функции преобразования S1, S2, . S8

    Номер столбца 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    S1
    14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
    S2
    15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
    S3
    10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
    Н о м е р с т р о к и
    S4
    7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
    S5
    2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
    S6
    12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
    S7
    4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
    S8
    13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

    К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 — номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.

    Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.

    Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), . B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3)). S8(B(8)).

    Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 — битом 2 и т.д.

    Таблица 5: Функция перестановки P

    Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получения 48-битовых ключей К(i), i=1. 16. На каждой итерации используется новое значение ключа K(i), которое вычисляется из начального ключа K. K представляет собой 64-битовый блок с восемью битами контроля по четности, расположенными в позициях 8,16,24,32,40,48,56,64.

    Для удаления контрольных битов и перестановки остальных используется функция G первоначальной подготовки ключа (табл.6).

    Матрица G первоначальной подготовки ключа

    57 49 41 33 25 17 09

    01 58 50 42 34 26 18

    10 02 59 51 43 35 27

    19 11 03 60 52 44 36

    63 55 47 39 31 23 15

    07 62 54 46 38 30 22

    14 06 61 53 45 37 29

    21 13 05 28 20 12 04

    Результат преобразования G(K) разбивается на два 28-битовых блока C(0) и D(0), причем C(0) будет состоять из битов 57, 49, . 44, 36 ключа K, а D(0) будет состоять из битов 63, 55, . 12, 4 ключа K. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1. 16. Для этого применяют циклический сдвиг влево на один или два бита в зависимости от номера итерации, как показано в табл.7.

    Таблица сдвигов для вычисления ключа

    Номер итерации Сдвиг (бит)

    Полученное значение вновь «перемешивается» в соответствии с матрицей H (табл.8).

    Таблица 8: Матрица H завершающей обработки ключа

    14 17 11 24 01 05

    03 28 15 06 21 10

    23 19 12 04 26 08

    16 07 27 20 13 02

    41 52 31 37 47 55

    30 40 51 45 33 48

    44 49 39 56 34 53

    46 42 50 36 29 32

    Ключ K(i) будет состоять из битов 14, 17, . 29, 32 последовательности C(i)D(i). Таким образом:

    Блок-схема алгоритма вычисления ключа приведена на рис.4.

    Рис.4. Блок-схема алгоритма вычисления ключа K(i)

    Восстановление исходного текста осуществляется по этому алгоритму, но вначале вы используете ключ

    K(15), затем — K(14) и так далее. Теперь вам должно быть понятно, почему автор настойчиво рекомендует использовать приведенные матрицы. Если вы начнете самовольничать, вы, должно быть, получите очень секретный шифр, но вы сами не сможете его потом раскрыть!

    Режимы работы алгоритма DES

    Для наиболее полного удовлетворения всем требованиям, предъявляемым к коммерческим системам шифрования, реализованы несколько режимов работы алгоритма DES. Наиболее широкое распространение получили режимы:

    электронный шифроблокнот (Electronic Codebook ) — ECB;

    цепочка цифровых блоков (Cipher Block Chaining) — CBC;

    цифровая обратная связь (Cipher Feedback) — CFB; • внешняя обратная связь (Output Feedback) — OFB.

    Кстати, если вы написали программу защиты данных и хотите дать полноценную рекламу, то автор рекомендует прямо указывать, какие из режимов поддерживает ваше детище. Это, вообще говоря, признак хорошего тона на рынке программного обеспечения средств защиты. Нет смысла раскрывать весь алгоритм, вы просто указываете: DES-CBC или DES-CFB и, как говорится, «умный догадается, а дураку и не надо».

    Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

    Алгоритм шифрования данных DES

    Достоинства и недостатки режимов:

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

    Криптостойкость алгоритма DES

    Нелинейность преобразований в DES средствами только S-блоков, и использование слабых S-блоков позволяет осуществлять контроль за шифрованной перепиской. Выбор S-блоков требует соблюдения нескольких условий:

    • Каждая строка каждого блока должна быть перестановкой множества
    • S-блоки не должны являться линейной или афинной функцией своих аргументов.
    • Изменение одного бита на входе S-блока должно приводить к изменению по крайней мере двух битов на выходе.
    • Для каждого S-блока и любого аргумента х значение S(x) и должны различаться по крайней мере двумя битами.

    Из-за небольшого числа возможных ключей (всего ), появляется возможность их полного перебора на быстродействующей вычислительной технике за реальное время. В 1998 году Electronic Frontier Foundation используя специальный компьютер DES-Cracker, удалось взломать DES за 3 дня.

    Слабые ключи

    Слабыми ключами называется ключи k такие, что , где x — 64-битный блок.

    Известны 4 слабых ключа, они приведены в таблице 9. Для каждого слабого ключа существует неподвижные точки, то есть, таких 64-битных блоков х, для которых .

    Таблица 9. DES-Слабые ключи

    Слабые ключи(hexadecimal)
    0101-0101-0101-0101
    FEFE-FEFE-FEFE-FEFE
    1F1F-1F1F-0E0E-0E0E
    E0E0-E0E0-F1F1-F1F1

    обозначает вектор, состоящий из 28 нулевых битов.

    Частично слабые ключи

    В алгоритме DES существуют слабые и частично слабые ключи. Частично-слабые ключи — это такие пары ключей , что

    Существуют 6 частично-слабых пар ключей, они приведены в таблице 10. Для каждого из 12 частично-слабых ключей существуют «анти-неподвижные точки», то есть такие блоки х, что

    Таблица 10. Частично-слабые ключи

    Пары частично-слабых ключей
    01FE-01FE-01FE-01FE,—-FE01-FE01-FE01-FE01
    1FE0-1FE0-1FE0-1FE0,—-E0F1-E0F1-E0F1-E0F1
    01E0-01E0-01F1-01F1,—-E001-E001-F101-F101
    1FFE-1FFE-0EFE-0EFE,—-FE1F-FE1F-FE0E-FE0E
    O11F-011F-010E-010E,—-1F01-1F01-0E01-0E01
    E0FE-E0FE-F1FE-F1FE,—-FEE0-FEE0-FEF1-FEF1

    Известные атаки на DES

    Таблица 11. Известные атаки на DES.
    Методы атаки Известные откр. тексты Выбранные отк. тексты Объём памяти Количество операций
    Полный поиск 1 Незначительный
    Линейный Криптоанализ Для текста
    Линейный Криптоанализ Для текста
    Диффер. Криптоанализ Для текста
    Диффер. Криптоанализ Для текста
    • Метод полного перебора требует одну известную пару шифрованного и расшифрованного текста, незначительный объём памяти, и его выполнение требует около шагов.
    • Дифференциальный криптоанализ — первую такую атаку на DES заявили Бихам и Шамир. Эта атака требует шифрования открытых текстов выбранных нападающим, и для её выполнения нужны примерно шагов. Теоретически являясь точкой разрыва, эта атака непрактична из-за чрезмерных требований к подбору данных и сложности организации атаки по выбранному открытому тексту. Сами авторы этой атаки Biham и Shamir заявили, что считают DES защищенным для такой атаки.
    • Линейный криптоанализ разработан Matsui. Этот метод позволяет восстановить ключ DES с помощью анализа известных открытых текстов, при этом требуется примерно шагов для выполнения. Первый экспериментальный криптоанализ DES, основанный на открытии Matsui, был успешно выполнен в течение 50 дней на автоматизированных рабочих местах 12 HP 9735.

    Для линейного и дифференциального криптоанализа требуется достаточно большой объём памяти для сохранения выбранных (известных) открытых текстов до начала атаки.

    Увеличение криптостойкости DES

    Чтобы увеличивать криптостойкость DES появляются несколько вариантов: double DES (2DES), triple DES (3DES), DESX, G-DES.

    • Методы 2DES и 3DES основаны на DES, но увеличивают длину ключей (2DES — 112 бит, 3DES — 168 бит) и поэтому увеличивается криптостойкость.
    • Схема 3DES имеет вид , где ключи для каждого шифра DES. Это вариант известен как в ЕЕЕ так как три DES операции являются шифрованием. Существует 3 типа алгоритма 3DES:
    • DES-EEE3: Шифруется три раза с 3 разными ключами.
    • DES-EDE3: 3DES операции шифровка-расшифровка-шифровка с 3 разными ключами.
    • DES-EEE2 и DES-EDE2: Как и предыдущие, за исключением того, что первая и третья операции используют одинаковый ключ.

    Самый популярный тип при использовании 3DES — это DES-EDE3, для него алгоритм выглядит так: Зашифрование: . Расшифрование: При выполнении алгоритма 3DES ключи могут выбрать так:

    • независимы.
    • независимы, а
    • .
    • Метод DESX создан Рональдом Ривестом и формально продемонстрирована Killian и Rogaway. Этод метод — усиленный вариант DES, поддерживаемый инструментарием RSA Security. DESX отличается от DES тем, что каждый бит входного открытого текста DESX логически суммируется по модулю 2 с 64 битами дополнительного ключа, а затем шифруется по алгоритму DES. Каждый бит результата также логически суммируется по модулю 2 с другими 64 битами ключа. Главной причиной использования DESX является простой в вычислительном смысле способ значительного повысить стойкость DES к атакам полного перебора ключа.
    • Метод G-DES разработан Schaumuller-Bichl для повышения производительности DES на основе увеличения размером шфрованного блока. Заявлялось, что G-DES защищен так же как и DES. Однако, Biham и Shamir показали, что G-DES с рекомендуемыми параметрами легко взламывается, а при любых изменениях параметров шифр становится ещё менее защищен чем DES.
    • Ещё другой вариант DES использует независимые суб-ключи. Различно от алгоритма DES, в котором на основе 56-битного секретного ключа пользователя алгоритм DES получает шестнадцать 48-битных суб-ключей для использования в каждом из 16 раундов, в этом варианте использует 768-битного ключа (разделенного на 16 48-битных подключей) вместо 16 зависимых 48-битных ключей, создаваемых по ключевому графику алгоритма DES. Хотя очевидно, что использование независимых суб-ключей значительно усложнит полный поиск ключа, но стойкость к атаке дифференциальным или линейным криптоанализом не намного превысит стойкость обычного DES. По оценке Biham для дифференциального криптоанализа DES с независимыми подключами требуется выбранных открытых текстов, в то время как для линейного криптоанализа требуется известных открытых текстов.

    Применение

    DES был национальным стандартом США в 1977—1980 гг., но в настоящее время DES используется (с ключом длины 56 бит) только для устаревших систем, чаще всего используют его более криптоустойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES, и сейчас он рассмотрен как стандарт. В ближайшее время DES и Triple DES будут заменены алгоритмом AES (Advanced Encryption Standard — Расширенный Стандарт Шифрования). Алгоритм DES широко применяется для защиты финансовой информации: так, модуль THALES (Racal) HSM RG7000 полностью поддерживает операции TripleDES для эмиссии и обработки кредитных карт VISA, EuroPay и проч. Канальные шифраторы THALES (Racal) DataDryptor 2000 используют TripleDES для прозрачного шифрования потоков информации. Также алгогритм DES используется во многих других устройствах и решениях THALES-eSECURITY.

    Применение стандарта криптосистем DES для шифрования информации

    Рубрика: Информационные технологии

    Статья просмотрена: 639 раз

    Библиографическое описание:

    Артюхов Ю. В. Применение стандарта криптосистем DES для шифрования информации // Молодой ученый. — 2010. — №8. Т. 1. — С. 146-150. — URL https://moluch.ru/archive/19/1928/ (дата обращения: 12.11.2020).

    Стандарт криптосистем DES (Data Encryption Standard) был разработан фирмой IBM и утвержден правительством США в конце 70-х годов как общепринятый стандарт шифрования. DES предназначен для работы с 64-битовыми блоками данных, который преобразуется к зашифрованному блоку (64-бит) за 16-шагов. Каждый из этих 16 ключей получается из 56 битного главного ключа, рис.1.

    Перед тем как над исходным блоком начнут выполняться его 16 циклов шифрования, проводится его первичное преобразование, а после шифрования производится преобразование, обратное первичному. Результатом является зашифрованный блок [1, 3].

    Рисунок 1. Общая схема алгоритма DES

    Рисунок 2. Cхема раунда шифрования алгоритма DES

    Каждый цикл шифрования использует блок 64-битных исходных данных полученных из предыдущего цикла шифрования , как показано на рис. 1,б. Каждые 64 бита разбиваются на левый 32 –битный сегмент и правый . Во время следующего цикла сегменты меняются местами. Основную роль в алгоритме DES играет искажающая функция . Данная функция принимает в качестве исходных данных 32-битный блок и 48-битный ключ , а затем генерирует 32-битный блок, предназначенный для использования в операции XOR (“или”) с блоком . В результате вышеизложенной последовательности действий на каждом шаге цикла порождается . Искажающая функция сначала добирает до 48 бит, а потом проводит над ним операцию XOR с применением ключа . В результате мы имеем восемь частей по шесть бит. На следующем шаге каждая часть проходит через один из восьми S-блоков (блоков подстановки), где преобразуется в набор из 4 битов. Иными словами S-блолки представляют собой нелинейные компоненты алгоритма DES, которые обеспечивают основную криптостойкость шифра. Каждый S-блок представляет собой поисковую таблицу из четырех строк и шестнадцати столбцов. Шесть входящих в S-блок битов определяют, какую строку и какой столбец необходимо использовать для замены. Первый и шестой бит задают номер строки, а остальные — номер столбца. Выход S-блока — значение соответствующей ячейки таблицы. Следующим этапом работы искажающей функции является обработка P-блоком групп из восьми 4-битовых элементов. Данные последовательности битов компонуются в 32-битовую строку и перемешиваются, формируя тем самым выход функции .

    Стандарт шифрования DES предусматриваем различные режимы работы с информацией [2].

    Режим ECBэлектронная кодовая книга (Electronic Code Book). Этот режим прост в обращении, но слабо защищен от возможных атак с удалениями и вставками. Ошибка, допущенная в одном из битов шифротекста, влияет на целый блок в расшифрованном тексте.

    Данные , которые необходимо зашифровать, делятся на блоки по бит:

    Последний из блоков, если необходимо, дополняется до длины . По ним определяются блоки как результат воздействия функции шифрования

    Режим CBC (Cilper Block Chaining) предназначен для минимизации потерь в результате атаки с использованием удаленных вставок. Здесь ошибочный бит шифротекста при расшифровании не только превращает в ошибочный блок, в котором содержится, но и портит один бит в следующем блоке открытого текста, что можно легко определить и интерпретировать как сигнал о предпринятой атаке. В данном режиме информация разбивается на блоки и дополняется последний как и в режиме ECB (1). Шифрование ведётся согласно формулам

    Илон Маск рекомендует:  Applet java апплеты (нет в html 2 0)

    Следует особое внимание уделить величине IV (начальное значение), которая используется в шифровании тем, чтобы шифрованные версии одинаковых частей открытой информации выглядели по разному. Скрывать значение IV нет необходимости.

    Режим OFB называемый обратной связью по выходу (Output Feedback) применяется для использования блочного шифра в качестве поточного. Для этого необходимо выбрать переменную , где , которая обозначает число битов на выходе генератора потока ключей при каждой итерации. Далее выполняем операцию, описанную формулой (1). В данном случае каждый блок данных состоит из битов. Зашифрование происходит следующим образом:

    1. переменной присваивается начальное значение IV;
    2. на каждом шаге, при , выполняются преобразования;
    3. ;
    4. крайний слева битов блока ;
    5. ;
    6. .

    Режим CFB (Cipher Feed Back) обратная связь по шифротексту. Он имеет много общего с режимом OFB. Блочный шифр в нем преобразуется в поточный. В режиме CFB поток ключей возникает в результате еще одного шифрования блоков криптограммы

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

    Как уже не раз отмечалось, в первом приближении DES — это шифр Фейстеля с 16 раундами (рис. 1), за исключением того, что как перед, так и после основных итераций алгоритма Фейстеля осуществляются некоторые перестановки. Обратите внимание (рис. 1) на то, как два блока меняются местами перед последней перестановкой алгоритма. Эта замена никак не влияет на стойкость шифра, и пользователи часто задавались вопросом: зачем вообще это делать Один из членов творческого коллектива, разработавшего DES утверждал, что она облегчает микросхемную реализацию процедуры шифрования. Шифр DES преобразует открытый текст следующим образом.

    • производит начальную перестановку (IP);
    • расщепляет блок на левую и правую половины;
    • осуществляет 16 раундов с одним и тем же набором операций;
    • соединяет половины блока;
    • производит конечную перестановку.

    Конечная перестановка обратная начальной. Это позволяет использовать одно и то же программное обеспечение и оборудование для двух сторон процесса: шифрования и расшифрования. Разворачивачивание ключа дает 16 подключен по 48 битов каждый, выделяя их из 56-битного основного ключа.

    Работа функции . Каждый цикл алгоритма DES состоит из 6 шагов, опишем их:

    • Перестановка с расширением. Правая половина из 32 битов растягивается до 48 битов и перемешивается. Это помогает рассеиванию связи между входными битами и выходными. Перестановка с расширением (отличная от начальной) выбирается так, чтобы один входной бит воздействовал на две замены через S-блоки, о которых речь пойдет ниже. Это помогает распространять зависимости и создает лавинный эффект (малое различие между двумя наборами входных данных превращается в большое на выходе);
    • Сложение с подключом. К строке из 48 битов, полученной после перестановки с расширением, и подключу (его длина тоже 48 битов) применяется операция исключающего ИЛИ, т. е. каждая пара соответствующих битов складывается по модулю 2. Заметим, что подключ используется только в этом месте алгоритма;
    • Расщепление, Результат предыдущего шага расщепляется на 6 частей по 8 битов в каждом;
    • S-блок. Каждый 6-битовый кусок передается в один из восьми S-блоков (блоков подстановки), где он превращается в набор из 4 битов. S-блоки — нелинейные компоненты алгоритма DES и именно они дают основной вклад в криптостойкость шифра. Каждый S-блок представляет собой поисковую таблицу из четырех строк и шестнадцати столбцов. Шесть входящих в S-блок битов определяют, какую строку и какой столбец необходимо использовать для замены. Первый и шестой бит задают номер строки, а остальные — номер столбца. Выход S-блока — значение соответствующей ячейки таблицы.
    • Р-блок. На этот момент у нас есть восемь групп 4-битовых элементов, которые комбинируются здесь в 32-битовую строку и перемешиваются, формируя выход функции F.

    Графически функция алгоритма DES схематически изображена на рисунке 3.

    Рисунок 3. Структура функции F алгоритма DES

    Начальная перестановка, IP. Начальная перестановка алгоритма DES определяется таблицей 1. Эту и все другие таблицы, изображающие перестановки, следует читать слева направо и сверху вниз. Так, число 58, расположенное в первой строке и первом столбце таблицы, означает, что IP перемещает пятьдесят восьмой бит входных данных на первое место. Аналогично, согласно этой таблице, второй бит перемещается в позицию 50, и т. д.

    Алгоритм шифрования данных DES

    DES (Data Encruption Standart) — Симметричный алгоритм шифрования, в котором один ключ используется как и для шифрования так и для расшифрования данных. DES разрабртан фирмой IBM и утвержен правительством США в 1977 году как официальный стандарт (FTPS 46-3). DES имеет блоки по 64 бит и 16 цикловую структуру сети Фейстеля, для шифрования использует ключ с длиной 56 бит. Алгоритм использует комбинирование нелинейного (S -блок) и линейного (перестановки E, IP, IP-1). Для DES рекомендовано несколько режимов: Режим электронной кодовой книги (EВС- Electronic Code Book), режим сцепления блоков (СВС- Cipher Block Chaining), режим обратной связи по шифртексту (CFB- Cipher Feed Back), режим обратной связи по выходу (OFB- Output Feed Back).

    История Править

    В 1972, после проведения исследования потребностей правительства США в компьютерной безопасности, американское НБС (Национальное Бюро Стандартов) — теперь переименовано НИСТ (Национальный Институт Стандартов и Технологий) — определило необходимость в общеправительственном стандарте шифрования некритичной информации. 15 мая 1973, после консультации с АНБ (Агентством национальной безопасности), НБС объявило конкурс на шифр, который удовлетворит строгим критериям проекта, но ни один конкурсант не обеспечивал выполнение всех требований. Второй конкурс был начат 27 августа 1974. На сей раз, шифр Lucifer, представленный IBM и развитый в течение периода 1973—1974 сочли приемлемым, он был основан на более раннем алгоритме Хорста Фейстеля.

    17 марта 1975 предложеный алгоритм DES был издан в Федеральном Регистре. В следующем году было проведено 2 открытых симпозиума по обсуждению этого стандарта, где подверглись жёсткой критике изменения внесённые АНБ в алгоритм: уменьшение первоначальной длины ключа и таинственные S-блоки. АНБ подозревалось в сознательном ослаблении алгоритма с целью, чтобы АНБ могло легко просматривать зашифрованые сообщения. После чего сенатом США была проведена проверка действий АНБ, результатом которой стало заявление опубликованное в 1978, в котором говорилось о том, что в процессе разработки DES АНБ убедило IBM, что уменьшенной длины ключа более чем достаточно для всех коммерческих приложений, использующих DES, косвенно помогало в разработке S-перестановок, а также, что окончательный алгоритм DES был лучшим, по их мнению, алгоритмом шифрования и был лишён статистической или математической слабости. Также было обнаружено, что АНБ никогда не вмешивалось в разработку этого алгоритма.

    Часть подозрений в скрытой слабости S-перестановок была снята в 1990, когда были опубликованы результаты независимых исследований Эли Бихама (Eli Biham) и Ади Шамира (Adi Shamir) по дифференциальному криптоанализу — основному методу взлома блочных алгоритмов шифрования с симметричным ключом. S-блоки алгоритма DES оказались намного более устойчивыми к атакам, чем если бы их выбрали случайно. Это означает, что такая техника анализа была известна АНБ ещё в 70-х годах XX века.

    DES является блочном шифром. Чтобы понять как работает DES прежде всего мы немного расмотрим блочный шифр, сеть Фейстеля.

    Блочный шифр Править

    Алфавитом, на котором действует блочный шифр, является множетсво двоичных векторов блоков открытого текста одинаковой длины (64, 128. бит).

    Потребление блочных шифров: пременение шифрующего преобразования к наборам аргументов, отличающихся в незначительном числе позиций, приводило к существеному изменению результата. Блочные шифры реализуюся путем многократного применения к блокам исходного текста некоторых базовых преобразований.

    — Сложное преобразование на одной локальной части блока.

    — Простое преобразование между частями блока.

    Так как объекты, на которые действует блочный шифр являются блоком, то один шаг при шифровании — это преобразование данных, которые должны зашифровать, в блоки.Данные могут сохранять в files .text, .word, .map, .jpg…При таком преобразовании во первых нужно сохранять данные в бинарном виде, потом разбить такие бинарные files в блоки, может есть еще другие способы.Все, сказаные здесь, могут осуществляться программами или аппаратами.

    Преобразования Сетью Фейстеля Править

    Это преобразование над векторами (блоками) представляющими собой левую и правую половины регистра сдвига. В алгоритме DES используются прямое преобразование сетью Фейстеля в шифровании (см. Рис.1) и обратное преобразование сетью Фейстеля в расшифрование(см. Рис.2).

    Схема шифрования алгоритма DES Править

    Схема шифрования алгоритма DES указана как на Рис.3

    Исходный текст – блок 64 бит.

    Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.

    Расмотрим подробную схему алгоримта DES:

    $ L_i,L_i, i=1,2,\ldots $ левая и правая половины 64-битового блока $ L_iR_i $

    $ k_i $ – 48 битовые ключи, f – функция шифрования, IP — начальная перестановка, $ IP^ <-1>$ – конечная перестановка.

    — Исходный текст T (блок 64 бит)преобразуетя c помощью начальной перестановки IP которая определяется таблицей 1:

    Таблица 1.Начальная перестановка IP

    58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
    62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
    57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
    61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

    По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58,50,42 входного блока Т, а его 3 последние бита являются битами 23,15,7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

    — 16 циклов преобразования Фейстеля:

    Разбить IP(T) на две части $ L_0,R_0 $ , где $ L_0,R_0 $ — соответствено 32 старщих битов и 32 младших битов блока $ T_0 $ IP(T)= $ L_0R_0 $

    Пусть $ T_ = L_R_ $ результат (i-1) итерации, тогда результат i-ой интерации $ T_i = L_iR_i $ определяется:

    $ L_i = R_ $ $ R_i = L_\oplus f(R_,k_i) $

    Левая половина $ L_i $ равна правой половине предыдущего вектора $ L_R_ $ . А правая половина $ R_i $ — это битовое сложение $ L_ $ и $ f(R_,k_i) $ по модулю 2.

    В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Расмотрим подровно функцию f.

    Аргументы функции f являются 32 битовой вектор $ R_ $ , 48 битовой ключ ki, которые являются результатом преобразования 56 битового исходного ключа шифра k.

    Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков $ S_1,S_2,S_3\ldots\ S_8 $ , и перестановка P.

    Функция Е расширяется 32 битовой вектор $ R_ $ до 48 битовой вектор $ E(R_) $ путем дублирования некоторых битов из $ R_ $ при этом порядок битов вектора $ E(R_) $ указан в таблице 2.

    Таблица 2.Функция расширения E

    32 1 2 3 4 5
    4 5 6 7 8 9
    8 9 10 11 12 13
    12 13 14 15 16 17
    16 17 18 19 20 21
    20 21 22 23 24 25
    24 25 26 27 28 29
    28 29 30 31 32 1

    Первые три бита вектора $ E(R_) $ являются битами 32, 1, 2 вектора $ R_ $ . По таблице 2 видно что биты 1,4,5,8,9,12,13,16,17,20,21,24,25,28,29,32 дублируются. Последние 3 биты вектора $ E(R_) $ — это биты 31,32,1 вектора $ R_ $ . Полученный после перестановки блок $ E(R_) $ складывается по модулю 2 с ключами $ k_i $ и затем представляются в виде восьми последовательных блоков $ B_1,B_2. B_8 $ . $ E(R_)= B_1B_2. B_8 $ . Каждый $ B_j $ является 6-битовым блоком. Далее каждый из блоков $ B_j $ трансформируется в 4 битовой блок $ B’_j $ с помощью преобразований $ S_j $ . Преобразования $ S_j $ определяется таблицей 3.

    Таблица 3.Преобразования $ S_i $ ,i=1. 16

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    14 4 13 1 2 15 11 8 3 10 6 12 5 9 7
    1 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 $ S_1 $
    2 4 1 4 8 13 6 2 11 15 12 9 7 3 10 5
    3 1 12 8 2 4 9 1 7 5 11 3 14 10 6 13
    15 1 8 14 6 11 3 4 9 7 2 13 12 5 10
    1 3 13 4 7 15 2 8 14 12 1 10 6 9 11 5 $ S_2 $
    2 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
    3 13 8 10 1 3 15 4 2 11 6 7 12 5 14 9
    10 9 14 6 3 15 5 1 13 12 7 11 4 2 8
    1 13 7 9 3 4 6 10 2 8 5 14 12 11 15 1 $ S_3 $
    2 13 6 4 9 8 15 3 11 1 2 12 5 10 14 7
    3 1 10 13 6 9 8 7 4 15 14 3 11 5 2 12
    7 13 14 3 6 9 10 1 2 8 5 11 12 4 15
    1 13 8 11 5 6 15 3 4 7 2 12 1 10 14 9 $ S_4 $
    2 10 6 9 12 11 7 13 15 1 3 14 5 2 8 4
    3 3 15 6 10 1 13 8 9 4 5 11 12 7 2 14
    2 12 4 1 7 10 11 6 8 5 3 15 13 14 9
    1 14 11 2 12 4 7 13 1 5 15 10 3 9 8 6 $ S_5 $
    2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 14
    3 11 8 12 7 1 14 2 13 6 15 9 10 4 5 3
    12 1 10 15 9 2 6 8 13 3 4 14 7 5 11
    1 10 15 4 2 7 12 9 5 6 1 13 14 11 3 8 $ S_6 $
    2 9 14 15 5 2 8 12 3 7 4 10 11 13 1 6
    3 4 3 2 12 9 5 15 10 11 14 1 7 6 8 13
    4 11 2 14 15 8 13 3 12 9 7 5 10 6 1
    1 13 11 7 4 9 1 10 14 3 5 12 2 15 8 6 $ S_7 $
    2 1 4 11 13 12 3 7 14 10 15 6 8 5 9 2
    3 6 11 13 8 1 4 10 7 9 5 15 14 2 3 12
    13 2 8 4 6 15 11 1 10 9 3 14 5 12 7
    1 1 15 13 8 10 3 7 4 12 5 6 11 14 9 2 $ S_8 $
    2 7 11 4 1 9 12 14 2 6 10 13 15 3 5 8
    3 2 8 14 7 4 10 8 13 15 12 9 3 5 6 11

    Предположим что $ B_3 = 101111 $ и мы хотим найти $ B’_3 $ .Первый и последний разряды $ B_3 $ являются двоичной записью числа а, 0 $ B’_3 $ .В нашем случае $ a = 11_2 = 3, b = 0111_2 = 7 $ ,число определяется парой (3,7) равно 7, следует $ B’_3 $ =0111.

    Значение функции $ f(R_,k_i) $ (32бит) получается перестановкой Р, применяемой к 32 битовому блоку $ B’_1B’_2. B’_8 $ . Перестановка Р задана таблицей 4.

    Таблица 4.Перестановка P

    16 7 20 21 29 12 28 17
    1 15 23 26 5 18 31 10
    2 8 24 14 32 27 3 9
    19 13 30 6 22 11 4 25

    $ f(R_,k_i) = P(B’_1B’_2. B’_8) $ Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это бита 16,7,20,21 вектора $ B’_1B’_2. B’_8 $

    Генератор ключей $ k_i $ . Ключи $ k_i $ получаются из начального ключа k (56 бит =7 байтов или 8 слов в АSCII )таким образом. Восемь битов, находящих в позициях 8,16,24,32,40,48,56,68 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей.Затем делают перестановку для 56 битового ключа. Такая перестановка определенна как в таблице 5.

    57 49 41 33 25 17 9 1 58 50 42 34 26 18 $ C_0 $
    10 2 59 51 43 35 27 19 11 3 60 52 44 36
    63 55 47 39 31 23 15 7 62 54 46 38 30 22 $ D_0 $
    14 6 61 53 45 37 29 21 13 5 28 20 12 4

    Эта перестановка определяется двумя блоками $ C_0 $ и $ D_0 $ по 28 бит каждый. Первые 3 бита $ C_0 $ есть биты 57, 49, 41 исходного ключа k.А первые три бита $ D_0 $ есть биты 63, 55, 47 ключа k. $ C_i, D_i $ i=1,2,3. получаются из $ C_, D_ $ одним или двумя левыми циклическими сдвигами согласно таблице 6.

    i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    Число сдвига 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

    Ключ $ k_i $ ,i=1,…16 состоит из 48 бит, выбранных из битов вектора $ C_iD_i $ (64 бит) согласно таблице 7. Первый и второй биты $ k_i $ есть биты 14, 17 вектора $ C_iD_i $

    14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4
    26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40
    51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

    Конечная перестанока $ IP^ <-1>$ действует на $ T_ <16>$ и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.

    40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
    38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
    36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
    34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

    Схема расшифрования Править

    При расшифровании данных все действия выполняются в обратном порядке. В 16 циклах расшифрования, в отличие от шифрования c помощью прямого преобразования сетью Фейстеля, здесь используется обратное преобразование сетью Фейстеля.

    $ L_ = R_i $ $ R_ = L_i \oplus f(R_i,k_i) $

    Cхема расшифрования указана как на Рис.5. Ключ $ k_i $ , i=1. 15, функция f, перестановка IP и $ IP^ <-1>$ такие же как и в процессе шифрования.

    Режимы использования DES Править

    DES может используется в четырех режимах.

    1.Режим электронной кодовой книги(ЕСВ –Electronic Code Book): обычное использование DES как блочный шифр (см. Рис.7).

    2.Режим сцепления блоков (СВС- Cipher Block Chaining) (см. Рис.8).

    Каждый блок $ C_i $ i>=1, перед очередным зашифрованием складывается по модулю 2 со следующим блоком открытого текста $ M_ $ . Вектор $ C_0 $ — начальный вектор, он меняется ежедневно и хранится в секрете.

    3.Режим обратной связи с шифртексту(CFB – Cipher Feed Back) (см. Рис.9).

    В режиме СFB выработывается блочная «гамма» $ Z_0, Z_1. $ $ Z_i=DES_k(C_) $ $ C_i = M_i \oplus Z_i $ . Начальный вектор $ C_0 $ сохраняется в секрете.

    4.Режим обратной связи по выходу (OFB – Output Feed Back) (см. Рис.10).

    В режиме OFB вырабатывается блочная «гамма» $ Z_0, Z_1. $ $ Z_i=DES_k(Z_) C_i = M_i \oplus Z_i $ , i>=1

    Достоинства и недостотачки режимов:

    Режим ECB просто реализуется, но возможно происходить проведение критоанализа. В режимах ECB и OFB искажение при передаче одного 64-битового блока шифртекста $ C_i $ приводит к искажению после расшифрования только соответствующего открытого блока $ M_i $ , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.

    В режимах CBC и CFB искажение при передаче одного блока шифрованного текста Сi приводит к искажению на приемнике не более двух блоков открытого текста $ M_i, M_ $ . Изменение $ M_i $ приводится к изменению всех остальных блоков $ M_, M_ $ . Это свойство используется для выработки кода аутентификации сообщения.

    Криптостойкость алгоритма DES Править

    Нелинейность преобразований в DES только S- блоками, сказали что S-блоки имеют некоторую слабину, позволяющую осуществовать контроль за шифрованной перепиской. Для выбора S- блоков потребуется несколько условия. -Каждая строка каждой блока – перестановка множество

    -S-блоки не должны являются линейной или афинной функцией своих входов.

    -Изменение одного бита входа S-блока должно приводить к изменению по крайней мере двух битов выхода.

    -Для кждого S-блока и любого входа х значение S(x) и $ S(x \oplus 001100_2) $ должны различаться по крайней мере двумя битами.

    Из-за не большлго числа ключей (всего $ 2^ <56>$ ключей) дает возможность их полного перебора на быстродействующей вычислительной технике за реальное время.В факте в 1998г The electronic Foundation использует специальный компьютер DES-Cracker, разбивает DES за 3 дня.

    В алгоритме DES существуют слыбые и полу-слабыми ключи. Слабыми ключами называется ключи k такие что $ DES_k(DES_k(x)) = x $ , x блок 64 бит. А полу-слабыми ключи- пары ключа $ (k_1, k_2) $ такие что $ DES_(DES_(x)) = x $ Существует 4 известных DES-слабых ключей,указаные в таблице 9. Для каждого слабого ключа существует $ 2^ <32>$ «постоянные точки», т.е. такие 64-битовые блоки х, что $ DES_k(x) = x $

    Таблица 9.DES-Слабые ключи

    Слабые ключи(hexadecimal) $ C_0 $ $ D_0 $
    0101-0101-0101-0101 $ [0]^ <28>$ $ [0]^ <28>$
    FEFE-FEFE-FEFE-FEFE $ [1]^ <28>$ $ [1]^ <28>$
    1F1F-1F1F-0E0E-0E0E $ [0]^ <28>$ $ [1]^ <28>$
    E0E0-E0E0-F1F1-F1F1 $ [1]^ <28>$ $ [0]^ <28>$

    $ [0]^ <28>$ обозначает вектор, состоящий из 28 нулевых битов.

    Существуют 6 DES-полу-слыбые паы ключей, указанные в таблице 10. Для каждого из 12 полу-слабых ключей существуют $ 2^ <32>$ «анти-постоянные точки», т.е. такие блоки х, что $ DES_k(x) = \tilde $

    Таблица 10.Полу-слабые ключи

    $ C_0 $ $ D_0 $ Пары полу-слабых ключей $ C_0 $ $ D_0 $
    $ [01]^ <14>$ $ [01]^ <14>$ 01FE-01FE-01FE-01FE,—-FE01-FE01-FE01-FE01 $ [10]^ <14>$ $ [10]^ <14>$
    $ [01]^ <14>$ $ [01]^ <14>$ 1FE0-1FE0-1FE0-1FE0,—-E0F1-E0F1-E0F1-E0F1 $ [10]^ <14>$ $ [10]^ <14>$
    $ [01]^ <14>$ $ [0]^ <28>$ 01E0-01E0-01F1-01F1,—-E001-E001-F101-F101 $ [10]^ <14>$ $ [0]^ <28>$
    $ [01]^ <14>$ $ [1]^ <28>$ 1FFE-1FFE-0EFE-0EFE,—-FE1F-FE1F-FE0E-FE0E $ [0]^ <28>$ $ [1]^ <28>$
    $ [0]^ <28>$ $ [01]^ <14>$ O11F-011F-010E-010E,—-1F01-1F01-0E01-0E01 $ [0]^ <28>$ $ [10]^ <14>$
    $ [1]^ <28>$ $ [01]^ <14>$ E0FE-E0FE-F1FE-F1FE,—-FEE0-FEE0-FEF1-FEF1 $ [1]^ <28>$ $ [10]^ <14>$

    Таблица11. Известные аттаки на DES.

    Методы атаки Data Complexity Known Data Complexity Chosen Storage Complexity Proccessing Complexity
    полный поиск 1 Negligible $ 2^ <55>$
    линейный криптоанализ $ 2^ <43>(85%) $ For texts $ 2^ <43>$
    $ 2^ <38>(10%) $ Fortexts $ s^ <50>$
    дифферц. криптоанализ $ 2^ <47>$ For texts $ 2^ <47>$
    $ 2^ <55>$ For texts $ 2^ <55>$

    Чтобы увеличивать криптостойкость DES появляются методы double DES (2DES), triple DES (3DES).Такие методы основны на DES но увеличивают длину ключи( 2DES – 112бит, 3DES- 168 бит), и поэтому увеличить критостойкость.

    Применение Править

    DES был нацианальном стандартом США в 1977 — 1980г.Сейчас DES еще испльзуется но чащее используют его более кпритостойчивый вид (3DES, 2DES). 3DES является простой эффективной заменой DES.

    Схема шифрования алгоритма DES. Стандарт шифрования данных (DES)

    Блочный шифр

    Преобразования Сетью Фейстеля

    Схема шифрования алгоритма DES

    Процесс шифрования состоит в начальной перестановке, 16 циклах шифрования и конечной перестановке.
    Рассмотрим подробную схему алгоритма DES:
    L i R i =1,2\ldots.левая и правая половины 64-битового блока L i R i
    k i — 48 битовые ключи
    f — функция шифрования
    IP — начальная перестановка
    IP -1 — конечная перестановка. По таблице первые 3 бита результирующего блока IP(T) после начальной перестановки IP являются битами 58, 50, 42 входного блока Т, а его 3 последние бита являются битами 23, 15, 7 входного блока. Дальше 64-битовой блок IP(T) участвует в 16-циклах преобразования Фейстеля.

    16 циклов преобразования Фейстеля:

    Разбить IP(T) на две части L 0 ,R 0 , где L 0 ,R 0 — соответствено 32 старших битов и 32 младших битов блока T0 IP(T)= L 0 R 0

    Пусть T i -1 = L i -1 R i -1 результат (i-1) итерации, тогда результат i-ой интерации T i = L i R i определяется:

    L i = R i — 1 Левая половина L i равна правой половине предыдущего вектора L i — 1 R i — 1 . А правая половина R i — это битовое сложение L i — 1 и f(R i — 1 , k i) по модулю 2.

    В 16-циклх преобразования Фейстеля функция f играет роль шифрования. Рассмотрим подробно функцию f.

    Аргументы функции f являются 32 битовой вектор R i — 1 , 48 битовой ключ k i , которые являются результатом преобразования 56 битового исходного ключа шифра k.

    Для вычисления функции f используются фукция расширения Е, преобразование S, состоящее из 8 преобразований S-блоков , и перестановка P.

    Функция Е расширяется 32 битовой вектор R i — 1 до 48 битовой вектор E(R i — 1) путем дублирования некоторых битов из R i — 1 при этом порядок битов вектора E(R i — 1) указан в таблице 2. Первые три бита вектора E(R i — 1) являются битами 32, 1, 2 вектора R i -1 . По таблице 2 видно что биты 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 дублируются. Последние 3 биты вектора E(Ri — 1) — это биты 31, 32, 1 вектора R i — 1 . Полученный после перестановки блок E(R i -1) складывается по модулю 2 с ключами k i и затем представляются в виде восьми последовательных блоков B 1 ,B 2 . B 8 .
    E(R i — 1) = B 1 B 2 . B 8
    Каждый B j является 6-битовым блоком. Далее каждый из блоков B j трансформируется в 4 битовой блок B» j с помощью преобразований S j . Преобразования S j определяется таблицей 3. Предположим что B 3 = 101111 и мы хотим найти B» 3 . Первый и последний разряды B 3 являются двоичной записью числа а, 0Значение функции f(R i — 1 ,k i) (32 бит) получается перестановкой Р, применяемой к 32 битовому блоку B» 1 B» 2 . B» 8 . Перестановка Р задана таблицей 4.
    f(R i — 1 ,k i) = P(B» 1 B» 2 . B» 8)
    Согласно таблице 4, первые четыре бита результирующего вектора после действия функции f — это бита 16, 7, 20, 21 вектора B» 1 B» 2 . B» 8

    Генерирование ключей k i .
    Ключи k i получаются из начального ключа k (56 бит = 7 байтов или 7 символов в АSCII) таким образом. Восемь битов, находящих в позициях 8, 16, 24, 32, 40, 48, 56, 64 добавляются в ключ k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Затем делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64). Такая перестановка определенна как в таблице 5.

    Эта перестановка определяется двумя блоками C 0 и D 0 по 28 бит каждый. Первые 3 бита C 0 есть биты 57, 49, 41 расширенного ключа. А первые три бита D 0 есть биты 63, 55, 47 расширенного ключа. C i ,D i i=1,2,3…получаются из C i — 1 ,D i — 1 одним или двумя левыми циклическими сдвигами согласно таблице 6.

    Ключ k i , i=1,…16 состоит из 48 бит, выбранных из битов вектора C i D i (56 бит) согласно таблице 7. Первый и второй биты k i есть биты 14, 17 вектора C i D i

    Конечная перестановка IP — 1 действует на T 16 и используется для востановления позиции. Она является обратной к перестановке IP. Конечная перестановка определяется таблицей 8.
    Режимы использования DES DES может используется в четырех режимах.

  • Режим электронной кодовой книги (ЕСВ — Electronic Code Book): обычное использование DES как блочного шифра (см. Рис.7).
  • Режим сцепления блоков (СВС — Cipher Block Chaining) (см. Рис.8). Каждый очередной блок C i i>=1, перед зашифровыванием складывается по модулю 2 со следующим блоком открытого текста M i + 1 . Вектор C 0 — начальный вектор, он меняется ежедневно и хранится в секрете.
  • Режим обратной связи по шифротексту (CFB — Cipher Feed Back) (см. Рис.9). В режиме СFB вырабатывается блочная «гамма» Z 0 ,Z 1 . Z i = DESk(C i — 1) . Начальный вектор C 0 сохраняется в секрете.
  • Режим обратной связи по выходу (OFB — Output Feed Back) (см. Рис.10). В режиме OFB вырабатывается блочная «гамма» Z 0 ,Z 1 . , i>=1
  • Режим ECB прост в реализации, но возможно проведение критоанализа
  • В режимах ECB и OFB искажение при передаче одного 64-битового блока шифротекста C i приводит к искажению после расшифрования только соответствующего открытого блока M i , поэтому такие режимы используется для передачи по каналам связи с большим числом искажений.
  • В режимах CBC и CFB искажение при передаче одного блока шифрованного текста С i приводит к искажению на приёмнике не более двух блоков открытого текста M i ,M i + 1 . Изменение Mi приводит к изменению всех остальных блоковM i + 1 ,M i + 2 … Это свойство используется для выработки кода аутентификации сообщения.

    Аннотация: Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard. Эта система первой получила статус государственного стандарта в области шифрования данных. И хотя старый американский стандарт DES в настоящее время утратил свой официальный статус, этот алгоритм все же заслуживает внимания при изучении криптографии. Кроме того в этой лекции объясняется, что такое «двухкратный DES», атака «встреча посередине» и способы ее устранения. В этой же лекции кратко рассматривается новый стандарт США на блочный шифр – алгоритм Rijndael.

    Цель лекции : познакомить студента с основными сведениями об алгоритме шифрования DES .

    Основные сведения

    Одной из наиболее известных криптографических систем с закрытым ключом является DES – Data Encryption Standard . Эта система первой получила статус государственного стандарта в области шифрования данных. Она разработана специалистами фирмы IBM и вступила в действие в США 1977 году. Алгоритм DES широко использовался при хранении и передаче данных между различными вычислительными системами; в почтовых системах, в электронных системах чертежей и при электронном обмене коммерческой информацией . Стандарт DES реализовывался как программно, так и аппаратно. Предприятиями разных стран был налажен массовый выпуск цифровых устройств, использующих DES для шифрования данных. Все устройства проходили обязательную сертификацию на соответствие стандарту.

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

    Длина ключа в алгоритме DES составляет 56 бит . Именно с этим фактом связана основная полемика относительно способности DES противостоять различным атакам. Как известно, любой блочный шифр с закрытым ключом можно взломать, перебрав все возможные комбинации ключей. При длине ключа 56 бит возможны 2 56 разных ключей. Если компьютер перебирает за одну секунду 1 000 000 ключей (что примерно равно 2 20), то на перебор всех 2 56 ключей потребуется 2 36 секунд или чуть более двух тысяч лет, что, конечно, является неприемлемым для злоумышленников.

    Однако возможны более дорогие и быстрые вычислительные системы, чем персональный компьютер . Например, если иметь возможность объединить для проведения параллельных вычислений миллион процессоров, то максимальное время подбора ключа сокращается примерно до 18 часов. Это время не слишком велико, и криптоаналитик, оснащенный подобной дорогой техникой, вполне может выполнить вскрытие данных, зашифрованных DES за приемлемое для себя время.

    Вместе с этим можно отметить, что систему DES вполне можно использовать в небольших и средних приложениях для шифрования данных, имеющих небольшую ценность. Для шифрования данных государственной важности или имеющих значительную коммерческую стоимость система DES в настоящее время, конечно, не должна использоваться. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блочный шифр , названный AES (Advanced Encryption Standard) , в основу которого был положен шифр Rijndael , разработанный бельгийскими специалистами. Этот шифр рассматривается в конце лекции.

    Основные параметры DES : размер блока 64 бита, длина ключа 56 бит , количество раундов – 16. DES является классической сетью Фейштеля с двумя ветвями. Алгоритм преобразует за несколько раундов 64-битный входной блок данных в 64-битный выходной блок. Стандарт DES построен на комбинированном использовании перестановки, замены и гаммирования. Шифруемые данные должны быть представлены в двоичном виде.

    Шифрование

    Общая структура DES представлена на рис. 4.1 . Процесс шифрования каждого 64-битового блока исходных данных можно разделить на три этапа:

    1. начальная подготовка блока данных;
    2. 16 раундов «основного цикла»;
    3. конечная обработка блока данных.

    На первом этапе выполняется начальная перестановка 64-битного исходного блока текста, во время которой биты определенным образом переупорядочиваются.

    На следующем (основном) этапе блок делится на две части (ветви) по 32 бита каждая. Правая ветвь преобразуется с использованием некоторой функции F и соответствующего частичного ключа , получаемого из основного ключа шифрования по специальному алгоритму преобразования ключей. Затем производится обмен данными между левой и правой ветвями блока. Это повторяется в цикле 16 раз.

    Наконец, на третьем этапе выполняется перестановка результата, полученного после шестнадцати шагов основного цикла . Эта перестановка обратна начальной перестановке.

    Рассмотрим более подробно все этапы криптографического преобразования по стандарту DES .

    На первом этапе 64-разрядный блок исходных данных подвергается начальной перестановке. В литературе эта операция иногда называется «забеливание» – whitening . При начальной перестановке биты блока данных определенным образом переупорядочиваются. Эта операция придает некоторую «хаотичность» исходному сообщению, снижая возможность использования криптоанализа статистическими методами.

    Одновременно с начальной перестановкой блока данных выполняется начальная перестановка 56 бит ключа. Из рис. 4.1 . видно, что в каждом из раундов используется соответствующий 48-битный частичный ключ K i . Ключи K i получаются по определенному алгоритму, используя каждый из битов начального ключа по нескольку раз. В каждом раунде 56-битный ключ делится на две 28-битовые половинки. Затем половинки сдвигаются влево на один или два бита в зависимости от номера раунда. После сдвига определенным образом выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, то эта операция называется » перестановка со сжатием». Ее результатом является набор из 48 битов. В среднем каждый бит исходного 56-битного ключа используется в 14 из 16 подключей, хотя не все биты используются одинаковое количество раз.

    Далее выполняется основной цикл преобразования, организованный по сети Фейштеля и состоящий из 16 одинаковых раундов. При этом в каждом раунде ( рис. 4.2) получается промежуточное 64-битное значение , которое затем обрабатывается в следующем раунде.

    Левая и правая ветви каждого промежуточного значения обрабатываются как отдельные 32-битные значения, обозначенные L и R .

    Вначале правая часть блока R i расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Эта операция приводит размер правой половины в соответствие с размером ключа для выполнения операции XOR . Кроме того, за счет выполнения этой операции быстрее возрастает зависимость всех битов результата от битов исходных данных и ключа (это называется «лавинным эффектом»). Чем сильнее проявляется лавинный эффект при использовании того или иного алгоритма шифрования, тем лучше.

    После выполнения перестановки с расширением для полученного 48-битного значения выполняется операция XOR с 48-битным подключом K i . Затем полученное 48-битное значение подается на вход блока подстановки S (от англ. Substitution — подстановка), результатом которой является 32-битное значение . Подстановка выполняется в восьми блоках подстановки или восьми S-блоках (S-boxes). При выполнении этой DES на бумаге выглядит достаточно сложным, что уж говорить про его программную реализацию! Разработать правильно и оптимально функционирующую программу полностью в соответствии с DES , наверно, под силу только опытным программистам. Некоторые трудности возникают при программной реализации, например, начальной перестановки или перестановки с расширением. Эти сложности связаны с тем, что первоначально планировалось реализовывать DES только аппаратно. Все используемые в стандарте операции легко выполняются аппаратными блоками, и никаких трудностей с реализацией не возникает. Однако через некоторое время после публикации стандарта разработчики программного обеспечения решили не стоять в стороне и тоже взяться за создание систем шифрования. В дальнейшем DES реализовывался и аппаратно, и программно.

    Алгоритм DES вполне подходит как для шифрования, так и для аутентификации данных. Он позволяет непосредственно преобразовывать 64-битовый входной открытый текст в 64-битовый выходной шифрованный текст, однако данные редко ограничиваются 64 разрядами.

    Чтобы воспользоваться алгоритмом DES для решения разнообразных криптографических задач, разработаны четыре рабочих режима:

    · электронная кодовая книга ECB(Electronic Code Book);

    · сцепление блоков шифра CBC (Cipher Block Chaining);

    · обратная связь по шифртексту CFB (Cipher Feed Back);

    · обратная связь по выходу OFB (Output Feed Back).

    Режим «Электронная кодовая книга»

    Длинный файл разбивают на 64-битовые отрезки (блоки) по 8 байтов. Каждый из этих блоков шифруют независимо с использованием одного и того же ключа шифрования (рис.3.6).

    Основное достоинство – простота реализации. Недостаток – относительно слабая устойчивость против квалифицированных криптоаналитиков. Из-за фиксированного характера шифрования при ограниченной длине блока 64 бита возможно проведение криптоанализа «со словарем». Блок такого размера может повториться в сообщении вследствие большой избыточности в тексте на естественном языке.

    Рисунок 3.6 – Схема алгоритма DES в режиме электронной кодовой книги

    Это приводит к тому, что идентичные блоки открытого текста в сообщении будут представлены идентичными блоками шифртекста, что дает криптоаналитику некоторую информацию о содержании сообщения.

    Режим «Сцепление блоков шифра»

    В этом режиме исходный файл М разбивается на 64-битовые блоки: М = М 1 М 2 . М n . Первый блок М 1 складывается по модулю 2 с 64‑битовым начальным вектором IV, который меняется ежедневно и держится в секрете (рис.3.7). Полученная сумма затем шифруется с использованием ключа DES, известного и отправителю, и получателю информации. Полученный 64-битовый шифр С 1 складывается по модулю 2 со вторым блоком текста, результат шифруется и получается второй 64‑битовый шифр С 2 , и т.д. Процедура повторяется до тех пор, пока не будут обработаны все блоки текста.

    Таким образом, для всех i = 1…n (n – число блоков) результат шифрования С i определяется следующим образом: С i =

    DES (М i  C i –1), где С 0 = IV – начальное значение шифра, равное начальному вектору (вектору инициализации).

    Очевидно, что последний 64-битовый блок шифртекста является функцией секретного ключа, начального вектора и каждого бита

    Рисунок 3.7 – Схема алгоритма DES в режиме сцепления блоков шифра

    открытого текста независимо от его длины. Этот блок шифртекста называют кодом аутентификации сообщения (КАС).

    Код КАС может быть легко проверен получателем, владеющим секретным ключом и начальным вектором, путем повторения процедуры, выполненной отправителем. Посторонний, однако, не может осуществить генерацию КАС, который воспринялся бы получателем как подлинный, чтобы добавить его к ложному сообщению, либо отделить КАС от истинного сообщения для использования его с измененным или ложным сообщением.

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

    Блок М i является функцией только С i –1 и С i . Поэтому ошибка при передаче приведет к потере только двух блоков исходно-го текста.

    Режим «Обратная связь по шифру»

    В этом режиме размер блока может отличаться от 64 бит (рис.3.8). Файл, подлежащий шифрованию (расшифрованию), считывается последовательными блоками длиной k битов (k=1…64).

    Входной блок (64-битовый регистр сдвига) вначале содержит вектор инициализации, выровненный по правому краю.

    Предположим, что в результате разбиения на блоки мы получили n блоков длинойk битов каждый (остаток дописывается нулями или пробелами). Тогда для любого i=1…n блок шифр-текста

    С i = M i  P i –1 ,

    где Р i–1 обозначает k старших битов предыдущего зашифрованного блока.

    Обновление сдвигового регистра осуществляется путем удаления его старших k битов и записи С i в регистр. Восстановление зашифрованных данных также выполняется относительно просто: Р i –1 и С i вычисляются аналогичным образом и

    М i = С i  Р i –1 .

    Рисунок 3.8 – Схема алгоритма DES в режиме обратной связи по шифртексту

    Режим «Обратная связь по выходу»

    Этот режим тоже использует переменный размер блока и сдвиговый регистр, инициализируемый так же, как в режиме СFB, а именно – входной блок вначале содержит вектор инициализации IV, выровненный по правому краю (рис.3.9). При этом для каждого сеанса шифрования данных необходимо использовать новое начальное состояние регистра, которое должно пересылаться по каналу открытым текстом.

    М = М 1 М 2 . M n .

    Для всех i = 1… n

    где Р i – старшие k битов операции DES (С i –1).

    Отличие от режима обратной связи по шифртексту состоит в методе обновления сдвигового регистра.

    Это осуществляется путем отбрасывания старших k битов и дописывания справа Р i .

    Рисунок 3.9 – Схема алгоритма DES в режиме обратной связи по выходу

    Каждому из рассмотренных режимов (ЕСВ, СВС, CFB, OFB) свойственны свои достоинства и недостатки, что обусловливает области их применения.

    Режим ЕСВ хорошо подходит для шифрования ключей: режим CFB, как правило, предназначается для шифрования отдельных символов, а режим OFB нередко применяется для шифрования в спутниковых системах связи.

    Режимы СВС и CFB пригодны для аутентификации данных. Эти режимы позволяют использовать алгоритм DES для:

    · интерактивного шифрования при обмене данными между терминалом и главной ЭВМ;

    · шифрования криптографического ключа в практике автоматизированного распространения ключей;

    · шифрования файлов, почтовых отправлений, данных спутников и других практических задач.

    Первоначально стандарт DES предназначался для шифрования и расшифрования данных ЭВМ. Однако его применение было обобщено и на аутентификацию.

    В системах автоматической обработки данных человек не в состоянии просмотреть данные, чтобы установить, не внесены ли в них какие-либо изменения. При огромных объемах данных, проходящих в современных системах обработки, просмотр занял бы слишком много времени. К тому же избыточность данных может оказаться недостаточной для обнаружения ошибок. Даже в тех случаях, когда просмотр человеком возможен, данные могут быть изменены таким образом, что обнаружить эти изменения человеку очень трудно. Например, «do» может быть заменено на «do not», «$1900» – на «$9100». Без дополнительной информации человек при просмотре может легко принять измененные данные за подлинные. Такие опасности могут существовать даже при использовании шифрования данных. Поэтому желательно иметь автоматическое средство обнаружения преднамеренных и непреднамеренных изменений данных.

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

    Этот процесс описывает стандарт для аутентификации данных ЭВМ (FIPS 113). Суть стандарта состоит в том, что данные зашифровываются в режиме обратной связи по шифртексту (режим CFB) или в режиме сцепления блоков шифра (режим СВС), в результате чего получается окончательный блок шифра, представляющий собой функцию всех разрядов открытого текста. После этого сообщение, которое содержит открытый текст, может быть передано с использованием вычисленного окончательного блока шифра, служащего в качестве криптографической контрольной суммы.

    Одни и те же данные можно защитить, пользуясь как шифрованием, так и аутентификацией. Данные защищаются от ознакомления шифрованием, а изменения обнаруживаются посредством аутентификации. Алгоритм аутентификации можно применить как к открытому, так и к зашифрованному тексту. При финансовых операциях, когда в большинстве случаев реализуются и шифрование, и аутентификация, последняя применяется и к открыто-

    Шифрование и аутентификацию используют для защиты данных, хранящихся в ЭВМ. Во многих ЭВМ пароли зашифровывают необратимым образом и хранят в памяти машины. Когда пользователь обращается к ЭВМ и вводит пароль, последний зашифровывается и сравнивается с хранящимся значением. Если обе зашифрованные величины одинаковы, пользователь получает доступ к машине, в противном случае следует отказ.

    Нередко зашифрованный пароль вырабатывают с помощью алгоритма DES, причем ключ полагается равным паролю, а открытый текст – коду идентификации пользователя.

    С помощью алгоритма DES можно также зашифровать файлы ЭВМ для их хранения.

    Одним из наиболее важных применений алгоритма DES является защита сообщений электронной системы платежей (ЭСП) при операциях с широкой клиентурой и между банками .

    Алгоритм DES реализуется в банковских автоматах, терминалах в торговых точках, автоматизированных рабочих местах и главных ЭВМ. Диапазон защищаемых им данных весьма широк – от оплат $50 до переводов на многие миллионы долларов. Гибкость основного алгоритма DES позволяет использовать его в самых разнообразных областях применения электронной системы платежей.

    Привет, %username%!
    Многим известно, что стандартом по умолчанию в области симметричного шифрования долгое время считался алгоритм DES. Первая успешная атака на этот неубиваемый алгоритм была опубликована в 1993 году, спустя 16 лет после принятия его в качестве стандарта. Метод, который автор назвал линейным криптоанализом, при наличии 2 47 пар открытых/зашифрованных текстов, позволяет вскрыть секретный ключ шифра DES за 2 43 операций.
    Под катом я попытаюсь кратко изложить основные моменты этой атаки.

    Линейный криптоанализ

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

    В первую очередь злоумышленник производит исследование шифра и находит т.н. статистический аналог, т.е. уравнение следующего вида, выполняющееся с вероятностью P ≠ 1/2 для произвольной пары открытый/закрытый текст и фиксированного ключа:
    P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1) ,
    где P n , C n , K n — n-ые биты текста, шифртекста и ключа.
    После того как подобное уравнение будет найдено атакующий может восстановить 1 бит информации о ключе, используя следующий алгоритм

    Алгоритм 1
    Пусть T — количество текстов, для которых левая часть уравнения (1) равняется 0, тогда
    Если T>N/2, где N — число известных открытых текстов.
    Предположить, что K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (когда P>1/2) или 1 (когда P 1/2) или 0 (когда P

    Алгоритм des

    Самым распространенным и наиболее известным алгоритмом симметричного шифрования является DES (Data Encryption Standard). Алгоритм был разработан в 1977 году, в 1980 году был принят NIST (National Institute of Standards and Technology, США) в качестве стандарта.

    DES является классической сетью Фейштеля с двумя ветвями. Данные шифруются 64-битными блоками, используя 56-битный ключ. Алгоритм преобразует за несколько раундов 64-битный вход в 64-битный выход. Длина ключа равна 56 битам. Процесс шифрования состоит из четырех этапов. На первом этапе выполняется начальная перестановка (IP) 64-битного исходного текста (забеливание), во время которой биты переупорядочиваются в соответствии со стандартной таблицей. Следующий этап состоит из 16 раундов одной и той же функции, которая использует операции сдвига и подстановки. На третьем этапе левая и правая половины выхода последней (16-й) итерации меняются местами. Наконец, на четвертом этапе выполняется перестановка IP-1 результата, полученного на третьем этапе. Перестановка IP-1 инверсна начальной перестановке.

    Рис.4. Алгоритм DES

    На рисунке показан способ, в котором используется 56-битный ключ. Первоначально ключ подается на вход функции перестановки. Затем для каждого из 16 раундов подключ Ki является комбинацией левого циклического сдвига и перестановки. Функция перестановки одна и та же для каждого раунда, но подключи Ki для каждого раунда получаются разные вследствие повторяющегося сдвига битов ключа.

    Начальная перестановка и ее инверсия определяются стандартной таблицей. Если М — это произвольные 64 бита, то X = IP (M) — переставленные 64 бита. Если применить обратную функцию перестановки Y = IP-1 (X) = IP-1 (IP(M)), то получится первоначальная последовательность битов.

    Описание раунда des

    Рассмотрим последовательность преобразований, используемую в каждом раунде.

    Рис.5. Иллюстрация раунда алгоритма DES

    64-битный входной блок проходит через 16 раундов, при этом на каждой итерации получается промежуточное 64-битное значение. Левая и правая части каждого промежуточного значения трактуются как отдельные 32-битные значения, обозначенные L и R. Каждую итерацию можно описать следующим образом:

    Таким образом, выход левой половины Li равен входу правой половины Ri-1. Выход правой половины Ri является результатом применения операции XOR к Li-1 и функции F, зависящей от Ri-1 и Ki.

    Рассмотрим функцию F более подробно. Ri, которое подается на вход функции F, имеет длину 32 бита. Вначале Ri расширяется до 48 битов, используя таблицу, которая определяет перестановку плюс расширение на 16 битов. Расширение происходит следующим образом. 32 бита разбиваются на группы по 4 бита и затем расширяются до 6 битов, присоединяя крайние биты из двух соседних групп. Например, если часть входного сообщения

    то в результате расширения получается сообщение

    . . . defghi hijklm lmnopq . . .

    После этого для полученного 48-битного значения выполняется операция XOR с 48-битным подключом Ki. Затем полученное 48-битное значение подается на вход функции подстановки, результатом которой является 32-битное значение.

    Подстановка состоит из восьми S-boxes, каждый из которых на входе получает 6 бит, а на выходе создает 4 бита. Эти преобразования определяются специальными таблицами. Первый и последний биты входного значения S-box определяют номер строки в таблице, средние 4 бита определяют номер столбца. Пересечение строки и столбца определяет 4-битный выход. Например, если входом является 011011, то номер строки равен 01 (строка 1) и номер столбца равен 1101 (столбец 13). Значение в строке 1 и столбце 13 равно 5, т.е. выходом является 0101.

    Далее полученное 32-битное значение обрабатывается с помощью перестановки Р, целью которой является максимальное переупорядочивание битов, чтобы в следующем раунде шифрования с большой вероятностью каждый бит обрабатывался другим S-box.

    Ключ для отдельного раунда Ki состоит из 48 битов. Ключи Ki получаются по следующему алгоритму. Для 56-битного ключа, используемого на входе алгоритма, вначале выполняется перестановка в соответствии с таблицей Permuted Choice 1 (РС-1). Полученный 56-битный ключ разделяется на две 28-битные части, обозначаемые как C0 и D0 соответственно. На каждом раунде Ci и Di независимо циклически сдвигаются влево на 1 или 2 бита, в зависимости от номера раунда. Полученные значения являются входом следующего раунда. Они также представляют собой вход в Permuted Choice 2 (РС-2), который создает 48-битное выходное значение, являющееся входом функции F(Ri-1, Ki).

    Процесс дешифрования аналогичен процессу шифрования. На входе алгоритма используется зашифрованный текст, но ключи Ki используются в обратной последовательности. K16 используется на первом раунде, K1 используется на последнем раунде. Пусть выходом i-ого раунда шифрования будет Li||Ri. Тогда соответствующий вход (16-i)-ого раунда дешифрования будет Ri||Li.

    После последнего раунда процесса расшифрования две половины выхода меняются местами так, чтобы вход заключительной перестановки IP-1 был R16||L16. Выходом этой стадии является незашифрованный текст.

    Илон Маск рекомендует:  Моделирование при сжатии текстовых данных терминология
  • Понравилась статья? Поделиться с друзьями:
    Кодинг, CSS и SQL