Диффие-Хеллман: Генијални алгоритам иза сигурне мрежне комуникације

Почнимо са брзим мисаоним експериментом.

Имате мрежу од 3 рачунара, које користе Алице, Боб и Цхарлие. Сва 3 учесника могу да шаљу поруке, али само на начин да је могу читати сви остали клијенти који су се повезали на мрежу. Ово је једини могући облик комуникације између учесника.

Ако Алице пошаље поруку путем жица, добиће је и Боб и Цхарлие. Другим речима, Алице не може послати директну поруку Бобу, а да је ни Цхарлие није примио.

Али Алице жели да пошаље поверљиву поруку Бобу и не жели да је Цхарлие може прочитати.

Чини се немогућим са овим строгим правилима, зар не? Лепа ствар коју су овај проблем 1976. године решили Вхитфиелд Диффие и Мартин Хеллман.

Ово је поједностављена верзија стварног света, али ми се суочавамо са истим проблемом када комуницирамо кроз највећу мрежу која је икада постојала.

Обично нисте директно повезани са Интернетом, али сте део локалне мање мреже, која се назива Етхернет.

Ова мања мрежа може бити жичана или бежична (Ви-Фи), али основни концепт остаје. Ако сигнал шаљете мрежом, овај сигнал могу да читају сви други клијенти повезани на исту мрежу.

Једном када на сервер банке пошаљете поруку са подацима о кредитној картици, сви остали клијенти у локалној мрежи ће добити поруку, укључујући рутер. Затим ће га проследити стварном серверу банке. Сви остали клијенти ће поруку игнорисати.

Али шта ако у мрежи постоји злонамерни клијент који неће игнорисати ваше поверљиве поруке, већ ће их уместо тога прочитати? Како је могуће да још увек имате новац на свом банковном рачуну?

Шифровање

У овом тренутку је сасвим јасно да морамо да користимо неку врсту шифрирања да бисмо били сигурни да је порука читљива за Алице и Боб, али за Цхарлие потпуну бесмислицу.

Шифровање информација врши се алгоритмом шифровања, који узима кључ (на пример низ) и враћа шифровану вредност, звану шифровани текст. Шифротекст је само низ потпуно случајног изгледа.

Важно је да се шифрована вредност (шифрирани текст) може дешифровати само оригиналним кључем. То се назива алгоритам симетричног кључа јер вам за дешифровање поруке треба исти кључ са којим је шифрована. Постоје и алгоритми са асиметричним кључем, али они нам тренутно нису потребни.

Да бисмо ово лакше разумели, ево лажног алгоритма за шифровање имплементираног у ЈаваСцрипт:

function encrypt(message, key) { return message.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode+key.length) }).join(""); }

У овој функцији пресликао сам сваки знак у други знак на основу дужине датог кључа.

Сваки знак има целобројни приказ, који се назива АСЦИИ код. Постоји речник који садржи све знакове са својим кодом, а зове се АСЦИИ табела. Тако смо повећали овај цели број за дужину кључа:

Дешифровање шифрованог текста је прилично слично. Али, уместо сабирања, одузимамо дужину кључа од сваког знака у шифреном тексту, па враћамо оригиналну поруку.

function decrypt(cipher, key) { return cipher.split("").map(character => { const characterAsciiCode = character.charCodeAt(0) return String.fromCharCode(characterAsciiCode-key.length) }).join(""); }

Коначно, овде је лажно шифровање на делу:

const message = "Hi Bob, here is a confidential message!"; const key = "password"; const cipher = encrypt(message, key); console.log("Encrypted message:", cipher); // Encrypted message: Pq(Jwj4(pmzm(q{(i(kwvnqlmv|qit(um{{iom) const decryptedMessage = decrypt(cipher, key); console.log("Decrypted message:", decryptedMessage); // Decrypted message: Hi Bob, here is a confidential message!

Применили смо одређени степен шифровања на поруку, али овај алгоритам био је користан само у демонстрацијске сврхе да би стекао осећај како се понашају алгоритми за шифровање са симетричним кључем.

Постоји неколико проблема са овом имплементацијом, осим лошег руковања угловним случајевима и типовима параметара.

Пре свега, сваки кључ дуг 8 знакова може дешифровати поруку која је шифрована кључем „лозинка“. Желимо да алгоритам шифровања може дешифровати поруку само ако јој дамо исти кључ којим је шифрована. Брава на вратима коју може отворити сваки други кључ није толико корисна.

Друго, логика је преједноставна - сваки знак се помера за исти износ у АСЦИИ табели, што је превише предвидљиво. Треба нам нешто сложеније да бисмо отежали откривање поруке без кључа.

Треће, не постоји минимална дужина кључа. Савремени алгоритми раде са најмање 128 битних дугих тастера (~ 16 знакова). Ово значајно повећава број могућих кључева, а самим тим и сигурност шифрирања.

На крају, потребно је премало времена за шифровање или дешифровање поруке. Ово је проблем јер не треба превише времена да испробате све могуће кључеве и разбијете шифровану поруку.

Ово је паралелно са дужином кључа: Алгоритам је сигуран ако ја као нападач желим да пронађем кључ, тада морам да испробам велики број комбинација кључева и потребно је релативно дуго времена да покушам једну комбинацију.

Постоји широк спектар симетричних алгоритама за шифровање који су се бавили свим овим тврдњама, често коришћени заједно како би се пронашао добар однос брзине и сигурности у свакој ситуацији.

Популарнији алгоритми са симетричним кључем су Твофисх, Серпент, АЕС (Ријндаел), Бловфисх, ЦАСТ5, РЦ4, ТДЕС и ИДЕА.

Ако желите да сазнате више о криптографији уопште, погледајте овај разговор.

Размена кључева

Изгледа да смо смањили првобитни простор проблема. Шифровањем можемо створити поруку која је значајна за странке које испуњавају услове за читање информација, али која је нечитљива за друге.

Када Алице жели да напише поверљиву поруку, изабрала би кључ и њиме шифрирала своју поруку и послала шифровани текст кроз жице. И Боб и Цхарлие би добили шифровану поруку, али нико од њих није могао да је протумачи без Алисиног кључа.

Сада је једино питање на које треба одговорити како Алице и Боб могу да пронађу заједнички кључ само комуницирањем путем мреже и спрече Чарлија да сазна тај исти кључ.

Ако Алице пошаље свој кључ директно преко жица, Цхарлие би га пресрео и могао би дешифрирати све Алицеине поруке. Дакле, ово није решење. То се у рачунарским наукама назива кључним проблемом размене.

Размена кључева Диффие – Хеллман

Овај кул алгоритам пружа начин генерисања заједничког кључа између две особе на такав начин да се кључ не може видети посматрањем комуникације.

Као први корак, рећи ћемо да постоји огроман прост број, познат свим учесницима, то је јавна информација. Зовемо га „п“ или модул .

There is also another public number called "g" or base,which is less than p.

Don't worry about how these numbers are generated. For the sake of simplicity let's just say Alice picks a very big prime number (p) and a number which is considerably less than p. She then sends them through the wires without any encryption, so all participants will know these numbers.

Example: To understand this through an example, we'll use small numbers. Let's say p=23 and g=5.

As a second step both Alice (a) and Bob (b) will pick a secret number, which they won't tell anybody, it's just locally living in their computers.

Example:Let's say Alice picked 4 (a=4), and Bob picked 3 (b=3).

As a next step, they will do some math on their secret numbers, they will calculate:

  1. the base (g) in the power of their secret number,
  2. and take the calculated number's modulo to p.
  3. Call the result A (for Alice) and B (for Bob).

Modulo is a simple mathematical statement, and we use it to find the remainder after dividing one number by another. Here is an example: 23 mod 4 = 3, because 23/4 is 5 and 3 remains.

Maybe it's easier to see all of this in code:

// base const g = 5; // modulus const p = 23; // Alice's randomly picked number const a = 4; // Alice's calculated value const A = Math.pow(g, a)%p; // Do the same for Bob const b = 3; const B = Math.pow(g, b)%p; console.log("Alice's calculated value (A):", A); // Alice's calculated value (A): 4 console.log("Bob's calculated value (B):", B); // Bob's calculated value (B): 10

Now both Alice and Bob will send their calculated values (A, B) through the network, so all participants will know them.

As a last step Alice and Bob will take each other's calculated values and do the following:

  1. Alice will take Bob's calculated value (B) in the power of his secret number (a),
  2. and calculate this number's modulo to p and will call the result s (secret).
  3. Bob will do the same but with Alice's calculated value (A), and his secret number (b).

At this point, they successfully generated a common secret (s), even if it's hard to see right now. We will explore this in more detail in a second.

In code:

// Alice calculate the common secret const secretOfAlice = Math.pow(B, a)%p; console.log("Alice's calculated secret:", secretOfAlice); // Alice's calculated secret: 18 // Bob will calculate const secretOfBob = Math.pow(A, b)%p; console.log("Bob's calculated secret:", secretOfBob); // Bob's calculated secret: 18

As you can see both Alice and Bob got the number 18, which they can use as a key to encrypt messages. It seems magic at this point, but it's just some math.

Let's see why they got the same number by splitting up the calculations into elementary pieces:

In the last step, we used a modulo arithmetic identity and its distributive properties to simplify nested modulo statements.

So Alice and Bob have the same key, but let's see what Charlie saw from all of this. We know that p and g are public numbers, available for everyone.

We also know that Alice and Bob sent their calculated values (A, B) through the network, so that can be also caught by Charlie.

Charlie knows almost all parameters of this equation, just a and b remain hidden. To stay with the example, if he knows that A is 4 and p is 23, g to the power of a can be 4, 27, 50, 73, ... and infinite other numbers which result in 4 in the modulo space.

He also knows that only the subset of these numbers are possible options because not all numbers are an exponent of 5 (g), but this is still an infinite number of options to try.

This doesn't seem too secure with small numbers. But at the beginning I said that p is a really large number, often 2000 or 4000 bits long. This makes it almost impossible to guess the value of a or b in the real world.

The common key Alice and Bob both possess only can be generated by knowing a or b, besides the information that traveled through the network.

If you're more visual, here is a great diagram shows this whole process by mixing buckets of paint instead of numbers.

Here p and g shared constants represented by the yellow "Common paint". Secret numbers of Alice and Bob (a, b) is "Secret colours", and "Common secret" is what we called s.

This is a great analogy because it's representing the irreversibility of the modulo operation. As mixed paints can't be unmixed to their original components, the result of a modulo operation can't be reversed.

Summary

Now the original problem can be solved by encrypting messages using a shared key, which was exchanged with the Diffie-Hellman algorithm.

With this Alice and Bob can communicate securely, and Charlie cannot read their messages even if he is part of the same network.

Хвала што сте прочитали оволико далеко! Надам се да сте добили неку вредност из овог поста и да сте разумели неке делове овог занимљивог комуникационог тока.

Ако је било тешко пратити математику овог објашњења, ево сјајног видео снимка који ће вам помоћи да разумете алгоритам без математике, са вишег нивоа.

Ако вам се свидео овај пост, можда ћете желети да ме пратите на Твиттер-у да бисте пронашли неке узбудљивије ресурсе о програмирању и развоју софтвера.