|
6- AMALIY MAShG‘ULOT MAVZUSI:
CHIZIQLI TAQQOSLAMALAR YECHISH USULLARI. CHIZIQLI TAQQOSLAMALAR TIZIMLARI. XITOY USULI.
Diffi va Xellman mahfiy uslubli bir tomonli funksiyaning aniqlanishiga asoslanib, mahfiy aloqa tizimi foydalanuvchilari uchun, o‘zlarining ochiq kalitli kriptosistema strukturasini (tuzilishini) taklif etdilar. har bir foydalanuvchi biror butun sonni (daraja ko‘rsatkichini) tanlaydi va uni mahfiy saqlaydi. So‘ngra, bu asosida algoritm tuzib ochiq ma’lumotlar kitobiga bu algoritmni joylashtiradi. Bundan tashqari asosida mahfiy saqlanadigan algoritmni ham tuzadi va uni sir tutadi. Agarda foydalanuvchi foydalanuvchiga mahfiy ma’lumotni uzatmoqchi bo‘lsa, u holda foydalanuvchi ochiq ma’lumotlar kitobidan algoritmni olib, uslub bilan kriptogrammani tuzib (hosil qilib), foydalanuvchiga jo‘natadi. Mahfiy ma’lumotni kriptogramma ko‘rinishida qabul qilib olgan foydalanuvchi o‘zining mahfiy algoritmidan foydalanib uslub bilan ochiq matnni hosil qiladi. Agarda haqiqatan ham mahfiy uslubli bir tomonli funksiya bo‘lsa, u holda bu funksiya asosida qurilgan algoritm shak-shubhasiz amaliy bardoshlilikni ta’minlaydi. Diffi va Xellman, agarda bir tomonli funksiyaning aniqlanish sohasidagi daraja ko‘rsatkichining barcha qiymatlari to‘plami bilan, aynan shu funksiyaning qiymatlari to‘plami ustma-ust tushsa, ya’ni funksiyaning aniqlanish sohasi bilan qiymatlar sohasi bir xil to‘plamni tashkil etsa, bunday bir tomonli funksiya asosida raqamli imzo olish mumkin. Agarda foydalanuvchi aloqa tizimi bo‘yicha mahfiy bo‘lmagan ma’lumotni barcha foydalanuvchilarga yetkazib, bu mahfiy bo‘lmagan ma’lumotni jo‘natuvchini ma’lumotni qabul qilib oluvchilar tomonidan behato aniqlashlari uchun, o‘zining mahfiy algoritmi asosida raqamli imzo qo‘yadi. har bir foydalanuvchi ochiq algoritm ni bilgan holda ni oladi, lekin foydalanuvchidan boshqa foydalanuvchi ma’lumotni kriptogramma ko‘rinishidagi raqamli imzo ifodasiga o‘tkaza olmaydi, chunki faqat foydalanuvchining o‘zigina ochiq algoritm asoslangan funksiyaga teskari bo‘lib, mahfiy algoritm asosini tashkil etuvchi ni hisoblay oladi. o‘z-o‘zidan tushinarliki, agarda foydalanuvchi foydalanuvchiga mahfiy ma’lumotni ham raqamli imzo bilan jo‘natishi mumkin. Buning uchun, foydalanuvchi foydalanuvchining funksiyaga asoslangan ochiq algoritmi (ochiq shifrlash kaliti) dan foydalanib, jo‘natilishi kerak bo‘lgan ma’lumotni shifrlaydi. Bu shifrlangan ma’lumotni qabul qilib olgan foydalanuvchi o‘zining funksiyaga asoslangan mahfiy deshifrlash algoritmi bilan ochadi.
1976 yilda Diffi va Xellman o‘zlarining «Kriptologiyada yangi yo‘nalish» ilmiy ishlarida bir tomonli funksiya sifatida aniqlangan diskret darajaga ko‘tarish funksiyasini taklif qilib, diskret logarifmni hisoblashning amaliy jihatdan murakkabligiga asoslangan edilar. 1978 yilda esa, Massachusets texnologiya institutining olimlari: R.L. Rivest, A. Shamir, L. Adlman, o‘zlarining ilmiy maqolasida birinchi bo‘lib mahfiy uslubli va haqiqatan ham bir tomonli bo‘lgan funksiyani taklif etdilar. Bu maqola «Raqamli imzolarni qurish uslublari va ochiq kalitli kriptosistemalar» deb atalib, ko‘proq autentifikatsiya masalalariga qaratilgan. hozirgi kunda, bu yuqorida nomlari keltirilgan olimlar taklif etgan funksiyani, shu olimlarning sharafiga RSA bir tomonli funksiyasi deyiladi. Bu funksiya murakkab bo‘lmay, uning aniqlanishi uchun, elementar sonlar nazaryasidan ba’zi ma’lumotlar kerak bo‘ladi.
Musbat butun bo‘lgan va sonlarining eng katta umumiy bo‘luvchisini EKUB(i,n) deb belgilaymiz. Misol uchun: EKUB(12, 18)=6, EKUB(9, 27)=9. har qanday musbat butun son uchun Eyler funksiyasi dan katta bo‘lmagan EKUB(i,n) =1 shartni qanoatlantiruvchi barcha i sonlarining sanog‘ini bildiradi. Misol uchun: va xokazo. Ihtiyoriy tub son uchun , hamda deb qabul qilingan. Bundan tashqari, ihtiyoriy p va q tub sonlari uchun ushbu
ifoda o‘rinli bo‘ladi. Misol uchun .
Buyuk matematik olim Eyler(1707-1783) teoremasiga ko‘ra ihtiyoriy musbat butun x va n (0 sonlari uchun EKUB(x,n)=1 shartini qanoatlantiruvchi tenglik bajariladi. Misol uchun:
EKUB(5,6)=1 va
Sonlar nazariyasi kursidan ma’lumki: agarda, e va m butun sonlar 0 va EKUB(m,e)=1 shartlarni qanoatlantirsa, u holda 0 tengsizlikni va
tenglikni qanoatlantiruvchi yagona d butun son mavjud bo‘lib, EKUB(m,e) ni topishning «kengaytirilgan» Yevklid algoritmidan foydalanib d ni topish mumkin.
Yuqorida keltirilgan ma’lumotlardan foydalanib mahfiy uslubli RSA bir tomonli funksiyasini aniqlanishini ko‘rib chiqamiz. Bu funksiya biror n soni moduli bo‘yicha diskret darajaga ko‘tarish funksiyasi, ya’ni
ko‘rinishida aniqlanadi. Bu yerda: x- musbat butun son bo‘lib, n=pq sondan katta emas; n=pq, ya’ni p va q tub sonlari uchun butun e soni dan kichik va EKUB . Shifrlashning ochiq algoritmini asosini tashkil etuvchi funksiya qiymatlarini yuqoridagi ifoda bilan hisoblashni osongina kvadratga ko‘tarish va ko‘paytirish amallariga keltirish mumkin. algoritmni ochiq kalitlar kitobiga kiritish, n va e sonlarini foydalanuvchilar uchun ochiq e’lon qilish demakdir va bunda n sonining ko‘paytuvchilari bo‘lgan p va q tub sonlari mahfiy tutiladi. Teskari funksiya quyidagi
ko‘rinishda bo‘lib, bu yerda d soni n sonidan kichik va ushbu
tenglikni qanoatlantiradi.
Do'stlaringiz bilan baham: |
