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

Всем привет!

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

Сегодня я хочу рассказать вам о волшебном алгоритме, который стоит за безопасным общением в интернете, и, в частности, в нашем любимом мессенджере — Telegram. Этот алгоритм называется алгоритмом Диффи-Хеллмана, и его история начинается в далеком 1976 году. На этом с историей закончим ?

Как это работает?

Алгоритм Диффи-Хеллмана используется для того, чтобы две стороны могли создать общий секретный ключ, его еще называют «транспортный ключ», который затем используется для шифрования и дешифрования сообщений. 

❗️Самое главное — этот ключ создается без прямого обмена им между сторонами.

Принцип работы

Алгоритм основан на принципе «сложности вычисления дискретного логарифма». 

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

Пример создания секретного ключа

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

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

2. Алиса генерирует свой секретный ключ a (допустим, 6) и вычисляет свой публичный ключ A: 

   A = g^a mod p = 5^6 mod 23 = 15625 mod 23 = 8.

3. Боб генерирует свой секретный ключ b (допустим, 9) и вычисляет свой публичный ключ B: 

   B = g^b mod p = 5^9 mod 23 = 1953125 mod 23 = 11.

4. Алиса и Боб обмениваются публичными ключами: Алиса отправляет свой ключ A (8) Бобу, а Боб отправляет свой ключ B (11) Алисе.

5. Алиса вычисляет общий секретный ключ s: 

   s = B^a mod p = 11^6 mod 23 = 1771561 mod 23 = 9.

6. Боб вычисляет общий секретный ключ s:

   s = A^b mod p = 8^9 mod 23 = 134217728 mod 23 = 9.

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

Безопасность общения

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

Применение Diffie-Hellman алгоритма

Алгоритм Diffie-Hellman используется во множестве криптографических протоколов и стандартов, таких как:

1. TLS/SSL: Протоколы передачи данных, обеспечивающие защищенное соединение между клиентом и сервером.

2. IPSec: Протокол безопасности для защиты данных, передаваемых через сети, в том числе в VPN-соединениях.

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

Реализация на GoLang

А теперь непосредственно расскажу как я это реализовал, весь код представлен в этом репозитории: https://github.com/vseriousv/diffiehellman.

Начнем с того что я буду использовать Go-Ethereum для генерации приватных и публичных ключей. Такой пакет я уже написал ранее, его можно посмотреть в этом репозитории: https://github.com/vseriousv/blockchainkeys.

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

// Пример функции, которая возвращает пару приватного и публичного ключа  func getKeys() (string, string, error) { bc, err := blockchainkeys.NewBlockchain(blockchainkeys.Ethereum) if err != nil { fmt.Println("Error:", err) return "", "", err }  privateKey, publicKey, _, err := bc.GenerateKeyPair() if err != nil { fmt.Println("Error:", err) return "", "", err }  return privateKey, publicKey, nil }

Сгенерируем пару ключей для Алисы и Боба используя нашу функцию:

// Generation ALisa pair privateAlisa, publicAlisa, err := getKeys() if err != nil { log.Fatal(err) }  // Generation Bob pair privateBob, publicBob, err := getKeys() if err != nil { log.Fatal(err) }

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

func GetTransportKey(publicKey, privateKey string) (string, error) {     // Так как ключи в Ethereum имеют прфик 0x, обрезаем его privateKeyAHex := privateKey[2:]     // Приводим приватный ключ к BigInt privateKeyABigInt, success := new(big.Int).SetString(privateKeyAHex, 16) if !success { return "", errors.New("invalid private key format") }      // Тут тоже обрезаем префикс publicKeyBHex := publicKey[2:]     // Приводим в байтовый формат publicKeyBBytes, err := hex.DecodeString(publicKeyBHex) if err != nil { return "", errors.New("invalid public key format") }     // Далее нам нужно конвертировать байтовый формат в secp256k1 publicKeyB, err := crypto.UnmarshalPubkey(publicKeyBBytes) if err != nil { return "", errors.New("unmarshalling public key failed") }     // магическая функция, которая возвращает нам X и Y координаты элиптической кривой согласно спецификации secp256k1  sharedSecretX, _ := secp256k1.S256().ScalarMult(publicKeyB.X, publicKeyB.Y, privateKeyABigInt.Bytes()) if sharedSecretX == nil { return "", errors.New("scalar multiplication failed") }      // Ну и заветная функция возвращающая нам транспортный ключ transportKey := crypto.Keccak256(sharedSecretX.Bytes()) return hex.EncodeToString(transportKey), nil }

Для того чтобы зашифровать сообщение я написал простые функции с использованием стандартной библиотеки "crypto"в Go. https://pkg.go.dev/crypto/aes

func Encrypt(message, key []byte) ([]byte, error) { // Create a new AES block cipher block, err := aes.NewCipher(key[:32]) if err != nil { return nil, err }  // Create a new GCM encryption mode aead, err := cipher.NewGCM(block) if err != nil { return nil, err }  // Create a random nonce nonce := make([]byte, aead.NonceSize()) if _, err := rand.Read(nonce); err != nil { return nil, err }  // Encrypt the message using a nonce and propagate the tag ciphertext := aead.Seal(nil, nonce, message, nil) ciphertext = append(nonce, ciphertext...) return ciphertext, nil }  func Decrypt(cipherText, key []byte) (string, error) { // Create a new AES block cipher block, err := aes.NewCipher(key[:32]) if err != nil { return "", err }  // Create a new GCM encryption mode aead, err := cipher.NewGCM(block) if err != nil { return "", err }  // Extract the nonce from the encrypted message nonceSize := aead.NonceSize() nonce, ciphertext := cipherText[:nonceSize], cipherText[nonceSize:]  // Decode the message and check the tag plaintext, err := aead.Open(nil, nonce, ciphertext, nil) if err != nil { return "", nil }  return string(plaintext), nil }

Итого имеем, что у Алисы и Боба есть пары ключей и мы теперь можем получить транспортный ключ для Алисы, используя ее приватный ключ и публичный ключ Боба, воспользовавшись нашей функцией GetTransportKey(publicBob, privateAlisa):

// Get transportKey for Alisa, // Alisa has publicKey(Bob) and privateKey(Alisa) transportKeyOne, err := transport_key.GetTransportKey(publicBob, privateAlisa) if err != nil { log.Fatal(err) } log.Println("transportKeyOne", transportKeyOne)

А далее зашифруем наше сообщение полученным транспортным ключом:

// Alisa's encryption message for Bob message := []byte("Hello Bob, I'm Alisa") encryptionMessage, err := encryption.Encrypt(message, []byte(transportKeyOne)) if err != nil { log.Fatal(err) }

Чтобы Бобу расшифровать данное сообщение, ему требуется получить транспортный ключ используя свой приватный ключ и публичный ключ Алисы, используя нашу функцию GetTransportKey(publicAlisa, privateBob)

// Get transportKey for Bob, // Bob has publicKey(Alisa) and privateKey(Bob) transportKeyTwo, err := transport_key.GetTransportKey(publicAlisa, privateBob) if err != nil { log.Fatal(err) } log.Println("transportKeyTwo", transportKeyTwo)

А далее расшифровать сообщение используя наш транспортный ключ Боба:

// Bob decrypt message from Alisa messageResult, err := encryption.Decrypt(encryptionMessage, []byte(transportKeyTwo)) if err != nil { log.Fatal(err) }

В итоге выведем эти сообщения в лог, убедимся, что все работает.

Полный код можно посмотреть в репозитории в директории примера работы.

Всем спасибо за внимание.