Введение в тайнописью: симметричное шифрование

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

Я решил пройти этот курс, потому что я блокчейн-разработчик без обычного образования в области компьютерных наук. В институте я изучал экономику, но потом ушёл в компьютерное программирование. Начав программировать, я стремился «стать поближе к компу» – разобраться, что прячется под всей той абстракцией, с которой я имел дело, занимаясь веб-разработкой. Переход с веб-программирования на криптовалюту и распределённые системы был безрассудно интересным, в том числе благодаря углублению в тайнописью. Но мне нужен был наиболее крепкий фундамент. Так как это достаточно широкая область, я не пожалел $70, чтоб получать информацию на форуме, который модерируют педагоги Стэнфордского института. Но курс можно пройти и безвозмездно без проверки заданий педагогами.

Итак, приступим.

Что такое тайнопись?

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

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

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

    В истинной статье мы сосредоточимся на симметричном шифровании.

    Два типа шифров

    Шифрование обеспечивает конфиденциальность данных и включает две принципиальных составляющих:

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

    Есть два типа симметричных шифров: потоковые и блочные. Для соответствующего осознания этих шифров полезно знакомство с битовыми операциями (операциями, выполняемыми над битами), а именно с исключающим «либо» (XOR). Если кратко, то это сложение 2-ух битов, при котором, если они различные (0 и 1), итог равен 1, а если они однообразные (два нуля либо две единицы), итог равен 0. В предстоящем изложении предполагается, что читатель понимает, что такое XOR и что эту операцию принято обозначать знаком ⊕.

    Потоковый шифр

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

    Как устроен потоковый шифр. : Дэн Бонех

    Внимательные читатели, наверняка, додумались, что у ключа и открытого текста обязано быть что-то общее, причём весьма принципиальное. Правильно! Ключ и открытый текст должны быть схожей длины. Это, естественно, не весьма удобно.

    Чтоб сделать потоковый шифр наиболее удобным, употребляются генераторы псевдослучайных чисел. Генератор псевдослучайных чисел – это детерминированная процедура, которая на базе входа выдаёт наиболее длиннющий псевдослучайный итог. «Детерминированная» значит, что эта процедура при схожем входе постоянно выдаёт один и этот же выход (т. е. «abc123» постоянно даёт «8474f24e0d72e1b949ffd2…»). Слово «псевдослучайный» значит, что хотя выход по сути не случайный (так как он детерминирован на базе определенного входа), он неотличим от истинной случайной строчки. Иными словами, если иметь набор входов и выходов, то нереально осознать, какому выходу соответствует какой вход. Если применять в качестве входа общий скрытый ключ, можно получить наиболее длиннющий псевдослучайный ключ, при помощи которого будет проведена операция XOR над открытым текстом таковой же длины.

    Описанная реализация потокового шифра именуется «разовый блокнот». Весьма принципиальное её свойство состоит в том, что ключ можно применять лишь ОДИН РАЗ. Если он употребляется повторно, сохранность сообщений скомпрометирована.

    Ниже показан слайд из курса. PRG(K) обозначает псевдослучайную последовательность, сгенерированную из нашего общего ключа K. Знак ⊕ обозначает операцию XOR; C – шифротекст; m – сообщение (открытый текст).

    : Дэн Бонех

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

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

    (Может быть, вы направили внимание, что на слайде выше написано «атака 1». Если у вас появился вопросец о «атаке 2», то она относится к тому факту, что потоковый шифр обеспечивает конфиденциальность, но НЕ целостность данных, упоминавшуюся сначала статьи).

    Блочный шифр

    2-ой тип шифров – блочные. Блочный шифр употребляет вход фиксированной длины и циклически опять и опять шифрует начальный текст, используя любой раз иной ключ («раундовый ключ»), пока не выдаст шифротекст той же длины. 3DES и AES – два примера блочных шифров, которые соответственно употребляют вход из 48 и 128 битов.

    Схема блочного шифра. : Дэн Бонех

    На слайде выше показана базисная архитектура блочного шифра. Как можно созидать, для получения в любом раунде новейшего ключа употребляется метод расширения ключа. Начальный текст (m) шифруется опять и опять, пока не будет получен шифротекст (C) таковой же длины.

    Ради краткости в данной нам статье я буду разглядывать AES. Невзирая на историческую значимость DES/3DES, AES сейчас наиболее обширно применяется.

    : Дэн Бонех

    AES построен как подстановочно-перестановочная сеть (SP-сеть). AES употребляет блоки размером 128 битов, что равно 16 б. 16 байтов записываются как матрица 4 на 4. Таковая матрица комфортна для операций с данными. В любом раунде процесс последующий:

  • Проводим операцию XOR над начальным сообщением и первым раундовым ключом (k0).
  • Исполняем подстановку, заменяя блоки данных иными на базе определённой таблицы (процедура ByteSub).
  • Проводим перестановку, сдвигая и перемешивая биты (процедуры ShiftRow и MixColumn).
  • Процесс повторяется 10 раундов.
  • В крайнем раунде опускается процедура MixColumn, проводится операция XOR с крайним раундовым ключом и получаем итоговый шифротекст. Для расшифровки употребляется оборотный процесс. Тем, кто хочет углубиться, могу порекомендовать ознакомиться с сетью Фейстеля, которая употребляется в 3DES, чтоб сопоставить различные блочные шифры.

    Опосля пуска архитектуры Westmere компания Intel стала встраивать в свои микропроцессоры особые аннотации для оптимизации AES, и скоро за ней последовала AMD.

    Режимы блочного шифрования

    В отличие от потоковых, блочные шифры употребляют вход фиксированной длины. Разумеется, мы желаем сразу обрабатывать больше 16 байтов данных. Потому далее принципиально осознать режимы, в каких можно использовать блочные шифры к огромным объёмам данных. 1-ый из их – режим электрической кодовой книжки (ECB). ECB просто разбивает данные на блоки по 16 байтов и делает AES-шифрование единообразно. Это можно созодать параллельно и весьма стремительно. Но это не очень неопасно.

    : Дэн Бонех

    Причина в том, что если 16-байтовые сообщения повторяются, шифротекст тоже будет повторяться. Так возможный злодей сумеет получить информацию о наших данных. Можно показать эту уязвимость на примере изображения, зашифрованного средством ECB. На картинке ниже видно, что тёмные волосы и футболка разрешают различить очертания, по которым можно осознать, что зашифрован снимок чьего-то лица.

    : Дэн Бонех, B. Preneel

    Принципиально, чтоб схемы шифрования были семантически стойкими. Семантическая стойкость значит, что, если есть шифротекст, соответственный одному из 2-ух открытых текстов, недоброжелатель не может знать с вероятностью больше 1/2, какому конкретно открытому тексту он соответствует. Разумеется, что режим ECB семантически нестойкий. Зашифрованное изображение выдаёт много инфы, позволяющей додуматься о исходнике.

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

    В режиме сцепления блоков шифротекста (CBC) любой 16-байтовый блок открытого текста складывается средством операции XOR с шифротекстом предшествующего блока, опосля что производится блочное шифрование (AES).

    : Дэн Бонех

    Начинаем со случайного вектора инициализации (IV), другими словами исходного значения в повторяющемся процессе. В случае CBC значение IV обязано быть случайным (и, как следует, непредсказуемым), а означает, неповторимым в каждой транзакции. 1-ый блок шифротекста – это просто незашифрованный случайный IV. Чтоб получить остальной шифротекст, поначалу проводится операция XOR над случайным IV и первым блоком открытого текста (m[0]). Итог шифруется при помощи раундового ключа k, и получаем 1-ый зашифрованный блок шифротекста (c[0]). Дальше проводится операция XOR над сиим шифротекстом и последующим блоком открытого текста (m[1]), итог шифруется раундовым ключом k, и получаем последующий блок шифротекста (c[1]). Процесс длится, пока не будут зашифрованы все блоки.

    : Дэн Бонех

    Для расшифровки применяется оборотный процесс.

    Принципиальная составляющая CBC-шифрования – это непредсказуемый случайный IV. Если IV будет прогнозируемым, то наша схема шифрования станет уязвимой к атаке на базе подобранного открытого текста. Атака на базе подобранного открытого текста (CPA) предполагает, что злодей может получить шифротексты случайных открытых текстов и с помощью их раскрыть информацию о зашифрованных сообщениях. Как следует, непредсказуемый IV обеспечивает защиту от CPA.

    Попробую разъяснить, как может смотреться таковая атака. Провести CPA при наличии прогнозируемого IV можно из-за параметров XOR. Итог операции XOR над 2-мя схожими значениями (к примеру, 0101 ⊕ 0101) постоянно будет равен нулю. Потому, если вы подозреваете, что шифротекст c[0] соответствует определённому открытому тексту m[0], можно проверить догадку при помощи прогнозируемого IV. Если открытый текст зашифровали при помощи IV1 (c[0] = E(k, m[0] ⊕ IV1)), то можно зашифровать новейший открытый текст и поглядеть, совпадёт ли итог с c[0]. Так как можно предсказать, что IV будет IV2, вы проделываете m[0] ⊕ IV1 ⊕ IV2. CBC сделает операцию XOR над сиим входом и последующим IV (IV2): c[1] = E(k, m[0] ⊕ IV1 ⊕ IV2 ⊕ IV2). Как следует, два IV2 взаимно уничтожаются, и мы опять шифруем E(k, IV1 ⊕ m[0]), что, снова же, даст c[0], и в таком случае мы можем додуматься, что было ранее зашифровано при помощи IV1.

    В конце концов, хотелось бы разглядеть ещё один режим блочного шифрования: рандомизированный режим счётчика (CTR). Это крайний, самый неопасный режим, и он также наиболее эффективен, чем CBC.

    : Дэн Бонех

    Рандомизированный режим счётчика также употребляет случайный IV, но тут он служит иной цели. Наш ключ складывается (к примеру, средством AES) с итерированной версией нашего IV: к примеру, в каждой итерации можно наращивать IV на единицу, чтоб итог не повторялся. Мы делаем это, пока не получим ключ таковой же длины, как наш открытый текст. Сейчас, как и в случае потокового шифра с разовым ключом, мы проводим операцию XOR над нашим открытым текстом и псевдослучайным ключом, чтоб получить шифротекст. Если у вашего компа есть несколько AES-процессоров, то это весьма отлично, потому что может производиться параллельно. В CBC любой шифротекст зависит от предшествующего блока, потому вычислять его параллельно нереально.

    Чтоб получить псевдослучайный ключ из сложения IV и нашего секретного ключа, блочный шифр не обязателен. Блочные шифры должны быть обратимы. Если пристально разглядеть механизм рандомизированного режима счётчика, то можно увидеть, что для дешифровки не надо делать в оборотном порядке F(k, IV). Беря во внимание характеристики XOR, довольно взять этот же псевдослучайный ключ и сложить его средством XOR с нашим шифротекстом. Другими словами для дешифровки необходимо повторить операцию, а не провести её в оборотном порядке.

    Если выражаться абстрактно (до сего времени я избегал абстрактных понятий), это означает, что процедура, которую мы используем для сложения нашего секретного ключа и IV (F(k, IV)) обязана быть псевдослучайной функцией (PRF), а не псевдослучайной перестановкой (PRP). По сути мы сталкивались с этими концепциями в данной нам статье. И PRF, и PRP – это детерминированные процедуры, которые при определенном входе дают псевдослучайный выход (AES, XOR). Но PRP имеет серьезное требование обратимости. Фактически говоря, понятия PRP и блочный шифр (к примеру, AES) нередко употребляются как синонимы. Но PRF НЕ обязана быть обратимой.

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

    Author: Anonim