Внебрачная статья. Криптография. Часть 1. Начало

Добрый день/вечер/ночь. Сегодня Мы(не путать с Мынкой) расскажем вам о криптографии, а если быть точнее, в первой статье мы рассмотрим симметричные алгоритмы шифрования или криптографию с секретными ключами. ПЕХАЛИ.

Основы.

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

Обмен осуществляется в три этапа:

1. Отправитель передает получателю ключ.
2. Отправитель, используя ключ, зашифровывает сообщение, которое пересылается получателю.
3. Получатель получает сообщение и расшифровывает его.

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

Криптографические алгоритмы обычно строятся с использованием простых и быстро выполняемых операторов нескольких типов. Множество обратимых операторов, преобразующих текст длиной n бит в текст длиной n бит, является элементами группы обратимых операторов по умножению (например, подстановок n-разрядных слов). Пусть f, g, h — обратимые операторы, то есть существуют

Поэтому hgf — последовательное выполнение операторов fgh - тоже обратимый оператор и, как известный факт(Да ну?), операторы выполняются справа налево, то вы, наверное, уже догадались, что обратный оператор к этому произведению равен

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

Ну а теперь поговорим об основных криптографических методах шифрования с секретным ключом и начнём мы с

Моно- и многоалфавитных подстановок.

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

А теперь немного определений: Подстановкой π на алфавите

называется автоморфизм, при котором буквы исходного текста t замещены буквами шифрованного текста π(t) :

Сложна? Скорее всего нет, но давайте для начала узнаем что такое автоморфизм. Автоморфизм — это отображение f:G→G такое что

1. f(a*b)=f(a)*f(b) для всех a,b∈G
2. f — биективно

Где G это некоторая группа с операцией *.

Набор всех подстановок из

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

Для доказательства этого утверждения необходимо показать выполнение всех аксиом группы. Доказательство:

1. Замкнутость: произведение подстановок

является подстановкой:

2. Ассоциативность: результат произведения

не зависит от порядка расстановки скобок:

3. Существование нейтрального элемента: постановка i, определяемая как i(t)=t, 0≤t≤n, является нейтральным элементом

по операции умножения:

4. Существование обратного: для любой подстановки π существует единственная обратная подстановка

удовлетворяющая условию:

Ну а что? Звучит классно, но а что дальше? А дальше, ещё определения(Мы, что, в школе?)

Ключом подстановки k для

называется последовательность элементов симметрической группы

Подстановка, определяемая ключом k, является криптографическим преобразованием

при помощи которого осуществляется преобразование n-граммы исходного текста

в n-грамму шифрованного текста (Как неожиданно)

Где n — произвольное (n=1, 2, …).

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

Мне тут подсказывают, что не все знают что такое n-грамма (Чему вас только Мынка учит?). n-граммой в нашем случае это последовательность из n букв алфавита. В общем случае элементами могут быть также слоги, звуки и слова.

Согласитесь, что это интересно, и Мы уверены, что вы уже хотите перейти к практике, но для начала давайте рассмотрим наиболее существенные особенности подстановки:

1. Исходный текст шифруется посимвольно. Шифрования n-граммы

и ее префикса

связаны соотношениями:

2. Буква шифрованного текста

является функцией только i-oй компоненты ключа

и i-oй буквы исходного текста

Интересный факт (О как мы их любим!!!), известный любому школьнику(Не обобщай): шифр Цезаря является простым вариантом постановки. Причём он относится к группе моноалфовитных подстановок. Согласитесь, звучит круто?(Нет)

Подмножество

симметрической группы

содержащее n подстановок

называется подстановкой Цезаря.

А теперь давайте рассмотрим свойства подстановки Цезаря.
1. Умножение коммутативно,

2. Нейтральный элемент,

3. Обратный элемент к

является

Звучит круто правда?(Ты уже достал, говори нормально). А теперь Мы расскажем вам про то, почему именно Цезаря и какого из — салата, Юлия или какого-то из других.

Семейство подстановок Цезаря названо по имени римского императора Гая Юлия Цезаря, который поручал Марку Туллию Цицерону составлять послания с использованием 50-буквенного алфавита и подстановки

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Стрелка (→) означает, что буква исходного текста (слева) шифруется при помощи

в букву шифрованного текста (справа).

Системой Цезаря называется моноалфавитная подстановка, преобразующая n-грамму исходного текста

в n-грамму шифрованного текста

в соответствии с правилом:

Как можно легко догадаться(Не обобщай, мы тебе уже говорили не делать этого), данная система легко уязвима.

Если злоумышленник имеет:

1. шифрованный и соответствующий исходный текст
2. Или шифрованный текст выбранного злоумышленником исходного текста,

то определение ключа и дешифрование исходного текста тривиальны.

Более эффективны обобщения подстановки Цезаря — шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n-грамм (шифр Хилла) (Так в скобках мы говорим, а вы используете его для статьи, вы нас ущемляете). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Слабая криптостойкость моноалфавитных подстановок преодолевается с применением многоалфавитных подстановок, которые определяются ключом

содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением.

Пусть

— независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве

Система одноразового использования преобразует исходный текст:

в шифрованный текст:

при помощи подстановки Цезаря:

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

и содержит mn точек.

Пример(Ну наконец-то, мы думали что их не будет): В качестве ключа примем текст: «НЕ_ЛЕНИТЕСЬ ИЗУЧАТЬ КРИПТОГРАФИЮ»
Зашифруем с помощью его и таблицы, представленной выше, текст “ПОПРОБУЙ_ РАЗГАДАЙ ”. Шифрование оформим в таблицу:

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

Вывод

Нас тут пинают, что пора заканчивать. Ну раз так, то Мы надеялись, что вам было интересно. Если вам понравится данная статья, то мы выпустим вторую часть, где расскажем вам о ещё более крутых и интересных вещах(Нам скорее всего придётся выпустить, ведь иначе Мынка нам не заплатит).

Если у вас появились вопросы мы с радостью ответим на них в комментариях или сообщениях группы.