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

Добрый день/вечер/ночь. Вы этого не просили, но Мынка нас уговорил. Сегодня будет весело и интересно. Советуем вам перед прочтением ознакомится с прошлой статьёй. ПОГРУЖАЕМСЯ.

Системы шифрования Вижинера

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

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

Например, при j=∞ и ключе пользователя 17 23 11 56 43 97 25 рабочий ключ будет периодической последовательностью:

17 23 11 56 43 97 25 17 23 11 56 43 97 25 17 23 11 56 43 97 25 …

Классно? Точно. А теперь любимая наша рубрика ОПРЕДЕЛЕНИЯ.

Подстановка Вижинера

определяется так

Таким образом:

1. исходный текст x делится на r фрагментов

2. i-й фрагмент исходного текста xᵢ шифруется при помощи подстановки Цезаря

Вариант системы подстановок Вижинера при m=2 называется системой Вернама (1917 г)(Скобки наши!!! Не используй их так). В то время ключ

записывался на бумажной ленте. Каждая буква исходного текста в алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту Бодо добавлялся ключ (по модулю 2). Старинный телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования, использовался корпусом связи армии США.

Очень распространена плохая с точки зрения секретности практика использовать слово или фразу в качестве ключа для того, чтобы

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

Давайте опробуем данный шифр. ПРИМЕР. Преобразование текста с помощью подстановки Вижинера при r=5.

Исходный текст – РАБОТАЙТЕ АККУРАТНО

Ключ: ПЕСНЯ

Разобьем исходный текст на блоки по 5 символов: РАБОТ АЙТЕ АККУР АТНО

и наложим на них ключ (используя таблицу Вижинера): Р+П=_, А+Е=Е и т.д. Получаем зашифрованный текст: _ЕТЫРПОГТЮППЫАОПЧЮЫ

Можно выдвинуть и обобщенную систему Вижинера. Ее можно сформулировать не только при помощи подстановки Цезаря.

Пусть

- подмножество.

Определение: . r-многоалфавитный ключ шифрования есть r-набор

Обобщенная система Вижинера преобразует исходный текст

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

при помощи ключа

по правилу

Следует признать, что и многоалфавитные подстановки в принципе доступны криптоаналитическому исследованию. Криптостойкость многоалфавитных систем резко убывает с уменьшением длины ключа. Тем не менее такая система как шифр Вижинера допускает несложную аппаратную или программную реализацию и при достаточно большой длине ключа может быть использован в современных ИС(Интересно и Весело(Нет). Дай нам что-то ещё).

Перестановки

Перестановки являются также несложным методом криптографического преобразования. Используется как правило в сочетании с другими методами. Определение перестановки было дано выше(ГДЕ? Я не увидел?).

Введем обозначение σ для взаимно-однозначного отображения набора

состоящего из n элементов, на себя, т.е

Будем говорить, что в этом смысле σ является перестановкой элементов S. И, наоборот, автоморфизм S соответствует перестановке целых чисел

Криптографическим преобразованием T для алфавита

называется последовательность автоморфизмов:

Каждое

является, таким образом, перестановкой n-грамм из

Поскольку

могут быть определены независимо при i≠j, число криптографических преобразований исходного текста размерности n равно

Оно возрастает непропорционально при увеличении m и n: так, при m=33 и n=2 число различных криптографических преобразований равно 1089!. Отсюда следует, что потенциально существует большое число отображений исходного текста в шифрованный.

Практическая реализация криптографических систем требует, чтобы преобразования

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

Гаммирование

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

, совпадающим с алфавитом шифрованных сообщений и ключевым множеством K. При этом для любого открытого текста

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

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

Обычно в настоящее время используется

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

, а следовательно речи о «совершенной стойкости» идти не может.

Задача создания качественного шифра гаммирования заключается в обеспечении следующих свойств.

1. Максимальную близость гаммы по статистическим свойствам к случайной равновероятной последовательности независимых величин (далее по аналогии с термином «белый шум», известным из физики, такую последовательность будем называть «белой гаммой»).
2. Отсутствие возможности практического восстановления неизвестных отрезков гаммы и ключа по известным. Первое свойство необходимо обеспечивать для невозможности дешифрования шифра гаммирования статистическими методами. Это свойство характеризует в некотором смысле близость конкретного шифра к шифру Вернама. Второе - для того чтобы по части открытого текста невозможно было восстановить весь текст или другие его отрезки.

К достоинствам шифров гаммирования следует отнести следующее:

1. Возможность достижения высоких скоростей шифрования.
2. Коэффициент размножения ошибки равен единице.
3. Поточность шифрования и расшифрования.
4. Сохранение размера текста при шифровании

К недостаткам относится:

1. Нестойкость шифра при повторном использовании ключа
2. Последовательность доступа к информации

Полученный зашифрованный текст является достаточно трудным для раскрытия в том случае, если гамма шифра не содержит повторяющихся битовых последовательностей. По сути дела гамма шифра должна изменяться случайным образом для каждого шифруемого слова. Фактически же, если период гаммы превышает длину всего зашифрованного текста и неизвестна никакая часть исходного текста, то шифр можно раскрыть только прямым перебором (пробой на ключ). Криптостойкость в этом случае определяется размером ключа. Метод гаммирования становится бессильным, если злоумышленнику становится известен фрагмент исходного текста и соответствующая ему шифрограмма. Простым вычитанием по модулю получается отрезок почти случайной последовательности (ПСП) и по нему восстанавливается вся последовательность. Злоумышленники может сделать это на основе догадок о содержании исходного текста. Так, если большинство посылаемых сообщений начинается со слов “СОВ.СЕКРЕТНО”, то криптоанализ всего текста значительно облегчается (Мы умнее этого. У нас все сообщения начинаются со слова «Мынка»). Это следует учитывать при создании реальных систем информационной безопасности. Ниже рассматриваются наиболее распространенные методы генерации гамм, которые могут быть использованы на практике. Этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генерируемой на основе ключа.

Датчики почти случайных чисел

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

Конгруэнтные датчики

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

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n , где n - длина машинного слова в битах. Датчик имеет максимальный период m до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период m был максимальным. Как показано Дональдом Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и А mod 4 = 1.

Для шифрования данных с помощью датчика ПСЧ может быть выбран ключ любого размера. Например, пусть ключ состоит из набора чисел x(j) размерностью n, где j=1, 2, ..., n. Тогда создаваемую гамму шифра G можно представить как объединение непересекающихся множеств H(j). (Мы пришли сообщения шифровать, а не математику учить)

Датчики М-последовательностей

Популярность М-последовательностей объясняется относительно легкой их реализаций. М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k-разрядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемый бит добавляется к гамме. Строго это можно представить в виде следующих отношений:

Здесь

- k однобитных регистров,

– коэффициенты неприводимого двоичного полинома степени k-1.

-i-е значение выходной гаммы.

Период М-последовательности, исходя из ее свойств, равен

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k. Эта характеристика приведена в таблице ниже.

Очевидно, что такие объемы ансамблей последовательности неприемлемы. Поэтому на практике часто используют последовательности Голда, образующиеся суммированием нескольких М-последовательностей. Объем ансамблей этих последовательностей на несколько порядков превосходят объемы ансамблей порождающих М-последовательностей. Так при k=10 ансамбль увеличивается от 1023 (М-последовательности) до 388000.

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

Вывод

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

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