Ани и Боби искат да си изпращат тайни съобщения така, че само те да могат да ги разчетат и да са сигурни, че именно отсрещната страна е изпратила всяко едно съобщение.

Това означава, че те трябва да имат шифър, познат само на тях, който да използват за криптиране и декриптиране на предаваната информация.

Алгоритъмът на Дифи-Хелман (Diffie-Hellman)[1] решава именно това – по сигурен начин две или повече страни да изчислят шифър без той да бъде пренасян. Последното е изключително важно, защото при пренасяне, шифърът може да бъде прочетен от трета страна, която да получи неправомерен достъп до кореспонденцията и дори да фалшифицира съобщенията, които страните си обменят, без те да разберат.

Алгоритъмът има вариант и за повече от две страни, но за максимално улеснение, ще продължа само с две.

Можеш да усетиш интуицията зад алгоритъма чрез следната картинка:

Диаграма, показващ интуицията зад алгоритъма на Дифи-Хелман. Подробно описание може да намериш в следващия абзац.

Ани и Боби се съгласяват открито за общ цвят. Също така, и двамата имат по таен цвят, който никой друг не знае. Чрез смесване на общия и своя таен, всеки получава публичен цвят, който дава на другия. Ани смесва публичния цвят на Боби със своя таен и получава цвят за шифър. Когато Боби направи същото, но с публичния цвят на Ани и с тайния си такъв, ще получи абсолютно същия цвят за шифър.

Нека да видим как на практика се случва това.

Всяка една страна трябва да генерира свой собствен частен ключ (таен цвят), който е просто число и е познат само и единствено на него. Припомням – прости са онези числа, които се делят единствено на себе си и на едно:

    \[\mathbb{P} = \{1,2,3,5,7,11,13,\dots\}\]

Ако се интересуваш защо точно прости числа – остави коментар и ще обясня! 🙂

Да приемем, че се генерирали следните частни ключове:

  • Ани: a = 3 | a \in \mathbb{P};
  • Боби: b = 5 | b \in \mathbb{P}.

Двамата се разбират за две случайни цели числа (съгласувания цвят) – простото p и цялото g, което е между нула и p-1:

    \[\begin{aligned}p &= 7 | p \in \mathbb{P} \\g &= 2 | g \in \{0, 1, 2,\dots, p-1\}\]

Всеки един изчислява своя публичен ключ (публичен цвят) A и B, съставен от g и личния му частен ключ с помощта на малко модулна аритметика (при нея, лявата част делим на дясната и резултатът от операцията е полученият остатък. Пр.: 11 \pmod 7 = 4, защото 11 = \pmb{7}.1 + \pmb{4}) :

    \[\begin{aligned}A &= g^a \pmod p &= 2^3 \pmod 7 &= 8 \pmod 7 = 6 \\B &= g^b \pmod p &= 2^5 \pmod 7 &= 32 \pmod 7 = 4\end{aligned}\]

Ани изпраща публичния си ключ A на Боби, а Боби своя B на Ани.

Сега е моментът, който ще промени играта. Всяка една от страните ще използва публичния ключ (цвят) на другата и своя частен ключ (цвят), за да изчисли (цвета на) шифъра s, който ще се използва за криптиране и декриптиране на предаваната оттук насетне информация:

    \[\begin{aligned}s &= B^a \pmod p &= 4^3 \pmod 7 &= 64 \pmod 7 &= 1\\s &= A^b \pmod p &= 6^5 \pmod 7 &= 7776 \pmod 7 &= 1\\\end{aligned}\]

Забележително е как и двете страни, независимо една от друга получават един и същи шифър. Това е така, защото:

    \[\begin{aligned}A^b \pmod p &= \pmb{(g^a \pmod p)^b \pmod p} \\& \pmb{= (g^b \pmod p)^a \pmod p} \\&= B^a \pmod p\end{aligned}\]

Важно е да се има предвид, че в реалния живот се избират много по-големи стойности за a, b и p, за да бъде трудно на един атакуващ да разбие връзката. Също така стойността следва да расте с развитието на изчислителната мощ на компютрите.

Как се гарантира сигурността на връзката?

Алгоритъмът постига сигурност на връзката по следните 3 начина:

Първият е, че частните ключове са познати само и единствено на една страна. Ани знае единствено своя собствен частен ключ, но не този на Боби, и обратно. Това е и причината, заради която е важно всеки да съхранява частните си ключове сигурно и да не ги предоставя на никого.

Вторият е, че за всяка една кореспонденции се използват различни p и g. Независимо кои са двете страни, независимо дали вече да говорили помежду си, стойностите на двете числа ще бъдат различни в общия случай.

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

Как може да се „разбие“ сигурната връзка?

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

За да се провери дали едно просто число x отговаря на някой от двата частни ключа, е небходимо познатото число g да се повдигне на степен x. Ако резултатът е A или B, то числото е съответният частен ключ a или b:

    \[X = g^{x} | x \in \{1,2,3,\dots, min(a,b)}\}\]

Хората сме опасна работа и очаквано в история са били откривани ефективни начини за отгатване на частните ключове по публичните[2].

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