Mavzu: rsa algoritmi yordamida shifrlash rsa algoritmining tavsifi va bajarilishi. Zamonaviy xakerlik urinishlari Ochiq kalitlarni shifrlash algoritmi rsa

p va q - ikkita tub son (yashirin, tanlangan);
p - pq (ochiq, hisoblangan);
shunday ebu (f (i), e) \u003d 1,1 e
d = e l (mod f (/?)) (maxfiy, hisoblangan).
Shaxsiy kalit quyidagicha tuzilgan (d, n), va oching (e, n).A foydalanuvchisi o'zining ochiq kalitini e'lon qildi va endi B foydalanuvchisi unga M xabarini jo'natmoqchi.
Keyin B foydalanuvchisi shifrlangan xabarni hisoblaydi

Ushbu shifrlangan matnni olgach, A foydalanuvchisi hisoblashni hal qiladi 
Ushbu algoritm uchun mantiqiy asosni taqdim etish mantiqiy. Tanlandi u d shunday
Shunday qilib, ko'rinish hali ham yaxshi. kc\u003e (n) +. Ammo Eyler teoremasi yordamida har qanday ikki tub son uchun p va qu butun sonlar n \u003d pqn M, bu O
Shuning uchun 
Endi bizda bor
10.1-jadvalda RSA algoritmi qisqartirilgan va sek. 10.1 uni qo'llash misolini ko'rsatadi. Ushbu misolda kalitlar quyidagicha hisoblanadi:

• 
  1. Ikkita asosiy raqam tanlandi: p- 7 wq- 17.
  
• 
  2. Hisoblangan n \u003d pq \u003d 7 x 17 \u003d 119.
  
• 
  3. Hisoblangan f (n) - (p -) (q.) - 1) = 96.
  
• 
  4. Tanlangan ef bilan o'zaro kelishish (n) \u003d 96 va f (s) dan kam; bu holda \u003d 5.
  
• 
  5. Bu aniqlanadi d nima de \u003d 1 (mod 96) va d 96. Tegishli qiymat bo'ladi d \u003d 77, chunki 77 x 5 \u003d 385 \u003d 4 x 96 + 1.
  
• 
  6. Natijada KU \u003d (5, 119) va shaxsiy kalit KR \u003d (77, 119) bo'ladi.
  

Ushbu misolda ushbu tugmachalardan foydalanish M \u003d 19 tekis matni bilan ko'rsatilgan, shifrlanganda 19 beshinchi kuchga ko'tariladi, natijada 2 476 099. 119 ga bo'linish natijasida qoldiq 66 ga teng bo'ladi, shuning uchun 19 5 \u003d 66 (mod 119) va shuning uchun 66 raqam shifrlangan matnga ega bo'ladi 


Shakl 10.1.
10.1-jadval
A ob'ekti xabarni B ob'ektiga shifrlangan shaklda uzatishni xohlaydi deb taxmin qiling. Buning uchun biz RSA algoritmidan foydalanamiz. Transmissiya tufayli yoki yomon muammolarga olib kelishi mumkin. Buning uchun foydalaning xatolarni aniqlash usullari . Ammo har xil tarmoqlar uchun har xil usullar.

• 
  b ob'ekti P va Q har qanday ikkita tub tub tubdan iborat;
  
• 
  ob'ekt B modul qiymatini belgilaydi N \u003d P × Q;
  
• 
  ob'ekt B Eyler funktsiyasini hal qiladi: φ (N) \u003d (P-1) × (Q-1);
  va shartlarni hisobga olgan holda K ochiq kalitining qiymatini har qanday usulda tanlaydi: 1 < K в ≤ φ(N), НОД (K в, φ(N)) = 1
  
• 
  b ob'ekti xususiy kalit qiymatini Evklid algoritmini hal qilishda shartga erishishda hal qiladi:  κ in ≡ K ning -1 (mod φ (N)).
  
• 
  ob'ekt B ob'ektni himoyalanmagan yo'l bo'ylab bir juft raqamni (N, K c) yuboradi.
  
• 
  Agar A ob'ekti B ob'ektiga xabar yuborishni istasa Mu boshlang'ich matnni buzishi kerak M bloklarga bo'ling, ularning har biri quyidagi ko'rinishda ko'rsatilishi mumkin: M i \u003d 0, 1, 2, ..., N - 1.
  
• 
  Ob'ekt raqamlarni ketma-ketligi sifatida ko'rsatilgan ma'lumotlarni shifrlaydi M i formula bo'yicha: C i \u003d M i K in (mod N), va C 1, C 2, ..., C i ... kriptogrammasini B ob'ektiga yuboradi.
  
• 
  B foydalanuvchisi C 1, C 2, ..., C i ... kriptogrammasining shifrini ochib, according formulaga muvofiq κ maxfiy kalitini ishlatadi: M i \u003d C i K in (mod N)
  

Amaliyotda algoritmni amalga oshirishda katta xarajatlarsiz katta tub sonlarni hosil qilish, shuningdek, kalitlarning qiymatini tezda hal qilish kerak.
Masalan: xabarni shifrlash
Aniqlik uchun biz kichik raqamlardan foydalanamiz. Ammo amalda juda katta sonlar ishlatiladi (uzunligi 200-300 ta o'nlik).
Ob'ekt B harakatlari:

• 
  P \u003d 3, Q \u003d 11 ni oladi.
  
• 
  N \u003d P × Q \u003d 3 × 11 \u003d 33 modulini oladi.
  
• 
  N \u003d 33 uchun Eyler funktsiyasining qiymatini oladi: φ (N) \u003d (P-1) × (Q-1) \u003d 2 × 10 \u003d 20.
  
• 
  K ochiq kaliti sifatida shartlarga muvofiq ixtiyoriy raqamni oladi: 1 < K в ≤ φ(N), НОД (K в, φ(N)) = 1 , deylik K in \u003d 7.
  
• 
  Yashirin kalitning qiymatini Evklid algoritmi yordamida aniqlaymiz: κ in κ \u003d 3.
  
• 
  ob'ekt B ob'ektni bir juft raqamga yuboradi (N \u003d 33, K in \u003d 7).
  

A ob'ekti xatti-harakatlari:

• 
  Shifrlangan xabarni 0 ... 32 oralig'idagi butun sonlar ketma-ketligi sifatida ko'rsatadi. A harfi 1 raqam bilan berilgan deylik, B harfi - 2 va C \u003d 3. A AB xabari 321 ketma-ketlikda ko'rsatilishi mumkin, deylik, M 1 \u003d 3, M 2 \u003d 1, M 3 \u003d 2.
  
• 
  K, \u003d 7 va N \u003d 33 tugmachasidan foydalanib, M formulaga muvofiq xabarni shifrlaydi: C i \u003d M i K in (mod N) \u003d M i 7 (mod 3).
  
• 
  Biz olamiz:
  
  • 
    C i \u003d 3 7 (mod 33) \u003d 2187 (33-mod) \u003d 9
    
  • 
    C i \u003d 1 7 (mod 33) \u003d 1 (mod 33) \u003d 1
    
  • 
    C i \u003d 2 7 (mod 33) \u003d 128 (mod 33) \u003d 29
    
• 
  Ob'ektga uzatiladigan kriptogrammada: C 1, C 2, C 3 \u003d 9, 1, 29.
  

Ob'ekt B harakatlari:

• 
  Qabul qilingan C 1, C 2, C 3 kriptogrammasining formulasiga binoan ≡ \u003d 3 maxfiy kalit yordamida shifrlangan: M i \u003d C i K in (mod N) \u003d C i 3 (3-mod)
  
  • 
    M 1 \u003d 9 3 (mod 33) \u003d 729 (33-mod) \u003d 3.
    
  • 
    M 2 \u003d 1 3 (mod 33) \u003d 1 (mod 33) \u003d 1.
    
  • 
    M 2 \u003d 29 3 (mod 33) \u003d 24389 (33-mod) \u003d 2.
    

Ob'ekt A tomonidan yuborilgan asl xabarni oldi.
RSA yordamida shifrlash Internet orqali ma'lumotlarni uzatish usullaridan biridir. Rabin pallasi RSA pallasiga juda o'xshash. RSA kriptografik algoritmi kalit uzunligi 1024 bitdan ortiq bo'lgan kuchli deb tan olingan. Shuni ta'kidlash kerakki, algoritm shifrlash uchun ham, raqamli imzo uchun ham qo'llaniladi. Shuni payqash mumkinki, assimetrik RSA kriptotizimida kalitlarning soni simmetrik tizimlarda ishlatilganidek kvadratik emas, balki chiziqli munosabatlar bo'yicha foydalanuvchilar soniga bog'liq (N foydalanuvchilari 2 × N tugmachalarini ishlatadilar).
Ikkinchi qismda biz mashhur RSA algoritmini ko'rib chiqamiz, bu erda shifrlash uchun ochiq kalit ishlatiladi. Lekin avval sizlarni yana ogohlantirmoqchiman. Ushbu maqolada keltirilgan kod faqat ma'lumot olish uchun mo'ljallangan. Kriptografiya juda keng va murakkab sohadir, shuning uchun muammolarga duch kelmaslik uchun men o'z mahoratimdan foydalanib ma'lumotlarni shifrlashni tavsiya etmayman.
Ikkinchi qismda biz mashhur RSA algoritmini ko'rib chiqamiz, bu erda shifrlash uchun ochiq kalit ishlatiladi. Lekin avval sizlarni yana ogohlantirmoqchiman. Ushbu maqolada keltirilgan kod faqat ma'lumot olish uchun mo'ljallangan. Kriptografiya juda keng va murakkab sohadir, shuning uchun muammolarga duch kelmaslik uchun men o'z mahoratimdan foydalanib ma'lumotlarni shifrlashni tavsiya etmayman.