• Scientific American
  • Shifrni ochish
    		•

    Rsa algoritmi




    Download 220,75 Kb.
    Sana23.09.2024
    Hajmi220,75 Kb.
    #272109
    Bog'liq
    9-amaliy mashg\'ulot


    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 American jurnalida RSA kriptotizimini yoritib berishdi va shu algoritm bilan shifrlangan quyidagi iborani ochishni o‘quvchilarga taklif etishdi:

    C=
    n=114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, 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 RFC standartida 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 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 < log2(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 Mi, 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 Ci sonlarning kеtma-kеtligi ko‘rinishida olinadi:

    Axborotni ochishda quyidagi munosabatdan foydalaniladi:

    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 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=[log2(n+1)] formula orqali topiladi.
    Shifrlash:

    1. BE SH so‘zini ASCII jadvali yordamida bit ko‘rinishga o‘tkazamiz: 01000010 01000101 01010011 01001000.

    2. Bitlardan iborat matnni 8 bitdan bloklarga ajratamiz va har bir blokni o‘nlik sanoq sistemasiga o‘tkazamiz: M1=66, M2=69, M3=83, M4=72.

    3. formula yordamida shifrlanadi:

    , ,

    Hosil bo‘lgan shifrtekst quyidagicha:
    Shifrni ochish:
    Modul son ko‘paytma bilan o‘zaro tub bo‘lgan e=11 ochiq kalit, matn uzunligi L=8 bit va bizga ma’lum.

    1. e sonining modul bo‘yicha teskarisini topamiz:

    2. formula yordamida shifrni ochamiz:


    3. Mi larni o‘nlikdan ikkilikka o‘tkazib, ASCII jadval yordamida harflarga o‘tamiz va natijada M=BESH so‘zi paydo bo‘ladi
    Download 220,75 Kb.




    Download 220,75 Kb.