3 ma’ruza Mavzu: Ma’lumotlarni shifrlash va arxivlash vositalari Oqimli shifrlash algoritmlari. Reja

Kalitlarni hisoblash. Ochiq kalitli kriptotizimlarga kalitlarni generastya qilish muhim ahamiyat kasb etadi. Har bir tomon ikkitadan kalit generatsiya qilishi kerak bo‘ladi. Buni amalga oshirish uchun esa quyidagi vazifalarni bajarish kerak bo‘ladi:

• 
  ikkita p va q dan iborat tub son aniqlab olinish;
  
• 
  ikkinchisini hisoblash uchun, e yoki d sonlaridan birini tanlash.
  

Birinchi bo‘lib p va q ni tanlash protsedurasini ko‘rib o‘tilsa. n=pq qiymati hamma ma’lumligini inobatga olgan holda, p va q ni qiymatini oddiy perebor usulda topish imkoniyatiga yo‘l qo‘ymaslik uchun, bu tub sonlar yetarli darajada katta bo‘lishi kerak. Shu bilan bir qatorda katta tub sonlarni topish metodi amaliy jihatdan unumli bo‘lishi kerak. Hozirgi kundagacha samaradorligi yaxshi bo‘lgan, ihtiyoriy katta sondagi tub sonni hisoblash metodi ishlab chiqilmagan. Bu metodlarda ko‘proq taxminan istalgan uzunlikdagi va aniqlikdagi, tanlab olingan toq sonni tublikka tekshirish protsedurasi yotadi. Agar tanlab olingan son tub bo‘lib chiqmasa, keyingi tub son tanlab olinadi toki tub son tanlab olinmashuncha. Sonlarni tublikka tekshiruvchi bir qator testlar mavjud bo‘lib, bu testlarining deyarli barchasi ehtimollik xarakteriga ega. Ya’ni testlash natijasi berilgan butun sonni ehtimoliy tubligini aniqlaydi. To‘liq ishonch bo‘lmasligiga qaramasdan, bunday testlarning bajarilishi, ishonchliligi ta’minlanganligi ehtimoli birga yaqin bo‘ladi.
Rabbin-Miller va aksariyat shunga o‘xshash algoritmlarda, berilgan butun n sonni tublikka sinash protsedurasi, tasodifiy tanlab olingan butun son a va n ishtiroidagi bir qator hisoblashlarni bajarishdan iborat. Agar n bunday testlashlarga javob bera olsa, u holda n tub son bo‘lib chiqadi, aks holda tub emas. Agar n har xil tasodifiy tanlangan a ning qiymatlarida,bir qator shunday sinovlardan muvaffaqiyatli o‘tsa, n ning tub son ekanligining ishonchliligi darajasi ortadi.
Hulosa qilib shuni aytish mumkinki, tub sonni tanlab olish protsedurasini quyidagi ko‘rinishda ko‘rsatish mumkin.

1. 
   Toq bo‘lgan butun n sonni qandaydir tasodifiy ravishda tanlab olish(masalan psevdotasodifiy generator orqali).
   
2. 
   Tasodifiy ravishda abo‘lgan butun a son tanlab olish.
   
3. 
   Tanlab olingan sonni tublikka sinash testidan o‘tkazish. Agar n soni testdan o‘ta olmasa, keyingi tasodifiy ravishda tanlab olingan sonni shu ketma-ketlikda bajarish kerak.
   
4. 
   Agarn yetarlicha qayta testlardan muvaffaqiyatli o‘tsa, n qiymatni munosib deb olish kerak, aks holda 2 qadamga o‘tish kerak.
   

Shuni esdan chiqarmaslik kerakki, bu jarayon faqat, qachonki yangi kalitlar juftligini (KU,KR) yaratish talab qilinsagina bajariladi. Sonlar nazariyasi haqidagi teoremalaridan biri, tub sonlar haqidagi teorema shuni tasdiqlaydiki, N gacha bo‘lgan butun sonlardan ln(N) tasi tub bo‘lishi mumkin. Bundan kelib chiqadikitub sonni topish uchun, ln(N)gacha bo‘lgan butun sonlarni tublikka sinashga to‘g‘ri keladi, bunga esa o‘z-o‘zidan ko‘p vaqt hamda super zamonaviy hisoblash mashinasi kerak bo‘ladi. Juft sonlarni chiqarib tashlashsak sonlar tartibi ln(N)/2 taga yetadi. Masalan tub sonni uzunligi tartibi _{ } bo‘lgan oraliqda izlaydigan bo‘lsak, tub sonni topish uchun ln(N)/2=70 ga yaqin urinish kerak bo‘ladi. p va q tub sonni aniqlagandan keyin, e qiymatni tanlab d ni hisoblash yoki teskari, d qiymatni tanlab e ni hisoblash bilan kalitlarni hisoblash jarayoni tugaydi. Birinchi navbatda e ni shunday tanlish kerakki, u Eyler funksiyasi bilan o‘zaro tub bo‘lishi kerak ya’ni gcd(_{ })=1, shundan so‘ng e ga o‘zaro teskari bo‘lgan d topiladi _{ }. Bunday o‘zaro tub sonlarni topish Yevklidning umumlashgan algoritmi bo‘yicha topiladi, ya’ni protsedura shundan iboratki tasodifiy ravishda generatsiyalangan sonni _{ } bilan o‘zaro tub bo‘lmaguncha taqqoslanadi. Tanlab olingan sonlarning tub bo‘lish ehtimoli 0.6 ga teng bo‘lib, to‘g‘ri keladigan qiymatni topish uchun bir necha tekshirishlar yetarli bo‘ladi.