4 маъруза Мавзу: Криптографиянинг математик асоси

Галуа майдони

Агар p –туб сон бўлса, у ҳолда 0 дан p-1 гача бўлган барча натурал сонлар тўплами {0, 1, 2, …, p-1} элементлари сони p та бўлган чекли майдон ташкил этади ва бу майдон Галуа майдони деб юритилади, ҳамда, GF(p) кўринишда белгиланади. Галуа майдонида қўшиш, айириш, кўпайтириш ва нолдан фарқли бўлган элементга бўлиш амаллари аниқланган. Ҳамда, бу майдонда: қўшиш амалига нисбатан ихтиёрий a GF(p) учун a + 0 = a тенгликни қаноатлантирувчи 0 (ноль) элемент мавжуд; кўпайтириш амалига нисбатан иҳтиёрий a GF(p) учун a ·1 = a тенгликни қаноатлантирувчи 1 (бир) элемент мавжуд; иҳтиёрий нолдан фарқли a GF(p) учун (a·b)mod p =1 тенгликни қаноатлантирувчи b GF(p) элемент мавжуд бўлиб, бу b элемент a элементга тескари элемент дейилади ва деб белгиланади; аниқланган амаллар коммутативлик, ассоциативлик ва дистрибутивлик хоссаларига эга.
Галуа майдони билан боғлиқ бўлган математик тушунча ва тасдиқлар криптографида кенг қўлланилади.
Криптографик масалаларни яна ҳам мураккаблаштириш мақсадида келтирилмайдиган (кўпайтувчиларга ажрамайдиган), коэфициентлари ушбу {0,1,…,q-1} ( бу ерда q –туб сон) тўпламдан бўлган барча n –тартибгача кўпҳадлар тўпламидан фойдаланилади. Бу кўпҳадлар майдони GF(qⁿ) деб белгиланади. Ҳамма амаллар характеристикаси n –тартибли келтирилмайдиган кўпҳад p(x) GF(qⁿ) билан аниқланадиган майдонда бажарилади. Мисол учун, GF(2³) майдон ушбу: 0,1, x, x + 1, x² , x²+1, x²+x, x²+x+1 элементларни ўз ичига олади.
Берилган GF(qⁿ) майдондан олинган p(x) кўпҳаднинг коэффициентлари ўзаро туб бўлса, бу кўпҳад ясовчи бўлади, ҳамда, примитив (содда) дейилади. Примитив кўпҳадлар чизиқли тескари боғлиқликга эга бўлган силжиш регистрлари билан узвий боғлиқликга эга, яъни q=2 бўлганда GF(2ⁿ) майдонда бажариладиган амалларни чизиқли тескари боғлиқликка эга бўлган силжитиш регистларининг аппарат-техник қурилмалари ёрдамида тез бажариш мумкин. Ҳақиқатан ҳам, даражага кўтариш амалини бажариш GF(qⁿ)_q<2 майдондагидан кўра GF(2ⁿ) майдонда самаралидир. Бундан эса GF(2ⁿ) майдонда дискрет логарифмларни ҳисоблашнинг ҳам самарали эканлиги келиб чиқади.
Коэффициентлари иккилик саноқ системаси элементларидан иборат n –тартибгача бўлган барча кўпҳадлар тўплами GF(2ⁿ) –Галуа майдонида модуль - майдон характеристикаси сифатида p(x)=xⁿ+x+1 кўринишдаги уч ҳаддан иборат бўлган n –тартибли примитив кўпҳад олинади. Майдон характеристикасининг бундай танлаб олиниши, яъни xⁿ ва x ҳадлар оралиғидаги: x^n-1 , x^n-2 , …, x² ҳадларнинг йўқлиги модуль бўйича кўпайтириш амалининг самарали бажарилишини таъминлайди. Майдон характеристикасини ифодаловчи p(x)=xⁿ+x+1 кўпҳад примитив бўлмаса, амалларнинг бажарилиши мураккаблашади ҳамда криптографик самарадорликка эришилмайди. Мисол учун, бевосита ҳисоблаш натижасида, n нинг 1000 дан кичик бўлган: 1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900) қийматларида p(x)=xⁿ+x+1 кўпҳад примитивлик хоссасига эга бўлади.

3.