Асимметричные криптосистемы

Реферат по предмету "Информационная безопасность" был защищен на "Отлично" в июне 2014 года. В данной работе будут рассмотрены асимметричные криптосистемы или системы с открытым ключом через призму развития математической мысли. В ходе работы затронуты такие вопросы, как проблема распределения ключей, алгоритм Диффи – Хеллмана, алгоритм шифрования RSA, конфиденциальность и проверка подлинности сообщений и ключей, хеш-функции и сертификаты открытых ключей. ...

Введение
Проблема распределения ключей
Алгоритм Диффи - Хеллмана
Алгоритм шифрования RSA
Конфиденциальность. Проверка подлинности сообщений и ключей
Хеш-функции
Сертификаты открытых ключей
Заключение
Список литературы

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

Предположим, что отправитель А шифрует сообщение с помощью своего ключа и посылает результат получателю В, который повторно шифрует зашифрованное послание своим ключом и возвращает его отправителю. А расшифровывает сообщение своим ключом и посылает назад результат, т.е. текст, в данный момент зашифрованный только ключом В, который его расшифровывает. Казалось бы, вековая проблема безопасного обмена ключами решена. Но, к сожалению, нет. В любом сложном алгоритме шифрования порядок применения ключей имеет решающее значение, а в нашем примере мы видим, что А расшифровывает сообщение, которое уже зашифровано другим ключом. Когда порядок ключей меняется, результат будет абракадаброй.В 1976 г. два молодых американских ученых, Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человекамогут обмениваться зашифрованными сообщениями без всякого обмена секретными ключами. Этот метод использует модульную арифметику, а так же свойства простых чисел. Идея заключается в следующем:А выбирает число, которое он держит в секрете. Обозначим это число Nj1.B выбирает другое случайное число, которое он тоже держит в секрете. Обозначим это число Np1.Затем А и В применяют к своим числам функцию вида f(x) = ax (mod p), где р – простое число, известное им обоим. После этой операции А получает новое число, Nj2, которое он посылает В, а В посылает А свое новое число Nр2.А вычисляет Np2Nj1(mod p) и получает новое число Сj.А вычисляет Nj2Np1(mod p) и получает новое число Сp.Хотя это кажется невозможным, но числа Сj и Сp являются одинаковыми. И теперь у нас есть ключ. Заметим, что А и В обменивались информацией только тогда, когда они выбирали функцию f(x) = ax (mod p) и посылали друг другу числа Nj2 и Nр2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:aNj1∙Np1(mod p).Важно также учесть, что данная функция имеет одну особенность: она необратима, т.е. зная саму функцию и результат ее применения к переменной х, невозможно (или, по крайней мере, очень сложно) найти исходное значение х.Алгоритм Диффи – Хеллмана продемонстрировал возможность создания криптографического метода, который не требует обмена ключами, хотя, использует открытую связь – передачу пары первых чисел, которые служат для определения ключа.Это дало возможность иметь надежную систему шифрования между отправителем и получателем, которым нет необходимости встречаться и договариваться о секретном ключе. Однако некоторые проблемы все же существуют: предположим, что А хочет послать сообщение В в то время, когда В, например, спит, ему придется подождать пробуждения В, чтобы завершить процесс генерации ключа.Алгоритм шифрования RSAВ августе 1977 г. знаменитый американский писатель и популяризатор науки Мартин Гарднер озаглавил свою колонку по занимательной математике в журнале Scientific American так: «Новый вид шифра, на расшифровку которого потребуются миллионы лет». После объяснения принципа системы шифрования с открытым ключом он показал само зашифрованное сообщение и открытый ключ N, используемый в этом шифре:N = 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733897 830 597 123 563 958 705 058 989 075 147 599 290 026 879543 541.Гарднер призвал читателей попробовать расшифровать сообщение, используя предоставленную информацию, и даже дал подсказку: для решения необходимо разложить число N на простые множители p и q. Более того, он назначил приз в размере $ 100 тому, кто первым получит правильный ответ. Каждый, кто захочет больше узнать о шифре, писал Гарднер, может обратиться к создателям шифра – Рону Ривесту, Ади Шамиру, Лену Адлеману из Лаборатории информации Массачусетского технологического института.Правильный ответ был получен лишь через 17 лет. Он стал результатом сотрудничества более 600 человек. Ключами оказались p = 32769132993266709549 9961988190834461413177642967992942539798288533 и q = 3490529510847650949147849 619903898133417764638493987843990820577, а зашифрованная фраза звучала так: «Волшебные слова – это брезгливый ягнятник».Алгоритм, представленный Гарднером, известен как RSA – буквенная аббревиатура от фамилий Rivest, Shamir, Adleman. Это первое практическое применение придуманной Диффи системы шифрования с открытым ключом, которая повсеместно используется и по сей день.В основе алгоритма лежат следующие факты:Количество натуральных чисел, меньших n и взаимно простых с n, называется функцией Эйлера и обозначается как ϕ(n).Если n = pq, где p и q – простые числа, то ϕ(n) = (p – 1)(q – 1).Из малой теоремы Ферма следует, что если а – целое число, больше нуля, и p – простое число, то ар – 1 ≡ 1 (mod p).Согласно теореме Эйлера, если НОД (n, a) = 1, то аϕ(n) ≡ 1 (mod n).Сначала отправитель А вычисляет значение n путем умножения двух простых чисел p и q (n = pq) и выбирает значение е так, чтобы НОД (ϕ(n), е) =1. ϕ(n) = (p – 1)(q – 1). Данные, которые являются открытыми, - это значение n и значение е. Пара (n, e) является открытым ключом системы, а значения p и q называются RSA-числами. Затем А вычисляет единственное значение d по модулю ϕ(n), которое удовлетворяет условию d ∙ e = 1, т.е. d является обратным элементом к числу е по модулю ϕ(n). Мы знаем, что обратный элемент существует, т.к. НОД (ϕ(n), е) =1. Это число d является закрытым ключом системы. Со своей стороны получатель В использует открытый ключ (n, e) для шифрования сообщения Х с помощью функции Х = me (mod n). Получив сообщение, А вычисляет Хd = (me)d(mod n), а это выражение эквивалентно Хd = (me)d = m(mod n), что свидетельствует о возможности расшифровать сообщение.Конфиденциальность. Проверка подлинности сообщений и ключейАлгоритм RSA требует много машинного времени и очень мощных процессоров. До 1980-х гг. только правительства, армия и крупные предприятия имели достаточные компьютеры для работы с RSA. В результате у них была фактически монополия на эффективное шифрование. Летом 1991 г. Филипп Циммерман, американский физик и борец за сохранение конфиденциальности, предложил бесплатную систему шифрования PGP (Pretty Good Privacy – «достаточно хорошая степень конфиденциальности»), алгоритм, который мог работать на домашних компьютерах. PGP использует классическое симметричное шифрование, что и обеспечивает ей большую скорость на домашних компьютерах, но она шифрует ключи по асимметричному алгоритму RSA.Циммерман объяснил причины этой меры в открытом письме, из которого можно заключить, что жизнь в век информации сопряжена с угрозой нашим традиционным представлениям о частной жизни. Следовательно, глубокое понимание кодирования и механизмов шифрования, используемых вокруг нас, не только делает нас мудрее, но также может оказаться чрезвычайно полезным, когда речь идет о защите того, что для нас особенно ценно.PGP с момента его создания становится все более популярным и представляет собой наиболее важный инструмент шифрования, доступный сегодня частным лицам.Различные системы шифрования с открытым ключом – или сочетающие открытые и закрытые ключи – обеспечивают высокий уровень конфиденциальности при передаче информации. Тем не менее, безопасность сложных систем связи, таких, как интернет, заключается не только в конфиденциальности.