Шифрование с помощью. Основные алгоритмы шифрования

Решение задачи определения ключа путем простого перебора всех возможных вариантов, как правило, является непрактичным, за исключением использования очень короткого ключа. Следовательно, если криптоаналитик хочет иметь реальные шансы на вскрытие шифра, он должен отказаться от «лобовых» методов перебора и применить другую стратегию. При раскрытии многих схем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов или их комбинаций. Для усложнения решения задачи вскрытия шифра с использованием статистического анализа К. Шеннон предложил две концепции шифрования, получившие название смешения (confusion ) и диффузии (diffusion ). Смешение – это применение такой подстановки, при которой взаимосвязь между ключом и шифрованным текстом становится как можно более сложной. Применение данной концепции усложняет применение статистического анализа, сужающего область поиска ключа, и дешифрование даже очень короткой последовательности криптограммы требует перебора большого количества ключей. В свою очередь диффузия – это применение таких преобразований, которые сглаживают статистические различия между символами и их комбинациями. В результате использование криптоаналитиком статистического анализа может привести к положительному результату только при перехвате достаточно большого отрезка шифрованного текста.

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

10.4.1. Метод подстановки.

Простейшим и имеющим наибольшую историю является метод подстановки, суть которого заключается в том, что символ исходного текста заменяется другим, выбранным из этого или другого алфавита по правилу, задаваемому ключом шифрования. Местоположение символа в тексте при этом не изменяется. Одним из ранних примеров использования метода постановки является шифр Цезаря , который использовался Гаем Юлием Цезарем во время его Галльских походов. В нем каждая буква открытого текста заменялась другой, взятой из того же алфавита, но циклически сдвинутого на определенное количество символов. Применение данного метода шифрования иллюстрирует пример, представленный на рис.10.3, в котором шифрующее преобразование основано на использовании алфавита с циклическим сдвигом на пять позиций.

Рис. 10.3 , а )

Рис. 10.3 , б )

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

Другим примером классической схемы, основанной на методе подстановки, может служить система шифрования, называемая квадратом Полибиуса . Применительно к русскому алфавиту данная схема может быть описана следующим образом. Первоначально объединяются в одну буквы Е, Ё; И, Й и Ъ, Ь, истинное значение которых в дешифрованном тексте легко восстанавливается из контекста. Затем 30 символов алфавита размещаются в таблицу размером 65, пример заполнения которой представлен на рис. 10.4.

Рис. 10.4.

Шифрование любой буквы открытого текста осуществляется заданием ее адреса (т.е. номера строки и столбца или наоборот) в приведенной таблице. Так, например, слово ЦЕЗАРЬ шифруется с помощью квадрата Полибиуса как 52 21 23 11 41 61. Совершенно ясно, что изменение кода может быть осуществлено в результате перестановок букв в таблице. Следует также заметить, что те, кто посещал экскурсию по казематам Петропавловской крепости, должно быть памятны слова экскурсовода о том, как заключенные перестукивались между собой. Очевидно, что их способ общения полностью подпадает под данный метод шифрования.

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

Рис. 10.5.

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

Рис. 10.6.

Известны несколько интересных вариантов шифров, основанных на прогрессивном ключе Тритемиуса. В одном из них, называемом методом ключа Вижинера , применяется ключевое слово, которое указывает строки для шифрования и расшифрования каждого последующего символа открытого текста: первая буква ключа указывает строку таблицы на рис. 10.5, с помощью которой шифруется первый символ сообщения, вторая буква ключа определяет строку таблицы, шифрующей второй символ открытого текста и т.д. Пусть в качестве ключа выбрано слово «ТРОМБ», тогда сообщение, зашифрованное с помощью ключа Вижинера, может быть представлено следующим образом (рис. 10.7). Очевидно, что вскрытие ключа возможно осуществить на основе статистического анализа шифрограммы.

Рис. 10.7.

Разновидностью этого метода является т.н. метод автоматического (открытого ) ключа Вижинера , в котором в качестве образующего ключа используется единственная буква или слово. Этот ключ дает начальную строку или строки для шифрования первого или нескольких первых символов открытого текста аналогично ранее рассмотренному примеру. Затем в качестве ключа для выбора шифрующей строки используются символы открытого текста. В приведенном ниже примере в качестве образующего ключа использована буква «И» (рис. 10.8):

Рис. 10.8.

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

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

Рис. 10.9.

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

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

Вариантом реализации подстановочной технологии, который в достаточной степени реализует концепцию смешения, служит следующий пример, базирующийся на нелинейном преобразовании. Поток информационных бит предварительно разбивается на блоки длиной m , причем каждый блок представляется одним из различных символов. Затем множество из
символов перемешивается таким образом, чтобы каждый символ заменялся другим символом из этого множества. После операции перемешивания символ вновь превращается вm –битовый блок. Устройство, реализующее описанный алгоритм при
, представлено нарис. 10.10, где в таблице задано правило перемешивания символов множества из
элементов.

Рис. 10.10.

Не составляет труда показать, что существует
различных подстановок или связанных с ними возможных моделей. В связи, с чем при больших значенияхm задача криптоаналитика становится в вычислительном плане практически невозможной. Например, при
число возможных подстановок определяется как
, т.е. представляет собой астрономическое число. Очевидно, что при подобном значенииm данное преобразование с помощью блока подстановки (substitution block , S –блок) можно считать обладающим практической секретностью. Однако его практическая реализация вряд ли возможна, поскольку предполагает существование
соединений.

Убедимся теперь, что S –блок, представленный на рис. 10.10, действительно осуществляет нелинейное преобразование, для чего воспользуемся принципом суперпозиций: преобразование
является линейным, если. Предположим, что
, а
. Тогда, а, откуда следует, чтоS –блок является нелинейным.

10.4.2. Метод перестановки.

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

Простейшим вариантом реализации данного метода шифрования может служить рассмотренный ранее алгоритм перемежения, суть которого заключается в разбиении потока информационных символов на блоки длиной
, построчной записи его в матрицу памяти размеромстрок истолбцов и считывании по столбцам. Иллюстрацией данному алгоритму служит пример с
на рис. 10.11, в ходе которого производится запись фразыX =«скоро начнется экзаменационная пора». Тогда на выходе устройства перестановки будет получена криптограмма вида

Рис. 10.11.

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

Рис. 10.12.

На рис. 10.13 приведен пример бинарной перестановки данных (линейная операция), из которого видно, что данные просто перемешиваются или переставляются. Преобразование осуществляется с помощью блока перестановки (permutation block , P –блок). Технология перестановки, реализуемая этим блоком, имеет один основной недостаток: она уязвима по отношению к обманным сообщениям. Обманное сообщение изображено на рис. 10.13 и заключается в подаче на вход одной единственной единицы при остальных нулях, что позволяет обнаружить одну из внутренних связей. Если криптоаналитику необходимо осуществить анализ подобной схемы с помощью атаки открытого текста, то он отправит последовательность подобных обманных сообщений, смещая при каждой передаче единственную единицу на одну позицию. В результате подобной атаки будут установлены все связи входа и выхода. Данный пример демонстрирует, почему защищенность схемы не должна зависеть от ее архитектуры.

10.4.3. Метод гаммирования .

Попытки приблизиться к совершенной секретности демонстрируют многие современные телекоммуникационные системы, использующие операцию скремблирования. Подскремблированием понимается процесс наложения на коды символов открытого текста кодов случайной последовательности чисел, которую называют также гаммой (по названию буквы  греческого алфавита, используемой в математических формулах для обозначения случайного процесса). Гаммирование относится к поточным методам шифрования, когда следующие друг за другом символы открытого текста последовательно превращаются в символы шифрограммы, что повышает скорость преобразования. Так, например, поток информационных бит поступает на один вход сумматора по модулю 2, изображенного на рис. 10.14, тогда как на второй – скремблирующая двоичная последовательность
. В идеале последовательность
должна быть случайной последовательностью с равновероятными значениями нулей и единиц. Тогда выходной шифрованный поток
будет статистически независимым от информационной последовательности
, а значит, будет выполняться достаточное условие совершенной секретности. В действительности абсолютная случайность
не является необходимой, поскольку в противном случае получатель не сможет восстановить открытый текст. Действительно, восстановление открытого текста на приемной стороне должно производиться по правилу
, так что на приемной стороне должна генерироваться точно такая же скремблирующая последовательность и с той же фазой. Однако вследствие абсолютной случайности
данная процедура становится невозможной.

На практике в качестве скремблирующих широкое применение нашли псевдослучайные последовательности (ПСП), которые могут быть воспроизведены на приемной стороне. В технологии поточного шифрования для формирования ПСП обычно используют генератор на основелинейного регистра сдвига с обратной связью (linear feedback shift register (LFSR)). Типичная структура генератора ПСП, представленная на рис. 10.15, включает регистр сдвига, который состоит из – ичных элементов задержки или разрядов, имеющихвозможных состояний и хранящих некоторый элемент поля
в течение тактового интервала, схема обратной связи, включающей умножители элементов (состояний), хранящихся в разрядах, на константы, и сумматоров. Формирование ПСП описывается рекуррентным соотношением вида

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

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

Пример 10.4.1. На рис. 10.16, a , представлена реализация генератора на основе регистра сдвига с линейной обратной связью, формирующего двоичную псевдослучайную последовательность периода
. Отметим, что в случае двоичной ПСП умножение на единицу эквивалентно простому соединению выхода разряда с сумматором. Рис. 10.16,b , иллюстрирует следующие друг за другом содержания регистра (состояния разрядов), а также состояния выхода обратной связи (точка ОС на схеме) при подаче тактовых импульсов. Последовательность считывается в виде последовательных состояний крайнего правого разряда. Считывание состояний других разрядов приводит к копиям той же самой последовательности, сдвинутой на один или два такта.

На первый взгляд можно предположить, что использование ПСП большого периода может обеспечить достаточно высокую защищенность. Так, например, в сотовой системе мобильной связи стандарта IS-95 в качестве скремблирующей используется ПСП периода
в числе элементарных чипов. При чиповой скорости 1.228810 6 симв/сек ее период составляет:

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

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

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

при начальном состоянии регистра 0001. В результате будет сформирована последовательность . Предположим, что криптоаналитику, которому ничего неизвестно о структуре обратной связи генератора ПСП, удалось получить
бит криптограммы и ее открытого эквивалента:

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

где символ ПСП, который вырабатывается схемой обратной связи и подается на вход первого разряда регистра, а
определяет отсутствие или наличиеi –го соединения между выходом разряда регистра сдвига и сумматором, т.е. схему обратной связи.

Анализируя состояния регистра сдвига в четыре последовательные момента времени можно составить следующую систему четырех уравнений с четырьмя неизвестными:

Решение данной системы уравнений дает следующие значения коэффициентов:

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

Обобщив рассмотренный пример на случай произвольного регистра сдвига памяти n , исходное уравнение может быть представлено в виде

,

а система уравнений записана в следующей матричной форме

,

где
, а
.

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

.

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

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

Рис. 10.17. Поточное шифрование с обратной связью.

Сначала передается преамбула, в которой содержится информация о параметрах генерируемой ПСП, в том числе и о значении начальной фазы Z 00 . По каждым n сформированным символам шифрограммы вычисляется и устанавливается в генераторе новое значение фазы
. Обратная связь делает метод гаммирования чувствительным к искажениям криптограммы. Так, из-за помех в канале связи могут исказиться некоторые принятые символы, что приведет к вычислению ошибочного значения фазы ПСП и затруднит дальнейшую расшифровку, но после полученияn правильных символов шифрованного текста система восстанавливается. В то же время такое искажение можно объяснить попыткой злоумышленника навязать ложные данные.

В этот день свой профессиональный праздник отмечает Криптографическая служба России.

«Криптография» с древнегреческого означает «тайнопись».

Как раньше прятали слова?

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

выбирали раба. Брили его голову наголо и наносили на неё текст сообщения водостойкой растительной краской. Когда волосы отрастали, его отправляли к адресату.

Шифр — это какая-либо система преобразования текста с секретом (ключом) для обеспечения секретности передаваемой информации.

АиФ.ru сделал подборку интересных фактов из истории шифрования.

Все тайнописи имеют системы

1. Акростих — осмысленный текст (слово, словосочетание или предложение), сложенный из начальных букв каждой строки стихотворения.

Вот, например, стихотворение-загадка с разгадкой в первых буквах:

Д овольно именем известна я своим;
Р авно клянётся плут и непорочный им,
У техой в бедствиях всего бываю боле,
Ж изнь сладостней при мне и в самой лучшей доле.
Б лаженству чистых душ могу служить одна,
А меж злодеями — не быть я создана.
Юрий Нелединский-Мелецкий
Сергей Есенин, Анна Ахматова, Валентин Загорянский часто пользовались акростихами.

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

употребляют в письме верхние буквы вместо нижних и наоборот, причём гласные остаются без перемены; так, например, токепот = котёнок и т. п.

Мудрая литорея предполагает более сложные правила подстановки.

3. «ROT1» — шифр для детишек?

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

А заменяется на Б, Б заменяется на В и так далее. «ROT1» буквально означает «вращать на 1 букву вперёд по алфавиту». Фраза «Я люблю борщ» превратится в секретную фразу «А мявмя впсъ» . Этот шифр предназначен для развлечения, его легко понять и расшифровать, даже если ключ используется в обратном направлении.

4. От перестановки слагаемых...

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

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

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

5. Сдвижной шифр Цезаря

Он состоит из 33 различных шифров, по одному на каждую букву алфавита (количество шифров меняется в зависимости от алфавита используемого языка). Человек должен был знать, какой шифр Юлия Цезаря использовать для того, чтобы расшифровать сообщение. Например, если используется шифр Ё, то А становится Ё, Б становится Ж, В становится З и так далее по алфавиту. Если используется шифр Ю, то А становится Ю, Б становится Я, В становится А и так далее. Данный алгоритм является основой для многих более сложных шифров, но сам по себе не обеспечивает надёжную защиту тайны сообщений, поскольку проверка 33-х различных ключей шифра займёт относительно небольшое время.

Никто не смог. Попробуйте вы

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

Криптос . Скульптура, созданная художником Джимом Санборном, которая расположена перед штаб-квартирой Центрального разведывательного управления в Лэнгли, Вирджиния. Скульптура содержит в себе четыре шифровки, вскрыть код четвёртой не удаётся до сих пор. В 2010 году было раскрыто, что символы 64-69 NYPVTT в четвёртой части означают слово БЕРЛИН.

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

Свои варианты оставляйте в комментариях к этой статье. Ответ появится в 13:00 13 мая 2014 года.

Ответ:

1) Блюдечко

2) Слоненку все надоело

3) Хорошая погода

Шифрование информации

Основным видом криптографического преобразования информации в КС является шифрование и дешифрование. Шифрование – это преобразование информации из открытой формы в закрытую (зашифрованную). Существует и обратный процесс - расшифрование.

За многовековую историю использования шифрования информации человечеством изобретено множество методов шифрования, или шифров. Методом шифрования, или шифром , называется совокупность обратимых преобразований открытой информации в закрытую в соответствии с алгоритмом шифрования. Появление ЭВМ и КС инициировало процесс разработки новых шифров, учитывающих возможности использования ЭВМ как для шифрования/расшифрования информации, так и для атак на шифр. Атака на шифр (криптоанализ) – это процесс расшифрования закрытой информации без знания ключа и, возможно, при отсутствии сведений об алгоритме шифрования.

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

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

В качестве примера удачного метода шифрования можно привести шифр DES (DataEncryptionStandard), применяемый в США с 1978 г. в качестве государственного стандарта. Алгоритм шифрования не является секретным и был опубликован в открытой печати. За время своего использования этого шифра не было обнародовано ни одного случая обнаружения слабых мест в алгоритме шифрования.

Методы шифрования-дешифрования подразделяются на две группы: методы шифрования с симметричными ключами и системы шифрования с открытыми ключами.

В конце 1970-х гг. использование ключа длиной в 56 бит гарантировало, что для раскрытия шифра потребуется несколько лет непрерывной работы самых мощных по тем временам компьютеров. Прогресс в области вычислительной техники позволил значительно сократить время определения ключа путем полного перебора. При затратах в 300 млн. долл. 56-битные ключи могут быть найдены за 12 с. Расчеты показывают, что в настоящее время для надежного закрытия информации длина ключа должна быть не менее 90 бит.

К методам шифрования с симметричными ключами относятся:

· методы замены;

· методы перестановки;

· аналитические методы;

· аддитивные методы (гаммирование);

· комбинированные методы.

К системам шифрования с открытыми ключами относятся:

· системаRSA (Rivest, Shamir and Aldeman – изобретателиалгоритма);

· система Эль-Гамаля;

· криптосистема Мак-Элиса.

Математически процесс шифрования сообщения М с помощью алгоритма шифрования Е выглядит так:

С=Е к1 (М), где

С – полученное в результате шифрования сообщение;

к1 – ключ шифрования.

Обычно алгоритмы шифрования не являются секретными. Например, современный российский алгоритм шифрования ГОСТ 28147-89 опубликован как стандарт.

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

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

Формула для расшифрования

М=D к2 (С), где

D – алгоритм расшифрования, которым ваш адресат обрабатывает сообщение с целью получить посланное ему сообщение М;

к2 – ключ для расшифрования.

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

Алгоритмы шифрования делятся на два вида:

1. Симметричные ;

2. Асимметричные .

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

Рис. 2.1.

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

Если М – сообщение, К – ключ , а Е – зашифрованное сообщение, то можно записать

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

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

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

В методах перестановки символы исходного текста меняются местами друг с другом по определенному правилу. В методах замены (или подстановки) символы открытого текста заменяются некоторыми эквивалентами шифрованного текста. С целью повышения надежности шифрования текст, зашифрованный с помощью одного метода, может быть еще раз зашифрован с помощью другого метода. В этом случае получается комбинированный или композиционный шифр . Применяемые на практике в настоящее время блочные или поточные симметричные шифры также относятся к комбинированным, так как в них используется несколько операций для зашифрования сообщения. "Принципы построения блочных шифров с закрытым ключом" , "Алгоритмы шифрования DES и AES" , "Алгоритм криптографического преобразования данных ГОСТ 28147-89" , а в этой лекции рассматриваются шифры подстановки и перестановки, применяемые человеком с древнейших времен. Мы должны познакомиться с этими шифрами, так как процедуры подстановки и перестановки используются в качестве составных операций и в современных блочных шифрах.

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

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

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

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

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

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

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

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы: для таблицы 3×3 - 36 вариантов, для таблицы 4×4 - 576 вариантов, для таблицы 5×5 - 14400 вариантов. Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

Шифры простой замены. При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита по одному правилу на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.

Система шифрования Цезаря . Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке.

При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту m от исходной буквы на k букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал латинский алфавит m = 26 и шифр замены при смещении k = 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифротекста. Совокупность возможных подстановок для k = 3 показана в таблице 6.1.

Таблица 6.1 - Одноалфавитные подстановки (k = 3, m = 26)

Система шифрования Цезаря образует, по существу, семейство одноалфавитных подстановок для выбираемых значений ключа k , причем 0 £ k < m . Достоинством системы шифрования Цезаря является простота шифрования и расшифрования.

К недостаткам системы Цезаря можно отнести следующее:

Подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;

Сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения k изменяются только начальные позиции такой последовательности;

Число возможных ключей k мало;

Шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифротексте.

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

Аффинная система подстановок Цезаря. В данном преобразовании буква, соответствующая числу t , заменяeтся на букву, соответствующую числовому значению (at + b ) по модулю m . Такое преобразование является взаимно однозначным отображением на алфавите тогда и только тогда, когда НОД (a , m ) - наибольший общий делитель чисел a и m равен единице, т. e. если a и m - взаимно простые числа.

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

Шифры сложной замены . Шифры сложной замены называют многоалфавитными, так как для шифрования каждого символа исходного сообщения применяют свой шифр простой замены. Многоалфавитная подстановка последовательно и циклически меняет используемые алфавиты. При r -алфавитной подстановке символ x 0 исходного сообщения заменяется символом y 0 из алфавита B 0 , символ x 1 - символом y 1 из алфавита B 1 , и т. д.; символ x r -1 заменяется символом y r -1 из алфавита B r -1 , символ x r заменяется символом y r снова из алфавита B 0 , и т. д.

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

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

Она имеет два входа:

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

Крайний левый столбец ключа.

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

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

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

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

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

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

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

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

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

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

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

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