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

6.3. Оддий сонларни купайтириш алгоритми

Янада юкори даражадаги химоя методлари бир томонлама (кайтмас) функциядан сирли равишда фойдаланишга асосланади. Бу функция Z параметрли f_Z кайтар функциялар гурухи сифатида олиниб, Z нинг берилган кийматларида E_Z ва D_Z алгоритмларни топиш мумкин. Бу E_Z ва D_Z лар мос равишда аникланиш сохасига тегишли булган барча х лар учун f_Z(x) функцияни ва кийматлар сохасига тегишли булган барча у лар учун f_Z^-1(у) функцияни осонгина хисоблаш имконини беради. Бирок амалда эса, барча Z ва f_Z нинг кийматлар сохасига тегишли барча у лар учун f_Z^-1(у) хисоблаб топиш, хатто E_Z алгоритм маълум булганда хам амалга ошириб булмайдиган ишдир.

Шуларни хисобга олиб, криптомутахассислар Р.Райвист, А.Шамир ва Л.Эйделман 1977 йилда RSA криптосистемасини ишлаб чикдилар ва жамоатчиликка такдим этдилар. Бу системада умумий фойдаланилувчи калит калит (очик калит) мавжуд б¢либ, унда модул сифатида оддий сондан эмас, балки иккита оддий катта сонларнинг к¢пайтмасидан фойдаланилади, яъни бундай холда модул n=pq куринишида акс этади, бу ерда р ва q - оддий катта сонлар. Бу усул берилган маълум n буйича p ва q купайтувчиларни хисоблашнинг мураккаблигига таянади. n сони умумий фойдаланилувчи калитга киради, яъни асосий амал шу модул буйича бажарилади, лекин ахборот кабул килувчи эса бу ахборотларни олиш учун фойдаланаётган p ва q ларни очиб куймайди. Бу оддий сонлар шундай танланиши керакки, бунда p-1 ва q-1 сонлар курсаткичли функция ёрдамида тескари алмаштириш усулидан системани химояни максадида катта кийматли купайтувчилар булиши керак.
Бундай системадан коллектив фойдаланишда хар бир фойдаланувчи узининг шифрлаш-дешифрлаш калитига эга булади. Шифрлаш калити хаммага маълум булади, дешифрлаш калити эса хар бир фойдаланувчининг узида махфий сакланади. Шифрлаш калити n ва e бутун сонлари билан аникланади, дешифрлаш калити эса d бутун сони билан аникланади. Яъни n бу махсус усул билан танлаб олинган иккита катта сонлар p ва q нинг купайтмаси булса, е - ЭКУБ(e, (p-1)(q-1))=1 шартни бажарувчи сон ва d эса de1(mod(p-1)(q-1)) ифоданинг таккослаш ечими.
Агар А фойдаланувчи В фойдаланувчига М маълумотни шифрлаб жунатса, у холда kM^e(mod n) ни хисоблаши керак (бу ерда 0  k  n, (n,e) жуфтлик бу В фойдаланувчининг шифрлаш калити). В фойдаланувчи эса k шифрланган маълумотдан М маълумотни хосил килиш учун Mk ^d(mod n) ни узининг d махфий калити ёрдамида хисоблаши зарур (бу ерда 0  k  n).
n ва е маълум сонлардан d калитни хисоблаш эса сонни p ва q оддий купайтувчиларга булишдек мураккаб масалага эквивалент хисобланади. Бу алгоритмнинг бир томонламалиги хам ана шундадир.