Kryptosystém Damgård – Jurik - Damgård–Jurik cryptosystem

The Kryptosystém Damgård – Jurik^[1] je zobecněním Kryptosystém Paillier. Využívá výpočty modulo ${displaystyle n ^ {s + 1}}$ kde ${displaystyle n}$ je RSA modul a ${displaystyle s}$ pozitivní) přirozené číslo. Paillierův režim je zvláštní případ ${displaystyle s = 1}$. Objednávka ${displaystyle varphi (n ^ {s + 1})}$ (Eulerova totientová funkce ) z ${displaystyle Z_ {n ^ {s + 1}} ^ {*}}$ lze rozdělit na ${displaystyle n ^ {s}}$. Navíc, ${displaystyle Z_ {n ^ {s + 1}} ^ {*}}$ lze psát jako přímý produkt z ${displaystyle G imes H}$. ${displaystyle G}$ je cyklický a řádový ${displaystyle n ^ {s}}$, zatímco ${displaystyle H}$ je izomorfní s ${displaystyle Z_ {n} ^ {*}}$. Pro šifrování se zpráva transformuje na odpovídající coset z skupina faktorů ${displaystyle G imes H / H}$ a bezpečnost schématu závisí na obtížnosti rozlišování náhodných prvků v různých kosetech ${displaystyle H}$. to je sémanticky bezpečné pokud je těžké rozhodnout, zda jsou dva dané prvky ve stejné cosetu. Stejně jako Paillier lze zabezpečení Damgård – Jurik prokázat pod předpoklad rozhodující složené reziduaity.

Generování klíčů

1. Vyberte si dva velké prvočísla p a q náhodně a nezávisle na sobě.
2. Vypočítat ${displaystyle n = pq}$ a ${displaystyle lambda = operatorname {lcm} (p-1, q-1)}$.
3. Vyberte prvek ${displaystyle gin mathbb {Z} _ {n ^ {s + 1}} ^ {*}}$ takhle ${displaystyle g = (1 + n) ^ {j} xmod n ^ {s + 1}}$ pro známou ${displaystyle j}$ relativní prime na ${displaystyle n}$ a ${displaystyle xin H}$.
4. Za použití Čínská věta o zbytku, Vybrat ${displaystyle d}$ takhle ${displaystyle dmod nin mathbb {Z} _ {n} ^ {*}}$ a ${displaystyle d = 0mod lambda}$. Například ${displaystyle d}$ mohlo by být ${displaystyle lambda}$ jako v původním schématu Pailliera.

• Veřejný (šifrovací) klíč je ${displaystyle (n, g)}$.
• Soukromý (dešifrovací) klíč je ${displaystyle d}$.

Šifrování

1. Nechat ${displaystyle m}$ být zpráva, která má být zašifrována ${displaystyle min mathbb {Z} _ {n ^ {s}}}$.
2. Vyberte náhodně ${displaystyle r}$ kde ${displaystyle rin mathbb {Z} _ {n ^ {s + 1}} ^ {*}}$.
3. Vypočítat šifrovací text jako: ${displaystyle c = g ^ {m} cdot r ^ {n ^ {s}} mod n ^ {s + 1}}$.

Dešifrování

1. Šifrovací text ${displaystyle cin mathbb {Z} _ {n ^ {s + 1}} ^ {*}}$
2. Vypočítat ${displaystyle c ^ {d}; mod; n ^ {s + 1}}$. Li C je tedy platný šifrovací text ${displaystyle c ^ {d} = (g ^ {m} r ^ {n ^ {s}}) ^ {d} = ((1 + n) ^ {jm} x ^ {m} r ^ {n ^ { s}}) ^ {d} = (1 + n) ^ {jmd; mod; n ^ {s}} (x ^ {m} r ^ {n ^ {s}}) ^ {d; mod; lambda} = (1 + n) ^ {jmd; mod; n ^ {s}}}$.
3. Chcete-li získat, použijte rekurzivní verzi dešifrovacího mechanismu Paillier ${displaystyle jmd}$. Tak jako ${displaystyle jd}$ je známo, je možné počítat ${displaystyle m = (jmd) cdot (jd) ^ {- 1}; mod; n ^ {s}}$.

Zjednodušení

Za cenu, že už nebude obsahovat klasiku Kryptosystém Paillier jako příklad lze Damgård – Jurik zjednodušit následujícím způsobem:

• Základna G je opraven jako ${displaystyle g = n + 1}$.
• Dešifrovací exponent d je vypočítán tak, že ${displaystyle d = 1; mod; n ^ {s}}$ a ${displaystyle d = 0; mod; lambda}$.

V tomto případě dojde k dešifrování ${displaystyle c ^ {d} = (1 + n) ^ {m}; mod; n ^ {s + 1}}$. Použitím rekurzivního Paillierova dešifrování nám to dává přímo holý text m.

Viz také

• The Interaktivní simulátor kryptosystému Damgård – Jurik předvádí hlasovací aplikaci.

Reference