A11: Chekli maydonda amallar

---

A11: Chekli maydonda amallar. 
Chekli maydonlarda diskret logarifmlash masalasining yechimi murakkabligiga 
asoslangan nosimmetrik shifrlar El Gamal algoritmida kriptotizimning har bir i-
foydalanuvchisiga tub modul r va hosil qiluvchi (generator) g ma’lum hisoblanadi 
va i-foydalanuvchi uchun shaxsiy kalitni ifodalovchi i x -son bo‘yicha 
hisoblanadigan y a p i x i 

mod - ochiq kalit generasiya qilinadi va u barchaga 
oshkor etiladi. Agarda mana shu i - foydalanuvchi bilan biror boshqa j -
foydalanuvchi ochiq ma’lumot M ni shifrmatnga o‘girilgan holda axborot 
almashuvini amalga oshirmoqchi bo‘lsa, u holda j -foydalanuvchi r sonidan kichik 
bo‘lgan biror k -sonini tanlab olib (mod ) 1 y g p k 

va ( / )(mod ) y2 M y p k 

, 
sonlarini hisoblaydi. So‘ngra j -foydalanuvchi (y1;y2) ma’lumotlarini i - 
foydalanuvchiga jo‘natadi. O‘z navbatida i -foydalanuvchi bu shifrlangan 
ma’lumotni qabul qilib, quyidagicha y y p M x ( 1 

2 )mod 

hisoblash bilan ochiq 
ma’lumotni tiklaydi. El Gamal kriptoalgoritmiga asoslangan kriptotizimning har bir 
i - foydalanuvchisi uchun 


i i y , x - kalitlar juftligi quyidagicha yaratilishi ham 
mumkin: biror pi -tub soni va gi 

pi - tengsizlikni qanoatlantiruvchi gi 
(foydalanuvchilar guruhi uchun umumiy p va g 

p tengsizlikni qanoatlantiruvchi g 
) sonlari tanlanadi. Ushbu i pi x 

tengsizlikni qanoatlantiruvchi maxfiy bo‘lgan i x 
- soni bo‘yicha ochiq deb e’lon qilinadigan i y -soni ushbu formula (mod ) i x yi gi 
p 

i (foydalanuvchilar guruhi uchun xi 

p hamda y g p i x i 

mod ) orqali 
hisoblanadi. Shunday qilib, El Gamal kritotizimida 


i i i p , g , y – uchlik 
(foydalanuvchilar guruhi uchun p va g umumiy bo‘lib, 


i p, g, y ) – uchlik ) ochiq 

---

kalit, i x - esa maxfiy (shaxsiy) kalit deb olinadi. Shundan so‘ng i-foydalanuvchidan 
j - foydalanuvchiga shifrlangan ma’lumotni jo‘natish quyidagicha amalga oshiriladi: 
Shifrlash qoidasi: ushbu ifoda j k a j 

g j mod p , j k bj 

y j M mod p 
(foydalanuvchilar guruhi uchun p va g umumiy bo‘lganda: a g p k 

mod , b y M p 
k 

j mod ) hisoblanadi, bu yerda M - ochiq ma’lumot, k - ma’lumotni shifrlab 
jo‘natuvchi tomonidan tanlangan tasodifiy son bo‘lib, u ( p j 

1 ) –soni bilan o‘zaro 
tub, 

a j ,bj


C ( p va g umumiy bo‘lganda 

a,b


C–shifrlangan ma’lumot); 2.
Deshifrlash qoidasi: p M a b x j j j j mod 

( p va g umumiy bo‘lganda: p M a b j x 
mod 

), haqiqatan ham, x j j j p a b j mod kx j j x k j p g g M i i 

mod 

M ( p va 
g umumiy bo‘lganda: p 

a b j x mod p 

a y M j x k j mod p g g M j j kx x k mod = 
M mod p 

M , chunki M 

p ). Kriptotizimning har bir i-foydalanuvchisi uchun 
ochiq va maxfiy kalitlarni i x - soni ma’lum bo‘lganda i x yi gi p 

i mod 
(foydalanuvchilar guruhi uchun xi 

p hamda y g p i x i 

mod ) tenglik bo‘yicha 
generasiya qilinadi. Ammo i x - soni foydalanuvchilarga noma’lum bo‘lganda, ochiq 
kalitni ifodalovchi i x yi gi p 

i mod tenglikdan log (mod ) i g i pi x y i 

- sonini 
topish, chekli maydon xarakteristikasi pi yetarli katta bo‘lganda, murakkablashadi 
va bugungi kunda chekli maydonlarda logarifmlash masalasi yechimining rasional 
(samarali) usullari mavjud emas. da xarakteristikasi katta bo‘lgan chekli 
maydonlarda diskret logarifmlashning ba’zi usullari keltirilgan.
Chekli maydon mavjud bo‘lishi uchun maydonning elementlari sonini 
ifodalovchi q-tub son bo‘lishi yoki tub sonning darajasi q=p m , bu yerda p - tub son, 
m - natural son ko‘rinishida ifodalanashi zarur va yetarli. Bunda p - tub son GF(q) - 

---

chekli maydonning xarakteristikasi, m soni GF(q) maydonning GF(p) qism 
maydonga nisbatan darajasi deyiladi hamda m=1 bo‘lsa, oddiy, aks holda 
kengaytirilgan maydon deyiladi. Agar p - tub son bo‘lmasa, u holda - algebraik 
tuzilmada aniqlangan qo‘shish va ko‘paytirish amallari biror n-asosli modul (mod 
n) bo‘yicha aniqlangan bo‘lsa, hatto noldan farqli elementga bo‘lish har doim ham 
mumkin bo‘lavermaydi va bu tuzilma maydon tashkil etmay halqa tashkil etadi. Har 
qanday maydonning barcha elementlari to‘plami qo‘shish amaliga ko‘ra additiv 
Abel gruppasini va noldan farqli barcha elementlari to‘plami ko‘paytirish amaliga 
nisbatan multiplikativ siklik gruppa tashkil etadi. Mumkin bo‘lgan har bir q – tartib 
uchun faqat bitta maydon mavjud, ya’ni barcha q – tartibli chekli maydonlar 
izomorfdir. Misol uchun, agarda q=p – tub son bo‘lsa, u holda maydonning 
elementlari 0, 1, ..., (p-1) – sonlar bo‘lib, qo‘shish va ko‘paytirish amallari mod p 
qo‘shish va ko‘paytirish amallaridan iborat, ya’ni GF(p)=Z/p. Shunday qilib, tub 
sonli modul bo‘yicha chegirmalar halqasi oddiy maydon tashkil etadi. 2-tasdiq. 
Ixtiyoriy GF(q) - chekli maydonning noldan farqli elementlari multiplikativ siklik 
gruppa tashkil etadi.
ta’rif. Siklik gruppaning 

- yasovchisi (tuzuvchisi, generatori) chekli maydonning 
primitiv elementi deyiladi hamda bu maydonning barcha elementlarini quyidagicha 
ifodalash mumkin:
Ta’rif. Ď – chekli, ya’ni n ta elementdan iborat butun sonlar maydoni ustida 
aniqlangan kvadrat diamatrisalar chekli to‘plami, Ώ = {+, ®’} – Ď ustida aniqlangan 
algebraik amallar to‘plami bo‘lsa, – juftlik diamatrisalar algebrasi deb ataladi; bu 
yerda o‘zaro mos tarzda + – qo‘shish, ®’ – diamatrisaviy ko‘paytirish amallarining 

---

belgilaridir. Mazkur takomillashgan diamatrisalar algebrasida keltirilgan algebradan 
amallar chekli to‘plam ustida berilgan diamatrisalar to‘plami ustida aniqlanishi, 
barcha amallar diamatrisalar to‘plami ustida aniqlanib diamatrisa hosil etilishi bilan 
farqlanadi.
Nazorat savollari 
1. Chekli maydon nimadan iborat. 
2. Chekli maydon bosqichlarini keltirib o’ting.