Открытое распределение ключей 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Открытое распределение ключей



 

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

1. Пусть имеются два абонента открытой сети А и В, знающие пару открытых ключей Р и D. Кроме того, у А есть секретный ключ Х из интервала (1, N), а у В есть секретный ключ Y из того же интервала.
2. Абонент А посылает В шифровку своего ключа Z'=D**X MOD Р, а абонент В посылает А шифровку своего ключа Z"=D**Y MOD P.
3. После этого общий ключ Z они вычисляют как
Z=Z'**Y =Z''**X.

При помощи специальных приемов время формирования общего ключа в системе Диффи-Хеллмана может быть сокращено в 5 раз по сравнению с системой ЭльГамаля в модификации Шамира, и в 30 раз по сравнению с RSA при том же уровне стойкости. Это, с точки зрения большинства практических приложений, оказывается заметным преимуществом, так как шифрование и расшифровывание по алгоритму RSA примерно в тысячу раз медленнее классических алгоритмов типа DES. Отметим, что для многих применений криптографических систем с открытым ключом время вычислений при криптографических преобразованиях не имеет большого значения. Например, при идентификации пользователей по кредитным карточкам не будет разницы потребует ли она одну микросекунду или одну секунду. То же относится и к выбору общего ключа шифрования для другой, более быстродействующей, но не обладающей способностью обмена ключами криптографической системы.

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

Из практически действующих сетей связи, использующих систему открытого распределения ключей, наиболее серьезно защищенной является телефонная государственная сеть США на основе аппаратов STU-III. Она начала функционировать в 1987 году и содержит сейчас более 150 тысяч абонентов. В России аналогичная сеть, называемая еще АТС-1 или "вертушкой", тоже надежно защищена, но абонентов там в сотни раз меньше. От этого многие данные передаются по не вполне закрытым сетям вроде ИСКРА-2, доступным для взлома хакерами. К началу восьмидесятых годов криптологи пришли к пониманию преимущества так называемых гибридных систем, в которых процедуры шифрования с открытым ключом используются лишь для передачи ключей и цифровой подписи, а информация, которую нужно передать, защищается классическим алгоритмом типа DES, ключ для которого передан с помощью шифрования с открытым ключом. Первым серийным устройством данного типа был Datacryptor фирмы Racal- Milgo, выпущенный в 1979 году. Аппарат управления ключами шифрования Datacryptor предназначен в основном для правительственных сетей связи и аттестован на соответствие английскому стандарту защиты не секретной, но важной информации. В нем предусмотрены сигнализация о нарушениях криптографических требований и извещения об ошибках. В этом аппарате используется алгоритм установления шифрованной связи при помощи выработки и передачи общего секретного ключа по алгоритму RSA. В дальнейшем аппаратов подобного типа для защиты информации было выпущено очень много. Другие примеры использования новых криптографических идей демонстрируют многие коммерческие сети, особенно банковские, как SWIFT. Кроме того, система цифровой подписи RSA применяется в аппаратуре проверки соблюдения договора об ограничении ядерных испытаний, разработанной Sandia Laboratories в 1982 году, сети BPMIS и других системах. В России ряд фирм тоже занимается гибридными схемами, как Телекрипт, использующей быстродействующий алгоритм ГОСТ 28147-89 для шифрования данных и генерации имитоприставок (Имитоприставка - шифрованная контрольная сумма по исходному тексту, позволяющая с любой наперед заданной вероятностью судить об отсутствии в нем искажений.) и алгоритм RSA для управления ключевой информацией и получения цифровых подписей.

Алгори́тм Ди́ффи — Хе́ллмана (англ. Diffie-Hellman, DH) позволяет двум или более пользователям обменяться без посредников ключом, который может быть использован затем для симметричного шифрования. [1]

Данный алгоритм не применяется для шифрования сообщений или формирования электронной подписи. Его назначение – в распределении ключей.

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

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

История

Основы криптографии с открытыми ключами были выдвинуты Уитфилдом Диффи(Whitfield Diffie) и Мартином Хеллманом(Martin Hellman), и независимо Ральфом Мерклом(Ralph Merkle). Их вкладом в криптографию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно, получить один ключ из другого. Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции 1976г., через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptography" [2] ("Новые направления в криптографии").

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


В 2002 году Мартин Хеллман писал:

«Эта система … с тех пор известна под названием алгоритма Диффи — Хеллмана. Однако, когда система была впервые описана на бумаге Диффи и мной, это была система распространения публичных ключей, концепция которой была выработана Мерклем, и поэтому она должна называться „алгоритмом Диффи — Хеллмана — Меркля“, если её связывают с именами. Я надеюсь что это небольшое изменение поможет признанию равного вклада Меркля в изобретение криптографии с открытыми ключами.»[3]

Следуя данной трактовке, журнале U.S. Patent 4 200 770, некогда описывающем данный алгоритм, отметил его создателями уже три автора - Хеллман, Диффи и Меркль.

Только в декабре 1997 года появилась обновленная информация о том что в Малькольм Вильямсон уже в 1974 году изобрел математический алгоритм, основанный на коммутативности показателей при последовательном возведении в степень ((bx)y = (by)x = bxy). Данный метод можно назвать аналогом алгоритма Диффи-Хеллмана.[4]

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

Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб— число b. Затем Алиса вычисляет значение[5] (1):

(1)

и пересылает его Бобу, а Боб вычисляет (2):

(2)

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

На втором этапе первый абонент на основе имеющегося у него a и полученного по сети B вычисляет значение (3):

(3)

Второй абонент на основе имеющегося у него b и полученного по сети A вычисляет значение (4):

(4)

Как нетрудно видеть, у Алисы и Боба получилось одно и то же число (5):

(5)

Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления (3) или (4) по перехваченным и , если числа p,a,b выбраны достаточно большими. Наглядная работа алгоритма показана на рисунке[6].

Алгоритм Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

1. генерирует случайное натуральное число aзакрытый ключ

2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

p является случайным простым числом

g является первообразным корнем по модулю p

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

A = ga mod p

4. обменивается открытыми ключами с удалённой стороной

5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = Ba mod p

К получается равным с обеих сторон, потому что:

Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

Цифровой конверт

Одиннадцатого января 1996 года министерство юстиции США без доведения до суда (и без всяких комментариев) прекратило длившееся около трех лет уголовное дело по статье «незаконный экспорт оружия». Однако подследственный «оружейный барон» Фил Зиммерман не продавал «Стингеры» Ираку или ядерные технологии Ирану. Он всего лишь написал бесплатную компьютерную программу, делающую практически невозможным расшифровку частных сообщений американскими правительственными агентствами. Оружие для всех Закончив Флоридский университет по специальности «компьютерные науки», Фил Зиммерман работал программистом, специализируясь на передаче данных и защите информации, а в свободное от работы время активно участвовал в антивоенном и правозащитном движении. Такое сочетание интересов привело его к сильнейшему желанию создать надежную криптографическую программу. За основу были взяты наиболее стойкие из известных по открытой печати алгоритмов шифрования. Странновато звучащее название PGP (Pretty Good Privacy – Весьма Приличная Приватность) родилось, по воспоминаниям автора, как-то само собой – по аналогии с названием бакалейной лавки Pretty Good Grocery из популярного в Америке радиоспектакля. PGP создавалась без какой-либо финансовой поддержки и в большой спешке, поскольку при президенте Буше-папе в США отчетливо складывалась ситуация, грозившая поставить публикацию подобных программ вне закона. В 1991 году в конгрессе обсуждался новый законопроект (Билль №261), направленный на борьбу с преступностью. Среди прочих в нем имелся и пункт о том, что всякая система связи должна обеспечивать правительству доступ к открытому тексту сообщения. По этой причине уже самая первая версия PGP стала распространяться как общедоступная бесплатная программа – в попытке упредить возможное подавление правительством подобных технологий в будущем. Но стараниями американских правозащитников упомянутый билль был вскоре отвергнут, а удачная программа PGP быстро набирала популярность не только в Америке, но и во всем мире, что вызвало сильное недовольство в компетентных органах США, так как еще со времен окончания Второй мировой войны государство поставило экспорт средств криптографии под строжайший контроль. Средства шифрования по своей опасности были приравнены к наступательным видам оружия и не подлежали экспорту без официальной лицензии Государственного департамента. Эти правила были созданы задолго до появления персональных компьютеров и Интернета, но, когда PGP попала во всемирную сеть и быстро распространилась по всей планете, правительство США сочло, что имело место нарушение закона, и в 1993 году на автора программы было заведено уголовное дело. Расследование велось около трех лет – впрочем, без особого успеха. С формальной точки зрения вменить Зиммерману в вину было практически нечего: программу он написал, что называется, для себя (а сие ненаказуемо) и дал ее нескольким друзьям (что тоже законом не запрещено). Кто-то из друзей положил PGP на сервер локальной сети, не имеющей выхода в Интернет (и за это наказать невозможно). А уж с этого сервера взять программу и запустить ее в Интернет мог воистину кто угодно, и найти тех людей нет никакой возможности... Как хранить секреты Отправлять по электронной почте незашифрованное письмо – примерно то же самое, что посылать по обычной почте открытки, содержимое которых доступно всем любопытствующим. Средства шифрования вроде PGP отлично решают эту проблему, как бы запечатывая электронное письмо в надежный «цифровой конверт». На заре всеобщей интернетизации подобные программы требовали от пользователей хотя бы общего понимания основ криптотехнологий, не говоря о специфической терминологии. Очень многих это обстоятельство отвратило и от PGP, и вообще от шифрования почты. Да и чего ради напрягаться, когда ежедневное количество сетевых писем исчисляется миллиардами, а твои послания – капля в безбрежном океане, кто их там разглядит? Вероятно, на это можно было надеяться 10–15 лет назад, но сейчас компьютерные технологии поиска и фильтрации информации позволяют весьма эффективно выделять в гигантских потоках данных нужные адреса, имена или ключевые слова. И вести эти поиски могут не только государственные спецслужбы. Самым же простым и надежным средством защиты от подобных угроз по-прежнему остается криптография. Важнейший элемент всякой криптосистемы – ключ. Предполагается, что с помощью шифрования данные засекречиваются от всякого, кому их знать не положено. Ну а те, для кого текст предназначен, должны располагать «ключом», особой информацией, с помощью которой производится расшифрование. На протяжении тысячелетий люди применяли лишь шифры с ключом отправителя, идентичным ключу получателя. Сейчас такие схемы называют «симметричным шифрованием», но еще полвека назад считалось, что других шифров не может быть в принципе. Симметричные криптоалгоритмы можно делать «железобетонно» стойкими ко взлому (практически невскрываемыми) и при этом чрезвычайно быстрыми в работе. Но для них требуется общий ключ шифрования/расшифрования, а это означает гигантскую по сложности и затратам проблему постоянной безопасной рассылки ключей. Во второй половине XX века математики придумали кардинально новую технологию, так называемую «криптографию с открытым ключом», где ключи генерируются как пара больших чисел: одно число-ключ используется для шифрования информации, второе – для расшифровки. Поскольку в этом случае ключи отправителя и получателя существенно различаются, новый класс шифров стали называть «асимметричными». Здесь один ключ из пары, «открытый», известен всем, так что зашифровать послание может любой желающий. А вот второй ключ, «закрытый», или «приватный», известен только одному человеку-владельцу, так что исключительно он может расшифровать адресованный ему секрет. Главная проблема асимметричных шифров – сложность вычислений. Такая криптография построена на вычислительных операциях с чудовищно большими числами длиной во многие сотни, а порой и тысячи бит. Даже для современных компьютеров это очень непростая задача. При приблизительно равной криптографической стойкости асимметричного и симметричного шифров на обработку сообщения в первом случае требуется в среднем в тысячу раз больше вычислительных ресурсов. По этой причине, собственно, и появились гибридные криптосхемы, такие как PGP, берущие от каждого из методов лучшее. Когда пользователь программы дает команду зашифровать послание, первым делом открытый текст подвергается сжатию. Это нужно не столько для экономии места на диске или сокращения времени передачи, сколько для усиления криптографической стойкости шифра. Сжатый стандартным алгоритмом компрессии текст дешифровать значительно сложнее. Следующий шаг в работе PGP – генерация так называемого «сеансового ключа», относительно небольшой (обычно длиной 80, 128 или 256 бит) секретной последовательности, которая используется строго однократно для шифрования отправляемого текста. Сеансовый ключ должен иметь как можно более случайный вид, чтобы противник не мог его угадать или подобрать перебором наиболее вероятных слов. Поэтому сеансовый ключ порождается алгоритмом-генератором случайных чисел, на вход которого подаются сигналы от произвольных движений манипулятора-мышки или нажатий на кнопки клавиатуры. Когда с помощью сеансового ключа изготовлен шифртекст, сам ключ зашифровывается открытым ключом получателя. Если у отправителя такого ключа еще нет, то раздобыть его несложно, ибо они публикуются их владельцами в Интернете на серверах инфраструктуры открытых ключей (PKI или Web Of Trust), а криптопрограмма умеет их искать по имени-адресу человека. Зашифрованный сеансовый ключ присоединяется к файлу шифртекста, и вместе они отправляются адресату в виде единого электронного письма. У получателя послания, в компьютере которого также установлена PGP, процесс расшифровывания происходит в обратном порядке. Личный закрытый ключ используется для расшифровки одноразового сеансового ключа, а тот, в свою очередь, применяется для получения открытого текста послания. Все эти процедуры происходят в автоматическом режиме и практически незаметно для пользователя. Сейчас криптография PGP встраивается в качестве сервисного элемента в любую из популярных почтовых программ. Единственное, что требуется от пользователя для защиты писем, – это выбрать в соответствующем меню позицию «шифровать» и/или «поставить цифровую подпись». Весьма приличная приватность Можно ли вскрыть сообщение, зашифрованное PGP? Если имеется в виду «любыми способами добраться до открытого текста», то да, такие способы в принципе существуют, но они зачастую не имеют никакого отношения к криптографии (например, тайно подсадить в компьютер программу-закладку, перехватывающую все вводимые с клавиатуры тексты или ворующую пароли доступа). Но если под «вскрытием» понимать аналитический взлом криптоалгоритмов PGP, то эта задача доказуемо неразрешима за любое реальное время при наличии у вскрывающего любого мыслимого объема вычислительных ресурсов. Чрезвычайно наглядное представление о стойкости этой криптопрограммы дал в свое время Уильям Кроуэлл, первый заместитель директора Агентства национальной безопасности США: «Если все персональные компьютеры в мире – а их примерно 260 млн. штук – бросить на вскрытие единственного сообщения, зашифрованного PGP, то для успешного его дешифрования понадобилось бы время, в 12 млн. раз превышающее возраст Вселенной». С марта 1997 года, когда Кроуэлл делал это заявление на слушаниях в конгрессе США, количество компьютеров на планете, конечно же, выросло многократно, однако это ни в малейшей степени не понизило теоретическую стойкость PGP. Причина тому – в чрезвычайно надежных и глубоко изученных алгоритмах шифрования, для которых не найдено никаких других методов вскрытия, кроме тотального перебора всех возможных ключевых последовательностей. В таких условиях важнейшим и, по сути, единственным фактором, влияющим на количество необходимых для вскрытия вычислений, становится длина ключа. В 1997 году базовым размером ключа для симметричного алгоритма PGP была длина 128 бит. Это для нее в докладе Кроуэлла были сделаны расчеты, согласно которым для отыскания ключа тотальным перебором (лобовым вскрытием) суперкомпьютеру производительностью порядка 30 млн. операций в секунду требовалось бы время работы, в 13 трлн. раз превышающее возраст Вселенной, составляющий 13 млрд. лет. На сегодняшний день стандартными длинами ключа в PGP являются 128, 192 и 256 бит. Увеличение длины ключа всего лишь на 1 бит означает двукратное увеличение общего числа опробований ключа при вскрытии. Иначе говоря, в таких условиях решение задачи вскрытия будет всегда оставаться абсолютно безнадежным делом. Но что интересно, практически любые криптосистемы при этом все равно можно вскрывать. Правда, не в лоб, а замысловатыми обходными путями, для рассказа о которых потребуется отдельная статья.

 

Законная контрабанда После того, как в начале 1996 года следствие по делу о PGP было закрыто, свободно вздохнувший да еще и ставший знаменитым разработчик основал собственную компанию для коммерческой раскрутки программы. Однако свободное плавание фирмы PGP оказалось совсем недолгим – в декабре 1997 года ее взял под свое крыло софтверный гигант Network Associates, специализирующийся на компьютерной безопасности. Продав свою компанию за $25 млн., Фил Зиммерман некоторое время состоял в совете директоров Network Associates, но затем предпочел статус независимого консультанта в области защиты информации. Завладев коммерческими правами на Pretty Good Privacy, новый хозяин пожелал сохранить и независимый дух легендарной криптопрограммы. До отмены строгих ограничений на экспорт американской криптографии дело тогда еще не дошло, тем не менее компания сумела найти абсолютно законный способ для свободной продажи своего «невывозного» продукта во всех странах мира. Поскольку федеральные запреты не распространяются на книги (свобода слова!), полный текст исходного кода программы был выпущен в виде отдельной брошюры, а та, в свою очередь, продана швейцарской компании CNLAB Software. В CNLAB каждую страницу тщательно отсканировали, вычитали и скомпилировали код обратно в программу. Затем эта версия программы была вновь продана Network Associates, но не американской штаб-квартире, а голландскому подразделению Network Associates International, которое и стало продавать PGP на международном рынке. Изготовленный таким образом продукт формально стал самостоятельной программой европейского происхождения, хотя исходный код ее ничем не отличался от американского оригинала.

 



Поделиться:


Последнее изменение этой страницы: 2017-01-24; просмотров: 373; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.200.196.114 (0.081 с.)