Diffi–Xellman kalit almashish algoritmi

Ikki tomon hech qachon uchrashmasdan, hamma tinglab turgan ochiq kanalda umumiy maxfiy kalit kelishib olishi mumkinmi? 1976 yilgacha bu imkonsiz deb hisoblangan. Diffi–Xellman algoritmi shifrlash yoki imzo uchun emas, aynan simmetrik kalitni hosil qilish uchun ishlatiladi.

Mualliflar: W. Diffie, M. Hellman (R. Merkle)Yil: 1976Asos: diskret logarifm

Bo'yoq aralashtirish o'xshatishi

✏️ Sodda tilda

Bo'yoqlarni aralashtirish oson, lekin aralashmani qayta ajratish imkonsiz. Ali va Vali ochiqchasiga umumiy sariq rangni kelishadi. Ali o'zining sirli qizil rangini qo'shib, to'q sariq aralashmani Valiga yuboradi. Vali o'zining sirli ko'k rangini qo'shib, yashil aralashmani Aliga yuboradi. Endi har biri olgan aralashmaga o'z sirli rangini qo'shadi — ikkalasida ham bir xil jigarrang hosil bo'ladi! Tinglovchi sariq, to'q sariq va yashilni ko'rdi, lekin jigarrangni hosil qila olmaydi.

Ali

umumiy + sirli

= yuboradi

Ochiq kanal (tinglovchi)

ko'radi

… lekin umumiy rangni hosil qila olmaydi

Vali

umumiy + sirli

= yuboradi

Har ikkalasida natija: umumiy sir

Algoritm

Oldindan ochiq kelishiladi: katta tub son n va g < n (darajalari n modul bo'yicha qisqa siklga tushmaydigan — yasovchi).

A tomonOchiq kanalB tomon

x ni tanlaydi (sir)y ni tanlaydi (sir)

A = gˣ mod nA

BB = gʸ mod n

K = Bˣ mod nK = Aʸ mod n

K = Bˣ = (gʸ)ˣ = g^xy = (gˣ)ʸ = Aʸ (mod n)

📜 Tarix

Uitfild Diffi va Martin Xellman 1976 yil noyabrida «New Directions in Cryptography» maqolasini chop etdi. 2002 yilda Xellman Ralf Merklning hissasi katta bo'lgani uchun algoritmni Diffi–Xellman–Merkl deb atash kerakligini aytgan. 2015 yilda Diffi va Xellman «hisoblash fanining Nobel mukofoti» — Tyuring mukofotiga sazovor bo'lishdi.

⚠ Zaif tomoni: o'rtadagi odam

Algoritm tomonlarni autentifikatsiya qilmaydi. Agar hujumchi kanalni tinglabgina qolmay, xabarlarni almashtira olsa, u A bilan ham, B bilan ham alohida kalit kelishib, o'rtada turib barcha xabarlarni o'qiydi. Shuning uchun TLS da DH qiymatlari sertifikat bilan imzolanadi. Algoritmdan uch va undan ortiq tomon uchun ham foydalanish mumkin.