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

Алгоритмы шифрования

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

• Симметричные алгоритмы
• Ассиметричные алгоритмы
• Алгоритмы хэш-функций

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

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

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

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

Где где М - открытый текст, К - секретный ключ, передаваемый по закрытому каналу, Еn(М) - операция зашифрования, а Dk(M) - операция расшифрования

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

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

Симметричные системы имеют как свои преимущества, так и недостатки перед асимметричными.

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

Примеры симметричных шифров

• ГОСТ 28147-89 - отечественный стандарт шифрования
• 3DES (Triple-DES, тройной DES)
• RC6 (Шифр Ривеста)
• Twofish
• SEED - корейский стандарт шифрования
• Camellia – японский стандарт шифрования
• CAST (по инициалам разработчиков Carlisle Adams и Stafford Tavares)
• XTEA - наиболее простой в реализации алгоритм
• AES – американский стандарт шифрования
• DES – стандарт шифрования данных в США до AES

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

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

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

Принцип работы асимметричных систем

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

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

Примеры асимметричных шрифтов

• RSA (Rivest-Shamir-Adleman, Ривест - Шамир - Адлеман)
• DSA (Digital Signature Algorithm)
• Elgamal (Шифросистема Эль-Гамаля)
• Diffie-Hellman (Обмен ключами Диффи - Хелмана)
• ECC (Elliptic Curve Cryptography, криптография эллиптической кривой)

Хеш-функции

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

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

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

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

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

Примеры хеш-алгоритмов

• Adler-32
• SHA-1
• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• HAVAL
• N-Hash
  • RIPEMD-160
• RIPEMD-256
• RIPEMD-320
• Skein
• Snefru
• Tiger (TTH)
• Whirlpool
• ГОСТ Р34.11-94 (ГОСТ 34.311-95)
• IP Internet Checksum (RFC 1071)

Криптографические примитивы

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

Квантовая криптография

Криптография в цифровых технологиях

История

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

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

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

Несколько позже ученые-историки определяют дату появления другой родственной науки – стеганография. Эта наука занимается маскировкой самого факта передачи сообщения. Зародилась она в античности, а примером здесь может служить получение спартанским царем Леонидом перед битвой с персами провощенной дощечки с текстом, покрытой сухим легкосмываемым раствором. При очистке оставленные на воске стилусом знаки становились отчетливо видимыми. Сегодня для сокрытия сообщения служат симпатические чернила, микроточки, микропленки и т.д.

С развитием математики стали появляться математические алгоритмы шифрования, но все эти виды криптографической защиты информации сохраняли в разной объемной степени статистические данные и оставались уязвимыми. Уязвимость стала особенно ощутима с изобретением частотного анализа, который был разработан в IX веке нашей эры предположительно арабским энциклопедистом ал-Кинди. И только в XV веке, после изобретения полиалфавитных шрифтов Леоном Баттистой Альберти (предположительно), защита перешла на качественно новый уровень. Однако в середине XVII века Чарлз Бэббидж представил убедительные доказательства частичной уязвимости полиалфавитных шрифтов перед частотным анализом.

Развитие механики позволило создавать приборы и механизмы, облегчающие шифрование – появились такие устройства, как квадратная доска Тритемиуса, дисковый шифр Томаса Джефферсона. Но все эти приборы ри в какое сравнение не идут с теми, были созданы в XX веке. Именно в это время стали появляться различные шифровальные машины и механизмы высокой сложности, например, роторные машины, самой известной из которых является «Энигма »

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

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

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

Литература

• Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. - М.: *Варфоломеев А. А., Жуков А. Е., Пудовкина М. А. Поточные криптосистемы. Основные свойства и методы анализа стойкости. М.: ПАИМС, 2000.
• Ященко В. В. Введение в криптографию. СПб.: Питер, 2001. .
• ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. М.: ГК СССР по стандартам, 1989.
• ГОСТ Р 34.10-94.Информационная технология. Криптографическая защита информации. *ГОСТ Р 34.11-94. Информационная технология. Криптографическая защита информации. Функция хэширования. М., 1995.
• ГОСТ Р 34.10-2001 Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. М., 2001.
• Нечаев В. И. Элементы криптографии (Основы теории защиты информации). М.: Высшая школа, 1999.
• Жельников В. Криптография от папируса до компьютера. М.: АВР,1996.

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

Первые шифры использовались еще во времена Древнего Рима, Древнего Египта и Древней Греции. Одним из известных шифров является шифр Цезаря . Данный алгоритм работал следующим образом: каждая буква имеет свой порядковый номер в алфавите, который сдвигался на $3$ значения влево. Сегодня подобный алгоритм не обеспечивает ту защиту, которую давал во времена его использования.

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

Разделяют алгоритмы шифрования на симметричные (к ним относятся AES, CAST, ГОСТ, DES, Blowfish) и асимметричные (RSA, El-Gamal).

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

Замечание 1

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

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

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

Замечание 2

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

Каждый пользователь должен обладать парой ключей – открытым и секретным ключом.

Ключ шифрования

Определение 1

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

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

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

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

Стойкость алгоритма шифрования

Замечание 3

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

Алгоритмы шифрования

Алгоритм AES (Rijndael) на данный момент является федеральным стандартом шифрования США. В качестве стандарта утвержден Министерством торговли в $2001$ г. Стандартом считается вариант шифра с размером блока $128$ бит. Разработан в $1997$ г. в Бельгии. Возможными размерами ключа являются ключи $128, 192$ и $256$ бит.

Алгоритм ГОСТ 28147-8 является стандартом Российской Федерации на шифрование и имитозащиту данных. Официальным стандартом стал в $1989$ г. Разработан в $1970$-х гг. в Главном Управлении КГБ СССР. Использует ключ размером $256$ бит.

Алгоритм Blowfish использует сложную схему создания ключей, что существенно затрудняет атаку на алгоритм методом перебора. Непригоден для использования в системах частого изменения ключа и при шифровании небольших по объему данных. Алгоритм лучше всего использовать для систем, в которых существует необходимость шифрования больших массивов данных. Разработан в $1993$ г. Используется размер ключа от $32$ до $448$ бит.

Алгоритм DES являлся Федеральным стандартом шифрования США в $1977-2001$ годах. Федеральным стандартом принят в $1977$ г. после введения в действие нового стандарта в $2001$ г. утратил статус стандарта. Разработан в $1972–1975$ гг. исследовательской лабораторией корпорации IBM. Использует ключ размером $56$ бит.

Алгоритм CAST является некоторым образом аналогом алгоритма DES. Использует ключи размером $128$ и $256$ бит.

Решение задачи определения ключа путем простого перебора всех возможных вариантов, как правило, является непрактичным, за исключением использования очень короткого ключа. Следовательно, если криптоаналитик хочет иметь реальные шансы на вскрытие шифра, он должен отказаться от «лобовых» методов перебора и применить другую стратегию. При раскрытии многих схем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов или их комбинаций. Для усложнения решения задачи вскрытия шифра с использованием статистического анализа К. Шеннон предложил две концепции шифрования, получившие название смешения (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 правильных символов шифрованного текста система восстанавливается. В то же время такое искажение можно объяснить попыткой злоумышленника навязать ложные данные.

Основные современные методы шифрования

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

• - Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
• - Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
• - Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности.
• - Алгоритмы, основанные на сложных математических преобразованиях исходного текста по некоторой формуле. Многие из них используют нерешенные математические задачи. Например, широко используемый в Интернете алгоритм шифрования RSA основан на свойствах простых чисел.
• - Комбинированные методы. Последовательное шифрование исходного текста с помощью двух и более методов.

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

Алгоритмы, основанные на сложных математических преобразованиях

Алгоритм RSA

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

Для начала необходимо выбрать два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита). Как результат перемножения р и q определяется параметр n. Затем выбирается случайное число е, причем оно должно быть взаимно простым с числом (n) = (р - 1)*(q - 1). Отыскивается такое число d, для которого верно соотношение

(e*d) mod (n) = 1.

Mod - остаток от деления, т. е. если e, умноженное на d, поделить (n), то в остатке должно получиться 1. Другими словами, числа (e*d - 1) и (n) должны делиться нацело.

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

C(i) = (M(i) e) mod n. (1)

В результате получается последовательность C(i), которая и составит криптотекст. Декодирование информации происходит по формуле

M(i) = (C(i) d) mod n. (2)

Как видно, расшифровка предполагает знание секретного ключа.

Рассмотрим пример на маленьких числах. Пусть р = 3, q = 7. Тогда n = = р*q = 21. Выберем е = 5. Из формулы (d*5) mod 12 = 1 вычисляем d = 17. Следовательно, открытый ключ 17, 21, секретный - 5, 21.

Зашифруем последовательность «2345»:

C 1 = 2 17 mod 21 = 11;

C 2 = 3 17 mod 21 = 12;

C 3 = 4 17 mod 21 = 16;

C 4 = 5 17 mod 21 = 17.

Криптотекст - 11 12 16 17. Проверим расшифровкой:

M 1 = 11 5 mod 21 = 2;

M 2 = 12 5 mod 21 = 3;

M 3 = 16 5 mod 21 = 4;

M 4 = 17 5 mod 21 = 5;

Как видно, результат совпал с изначальным открытым текстом.

Криптосистема RSA широко применяется в Интернете. Когда пользователи подсоединяются к защищенному серверу по протоколу SSL SSL (Secure Socket Layer), протокол защищенных сокетов - протокол, гарантирующий безопасную передачу данных по сети; комбинирует криптографическую систему с открытым ключом и блочное шифрование данных., устанавливает на свой ПК сертификат WebMoney либо подключается к удаленному серверу с помощью Oрen SSH или SecureShell, большинство даже не подозревает, что все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA.

Действительно ли эта система так надежна?

С момента своего создания RSA постоянно подвергалась атакам типа brute-force attack (атака методом грубой силы Brute force («грубая сила») - атака, осуществляемая простым перебором всех возможных либо наиболее часто встречающихся ключей (паролей). Во втором случае brute force достаточно часто называют "атакой по словарю".). В 1978 г. авторы алгоритма опубликовали статью, где привели строку, зашифрованную только что изобретенным ими методом. Первому, кто расшифрует сообщение, было назначено вознаграждение в размере 100 долларов, но для этого требовалось разложить на два сомножителя 129-значное число. Это был первый конкурс на взлом RSA. Задачу решили только через 17 лет после публикации статьи.

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

Компания RSA (httр://www.rsa.ru) регулярно проводит конкурсы на взлом собственных (и не только собственных) шифров. Предыдущие конкурсы выиграла организация Distributed.net (httр://www.distributed.net), являющаяся Интернет-сообществом добровольцев.

Участники Distributed.net загружают к себе на ПК небольшую программу-клиент, которая подсоединяется к центральному серверу и получает кусочек данных для вычислений. Затем все данные загружаются на центральный сервер, и клиент получает следующий блок исходной информации. И так происходит до тех пор, пока все комбинации не будут перебраны. Пользователи, участники системы, объединяются в команды, а на сайте ведется рейтинг как команд, так и стран. Например, участвующей в конкурсе по взлому RC5-64 (блочный шифр компании RSA, использующий ключ длиной 64 бита) организации Distributed.net удалось осуществить взлом через пять лет (1757 дней) работы. За это время в проекте участвовали 327 856 пользователей и было перебрано более 15,268*10 18 вариантов ключа. Выяснилось, что была (не без юмора) зашифрована фраза «some things are better left unread» («некоторые вещи лучше оставлять непрочтенными»). Общие рекомендации по шифру RC5-64 таковы: алгоритм достаточно стоек для повседневных нужд, но шифровать им данные, остающиеся секретными на протяжении более пяти лет, не рекомендуется».

Вероятностное шифрование

Одной из разновидностей криптосистем с открытым ключом является вероятностное шифрование, разработанное Шафи Гольвассером и Сильвио Минелли. Его суть состоит в том, чтобы алгоритм шифрования Е подчинить вероятностным моделям. В чем же преимущества такого подхода? Для примера, в системе RSA не «маскируются» 0 и 1. Эту проблему успешно решают вероятностные алгоритмы, поскольку они ставят в соответствие открытому тексту М не просто криптотекст С, а некоторый элемент из множества криптотекстов СМ. При этом каждый элемент этого множества выбирается с некоторой вероятностью. Другими словами, для любого открытого текста М результат работы алгоритма Е будет случайной величиной. Может показаться, что в этом случае дешифровать информацию будет невозможно, но это совсем не так. Для того чтобы сделать возможной дешифровку, нужно, чтобы для разных открытых текстов М 1 и М 2 множества СМ 1 и СМ 2 не пересекались. Также хочется сказать, что вероятностные алгоритмы шифрования являются более надежными, нежели детерминированные. В этой области наиболее распространены вероятностное шифрование на основе RSA-функций и криптосистема Эль-Гамала.

Комбинированные методы шифрования

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

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

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

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

подстановка + гаммирование;

перестановка + гаммирование;

гаммирование + гаммирование;

подстановка + перестановка;

Типичным примером комбинированного шифра является национальный стандарт США криптографического закрытия данных (DES).

Криптографический стандарт DES

В 1973 г. Национальное бюро стандартов США начало разработку программы по созданию стандарта шифрования данных на ЭВМ. Был объявлен конкурс среди фирм-разработчиков, который выиграла фирма IBM, представившая в 1974 году алгоритм шифрования, известный под названием DES (Data Encryption Standart).

В этом алгоритме входные 64-битовые векторы, называемые блоками открытого текста, преобразуются в выходные 64-битовые векторы, называемые блоками шифротекста, с помощью двоичного 56-битового ключа К. Число различных ключей DES-алгоритма равно 2 56 .

Алгоритм реализуется в течение 16 аналогичных циклов шифрования, где на i-ом цикле используется цикловой ключ K i , представляющий собой алгоритмически вырабатываемую выборку 48 из 56 битов ключа K i , i = 1,2,…,16.

Алгоритм обеспечивает высокую стойкость, однако недавние результаты показали, что современная технология позволяет создать вычислительное устройство стоимостью около 1 млн. долларов США, способное вскрыть секретный ключ с помощью полного перебора в среднем за 3,5 часа.

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

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

Достигнута высокая скорость шифрования. Она составляет в лучших изделиях 45 Мбит/с. Цена некоторых аппаратных изделий не превышает 100 долларов США.

Основные области применения DES-алгоритма:

хранение данных на компьютерах (шифрование файлов, паролей);

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

электронная система платежей (при операциях с широкой клиентурой и между банками);

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

Позднее появилась модификация DES - Triple DЕS («тройной DES» - так как трижды шифрует информацию «обычным» алгоритмом DES), свободная от основного недостатка прежнего варианта - короткого ключа; он здесь в два раза длиннее. Но, как оказалось, Triple DES унаследовал другие слабые стороны своего предшественника: отсутствие возможности для параллельных вычислений при шифровании и низкую скорость.

ГОСТ 28147-89

В 1989 году в СССР был разработан блочный шифр для использования в качестве государственного стандарта шифрования данных . Разработка была принята и зарегистрирована как ГОСТ 28147-89. Алгоритм был введен в действие в 1990 году. И хотя масштабы применения этого алгоритма шифрования до сих пор уточняются, начало его внедрения, в частности в банковской системе, уже положено. Алгоритм несколько медлителен, но обладает весьма высокой криптостойкостью.

В общих чертах ГОСТ 28147-89 аналогичен DES. Блок-схема алгоритма ГОСТ отличается от блок-схемыDES-алгоритма лишь отсутствием начальной перестановки и числом циклов шифрования (32 в ГОСТ против 16 в DES-алгоритме).

Ключ алгоритма ГОСТ - это массив, состоящий из 32-мерных векторов X 1 , X 2 ,…X 8 . Цикловой ключ i-го цикла K i равен Xs,где ряду значенийi от 1 до 32 соответствует следующий ряд значений s:

1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1.

В шифре ГОСТ используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одной из существующих в настоящее время или предполагаемых к реализации в недалеком будущемкомпьютерных систем общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт проектировался с большим запасом, по стойкости он на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 , чего явно недостаточно. Ключ криптоалгоритма ГОСТ длиной 32 байта (256 бит) вчетверо больше ключа DES. Необходимое же на перебор всех ключей время при этом возрастает не в четыре раза, а в 256 32-8 = 256 24 , что выливается уже в астрономические цифры). В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес.

Выводы об использовании современных алгоритмов шифрования

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

• - DES;
• - ГОСТ 28147-89 - отечественный метод, отличающийся высокой криптостойкостью;
• - RSA - система, в которой шифрование и расшифровка осуществляется с помощью разных ключей.

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

Таблица 1 Характеристики наиболее распространенных методов шифрования

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

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

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

Ключ – это конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования данных , обеспечивающее выбор только одного варианта из всех возможных для данного алгоритма. В симметричных криптоалгоритмах для зашифрования и расшифрования сообщения используется один и тот же блок информации (ключ). Хотя алгоритм воздействия на передаваемые данные может быть известен посторонним лицам, но он зависит от секретного ключа, которым должны обладать только отправитель и получатель. Симметричные криптоалгоритмы выполняют преобразование небольшого блока данных (1 бит либо 32-128 бит) в зависимости от секретного ключа таким образом, что прочесть исходное сообщение можно, только зная этот секретный ключ.

Симметричный алгоритм шифрования.

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

Для блочных шифров единицей шифрования является блок из нескольких байтов. Результат шифрования зависит от всех исходных байтов этого блока. Блочное шифрование применяется при пакетной передаче информации и кодировании файлов. Блочные шифры шифруют целые блоки информации (от 4 до 32 байт) как единое целое – это значительно увеличивает стойкость преобразований к атаке полным перебором и позволяет использовать различные математические и алгоритмические преобразования.

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

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

Функция

С = ЕК (М),
М = DK (C),
где М – исходный (открытый) блок данных;
С – зашифрованный блок данных.

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

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

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

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

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

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

Примечание

Рассеивание представляет собой распространение влияния одного знака открытого текста на много знаков шифротекста, что позволяет скрыть статистические свойства открытого текста…

Примечание

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

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

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

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

Все действия, производимые блочным криптоалгоритмом над данными, основаны на том факте, что преобразуемый блок может быть представлен в виде целого неотрицательного числа из диапазона, соответствующего его разрядности. Например, 32-битовый блок данных можно интерпретировать как число из диапазона 0 – 4294967295. Кроме того, блок, разрядность которого представляет собой «степень двойки», можно трактовать как сцепление нескольких независимых неотрицательных чисел из меньшего диапазона (указанный выше 32-битовый блок можно также представить в виде сцепления двух независимых 16-битовых чисел из диапазона 0 – 65535 или в виде сцепления четырех независимых 8-битовых чисел из диапазона 0 – 255).

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

1. Математические функции:
– сложение X’ = X + V;
– «исключающее ИЛИ» X’ = X xor V;
– умножение по модулю 2N + 1 X’ = (X*V) mod (2N + 1);
– умножение по модулю 2N X’ = (X*V) mod 2N.
2. Битовые сдвиги:
– арифметический сдвиг влево X’ = X shl V;
– арифметический сдвиг вправо X’ = X shr V;
– циклический сдвиг влево X’ = X rol V;
– циклический сдвиг вправо X’ = X ror V.
3. Табличные подстановки:
– S-box (англ. substitute) X’ = Table .

В качестве параметра V для любого из этих преобразований может использоваться:

• фиксированное число (например, X’ = X + 125).
• число, получаемое из ключа (например, X’ = X + F(K)).
• число, получаемое из независимой части блока (например, X2’ = X2 + F(X1)).

Примечание

Последний вариант используется в схеме, называемой сетью Фейстеля (по имени ее создателя)…

Сеть Фейстеля.

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

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

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

На основе сети Фейстеля построены американский стандарт шифрования данных DES и наш ГОСТ 28147-89.