Ochiq kalitlarning infratuzilmasi

Kalitlarni yaratish

RSA algoritmining kalitlari quyidagi tarzda hosil qilinadi:

1. 
   Ikkita farqni tanlang tub sonlar p va q.
   
   • 
     Xavfsizlik maqsadida butun sonlar p va q tasodifiy tanlanishi kerak va kattaligi o'xshash bo'lishi kerak, lekin faktoringni qiyinlashtirish uchun uzunligi bir necha raqam bilan farqlanadi. A yordamida butun sonlarni samarali topish mumkin dastlabki sinov.
     
   • 
     P va q sir saqlanadi.
     
2. 
   Hisoblash n = pq.
   
   • 
     N sifatida ishlatiladi modul ham ochiq, ham shaxsiy kalitlar uchun. Uning uzunligi, odatda bit bilan ifodalangan, kalit uzunligi.
     
   • 
     N ochiq kalitning bir qismi sifatida chiqariladi.
     
3. 
   Hisoblash λ(n), qaerda λ bu Karmaylning totient funktsiyasi. Beri n = pq, λ(n) = lcm(λ(p),λ(q)) va beri p va q asosiy, λ(p) = φ(p) = p - 1 va shunga o'xshash λ(q) = q - 1. Demak λ(n) = lcm (p − 1, q − 1).
   
   • 
     λ(n) sir saqlanadi.
     
   • 
     Lcm hisoblash mumkin Evklid algoritmi, chunki lcm (a,b) = | ab |/ gcd (a,b).
     
4. 
   Butun sonni tanlang e shu kabi 1 < e < λ(n) va gcd(e, λ(n)) = 1; anavi, e va λ(n)
   
   • 
     e qisqa bit uzunligi va kichik hamming vazni natijada shifrlash samaraliroq bo'ladi - bu eng ko'p tanlangan qiymat e bu 2¹⁶ + 1 = 65,537. Uchun eng kichik (va eng tezkor) mumkin bo'lgan qiymat e 3 ga teng, ammo uchun bunday kichik qiymat e ba'zi sozlamalarda xavfsizligi pastligi ko'rsatilgan.
     
   • 
     eochiq kalitning bir qismi sifatida chiqariladi.
     
5. 
   Aniqlang d kabi d ≡ e⁻¹ (mod λ(n)); anavi, d bo'ladi modulli multiplikativ teskari ning e modul λ(n).
   
   • 
     Buning ma'nosi: uchun hal qilish d tenglama d⋅e ≡ 1 (mod.) λ(n)); d yordamida samarali hisoblash mumkin Kengaytirilgan evklid algoritmi, beri, rahmat e va λ(n) koprime bo'lish, aytilgan tenglama bir shakl Bézout kimligi, qayerda d koeffitsientlardan biridir.
     
   • 
     d kabi sir saqlanadi shaxsiy kalit ko'rsatkichi.
     

Asl RSA qog'ozida, The Eyler totient funktsiyasi φ(n) = (p − 1)(q − 1) o'rniga ishlatiladi λ(n) xususiy ko'rsatkichni hisoblash uchun d. Beri φ(n) har doim bilan bo'linadi λ(n) algoritm ham ishlaydi. Bu Eyler totient funktsiyasi foydalanish mumkin, shuningdek, natijasi sifatida qaralishi mumkin Lagranj teoremasiga qo'llaniladi multiplikativ butun sonli modul pq. Shunday qilib har qanday d qoniqarli d⋅e ≡ 1 (mod.) φ(n)) ham qondiradi d⋅e ≡ 1 (mod.) λ(n)). Biroq, hisoblash d modul φ(n) ba'zan zarur bo'lganidan kattaroq natija beradi (ya'ni.) d > λ(n)). RSA dasturlarining aksariyati har qanday usul yordamida hosil qilingan ko'rsatkichlarni qabul qiladi (agar ular xususiy eksponentdan foydalansalar) d optimallashtirilgan parol hal qilish usulidan foydalanish o'rniga Xitoyning qolgan teoremasiga asoslangan quyida tavsiflangan), ammo ba'zi bir standartlar FIPS 186-4 buni talab qilishi mumkin d < λ(n). Ushbu mezonga mos kelmaydigan har qanday "katta hajmdagi" xususiy eksponentlar har doim modul bilan kamaytirilishi mumkin λ(n) kichikroq ekvivalent ko'rsatkichni olish uchun.
Ning har qanday umumiy omillaridan beri (p − 1) va (q − 1) ning faktorizatsiyasida mavjud n – 1 = pq – 1 = (p − 1)(q − 1) + (p − 1) + (q − 1), tavsiya etiladi (p − 1) va (q − 1) faqat zarur bo'lgan 2dan tashqari, juda kichik umumiy omillarga ega.
RSA qog'oz mualliflari tanlov orqali kalitlarni ishlab chiqarishni amalga oshiradilar d va keyin hisoblash e sifatida modulli multiplikativ teskari ning d modul φ(n), aksincha RSA ning quyidagi amaldagi amaldagi dasturlari PKCS №1, teskari tomonni tanlang (tanlang e va hisoblash d). Tanlangan kalit kichik bo'lishi mumkin, ammo hisoblash kaliti odatda bunday emas, RSA qog'oz algoritmi shifrlash bilan taqqoslaganda shifrlashni optimallashtiradi, zamonaviy algoritm esa uning o'rniga shifrlashni optimallashtir