Texnologiyalari universiteti kriptografiyaning matematik asoslari

5.3. Faktorlash murakkabligiga asoslangan nosimmetrik shifrlar

RSA ochiq kalitli shifrlash algoritmi berilgan yetarli katta toq sonni tub ko‘paytuvchilarga ajratishning rasional usuli mavjud emasligiga asoslangan.
Maxfiy tutiladigan hamda yetarli katta bo‘lgan p va q -tub sonlari olinib, n _ pq -soni va Eyler funksiyasining qiymati n=p1q1 hisoblanadi. Bu n -son ochiq va maxfiy kalitlarni generasiya qilish qoidasining maxfiy tutiladigan parametri hisoblanadi. So‘ngra, e_i ,n1 shartni qanoatlantiruvchi, ya’ni n soni bilan o‘zaro tub bo‘lgan e_i -son bo‘yicha d_i -soni ushbu e_id_i 1modn formula orqali Yevklid algoritmi bo‘yicha hisoblanadi. Bu (e_i ;d_i ) juftlikda e_i ochiq kalit va d_i -maxfiy kalit deb e’lon qilinadi. Shunday qilib RSA kriptotizimi foydalanuvchisining ochiq kaliti (n, e) bo‘lsa, shaxsiy kaliti (d_i, _n) juftligidir.
RSA kriptotizimida i - foydalanuvchidan j - foydalanuvchiga shifrlangan ma’lumotni jo‘natish quyidagicha amalga oshiriladi:

1. 
   Shifrlash qoidasi: ushbu ifoda M^ej modn _C hisoblanadi, bu yerda M ochiq ma’lumot, S –shifrlangan ma’lumot;
   
2. 
   Deshifrlash qoidasi: ushbu ifoda C^{d j} modn _ M ^{e jd j} modn _ M hisoblanib, ochiq ma’lumot M hosil qilinadi.
   

Deshifrlash qoidasidagi C^{d j} modn_ M^{ejd j} modn_ M munosabatning o‘rinliligi quyidagi teoremalardan kelib chiqadi.