Paye kryptosystém

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. září 2017; kontroly vyžadují 11 úprav .

Peyetův kryptosystém je pravděpodobnostní kryptosystém s veřejným klíčem , který vynalezl francouzský kryptograf Pascal Paillier v roce 1999 . Podobně jako kryptosystémy RSA , Goldwasser-Micali a Rabin je Peyeův kryptosystém založen na složitosti faktorizace složeného čísla , které je součinem dvou prvočísel . [jeden]

Schéma je aditivní homomorfní kryptosystém, to znamená, že známe pouze veřejný klíč a šifrové texty odpovídající otevřeným textům a můžeme vypočítat šifrový text otevřeného textu . [2] $m_1$ $m_2$ ${\displaystyle m_{1}+m_{2))$

Historie

Algoritmus poprvé navrhl Pascal Peyet ve svém článku v roce 1999 [3] . Článek popsal předpoklad o složitosti výpočtu kořene zbytku modulo a navrhl vhodný mechanismus pro použití tohoto matematického problému pro kryptografické účely. Původní článek uvádí, že kryptosystém může být zranitelný vůči útokům na základě zvoleného šifrového textu , ale již v roce 2001 se ukázalo, že s mírnou změnou původního schématu přestává být kryptosystém vůči takovým útokům zranitelný [4] . V roce 2006 byla navržena metoda ke zvýšení účinnosti a bezpečnosti kryptosystému Peye založená na ověřitelných permutacích [5] .

Popis algoritmu

Algoritmus funguje následovně: [3]

Generování klíčů

Vyberte dvě velká prvočísla a takové, že . $p$ $q$ $\gcd(pq,(p-1)(q-1))=1$
a počítá se . $n=pq$ $\lambda =\operatorname {lcm} (p-1,q-1)$
Je vybráno náhodné celé číslo , např $G$ $g\in \mathbb {Z} _{n^{2}}^{*}$
Kde se počítá . $\mu =(L(g^{\lambda }\mod n^{2}))^{-1}{\bmod {n))$ $L(u)=div({\frac {u-1}{n)))$

Veřejný klíč je pár . $(n,g)$
Soukromý klíč je pár $(\lambda ,\mu ).$

Šifrování

Předpokládejme, že prostý text musí být zašifrován , $m$ $m\in \mathbb {Z} _{n}$
Vyberte náhodné číslo $r$ $r\in \mathbb {Z} _{n}^{*}$
Vypočítejte šifrový text $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$

Dešifrování

Přijímáme šifrovaný text $c\in \mathbb {Z} _{n^{2}}^{*}$
Vypočítejte původní zprávu $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$

Elektronický podpis

Pro práci v režimu elektronického podpisu je vyžadována hašovací funkce . $h:\mathbb {N} \mapsto \{0,1\}^{k}\subset \mathbb {Z} _{n^{2}}^{*}$

Podpis zprávy

Aby bylo možné podepsat zprávu , je nutné počítat $m$

$s_{1}={\frac {L(h(m)^{\lambda }{\bmod {n}}^{2})}{L(g^{\lambda }{\bmod {n }}^{2})}}{\bmod {n}}$

$s_{2}=(h(m)g^{-s_{1)))^({\frac {1}{n)){\bmod {\lambda ))}{\bmod {n} }$

Elektronický podpis bude dvojice . $(s_{1},s_{2})$

Ověření podpisu

Podpis je považován za platný, pokud jsou splněny následující podmínky:

$h(m)=g^{s_{1}}s_{2}^{n}{\bmod {n}}^{2}$ .

Homomorfní vlastnosti

Charakteristickým rysem kryptosystému Peye je jeho homomorfismus . Protože je šifrovací funkce aditivně homomorfní, lze zapsat následující identity [2] :

Homomorfní přidávání otevřených textů

Součin dvou šifrovaných textů bude dešifrován jako součet jejich příslušných otevřených textů,

D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n))^{2})=m_{1}+m_ {2}{\bmod {n}}.

Vynásobením šifrového textu dostaneme součet odpovídajících otevřených textů,

g^{m_{2))

D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{ \bmod{n}}.

Homomorfní násobení otevřených textů

Šifrovaný text povýšený na sílu jiného šifrovaného textu bude dešifrován jako produkt dvou otevřených textů,

D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n }},

D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n }}.

Obecně platí, že zvýšení šifrovaného textu na mocninu bude dešifrováno jako produkt otevřeného textu pomocí ,

k

k

D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.

Generalizace

V roce 2001 Ivan Damgard a Mads Jurik navrhli zobecnění [6] kryptosystému Peye. K tomu se navrhuje provést výpočty modulo , kde , je přirozené číslo . Upravený algoritmus vypadá takto: $n^{s+1}$ $n=p*q$ $s$

Generování klíčů

Náhodně a nezávisle na sobě jsou vybrána dvě velká prvočísla a . $p$ $q$
a počítá se . $n=pq$ $\lambda =\operatorname {lcm} (p-1,q-1)$
Číslo je vybráno tak, že , kde je známé hlavní číslo s a . $g\in \mathbb {Z} _{n^{s+1}}^{*}$ $g=(1+n)^{j}x{\bmod {n}}^{s+1}$ $j$ $n$ $x\v H$
Pomocí čínské věty o zbytku se volí takové, že a . Může se například rovnat původnímu kryptosystému Paye. $d$ $d{\bmod {n}}\in \mathbb {Z} _{n}^{*}$ $d=0{\bmod {\lambda ))$ $d$ $\lambda$

Veřejný klíč je pár . $(n,g)$
Soukromý klíč je . $d$

Šifrování

Řekněme, že chceme zašifrovat zprávu , kde . $m$ $m\in \mathbb {Z} _{n^{s))$
Vybereme náhodné číslo takové, že . $r$ $r\in \mathbb {Z} _{n^{s+1}}^{*}$
Vypočítáme šifrový text . $c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}$

Dešifrování

Předpokládejme, že máme šifrovaný text a chceme jej dešifrovat. $c\in \mathbb {Z} _{n^{s+1}}^{*}$
Vypočítáme . Pokud se skutečně jedná o šifrový text, pak platí následující rovnosti: . $c^{d}\;mod\;n^{s+1}$ $C$ $c^{d}=(g^{m}r^{n^{s)))^{d}=((1+n)^{jm}x^{m}r^{n^ {s}})^{d}=(1+n)^{jmd\;bmod\;n^{s}}(x^{m}r^{n^{s}})^{d\; bmod\;\lambda }=(1+n)^{jmd\;bmod\;n^{s}}$
K získání dat používáme rekurzivní verzi mechanismu dešifrování kryptosystému Peye . Protože součin je znám, můžeme vypočítat . $jmd$ $jd$ ${\displaystyle m=(jmd)\cdot (jd)^{-1}\;bmod\;n^{s))$

Aplikace

Elektronické hlasování

Pomocí kryptosystému Peyet je možné organizovat volby mezi několika kandidáty pomocí následujícího schématu: [7] [8]

Nechť je počet voličů a takový, že . $N$ $k\in \mathbb {N}$ ${\displaystyle N<2^{k))$
Pokud chce volič hlasovat pro kandidátní číslo , pak toto číslo zašifruje a přijatý šifrovaný text odešle koordinátorovi voleb. $i$ ${\displaystyle 2^{k(i-1)))$
Při sumarizaci výsledků voleb koordinátor dešifruje součin všech šifrovaných textů obdržených od voličů. Je snadné vidět, že první bity výsledku poskytnou počet hlasů odevzdaných pro prvního kandidáta, druhé bity udají počet hlasů odevzdaných druhému kandidátovi a tak dále. $k$ $k$

Elektronická loterie

Pomocí kryptosystému Paye můžete organizovat elektronickou loterii následovně: [7] [8]

Ať se hráči chtějí zúčastnit loterie, každý má svůj vlastní los s jedinečným číslem . $N$ $n\in \{0,\tečky ,N-1\}$
Každý hráč si vybere náhodné číslo, zašifruje ho a odešle organizátorovi loterie.
Aby bylo možné vypočítat „šťastný“ tiket, organizátor dešifruje součin všech přijatých šifrových textů, přičemž obdrží součet náhodných čísel vygenerovaných hráči. Organizátor loterie vyhlásí výherce tiketu s číslem . $s$ $s{\bmod {n))$

Je snadné vidět, že všichni účastníci budou mít stejnou pravděpodobnost výhry, i když se hráči pokusí zfalšovat výsledek loterie zasláním předem připravených čísel pořadateli. $n-1$

Elektronická měna

Dalším výrazným rysem kryptosystému Peye je takzvané samoslepování [ . Tento termín se odkazuje na schopnost změnit šifrovaný text bez změny holého textu . Toho lze využít při vývoji systémů elektronických měn, jako je ecash . Řekněme, že chcete zaplatit za položku online, ale nechcete obchodníkovi sdělit číslo své kreditní karty , a tedy svou identitu. Stejně jako u elektronického hlasování můžeme ověřit platnost e-coinu (nebo e-hlasu), aniž bychom odhalili identitu osoby, se kterou je aktuálně spojen.

Poznámky

↑ Jonathan Katz, Yehuda Lindell, „Úvod do moderní kryptografie: Principy a protokoly“, Chapman & Hall/CRC, 2007
↑ 1 2 Varnovsky N. P., Shokurov A. V. "Homomorfní šifrování", 2007
↑ 1 2 Pascal Paillier, „Kryptosystémy s veřejným klíčem založené na třídách složeného stupně reziduosity“, 1999
↑ Pierre-Alain Fouque a David Pointcheval, „Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks“, 2001
↑ Lan Nguyen, Rei Safavi-Naini, Kaoru Kurosawa, „Prokazatelně bezpečný a účinný ověřitelný náhodný výběr založený na variantě kryptosystému Paillier“, 2006
↑ Jurik M., Damgård I. „Zobecnění, zjednodušení a některé aplikace Paillierova pravděpodobnostního systému veřejného klíče“, 1999
↑ 1 2 P.-A., Poupard G., Stern J., "Sdílení dešifrování v kontextu hlasování nebo loterií", 2001
↑ 1 2 Jurik MJ, "Rozšíření kryptosystému paillier s aplikacemi pro kryptologické protokoly", 2003

Literatura

Paillier P. Kryptosystémy s veřejným klíčem založené na složených třídách reziduálních stupňů (anglicky) // Pokroky v kryptologii, EUROCRYPT'99. - 1999. - S. 223-238 . - ISBN 978-3-540-48910-8 . - doi : 10.1007/3-540-48910-X_16 . Archivováno z originálu 17. prosince 2014.

Fouque P.-A., Poupard G., Stern J. Dešifrování sdílení v kontextu hlasování nebo loterií // Finanční kryptografie, sborník příspěvků ze 4. mezinárodní konference. - 2001. - S. 90-104 . — ISBN 978-3-540-45472-4 . - doi : 10.1007/3-540-45472-1_7 .

Jurik MJ Rozšíření kryptosystému paillier s aplikacemi pro kryptologické protokoly (anglicky) // Public Key Cryptography. - 2003. - S. 119-136 .

Jurik M., Damgård I. Zobecnění, zjednodušení a některé aplikace Paillierova pravděpodobnostního systému veřejného klíče // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. - 2001. - S. 119-136 .

Varnovsky N. P., Shokurov A. V. Homomorphic encryption // Proceedings of ISP RAS. - 2007. - S. 27-36 . (Ruština)

Katz J., Lindell Y. Úvod do moderní kryptografie: Principy a protokoly. - Chapman & Hall / CRC, 2007. - S. 385-395. — ISBN 978-1584885511 .

Odkazy

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta