Kryptosystém Okamoto – Uchiyama - Okamoto–Uchiyama cryptosystem

The Kryptosystém Okamoto – Uchiyama je kryptosystém veřejného klíče navržené v roce 1998 Tatsuaki Okamoto a Shigenori Uchiyama. Systém pracuje v multiplikativní skupina celých čísel modulo n, ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$, kde n je ve formě p²q a p a q jsou velké připraví.

Úkon

Jako mnozí kryptosystémy veřejného klíče, toto schéma funguje ve skupině ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$. Toto schéma je homomorfní a tudíž tvárný.

Generování klíčů

Pár veřejného / soukromého klíče je generován následovně:

1. Vytvořte dvě velká prvočísla ${displaystyle p}$ a ${displaystyle q}$.
2. Vypočítat ${displaystyle n = p ^ {2} q}$.
3. Vyberte náhodné celé číslo ${displaystyle gin {2dots n-1}}$ takhle ${displaystyle g ^ {p-1} nebo ekvivalentní 1mod p ^ {2}}$.
4. Vypočítat ${displaystyle h = g ^ {n} {mod {n}}}$.

Veřejný klíč je tedy ${displaystyle (n, g, h)}$ a soukromý klíč je ${displaystyle (p, q)}$.

Šifrování

Zpráva ${displaystyle m$ lze zašifrovat veřejným klíčem ${displaystyle (n, g, h)}$ jak následuje.

1. Vyberte náhodné celé číslo ${displaystyle rin {1dots n-1}}$.
2. Vypočítat ${displaystyle c = g ^ {m} h ^ {r} {mod {n}}}$.

Hodnota ${displaystyle c}$ je šifrování ${displaystyle m}$.

Dešifrování

Zašifrovaná zpráva ${displaystyle c}$ lze dešifrovat pomocí soukromého klíče ${displaystyle (p, q)}$ jak následuje.

1. Vypočítat ${displaystyle a = {frac {(c ^ {p-1} {mod {p ^ {2}}}) - 1} {p}}}$.
2. Vypočítat ${displaystyle b = {frac {(g ^ {p-1} {mod {p ^ {2}}}) - 1} {p}}}$. ${displaystyle a}$ a ${displaystyle b}$ budou celá čísla.
3. Za použití Rozšířený euklidovský algoritmus, spočítat inverzní funkci k ${displaystyle b}$ modulo ${displaystyle p}$:

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

4. Vypočítat ${displaystyle m = ab '{mod {p}}}$.

Hodnota ${displaystyle m}$ je dešifrování ${displaystyle c}$.

Příklad

Nechat ${displaystyle p = 3}$ a ${displaystyle q = 5}$. Pak ${displaystyle n = 3 ^ {2} cdot 5 = 45}$. Vybrat ${displaystyle g = 22}$. Pak ${displaystyle h = 22 ^ {45} {mod {4}} 5 = 37}$.

Nyní k zašifrování zprávy ${displaystyle m = 2}$, vybereme náhodně ${displaystyle r = 13}$ a počítat ${displaystyle c = g ^ {m} h ^ {r} {mod {n}} = 22 ^ {2} 37 ^ {13} {mod {4}} 5 = 43}$.

Pro dešifrování zprávy 43 spočítáme

${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}$.

A nakonec ${displaystyle m = ab '= 2}$.

Důkaz správnosti

Chceme dokázat, že hodnota vypočítaná v posledním dešifrovacím kroku, ${displaystyle ab '{mod {p}}}$, se rovná původní zprávě ${displaystyle m}$. My máme

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

Takže se vzpamatovat ${displaystyle m}$ musíme vzít diskrétní logaritmus se základnou ${displaystyle g ^ {p-1}}$.

Skupina

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

Definujeme H což je podskupina ${displaystyle mathbb {Z} / p ^ {2} mathbb {Z} ^ {*}}$ a jeho mohutnost je p-1

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

Pro jakýkoli prvek X v ${displaystyle (mathbb {Z} / p ^ {2} mathbb {Z}) ^ {*}}$, my máme X^p−1 modp² je v H, od té doby p rozděluje X^p−1 − 1.

Mapa ${displaystyle L (x) = {frac {x-1} {p}}}$ by měl být považován za logaritmus z cyklické skupiny H do skupiny aditiv ${displaystyle mathbb {Z} / pmathbb {Z}}$a je snadné to zkontrolovat L(ab) = L(A) + L(b), a že L je izomorfismus mezi těmito dvěma skupinami. Stejně jako u obvyklého logaritmu, L(X)/L(G) je v jistém smyslu logaritmus X se základnouG.

čehož je dosaženo

${displaystyle {frac {Lleft ((g ^ {p-1}) ^ {m} ight)} {L (g ^ {p-1})}} = mmod p.}$^{[je třeba další vysvětlení ]}

Bezpečnostní

Zabezpečení celý zprávu lze zobrazit jako ekvivalent factoringu n.^{[je zapotřebí objasnění ]} The sémantická bezpečnost spočívá na p-podskupinový předpoklad, který předpokládá, že je obtížné určit, zda je prvek X v ${displaystyle (mathbb {Z} / nmathbb {Z}) ^ {*}}$ je v podskupině objednávky p. To je velmi podobné kvadratický problém reziduaity a problém vyšší reziduaity.

Reference

• Okamoto, Tatsuaki; Uchiyama, Shigenori (1998). „Nový kryptosystém veřejného klíče stejně bezpečný jako factoring“. Pokroky v kryptologii - EUROCRYPT'98. Přednášky z informatiky. 1403. Springer. 308–318. doi:10.1007 / BFb0054135.