• 2.3.2. RSA algoritmi
  • Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot



    bet25/149
    Sana10.09.2024
    Hajmi
    #270811
    1   ...   21   22   23   24   25   26   27   28   ...   149
    Bog'liq
    kiberxavfsizlik-asoslari

    Teorema.
    Aytaylik,
    a
    va 
    b
    natural sonlar,
    𝑑𝑑
    = EKUB( a ,
    𝑎𝑎
    )
    bo’lsin. U 
    holda shunday
    α
    va 
    β
    butun sonlar topiladiki
    α

    a +
    β

    𝑎𝑎
    =
    𝑑𝑑

    tenglik o’rinli bo’ladi. 
    Demak, bu algoritm nafaqat ikkita natural sonning EKUBini, balki 
    yoyilmadagi
    α
    va 
    β
    koeffisentlarni ham topish imkonini berar ekan. Shunisi bilan 
    ham aslida Yevklid algoritmidan farqlanadi. 
    Kengaytirilgan Yevklid algoritmiga muvofiq topiladigan 
    α
    va 
    β
    butun 
    sonlar, quyidagi Diafant tenglamasining
    α

    a +
    β

    𝑎𝑎
    =
    𝑑𝑑

    butun yechimlari hisoblanadi. Bundan RSA algoritmining ochiq kalitiga ko’ra 
    maxfiy kalitini hisoblashda foydalanish mumkin. Shu sababli bu algoritm ishlash 
    qadamlari bilan yaqindan tanishib chiqiladi. 


    48 
    Faraz qilaylik,

    va
    b
    sonlarning EKUBni topishda quyidagi ketma-ketlik 
    qaralayotgan bo’lsin: 
    a= b*q
    1
     + r
    1
    r
    1
    = ax
    1
     + by
    1;
     
     
     
    b = r
    1
    * q
    2
     + r
    2
    r
    2
    = ax
    2
    + by
    2

     
     
    r
    1
    = r
    2
     *q
    3
     + r
    3

    3
    = ax
    3
    + by
    3


     
    ………………. ……………….. 
     
     

    n-3
    = r
    n-2
    * q 
    n-1 
    + r 
    n-1

    n-1 
    =ax 
    n-1
    + by 
    n-1
     
     
     

    n-2 
    = r 
    n-1
    * q
    n

    n
     =0; 
    Bu yerda,
     x
    1
    , x
    2
    ,….x 
    n-1 
     
    va
    u
    1
    , u
    2
    ……y
    n -1
    sonlarini topish kerak bo’lsin. Bu sonlar quyidagi formula yordamida topiladi: 
    x
    j
    = x 
    j-2
     – q 


    j-1 
    va u

     = y 
    j - 2
     
     
    - q
    j
     y
    j-1

    bu yerda, 

    -1
    =1 , u
    -1
     =0 , x
    0
     =0 , u
    0
     =1.
    Kerakli ma’lumotlarni quyidagi jadval orqali aniqlash mumkin: 
    qoldiqlar 
    bo’luvchi 


    a


    -1
     
    u
    -1 



    0
     
    y
    -1
     

    1
     
    r


    3
     





    n-2


    n-1
     
    q
    1
     
    q
    2
     
    q
    3
     




    q
    n-2
     

    n-1
     
    x
    1
     
    x
    2
     
    x
    3
     





    n-2


    n-1
     
    y

    y
    2
     
    y
    3
     




    y
    n-2
     
    y
    n-1 
     
    Jadvalning oxirgi ustunida keltirilgan ikki qiymat izlanayotgan alfa va beta 
    koeffisentlar, yani
    α
     = x 
    n-1 

    β
     = u
    n-1
    bo’ladi. 


    49 
    Misol
    . Yevklid algoritmini qo’llab EKUB (6188,4709) va
    α
    ,
    β
    - qiymatlar 
    topilsin. 
    Yevklid algoritmi qadamlariga muvofiq: 
    6188=4709*1+1479, ya’ni r
    1
    =1479 
    4709=1479*3+272, ya’ni r
    2
    =272 
    1479=272*5+119, ya’ni r
    3
    =119 
    272=119*2+34, ya’ni r
    4
    =34 
    119=34*3+17, ya’ni r
    5
    =17 
    34=17*2+0, ya’ni r
    6
    =0 
    demak,
    r
    5
    =17
    soni 6188 va 4709 sonlarining EKUBi deb e’lon kilinadi, ya’ni
    EKUB (6188, 4709)=17 .
    Kengaytirilgan Yevklid algoritmiga ko’ra: 
    6188*
    α
    + 4709 *
    β
    =17 
    α
    =?,
    β
    =? topilsin: 
    yuqorida keltirilgan ifodani quyidagicha yozish mumkin: 
    17=119 – 34*3 
    34=272 – 119*2 
    119=1479 – 272*5 
    272=4709 – 1479*3 
    1479=6188 – 4709*1 
    yoki: 
    17= 119 – 3* (272 – 119*2)=7*119 – 3*272=7* (1479 – 272*5) – 3*272= 
    =7*1479 - 38*272=7*1479 – 38* (4709 – 1479*3)=121*1479 – 38*4709= 
    =121* (6188 - 4709) – 38*4709=121*6188 – 159*4709 ,
    Ya’ni, 
    6188*121+4709* (- 159)=17; demak,
    α
    =121; 
    β
    = - 159 
    Javob
    :
    α
    =121, 
    β
    = - 159. 


    50 
    Misol. 
    3
    −1
    𝑆𝑆𝑒𝑒𝑑𝑑
    7
    ≡ 𝑥𝑥
     
    ni topish talab etilgan bo’lsin. Yuqorida keltirilgan 
    algoritmga ko’ra 
    7 = 3

    2 + 1
     
    3 = 1

    3 + 0
     
    Qoldig’i nolga teng bo’lgan tenglikdan oldingi tenglikdan boshlab 
    quyidagicha teskari yozish amalga oshiriladi: 
    1 = 7

    (3

    2) = 7 + (

    2

    3) = 7

    1 + (

    2

    3)
     
    Yuqoridagi tenglikni ikki tomonini modulga (
    𝑆𝑆𝑒𝑒𝑑𝑑
    7)
    olinsa quyidagi 
    tenglikga ega bo’linadi: 

    (7

    1)
    𝑆𝑆𝑒𝑒𝑑𝑑
    7 + (

    2

    3)
    𝑆𝑆𝑒𝑒𝑑𝑑
    7
    �𝑆𝑆𝑒𝑒𝑑𝑑
    7

    1
    𝑆𝑆𝑒𝑒𝑑𝑑
    7
     
    yoki 
    (

    2

    3)
    𝑆𝑆𝑒𝑒𝑑𝑑
    7

    1
    𝑆𝑆𝑒𝑒𝑑𝑑
    7

    1
    . Ushbu tenglikni 
    (3
    ∗ 𝑥𝑥
    )
    𝑆𝑆𝑒𝑒𝑑𝑑
    7

    1
    taqqoslash 
    orqali 
    𝑥𝑥
    =

    2
    ga tengligini yoki 

    2
    𝑆𝑆𝑒𝑒𝑑𝑑
    7 = 5
    ligini topish mumkin. Ya’ni, 
    (3

    5)
    𝑆𝑆𝑒𝑒𝑑𝑑
    7

    1
    tenglikni qanoatlantiradi.
     
    Javob
    3
    −1

    𝑆𝑆𝑒𝑒𝑑𝑑
    7) = 5.
     
    2.3.2. RSA algoritmi 
    RSA nomi algoritmni yaratuvchilari familiyalarining birinchi harflaridan 
    olingan (Rivest, Shamir va Adleman). RSA algoritmi modul arifmetikasining 
    darajaga ko’tarish amalidan foydalanishga asoslangan [20].
    RSA algoritmida ochiq va shaxsiy kalitlar juftini generasiya qilish uchun 
    ikkita katta uzunlikdagi 
    𝑆𝑆
    va 
    𝑞𝑞
    sonlari tanlanadi va ularning ko’paytmasi 
    hisoblanadi: 
    𝑁𝑁
    =
    𝑆𝑆 ∗ 𝑞𝑞
    . Shundan so’ng 
    𝜑𝜑
    (
    𝑁𝑁
    ) = (
    𝑆𝑆 −
    1)

    (
    𝑞𝑞 −
    1)
    bilan o’zaro tub 
    bo’lgan, 
    𝑒𝑒
    soni tanlanadi (
    𝜑𝜑
    (
    𝑁𝑁
    )
    funksiya ma’nosi quyida keltirilgan). Shundan 
    so’ng 
    𝜑𝜑
    (
    𝑁𝑁
    )
    modulda 
    𝑒𝑒
    sonining teskarisi hisoblanadi va u 
    𝑑𝑑
    ga teng bo’ladi. 
    Shundan so’ng, ikkita tub sonlarning (
    𝑆𝑆
    va 
    𝑞𝑞
    ) ko’paytmasi 
    𝑁𝑁
    va 
    𝑒𝑒𝑑𝑑
    = 1 
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝜑𝜑
    (
    𝑁𝑁
    )
    shartni qanoatlantiruvchi 
    𝑒𝑒
    va 
    𝑑𝑑
    sonlari mavjud. Shundan so’ng, 
    𝑆𝑆
    va 
    𝑞𝑞
    lar esdan 
    chiqariladi (o’chirib tashlanadi). 
    Bu yerda, 
    𝑁𝑁
    modul hisoblanib, (
    𝑁𝑁
    ,
    𝑒𝑒
    ) ochiq kalit juftini va 
    𝑑𝑑
    maxfiy kalitni 
    tashkil etadi. RSA algoritmida shifrlash va deshifrlash modul bo’yicha darajaga 


    51 
    oshirish asosida bajariladi. RSA algoritmida shifrlash uchun 
    𝑀𝑀
    xabarni son 
    ko’rinishida ifodalash talab etiladi va 
    𝑁𝑁
    modul bo’yicha 
    𝑒𝑒
    darajaga ko’tariladi, ya’ni 
    𝐶𝐶
    =
    𝑀𝑀
    𝑒𝑒
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁


    ni deshifrlash uchun uni 
    𝑁𝑁
    modul bo’yicha shaxsiy kalit 
    𝑑𝑑
    darajaga 
    ko’tarish talab etiladi: 
    𝑀𝑀
    =
    𝐶𝐶
    𝑑𝑑
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁

    Boshqacha aytganda RSA algoritmida xabar ochiq kalit bilan shifrlansa va 
    shaxsiy kalit bilan deshifrlansa, 
    𝑀𝑀
    =
    𝐶𝐶
    𝑑𝑑
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁

    𝑀𝑀
    𝑒𝑒𝑑𝑑
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁
    tenglik 
    to’g’riligini isbotlash zarur. 
    Eyler teoremasi. 
    Agar 
    𝑥𝑥
    haqiqiqatdan 
    𝑛𝑛
    bilan o’zaro tub bo’lsa, 
    𝑥𝑥
    𝜑𝜑
    (
    𝑛𝑛
    )
    =

    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑛𝑛
    bo’ladi. Bu yerda, 
    𝜑𝜑
    (
    𝑛𝑛
    )
    – funksiya, 
    𝑛𝑛
    dan kichik va u bilan o’zaro tub 
    bo’lgan sonlar miqdorini ko’rsatadi. Agar 
    𝑛𝑛
    soni tub bo’lsa, 
    𝜑𝜑
    (
    𝑛𝑛
    ) =
    𝑛𝑛 −
    1
    bo’ladi.
    Shuning uchun 
    𝑒𝑒𝑑𝑑
    = 1 
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝜑𝜑
    (
    𝑁𝑁
    ) = 1 
    𝑆𝑆𝑒𝑒𝑑𝑑
    (
    𝑆𝑆 −
    1)(
    𝑞𝑞 −
    1)
    tenglik kabi 
    yozish mumkin. Mazkur tenglikning to’liq shakli aslida 
    𝑒𝑒𝑑𝑑
    = 1 
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝜑𝜑
    (
    𝑁𝑁
    ) +
    𝑘𝑘
    𝜑𝜑
    (
    𝑁𝑁
    )
    ga teng. Ya’ni, 
    𝑒𝑒𝑑𝑑
    ko’paytmani 
    𝜑𝜑
    (
    𝑁𝑁
    )
    ga bo’lganda 
    𝑘𝑘
    tadan tegib, bir 
    qoldiq qolgan. Shuning uchun ushbu tenglikni quyidagicha yozish mumkin: 
    𝑒𝑒𝑑𝑑 −
    1 =
    𝑘𝑘
    𝜑𝜑
    (
    𝑁𝑁
    )

    Ushbu tengliklardan, RSA algoritmining to’g’ri ishlashini tasdiqlash mumkin: 
    𝐶𝐶
    𝑑𝑑
    =
    𝑀𝑀
    𝑒𝑒𝑑𝑑
    =
    𝑀𝑀
    (
    𝑒𝑒𝑑𝑑−1
    )
    +1
    =
    𝑀𝑀 ∗ 𝑀𝑀
    𝑒𝑒𝑑𝑑−1
    =
    𝑀𝑀 ∗ 𝑀𝑀
    𝑘𝑘
    𝜑𝜑
    (
    𝑁𝑁
    )
    =
    𝑀𝑀 ∗
    1
    𝑘𝑘
    =
    𝑀𝑀
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁
    .
    Aytaylik, RSA algoritmida ma’lumotni shifrlash va deshifrlash amallarini 
    tanlab olingan (
    𝑆𝑆
    = 11 va 
    𝑞𝑞
    = 3
    ) “katta” sonlar ustida amalga oshirish talab qilinsin. 
    Mazkur holda modul 
    𝑁𝑁
    =
    𝑆𝑆 ∗ 𝑞𝑞
    = 33
    ga teng bo’ladi va 
    𝜑𝜑
    (
    𝑁𝑁
    ) = (
    𝑆𝑆 −
    1)(
    𝑞𝑞 −
    1) = 20
    ga teng bo’ladi. U holda shifrlash uchun zarur bo’lgan daraja 

    ni (
    𝑒𝑒
    = 3

    ga teng deb olish mumkin. Sababi, 3 soni 
    𝜑𝜑
    (
    𝑁𝑁
    ) = 20
    bilan o’zaro tubdir. Shundan 
    so’ng, Evklidning kengaytirilgan algoritmi asosida deshifrlash kaliti (
    𝑑𝑑
    = 7

    aniqlanadi. Ya’ni, 
    𝑒𝑒𝑑𝑑
    = 3

    7 = 1 
    𝑆𝑆𝑒𝑒𝑑𝑑
    20
    . U holda A tomonning ochiq kalit jufti 
    (
    𝑁𝑁
    ,
    𝑒𝑒
    ) = (33,3)
    va shaxsiy kaliti esa 
    𝑑𝑑
    = 7
    ga teng.


    52 
    Shundan so’ng, A tomon o’zining ochiq kalitini barchaga uzatadi. Biroq, 
    shaxsiy kalitini maxfiy saqlaydi.
    Faraz qilaylik, B tomon A tomonga 
    𝑀𝑀
    = 15
    ma’lumotni shifrlab 
    yubormoqchi. Buning uchun B tomon A tomonning ochiq kaliti juftini 
    (
    𝑁𝑁
    ,
    𝑒𝑒
    ) =
    (33,3)
    oladi va shifrmatnni quyidagicha hisoblaydi: 
    𝐶𝐶
    =
    𝑀𝑀
    𝑒𝑒
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁
    = 15
    3
    = 3375 = 9 
    𝑆𝑆𝑒𝑒𝑑𝑑
    33
     
    va uni A tomonga yuboradi.
    A tomon 
    𝐶𝐶
    = 9
    shifrmatnni deshifrlash uchun shaxsiy kalit 
    𝑑𝑑
    = 7
    dan 
    foydalanadi: 
    𝑀𝑀
    =
    𝐶𝐶
    𝑑𝑑
    𝑆𝑆𝑒𝑒𝑑𝑑
    𝑁𝑁
    = 9
    7
    = 4782969 = 144938

    33 + 15 = 15 
    𝑆𝑆𝑒𝑒𝑑𝑑
    33
     
    Agar RSA algoritmida kichik tub sonlardan (
    𝑆𝑆
    va 
    𝑞𝑞
    uchun
    ) foydalanilgan 
    taqdirda, hujumchi ochik bo’lgan 
    𝑁𝑁
    ni osonlik bilan ikkita tub sonning ko’paytmasi 
    ko’rinishida yozishi mumkin. Shundan so’ng, ochiq kalitning ikkinchi qism 
    𝑒𝑒
    dan 
    foydalangan holda, shaxsiy kalit 
    𝑑𝑑
    ni hisoblay oladi. Shuning uchun RSA 
    algoritmidan amalda foydalanish uchun tanlanuvchi tub sonlar uzunligi kamida 2048 
    bit bo’lishi talab etiladi. Bundan tashqari, RSA algoritmini buzish faqat faktorlash 
    muammosiga bog’liqligi isbotlanmagan. Boshqacha aytganda, RSA algoritmini 
    buzishning faktorlash muammosini yechishdan tashqari biror usuli aniqlanmagan.

    Download
    1   ...   21   22   23   24   25   26   27   28   ...   149




    Bosh sahifa
    Aloqalar

        Bosh sahifa



    Respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot