Skip to content

Latest commit

 

History

History
217 lines (123 loc) · 16.7 KB

2.5.2 Encryption.md

File metadata and controls

217 lines (123 loc) · 16.7 KB

Encryption (Шифрование)

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

«Отец кибернетики» Норберт Винер (XX в): «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит затраченных средств, усилий и времени...»

Симметричное шифрование

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

Раскрыть

Наиболее развитых в криптографическом отношении странах существуют стандартные шифры: например, DES – в США и СКЗД – в России.

В своей работе «Математическая теория секретной связи» Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в сложных симметричных шифрах в качестве типичных компонентов можно выделить:

  • Шифры замены Пример: заменить все "А" на "Б";
  • Шифры перестановки Пример: переставить буквы в слове "КОД" на "ДКО";
  • Сочетания двух вышеперечисленных;

Шифры замены

Шифр Цезаря

Шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т.е. после буквы «я» следует буква «а». Поэтому класс шифров, к которым относится и шифр Цезаря, называется шифрами замены.Например, открытый текст при таком способе шифрования преобразуется в шифртекст.

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

Шифр Атбаш

Переворачивает алфавит: 1я буква становится последней и тд

Впервые встречается в древнееврейском тексте Библии / Танаха

Ниже даны примеры для английского, русского и еврейского алфавитов:

Шифр Виженера

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

Шифр Вернама (One Time Pad - OTP)

Шифр Вернама использует побитовую XOR(исключающее ИЛИ) версию шифра Виженера.

Побитовая XOR(исключающее ИЛИ):

Почему этот шифр невзламываемый?

Для начала договоримся, что под взломом мы понимаем прочтение этого сообщения без ключа. Если бы у нас был ключ, мы бы прочитали это сообщение почти сразу, и это уже не взлом.

Теперь посмотрим, почему без ключа этот шифр невозможно взломать.

  • Каждый бит нашего исходного сообщения шифруется соответствующим битом, который берётся из ключа шифрования;
  • Ключ шифрования — это случайные биты, такой «цифровой шум». Он не имеет смысла и в нём нет никакой логики. Каждый следующий бит может быть каким угодно;
  • Шифрование происходит на самом низком уровне — на уровне битов. Мы даже не знаем, что перед нами: буквы, цифры, числа, картинки или аудио. Просто какой-то набор битов, которые выглядят как цифровой шум;

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

«Цифирная азбука» Петра Великого

Cлово «УЖГОРОД» превращалось в шифротекст «амнюинхицахизе».

Шифры перестановки

Шифр Древней Спарты (Сциталь/Скитала/сцитала)

Скитала является официальным символом Американской ассоциации криптограмм:

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

Например, используется палочка, по длине окружности которой помещается 4 символа (число строк в таблице), а длина самой палочки позволяет записать 5 символов (число столбцов в таблице), исходный текст: «это шифр древней спарты». Схематически это можно изобразить так:

_________________________________________
    |  |   |   |   |   |   |
    |  | Э | Т | О | Ш | И |  
    |__| Ф | Р | Д | Р | Е |__ 
       | В | Н | Е | Й | С |  |
       | П | А | Р | Т | Ы |  |
       |   |   |   |   |   |  |
_________________________________________

После разматывания ленты, шифротекст будет следующим «ЭФВПТРНАОДЕРШРЙТИЕСЫ»

Криптосистемой с открытым ключом (асимметричные)

Асимметричным алгоритм - есть асимметрия в алгоритмах: алгоритмы шифрования и дешифрования различны.

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

Раскрыть

В своей работе Диффи и Хеллман, опубликованной под названием «Новые направления в криптографии» (англ. New Directions in Cryptography), они описали метод, позволяющий двум сторонам безопасно обмениваться зашифрованными сообщениями, не передавая заранее общий секретный ключ.

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

Эта концепция легла в основу современных методов шифрования и электронной безопасности, например, таких как SSL/TLS для защиты интернет-соединений и электронных транзакций.

Идея односторонней функции

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

Принцип работы можно описать следующим образом:

  1. Публикация функции шифрования: Пользователь 𝐴, который хочет получать защищенные сообщения, выбирает некоторую одностороннюю функцию 𝐹(𝐾), зависящую от секрета 𝐾. Он открыто сообщает всем описание функции 𝐹(𝐾), так что любой желающий может использовать её для шифрования, но сам секрет 𝐾 остается скрытым и известен только пользователю 𝐴.

  2. Процесс шифрования (открытый ключ): Когда другой пользователь 𝐵 хочет отправить зашифрованное сообщение пользователю 𝐴, он берет информацию 𝑥, которую нужно защитить, и вычисляет её образ под функцией 𝐹(𝐾), получая зашифрованное сообщение 𝐹(𝐾𝑥)​. Это сообщение отправляется пользователю 𝐴 по открытому каналу.

  3. Расшифровка (закрытый ключ): Поскольку у пользователя 𝐴 есть секрет 𝐾, он может инвертировать функцию 𝐹(𝐾), что позволяет ему вычислить исходное сообщение 𝑥 из полученного 𝐹(𝐾𝑥).

Пример односторонней функции

  1. Выбрали функцию умножения чисел — это будет наша "односторонняя функция";

    𝐹(𝐾х)= x × K, где K (секретный ключ) = 17 — это какое-то большое простое число;

  2. Человек хочет отправить число 𝑥=5 мне по открытому каналу, применяя функцию 𝐹(𝐾х)= x × K и получает 85;

  3. Когда получаешь число 85, зная что 𝐾=17, находим исходное число х: 5;

Таким образом, даже если кто-то перехватит 𝐹(𝐾𝑥) - 85, без знания секрета 𝐾 он не сможет за полиномиальное время восстановить исходное сообщение 𝑥, так как функция 𝐹(𝐾) обладает свойством односторонности.

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

Р/NP и односторонняя функция

Доказано, что проблема существования односторонней функции эквивалентна одной из хорошо известных нерешенных проблем – «совпадают ли классы сложностей Р и NP?»

Алгорится ассиметричного шифрования с односторонней функцией

Все действующие сейчас системы опираются на один из следующих трех типов необратимых преобразований:

  • Разложение больших чисел на простые множители (RSA);
  • Вычисление логарифма в конечном поле (криптосистема Эль-Гамаля, дискретное логарифмирование);
  • Вычисление корней алгебраических уравнений (на основе эллиптических уравнений);
  • и др;

TBD - to be determined (еще будет дописываться)

Основы криптографии для начинающих. Алгоритмы и методы шифрования данных https://www.youtube.com/watch?v=mihW-4bt9rg

asymmetric encryption https://www.youtube.com/watch?v=Mm1U_9f4h8w

symmetric encryption https://www.youtube.com/watch?v=IlEj5wajjt8

2.5.1 Cryptology Theme | Back To iOSWiki Contents | 2.5.3 Certificate Theme