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

Всем привет!

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

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

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

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

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

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

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

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

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

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

Алиса и Боб выбирают общие параметры: основание g (допустим, 5) и большое простое число p (допустим, 23).
Алиса генерирует свой секретный ключ a (допустим, 6) и вычисляет свой публичный ключ A:
A = g^a mod p = 5^6 mod 23 = 15625 mod 23 = 8.
Боб генерирует свой секретный ключ b (допустим, 9) и вычисляет свой публичный ключ B:
B = g^b mod p = 5^9 mod 23 = 1953125 mod 23 = 11.
Алиса и Боб обмениваются публичными ключами: Алиса отправляет свой ключ A (8) Бобу, а Боб отправляет свой ключ B (11) Алисе.
Алиса вычисляет общий секретный ключ s:
s = B^a mod p = 11^6 mod 23 = 1771561 mod 23 = 9.
Боб вычисляет общий секретный ключ 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
}

Скрытый текст

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

Для того чтобы зашифровать сообщение я написал простые функции с использованием стандартной библиотеки "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)
	}

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

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

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