Основы симметричного шифрования

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Базовые операции
Побитное сложение по модулю 2
Арифметические операции
Перестановка
Подстановка
Дополнение
Способы построения алгоритмов
Режимы блочного шифрования

У Г А Т У
Побитное сложение по модулю 2
Уфимский государственный авиационный технический университет
Для криптографии важно свойство:
При этом по нельзя определить ни x, ни k
Шифр Вернама:
Длина ключа равна длине сообщения – практически бесполезен
Разбить сообщение на блоки и складывать их с ключом меньшей длины нельзя
Если в ОТ изменить 1 бит, в ШТ изменится тот же по порядку бит

У Г А Т У
Арифметические операции
Уфимский государственный авиационный технический университет
Применяются сложение (a + b), вычитание (a - b), умножение
При выполнении операций игнорируются разряды, вылезающие за границы обрабатываемого слова
т.е. операции выполняются по модулю 2^?, где n – число бит в слове
Чтобы обратить сложение применяется вычитание и наоборот
Сложение/вычитание – альтернатива XOR
Умножение применяется в операциях, которые не придется обращать
Время выполнения умножения часто зависит от значения умножаемых данных, что создает потенциальную уязвимость к тайминг-атакам

У Г А Т У
Перестановка [permutation]
Уфимский государственный авиационный технический университет
Биты меняются местами
Количество возможных перестановок =n! где n – число разрядов
Если изменить 1 бит x, изменится 1 бит y, но расположенный в другом месте
Простейшая аппаратная реализация – перепутывание линий в нужном порядке
Программная реализация:
Таблица перестановок
Умножение матрицы на вектор данных
Некоторые математические функции могут реализовывать подстановку
Таблица начальной перестановки DES.
В 1-й бит y записывается 58-й бит х.
Во 2-й бит у записывается 50-й бит x
и т. д.

У Г А Т У
Перестановка [permutation]
Уфимский государственный авиационный технический университет

У Г А Т У
Подстановка [substitution]
Уфимский государственный авиационный технический университет
Замена блока бит на некоторый другой блок бит той же величины
Подстановка должна:
Существовать для любого значения блока
Быть обратимой
Простейшая аппаратная реализация – перестановка в унарном коде
Если в х изменить 1 бит, y изменится целиком – лавинный эффект
DC
P
EC

У Г А Т У
Подстановка [substitution]
Уфимский государственный авиационный технический университет
Программная реализация:
Таблица замен
Любая обратимая функция y=f(x), где y и x имеют одинаковый размер, является подстановкой
Таблица замен AES.
Байт со значением 00 заменяется на байт со значением 63
Байт со значением 01 заменяется на байт со значением 7С
и т. д.

У Г А Т У
Подстановки и перестановки
Уфимский государственный авиационный технический университет
Существуют подобные операции, при которых меняется размер блока
Расширение (E) – подстановка/перестановка с увеличением размера
Сжатие - подстановка/перестановка с уменьшением размера (необратимо)
Таблицы замен/перестановок гипотетически могут оставлять лазейку, позволяющую создателю алгоритма взламывать шифр
Поэтому они как правило составляются на основе некоторых общеизвестных псевдослучайных данных (например, двоичное представление числа π)

У Г А Т У
Дополнение [padding]
Уфимский государственный авиационный технический университет
Алгоритмы часто оперируют блоками данных определенной длины
Величина текста может не быть кратной длине блока
В таком случае текст может дополняться до нужной величины (нулями, единицами, случайными значениями и т.д.)
Желательно, чтобы исходный текст можно было однозначно восстановить
Может быть непонятно, где кончается блок и начинается дополнение
Примеры:
В последний байт записывается количество значимых бит в последнем блоке, промежуток между ними и концом сообщения заполняется нулями
В самое начало сообщения записывается его длина

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Базовые операции
Способы построения алгоритмов
Гаммирование
SP-сеть
Сеть Фейстеля
Режимы блочного шифрования

У Г А Т У
Способы построения алгоритмов
Уфимский государственный авиационный технический университет
Симметричные алгоритмы бывают блочные и поточные (асимметричные – только блочные)
И те и другие могут оперировать блоками данных фиксированной длины (в поточном алгоритме блок может состоять из одного бита)
Результат зашифровывания блока зависит
В блочных алгоритмах – от своего исходного значения и от ключа
В поточных алгоритмах - <…> и от порядкового номера блока
Блочный алгоритм можно использовать в поточном режиме

У Г А Т У
Гаммирование
Уфимский государственный авиационный технический университет
Основной способ построения поточных алгоритмов
Развитие идеи шифра Вернама
Гамма Г=f(K) – псевдослучайная последовательность, вычисленная на основе секретного ключа К и равная по длине шифруемому тексту
Если ключ есть у Боба и Алисы, оба могут рассчитать Г
Зашифровывание
Расшифровывание
+ Два одинаковых фрагмента ОТ при зашифровывании дадут два разных фрагмента ШТ
- Гаммирование не обеспечивает лавинного эффекта: если в ОТ изменить 1 бит, в ШТ изменится тот же самый бит

У Г А Т У
Подстановочно-перестановочная сеть
Уфимский государственный авиационный технический университет
SP-сеть
Способ построения блочных алгоритмов
Операция XOR выполняется с раундовым ключом
Раундовые ключи для каждого раунда генерируются на основе исходного ключа с помощью процедуры расширения ключа
Расшифровка представляет собой выполнение обратных операций в обратном порядке
i=1:n
Подстановка
Перестановка
XOR

У Г А Т У
Сеть Фейстеля
Уфимский государственный авиационный технический университет
Сбалансированная
Способ построения блочных алгоритмов
Блок данных делится на два полублока L и R
На каждом раунде выполняется:
L(i+0)=L(i) ⨁ f(R(i),K(i))
R(i+0)=R(i)
L(i+1) = R(i+0)
R(i+1) = L(i+0)
где f – функция от полублока и раундового ключа
Даже если функция f односторонняя, раунд будет обратим:
L0= R(i+1)= L(i+0)= L(i) ⨁ f(R(i),K(i))
R0=L(i+1)= R(i+0)=R(i)
L= L0 ⨁ f(R0,K(i))= L(i) ⨁ f(R(i),K(i)) ⨁ f(R(i),K(i)) = L(i)
R= R0 = R(i)

У Г А Т У
Сеть Фейстеля
Уфимский государственный авиационный технический университет
Сбалансированная
При расшифровывании выполняются те же операции, что при зашифровывании, но:
раундовые ключи берутся в обратном порядке,
полублоки меняются местами в начале раунда, а не в конце
Несбалансированная
На каждом раунде:
блок разбивается на части A и B
выполняется А=f1( A, f2(B,Ki) )
где f1 обратима
f2 может быть односторонней
За все раунды любой бит блока должен поменяться несколько раз

У Г А Т У
Блочные алгоритмы
Уфимский государственный авиационный технический университет
Сравнение SP-cети с сетью Фейстеля
При аппаратной реализации удобнее сеть Фейстеля, поскольку одну и ту же схему можно применять и для зашифровки, и для зашифровки
При программной реализации особой разницы нет, однако SP-сеть позволяет обрабатывать весь блок за один раунд, а сеть Фейстеля в лучшем случае за 2
На процессорах с высокой разрядностью SP-сеть предпочтительна
Алгоритмы строят разными способами, однако в разное время были популярны разные подходы:
До 1977 - гаммирование и SP-сеть (сеть Фейстеля еще не была изобретена)
1977-1987 - сбалансированная сеть Фейстеля
1987-2000 - несбалансированная сеть Фейстеля
После 2000 - SP-cеть

У Г А Т У
Содержание лекции
Уфимский государственный авиационный технический университет
Базовые операции
Способы построения алгоритмов
Режимы блочного шифрования
ECB
CBC
PCBC
CFB
OFB
CTR
Синхропосылки

У Г А Т У
Режимы блочного шифрования
Уфимский государственный авиационный технический университет
Блочный алгоритм задает 2 операции:
ШТ = Ш(ОТ,К)
ОТ = ДШ(ШТ,К)
где ОТ и ШТ – блоки фиксированной одинаковой длины
Эти операции могут выполняться в различных режимах
Исходный алгоритм блочный, но все нижеописанные режимы кроме ECB являются поточными

У Г А Т У
Режим ECB
Уфимский государственный авиационный технический университет
ECB
CBC

У Г А Т У
Режим CBС
Уфимский государственный авиационный технический университет

У Г А Т У
Режим CBС
Уфимский государственный авиационный технический университет

У Г А Т У
Режим CBС
Уфимский государственный авиационный технический университет
Режим зацепления блоков шифротекста [Cipher Block Chaining]
Шифрование распараллелить нельзя, расшифровывание - можно
Самый часто используемый режим
IV – синхропосылка, вектор инициализации [Initialization Vector]
Синхропосылка не является секретной, ее знание ничего не дает злоумышленнику
ECB
CBC

У Г А Т У
Режим PCBС
Уфимский государственный авиационный технический университет

У Г А Т У
Режим PCBС
Уфимский государственный авиационный технический университет

У Г А Т У
Режим CFB
Уфимский государственный авиационный технический университет

У Г А Т У
Режим CFB
Уфимский государственный авиационный технический университет

У Г А Т У
Режим CFB
Уфимский государственный авиационный технический университет
Режим гаммирования с обратной связью, режим обратной связи по шифротексту [Cipher FeedBack]
Операция ДШ(ШТ,К) в этом режиме не применяется
Теоретически функция Ш(ОТ,К) может быть односторонней
Шифрование распараллелить нельзя, расшифровывание – можно
Режим не обрел особой популярности за рубежом, однако в отечественной криптографии используется вместо CBC

У Г А Т У
Режим OFB
Уфимский государственный авиационный технический университет

У Г А Т У
Режим OFB
Уфимский государственный авиационный технический университет
Режим обратной связи по выходу [Output FeedBack]
Использование блочного алгоритма в режиме OFB является разновидностью гаммирования
Распараллелить алгоритм нельзя, но можно рассчитать гамму заранее
Расшифрование полностью идентично шифрованию
Дополнение блоков необязательно
Синхропосылка должна быть уникальна для каждого шифруемого текста, иначе

У Г А Т У
Режим CTR
Уфимский государственный авиационный технический университет
* Здесь и далее в рамках курса оператор || обозначает конкатенацию, т.е. склейку строк