Разделы: Информационные технологии
Размещена 13.11.2013. Последняя правка: 18.11.2013.
Просмотров - 10987

Обзор алгоритма обмена ключами Diffie-Hellman

Мандрыкин Евгений Сергеевич

NVision Group, НГТУ

Инженер-стажер

УДК 004.021

История криптографии очень богата и насчитывает около четырех тысяч лет. Древние египтяне (да и не только египтяне, а еще и греки, индийцы и другие развитые народы Древнего мира) использовали криптографию для защиты переписки. Описывать все способы шифрования информации в древности смысла не имеет, поскольку эта тема очень широка и является темой многих изданий. В большинстве своем древняя криптография использовала симметричные шифры, т.е. использовала один и тот же ключ для шифровки и расшифровки сообщения. Такой способ шифрования делает получателя письма целиком и полностью зависимым от адресата – ведь если тот не скажет ему ключ, получатель не сможет расшифровать сообщение, а держать под рукой важную информацию, которую нельзя прочитать, бессмысленно. Особенно остро эта проблема стояла в  древности, где других способов коммуникации, кроме личной встречи и письма, не было. Сейчас, когда есть множество способов связи и широкий спектр защищенных каналов связи, по-прежнему существует риск перехвата от Евы шифра или сообщения от Алисы к Бобу.  Алиса, Боб и Ева – архетипы, использующиеся в области криптографии. Алиса и Боб – два заинтересованных в передаче зашифрованного сообщения человека, Ева – пассивный злоумышленник, который хочет это зашифрованное сообщение прочитать. [1]

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

В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (Diffi W., Hellman M.) предложили новый принцип построения криптосистем [2]. По их задумке, передачу от Алисы к Бобу сообщения можно было осуществить без передачи ключей, более того, не было необходимости скрывать метод шифрования. Предложенный принцип, в итоге, преобразовался в отдельную классификацию алгоритмов шифрования - шифрование с открытым ключом.

В поисках способов реализовать свою идею, Диффи и Хеллман пришли к использованию односторонних функций, т.е. функций, в которых получить исходное значение практически невозможно. Одна из таких функций в математике – вычисление по модулю [3]. Перейдем к рассмотрению самого алгоритма.

Принцип простой. Сначала Алиса и Боб вместе выбирают большие простые числа n и g так, чтобы работало следующее соотношение: g^xmod n. Эти два числа не нужно хранить в секрете, поэтому об использовании этих чисел Алиса и Боб могут договориться как им удобно (даже прийти в гости к Еве и выбрать эти числа при ней). Потом выполняются следующие действия:

1)    Алиса выбирает случайное целое большое число x и присылает Бобу число X, полученное по формуле X =  g^xmod n.

2)    Боб выбирает случайно целое большое число y и присылает Алисе число Y, которое считается как Y = g^ymod n.

3)    Алиса вычисляет число k1 = Y^xmod n.

4)    Боб вычисляет число k2 = X^ymod n.

Нетрудно заметить, что и k1, и k2 равны g^xymod n. Но ни Ева, ни кто-нибудь еще, кто прослушивал канал, не знают этого значения. Им известны только n, g, X и Y. Теоретически, Ева знает функцию и может вычислить k1 или k2, но, к сожалению для нее, эта функция является односторонней, и если Алиса и Боб могут выполнить обратное преобразование, поскольку обладают всеми необходимыми числами, то Еве будет очень сложно сделать тоже самое, а учитывая, что работа ведется с большими числами, - почти невозможно.

Есть, конечно, одно «но». Выбор n и g довольно сильно влияет на безопасность системы. Следует выбирать n такое, чтобы (n-1)/2 было также простым, и, самое главное, чтобы n было большим: безопасность заключается в сложности разложения на множители чисел того же размера, что и n. Требования к выбору g не такие строгие, главное требование – оно должно быть примитивом mod n. В остальном же, оно может быть хоть одноразрядным простым числом.

Следует добавить, что алгоритм Диффи-Хеллмана успешно работает с тремя и более участниками, секретный ключ, после всех вычислений будет иметь вид k = g^n1*n2*…*nNmod n, где n1..nN – переменные, закрепленные за каждым участником (x,y, z и т.д.) [1]. Алгоритм, как видно из заголовка, является алгоритмом обмена ключами, а не шифрования.

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

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

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

RSA получил широкое распространение за счет использования в системах шифрования. Отличный пример, система открытого шифрования PGP (PrettyGoodPrivacy), разработанная в 1991 году Филиппом Циммерманном, получила большую популярность и в 2010 году была приобретена компанией Symantec за 300 млн. долларов. Первая версия программы включала в себя только алгоритм RSA.

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

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

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

1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си; Applied Cryptography. Protocols, Algorithms and Source Code in C / Под ред. А. Б. Васильева. – М.: Триумф, 2002.
2. Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. – СПб.: СПбГИТМО(ТУ), 2002.
3. Сингх С. Книга шифров: тайная история шифров и их расшифровки / пер. с англ. А. Галыгина. – М.: АСТ: Астрель, 2007.

Рецензии:

14.11.2013, 2:54 Назарова Ольга Петровна
Рецензия: Статья по сути имеет информационный характер.Нет анализа по достоинствам и недостаткам других алгоритмов. Непонятно, алгоритм "открывший абсолютно другую методику", разработан в 1976, а позже ничего хорошего не было? если было, чем отличалось? Режет слух "В статье обозревается"- аннотацию отредактировать. Судя по стилю, создается впечатление, что взяты здоровенные куски текста из источников [1],[2],[3]. Где автор? Устранить недостатки.

14.11.2013, 15:10 Панов Александр Викторович
Рецензия: Хорошо отражены основы шифрования с открытым ключем. С учетом статуса "Инженер-стажер",- можно отметить логическую взаимосвязь статьи и системность в изложении материала. Понятно раскрыт принцип открытого обмена, упоминая: "использованию односторонних функций..., вычисление по модулю...", путем цитирования. Это позволяет среднестатистическому специалисту, не вдаваясь в математические тонкости понять сущность принципа шифрования с открытым ключем. Согласен с Назаровой О.П., что желательно показать значение этого принципа и его влияние на современную практику. Таким образом, автору советую написать выводы от себя, как он оценивает и понимает влияние этого способа шифрования на современное и будущее состояние. Рекомендую к публикации.

18.11.2013, 19:02 Бондаревский Аркадий Самуилович
Рецензия: В статье выделены три наиболее продвинутых алгоритма криптографии. Подвергнуты критике все три. Ну и что? В работе нет позитива, - точки зрения и предлагаемого автором. Статья актуальна, полезна и содержит новизну. Рекомендуется к публикованию, - ПРИ УСЛОВИИ УЧЁТА ЗАМЕЧАНИЯ. Кстати, почему "Обзор алгоритма" (как можно "обзирать" ОДИН алгоритм?

19.11.2013, 10:49 Туманов Владимир Евгеньевич
Рецензия: Научное направление работы. Информационные технологии Класс статьи: наблюдения из практики . Научная новизна: 1) Подтверждение новой оригинальной заимствованной концепции, 2) Констатация известных фактов. Оценка достоверности представленных результатов. Практическая значимость. Предложены: 1) Обзор хорошо известных алгоритмов. Формальная характеристика статьи. Стиль изложения - хороший, но требует правки. ОБЩЕЕ ЗАКЛЮЧЕНИЕ. Статья не актуальна, не обладает научной и практической новизной, не рекомендуется для печати. Очень жаль, что автор не знаком с большим числом работ в этой сфере, в основном опубликованных за последние 10-12 лет в трудах международных конференций, например ASIACRYPT и т.д., иначе бы он не стал писать свою статью в таком стиле.



Комментарии пользователей:

5.12.2013, 3:29 Назарова Ольга Петровна Отзыв: Рекомендуется к печати.

Оставить комментарий