|
Ushbu bo'limda biz ba'zi klassik gomomorfik shifrlash tizimlarini tasvirlaymiz
kriptografiya sohasidagi tadqiqotchilar o'rtasida katta qiziqish uyg'otdi. Biz boshlaymiz
1982 yilda Goldwasser va Micali tomonidan taklif qilingan birinchi ehtimoliy tizimlar bilan (Goldwasser)
& Micali, 1982; Goldwasser & Micali, 1984) va keyin mashhur Paillier-ning shifrlashini muhokama qiling
sxemasi (Paillier, 1999) va uni takomillashtirish. Paillier sxemasi va uning variantlari taniqli ularning samaradorligi va homomorfik shifrlashning yuqori darajadagi xavfsizligi uchun tion. Biz ularning matematik mulohazalarini batafsil muhokama qilmaymiz, balki ularni umumlashtiramiz muhim parametrlar va xususiyatlar.
Goldwasser-Micali sxemasi: Ushbu sxema (Goldwasser & Micali, 1982; Goldwasser & Micali, 1984) tarixiy jihatdan juda muhimdir, chunki gomomorfikaga oid ko'plab keyingi takliflar shifrlash asosan uning yondashuvi bilan bog'liq edi. RSA singari, ushbu sxemada biz foydalanamiz
hisoblashlar moduli n = p.q, ikkita katta son hosilasi. Shifrlash jarayoni oddiy bu mahsulot va kvadratdan foydalanadi, parol hal qilish esa og'irroq va ko'rsatkichni o'z ichiga oladi.
Parolni hal qilish jarayonining murakkabligi: O (k.l (p)
2), bu erda l (p) bit sonini bildiradi
p. Afsuski, ushbu sxema cheklangan, chunki uning kiritilishi bitta bitdan iborat. Birinchidan, bu k bitlarni shifrlash O (k.l (p) narxiga olib kelishini anglatadi
2). Bu juda samarali emas buni amaliy deb hisoblash mumkin. Ikkinchi tashvish kengaytirish masalasi bilan bog'liq - a bitta matnli matn butun modulda, ya'ni l (n) bitda shifrlangan. Bu juda katta narsaga olib keladi shifrlangan matnni portlatish ushbu sxemada jiddiy muammo tug'diradi.
Goldwasser-Micali (GM) sxemasini boshqa nuqtai nazardan ko'rib chiqish mumkin. Qachon qaragan
bu burchak, ushbu sxemaning asosiy printsipi - bu to'g'ri tanlangan butun sonlarni ajratish modul n ikkita maxfiy qismga bo'linadi: M0 va M1
. Shifrlash jarayoni tasodifiy elementni tanlaydi
Mb
oddiy matnni b shifrlash uchun va parolni hal qilish jarayoni foydalanuvchiga qaysi qismda ekanligini bilib olishga imkon beradi
tasodifiy tanlangan element yotadi. Sxemaning mohiyati aniqlash mexanizmida yotadi pastki qism va uni M0 ga bo'lish
va M1
. Bunga erishish uchun sxema guruh nazariyasidan foydalanadi
maqsad. Ichki to'plam - bu teskari butun sonlarning G guruhi, ular bilan Jacobi belgisi mavjud n ga nisbatan, 1 ga teng. Bo'lim boshqa H ⊂G guruhi tomonidan hosil qilinadi
10 Kriptografiya nazariyasi va amaliyoti va tarmoq xavfsizligi protokollari va texnologiyalari teskari omil n ga nisbatan Jakobi belgisi bilan qaytariladigan modul n bo'lgan elementlar, ga teng 1. Ushbu parametr parametrlari bilan G ni ikki qismga - H va G ga bo'lish mumkin \ H. GMning umumlashtirish sxemalari ushbu ikki guruhga tegishli. Ushbu sxemalar bunga harakat qilmoqda ikkita G va H guruhlarni toping, shunda G ni k = 2 qismdan ko'proq bo'lish mumkin.
Benaloh sxemasi: Benaloh (Benaloh, 1988) - bu GM sxemasini umumlashtirish bo'lib, unga imkon beradi
$ l (k) $ bitlarini kiritishni boshqarish, $ k $ ba'zi bir cheklovlarni qondiradigan asosiy daraja.
Shifrlash
GM sxemasidagi kabi (xabarni shifrlash m ∈ {0,…., k - 1} yig'ish bilan barobardir tamsayı r ∈ Zn
*
va hisoblash c = g m
r k
mod n). Biroq, parolni hal qilish bosqichi ko'proq
murakkab. Agar kirish va chiqish o'lchamlari mos ravishda l (k) va l (n) bit bo'lsa, kengayish tengdir l (n) / l (k) gacha. Ushbu yondashuvda olingan kengayish qiymati GMda erishilganidan kamroq. Bu sxemani yanada jozibali qiladi. Bundan tashqari, shifrlash ham qimmat emas. Parolni hal qilish jarayonida xarajatlar oldindan hisoblash uchun O (k.l (k)) ga teng
bu har bir dinamik shifrlash bosqichi uchun doimiy bo'lib qoladi. Bu k ning qiymati borligini anglatadi juda kichik qabul qilinishi kerak, bu esa o'z navbatida kengayish qiymatidan olinadigan daromadni cheklaydi.
Naccache-Stern sxemasi: Ushbu sxema (Naccache & Stern, 1998) Benalohning takomillashtirilishi
sxema. K parametrining Benaloh sxemasida ishlatilganidan kattaroq qiymatidan foydalanib, u kichikroq kengayishga erishadi va shu bilan yuqori samaradorlikka erishadi. Shifrlash bosqichi aynan Benaloh sxemasi bilan bir xil. Biroq, parolni hal qilish boshqacha. Ning qiymati kengayish Benaloh sxemasida bo'lgani kabi, ya'ni l (n) / l (k). Biroq, parolni hal qilish qiymati kamroq va quyidagicha berilgan: O (l (n)
5
log (l (n)). Mualliflarning ta'kidlashicha, qadriyatlarni tanlash mumkin tizimdagi parametrlarning kengayishining erishilgan qiymati 4 ga teng bo'ladigan tarzda (Naccache & Stern, 1998).
Okamoto-Uchiyama sxemasi: homo bo'yicha oldingi sxemalarning ishlashini yaxshilash morfik shifrlash, Okamoto va Uchiyama G guruhining asosiy guruhini o'zgartirdi (Okamoto va Uchiya )‐
ma, 1998). N = p 2 ni olib
q, p va q odatdagidek ikkita katta tub son va guruh
G = Z p
2018-04-01 121 2
*
, mualliflar k = p ga erishadilar. Sxema bo'yicha olingan kengayish qiymati 3. Bir
ushbu sxemaning eng katta afzalliklaridan biri shundaki, uning xavfsizligi faktorizatsiyaga tengdir n. Biroq, tanlangan shifrlangan matn
Do'stlaringiz bilan baham: |
