logo
  1. Bosh sahifa
  2. Diplom ishlar
  3. Umumiy
  4. Kombinatorika va kiriptografiya masalalari

Kombinatorika va kiriptografiya masalalari

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

593.955078125 KB
Ko'chirib olish
1 Mavzu: “Kombinatorika va kiriptografiya masalalari” MUNDARIJA KIRISH ............................................................................................................ 2 I Bob KOMBINATORIKA ASOSLARI. ....................................................... 4 1.1 Kombinatorikaning asosiy tushunchalari. ................................................. 4 1.2.Kombinatorik masalalar va tartiblangan to’plamlar. .......................... 7 1.3.Kombinatorikaning ehtimollar nazariyasiga tadbiqlari. ........................... 9 II BOB. KIRIPTOGRAFIYA TARIXI ......................................................... 12 2.1 Dastlabki kiriptografiya ........................................................................... 12 2.2. Formal kiriptografiya ....................................................................... 17 2.3. Ilmiy kiriptografiya ................................................................................ 19 2.4 . Kompyuter kriptografiyasi davri ........................................................... 20 2.5 Simmetrik kriptotizimlar ......................................................................... 20 2.6 Nosimmetrik kriptotizimlar ..................................................................... 21 XULOSA ....................................................................................................... 24 ADABIYOTLAR RO’YXATI ...................................................................... 25 ILOVALAR ................................................................................................... 26 ILOVA 1. ....................................................................................................... 26 2 KIRISH Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog‘liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo‘yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O‘z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo‘yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko‘proq shaxsning ijobiy o‘zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo‘llarini (matematik statistika o‘rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo‘l keladi. Ehtimollar nazariyasi va matematik statistikani o‘rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo‘lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo‘lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to‘g‘risida mulohazalar» nomli kitobida birinchi marta qo‘llagan edi. Hozirgi vaqtda kombinatorik usullar informatsiya nazariyasi muammolarini, chiziqli dasturlash masalalarini yechishda, transport masalalarini yechish uchun va h.k.larni hal qilishda keng qo‘llanilmoqda. Kombinatorik masalalar nafaqat matematika go‘zalligini ko‘rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko‘rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko‘pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Uslubiy qo‘llanmada matematika o‘qitishda kombinatorika elementlarini o‘rganish samaradorligini oshirish maqsadida kombinatorika fanining asosiy 5 tushunchalari, kombinatorika elementlarini o‘rganish xususiyatlari, o‘qitish jarayonida kombinatorika elementlarini o‘rgatish bilan birga o‘quvchilarning ijodiy faolligini oshirish bo‘yicha uslubiy tavsiyalar bayon etilgan. Axborotni muhofaza qilish masalalari bilan kriptologiya fani shug‘ullanadi. Keyingi oxirigi yillarda kriptologiya yo‘nalishini rivojlantirishga davlatimiz tomonidan katta ahamiyat berilmoqda. O‘zbekiston Respublikasi Prezidentining 2007 yil 3 aprelda qabul qilgan “O‘zbekiston Respublikasida axborotning kriptografik himoyasini tashkil etish chora-tadbirlari to‘g‘risida” gi PQ-614–son 5 qarorida hamda O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi “O‘zbekiston Respublikasini yanada rivojlantirish bo‘yicha Harakatlar strategiyasi to‘g‘risida” gi PF-4947-son farmoyishida beshta ustuvor yo‘nalishdan biri sifatida axborotni muhofaza qilish tizimini takomillashtirish, axborot sohasidagi tahdidlarga o‘z vaqtida va munosib qarshilik ko‘rsatish kabilar ko‘zda tutilgan. Mazkur qaror va farmoyishning asosiy vazifalaridan biri axborotni muhofaza qilish 3sohasida yuqori malakali kadrlarni tayyorlashdan iborat bo‘lib, buning uchun axborot xavfsizligi va kriptografiya yo‘nalishida davlat tilida ta’lim olayotgan talabalar, tadqiqotchilar va ilmiy xodimlar uchun mo‘ljallangan o‘quv qo‘llanmalar, darsliklar, uslubiy qo‘llanmalar va kitoblar ishlab chiqish muhim ahamiyat kasb etadi. Taqdim etilayotgan o‘quv qo‘llanma ana shu sohada bajarilgan ishlardan biri hisoblanadi. Ushbu o‘quv qo‘llanma axborot xavfsizligi va kriptografiya yo‘nalishida ta’lim olayotgan magistrlar uchun mo‘ljallangan. Shuningdek ushbu o‘quv qo‘llanmadan axborot xavfsizligi yo‘nalishida bakalavrlar tayyorlash jarayonida hamda kriptografiya yo‘nalishida ilmiy-tadqiqot olib borayotgan tadqiqotchilar, ilmiy xodimlar va soha mutaxassislari foydalanishlari mumkin. 4I Bob KOMBINATORIKA ASOSLARI. 1.1 Kombinatorikaning asosiy tushunchalari. Ta’rif. Kombinatorika – ma’lum xossalarga ega bo‘lgan elementlarning turli kombinatsiyalarini o‘rganuvchi matematikaning bo‘limi. Kombinatorikaning asosiy masalasi – berilgan ob’ektlardan u yoki bu shartlarga bo‘ysunuvchi bir nechta turli kombinatsiyalari tuzish mumkin. To‘plamlardan farqli elmentlar kombinatsiyalari bir xil (takroriy) elementlarni o‘z ichiga olishi mumkin Kombinatorik masalalarni yechishda ko‘pincha ikkita asosiy qoida qo‘llaniladi. Qo‘shish qoidasi: Agar biror a elementni t ta usul bilan, ikkinchi b elementni – p ta usul bilan tanlash mumkin bo‘lsa, u holda a yoki b elementni (t+p) ta usul bilan tanlash mumkin. Qo‘shish qoidasidan foydalanishda A ob’ektni tanlashning hech qanday usuli B ob’ektni tanlash usuli bilan ustma-ust tushmasligi kerak. Agar bunday ustma-ust tushishlar bo‘lsa, u holda qo‘shish qoidasi o‘z kuchini yo‘qotadi va faqat tanlashning (m+n-k) ta usulini olish mumkin, bu erda k- ustma-ust tushishlar soni. Ko‘paytirish qoidasi: Agar biror a elementni t ta usul bilan, ikkinchi b elementni – p ta usul bilan tanlash mumkin bo‘lsa, u holda a va b elementni tp ta usul bilan tanlash mumkin. Qo‘shish va ko‘paytirish qoidalari ixtiyoriy sondagi chekli elementlar uchun o‘rinli. Masalalar 1. p ta turli raqamdan nechta turli p xonali son tuzish mumkin? Yechish . Bitta raqam (1) dan faqat bitta bir xonali son olish mumkin: 1. Ikkita raqamdan (1 va 2) 2 ta ikki xonali son olish mumknim: 12 va 21. Buni quyidagicha hosil qilish mumkin: oldingi holdagi 1 soni o‘ng va chap tarafiga 2 raqamini yozish bilan hosil qilish mumkin, ya’ni oldingi holni 2 ga ko‘paytirish lozim (1·2). 3 ta raqam (1,2 va 3) dan 6 ta uch xonali son olish mumkin: 312, 132, 123, 321, 231, 213. Buni quyidagicha hosil qilish mumkin: oldingi holdagi har bir ikki xonali son o‘ng, chap tarafiga va o‘rtasigav 3 raqamini yozish bilan hosil qilish mumkin, ya’ni oldingi holni 3 ko‘paytirish lozim (1·2·3). Qiyin emaski, bunda quyidagi qonuniyatni sezish mumkin: har bir navbatdagi holda javob oldingisiga qaganda p marta ortiq bo‘ladi. Ixtiyoriy p soni uchun formula olamiz: 1·2·3·...·(n-1)·n. Javob : 1·2·3·...·(n-1)·n Ta’rif. 1 dan p gacha barcha natural sonlar ko‘paytmasi p-faktorial deb ataladi va p! deb belgilanadi. Shunday qilib: p!=1·2·3·… ·p. 0!=1 deb hisoblanadi. Manfiy sonning faktoriali mavjud emas. Faktorialning asosiy xossasi: p!=(p-1)!p 5Tarixiy ma’lumot. Ba’zi kombinatorik masalalarni yechish bilan qadimgi Xitoyda, keyinchalik Rim imperiyasi davrida ham shug‘ullanganlar. Lekin matematikaning mustaqil bo‘limi sifatida faqat ehtimollar nazariyasi fani rivoji tufayli Evropada 18 asrdan boshlab tan olindi. 1.Guruhda 20 ta qiz va 5 ta o‘g‘il bola bor. Sardorni necha xil usul bilan tanlash mumkin ? Yechish: Sardor sifatida 20 ta qizdan biri yoki 5 ta o‘g‘il boladan biri tanlanishi mumkin, demak, sardorni saylashning umumiy soni 20+5=25. 2.Maktabda 76 o‘qituvchi ishlaydi. Ulardan 49 tasi ingliz tilini, 32 tasi nemis tilini va 15 nafari ikkala tilni ham biladi. Necha o‘qituvchi na ingliz tilini, na nemis tilini biladi? Yechish: Ingliz yoki nemis tilini 49+32–15=66 nafar o‘qituvchi biladi. Demak, bu ikkala tildan birortasini ham 76–66=10 o‘qituvchi bilmaydi. 3.Guruhda 30 kishi bor. Sardor va yoshlar ittifoqi etakchisini saylash lozim. Buni necha xil usul bilan amalga oshirish mumkin? Yechish: Sardor bo‘lib 30 o‘quvchidan ixtiyoriysi saylanishi mumkin, ya’ni sardorni tanlashning 30 ta usuli mavjud. Sardor saylangandan so‘ng qolgan 29 o‘quvchidan yoshlar yetakchisini saylab olish mumkin. Shunday qilib, sardornin saylashning bir usuliga yoshlar etakchisini tanlashning 29 usuli mos keladi. Demak, sardor va yoshlar etakchisini tanlashning umumiy soni 30·29=870 ga teng. 4. Agar raqamlar takrorlanishi mumkin bo‘lsa, 0,1,2,3,4,5,6 raqamlaridan nechta uch xonali juft son tuzish mumkin? Yechish: abc uch xonali sonni tuzishda berilgan raqamlardan a ning o‘rniga noldan tashqari, ixtiyoriy raqamni olish (6 ta imkoniyat), b ning o‘rniga ulardan ixtiyoriysini olish mumkin (7 imkoniyat), c ning o‘rniga 0,2,4,6 raqamlardan ixtiyoriysini olish mumkin (4 imkoniyat). Shunday qilib, ko‘paytirish qoidasiga ko‘ra masala shartini qanoatlantiruvchi sonni tuzishning 6 ·7·4=168 ta usuli mavjud ekan. 5. 1-navli 20 ta va 2-navli 30 ta buyum bor. Bir navdagi ikkita buyumni tanlash lozim. Buni necha xil usul bilan bajarish mumkin? Yechish: Ko‘paytirish qodisaga ko‘ra 1-navli 2 ta buyumni 20 ·19=380 usul bilan tanlash mumkin. Shunga o‘xshash 2-navli 2 ta buyumni 30 ·29=870 usuli bilan tanlash mumkin. Masala shartigi ko‘ra bir xil navli ikkita buyumni tanlash lozim bo‘lgani uchun, qaysi navdan bo‘lishi muhim emas, bir xil navli 2 ta buyumni tanlashning umumiy soni 380+870=1250 ga teng bo‘ladi. 6. Agar raqamlar takrorlanishi mumkin bo‘lsa 0,1,2,3, raqamlaridan nechta bir xonali, ikki xonali va uch xonali juft sonlar tuzish mumkin? Yechish: Ravshanki, berilgan raqamlardan faqat bitta birxonali juft son tuzish mumkin–2. Berilgan raqamlardan ikki xonali ab sonni tuzishda a ning o‘rniga noldan tashqari ixtiyoriy raqamni olish mumkin (3 imkoniyat), b ning o‘rniga 0 va 2 raqamlaridan ixtiyoriy raqamni olish mumkin (2 ta imknoiyat). Shunday qilib, ko‘paytirish qoidasiga asosan bizga kerak bo‘lgan sonni tuzishning 3 ·2=6 ta usuli mavjud. 6 Berilgan raqamlardan uch xonali abc sonni tuzishda a ning o‘rniga noldan tashqari ixtiyoriy raqamni olish mumkin (3 imkoniyat), b ning o‘rniga ulardan ixtiyoriysini olish mumkin (4 imkoniyat), c ning o‘rniga 0 va 2 raqamlaridan ixtiyoriy raqamni olish mumkin (2 ta imknoiyat). Shunday qilib, ko‘paytirish qoidasiga asosan bizga kerak bo‘lgan sonni tuzishning 3·4·2=24 ta usuli mavjud ekan. Qo‘shish qoidasini qo‘llab: 1+6+24=31 ga ega bo‘lamiz. Figurali sonlar: Qadimda hisoblashlarni osonlashtirish uchun toshlardan foydalanganlar. Bunda asosiy e’tibor muntazam figura shaklida tavsirlash mumkin bo‘lgan toshlar soniga qaratilar edi. Shunday qilib kvadrat sonlar (1,4,16,25,…) paydo bo‘ldi. Masalan: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2*2=22=4, 3*3=32=9, 4*4=42=16, Ixtiyoriy p-chi tartibli kvadrat son N=n2 formula bo‘yicha hisoblanadi. Uchburchak sonlar (1, 3, 6, 10,15, . . .) va beshburchak (1, 5, 12,22, ) sonlar ham tuzilgan. Masalalar. 1.Yettinchi tartibli: 1) kvadrat sonni; 2) uchburchak sonni; 3) beshburchak sonni toping. Yechish: 1) N=n2 formulaga ko‘ra n=7 da N=72=49. 2) N=n(n+1)/2 formulaga ko‘ra n=7 da N=7*(7+1)/2=28. 3) N=n+3*(n-1)/2 formulaga ko‘ra n=7 da N =7+3*7*(7-1)/2=70. 2. n-chi tartibli kvadrat sonni yozing: 1) n=20; 2) n=25; 3) n=31; 4) n=50. 3. Quyidagi kvadrat sonlar tartibini aniqlang: 1) 169; 2) 225; 3) 324; 4)3600? 4.n-chi tartibli uchburchak sonni yozing, agar: 1) n=20; 2) n=33 bo‘lsa. 5. n-chi tartibli beshburchak sonni yozing, agar: 1) n=5; 2) n=6 bo‘lsa. Takrorsiz o‘rin almashtirishlar. Ta’rif. Bir-biridan elementlarning joylashish tartibi bilan farq qiluvchi barcha mumkin bo‘lgan kombinatsiyalar n elementdan o‘rin almashtirishlar deb ataladi. n elementdan barcha mumkin bo‘lgan o‘rin almashtirishlar soni Pn deb belgilanadi (P- fransuzcha permutation – o‘rin almashtirish so‘zining birinchi harfi). «n elementdan o‘rin almashtirishlar soni” yoki «En dan pe» deb qiladi. Ko‘paytirish qoidasiga ko‘ra Pn=n*(n-1)*…*3*2*1 ekanligini asoslash mumkin. Ko‘paytirishning o‘rin almashtirish qonunini qo‘llagandan so‘ng formula Pn=1*2*3*…*(n-1)*n ko‘rinishga keladi. Birinchi p ta natural sonlar ko‘paytmasini qisqacha yozish uchun n! faktorial belgisidan foydalaniladi: Pn= n! 71.Azim, Bexzod, Vali va Guli tennis stoliga o‘ynash uchun navbatga turishdi. Ular stol tennisi o‘ynash uchun necha xil usul bilan navbatga turishlari mumkin? Yechish. Ko‘paytirish qoidasiga ko‘ra 4*3*2*1=24 ta usul bilan. Masalada biri-biridan ulardagi joylashish tartibi bilan farq qiluvchi barcha mumkin bo‘lgan kombinatsiyalar soni hisoblab chiqildi. Bunday kombinatsiyalar bir nechta elementdan o‘rin almashtirishlar deb ataladi. 2. Chipta sotish oynasiga: 1) 3 kishi; 2) 5 kishi necha xil usul bilan turishlari mumkin ? Yechish: 1) Pn= 3!=6 2) Pn=5!=120 3. 4, 5, 6, 7 va 8 raqamlari yordamida barcha raqamlari turlicha bo‘lgan nechta besh xonali son yozish mumkin. Yechish: Pn=5!=120 4. 8 ta kitobni javonga nechdaa xil usul joylashtirish mumkin, agar ular orasida har qanday joylashishda bir qator turish lozim bo‘lgan bir muallifning ikkita kitobi bo‘lsa? Yechish: Agar bir muallifning 2 ta kitobini bitta kitob deb hisoblasak, u holda 7 elementdan o‘rin almashtirishlar soni Pn=7!=5040 ga teng, lekin bu o‘rin almashtirishning har birida bir muallifning kitoblari 5040*2=10080 usul bilan almashinadi. 5. 30 va 210 sonlarining tub ko‘paytuvchilarga ajrting. Sonning tub ko‘paytuvchilar ko‘paytmasini nech xil usul bilan yozish mumkin? Yechish: 30=1*2*3*5, P4=4!=24; 210=1*2*3*5*7 , P5=5!=120 39. 6 ta stulni mato bilan necha xil usul bilan o‘rash mumkin, agar olti xil rangdagi mato bo‘lib, barcha stullar turlicha rangda mato bilan o‘raladigan bo‘lsa? [6!=720] 1.2.Kombinatorik masalalar va tartiblangan to’plamlar. Kombinatorika predmeti va paydo bo‘lish tarixi. Matematikaning kombinatorik tahlil, kombinatorik matematika, birlashmalar nazariyasi, qisqacha, kombinatorika deb ataluvchi bo‘limida chekli yoki muayyan ma‘noda cheklilik shartini qanoatlantiruvchi to‘plamni (bu to‘plamning elementlari qanday bo‘lishining ahamiyati yo‘q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o‘rinlash va o‘zaro joylash ya‘ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog‘liq masalalar o‘rganiladi. Hozirgi davrda kombinatorikaga oid ma‘lumotlar inson faoliyatining turli sohalarida qo‘llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko‘ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. To‘plamlar nazariyasi iboralari bilan aytganda, kombinatorikada kortejlar va to‘plamlar, ularning birlashmalari va kesishmalari hamda kortejlar va qism to‘plamlarni turli usullar bilan tartiblash masalalari qaraladi. To‘plam yoki kortej elementlarining berilgan xossaga ega konfiguratsiyasi bor yoki yo‘qligini tekshirish, bor bo‘lsa, ularni tuzish va sonini topish usullarini o‘rganish hamda 7 bu usullarni biror parametr bo‘yicha takomillashtirish kombinatorikaning asosiy masalalari hisoblanadi. Kombinatorikaning ba’zi elementlari eramizdan oldingi II asrda hindistonliklarga ma‘lum edi. Ular hozirgi vaqtda gruppalashlar deb 8ataluvchi kombinatorik tushunchadan foydalanishgan. Eramizning XII asrida Bxaskara Acharya o‘zining ilmiy tadqiqotlarida gruppalash va o‘rin almashtirishlarni qo‘llagan. Tarixiy ma‘lumotlarga ko‘ra, hindistonlik olimlar kombinatorika elementlaridan, jumladan, birlashmalardan foydalanib, she‘riy asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o‘yinlarini tahlil qilish bilan bog‘liq. Ba‘zi atoqli matematiklar, masalan, fransuz matematigi B.Paskal (1623- 1662), sveytasriyalik matematik Ya.Bernulli (1654- 1705), L.Eyler (1707-1783), rus matematigi P.L.Chebishev (1821-1894) turli o‘yinlarda (tanga tashlash, soqqa tashlash, qarta o‘yinlari va shu kabilarda) ilmiy jihatdan asoslangan qarorlar qabul qilishda kombinatorikani qo‘llashgan. XVII asrda kombinatorika matematikaning alohida bir ilmiy yo‘nalishi sifatida shakllana boshladi. Blez Paskal. o‘zining “Arifmetik uchburchak haqida traktat” va “Sonli tartiblar haqida traktat” (1665 y.) nomli asarlarida hozirgi vaqtda binomial koeffitsientlar deb ataluvchi sonlar haqidagi ma‘lumotlarni keltirgan. Fransuz matematigi P.Ferma (1601-1665) esa figurali sonlar bilan birlashmalar nazariyasi orasida bog‘lanish borligini bilgan. Figurali sonlar quyidagicha aniqlanadi. Birinchi tartibli figurali sonlar: 1, 2, 3, 4, 5, … (ya‘ni, natural sonlar); ikkinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si dastlabki ikkita natural sonlar yig‘indisi (3), 3-si dastlabki uchta natural sonlar yig‘indisi (6) va hokazo (1, 3, 6, 10, 15, …); uchinchi tartibli figurali sonlar: 1-si 1ga teng, 2-si birinchi ikkita ikkinchi tartibli figurali sonlarlar yig‘indisi (4), 3-si birinchi uchta ikkinchi tartibli figurali sonlarlar yig‘indisi (10) va hokazo (1, 4, 10, 20, 35, …); va hokazo. Kombinatorika iborasi nemis matematigi G.Leybnis (1646- 1716) ning “Kombinatorik san‘at haqidagi mulohazalar” nomli asarida birinchi bor 1665- yilda keltirilgan. Bu asarda birlashmalar nazariyasi ilmiy jihatdan ilk bor asoslangan. O‘rinlashtirishlarni o‘rganish bilan birinchi bo‘lib Yakob Bernulli shug‘ullangan va bu haqdagi ma‘lumotlarni 1713 - yilda bosilib chiqqan “Ars conjectandi” (Bashorat qilish san‘ati) nomli kitobining ikkinchi qismida bayon qilgan. Hozirgi vaqtda kombinatorikada qo‘llanilayotgan belgilashlar XIX asrga kelib shakllandi. Tekislikda radiuslari o‘zaro teng bo‘lgan aylanalar bir- biriga uringan holda yuqoridan 1 - qatorda bitta, 2 - qatorda ikkita, 3 – qatorda uchta va hokazo, joylashtirilgan bo‘lsin. 1-rasim Aylanalar sonlari ketma-ketligi birinchi tartibli figurali sonlarni tashkil qiladi 9 1-rasm. Masalan, aylanalar bunday joylashuvining dastlabki to‘rt qatori 1 - shaklda tasvirlangan. Bu yerda qatorlardagi aylanalar sonlari ketma-ketligi birinchi tartibli figurali sonlarni tashkil qiladi. Bu tuzilmadan foydalanib, ikkinchi tartibli figurali sonlarni quyidagicha hosil qilish mumkin. Dastlab 1 - qatordagi aylanalar soni (1), keyin dastlabki ikkita qatordagi aylanalar soni (3), undan keyin dastlabki uchta qatordagi aylanalar soni (6), va hokazo. 1.3.Kombinatorikaning ehtimollar nazariyasiga tadbiqlari. Ko‘pgina o‘yinlarda o‘yin kubigidan foydalaniladi. Kubikda 6 ta yoq bo‘lib, har bir yoqqa 1 dan 6 gacha sonda bo‘lgan nuqtalar belgilangan. O‘yinchi kubikni tashlaydi va tushgan yoqda (kubikning yuqorida joylashgan yoqidagi) nechta nuqta borligiga qaraydi. Ko‘pincha kubikning yoqlaridagi nuqtalar mos raqamlar bilan almashtiriladi va 1,2,….,6 raqamlarning tushgani haqida gapirishadi. Kubikni tashlashni tajriba, eksperiment, sinov (hatto o‘yin ham deb), olingan natijani – sinov, tajriba yoki elementar hodisa deb hisoblash mumkin. Odamlarga u yoki bu hodisani ro‘y berishini topish, uning natijasini bashorat qilish qiziqarli. O‘yin kubigini tashlaganda ular qanday bashoratlar qilishi mumkin? Masalan, bunday: A hodisa 1,2,3,4,5 yoki 6 raqami tushishi; B hodisa –7, 8 yoki 9 raqami tushishi; C hodisa–1 raqami tushishi. Hodisalar – kuzatish yoki tajriba natijasi. 49 Birinchi holda bashorat qilingan A hodisa albatta ro‘y beradi. Berilgan tajribada albatta ro‘y beradigan hodisa ishonchli hodisa deyiladi. Masalan, suv to‘la stakan to‘nkarilsa, u holda suv to‘kiladi. Ikkinchi holda bashorat qilingan B hodisa hech qachon ro‘y bermaydi, bu mumkin emas. Berilgan tajribada ro‘y berishi mumkin bo‘lmagan hodisa mumkin bo‘lmagan hodisa deb ataladi. Uchinchi holda bashorat qilingan C hodisa haqida nima deyishimiz mumkin, ro‘y beradimi yoki ro‘y bermaydimi? Bu savolga to‘la ishonch bilan javob bera olmaymiz, chunki 1 raqami tushishi ham, tushmasligi ham mumkin. Berilgan tajribada ro‘y berishi ham, ro‘y bermasligi ham mumkin bo‘lgan hodisaga tasodifiy hodisa deyiladi. Masalan, kishi ko‘chada tanishlarini uchratdi. Masalalar 1.Barcha ikki xonali sonlar qog‘ozchalarga yozilgan. Po‘lat tasodifiy ravishda bitta qog‘ozchani tanladi. Quyidagi hodisalarni ishonchli, mumkin bo‘lmagan va tasodifiy hodisalar sifatida qanday hodisa ekanligini aniqlang: a) A hodisa – tanlangan qog‘ozchada tub son yozilgan bo‘lishi ; 10b) B hodisa – tanlangan qog‘ozchada murakkab son yozilgan bo‘lishi; c) C hodisa – tanlangan qog‘ozchada tub ham murakkab ham bo‘lmagan son yozilgan bo‘lishi; d) D hodisa – tanlangan qog‘ozchada toq yoki juft son yozilgan bo‘lishi. Yechish: A va B hodisalar - tasodifiy, C - mumkin bo‘lmagan hodisa, D – ishonchli hodisa. 2. Quyidagi hodisalardan qaysi biri ishonchli: A – uchta o‘q otishda ikki marta nishonga tegish; B – uchta o‘yin kubigini tashlaganda 18 ta ochkodan ko‘p ochko chiqmasligi; D – tasodifan tashlangan uch xonali soning 1000 dan katta bo‘lmasligi; E – 1,2,3 raqamlaridan takrorsiz tuzilgan tasodifan tanlangan sonning 400 dan kichik bo‘lishligi; Yechish. B, D va E – ishonchli hodisalar. 69. Quyidagi hodisalardan qaysi biri mumkin bo‘lmagan hodisa A – Toshkent tezyurar poezdining shanba kunlari kechikishi; B –3 ta o‘yin kubigini 50 tashlaganda 17 ochkoning chiqishi; C –o,n,a harflar jamlanmasini tasodifan terganda ona so‘zining chiqishi; D – 1,2,3,7,8 raqamlardan tuzilgan va 9 ga karrali sonning ko‘rsatilgan raqamlarni bir marta tasodifan terganda chiqishi. Yechish: D – mumkin bo‘lmagan hodisa. 3. Siz kitobni ixtiyoriiy betini ochdingiz va birinch uchragan so‘zni tanladingiz. Hodisa quyidagidan iborat: a) so‘zning yozuvida unli harf bor; b) so‘zda o harfi bor; c) so‘zda unli harf yo‘q; g) so‘zda ayirish belgisi bor. Bu hodisalardan qaysiri ishonchli, mumkin bo‘lmagan va tasodifiy hodisa? Yechish : a) – ishonchli; b), g) –tasodifiy; c) – mumkin bo‘lmagan hodisalar. Hodisa ehtimolining klassik ta’rifi : O‘yin kubigini tashlaymiz. 1 dan 6 gacha sonlar tushishi mumkin. Bu hodisalardan har biri elementar hodisa va ular birgalikda elementar hodisalar fazosin tashkil etadi. Lekin bu elementar hodisalar teng imkoniyatli bo‘ladimi? Teng imkoniyatli elementar hodisalar deb ulardan ixtiyoriysi qolgan boshqalariga nisbatan bir xil sharoitlarda o‘tkaziladigan ko‘p sonli tajribalarda boshqasiga nisbatan hech qanday ro‘y berish afzalligiga ega bo‘lmaydigan hodisalar hisoblanadi. Biror A hodisaning ro‘y berish imkoniyatini m/n nisbat bilan o‘lchash qulay, bu erda n – berilgan tajriba sharoitlaridan kelib chiquvchi barcha teng imkoniyatli elementar hodisalar soni, m –A hodisaning ro‘y berishiga imkon beruvchi teng imkoniyatli hodisalar soni . Bu A hodisaning ro‘y berish imkoniyaning qulay o‘lchovini bu hodisaning ehtimoli deb atash qabul qilingan va u quyidagicha formula shaklida yoziladi: Ta’rif. A tasodifiy hodisaning ehtimoli deb bu hodisa ro‘y berishiga imkon beruvchi teng imkoniyatli elementar hodisalar sonining (yoki barcha natijalar sonining) berilgan tajriba bilan aniqlanuvchi E fazoning barcha teng imkoniyatli elementar hodisalar soniga (o‘zaro natijalarning umumiy soniga) nisbatiga aytiladi (tasodifiy hodisa ehtimolining klassik ta’rifi). 111.O‘yin kubigini bir marta tashlaganda: a) 4; b) 5; c) juft sondagi ochkolar; g) 4 dan katta ochko d) 3 karrali bo‘lmagan ochkolarning tushish ehtimolini toping. Yechish: Jami n=6 mumkin bo‘lgan natija mavjud, ya’ni bu natijalarning teng imkoniyatli haqidagi farazni qabul qilamiz. Hodisa ehtimolining klassik ta’rifiga asosan a) b) n=6, m=1, P(A)=1/6; c) n=6, m=3, P(A)=3/6=1/2; g) n=6, m=2, P(A)=2/6=1/3; d) n=6, m=4 , P(A)=4/6=2/3; Hodisa ehtimolining statistik ta’rifi . Klassik yondashuvda hodisa ehtimol tushunchasi oddiyroq tushunchaga – elementar hodisalarning teng imkoniyatligiga olib kelinadi. Bu tushuncha esa bu teng imkoniyatlilikni qandaydir tarzda ishonchli aniqlaydigan tajribaning 53 sharoitlarini inson tomonidan intuitiv faraz qilishiga asoslanadi. Ma’lumki, to‘g‘ri o‘yin kubigini tashlaganda olti ochkoning chiqish ehtimoli 1/6 ga teng. Faraz qilaylik, bunday o‘yin kubigini n marta tashlaganda, oltili ochko m marta tushsin. m/n nisbatni oltilikning ro‘y berishining statistik chastotasi deb ataymiz. Shunday tajribalar seriyasini o‘tkazganda statistik chastota p1=m1/n ga teng bo‘lishi mumkin; yana bir martada p2=m2/(n+1), N marta tashlaganda pn=mn/N ga teng bo‘lishi mumkin. p1,p2,…,pn statistik chastotalar uchun turg‘unlik xos bo‘ladi: ular tajribalar sonining oshishi bilan p=1/6 ga yetarlicha yaqin bo‘ladi. Ta’rif. A hodisaning ehtimoli deb shunday noma’lum p songa aytiladiki, uning atrofida tajribalar soni oshganda A hodisaning ro‘y berishining statistik chastotalari qiymatlari jamlanadi. [bu – tasodifiy hodisa ehtimolining statistik ta’rifi] Mergan nishonga o‘q otayotgan bo‘lsin. Nishonga tegish ehtimolini qanday baholash mumkin? Agar “nishonga tekkizish” va “nishonga tekkizmaslik” hodisalari teng imkoniyatli bo‘lsa, javobni birdaniga olamiz: P(nishonga tekkizish)=1/2. Lekin ular teng imkoniyatli bo‘lmasligi mumkin. Aytaylik, Alisher o‘q otganda nishonga 80-90 marta, Siroj esa 30-40 marta tekkizadi. Ravshanki Alisherda nishonga tekkizish imkoniyati Sirojnikidan kattaroq. Alisher va Sirochning o’q otishlar soni jadvali. 12Lekin ko‘rinib turibdiki bu nisbat ma’lum son atrofida tebranadi: Alisherda 4/5, Sirojda esa 3/10. L – A hodisa ro‘y berishi yoki ro‘y bermasligi mumkin bo‘lgan tajribalar soni bo‘lsin, k – A hodisa ro‘y beradigan tajribalar soni bo‘lsin. k/L nisbatni A hodisaning chastotasi deymiz va P{A}=k/L Pl{A}=P(A) kabi belgilanadi. Masala: 1000 ta ixtiyoriy tanlangan detaldan taxminan 4 tasi yaroqsiz. 2400 detal orasida nechta yaroqsizi bo‘lishi mumkin ? Yechish: A – tasodifiy tanlangan detalning yaroqsiz bo‘lish hodisasi, u holda masala shartiga ko‘ra P(A)=0,004. Agar 2400 detal orasida x tasi yaroqsiz bo‘lsa, u holda R(A)= x/2400. Chunki R{A}=R(A), u holda x/2400=0,004, bundan x=10. II BOB. KIRIPTOGRAFIYA TARIXI 2.1 Dastlabki kiriptografiya Kriptografiya axborotni muhofaza qilish usullaridan biri hisoblanadi. Kriptografiya axborot (ma’lumotlar)ni o‘zgartirish tamoyillari, vositalari va usullarini tadqiq etadi. Bundan maqsad axborot mazmunidan ruxsat etilmagan foydalanishdan muhofazalash va uni buzishni bartaraf qilish. Kriptografiya ma’lumotlarni aloqa kanallari orqali uzatishda yoki saqlashda konfedensiallikni yoki haqiqiylikni ta’minlash usullari bilan shug‘ullanadi. Shu bilan birga kriptografiya ma’lumotlarni xabardor bo‘lmagan shaxslar uchun tushuna olmaydigan qilish maqsadida o‘zgartirish usuli hamdir. Ma’lumotlar xavfsizligi tizimining muhim tarkibiy bo‘lagi. Uning mohiyati ma’lumotlarni uzatishdan oldin ma’nosiz belgilar yoki signallar yig‘masiga aylantirish va ma’lumotlarni oluvchi qabul qilib olgandan so‘ng, ularni dastlabki shakliga qayta tiklashdir. 2-rasim KRIPTOGRAFIYA: ASOSIY TUSHUNCHALARI VA QISQACHA TARIXI. Insoniyat axborotni himoya qilish muammosi bilan yozuv paydo bo‘lgandan beri shug‘ullanadi. Bu muammo harbiy va diplomatik ma’lumotlarni yashirincha uzatish zaruratidan kelib chiqqan. Masalan, antik spartalilar harbiy ma’lumotlarni 13shifrlashgan. Xitoyliklar tomonidan oddiy yozuvni iyerogriflar ko‘rinishida tasvirlashlari uni xorijiylardan yashirish imkonini bergan. «Kriptografiya» atamasi grek tilidan tarjima qilinganda « yashirish, yozuvni berkitib qo‘ymoq » ma’nosini bildiradi. Atamaning ma’nosi kriptografiya kerakli ma’lumotni yashirin saqlash va himoyalash maqsadida qo‘llanishini anglatadi. Kriptografiya axborotni himoyalash vositasi, shuning uchun u axborot xavfsizligini ta’minlashning bir tarmog‘i hisoblanadi. Kriptotahlil – bu kalitni bilmay turib, shuningdek, shifrlash algoritmi haqida ma’lumotlar yo‘q bo‘lgan holda yopiq axborotni shifrdan ochish jarayonidir. Shifrning kriptomustahkamligi – samaradorlikning asosiy ko‘rsatkichi bo‘lib, u vaqt bilan yoki kriptotahlilchining kalit ma’lum bo‘lmagan holda shifrmatndan dastlabki ma’lumotni chiqarib olishi uchun kerak bo‘ladigan vositalar narxi bilan o‘lchanadi. Keng qo‘llaniluvchi shifrlash algoritmlarini maxfiy saqlash mumkin emas. Shuning uchun shifrlash algoritmini yashirish zarurati yo‘q. U holda shifrlashning kriptomustahkamligi kalit uzunligi bilan belgilanadi. Chunki, yopiq axborotni shifrdan ochish uchun yo‘l faqatgina kalitni to‘g‘ri tanlashdir. Demak, kriptotahlilga ketadigan xarajat, ya’ni vaqt va mablag‘ kalitning uzunligi va shifrlash algoritmi murakkabligiga bog‘liq bo‘ladi. Kriptologiyaning (kripto – yashirin, logiya – fan, bilim) rivojlanishini uchta bosqichga ajratish mumkin. Birinchi bosqich – kriptologiyani fan sifatidan e’tirof etilmagan davri, tor doiradagi qiziquvchilarga xos faoliyat turi bo‘lgan. Ikkinchi bosqich 1949-yildan boshlanib, K.Shenonning « Maxfiy tizimlarda aloqa nazariyasi » nomli risolaning chop etilishi bilan bog‘lanadi. Bu risolada shifrlashning fundamental ilmiy tadqiqoti va uning mustahkamligi yoritib berilgan. Bu kitobning chop etilishi kriptologiya amaliy matematikaning tarkibiy qismi sifatida shakllanishiga asos bo‘ldi. 3-bosqich 1976-yilda U.Diffi va M.Xellman tomonidan « Kriptografiyaning yangi yo‘nalishlari » nomli asarning chop etilishi bilan belgilanadi. Unda maxfiy aloqa, yopiq kalitni avvaldan bermasdan ham, amalga oshirish mumkinligi bayon etilgan. Ushbu sanadan boshlab to hozirgi kungacha an’anaviy klassik kriptografiya bilan bir qatorda ochiq kalitli kriptografiyaning intensiv rivojlanishi davom etmoqda. Eramizdan oldingi XX asr. Mesopatamiyada o‘tkazilgan qazilmalar vaqtida eng qadimiy shifrlangan matnlar topilgan. Loydan yasalgan taxtachaga qoziqchalar bilan yozilgan matn hunarmandlarning sopol buyumlarini qoplash uchun tayyorlanadigan bo‘yoqning retsepti bo‘lib, u tijorat siri hisoblangan. Qadimgi misrliklarning diniy yozuvlari va tibbiyot retseptlari ham ma’lum. Eramizdan oldingi IX asrning o‘rtalari . Plutarx bergan ma’lumotlariga ko‘ra, ana shu davrda shifrlovchi qurilma – skital, qo‘lla nilgan bo‘lib, u o‘rin almashtirishlar orqali matnni shifrlash imkonini bergan. Matnni shifrlashda so‘zlar biror diametrli silindrga (skitalga) o‘ralgan ensiz lentaga yozilgan. Lenta yoyilganda unda ochiq matn harflarining o‘rinlari almashtirilgan holati hosil 14bo‘lgan. Bunda kalit sifatida silindrning diametri xizmat qilgan. Bunday matnni shifrdan yechish usulini Aristotel taklif etgan. U lentani konusga o‘ragan va o‘qilishi mumkin bo‘lgan so‘z yoki so‘zning bir qismini ko‘rsatuvchi joy silindrning diametri deb hisoblagan. Eramizning 56-yili. Y.Sezar gallar bilan urush vaqtida shirflashning almashtirish turini qo‘llagan. Ochiq matn alfaviti ostiga sikl bo‘yicha (Sezarda uchta pozitsiyaga) siljitish orqali shu alfavit yozilgan. Shifrlashda ochiq matndagi alfavitlar, ya’ni yuqori qismda joylashgan harflar quyi qismdagi mos harflar bilan almashtirilgan. Bu turdagi shifrlash Y.Sezargacha ma’lum bo‘lgan bo‘lsa-da, lekin bunday shifrlash usuli uning nomi bilan yuritiladi. Zamonaviy kriptografiya axborot xavfsizligining konfedensiallik , butunlik , autentifikatsiya va tomonlarning mualliflikni inkor etolmasliklari muammolarini hal etuvchi bilim sohasi hisoblanadi. Konfedensiallikni ta’minlash deganda axborot bilan tanishish huquqi bo‘lmagan shaxslardan bu axborotni himoyalash tushuniladi. 3-rasim Konfedensiallikni ta’minlash Raqib tomonidan nazoratda bo‘lgan aloqa kanali orqali uzatiladigan xabarning konfedensialligini ta’minlash muammosi kriptografiyaning an’anaviy masalalaridan hisoblanadi. Oddiy holda bu muammo uchta subyekt (tomonlar)ning o‘zaro munosabati sifatida bayon etiladi. Axborot egasi (jo‘natuvchi), raqibdan himoya qilish maqsadida, ochiq kanal orqali qabul qiluvchiga yuborilayotgan ochiq ma’lumotni o‘zgartiradi, ya’ni shifrlaydi. Uzatilayotgan xabar ma’nosi bilan tanishish huquqi yo‘q subyekt raqibni anglatadi. Deshifrlash bilan shug‘ullanuvchi kriptotahlilchi ham raqib sifatida qaralishi mumkin. Olingan xabarni haqiqiy qabul qiluvchi deshifrlaydi. Raqib esa himoyalangan xabarga egalik qilmoqchi bo‘ladi, uning harakati hujum hisoblanadi. Hujum faol yoki sust bo‘lishi mumkin. Sust hujum yashirin eshitish, trafikni tahlil qilish, shifrlangan xabarni qo‘lga kiritish, deshifrovka qilish, ya’ni himoyani «sindirish»ga qaratilgan harakatlar hisoblanadi. Faol hujum da raqib xabarni uzatish jarayonini to‘xtatib qo‘yishi, qalbaki xabarlar yuborishi yoki shifrlab uzatilayotgan xabarni modifikatsiya qilishi mumkin. Bu faol harakatlar mos ravishda imitatsiya qilishga va almashtirib qo‘yishga urinish hisoblanadi. 15Kalit shifrlashning asosiy elementi bo‘lib, berilgan xabarni shifrlashdagi almashtirishlar u orqali amalga oshiriladi. Odatda, kalit harf va sonlarning biror-bir ketma-ketligidan iborat bo‘ladi. Har bir almashtirish kalit bilan bir qiymatli aniqlanadi va biror kriptografik algoritm orqali amalga oshiriladi. Shifrlashda bir kriptografik algoritm har xil rejimlarda qo‘lla nishi mumkin. Shu tarzda har xil shifrlash usullari (oddiy almashtirish, gammalash va boshqalar) amalga oshiriladi. Har bir rejimning afzallik va kamchilik tomonlari mavjud. Shuning uchun rejimni tanlash konkret holatga bog‘liq. Deshifrlashdagi kriptografik algoritm, umumiy holda, shifrlashdagi algoritmdan farq qilishi mumkin. Bu holatda shifrlashdagi va deshifrovka qilishdagi kalitlar ham mos tushmasligi mumkin. Shifrlovchi va deshifrovka qiluvchi algoritmlar juftligini kriptotizim , bu algoritmlarni amalga oshiruvchi qurilmani shifrovchi texnika deyiladi. Zamonaviy shifrlash usullari quyidagi talablarga javob berishi lozim: shifrning mustahkamligi kriptotahlilga shunday qarshi tura olishi kerakki, bunda shifrdan ochish faqatgina kalitlarni to‘liq topish orqali amalga oshirilishi mumkin bo‘lsin; kriptomustahkamlik shifrlash algoritmining maxfiyligi bilan emas, balki, kalitning maxfiyligi bilan ta’minlanishi lozim. shifrmatn hajm jihatidan dastlabki axborotdan sezilarli darajada yuqori bo‘lib ketmasligi kerak; shifrlash jarayonida yuzaga keladigan xatolar axborot buzilishi va yo‘qotilishiga olib kelmasligi kerak; shifrlash vaqti katta bo‘lmasligi kerak; shifrlash narxi shifrlanayotgan axborot qiymati bilan mos kelishi kerak. Sodda shifrlar va ularning xossalari An ’ anaviy ( klassik ) shifrlash usullariga o ‘ rinlarini almashtirish shifrlari , oddiy va murakkab almashtirish shifrlari va ularning kombinatsiyalari va modifikatsiyalari kiradi . Ta ’ kidlash joizki , o ‘ rinlarini almashtirish shifrlari va almashtirish shifrlarining kombinatsiyalari amaliyotda qo ‘ lla nilayotgan har xil turdagi simmetrik shifrlarni tashkil etadi . O‘rinlarini almashtirish shifrlarida shifrlanadigan matnning harflari shu matn bloki ichida ma’lum qoidalar bo‘yicha o‘rin almashtiriladi. O‘rinlarini almashtirish shifrlari eng sodda va eng qadimiy hisoblanadi. Shifrlovchi jadvallar. Tiklanish (XIV asr oxirlari) davrining boshlarida o‘rinlarini almashtirish shifrlarida shifrlovchi jadvallardan foydalanilgan. Shifrlovchi jadvallarning kaliti sifatida: jadvalning o‘lchami; o‘rin almashtirishni belgilovchi so‘z yoki jumla; jadval tuzilishining xususiyati bo‘lgan. Kriptografiya tarixini shartli ravishda 4 bosqichga bo‘lish mumkin: 1. Dastlabki kriptografiya. 2. Formal kriptografiya. 3. Ilmiy kriptografiya. 164. Kompyuter kriptografiyasi, bu bosqich kriptografiyada simmetrik va nosimmetrik kriptotizimlar bo‘yicha ikki ilmiy yo‘nalish yuzaga kelishi bilan xarakterlanadi. Dastlabki kriptografiya davriga oid shifrlar haqida gap borganda Yevropa fani tarixidan o‘rin olgan Plutarx, Aristotel (miloddan avvalgi IV asr), Yuliy Sezar (miloddan avvalgi 100-44 yy.), R. Bekon (1214-1294 yy.) shifrlarini aytib o‘tish joiz Dastlabki shifrlash moslamalaridan biri sifatida g‘altak (skitala)dan foydalanilgan. Silindrsimon g‘altakka zich bir qavat o‘ralgan ensiz papirus lentasiga dastlabki matn harflari silindr o‘qi bo‘ylab yozilib shifrmatn shakllantirilgan. Lenta g‘altakdan yechib olinib qabul qiluvchiga jo‘natilgan. Qabul qiluvchi shifrmatnli lentani shifrlash g‘altagi bilan bir xil g‘altakka o‘rab dastlabki matnni o‘qigan. G‘altak o‘lchamlari maxfiy shifrlash kaliti vazifasini o‘tagan. 4- rasim Shifrlash moslamasi Bunday shifr moslamasidan eramizgacha V asrda bo‘lib o‘tgan Spartaning Afinaga qarshi urushi davrida foydalanilgan. Shifrlash g‘altagi o‘lchamlarini topish g‘oyasi Aristotelga tegishlidir. U buning uchun uzun konus olib, unga asosidan boshlab konus uchigacha shifrmatnli lenta o‘ralganda konusning biror qismida o‘qiladigan matn hosil bo‘lishiga qarab g‘altak o‘zagi diametrini aniqlagan. Qadim zamonlarda atbash deb atalgan shifr ma’lum bo‘lgan, undan ba’zan muqaddas iudey matnlarini shifrlashda foydalanilgan. Shifrmatn yaratishda dastlabki matnga tegishli alifboning birinchi harfi oxirgisiga, ikkinchi harfi undan avvalgisiga almashtirilgan. 5- rasim Atbash shifri To‘la bayoni saqlangan shifrlardan yana biri Sezar shifri bo‘lib, u ham atbash shifri oilasiga mansubdir. Sezar tizimining kalit maydoni 26 ta son: 0,1,2,...,25 dan iborat. k kalitli Ek shifrlash algoritmi alifbodagi harflarni k qadam bilan o‘ngga siljitishni o‘z ichiga oladi. Mos ravishda shifrmatn Dk ni ochish algoritmi alifbodagi harflarni k qadam bilan chapga siljitish natijasini beradi. 17Sezar tizimi va unga o‘xshash tizimlarni hozirgi zamon o‘quvchisi uchun harflarni alifbodagi tartib raqami bilan almashtirib sonlar ustida modul bo‘yicha qo‘shish amali  yordamida tushuntirish oson. Sezar tizimiga muvofiq, shifrmatn hosil qilishda dastlabki matnning har bir  harfi shifrmatnda sh    k(mod26)ga aylanadi. Dastlabki matn harfi   sh  k(mod26) ko‘rinishda tiklanadi. Ta’kidlash joizki, modul arifmetikasida mazkur qo‘shish amali zamonaviy shifrlarda ham eng ko‘p foydalaniladigan amaldir. 2.2. Formal kiriptografiya Formal kriptografiya (XV asr oxiri – XX asr boshlari) bosqichi qo‘lda kriptotahlillashga bardoshli va formallashtirilgan shifrlar paydo bo‘lishi bilan xarakterlanadi. Kriptografiya tarixining bu davrida Leon Batista Alberti (1404- 1472 yy.), Iogann Trisemus (1462-1516 yy.), Djirolano Kardono, Kardinal Rishelye, Djovanni Batista Port, Blez de Vijener (1523-1596 yy.), Fransua Viyet (1540- 1603 yy.), Frensis Bekon (1562-1626 yy.), Karl Fridrix Gauss (1777- 1855 yy.), Ogyust Kerkxoff (1835-1903 yy.) va G.S.Vernamlar [1, 3, 8, 16-17] ijodiyoti alohida chuqur iz qoldirgan. Avval ma’lum bo‘lgan ko‘p alifboli almashtirishga asoslangan Jefferson shifrator kalitining qismlari sifatida harflarning har bir diskda va disklarning umumiy o‘qda joylashish tartiblaridan foydalanilgan. Foydalanilishi mumkin bo‘lgan kalitlarning umumiy soni (26!)36ga teng. Shifrning bunday yuksak kriptobardoshlilikka ega ekanligi XX asrga kelib tan olingan va AQSh armiyasida foydalanish uchun qabul qilingan. 6-rasim JIFFIRON shifratori T. Jefferson o‘z shifriga yuqori darajada ehtiyotkorlik bilan yondashib, uni chuqur tahlil etish lozim deb hisoblagan va o‘z amaliyotida an’anaviy kodlardan va Vijener tipidagi shifrlardan foydalanishda davom etgan. Uning shifri XX asrning 20-yillarida to‘rtinchi bor qayta kashf etilgan. XIX asr oxiriga kelib kriptografiya aniq fan sifatlariga ega bo‘la boshladi va u harbiy akademiyalarda o‘rganila boshlandi. XIX asrda yaratilgan shifrlar orasida Vijener shifri oilasiga oid Sen-Sir Fransiya harbiy-dala akademiyasi shifri - “Sen- Sir chizg‘ichi” mashhur bo‘lgan. Bunday shifrator logarifmik chizg‘ichga o‘xshash tuzilgan bo‘lib, alifbo harflari bosmalangan uzun karton bo‘lagi shaklidagi 18qo‘zg‘almas shkala qismdan va alifbo harflari ikki qayta bosmalangan tor karton bo‘lagi shaklidagi qo‘zg‘aluvchan qismdan 15 iborat. Shifrlash jarayoni qo‘zg‘aluvchan qismni kalitning 1-harfi shkalaning «A» harfi ostida joylashuv holatiga mos bo‘lguncha siljitishdan iborat. Bunda dastlabki matnning 1-harfini kalitning shu harfi bilan almashtiriladi. Shu zaylda dastlabki matnning 2-harfi qo‘zg‘aluvchan qismni kalitning 2-harfi shkalaning «A» harfi ostida joylashuv holatiga mos bo‘lguncha siljitib u bilan almashtiriladi va h.k. “Sen-Sir chizg‘ichi” Vijener shifrining sodda mexanik qurilmasi bo‘lgani uchun shifrlovchilar mehnatini osonlashtirgan. Bu g‘oya qo‘zg‘aluvchan qismda alifbo harflarini ixtiyoriy joylashtirish orqali o‘z rivojini topgan va kriptobardoshlilikning yanada oshishiga olib kelgan. “Sen-Sir chizg‘ichi”dan Germaniyada ham takomillashtirilgan shaklda foydalanilgan. Elektrotexnika sohasida fundamental ilmiy asarlari bilan mashhur bo‘lgan Gollandiyalik yirik alloma Ogyust Kerxgoff XIX asr kriptografiyasi tarixida o‘z nomini abadiylashtirgan. U kriptografiya bilan boshlang‘ich tanishuvni harbiy– dala telegraf shifrlaridan boshlab, 1880-yillarda 64 betli “Harbiy kriptografiya” kitobini bosmadan chiqargan. Kitobda shifrga qo‘yiladigan quyidagi umumiy talablar shakllantirib berilgan:  foydalanish osonligi;  ishonchlilik (yuqori kriptobardoshlilik);  tezkorlik (shifrmatnni shakllantirishda va dastlabki manni tiklashda kriptografik almashtirishlar uchun oz vaqt sarf bo‘lishi);  kriptobardoshlilik faqat shifrlash kalitiga bog‘liq bo‘lishi. Shifr, ya’ni kriptografik almashtirishlar algoritmi raqib tomonga ma’lum bo‘lganda ham yuqori kriptobardoshlilikning ta’minlanishi talab etilgan. Shifr qurilmasi bitta foydalanuvchi uchun oson va qulay bo‘lishga mo‘ljallanishi talab etilgan. Lekin ikkinchi jahon urushi yillarida Germaniya qo‘shinlarida tezkorlikni ta’minlash maqsadida har bir shifratorda uchta foydalanuvchi xizmat ko‘rsatgan edi. Mazkur talablar bugungi kunda ham yaratiladigan shifrlar uchun majburiy talablar to‘plamining asosini tashkil etadi. Kriptografiya asosan urushlar zamonida va terrorizm avjiga chiqqan davrlarda hal qiluvchi ahamiyatga ega bo‘lgan. Bu kriptografiyani rivojlantirish borasida keng miqyosli tadbirlar amalga oshirilishiga turtki bo‘lgan. Masalan, 1866 yil 4 aprelda D.V. Karakozov tomonidan rus podshohi Aleksandr II ga qarata o‘q otilgandan so‘ng chor Rossiyasi kriptografiya xizmatining faoliyatida yangi davr boshlangan. Formal kriptografiyaning, umuman butun kriptografiya taraqqiyotining yuksak cho‘qqisi bo‘lib ilk bora amaliyotda foydalanila boshlangan 1917 yilda Edvard Xebern tomonidan ishlab chiqilgan va Artur Kirx tomonidan takomillashtirilgan nemis «Enigma» rotor shifrlash mashinasi tan olingan. Edvard Xebernning kriptografik jarayonlarni mexanizasiyalash borasida inqilobiy tamoyili rotor qurilmalar uchun asos sifatida qabul qilingan. Nemis Enigmasidan boshqa yana AQShning SIGABA, Buyuk Britaniyaning TYPEX, Yaponiyaning RED, ORANGE va PURPLE qurilmalaridan ham foydalanganlar. 192.3. Ilmiy kiriptografiya Kriptografiya tarixining navbatdagi bosqichi ilmiy kriptografiya davri XX asrning 30-60 yillarini o‘z ichiga oladi. Bu 22 davrning farqli tomoni kriptobardoshliligi jiddiy matematik asoslangan kriptotizimlarning yuzaga kelishidir. XX asrning 30 yillari boshlarida kriptologiyaning ilmiy asosi bo‘lgan matematikaning bo‘limlari batamom shakllanib bo‘ldi. Bularga ehtimollar nazariyasi va matematik statistika, umumiy algebra, sonlar nazariyasi kiradi. Ular bilan birgalikda algoritmlar nazariyasi, axborot nazariyasi va kibernetika faol rivojlana boshladi. Ilmiy kriptografiya davrining muhim muvaffaqiyatlari ro‘yxati boshida Klod Elvud Shennonning «Maxfiy tizimlarda aloqa nazariyasi» (1949) asari turadi. Unda axborot muhofazasining nazariy tamoillari shakllantirib berilgan. K. Shennonning ilmiy kriptologiya asoslarini o‘zida mujassamlashtirgan maqolasi bu sohada ochiq tadqiqotlarning sezilarli o‘sishiga turtki bo‘la olmadi. Chunki, birinchidan, maxfiy aloqa tizimlarining nazariy bardoshlilik nazariyasi o‘z mohiyatiga ko‘ra to‘la edi. Unga ko‘ra nazariy jihatdan bardoshli maxfiy tizimlarni hosil qilish uchun himoyalangan kanallar bo‘ylab haddan tashqari katta hajmdagi kalitlarni uzatish lozim bo‘lardi. Ikkinchidan, amaliy bardoshlilik masalalarini yechish mavjud kriptografiya usullarini takomillashtirish bilangina cheklanib qoldi. K. Shennonning «yaxshi» shifr yaratish muammosi ma’lum shartlarni qondiruvchi eng murakkab masalalarni topishga keltiriladi. «Bizning shifrimizni shunday tuzish mumkinki, uni buzib ochish yechilishi katta hajmdagi ishlarni talab qilishi ma’lum bo‘lgan muammoni o‘z ichiga olsin yoki unga ekvivalent bo‘lsin» luqmasi yana chorak asr e’tiborsiz qoldi. Devid Kanning «Kriptograflar» asari kriptografiya tarixi bo‘yicha mumtoz asar bo‘lib qolgan. Bu asar XX asrning 70 yillari oxirigacha ham Davlat Xavfsizligi Nazoratining maxsus kutubxonasida saqlanib undan foydalanishga ruxsati bo‘lgan kimsalar davrasi «ideologik mulohazalar asosida» jiddiy cheklangan. Unda Rossiya haqidagi bo‘limda «Maxfiy polisiyaning vazifalaridan biri bo‘lib yo‘qsillar diktaturasini yo‘qsillarning o‘zidan muhofaza qilish bo‘lgan» deyiladi. Bu XX asrning 70 yillarida ham qo‘rqinchli sir bo‘lgan . Ikkinchi jahon urushi tugagach, sovet kriptograflaridan undan kam bo‘lmagan kuchlarni sarflashni talab etgan «sovuq urush» davri boshlandi. Bu davrda harbiy kriptografik xizmatning ko‘plab ilmiy xodimlari harbiy xizmatdan bo‘shatilgan edi. Bu sharoitlarda harbiy chaqiriq yoshida bo‘lgan yuqori malakali kriptograflar «xalqlar otasi»ga to‘g‘ridan-to‘g‘ri murojaat etishga o‘zlarida jasurlik topdilar va ularning murojaatiga e’tibor berildi. Shu o‘rinda kriptografiyaga Sovet rahbariyati munosabatini tasavvur etish uchun Mixail Maslennikov xotiralaridan parcha keltirish o‘rinli. U 1949 yil Moskva aviasiya institutini tamomlagandan so‘ng Ilyushin konstruktorlik byurosiga ishga jo‘natilgach, bir yildan so‘ng kriptografiya bo‘yicha o‘qishga tanlangan va 1800 rubl stipendiya bilan ta’minlangan. Uning podpolkovnik D. SHukin bilan bo‘lib o‘tgan suhbati alohida e’tiborga loyiq. «Biz kriptograflarmiz, shifrlar bilan maxfiy aloqa sohasida ishlaymiz. Lekin, o‘rtoq Stalin bizga ham «Hammani o‘qish, lekin bizning suhbatlar va yozishmalarni 20hyech kim o‘qiy olmasligi zarur»ligi vazifasini qo‘ydi. D. SHukin suhbatdoshiga telegraf aloqasini maxfiylashtirish uchun maxsus texnika yaratish bilan shug‘ullanishini, lekin bu haqda hyech kim na onasi, na yaqin do‘stlaridan birortasi bilmasligi zarurligini uqtirgan. Bundan bu davrlarda kriptografiya bilan shug‘ullanganlar ham maxfiy sir saqlanishi va ular yetarli darajada iqtisodiy himoyalanganligi ko‘rinib turibdi. XX asrning 60 yillariga kelib kriptografik maktablar rotor kriptotizimlarga nisbatan bardoshliligi yuksak bo‘lgan blokli shifrlar yaratishgacha yetib keldilar. Kriptografiya tarixi bo‘yicha birinchi asar Devid Kannning «Kod buzuvchilar» monografiyasi bo‘ldi. AQShda XX asrning 60 yil oxirlarida yuzaga kelgan bu asar kriptologiya sohasidagi birinchi fundamental ish bo‘lib, u uzoq vaqt davomida kriptologiyaga bag‘ishlangan umumiy tadqiqot yo‘nalishlarini aniqlab berdi. Ammo bu ish har tomonlama kriptologiyani qamrab olgan deyish qiyin, chunki u kriptologiyaning bir yo‘nalishi bo‘lgan kriptotahlilni asos qilib olgan. Kanning bu asarida kriptotahlilning nazariy asoslari va uni amaliyotda qo‘llash ko‘rib o‘tilgan. Lekin bu asarning ahamiyati shundaki, muallif o‘quvchilarni kriptologiyaning asosiy tushunchalari bilan tanishtirib o‘tgan. Kanning bu asari faqat tadqiqotchilar uchun emas, balki keng kitobxonlar ommasi uchun mo‘ljallangan ilmiy asar hisoblanadi. 2.4 . Kompyuter kriptografiyasi davri Kompyuter kriptografiyasi davri XX asrning 70 yillarida avvallari qo‘lda bajarib kelingan, undan so‘ng mexanik va elektromexanik qurilmalar yordamida amalga oshirilgan shifrlar o‘rniga ulardan haddan ziyod yuqori kritobardoshlilikka va tezkorlikka ega kriptotizimlar yaratishga yangicha yondashuvlarni amalga oshirishga qodir bo‘lgan elektron hisoblash mashina (kompyuter)larning yuzaga kelishi bilan xarakterlanadi. Yuqori quvvatli va ixcham kompyuterlarning paydo bo‘lishi axborot texnologiyalarining misli ko‘rilmagan rivojiga, kompyuter va kommunikasiya tarmoqlarining, Internet tarmog‘ining keng quloch yoyishiga, aloqa vositalarining raqamlashishiga olib keldi va axborot xavfsizligi muammosi yanada dolzarb muammolar qatoridan joy oldi. Natijada kriptologiyada ikkita muhim voqyea sodir bo‘ldi. Kompyuter kriptografiyasi davrining birinchi muhim voqyeasi simmetrik kriptotizimlarning birinchi sinfi bo‘lgan blokli shifrlar yuzaga kelib, ular tarixda birinchi marta Davlat standarti maqomiga ega bo‘lishi bo‘lsa, davrning ahamiyatga molik ikkinchi tamoyilli muhim kashfiyoti kriptologiyaga yangicha yondashuvlarni boshlab bergan oshkora kriptografiyaning yuzaga kelishidir. Bu davrdan boshlab kriptografik tizimlar ikkita sinfga bo‘lina boshladi: simmetrik (maxfiy kalitli, bir kalitli) va nosimmetrik (oshkora (ochiq) kalitli, ikki kalitli) kriptotizimlar. O‘z navbatida simmetrik kriptotizimlar miloddan avvalgi davrlardan ma’lum bo‘lib, ular oqimli va blokli shifr turlariga bo‘linadi. 2.5 Simmetrik kriptotizimlar 21Simmetrik kriptotizimlarning ilmiy nazariyasi yaratilishi va amaliyoti rivojiga ilmiy kriptografiya asoschisi K. Shennon, A.N. Kolmogorov va formal kriptografiya namoyandalari O. Kerxgoff, Ch. Bebbidj, U. Fridman, G. Vernam, E. Xebern va boshqalar katta hissa qo‘shgan. Simmetrik kriptotizimlarning ilmiy nazariyasi yaratilishi va amaliyoti rivojiga ilmiy kriptografiya asoschisi K. Shennon, A.N. Kolmogorov va formal kriptografiya namoyandalari O. Kerxgoff, Ch. Bebbidj, U. Fridman, G. Vernam, E. Xebern va boshqalar katta hissa qo‘shgan. - shifrlangan axborotni o‘zgartirib qo‘yish yoki uning shifrini buzib – ochishga yo‘l qoldirmaslik; - axborot muhofazasi faqat kalitning ma’lumligiga bog‘liq bo‘lib, algoritmning ma’lum yo noma’lumligiga bog‘liq emas (O.Kerkgoff qoidasi); - dastlabki axborot (ma’lumot)ni yoki kalitni biroz o‘zgartirish shifrlangan matnning butunlay o‘zgartirib yuborishi lozim (K. Shennon tamoyili, “o‘pirilish” hodisasi); - kalit qiymatlari sohasi shunday katta bo‘lishi kerakki, undan kalit qiymatlarini bir boshdan ko‘rib chiqish asosida shifrni buzib ochish imkoni bo‘lmasligi lozim; - algoritm iqtisodiy jihatdan tejamli va yetarli tezkorlikka ega bo‘lishi lozim; - shifrmatnni buzib ochishga ketadigan sarf-xarajatlar axborot bahosidan yuqori bo‘lishi lozim. Kriptotizimdan foydalanishda matn muallifi shifrlash algoritmi va shifrlash kaliti vositasida avvalo dastlabki matnni shifrlangan matnga o‘giradi (1.9-rasm). Matn muallifi uni o‘zi foydalanishi uchun shifrlagan bo‘lsa (bunda kalitlarni boshqaruv tizimiga hojat ham bo‘lmaydi) uni saqlab qo‘yadi va kerakli vaqtda shifrlangan matnni ochadi. 7-rasim Shifrlangan axborot Kriptograflar orasida mashhur bo‘lgan ma’lumotlarni shifrlash algoritmlari guruhiga AQSh davlat standartlari – DES [11, 25], AES [26], Rossiya Federasiyasi davlat standarti GOST 28147-89 [27], IDEA [11, 25], FEAL [11, 25] kiradi. 2.6 Nosimmetrik kriptotizimlar Nosimmetrik kriptografik tizimlar yaratish tamoyili jahon kriptografiya tarixida ilk bor bundan 35 yil muqaddam amerikalik 33 olimlar Uitfild Diffi va Martin Xellman [29-30] tomonidan taklif etilgan bo‘lib, ular katta sonli chekli to‘plamlarda bir tomonlama funksiyalardan foydalanishga asoslangan. U. Diffi va 22M. Xellmanning 1976 yilda bosilib chiqqan “Kriptologiyada yangi yo‘nalishlar” maqolasida ilgari surilgan ”maxfiy kalitni uzatishni talab etmaydigan amaliy bardoshli maxfiy tizimlarni tuzish mumkin” degan fikri kriptologiyada nosimmetrik kriptotizimlarning yuzaga kelishi hamda ularning rivojlanish davrining boshlanishiga sabab bo‘ldi. U. Diffi va M. Xellman maqolasining hal qiluvchi hissasi ikkita ta’rifda mujassamlangan. Bular «bir tomonlama funksiya» va «yashirin yo‘lli bir tomonlama funksiya «tushunchalaridir. Nosimmetrik kriptotizimlar nazariyasi va amaliyoti rivojiga U. Diffi va M. Xellman [29-30] bilan bir qatorda R. Rayvest, A. Shamir, L. Adleman [31-36], El Gamal [37-38], K. Shnorr [39-41], N. Koblis [42-44], A. Menezes [45-46], B. Shnayer [11, 25, 47] va boshqalar katta hissa qo‘shgan. Shifrlash va shifr ochish kalitlari o‘zaro funksional bog‘langan bo‘lib, ulardan biri asosida ikkinchisi amaliy jihatdan (mavjud hisoblash vositalari taraqqiyoti darajasida) hisoblab topilishi mumkin bo‘lmagan va ulardan biri faqat aloqa ishtirokchisiga ma’lum bo‘lib, boshqalardan maxfiy tutiladigan, ikkinchisi esa aloqa ishtirokchilarining hammasiga oshkora bo‘lgan kriptotizim nosimmetrik (oshkora kalitli) kriptotizim deb ataladi. 8-rasim Nosimmitrik kiriptografik tizimda axborot uzatish jarayoni Nosimmetrik kriptotizimda aloqa ishtirokchilarining har biri o‘zining shaxsiy maxfiy va oshkora kalitlari juftiga ega bo‘lib o‘z oshkora kalitini boshqa aloqa ishtirokchilariga e’lon qiladi. Shaxsiy maxfiy kalit qabul qilinadigan axborot konfidensialligini ta’minlash uchun yaratilganda shifrni ochish kaliti bo‘lib xizmat qiladi. Bunda kimga konfidensial axborot jo‘natiladigan bo‘lsa uning oshkora kalitidan foydalanib shifrlangan axborot jo‘natiladi. Bunday axborotning shifrini faqat yagona maxfiy kalit egasigina ocha oladi. Agar maxfiy kalit autentifikasiya maqsadida xabarlarga elektron raqamli imzo bosish uchun hosil qilingan bo‘lsa, u shifrlash kaliti sifatida foydalaniladi. Oshkora kalit esa yuqoridagi birinchi holda shifrlash kaliti bo‘lib, ikkinchi holda shifrni ochish (tekshirish) kaliti bo‘lib xizmat qiladi. Nosimmetrik kriptotizimlar asosida simmetrik tizimlarda yechilmay qolgan kalit tarqatish va elektron raqamli imzo masalalarining yechimini izlash yo‘llarida U. Diffi va M. Xellman ko‘pgina takliflarni ilgari surganlar. Ochiq kalitli kriptotizimlar axborot xavfsizligining ko‘plab muammolarini yechib berishga 23qodir bo‘lib, ularning muhim qo‘llanish sohalaridan biri elektron raqamli imzo (ERI) hisoblanadi. 24 XULOSA Ming yilliklar davomida kriptografiyadan davlat qurilishida, harbiy va diplomatiya aloqasini muhofazalashda foydalanib kelingan bo‘lsa, axborot asrining boshlanishi bilan kriptologiya jamiyatda, xususiy sektorda foydalanish uchun ham zarur bo‘lib qoldi. Qariyb 35 yildan buyon kriptologiyada keng miqyosda ochiq tadqiqotlar olib borilmoqda. Hozirgi kunda konfidensial axborot (masalan, yuridik hujjatlar, moliyaviy, kredit stavkalari to‘g‘risidagi axborotlar, kasallik tarixi va shunga o‘xshash)larning talay qismi kompyuterlararo odatdagi aloqa kanallari orqali uzatilmoqda. Jamiyat uchun bunday axborotning konfidensialligi va asl holda saqlanishi zaruratga aylangan. Kriptografiya tarixida birinchi muhim voqyea simmetrik kriptotizimlarning birinchi marta Davlat standarti maqomiga ega bo‘lishi bo‘lsa, keyingi o‘n yilliklarning muhim kashfiyoti kriptologiyaga yangicha yondashuvlarni boshlab bergan oshkora kriptografiyaning yuzaga kelib uning muttasil rivojlanib borayotganligidir AQShdan keyin Yevropa davlatlari va Yaponiyada elektron raqamli imzo bo‘yicha qonun va dastlabki davlat standartlari qabul etildi. Ko‘pchilik davlatlar, shu jumladan O‘zbekiston Respublikasi ham kriptografiya vositalaridan axborot– telekommunikasiya tarmoqlarida maxfiy axborotlarni xavfsiz uzatish va elektron raqamli imzo yaratishda o‘z milliy algoritmlaridan foydalanmoqdalar. Ushbu o‘quv qo‘llanmada kriptografiya tarixi, kriptografiyaning asosiy matematik tushunchalari, ta’riflari, teoremalari hamda simmetrik va nosimmetrik kriptografik algoritmlarning matematik asoslari bayon etilgan. Unda O‘zbekiston davlat standartlarini ishlab chiqishga asos bo‘lgan alebraik strukturalar va funksiyalar - diamatrisalar algebrasi, parametrli elliptik egri chiziqli funksiyalar va ularning asosiy xossalari, hamda ishlab chiqilgan kriptoalgoritmlar keltirilgan. Ushbu o‘quv qo‘llanma axborot xavfsizligi va kriptografiya yo‘nalishida davlat tilida ta’lim olayotgan magistrlar uchun mo‘ljallangan. Shuningdek ushbu o‘quv qo‘llanmadan axborot xavfsizligi yo‘nalishida bakalavrlar tayyorlash jarayonida hamda kriptografiya yo‘nalishida ilmiy-tadqiqot olib borayotgan tadqiqotchilar, ilmiy xodimlar va soha mutaxassislari foydalanishlari mumkin. 25ADABIYOTLAR RO’YXATI 1. Виленкин Н.Я. Популярmя комбиmторика. М.: Наука, 1975. -208 с. 2. Холл М. Комбиmторика: перевод с английского. M .: Мир, 1970.- 424 с. 3. To‘rayev H.T., Azizov I. Matematik mantiq va diskret matematika. 1,2- jild. "Tafakkur-Bo‘stoni", Toshkent, 201l. 4. Ўзбекистон Республикасини яmда ривожлантириш бўйича ҳаракатлар стратегияси тўғрисида. Ўзбекистон Республикаси Президентининг ПФ-4947- сон фармони. Тошкент, 2017 йил 7 феврал. 5. Хасанов П.Ф., Исаев Р.И., Хасанов Х.П., Назарова М.Х. Ахмедова О.П. Ахборотнинг криптографик муҳофазаси тарихи (Дастлабки ва формал криптография даври) // Aloqa dunyosi . – Тошкент, 2005, №1 (4). – 32-37 -бетлар. 6. Ахмедова О.П. Параметрлар алгебраси асосида носимметрик криптотизимлар яратиш усули ва алгоритмлари // Номзодлик диссертация иши, Тошкент-2007. 7. Бабаш А.В., Шанкин Г.П. История криптографии. Часть I . – Москва: Лори Гелиос АРВ, 2002. – 240 с. 8. Бабаш А.В., Шанкин Г.П., Криптография – Москва: Лори Гелиос АРВ, 2002. – 512 с. 9. Арипов М.М., Пудовченко Ю.Е. Основы криптологии – Ташкент: 2004. – 136 с. 10. Баричев С.Г., Серов Р.Е. Основы современой криптографии. Учебное пособие. – Москва: Лори Горячая Линия - Телеком, 2002. – 152 с 26 ILOVALAR ILOVA 1. Agar bolada 4 ta konfet (turli xil) bo'lsa va ulardan faqat 2 tasini olib, qolganlarini singlisiga qoldirsa, u quyidagi variantlarga ega: ABCD - to'rt xil konfet. A+B, A+C, A +D, B+C, B+D, C+D - ularning juftligini tanlashning oltita usuli. N to‘plamdagi K elementlarning nechta kombinatsiyasi mavjud (barcha N element har xil bo‘lsa). Matematik formulani osongina topish mumkin: N! ------------- = C(N, K) - turli kombinatsiyalar soni K! * (N - K)! Qayerda x! bu X ning faktoriali, ya'ni 1 * 2 * 3 * ... * X mahsulotidir. Berilgan N va K uchun aynan shu C(N, K) qiymatini hisoblashingiz kerak. #include <iostream> using namespace std; unsigned int fact(int); // faktorial uchun funksiyani elon qilish int combination(int, int); // kambinatsiyani hisoblash uchun funksiya int main() { int m; cin>>m; int *a=new int[m]; // dinamik massiv for(int i=0; i!=m; i++) { int l,q; cin>>l>>q; // 2ta element kiritilib ularni combination funksiyaga yuboramiz a[i]=combination(l,q); // bu kanbinatsiyalarni bajarib dinamik massivga taminlash } for(int i=0; i!=m; i++) { cout<<a[i]<<" "; } delete[]a; // xotiradan dinamik massivni o'chirib tashlash return 0; } int combination(int n, int k) { return fact(n)/(fact(k)*fact(n-k)); /* fac(n) -- n factariolni xisoblaydi,fac(k) -- k factarialni xisoblaydi,fac (n-k)-- n-k ni hisoblaydi. (n!)/(k!*(n-k)!) */ 27} unsigned int fact(int x) { unsigned int p=1; for(int i=1; i<=x; i++) { p*=i; } return p; }

1 Mavzu: “Kombinatorika va kiriptografiya masalalari” MUNDARIJA KIRISH ............................................................................................................ 2 I Bob KOMBINATORIKA ASOSLARI. ....................................................... 4 1.1 Kombinatorikaning asosiy tushunchalari. ................................................. 4 1.2.Kombinatorik masalalar va tartiblangan to’plamlar. .......................... 7 1.3.Kombinatorikaning ehtimollar nazariyasiga tadbiqlari. ........................... 9 II BOB. KIRIPTOGRAFIYA TARIXI ......................................................... 12 2.1 Dastlabki kiriptografiya ........................................................................... 12 2.2. Formal kiriptografiya ....................................................................... 17 2.3. Ilmiy kiriptografiya ................................................................................ 19 2.4 . Kompyuter kriptografiyasi davri ........................................................... 20 2.5 Simmetrik kriptotizimlar ......................................................................... 20 2.6 Nosimmetrik kriptotizimlar ..................................................................... 21 XULOSA ....................................................................................................... 24 ADABIYOTLAR RO’YXATI ...................................................................... 25 ILOVALAR ................................................................................................... 26 ILOVA 1. ....................................................................................................... 26

2 KIRISH Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog‘liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo‘yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O‘z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo‘yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko‘proq shaxsning ijobiy o‘zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo‘llarini (matematik statistika o‘rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo‘l keladi. Ehtimollar nazariyasi va matematik statistikani o‘rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo‘lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo‘lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to‘g‘risida mulohazalar» nomli kitobida birinchi marta qo‘llagan edi. Hozirgi vaqtda kombinatorik usullar informatsiya nazariyasi muammolarini, chiziqli dasturlash masalalarini yechishda, transport masalalarini yechish uchun va h.k.larni hal qilishda keng qo‘llanilmoqda. Kombinatorik masalalar nafaqat matematika go‘zalligini ko‘rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko‘rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko‘pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Uslubiy qo‘llanmada matematika o‘qitishda kombinatorika elementlarini o‘rganish samaradorligini oshirish maqsadida kombinatorika fanining asosiy 5 tushunchalari, kombinatorika elementlarini o‘rganish xususiyatlari, o‘qitish jarayonida kombinatorika elementlarini o‘rgatish bilan birga o‘quvchilarning ijodiy faolligini oshirish bo‘yicha uslubiy tavsiyalar bayon etilgan. Axborotni muhofaza qilish masalalari bilan kriptologiya fani shug‘ullanadi. Keyingi oxirigi yillarda kriptologiya yo‘nalishini rivojlantirishga davlatimiz tomonidan katta ahamiyat berilmoqda. O‘zbekiston Respublikasi Prezidentining 2007 yil 3 aprelda qabul qilgan “O‘zbekiston Respublikasida axborotning kriptografik himoyasini tashkil etish chora-tadbirlari to‘g‘risida” gi PQ-614–son 5 qarorida hamda O‘zbekiston Respublikasi Prezidentining 2017 yil 7 fevraldagi “O‘zbekiston Respublikasini yanada rivojlantirish bo‘yicha Harakatlar strategiyasi to‘g‘risida” gi PF-4947-son farmoyishida beshta ustuvor yo‘nalishdan biri sifatida axborotni muhofaza qilish tizimini takomillashtirish, axborot sohasidagi tahdidlarga o‘z vaqtida va munosib qarshilik ko‘rsatish kabilar ko‘zda tutilgan. Mazkur qaror va farmoyishning asosiy vazifalaridan biri axborotni muhofaza qilish

3sohasida yuqori malakali kadrlarni tayyorlashdan iborat bo‘lib, buning uchun axborot xavfsizligi va kriptografiya yo‘nalishida davlat tilida ta’lim olayotgan talabalar, tadqiqotchilar va ilmiy xodimlar uchun mo‘ljallangan o‘quv qo‘llanmalar, darsliklar, uslubiy qo‘llanmalar va kitoblar ishlab chiqish muhim ahamiyat kasb etadi. Taqdim etilayotgan o‘quv qo‘llanma ana shu sohada bajarilgan ishlardan biri hisoblanadi. Ushbu o‘quv qo‘llanma axborot xavfsizligi va kriptografiya yo‘nalishida ta’lim olayotgan magistrlar uchun mo‘ljallangan. Shuningdek ushbu o‘quv qo‘llanmadan axborot xavfsizligi yo‘nalishida bakalavrlar tayyorlash jarayonida hamda kriptografiya yo‘nalishida ilmiy-tadqiqot olib borayotgan tadqiqotchilar, ilmiy xodimlar va soha mutaxassislari foydalanishlari mumkin.

4I Bob KOMBINATORIKA ASOSLARI. 1.1 Kombinatorikaning asosiy tushunchalari. Ta’rif. Kombinatorika – ma’lum xossalarga ega bo‘lgan elementlarning turli kombinatsiyalarini o‘rganuvchi matematikaning bo‘limi. Kombinatorikaning asosiy masalasi – berilgan ob’ektlardan u yoki bu shartlarga bo‘ysunuvchi bir nechta turli kombinatsiyalari tuzish mumkin. To‘plamlardan farqli elmentlar kombinatsiyalari bir xil (takroriy) elementlarni o‘z ichiga olishi mumkin Kombinatorik masalalarni yechishda ko‘pincha ikkita asosiy qoida qo‘llaniladi. Qo‘shish qoidasi: Agar biror a elementni t ta usul bilan, ikkinchi b elementni – p ta usul bilan tanlash mumkin bo‘lsa, u holda a yoki b elementni (t+p) ta usul bilan tanlash mumkin. Qo‘shish qoidasidan foydalanishda A ob’ektni tanlashning hech qanday usuli B ob’ektni tanlash usuli bilan ustma-ust tushmasligi kerak. Agar bunday ustma-ust tushishlar bo‘lsa, u holda qo‘shish qoidasi o‘z kuchini yo‘qotadi va faqat tanlashning (m+n-k) ta usulini olish mumkin, bu erda k- ustma-ust tushishlar soni. Ko‘paytirish qoidasi: Agar biror a elementni t ta usul bilan, ikkinchi b elementni – p ta usul bilan tanlash mumkin bo‘lsa, u holda a va b elementni tp ta usul bilan tanlash mumkin. Qo‘shish va ko‘paytirish qoidalari ixtiyoriy sondagi chekli elementlar uchun o‘rinli. Masalalar 1. p ta turli raqamdan nechta turli p xonali son tuzish mumkin? Yechish . Bitta raqam (1) dan faqat bitta bir xonali son olish mumkin: 1. Ikkita raqamdan (1 va 2) 2 ta ikki xonali son olish mumknim: 12 va 21. Buni quyidagicha hosil qilish mumkin: oldingi holdagi 1 soni o‘ng va chap tarafiga 2 raqamini yozish bilan hosil qilish mumkin, ya’ni oldingi holni 2 ga ko‘paytirish lozim (1·2). 3 ta raqam (1,2 va 3) dan 6 ta uch xonali son olish mumkin: 312, 132, 123, 321, 231, 213. Buni quyidagicha hosil qilish mumkin: oldingi holdagi har bir ikki xonali son o‘ng, chap tarafiga va o‘rtasigav 3 raqamini yozish bilan hosil qilish mumkin, ya’ni oldingi holni 3 ko‘paytirish lozim (1·2·3). Qiyin emaski, bunda quyidagi qonuniyatni sezish mumkin: har bir navbatdagi holda javob oldingisiga qaganda p marta ortiq bo‘ladi. Ixtiyoriy p soni uchun formula olamiz: 1·2·3·...·(n-1)·n. Javob : 1·2·3·...·(n-1)·n Ta’rif. 1 dan p gacha barcha natural sonlar ko‘paytmasi p-faktorial deb ataladi va p! deb belgilanadi. Shunday qilib: p!=1·2·3·… ·p. 0!=1 deb hisoblanadi. Manfiy sonning faktoriali mavjud emas. Faktorialning asosiy xossasi: p!=(p-1)!p

5Tarixiy ma’lumot. Ba’zi kombinatorik masalalarni yechish bilan qadimgi Xitoyda, keyinchalik Rim imperiyasi davrida ham shug‘ullanganlar. Lekin matematikaning mustaqil bo‘limi sifatida faqat ehtimollar nazariyasi fani rivoji tufayli Evropada 18 asrdan boshlab tan olindi. 1.Guruhda 20 ta qiz va 5 ta o‘g‘il bola bor. Sardorni necha xil usul bilan tanlash mumkin ? Yechish: Sardor sifatida 20 ta qizdan biri yoki 5 ta o‘g‘il boladan biri tanlanishi mumkin, demak, sardorni saylashning umumiy soni 20+5=25. 2.Maktabda 76 o‘qituvchi ishlaydi. Ulardan 49 tasi ingliz tilini, 32 tasi nemis tilini va 15 nafari ikkala tilni ham biladi. Necha o‘qituvchi na ingliz tilini, na nemis tilini biladi? Yechish: Ingliz yoki nemis tilini 49+32–15=66 nafar o‘qituvchi biladi. Demak, bu ikkala tildan birortasini ham 76–66=10 o‘qituvchi bilmaydi. 3.Guruhda 30 kishi bor. Sardor va yoshlar ittifoqi etakchisini saylash lozim. Buni necha xil usul bilan amalga oshirish mumkin? Yechish: Sardor bo‘lib 30 o‘quvchidan ixtiyoriysi saylanishi mumkin, ya’ni sardorni tanlashning 30 ta usuli mavjud. Sardor saylangandan so‘ng qolgan 29 o‘quvchidan yoshlar yetakchisini saylab olish mumkin. Shunday qilib, sardornin saylashning bir usuliga yoshlar etakchisini tanlashning 29 usuli mos keladi. Demak, sardor va yoshlar etakchisini tanlashning umumiy soni 30·29=870 ga teng. 4. Agar raqamlar takrorlanishi mumkin bo‘lsa, 0,1,2,3,4,5,6 raqamlaridan nechta uch xonali juft son tuzish mumkin? Yechish: abc uch xonali sonni tuzishda berilgan raqamlardan a ning o‘rniga noldan tashqari, ixtiyoriy raqamni olish (6 ta imkoniyat), b ning o‘rniga ulardan ixtiyoriysini olish mumkin (7 imkoniyat), c ning o‘rniga 0,2,4,6 raqamlardan ixtiyoriysini olish mumkin (4 imkoniyat). Shunday qilib, ko‘paytirish qoidasiga ko‘ra masala shartini qanoatlantiruvchi sonni tuzishning 6 ·7·4=168 ta usuli mavjud ekan. 5. 1-navli 20 ta va 2-navli 30 ta buyum bor. Bir navdagi ikkita buyumni tanlash lozim. Buni necha xil usul bilan bajarish mumkin? Yechish: Ko‘paytirish qodisaga ko‘ra 1-navli 2 ta buyumni 20 ·19=380 usul bilan tanlash mumkin. Shunga o‘xshash 2-navli 2 ta buyumni 30 ·29=870 usuli bilan tanlash mumkin. Masala shartigi ko‘ra bir xil navli ikkita buyumni tanlash lozim bo‘lgani uchun, qaysi navdan bo‘lishi muhim emas, bir xil navli 2 ta buyumni tanlashning umumiy soni 380+870=1250 ga teng bo‘ladi. 6. Agar raqamlar takrorlanishi mumkin bo‘lsa 0,1,2,3, raqamlaridan nechta bir xonali, ikki xonali va uch xonali juft sonlar tuzish mumkin? Yechish: Ravshanki, berilgan raqamlardan faqat bitta birxonali juft son tuzish mumkin–2. Berilgan raqamlardan ikki xonali ab sonni tuzishda a ning o‘rniga noldan tashqari ixtiyoriy raqamni olish mumkin (3 imkoniyat), b ning o‘rniga 0 va 2 raqamlaridan ixtiyoriy raqamni olish mumkin (2 ta imknoiyat). Shunday qilib, ko‘paytirish qoidasiga asosan bizga kerak bo‘lgan sonni tuzishning 3 ·2=6 ta usuli mavjud.

O'xshashlar

Kombinatorika va kriptografiya masalalari
Kombinatorika va kriptografiya masalalari
Kombinatorika KURS ISHI
Kombinatorika algoritmlari. O’rin almashtirish algoritmini loyihalash
Kombinatorika algoritmlari. O’rin almashtirish algoritmini loyihalash