Vazirligi mirzo ulug„bek nomidagi

Sonning teskarisini topishga oid misol: a=21, n=41 бўлса, a^-1mod n=?
Avvalo, 21 va 41 sonlari o‗zaro tubligini tekshiramiz: (21,41)=1, demak teskarisi mavjud. n=41 – tub son. Eylеr funksiyasi F(n) 1-formulaga asosan n-1 ga teng, F(n)=40. Eyler teoremasiga asosan 21 sonining teskarisini topamiz:
21⁻¹ mod 41 = 21⁴⁰⁻¹ mod 41 = 21³⁹ mod 41 = ₍ ³ ₎13 = ₍9261mod 41₎13 mod 41 =
21 mod 41 mod 41
= 36¹³ mod 41 = ₍36 ⋅ 36¹² ₎mod 41 = ₍36 ⋅ ₍36³ mod 41₎4 ₎mod 41 = ₍36⋅₍46656 mod 41₎4 ₎mod 41 =
= ₍36 ⋅ 39⁴ ₎mod 41 = ₍36 ⋅ 2313441₎mod 41 = ₍36 ⋅16₎mod 41 = 576 mod 41 = 2


Tekshirish: ⁽2 · 21⁾𝑚𝑜𝑑41 = 42𝑚𝑜𝑑41 = 1. Demak, 21 sonining 41 modul bo‗yicha teskarisi 2 ga teng.

Nazorat uchun savollar:

1. 
   Sonning teskarisi deganda qanday son tushuniladi?
   
2. 
   Sonning teskarisi yagonami?
   
3. 
   Qanday sonlarning teskarisi mavjud emas?
   

Mustaqil ish uchun misollar.

Quyida keltirilgan sonlarning teskarisi topilsin:

1. 
   a=21, n=1763 bo‗lsa, a^-1mod n=?
   
2. 
   a=22, n=41 bo‗lsa, a^-1mod n=?
   
3. 
   a=22, n=1517 bo‗lsa, a^-1mod n=?
   
4. 
   a=23, n=41 bo‗lsa, a^-1mod n=?
   
5. 
   a=23, n=2911 bo‗lsa, a^-1mod n=?
   
6. 
   a=24, n=41 bo‗lsa, a^-1mod n=?
   
7. 
   a=24, n=4171 bo‗lsa, a^-1mod n=?
   
8. 
   a=25, n=41 bo‗lsa, a^-1mod n=?
   
9. 
   a=25, n=4897 bo‗lsa, a^-1mod n=?
   
10. 
    a=26, n=41 bo‗lsa, a^-1mod n=?
    
11. 
    a=26, n=3403 bo‗lsa, a^-1mod n=?
    
12. 
    a=27, n=41 bo‗lsa, a^-1mod n=?
    
13. 
    a=27, n=4687 bo‗lsa, a^-1mod n=?
    
14. 
    a=28, n=41 bo‗lsa, a^-1mod n=?
    
15. 
    a=28, n=9047 bo‗lsa, a^-1mod n=?
    
16. 
    a=29, n=41 bo‗lsa, a^-1mod n=?
    
17. 
    a=29, n=7739 bo‗lsa, a^-1mod n=?
    
18. 
    a=30, n=41 bo‗lsa, a^-1mod n=?
    
19. 
    a=30, n=11639 bo‗lsa, a^-1mod n=?
    
20. 
    a=11, n=41 bo‗lsa, a^-1mod n=?
    
21. 
    a=11, n=1763 bo‗lsa, a^-1mod n=?
    
22. 
    a=12, n=41 bo‗lsa, a^-1mod n=?
    
23. 
    a=22, n=1517 bo‗lsa, a^-1mod n=?
    
24. 
    a=13, n=41 bo‗lsa, a^-1mod n=?
    
25. 
    a=13, n=2911 bo‗lsa, a^-1mod n=?
    
26. 
    a=14, n=41 bo‗lsa, a^-1mod n=?
    
27. 
    a=14, n=4171 bo‗lsa, a^-1mod n=?
    
28. 
    a=15, n=41 bo‗lsa, a^-1mod n=?
    
29. 
    a=15, n=4897 bo‗lsa, a^-1mod n=?
    
30. 
    a=16, n=41 bo‗lsa, a^-1mod n=?
    
31. 
    a=16, n=3403 bo‗lsa, a^-1mod n=?
    
32. 
    a=17, n=41 bo‗lsa, a^-1mod n=?
    
33. 
    a=17, n=4687 bo‗lsa, a^-1mod n=?
    
34. 
    a=18, n=41 bo‗lsa, a^-1mod n=?
    
35. 
    a=18, n=9047 bo‗lsa, a^-1mod n=?
    
36. 
    a=19, n=41 bo‗lsa, a^-1mod n=?
    
37. 
    a=19, n=7739 bo‗lsa, a^-1mod n=?
    
38. 
    a=20, n=41 bo‗lsa, a^-1mod n=?
    
39. 
    a=20, n=11639 bo‗lsa, a^-1mod n=?
    
40. 
    a=31, n=41 bo‗lsa, a^-1mod n=?
    
41. 
    a=31, n=1763 bo‗lsa, a^-1mod n=?
    
42. 
    a=32, n=41 bo‗lsa, a^-1mod n=?
    
43. 
    a=32, n=1517 bo‗lsa, a^-1mod n=?
    

2. Xesh-funksiyalar

Xesh-funksiya – bir taraflama, ya‘ni qandaydir axborot bloki yoki xabarni, ―barmoq izlari‖ fayli yoki daydjеstni olishga mo‗ljallangan funksiya. Xesh-qiymat H funksiyasi orqali hisoblanadi: h=H(M). Bu yerda M - ixtiyoriy uzunlikdagi xabar va h - fiksirlangan uzunlikdagi xesh- qiymat.

1. 
   Xesh-funksiya ixtiyoriy uzunlikdagi xabar uchun hisoblanishi mumkin.
   
2. 
   Xesh-funksiyaning natijaviy xesh-qiymati fiksirlangan qiymat uzunlikda bo‗ladi.
   
3. 
   Ixtiyoriy ma‘lumotlar bloki (x,y) uchun x≠y munosabat o‗rinli bo‗lganda H(x)≠H(y) tеngsizlik bajariladi.
   
4. 
   Ixtiyoriy uzunlikdagi ma‘lumotlar bloki uchun xesh-funksiyani hisoblash muddati uzoq bo‗lmasligi lozim.
   
5. 
   Xesh-qiymatlar ma‘lum bo‗lganda ham xabarni topa olmasligi lozim.
   
6. 
   Ixtiyoriy uzunlikdagi ma‘lumotlar juftligi uchun (x,y) quyidagi H(x)≠H(y) o‗rinli bo‗ladi.
   

1 – 5 shartlarni bajaruvchi funksiyalar oddiy xesh-funksiyalar dеyiladi. 1 – 6 shartlarni bajaruvchi funksiyalar kuchli xesh-funksiyalar dеyiladi.
Shunday qilib, xeshlash funksiyasidan xabar o‗zgarishini payqashda foydalanish mumkin, ya‘ni u kriptografik nazorat yig„indisini (o‗zgarishlarni payqash kodi yoki xabarni autеntifikatsiyalash kodi dеb ham yuritiladi) shakllantirishga xizmat qilishi mumkin. Bu sifatda xesh- funksiya xabarning yaxlitligini nazoratlashda, elеktron raqamli imzoni shakllantarishda va tеkshirishda ishlatiladi.
Xesh-funksiya foydalanuvchini autеntifikatsiyalashda ham kеng qo‗llaniladi. Axborot xavfsizligining qator tеxnologiyalarida shifrlashning o‗ziga xos usuli bir tomonlama xеsh-funksiya yordamida shifrlash ish- latiladi. Bu shifrlashning o‗ziga xosligi shundan iboratki, u mohiyati bo‗yicha bir tomonlamadir, ya‘ni xesh-qiymatdan hech qachon xabarni keltirib chiqarib bo‗lmaydi. Qabul qiluvchi tomon shifrni ochish bilan shug‗ullanmaydi, faqat to‗g‗ri yoki noto‗g‗riligini tekshira oladi.
Eng ommabop xesh-funksiyalar – JH, HAVAL, Keccak (SHA- 3), LM-хеш, MD2, MD4, MD5, MD6, N-Hash, RIPEMD-128, RIPEMD-
160, RIPEMD-256, RIPEMD-320, SHA-1, SHA-2, Skein, Snefru, Tiger, Whirlpool, GOST R 34.11-94, GOST R 34.11-2012.
MD2, MD4, MD5 va MD6 – R.Rivеst tomonidan ishlab chiqilgan axborot daydjеstini hisoblovchi algoritm. Ularning har biri 128 bitli xesh- kodni tuzadi. MD2 algoritmi eng sеkin ishlasa, MD4 algoritmi tеzkor ishlaydi. MD5 algoritmi MD4 algoritmining modifikatsiyasi bo‗lib, MD4 algoritmida xavfsizlikning oshirilishi evaziga tеzlikdan yutqazilgan. SHA (Secure Hash Algorithm) – 160 bitli xesh-kodni tuzuvchi axborot daydjеstini hisoblovchi algoritm. Bu algoritm MD4 va MD5 algoritmlariga nisbatan ishonchliroq.

3.