Информация Хавфсизлиги

6.2. Дискрет даражага ошириш алгоритми

Америкалик мутахассислар В. Диффи ва М.Хеллман дискрет даражага ошириш алгоритми тадкик этдилар. Бундай холатда экспоненциал калит алмашиниш q (q-оддий сон) элементдан иборат GF(q) Галуа чекли майдонида курсаткичли функцияни хисоблаш соддалигига (худди шу майдонда логарифмларни хисоблаш кийинлигига нисбатан) асосланади.

Агар y=a^x,1<x<q-1 булса, бу ерда а - GF(q) майдонининг катъий урнатилган элементи, у холда x=log_ay булади. Агар х маълум булса у ни хисоблаш осон кечади. Бунинг учун 2ln(x+y) та купайтириш амалини бажариш талаб килинади. Аксинча, тескари амал - у ни билган холда х ни хисоблаш анча мушкул. Агар q тугри танланган булса, у холда модул буйича логарифмларни хисоблаш га пропорционал хисоблашларни бажаришга тугри келади.
Информация алмашинишда биринчи фойдаланувчи 1, ..., q-1 бутун сонлардан тенг эхтимолликка эга булган х₁ тасодифий сонни танлайди. Фойдаланувчи бу сонни махфий саклайди, бошка фойдаланувчига эса y₁=a^x mod q сонини жунатади. Иккинчи фойдаланувчи хам шундай харакат килади. Натижада улар ни хисоблашлари мумкин. Бунинг учун k₁₂ ни хисоблаб топиш учун биринчи фойдаланувчи y₂ ни х₁ даражага оширади, иккинчи фодаланувчи хам худди шундай йул тутади. Бузгунчи эса х₁ ва х₂ ни билмасдан туриб, у₁ ва у₂ ни билган холда k₁₂ ни хисоблашга харакат килади. Масалан, оддий сон 1000 бит узунликка эга булса, у холда х₁ дан у₁ни хисоблаб чикариш учун 1000 битли сонларни 2000 мартага якин купайтиришга тугри келади. Бошкачасига айтганда, хатто логарифмларни GF(q) майдон остида хисоблаш алгоритмларига эга булганда хам, 2¹⁰⁰10³⁰ та амалларни бажаришига тугри келади.
Бундан куринадики, Диффи ва Хеллманнинг очик калитларни таркатиш системаси химояланмаган каналда хам махфий калитларни ишончли узата олиш имконини берар экан, бирок бу калитларнинг аутентификациясини таъминлаш зарурати пайдо булади. Калитларнинг хамма фойдаланиши мумкин булган справочнигини сакловчи, махфий булмаган у_i очик калит справочникка айнан i-нчи фойдаланувчи томонидан жойлаштирилганлигига, j фойдаланувчи эса y_j калитнинг айнан справочник сакловчидан олинганлигига ишонч хосил килиши лозим. Бошка томондан эса махфий (бир) калитли системаларда Z калит узатилиш жараёнида махфий сакланиши хамда у хакикий жунатувчи томонидан узатилиши лозим.