Всем привет!
Давно хотел опубликовать статью тут, но никак не находил повода для хорошей темы. Однако я уже давно веду телеграм канал по 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
}
Hidden text
Я дико извиняюсь, что приходится очень поверхностно описывать процедуры работы с элиптическими кривыми и как устроены алгоритмы криптографии в блокчейне, посколько иначе эта статья превратиться в длиннопост. Однако в будущем я попробую написать статью про спецификацию 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)
}
В итоге выведем эти сообщения в лог, убедимся, что все работает.
![Результат вывода функции Результат вывода функции](https://webcf.waybackmachine.org/web/20230519064647im_/https://habrastorage.org/getpro/habr/upload_files/69b/f42/781/69bf42781c4b8d61bc2f185eb26410b0.png)
Полный код можно посмотреть в репозитории в директории примера работы.
Всем спасибо за внимание.