Benaloh kriptosistemasi - Benaloh cryptosystem

The Benaloh Kriptosistemasi ning kengaytmasi Goldwasser-Micali kriptosistemasi (GM) 1985 yilda Josh (Koen) Benaloh tomonidan yaratilgan. Benaloh Kriptosistemasining GM bo'yicha yaxshilanishi shundan iboratki, ma'lumotlarning uzunroq bloklari birdan shifrlanishi mumkin, GM da har bir bit alohida-alohida shifrlanadi.^[1][2][3]

Sxema ta'rifi

Ko'pchilik singari ochiq kalitli kriptosistemalar, ushbu sxema guruhda ishlaydi ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$ qayerda n ikkita katta mahsulot asosiy. Ushbu sxema gomomorfik va shuning uchun egiluvchan.

Kalit avlod

Blok hajmi berilgan r, ochiq / xususiy kalit juftligi quyidagicha hosil bo'ladi:

1. Katta sonlarni tanlang p va q shu kabi ${displaystyle rvert (p-1), operator nomi {gcd} (r, (p-1) / r) = 1,}$ va ${displaystyle operator nomi {gcd} (r, (q-1)) = 1}$
2. O'rnatish ${displaystyle n = pq, phi = (p-1) (q-1)}$
3. Tanlang ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ shu kabi ${displaystyle y ^ {phi / r} ot equiv 1mod n}$.

Eslatma: Agar r kompozitdir, buni Fousse va boshqalar ta'kidladilar. 2011 yilda^[4] yuqoridagi shartlar (ya'ni asl qog'ozda ko'rsatilgan holatlar) to'g'ri parolni ochishni kafolatlash uchun etarli emas, ya'ni ${displaystyle D (E (m)) = m}$ barcha holatlarda (shunday bo'lishi kerak). Buni hal qilish uchun mualliflar quyidagi tekshiruvni taklif qilishadi: ruxsat bering ${displaystyle r = p_ {1} p_ {2} nuqta p_ {k}}$ ning asosiy faktorizatori bo'lish r. Tanlang ${displaystyle yin mathbb {Z} _ {n} ^ {*}}$ har bir omil uchun ${displaystyle p_ {i}}$, bu shunday ${displaystyle y ^ {phi / p_ {i}} eq 1mod n}$.

1. O'rnatish ${displaystyle x = y ^ {phi / r} mod n}$

Ochiq kalit shunda ${displaystyle y, n}$va shaxsiy kalit ${displaystyle phi, x}$.

Xabarlarni shifrlash

Xabarni shifrlash uchun ${displaystyle min mathbb {Z} _ {r}}$:

1. Tasodifiy tanlang ${displaystyle uin mathbb {Z} _ {n} ^ {*}}$
2. O'rnatish ${displaystyle E_ {r} (m) = y ^ {m} u ^ {r} mod n}$

Xabarni parolini hal qilish

Shifrlangan matnni parolini hal qilish uchun ${displaystyle cin mathbb {Z} _ {n} ^ {*}}$:

1. Hisoblash ${displaystyle a = c ^ {phi / r} mod n}$
2. Chiqish ${displaystyle m = log _ {x} (a)}$, ya'ni toping m shu kabi ${displaystyle x ^ {m} equiv amod n}$

Shifrni hal qilishni tushunish uchun avvalo hamma uchun e'tibor bering ${displaystyle min mathbb {Z} _ {r}}$ va ${displaystyle uin mathbb {Z} _ {n} ^ {*}}$ bizda ... bor:

${displaystyle a = (c) ^ {phi / r} equiv (y ^ {m} u ^ {r}) ^ {phi / r} equiv (y ^ {m}) ^ {phi / r} (u ^ { r}) ^ {phi / r} equiv (y ^ {phi / r}) ^ {m} (u) ^ {phi} equiv (x) ^ {m} (u) ^ {0} equiv x ^ {m } mod n}$

Qayta tiklash uchun m dan a, biz olamiz alohida jurnal ning a tayanch x. Agar r kichik, biz to'liq qidirish orqali mni tiklashimiz mumkin, ya'ni ${displaystyle x ^ {i} equiv amod n}$ Barcha uchun ${displaystyle 0dots (r-1)}$. Ning katta qiymatlari uchun r, Chaqaloq qadam - ulkan qadam tiklash uchun algoritmdan foydalanish mumkin m yilda ${displaystyle O ({sqrt {r}})}$ vaqt va makon.

Xavfsizlik

Ushbu sxemaning xavfsizligi Yuqori qoldiq muammosi, xususan, berilgan z,r va n bu erda faktorizatsiya n noma'lum, yo'qligini aniqlash uchun hisoblash mumkin emas z bu rqoldiq rejimi n, ya'ni mavjud bo'lsa x shu kabi ${displaystyle zequiv x ^ {r} mod n}$.

Adabiyotlar