EPOC (titkosítási séma)

Az EPOC ( Efficient Probabilistic Public Key Encryption ; hatékony valószínűségi nyilvános kulcsú titkosítás) egy valószínűségi nyilvános kulcsú titkosítási séma .

Az EPOC-t 1998 novemberében fejlesztette ki T. Okamoto, S. Uchiyama és E. Fujisaki, az NTT Laboratories japán munkatársa . Véletlenszerű orákulummodellre épül , amelyben egy nyilvános kulcsú titkosítási funkciót egy (valóban) véletlenszerű hash függvény segítségével biztonságos titkosítási sémává alakítanak át ; az eredményül kapott sémát úgy tervezték, hogy szemantikailag biztonságos legyen a választott rejtjelezett szövegen alapuló támadásokkal szemben [1] .

Sémák típusai

Az EPOC titkosítási függvény egy OU (Okamoto-Uchiyama) függvény, amelyet ugyanolyan nehéz invertálni, mint egy összetett egész nyilvános kulcsot. Az EPOC [2] három változata létezik :

EPOC-1, egy egyirányú függvény (angol trapdoor function) és egy véletlen függvény (hash függvény) használatával [3] .;
EPOC-2 egyirányú függvény , két véletlenszerű függvény (hash függvények) és szimmetrikus kulcsú titkosítás (például egyszeri pad és blokk titkosítás) használatával [4] ;
Az EPOC-3 egyirányú OU (Okamoto-Uchiyama) funkciót és két véletlenszerű függvényt (hash függvényeket), valamint bármilyen szimmetrikus titkosítási sémát használ, például egyszeri padokat (angolul one-time pad) vagy blokk titkosítást .

Tulajdonságok [1] [5]

Az EPOC a következő tulajdonságokkal rendelkezik:

Az EPOC-1 szemantikailag biztonságos , ellenáll a kiválasztott titkosított szöveges támadásoknak ( IND-CCA2 vagy NM-CCA2 ) a véletlenszerű orákulummodellben [6] a p-alcsoport feltételezése mellett, amely számításilag összehasonlítható a kvadratikus maradék és a magasabb fokú maradék feltevésekkel.
Az egyszeri paddal ellátott EPOC-2 szemantikailag biztonságos , ellenáll a kiválasztott titkosított szöveges támadásoknak ( IND-CCA2 vagy NM-CCA2 ) véletlenszerű orákulummodellben, faktorizációs feltételezés mellett.
A szimmetrikus titkosítású EPOC-2 szemantikailag biztonságos , ellenáll a kiválasztott rejtjelezett szövegen ( IND-CCA2 vagy NM-CCA2 ) alapuló támadásoknak a véletlenszerű orákulummodellben a faktorizációs feltételezés mellett, ha az alapul szolgáló szimmetrikus titkosítás biztonságos a passzív támadásokkal szemben (a támadások megtekintése, ahol a kriptoanalitikus csak a továbbított rejtjelezett szövegeket láthatja, és a nyilvános kulcs segítségével létrehozhatja a sajátját .).

Háttér

Diffie és Hellman 1976-ban javasolta a nyilvános kulcsú kriptorendszer (vagy egyirányú funkció ) koncepcióját. Bár sok kriptográfus és matematikus végzett kiterjedt kutatást a nyilvános kulcsú kriptorendszerek koncepciójának megvalósítására több mint 20 éve, nagyon kevés konkrét, biztonságos módszert találtak [7] .

A módszerek egyik tipikus osztálya az RSA-Rabin , amely egy polinomiális algoritmus kombinációja a maradékok gyűrűjében lévő polinom gyökerének megtalálására egy összetett szám modulo ( véges mezőben ) és egy megoldhatatlan faktorizációs probléma ( számítási szempontból) kombinációja. komplexitás ). A módszerek másik tipikus osztálya a Diffie-Hellman, ElGamal módszer , amely a véges Abel-csoport logaritmusának kommutatív tulajdonságának és a megoldhatatlan diszkrét logaritmus -probléma kombinációja [8] .

Az egyirányú függvény megvalósítására szolgáló RSA-Rabin és Diffie-Hellman-ElGamal módszerek közül a Rabin-függvényen és annak változatain, például annak elliptikus görbéjén és a Williams-változatokon kívül egyetlen más funkció sem bizonyult olyan robusztusnak, mint a primitív. problémák [9] (pl. faktorizálás és diszkrét logaritmus problémák ).

Okamoto és Uchiyama egy OU (Okamoto-Uchiyama) nevű egyirányú függvényt javasoltak , amely praktikus, bizonyíthatóan biztonságos, és van még néhány érdekes tulajdonsága [10] .

OU függvény tulajdonságai [11]

Valószínűségi függvény: Ez egy egyirányú, valószínűségi függvény . Legyen egy egyszerű szöveges titkosított szövegvéletlenszerűséggel. $E(m,r)$ $m$ $r$
Egy függvény egyoldalúsága: Egy függvény invertálása ugyanolyan nehéznek bizonyult, mint a faktorizálás. $n:=p^{2}q$
Szemantikai biztonság: Egy függvény szemantikailag biztonságos , ha a következő feltevés igaz ( a p-alcsoport feltételezése ):ésszámításilag megkülönböztethetetlen, aholésegységesen és egymástól függetlenül választottak. Ez a rejtjelezett szöveg megkülönböztethetetlenségi feltételezéseaz egyező egyszerű szövegű támadásoknál számításilag összehasonlítható egy négyzetes és egy magasabb fokú maradék megtalálásával. $E(0,r)=h^{r}{\text{ mod }}n$ $E(1,r')=gh^{r'}{\text{ mod }}n$ $r$ $r'$ $\mathbf {Z} /n\mathbf {Z}$
Hatékonyság: Nyilvános kulcsú kriptorendszer környezetben , ahol a nyilvános kulcsú titkosítási rendszert csak a titkos kulcsú kriptorendszer titkos kulcsának (például 112 és 128 bit hosszúságú) terjesztésére használják (például Triple DES és IDEA ), a titkosítást és a visszafejtést. az OU függvény sebessége összehasonlítható (többször lassabb) az elliptikus görbe kriptorendszerek sebességével .
Homomorf titkosítási tulajdonság: A függvény homomorf titkosítási tulajdonsággal rendelkezik: (Ez a tulajdonság e-szavazáshoz és más titkosítási protokollokhoz használatos ). $E(m_{0},r_{0})E(m_{1},r_{1}){\text{ mod }}n=E(m_{0}+m_{1},r_{ 3}),{\text{ if }}m_{0}+m_{1}<p$
Rejtjelszöveg megkülönböztethetetlensége : Még az is, aki nem ismeri a titkos kulcsot, lecserélheti a,, rejtjelezett szöveget egy másik rejtjelezett szövegre,, miközben megtartja a nyílt szöveget m (azazésésközötti kapcsolatelrejthető (vagyismegkülönböztethetetlen). Ez a tulajdonság hasznos az adatvédelmi protokollokhoz.) $C=E(m,r)$ $C'=Ch^{r'}{\text{ mod }}n$ $C'=E(m,r'')$ $C$ $C'$ $(C,C')$ ${\megjelenítési stílus (C,E(m',t)}$

A titkosítási séma biztonságának bizonyítéka

A nyilvános kulcsú titkosítás egyik legfontosabb tulajdonsága a bizonyítható biztonság . A nyilvános kulcsú titkosítás legerősebb biztonsági koncepciója a támadások elleni szemantikai védelem egy kiválasztott rejtjelezett szöveg alapján .

Az adaptívan választott rejtjelezett szövegen ( IND -CCA2 ) alapuló szemantikus támadásvédelem egyenértékűnek (vagy elegendőnek) bizonyult a legerősebb biztonsági koncepcióval ( NM -CCA2 ) [12] [13] .

Fujisaki és Okamoto két gyakori és hatékony intézkedést valósított meg annak érdekében, hogy egy valószínűségi egyirányú függvényt biztonságos IND-CCA2 áramkörré alakítsanak át egy véletlenszerű orákulummodellben [ 6] . Az egyik egy szemantikailag biztonságos ( IND-CPA ) egyirányú függvény átalakítása biztonságos IND-CCA2 sémává . Mások, az egyirányú funkciótól (OW-CPA) és a szimmetrikus kulcsú titkosítástól (beleértve az egyszeri betétet is) a biztonságos IND-CCA2 sémáig . Ez utóbbi transzformáció egy szimmetrikus kulcsú titkosítási sémával kombinálva garantálhatja a nyilvános kulcsú titkosítási rendszer teljes biztonságát [14] .

EPOC titkosítási séma

Áttekintés

Az EPOC nyilvános kulcsú titkosítási séma , amelyet a triplet határoz meg , ahol a kulcsgenerálási művelet, a titkosítási művelet és a visszafejtési művelet. $({\mathcal {G}},{\mathcal {E}},{\mathcal {D}}))$ ${\mathcal {G}}$ ${\mathcal {E}}$ $\mathcal{D}$

EPOC sémák: EPOC-1 és EPOC-2.

Az EPOC-1 kulcselosztásra, míg az EPOC-2 kulcselosztásra és titkosított adatátvitelre, valamint hosszabb kulcselosztásra szolgál, korlátozott nyilvános kulcsmérettel.

Kulcstípusok

Kétféle kulcs létezik: OU nyilvános kulcs és OU privát kulcs, mindkettőt az EPOC-1, EPOC-2 kriptográfiai titkosítási sémák használják [15] .

OU nyilvános kulcs [15]

Egy szervezeti egység nyilvános kulcsa egy halmaz, amelynek összetevői a következő értékekkel rendelkeznek: $(n,g,h,pLen)$

$n$ egy nem negatív egész szám
$g$ egy nem negatív egész szám
$h$ egy nem negatív egész szám
$pLen$ — titkos paraméter, nem negatív egész szám

A gyakorlatban a nyilvános kulcsú OU-ban a modul formátumot vesz fel , ahol és két különböző páratlan prímszám, és a és bithosszúsága egyenlő . -elemben úgy, hogy a sorrend a következő , ahol . -elem a . $n$ $n:=p^{2}q$ $p$ $q$ $p$ $q$ $pLen$ $g$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}$ $(\mathbf {Z} /p^{2}\mathbf {Z} )^{*}$ $p$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $h$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$

OU privát kulcs [15]

Egy szervezeti egység privát kulcsa egy halmaz, amelynek összetevői a következő értékekkel rendelkeznek: ${\megjelenítési stílus (p,g,pLen,w)}$

$p$ — első tényező, nem negatív egész szám
$h$ — második tényező, nem negatív egész szám
$pLen$ — titkos paraméter, nem negatív egész szám
$w$ — érték , ahol , nem negatív egész szám $L(g_{p})$ $L(x)={\frac {x-1}{p))$

EPOC-1 [14]

Kulcs létrehozása: G

A bemenet és a kimenet a következő: ${\mathcal {G}}$

[Input]: A titkos paraméter ( ) egy pozitív egész szám. $k$ $=plen$

[Output]: Nyilvános kulcs és privát kulcs párja . $(n,g,h,H,pLen,mLen,hLen,rLen)$ ${\megjelenítési stílus (p,g_{p})}$

A bejelentkezési művelet így néz ki: ${\mathcal {G}}$ $k$

Válasszunk ki két prímszámot ( ) és számítsuk ki . Itt és olyan, hogy és prímszámok, és és olyan, hogy . $p$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Véletlenszerűen választunk úgy, hogy a sorrend egyenlő legyen (Megjegyzendő, hogy gcd( , ) és gcd( , ) ). $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $p$ $p$ $q-1$ ${\displaystyle=1}$ $q$ $p-1$ ${\displaystyle=1}$

Véletlenszerűen és a -tól függetlenül választunk . Számoljunk . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g$ $h:=h_{n}^{0}{\text{ mod }}n$

Telepítse . Telepítse és olyan, hogy . $pLen:=k$ $mLen$ $rLen$ $mLen+rLen\leq pLen-1$

Válasszunk egy hash függvényt . ${\displaystyle H:\{0,1\}^{*}\jobbra \{0,1\}^{hLen))$

Megjegyzés: egy további paraméter, amely növeli a visszafejtés hatékonyságát, és a és -ból számítható . amikor ( -konstans ). a rendszer javíthatja, és sok felhasználó megoszthatja. $g_{p}$ $p$ $g$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$

Titkosítás: E

A bemenet és a kimenet a következő: ${\mathcal {E}}$

[Input]: Egyszerű szöveg nyilvános kulccsal együtt . ${\displaystyle M\in \{0,1\}^{mLen))$ $(n,g,h,H,pLen,mLen,hLen,rLen)$

[Kimenet]: Rejtjelezett szöveg C.

A beviteli művelet így néz ki: ${\mathcal {E}}$ $M$ ${\megjelenítési stílus (n,g,h,H,mLen,rLen)}$

Válasszunk és számoljunk . Itt az összefűzést és a . ${\displaystyle R\in \{0,1\}^{rLen))$ $r:=H(M\parallel R)$ $M\parallel R$ $M$ $R$

Számítsd ki : $C$

$C:=g^{(M\parallel R)}h^{r}{\text{ mod }}n.$

Dekódolás: D

A bemenet és a kimenet a következő: $\mathcal{D}$

[Input]: Titkosított szöveg a nyilvános kulccsal és a privát kulccsal együtt . $C$ $(n,g,h,H,pLen,mLen,hLen)$ ${\megjelenítési stílus (p,g_{p})}$

[Output]: Egyszerű szöveg vagy null karakterlánc. $M$

A művelet a bemenetekkel , és így néz ki: $\mathcal{D}$ $C$ $(n,g,h,H,pLen,mLen,hLen)$ ${\megjelenítési stílus (p,g_{p})}$

Számítsuk ki , és hol . $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$ $X:={\frac {L(C_{p})}{L(g_{p))}}{\text{ mod }}p$ $L(x):={\frac {x-1}{p))$

Ellenőrizzük, hogy igaz-e a következő egyenlet: . $C=g^{X}h^{H(X)}{\text{ mod }}n$

Ha a kifejezés igaz, akkor dekódolt egyszerű szövegként adja ki a kimenetet, ahol a legjelentősebb biteket jelöli . Ellenkező esetben null karakterláncot adunk ki. ${\displaystyle [X]^{mLen))$ ${\displaystyle [X]^{mLen))$ $mLen$ $x$

EPOC-2 [16] [14]

Kulcs létrehozása: G

A bemenet és a kimenet a következő: ${\mathcal {G}}$

[Input]: Titkos paraméter ( ). $k$ $=plen$

[Output]: Nyilvános kulcs és privát kulcs párja . $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ ${\megjelenítési stílus (p,g_{p})}$

A bejelentkezési művelet így néz ki: ${\mathcal {G}}$ $k$

Válasszunk ki két prímszámot ( ) és számítsuk ki . Itt és olyan, hogy és prímszámok, és és olyan, hogy . $p$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Véletlenszerűen választunk úgy, hogy a sorrend egyenlő legyen . $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $p$

Véletlenszerűen és a -tól függetlenül választunk . Számoljunk . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $g$ $h:=h_{n}^{0}{\text{ mod }}n$

Telepítse . Telepítse és olyan, hogy . $pLen:=k$ $mLen$ $rLen$ $mLen+rLen\leq pLen-1$

Kivonatfüggvényeket és . _ ${\displaystyle H:\{0,1\}^{*}\jobbra \{0,1\}^{hLen))$ ${\displaystyle G:{0,1}^{*}\rightarrow \{0,1\}^{hLen))$

Megjegyzés: egy további paraméter, amely növeli a visszafejtés hatékonyságát, és a és -ból számítható . amikor ( -konstans ). és a rendszer javíthatja, és sok felhasználó megoszthatja. $g_{p}$ $p$ $g$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$ $G$

Titkosítás: E

Legyen egy szimmetrikus kulccsal rendelkező titkosító és visszafejtő algoritmuspár , ahol a hossza . A titkosítási algoritmus kulcsot és egyszerű szöveget vesz fel, és titkosított szöveget ad vissza . A visszafejtő algoritmus felveszi a kulcsot és a titkosított szöveget , és visszaadja az egyszerű szöveget . $SymE=(SymeEnc,SymDec)$ $K$ $K$ $gLen$ $SymeEnc$ $K$ $x$ $SymEnc(K,X)$ $SymDec$ $K$ $Y$ $SymDec(K,Y)$

A bemenet és a kimenet a következő: ${\mathcal {E}}$

[Input]: Egyszerű szöveg , nyilvános kulccsal és . ${\displaystyle M\in \{0,1\}^{mLen))$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymeEnc$

[Kimenet]: Titkosított szöveg . $C=(C_{1},C_{2})$

A művelet a bemenetekkel , és így néz ki: ${\mathcal {E}}$ $M$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymeEnc$

Válasszunk és számoljunk . $r\in \{0,1\}^{rLen}$ $G(R)$

Számoljunk . Itt az összefűzést és a . $H(M\parallel R)$ $M\parallel R$ $M$ $R$

$C_{1}:=g^{R}h^{H(M\parallel R)}{\text{ mod }}n$ ; $C_{2}:=SymEnc(G(R),M)$

Megjegyzés: Egy tipikus megvalósítás az egyszeri pad. Azaz , és , ahol a bitenkénti XOR műveletet jelöli . $SymE$ $SymEnc(K,X):=K\oplus X$ $SymDec(X,Y):=X\oplus Y$ $\oplus$

Dekódolás: D

A bemenet és a kimenet a következő: $\mathcal{D}$

[Input]: A titkosított szöveg a nyilvános kulccsal , titkos kulccsal és . $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ ${\megjelenítési stílus (p,g_{p})}$ $SymDec$

[Output]: Egyszerű szöveg vagy null karakterlánc. $M$

A művelet a , és bemenetekkel a következő: $\mathcal{D}$ $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen)$ ${\megjelenítési stílus (p,g_{p})}$ $SymDec$

Számítsuk ki , és hol . $C_{p}:=C^{p-1}{\text{ mod }}p^{2}$ $R':={\frac {L(C_{p})}{L(g_{p))}}{\text{ mod }}p$ $L(x):={\frac {x-1}{p))$

Kiszámít $M':=SymDec(G(R'),C_{2}).$

Ellenőrizzük, hogy igaz-e a következő egyenlet: . $C=g^{R'}h^{H(M'\parallel R')}{\text{ mod }}n$

Ha a kifejezés igaz, akkor a kimenet dekódolt egyszerű szövegként. Ellenkező esetben null karakterláncot adunk ki. $M'$

Jegyzetek

↑ 1 2 T. Okamoto; S. Uchiyama, 1998 , p. egy.
↑ Katja Schmidt-Szamoa, 2006 .
↑ T. Okamoto; S. Uchiyama, 1998 , p. 2-3.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , p. 3-4.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , p. 8-11.
↑ 1 2 E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung, 2000 .
↑ W. DIFFIE ÉS ME HELLMAN, 1976 .
↑ T. Elgamal, 1985 .
↑ T. Okamoto; S. Uchiyama, 1998 , p. 5.
↑ T. Okamoto; S. Uchiyama, 1998 , p. négy.
↑ T. Okamoto; S. Uchiyama, 1998 , p. 3-4.
↑ Maxwell Krohn, 1999 , p. 53.
↑ Bellare, M., Desai, A., Pointcheval, D., és Rogaway, P., 1998 .
↑ 1 2 3 T. Okamoto; S. Uchiyama, 1998 , p. 5.
↑ 1 2 3 NTT Corporation, 2001 , p. 7.
↑ NTT Corporation, 2001 , p. 9-10.

Irodalom

Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. Aszimmetrikus és szimmetrikus titkosítási sémák biztonságos integrációja . – 1999.
W. DIFFIE ÉS ÉN HELLMAN. Új irányok a kriptográfiában . – 1976.
Maxwell Krohn. A kriptográfiai biztonság definícióiról : A választott titkosított szövegű támadás újralátogatása . – 1999.
T. Elgamal. Nyilvános kulcsú titkosítási rendszer és diszkrét logaritmusokon alapuló aláírási séma . – 1985.
NTT Information Sharing Platform Laboratories, NTT Corporation. EPOC-2 specifikáció . - 2001. - P. 7-10 .
Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. EPOC: Hatékony valószínűségi nyilvános kulcsú titkosítás . - 1998. - P. 1-12 .
Értékelő: Prof. Jean-Jacques Quisquater, Math RiZK, tanácsadás; Tudományos támogatás: Dr. François Koeune, K2Crypt. A titkosítási rendszer biztonsági értékelése . – 2002.
E.Brickell, D.Pointcheval, S.Vaudenay, M.Yung. Tervérvényesítések diszkrét logaritmus alapú aláírási sémákhoz . - 2000. - P. 276-292 .
Bellare, M., Desai, A., Pointcheval, D., és Rogaway, P. Relations among Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto'98, LNCS 1462, Springer-Verlag, (angol) . - 1998. - P. 26–45 .
Katja Schmidt Szamoa. Egy új Rabin típusú csapóajtó permutáció, amely egyenértékű a faktorozással . - 2006. - P. 86–88 .