Криптографические методы защиты информации

    

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

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

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

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

• во всех (кроме первой) строках таблицы буквы располагаются в произвольном порядке.
• В качестве ключа используется случайность последовательных чисел. Из таблицы Вижинера выбираются десять произвольных строк, которые кодируются натуральными числами от 0 до 10. Эти строки используются в соответствии с чередованием цифр в выбранном ключе.

   

 Известны также  и многие другие модификации  метода.

 

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

 

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

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

 

     ПУСТЬ БУДЕТ  ТАК, КАК МЫ ХОТЕЛИ.

 

получится такой шифротекст:

 

     ИЛЕТО ХЫМКА  ККАТТ ЕДУБЪ ТСУП

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

 

     ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

 

Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому:

 

      ОИЛЕТ  ОХЫМК АККАТ ТЕДУБ ЬТСУП

 

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

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

 

     П  У   С  Т  Ь  Б  У   Д  Е  Т  Т  А   К  К  А

     К  М   Ы Х  О  Т  Е  Л   И  К Л  М  Н О   П

 

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

 

    ПКУМС  ЫТХЬО   БТУЕД  ЛЕИТК  ТЛАМК  НКОАП

 

 

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

 

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

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

                    R_i = ( S_i + G ) mod (k –1),

 где R_i, S_i, G — символы соответственно зашифрованного, исходного текста и гаммы.

    Рис. 3.3.1 Пример шифрования гаммированием

 

При втором методе символы исходного текста и гаммы представляются в виде двоичного кода, затем соответствующие разряды складываются по модулю 2. Вместо

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

Шифруемый текст	Б	У	Д	Ь      …
	010010	100000	110010	100000
Знаки гаммы	7	1	8	2      …
	000111	000001	001000	000010
Шифрованный текст	010101	1000001	111010	100010

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

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

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

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

 

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

Алгоритм RSA

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

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

 

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

 

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

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

 

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

 

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

 

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

 

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

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

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

 

C(2)= 2¹⁷ mod 21 =11

C(3)= 3¹⁷ mod 21= 12

C(4)= 4¹⁷ mod 21= 16

C(5)= 5¹⁷ mod 21= 17

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

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

M(2)= 11⁵ mod 21= 2

M(3)= 12⁵ mod 21= 3

M(4)= 16⁵ mod 21= 4

M(5)= 17⁵ mod 21= 5

 

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

 

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

С момента своего создания RSA постоянно подвергалась атакам типа Brute-force attack (атака методом грубой силы, т. е. перебором). В 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 315 356 922 380 288 вариантов ключа. Выяснилось, что была (не без юмора) зашифрована фраза «some things are better left unread» («некоторые вещи лучше оставлять непрочтенными»). Общие рекомендации по шифру RC5-64 таковы: алгоритм достаточно стоек для повседневных нужд, но шифровать им данные, остающиеся секретными на протяжении более пяти лет, не рекомендуется».

 

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

 

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

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

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

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

1. подстановка + гаммирование;
2. перестановка + гаммирование;
3. гаммирование + гаммирование;
4. паодстановка + перестановка;

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

 

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

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

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

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

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

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