Xo'rozlar IBE sxemasi - Cocks IBE scheme

Xo'rozlar IBE sxemasi bu identifikatsiyaga asoslangan shifrlash tomonidan taklif qilingan tizim Clifford Cocks 2001 yilda.^[1] Sxema xavfsizligi qattiqlikning qattiqligiga asoslanadi kvadratik qoldiq muammosi.

Protokol

Sozlash

PKG quyidagilarni tanlaydi:

1. jamoat RSA-moduli ${displaystyle extstyle n = pq}$, qayerda ${displaystyle extstyle p, q ,, pequiv qequiv 3 {mod {4}}}$ asosiy va sir saqlanadi,
2. xabar va shifr maydoni ${displaystyle extstyle {mathcal {M}} = chap {-1,1ight}, {mathcal {C}} = mathbb {Z} _ {n}}$ va
3. xavfsiz ommaviy xesh funktsiyasi ${displaystyle extstyle f: left {0,1ight} ^ {*} ightarrow mathbb {Z} _ {n}}$.

Ekstrakt

Qachon foydalanuvchi ${displaystyle extstyle identifikatori}$ shaxsiy kalitini olishni istaydi, u xavfsiz kanal orqali PKG bilan bog'lanadi. PKG

1. kelib chiqadi ${displaystyle extstyle a}$ bilan ${displaystyle extstyle chap ({frac {a} {n}} ight) = 1}$ dan deterministik jarayon bilan ${displaystyle extstyle identifikatori}$ (masalan. ning bir nechta qo'llanilishi ${displaystyle extstyle f}$),
2. hisoblash ${displaystyle extstyle r = a ^ {(n + 5-p-q) / 8} {pmod {n}}}$ (bu ham bajariladi ${displaystyle extstyle r ^ {2} = a {pmod {n}}}$ yoki ${displaystyle extstyle r ^ {2} = - a {pmod {n}}}$, pastga qarang) va
3. uzatadi ${displaystyle extstyle r}$ foydalanuvchiga.

Shifrlash

Bir oz shifrlash uchun (kodlangan ${displaystyle extstyle 1}$/${displaystyle extstyle -1}$) ${displaystyle extstyle min {mathcal {M}}}$ uchun ${displaystyle extstyle identifikatori}$, foydalanuvchi

1. tasodifiy tanlaydi ${displaystyle extstyle t_ {1}}$ bilan ${displaystyle extstyle m = chap ({frac {t_ {1}} {n}} ight)}$,
2. tasodifiy tanlaydi ${displaystyle extstyle t_ {2}}$ bilan ${displaystyle extstyle m = chap ({frac {t_ {2}} {n}} ight)}$, dan farqli ${displaystyle extstyle t_ {1}}$,
3. hisoblash ${displaystyle extstyle c_ {1} = t_ {1} + at_ {1} ^ {- 1} {pmod {n}}}$ va ${displaystyle c_ {2} = t_ {2} -at_ {2} ^ {- 1} {pmod {n}}}$ va
4. yuboradi ${displaystyle extstyle s = (c_ {1}, c_ {2})}$ foydalanuvchiga.

Shifrni ochish

Shifrlangan matnni parolini hal qilish uchun ${displaystyle s = (c_ {1}, c_ {2})}$ foydalanuvchi uchun ${displaystyle ID}$, u

1. hisoblash ${displaystyle alfa = c_ {1} + 2r}$ agar ${displaystyle r ^ {2} = a}$ yoki ${displaystyle alfa = c_ {2} + 2r}$ aks holda, va
2. hisoblash ${displaystyle m = chap ({frac {alfa} {n}} ight)}$.

E'tibor bering, bu erda biz shifrlash mavjudligini bilmaydi deb taxmin qilamiz ${displaystyle ID}$ bor kvadrat ildiz ${displaystyle r}$ ning ${displaystyle a}$ yoki ${displaystyle -a}$. Bunday holda biz ikkala holat uchun ham shifrlangan matn yuborishimiz kerak. Ushbu ma'lumot shifrlash ob'ektiga ma'lum bo'lishi bilanoq, faqat bitta elementni yuborish kerak.

To'g'ri

Birinchi eslatma beri ${displaystyle extstyle pequiv qequiv 3 {pmod {4}}}$ (ya'ni ${displaystyle left ({frac {-1} {p}} ight) = chap ({frac {-1} {q}} ight) = - 1}$) va ${displaystyle extstyle left ({frac {a} {n}} ight) rightarrow left ({frac {a} {p}} ight) = left ({frac {a} {q}} ight)}$, yoki ${displaystyle extstyle a}$ yoki ${displaystyle extstyle -a}$ a kvadratik qoldiq modul ${displaystyle extstyle n}$.

Shuning uchun, ${displaystyle extstyle r}$ ning kvadrat ildizi ${displaystyle extstyle a}$ yoki ${displaystyle extstyle -a}$:

${displaystyle {egin {aligned} r ^ {2} & = left (a ^ {(n + 5-pq) / 8} ight) ^ {2} & = left (a ^ {(n + 5-pq-) Phi (n)) / 8} kech) ^ {2} & = chap (a ^ {(n + 5-pq- (p-1) (q-1)) / 8} tun) ^ {2} & = chap (a ^ {(n + 5-pq-n + p + q-1) / 8} kech) ^ {2} & = chap (a ^ {4/8} tun) ^ {2} & = pm aend {aligned}}}$

Bundan tashqari, (ish uchun ${displaystyle extstyle a}$ kvadratik qoldiq, xuddi shu fikrga asoslanadi ${displaystyle extstyle -a}$):

${displaystyle {egin {aligned} left ({frac {s + 2r} {n}} ight) & = left ({frac {t + at ^ {- 1} + 2r} {n}} ight) = chap ({ frac {tleft (1 + at ^ {- 2} + 2rt ^ {- 1} ight)} {n}} ight) & = left ({frac {tleft (1 + r ^ {2} t ^ {- 2) } + 2rt ^ {- 1} ight)} {n}} ight) = chap ({frac {tleft (1 + rt ^ {- 1} ight) ^ {2}} {n}} ight) & = chap ({frac {t} {n}} ight) chap ({frac {1 + rt ^ {- 1}} {n}} ight) ^ {2} = chap ({frac {t} {n}} ight) (pm 1) ^ {2} = chap ({frac {t} {n}} ight) oxiri {hizalanmış}}}$

Xavfsizlik

Sxemani buzish juda qiyin deb gumon qilinadigan kvadratik qoldiq masalasini echishga teng ekanligini ko'rsatish mumkin. A ni tanlashning umumiy qoidalari RSA moduli ushlab turing: xavfsiz vositadan foydalaning ${displaystyle extstyle n}$, tanlovini qiling ${displaystyle extstyle t}$ bir xil va tasodifiy, shuningdek, ba'zi bir haqiqiyligini tekshirishni o'z ichiga oladi ${displaystyle extstyle t}$ (aks holda, bir moslashuvchan tanlangan shifrlangan matn hujumi bitni uzatuvchi paketlarni o'zgartirish va oracle shifrlangan bitga ta'sirini kuzatish uchun).

Muammolar

Ushbu sxemaning katta kamchiligi shundaki, u bitlarni bitga bittagina shifrlashi mumkin - shuning uchun u faqat sessiya kaliti kabi kichik ma'lumotlar paketlariga mos keladi. Tasvirlash uchun 1024 bitli modul yordamida uzatiladigan 128 bitli kalitni ko'rib chiqing. Keyin 2 × 128 × 1024 bit = 32 KByte yuborish kerak (yoki yo'qligi noma'lum bo'lganda) ${displaystyle r}$ ning kvadrati a yoki -a), bu faqat sessiya tugmachalari kamdan-kam o'zgarib turadigan muhit uchun qabul qilinadi.

Ushbu sxema kalitning maxfiyligini saqlamaydi, ya'ni passiv raqib shifr matnini kuzatayotgan qabul qiluvchining shaxsi to'g'risida mazmunli ma'lumotlarni tiklay oladi.

Adabiyotlar