Алгоритм Diffie-Hellman: Ключ к безопасному общению

[Number571]

Протокол Диффи-Хеллмана не так идеален, как описан в статье, и может содержать массу условностей при безопасном применении. Как минимум на нём работает старая добрая MITM атака. Как максимум необходимо использовать надёжные простые числа. В статье это к сожалению никак не затрагивалось, хотя тема очень важная, потому что без подобного рода простых чисел протокол Диффи-Хеллмана может просто скатиться к маркетинговой рекламе.
Для новичков такой материал хоть и будет понятнее, чем с подробностями, но такие облегчения просто приведут к неправильной картине восприятия самого протокола. На счёт подобного рода подводных камней протокола Диффи-Хеллмана очень хорошо написано в книге "Практическая криптография" (Шнайер, Фергюсон).

[Ariurn]

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

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

Единственное, что действительно хотелось бы добавить к статье - не изобретайте собственный велосипед, это чревато печальными последствиями.

[TimsTims]

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

Там все просто, импортируем библиотеку и вызываем функцию 

Т.е. вся поднаготная генерации публичного ключа и приватного ключа у вас спрятана где-то далеко в библиотеке. А статья изначально "на пальцах" описывала алгоритм DH. Получается как в том меме про "как нарисовать сову".

функцию NewBlockchain(), в которую нужно передать тип блокчейна blockchainkeys.Ethereum.

И вот тут тоже начинающего разработчика может спутить, что вроде у нас статья про алгоритм DH про безопасное общение, а в коде блокчейн и Ethereum.

// Так как ключи в Ethereum имеют прфик 0x, обрезаем его

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

[vseriousv]

Спасибо за отзыв, мне как начинающему автору это полезно :)

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

[AlexanderS]

Всегда было интересно, почему общий ключ получается одинаковым: B^a mod p = A^b mod p -> (g^b mod p)^a mod p = (g^a mod p)^b mod p. Я конечно, понимаю, что интерес в данном случае основывается исключительно на незнании модулярной арифметики и биноминального разложения. Но всё равно интересно, потому что и математически, и практически вычисление общего ключа выглядит красиво.

[yeputons]

Забудем сначала про модуль. Посмотрим просто на числа: пусть B=g^b и A=g^a. Тогда B^a=(g^b)^a=g^(b*a) — вот тут единственный нетривиальный трюк, надо заменить двойное возведение в степень на степень произведения. Аналогично с A^b=(g^a)^b=g^(a*b). А дальше пользуемся коммутативностью умножения: b*a=a*b.

А теперь если везде взять результат по модулю p (кроме b*a или a*b), то равенства не сломаются. Почему не сломаются — надо уже аккуратнее расписывать, что именно не ломается. Например, можно обозначить за B "настоящее" g^b, а за B' — взятое по модулю, дальше расписывать. Ещё из полезных трюков, через который вся модульная арифметика выводится: a = b (mod p) эквивалентно "(a - b) делится на p".

[kt97679]

Алиса и Боб выбирают общие параметры: основание g (допустим, 5) и большое простое число p (допустим, 23).

Скажите, пожалуйста, а как в реальной жизни выбираются числа g и p? Ведь Алиса и Боб не могут обменяться ими по открытым каналам? Или я что-то упускаю?

[Rsa97]

g и p полне могут передаваться открыто. Защита строится на том, что у функции (g^a mod p) нет обратной аналитической функции, позволяющей получить значение a при известных g, p и результате. От перебора защищаются выбирая a порядка 10¹⁰⁰, p порядка 10³⁰⁰ при небольших g.

[sgrechnev]

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

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

3. В разделе Безопасность общения нет упоминания сложности задачи дискретного логарифмирования, а именно на этом построен алгоритм. Не на том, что участники не обмениваются секретным ключом. А на том, что из тех чисел, которые они передают по открытому каналу связи, не умеем эффективно (с полиномиальной сложностью) восстанавливать секретные ключи. Квантовые вычисления пока не учитываем =)
   Ну и сгенерировать секретный ключ из открытых ключей , , и тоже не знаем как.

4. Про генерацию ключей с помощью библиотечных функций уже сказали, хотелось бы увидеть собственную и соответствующую теории реализацию. НО, меня очень смущает наличие эллиптических кривых в реализации. Разве мы теорию ECDH в статье разбирали? Разве на сложность дискретного логарифмирования на эллиптических кривых опираемся?
   Думаю, более правильно было бы доразобрать классический DH с возведением в степень.

5. секретный ключ, его еще называют «транспортный ключ»
   Вовсе необязательно секретный ключ является транспортным. Транспортный ключ определяется назначением, а не способ генерации / секретностью. По назначению можно выделить DEK, KEK, MEK.

[durnoy]

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

[devalio]

Как же вам не стыдно, делать столько возвратных значений в функции на GO =)

func (e *EthereumNetwork) GenerateKeyPair() (privateKey string, publicKey string, address string, err error) {