Криптография

Наука секретного письма с целью сокрытия сообщения.

Криптоанализ

Искусство взлома криптосистем.

Отрасли криптографии

Симметричные алгоритмы

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

Problem with symmetric key cryptography is that both parties need to share the key with each other before they begin the communication which ultimately poses the threat of leakage of key to some other party.
  • Уравнение шифрования y = eK(x)
  • Уравнение расшифровки x = dK(y)

Асимметричные (или с открытым ключом) алгоритмы

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

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

Криптоанализ: атака на криптосистемы

title:Kerckhoff's Principle
A Cryptosystem should be secure even if the attacker knows all the details of the system with the exception of key.

Принцип Керкхоффа противоречит здравому смыслу! Чрезвычайно заманчиво разработать систему, которая кажется более безопасной, потому что мы скрываем детали. Это называется безопасность через неизвестность.

Классические атаки

Математические атаки

Атаки грубой силы

  • Требуется по крайней мере 1 пара открытый текст-зашифрованный текст.
  • Проверяет все возможные комбинации, пока не будет найден ключ. Атака подстановкой
  • Исторический шифр
  • Шифрует буквы, а не цифры
  • Простой текст заменяется шифрованными буквами.

Обычный текст в зашифрованный текст

A->k
B->d
C->w

так что АББА -> kddk

Возможные атаки на шифр замены:

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

Модульная арифметика

Большинство криптосистем основано на наборах чисел, которые

  • Дискретный (наборы с целыми числами особенно полезны)
  • конечный

Для заданного целого числа n › 1, называемого модулем, два целых числа a и b называются конгруэнтными по модулю n, если n делитель их разности (т. е. если существует целое число k такое, что a − b = kn).

Свойства конгруэнтности

  1. a≡b(mod m) iff m/a-b

Где a и b — целые числа.

  1. a=q.m+r
  2. a≡b(mod m) implies b≡a(mod m)
  3. если a≡b(mod m) и b≡c(mod m) то a≡c(mod m)

Чтобы найти форму отрицательного числа -x mod y = y -(x mod y) : но эту формулу можно использовать только в том случае, если |x| mod y != 0

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

Существует два типа симметричных шифров: — потоковый шифр: шифрует биты по отдельности — блочный шифр: шифрует блок битов

Примеры

  • AES — это пример блочного шифра, который используется для шифрования интернет-коммуникаций.
  • Stream Cipher используется для шифрования голосовой связи мобильного GSM.
  • AES и DES оптимизированы для эффективной работы с современными приложениями.

Поточный шифр

Шифрование

Шифрование в Stream Cipher выполняется путем добавления каждого бита с text+key (mod 2). стоит поближе рассмотреть сложение по модулю 2. Если мы выполняем арифметические действия по модулю 2, единственными возможными значениями будут 0 и 1 (потому что при делении на 2 единственными возможными остатками будут 0 и 1). Таким образом, мы можем рассматривать арифметику по модулю 2 как логические функции, такие как вентили И, вентили ИЛИ, вентили И-НЕ и т. д.

Мод 2 эквивалентен операции XOR

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

Генераторы случайных чисел

ГСЧ играют важную роль в потоковых шифрах. Существует три типа генератора случайных чисел

Генератор истинных случайных чисел (TRNG)

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

(Общие) Генератор псевдослучайных чисел (PRNG)

  • PRNG имеет начальное состояние, называемое seed state
  • Генерируется много чисел, которые можно воспроизвести, если известна начальная точка.
  • Цифры предсказуемы, но эффективны
  • Они используют уже разработанный алгоритм для получения случайных чисел.
s0 = 12345  # this is the initial seed state
si+1 = 012023492si+12345 mod 2E31
So,
s0 = seed
si+1 = ASi+B mod m

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

Криптографически безопасный генератор псевдослучайных чисел (CSPRNG)

  • Они представляют собой особый тип PRNG.
  • Они обладают непредсказуемостью в отличие от PRNG.

Блокнот на один раз

title: Unconditional Security
A cryptosystem is unconditionally or information-theoretically se-
cure if it cannot be broken even with infinite computational re-
sources.

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

В криптографии одноразовый блокнот (OTP) — это метод шифрования, который не может быть взломан, но требует использования одноразового предварительного общего ключа, размер которого не меньше размера отправляемого сообщения. В этом методе открытый текст сочетается со случайным секретным ключом (также называемым одноразовым блокнотом). Затем каждый бит или символ открытого текста шифруется путем объединения его с соответствующим битом или символом из подушечки с использованием модульного сложения.

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

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

Сдвиговые регистры с линейной обратной связью

  • LFSR содержат элемент хранения часов, называемый триггерами, и путь обратной связи.
  • Количество триггеров дает нам степень LFSR, что означает, что m триггеров означают, что степень LFSR равна m.

В операции XOR, если биты совпадают, результат равен 0, в противном случае - 1.

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

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

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

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

Обычный DES больше не используется, вместо него используется 3DES (произносится как тройной DES), где мы применяем шифрование, троекратное DES. DES был взломан атакой с полным перебором. У DES были банковские приложения. В 2018 году поддержка 3DES была фактически прекращена.

Обзор алгоритма DES

DES использует 56-битный ключ для шифрования 64-битного блока или 8 байтов за раз. DES построен вокруг основной идеи под названием Feistel Network. На самом деле многие современные шифры основаны на сети Фейстеля.

DES основан на 16-раундовой сети Фейстеля

Работа сети Фейстеля

  • После первоначальной перестановки 64-битный вход делится на 32-битный L0 и R0 отдельный вход.
  • R0 или правая сторона переходит к L1 без каких-либо изменений.
  • R0 также используется в функции (f), выход которой представляет собой XOR с входом L0.
  • В результате получается R1.
  • Таким образом, шифруется только один 32-битный бит, то есть L0.
  • Обратите внимание, что значения меняются местами для следующего раунда.

Функция, задействованная в DES

  • сначала в качестве входных данных принимается 32-битный открытый текст p1.
  • Затем выполняется расширение, и оно превращается в 48-битное.
  • Теперь эти 48 бит получают XOR с 48-битным ключом.
  • Результат преобразуется в 8 групп по 6 бит.
  • Эти группы входят в s-блоки, которые сопоставляют эти 6 битов с 4 битами, используя таблицу поиска, что дает нам общий результат 32 бита.
  • В конце выполняется перестановка и выдается окончательный 32-битный вывод.