Основные способы современного шифрования. Типы алгоритмов шифрования

09.07.2003

Что такое шифрование?

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

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

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

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

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

• Алгоритмы замены или подстановки - символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.
• Алгоритмы перестановки - символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.
• Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов "имя пользователя.pwl", в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUp-доступа в Интернет и т.д.).

Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

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

Симметричные и асимметричные криптосистемы

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

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

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

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

Алгоритм RSA

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

Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, Unix-программа ssh-keygen по умолчанию генерирует ключи длиной 1024 бита).

Определим параметр n как результат перемножения p и q . Выберем большое случайное число и назовем его d , причем оно должно быть взаимно простым с результатом умножения (p -1)*(q -1) .

Отыщем такое число e, для которого верно соотношение

(e*d) mod ((p -1)*(q -1)) = 1

(mod - остаток от деления, т. е. если e, умноженное на d, поделить на ((p -1)*(q -1)) , то в остатке получим 1).

Открытым ключом является пара чисел e и n , а закрытым - d и n .

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

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

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

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

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

Давайте попробуем на маленьких числах.

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

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

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Криптотекст - 1 11 12 16 17.

Проверим расшифровкой:

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

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

Криптосистема RSA широко применяется в Интернете. Когда вы подсоединяетесь к защищенному серверу по протоколу SSL, устанавливаете на свой ПК сертификат WebMoney либо подключаетесь к удаленному серверу с помощью Open SSH или SecureShell, то все эти программы применяют шифрование открытым ключом с использованием идей алгоритма RSA. Действительно ли эта система так надежна?

Конкурсы по взлому RSA

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

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

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

Один из самых распространенных в России почтовых клиентов, программа The Bat!, обладает встроенными возможностями добавлять цифровые подписи к письмам (обратите внимание на пункт меню Privacy при редактировании письма). Подробнее об этой методике читайте в статье (см. «Мир ПК», № 3/02).

Рис. 3

Криптография

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

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

Олег Бунин - специалист по разработке ПО для крупных Интернет-проектов, сотрудник компании «Рамблер», [email protected] .

Литература

1. Лукашов И. В. Криптография? Железно! // Мир ПК. 2003. № 3 (
2. Носов В. А. Краткий исторический очерк развития криптографии // Материалы конференции "Московский университет и развитие криптографии в России", МГУ, 17-18 октября 2002 г.
3. Саломаа А. Криптография с открытым ключом. М., 1996 .
4. Циммерман Ф. PGP - кодирование с открытым ключом для всех.

Система шифрования Цезаря

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

РЛЗЬ ЁМЭЙЗ АВБЖУ ИЙЗАВЛУ, БЖЩЛУ ЖЩЭЗЬЖЗ ЖЮЁЩЕЗ, ЭЫЩ ЫЩАЖФО ИЙЩЫВЕЩ БЩИЗЁЖВ ЭЕШ ЖЩРЩЕЩ: ЛФ ЕМРСЮ ЪЗЕЗЭЩГ, РЮЁ РЛЗ ИЗИЩЕЗ ЮКЛУ, В ЕМРСЮ ЬМЭУ ЗЭВЖ, РЮЁ ЫЁЮКЛЮ К ДЮЁ ИЗИЩЕЗ.

Успели? Привожу «отгадку»:

Чтоб мудро жизнь прожить, знать надобно немало,

Два важных правила запомни для начала:

Ты лучше голодай, чем что попало есть,

И лучше будь один, чем вместе с кем попало.

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

Windows и пароли

Как Windows шифрует пароли?

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

Конкурс AES (Advanced Encryption Standard)

В 80-х гг. в США приняли стандарт симметричного шифрования для внутреннего применения - DES ((Data Encryption Standard, подобный стандарт есть и в России). Но в 1997 г., когда стало понятно, что 56-битового ключа DES недостаточно для надежной криптосистемы, Американский институт стандартизации объявил конкурс на новый стандартный алгоритм. Из 15 вариантов был выбран лучший: бельгийский алгоритм Rijndael (его название составлено из фамилий авторов - Rijmen и Daemen, читается как «Рэйндал». Этот алгоритм уже встроен в различные криптографические средства, поставляемые на рынок). Другими финалистами конкурса стали MARS, RC6, Serpent, TwoFish. Все эти алгоритмы были признаны достаточно стойкими и успешно противостоящими всем широко известным методам криптоанализа.

Криптографические хэш-функции

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

• два разных набора данных с одинаковым результатом преобразования (стойкость к коллизиям); например, количество арифметических операций, необходимых для того, чтобы найти блок данных, также имеющий краткое сообщение для хэш-функции MD5, составляет приблизительно 2 64;
• входное значение по известному результату хэширования (необратимость); для MD5 предполагаемое количество операций, необходимых для вычисления исходного сообщения, равно 2 128.

Занимательное шифрование

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

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

Что собой представляет система шифрования данных?

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

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

Зачем это нужно?

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

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

На ум приходит только одна фраза, ставшая классикой принципов деятельности Натана Ротшильда: «Кто владеет информацией, тот владеет миром». И именно поэтому информацию приходится защищать от посторонних глаз, дабы ей не воспользовался кто-то еще в своих корыстных целях.

Криптография: точка отсчета

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

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

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

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

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

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

Симметричные и асимметричные алгоритмы шифрования: в чем разница

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

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

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

Наиболее известные и часто применяемые алгоритмы шифрования

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

В большинстве стран стандартом де-факто является криптографическая система AES на основе 128-битного ключа. Однако параллельно с ней иногда используется и алгоритм который хоть и относится к шифрованию с использованием открытого (публичного) ключа, тем не менее является одним из самых надежных. Это, кстати, доказано всеми ведущими специалистами, поскольку сама система определяется не только степенью шифрования данных, но и сохранением целостности информации. Что касается ранних разработок, к коим относится алгоритм шифрования DES, то он безнадежно устарел, а попытки его замены начали проводиться еще в 1997 году. Вот тогда-то на его основе и возник новый расширенный (Advanced) стандарт (сначала с ключом 128 бит, потом - с ключом 256 бит).

Шифрование RSA

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

Для шифрования берутся два достаточно больших числа X и Y, после чего вычисляется их произведение Z, называемое модулем. Далее выбирается некое постороннее число A, удовлетворяющее условию: 1< A < (X - 1) * (Y - 1). Оно обязательно должно быть простым, то есть не иметь общих делителей с произведением (X - 1) * (Y - 1), равным Z. Затем происходит вычисление числа B, но только так, что (A * B - 1) делится на (X - 1) * (Y - 1). В данном примере A - открытый показатель, B - секретный показатель, (Z; A) - открытый ключ, (Z; B) - секретный ключ.

Что происходит при пересылке? Отправитель создает зашифрованный текст, обозначенный как F, с начальным сообщением M, после чего следует A и умножение на модуль Z: F = M**A*(mod Z). Получателю остается вычислить несложный пример: M = F**B*(mod Z). Грубо говоря, все эти действия сводятся исключительно к возведению в степень. По тому же принципу работает и вариант с создание цифровой подписи, но уравнения тут несколько сложнее. Чтобы не забивать пользователю голову алгеброй, такой материал приводиться не будет.

Что же касается взлома, то алгоритм шифрования RSA ставит перед злоумышленником практически нерешаемую задачу: вычислить ключ B. Это теоретически можно было бы сделать с применением доступных средств факторинга (разложением на сомножители исходных чисел X и Y), однако на сегодняшний день таких средств нет, поэтому сама задача становится не то что трудной - она вообще невыполнима.

Шифрование DES

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

Суть его симметричного шифрования заключается в том, что для этого применяется некая последовательность из 48 бит. При этом для операций используется 16 циклов из выборки ключей в 48 бит. Но! Все циклы по принципу действия аналогичны, поэтому на данный момент вычислить искомый ключ труда не составляет. К примеру, один из самых мощных компьютеров в США стоимостью более миллиона долларов «ломает» шифрование в течение примерно трех с половиной часов. Для машин рангом ниже на то, чтобы вычислить даже последовательность в максимальном ее проявлении, требуется не более 20 часов.

Шифрование AES

Наконец, перед нами самая распространенная и, как считалось до недавнего времени, неуязвимая система - алгоритм шифрования AES. Он сегодня представлен в трех модификациях - AES128, AES192 и AES256. Первый вариант применяется больше для обеспечения информационной безопасности мобильных устройств, второй задействован на более высоком уровне. Как стандарт, эта система была официально внедрена в 2002 году, причем сразу же ее поддержка была заявлена со стороны корпорации Intel, производящей процессорные чипы.

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

Проблемы с вирусами и дешифровкой

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

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

А если исходить из заявления правительства США о сроке, отводимом для дешифрования ключа длиной 128 бит, то что можно сказать о времени, которое потребуется на поиск решения для случая с ключом и его вариантами длиной 1024 бита? Вот тут-то США и прокололись. Они ведь считали, что их система компьютерной криптографии совершенна. Увы, нашлись какие-то спецы (судя по всему, на постсоветском пространстве), которые превзошли «незыблемые» американские постулаты по всем параметрам.

При всем этом даже ведущие разработчики антивирусного ПО, в том числе «Лаборатория Касперского», специалисты, создавшие «Доктора Веба», корпорация ESET и многие другие мировые лидеры просто разводят руками, дескать, на расшифровку такого алгоритма попросту нет средств, умалчивая при этом о том, что и времени не хватит. Конечно, при обращении в службу поддержки предлагается отправить зашифрованный файл и, если есть, желательно его оригинал - в том виде, в каком он был до начала шифрования. Увы, даже сравнительный анализ пока не дал ощутимых результатов.

Мир, которого мы не знаем

Да что там говорить, если мы гонимся за будущим, не имея возможности расшифровать прошлое. Если посмотреть на мир нашего тысячелетия, можно заметить, что тот же римский император Гай Юлий Цезарь в некоторых своих посланиях использовал симметричные алгоритмы шифрования. Ну а если взглянуть на Леонардо да Винчи, так вообще становится как-то не по себе от одного осознания того, что в области криптографии этот человек, чья жизнь покрыта неким флером тайны, на века превзошел свою современность.

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

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

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

Вместо послесловия

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

Тут главное - понять и вникнуть, так сказать, в суть вопроса. Ну а если говорить о том, что представляют собой современные системы, предлагающие хранить конфиденциальную информацию таким образом, чтобы она была доступна ограниченному кругу пользователей, здесь выбор невелик. Несмотря на наличие множества криптографических систем, те же алгоритмы RSA и DES явно проигрывают специфике AES. Впрочем, и большинство современных приложений, разработанных для совершенно разнящихся между собой операционных систем, используют именно AES (естественно, в зависимости от области применения и устройства). Но вот «несанкционированная» эволюция этой криптосистемы, мягко говоря, многих, особенно ее создателей, повергла в шок. Но в целом, исходя из того, что имеется на сегодняшний день, многим пользователям нетрудно будет понять, что такое криптографические системы шифрования данных, зачем они нужны и как работают.

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

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

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

Алгоритмы гаммирования - символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов «имя пользователя.рwl», в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUр-доступа в Интернет и т.д.). Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

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

Комбинированные методы. Последовательное шифрование исходного текста с помощью двух и более методов.

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

Рассмотрим подробнее методы криптографической защиты данных

1. Алгоритмы замены(подстановки)

2. Алгоритм перестановки

3. Алгоритм гаммирования

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

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

Алгоритмы 1-4 в «чистом виде» использовались раньше, а в наши дни они заложены практически в любой, даже самой сложной программе шифрования. Каждый из рассмотренных методов реализует собственный способ криптографической защиты информации и имеет собственные достоинства и недостатки, но их общей важнейшей характеристикой является стойкость. Под этим понимается минимальный объем зашифрованного текста, статистическим анализом которого можно вскрыть исходный текст. Таким образом, по стойкости шифра можно определить предельно допустимый объем информации, зашифрованной при использовании одного ключа. При выборе криптографического алгоритма для использования в конкретной разработке его стойкость является одним из определяющих факторов.

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

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

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

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

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

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

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

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

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

Заключение

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

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

· невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры,

· совершенство используемых протоколов защиты,

· минимальный объем используемой ключевой информации,

· минимальная сложность реализации (в количестве машинных операций), ее стоимость,

· высокая оперативность.

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

Практическая часть:

Задание 1.

1) Заполняем поле X выполнив

1.1 Задаем вручную первое значение

1.2 Выполняем Правка->Заполнить->

2) Заполняем поле значений функции g =

Рис.1.1 – Формула функции g(x)

2.1) Просчитываем значения функций

3) Построение графиков

3.1) Выделяем ячейки с значениями Функций g

3.2) Выбираем мастер диаграмм

Рис.1.2 – Мастер диаграмм - График

Рис.1.3 – Мастер диаграмм – подпись осей

Выделяем значение оси X

Нажимаем Ввод (enter)

3.3) Даем имена графикам

3.4) Выделяем ячейку с формулой графика

3.6) Выбираем закладку ->Линии сетки, выставляем

X промежуточные линии, Y Основные линии ->Далее

3.7) Помещаем график функции на имеющемся листе -> (Готово)

4) В итоге получаем (Рис.1.4)

Рис.1.4 – График функции g(x)

1.2.

1) Определяем в полях таблицы функции будущих графиков

Рис.1.5 – Подпись функций будущих графиков

2) Заполняем поле X выполнив:

2.1 Задаем вручную первое значение

2.2 Выполняем Правка->Заполнить->Прогрессия (по столбцам, арифметическая, шаг, предельное значение) при х [-2;2]

3) Просчитываем значения функций y=2sin( x) – 3cos( x), z = cos²(2 x) – 2sin( x).

Рис.1.6 – Формулы функций y(x) и z(x)

4) Построение графиков

4.1Выделяем ячейки с значениями Функций y и z

Выбираем мастер диаграмм

Рис.1.7 - Мастер диаграмм - График

Выделяем значение оси X

Нажимаем Ввод (enter)

4.2) Даем имена графикам

4.3) Выделяем ячейку с формулой графика

Нажимаем ввод (enter) , потом тоже самое проделываем со вторым рядом

4.5) Выбираем закладку ->Линии сетки, выставляем

X промежуточные линии, Y Основные линии ->Далее

4.6) Помещаем график функции на имеющемся листе -> (Готово)

5) В итоге получаем (Рис.1.8)

Рис.1.8 – Графики функций y(x) и z(x)

Задание 2.

· Создание списка «Отдела кадров»

Рис.2.1 Список «Отдела кадров»

· Сортировка

Рис.2.2 – Сортировка по полю Имя

В итоге получаем (Рис.2.3)

Рис.2.3 – Отсортированная таблица «Отдел кадров»

·
Поиск информации с помощью автофильтра (получить информацию о мужчинах, имя которых начинается на букву Буква, отчество – «Иванович», с окладом Оклад );

Рис.2.4 - Автофильтр

· Поиск информации с помощью расширенного фильтра (найти информацию из отдела Отдел1 в возрасте Возраст1 и Возраст2 , и о женщинах из отдела Отдел2 в возрасте Возраст3 );

1) Вводим критерии для расширенного фильтра 1

В итоге получаем (Рис.2.5)

Рис.2.5 – Расширенный фильтр 1

2) Вводим критерии для расширенного фильтра 2.

В итоге получаем(Рис.2.6)

Рис.2.6 – Расширенный фильтр 2

· Подведение итогов (определить количество и средний возраст сотрудников в каждом отделе);

Рис.2.7 - Итоги

Функция ДМИН- Возвращает наименьшее число в поле (столбце) записей списка или базы данных, которое удовлетворяет заданным условиям.

Рис.2.8 – Анализ списка с помощью функции ДМИН

Задание 3.

Создаём две связанные таблицы Сессия (рис.3.2) и Студенты (рис.3.4)

Рис.3.1- Конструктор таблицы Сессия

Рис.3.2- Таблица Сессия

Рис.3.3 – Конструктор таблицы Студенты

Рис.3.4 – Таблица Студенты

1) Используя таблицу Студенты, создать три запроса, по которым из базы данных будут поочередно отобраны фамилии и имена студентов групп 1-Э-1, 1-Э-2, 1-Э-3.

Рис.3.5– Конструктор Запроса 1.1

Рис.3.7– Конструктор Запроса1.2

Рис.3.9– Конструктор Запроса 1.3

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

Рис.3.11– Конструктор Запроса 2.1

Рис.3.13 – Конструктор Запроса 2.2

3)Использую таблицу Студенты, создать два запроса, по которым из базы данных будут поочередно отобраны фамилии и имена женщин группы 1-Э-2, а затем-мужчин группы 1-Э-1.

Рис.3.15– Конструктор Запроса 3.1

Рис.3.17– Конструктор – 3.2

4) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток и оценки по математике студентов группы 1-Э-2.

Рис.3.19– Конструктор Запроса 5

5) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток и оценки по философии студентов (мужчин) группы 1-Э-2.

Рис.3.21– Конструктор Запроса 8

6) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «удовлетворительно» (3) по философии.

Рис.3.23– Конструктор Запроса 10

7) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «хорошо» (4) одновременно по двум предмета: философии и математике.

Рис.3.25– Конструктор Запроса 14

8) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «неудовлетворительно» (2) по одному из двух предметов: по математике или информатике.

Рис.3.27– Конструктор Запроса 18

9) Используя связанные таблицы Студенты и Сессия, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «хорошо» (4) по всем предметам.

Рис.3.29– Конструктор Запроса 22

10) Используя таблицу Сессия, создать запрос с именем Средний балл для расчёта среднего балла каждого студента по результатам сдачи четырёх экзаменов. Запрос обязательно должен содержать поле Зачётка , которое впоследствии будет использовано для связывания нескольких таблиц.

Рис.3.31 – Конструктор таблицы Сессия

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

Рис.3.33 – Конструктор Запроса 25

12) Используя связанные таблицы Студенты , Сессия и запрос Средний балл , создать запрос, по которому из базы данных будут отобраны оценка по математике, средний балл и номер группы студента Иванова.

Рис.3.35– Конструктор Запроса 29

13) Используя связанные таблицы Студенты , Сессия и запрос Средний балл , создать запрос, по которому из базы данных будут отобраны фамилии, имена студентов имеющих средний балл менее 3,75.

Рис.3.37– Конструктор Запроса 33

14) Используя таблицу Студенты , определить фамилию, имя и номер зачетки студентки, если известно, что её отчество Викторовна.

Рис.3.39– Конструктор Запроса 35

Задание 4.

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

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

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

в) Ответ записывают в виде сложения переведенной целой и переведенной дробной части числа.

49812,22₁₀ = 1100001010010100,001₂ 49812,22₁₀ = 141224,160₈

49812,22₁₀ = С294, 385₁₆

Задание 5.

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

А) 10101001,11001₂ = 1*2^7+1*2^5+1*2^3+1*2^0+1*2^(-1)+1*2^(-2)+1*2(-5)= 169,78125₁₀

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

Таблица 5.1 – Перевод чисел

Б) 674,7₈ = 110111100,111₂=1*2^2+1*2^3+1*2^4+1*2^5+1*2^7+1*2^8+1*2^(-1) +1*2^(-2) +1*2^(-3)= 443,875₁₀

110 111 100. 111₂

В) EDF,51₁₆ = 111011011111,01010001₂=1*2^0+1*2^1+1*2^2+1*2^3+1*2^4+1*2^6+ +1*2^7+1*2^9+ +1*2^10+1*2^11+1*2^(-2) 1*2^(-4) 1*2^(-8)= 3807,31640625₁₀

1110 1101 1111 . 0101 0001₂

Задание 6.

В основе сложения чисел в двоичной системе лежит таблица сложения одноразрядных двоичных чисел.

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10
Сложение многоразрядных двоичных чисел осуществляется в соответствии с этой таблицей с учетом возможных переносов из младшего разряда в старшие. В восьмеричной системе счисления, как и в любой другой позиционной, действуют собственные правила сложения чисел, представляющиеся правилами сложения цифр с равными порядками, относящихся к двум складываемым числам. Эти правила видны из табл.6.1. Появляющийся при сложении некоторых цифр данного разряда перенос, показан символом "↶". Таблица 6.1 - Сложение в 8–ой системе счисления
+
								↶0
							↶0	↶1
						↶0	↶1	↶2
					↶0	↶1	↶2	↶3
				↶0	↶1	↶2	↶3	↶4
			↶0	↶1	↶2	↶3	↶4	↶5
		↶0	↶1	↶2	↶3	↶4	↶5	↶6

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

6 8 5 , 3 2 2 A ₁₆ + 1 0 1 0 1 0 0 1 0 , 1 0 ₂ + 4 7 7 , 6₈

D A 4 8 5 , 4 4 6 0 ₁₆ 1 1 0 0 0 0 1 1 0 , 1 1 0 1 0₂6 5 1 , 5 6₈

D A B 0 A , 7 6 8 A₁₆ 1 0 1 1 0 1 1 0 0 1 , 0 1 0 1 0₂ 1 3 5 1 ,3 6₈

Таблица 6.2 - Сложение в 16-ой системе счисления

Задание 7.

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

а) _ 2 5 1 5 1 4 , 4 0₈

5 4 2 5 , 5 5 ₈

2 4 3 0 6 6 , 6 3₈

б) _1 0 1 1 0 1 1 0 0 0 , 1 0 0 0 0₂

1 0 1 0 0 1 0 0 1 , 1 0 0 1 1 ₂

1 0 1 1 0 0 1 0 0 1 1 , 0 0 0 0 1₂

в) _E 3 1 6 , 2 5 0₁₆

5 8 8 1 , F D C₁₆

8 А 9 4 , 2 7 4

Задание 8.

В основе умножения чисел в двоичной системе лежит таблица умножения одноразрядных двоичных чисел.

0 · 0 = 0
0 · 1 = 0
1 · 0 = 0
1 · 1 = 1

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

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

Табл. 8.1. – Умножение в 8-ой системе

а) 1 0 1 0 0 1₂

* 1 1 1 0 1 1 ₂

1 0 1 0 0 1 .

1 0 0 1 0 1 1 1 0 0 1 1₂

б) 1 0 1 1 1 0 0₂

* 1 1 0 1 1 ₂

1 0 1 1 1 0 0 .

1 0 0 1 1 0 1 1 0 1 0 0₂

в) B C D , 5₁₆

* D5A ₁₆

9 D 9 3 3 E 2₁₆

Табл.8.2 – Умножение в 16-ой системе

Задание 9.

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

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

Дополнительный код (англ. two’s complement , иногда twos-complement ) - наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. При записи числа для положительного числа совпадает с прямым кодом, а для отрицательного числа дополнительный код обуславливается получением обратного кода и добавлением 1.

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

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

Прямой код:

X=0,10111 1,11110

Y=1,11110 0,10111

Обратный код:

X=0,10111 0,10111

Y=1,00001 1,00001

1,11000 1,00111

Дополнительный код:

X=0,10111 0,10111

Y=1,00010 1,00010

1,11001 1,00110

Прямой код:

Обратный код:

X=0,110110 0,0110110

Y=0,101110 0,0101110

Дополнительный код:

X=0,110110 0,0110110

Y=0,101110 0,0101110

Задание 10.

Логические элементы

1. Логический элемент НЕ выполняет логическое отрицание. Он имеет один вход и один выход. Отсутствие сигнала (напряжения) обозначим через «0», а наличие сигнала через «1». Сигнал на выходе всегда противоположен входному сигналу. Это видно из таблицы истинности, которая показывает зависимость выходного сигнала от входного.

2. Логический элемент ИЛИ выполняет логическое сложение. Он имеет несколько входов и один выход. Сигнал на выходе будет, если есть сигнал хотя бы на одном входе.

Условное обозначение Таблица истинности

3. Логический элемент И выполняет логическое умножение. Сигнал на выходе этого логического элемента будет только в том случае, если есть сигнал на всех входах.

Условное обозначение Таблица истинности

F=(A v B) ʌ (C v D)

Таблица 10.1 – Таблица истинности

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

1. Закон двойного отрицания: (А) = А

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

2. Переместительный (коммутативный) закон:

Для логического сложения: A V B = B V A

Для логического умножения: A&B = B&A

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

3. Сочетательный (ассоциативный) закон:

Для логического сложения: (A v B) v C = A v (Bv C);

Для логического умножения: (A&B)&C = A&(B&C).

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

4. Распределительный (дистрибутивный) закон:

Для логического сложения: (A v B)&C = (A&C)v(B&C);

Для логического умножения: (A&B) v C = (A v C)&(B v C).

Определяет правило выноса общего высказывания за скобку.

5. Закон общей инверсии (законы де Моргана):

Для логического сложения: (Av B) = A & B;

Для логического умножения: (A& B) = A v B;

6. Закон идемпотентности

Для логического сложения: A v A = A;

Для логического умножения: A&A = A.

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

Для логического сложения: A v 1 = 1, A v 0 = A;

Для логического умножения: A&1 = A, A&0 = 0.

8. Закон противоречия: A& A = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего: A v A = 1.

10. Закон поглощения:

Для логического сложения: A v (A&B) = A;

Для логического умножения: A&(A v B) = A.

11. Закон исключения (склеивания):

Для логического сложения: (A&B) v (A &B) = B;

Для логического умножения: (A v B)&(A v B) = B.

12. Закон контрапозиции (правило перевертывания):

(A v B) = (Bv A).

(А→В) = А&В

А&(АvВ)= А&В

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

Похожая информация.

Алгоритм шифрования данных DES (Data Encryption Standard) был опубликован в 1977 г. и остается пока распространенным блочным симметричным алгоритмом, используемым в системах защиты коммерческой информации.

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

Процесс шифрования заключается в начальной перестановке битов 64-битового блока, 16 циклах (раундах) шифрования и, наконец, в конечной перестановке битов (рис. 6.2).

Рис. 6.2.

Расшифровывание в DES является операцией, обратной шифрованию, и выполняется путем повторения операций шифрования в обратной последовательности.

Основные достоинства алгоритма DES:

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

Современная микропроцессорная техника позволяет за достаточно приемлемое время взламывать симметричные блочные шифры с длиной ключа 40 бит. Для такого взламывания используется метод полного перебора - тотального опробования всех возможных значений ключа (метод «грубой силы»). До недавнего времени DES считался относительно безопасным алгоритмом шифрования.

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

Алгоритм 3-DES (Triple DES - тройной DES) используется в ситуациях, когда надежность алгоритма DES считается недостаточной.

Сегодня все шире используются два современных криптостойких алгоритма шифрования: отечественный стандарт шифрования ГОСТ 28147-89 и новый криптостандарт США - AES (Advanced Encryption Standard).

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

Данные, подлежащие зашифрованию, разбивают на 64-раз-рядные блоки. Эти блоки разбиваются на два субблока N x и N 2 по 32 бит (рис. 6.3). Субблок /V, обрабатывается определенным образом, после чего его значение складывается со значением субблока N 2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - «исключающее или»), а затем

Рис. 6.3.

субблоки меняются местами. Данное преобразование выполняется определенное число раз («раундов») - 16 или 32, в зависимости от режима работы алгоритма.

В каждом раунде выполняются две операции.

Первая операция - наложение ключа. Содержимое субблока /V, складывается по модулю 2 32 с 32-битовой частью ключа К х. Полный ключ шифрования представляется в виде конкатенации 32-битовых подключей: К 0 , К { , К 2 , К 3 , К 4 , К 5 , К 6 , К 7 . В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.

Вторая операция - табличная замена. После наложения ключа субблок N { разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.

Табличные замены. Блок подстановки 5-box (Substitution box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция.

Блок подстановки 5-Ьох состоит из восьми узлов замены (5-блоков замены) 5, S 2 , ..., 5 8 с памятью 64 бит каждый. Поступающий на блок подстановки S 32-битовый вектор разбивают на 8 последовательно идущих 4-битовых векторов, каждый из которых преобразуется в 4-битовый вектор соответствующим узлом замены. Каждый узел замены можно представить в виде таблицы-перестановки 16 4-битовых двоичных чисел в диапазоне 0000... 1111. Входной вектор указывает адрес строки в таблице, а число в этой строке является выходным вектором. Затем 4-битовые выходные векторы последовательно объединяют в 32-би-товый вектор. Узлы замены (таблицы-перестановки) представляют собой ключевые элементы, которые являются общими для сети ЭВМ и редко изменяются. Эти узлы замены должны сохраняться в секрете.

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

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

К 0 , К { , К 2 , К 3 , К 4 , К 5 , К 6 , К 7 , К 0 , /Г, и т. д. - в раундах с 1-го по 24-й;

К 7 , К ь, К 5 , К 4 , К 3 , К 2 , К х, К 0 - в раундах с 25-го по 32-й.

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

К 0 , АГ, К 2 , К 3 , К 4 , К 5 , К ь, К 7 - в раундах с 1-го по 8-й;

К 7 , К 6 , К 5 , К 4 , К 3 , К 2 , К { , К 0 , К 7 , К ь и т. д. - в раундах с 9-го по 32-й.

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

В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N 1 и Ы 2 (рис. 6.9):

• 1. В регистры N^ и 1У 2 записывается их начальное заполнение - 64-битовая величина, называемая синхропосылкой.
• 2. Выполняется зашифровывание содержимого регистров N 1 и М 2 (в данном случае - синхропосылки) в режиме простой замены.
• 3. Содержимое регистра N^ складывается по модулю (2 32 - 1) с константой С, = 2 24 + 2 16 + 2 8 + 2 4 , а результат сложения записывается в регистр N 1 .
• 4. Содержимое регистра УУ 2 складывается по модулю 232 с константой С 2 = 2 24 + 2 16 + 2 8 + 1, а результат сложения записывается в регистр УУ 2 .
• 5. Содержимое регистров N , и Ы 2 подается на выход в качестве 64-битового блока гаммы шифра (в данном случае N^ и УУ 2 образуют первый блок гаммы).

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

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

Таблица 6.1. Зашифровывание и расшифровывание в режиме гаммирования

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

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

В режиме гаммирования с обратной связью для заполнения регистров Л", и ІУ 2 , начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифрования предыдущего блока открытого текста (рис. 6.4). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.

Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с исполь-

Рис. 6.4.

зованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-битовый блок массива информации, для которого вычисляется имитоприставка, записывается в регистры ^ и А^ 2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в Л", и Ы 2 .

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-битовое содержимое регистров Л^, и А^ 2 или его часть и называется имитопри-ставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки г бит вероятность, что изменение сообщения останется незамеченным, равна 2~ г.

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

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

Алгоритм ГОСТ 28147-89 является очень стойким алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).

Стандарт шифрования AES. В 1997 г. Американский институт стандартизации NIST (National Institute of Standards & Technology) объявил конкурс на новый стандарт симметричного криптоалгоритма, названного AES (Advanced Encryption Standard). К его разработке были подключены самые крупные центры криптологии всего мира. Победитель этого соревнования фактически становился мировым криптостандартом на ближайшие 10-20 лет.

К криптоалгоритмам - кандидатам на новый стандарт AES - были предъявлены следующие требования:

• алгоритм должен быть симметричным;
• алгоритм должен быть блочным шифром;
• алгоритм должен иметь длину блока 128 бит и поддерживать три длины ключа: 128, 192 и 256 бит.

Дополнительно разработчикам криптоалгоритмов рекомендовалось:

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

Итоги конкурса были подведены в октябре 2000 г. - победителем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen). Алгоритм Rijndael стал новым стандартом шифрования данных AES .

Алгоритм AES не похож на большинство известных алгоритмов симметричного шифрования, структура которых носит название «сеть Фейстеля» и аналогична российскому ГОСТ 28147-89. В отличие от отечественного стандарта шифрования, алгоритм AES представляет каждый блок обрабатываемых данных в виде двухмерного байтового массива размером 4x4, 4x6 или 4 х 8 в зависимости от установленной длины блока (допускается использование нескольких фиксированных размеров шифруемого блока информации). Далее на соответствующих этапах производятся преобразования либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами.

Алгоритм AES состоит из определенного количества раундов (от 10 до 14 - это зависит от размера блока и длины ключа) и выполняет четыре преобразования:

BS (ByteSub) - табличная замена каждого байта массива (рис. 6.5);

SR (ShiftRow) - сдвиг строк массива (рис. 6.6). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4x4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта;

МС (MixColumn) - операция над независимыми столбцами массива (рис. 6.7), когда каждый столбец по определенному правилу умножается на фиксированную матрицу с(х);

АК (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который в свою очередь определенным образом вычисляется из ключа шифрования (рис. 6.8).

Рис. 6.5.

для обработки каждого байта массива State

Рис. 6.6. Преобразование SR (ShiftRow) циклически сдвигает три последних

строки в массиве State

Рис. 6.8. Преобразование АК (AddRoundKey) производит сложение XOR каждого

столбца массива State со словом из ключевого набора

Эти преобразования воздействуют на массив State, который адресуется с помощью указателя "state". Преобразование AddRoundKey использует дополнительный указатель для адресации ключа раунда Round Key.

Преобразование BS (ByteSub) является нелинейной байтовой подстановкой, которая воздействует независимо на каждый байт массива State, используя таблицу замен (подстановок) iS-box.

В каждом раунде (с некоторыми исключениями) над шифруемыми данными поочередно выполняются перечисленные

преобразования (рис. 6.9). Исключения касаются первого и последнего раундов: перед первым раундом дополнительно выполняется операция А К, а в последнем раунде отсутствует МС.

Рис. 6.9.

В результате последовательность операций при зашифровы-вании выглядит так:

AK, {BS, SR, MC, АК} (повторяется R - 1 раз), BS, SR, АК.

Количество раундов шифрования R в алгоритме AES переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Расшифровывание выполняется с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровывании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для МС - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию с(х) d{x ) = 1. Добавление ключа АК является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.

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

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

Недостатком алгоритма AES можно считать лишь его нетрадиционную схему. Дело в том, что свойства алгоритмов, основанных на «сети Фейстеля», хорошо исследованы, a AES, в отличие от них, может содержать скрытые уязвимости, которые могут обнаружиться только по прошествии какого-то времени с момента начала его широкого распространения.

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

Основные режимы работы блочного симметричного

алгоритма

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

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

• электронная кодовая книга ЕС В (Electronic Code Book);
• сцепление блоков шифра СВС (Cipher Block Chaining);
• обратная связь по шифртексту CFB (Cipher Feed Back);
• обратная связь по выходу OFB (Output Feed Back).

Эти рабочие режимы первоначально были разработаны для блочного алгоритма DES, но в любом из этих режимов могут работать и другие блочные криптоалгоритмы.