Для начала выберем два очень больших простых числа (большие исходные числа нужны для построения больших криптостойких ключей. Например, 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)= 217 mod 21 =11
C(3)= 317 mod 21= 12
C(4)= 417 mod 21= 16
C(5)= 517 mod 21= 17
Криптотекст -- 11 12 16 17.
Проверим расшифровкой:
M(2)= 115 mod 21= 2
M(3)= 125 mod 21= 3
M(4)= 165 mod 21= 4
M(5)= 175 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-алгоритма равно 256>7*1016.
Алгоритм реализуется в течение 16 аналогичных циклов шифрования, где на I-ом цикле используется цикловой ключ Ki , представляющий собой алгоритмически вырабатываемую выборку 48 битов из 56 битов ключа Ki, I=1,2,…,16.
Алгоритм обеспечивает высокую стойкость, однако недавние результаты показали, что современная технология позволяет создать вычислительное устройство стоимостью около 1 млн. долларов США, способное вскрыть секретный ключ с помощью полного перебора в среднем за 3,5 часа.
Из-за небольшого размера ключа было принято решение использовать DES-алгоритм для закрытия коммерческой(несекретной) информации. Практическая реализация перебора всех ключей в данных условиях экономически не целесообразна, так как затраты на реализацию перебора не соответствуют ценности информации, закрываемой шифром.
DES-алгоритм явился первым примером широкого производства и внедрения технических средств в области защиты информации. Национальное бюро стандартов США проводит проверку аппаратных реализаций DES-алгоритма, предложенных фирмами-разработчиками, на специальном тестирующем стенде. Только после положительных результатов проверки производитель получает от Национального бюро стандартов сертификат на право реализации своего продукта. К настоящему времени аттестовано несколько десятков изделий, выполненных на различной элементарной базе.
Достигнута высокая скорость шифрования. Она составляет в лучших изделиях 45 Мбит/с. Цена некоторых аппаратных изделий ниже 100 долларов США.
Основные области применения DES-алгоритма:
1) хранение данных на компьютерах (шифрование файлов, паролей);
2) аутентификация сообщений (имея сообщение и контрольную группу, несложно убедиться в подлинности сообщения;
3) электронная система платежей (при операциях с широкой клиентурой и между банками);
4) Электронный обмен коммерческой информацией( обмен данными между покупателями, продавцом и банкиром защищен от изменений и перехвата.
Позднее появилась модификация DESa -- Triple Des («тройной DES» -- так как трижды шифрует информацию «обычным» DESом) свободен от основного недостатка прежнего варианта -- короткого ключа; он здесь в два раза длиннее. Но зато, как оказалось, Triple DES унаследовал другие слабые стороны своего предшественника: отсутствие возможности для параллельных вычислений при шифровании и низкую скорость.
3.5.2 ГОСТ 28147-89
В 1989 году в СССР был разработан блочный шифр для использования в качестве государственного стандарта шифрования данных. Разработка была принята и зарегистрирована как ГОСТ 28147-89. Алгоритм был введен в действие в 1990 году. И хотя масштабы применения этого алгоритма шифрования до сих пор уточняются, начало его внедрения, в частности в банковской системе , уже положено. Алгоритм несколько медлителен, но обладает весьма высокой стойкостью.
В общих чертах ГОСТ 28147 аналогичен DES. Блок-схема алгоритма ГОСТ отличается от блок-схемы DES-алгоритма лишь отсутствием начальной перестановки и число циклов шифрования (32 в ГОСТ против 16 в DES-алгоритме).
Ключ алгоритма ГОСТ -- это массив, состоящий из 32-мерных векторов X1, X2,…X8. Цикловой ключ i-го цикла Ki равен Xs, где ряду значений i от 1 до 32 соответствует следующий ряд значений s:
1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,7,6,5,4,3,2,1.
В шифре ГОСТ используется 256-битовый ключ и объем ключевого пространства составляет 2256. Ни на одной из существующих в настоящее время или предполагаемых к реализации в недалеком будущем компьютерной системе общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт проектировался с большим запасом, по стойкости он на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит о и объемом ключевого пространства всего 256( и неудивительно: его ключ длиной 32 байта (256 бит) вчетверо больше ключа DES. Необходимое же на перебор всех ключей время при этом возрастает не в четыре раза, а в 25632-8=25624, что выливается уже в астрономические цифры), чего явно недостаточно. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8
