Okamoto – Uchiyama kriptosistemasi - Okamoto–Uchiyama cryptosystem

The Okamoto – Uchiyama kriptosistemasi a ochiq kalit kriptosistemasi tomonidan 1998 yilda taklif qilingan Tatsuaki Okamoto va Shigenori Uchiyama. Tizim multiplikativ butun sonli guruh moduli n, ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$, qayerda n shakldadir p²q va p va q katta asosiy.

Ishlash

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

Kalitlarni yaratish

Ochiq / shaxsiy kalit juftligi quyidagicha hosil bo'ladi:

1. Ikkita katta sonni yarating ${displaystyle p}$ va ${displaystyle q}$.
2. Hisoblash ${displaystyle n = p ^ {2} q}$.
3. Tasodifiy sonni tanlang ${displaystyle gin {2dots n-1}}$ shu kabi ${displaystyle g ^ {p-1} ot equiv 1mod p ^ {2}}$.
4. Hisoblash ${displaystyle h = g ^ {n} {mod {n}}}$.

Ochiq kalit shunda ${displaystyle (n, g, h)}$ va shaxsiy kalit ${displaystyle (p, q)}$.

Shifrlash

Xabar ${displaystyle m$ ochiq kalit bilan shifrlanishi mumkin ${displaystyle (n, g, h)}$ quyidagicha.

1. Tasodifiy sonni tanlang ${displaystyle rin {1dots n-1}}$.
2. Hisoblash ${displaystyle c = g ^ {m} h ^ {r} {mod {n}}}$.

Qiymat ${displaystyle c}$ ning shifrlashidir ${displaystyle m}$.

Parolni hal qilish

Shifrlangan xabar ${displaystyle c}$ maxfiy kalit bilan parolini ochish mumkin ${displaystyle (p, q)}$ quyidagicha.

1. Hisoblash ${displaystyle a = {frac {(c ^ {p-1} {mod {p ^ {2}}}) - 1} {p}}}$.
2. Hisoblash ${displaystyle b = {frac {(g ^ {p-1} {mod {p ^ {2}}}) - 1} {p}}}$. ${displaystyle a}$ va ${displaystyle b}$ butun sonlar bo'ladi.
3. Dan foydalanish Kengaytirilgan evklid algoritmi, ning teskarisini hisoblang ${displaystyle b}$ modul ${displaystyle p}$:

   ${displaystyle b '= b ^ {- 1} {mod {p}}}$.

4. Hisoblash ${displaystyle m = ab '{mod {p}}}$.

Qiymat ${displaystyle m}$ ning parolini hal qilish ${displaystyle c}$.

Misol

Ruxsat bering ${displaystyle p = 3}$ va ${displaystyle q = 5}$. Keyin ${displaystyle n = 3 ^ {2} cdot 5 = 45}$. Tanlang ${displaystyle g = 22}$. Keyin ${displaystyle h = 22 ^ {45} {mod {4}} 5 = 37}$.

Endi xabarni shifrlash uchun ${displaystyle m = 2}$, biz tasodifiy tanlaymiz ${displaystyle r = 13}$ va hisoblash ${displaystyle c = g ^ {m} h ^ {r} {mod {n}} = 22 ^ {2} 37 ^ {13} {mod {4}} 5 = 43}$.

43-xabarni parolini hal qilish uchun biz hisoblaymiz

${displaystyle a = {frac {(43 ^ {2} {mod {3}} ^ {2}) - 1} {3}} = 1}$.

${displaystyle b = {frac {(22 ^ {2} {mod {3}} ^ {2}) - 1} {3}} = 2}$.

${displaystyle b '= 2 ^ {- 1} {mod {3}} = 2}$.

Va nihoyat ${displaystyle m = ab '= 2}$.

To'g'ri ekanligining isboti

Biz oxirgi parolni hal qilishda hisoblangan qiymatni isbotlamoqchimiz, ${displaystyle ab '{mod {p}}}$, asl xabarga teng ${displaystyle m}$. Bizda ... bor

${displaystyle (g ^ {m} h ^ {r}) ^ {p-1} equiv (g ^ {m} g ^ {nr}) ^ {p-1} equiv (g ^ {p-1}) ^ {m} g ^ {p (p-1) rpq} ekviv (g ^ {p-1}) ^ {m} mod p ^ {2}}$

Shunday qilib tiklash uchun ${displaystyle m}$ biz olishimiz kerak alohida logaritma taglik bilan ${displaystyle g ^ {p-1}}$.

Guruh

${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*} simeq (mathbb {Z} / p ^ {2} mathbb {Z}) ^ {*} imes (mathbb {Z} / qmathbb {Z}) ^ {*}}$.

Biz aniqlaymiz H qaysi kichik guruh hisoblanadi ${displaystyle mathbb {Z} / p ^ {2} mathbb {Z} ^ {*}}$ va uning muhimligi p-1

${displaystyle H = {x: x ^ {p-1} mod p ^ {2} = 1 + rp, 0$.

Har qanday element uchun x yilda ${displaystyle (mathbb {Z} / p ^ {2} mathbb {Z}) ^ {*}}$, bizda ... bor x^p−1 modp² ichida H, beri p ajratadi x^p−1 − 1.

Xarita ${displaystyle L (x) = {frac {x-1} {p}}}$ tsiklik guruhdan logaritma deb qarash kerak H qo'shimchalar guruhiga ${displaystyle mathbb {Z} / pmathbb {Z}}$va buni tekshirish oson L(ab) = L(a) + L(b) va bu L bu ikki guruh o'rtasidagi izomorfizmdir. Odatiy logaritmada bo'lgani kabi, L(x)/L(g) qaysidir ma'noda ning logarifmidir x taglik bilang.

tomonidan amalga oshiriladi

${displaystyle {frac {Lleft ((g ^ {p-1}) ^ {m} ight)} {L (g ^ {p-1})}} = mmod p.}$^{[qo'shimcha tushuntirish kerak ]}

Xavfsizlik

Xavfsizligi butun xabar faktoringga teng ekranda ko'rsatilishi mumkin n.^{[tushuntirish kerak ]} The semantik xavfsizlik ga asoslangan p- element yoki yo'qligini aniqlash qiyinligini taxmin qiladigan kichik guruh taxminlari x yilda ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$ buyurtmaning kichik guruhida joylashgan p. Bu juda o'xshash kvadratik qoldiq muammosi va yuqori qoldiq muammosi.

Adabiyotlar

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). "Faktoring kabi xavfsiz yangi ochiq kalitli kriptotizim". Kriptologiya sohasidagi yutuqlar - EUROCRYPT'98. Kompyuter fanidan ma'ruza matnlari. 1403. Springer. 308-318 betlar. doi:10.1007 / BFb0054135.