EPOC (šifrovací schéma)

EPOC ( Efficient Probabilistic Public Key Encryption ; efektivní pravděpodobnostní šifrování veřejným klíčem) je pravděpodobnostní schéma šifrování veřejného klíče .

EPOC vyvinuli v listopadu 1998 T. Okamoto, S. Uchiyama a E. Fujisaki z NTT Laboratories v Japonsku . Je založen na modelu náhodného orákula , ve kterém je funkce šifrování veřejného klíče převedena na bezpečné šifrovací schéma pomocí (skutečně) náhodné hašovací funkce; výsledné schéma je navrženo tak, aby bylo sémanticky bezpečné proti útokům na základě zvoleného šifrového textu [1] .

Typy schémat

Funkce šifrování EPOC je funkce OU (Okamoto-Uchiyama), kterou lze invertovat stejně obtížně jako faktor složeného celočíselného veřejného klíče. Existují tři verze EPOC [2] :

EPOC-1, využívající jednosměrnou funkci (anglicky trapdoor function) a náhodnou funkci (hash function) [3] .;
EPOC-2 používající jednosměrnou funkci , dvě náhodné funkce (hashovací funkce) a šifrování symetrickým klíčem (jako jsou jednorázové vycpávky a blokové šifry) [4] ;
EPOC-3 používá jednosměrnou funkci OU (Okamoto-Uchiyama) a dvě náhodné funkce (hashovací funkce), stejně jako jakékoli symetrické šifrovací schéma, jako jsou jednorázové bloky (anglicky one-time pad) nebo bloková šifra .

Vlastnosti [1] [5]

EPOC má následující vlastnosti:

EPOC-1 je sémanticky bezpečný , odolný vůči vybraným útokům šifrovaného textu ( IND-CCA2 nebo NM-CCA2 ) v modelu náhodného orákula [6] za předpokladu p-podskupiny , který je výpočetně srovnatelný s předpoklady kvadratického zbytku a vyššího stupně.
EPOC-2 s jednorázovou podložkou je sémanticky bezpečný , odolný vůči vybraným útokům šifrovaným textem ( IND-CCA2 nebo NM-CCA2 ) v modelu náhodného orákula za předpokladu faktorizace.
EPOC-2 se symetrickým šifrováním je sémanticky bezpečný , odolný vůči útokům na základě zvoleného šifrovaného textu ( IND-CCA2 nebo NM-CCA2 ) v modelu náhodného orákula za předpokladu faktorizace, pokud je základní symetrické šifrování zabezpečené proti pasivním útokům (zobrazte útoky, kde kryptoanalytik má možnost vidět pouze přenášené šifrové texty a generovat vlastní pomocí veřejného klíče .).

Pozadí

Diffie a Hellman navrhli koncept kryptosystému s veřejným klíčem (nebo jednosměrné funkce ) v roce 1976. Ačkoli mnoho kryptografů a matematiků provedlo rozsáhlý výzkum implementace konceptu kryptosystémů s veřejným klíčem již více než 20 let, bylo nalezeno jen velmi málo konkrétních metod, které jsou bezpečné [7] .

Typickou třídou metod je RSA-Rabin , což je kombinace polynomiálního algoritmu pro nalezení kořene polynomu v kruhu zbytků modulo složené číslo (v konečném poli ) a neřešitelný problém faktorizace (z hlediska výpočetního složitost ). Další typickou třídou metod je Diffie-Hellmanova, ElGamalova metoda , která je kombinací komutativní vlastnosti logaritmu v konečné abelovské grupě a neřešitelného problému diskrétního logaritmu [8] .

Mezi metodami RSA-Rabin a Diffie-Hellman-ElGamal pro implementaci jednosměrné funkce se žádná jiná funkce než Rabinova funkce a její varianty, jako je její eliptická křivka a Williamsovy verze, neprokázala jako tak robustní jako primitivní funkce. problémy [9] (např., faktorizace a problémy s diskrétním logaritmem ).

Okamoto a Uchiyama navrhli jednosměrnou funkci nazvanou OU (Okamoto-Uchiyama), která je praktická, prokazatelně bezpečná a má některé další zajímavé vlastnosti [10] .

Vlastnosti funkce organizační jednotky [11]

Pravděpodobnostní funkce: Toto je jednosměrná pravděpodobnostní funkce . Dovolit být šifrovaný text v otevřeném textus náhodným. $E(m,r)$ $m$ $r$
Jednostrannost funkce: Ukázalo se, že invertování funkce je stejně těžké jako faktorizace. $n:=p^{2}q$
Sémantické zabezpečení: Funkce je sémanticky bezpečná , pokud platí následující předpoklad ( předpoklad p-podskupiny ):avýpočetně nerozlišitelné, kdeajsou jednotně a nezávisle vybrány z. Tento předpoklad nerozlišitelnosti šifrovaného textu pro útoky se shodným prostým textem je výpočetně srovnatelný s nalezením kvadratického zbytku a zbytku vyššího stupně. $E(0,r)=h^{r}{\text{ mod }}n$ $E(1,r')=gh^{r'}{\text{ mod }}n$ $r$ $r'$ $\mathbf {Z} /n\mathbf {Z}$
Efektivita: V prostředí kryptosystému s veřejným klíčem , kde se kryptosystém s veřejným klíčem používá pouze k šíření tajného klíče (například 112 a 128 bitů dlouhý) kryptosystému s tajným klíčem (například Triple DES a IDEA ), je šifrování a dešifrování rychlost funkce OU je srovnatelná (několikrát pomalejší) s rychlostí kryptosystémů s eliptickou křivkou .
Vlastnost homomorfního šifrování: Funkce má vlastnost homomorfního šifrování: (Tato vlastnost se používá pro elektronické hlasování a další šifrovací protokoly ). $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$
Nerozlišitelnost šifrovaného textu : I ten, kdo nezná tajný klíč, může změnit šifrový text,, na jiný šifrový text,, a přitom zachovat otevřený text m (tj.), a spojení meziamůže být skryté (tj.anerozlišitelné). Tato vlastnost je užitečná pro protokoly ochrany osobních údajů.) $C=E(m,r)$ $C'=Ch^{r'}{\text{ mod }}n$ $C'=E(m,r'')$ $C$ $C'$ $(C,C')$ $(C,E(m',t)$

Důkaz o zabezpečení šifrovacího schématu

Jednou z nejdůležitějších vlastností šifrování veřejným klíčem je prokazatelné zabezpečení . Nejsilnějším konceptem zabezpečení v šifrování veřejným klíčem je sémantická ochrana proti útokům na základě zvoleného šifrovaného textu .

Ochrana proti sémantickému útoku založená na adaptivně zvoleném šifrovém textu ( IND -CCA2 ) se ukázala jako ekvivalentní (nebo dostatečná) s nejsilnějším bezpečnostním konceptem ( NM-CCA2 ) [12] [13] .

Fujisaki a Okamoto implementovali dvě běžná a účinná opatření k transformaci pravděpodobnostní jednosměrné funkce na bezpečný obvod IND-CCA2 v modelu náhodného orákula [6] . Jedním z nich je převod sémanticky bezpečné ( IND-CPA ) jednosměrné funkce na bezpečné schéma IND-CCA2 . Ostatní, od jednosměrné funkce (OW-CPA) a šifrování symetrickým klíčem (včetně jednorázové podložky) až po zabezpečené schéma IND-CCA2 . Posledně jmenovaná transformace může zaručit úplnou bezpečnost systému šifrování veřejného klíče v kombinaci se schématem šifrování symetrickým klíčem [14] .

Schéma šifrování EPOC

Přehled

Schéma šifrování veřejného klíče EPOC , které je specifikováno trojicí , kde je operace generování klíče, je operace šifrování a je operace dešifrování. $({\mathcal {G}}, {\mathcal {E}}, {\mathcal {D}}))$ ${\mathcal {G}}$ ${\mathcal {E}}$ $\mathcal{D}$

Schémata EPOC: EPOC-1 a EPOC-2.

EPOC-1 je pro distribuci klíčů, zatímco EPOC-2 je pro distribuci klíčů a šifrovaný přenos dat a delší distribuci klíčů s omezenou velikostí veřejného klíče.

Typy klíčů

Existují dva typy klíčů: veřejný klíč OU a soukromý klíč OU, oba se používají v kryptografických šifrovacích schématech EPOC-1, EPOC-2 [15] .

Veřejný klíč OU [15]

Veřejný klíč organizační jednotky je sada, jejíž komponenty mají následující hodnoty: $(n,g,h,pLen)$

$n$ je nezáporné celé číslo
$G$ je nezáporné celé číslo
$h$ je nezáporné celé číslo
$pLen$ — tajný parametr, nezáporné celé číslo

V praxi má modul v organizační jednotce veřejného klíče tvar , kde a jsou dvě různá lichá prvočísla a bitová délka a je rovna . -prvek v tak, že pořadí v je , kde . -prvek v . $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} )^{*}$

Soukromý klíč organizační jednotky [15]

Soukromý klíč organizační jednotky je sada, jejíž součásti mají následující hodnoty: $(p,g,pLen,w)$

$p$ — první faktor, nezáporné celé číslo
$h$ — druhý faktor, nezáporné celé číslo
$pLen$ — tajný parametr, nezáporné celé číslo
$w$ — hodnota , kde , nezáporné celé číslo $L(g_{p})$ $L(x)={\frac {x-1}{p))$

EPOC-1 [14]

Vytvoření klíče: G

Vstup a výstup jsou následující: ${\mathcal {G}}$

[Vstup]: Tajný parametr ( ) je kladné celé číslo. $k$ $=plen$

[Výstup]: Pár veřejného klíče a soukromého klíče . $(n,g,h,H,pLen,mLen,hLen,rLen)$ $(p,g_{p})$

Operace přihlášení vypadá takto: ${\mathcal {G}}$ $k$

Zvolme dvě prvočísla , ( ) a vypočítejme . Tady a takové, že a jsou prvočísla, a a takové, že . $p$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Vybíráme náhodně tak, aby se pořadí rovnalo (Všimněte si, že gcd( , ) a 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}$

Vybíráme z náhodně a nezávisle na . Pojďme počítat . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $G$ $h:=h_{n}^{0}{\text{ mod }}n$

Nainstalujte . Instalovat a tak, že . $pLen:=k$ $mlen$ $rLen$ $mlen+rLen\leq pLen-1$

Zvolme hashovací funkci . ${\displaystyle H:\{0,1\}^{*}\rightarrow \{0,1\}^{hLen))$

Poznámka: je další parametr, který zvyšuje účinnost dešifrování a lze jej vypočítat z a . když ( -konstanta ). mohou být opraveny systémem a sdíleny mnoha uživateli. $g_{p}$ $p$ $G$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$

Šifrování: E

Vstup a výstup jsou následující: ${\mathcal {E}}$

[Vstup]: Prostý text spolu s veřejným klíčem . $M\in \{0,1\}^{mLen}$ $(n,g,h,H,pLen,mLen,hLen,rLen)$

[Výstup]: Šifrovaný text C.

Vstupní operace vypadá takto: ${\mathcal {E}}$ $M$ $(n,g,h,H,mLen,rLen)$

Pojďme si vybrat a spočítat . Zde znamená zřetězení a . $R\in \{0,1\}^{rLen}$ $r:=H(M\paralelní R)$ $M\parallel R$ $M$ $R$

Spočítat : $C$

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

Dešifrování: D

Vstup a výstup jsou následující: $\mathcal{D}$

[Vstup]: Šifrovaný text spolu s veřejným klíčem a soukromým klíčem . $C$ $(n,g,h,H,pLen,mLen,hLen)$ $(p,g_{p})$

[Výstup]: Prostý text nebo prázdný řetězec. $M$

Operace se vstupy a vypadá takto: $\mathcal{D}$ $C$ $(n,g,h,H,pLen,mLen,hLen)$ $(p,g_{p})$

Pojďme vypočítat , a , kde . $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))$

Zkontrolujme, zda platí následující rovnice: . $C=g^{X}h^{H(X)}{\text{ mod }}n$

Pokud je výraz pravdivý, vypíše se jako dešifrovaný prostý text, kde označuje nejvýznamnější bity v . V opačném případě vypíšeme nulový řetězec. $[X]^{mLen}$ $[X]^{mLen}$ $mlen$ $X$

EPOC-2 [16] [14]

Vytvoření klíče: G

Vstup a výstup jsou následující: ${\mathcal {G}}$

[Vstup]: Tajný parametr ( ). $k$ $=plen$

[Výstup]: Pár veřejného klíče a soukromého klíče . $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $(p,g_{p})$

Operace přihlášení vypadá takto: ${\mathcal {G}}$ $k$

Zvolme dvě prvočísla , ( ) a vypočítejme . Tady a takové, že a jsou prvočísla, a a takové, že . $p$ $q$ $|p|=|q|=k$ $n:=p^{2}q$ $p-1=p'u$ $q-1=q'v$ $p'$ $q'$ $|u|$ $|v|$ $O(\log k)$

Vybíráme náhodně tak, aby se pořadí rovnalo . $g\in (\mathbf {Z} /n\mathbf {Z} )^{*}$ $g_{p}:=g^{p-1}{\text{ mod }}p^{2}$ $p$

Vybíráme z náhodně a nezávisle na . Pojďme počítat . $h_{0}$ $(\mathbf {Z} /n\mathbf {Z} )^{*}$ $G$ $h:=h_{n}^{0}{\text{ mod }}n$

Nainstalujte . Instalovat a tak, že . $pLen:=k$ $mlen$ $rLen$ $mlen+rLen\leq pLen-1$

Vybíráme hašovací funkce a . ${\displaystyle H:\{0,1\}^{*}\rightarrow \{0,1\}^{hLen))$ ${\displaystyle G:{0,1}^{*}\rightarrow \{0,1\}^{hLen))$

Poznámka: je další parametr, který zvyšuje účinnost dešifrování a lze jej vypočítat z a . když ( -konstanta ). a může být opraven systémem a sdílen mnoha uživateli. $g_{p}$ $p$ $G$ $h=g^{n}{\text{ mod }}n$ $hLen=(2+c_{0})k$ $c_{0}$ $>0$ $H$ $G$

Šifrování: E

Dovolit je dvojice šifrovacích a dešifrovacích algoritmů se symetrickým klíčem , kde délka je . Šifrovací algoritmus vezme klíč a prostý text a vrátí šifrovaný text . Dešifrovací algoritmus vezme klíč a šifrovaný text a vrátí prostý text . $SymE=(SymEnc,SymDec)$ $K$ $K$ $gLen$ $SymEnc$ $K$ $X$ $SymEnc(K,X)$ $SymDec$ $K$ $Y$ $SymDec(K,Y)$

Vstup a výstup jsou následující: ${\mathcal {E}}$

[Vstup]: Prostý text spolu s veřejným klíčem a . $M\in \{0,1\}^{mLen}$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymEnc$

[Výstup]: Šifrovaný text . $C=(C_{1},C_{2})$

Operace se vstupy a vypadá takto: ${\mathcal {E}}$ $M$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $SymEnc$

Pojďme si vybrat a spočítat . $r\in \{0,1\}^{rLen}$ $G(R)$

Pojďme počítat . Zde znamená zřetězení a . $H(M\paralelní R)$ $M\parallel R$ $M$ $R$

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

Poznámka: Typickou implementací je jednorázová podložka. To znamená, , a , kde označuje bitovou operaci XOR . $SymE$ $SymEnc(K,X):=K\oplus X$ $SymDec(X,Y):=X\oplus Y$ $\oplus$

Dešifrování: D

Vstup a výstup jsou následující: $\mathcal{D}$

[Vstup]: Šifrovaný text spolu s veřejným klíčem , tajným klíčem a . $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen,rLen)$ $(p,g_{p})$ $SymDec$

[Výstup]: Prostý text nebo prázdný řetězec. $M$

Operace se vstupy , a je následující: $\mathcal{D}$ $C=(C_{1},C_{2})$ $(n,g,h,H,G,pLen,hLen,gLen)$ $(p,g_{p})$ $SymDec$

Pojďme vypočítat , a , kde . $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))$

Vypočítat $M':=SymDec(G(R'),C_{2}).$

Zkontrolujme, zda platí následující rovnice: . $C=g^{R'}h^{H(M'\paralelní R')}{\text{ mod }}n$

Je-li výraz pravdivý, vypíše se jako dešifrovaný prostý text. V opačném případě vypíšeme nulový řetězec. $M'$

Poznámky

↑ 1 2 T. Okamoto; S. Uchiyama, 1998 , str. jeden.
↑ Katja Schmidt-Samoa, 2006 .
↑ T. Okamoto; S. Uchiyama, 1998 , str. 2-3.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , str. 3-4.
↑ Prof. Jean-Jacques Quisquater, Math RiZK, 2002 , str. 8-11.
↑ 1 2 E. Brickell, D. Pointcheval, S. Vaudenay, M. Yung, 2000 .
↑ W. DIFFIE AND ME HELLMAN, 1976 .
↑ T. Elgamal, 1985 .
↑ T. Okamoto; S. Uchiyama, 1998 , str. 5.
↑ T. Okamoto; S. Uchiyama, 1998 , str. čtyři.
↑ T. Okamoto; S. Uchiyama, 1998 , str. 3-4.
↑ Maxwell Krohn, 1999 , s. 53.
↑ Bellare, M., Desai, A., Pointcheval, D. a Rogaway, P., 1998 .
↑ 1 2 3 T. Okamoto; S. Uchiyama, 1998 , str. 5.
↑ 1 2 3 NTT Corporation, 2001 , str. 7.
↑ NTT Corporation, 2001 , str. 9-10.

Literatura

Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. Bezpečná integrace asymetrických a symetrických šifrovacích schémat . — 1999.
W. DIFFIE A JÁ HELLMAN. Nové směry v kryptografii . — 1976.
Maxwell Krohn. K definicím kryptografické bezpečnosti : Přehodnocený útok na vybraný šifrový text . — 1999.
T. Elgamal. Šifrovací systém s veřejným klíčem a schéma podpisu založené na diskrétních logaritmech . — 1985.
Laboratoře platformy pro sdílení informací NTT, NTT Corporation. Specifikace EPOC-2 . - 2001. - S. 7-10 .
Tatsuaki Okamoto Shigenori Uchiyama Eiichiro Fujisaki. EPOC: Efektivní pravděpodobnostní šifrování veřejného klíče . - 1998. - S. 1-12 .
Hodnotitel: Prof. Jean-Jacques Quisquater, Math RiZK, poradenství; Vědecká podpora: Dr. François Koeune, K2Crypt. Hodnocení bezpečnosti šifrovacího schématu . — 2002.
E.Brickell, D.Pointcheval, S.Vaudenay, M.Yung. Ověření návrhu pro schémata podpisu založená na diskrétním logaritmu . - 2000. - S. 276-292 .
Bellare, M., Desai, A., Pointcheval, D. a Rogaway, P. Relations Among Notions of Security for Public-Key Encryption Schemes, Proc. of Crypto'98, LNCS 1462, Springer-Verlag, (anglicky) . - 1998. - S. 26–45 .
Katja Schmidt Samoa. Nová permutace poklopových dveří typu Rabin ekvivalentní faktoringu . - 2006. - S. 86–88 .