Размещено на http://www.allbest.ru/

Государственная Классическая Академия им. Маймонида

КУРСОВАЯ РАБОТА

на тему:

“Алгоритмические методы защиты информации”

выполнил студент

Руководитель:

Оценка:

Москва 2003

Оглавление

Введение

1. Что такое криптография?

2. Общие сведения по классической криптографии

3. Стойкость алгоритмов шифрования

4. Типы алгоритмов шифрования

5. Принципы построения криптосистем с открытым ключом

6. Системы криптографии с открытым ключом

7. Применение криптосистем с открытым ключом

8. Условия применения методов криптосистем с открытым ключом

9. Криптоанализ схем информации с открытым ключом

10. Алгоритм RSA

11. Описание алгоритма

12. Вычисление ключей

13. Защищенность алгоритма RSA

14. Проблема разложения на множители

Вывод

Литература

Введение

криптография алгоритм шифрование ключ

Основные понятия безопасности компьютерных систем.

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

НСД заключается в получении пользователем или программой доступа к объекту, разрешения на который в соответствии с принятой в системе политикой безопасности отсутствует. Реализация угрозы называется атакой. Человек, стремящийся реализовать угрозу, называется нарушителем, или злоумышленником.

Существуют различные способы защиты информации, в том числе алгоритмические.

1. Что такое криптография?

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

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

2. Общие сведения по классической криптографии

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

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

Зашифрование - процесс криптографического преобразования множества открытых сообщений во множество закрытых сообщений.

Расшифрование - процесс криптографического преобразования закрытых сообщений в открытые.

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

Множество открытых сообщений может быть представлено в виде битового потока, файла и т. д.

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

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

Работу системы засекреченной связи можно описать следующим образом:

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

2. К открытому сообщению С, предназначенному для передачи, применяют конкретное преобразование Fk, определяемое ключом К, для получения зашифрованного сообщения М-М=Fk(С).

3. Полученное зашифрованное сообщение М пересылают по каналу передачи данных.

4. На принимающей стороне к полученному сообщению М применяют конкретное преобразование Dk, определяемое из всех возможных преобразований ключом К, для получения открытого сообщения С:С=Dk(М).

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

3. Стойкость алгоритмов шифрования

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

Полное раскрытие. Противник находит путем вычислений секретный ключ системы.

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

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

Частичное раскрытие. Противник получает частичную информацию об используемом ключе или об открытом сообщении.

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

Конкретный объем перехваченных зашифрованных сообщений.

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

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

Таблица 1. Время жизни некоторых типов информации

Тип информации	время жизни информации
Военная тактическая информация	минуты/ часы
Заявления о выпуске продукции	дни/недели
Долгосрочные бизнес проекты	годы
Производственные секреты	десятилетия
Секрет создания водородной бомбы	>40
Информация о разведчиках	> 50 лет
Личная информация	> 50 лет
Дипломатическая тайна	> 65 лет
Информация о переписи населения	100 лет

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

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

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

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

Длина ключа и длина открытого сообщения должны быть одинаковы;

Ключ должен использоваться только один раз;

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

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

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

Наличие вероятных слов. Речь идет о словах или выражениях, появление которых можно ожидать в перехваченном сообщении. Так, в деловой переписке присутствуют шаблонные слова; в английском языке; например, наиболее часто встречаются and, the, are.

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

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

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

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

4. Типы алгоритмов шифрования

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

Размещено на http://www.allbest.ru/

Рис.1. Общая схема перестановки

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

Шифры простой замены. Один символ открытого текста заменяется одним символом зашифрованного текста;

Шифры сложной замены. Один символ открытого текста заменяется одним или несколькими символами зашифрованного текста, например: А может быть заменен С или РО4Е;

Шифры блочной замены. Один блок символов открытого текста заменяется блоком закрытого текста, например: АВС может быть заменен СРТ или КАР;

Полиалфавитные шифры замены, в которых к открытому тексту применяются несколько шифров простой замены.

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

Размещено на http://www.allbest.ru/

Рис.2. Классификация алгоритмов шифрования

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

5. Принципы построения криптосистем с открытым ключом

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

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

Диффи и Хеллман пришли к своему открытию в 1976 году, разработав метод, с помощью которого решались обе вышеупомянутые проблемы, и который радикально отличался от всех известных ранее подходов в криптографии за всю ее четырех тысячелетнюю историю. Диффи и Хеллман были первыми, кто публично изложил принципы криптографии с открытым ключом. Однако не это событие следует считать истинным началом истории криптографии с открытым ключом. Адмирал Бобби Инман, бывший в то время директором NSA (Агентство национальной безопасности США), заявил, что метод криптографии с открытым ключом был разработан NSA еще в середине 60-х. Первое документальное упоминание об этом методе появилось в 1970 году в секретном отчете Джеймса Эллиса из группы защиты электронных коммуникаций Службы безопасности Великобритании. Эллис относил данную технологию к несекретным методам шифрования и описал открытие в несекретном отчете.

6. Системы криптографии с открытым ключом

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

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

Кроме того, некоторые алгоритмы (например, RSA) имеют следующее свойство.

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

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

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

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

3. Если пользователь А собирается послать сообщение пользователю В, он шифрует сообщение, используя открытый ключ пользователя В.

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

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

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

а) Шифрование

Размещено на http://www.allbest.ru/

б) Аутентификация

Размещено на http://www.allbest.ru/

Рис.3. Шифрование с открытым ключом

Таблица 2. Традиционное шифрование и шифрование с открытым ключом

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

Давайте рассмотрим основные элементы схемы шифрования с открытым ключом более подробно. Итак, имеется некоторый источник сообщений А, создающий сообщение Х = (Х₁, Х₂ ,..Х_м) в виде открытого текста. Все М элементов Х являются буквами некоторого конечного алфавита. Сообщение адресовано получателю В. Адресат В генерирует связанную пару ключей: открытый ключ КU_b и личный ключ KR_b. Ключ KR_b остаётся известным только пользователю В, тогда как ключ KU_b публично доступен и, таким образом, оказывается доступным отправителю А.

Имея сообщение X и ключ шифрования KU_b в качестве входных данных, отправитель А формирует шифрованный текст Y = [Y₁, Y₂,…, Y_N] следующим образом:

Y = E_KUb(X) 1.

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

X = D_KRb (Y).

Противник, наблюдая Y и имея доступ к KU_b, но не к KR_b или X, должен будет пытаться восстановить X и/или KU_b. Предполагается, что противник знает алгоритмы шифрования (Е) и дешифрования (D). Если противника интересует только данное конкретное сообщение, то он сосредоточит свои усилия на восстановлении X с помощью получению оценок X для открытого текста. Но часто противник бывает заинтересован в возможности чтения и последующих сообщений. В таком случае, будет предпринята попытка восстановить ключ KR_b путём генерирования для него оценки KR_b.

Размещено на http://www.allbest.ru/

Рис. 4. Криптосистема с открытым ключом: защита

Мы уже упоминали выше, что любой из двух связанных ключей может применяться для шифрования, при этом предполагается, что другой будет служить для дешифрования. Это дает возможность реализовать различные криптографические схемы. И, если схема, показанная на рис.4, обеспечивает конфиденциальность, то рис.3б и рис.5 показывают, как использовать шифрование с открытым ключом для аутентификации:

Y = E (X)

X = D (Y).

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

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

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

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

Z = E_Kub[E_KRa(X)],

X = E_Kua[E_KRb(Z)].

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

Размещено на http://www.allbest.ru/

Рис.5 Криптосистема с открытым ключом: аутентификация

Размещено на http://www.allbest.ru/

Рис. 6 Криптосистема с открытым ключом: защита и аутентификация

7. Применение криптосистем с открытым ключом

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

В самых широких пределах использование криптосистем с открытым ключом можно отнести к трем категориям.

Шифрование/дешифрование. Отправитель шифрует сообщение с использованием открытого ключа получателя.

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

Обмен ключами. Две стороны взаимодействуют, чтобы обменяться сеансовым ключом.

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

Один алгоритм подходит для всех трех типов применения, тогда как другие предназначены только для одной или двух из этих категорий. Возможности применения алгоритмов RSA и Диффи-Хеллмана указаны в табл.3.

Таблица 3 Применение криптосистем с открытым ключом

Алгоритм	Шифрование/ дешифрование	Цифровая подпись	Обмен ключами
RSA	Да	Да	Да
Диффи - Хеллмана	Нет	Нет	Да

8. Условия применения методов криптографии с открытым ключом

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

1. Для стороны В процесс генерирования пары ключей (открытый ключ KU_b, личный ключ KR_b) не должны вызывать вычислительных трудностей.

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

С = E_Kub(M)

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

M = D_KRb(C) = D_KRb[E_Kub(M)].

4. Для противника должно быть практически невозможным с точки зрения вычислительных возможностей восстановление личного ключа KR_b из имеющегося открытого ключа KU_b.

5. Для противника должно быть невозможным с точки зрения вычислительных возможностей восстановление оригинального сообщения М из имеющихся открытого ключа KU_b и шифрованного текста С.

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

6. Функции шифрования и дешифрования могут применяться в любом порядке:

M = E_Kub[D_KRb(M)].

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

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

Y = f(X) вычисляется легко

X = f--¹(Y) практически не поддается вычислению

В общем случае термин “легко вычислимый” означает, что проблема решается за полиномиальное время, рассматриваемое как функция длины вводимого значения. Так, если длина вводимого значения равна n битов, то время, требуемое для вычисления функции пропорционально n^a, где а является фиксированной константой. Термин “практически невычислимый” означает, что усилия по ее вычислению возрастают быстрее, чем полиномиальная функция от длины вводимого значения. Например, если вводимое значение имеет длину n битов и время, требуемое для вычисления функции, пропорционально 2ⁿ, то такая функция считается практически невычислимой.

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

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

9. Криптоанализ схем шифрования с открытым ключом

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

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

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

10. Алгоритм RSA

Пионерская статья Диффи и Хеллмана знаменовала появление нового подхода в криптографии и на самом деле бросила вызов криптологам предложением найти криптографический алгоритм, который отвечал бы всем требованиям, выдвигаемым криптосистемам с общим ключом. Одними из первых на этот вызов ответили в 1977 году Рон Ривест, Ади Шамир и Лен Адлеман из МТИ, а соответствующая публикация появилась в 1978 году. Схема Ривеста-Шамира-Адлемана (RSA) стала с тех пор единственной получившей широкое признание и практически применяемой схемой шифрования с открытым ключом. Схема RSA представляет собой блочный шифр, в котором и открытый текст, и шифрованный текст представляются целыми числами из диапазона от 0 до n-1, для некоторого n.

11. Описание алгоритма

Схема, разработанная Ривестом, Шамиром и Адлеманом, основана на выражении со степенями. Открытый текст шифруется блоками, каждый из которых содержит двоичное значение, меньшее некоторого заданного числа n. Это означает, что длина блока должна быть меньше или равна log₂(n). Шифрование/дешифрование для блока открытого текста М и блока шифрованного текста С можно представить в виде следующих формул:

С=М^е mod n,

M=C^d mod n = (M^e)^d mod n = M^ed mod n.

Как отправитель, так и получатель должны знать значение n. Отправитель знает значение е, и только получателю известно значение d, таким образом, данная схема является алгоритмом шифрования с открытым ключом KU={e,n} и личным ключом KR={d,n}. Необходимые требования:

1) Должны существовать такие числа e, d, n, что M^ed = M mod n, для всех чисел M, взаимно простых с числом n. Заметим, что это ограничениет не позволяет зашифровать произвольный блок битов. Однако на практике такое ограничение легко преодолеть.

2) Должны относительно легко вычисляться M^e и C^d , для M<n.

3) Должно быть практически невозможно определить d по имеющимся e и n.

Рассмотрим первое требование: M^ed=M mod n. Отметим следующее

Следствие из теоремы Эйлера. Пусть p и q - два разных простых числа,

n = pq,

число M взаимно просто с числом n. Для любого целого числа k выполняются следующие соотношения:

M^kц(n)+1 = M mod n,

где ц(n) =(p-1)(q-1) - функция Эйлера.

Поэтому требуемое соотношение получается при условии ed = kц(n)+1. Это эквивалентно следующим соотношениям: ed = 1 mod ц(n), d = e^-1 mod ц(n), т.е. e и d являются взаимно обратными по mod ц(n), т. е. gcd(ц(n), d) = 1.

Компонентами схемы являются:

p и q - два разных простых числа (секретные, выбираются),

n = pq (открытое, вычисляется),

такое e, что gcd(ц(n), e) = 1, 1< е < ц(n), (открытое, выбирается),

d = e^-1 mod ц(n) (секретное, вычисляется).

Личный ключ складывается из (d,n), а открытый - из (e,n). Предположим, что пользователь А опубликовал свой открыты й ключ и теперь пользователь В собирается переслать ему сообщение М. При этом предполагается, что числа M и n взаимно простые. Пользователь В вычисляет С = М^е (mod n) и пересылает С. Получив этот шифрованный текст, пользователь А дешифрует его, вычисляя М = С^d (mod n).

Обоснование алгоритма. Числа d и e выбраны так, что

ed = 1 mod ц(n).

Значит, ed имеет вид kц(n)+1. По следствию из теоремы Эйлера

M^kц(n)+1 = М mod n.

Поэтому М^ed = М mod n.

Имеем соотношения

С = М^e mod n,

М = С^d (mod n) = М^ed mod n = M mod n.

Пример: рассмотрим следующие два простых числа p и q и их произведение n:

p =37866809061660057264219253397,

q =2⁶⁰ - 173= 1 152 921 504 606 846 803,

n =pq=43 657 458 478 029 293 976 669 622 635 814 729 303 016 339 791.

Отметим, что факторизация n обычным методом потребовала бы порядка 10¹⁷ операций, что соответствует примерно 1000 лет работы машины, выполняющей миллион операций в секунду. Немного усовершенствованный, типа метода Полларда, метод факторизации требует порядка 10⁹ операций, а значит, с выбранными числами предложения система шифрования может быть взломана. Однако на практике выбирают простые числа, имеющие порядка 100 цифр в десятичной записи, и там даже метод Полларда бессилен.

Итак, в качестве открытого ключа требуется обнародовать n и число, обратимое по модулю (p-1)(q-1)=43 657 458 478 029 293 938 802 813 573 001 750 534 190 239 592.

Например, e=3. Если исходное послание представляется в виде числа

M=123 456 654 092 127 765 342 896 201 397,

то посылающий возводит его в куб по модулю n , что дает

M³ mod n=36 807 684 002 873 914 344 429 802 591 773 115 971 466 280 467.

Получатель легко может обратить 3 по модулю ц(n); действительно, так как p и q сравнимы с 2 по модулю 3, то ц(n) = (p-1)(q-1) сравнимо с 1 по модулю 3, а значит, число d = ц(n) - (ц(n) - 1)/3 =29 104 972 318 686 195 959 201 875 715 334 500 356 126 826 395.

Обратно к 3 по модулю (p-1)(q-1). Возводя полученное сообщение в степень d по модулю n, получатель найдет число M.

12. Вычисление ключей

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

-определение двух простых чисел p и q;

-выбор одного из чисел e или d и вычисление второго.

Сначала рассмотрим процедуру выбора p и q. Ввиду того, что значение n=pq будет известно любому потенциальному противнику, то для того, чтобы не допустить возможности нахождения p и q с помощью простого перебора вариантов, эти простые числа должны быть выбраны из достаточно большого множества. В то же время метод нахождения больших простых чисел должен быть практически эффективным.

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

Процедуру выбора простого числа можно представить в следующем виде.

1.Выберите нечетное целое число n некоторым случайным образом

2.Выберите целое число а< n некоторым случайным образом.

3.Выполните вероятностный тест на простоту, например тест Миллера - Рабина. Если n не выдерживает тестирования, отбросьте данное значение n и перейдите к п.1.

4.Если n выдерживает достаточное число повторных тестов, примите данное значение n как подходящее, в противном случае перейдите к п.2.

Одна из теорем теории чисел, известная под названием теоремы о простых числах, утверждает, что простые числа около N распределяются в среднем по одному на каждыеln(N) целых чисел. Таким образом, в среднем придется протестировать порядка ln(N) целых чисел прежде, чем найдется простое число. В действительности из-за того, что все четные числа можно отбросить сразу же, истинный порядок задается числом ln(N)/ 2. Например, если искать простые числа в области величин порядка 2²⁰⁰, то для нахождения простого числа потребуется около ln(2²⁰⁰)/2=70 попыток.

После определения простых чисел p и q процесс вычисления ключей завершается выбором значения е и вычислением d или, наоборот, выбором значения d и вычислением е. В первом случае необходимо сначала выбрать такое е, что gcd (ц(n),е) =1, а потом вычислить d=e^-1mod ц(n). К счастью, имеется один алгоритм, который в одно и то же время вычисляет наибольший общий делитель двух целых чисел и , если наибольший общий делитель оказывается равным 1, определяет обратное для одного из целых чисел по модулю другого. Этот алгоритм в дальнейшем называемый обобщенным алгоритмом Евклида. Процедура заключается в генерировании случайных чисел и сравнении их с ц(n) до тех пор, пока не будет найдено число, взаимно простое с ц(n).

13. Защищенность алгоритма RSA

Тремя возможными подходами к криптоанализу алгоритма RSA являются следующие:

1. Простой перебор. Предполагает проверку всех возможных личных ключей.

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

3. Анализ временных затрат. Опирается на анализ времени выполнения алгоритма дешифрования.

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

14. Проблема разложения на множители

Можно выделить следующие три математически различных подхода к криптоанализу RSA.

1.Разложение числа n на два простых множителя p и q. Это позволит вычислить

ц(n) = (p-1)(q-1),

на основании чего можно будет определить

d = e^-1 (mod ц(n)).

2.Определение непосредственно ц(n) без того, чтобы сначала определять p и q. Это также позволит определить

d = e^-1 (mod ц(n)).

3.Определение непосредственно d без того, чтобы сначала определять ц(n).

Задача определения ц(n) по данному n оказывается эквивалентной задаче разложения n на множители. Затраты на решение задачи разложения на множители можно использовать в качестве эталона при оценке степени защищенности RSA. Запишем еще ряд ограничений относительно p и q.

1.Значения p и q должны отличаться по длине всего на несколько разрядов. И p, и q должны попадать в диапазон от 10⁷⁵ до 10¹⁰⁰.

2.Как (p-1) так и (q-1) должны содержать в своих разложениях достаточно большой простой множитель.

3.gcd(p-1, q-1) должен быть достаточно малым.

Если же e < n и d < n^1/4, то d можно определить достаточно легко.

Вывод

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

Литература

1. Вильям Столингс. Криптография и защита сетей. Принципы и практика. 2-ое издание.

2. П. Ноден, К. Китте. Алгебраическая алгоритмика. М.: Мир, 1999.

3. В.В. Ященко. Введение в криптографию. М.:ЧеРо, 1998.

4. Г. Биркгоф, Т. Барти. Современная прикладная алгебра. М.: Мир, 1976.

Размещено на Allbest.ru