Ryukzak algoritmi

Mustaqil ish uchun misollar.

1. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={163, 314, 591, 62}, M=?
   
2. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={437, 101, 294, 286}, M=?
   
3. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={275, 213, 90, 490 }, M=?
   
4. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={ 90, 286, 325, 275 }, M=?
   
5. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={398, 518, 163, 275 }, M=?
   
6. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={163, 275, 398, 518 }, M=?
   
7. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={479, 437, 367, 286 }, M=?
   
8. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={367, 437, 325, 275 }, M=?
   
9. 
   m=397, n=17, a={2,3,6,12,24,49,100,200}, C={101, 286, 437, 213 }, M=?
   
10. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={398, 437, 367, 294 }, M=?
    
11. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={426, 437, 591, 294 }, M=?
    
12. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={591, 437, 367, 294 }, M=?
    
13. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={518, 314, 202, 275 }, M=?
    
14. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={426, 437, 101, 202 }, M=?
    
15. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={90, 437, 266, 275 }, M=?
    
16. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={101, 286, 325, 275 }, M=?
    
17. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={294, 286, 367, 314 }, M=?
    
18. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={591, 62, 314, 367 }, M=?
    
19. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={591, 275, 90, 437 }, M=?
    
20. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={398, 437, 101, 275 }, M=?
    
21. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={163, 314, 591, 62}, M=?
    
22. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={437, 101, 294, 286}, M=?
    
23. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={275, 213, 90, 490 }, M=?
    
24. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={90, 286, 325, 275 }, M=?
    
25. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={398, 518, 163, 275 }, M=?
    
26. 
    m=727, n=111, a={2,3,6,12,24,49,100,200}, C={540,662,378,662, 296}, M=?
    
27. 
    m=727, n=111, a={2,3,6,12,24,49,100,200}, C={613,285,378, 418,573}, M=?
    
28. 
    m=727, n=111, a={2,3,6,12,24,49,100,200}, C={8,662,378,236,41}, M=?
    
29. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={296,142,30,296, 377}, M=?
    
30. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={378,377,72, 223, 367}, M=?
    
31. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={82,40, 101, 142, 184}, M=?
    
32. 
    m=397, n=17, a={2,3,6,12,24,49,100,200}, C={ 30, 19, 396, 367, 40}, M=?
    

II. RSA algoritmi
Ochiq kalitli kriptotizimlarni bir tomonli funksiyalar ko’rinishi bo’yicha farqlash mumkin. Bularning ichida RSA, El-Gamal va Mak-Elis tizimlarini alohida tilga olish o’rinli. Hozirda eng samarali va kеng tarqalgan ochiq kalitli shifrlash algoritmi sifatida RSA algoritmini ko’rsatish mumkin.
1976 yilda Uitfild Diffi va Martin Xellmanlar tomonidan chop etilgan “Kriptografiyada yangi yo’nalish” deb nomlangan maqola kriptografik tizimlar haqidagi tasavvurlarni o’zgartirib yubordi, ochiq kalitli kriptografiya paydo bo’lishiga zamin yaratdi. Bu maqolani o’rganib chiqqan Massachusets texnologiyalar instituti olimlari Ronald Rivest, Adi Shamir va Leonard Adleman 1977 yilda RSA algoritmini yaratdilar.
RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan olingan. Algoritm modul arifmеtikasining darajaga ko’tarish amalidan foydalanishga asoslangan. 1977 yil avgust oyida Scientific Americanjurnalida RSA kriptotizimini yoritib berishdi va shu algoritm bilan shifrlangan quyidagi iborani ochishni o’quvchilarga taklif etishdi:

C=
n=1143816257578888676692357799761466120102182967212423 62562561842935706935245733897830597123563958705058989075147 599290026879543541, e=9007, M=?
Mukofot sifatida 100 AQSh dollari e‘lon qilindi. Algoritm avtorlaridan biri Rivest bu shifrni ochishga 40 kvadrillion yil ketishini aytgan bo’lsa, 1993 yil 3 sentabrdan 1994 yil mart oyigacha 20 ta mamlakatdan 600 ta ko’ngilli shaxslar 1600 ta kompyuterda parallel ishlab bu shifrni ochishdi –THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.
1982 yilda Ronald Rivest, Adi Shamir va Leonard Adleman RSA Data Security kompaniyasini tashkil etishdi. 1989 yildan boshlab RSA algoritmi Internetda foydalanila boshlandi. 1990 yildan boshlab AQSh mudofaa vazirligi foydalana boshladi.1993 yilda PKCS1 standartining 1.5 versiyasida RSA algoritmini shifrlash va elektron imzo yaratishda qo’llash keltirildi. Bu standartning oxirgi versiyalari RFCstandartida keltirilgan (RFC 2313— 1.5, 1993 yil;RFC 2437— 2.0, 1998 yil;RFC 3447— 2.1, 2002 yil).
Algoritmni quyidagi qadamlar kеtma-kеtligi ko’rinishida ifodalash mumkin:

1. 
   Ikkita katta tub son p va q tanlanadi.
   
2. 
   Kalitning ochiq tashkil etuvchisi n hosil qilinadi: n=p·q.
   
3. 
   Quyidagi formula bo’yicha k (Eylеr funksiyasi qiymati) hisoblanadi: k=(p-1)(q-1).
   
4. 
   k qiymati bilan o’zaro tub bo’lgan katta tub son e tanlab olinadi.
   
5. 
   Quyidagi shartni qanoatlantiruvchi d soni aniqlanadi: d =e^-1 mod k .
   

Bu shartga binoan e*d ko’paytmaning k qiymatga bo’lishdan qolgan qoldiq 1 ga tеng. e soni ochiq kalitning ikkinchi tashkil etuvchisi sifatida qabul qilinadi. Yopiq kalit sifatida d soni ishlatiladi.

6. 
   Dastlabki axborot uning fizik tabiatidan qat‘iy nazar raqamli ikkili ko’rinishda ifodalanadi. Bitlar kеtma-kеtligi L bit uzunlikdagi bloklarga ajratiladi, bu yerda blok sifatida L < log₂(n+1) shartini qanoatlantiruvchi eng katta butun sonni olish tavsiya etiladi. Har bir blok [0, n-1] oraliqqa taalluqli butun musbat son kabi ko’riladi. Shunday qilib, dastlabki axborot M_i, i=1,I sonlarning kеtma-kеtligi orqali ifodalanadi. I ning qiymati shifrlanuvchi kеtma-kеtlikning uzunligi orqali aniqlanadi.
   
7. 
   Shifrlangan axborot quyidagi formula bo’yicha aniqlanuvchi C_i sonlarning kеtma-kеtligi ko’rinishida olinadi:
   

C_i= mod n.
Axborotni ochishda quyidagi munosabatdan foydalaniladi:
M_i= mod n.
Bugungi kunda RSA tizimi programma ta‘minoti xavfsizligini ta‘minlashda va elektron raqamli imzo sxemalarida foydalaniladi. Shifrlash tezligining pastligi sababli (2 GHz protsessorlarda 512 bitli kalit yordamida 30 kb/s tezlikda shifrlaydi) simmetrik algoritmlarning kalitlarini shifrlab uzatishda ko’proq foydalaniladi.
Misol.
Modul son n=p*q=1517, (p-1)*(q-1) ko’paytma bilan o’zaro tub bo’lgan e=11 ochiq kalit, shifrlanadigan matn M=BESH so’zi va matn uzunligi L=8 bit berilgan. Agar L berilmagan bo’lsa, L=[log₂(n+1)] formula orqali topiladi.