Shifrlash

Asimmetrik shifrlash

Yuqorida aytib o'tilganidek, assimetrik shifrlash algoritmlarida ikkita kalit ishlatiladi: k1 - bu shifrlash kaliti yoki ommaviy, k2 - bu shifrlash kaliti yoki maxfiy. Ochiq kalit sirdan hisoblanadi: k1 \u003d f (k2).

Asimmetrik shifrlash algoritmlari bir tomonlama funktsiyalardan foydalanishga asoslangan. Ta'rif bo'yicha y \u003d f (x) funktsiya bir yo'nalishda emas, agar: barchasini hisoblash oson bo'lsa mumkin bo'lgan variantlar x va mumkin bo'lgan y qiymatlari uchun y \u003d f (x) bo'lgan x qiymatini hisoblash juda qiyin.

Bir tomonlama funktsiyaga misol qilib ikkita katta raqamni ko'paytirishni aytish mumkin: N \u003d P * Q. Bunday ko'payishning o'zi oddiy operatsiya. Ammo, zamonaviy vaqt hisob-kitoblariga ko'ra, faktorizatsiya deb nomlangan teskari funktsiya (N ni ikkita katta omilga ajratish) ancha murakkab matematik muammodir. Masalan, P-da 664 bitdan N faktoring? Q, taxminan 1023 ta operatsiyani bajarish kerak, va x, a, p va y (a va p o'lchovlari bilan) ma'lum bo'lgan y \u003d ax mod p modulli ko'rsatkich uchun taxminan 1026 ta operatsiyani bajarish talab etiladi. Ushbu misollarning oxirgisi "Diskret logaritm muammosi" (DLP) deb nomlanadi va bunday funktsiya ko'pincha assimetrik shifrlash algoritmlarida, shuningdek elektron raqamli imzolarni yaratish uchun ishlatiladigan algoritmlarda qo'llaniladi.

Asimmetrik shifrlashda ishlatiladigan funktsiyalarning yana bir muhim klassi orqa tarafdagi bir tomonlama funktsiyalardir. Ularning ta'rifida aytilishicha, funktsiya sirli o'tish bilan bir yo'nalishga ega va agar u bir yo'nalishda bo'lsa va teskari funktsiyani x \u003d f-1 (y) ni samarali hisoblash mumkin, ya'ni "yashirin o'tish" ma'lum bo'lsa (ma'lum bir maxfiy raqam, unga nisbatan qo'llaniladigan). assimetrik shifrlash algoritmlari uchun - maxfiy kalitning qiymati).

Tashqi ko'rinishdagi bir tomonlama funktsiyalar mashhur RSA assimetrik shifrlash algoritmida qo'llaniladi.

RSA algoritmi

1978 yilda uchta muallif (Rivest, Shamir, Adleman) tomonidan ishlab chiqilgan bo'lib, u o'z nomini ishlab chiquvchilar familiyasining birinchi harflaridan oldi. Algoritmning mustahkamligi ko'p sonli faktorlarni aniqlash va diskret logaritmlarni hisoblashning murakkabligiga asoslanadi. RSA algoritmining asosiy parametri N tizim moduli bo'lib, unga muvofiq tizimdagi barcha hisob-kitoblar amalga oshiriladi va N \u003d P * Q (P va Q - yashirin tasodifiy katta raqamlar, odatda bir xil o'lchamdagi).

K2 maxfiy kaliti tasodifiy tanlanadi va quyidagi shartlarga javob berishi kerak:

1

bu erda GCD eng katta umumiy bo'linuvchi, ya'ni k1 Euler F (N) funktsiyasining qiymati bilan tenglashtirilishi kerak, u 1 dan N gacha bo'lgan musbat butun sonlar soniga teng, N bilan yozish va quyidagicha hisoblanadi. F (N) \u003d (P - 1) * (Q - 1).

Ochiq kalit k1 aloqadan hisoblanadi (k2 * k1) \u003d 1 mod F (N)va buning uchun umumlashtirilgan Evklid algoritmi (eng katta umumiy bo'linuvchini hisoblash algoritmi) qo'llaniladi. M bloklar bloki RSA algoritmi yordamida quyidagicha shifrlangan: C \u003d M [k1 kuchiga] mod N... Shuni yodda tutingki, RSA-dan foydalanib haqiqiy kriptotizim tizimida k1 soni juda katta (hozirgi vaqtda uning o'lchami 2048 bitgacha yetishi mumkin), M ni to'g'ridan-to'g'ri hisoblash [k1 kuchiga] xayoliy emas. Uni olish uchun ko'p sonli M ning natijalarini ko'paytirish bilan birikmasidan foydalaniladi.

Katta o'lchovlar uchun ushbu funktsiyani burish mumkin emas; boshqacha qilib aytganda, ma'lum C, N va k1 dan M ni topish mumkin emas. Shu bilan birga, k2 maxfiy kalitiga ega bo'lib, oddiy o'zgarishlardan foydalanib, biz M \u003d Ck2 mod N. ni hisoblashimiz mumkin. Shubhasiz, maxfiy kalitning o'zi bilan bir qatorda, P va Q parametrlarining maxfiyligini ta'minlash kerak, agar tajovuzkor ularning qiymatlarini qo'lga kiritsa, u k2 maxfiy kalitini hisoblash imkoniyatiga ega bo'ladi.