|
| |||
Реферат: Современные криптографические методыМинистерство образования Российской Федерации САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра прикладной математики и информатики К У Р С О В А Я Р А Б О Т А Современные криптографические методы Студент IV-ИЭ-8 Альперт В. В. Научный руководитель Пономарев В. П. С а м а р а 2000 С О Д Е Р Ж А Н И Е Стр. Введение в криптографию 3 Симметричные криптосистемы 5 Стандарт шифрования данных ГОСТ 28147-89 6 Международный алгоритм шифрования данных IDEA 10 Алгоритм RSA 12 Оценка надежности криптосистем 14 ЗАКЛЮЧЕНИЕ 19 ЛИТЕРАТУРА 20 Введение в криптографию Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Начиная с послевоенного времени и по нынешний день, появление вычислительных средств ускорило разработку и совершенствование криптографических методов. Проблема использования криптографических методов в информационных системах стала в настоящий момент особо актуальна потому, что с одной стороны, расширилось использование компьютерных сетей, в частности глобальной сети Интернет, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц. С другой стороны, появление новых мощных компьютеров, технологий сетевых и нейронных вычислений сделало возможным дискредитацию криптографических систем еще недавно считавшихся практически не раскрываемыми. Проблемой защиты информации путем ее преобразования занимается криптология (kryptos - тайный, logos - наука). Криптология разделяется на два направления - криптографию и криптоанализ. Цели этих направлений прямо противоположны. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей. Шифрование - преобразовательный процесс: исходный текст, который носит также название открытого текста, заменяется шифрованным текстом. Дешифрование - обратный шифрованию процесс. На основе ключа шифрованный текст преобразуется в исходный. Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов. Криптосистемы разделяются на симметричные и системы с открытым ключом. В системах с открытым ключом используются два ключа - открытый и закрытый, которые математически связаны друг с другом. Информация шифруется с помощью открытого ключа, который доступен всем желающим, а расшифровывается с помощью закрытого ключа, известного только получателю сообщения. Электронной (цифровой) подписью называется присоединяемое к тексту его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность сообщения. Криптостойкостью называется характеристика шифра, определяющая его стойкость к дешифрованию без знания ключа (т.е. криптоанализу). Имеется несколько показателей криптостойкости, среди которых: количество всех возможных ключей; среднее время, необходимое для криптоанализа. Криптография в прошлом использовалась лишь в военных целях. Однако сейчас, с становлением информационного общества, она становится центральным инструментом для обеспечения конфиденциальности. По мере образования информационного общества, крупным государствам становятся доступны технологические средства тотального надзора за миллионами людей. Поэтому криптография становится одним из основных инструментов обеспечивающих конфиденциальность, доверие, авторизацию, электронные платежи, корпоративную безопасность и бесчисленное множество других важных вещей. Симметричные криптосистемы Все многообразие существующих криптографических методов можно свести к следующим классам преобразований: Моно- и полиалфавитные подстановки. Наиболее простой вид преобразований, заключающийся в замене символов исходного текста на другие (того же алфавита) по более или менее сложному правилу. Для обеспечения высокой криптостойкости требуется использование больших ключей. Перестановки. Также несложный метод криптографического преобразования. Используется, как правило, в сочетании с другими методами. Гаммирование. Этот метод заключается в наложении на исходный текст некоторой псевдослучайной последовательности, генерируемой на основе ключа. Блочные шифры. Представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем “чистые” преобразования того или иного класса в силу их более высокой криптостойкости. Российский и американский стандарты шифрования основаны именно на этом классе шифров. Стандарт шифрования данных ГОСТ 28147-89 Российский стандарт шифрования является блочным, т. е. преобразование
ведется по блокам. Он включает в себя режим замены и два режима
гаммирования. Стандарт ГОСТ 28147-89 формировался с учетом мирового опыта,
и в частности, были приняты во внимание недостатки и нереализованные
возможности алгоритма DES, поэтому использование стандарта ГОСТ
предпочтительнее. Эффективность данного стандарта достаточно высока. Введем ассоциативную операцию конкатенации. Если L и R –
последовательность бит, то LR обозначает конкатенацию последовательностей,
то есть LR - последовательность бит с размерностью равной сумме
размерностей L и R, причем биты R следуют за битами L. Кроме того, будем
использовать следующие операции сложения: На следующем шаге в качестве p1, p2, p3, p4 используют d11, d13, d12, d14 и новые шесть подключей. Полученные четыре последние 16 битных блока и есть зашифрованный текст. Процесс дешифрования осуществляется аналогично. Шифрование и дешифрование отличаются только подключами. Первые восемь подключей определяются с помощью 128 битного ключа, который разделяется на восемь частей. Новые восемь подключей определяются следующим образом: начальный ключ смещается на 25 бит, и разделяется на восемь частей. Подключи для дешифрования определяются таблицей: 1 шаг s49* s50# s51# s52* s47 s48 2 шаг s43* s45# s44# s46* s41 s42 3 шаг s37* s39# s38# s39* s35 s36 4 шаг s31* s33# s32# s34* s29 s30 5 шаг s25* s27# s26# s28* s23 s24 6 шаг s19* s21# s20# s22* s17 s18 7 шаг s13* s15# s14# s16* s11 s12 8 шаг s7* s9# s8# s10* s5 s6 Последнее преобразование s1* s2# s3# s4* sXX* = мультипликативная инверсия sXX по модулю 216+1 sXX# = аддитивная инверсия sXX по модулю 216 Алгоритм RSA Как бы ни были сложны и надежны криптографические системы - их слабое место при практической реализации - проблема распределения ключей. Для того чтобы был возможен обмен конфиденциальной информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из них, а затем, в конфиденциальном порядке, передан другому. Т.е. в общем случае для передачи ключа опять же требуется использование какой-то криптосистемы. Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом. Суть их состоит в том, что каждым адресатом ИС генерируются два ключа, связанные между собой по определенному правилу. Один ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому, кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне. Исходный текст шифруется открытым ключом адресата и передается ему. Асимметричные криптографические системы используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для вычисления значения x. Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем. Алгоритмы криптосистем с открытым ключом можно использовать в 3 назначениях. 1. Как самостоятельные средства защиты передаваемых и хранимых данных. 2. Как средства для распределения ключей. 3. Средства аутентификации пользователей. Алгоритмы криптосистем с открытым ключом более трудоемки, чем традиционные криптосистемы, поэтому использование их в качестве самостоятельных средств защиты нерационально. Поэтому на практике рационально с помощью криптосистем с открытым ключом распределять ключи, объем которых как информации незначителен. А потом с помощью обычных алгоритмов осуществлять обмен большими информационными потоками. Несмотря на довольно большое число различных криптосистем с открытым ключом, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Ривеста, Шамира и Эйдельмана. Ривест, Шамир и Эйдельман воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время. Пусть n=p*q, где p и q - различные простые числа, и e и d удовлетворяют уравнению e*d (mod (p-1)*(q-1))= 1 Если p и q - достаточно большие простые числа, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA. {e,n} образует открытый ключ, а {d,n} - закрытый (можно взять и наоборот). Открытый ключ публикуется и доступен каждому, кто желает послать
владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. Шифрование осуществляется по формуле: Sшифр = Se mod N Шифрование осуществляется по формуле: S = Sdшифр mod N Где S – исходный текст, Sшифр – преобразованный текст, при этом S < N Оценка надежности криптосистем Группа известных специалистов-криптографов, созданная под эгидой Проблема поиска ключей симметричной криптосистемы путем перебора всех
возможных ключей относится к классу задач, допускающих распараллеливание. 2) увеличения количества таких устройств в системе. C физической точки зрения тот тип транзистора, который является
основой современной интегральной схемы, может быть уменьшен еще примерно в Других способов повышения вычислительной мощности нет. Таким образом, с точки зрения защиты информации криптографическими методами, анализ потенциальных возможностей метода распределенных вычислений представляет как для криптоаналитиков, так и для разработчиков криптографических систем значительный интерес. Попробуем, поэтому, проанализировать предельные значения двух указанных тенденций. Из списка, появившегося летом 1999 года, следует, что по быстродействию суперкомпьютеры распределились следующим образом: с мощностью порядка 1012 FLOPS 3 экз.; с мощностью порядка 1011 FLOPS 54 экз.; с мощностью порядка 1010 FLOPS 428 экз.; с мощностью порядка 109 FLOPS 251 экз. Десять самых мощных суперкомпьютеров в мире по состоянию на июль 1999 г. Первое место в мире по количеству суперкомпьютеров занимают США 254 Количество установок суперкомпьютеров возрастает год от года в
геометрической прогрессии, причем основной объем опять же приходится на 1999 786 установок 1998 638 установок 1997 207 установок 1996 168 установок 1995 52 установки 1994 45 установок 1993 16 установок 1992 10 установок Допустим, что рассматриваемые нами алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей данного алгоритма. Очевидно, что в этом случае стойкость криптосистем будет определяться длиной ключа. При проведении данного исследования предполагалось, что криптоаналитик противной стороны обладает всей информацией относительно алгоритма шифрования, за исключением данных о секретном ключе, и ему доступен для анализа шифрованный текст сообщения. По определению предполагается, что идеальный алгоритм лишен каких-либо недостатков, снижающих его криптостойкость. Для шифров ГОСТ-28147-89 и IDEA существенных недостатков в настоящее время не выявленно. Предположим также, что генерация ключа компьютером происходит за один такт его работы, а операция дешифрования мгновенно. Определив отношение количества ключей к быстродействию самого мощного компьютера, мы получим нижнюю оценку сложности дешифрования сообщения для идеального алгоритма. Время, необходимое в настоящий момент самым мощным суперкомпьютерам
для полного перебора ключей Таким образом с помощью указанной рабочей модели можно оценивать
надежность проектируемых и эксплуатируемых систем шифрования. Алгоритм ГОСТ Оценки трудоемкости разложения простых чисел (1994 год) Оценки трудоемкости разложения простых чисел (2000 год) В конце 1995 года удалось практически реализовать раскрытие шифра RSA
для 500-значного ключа. Для этого с помощью сети Интернет было
задействовано 1600 компьютеров. Сами авторы RSA рекомендуют использовать
следующие размеры модуля N: Таким образом метод RSA в ближайшее время перестанет использоваться и будет заменен более надежными криптосистемами. Предположим, что размер процессора равен размеру атома. Тогда в наших
обозначениях быстродействие гипотетического процессора выразится формулой Этому процессору понадобится 1.15*Е51 лет для перебора 256 битного
ключа. Более быстрый процессор в нашей вселенной невозможен в принципе,
поэтому более быстро производить дешифрование методом тотального перебора
ключей принципиально невозможно. Таким образом, прогноз будущего силовой
атаки на основе распределенных вычислений неутешителен. Cиловая атака на
криптосистемы бесперспективна. Однако, недостатки алгоритмов могут
существенно сократить число вариантов перебора. Использование в качестве
ключей осмысленных слов позволяет применять атаку по словарю. ЗАКЛЮЧЕНИЕ Хотелось бы отметить, что шифрование и дешифрование востребованы в
обществе не сами по себе, а лишь потому, что они могут принести прибыль или
позволяют избежать убытков, поэтому всегда необходимо знать какова же
стоимость одного знака шифрованной и дешифрованной информации и во что это
обходится? Являются ли рентабельными те организации, занимающиеся
перехватом и дешифровкой информации, или они заведомо убыточны? Наиболее
интересен сравнительный анализ данных с целью научного обоснования доли
затрат на защиту информации. При этом также необходимо учитывать, что
значительное число атак осуществляется изнутри сотрудниками учреждений, от
которых защитится гораздо сложнее. В частности, проблема хранения ключей
является в настоящее время наиболее острой и, если использование открытых
ключей позволяет решить проблему распределения ключей и аутентификации
пользователей, то более эффективного способа хранения ключей, чем
запоминание, не найдено, а использование запоминающихся паролей позволяет
применить атаку по словарю. Кроме того, использование надежных
криптографических методов не гарантирует защиты от программных атак. ЛИТЕРАТУРА
----------------------- Криптографическая система исходный текст шифрованный текст КЛЮЧ шифрованный текст исходный текст Криптографическая система КЛЮЧ Гаммирование Подстановки Симметричные криптосистемы Блочные шифры Перестановки Адресат Отправитель Система с открытым ключом Система с открытым ключом Шифрованный текст исходный текст исходный текст Открытый ключ Закрытый ключ |
|