Алгоритмические методы защиты информации
PAGE 19
Государственная Классическая Академия им. Маймонида
КУРСОВАЯ РАБОТА
на тему:
“Алгоритмические методы защиты информации”
выполнил студент
Руководитель:
Оценка:
Москва, 2003
Оглавление
- Введение 3
- Что такое криптография? 4
- Общие сведения по классической криптографии 4
- Стойкость алгоритмов шифрования 5
- Типы алгоритмов шифрования 7
- Принципы построения криптосистем с открытым ключом 9
- Системы криптографии с открытым ключом 9
- Применение криптосистем с открытым ключом 14
- Условия применения методов криптосистем с открытым ключом 14
- Криптоанализ схем информации с открытым ключом 15
- Алгоритм RSA: 16
- описание алгоритма 16
- вычисление ключей 17
- защищенность алгоритма RSA 18
- проблема разложения на множители 18
- вывод 19
- Литература 19
Введение
Основные понятия безопасности компьютерных систем.
В настоящее время благополучие и даже жизнь многих людей зависят от обеспечения информационной безопасности множества компьютерных систем обработки информации, а также контроля и управления различными объектами. К таким объектам можно отнести системы телекоммуникаций, банковские системы, атомные станции, системы управления воздушным и наземным транспортом, а также системы обработки и хранения секретной и конфиденциальной информации. Для нормального и безопасного функционирования этих систем необходимо поддерживать их безопасность и целостность. Под безопасностью информации понимается «состояние защищенности информации, обрабатываемой средствами вычислительной техники или автоматизированной системы от внутренних или внешних угроз». Целостность понимается как «способность средств вычислительной техники или автоматизированной системы обеспечивать неизменность информации в условиях случайного искажения или угрозы разрушения». Согласно этому же документу угрозы безопасности и целостности состоят в потенциально возможных воздействиях на вычислительную систему, которые прямо или косвенно могут нанести ущерб безопасности и целостности информации, обрабатываемой системой. Ущерб целостности информации состоит в её изменении, приводящем к нарушению её вида или качества. Ущерб безопасности подразумевает нарушение состояния защищенности содержащейся в вычислительной системе информации путем осуществления несанкционированного доступа к объектам вычислительной системы. НСД определяется как «доступ к информации, нарушающий правила разграничения доступа с использованием штатных средств, предоставляемых вычислительной системой».
НСД заключается в получении пользователем или программой доступа к объекту, разрешения на который в соответствии с принятой в системе политикой безопасности отсутствует. Реализация угрозы называется атакой. Человек, стремящийся реализовать угрозу, называется нарушителем, или злоумышленником.
Существуют различные способы защиты информации, в том числе алгоритмические.
Что такое криптография?
Криптография - наука о шифрах – долгое время была засекречена, так как применялась в основном, для защиты государственных и военных секретов. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц, организаций. Дело здесь не обязательно в секретах. Слишком много различных сведений «гуляет» по всему свету в цифровом виде. И над этими сведениями «висят» угрозы недружественного ознакомления, накопления, подмены, фальсификации и т. п. Наиболее надежные методы защиты от таких угроз дает именно криптография.
Пока криптографические алгоритмы для рядового потребителя – тайна за семью печатями, хотя многим уже приходилось пользоваться некоторыми криптографическими средствами: шифрование электронной почты, интеллектуальные банковские карточки и др. Естественно, что при этом основной вопрос для пользователя – обеспечивает ли данное криптографическое средство надежную защиту. Но даже правильно сформулировать этот элементарный вопрос непросто. От какого противника защищаемся? Какие возможности у этого противника? Какие цели он преследует? Этот список можно продолжить. Для ответа на них необходимы знания основных понятий криптографии.
Общие сведения по классической криптографии
Прежде чем перейти к рассмотрению криптографических алгоритмов необходимо уделить внимание основам построения систем засекреченной связи.
Под системой засекреченной связи будем понимать систему передачи информации, в которой смысл передаваемой информации скрывается с помощью криптографических преобразований. При этом сам факт передачи не утаивается. В основе каждой системы засекреченной связи – использование алгоритмов шифрования как основного средства конфиденциальности.
Зашифрование – процесс криптографического преобразования множества открытых сообщений во множество закрытых сообщений.
Расшифрование – процесс криптографического преобразования закрытых сообщений в открытые.
Дешифрование – процесс нахождения открытого сообщения, соответствующего заданному закрытому при неизвестном криптографическом преобразовании.
Множество открытых сообщений может быть представлено в виде битового потока, файла и т. д.
Систему засекреченной связи можно описать как множество отображений множества открытых сообщений в множество закрытых. Выбор конкретного преобразования определяется ключом зашифрования (расшифрования). Отображения должны обладать свойством взаимооднозначности, т. е. при расшифровании должен получаться единственный результат, совпадающий с первоначальным открытым сообщением.
Ключи зашифрования и расшифрования могут в общем случае быть различными, хотя для простоты рассуждений (применительно к этой главе) предположим, что они идентичны. Множество, из которого выбираются ключи, называется ключевым пространством. Совокупность процессов зашифрования, множества открытых сообщений, множества возможных закрытых сообщений и ключевого пространства называется алгоритмом зашифрования. Совокупность процессов расшифрования, множества возможных закрытых сообщений, множества открытых сообщений и ключевого пространства называется алгоритмом расшифрования.
Работу системы засекреченной связи можно описать следующим образом:
1.Из ключевого пространства выбирается ключ зашифрования К и отправляется по надежному каналу передачи.
2.К открытому сообщению С, предназначенному для передачи, применяют конкретное преобразование Fk, определяемое ключом К, для получения зашифрованного сообщения М-М=Fk(С).
3.Полученное зашифрованное сообщение М пересылают по каналу передачи данных.
4.На принимающей стороне к полученному сообщению М применяют конкретное преобразование Dk, определяемое из всех возможных преобразований ключом К, для получения открытого сообщения С:С=Dk(М).
Канал передачи данных, используемый для отправки зашифрованных сообщений, считается ненадежным, то есть любое зашифрованное сообщение может быть перехвачено противником (злоумышленником). Здесь мы предполагаем, что передаваемая информация сохраняет целостность, хотя на практике это не менее важная задача по сравнению с обеспечением конфиденциальности передаваемых сообщений. Наличие потенциального противника приводит к тому, что система засекреченной связи может быть скомпроментирована. На практике обеспечение надежности функционирования подобной системы сводится к стойкости используемых алгоритмов шифрования, однако может быть и гораздо ниже, хотя бы в силу технической реализации самой системы. Так, противник, анализируя побочные излучения от аппаратуры, на которой реализуются алгоритмы шифрования, в состоянии получить интересующий его ключ. Использование технических средств для обработки, передачи и хранения конфиденциальной информации порождает сложную научно-техническую задачу обеспечения ее защиты (под защитой мы будем подразумевать сохранение свойств информации, необходимых пользователям).
Стойкость алгоритмов шифрования
Для каждого открытого сообщения существует априорная вероятность выбора, поскольку механизм выбора открытых сообщений можно представить как некоторый вероятностный процесс. Аналогично выбор каждого ключа тоже имеет априорную вероятность. Противник осведомлен об используемой системе засекреченной связи. Предположим, что противнику известны все криптографические преобразования, используемые в системе засекреченной связи, а также ключевое пространство. В результате перехвата некоторого объема зашифрованных сообщений и вычисления апостериорных вероятностей противник поймет, что им будет соответствовать единственное решение об использовании ключа или передаче открытого сообщения (точка единственности принятия решения), удовлетворяющего данным вероятностям. Понятно, что подобный вывод вполне может привести к раскрытию системы противником. Под раскрытием системы засекреченной связи или алгоритма шифрования мы будем понимать одну из следующих планируемых противником операций, направленных на достижение этой цели:
Полное раскрытие. Противник находит путем вычислений секретный ключ системы.
Нахождение эквивалентного алгоритма. Противник находит алгоритм, функционально эквивалентный алгоритму зашифрования, не имея при этом представления об используемом секретном ключе.
Нахождение открытого сообщения. Противник находит открытое сообщение, соответствующее одному из перехваченных зашифрованных.
Частичное раскрытие. Противник получает частичную информацию об используемом ключе или об открытом сообщении.
Наука, занимающаяся вопросами раскрытия алгоритмов шифрования, называется криптоанализом. Под стойкостью алгоритма шифрования будем понимать способность противостоять всем возможным атакам против него. Стойким считается алгоритм, в котором перехват зашифрованных сообщений не приводит к появлению точки единственности принятия решения об используемом ключе или переданном открытом сообщении. На практике же получение противником требуемых для вскрытия алгоритма шифрования апостериорных вероятностей зависит от наличия у него определенных ресурсов, а именно:
Конкретный объем перехваченных зашифрованных сообщений.
Временные ресурсы. Здесь подразумевается время, необходимое для проведения определенных вычислений, в некоторых случаях временные затраты противника могут превышать время жизни секретной информации (табл. 1). Время жизни секретной информации можно определить как время, в течение которого информация должна сохранять свое свойство конфиденциальности.
Вычислительные ресурсы. Имеется в виду количество памяти в вычислительных системах, используемых для успешной реализации атаки.
Таблица 1. Время жизни некоторых типов информации
Тип информации время жизни информации
Военная тактическая информация минуты/ часы
Заявления о выпуске продукции дни/недели
Долгосрочные бизнес проекты годы
Производственные секреты десятилетия
Секрет создания водородной бомбы >40
Информация о разведчиках > 50 лет
Личная информация > 50 лет
Дипломатическая тайна > 65 лет
Информация о переписи населения 100 лет
Стойким считается алгоритм, который для своего вскрытия требует от противника практически недостижимых вычислительных ресурсов или недостижимого объема перехваченных зашифрованных сообщений или времени раскрытия, которое превышает время жизни интересующей противника информации.
Атака с выбором ключа. Противник знает не сами ключи, а некоторые различия между ними. С точки зрения криптоанализа последняя атака является самой сильной, хотя существует еще более сильная атака, заключающаяся в получении секретного ключа путем вымогательства, шантажа и подкупа.
Наибольшей стойкостью алгоритм обладает в том случае, когда он способен противостоять самой сильной атаке, проводимой противником, при условии, что он преследует самую слабую из возможных целей атаки (угроза).
Теоретически существует абсолютно стойкие алгоритмы шифрования. Математическое доказательство данного факта было предложено в работах Шеннона. Для того чтобы алгоритм считался абсолютно стойким, он должен удовлетворять следующим условиям:
Длина ключа и длина открытого сообщения должны быть одинаковы;
Ключ должен использоваться только один раз;
Выбор ключа из ключевого пространства должен осуществляться равновероятно.
Рассмотрим самые распространенные на сегодняшний день причина осуществления успешных атак на алгоритмы шифрования:
Наличие статистической структуры исторически сложившихся языков. То есть существуют определенные символы или комбинации символов, наиболее часто встречающиеся в естественной речи. Таким образом, при перехвате зашифрованного сообщения для некоторых типов алгоритмов шифрования можно подсчитать частоту появления определенных символов и сопоставить их с вероятностями появления определенных символов или их комбинаций (биграммы, триграммы и т.д.), что в некоторых случаях может привести к однозначному дешифрованию отдельных участков зашифрованного сообщения;
Наличие вероятных слов. Речь идет о словах или выражениях, появление которых можно ожидать в перехваченном сообщении. Так, в деловой переписке присутствуют шаблонные слова; в английском языке; например, наиболее часто встречаются and, the, are.
Следует учесть, что существует ряд методов, позволяющих сделать зашифрованные сообщения практически непригодными для статистического анализа и анализа посредством вероятных слов. К ним относятся:
Рассеивание. Влияние одного символа открытого сообщения распространяется на множество символов зашифрованного сообщения. Этот метод хотя и приводит к увеличению количества ошибок, однако с его помощью удается скрыть статистическую структуру открытого сообщения;
Запутывание. Развитием принципа рассеивания стал принцип запутывания, в котором влияние одного ключа распространяется на множество символов зашифрованного сообщения;
Перемешивание. Принцип перемешивания основывается на использовании особых преобразований исходного сообщения, в результате чего вероятные последовательности как бы рассеиваются по всему пространству возможных открытых сообщений. В качестве примера можно привести произведение двух простых не коммутирующих операций.
Типы алгоритмов шифрования
Было доказано, что в криптографии существуют только два основных типа преобразований - замены и перестановки. Таким образом, есть криптографические алгоритмы, построенные на основе замены, перестановки и объединения этих двух преобразований. В перестановочных шифрах символы открытого текста изменяют свое местоположение.
Рис.1. Общая схема перестановки
С другой стороны, в шифрах замены один символ открытого текста заменяется символом зашифрованного текста. В классической криптографии различают четыре типа шифров замены:
Шифры простой замены. Один символ открытого текста заменяется одним символом зашифрованного текста;
Шифры сложной замены. Один символ открытого текста заменяется одним или несколькими символами зашифрованного текста, например: А может быть заменен С или РО4Е;
Шифры блочной замены. Один блок символов открытого текста заменяется блоком закрытого текста, например: АВС может быть заменен СРТ или КАР;
Полиалфавитные шифры замены, в которых к открытому тексту применяются несколько шифров простой замены.
Классическая криптография, в частности теория связи в секретных системах, основанная К.Шенноном, исходила из того, что ключи 1 и 2 (рис.1), используемые соответственно для шифрования и расшифрования, являются секретными и одинаковыми, и передача их должна осуществляться по надежному каналу обмена ключевой информации. Подобные алгоритмы были названы симметричными, так как зашифрование и расшифрование происходит на одинаковых ключах. Однако развитие теории построения алгоритмов шифрования с открытым ключом, родоначальниками которой стали Диффи и Хеллман, положило начало повсеместному использованию асимметричных алгоритмов шифрования, в которых ключи зашифрования и расшифрования различны. В зависимости от применения один из ключей будет открытым, то есть общедоступным, а другой необходимо хранить в секрете.
Рис.2. Классификация алгоритмов шифрования
Спустя некоторое время симметричные алгоритмы были разделены на два больших класса – блочные и поточные. В первых открытый текст разбивается на блоки подходящей длины и фактически каждый блок шифруется, хотя существуют различные варианты применения алгоритмов блочного шифрования. В поточных алгоритмах каждый символ открытого текста зашифровывается независимо от других и расшифровывается таким же образом. Иначе говоря, преобразование каждого символа открытого текста меняется от одного символа к другому, в то время как для блочных алгоритмов в рамках шифрования блока используется одно и то же криптографическое преобразование. Главная идея, воплощенная в алгоритмах поточного шифрования, заключается в выработке на основе секретного ключа последовательности символов из входного алфавита, с которым работает алгоритм шифрования.
Принципы построения криптосистем с открытым ключом.
Идея применения методов криптографии с открытым ключом возникла из попыток найти решение двух из наиболее сложных проблем, возникающих при использовании традиционного шифрования. Первой проблемой является распределение ключей. Распределение ключей при традиционном шифровании требует, чтобы обе участвующие в обмене данными стороны либо (1) уже имели общий ключ, который каким-то образом был им доставлен, либо (2) использовали услуги некоторого центра распределения ключей. Уитфилд Диффи, один из открывателей метода шифрования с открытым ключом, считал, что второе из этих требований противоречит самой сущности криптографии-возможности обеспечить полную секретность вашей собственной корреспонденции. Как он заметил - ”Какой смысл имеет разработка неприступной криптосистемы, если ее пользователи должны использовать свои секретные ключи совместно с некоторым центром распределения ключей, который может быть скомпрометирован либо взломщиками, либо судебным решением?”
Второй проблемой, которую сформулировал Диффи и которая, очевидно, не связана с первой, является проблема “ цифровых подписей “. Если использование криптографии получило очень широкое распространение, и не только в области военного дела, но и в области коммерции и частных коммуникаций, то электронные сообщения и документы нуждаются в эквивалентах подписей, используемых в бумажных документах. Иными словами, можно ли разработать метод, с помощью которого обе стороны могли бы убедиться в том, что цифровое сообщение было отправлено данным конкретным лицом?
Диффи и Хеллман пришли к своему открытию в 1976 году, разработав метод, с помощью которого решались обе вышеупомянутые проблемы, и который радикально отличался от всех известных ранее подходов в криптографии за всю ее четырех тысячелетнюю историю. Диффи и Хеллман были первыми, кто публично изложил принципы криптографии с открытым ключом. Однако не это событие следует считать истинным началом истории криптографии с открытым ключом. Адмирал Бобби Инман, бывший в то время директором NSA (Агентство национальной безопасности США), заявил, что метод криптографии с открытым ключом был разработан NSA еще в середине 60-х. Первое документальное упоминание об этом методе появилось в 1970 году в секретном отчете Джеймса Эллиса из группы защиты электронных коммуникаций Службы безопасности Великобритании. Эллис относил данную технологию к несекретным методам шифрования и описал открытие в несекретном отчете.
Системы криптографии с открытым ключом.
Алгоритмы шифрования с открытым ключом зависят от ключа для шифрования и другого связанного с первым ключа для де шифрования. Эти алгоритмы имеют следующую важную особенность.
С точки зрения вычислений нереально определить ключ де шифрования, зная только используемый криптографический алгоритм и ключ шифрования.
Кроме того, некоторые алгоритмы (например, RSA) имеют следующее свойство.
Любой из этих двух связанных ключей может служить для шифрования, и тогда другой может применяться для де шифрования.
На рис.3. показана общая схема процесса шифрования с открытым ключом, которая выглядит следующим образом.
- Каждая конечная система в сети генерирует пару ключей для шифрования и де шифрования получаемых сообщений.
- Каждая из систем публикует свой ключ шифрования, размещая его ключ в открытом для всех реестре или файле. Этот и есть открытый ключ. Второй ключ, соответствующий открытому, остается в личном владении.
- Если пользователь А собирается послать сообщение пользователю В, он шифрует сообщение, используя открытый ключ пользователя В.
- Когда пользователь В получит сообщение, он дешифрует его с помощью своего личного ключа. Другой получатель не сможет дешифровать сообщение, поскольку личный ключ В знает только В.
В рамках этого подхода все участники имеют доступ к открытым ключам, а личные ключи генерируются на месте каждым участником для себя и поэтому их никогда не приходиться распределять. До тех пор пока системе удается сохранять свой личный ключ в секрете, поступающие сообщения оказываются зашифрованными. В любой момент система может изменить свой личный ключ и опубликовать соответствующий ему открытый ключ, заменяющий старый открытый ключ.
В табл.2. сравниваются некоторые важные характеристики традиционного шифрования и шифрования с открытым ключом. Чтобы различать эти два подхода, мы будем называть ключи, предназначенные для традиционного шифрования, секретными ключами. Два ключа, с помощью которых осуществляется шифрование с открытым ключом, будут называться, соответственно, открытым ключом и личным ключом. Личный ключ, конечно же, тоже должен храниться в секрете, но называется личным ключом, а не секретным ключом во избежание путаницы с ключом схемы традиционного шифрования.
Рис.3. Шифрование с открытым ключом.
а) Шифрование
Личный ключ Боба
Передаваемый
шифрованный
текст
Ввод открытого Алгоритм Алгоритм Вывод
текста шифрования дешифрования открытого текста
б) Аутентификация
Личный ключ Эллиса
Передаваемый
шифрованный текст
Ввод открытого текста Алгоритм шифрования Алгоритм дешифрования Вывод открытого
(например, RSA) (обращение алгоритма шифрования) текста
Таблица 2. Традиционное шифрование и шифрование с открытым ключом
|
Традиционное шифрование
|
Шифрование с открытым ключом
|
Необходимо для работы
|