Damgordin kryptojärjestelmä - Eureka

Damgord-Yurik- salausjärjestelmä on Ivan Damgordin ja Mads Yurikin vuonna 2000 ehdottama julkisen avaimen salausjärjestelmä. Se on yleistys Peyen salausjärjestelmästä suurille moduuleille laajennuksen laajentamiseksi [1] .

Taustaa: Yleistys Peyen skeemasta

Kuvattu salausjärjestelmä käyttää laskentamoduulia , jossa on RSA - moduuli ja on luonnollinen luku. Tapauksessa on Peyetin salausjärjestelmän kaavio . ${\näyttötyyli {n^{s+1))}$ $n$ $s$ $s = 1$

Olkoon , missä , on parittomia alkulukuja. Huomaa, että kertova ryhmä on karteesinen tulo , jossa on syklinen järjestyksen ryhmä ja on isomorfinen ryhmän kanssa . Näin ollen osamääräryhmä on myös järjestyksessä syklinen . Määritämme jokaiselle mielivaltaiselle elementille elementin tekijäryhmästä . ${\näyttötyyli {n=pq))$ $s$ $q$ ${Z_{n^{s+1}}^{*}}$ ${G\times H}$ $G$ ${\näyttötyyli {n^{s))}$ $H$ ${Z_{n}^{*}}$ ${{\overline {G}}=Z_{n^{s+1}}^{*}/}$ $H$ ${\näyttötyyli {n^{s))}$ ${a\in Z_{n^{s+1}}^{*}}$ ${{\overline {a}}=aH}$ $\overline{G}$

Lisäpäättelyn selittämiseksi muotoilemme seuraavan lemman [2]

Lemma: Minkä tahansa elementin kohdalla on järjestys kertovassa ryhmässä . $s<p,q$ $N+1$ ${\näyttötyyli {n^{s))}$ ${Z_{n^{s+1}}^{*}}$

Kun järjestyksestä tulee koprime , voimme olettaa, että elementti on ryhmän generaattori , paitsi ehkä . Siten ja hinnat ovat : $H$ ${\näyttötyyli {n^{s))}$ ${{\overline {1+n}}:=(1+n)H\in {\overline {G}}}$ $\overline{G}$ $s\geqslant p,q$ $H$ ${Z_{n^{s+1}}^{*}}$

${\näyttötyyli {H,(1+n)H,(1+n)^{2}H,\pisteet ,(1+n)^{n^{s}-1},}}$

mikä johtaa näiden kosettien luonnolliseen luetteloon.

Toinen lisälaskelmien perustelemiseen tarvittava tekniikka on yksinkertainen tapa määrittää . Sen toteuttamiseksi merkitsemme sitten funktiota $i$ ${(1+n)^{i}{\bmod {n}}^{s+1}}$ ${\näyttötyyli {L(b)=(b-1)/}}$ $n$

${L((1+n)^{i}{\bmod {n}}^{s+1})=(i+{\dbinom {i}{2}}n+...+{\dbinom {i}{s}}n^{s-1}){\bmod {n}}^{s}}$

Seuraavaksi laskemme peräkkäin:

${i_{1}=i{\bmod {n}},i_{2}=i{\bmod {n}}^{2},\dots }$

Se on tarpeeksi helppo laskea : $i_{1}$

${i_{1}=L((1+n)i{\bmod {n}}^{2})=i{\bmod {n}}}$

Lisälaskelmat suoritetaan induktiolla: -: nnessä vaiheessa tiedämme . Sitten joillekin . Käytetään tätä suhdetta: $j$ $i_{j-1}$ ${i_{j}=i_{j-1}+kn^{j-1))$ ${0\leq k<n}$

${L((1+n)^{i}{\bmod {n}}^{j+1})=(i_{j}+{\dbinom {i_{j}}{2}}n+ ...+{\dbinom {i_{j}}{j}}n^{(j-1)}){\bmod {n}}^{j}}$

Huomaa, että jokainen termi täyttää . Näin ollen: ${{\dbinom {i_{j}}{t+1}}n^{t}}}$ ${\näyttötyyli {j>t>0}}$ ${{\dbinom {i_{j}}{t+1}}n^{t}={\dbinom {i_{j-1}}{t+1}}n^{t}{\bmod {n}}^{j}}$

${L((1+n)^{i}{\bmod {n}}^{j+1})=(i_{j-1}+kn^{j-1}+{\dbinom { i_{j-1}}{2}}n+...+{\dbinom {i_{j-1}}{j}}n^{(j-1)}){\bmod {n}}^{ j}}$

Siten saamme:

${i_{j}=i_{j-1}+kn^{j-1}=i_{j-1}+L((1+n)^{i}{\bmod {n}}^ {j+1})-(i_{j-1}+{\dbinom {i_{j-1}}{2}}n+\pisteet +{\dbinom {i_{j-1}}{j}}n ^{(j-1)}){\bmod {n}}^{j}}=}$

${=L((1+n)^{i}{\bmod {n}}^{j+1})-({\dbinom {i_{j-1}}{2}}n+\pistettä +{\dbinom {i_{j-1}}{j}}n^{(j-1)}){\bmod {n}}^{j}}$

Piirin kuvaus

Avaimen luominen

Satunnaisesti ja toisistaan riippumatta kaksi suurta alkulukua ja ; $s$ $q$
Laskettu ja lukujen ja ; $n = pq$ $\lambda$ ${\näyttötyyli {p-1}}$ ${q-1}$
Elementti valitaan siten, että tietylle se on koprime ja . Huomautus: tätä voidaan helpottaa valitsemalla ensin satunnaisesti ja ja sitten laskemalla . ${g\in {\mathbb {Z} }_{n^{s+1}}^{*}}$ ${g=(1+n)^{j}x{\bmod {n}}^{s+1}}$ $j$ $n$ ${x\in H}$
$j$ $x$ $g$
Yksi valitaan siten, että ja (käyttäen kiinalaista jäännöslausetta ). Esimerkiksi for voidaan ottaa kuten Peye-järjestelmässä. $d$ ${d{\bmod {n}}\in {\mathbb {Z} }_{n}^{*}}$ ${\displaystyle {d=0{\bmod {\lambda ))))$ $d$ ${\lambda }$

Joten julkinen avain on , ja salainen avain on . ${\näyttötyyli (n,g)}$ $d$

Salaus

Antaa olla salattu viesti, ja ; $m$ ${\displaystyle {m\in {\mathbb {Z} }_{n^{s))))$
Satunnainen valitaan siten, että ; $r$ ${r\in {\mathbb {Z} }_{n^{s+1}}^{*}}$
Salateksti lasketaan: . ${c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}}$

Transkriptio

Antaa olla salateksti, ja ; $c$ ${c\in {\mathbb {Z} }_{n^{s+1}}^{*}}$
Laskettu . Jos on kelvollinen salateksti, niin ${c^{d}\;bmod\;n^{s+1))$ $c$ ${\displaystyle {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))))$
Yllä olevan algoritmin mukaan . Koska tuote on jo tiedossa, on vielä laskettava . ${jid{\bmod {n}}^{s}}$ ${\näyttötyyli {jd}}$ ${m=(jmd)\cdot (jd)^{-1}\;{\bmod {\;}}n^{s}}$

Homomorfismi

Järjestelmä on homomorfinen summauksen suhteen : ${\näyttötyyli {Z_{n^{s))))$

${{\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})={\mathcal {E}}(x_{1}+x_{2} \;{\bmod {\;}}n^{s}})}$ .

Muistiinpanot

↑ Homomorfinen salaus: pilvitekniikan tietoturva ja muut sovellukset (arvostelu) A.I.Trubey
↑ Paillierin todennäköisyyspohjaisen julkisen avaimen järjestelmän yleistys, yksinkertaistaminen ja joitain sovelluksia (Ivan B. Damgard, Mads J. Jurik)

Kirjallisuus

Homomorfinen salaus: Cloud Computing Security ja muut sovellukset (arvostelu) (A.I.Trubey)
Paillierin todennäköisyyspohjaisen julkisen avaimen järjestelmän yleistys, yksinkertaistaminen ja joitain sovelluksia (Ivan B. Damgard, Mads J. Jurik)

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
Muut	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti