Damgård–Jurik kryptosystem

Damgård –Jurik-kryptosystemet är en generalisering av Paillier-kryptosystemet . Den använder beräkningar modulo $n^{s+1}$ där $n$ är en RSA- modul och $s$ ett (positivt) naturligt tal . Pailliers schema är specialfallet med $s=1$ . Ordningen $\varphi (n^{s+1})$ ( Eulers totientfunktion ) av $Z_{n^{s+1}}^ {*}$ kan delas med $n^{s}$ . Dessutom $Z_{n^{s+1}}^{*}$ skrivas som den direkta produkten av $G\times H$ . $G$ är cyklisk och av ordningen $n^{s}$ , medan $H$ är isomorf till $Z_{n}^{*}$ . För kryptering omvandlas meddelandet till motsvarande coset av faktorgruppen $G\times H/H$ och schemats säkerhet beror på svårigheten att särskilja slumpmässiga element i olika coset av ${ \displaystyle H}$ . Det är semantiskt säkert om det är svårt att avgöra om två givna element är i samma coset. Liksom Paillier kan säkerheten för Damgård–Jurik bevisas under beslutssammansatta residuositetsantaganden .

Nyckelgenerering

1. Välj två stora primtal p och q slumpmässigt och oberoende av varandra.
2. Beräkna $n=pq$ och $\lambda =\operatörsnamn {lcm} (p-1,q-1)$ .
3. Välj ett element $g\in \mathbb {Z} _{n^{s+1}}^{*}$ så att $g=(1+n)^{j}x\mod n^{s+1}$ för ett känt $j$ relativt primtal till $n$ och $x\in H$ .
4. Använd den kinesiska restsatsen , välj $d$ så att $d\mod n\in \mathbb {Z} _{n}^{*}$ och $d=0\mod \lambda$ . Till exempel $d$ vara $\lambda$ som i Pailliers ursprungliga schema.

• Den offentliga (krypterings-) nyckeln är $(n,g)$ .
• Den privata (dekrypterings-) nyckeln är $d$ .

Kryptering

1. Låt $m$ vara ett meddelande som ska krypteras där $m\in \mathbb {Z} _{n^{s}}$ .
2. Välj slumpmässigt $r$ där $r\in \mathbb {Z} _{n}^{*}$ .
3. Beräkna chiffertext som: $c=g^{m}\cdot r^{n^{s}}\mod n^{s+1}$ .

Dekryptering

1. Chiffertext $c\in \mathbb {Z} _{n^{s+1}}^{*}$
2. Beräkna $c^{d}\;mod\;n^{s+1}$ . Om c är en giltig chiffertext då $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. Använd en rekursiv version av Pailliers dekrypteringsmekanism för att få $jmd$ . Eftersom $jd$ är känd är det möjligt att beräkna $m=(jmd)\cdot (jd)^{ -1}\;mod\;n^{s}$ .

Förenkling

Till priset av att inte längre innehålla det klassiska Paillier-krypteringssystemet som instans kan Damgård–Jurik förenklas på följande sätt:

• Basen g är fixerad som $g=n+1$ .
• Dekrypteringsexponenten d beräknas så att $d=1\;mod\;n^{s}$ och $d=0\;mod\ ;\lambda$ .

I detta fall ger dekryptering $c^{d}=(1+n)^{m}\;mod\;n^{s+1 }$ . Genom att använda rekursiv Paillier-dekryptering ger detta oss direkt klartexten m .

Se även

• Den interaktiva simulatorn Damgård–Jurik kryptosystem demonstrerar en röstningsapplikation.